Seminar über Wahrscheinlichkeitstheorie:
Randomisierte Algorithmen

Kontakt

Prof. Dr. G. Kersting
Prof. Dr. R. Neininger
Dipl. Math. H. Sulzbach

Organisatorisches

Termin: Do 14-16 Uhr, Ort: 711 groß, Beginn: n. Vereinb..
Voraussetzungen: Elementare Stochastik. Empfehlung: Stochastische Prozesse oder Höhere Stochastik.
Bei der Vorbereitungszeit für den Vortrag sollte man mit ca. 6 Wochen rechnen. Spätestens 3 Wochen vor dem Vortragstermin sollte die/der Vortragende bei dem Betreuer vorbeikommen. Spätestens 1 Woche vor dem Vortagstermin muss ein Thesenblatt (Handout) mit den wichtigsten Aussagen abgegeben werden. Dieses wird dann vor dem Vortrag an die Seminarteilnehmer ausgeteilt.
Zusätlich muss eine Ausarbeitung des Vortrags (in Maschinenschrift 4-7 Seiten) spätetens drei Wochen nach dem Vortrag abgegeben werden. Diese sollte die Aussagen kommentieren und Beweise enthalten, wobei auf technische Finessen verzichtet werden darf. Es ist empfehlenswert, diese, wie auch das Handout, am Computer mit dem Programm "LaTex" zu erstellen. Näheres zu einem LaTex Kurs wird im Semester bekannt gegeben. Für weitere Informationen siehe unten. Natürlich werden auch handschriftliche Ausarbeitungen und Handouts akzeptiert.

Vorträge

16.10.08: Fingerabdrücke - Markov-Ketten
Henning Sulzbach

Schnelle Methoden zur Lösung des Textsuche-Problems. Basics über diskrete Markov-Ketten.

Geiger: Kap 5,
Motwani & Raghavan: Kap 7,
Rabin (1981).

Handout (.pdf)


23.10.08: Routenplanung in Netzwerken
Marie Gotthardt

Chernoff-Schranken für Summen unabhängiger, beschränkter Zufallsvariable, Randomisierter Algorithmus zur Beschleunigung der Zustellung von Paketen in Netzwerken, Anwendung im Booleschen Würfel.

Geiger: Kap. 4,
Mitzenmacher & Upfal: Kap. 4,
Motwani & Raghavan: Kap. 4.1, 4.2.

Handout (.pdf)
Ausarbeitung (.pdf)

30.10.08: Approximatives Zählen - Teil 1
Ivan Kasa

Anwendung der MCMC- Methode zur Lösung eines Rucksackproblems, Konfidenzbereiche, rasch mischende Markovketten.

Geiger: Kap. 8.

Handout (.pdf)


06.11.08: Approximatives Zählen - Teil 2
Ivan Kasa

Selbstmeidende Pfade, rasch mischende Markov-Ketten

Geiger: Kap 8.

Handout (.pdf)


13.11.08: Der Propp-Wilson Algorithmus - Teil 1
Marie Cuno

Algorithmus zum exakten Samplen einer Verteilung, Sandwiching.

Häggström: Kap 11.

Handout (.pdf)


20.11.08: Der Propp-Wilson Algorithmus - Teil 2
Marie Cuno

Anwendungen, Ising-Modell, Simulationen.

Häggström: Kap 12.



27.11.08: Auswerten von Spielbäumen
Nele Küsener

Spieltheoretische Aspekte bei der Auswertung von Spielbäumen, von Neumann's Minimax Theorem für Zwei-Personen- Nullsummen-Spiele, Yao's Minimax-Prinzip, untere Schranken für die (erwartete) Laufzeit randomisierter Algorithmen.

Geiger: Kap. 3,
Motwani & Raghavan: Kap. 2.

Handout (.pdf)
Ausarbeitung (.pdf)

04.12.08: Der randomisierte Quicksortalgorithmus
Bastian Werth

Grenzwertsatz für die Anzahl Schlüsselvergleiche für die randomisierte Version des bekannten Sortieralgorithmus Quicksort, Martingale, Fixpunktgleichungen.

Regnier (1989),
Rösler (1991).

11.12.08: Besuch auf dem Weihnachtsmarkt



18.12.08: Das zufällige k-SAT Problem
Ute Lenz

Achlioptas, D. and Peres, Y. (2003)

Handout (.pdf)


15.01.09: Zufällige Projektionen und das MAX-CUT Problem
Arne Moritz Harff

