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