Direkt zum InhaltDirekt zur SucheDirekt zur Navigation
▼ Zielgruppen ▼

Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Logik in der Informatik

VL Logik und Komplexität

Aktuelles

  • Im Logbuch finden Sie nach den Vorlesungen Informationen zum Inhalt der einzelnen Vorlesungsstunden und gelegentlich ergänzende Bemerkungen.

Einführung

Viele algorithmische Probleme lassen sich durch logische Formeln beschreiben. Dabei besteht ein enger Zusammenhang zwischen der Kompliziertheit der Formeln und der Berechnungskomplexität der Probleme. Dieser Zusammenhang spielt in verschiedenen Bereichen der Informatik eine Rolle, zum Beispiel in der Theorie formaler Sprachen, der Datenbanktheorie, der Komplexitätstheorie und im Zusammenhang mit automatischer Verifikation.

Themen dieser Vorlesung sind beispielsweise:

  • Erweiterungen der Logik erster Stufe: Logik zweiter Stufe, Fixpunktlogiken
  • Automatentheorie und Logik: logische Charakterisierung der regulären Sprachen (z.B. die Sätze von Büchi und Doner, Thatcher & Wright)
  • deskriptive Komplexitätstheorie: logische Charakterisierungen von Komplexitätsklassen (z.B. die Sätze von Fagin und Immerman & Vardi)
  • Endliche Modelltheorie: Trennungsresultate zwischen logisch definierten Klassen endlicher Strukturen, 0-1-Gesetze

 

Ziel dieser Veranstaltung ist, den Zusammenhang zwischen der logischen Beschreibbarkeit und der Berechnungskomplexität von Problemen zu verstehen.


Inhalte

Das folgende Inhaltsverzeichnis wird im Laufe der Vorlesung noch ergänzt und möglicherweise verändert.

Als Literatur werden Teile des Skripts [S-LuK] und der Bücher [L] und [EF] empfohlen.

Beachten Sie: In den Vorlesungs- und Übungsstunden wird hauptsächlich an der Tafel gearbeitet. Alle behandelten Inhalte sind für die Veranstaltung wesentlich und daher auch dann prüfungsrelevant, wenn sie nicht in den auf den Webseiten erhältlichen Materialien enthalten sind.
Zur Vorbereitung auf eine Prüfung wird dringend empfohlen, das gesamte in den Vorlesungs- und Übungsstunden vermittelte Material durchzuarbeiten.
Es ist daher wichtig, dass Sie sich während der Vorlesungs- und Übungsstunden Notizen machen.

 


Logbuch

Hier finden Sie nach den Vorlesungen Informationen zum Inhalt der einzelnen Vorlesungsstunden und gelegentlich ergänzende Bemerkungen.


Termine

 

Vorlesung
Dienstags 11:00-13:00 im Schrödinger Zentrum (Rudower Chaussee 26), Raum 1'303 und
Mittwochs 11:00-13:00 im Schrödinger Zentrum (Rudower Chaussee 26), Raum 1'303

Dozentin: Prof. Dr. Nicole Schweikardt

 
Übung
Dienstags 15:00-17:00 im Schrödinger Zentrum (Rudower Chaussee 26), Raum 1'306

Übungsleiter: Jens Keppeler


Übungsblätter

Ab der zweiten Vorlesungswoche wird wöchentlich ein Übungsblatt ausgegeben. Auf jedem Übungsblatt können bis zu 100 Punkte erreicht werden.

Das aktuelle Übungsblatt wird jeweils dienstags am Ende der Vorlesung in gedruckter Form ausgeteilt und außerdem im Laufe des Dienstag Abend hier online bereit gestellt.

  • Blatt 1 (ausgeteilt am xx; zu bearbeiten bis xx)

 


Prüfung

Zur Vorbereitung auf eine Prüfung (Modulabschlussprüfung) ist es unbedingt notwendig, das gesamte in den Vorlesungs- und Übungsstunden vermittelte Material durchzuarbeiten.

