Randomisierte Algorithmik
- Typ: Vorlesung / Übung (VÜ)
- Semester: WS 24/25
-
Ort:
50.34 Raum 236
-
Zeit:
Di 09:45 - 11:15, 14-täglich
Do 11:30 - 13:00, wöchentlich - Dozent:
- SWS: 3
- LVNr.: 2400153
- Hinweis: Präsenz
Inhalt |
Randomisierte Algorithmen und Datenstrukturen machen ihr Vorgehen von Zufallsexperimenten abhängig. Während der Entwurf deterministischer Algorithmen oft von einer pessimistischen Sicht auf Worst-Case Verhalten getrieben ist, greifen randomisierte Algorithmen auf Ansätze zurück, die zwar gelegentlich versagen aber meistens wesentlich besser abschneiden. Die Laufzeit solcher Algorithmen sowie die Lösungsqualität (im Falle von Optimierungsproblemen) und manchmal auch die Korrektheit (im Falle von Berechnungsproblemen) sind dann dem Zufall unterworfen. Eine formale Analyse nimmt daher Erwartungswerte und Erfolgswahrscheinlichkeiten in den Blick. Wir werden uns sowohl klassischen Beispielen als auch aktuellen Forschungsthemen aus dem Bereich Hashing und der Graphentheorie widmen. Hierbei kommen spezifische Entwurfsmethoden (wie Probability Amplification) und fortgeschrittene Analysewerkzeuge der Wahrscheinlichkeitstheorie (etwa Coupling, Poissonisierung und Konzentrationsschranken) zur Anwendung. Oft wird sich zeigen, dass randomisierte Ansätze effizienter oder einfacher sind als alle (oder zumindest alle bekannten) deterministischen Ansätze. Kurz werden wir zudem auf theoretischer Seite betrachten, wie sich randomisierte Komplexitätsklassen zu bekannten Klassen wie P und NP verhalten, und auf praktischer Seite klären, wie man randomisierte Algorithmen auf gängigen (im Wesentlichen deterministisch arbeitenden) Computern mit Pseudozufall implementieren kann. |
Vortragssprache | Deutsch mit Englischen Folien |
Material zu Vorlesung und Übung
- Thema 0 (22.10): Basic Notions and Notation / Übungsblatt / Lösung
- Thema 1 (24.10): The Power of Randomness / Handout-Version / Übungsblatt / Lösung
- Thema 2 (31.10): Important Random Variables and how to Sample Them / Handout-Version / Übungsblatt / Lösung
- Thema 3 (31.10): Probability Amplification / Handout-Version / Übungsblatt / Lösung
- Thema 4 (7.11): Randomised Complexity Classes / Handout-Version / Übungsblatt / Lösung
- Thema 5 (14.11): Concentration Bounds / Handout-Version / Übungsblatt / Lösung
- Thema 6 (14.11): Classic Hash Tables / Handout-Version / Übungsblatt / Lösung
- Thema 7 (21.11): Bounded Differences and Bloom Filters / Handout-Version / Übungsblatt / Lösung
- Thema 8 (28.11): Coupling, Balls into Bins, Poissonisation and the Poisson Point Process / Handout-Version / Übungsblatt / Lösung
- Thema 9 (5.12): Approximation Algorithms / Handout-Version / Übungsblatt / Lösung
- Thema 10 (5.12): Streaming Algorithms / Handout-Version (kein Übungsblatt)
- Thema 11 (12.12): Game Theory & Yao’s Principle / Handout-Version / Übungsblatt / Lösung
- Thema 12 (19.12): Probabilistic Method / Handout-Version / Übungsblatt