KIT | KIT-Bibliothek | Impressum | Datenschutz

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

Sanders, Peter; KIT | Webcast [Hrsg.]

  • 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
Open Access Logo


Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Audio & Video
Publikationsdatum 04.02.2019
Erstellungsdatum 04.02.2019
DOI 10.5445/DIVA/2019-121
Identifikator KITopen-ID: 1000116309
Serie Algorithmen II, Vorlesung, WS 2018/19
Lizenz KITopen-Lizenz
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page