Randomisierte Algorithmen
Wintersemester 2007/08
Beate Bollig
Termine
Die erste Vorlesung findet am 15. Oktober 2007 statt.
Der Übungsbetrieb beginnt in der zweiten Vorlesungswoche.
Inhalt
Randomisierte Algorithmen sind eine in den Anwendungen
nützliche Verallgemeinerung deterministischer Algorithmen, solange
die Wahrscheinlichkeit unerwünschter Verhaltensweisen wie zu lange
Rechenzeiten oder die Berechnung falscher Ergebnisse sehr gering ist.
Sie zeichnen sich häufig durch ihre Einfachheit und ihre Effizienz bei
der Lösung komplexer Aufgaben aus.
Randomisierte Algorithmen lassen sich bestimmten Entwurfsparadigmen zuordnen,
die manchmal mehr, manchmal weniger im Vordergrund des Entwurfs stehen,
beispielsweise:
- Überlisten des Gegners (Vermeiden von schlechten Fällen)
- Methode der Fingerabdrücke
- Wahrscheinlichkeitsverstärkung durch Wiederholungen
- Stichprobenmethode
- Methode der häufigen Zeugen
- Zufälliges Runden
Die Kenntnis dieser Entwurfsmethoden ist hilfreich
bei der gezielten Suche nach einem effizienten randomisierten Verfahren
für ein zu untersuchendes Problem.
In der Vorlesung behandeln wir den Entwurf und die Analyse randomisierter
Algorithmen.
Es werden keine tieferen Kenntnisse aus der Wahrscheinlichkeitstheorie
vorausgesetzt. Die entsprechenden Kenntnisse werden bei Bedarf in der Vorlesung anhand
von Anwendungen aus der Informatik entwickelt.
Literatur zur Vorlesung
Die Vorlesung richtet sich, wenn nicht anders angegeben, nach dem
Standardwerk zum Thema Randomisierte Algorithmen:
Rajeev Motwani, Prabhakar Raghavan (1995). Randomized Algorithms.
Cambridge University Press.
Eine gut lesbare Einführung in den Entwurf und die Analyse randomisierter
Algorithmen bietet das folgende Buch:
Juraj Hromkovic (2004). Randomisierte Algorithmen. Teubner Verlag.
Kapitel 1:
Für das Sekretärinnenproblem siehe:
Thomas Cormen, Charles Leiserson, Ronald Rivest und Clifford Stein (2001).
Introduction to Algorithms. Second Edition.
MIT Press.
Kapitel 2:
Für den randomisierten Miller-Rabin-Primzahltest siehe auch:
Martin Dietzfelbinger (2004). Primality Testing in Polynomial
Time. Springer Verlag.
Für die Generierung zufälliger Primzahlen siehe:
Juraj Hromkovic (2004). Randomisierte Algorithmen. Teubner Verlag.
Für das FBDD-Äquivalenzproblem siehe auch:
Uwe Schöning (1995).
Perlen der Theoretischen Informatik (Kapitel 14).
BI Wissenschaftsverlag.
Kapitel 3:
Für die Klassifikation randomisierter Algorithmen siehe auch:
Ingo Wegener (2003).
Komplexitätstheorie - Grenzen der Effizienz von Algorithmen.
Springer Verlag.
Kapitel 4:
Zum Thema Hashing siehe auch:
Juraj Hromkovic (2004). Randomisierte Algorithmen. Teubner Verlag.
Für das Recycling von Zufallsbits siehe auch:
Uwe Schöning (1995).
Perlen der Theoretischen Informatik (Kapitel 17).
BI Wissenschaftsverlag.
Kapitel 5:
Zum Thema Online-Algorithmen für das Seitenwechselproblem siehe auch:
Allan Borodin und Ran El-Yaniv (1998).
Online Computation and Competitive Analysis. Cambridge University Press.
Kapitel 6:
Leider existiert noch kein Lehrbuch über Sublineare Algorithmen.
Einen kurzen Überblick über das Gebiet Sublineare Algorithmen bietet:
Kapitel 6.1:
Einen guten Überblick über das Gebiet Property Testing im speziellen bieten:
- Fischer, E. (2001).
(Eldar Fischers Publikationen
)
The art of uninformed decisions. A primer to property testing.
Bulletin of the European Association for Theoretical Computer Science,
75:97-126.
- Ron, D. (2001).
(Dana Rons Publikationen
)
Property testing.
In Handbook of Randomized Algorithms. Kluwer Academic Publishers.
Originalliteratur:
- Bender, M.A., Ron, D. (2002).
Testing Properties of directed graphs: acyclicity and connectivity.
Random Struct. Algorithms 20 (2), 184-205.
- Goldreich, O., Goldwasser, S., Ron, D. (1998).
Property Testing and its connection to learning and approximation.
Journal of the ACM 45 (4), 653-750.
- Raskhodnikova, S. (2003).
Approximate testing of visual properties.
Approximation, Randomization, and Combinatorial Optimization
Algorithms and Techniques, LNCS 2764, 370-381.
Kapitel 6.2:
Originalliteratur:
Chazelle, B., Rubinfeld, R., Trevisan, L. (2001).
Approximating the minimum spanning tree weight in sublinear time.
ICALP, LNCS 2076, 190-200.
Externe Links
Für die Beispielalgorithmen für verschiedene Entwurfsparadigmen (Kapitel 1) siehe auch
das Skript zur Vorlesung Randomisierte Algorithmen von Rolf Niedermeier,
das über
diese
WWW-Seite erreichbar ist.
Weitere Literaturhinweise auf zugrundeliegende Originalarbeiten finden sich auf den Folien zur Vorlesung.
Weitere Literatur kann bei Bedarf bei der Dozentin
nachgefragt werden.
Inhalt der Vorlesung
Die Folien der jeweils aktuellen Vorlesung sowie der
vergangenen Vorlesungen findet Ihr
hier
.
- 15.10.2007: Einführung und Motivation, Paradigmen für randomisierte Algorithmen,
das Sekretärinnenproblem
- 18.10.2007: Fortsetzung Analyse Sekretärinnenproblem, Beispielalgorithmen für
verschiedene Entwurfsparadigmen: Signaturmethode, Zufallsstichproben,
Vereitelung gegnerischer Angriffe
- 22.10.2007: Fortsetzung Beispielalgorithmen für verschiedene Entwurfsparadigmen:
Markov-Ketten, Aufbrechen von Symmetrien;
Vorbereitung Miller-Rabin-Test für Primzahlen
- 25.10.2007 : Miller-Rabin-Test für Primzahlen: Fermat-Test, Carmichaelsche Zahlen
- 29.10.2007: Fortsetzung Miller-Rabin-Test: A-Zeugen, Miller-Rabin-Test, Korrektheit und Analyse der
Fehlerwahrscheinlichkeit
- 5.11.2007: Algorithmus zur Generierung von Primzahlen,
Pattern Matching Algorithmus (Fingerprinting),
- 8.11.2007: FBDD Äquivalenz (Fingerprinting);
Modellierung und Klassifikation randomisierter Algorithmen,
Äquivalenz multilinearer Ausdrücke
- 12.11.2007: Test auf perfektes Matching, randomisierte Komplexitätsklassen,
probability amplification
- 15.11.2007: Grundlagen Hashing
- 19.11.2007: (fast) universelles Hashing und Recycling von Zufallsbits
- 22.11.2007: randomisierte Online-Algorithmen für das Seitenwechselproblem,
nicht-adaptive und adaptive Widersacher, Kompetitivfaktor,
Analyse eines randomisierten Online-Algorithmus für das
Seitenwechselproblem gegen einen nicht-adaptiven Widersacher
- 26.11.2007: Untere-Schranken-Methode für randomisierte Algorithmen,
Exkurs Yaos Minimax-Prinzip, eine untere Schranke für
den Kompetitivfaktor randomisierter Online-Algorithmen gegen
nicht-adaptive Widersacher, Exkurs Coupon-Sammler-Problem
- 29.11.2007: Analyse eines randomisierten Online-Algorithmus für das
Seitenwechselproblem gegen einen adaptiven Widersacher, Exkurs
Grundlagen Wahrscheinlichkeitstheorie,
Einführung Sublineare Algorithmen
- 3.12.2007 : Einführung Property Testing, Test auf Sortiertheit,
Modelle für das Testen von
Grapheigenschaften, Test auf Kreisfreiheit in
gerichteten Graphen
- 6.12.2007: Fortsetzung Test auf Kreisfreiheit in gerichteten Graphen,
Testen visueller Eigenschaften, Exkurs Chernoff-Schranken
- 10.12.2007: Nachtrag Test auf Konvexität, Test auf Bipartitheit
- 13.12.2007: Analyse Test auf Bipartitheit als Spiel,
Einführung sublinearer Approximationsalgorithmen,
Anzahl Zusammenhangskomponenten im
gradbeschränkten Adjazenzlisten-Modell
- 17.12.2007: Fortsetzung Anzahl Zusammenhangskomponenten im
gradbeschränkten Adjazenzlisten-Modell,
sublinearer Approximationsalgorithmus für Bestimmung des
Gewichts mininmaler Spannbäume
- 20.12.2007: Einführung Datenströme,
Einschub Test auf Graphzusammenhang im unbeschräkten
Adjazenzlistenmodell
- 7.1.2008: Datenstromalgorithmus für Berechnung des Gewichts euklidischer
minimaler Spannbäume, randomisierter Graphalgorithmus für
das APSP-Problem
- 10.1.2008 Fortsetzung randomisierter Graphalgorithmus für
das APSP-Problem, APD-Problem, BPWM-Problem
- 14.1.2008: Fortsetzung randomisierter Graphalgorithmus für
das APSP-Problem, Verbesserung algorithmus für das BPWM-Problem,
Prinzip der verzögerten Entscheidung
- 17.1.2008: Fortsetzung Prinzip der verzögerten Entscheidung,
Vorbereitung randomisierter Graphalgorithmus für MSF
- 28.1.2008: Kartenrätsel, randomisierter Graphalgorithmus für MSF mit erwarteter
linearer Laufzeit und Analyse
- 31.1.2008: Fortsetzung Analyse des randomisierten Graphalgorithmus für MSF,
randomisierte Approximationsalgorithmen
- 4.2.2008: Fortsetzung randomisierte Approximationsalgorithmen
- 7.2.2008: best of randomized algorithms
Der Inhalt der Vorlesung lässt sich einteilen in:
- Kapitel 1: Einführung und Motivation, Beispielalgorithmen für verschiedene
Entwurfsparadigmen
- Kapitel 2: Ein randomisierter Primzahltest: Miller-Rabin-Test; Anwendung: Generierung
zufälliger Primzahlen, Pattern Matching, Äquivalenztest für FBDDs
- Kapitel 3: Klassifikation randomisierter Algorithmen, Las Vegas- und Monte Carlo-Algorithmen,
Beispielalgorithmen Äquivalenztest für multilineare Ausdrücke und
Test auf bipartites Matching, Komplexitätsklassen bezüglich randomisierter
Algorithmen
- Kapitel 4: Hashing und Recycling von Zufallsbits
- Kapitel 5: Randomisierte Online-Algorithmen, Seitenwechselproblem (paging) und deterministische
Algorithmen, randomisierte Algorithmen und Widersacher,
Seitenwechsel gegen nicht-adaptive Widersacher,
Seitenwechsel gegen adaptive Widersacher
- Kapitel 6: Sublineare Algorithmen: Property Testing, sublineare Approximationsalgorithmen,
Datenströme
- Kapitel 7: Graphalgorithmen: APSP und MSF
- Kapitel 8: Randomisierte Approximationsalgorithmen: Verdrahtungsproblem, MAXSAT, HITTING SET
Übungen
Die aktuellen Übungsblätter werden jeweils bis zur Vorlesung am
Donnerstag
hier
bereitgestellt. Die Besprechung erfolgt eine Woche später in den Übungen.
Prüfungsform
Fachprüfung mündlich (6SWS, 9LP),
Schwerpunktgebiet 4 (Algorithmen, Komplexität und formale Modelle)
Leistungsschein durch mündliches Fachgespräch,
Voraussetzung regelmässiger Besuch der Vorlesung und aktive Mitarbeit in den Übungen
7.2.2008 - Beate
Bollig