Logik und Spiele
SS 2009
Aktuelles
- Die Übung am Mittwoch, dem 24.6., wird wegen des RWTH Sports-Day (Dies) auf Donnerstag, den 25.6., um 13:30 Uhr in Raum 4116 (Seminarraum des Lehrstuhls) verschoben.
- Eine vorläufige Version des ersten Kapitels des Vorlesungsskripts steht zum Download bereit. Das zweite Kapitel wird noch überarbeitet.
- Am Mittwoch, dem 10.6., finden wegen des Studieninformationstags (Dies) weder Vorlesung noch Übung statt.
- Übungsbetrieb: Die Übungen können in Gruppen bearbeitet werden (max. 3 Studenten) und sind spätestens dienstags um 12 Uhr im Kasten am Lehrstuhl (bzw. zuvor in der Vorlesung) abzugeben. Neue Aufgabenblätter werden in der Regel ab dienstags auf der Homepage verfügbar sein.
Termine
Art | Termin | Ort | Veranstalter | ||||
---|---|---|---|---|---|---|---|
V4 | Di | 10:00 | – | 11:30 | AH I | Beginn 21. April | Ł. Kaiser |
Mi | 10:00 | – | 11:30 | AH I | Beginn 22. April | E. Grädel | |
Ü2 | Mi | 17:15 | – | 18:45 | 5056 | Beginn 29. April | T. Ganzow |
Übungen
- Übung 1 [ps] [pdf]
- Übung 2 [ps] [pdf]
- Übung 3 [ps] [pdf]
- Übung 4 [ps] [pdf]
- Übung 5 [ps] [pdf]
- Übung 6 [ps] [pdf]
- Übung 7 [ps] [pdf]
- Übung 8 [ps] [pdf]
- Übung 9 [ps] [pdf]
- Übung 10 [ps] [pdf]
- Übung 11 [ps] [pdf]
Skript
- Alle Kapitel [pdf] [pdf-2up]
- Kapitel 1: Finite Games and First-Order Logic [pdf] [pdf-2up]
- Kapitel 2: Parity Games and Fixed-Point Logics [pdf] [pdf-2up]
- Kapitel 3: Infinite Games [pdf] [pdf-2up]
- Kapitel 4: Basic Concepts of Mathematical Game Theory [pdf] [pdf-2up]
Inhalt
Lernziele
Verständnis der grundlegenden Begriffe und Probleme der algorithmischen Spieltheorie und der Zusammenhänge von Logik und Spieltheorie. Kenntnis der logischen und algorithmischen Methoden zur Behandlung unendlicher Spiele. Verständnis der Anwendungen unendlicher Spiele als Modell reaktiver Systeme und zur Auswertung logischer Formeln.
Themen
Fundamentale Modelle und Begriffe der Spieltheorie. Endliche und unendliche Spiele. Model-Checking-Spiele. Determinierte und nichtdeterminierte Spiele. Borel-Spiele, Muller-Spiele und Paritätsspiele. Komplexität und Definierbarkeit von Gewinnregionen. Algorithmische Synthese und Optimierung von Gewinnstrategien. Mehrpersonenspiele.
Literatur
Voraussetzungen
- Mathematische Logik
Zuordnung
- Mathematik (D): Reine Mathematik
- Mathematik (B.Sc.)
- Informatik (D): Theoretische Informatik, Vertiefungsfach, Anwendungsfach Mathematik
- Lehramtskandidaten Informatik: Mathematische Methoden der Informatik (C)
- Software Systems Engineering (M.Sc.): Theoretical Computer Science
Leistungsnachweis
- Bachelor- und Masterstudiengänge: Lösen von 50% der Übungsaufgaben und Bestehen einer mündlichen Prüfung im Umfang von 30 Minuten
- Diplomstudiengänge: Übungsschein bei Lösen von 50% der Übungsaufgaben und aktiver Teilnahme an den Übungen
Rückfragen
Erich Grädel, Tobias Ganzow, Łukasz Kaiser