Randomisierte Algorithmen
Wintersemester 2008/09
Beate Bollig
Termine
|
Wann? |
Wo? |
Wer? |
| Vorlesung: |
Mo 14:15 - 16:00 |
OH 14, R 304 |
Beate Bollig |
| Vorlesung: |
Do 8:30 - 10:00 |
OH 14, R 304 |
Beate Bollig |
Die erste Vorlesung findet am 13. Oktober 2008 statt.
Am 11.12., 15.12. und 18.12. finden keine Vorlesungen statt.
Der Stoff der entsprechenden Vorlesungen wird vorgearbeitet.
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 die Klassifikation randomisierter Algorithmen siehe auch:
Ingo Wegener (2003).
Komplexitätstheorie - Grenzen der Effizienz von Algorithmen.
Springer Verlag.
Kapitel 3:
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 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 zu Kapitel 1-4 und zu Kapitel 5-6 der Vorlesung stehen bereits
hier
bereit.
Der Inhalt der Vorlesung lässt sich einteilen in:
- Kapitel 1: Einführung und Motivation, Beispielalgorithmen für verschiedene
Entwurfsparadigmen
- Kapitel 2: 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 3: Ein randomisierter Primzahltest: Miller-Rabin-Test; Anwendung: Generierung
zufälliger Primzahlen, Pattern Matching, Äquivalenztest für FBDDs
- 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
Prüfungsform
Fachprüfung mündlich (4SWS, 6LP),
Schwerpunktgebiet 4 (Algorithmen, Komplexität und formale Modelle)
Leistungsschein durch mündliches Fachgespräch,
Voraussetzung regelmässiger aktiver Besuch der Vorlesung, Präsentation eines Algorithmus
4.11.2008 - Beate
Bollig