Zur Seitennavigation oder mit Tastenkombination für den accesskey-Taste und Taste 1 
Zum Seiteninhalt oder mit Tastenkombination für den accesskey und Taste 2 
QIS-Portal vom * 11. - 15.11.2019 * nicht verfügbar! Weitere Informationen unter: https://www.tu-bs.de/it/aktuelles
Startseite    Anmelden    Semester: WiSe 2019/20      Switch to english language    Hilfe    Sitemap
Logout in [min] [minutetext]

Spiele mit perfekter Information - Einzelansicht

  • Funktionen:
Grunddaten
Veranstaltungsart Übung Langtext
Veranstaltungsnummer 4212058 Kurztext
Semester SoSe 2019 SWS 2.0
Erwartete Teilnehmer/-innen 50 Max. Teilnehmer/-innen 50
Rhythmus keine Übernahme Studienjahr
Credits Belegung Keine Belegpflicht
Hyperlink  
Sprache englisch
Termine iCalendar Export für Outlook
  Tag Zeit Rhythmus Dauer Raum Raum-
plan
Lehrperson Status fällt aus am Max. Teilnehmer/-innen
Einzeltermine anzeigen
iCalendar Export für Outlook
Mi. 15:00 bis 16:30 woch Mühlenpfordtstraße 23 (4103) - 4103.03.358 - IZ 358 Raumplan       50
 
Zuordnung zu Einrichtungen
Institut für Theoretische Informatik
Inhalt
Kommentar QUALIFIKATIONSZIELE:
Die Studierenden erlernen das Modellieren von Systemen als Spiele mit perfekter Information und das Lösen solcher Spiele. Den Schwerpunkt der Vorlesung bilden algorithmische Analyseverfahren. Die Studierenden besitzen die Fähigkeit, mit Hilfe dieser Verfahren Informationen über die Spiele (und damit über die modellierten Systeme), insbesondere ihre Gewinnregionen und Gewinnstrategien, berechnen zu können.

INHALTE:
Spiele auf endlichen Graphen
============================
Reachability- und Safety-Spiele
Büchi- und Co-Büchi-Spiele
Streett-, Rabin- und Muller-Spiele
Paritätsspiele, McNaughtons & Zielonkas Algorithmus
Spiele auf gewichteten Graphen

Spiele auf unendlichen Graphen
==============================
Pushdown-Spiele (Reachability-, Liveness-, Paritätsspiele)
Kontextfreie Spiele (Reachability-, Liveness-, Paritätsspiele)
Cachats Saturierungsalgorithmus
Summary-Algorithmus
Walukiewiczs Reduktion
Regularität von Gewinnregionen

Entscheidbarkeit & Determiniertheit
===================================
Unentscheidbare Spiele
Borel Determinacy Theorem, Nichtdeterminierte Spiele

Anwendungen
===========
Spiele in der Verfikation
Synthese als Spiel
Rabin's Tree Theorem
Literatur B. Khoussainov, A. Nerode. Automata Theory and its Applications. Birkhäuser, 2001.

M. Hofmann and M. Lange. Automatentheorie und Logik. Springer-Verlag, 2011.

Th. Cachat. Symbolic Strategy Synthesis for Games on Pushdown Graphs. In Proc. of the 29th International Colloquium on Automata, Languages and
Programming, ICALP, pages 704-715, Springer, 2002.

I. Walukiewicz. Pushdown Processes: Games and Model Checking. In Journal Information and Computation - Special issue on FLOC '96, pages 234?263.
Academic Press, 2001. Pages 234?263

L. Holik, R. Meyer, S. Muskalla. Summaries for Context-Free Games. In Proc.of 36th IARCS Annual Conference on Foundations of Software Technology and
Theoretical Computer Science, FSTTCS, pages 41:1-41:16. LIPIcs, 2016.

O. Serre. Note on winning positions on pushdown games with omega-regular winning conditions. In Information Processing Letters, Vol 85 Issue 6, pages 285-291. Elsevier, 2003.

D. A. Martin. A purely inductive proof of Borel determinacy. In Proc. Sympos. Pure Math., Vol 42, page 303?30. AMS, 1985.

U. Zwick, M. Paterson. The complexity of mean payoff games on graphs. In Theoretical Computer Science, Vol. 158, Issues 1?2, pages 343?359. Elsevier, 1996.
Bemerkung 1 Prüfungsleistung: Klausur (90 Minuten) oder mündliche Prüfung (30 Minuten). 1 Studienleistung: Lösung von Übungsaufgaben; 60% der Übungsaufgaben müssen erfolgreich bearbeitet werden.
Server: LSF16 Impressum & Datenschutz