Mitteilungen

Beginn: 12.10. 2009

Die erste Übung findet in der 44. Kalenderwoche statt.

Für : Studierende der Informatik (Bachelor) im 5. Semester, Studierende der Informatik (Diplom) im 9. Semester, Interessierte

Inhalte

1. Einführung, Beispiele:

Randomisierter Min-Cut-Algorithmus, Polynomprodukte, Verifikation von Matrixmultiplikation, alternative Analyse von Quicksort

2. Grundlagen aus der Wahrscheinlichkeitsrechnung:

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

3. Modellierung, Typen randomisierter Algorithmen:

Randomisierte RAM, W-Raum-Konstruktion, Laufzeiten und Resultate als Zufallsvariable, 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. Zahlentheoretische Aufgaben, Grundlagen für kryptographische Anwendungen:

Grundlagen aus der Zahlentheorie (modulare Arithmetik, kleiner Satz von Fermat, chinesischer Restsatz), ziehen von Quadratwurzelm modulo p, Fermat-Test, Miller-Rabin-Primzahlentest mit Wahrscheinlichkeitsanalyse, Primzahlerzeugung

6. Algebraische Methoden:

Nullstellen von multivariaten Polynomen (satz von Schwartz-Zippel), Textvergleich, Textsuche (Fingerprint-Techniken), Polynomdeterminanten, Polynomprodukte

7. Eventuell: Endliche Markoffketten, randomisierte SAT-Solver

Termine

Vorlesung (Univ.- Prof. Dietzfelbinger)	Montag	9:00 - 10:30 Uhr	HU 210
Übung (Dr. Ulf Schellbach)	Freitag (G)	9:00 - 10:30 Uhr	HU 117

Kriterien für den Scheinerhalt

Prüfung (B.Sc.): Mündlich, 20 Minuten, am Semesterende

Scheinerwerb: Fachgespräch, 20 Minuten, am Semesterende

Bonuspunkte: 1/3 oder 2/3 einer Notenstufe durch einmaliges/ zweimaliges Vorrechnen (keine automatische Verbesserung von 5,0 auf 4,0)

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).
M.Dietzfelbinger, Primality Testing in Polynomial Time, LNCS 3000, Springer-Verlag, 2004 www.tu-ilmenau.de/fakia/Textbook-Primality.6432.0.html (freier Zugang von rechnern der Universität/ Bibliothek)
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).