08: Universelles Hashing, Sortieren durch Mischen

0:00:00 Start
0:00:12 Rückblick Vorlesung 07.05.
0:03:57 Analyse für zufällige Hash-Funktionen
0:10:12 Universelles Hashing
0:13:50 Eine einfache universelle Familie
0:22:36 Beispiele für H
0:25:13 Beweis Theorem
0:33:14 Sortieren & Co
0:36:47 Lochkartensortierer
0:41:28 Grundproblem Sortieren
0:45:33 Anwendungsbeispiele
0:47:49 Einfache Sortieralgorithmen
0:51:17 Sentinels am Beispiel Sortieren durch Einfügen
0:57:07 Analyse
1:00:25 Sortieren durch Mischen
1:03:33 Beispiel
1:05:00 Mischen
1:07:27 Analyse
1:11:24 Untere Schranken
1:13:49 Eine Vergleichsbasierte untere Schranke
1:16:51 Baumbasierte Sortierdarstellung
1:19:03 Beweis
1:22:16 Randomisierung, Mittlere Ausführungszeit
1:22:58 Quicksort – erster Versuch

Dozenten:
Prof. Dr. Carsten Sinz | Karlsruher Institut für Technologie (KIT), Institut für Theoretische Informatik

Vorlesungsaufzeichnung: KIT | WEBCAST