KIT | KIT-Bibliothek | Impressum | Datenschutz

Algorithmen I, SS 2015, gehalten am 20.05.2015, Vorlesung 12 (+ Übung)

Hofheinz. Dennis; Striecks, Christoph

  • 00:00:24 Prioritätslisten
  • 00:00:48 Prioritätslisten (priority queues)
  • 00:01:26 Prioritätslisten – Anwendungen
  • 00:01:48 Binäre Heaps
  • 00:03:33 Implizite Baum-Repräsentation
  • 00:04:56 Pseudocode
  • 00:06:07 Einfügen
  • 00:21:01 deleteMin: Beispiel
  • 00:23:49 Binärer Heap – Analyse
  • 00:25:16 Binärer Heap – Konstruktion
  • 00:29:12 Beispiel: Binärer Heap – Konstruktion
  • 00:30:01 Binärer Heap – Konstruktion
  • 00:34:46 Ein nützlicher Rechentrick
  • 00:37:57 Heapsort
  • 00:40:57 Heapsort: Beispiel
  • 00:42:27 Heapsort – Quicksort – Mergesort
  • 00:46:01 Adressierbare Prioritätslisten
  • 00:48:09 Adressierbare Prioritätslisten: Anwendungen
  • 00:49:50 Adressierbare Binäre Heaps
  • 00:51:35 Adressierbare Prioritätslisten – Laufzeiten
  • 00:52:16 Prioritätslisten: Mehr
  • 00:55:32 Prioritätslisten: Zusammenfassung
  • 00:55:50 Was haben wir jenseits von Prioritätslisten gelernt?
  • 00:56:17 Übung
  • 00:56:31 Roadmap
  • 00:56:50 Organisation
  • 00:57:12 Sortieren durch Mischen
  • 00:57:27 Merge Sort
  • 00:58:46 Tatsächliche Laufzeit einer Implementierung
  • 01:00:28 Quicksort – erster Versuch
  • 01:01:16 Quicksort – Analyse im schlechtesten Fall
  • 01:01:24 Schlechtester Fall: Beispiel
  • 01:01:50 Einige Quicksort-Analysen
  • 01:02:58 Vorgefertigte Sortieralgorithmen in aktuellen Programmiersprachen
  • 01:03:54 C++
  • 01:04:20 Java
  • 01:04:39 Dual Pivot Quicksort
  • 01:07:32 Partitionierung mit 2 Pivot
  • 01:12:21 Einige Quicksort-Analysen
  • 01:14:13 Kennzahlen der Vorsortiertet und adaptive Sortierverfahren
  • 01:14:17 Adaptives Sortieren
  • 01:20:14 Runs
  • 01:24:48 Adaptives Sortieren
Open Access Logo


Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Audio & Video
Publikationsdatum 03.12.2015
Erstellungsdatum 20.05.2015
DOI 10.5445/DIVA/2015-908
Identifikator KITopen-ID: 1000113548
Serie 12
Serie Algorithmen 1, Vorlesung und Übung, SS 2015
Lizenz KITopen-Lizenz
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page