http://www.tu-ilmenau.de

Logo TU Ilmenau


INHALTE

Randomisierte Algorithmen

Mitteilungen

Die mündlichen Prüfungstermine finden Sie hier.

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

Die Übung RA am 11.12.2014 fällt aus!

Die erste Vorlesung findet am Freitag, den 24. Oktober 2014 statt, die erste Übung findet am Donnerstag, den 30. Oktober 2014 statt!

Termine

Vorlesung: Univ.-Prof. M. Dietzfelbinger

Donnerstag,  ungerade KW, 13:00 - 14:30 Uhr, K-Hs 2

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

Übung: C. Mattern

Donnerstag, gerade KW, 13:00 - 14:30 Uhr, Sr HU 012

Materialien - Vorlesung

Kapitel 1 - Einführung und Beispiele

Kapitel 2 - Grundlagen aus der Wahrscheinlichkeitsrechnung [Stand: 17.11.2014]

Kapitel 3 - Modellierung und Transformationen

Zusatz: Conditional Expectation Inequality

Kapitel 4 - Randomisierte Suche

Kapitel 5 - Quadratwurzeln modulo p 

Kapitel 6 - Algebraische Methoden

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).