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

Autor

Hofheinz. Dennis, Christoph Striecks

Beteiligtes Institut

Institut für Theoretische Informatik (ITI)

Genre

Vorlesung

Beschreibung

12: Vorlesung und Übung |
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?

Übung
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

Laufzeit (hh:mm:ss)

01:26:04

Serie

Algorithmen 1, Vorlesung und Übung, SS 2015

Publiziert am

03.12.2015

Fachgebiet

Informatik

Lizenz

KITopen-Lizenz