Proseminar: Markovketten in der Algorithmik

Dienstags, 14.00 Uhr bis 16.00 Uhr, im Raum MI 03.11.018

[Zusammenfassung] [Themenliste] [Anmeldung] [Vorbesprechung] [Termine] [Hinweise] [Literatur]

Zusammenfassung

Unter einer Markovkette versteht man einen stochastischen Prozess, der die Eigenschaft der "Gedächtnisslosigkeit" besitzt. Unter "Gedächtnislosigkeit" versteht man, dass die zukünftige Entwicklung eines Prozesses nur von dem aktuellen Zustand abhängt und nicht von der Vergangenheit.

Trotz ihrer einfachen Struktur lassen sich sehr viele Phänomene (z.B. Entwicklung von Spielen, Populationen, Wettersimulation) mit Hilfe von diskreten Markovketten beschreiben und - gerade wegen der einfachen Struktur - gut analysieren. Eine weitere Anwendung finden Markovketten in Bereich des "Sampling". Unter "Sampling" versteht man das "Ziehen eines zufälligen Elementes aus einer Menge von Elementen". Solche Mengen sind zum Beipiel "Die Menge aller Spannbäume eines Graphen", "Die Menge aller Hamiltonkreise eines Graphen" oder allgemeiner "Die Menge aller zulässigen Lösungen eines Problems". Oft sind diese Mengen so groß, dass der triviale Samplingansatz nicht effizient durchführbar ist: "Erzeuge alle Elemente der Menge und ziehe ein Element zufällig." In solchen Fällen kann man mit Hilfe von Markovkette dennoch effizient Samplen. Zuletzt kann man das "zufällige Ziehen" auch insoweit "beeinflussen", dass "bessere Elemente" wahrscheinlicher werden als "schlechtere Elemente". Das ist ein genereller Ansatz, einen randomisierten Algorithmus zur Lösung eines Problems zu entwerfen.

Die Proseminarteilnehmer sollen sowohl die mathematischen Grundlagen der Theorie der Markovketten, als auch algorithmische Bespiele kennenlernen. Die Vortragsthemen sind kurz und überschaubar gehalten, es wird in diesem Proseminar Wert auf Anschaulichkeit und sichere Präsentation (inklusive übersichtlicher Slides [mit Latex oder Texpoint]) gelegt.

Themenliste:

Einführung in die Wahrscheinlichkeitsrechnung
Markov Ketten: Einführung, Eigenschaften, Beispiele
Konvergenz von Markov Ketten
Das Hard-Core-Modell und der Gibbs-Sampler
Konvergenz von MCMC-Algorithmen
"Exact Sampling: Der Propp-Wilson-Algorithm"
"Bounding the Space: Sandwiching"
Improved Propp-Wilson-Algorithm
Simulated Annealing
Metropolis-Hastings Algorithmus

zusätzliche Themen:

Lineare Algebra und Markov Ketten
Markov Entscheidungsprozesse
Simulated Annealing

Das erste Thema "Einführung in die Wahrscheinlichkeitsrechnung" wird von einem Betreuer gehalten. Die Themen 2,3 ud 11 beschäftigen sich mit den Grundlagen der Theorie der Markovketten. Die Themen 4 bis 8 beschäftigen sich mit dem Problem des "Sampling". Die Themen 9, 10, 12 und 13 beschäftigen sich mit Optimierungsverfahren auf Markovketten.

Anmeldung

Interessenten/innen können sich bei der Vorbesprechung oder vorab per Email an eckhardt 'that at' in 'dot' tum 'dot' de mit Subject "Markov-Ketten (Anmeldung)" anmelden. In der E-Mail sollen folgende Informationen enthalten sein:

Name, Vorname
Studiengang und Studienfach
Semester
E-Mail (nur Adressen @in.tum.de)
bevorzugtes Thema

Vorbesprechung

Die Vorbesprechung für das Proseminar findet am 10.02.2005 im Raum MI 03.11.018 um 15.00 Uhr s.t. statt.

Termine und Betreuer

Termin	Thema	Vortragender	Literatur	Betreuer
26.04.	Markov Ketten und Wahrscheinlichkeitstheorie: Eine Einführung	Betreuer	[Hag02], Kapitel 1ff.	--
03.05.	Konvergenz von Markov Ketten	Manfred Pauli	[Hag02], Kapitel 5+6	Jan Griebsch
24.05.	Konvergenz von MCMC-Algorithmen	Thomas Kasper	[Hag02], Kapitel 8	Moritz Maaß
31.05.	Exact Sampling: Der Propp-Wilson-Algorithm	Markus Gerstel	[Hag02], Kapitel 10	Hanjo Täubig
07.06.	Bounding the Space: Sandwiching	Jason Franklin	[Hag02], Kapitel 11	Sven Kosub
14.06.	Das Hard-Core-Modell und der Gibbs-Sampler	Musa Niyazi Ilker Hatipoglu	[Hag02], Kapitel 7	Stefan Pfingstl

