Mitteilungen

Beginn: 11.10.2007

Für Studierende der Informatik (Diplom) im Hauptstudium, Interessierte.

Inhalte

1. Einführung, Beispiele:

Randomisierter Min-Cut-Algorithmus, Quicksort, Polynomprodukte, Verifikation von Matrixmultiplikation.

2. Grundlagen aus der Wahrscheinlichkeitsrechnung:

Wahrscheinlichkeitsräume, Erwartungswert und Varianz, Chebychev-Ungleichung, Unabhängigkeit, einige wesentliche Verteilungen, Chernoff-Hoeffding-Schranken.

3. Typen randomisierter Algorithmen:

Monte-Carlo-Algorithmen, Las-Vegas-Algorithmen, Zeitkappung, Wahrscheinlichkeitsverbesserung, Komplexitätsklassen

4. Randomisiertes Suchen:

Suchen in linearen Listen, Mediansuche, Suchschema mit wenigen Zufallsbits (k-fache Unabhängigkeit)

5. Randomisierter Primzahltest und Primzahlerzeugung

6. Endliche Markoffketten, randomisierter SAT-Solver

7. Algebraische Methoden:

Textvergleich, Textsuche (Fingerprint-Techniken), Polynomdeterminanten, Polynomprodukte

8. Weitere Anwendungen

Termine

Vorlesung	Donnerstag, 9:00-10:30	Sr Hu 010	Prof. Dr. (USA) M. Dietzfelbinger
Übung	Montag (G), 9:00-10:30	Sr Hu 010	Prof. Dr. (USA) M. Dietzfelbinger

Kriterien für den Scheinerhalt

Benoteter Schein durch:

Vorrechnen einer Übungsaufgabe und
Bestehen einer Klausur (60 Minuten, nach Semesterende)

Literatur und Links

J.Hromkovic, Randomisierte Algorithmen, Teubner, 2004 (einführend)
M.Mitzenmacher, E.Upfal, Probability and Computing, Cambridge University Press, 2005 (startet bei Grundlagen, führt weit in die Theorie hinein).
R.Motwani, P.Raghavan, Randomized Algorithms, Cambrigde University Press, 1995 (ein ziemlich umfassendes Standardwerk).
U.Schöning, Algorithmik, Spektrum Akademischer Verlag, 2001 (Kapitel 12).
T.Cormen, C.Leiserson, R.Rivest, C.Stein, Introduction to Algorithms, MIT Press, 2001 (Umfassendes Standardwerk zu Algorithmen. Es gibt auch eine deutschsprachige Ausgabe im Oldenbourg-Verlag).