Seminar Markov-Ketten Algorithmen, WS 95/96

Artur Czumaj, Miroslaw Kutylowski, Christian Scheideler

Anmeldung: elektronisch bei Artur Czumaj (artur@uni-paderborn.de) bis Ende Oktober.
Hier kann man Artur eine email schicken.

Vorbesprechung: die Leute, die Interesse haben, sollten sich bei einem der Veranstalter melden,
Sprechstunden nach Vereinbarung und zusätzlich wie folgt:

• Artur Czumaj
  Freitag: 9-11 Uhr, F1.316
• Miroslaw Kutylowski
  Freitag: 9-11 Uhr, F1.219,
  zusätzlich direkt nach Vorlesungen in Campus zu erreichen:
  Mittwoch, 17.30, C2 (nicht am 25.10)
  Freitag, 15.30, C2
• Christian Scheideler
  Freitag: 9-11 Uhr, F1.125

Voraussetzungen: Grundkenntnisse in Stochastik, Algorithmen und Datenstrukturen

Scheinerwerb: Ausarbeitung und Seminarvortrag

Prüfungsgebiet: H II, Th I

Termine:

• Anmeldung zum Seminar bis Ende Oktober
• Einführung in Markov-Ketten in den ersten 2 Wochen im November
  (1 bis 2-stündige Vorlesung durch Betreuer)
• Seminarvorträge im Januar
  (ca. 3 Treffen, insgesamt 6 Vorträge)

Raum: im Gebäude an der Fürstenallee,

Inhaltsübersicht:

• Einführung in Markov Ketten und den Begriff "rapid mixing"
• Approximierung der Permanente und Zählen von perfekten Matchings
• Uniforme Generierung von zufälligen Graphen
• Abschätzung des Volumens von konvexen Körpern

Literatur:

• A. Sinclair, ``Algorithms for Random Generation & Counting: A Markov Chain Approach'', Birkhauser, Boston, 1993.
• M. Jerrum, ``The "Markov chain Monte Carlo" method: Analytical techniques and applications'', Proc. IMA Conference on Complex Stochastic Systems and Egngineering, Oxford University Press, Oxford, 1995, pp. 191-207.
• R. Kannan, ``Markov chains and polynomial time algorithms'', Proc. 34th IEEE Symposium on Foundations of Computer Science, 1994, pp. 656-671.

Weitere Informationen (Termine,...) werden durch email verschickt,

Ausarbeitungen werden durch WWW zugänglich gemacht unter dieser Adresse