Veranstaltung

• J. Hromkovic : Randomisierte Algorithmen, Teubner, 2004
• M. Mitzenmacher, E. Upfal: Probability and Computing, Cambridge Univ. Press, 2005
• R. Motwani, P. Raghavan: Randomized Algorithms, Cambridge Univ. Press, 1995

Weiterführende Literatur

• E. Behrends: Introduction to Markov Chains, Vieweg, 2000
• A. Borodin, R. El-Yaniv: Online Computation and Competitive Analysis, Cambridge Univ. Press, 1998

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 wahrscheinlichkeitstheoretischen Grundlagen weitgehend erarbeitet und grundlegende Konzepte wie Markov-Ketten behandelt. Da stochastische Methoden in immer mehr Informatikbereichen von Bedeutung sind, ist diese Vorlesung daher auch über das eigentliche Thema hinaus von Nutzen.

Inhalte:

• probabilitische Komplexitätsklassen
• Routing in Hyperwürfeln
• Spieltheorie
• Random walks und Markovketten
• randomisierte Graphalgorithmen
• randomisiertes Hashing
• randomisierte Approximationen bei Zählproblemen
• randomisierte Online-Algorithmen