http://www.tu-ilmenau.de

Logo TU Ilmenau


INHALTE

Randomisierte Algorithmen (Univ.-Prof. M. Dietzfelbinger)

Aktuelle Informationen

Die Termine für die mündlichen Prüfungen finden Sie hier.

Materialien

Vorlesung

Kapitel 1 - Einführung und Beispiele

Kapitel 2 - Grundlagen aus der Wahrscheinlichkeitsrechnung

Kapitel 3 - Modellierung und Transformationen

Kapitel 4 - Randomisiertes Suchen

Kapitel 5 - Randomisierte Algorithmen für Probleme aus der Zahlentheorie

Kapitel 6 - Algebraische Methoden

Übung

Übungsblatt 1 [Stand 16.10.2012]

Übungsblatt 2, Lösung für Aufgabe 3

Übungsblatt 3

Übungsblatt 4

Übungsblatt 5, Lösung für Aufgabe 2d [Stand: 23.01.2013]

Übungsblatt 6, Lösung für Aufgaben 2, 3b

Termine

Vorlesung ( Univ.-Prof. M. Dietzfelbinger): Freitag, 15-16.30 Uhr, Sr Oe 311

Übung (C. Mattern): Mittwoch G, 9-10.30 Uhr, Sr HU 211/212

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

 

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

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