Unendliche Spiele
» This course is given in German.
» There is an L2P learning room for this course.
Vorlesung im Wintersemester 2008/2009
| Art | Termine/Ort | Beginn | Veranstalter |
|---|---|---|---|
| V2 | Di 10:00-11:30, AH VI | 14.10.2008 | Thomas |
| Ü1 | Fr 14:50-15:35, AH II | 17.10.2008 | Thomas, Neider |
Inhalt
Bei den unendlichen Spielen, die in dieser Vorlesung untersucht werden sollen, handelt es sich um Spiele von unendlicher Dauer, die auf endlichen Graphen gespielt werden. Eine Partie in einem solchen Spiel ist ein unendlicher Pfad durch den Graphen, der von zwei Spielern, die einen Spielstein abwechselnd entlang der Kanten ziehen, generiert wird. Welcher der beiden Spieler die Partie gewinnt, hängt davon ab, welche Knoten des Graphen besucht bzw. unendlich oft besucht werden. Spiele dieser Art werden in der Theorie der Verifikation und Synthese nicht-terminierender Systeme, die mit einer Umgebung interagieren, benutzt.
In der Vorlesung werden Algorithmen zur Berechnung von Gewinnstrategien für verschiedene Arten von Gewinnbedingungen in dem oben beschriebenen Spielmodell vorgestellt. Gegen Ende der Vorlesung werden erweiterte Modelle betrachtet, wie z.B. nebenläufige Spiele, bei denen die Spieler nicht abwechselnd ziehen, sondern gleichzeitig ihre Entscheidung treffen, oder stochastische Spiele, bei denen neben den Zügen der beiden Spieler von einigen Knoten des Graphen unkontrollierte Züge gemäß einer gegebenen Wahrscheinlichkeitsverteilung ausgeführt werden.
Vorwissen
Gute Kenntnisse der Grundveranstaltungen Automatentheorie und Formale Sprachen bzw. Formale Systeme, Automaten, Prozesse werden vorausgesetzt.
Credit Points
4 ECTS
Übungsblätter
Aufgrund eines Problems mit dem L2P-Lernraum ist die erste Übung ausnahmsweise hier zu finden.
Übungsblatt 1