Algorithmen 1, SS2019, Vorlesung Karlsruher Institut für Technologie (KIT)

23 |
0:00:00 Start
0:00:13 Übung: Überblick
0:03:26 Dijkstras Algorithmus
0:07:19 Bellmann Ford Algorithmus
0:14:50 Minimale Spannbäume
0:20:31 Steinerbäume
0:27:20 Problem des Handlungsreisenden (TSP)

22 |
0:00:00 Start
0:00:23 Generische Optimierungsansätze
0:05:36 Rucksackproblem
0:09:28 Maximierungsprolem
0:12:42 Black-Box-Löser
0:17:38 Lineare Programmierung
0:24:53 Kürzeste Wege
0:29:29 Tierfutter
0:35:21 Algorithmen und Implementierungen
0:39:09 Ganzzahlige Lineare Programmierung
0:53:05 Greedy-Algorithmen
1:00:00 Dynamische Programmierung
1:17:32 Algorithmenentwurf mittels dynamischer Programmierung
1:23:01 Systematische Suche

21 |
0:00:00 Start
0:00:10 Rückblick
0:01:58 Heutige Vorlesung
0:03:31 Minimale Spannbäume
0:08:34 MST-Kanten auswählen und verwerfen
0:22:22 Jarnik-Prim-Algorithmus
0:37:10 Analyse - Jarnik-Prim-Algorithmus
0:38:04 Kruskals-Algorithmus
0:45:14 Kruskals Algorithmus - Korrektheit
0:49:51 Union-Find Datenstruktur
1:03:25 Pfadkompression
1:08:34 Union by Rank
1:10:11 Analyse - nur Union by Rank
1:11:33 Analyse - nur Pfadkompression
1:12:05 Analyse - Pfadkompression und Union by Rank
1:15:21 Ackermannfunktion - Beispiele
1:15:44 Kruskal mit Union-Find
1:21:09 Vergleich Jarnik-Prim vs. Kruskal
1:23:00 Mehr MST-Algorithmen
1:25:11 Zusammenfassung

20 |
0:00:00 Start
0:01:21 Kürzeste Wege: Definition
0:02:23 Dijkstras Algorithmus. Pseudocode
0:08:12 Dijkstra: negative Kantengewichte
0:17:02 Monotone ganzzahlige Prioritätslisten
0:19:49 Negative Zyklen
0:21:55 Zurück zu Basiskonzepten
0:26:31 Allgemeines Korrektheitskriterium
0:31:09 Bellman-Ford-Algorithmus
0:39:29 Beispiel
0:43:57 Bellman-Ford: Laufzeit
0:45:30 Azyklische Graphen
0:49:38 Von überall nach überall
0:52:15 Kürzeste Wege: Zusammenfassung
0:57:10 Exkurs: Routing in Straßennetzwerken
1:01:56 Ideen für Routenplanung
1:03:47 Ansatz: Transit-Node Routing
1:09:15 Zweite Beobachtung
1:17:04 Offene Fragen
1:18:36 Minimale Spannbäume (MST)
1:23:59 Minimal aufspannende Wälder (MSF)

19 |
0:00:00 Start
0:00:11 Rückblick: Kürzeste Wege
0:02:00 Dijkstras Algorithmus
0:02:54 Allgemeine Definition
0:07:38 Kante relaxieren
0:13:02 Dijkstras Algorithmus: Pseudocode
0:16:44 Beispiel
0:23:52 Korrektheit
0:37:29 Implementierung
0:40:10 Prioritätsliste
0:46:50 Beispiel
0:49:18 Dijkstra: Laufzeit
0:58:32 Analyse im Mittel
0:59:32 Monotone ganzzahlige Prioritätslisten
1:01:18 Negative Kosten
1:03:38 Zurück zu Basiskonzepten
1:06:34 Allgemeines Korrektheitskriterium
1:08:46 Bellman-Ford Algorithmus

18 |
0:00:00 Start
0:07:02 Graph-Traversierung
0:11:13 Breitensuche
0:13:13 Tiefensuche
0:21:56 DFS-Baum
0:28:14 DFS-Nummerierung
0:38:39 Topologische Sortierung
0:43:27 Topologisches Sortieren mittels DFS
0:55:01 Begriff Zusammenhang
1:02:26 BFS vs DFS
1:07:16 Kürzeste Wege : Definition
1:17:22 Dijkstras Algorithmus