Veranstaltungsnummer 042617
Titel Logik und Komplexität (INF-MSC-509)
Veranstalter Prof. Dr. Thomas Schwentick
Klassifikation Vertiefungsmodul (MPO)
Spezialvorlesung (DPO)
Semester Wintersemester 2017/18
SWS 4 (3V+1Ü)
Kreditpunkte 6
Ort und Zeit

Vorlesung:

  • Dienstag 16:15-18:00 Uhr, OH 12, 2.063
  • Donnerstag 10:15-12:00 Uhr OH 12, 2.063
    (ca 14-tägig)
  • Beginn: Dienstag, 10.10.

Übung:

  • Donnerstag 10:15-12:00 Uhr OH 12, 2.063
    (ca 14-tägig)
Querverbindungen Komplexitätstheorie, Logik
Voraussetzungen GTI-Stoff wird vorausgesetzt,
Komplexitätstheorie ist hilfreich, aber nicht unbedingt notwendig
Forschungsbereich (MPO) Algorithmen und Komplexität
Schwerpunktgebiete (DPO) 4 (Algorithmen,...)
5 (Sicherheit und Verifikation)
Materialien Moodle-Arbeitsraum: Link

 

 

Viele algorithmische Probleme lassen sich durch logische Formeln beschreiben. Dabei besteht ein enger Zusammenhang zwischen der Kompliziert der Formeln und der Berechnungskomplexität der Probleme. Dieser Zusammenhang spielt in verschiedenen Bereichen der (theoretischen) Informatik eine Rolle, zum Beispiel in der Theorie Formaler Sprachen, der Datenbanktheorie, der Komplexitätstheorie und im Zusammenhang automatischer Verifikation. Die Vorlesung wird sich mit wichtigen solchen Korrespondenz-Resultaten und mit den grundlegenden Eigenschaften der beteiligten Logiken beschäftigen.

Einzelthemen:

  • Logik erster Stufe: Grundlagen
  • Ausdrucksstärke der Logik erster Stufe: Ehrenfeuchtspiele, Lokalität, andere Methoden
  • Logik und Komplexitätstheorie: Logik zweiter Stufe, Fixpunktlogiken, Trennungen
  • Auswertung logischer Formeln: Algorithmen und Komplexität
  • Logik und Formale Sprachen
  • Logik und Verifikation

Ein Folienskript wird parallel zur Vorlesung erstellt.

Weitere Literatur:

  • Leonid Libkin: Elements of Finite Model Theory, Springer, 2004
  • Immerman: Descriptive Complexity, Springer, 1999

Hier finden Sie die Übungsblätter.

Hier finden Sie die Vorlesungfolien.