Zum Inhalt
Fakultät für Informatik

Logik und Komplexität

Veranstaltungsnummer 042617
Titel Logik und Komplexität (INF-MSC-509)
Veranstalter Prof. Dr. Thomas Schwentick
Klassifikation Vertiefungsmodul (MPO)
Semester Wintersemester 2024/25
SWS 4 (3V+1Ü)
Kreditpunkte 6
Ort und Zeit Vorlesung:
Dienstags, 14:15 - 16:00 Uhr (Beginn: 8.10.2024) und Donnerstags (10:15-12:00 Uhr, 14-tägig )
Übung: 
Donnerstags 10:15 - 12:00 (14-tägig)
Alle Termine in OH 12, 3.031
Querverbindungen Komplexitätstheorie, Logik
Voraussetzungen GTI-Stoff wird vorausgesetzt,
Komplexitätstheorie ist hilfreich, aber nicht unbedingt notwendig
Forschungsbereich (MPO) Algorithmen und Komplexität
Materialien Im Moodle-Arbeitsraum (Anmeldung über LSF)
Sprache Folien und Videos: Englisch, Vorlesung: deutsch/englisch

Aktuelles

The course can be taught at least partially in English.

Inhalt

Many algorithmic problems can be described by logical formulae. There is a close connection between the complexity of the formulae and the computational complexity of the problems. This connection plays a role in various areas of (theoretical) computer science, for example in the theory of formal languages, database theory, complexity theory and in the context of automatic verification. The lecture will deal with important such correspondence results and with the basic properties of the logics involved.

Individual topics:

  • Foundations of first-order logic
  • Expressive power of first-order logic: Ehrenfeucht games, locality, other methods
  • Logic and complexity theory: second-order logic, fixed-point logics, separations
  • Evaluation of logical formulae: Algorithms and complexity
  • Logic and Formal Languages
  • Efficient logics

 

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

Literatur

Ein Folienskript wird parallel zur Vorlesung erstellt.

Weitere Literatur:

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