29: Algorithmen II, Vorlesung, WS 2018/19, 04.02.2019

Autor

Peter Sanders

Herausgeber

KIT | Webcast

Beteiligtes Institut

Institut für Theoretische Informatik (ITI)

Genre

Vorlesung

Beschreibung

29 |
0:00:00 Starten
0:00:10 Inhaltsübersicht
0:03:02 Rolle der Algorithmik
0:03:43 Machine Learning macht das von selbst
0:17:02 Algorithm Theory
0:21:47 Graphenalgorithmen
0:22:20 Laufzeit
0:26:50 Satz 1
0:29:13 Monotone ganzzahlige Prioritätslisten
0:30:15 Bucket Queue
0:33:27 Analyse
0:34:30 All-Pair Shortest Paths
0:35:09 Knotenpotentiale
0:36:07 Algorithmus
0:37:46 Landmarks
0:38:33 Zusammenfassung Kürzeste Wege
0:39:47 Fortgeschrittene Datenstrukturen
0:40:21 Adressierbare Prioritätslisten
0:41:04 Grundlegende Datenstruktur
0:42:44 Pairing Heaps
0:47:06 Union by Rank
0:49:25 Zusammenfassung Datenstrukturen
0:50:45 Anwendung von DFS
0:51:16 Starke Zusammenhangskomponenten
0:54:00 Repräsentation offener Komponenten
0:57:08 Zusammenfassung SCC Berechnung
0:57:34 2 zusammenhängende Komponenten
0:57:47 Mehr DFS basierte Linearzeitalgorithmen
0:58:25 Maximum Flows and Matchings
0:58:31 Definitions: Network
0:59:24 Duality between Flows and Cuts
1:00:01 Applications
1:00:27 Algorithms 1956-now
1:04:27 Residual Graph
1:06:27 Ford Fulkerson Algorithm
1:07:34 Max Flow Min Gut theorem
1:07:41 Bad Example for Ford Fulkerson
1:08:35 Blocking Flows
1:08:58 Dinitz Algorithm
1:09:52 Blocking Flow Analysis
1:11:20 Maximum Cardinality Bipartite Matching
1:13:09 Preflow Push Algorithms
1:14:45 Level Function
1:16:04 FIFO Preflow push
1:17:17 Timings
1:17:24 Zusammenfassung Flows and Matchings
1:17:57 Randomisierte Algorithmen
1:18:11 Here Fast SOace Efficient Hashing
1:18:50 Externe Algorithmen

Laufzeit (hh:mm:ss)

01:22:51

Serie

Algorithmen II, Vorlesung, WS 2018/19

Publiziert am

04.02.2019

Fachgebiet

Informatik

Lizenz

KITopen-Lizenz