Randomisierte Algorithmen

• Dozent: Thomas Worsch, Alexander Wolff
• Betreuung der Übung: Thomas Schank, Étienne Schramm, Marc Benkert

Randomisierte Algorithmen sind nicht deterministisch. Ihr Verhalten hängt vom Ausgang von Zufallsexperimenten ab. Diese Idee wurde erstmals von Rabin durch einen randomisierten Primzahltest bekannt. Inzwischen gibt es für eine Vielzahl von Problemen randomisierte Algorithmen, die (in dem einen oder anderen Sinne) schneller sind als deterministische Verfahren. Außerdem sind randomisierte Algorithmen mitunter einfacher zu verstehen und zu implementieren als normale (deterministische) Algorithmen.

Im Rahmen der Vorlesung werden nicht nur verschiedene Arten randomisierter Algorithmen (Las Vegas, Monte Carlo, …) vorgestellt, sondern auch die für die Analyse ihrer Laufzeit notwendigen wahrscheinlichkeits- theoretischen Grundlagen weitgehend erarbeitet. Da stochastische Methoden in immer mehr Informatikbereichen angewendet werden, ist diese Vorlesung auch über das eigentliche Thema hinaus von Nutzen.

Der Nutzen von randomisierten Algorithmen wird insbesondere an Beispielen aus der algorithmischen Geometrie erläutert, wie etwa Trapezzerlegung, konvexe Hülle, Voronoidiagramm, Punktlokalisierung oder Bereichsabfragen. Es werden deterministische und randomisierte Verfahren zur Lösung dieser Probleme behandelt und miteinander verglichen.

• Skript der aktuellen Vorlesung.
• Der „geometrische Teil“ der Vorlesung stützt sich in erster Linie auf die ersten drei Kapitel des Buchs „Computational Geometry: An Introduction Through Randomized Algorithms“ von Mulmuley [1]. Ein weiteres Standardwerk zum Thema ist „Randomized Algorithms“ von Motwani und Raghavan [2].
• Der sehr lesenswerte und für die Vorlesung relevante Übersichtsartikel Backwards Analysis of Randomized Geometric Algorithms von Raimund Seidel [3] ist erhältlich als Technischer Bericht TR-92-014.
• Zum Thema „Spannbäume mit wenigen Kreuzungen in geometrischen Graphen“ gibt es einen kurzen wissenschaftlichen Artikel [4]. Wichtig für die Vorlesung ist hauptsächlich Kapitel 3 (Fixed-parameter tractability).
• Zur Vorlesung am 14.02.2005 (Triangulierung von Polygonen):
  • Triangulierung von Polygonen mit Löchern in O(n log n) Zeit [pdf]
  • Triangulierung von einfachen Polygonen in O(n log* n) Zeit [pdf]; dazu der Originalartikel von Raimund Seidel [5]

1. K. Mulmuley. Computational Geometry: An Introduction Through Randomized Algorithms. Prentice Hall, Englewood Cliffs, NJ, 1993.
2. R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, New York, NY, 1995.
3. R. Seidel. Backwards Analysis of Randomized Geometric Algorithms. In J. Pach, editor, New Trends in Discrete and Computational Geometry, volume 10 of Algorithms and Combinatorics, pages 37-68. Springer-Verlag, 1993.
4. Christian Knauer, Étienne Schramm, Andreas Spillner, and Alexander Wolff. Configurations with Few Crossings in Topological Graphs. Computational Geometry: Theory and Applications, 37(2):104-114, 2007.
5. R. Seidel. A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons. Comput. Geom. Theory Appl., 1(1):51-64, 1991.