KIT | KIT-Bibliothek | Impressum | Datenschutz

04: Algorithmen II, Vorlesung und Übung, WS 2018/19, 23.10.2018

Sanders, Peter; Hespe, Demian; KIT | Webcast [Hrsg.]

  • 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 Radix-Heaps
  • 0:42:31 Übung
  • 0:42:36 Amortisierte Analyse
  • 0:52:53 Legende
  • 0:54:44 Fibonacci Heaps - Insert
  • 0:56:45 Fibonacci Heaps - Delete Min
  • 1:08:31 Fibonacci Heaps - Decrease Key


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