Logik und Datenbanktheorie
Prof. Dr. Nicole Schweikardt

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

Vorlesung Logik und Komplexität

Aktuelles   Einführung   Inhalt   Logbuch   Vorlesung&Übung   Übungsaufgaben   Prüfung    Literatur    Links

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 wird nach und nach ein Vorlesungsskript erstellt.

Das Skript der Vorlesung Logik und Komplexität vom Sommersemester 2005 ist hier als postscript oder als PDF erhältlich. Die Vorlesung im Sommersemester 2007 wird diesem Skript im Wesentlichen folgen, aber in einigen Details davon abweichen.

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.
[G] E. Grädel. Finite Model Theory and Descriptive Complexity. Kapitel 3 des Buchs Finite Model Theory and Its Applications. Springer-Verlag, 2007. Download (passwortgeschützt) einer Vorabversion (ps):  hier.
[K] P. Kolaitis. On the expressive power of logics on finite models. Kapitel 2 des Buchs Finite Model Theory and Its Applications. Springer-Verlag, 2007. Download (passwortgeschützt) einer Vorabversion (ps):  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:

 

Last modified: Wed Jul 18 15:00:28 CEST 2007
Nicole Schweikardt