20. August - Die Informationen auf dieser Seite sind noch vorläufig.
12. Oktober - Der Termin für die erste Vorlesung wurde ergänzt
Die Vorlesung wird von Prof. Dr. Roland Meyer gehalten. Die Übung wird von Eren Keskin gehalten.
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 werden auch kompliziertere Spiele (zB. Mean Payoff Spiele) behandeln, die wie Paritätsspiele im Schnitt von NP und coNP liegen. Wir werden auch ihre Verbindung zu Linear Programming (im tropischen Algebra) behandeln, die zu neuen Ansätzen zur Lösung dieses Problems führen mag.
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.
Diese Vorlesung wird ähnliche Themen wie die SmPI Vorlesung von WS 24/25 und WS25/26 behandeln. Die Notizen aus dieser Vorlesung können Sie bei der Webseite dieser Vorlesung finden. Allerdings wird es dieses Jahr auch neue Themen geben. Die in der Vorlesung besprochenen Notizen werden hier veröffentlicht.