Modul
Randomisierte Algorithmen [M-INFO-100794]
Leistungspunkte
5Turnus
Jedes WintersemesterDauer
1 SemesterSprache
DeutschLevel
4Version
1Verantwortung
Einrichtung
- KIT-Fakultät für Informatik
Bestandteil von
Teilleistungen
Identifier | Name | LP |
---|---|---|
T-INFO-101331 | Randomisierte Algorithmen | 5 |
Erfolgskontrolle(n)
Siehe Teilleistung
Qualifikationsziele
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.
Voraussetzungen
Siehe Teilleistung
Inhalt
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
Empfehlungen
Siehe Teilleistung
Arbeitsaufwand
Der Gesamtarbeitsaufwand für diese Lerneinheit beträgt ca. 120 Stunden (4.0 Credits).