Algorithmen 1, SS2019, Vorlesung

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

17 | 0:00:00 Start 0:00:05 Rückblick und Überblick 0:01:35 Graphen 0:02:12 Repräsentation von Graphen 0:02:33 Kantenfolgenrepräsentation 0:03:31 Adjazenzfelder 0:05:59 Kantenliste -> Adjazenzfeld 0:07:29 Adjazenzlisten 0:13:10 Customization (Zuschneiden) 0:13:53 Beispiel: DAG-Erkennung 0:23:23 Adjazenz-Matrix 0:31:24 Pfade zählen mittels linearer Algebra (LA) 0:35:54 Beispiel, wo Graphentheorie bei LA hilft 0:38:56 Implizite Repräsentation 0:40:53 Zusammenhangstest für Intervallgraphen 0:43:46 Beispiel 0:45:13 Graphpräsentation: Zusammenfassung 0:52:00 Graph-Traversierung 0:58:59 Breitensuche 1:07:32 Repräsentation des Baums 1:16:41 Repräsentation von Q und Q' mittels FIFO 1:19:17 Tiefensuche 1:24:26 DFS-Baum

16 | 0:00:00 Start 0:00:11 Wiederholung 0:11:16 Locate 0:19:22 Einfügen-Algorithmenskizze 0:50:36 Zusammenfassung 0:53:43 Graphen 0:58:43 Graphen-Anwendung 1:05:15 Operationen 1:10:05 Kantenfolgenrepräsentation 1:13:28 Adjazenzfelder

15 | 0:00:00 Start 0:00:08 Übungsblatt 7, Pseudocode 0:02:49 4. Übung 0:02:52 Roadmap, Bucket Sort Spezial, Bucket Queue, Binary Radix Heap 0:03:14 Erinnerung: Bucketsort 0:06:46 Bucket Sort Spezial 0:13:55 Spezielle Priority Queues 0:14:55 Bucket Queue 0:17:40 Binary Radix Heap 0:22:52 Binary Radix Heap: deleteMin 0:24:06 Binary Radix Heap 0:25:54 Möglichkeit Ternärer Radix Heaps

14 | 0:00:00 Start 0:00:05 Rückblick und Überblick 0:02:06 Sortierte Folgen 0:07:56 Statisch: Sortiertes Feld mit binärer Suche 0:18:14 Dynamisch sortierte Folgen 0:26:49 Abgrenzung 0:32:27 Sortierte Folgen - Anwendungen 0:46:39 Binäre Baumsuche 0:52:08 locate (k) 1:00:15 Laufzeit von locate (k) 1:03:05 Naives Einfügen 1:08:07 Naives Einfügen - Beispiel 1:11:25 Suchbäume balancieren 1:16:25 Items 1:20:24 Initialisierung 1:22:27 Locate