Vorlesung 05: Algorithmen und Datenstrukturen SS 2021

Dies ist die Aufzeichnung der Vorlesung 5 der Lehrveranstaltung "Algorithmen und Datenstrukturen" gehalten am 18. Mai 2021 von Prof. Dr. Hannah Bast an der Universität Freiburg.

Die Themen waren: Universelles Hashing (30 Minuten) + Crashkurs Wahrscheinlichkeitsrechnung (30 Minuten) + Klassen von Hashfunktionen (20 Minuten) + Histogramme für das Ü5 (20 Minuten)

Sprungmarken:

Sprungmarken:
0:00 : Begrüßung, Erfahrungen mit dem Übungsblatt 4, Freitagstutorate, Blick über die Vorlesung
11:50 : Nachteile fixer Hashfunktionen
15:19 : Universelles Hashing, Grundidee
20:47 : Hashing durch zufälliges Werfen
22:11 : Wahrscheinlichkeitsräume und Ereignisse
30:10 : Zufallsvariablen und Erwartungswerte
50:35 : Verteilung bei zufälligem Werfen
57:24 : Universelles Hashing, Ziel und formale Definition, c-Universalität
1:10:12 : Erwartungswert der Anzahl der Kollisionen
1:19:10 : Verschiedene Beispielklassen von Hashfunktionen
1:41:57 : Histogramme
2:00:26 : Epilog, Fragen

Link zur Homepage der Veranstaltung mit allen Materialien
http://ad-wiki.informatik.uni-freiburg.de/teaching/AlgoDatSS2021

Link zur Homepage der Professur:
https://ad.informatik.uni-freiburg.de