Zufällige Projektionen auf niedrigdimensionale Räume, MAX-CUT, Färbungen von Graphen.

Vempala: Kap. 1, 2.

Handout (.pdf)


29.01.09: Cuckoo-Hashing - Teil 1
Jochen Kienberger

Verzweigungsprozesse, Chernoff-Schranken für Binomialverteilung, Laufzeit und Fehlerwahrscheinlichkeit des randomisierten Cuckoo-Hashing Verfahrens.

Pagh, R. and Rodler, F. (2001),
Devroye, L. and Morin, P. (2001).

Handout (.pdf)

05.02.09: Cuckoo-Hashing - Teil 2
Jochen Kienberger

Vervollständigung des Beweises zur Laufzeit des Algorithmus'.

Literatur

Sämtliche Quellen können beim Betreuer in kopierter Form abgeholt werden. Zusätzlich werden die Bücher in den Bibliotheken vorhanden sein.

Achlioptas, D. and Peres, Y. (2003) The threshold for random k-SAT is 2^k (ln 2 - O(k))
STOC '03: Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, 2003, 223-232

Devroye, L. and Morin, P (2001) Cuckoo Hashing: Further Analysis
Information Processing Letters, vol. 86, pp. 215-219, 2003

Geiger, J. (2006) Algorithmen und Zufälligkeit.
Lecture Notes, TU Kaiserslautern.

Häggström, O. (2002) Finite Markov Chains and Algorithmic Applications.
London Mathematical Society Student Texts, 52. Cambridge University Press, Cambridge. x+114 pp.
ISBN: 0-521-81357-3; 0-521-89001-2

Mitzenmacher, M. and Upfal, E. (2005) Probability and Computing.
Cambridge University Press, Cambridge , 2005. xvi+352 pp. ISBN: 0-521-83540-2

Motwani, R. and Raghavan, P. (1995) Randomized Algorithms.
Cambridge University Press, Cambridge . xiv+476 pp.
ISBN: 0-521-47465-5

Pagh, R. and Rodler, F. (2001) Cuckoo Hashing
J. Algorithms 51, No. 2.

Rabin, M. O. (1981) Fingerprinting by random polynomials

Regnier, M. (1989) A limiting distribution for quicksort.
RAIRO Inform. Theor. Appl. 23 (1989), no.3, 335-343

Rösler, U. (1991) A limit theorem for "Quicksort"
RAIRO Inform. Theor. Appl. 25 (1991). no.1, 85-100

Vempala, S. (2004) The random projection method.
DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 65. American Mathematical Society, Providence, RI , 2004. x+105 pp.
ISBN: 0-8218-2018-4

LaTex

Nachfolgender Text und Beispieldateien sind von einer älteren Seminarseite übernommen und wurden von Martin Hutzenthaler erstellt, vielen Dank an dieser Stelle.

Das folgende ist für LaTeX-Anfänger auf Windows gedacht.

Das Standard LaTeX Programm für MiKrosoft heißt MiKTeX. Hier kann man es sich herunterladen. Desweiteren benötigt man einen Editor. Es sollte im MiKTeX-Paket ein LaTeX-Editor dabei sein. Eine Suche im Netz nach besseren Editoren lohnt sich eventuell. Nach der Installation kann es los gehen.

LaTeX ist ein Programm, welches eine Quelldatei, übliche Dateiendung .tex, in eine pdf-Datei übersetzt. In einem LaTeX-Editor geschieht dies durch Drücken eines Buttons, der zB "Übersetzen" oder "Setzen" heissen könnte. Zum Test der Installation sollte man eine Minimal-Quelldatei übersetzen, beispielsweise hello_world.tex (download). Also diese Datei herunterladen, mit dem Editor öffnen und übersetzen. Das Ergebnis sollte hello_world.pdf (im selben Verzeichnis) sein, welches nur den Text "Hello World!" enthält. Falls das funktioniert hat, kann es weitergehen.

Die Quelldateien WienerHopf.tex (download) und Austauschbar.tex (download) enthalten einige Befehle und könnten für die ersten Schritte als Beispiel nützlich sein. Die zugehörigen pdf-Dateien sind WienerHopf.pdf und Austauschbar.pdf. Beide Beispieldateien binden die Datei global.tex (download) ein, welches meine LaTeX-Konfiguration enth"alt. Die Beispieldateien können nur übersetzt werden, wenn sich global.tex in demselben Verzeichnis befindet.