18. Juli - Die Informationen auf dieser Seite sind noch vorläufig.
Der Modulverantwortliche ist Prof. Dr. Roland Meyer. Die Veranstaltung wird zudem von Eren Keskin betreut.
Diese Vorlesung behandelt die neuen bahnbrechenden Entwicklungen im Bereich der Paritätsspiele. Paritätsspiele sind ein grundlegendes Werkzeug für reaktive Programsynthese. Bei reaktiver Programsynthese besteht das Ziel darin, ein Programm zu generieren, das trotz der Aktionen einer gegnerischen Umgebung Fehler vermeidet. Um so ein Programm zu generieren, modellieren wir das Zusammenspiel von dem Programm und der Umgebung als Spiel für zwei Spieler, und dann "lösen" wir das Spiel. Das heißt, dass wir nach einer Strategie suchen, die den Gewinn garantiert. Im Rahmen dieser Vorlesung interessieren wir uns nur für Spiele mit perfekter Information. Dies sind Spiele, wie z.B. Schach, bei denen beide Spieler volle Information über den aktuellen Zustand der Spiele haben. Paritätsspiele bilden eine fundamentale Subklasse von Spielen mit perfekter Information. Sie können komplexe Gewinnbedingungen ausdrücken (z.B. "Spieler A besucht Region W unendlich oft"), und erlauben dabei eine relativ effiziente algorithmische Behandlung.
Die genaue Komplexität von Paritätsspielen ist ein großes ungelöstes Problem der Theoretischen Informatik. Obwohl es bewiesen ist, dass das Problem im Schnitt der Komplexitätsklassen NP und coNP liegt, konnte noch nicht gezeigt werden, dass das Problem in P liegt. In dieser Vorlesung, untersuchen wir Paritätsspiele, und zielen darauf ab, ein in sich geschlossenes Verständnis der jüngsten bahnbrechenden Ergebnissen zu entwickeln, die zeigen dass das Problem in Zeit nO(log(n)) lösbar ist. Wir behandeln auch Ergebnisse, die die Beschränkungen von den neuen Methoden zeigen. Letztlich werden wir einen kurzen Blick auf kompliziertere Spiele (Mean Payoff Spiele und Discounted Payoff Spiele) werfen, die wie Paritätsspiele im Schnitt von NP und coNP liegen.
Die Übungsblätter werden hier veröffentlicht. Das Abgabedatum von einem Übungsblatt wird auf dem Übungsblatt bekanntgegeben. Bitte Ihre Lösungen vor der Übung (am Abgabedatum) abgeben. Email Abgaben an e.keskin@tu-bs.de (als PDF) werden auch akzeptiert. Die Abgabe ist allein oder in Zweiergruppen möglich.
Wann das erste Blatt erscheinen wird, und weitere Details werden in Kürze hier angegeben.
Diese Vorlesung wird ähnliche Themen wie die SmPI Vorlesung von WS 24/25 behandeln. Die Notizen aus dieser Vorlesung können Sie bei der Webseite dieser Vorlesung finden. Allerdings wird es dieses Jahr neue Themen, sowie geupdatete Notizen geben. Die neuen Notizen werden hier veröffentlicht.