Vorlesung: Randomisierte Algorithmen und Probabilistische Analyse

Dozent: Anusch Taraz

Termine

Beginn der Vorlesung: 22.10.2003

VL	Mittwoch	11:00 - 12:30	(RUD 25, 3.101)
VL	Freitag	09:30 - 11:00	(RUD 26, 1.305)
UE	Mittwoch	13:15 - 14:45	(RUD 25, 3.101)

Zuordnung

Hauptstudium, Halbkurs
Theoretische Informatik

Voraussetzungen

Grundstudium (Informatik oder Mathematik)
Graphen und Algorithmen 1 ist als Ergänzung sinnvoll
Die erforderlichen Hilfsmittel aus der Wahrscheinlichkeitstheorie werden in der Vorlesung behandelt.

Inhalte und Lernziele

Zwei verschiedene Aspekte der Thematik "Algorithmen und Zufall" sind Inhalt dieser Vorlesung: In Randomisierten Algorithmen einerseits dient der Zufall als algorithmisches Konzept. Algorithmen, die von "Münzwürfen" Gebrauch machen, bieten oft eine bessere Laufzeit oder sind einfacher zu analysieren als deterministische Algorithmen. Die Probabilistische Analyse andererseits hat das Ziel, "harten" Problemen beizukommen. Der Ansatz ist, schnelle Algorithmen zu entwickeln, die zwar nicht für alle Eingaben gut funktionieren, aber doch für "typische" Eingaben.

Folgende Themen sollen in der Vorlesung behandelt werden:

Randomisierte Algorithmen: Einführung
Randomisiertes Routing, Online-Verfahren und Primzahltests
Markov-Ketten Monte-Carlo Simulationen
Martingal-Methoden
Probabilistische Analyse: Einführung
Analyse von Heuristiken auf "typischen" Eingaben
Spektraltechniken
Umgang mit schwer approximierbaren Größen
...

Übungen

In den Übungen wird der aktive Umgang mit den Lerninhalten vertieft, in einigen Fällen gibt es auch Hausaufgaben.

Empfohlene Literatur

Motwani, Raghavan, Randomized algorithms, Cambridge, 1995.
Alon, Spencer, The probabilistic method, Wiley, 2001.
Vazirani, Approximation algorithms, Springer, 2001.
Bollobas, Random graphs, Cambridge, 2002.
Janson, Luczak, Ruciniski, Random graphs, Wiley, 2001.
Feller, An introduction to probability theory and its applications, Wiley, 1968.

zuletzt geändert am 23.01.2006 (alkox-www)