Randomisierte Algorithmen
3V + 1 Ü
Wintersemester 2009/10
Beate Bollig
Termine
|
Wann? |
Wo? |
Wer? |
| Vorlesung und Übung: |
Do 8:30 - 12:00 |
OH 14, R 304 |
Beate Bollig |
Die Vorlesung beginnt am 15. Oktober 2009. Die Übung findet im Wechsel mit der Vorlesung
alle zwei Wochen donnerstags von 10:00-12:00 Uhr zweistündig statt.
Studierende in den Master-Studiengängen mögen sich bitte vor Beginn
der Veranstaltung bei der Dozentin melden.
Inhalt
Randomisierte Algorithmen sind eine in den Anwendungen
nützliche Verallgemeinerung deterministischer Algorithmen,
da sie sich häufig durch Einfachheit und Effizienz bei
der Lösung komplexer Aufgaben auszeichnen und
die Wahrscheinlichkeit unerwünschter Verhaltensweisen wie zu lange
Rechenzeiten oder die Berechnung falscher Ergebnisse oft gering gehalten werden kann.
Typische Entwurfsparadigmen randomisierter Algorithmen sind z.B.:
- Ü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 kann
bei der gezielten Suche nach einem effizienten randomisierten Verfahren
für ein zu untersuchendes Problem hilfreich sein.
In der Vorlesung behandeln wir den Entwurf und die Analyse randomisierter
Algorithmen, wobei
keine tieferen Kenntnisse aus der Wahrscheinlichkeitstheorie
vorausgesetzt werden. Die entsprechenden Kenntnisse werden bei Bedarf in der Vorlesung anhand
von Anwendungen aus der Informatik entwickelt.
Literatur zur Vorlesung
Es gibt mehrere Standardwerke über randomisierte Algorithmen.
Die Vorlesung richtet sich, wenn nicht anders angegeben, nach:
R. Motwani, P. Raghavan (1995). Randomized Algorithms.
Cambridge University Press.
Eine gut lesbare Einführung in den Entwurf und die Analyse randomisierter
Algorithmen bietet das folgende Buch:
J. Hromkovic (2004). Randomisierte Algorithmen. Teubner Verlag.
Kapitel 1:
Für das Sekretärinnenproblem siehe:
T. Cormen, C. Leiserson, R. Rivest, C. Stein (2001).
Introduction to Algorithms. Second Edition.
MIT Press.
Kapitel 2:
Für die Klassifikation randomisierter Algorithmen siehe auch:
I. Wegener (2003).
Komplexitätstheorie - Grenzen der Effizienz von Algorithmen.
Springer Verlag.
Kapitel 3:
Für den randomisierten Miller-Rabin-Primzahltest siehe (auch):
M. Dietzfelbinger (2004). Primality Testing in Polynomial
Time. Springer Verlag.
Die Nummerierung auf den Folien bezieht sich auf dieses Lehrbuch.
Für die Generierung zufälliger Primzahlen siehe:
J. Hromkovic (2004). Randomisierte Algorithmen. Teubner Verlag.
Für das FBDD-Äquivalenzproblem siehe auch:
U. Schöning (1995).
Perlen der Theoretischen Informatik (Kapitel 14).
BI Wissenschaftsverlag.
Kapitel 4:
Für das Recycling von Zufallsbits siehe auch:
Uwe Schöning (1995).
Perlen der Theoretischen Informatik (Kapitel 17).
BI Wissenschaftsverlag.
Kapitel 5:
M. Aigner und G.M. Ziegler (2004).
Das Buch der Beweise. 2. Auflage. Springer Verlag.
Kapitel 6:
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 7:
Leider existiert noch kein Lehrbuch über Sublineare Algorithmen.
Einen kurzen Überblick über das Gebiet Sublineare Algorithmen bietet:
Kapitel 7.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 7.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 R. Niedermeier,
das über
diese WWW-Seite
erreichbar ist.
Weitere Literaturhinweise auf zugrundeliegende Originalarbeiten finden sich auf den Folien zur Vorlesung.
Begleitmaterial
Die Folien zur aktuellen Veranstaltung Randomisierte Algorithmen
findet Ihr
hier
.
Übungen
Die aktuellen Übungsblätter werden jeweils für die entsprechende Woche bis zur Vorlesung am
Donnerstag
hier
bereitgestellt. Die Besprechung erfolgt in der nächsten Übung.
Prüfungsform
Fachprüfung mündlich (4SWS, 6LP),
Schwerpunktgebiet 4 (Algorithmen, Komplexität und formale Modelle)
Erwerb eines Leistungsscheins durch mündliches Fachgespräch möglich,
Voraussetzung ist der aktiver Besuch der Vorlesung und der Übung.
4.01.2010 - Beate
Bollig