Mitteilungen

Beginn:

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	Mittwoch, 11:00-12:30	Sr Hu 204	Prof. Dr. (USA) M. Dietzfelbinger
Übung	Donnerstag (U), 9:00-10:30	Sr Hu 204	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).