Spezialvorlesung Randomisierte Algorithmen WS2004/05

Termine:
Di., 10:15-11.45 Uhr, HG I, HS 2
Mi., 12:15-13:45 Uhr, HG I, HS 2

Übungen

Die Übungen zur Vorlesung (inkl. Aufgabenblätter) werden von
Thomas Franke betreut, bei Fragen zu diesen bitte an ihn wenden.

Skript

Es gibt ein Skript:
Das Skript in der "vorlesungsbegleitend" aktualisierten Version.

Was wurde wann gemacht?

Worum geht es in der Vorlesung?

In vielen praktischen Anwendungen sind Algorithmen selbst dann nicht effizient genug, wenn die Rechenzeit zwar polynomiell, aber z.B. wie n³ wächst. Dann bilden randomisierte Algorithmen, die auf die Ergebnisse von unabhängigen Münzwürfen (in der Praxis Pseudozufallszahlen) zurückgreifen können, eine attraktive Alternative. Es gibt randomisierte Algorithmen, die das richtige Resultat in einer bestimmten mittleren Rechenzeit liefern. Bei anderen randomisierten Algorithmen ist zwar eine obere Schranke für die Rechenzeit gesichert, die Antwort des Algorithmus kann jedoch mit kleiner Wahrscheinlichkeit "weiß nicht" lauten. Selbst randomisierte Algorithmen, die mit kleiner Wahrscheinlichkeit falsche Ergebnisse liefern, sind von praktischer Bedeutung, wenn sie wesentlich schneller als die besten bekannten "normalen", also deterministischen Algorithmen sind. In dieser Spezialvorlesung sollen Entwurf und Analyse randomisierter Algorithmen behandelt werden, wobei die Grundlagen aus der Wahrscheinlichkeitsrechnung dann vorgestellt werden, wenn sie gebraucht werden. Kenntnisse in Wahrscheinlichkeitstheorie werden also nicht vorausgesetzt, sondern anhand von Anwendungen innerhalb der Informatik entwickelt.

Links

Buch "Randomized algorithms" bei Amazon.
Ein Link zu einem Skript von Rolf Niedermeier und...
das Skript selbst
Lecture by David Karger
Lecture notes Avrim Blum
Ftp-Download Skript Martin Tompa
Probabilistic methods in CS
The Probabilistic Method (Alon/Spencer) (nicht abrufbar)
Probabilistic algorithms (Diaz) (momentan nicht abrufbar)
Skript Probabilistic Methods (Naor)