Instituts-Logo Logik in der Informatik
Prof. Dr. Nicole Schweikardt
Humboldt-Logo

Vorlesung Logik und Komplexität

Sommersemester 2018

Aktuelles   Einführung    Inhalte    Logbuch    Termine    Übungsblätter    Prüfung    Literatur   Links  


Aktuelles


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:

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 13:00-15:00 im Schrödinger Zentrum (Rudower Chaussee 26), Raum 1'303 und
Mittwochs 13:00-15: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'303

Übungsleiter: Dr. André Frochaux


Ü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.


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 Sandig 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:


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)


Last modified: 17.07.2018
Nicole Schweikardt
Valid HTML 4.01!