Termine
| Art | Wann | Wo | Beginn | LP | Dozent |
|---|---|---|---|---|---|
| V4 | Dienstag 10:15 - 11:45
Donnerstag 10:15 - 11:45 |
AVZ III / HS 1
AVZ III / HS 1 |
11. Oktober 2011 | 5 | Röglin |
| Ü2 | Mittwoch 12:30 - 14:00
Donnerstag 14:30 - 16:00 |
LBH / E.08
LBH / E.08
|
19. Oktober 2011 | 3 | Brunsch, Röglin |
Inhalt
Wir werden uns in dieser Vorlesung mit der Frage beschäftigen, wie wir Zufall
beim Entwurf und der Analyse von Algorithmen einsetzen und ausnutzen können. Dabei
werden wir zwei große Themenkomplexe behandeln.
- Zunächst werden wir uns mit randomisierten Algorithmen beschäftigen, also Algorithmen, die zufällige Entscheidungen treffen. Auf den ersten Blick mag es komisch erscheinen, Algorithmen zufällig handeln zu lassen, aber wir werden sehen, dass randomisierte Algorithmen für viele Probleme effizienter und einfacher sind als die besten bekannten deterministischen Algorithmen.
- Das zweite Thema, mit dem wir uns beschäftigen werden, ist probabilistische Analyse. Dabei geht es darum, das Verhalten von deterministischen oder randomisierten Algorithmen auf zufälligen Eingaben zu analysieren. Dies ist sinnvoll, da die klassische Worst-Case-Analyse, bei der man Algorithmen nur basierend auf ihrem schlimmsten Verhalten beurteilt, oft zu pessimistische Ergebnisse liefert.
Kenntnisse in Wahrscheinlichkeitstheorie sind für die Vorlesung nützlich, aber nicht notwendig, da sie wiederholt werden.
| Datum | Inhalt | Literatur |
|---|---|---|
| 11. Oktober | 1. Grundlagen
1.1 Diskrete Wahrscheinlichkeitsräume
1.2 Unabhängigkeit und bedingte Wahrscheinlichkeit |
Skript
Kapitel 1 in [MU05]
Kapitel 1 in [Kr05] |
| 13. Oktober | 1.3 Anwendungen
1.3.1 Verifikation von Matrixprodukten |
Skript
Kapitel 1 in [MU05]
Kapitel 10.2 in [MR95] |
| 18. Oktober | 1.3.2 Berechnung eines minimalen Schnittes |
Skript
Kapitel 1 in [MU05]
Kapitel 10.2 in [MR95] |
| 20. Oktober | 1.3.2 Berechnung eines minimalen Schnittes (Fortsetzung)
1.4 Zufallsvariablen und Erwartungswerte |
Skript
Kapitel 10.2 in [MR95]
Kapitel 2 in [MU05]
Kapitel 1 in [Kr05] |
| 25. Oktober | 1.4 Zufallsvariablen und Erwartungswerte (Fortsetzung)
1.4.1 Anwendung: Analyse von Quicksort |
Skript
Kapitel 2 in [MU05]
Kapitel 1 in [Kr05]
|
| 27. Oktober | 1.4.2 Anwendung: Hashing
1.4.3 Binomialverteilung und geometrische Verteilung |
Skript
Kapitel 2 in [MU05]
Kapitel 1 in [Kr05]
|
| 3. November | 1.4.4 Anwendung: Coupon Collector's Problem
1.5 Konzentration von Verteilungen
1.5.1 Markow- und Tschebyschew-Ungleichung
1.5.2 Anwendung: Bestimmung des Medians |
Skript
Kapitel 2 und 3 in [MU05]
|
| 8. November | 1.5.2 Anwendung: Bestimmung des Medians (Fortsetzung) |
Skript
Kapitel 3 in [MU05]
|
| 10. November | 2 Komplexitätstheorie für randomisierte Algorithmen
2.1 Rechnermodelle und Komplexitätsklassen
2.1.1 Probabilistische Rechnermodelle
2.1.2 Monte-Carlo- und Las-Vegas-Algorithmen
2.1.3 Komplexitätsklassen |
Skript
Kapitel 1 in [MR95]
|
| 15. November | 2.1.3 Komplexitätsklassen (Fortsetzung)
2.2 Untere Schranken für randomisierte Algorithmen
2.2.1 Spielbaumauswertung |
Skript
Kapitel 1 und 2 in [MR95]
|
| 17. November | 2.2.1 Spielbaumauswertung (Fortsetzung)
2.2.2 Das Min-Max-Prinzip |
Skript
Kapitel 2 in [MR95]
|
| 22. November | 2.2.3 Eine untere Schranke für Spielbaumauswertung
3 Chernoff-Schranken und randomisierte Lastverteilung
3.1 Chernoff-Schranken
3.1.1 Momenterzeugende Funktionen
3.1.2 Chernoff-Schranken für die Summe von Bernoulli-Zufallsvariablen |
Skript
Kapitel 4 in [MU05]
|
| 24. November | 3.1.3 Anwendungen
3.2 Randomisierte Lastverteilung |
Skript
Kapitel 4 und 5 in [MU05]
|
| 29. November | 3.2.1 Anwendung: Bucketsort
3.2.2 Auslastung der vollsten Kiste |
Skript
Kapitel 5 in [MU05]
|
| 1. Dezember | 3.2.3 Anwendung: Verwaltung einer Menge
3.2.4 Bloom-Filter
3.2.5 The Power of Two Choices |
Skript
Kapitel 5 in [MU05]
|
| 6. Dezember | 4 Markow-Ketten und Random Walks
4.1 Markow-Ketten
4.1.1 Anwendung: Randomisierter Algorithmus für 2-SAT |
Skript
Kapitel 7 in [MU05]
|
| 8. Dezember | 4.1.2 Anwendung: Randomisierter Algorithmus für 3-SAT |
Skript
Kapitel 7 in [MU05]
|
| 13. Dezember | 4.2 Eigenschaften von Markow-Ketten
4.2.1 Klassifikation von Zuständen
4.2.2 Anwendung: Gambler's Ruin Problem
4.2.3 Stationäre Verteilung |
Skript
Kapitel 7 in [MU05]
Kapitel 6 in [MR95]
|
| 15. Dezember | 4.3 Random Walks auf Graphen
4.3.1 Anwendung: Zusammenhangstest
4.3.2 Elektrische Schaltungen |
Skript
Kapitel 7 in [MU05]
Kapitel 6 in [MR95]
|
| 20. Dezember | 4.3.2 Elektrische Schaltungen (Fortsetzung)
4.3.3 Der Random Walk des Weihnachtsmanns |
Skript
Kapitel 6 in [MR95]
|
| 10. Januar | 5. Smoothed Analysis
5.1 Einführung |
Skript
Folien
|
| 12. Januar | 5.2 Rucksackproblem |
Skript
|
| 17. Januar | 5.2 Rucksackproblem (Fortsetzung)
5.3 2-OPT-Heuristik für das TSP |
Skript
|
| 19. Januar | 5.3 2-OPT-Heuristik für das TSP (Fortsetzung) |
Skript
|
| 24. Januar | 5.4 k-Means-Methode |
Folien
|
| 26. Januar | 6. Stable Marriage Problem |
Folien
Paper
|
| 31. Januar | 6. Stable Marriage Problem (Fortsetzung) |
Paper
|
Übungen
- Präsenzblatt (Besprechung in KW 42, keine Abgabe)
- Übungsblatt 1 (Besprechung in KW 43, Abgabe am 20.10. in der Vorlesung)
- Übungsblatt 2 (Besprechung in KW 44, Abgabe am 27.10. in der Vorlesung)
- Übungsblatt 3 (Besprechung in KW 45, Abgabe am 03.11. in der Vorlesung)
- Übungsblatt 4 (Besprechung in KW 46, Abgabe am 10.11. in der Vorlesung)
- Übungsblatt 5 (Besprechung in KW 47, Abgabe am 17.11. in der Vorlesung)
- Übungsblatt 6 (Besprechung in KW 48, Abgabe am 24.11. in der Vorlesung)
- Übungsblatt 7 (Besprechung in KW 49, Abgabe am 01.12. in der Vorlesung)
- Übungsblatt 8 (Besprechung in KW 50, Abgabe am 08.12. in der Vorlesung)
- Übungsblatt 9 (Besprechung in KW 2, Abgabe am 15.12. in der Vorlesung)
- Übungsblatt 10 (Besprechung in KW 3, Abgabe am 12.01. in der Vorlesung)
- Übungsblatt 11 (Besprechung in KW 4, Abgabe am 19.01. in der Vorlesung)
- Übungsblatt 12 (Besprechung in KW 5, Abgabe am 26.01. in der Vorlesung)
Literatur
Es gibt zwei Skripte, die zusammen den Inhalt der Vorlesung abdecken.
Die Inhalte der Kapitel 1 bis 4 basieren größtenteils auf den folgenden Büchern.
Die Bücher [MR95] und [MU05] sind im Lesesaal der Fachschaft verfügbar.
- [MR95] Rajeev Motwani und Prabhakar Raghavan. Randomized Algorithms.ISBN: 978-0521474658, Cambridge University Press, 1995.
- [MU05] Michael Mitzenmacher und Eli Upfal. Probability and Computing.ISBN: 978-0521835404, Cambridge University Press, 2005.
- [Kr05] Ulrich Krengel. Einführung in die Wahrscheinlichkeitstheorie und Statistik.ISBN: 978-3834800633, Vieweg+Teubner Verlag, 8. Auflage, 2005.