Unendliche Spiele

» This course is given in German.

Vorlesung im Wintersemester 2005/2006

ArtTermine/OrtBeginnVeranstalter
V2 Mo 15:00 - 16:30 AH V 24.10.2005 Löding, Thomas
Ü1 Mi 16:00 - 16:45 AH V 26.10.2005 Löding, Rohde

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.

Vorkenntnisse

Diese Vorlesung wendet sich an Studierende ab dem 5. Fachsemester. Kenntnisse aus der Grundstudiumsvorlesung "Automatentheorie und formale Sprachen" werden vorausgesetzt.

Kombination mit anderen Veranstaltungen

Diese Vorlesung kann mit der Vorlesung "Automata on Infinite Words" (W. Thomas) zu einer vierstündigen Veranstaltung (V4, Ü2) kombiniert werden. In dieser Kombination entspricht der Stoff in etwa dem Inhalt der Vorlesung "Automata and Reactive Systems" vom WS 2002/03.

Wichtiger Hinweis: Die beiden Vorlesungen werden separat behandelt. Die Kriterien für die Ausgabe von Übungsscheinen sind unabhängig für beide Vorlesungen. Bei Erfüllung der Kriterien werden kleine Übungsscheine (V2, Ü1) ausgegeben. Dann und nur dann, wenn man beide kleinen Übungsscheine erhalten hat, kann man diese gegen einen großen Übungsschein (V4, Ü2) eintauschen.

Prüfungsleistung

Um einen Übungsschein (V2, Ü1) bzw. Credit Points zu bekommen, müssen die beiden folgenden Bedingungen erfüllt werden:

  1. Es muss eine bestimmte Anzahl an Punkten in den Übungen erreicht werden (ca. 50%).
  2. Die Abschlussklausur muss bestanden werden.

Wer genügend Punkte in den Übungen erreicht hat, aber die Abschlussklausur nicht mitgeschrieben oder nicht bestanden hat, ist zur Teilnahme an einer Nachprüfung berechtigt.

Wer nicht genügend Punkte in den Übungen erreicht hat, kann die Abschlussklausur mitschreiben, aber er oder sie erhält auch bei Bestehen der Klausur keinen Übungsschein.

Abschlussklausur

Die Abschlussklausur wird am 8. Februar 2005, 16:00 bis 16:45 im Hörsaal AH II geschrieben.

Credit Points

4 ECTS