Algorithmische Modelltheorie

SS 2010

Aktuelles

  • Das letzte Kapitel des Skripts ist jetzt online.
  • Am Dienstag, dem 13.07., findet die Vorlesung nicht statt.
  • Am Mittwoch, dem 09.06., findet die Vorlesung wegen des Studieninformationstags (Dies) nicht statt.

Termine

Art Termin Ort   Veranstalter
V4 Di 10:00 – 11:30 AH I Beginn 20. April E. Grädel, Ł. Kaiser
Mi 10:00 – 11:30 AH I Beginn 14. April E. Grädel, Ł. Kaiser
Ü2 Mi 17:15 – 18:45 5056 Beginn 28. April R. Rabinovich

Übungen

Skript

Inhalt

  • Entscheidbare und unentscheidbare Theorien
  • Endliche-Modell-Eigenschaft
  • Deskriptive Komplexität: Logische Charakterisierung von Komplexitätsklassen
  • Lokalität der Prädikatenlogik, 0-1-Gesetze
  • Logiken mit transitiver Hülle, Fixpunktlogiken

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

  • Mathematik (D): Reine Mathematik
  • Mathematik (B.Sc.): 5./6. Semester
  • Informatik (D): Theoretische Informatik, Vertiefungsfach, Anwendungsfach Mathematik
  • Informatik (M.Sc.): Theoretische Informatik
  • 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, Łukasz Kaiser, Roman Rabinovich