Hinweise

Ein Schein für die erfolgreiche Teilnahme am Proseminar wird vergeben, wenn folgende Leistungen erbracht worden sind (die Gesamtnote setzt sich aus gewichteten Einzelnoten zusammen):

Probevortrag (ohne Bewertung)	Der Probevortrag erfolgt spätestens zum angegebenen Termin beim Betreuer. Vorzulegen sind dabei die fertig ausgearbeiteten Folien oder ähnliche Präsentationshilfsmittel und die Erstfassung der Seminarbeit. Vereinbaren Sie für den Probevortrag rechtzeitig einen Termin beim Betreuer (spätestens eine Woche vor dem anvisierten Termin). Versuchen Sie, alle Verbesserungsvorschläge Ihres Betreuers umzusetzen.
Seminarvortrag (in mindestens zufriedenstellender Qualität)	Der Seminarvortrag ist zum festgelegten Termin zu halten und dauert 45 (+/-5) Minuten. Tafelvorträge werden nicht akzeptiert. Nach dem Vortrag muss auf Fragen aus dem Publikum eingegangen werden.
Seminararbeit (in mindestens zufriedenstellender Qualität)	Die Endfassung der Seminarbeit ist spätestens 2 Wochen nach dem Votrag als TeX-Datei und Postscript-Datei abzugeben. Der Umfang der Seminararbeit beträgt 5 (+/- 1) Seiten unter LaTeX, beispielsweise im LNCS-Style. Die Seminararbeit sollte von jedem interessierten Leser auch ohne Vortrag verstanden werden können. Auchten Sie besonders darauf, das Thema, über das Sie schreiben zu motivieren und Zusammenhänge herzustellen. (Hinweise siehe unten).
Anwesenheit bei allen Vorträgen	Bei den einzelnen Vorträgen wird eine Anwesenheitsliste geführt. Da nur sehr wenige Vorträge stattfinden besteht Anwesenheitspflicht.

Ablauf der Vorbereitung

Der Vortrag und die Ausarbeitung müssen mit dem Betreuer abgesprochen werden. Hierzu sind nachfolgende Terminvorgaben bindend (soweit nicht anders mit dem Betreuer abgestimmt). Werden die Termine nicht eingehalten, führt dies zur Streichung des Vortrags und zum Nichtbestehen des Seminars:

bis 5 Wochen vor dem Vortrag		erstes Treffen mit dem Betreuer (vor dem Treffen ist die Literatur bereits zu lesen); der genaue Termin ist bei den Vortragsterminen angegeben;
bis 3 Wochen vor dem Vortrag		Gliederung des Vortrags und der Ausarbeitung mit dem Betreuer besprechen;
bis 1 Woche vor dem Vortrag		Probevortrag vor den Betreuer; fertige Folien und vollständige erste Version der Ausarbeitung mit dem Betreuer abstimmen;
bis 2 Wochen nach dem Vortrag		fertige Ausarbeitung abgeben.

Hinweise zur Anfertigung einer Seminararbeit

	Die Seminararbeiten werden nach der letzten Seminarveranstaltung online zur Verfügung gestellt. Damit eine einheitliche Form erzielt wird, müssen alle Ausarbeitungen mit dem Textsatzsystem LaTeX erstellt werden. Hierzu sind folgende Richtlinien zu beachten:
	Es ist der LNCS-Style (die Datei llncs.cls) des Springer-Verlages zu verwenden. Der folgende Rahmen ist zu verwenden (seminararbeit.tex). Dabei dürfen die Seitengröße und der Font nicht verändert werden. Ein Beispiel kann in der Datei example.tex gefunden werden (das Bild example.eps wird eingebunden) Die Ausarbeitung soll auf die verwendete Literatur verweisen, diese Literatur ist mit BibTeX zu verwalten und in einer eigenen Datei zu speichern (hier die zum Beispiel gehörende Datei: example.bib).
	Bei Fragen zu LaTeX sei einerseits auf die folgenden Links hingewiesen, ferner kann auch der Betreuer um Hilfestellungen bzw. Literaturangaben gebeten werden:
	LaTeX Kochbuch RBG-Seite zu LaTeX
	Eine weitere Anleitung zur Erstellung von Ausarbeitungen finden sie hier.
	Informationen zur Installation von LaTeX unter Windows finden Sie hier.

Hinweise zur Gestaltung der Vorträge

Wer seine Folien mit LaTeX erstellen möchte findet hier einige Hinweise (einschließlich Rahmen-Datei als Vorlage)

Literatur

[Hag02]

Olle Häggström: Finite Markov Chains an Algorithmic Applications, Cambridge University Press, 2002, ISBN 0521813573 (Link zur Onlineausgabe)

Stefan Eckhardt

Last modified: Thu Mar 31 16:47:08 2005