|
Logik in der Informatik
Prof. Dr. Nicole Schweikardt |
|
Aktuelles Einführung Inhalte Logbuch Termine Übungsblätter Prüfung Literatur Links
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.
Das folgende Inhaltsverzeichnis wird im Laufe der Vorlesung noch ergänzt und möglicherweise verändert.
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.
Hier finden Sie nach den Vorlesungen Informationen zum Inhalt der einzelnen Vorlesungsstunden und gelegentlich ergänzende Bemerkungen.
Dozentin: Prof. Dr. Nicole Schweikardt
Übungsleiter: Dr. André Frochaux
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.
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:
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.
| [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) |