Die Modulabschlussprüfung wird durch eine mündliche Prüfung abgelegt. Termine für mündliche Modulabschlussprüfungen können nach Vereinbarung bei Frau Pergl angefragt werden.

Voraussetzung für die Zulassung zur Prüfung sind:

  1. Bestehen der beiden jeweils 90-minütigen schriftlichen Tests, in die in der Mitte und am Ende der Vorlesungszeit geschrieben werden und
  2. Erreichen von mindestens 50 Prozent aller Übungspunkte. Um dies zu gewährleisten empfehlen wir dringend, regelmäßig und aktiv an den Übungsstunden teilzunehmen.

 

Verbindliche "Spielregeln" zum Erwerb von Übungspunkten:

Übungsblätter werden dienstags nach der Vorlesung ausgeteilt. Das jeweilige Übungsblatt wird in der Übungsstunde der darauf folgenden Woche besprochen. Sie können bei jedem Übungsblatt entscheiden, gemäß welcher der folgenden beiden Varianten A bzw. B Ihre Lösung bewertet werden soll:

  • Variante A:
    Sie geben eine schriftliche, ausführlich ausgearbeitete und mathematisch präzise Lösung spätestens direkt vor Beginn der Übungsstunde ab.

  • Variante B:
    Sie geben keine Lösung ab. Stattdessen tragen Sie direkt vor Beginn der Übung in eine vom Übungsleiter bereitgestellte Liste ein, wie viele Übungspunkte Sie für Ihre Lösung der einzelnen Aufgaben(teile) für gerechtfertigt halten. Während der Übungsstunde werden vom Übungsleiter aus dieser Liste einzelne Teilnehmer zum Vorrechnen von Aufgaben(teilen) ausgesucht. Falls sich beim Vorrechnen herausstellen sollte, dass Sie keine sinnvolle Lösung vorweisen können, obwohl Sie in der Liste Punkte für diese(n) Aufgabe(nteil) eingetragen haben, werden Ihnen für das gesamte gerade behandelte Übungsblatt keine Übungspunkte angerechnet. Eine sinnvolle Lösung muss hierbei nicht notwendigerweise vollständig korrekt sein.

 


Literatur

 

[L] Leonid Libkin, Elements of Finite Model Theory. Springer-Verlag, 2004. Die für die Vorlesung relevanten Teile des Buchs sind hier unter dem mit "Download table of contents and a sample chapter" beschrifteten Link erhältlich.
[EF] Heinz-Dieter Ebbinghaus und Jörg Flum. Finite Model Theory. Springer-Verlag, 2. Auflage, 1999.
[FG] Jörg Flum und Martin Grohe, Parameterized Complexity Theory. Springer-Verlag, 2005.
[G] Martin Grohe, Descriptive Complexity, Canonisation, and Definable Graph Structure Theory, Lecture Notes in Logic, Volume 47. Cambridge University Press, 2017. LINK.. Springer-Verlag, 2005.
[I] Neil Immerman, Descriptive Complexity. Springer-Verlag, 1999.
[S-LuK] Nicole Schweikardt, Skript zur Vorlesung "Logik und Komplexität" im Sommersemester 2007, Humboldt-Universität zu Berlin. Link
[S-LI] Nicole Schweikardt, Skript zur Vorlesung "Logik in der Informatik" im Wintersemester 2014/15, Humboldt-Universität zu Berlin. Link
[F] E. Grädel, P. Kolaitis, L. Libkin, M. Marx, J. Spencer, M. Vardi, Y. Venema und S. Weinstein, Finite Model Theory and Its Applications. Springer-Verlag, 2007.
[G] E. Grädel, Finite Model Theory and Descriptive Complexity. Kapitel 3 des Buchs [F].
[K] P. Kolaitis, On the expressive power of logics on finite models. Kapitel 2 des Buchs [F].

 


 

[LICS] IEEE Symposium on Logic in Computer Science (LICS)
[EACSL] European Association for Computer Science Logic (EACSL)