Randomisierte Algorithmen
Randomisierte Algorithmen
Prof. M. Dietzfelbinger
Termine
Prüfungstermine:
Die mündlichen Prüfungen finden vom 8. - 9. März 2012 statt. Zur Terminvergabe tragen Sie sich bitte bis zum 3. Februar 2012 im Sekretariat bei Frau Kopp, Zusebau, Raum 1046, in die Terminliste ein.
Vorlesung:
Freitag, 15:00-16:30 Uhr, Sr HU 010
Übung:
Donnerstag (G), 19:00-20:30 Uhr, Sr HU 010, C. Mattern
Materialien und Übungen
Einführung und Beispiele (Stand: 21.10.2011)
Übungsblätter
Übungsblatt 1 Lösung Aufgabe 1c
Übungsblatt 3 Lösung Aufgabe 1c
Übungsblatt 5 (Übung findet am 05.01.2012 statt.)
Inhalte und Literatur
Für Studierende der Informatik im 5. Semester
Inhalte
1. Einführung, Beispiele:
Randomisierter Min-Cut-Algorithmus, Polynomprodukte, Verifikation von Matrixmultiplikation, alternative Analyse von Quicksort
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
Kriterien für den Scheinerhalt
Prüfung (B.Sc.): Mündlich, 20 Minuten, am Semesterende
Scheinerwerb: Fachgespräch, 20 Minuten, am Semesterende
Bonuspunkte: 1/3 oder 2/3 einer Notenstufe durch einmaliges/ zweimaliges Vorrechnen (keine automatische Verbesserung von 5,0 auf 4,0)
Literatur und Links
- 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. Es gibt auch eine deutschsprachige Ausgabe im Oldenbourg-Verlag).