|
|
Randomisierte Algorithmen (WS 04/05)
 |
Dozentin:
Prof. Angelika Steger
 |
|
Assistent:
Konstantinos Panagiotou
|
|
Zeit und Ort:
- Vorlesung: Montag, 10.00 - 12.00 Uhr, IFW B 42
- Übung: Dienstag, 13:00 - 14:00 Uhr, IFW B 42
Vorlesungsbeginn ist am 25. Oktober 2004, Übungsbeginn am 26. Oktober
2004! |
|
Inhalt:
Für viele Probleme wurden in den letzten Jahren effiziente randomisierte
Algorithmen gefunden, die deterministischen Verfahren in Bezug auf Laufzeit
und/oder benötigte Hardwareressourcen weit überlegen sind. Oft sind
randomisierte Algorithmen zudem auch viel einfacher zu analysieren und zu
implementieren. Im Rahmen der Vorlesung werden
-
für die Analyse der Laufzeit von randomisierten Algorithmen
notwendigen Grundlagen aus der Wahrscheinlichkeitstheorie vorgestellt. Da
stochastische Methoden in der Informatik immer mehr Anwendungen finden,
ist diese Vorlesung daher auch über das eigentliche Thema hinaus von
Nutzen.
-
verschiedene 'Arten' randomisierter Algorithmen (Monte Carlo/Las
Vegas) für praxisrelevante Probleme vorgestellt.
Im Detail werden insbesondere
folgende Themen behandelt:
-
Teaser: randomisierter Primzahltest, MinCut
Methoden anhand
von Beispielen
-
Markov's Ungleichung - 2SAT
-
Chebyshev's Ungleichung -
randomisierte Medianbestimmung
-
1st and 2nd moment Method -
Hashing/Bälle und Urnen Modelle
-
Chernoff's Ungleichung -
Permutation Routing und BitFixing
-
Wahrscheinlichkeitserzeugende
Funktionen - rekurrente Ereignisse
Markov-Ketten
-
Einführung
-
Anwendungen:
Warteschlangentheorie, 3SAT, schnell mischende Markov-Ketten,
approximatives Zählen/gleichverteiltes Erzeugen
Average-Case
Analyse
|
|
Voraussetzung:
Grundstudium |
|
Material: Übung:
|
|
Literatur:
|
|
Links: |
|
