Seminar Logik, Komplexität, Spiele: Algorithmische Aspekte der Paritätsspiele

SS 2011

Organisation

Die Veranstaltung wird als Blockseminar am Ende der Vorlesungszeit durchgeführt.

Zeitplan

25.04. Gliederung
30.05. Ausarbeitung
20.06. Endgültige Fassung
01.07. Folien
Juli Vorträge

Programm

Dienstag, 19. Juli
9:00 9:45 Felix Canavoi Small Progress Measures
9:50 10:35 Sarah Winter Discrete Strategy Improvement
11:00 11:45 Kevin Schewior Lower Bounds for Strategy Improvement

Themen

Thema Vortragende(r) Betreuer(in) Literatur
Discrete Strategy Improvement Sarah Winter Bernd Puchala [JV00]
Small Progress Measures Felix Canavoi Faried Abu Zaid [J00]
Lower Bounds for Strategy Improvement Kevin Schewior Roman Rabinovich [F09]

Literatur

[F09] O. Friedmann. A Super-Polynomial Lower Bound for the Parity Game Strategy Improvement Algorithm as We Know it. CoRR, vol. abs/0901.2731, 2009.
[J00] M. Jurdzinski. Small Progress Measures for Solving Parity Games. In STACS, pp. 290-301, 2000.
[JV00] J. Vöge and M. Jurdzinski. A Discrete Strategy Improvement Algorithm for Solving Parity Games. In CAV, pp. 202-215, 2000.

Zuordnung

  • Informatik (B.Sc.)/Seminar Informatik
  • Mathematik (B.Sc.)/Seminar: Logik, Komplexität, Spiele
  • Informatik (M.Sc.)/Seminar Theoretische Informatik
  • Mathematik (M.Sc.)/Seminar: Logik, Komplexität, Spiele (Reine Mathematik)
  • Informatik (D)/Hauptstudium/Theoretische Informatik
  • Mathematik (D)/Hauptstudium/Reine Mathematik
  • Informatik (S II)
  • Mathematik (S II)/Hauptstudium/Modul Algebra
  • Mathematik (S II)/Hauptstudium/Modul Angewandte Mathematik

Voraussetzungen

  • Modul Mathematische Logik
  • für B.Sc. Informatik: bestandenes Modul "Einführung in das wissenschaftliche Arbeiten (Proseminar)"

Rückfragen

Erich Grädel, Faried Abu Zaid, Bernd Puchala, Roman Rabinovich