Seminar Logik in der Informatik

Seminar im SoSe 2012

Gehalten von Prof. Dr. Nicole Schweikardt

Aktuelles

• Wichtige Information für alle Seminarteilnehmer/innen: Wenn Sie in einem Bachelor- oder Masterstudiengang eingeschrieben sind, müssen Sie sich rechtzeitig beim Prüfungsamt für dieses Seminar anmelden! (Firsten und weitere Informationen können Sie beim Prüfungsamt Informatik in Erfahrung bringen.)

Einführung

Im Seminar werden aktuelle Themen aus dem Bereich Logik in der Informatik behandelt.
Lernziele: Kenntnis grundlegender Methoden und Verfahren, Einübung von Literatursuche und -analyse sowie Präsentationstechniken. Theoretische Kompetenz; autodidaktische Kompetenz.

Kürzel laut Studienordnung: B-LI-BS, M-LI-S, Bioinf Modul 21.  Creditpoints: 5.  SWS: 2 S.

Ort und Zeit

Das Seminar ist als Blockseminar organisiert. Das Seminar findet i.d.R. in Raum 117, Robert-Mayer-Str. 11-15 statt. Termine:

1. Donnerstag, den 12.04.2012, 14:15-16:00, Raum 117:
   Vorbesprechung und Themenvergabe
2. Donnerstag, den 19.04.2012, 14:15-16:00, Raum SR 9:
   Überblicksvortrag zur Einleitung ins Thema des Seminars
3. "Deadline 1": bis spätestens Donnerstag, 31.05.2012, 14:15 Uhr:
   Treffen jedes Seminarteilnehmers mit einem der Organisatoren des Seminars: Klärung von Detailfragen zum Vortragsthema und Vorlage eines groben Konzepts zum Vortrag und zur schriftlichen Ausarbeitung des Vortragsthemas
4. "Deadline 2": bis spätestens Donnerstag, 21.06.2012, 14:15 Uhr:
   Abgabe der schriftlichen Ausarbeitung des Vortragsthemas bei den Organisatoren des Seminars (Layout: wie in der Layout-Vorlage angegeben)
5. "Deadline 3": bis spätestens Donnerstag, 05.07.2012, 14:15 Uhr:
   Treffen jedes Seminarteilnehmers mit einem der Organisatoren des Seminars: Vorlage eines detaillierten Vortragskonzepts inkl. Vortragsfolien
6. 23. und 24.07.2012, 8:15 - 12:00 Uhr:
   Blockseminar mit Vorträgen der am Seminar teilnehmenden Studierenden (in Raum 117 oder einem anderen noch festzulegenden Raum)

Unterstützung

Während der Vorlesungszeit stehen jeden Mittwoch von 15:00 bis 15:45 Termine bei Nicole Schweikardt zur Verfügung, während denen Seminarteilnehmer Fragen zur Literatur klären können. Falls Sie einen solchen Termin wahrnehmen wollen, melden Sie sich bitte spätestens am Tag vorher per Email an.

Einige generelle Informationen darüber, wie man gute Vorträge im Fach Informatik halten kann, finden sich hier.

Einführende Literatur

• Zur Vorbereitung aufs Seminar wird empfohlen, die Logik-Kapitel der Vorlesung Diskrete Modellierung sowie einige grundlegende Kapitel der Vorlesung Logik in der Informatik durchzuarbeiten.

Vortragsthemen und Literatur

Mögliche Vortragsthemen

1. Der Satz von Büchi: Eine logische Charakterisierung der regulären Sprachen
2. Der Satz von Fagin: Eine logische Charakterisierung von NP
3. Das Ajtai-Fagin-Spiel und die existentielle monadische Logik zweiter Stufe
4. Erreichbarkeit ist für gerichtete Graphen schwerer als für ungerichtete Graphen
5. Ein Satz von Immerman: Eine logische Charakterisierung von LOGSPACE auf geordneten Strukturen
6. Pebble-Spiele und infinitäre Logiken
7. Der Satz von Immerman und Vardi: Eine logische Charakterisierung von P auf geordneten Strukturen
8. Cai-Fürer-Immerman Graphen und Fixpunktlogik mit Zählquantoren
9. 0-1-Gesetze
10. Ein Satz von Immerman: Eine logische Charakterisierung der Schaltkreiskomplexitätsklasse AC°
11. Die Gaifman-Lokalität von AC°-berechenbaren Anfragen

Literatur zu ausgewählten Vortragsthemen

• Thema 1: Der Satz von Büchi: Eine logische Charakterisierung der regulären Sprachen
  Kapitel 7.1, 7.2, 7.4 und 7.6 in: Leonid Libkin, Elements of Finite Model Theory. Springer-Verlag, 2004.
