Algorithmen 2, Vorlesung, WS18/19

10 | 0:00:00 Start 0:00:39 Preflow-Push Algorithms 0:02:02 Level Funktion 0:05:36 Example 0:06:50 Pratial Correctness 0:13:09 Lemma 4. 0:16:18 Lemma 5. 0:21:08 Lemma 6. 0:23:11 Lemma 7. 0:23:34 Lemma 8. 0:26:09 Lemma 9. 0:32:41 Searching for Eligable Edges 0:37:49 Satz 11. 0:40:06 FIFO Preflow push 0:41:52 Highest Level Preflow Push 0:45:18 Example 0:51:22 Übung 4 0:51:56 Flüsse und Ford Fulkerson 0:55:48 Residualgraph 1:02:15 Max Flow - Min Cut 1:04:59 Dinitz Algorithmus

09 | 0:00:00 Start 0:00:09 Ford Fulkerson - Correctness 0:00:46 Ford Fulkerson Algorithm 0:08:49 Max-Flow-Min-Cut theorem 0:11:18 A bad example for Ford Fulkerson 0:13:25 Dinitz Algorithm 0:18:35 Dinitz-Correctness 0:21:22 Computing blocking flows 0:27:46 Blocking flows analysis 0:33:40 Dinitz analysis 0:40:55 Matching 0:43:54 Maximum cardinality bipartite matching 0:46:31 Similar performance for weight graphs? 0:50:06 Disadvantage of augmenting paths algorithms 0:52:10 Pre-flow-push...

08 | 0:00:00 Start 0:00:05 Augmenting Paths 0:01:56 Ford Fulkerson Algorithm 0:07:57 Some Basic Observations 0:14:57 Blocking Flows 0:16:44 Suche in Graphen 0:20:19 Dijkstras Algorithmus 0:28:30 A*-Suche 0:31:31 A*-Suche – Potentialfunktionen 0:37:23 A*-Suche – Landmarken 0:47:01 Starke Zusammenhangskomponenten 1:00:07 Floyd Warshall: SCC als Speedup Technik

07 | 0:00:00 Start 0:00:37 Tiefensuchschema 0:01:14 Starke Zusammenhangskomponenten 0:02:21 Schrumpfgraph 0:02:55 Konkreter: SCCs mittels DFS 0:04:04 Invarianten von G 0:05:58 Lemma: Abgeschlossene SCCs von G sind SCCs von G 0:06:14 Repräsentation offener Komponenten 0:13:24 Beispiel 0:24:48 Zusammenfassung: SCC Berechnung 0:26:22 2-zusammenhängende Komponenten 0:29:06 Mehr DFS-basierte Linearzeitalgorithmen 0:31:56 Maximum Flows and Matching 0:33:06 Definitions: Network 0:34:38...

06 | 0:00:00 Start 0:02:23 Anwendungen von DFS 0:06:45 DFS Nummerierung 0:09:51 Starke Zusammenhangskomponenten 0:17:07 Abstrakter Algorithmus 0:21:45 Auswirkungen einer neuen Kante e auf Gc, (Gc)s 0:28:56 Invarianten von Gc 0:34:11 Repräsentation offener Komponenten 0:46:37 Spezielle Priority Queues 0:51:13 Bucket Queues 0:57:25 Radix Heaps 1:20:25 Average case Analyse für MST

05 | 0:00:00 Start 0:00:08 Kürzeste Wege 0:02:50 Allgemeine Definition 0:03:01 Monotone ganzzahlige Prioritätslisten 0:04:23 Laufzeit Dijkstra mit Bucket-Queues 0:05:13 Radix-Heaps 0:07:25 Radix Heap: deleteMin 0:09:39 Beispiel 0:14:16 Laufzeit Dijkstra mit Radix-Heaps 0:16:21 Lineare Laufzeit für zufällige Kantengewichte 0:18:53 Änderung im Algorithmus für zufällige Kantengewichte 0:22:24 Analyse 0:28:29 All-Pairs Shortest Paths 0:33:59 Knotenpotenziale 0:40:25 Hilfsknoten 0:42:04...

04 | 0:00:00 Start 0:00:04 Dijkstra's Algorithmus: Pseudocode 0:00:39 Laufzeit 0:01:30 Laufzeit im Durchschnitt 0:02:05 Lineare Laufzeit für dichte Graphen 0:02:21 Satz 1 0:11:50 Präfixminima einer Zufallsfolge 0:14:11 Monotone ganzzahlige Prioritätslisten 0:17:38 Bucket-Queue 0:20:18 Operationen 0:24:46 Laufzeit Dijkstra mit Bucket-Queues 0:26:07 Radix-Heaps 0:29:28 Definition 0:32:05 Radix-Heap_invariante 0:36:38 Radix Heap: deleteMin 0:39:34 Buckets 0:41:40 Lufzwit Dijkstra mit...

03 | 0:00:00 Start 0:00:10 Algorithmics as Algorithm Engineering 0:01:26 Problem Instances 0:02:50 Example: Sorting Benchmark (Indy) 0:09:34 GraySort: 0:11:27 JouleSort 0:13:39 Applications that ""Change the world"" 0:22:09 Conclusion 0:24:17 More on experimental Methodology 0:29:48 Quality Criteria 0:36:53 Not here but important 0:37:57 The starting point 0:40:08 The Process 0:45:06 Of Risks and Opportunities 0:47:19 Fortgeschrittene Datenstrukturen 0:47:35...

Diese Lehrveranstaltung soll Studierenden die grundlegenden theoretischen und praktischen Aspekte der Algorithmentechnik vermitteln. Es werden generelle Methoden zum Entwurf und der Analyse von Algorithmen für grundlegende algorithmische Probleme vermittelt sowie die Grundzüge allgemeiner algorithmischer Methoden wie Approximationsalgorithmen, Lineare Programmierung, Randomisierte Algorithmen, Parallele Algorithmen und parametrisierte Algorithmen behandelt.

02 | 0:00:00 Start 0:01:39 Fortgeschrittene Datenstrukturen 0:03:10 Adressierbare Prioritätslisten 0:07:41 Grundlegende Datenstruktur 0:11:23 Pairung Heaps 0:23:14 Fibonacci Heaps 0:25:26 Repräsentation 0:26:22 deleteMin mit Union-by-Rank 0:27:23 Schnelles Union-by-Rank 0:30:49 Amortisierte Analyse von deleteMin 0:36:19 Schnelles Union-by-Rank 0:38:10 Warum ist maxRank logarithmisch? 0:40:10 Kaskadierende Schnitte 0:45:36 Auftritt Herr Fibonacci 0:51:52 Addressable Priority Queues:...