Algorithmische Modelltheorie

SS 2008

Aktuelles

  • Am Mittwoch, dem 11.6., finden wegen des Studieninformationstags (Dies) weder Vorlesung noch Übung statt.
  • Die Übung am Mittwoch, den 28.5. entfällt wegen des RWTH Sports Day. Das aktuelle Übungsblatt kann daher bis zum 3.6. bearbeitet werden.

Termine

Art Termin Ort   Veranstalter
V4 Di 10:00 – 11:30 AH I   E. Grädel, D. Berwanger
Mi 10:00 – 11:30 AH I Beginn 9. April E. Grädel, D. Berwanger
Ü2 Mi 17:15 – 18:45 5056 Beginn 16. April T. Ganzow

Übungen

Materialien

  • Folie: Interpretation von Q in Z [pdf]

Inhalt

  • Entscheidbare und unentscheidbare Theorien, Interpretationen,
  • Logik und Automaten,
  • monadische Theorien,
  • Prädikatenlogik auf endlichen Strukturen, Lokalität, Ehrenfeucht-Fraisse-Spiele,
  • TC-Logiken, Fixpunktlogiken,
  • Logische Charakterisierung von Komplexitätsklassen,
  • endlich präsentierbare Strukturen, automatische Strukturen.

Lernziele

  • Verständnis der Zusammenhänge von logischer Definierbarkeit und algorithmischer Komplexität (Entscheidbarkeit von Theorien, Auswertungsalgorithmen, logische Charakterisierungen von Komplexitätsklassen).
  • Beherrschen der modelltheoretischen und algorithmischen Methoden zur Analyse der Ausdrucksstärke und Komplexität logischer Spezifikationen auf endlichen und endlich präsentierbaren Strukturen.
  • Fähigkeit, mit den fundamentalen Logiken der algorithmischen Modelltheorie umzugehen und diese in konkreten Szenarien anzuwenden.

Literatur

Voraussetzungen

  • Mathematische Logik

Zuordnung

  • Informatiker: Theoretische Informatik, Vertiefungsfach, Anwendungsfach Mathematik
  • Mathematiker (D): Reine Mathematik
  • Mathematiker (B.Sc.)
  • Lehramtskandidaten Informatik: Mathematische Methoden der Informatik (C)
  • Software Systems Engineering (M.Sc.): Theoretical Computer Science
  • Sonstige: Informatik

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, Dietmar Berwanger, Tobias Ganzow