Vorlesung: Logik und Komplexität

Aktuelles

Am Donnerstag, dem 20.10.2011, von 16-18 Uhr, findet zunächst eine Einführung in die Vorlesung statt, in der der Inhalt und sonstige organisatorische Dinge besprochen werden.
Inhaltlich beginnt die Vorlesung am Montag, dem 24.10.2011.

Zeiten und Räume

Vorlesung:
Montags, 10 - 12 Uhr, Raum FR 5514
Donnerstag, 16 - 18 Uhr, Raum FR 5514
Übung:
Nach Absprache in der Vorlesung

Inhalt

Aufbauend auf der Vorlesung TheGI3 behandelt dieses Modul weiterführende Themen der Logik in der Informatik.

Es werden zunüchst verschiedene Anwendungsgebiete der Logik eingeführt, besonders Anwendungen in der Datenbanktheorie, der Algorithmik und Komplexitätstheorie, sowie der automatischen Verifikation.

Im Zentrum des ersten Teils der Vorlesung stehen Fragen zur Ausdrucksstärke verschiedener Logiken und Datenbankabfragesprachen. Es werden Methoden eingeführt um nachzuweisen, dass bestimmte Abfragen nicht in der Prädikatenlogik definiert werden können. Aufbauend darauf werden dann sogenannte "Lokalitätssätze" bewiesen, die die Ausdrucksstärke der Prädikatenlogik auf sehr überraschende Art charakterisieren.

Thema des zweiten Teils der Vorlesung ist der Zusammenhang zwischen Logik und Komplexität. Hier steht zunächst die Frage im Vordergrund, wie schwierig es ist, Formeln einer gegebene Logik in einer Struktur auszuwerten. Vor allem aber werden wir den Bereich der "deskriptiven Komplexitätstheorie" behandeln, in dem algorithmische Probleme nicht anhand der zu ihrer Lösung benötigten Ressourcen wie Speicherplatz und Laufzeit klassifiziert werden, sondern der zu ihrer Beschreibung nötigen Art und Zahl logischer Quantoren und Operatoren. Es stellt sich heraus, dass es einen erstaunlich engen Zusammenhang zwischen diesen beiden Arten der Beschreibung von Problemen gibt, in dem Sinne, dass Probleme, die in nütürlichen Komplexitätsklassen wie PTIME oder NP berechnet werden künnen, auch Beschreibungen in natürlichen Logiken haben. Die Logik bietet demnach einen alternativen und sehr eleganten Zugang zur Komplexitätstheorie, den wir in diesem Teil der Vorlesung behandeln werden.

Übungsblätter

Die Übungsblätter werden hier wöchentlich zur Verfügung gestellt, beginnend ab Woche 2.

Lehrmaterialien

Zur Vorlesung wird ein ausführliches Skript erstellt und jeweils am Ende jedes Kapitels zur Verfügung gestellt.