Randomisierte Algorithmik
Betreuung: Thomas Bläsius, Maximilian Katzmann, Hans-Peter Lehmann, Peter Sanders, Stefan Walzer
In der Vorlesung geht es darum, zu verstehen, wann und warum Randomisierung zur Lösung eines algorithmischen Problems nützlich oder notwendig ist. Dabei werden zentrale Entwurfsmethoden und Analysewerkzeuge der randomisierten Algorithmik erklärt und trainiert wie randomisierte Algorithmen und Datenstrukturen zur Lösung eines Problems entworfen werden können und welche Werkzeuge sich für die Analyse der Ansätze eignen.
Ilias-Kurs für Abgabe der Übungsblätter, Discord-Link, etc.
Teile der Vorlesung werden auch im Skript der Vorgängerveranstaltung behandelt, aber nicht alle.
Ablauf
Es gibt zwei wiederkehrende Termine:
- wöchentlich Donnerstags 11:30 - 13:00, Raum 236 (typischerweise Vorlesung)
- zwei-wöchentlich Dienstags 08:00 - 09:30, Raum 236 (typischerweise Übung)
Die erste Woche bildet hierbei eine Ausnahme!
| Woche | Dienstag | Donnerstag |
|---|---|---|
| 1 | 2023-10-24: Vorlesung 1 | 2023-10-26: Übung 1 |
| 2 | 2023-11-02: Vorlesung 2 | |
| 3 | 2023-11-07: Übung 2 | 2023-11-09: Vorlesung 3 |
| 4 | 2023-11-16: Vorlesung 4 | |
| 5 | 2023-11-21: Übung 3 | 2023-11-23: Vorlesung 5 |
| 6 | 2023-11-30: Vorlesung 6 | |
| 7 | 2023-12-05: Übung 4 | 2023-12-07: Vorlesung 7 |
| 8 | 2023-12-14: Vorlesung 8 | |
| 9 | 2023-12-19: Übung 5 | 2023-12-21: Vorlesung 9 |
| 10 | 2024-01-11: Vorlesung 10 | |
| 11 | 2024-01-16: Übung 6 | 2024-01-18: Vorlesung 11 |
| 12 | 2024-01-25: Vorlesung 12 | |
| 13 | 2024-01-30: Übung 7 | 2024-02-01: Gemischte Session |
| 14 | 2024-02-08: Inverted-Classroom Session | |
| 15 | 2024-02-13: Inverted Classroom Session | 2024-02-15: Zusammenfassung + Fragen |
Vorlesung
Hier erscheinen die Foliensätze der Vorlesungen
- Overview & The Power of Randomness: mit Klicks, ohne Klicks
- Probability Amplification: mit Klicks, ohne Klicks
- Coupling & Erdős-Rényi Random Graphs: mit Klicks, ohne Klicks (Update 09.11. - 15:15 - Herleitung der Coupling Inequality korrigiert)
- Concentration: mit Klicks, ohne Klicks (Update 08.02. - 16:30 - Fehlende Folien in “ohne Klicks” ergänzt)
- Nachtrag zum Coupling im Konzentrationsbeweis: ohne Klicks
- Probabilistic Method: mit Klicks, ohne Klicks (Update 23.11. 14:30 – Beispiel mit Abhängigkeiten und Ungleichheitszeichen korrigiert)
- Continuous Probability Spaces & Random Geometric Graphs: mit Klicks, ohne Klicks (Update 05.12. 16:00: Integration durch Substitution, Kettenregel für bedingte Dichtefunktionen und Torus-Distanz korrigiert)
- Bounded Differences & Geometric Inhomogeneous Random Graphs: mit Klicks, ohne Klicks (Update 07.12. 13:30 – Doppelte Quantifizierung in Lipschitzbedingungen korrigiert)
Vollständiger Foliensatz
Ohne Klicks (50 MB).
Übungen
Hier erscheint das Material zu den Übungen
Übungsblätter
Übungsblätter können jeweils bis zum Donnerstag vor der nächsten Übung über den Ilias-Kurs abgeben werden.