Randomisierte und Approximative Algorithmen (BA-INF 104)

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
Kapitel 1 in [MU05]
Kapitel 1 in [Kr05]
13. Oktober
1.3 Anwendungen
1.3.1 Verifikation von Matrixprodukten
Kapitel 1 in [MU05]
Kapitel 10.2 in [MR95]
18. Oktober
1.3.2 Berechnung eines minimalen Schnittes
Kapitel 1 in [MU05]
Kapitel 10.2 in [MR95]
20. Oktober
1.3.2 Berechnung eines minimalen Schnittes (Fortsetzung)
1.4 Zufallsvariablen und Erwartungswerte
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
Kapitel 2 in [MU05]
Kapitel 1 in [Kr05]
27. Oktober
1.4.2 Anwendung: Hashing
1.4.3 Binomialverteilung und geometrische Verteilung
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
Kapitel 2 und 3 in [MU05]
8. November
1.5.2 Anwendung: Bestimmung des Medians (Fortsetzung)
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
Kapitel 1 in [MR95]
15. November
2.1.3 Komplexitätsklassen (Fortsetzung)
2.2 Untere Schranken für randomisierte Algorithmen
2.2.1 Spielbaumauswertung
Kapitel 1 und 2 in [MR95]
17. November
2.2.1 Spielbaumauswertung (Fortsetzung)
2.2.2 Das Min-Max-Prinzip
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
Kapitel 4 in [MU05]
24. November
3.1.3 Anwendungen
3.2 Randomisierte Lastverteilung
Kapitel 4 und 5 in [MU05]
29. November
3.2.1 Anwendung: Bucketsort
3.2.2 Auslastung der vollsten Kiste
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
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
Kapitel 7 in [MU05]
8. Dezember
4.1.2 Anwendung: Randomisierter Algorithmus für 3-SAT
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
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
Kapitel 7 in [MU05]
Kapitel 6 in [MR95]
20. Dezember
4.3.2 Elektrische Schaltungen (Fortsetzung)
4.3.3 Der Random Walk des Weihnachtsmanns
Kapitel 6 in [MR95]
10. Januar
5. Smoothed Analysis
5.1 Einführung
12. Januar
5.2 Rucksackproblem
17. Januar
5.2 Rucksackproblem (Fortsetzung)
5.3 2-OPT-Heuristik für das TSP
19. Januar
5.3 2-OPT-Heuristik für das TSP (Fortsetzung)
24. Januar
5.4 k-Means-Methode
26. Januar
6. Stable Marriage Problem
31. Januar
6. Stable Marriage Problem (Fortsetzung)

Übungen


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.