Algorithmen I, SS 2015, gehalten am 27.05.2015, Vorlesung 13 (+ Übung)

Autor

Henning Meyerhenke, Christoph Striecks

Beteiligtes Institut

Institut für Theoretische Informatik (ITI)

Genre

Vorlesung

Beschreibung

13: Vorlesung und Übung |

Vorlesung
00:00:08 Prioritätslisten
00:00:31 Prioritätslisten (priority Queues)
00:00:52 Prioritätslisten – Anwendungen
00:00:54 Binäre Heaps
00:01:54 Implizite Baum-Repräsentation
00:02:48 deletMin: Beispiel
00:02:54 Binärer Heap – Analyse
00:03:00 Beispiel: Binärer Heap – Konstruktion
00:03:01 Binärer Heap – Konstruktion
00:03:15 Ein nützlicher Rechentrick
00:03:18 Heapsort: Beispiel
00:03:22 Heapsort
00:04:03 Heapsort – Quicksort – Mergesort
00:04:28 Adressierbare Prioritätslisten
00:04:33 Adressierbare Prioritätslisten: Anwendungen
00:04:37 Adressierbare Binäre Heaps
00:05:15 Prioritätslisten: Zusammenfassung
00:05:48 Was haben wir jenseits von Prioritätslisten gelernt?
00:05:50 Sortierte Folgen
00:12:16 Statisch: Sortiertes Feld mit binärer Suche
00:17:26 Binäre Suche – Beispiel: k = 15
00:20:13 Dynamische Sortierte Folgen – Grundoperationen
00:21:13 Mehr Operationen
00:23:58 Noch mehr Operationen
00:25:43 Abgrenzung
00:28:52 Sortierte Folgen – Anwendungen
00:30:20 Anwendungsbeispiel: Best Fit Bin Packing
00:33:50 Binäre Suchbäume
00:36:54 Varianten, Bemerkungen
00:37:30 locate(k)
00:39:34 locate(k) – anderes Beispiel
00:40:00 Invariante von locate(k)
00:40:38 Ergebnisberechnung von locate(k)
00:41:25 Laufzeit von locate(k)
00:42:59 Naives Einfügen
00:44:45 Beispiel

Übung
00:44:45 Roadmap
00:46:28 Perfekter Binärbaum
00:53:13 (Max)Heap und Suchbaum
00:53:17 Perfekter Binärbaum
00:53:42 (Max)Heap und Suchbaum
00:55:21 Heapsort mit Max-Heap
00:55:25 (Max)Heap und Suchbaum
00:56:04 Heapsort
00:57:53 Heapsort mit Max-Heap
01:05:30 Adressierbare binäre Heaps
01:05:42 Anwendungsbeispiel
01:08:06 Adressierbare binäre Heaps

Laufzeit (hh:mm:ss)

01:11:14

Serie

Algorithmen 1, Vorlesung und Übung, SS 2015

Publiziert am

03.12.2015

Fachgebiet

Informatik

Lizenz

KITopen-Lizenz