Modul

Siehe Teilleistung

Die Studierenden kennen grundlegende Ansätze und Techniken für den Einsatz von Randomisierung in Algorithmen sowie Werkzeuge für deren Analyse.

Sie sind in der Lage, selbst typische Schwachstellen deterministischer Algorithmen zu identifizieren und randomisierte Ansätze zu deren Behebung zu entwickeln und zu beurteilen.

Siehe Teilleistung

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.
Themen: probabilitische Komplexitätsklassen, Routing in Hyperwürfeln, Spieltheorie, Random Walks, randomisierte Graphalgorithmen, randomisiertes Hashing, randomisierte Online-Algorithmen

Siehe Teilleistung

Der Gesamtarbeitsaufwand für diese Lerneinheit beträgt ca. 120 Stunden (4.0 Credits).