• Thema 2: Der Satz von Fagin: Eine logische Charakterisierung von NP
  Kapitel 3.2.1 bis 3.2.3 in: Erich Grädel, Finite model theory and descriptive complexity, Kapitel 3 in Grädel, Kolaitis, Libkin, Marx, Spencer, Vardi, Venema, Weinstein (editors), Finite model theory and its applications, Springer-Verlag, 2007.
• Thema 3: Das Ajtai-Fagin-Spiel und die existentielle monadische Logik zweiter Stufe
  Kapitel 7.3, Exercise 7.9 und Exercise 7.10 in: Leonid Libkin, Elements of Finite Model Theory. Springer-Verlag, 2004.
  Zum Lösen von Exercise 7.9 und Exercise 7.10 wird empfohlen, Kapitel 3.2.2 des folgenden Vorlesungsskripts durchzuarbeiten: Nicole Schweikardt, Skript zur Vorlesung "Logik und Komplexität", Sommersemester 2007.
• Thema 4: Erreichbarkeit ist für gerichtete Graphen schwerer als für ungerichtete Graphen
  Kapitel 8.2 in: Neil Immerman, Descriptive Complexity, Springer-Verlag, 1999. Zum Ausarbeiten der Beweisdetails wird empfohlen, die Abschnitte 4 (aus Zeitgründen evtl. ohne den Beweis von Theorem 4.1), 5 und 7 der folgenden Arbeit durchzuarbeiten: Sanjeev Arora, Ronald Fagin, On winning strategies in Ehrenfeucht-Fraisse games, Theoretical Computer Science, volume 174, number 1-2, pages 97-121, 1997.
  Als ergänzende Hintergrundlektüre kann es auch interessant sein, Teile der folgenden Arbeit anzuschauen: Miklós Ajtai, Ronald Fagin, Reachability Is Harder for Directed than for Undirected Finite Graphs. Journal of Symbolic Logic, volume 55, issue 1, pages 113-150, 1990.
• Thema 10: Ein Satz von Immerman: Eine logische Charakterisierung der Schaltkreiskomplexitätsklasse AC°
  Kapitel 6.1 bis 6.4 und Exercise 6.5 in: Leonid Libkin, Elements of Finite Model Theory. Springer-Verlag, 2004.
  Zum Lösen von Libkins Exercise 6.5 wird empfohlen, folgendes durchzuarbeiten: Abschnitt 1.2.1 in Neil Immerman, Descriptive Complexity, Springer-Verlag, 1999.
• Thema 11: Die Gaifman-Lokalität von AC°-berechenbaren Anfragen
  Matthew Anderson, Dieter van Melkebeek, Nicole Schweikardt, Luc Segoufin, Locality from Circuit Lower Bounds. Electronic Colloquium on Computational Complexity (ECCC), volume 18, report number 158, 2011.
  Für dieses Seminar sind insbesondere die Abschnitte 1, 2, 3, 4.1 und 4.4 relevant.
  Ein Mitschnitt eines Vortrags zu diesem Thema beim Newton-Insitute Workshop "Logical approaches to barriers in complexity II" vom 30.03.2012 findet sich hier.

Verbindliche Regeln zum Bestehen des Moduls

Um das Modul zu bestehen sind nötig:

1. Einen Vortrag zu einem der oben genannten Themen zu halten (Dauer: 60 Minuten, plus 10 Minuten zur Diskussion und zur Klärung von Fragen aus dem Publikum),
2. Abgabe einer schriftlichen Ausarbeitung des Vortragsthemas. Abzugeben bis spätestens am 21.06.2012 (14:15 Uhr); Layout: wie in der Layout-Vorlage angegeben,
3. Anwesenheit bei mindestens 75% aller Vorträge und
4. Einhalten der drei oben genannten Deadlines.

Es werden eine Note für den Vortrag und eine Note für die schriftliche Ausarbeitung vergeben. Die Gesamtnote setzt sich folgendermaßen zusammen:

• Falls einer der folgenden 4 Fälle eintritt, so ist die Gesamtnote eine 5.0 und das Modul wird als "nicht bestanden" gewertet:
  1. Der Teilnehmer war an weniger als 75% der Vorträge anwesend.
  2. Der Teilnehmer erhielt für seinen Vortrag die Note 5.0.
  3. Der Teilnehmer erhielt für seine schriftliche Ausarbeitung die Note 5.0.
  4. Der Teilnehmer hat mindestens eine der drei oben genannten Deadlines nicht eingehalten.
• Falls keiner der obigen 4 Fälle eintritt, so wird ein Seminarschein erteilt bzw. das Modul wird als "bestanden" gewertet, und die Gesamtnote setzt sich zu 2/3 aus der Note für den Vortrag und zu 1/3 aus der Note für die schriftliche Ausarbeitung zusammen.