Logik und Datenbanktheorie Prof. Dr. Nicole Schweikardt

Logik in der Informatik, Institut für Informatik, Humboldt-Universität zu Berlin

Aktuelles:

An dieser Stelle finden Sie im Laufe des Semesters aktuelle Mitteilungen. Bitte sehen Sie regelmäßig nach, ob es Neues gibt. Informationen zum Inhalt der einzelnen Vorlesungsstunden sowie Teile des Vorlesungsskripts und gelegentlich ergänzende Bemerkungen finden Sie (nach den Vorlesungen) im Logbuch. Prüfungstermine:   30.+31.07.2007 (Raum 4.426, J.v.N.-Haus)   und   27.+28.08.2007 (Raum 4.410, J.v.N.-Haus) Anmeldung bei Frau Eisenmann (Raum 4.402, J.v.N.-Haus) bzw. bei Frau Kämpfer (Raum 4.407, J.v.N-Haus)

Einführung:

Thema dieser Vorlesung ist der Zusammenhang zwischen logischer Beschreibbarkeit und Komplexität. Ein Schwerpunkt ist die deskriptive Komplexitätstheorie, in der der Zusammenhang zwischen Beschreibungskomplexität und klassischer Berechnungskomplexität von Problemen untersucht wird. So können wichtige Komplexitätsklassen wie P und NP durch Erweiterungen der Logik erster Stufe beschrieben werden. Zur Bestimmung der Ausdrucksstärke der relevanten Logiken werden unter anderem Zwei-Personen Spiele behandelt. Stichworte: deskriptive Komplexität, endliche Modelltheorie, Ehrenfeucht-Fraïssé-Spiele, Fixpunktlogiken.

Inhalt:

Begleitend zur Vorlesung wurde nach und nach ein Vorlesungsskript erstellt. Das gesamte Skript ist hier als postscript oder als PDF erhältlich. Die einzelnen Kapitel können auch separat betrachtet werden: Titelseite und Inhaltsverzeichnis Kapitel 0:   Einleitung Kapitel 1:   Grundlagen Kapitel 2:   Deskriptive Komplexität Kapitel 3:   Ehrenfeucht-Fraïssé Spiele Kapitel 4:   Der Satz von Gaifman Kapitel 5:   Fixpunktlogiken

Logbuch:

Hier finden Sie (nach den Vorlesungen) Informationen zum Inhalt der einzelnen Vorlesungsstunden, die in der Vorlesung verwendeten Teile des Vorlesungsskripts und gelegentlich ergänzende Bemerkungen.

Informationen zum Vorlesungs- und Übungsbetrieb:

Vorlesung: Montags   13-15 in Raum 1'305 und Mittwochs 15-17 in Raum 1'307, Erwin Schrödinger-Zentrum (Rudower Chaussee 26)   Dozentin:   Prof. Dr. Nicole Schweikardt   (Sprechstunde: Dienstags 14-15 Uhr)   Übung: Montags 15-17 in Raum 1'305, Erwin Schrödinger-Zentrum (Rudower Chaussee 26)   Dozent:   Dipl.-Inf. André Hernich   (Sprechstunde: Mittwochs 14-15 Uhr)

Übungsaufgaben:

Es wird regelmäßig Übungsaufgaben geben, deren erfolgreiche Bearbeitung Voraussetzung für den Scheinerwerb und die Zulassung zur Prüfung ist. Blatt 1 (ausgeteilt am 18.04.2007; abzugeben am 25.04.2007) Blatt 2 (ausgeteilt am 25.04.2007; abzugeben am 02.05.2007) Blatt 3 (ausgeteilt am 02.05.2007; abzugeben am 09.05.2007) Blatt 4 (ausgeteilt am 09.05.2007; abzugeben am 16.05.2007) Blatt 5 (ausgeteilt am 16.05.2007; abzugeben am 23.05.2007) Blatt 6 (ausgeteilt am 23.05.2007; abzugeben am 30.05.2007) Blatt 7 (ausgeteilt am 30.05.2007; abzugeben am 06.06.2007) Blatt 8 (ausgeteilt am 06.06.2007; abzugeben am 20.06.2007) Blatt 9 (ausgeteilt am 20.06.2007; abzugeben am 27.06.2007; da "Pebble-Spiele" in der Vorlesungsstunde vom 20.06. noch nicht eingeführt wurden, sind von Blatt 9 zunächst lediglich die Aufgaben 1, 2 und 3 zu bearbeiten) Blatt 10 (ausgeteilt am 27.06.2007; abzugeben am 04.07.2007) Blatt 11 (ausgeteilt am 04.07.2007; abzugeben am 11.07.2007) Blatt 12 (ausgeteilt am 11.07.2007; abzugeben am 18.07.2007)

Prüfung:

Zu Beginn der Semesterferien finden mündliche Prüfungen statt. Für die Zulassung zur Prüfung müssen mindestens 40% der Punkte in den Übungaufgaben erworben werden. Prüfungstermine:   30.+31.07.2007 (Raum 4.426, J.v.N.-Haus)   und   27.+28.08.2007 (Raum 4.410, J.v.N.-Haus) Anmeldung bei Frau Eisenmann (Raum 4.402, J.v.N.-Haus) bzw. bei Frau Kämpfer (Raum 4.407, J.v.N-Haus)

Literatur:

[EF] H.-D. Ebbinghaus und J. Flum. Finite Model Theory. Springer-Verlag, 2te Auflage, 1999. [I] N. Immerman. Descriptive Complexity. Springer-Verlag, 1999. [L] L. Libkin. Elements of Finite Model Theory. Springer-Verlag, 2004. [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]. Download (passwortgeschützt) einer Vorabversion (ps):  hier. [K] P. Kolaitis. On the expressive power of logics on finite models. Kapitel 2 des Buchs [F]. Download (passwortgeschützt) einer Vorabversion (ps):  hier. [S] N. Schweikardt. Logik und Komplexität. Skript zur Vorlesung im Sommersemester 2007, Humboldt-Universität zu Berlin.   Download (pdf):  hier. [KS] S. Kreutzer und N. Schweikardt. Logik und Komplexität. Skript zur Vorlesung im Sommersemester 2005, Humboldt-Universität zu Berlin.   Download (pdf):  hier. Links: IEEE Symposium on Logic in Computer Science (LICS) European Association for Computer Science Logic (EACSL)   Last modified: Fri Jul 20 12:51:36 CEST 2007 Nicole Schweikardt