03: Algorithmen II, Vorlesung, WS 2019/20, 21.10.2019

03 | 0:00:00 Start 0:00:05 2 Fortgeschrittene Datenstrukturen 0:00:27 2.1 Adressierbare Prioritätslisten 0:01:45 Wälder Bearbeiten 0:02:10 Pairing Heaps 0:03:06 Fibonacci Heaps 0:05:01 Amortisierte Analyse von deleteMin 0:08:48 Warum ist maxRank logarithmisch? – Binomialbäume 0:11:41 Kaskadierende Schnitte 0:17:29 Auftritt Herr Fibonacci 0:18:57 Beweis: 0:23:56 Addressable Priority Queues: Mehr 0:27:47 Fortgeschrittene Graphenalgorithmen; 3 Kürzeste Wege 0:29:56 Allgemeine Definitionen 0:33:14 Dijkstra's Algorithmus: Pseudocode 0:35:35 Beispiel 0:37:04 Laufzeit 0:41:31 Laufzeit im Durchschnitt 0:49:55 Lineare Laufzeit für dichte Graphen 0:59:50 Präfixminima einer Zufallsfolge 1:02:15 Monotone ganzzahlige Prioritätslisten 1:08:41 Bucket-Queue 1:10:47 Operationen 1:13:53 Laufzeit Dijkstra mit Bucket-Queues