<-- Diese Seite  ---------   http://www.math.tu-berlin.de/~felsner/Lehre/semMK08.html -->

Seminar
Ausgewählte Kapitel der Graphentheorie:
Markov Ketten & Random Sampling


Wintersemester 2008/09
Prof. Stefan Felsner
Sprechstunde n.V.

LV-Nr.: 0230 L 316


Zeichnung



Seminarwochenende: 6.-9. Februar 2009

Blitzvorträge: Fr. 5. Dez., 14:15 Raum MA 550


Thema:

Wir beschäftigen uns mit Markov Ketten die es ermöglichen ein zufälliges Element aus einer großen kombinatorischen Menge zu erzeugen (random sampling). Beispiele für solche kombinatorischen Mengen sind: Meistens ist es nicht schwer eine Markov Kette anzugeben die wenn man sie lange genug laufen läßt ein zufälliges Element ausgibt. Interessant ist die mathematische Behandlung der Frage, was ist lange genug. Dafür gibt es Techniken wie Kanonische Wege und Couplings. Dies und die Zusammenhänge mit approximativem Zählen sind Thema des Seminars.

Vorträge:

Thema Vortragende Quelle Betreuung
Basics on Probability and Markov Chains >>> Eigenlektüre <<< OH 1-15
Fundamentals of Markov Chains Tillmann Miltzow OH 23-43 Felsner
Coupling and Linear Extensions Josef Levant Jer.Kap4 &
Bubley-Dyer
Massow
The Propp-Wilson Algorithm Laura Buhmann OH 76-98 Massow
Canonical Paths and Matching Julia Rucker Jer.Kap5 Heldt
Sampling Knapsack Solutions Adrian Raeder Morris-Sinclair & Guruswami (Survey) Ueckerdt
Sampling and Counting - Inapproximability Sofia Börner Jer.Kap3+7 Ueckerdt
Markov Chains for Lattice Paths Tobias Friedel Luby-Randall-Sinclair & Martin-Randall Ueckerdt
Markov Chains for Spanning Trees Kolja Knauer Wilson & Propp-Wilson
Conductance and the Volume of a Convex Body Ingo Spiegelberg Jer.Kap6 &
Karzanov-Khachian
Felsner
Massow
The Mixing Rate of the Triangulation Walk Laura Traverso McShine-Tetali Felsner
Eulerian Orientations of the Triangular Lattice Bernhard Schmidt Creed Felsner
Shuffling a Deck of Cards Gregor Myrach Mann Heldt

Literatur:

Termine:

Wir werden das Seminar als Blockseminar im Umland durchzuführen: Seminarwochenende: 6.-9. Februar 2009, KiEZ Frauensee
Weitere Termine sind:

Zielgruppe:

Studentinnen und Studenten der Mathematik, Techno- und Wirtschaftsmathematik im Hauptstudium.
       Dieses Seminar wird im Rahmen des Studienschwerpunkts Diskrete Strukturen empfohlen.


Zuletzt bearbeitet 12. Nov. 2008