Logik und Komplexität - Endliche Modelltheorie

Vorlesung im SoSe 2014

Gehalten von Prof. Dr. Nicole Schweikardt
Betreuung der Übungen durch M.Sc. Frederik Harwath

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:

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

Kenntnisse aus den Modulen M-LI oder M-KTH sind hilfreich.

Kürzel laut Studienordnung: M-LK, MaM-LOG-k.  Creditpoints: 8.  SWS: 3 V, 2 Ü.

Inhalte
  1. Einleitung (handschriftliche Notizen zu Kapitel 0)
  2. Grundlagen (handschriftliche Notizen zu Kapitel 1)
  3. Logik zweiter Stufe (handschriftliche Notizen zu Kapitel 2: Teil 1, Teil 2, Teil 3, Teil 4, Teil 5, Teil 6)
  4. 0-1-Gesetze (handschriftliche Notizen zu Kapitel 3: Teil 1, Teil 2, Teil 3, Teil 4)
  5. Fixpunktlogiken (handschriftliche Notizen zu Kapitel 4: Teil 1, Teil 2, Teil 3)

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

Logbuch

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

Termine
ZeitOrtLeitung
Vorlesung i.d.R. Dienstags 14:00-17:00 Magnus-Hörsaal in der Informatik, Robert-Mayer-Str. 11-15 Prof. Dr. Nicole Schweikardt
Übung 1 i.d.R. Donnerstags 14:00-16:00 Magnus-Hörsaal in der Informatik, Robert-Mayer-Str. 11-15 M.Sc. Frederik Harwath

Übungsblätter

Prüfungen bzw. Scheine

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

Modulabschlussprüfung (relevant für Studierende in einem Bachelor- oder Master-Studiengang):

Die Modulabschlussprüfung wird durch eine mündliche Prüfung abgelegt.
Termine für mündliche Modulabschlussprüfungen können nach Vereinbarung bei Frau Nadland angefragt werden. Generelle Informationen zur Anmeldung zu mündlichen Prüfungen finden Sie hier.

Im Lauf des Semesters können Bonuspunkte erworben werden, durch deren Einbringen die Note einer bestandenen Modulabschlussprüfung um eine Teilnote verbessert werden kann (also von 4,0 auf 3,7; von 3,7 auf 3,3; von 3,3 auf 3,0; von 3.0 auf 2,7; von 2,7 auf 2,3; von 2,3 auf 2,0; von 2,0 auf 1,7; von 1,7 auf 1,3; von 1,3 auf 1,0).

Es werden zwei je 90-minütige Test geschrieben.
Voraussetzung für den Erwerb von Bonuspunkten, durch deren Einbringen die Note einer bestandenen Modulabschlussprüfung um eine Teilnote verbessert werden kann, sind:

  1. Bestehen der beiden Tests und
  2. Erreichen von mindestens 50 Prozent aller Übungspunkte (bitte beachten Sie, dass dies insbes. die regelmäßige und aktive Teilnahme an den Übungsstunden erfordert, siehe unten).

Scheinerwerb (relevant für Studierende in einem Lehramts-Studiengang):

Es werden zwei je 90-minütige Tests geschrieben.
Voraussetzung für den Scheinerwerb sind:
  1. Bestehen der beiden Tests und
  2. Erreichen von mindestens 50 Prozent aller Übungspunkte (bitte beachten Sie, dass dies insbes. die regelmäßige und aktive Teilnahme an den Übungsstunden erfordert, siehe unten).

Verbindliche "Spielregeln" zum Erwerb von Übungspunkten:

Übungsblätter werden dienstags nach der Vorlesung ausgeteilt. Am Donnerstag der darauf folgenden Woche wird das jeweilige Übungsblatt in der Übungsstunde besprochen. Zu Beginn dieser Übungsstunde können alle Teilnehmer in eine Liste eintragen, für welche Aufgaben(teile) sie wie viele Übungspunkte angerechnet bekommen wollen. Während der Übungsstunde werden vom Übungsleiter aus dieser Liste willkürlich einzelne Teilnehmer zum Vorrechnen von Aufgaben(teilen) ausgesucht. Falls sich beim Vorrechnen herausstellen sollte, dass ein Teilnehmer keine sinnvolle Lösung vorweisen kann, obwohl er in der Liste Übungspunkte für diese Aufgabe beansprucht hat, geschieht folgendes:
  1. Tritt diese Situation für den jeweiligen Teilnehmer zum ersten Mal in diesem Semester auf, so werden ihm für das gesamte gerade behandelte Übungsblatt keine Übungspunkte angerechnet.
  2. Tritt diese Situation für den jeweiligen Teilnehmer zum zweiten Mal in diesem Semester auf, so kann er in der Veranstaltung "Logik und Komplexität" im SS 2014 keine Übungspunkte erwerben.

Literatur
[S] N. Schweikardt. Skript zur Vorlesung "Logik und Komplexität" im Sommersemester 2007, Humboldt-Universität zu Berlin. Link
[L] L. Libkin. Elements of Finite Model Theory. Springer-Verlag, 2004. Inhaltsverzeichnis und ausgewählte Kapitel des Buchs können hier heruntergeladen werden.
[EF] H.-D. Ebbinghaus und J. Flum. Finite Model Theory. Springer-Verlag, 2te Auflage, 1999.
[I] N. Immerman. Descriptive Complexity. Springer-Verlag, 1999.
[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] .
[FG] F. Flum und M. Grohe. Parameterized Complexity. Springer-Verlag, 2006.

Links
[LICS] IEEE Symposium on Logic in Computer Science (LICS)
[EACSL] European Association for Computer Science Logic (EACSL)
zuletzt geändert: Tue Jul 8 17:15:57 2014 von Lucas Heimberg