Logik und Komplexität SoSe 2011

Veranstaltungsnummer  
Titel Logik und Komplexität
Veranstalter Prof. Dr. Thomas Schwentick
Klassifikation Spezialvorlesung (DPO), Vertiefungsmodul (MPO)
Semester Sommersemester 2011
SWS 4 (3V+1Ü)
Kreditpunkte 6
Ort und Zeit

Vorlesung:

  • Dienstag 14:15-16:00 Uhr, OH 14, E02
    • am: 19.4., 26.4., 3.5., 10.5., 17.5., 31.5., 7.6., 28.6., 5.7., 12.7.
  • Mittwoch 10:15-12:00 Uhr OH 16, 205
    • außer: 13.4., 15.6., 22.6.

Übung: 14-tägig 2 Stunden,

  • Mittwoch, 16:15-17:45 Uhr, OH 16, 205
    • 20.4., 27.4., 11.5.,  25.5., 8.6., 6.7., 13.7.
Querverbindungen Komplexitätstheorie, Logik
Voraussetzungen GTI-Stoff wird vorausgesetzt,
Komplexitätstheorie ist hilfreich, aber nicht unbedingt notwendig

Aktuelles

Da mehrere Teilnehmer in der zweiten Vorlesungswoche eine PG-Fahrt haben, ist die zweite Vorlesungsstunde erst am 19.4..

Also: keine Vorlesung am 12.4. und 13.4.!

Logbuch

Hier finden Sie Informationen zum Verlauf der Vorlesung

Übungsblätter

Hier finden Sie die Übungsblätter.

Inhalt

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.

Einige Einzelthemen:

  • Logik erster Stufe: Grundlagen, Auswertung von Formeln
  • Ausdrucksstärke der Logik erster Stude: Ehrenfeuchtspiele, Andere Methoden
  • Logik und Komplexitätstheorie: Logik zweiter Stufe, Fixpunktlogiken, Trennungen
  • Logik und ... Formale Sprachen, Verifikation, Algorithmen

Literatur

Ein Folienskript wird parallel zur Vorlesung erstellt.

Weitere Literatur:

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