http://www.tu-ilmenau.de

Logo TU Ilmenau


INHALTE

Randomisierte Algorithmen

Mitteilungen

Inhalt

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 Registermaschine, Wahrscheinlichkeitsraum-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 Algorithmen: Primzahltests, Quadratwurzeln

5. Algebraische Methoden: Nullstellen von multivariaten Polynomen (Satz von Schwartz-Zippel), Textvergleich, Textsuche (Fingerprint-Techniken), Polynomdeterminanten, Polynomprodukte, maximale Matchings, Äquivalenz von Branchingprogrammen

6. Eventuell: Randomisierte SAT-Solver

 

Literatur

J.Hromkovic, "Randomisierte Algorithmen", Teubner, 2004 (einführend)

M.Mitzenmacher, E.Upfal, "Probability and Computing", 2. Auflage, Cambridge University Press, 2017 (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).

Materialien

Vorlesungsskripte

Kapitel 1: Einführung und Beispiele (aktualisiert: 09.04.2018)

Kapitel 2: Grundlagen aus der Wahrscheinlichkeitsrechnung (aktualisiert: 17.04.2018)

Kapitel 3: Modellierung und Transformation (aktualisiert: 07.05.2018)

Kapitel 4: Randomisierte Suche (aktualisiert: 01.06.2018), Korrektur zur Analyse von Quickselect (aktualisiert: 01.06.2018)

Kapitel 5: Zahlentheorie

Kapitel 6: Algebraische Methoden (aktualisiert: 03.08.2018, Abschnitt 6.7 nicht prüfungsrelevant)

Termine

Vorlesung (Univ.-Prof. M. Dietzfelbinger):

Montag (U), 9:00 - 10:30 Uhr, Sr HU 011

Dienstag, 11:00 - 12:30 Uhr, Sr HU 012

Übung ( P. Schlag)

Montag (G), 9:00 - 10:30 Uhr, Sr HU 011