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

Einführung und Beispiele (Stand: 21.10.2011)

Kapitel 2

Kapitel 3

Kapitel 4

Kapitel 5

Kapitel 6

Übungsblätter

Übungsblatt 1     Lösung Aufgabe 1c

Übungsblatt 2

Übungsblatt 3     Lösung Aufgabe 1c

Übungsblatt 4 

Übungsblatt 5 (Übung findet am 05.01.2012 statt.)

Übungsblatt 6

Übungsblatt 7

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

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