http://www.tu-ilmenau.de

Logo TU Ilmenau


INHALTE

Informationen

Die Ankündigung zu den mündlichen Prüfungsterminen finden Sie hier.

Materialien

Vorlesung

Kapitel 1 - Einführung und Beispiele
Kapitel 2 - Grundlagen aus der Wahrscheinlichkeitsrechnung
Kapitel 3 - Modellierung und Transformationen
(Stand 20.11.2015)
Kapitel 4 - Randomisiertes Suchen
Kapitel 5 - Quadratwurzeln
Kapitel 6 - Algebraische Methoden (Anfang)
(Stand 14.01.2016)

Termine

Vorlesung:

Donnerstag (U), 13:00 - 14:30 Uhr, Sr Oe311, Univ.-Prof. Dietzfelbinger

Freitag, 15:00 - 16:30 Uhr, Sr HU 012

Übungen:

Donnerstag (G), 13:00 - 14:30 Uhr, Sr HU 010, C. Mattern

Inhalte

1. Einführung, Beispiele: Randomisierter Min-Cut-Algorithmus, Polynomprodukte, Verifikation von Matrixmultiplikation

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. Algebraische Methoden: Nullstellen von multivariaten Polynomen (satz von Schwartz-Zippel), Textvergleich, Textsuche (Fingerprint-Techniken), Polynomdeterminanten, Polynomprodukte

6. Eventuell: Endliche Markoffketten, randomisierte SAT-Solver

Hinweis: Ein randomisierter Primzahltest wird in der Vorlesung Grundlagen und Methoden der Kryptographie behandelt.

Literatur

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, eine deutschsprachige Ausgabe ist im Oldenbourg-Verlag erhältlich).