Sect. 3: shortest paths - Application 3: fastest train connection
This is a modal window.
Das Video konnte nicht geladen werden, da entweder ein Server- oder Netzwerkfehler auftrat oder das Format nicht unterstützt wird.
Formale Metadaten
| Titel |
| |
| Untertitel |
| |
| Serientitel | ||
| Teil | 3 | |
| Anzahl der Teile | 12 | |
| Autor | ||
| Lizenz | CC-Namensnennung - Weitergabe unter gleichen Bedingungen 3.0 Deutschland: Sie dürfen das Werk bzw. den Inhalt zu jedem legalen Zweck nutzen, verändern und in unveränderter oder veränderter Form vervielfältigen, verbreiten und öffentlich zugänglich machen, sofern Sie den Namen des Autors/Rechteinhabers in der von ihm festgelegten Weise nennen und das Werk bzw. diesen Inhalt auch in veränderter Form nur unter den Bedingungen dieser Lizenz weitergeben. | |
| Identifikatoren | 10.5446/45127 (DOI) | |
| Herausgeber | ||
| Erscheinungsjahr | ||
| Sprache |
Inhaltliche Metadaten
| Fachgebiet | ||
| Genre | ||
| Abstract |
|
5
9
11
00:00
RichtungEreignishorizontWorkstation <Musikinstrument>ZeitrichtungVorzeichen <Mathematik>DatenmodellVertikaleKette <Mathematik>ZeitzoneWellenpaketGreen-FunktionTabelleAbfrageÜberschallströmungGraphRechenschieberGerichtete MengeKomplex <Algebra>SchlussregelPaarvergleichVorgehensmodellGewicht <Ausgleichsrechnung>Kondition <Mathematik>KreisbogenDienst <Informatik>StellenringFolge <Mathematik>ÄhnlichkeitsgeometrieInformationART-NetzZeichenketteZeichenvorratGlobale OptimierungComputervirusQuadratzahlDiagonale <Geometrie>NichtunterscheidbarkeitSystemprogrammierungDateiformatProzess <Informatik>SchnelltasteOrdnungsreduktionGeradeRechenwerkDickeMaß <Mathematik>MathematikProdukt <Mathematik>LogarithmusBitratePotenz <Mathematik>Reverse EngineeringFramework <Informatik>SchwellwertverfahrenRelation <Informatik>GewichtungSummierbarkeitAdditionMittelwertNumerisches VerfahrenParametersystemFunktion <Mathematik>MinimalgradGarbentheorieSchedulingNebenbedingungGrundraumAlgorithmusConstraint <Künstliche Intelligenz>Lösung <Mathematik>NP-hartes ProblemZugbeanspruchungInformationInternetAdditionPhysikalische GrößeParametersystemRechenwerkVorzeichen <Mathematik>Gewicht <Mathematik>MinimierungBerechnungZahlWort <Informatik>Algebraisch abgeschlossener KörperGRADEWegeproblemDickeCURRICULUM <Programm>Kürzester-Weg-ProblemAutomat <Automatentheorie>Gewichtete SummePfad <Mathematik>Puffer <Netzplantechnik>MomentenproblemLogarithmusMultiplikationMengeZielfunktionKanteAbfrageLängeEgo-ShooterSummeÄquivalenzExpect <Programm>Abteilung <Mathematik>ExponentInformationsmodellierungZahlenbereichBenutzerprofilART-NetzFörderverein International Co-Operative StudiesRichtungGerichteter GraphDatenerhebungAggregatzustandNegative ZahlDimension 3PhysikTotal <Mathematik>e <Zahl>DatenbusVerträglichkeit <Mathematik>ÄhnlichkeitsgeometrieMillisekundenbereichVersion <Informatik>EreignishorizontMaßstabZeichenketteGruppoidSystems <München>Matching <Graphentheorie>GleichungFreiheitsgradNoten <Programm>VertikaleBetrag <Mathematik>LinieFaktorisierungProzess <Physik>Objekt <Kategorie>Funktion <Mathematik>Kontextbezogenes SystemBiproduktKraftMathematikerVerschlingungAnwendungssoftwareLaufzeitModulCafé <Programm>AbstandInformatikNabel <Mathematik>Restriktion <Mathematik>Technische Zeichnung
Transkript: Deutsch(automatisch erzeugt)
00:00
Damit haben wir das Problem, sie wollen an Anführungszeichen Längen nicht addieren, sondern sie wollen sie multiplizieren und dank dem Logarithmus kann man das problemlos zurückführen auf die Addition von Werten anstelle der Multiplikation von Werten.
00:29
So, den vielleicht ein bisschen höher, langsam entwickle ich Ehrgeiz beim Fotografieren. So, die Ergebnisse entsprechen nicht dem Ehrgeiz.
00:48
Gut, aber sie sind lesbar. Gut, und wenn Sie jetzt nicht nur den kürzesten Pfad haben wollen, sondern auch die Gesamtlänge, ja gut, dann entweder nehmen Sie sich die Austauschraten entlang dieses Pfades her nochmal und multiplizieren Sie.
01:03
Oder Sie nehmen das Ergebnis und exponentieren das, sollten Sie bis auf numerische Fehler auf dasselbe rauskommen. So, das war es aber auch schon mit diesem Beispiel. Wie stehen wir mit der Zeit? Ein bisschen Zeit haben wir noch. Ich will jetzt einen kleinen Zwischenschritt machen und auf kürzeste Wege Probleme zu sprechen kommen, in
01:24
denen es nicht nur ein Kriterium gibt, sondern mehrere Kriterien, die man irgendwie zugleich miteinander behandeln sollte. Sie kennen das vom Fahrplan gebundenen öffentlichen Verkehr, Bahn, Bus, ja, Bahn vor allem.
01:43
Sie haben mehrere Kriterien. Ein Kriterium ist die Fahrzeit. Was Sie minimieren wollen, Sie wollen natürlich nicht unnötig lange fahren. Zweites Kriterium ist der Fahrpreis, was bei Geschäftsleuten sicherlich weniger wichtig
02:03
ist, aber bei Studierenden, wenn sie privat fahren, sicherlich besonders wichtig ist. Drittes Kriterium, was man nicht außer achten lassen sollte, ist die Bequemlichkeit im weitesten Sinne. Ja, da gehen die Anzahl der Umstiege ein und auch die Zeit, die Pufferzeit, die man Umstieg hat.
02:20
Denken Sie an eine alleinreisende alte Dame mit zwei schweren Koffern. Dann bekommen Sie ein Gefühl dafür, dass Bequemlichkeit durchaus ein wichtiges Kriterium ist für viele Reisende. Mindestens diese drei Kriterien haben Sie und dementsprechend ergeben sich auch Kundenprofile.
02:42
Naja, wir hatten das, als ich von Berlin nach Konstanz gezogen bin, von der TU Berlin an die Uni Konstanz. Da sind auch ein paar Studierende mitgekommen und einer hat das wirklich konsequent jedes Wochenende gemacht,
03:04
dass er mit dem schönen Wochenendticket, damals konnte man mit dem schönen Wochenendticket noch zwei Tage fahren, Samstag und Sonntag, das glaube ich ist schon lange abgeschafft, dass er mit dem schönen Wochenendticket losgefahren ist,
03:24
sich fünf Stunden mit seiner Freundin getroffen hat und wieder zurückgefahren ist und damit war das Wochenende auch schon wieder zu Ende. Frühmorgens, Samstags losgefahren, spät abends, Sonntags zurückgekommen. Hauptsache, es war billig. Ja, schönes Wochenendticket war damals sogar auch noch sehr viel billiger als heute, sollte ich dazu noch sagen.
03:44
Dann gibt es, das ist ein extremes Kundenprofil. Ein anderes extremes Kundenprofil ist eben die alte, vielleicht reiche Dame mit zwei schweren Koffern. Na gut, wenn sie reich ist, kann sie sich auch was anderes leisten, aber gut, also für die Fahrpreis nicht so wichtig ist
04:01
und Fahrzeit jetzt auch nicht so wichtig ist, die aber möglichst bequem reisen will, möglichst nicht in überfüllten Abteilen, möglichst wenig Umstiege und wenn Umstieg, dann mit schöner, langer Pufferzeit und so weiter. Das ist ein zweites Extrembeispiel eines Kundenprofils. Ein drittes Extrembeispiel eines Kundenprofils wäre der eilige Geschäftsmann, die eilige Geschäftsfrau.
04:23
Geld spielt fast keine Rolle, Hauptsache, die Fahrzeit minimiert, Bequemlichkeit ist auch nicht so wichtig. Hauptsache, die Fahrzeit minimiert, damit man von einem Termin zum anderen noch rechtzeitig kommt. Die meisten Leute werden sicherlich eher so ein Mischprofil haben, dass sie zwar gerne die Fahrkosten minimieren,
04:43
aber sich das jetzt mit dem schönen Wochenendticket, was ich skizziert habe, jetzt soweit doch nicht antun, wenn sie schon von Konstanz nach Berlin fahren, dass sie dann ein reguläres Ticket hernehmen und in vernünftiger Zeit mit vernünftigen Zügen dann tatsächlich hin und her kommen und so weiter.
05:03
Sie haben für verschiedene Kundenprofile, wollen sie eigentlich Lösungen haben. Ein Resultat unserer Forschung ist ganz interessant. Für praktisch alle Anfragen, die so gestellt werden an Fahrplanauskunft der Bahn,
05:25
lassen sich eine einstellige oder kleine zweistellige Zahl von Verbindungen angeben, sodass wirklich sämtliche Kundenprofile, sowohl die extremen als auch die gemischten, abgedeckt sind. Sodass man jedem Kundenprofil, auch wenn man das Kundenprofil von demjenigen,
05:43
der die Fahrplanauskunft benutzt, überhaupt nicht kennt. Dass man trotzdem sagen kann, aus dieser kleine Auswahl lässt sich sagen, egal, lieber Kunde, was dein Profil ist, eine davon ist optimal für dich. Das ist doch eigentlich ein ganz interessantes Ergebnis, wenn man bedenkt,
06:00
dass theoretisch die Anzahl der möglichen, wenn man wirklich verschiedene Kundenprofile, so eine ganze Kontinuität, mehrdimensionale Kontinuität von Kundenprofilen abdecken will, dass man theoretisch eine exponentielle Anzahl von Verbindungen bräuchte. Im schlimmsten Fall. Aber der schlimmste Fall tritt nicht ein. Ganz im Gegenteil, irgendwas ist in den Daten drin von der Deutschen Bahn.
06:25
Irgendwas haben sie richtig gemacht, dass wirklich eine so kleine Anzahl von Verbindungsvorschlägen ausreicht, um für jedes Kundenprofil eine Optimallösung zu geben. So, aber wie geht man? Anderes Beispiel für Multi-Objective.
06:45
Ergibt sich beispielsweise ein Unternehmen, das natürlich Rendite machen will, muss. Auf der anderen Seite aber gerne Umwelt, was für die Umwelt tun will. Also zwei Zielkriterien, die man gegeneinander irgendwie in irgendeiner Form gewichten muss.
07:05
Gut, oft genug ist dann das zweite Kriterium dann eher nur bei der Marketing Abteilung angesiedelt, weniger dann bei der Produktion. Aber ein Beispiel dafür, dass wir zwei Kriterien haben,
07:21
die auch erst mal wieder zwei inkommensurable sind, nicht von vornherein miteinander vergleichbar sind. So, eine Möglichkeit ist natürlich, dass man jedem Kriterium ein Gewicht gibt
07:41
und diese Gewichte aufsummiert. Das sieht dann formal so aus, sie haben verschiedene Werte, die Fahrzeit, die Fahrkosten, die Bequemlichkeit, beziehungsweise mit dem umweltverträglichen Unternehmen, die Rendite und der Umweltnutzen oder die Minimierung des Umweltschadens,
08:03
oder wie man das definieren will. Man könnte natürlich daran denken, die einfach zu minimieren, aber das macht natürlich überhaupt keinen Sinn. Das wissen Sie aus der Physik, dass das keinen Sinn macht. Wenn verschiedene Größen unterschiedliche Einheiten haben,
08:21
dann addiert man die nicht, aus gutem Grund. Sondern, dass man dann halt geeignet gewählte Umrechnungsfaktoren hernimmt, mit denen man die jeweils gewichtet. Das wäre eine typische BWL-Sache bei dem Unternehmen mit der Naturverträglichkeit,
08:42
dass man den Naturschaden, den das Unternehmen produziert, in Euro ausdrückt, wie auch immer man das macht. Und dann kann man das mit der Rendite verrechnen, weil man beide auf dieselbe Einheit gebracht hat, indem man nämlich Umweltschaden als Schaden pro Euro oder als Umrechnungsfaktor hernimmt.
09:03
Oder, das wird auch bei der Bahn gemacht, Kundenprofile, nämlich, wenn Sie Fahrzeit und Fahrkosten näher nehmen, dann können Sie nur die beiden, dann können Sie den Kundenprofil auch ausdrücken in einer Relation, wie viel ist es Ihnen wert,
09:23
einen bestimmten Zeitbetrag einzusparen. Ein Umrechnungsfaktor Zeit wert. Wie viel Zeit ist Geld? Wie viel Geld ist Ihnen Zeit wert? Der eilige Geschäftsmann, die eilige Geschäftsfrau wird da einen anderen Wert haben als Sie,
09:41
wenn Sie wirklich zu dieser Extremistenfraktion gehören, die mit einem schönen Wochenendicket von Konstanz nach Berlin reisen, beziehungsweise, es muss ja nicht ganz so extremistisch sein, wenn Sie eben kostenbewusst Ihren Fahrpreis wählen und dann bereit sind eben nicht mit dem IC zu fahren, sondern mit diversen S-Bahnen und Regionalbahnen.
10:05
Das sind solche konkreten Beispiele für solche Umrechnungsfaktoren. So könnte man das machen, dass man ein Kundenprofil in so eine gewichtete Summe reinbringt, ist natürlich hoffnungslos, wenn Sie mit Endkunden zu tun haben.
10:22
Also was können Sie machen in innerbetrieblichen Prozessen? Da mag es nicht immer, aber oft genug macht das Sinn. Aber Sie können natürlich von keinem Kunden der Fahrplanauskunft und egal ob im Internet oder am Automaten verlangen, dass er Ihnen solche Umrechnungsfaktoren gibt, dass er sich sein Kundenprofil in Form von solchen Umrechnungsfaktoren
10:45
Ihnen dann definiert. Ganz abgesehen davon, dass es wahrscheinlich auch einen Aufschrei gäbe, wenn die Bahn beim Fahrplanauskunft, bei Reiseauskunft abfragen würde, wie viel Geld ist es Ihnen wert, eine Stunde kürzer zu fahren oder sowas. Ja, das käme sicherlich nicht gut in der Presse.
11:07
Anderes Beispiel ist, da werden Sie dann auch auf dem Übungsblatt mit konfrontiert sein. Auf dem Übungsblatt steht ganz konkret eine Aufgabe. Sie sollen in OPL spezifizieren.
11:26
Sie wollen eine billigste Verbindung unter der Bedingung, dass diese Verbindung, die Sie rauskriegen, nicht mehr als 30% mehr Zeit kostet gegenüber der schnellsten Verbindung.
11:44
War das jetzt zu schnell? Nein, nicht? So, das Problem an der Sache ist, beides zusammen in ein OPL-Modell zu stecken. Sie haben eigentlich zwei Kriterien. Sie haben eine Referenzverbindung, die schnellste Verbindung, von der Sie ablesen können, wie schnell geht es denn prinzipiell.
12:02
Und Sie wollen nicht mehr als 30% zusätzliche Zeit haben. Und dann haben Sie noch eine Verbindung zu berechnen, wo Sie die minimalen Kosten berechnen wollen unter dieser Bedingung. Und beides in ein Minimals reinpacken. Das ist die Herausforderung bei dieser Aufgabe. Da kann ich gerne hier als Hinweis sagen.
12:23
So, das ist ein Beispiel dafür, dass man eben sagt, naja, ich will nicht mehr als 8 Stunden fahren, weil nach 8 Stunden tut mir mein Rücken weh. Also, ich will möglichst billig fahren, aber es darf nicht mehr als 8 Stunden Zeit kosten oder so etwas.
12:41
Das ist auch eine typische Art und Weise, wie man damit umgeht. Maximal 8 Stunden oder eben Differenz. Nicht mehr als 30% langsamer als die maximal schnellste Verbindung oder Percentage nicht mehr als 30% schlechter als die schnellste Verbindung.
13:02
So etwas. Wir haben zum Beispiel bei Fahrplanauskunft, bei Reiseauskunft so den Multi-Objective Case, also mehrere Zielsetzungen,
13:25
mehrere Zielfunktionen zu beachten. Wir können nicht vom Endkunden erwarten, egal wie wir vorgehen, dass er diese numerischen Parameter setzt,
13:42
die hier in diesen Ansätzen verlangt werden. Es gibt natürlich noch die Möglichkeit, das sehen Sie auch, dass das Fahrplanauskunftssystem, das System, was dahinter ist,
14:01
also auf jeden Fall, wenn Sie mit Bahncard fahren, kann ich Ihnen definitiv sagen, wird alles, was Sie jemals mit Ihrer Bahncard gemacht haben, von der Deutschen Bahn gespeichert. Das ist ja heutzutage jetzt kein Stein des Anstoßes mehr. In der NSA-Ära ist das jetzt irgendwas, was Sie eher langweilt, diese Information.
14:27
Und eine der Zielsetzungen dabei ist, zu versuchen, Ihr Kundenprofil einzuschätzen und eben solche numerischen Parameter dann zu schätzen, um zu versuchen, das hinzulenken auf Ihre Kundenpräferenzen,
14:46
ist momentan nicht, soweit ich weiß, nicht implementiert im Reiseauskunftssystem. Das ist noch in den Kinderschuhen. Vor allem gibt es ja auch dann solche Probleme. Sie benutzen die Bahncard sowohl für private Reisen als auch für Geschäftsreisen. Und als Geschäftsreisende sind Sie interessiert an möglichst schnellen Verbindungen.
15:01
Geld spielt wenig Rolle. Geld spielt praktisch keine Rolle, weil Sie auf Firmenkosten fahren. Und als Privatreisende mit derselben Bahncard haben Sie ein ganz anderes Kundenprofil. Da spielt Geld plötzlich eine wesentliche Rolle. Also Sie verstehen, da wäre noch eine ganze Menge Data-Mining-Forschungsarbeit zu leisten.
15:23
So, vielleicht noch zum Abschluss dieses Kapitels und zum Abschluss des heutigen Tages auch die Fachbegrifflichkeiten dazu, die Ihnen zumindest in BWL, vielleicht auch in anderen Kontexten, wieder über den Weg laufen würden.
15:45
Sie haben jetzt verschiedene Fahrverbindungen. Habe ich jetzt hier Beispiele eigentlich? Nee, habe ich nicht. Sie haben jetzt hier verschiedene Fahrverbindungen, Lösungsvorschläge, Verbindungsvorschläge vom System bekommen. Und das System kann von sich aus schon gewisse Fahrvorschläge herausfiltern,
16:05
von denen es weiß, die braucht es Ihnen als Endkunden gar nicht erst zu präsentieren, nämlich solche, die von anderen Lösungsvorschlägen, die das System auch berechnet hat, schon dominiert werden. Dominiert heißt beispielsweise, nur ein Beispiel zu nennen, Sie haben zwei Fahrverbindungen auf dieselbe Verbindungsanfrage hin berechnet.
16:25
Ihr System hat zwei Verbindungen berechnet. Beide brauchen 123 Minuten Fahrzeit, aber das eine kostet 50 Euro und das andere kostet 60 Euro. Beides selbe Fahrzeit, Unterschied in den Kosten, dann wissen Sie, die Teure von den beiden Verbindungen können Sie schon rausstreichen.
16:46
Ja, das ist das Grundprinzip. In jeder Zielsetzung mindestens so gut wie die andere Lösung. Und in einer Zielsetzung echt besser als das andere.
17:05
Dann sagt man, eine Lösung dominiert die andere. Und eine Lösung, die von keiner anderen Lösung dominiert wird, die nennt man Pareto optimal, im Gedenken an einen italienischen Mathematikerbetriebswirt usw.
17:23
Weiß nicht, was da so alles genau war. Nur, damit Sie die entsprechenden Begriffe, wenn sie Ihnen über den Weg laufen, dass Sie die einordnen können, bzw. umgekehrt, dass Sie diesen Stoff hier einordnen können in die entsprechenden Begrifflichkeiten, die Ihnen woanders über den Weg laufen.
17:44
Noch eine weitere Anwendung, zu der wir heute nur ein paar Worte sagen werden. Scheduling, da geht es jetzt nicht um kürzeste Wege, sondern um längste Wege. Ist aber kein Problem, da die Grafen hier a-zyklusch sind,
18:02
können wir auch längste Wege berechnen und nicht nur kürzeste Wege. Ja, mit Dijkstra können Sie keine längsten Wege berechnen. Weil, was heißt das überhaupt, ein längster Weg? Wenn der Weg durch den Zügel läuft, hat er sich nur verlängert. Und wenn er nochmal durch den selben Zügel läuft, hat er sich nochmal verlängert. Und wenn er nochmal durchläuft, hat er sich immer weiter verlängert.
18:23
Also, es ist überhaupt nicht klar, was ein längster Weg überhaupt ist. Und wenn Sie sagen, okay, ich will jetzt den längsten Weg haben, der durch keinen Zügel durchläuft, dann stehen Sie vor dem selben Problem, was wir schon mal angesprochen hatten,
18:40
einen kürzesten Weg mit negativen Zyklen. Das ist exakt dieselbe Situation, nur Vorzeichen umgedreht. Ist nicht mehr so effizient lösbar mit unseren Dijkstra oder Bellman-Ford oder Floyd Warshall und so weiter, sondern ist NP-schwer. Ich hatte schon mal gesagt, was das pragmatisch heißt.
19:02
NP-schwer, wenn eine Problemstellung, eine algorithmische Problemstellung NP-schwer ist, dann heißt das pragmatisch, Sie können für jeden Algorithmus, den Sie sich überhaupt nur ausdenken können, egal ob er von der Menschheit gefunden worden ist oder nicht, für jeden Algorithmus, der überhaupt nur ausdenkbar ist, finden Sie Beispiele von moderater Größe, 50 Knoten vielleicht,
19:27
auf denen dieser Algorithmus länger rechnet als das Universum dauert und auch länger als das nächste und das übernächste und so weiter Universum dauert, also richtig lange, also etwas mehr als nur sich einen Kaffee holen zwischendurch,
19:41
bis der Algorithmus zu Ende ist. Ich sollte etwas dazu sagen, das Thema NP-schwer und so, das ist ein Fehler in der Konstruktion unseres Curriculums hier an der TU Darmstadt in Informatik, war eigentlich für die GDI 2 vorgesehen, als wir damals auf Bachelor Master umgestellt hatten,
20:07
aber war dort auch ins Modulhandbuch eingetragen, aber die Dozenten der GDI 2, die damals die GDI 2 ausgerichtet haben, haben das alle ignoriert.
20:20
Ich habe das jetzt, als ich zweimal jetzt die GDI 2 ausgerichtet habe, dann entsprechend auch ignoriert, aber jetzt können wir es demnächst nicht mehr ignorieren. Jetzt müssen wir das Curriculum der ACM, der amerikanischen und auch weltweiten Informatik-Gesellschaft, umsetzen und das beinhaltet, dass wir irgendwo solche Sachen wie dieses NP-schwer unterbringen werden
20:42
und wir werden es in der GDI 2 unterbringen, wo es eigentlich schon geplant war. Das werde ich dann im nächsten Sommersemester dann implementieren. Gut, längste Wege geht es jetzt. Was ist Schedulink? Nur eine ganz kurze Vorstellung hier heute noch, was Schedulink ist.
21:04
Manche sprechen auch Schedulink aus, das gibt es in beiden Varianten im angelsächsischen. Sie haben beispielsweise ein großes Projekt, beispielsweise ein Bauprojekt. Und dieses Projekt, um darüber nachzudenken, zerlegen Sie das in Gedanken und auf Papier
21:22
und sonst wie zerlegen Sie es in viele kleine Teilprojekte, die in sich wieder unteilbar sind. Da können Sie den Grad der Granularität auch wählen. Sie können sagen, sämtliche Elektrik verlegen ist eine Aufgabe, ein Job, den sehe ich als unteilbar an.
21:41
Oder Sie können auch sagen, ich will einen feineren Grad an Granularität haben. Den Teilschritt bei Elektrik verlegen ist ein eigener Job, der Teilschritt ist ein eigener Job, der Teilschritt ist ein eigener Job und so weiter und so fort. Ja, das liegt dann an Ihren Zielsetzungen, welche Granularität Sie dann wählen bei der Beschreibung Ihres Projektes.
22:05
Und dann gibt es Restriktionen, es gibt erst einmal Reihenfolgerestriktionen. Sie können das Dach nicht bauen, bevor Sie die Wände nicht hochgezogen haben, sollten Sie jedenfalls nicht versuchen. Sie können die Wände nicht hochziehen, bevor Sie den Keller nicht gebaut haben und so weiter und so fort.
22:21
Solche Restriktionen, Reihenfolgebeziehungen, das, was bestimmt ist, erst angefangen werden kann, wenn was anderes oder viele andere Sachen schon fertig sind. Ressourcenbeschränkungen, wenn Sie nur einen Elektriker haben, dann kann der in jedem Moment nur eine Aufgabe für einen Elektriker durchführen.
22:42
Wenn Sie zwei Elektriker haben, können Sie die Aufgaben für Elektriker entsprechend parallelisieren, dass immer zwei Aufgaben gleichzeitig bearbeitet werden. Und wenn Sie nur einen Kran haben, dann können Sie keine zwei Aufgaben, die einen Kran brauchen, gleichzeitig oder zeitlich überlappend laufen lassen und so fort.
23:01
Das müssen Sie strikt sterilisieren und so weiter. Das sind so die ganzen Beschränkungen und was Sie wollen ist, Sie haben für jeden Job eine geschätzte Dauer, was das dauern wird. Darüber werde ich mich dann noch später im Laufe des Semesters ziemlich auslassen mit diesen geschätzten Dauern.
23:21
Also da werde ich so richtig leidenschaftlich, sorry. Ich hoffe, das war jetzt nicht zu verwirrend. Also Sie werden es dann einordnen können. Sie haben eine geschätzte Dauer. Sie haben diese ganzen Beschränkungen und unter diesen ganzen Einschränkungen wollen Sie das Projekt in möglichst kurzer Zeit durchführen.
23:41
Eine algorithmische Aufgabe. Wie wir das reduzieren können auf ein längstes Wegeproblem zum Teil reduzieren und was das bedeutet, das zum Teil zu reduzieren und was mit den anderen Teilen ist. Das werden wir uns dann beim nächsten Mal angucken. Vielen Dank für heute.