Randomisierte Algorithmen

Termine

	Wann?	Wo?	Wer?
Vorlesung und Übung:	Do 8:30 - 12:00	OH 14, R 304	Beate Bollig

Die Vorlesung beginnt am 14. Oktober 2010. Die Übung findet im Wechsel mit der Vorlesung alle zwei Wochen donnerstags von 10:00-12:00 Uhr zweistündig statt.

Die Veranstaltung kann von Studierenden als Modul Randomisierte Algorithmen in den Master-Studiengängen besucht werden.

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.

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

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.

• J. Hromkovic (2004). Randomisierte Algorithmen. Teubner Verlag.

Für das FBDD-Äquivalenzproblem siehe auch:

• U. Schöning (1995) (Uwe Schönings Online-Publikationen).
  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.
• R. Impagliazzo, D. Zuckermann (1989). (David Zuckermanns Publikationen)
  How to recycle random bits.

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:

Einen kurzen Überblick über das Gebiet Sublineare Algorithmen bietet:

• Rubinfeld, R. (2006). (Ronitt Rubinfelds Publikationen )
  Sublinear time algorithms.
  

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.

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

Originalliteratur:

• Chazelle, B., Rubinfeld, R., Trevisan, L. (2001).
  Approximating the minimum spanning tree weight in sublinear time.
  ICALP, LNCS 2076, 190-200.

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.

Begleitmaterial

Die Folien zur aktuellen Veranstaltung Randomisierte Algorithmen findet Ihr hier .

Übungen

Prüfungsform

• Erwerb eines Leistungsscheins bzw. der für eine Modulprüfung im Master notwendigen Studienleistungen ist durch ein mündliches Fachgespräch im Anschluss an die Veranstaltung möglich, alternativ auch durch eine Kurzpräsentation
• Voraussetzung ist der aktiver Besuch der Vorlesung und der Übung

31.1.2011 - Beate Bollig