http://www.tu-ilmenau.de

Logo TU Ilmenau


INHALTE

Mitteilungen

Die mündlichen Prüfungstermine finden Sie hier.

Die Vorlesung Randomisierte Algorithmen fällt wegen Krankheit am 16.01.2014 und 17.01.2014 aus.

 

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

Termine

Vorlesung: Prof. M. Dietzfelbinger

Donnerstag, ungerade KW, 13:00-14:30 Uhr, Sr H 1519

Freitag, jede KW, außer 43. KW 2013 (siehe unten), 15:00-16:30 Uhr, Sr H1519

Übung: C. Mattern

Donnerstag, gerade KW, außer 44. KW 2013, 13:00-14:30 Uhr, Sr H 1519

Freitag, einmalig in 43. KW 2013, 15:00-16:30 Uhr, Sr H1519

Materialien

Vorlesung

Kapitel 1 - Einführung und Beispiele

Kapitel 2 - Grundlagen aus der Wahrscheinlichkeitsrechnung

Kapitel 3 - Modellierung und Transformationen

Kapitel 4 - Randomisierte Suche

Kapitel 5 - Quadratwurzeln

Kapitel 6 - Algebraische Methoden

Übung

Übungsblatt 1

Übungsblatt 2 Korrigiert: 24.10.2013

Übungsblatt 3

Übungsblatt 4 Korrigiert: 28.11.2013

Übungsblatt 5

Übungsblatt 6

Übungsblatt 7

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

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