Unendliche Spiele

» Diese Veranstaltung wird auf deutsch gehalten.

» Es gibt einen L2P-Lernraum zu dieser Veranstaltung.

Vorlesung im Wintersemester 2008/2009

ArtTermine/OrtBeginnVeranstalter
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