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
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


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.