KIT | KIT-Bibliothek | Impressum | Datenschutz

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

Sanders, Peter; Lamm, Sebastian; Heuer, Tobias; Zentrum für Mediales Lernen (ZML) [Hrsg.]

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


Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Audio & Video
Publikationsdatum 21.10.2019
Erstellungsdatum 21.10.2019
Sprache Deutsch
DOI 10.5445/DIVA/2019-778
Identifikator KITopen-ID: 1000116940
Lizenz KITopen-Lizenz
Serie Algorithmen II, Vorlesung, WS 2019/20
Folge 3
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page