Logik in der Informatik
Prof. Dr. Martin Grohe
Institut für Informatik

Seminar Logik und Komplexität

Aktuelles  Einführung  Zeit&Raum  Literatur  Vorträge

Aktuelles

17.12.2003:
Bis auf weiteres findet das Seminar in Raum 4.410 des Johann von Neumann-Hauses statt.

09.12.2003:
Am Donnerstag, den 11.12.03 findet das Seminar statt! Wegen des Streiks allerdings nicht im Schrödinger Zentrum sondern in Raum 4.410 des Johann von Neumann-Hauses.

27.11.2003 und 04.12.2003:
Wegen des Streiks war der Zugang zum Seminarraum versperrt. Das Seminar ist deshalb heute ausgefallen. Die nachfolgenden Vorträge verschieben sich daher jeweils um eine Woche nach hinten.
Die unten stehende Liste der Vorträge wurde entsprechend angepasst.

23.10.2003:
Das erste Treffen, bei dem das Seminar vorgestellt und die Vorträge vergeben wurden, fand am Donnerstag dem 23. Oktober 2003 um 13 Uhr statt.
Eine Liste, wer wann welchen Vortrag hält gibt es hier.
Literaturhinweise finden Sie hier.
Sie können die Literatur bei Prof. Martin Grohe (Raum 4.403) oder bei Dr. Nicole Schweikardt (Raum 4.408) abholen.

Einführung

Logik und Komplexität sind auf vielfältige Weise miteinander verflochten. Zum einen spielen "logische" Probleme, wie beispielsweise das aussagenlogische Erfüllbarkeitsproblem (SAT), eine wichtige Rolle sowohl in der theoretischen als auch praktischen Informatik, weil sich viele andere Probleme leicht darauf reduzieren lassen. Ein besseres Verständnis der Komplexität derartiger Probleme ist deswegen von großem Interesse. Zum anderen lassen logische Beschreibungen von Problemen oftmals Rückschlüsse auf deren Komplexität zu; vereinfacht gesagt lassen sich Probleme, die sich leicht in einer formalen Logik beschreiben lassen, auch leicht algorithmisch lösen.

In diesem Seminar wollen wir uns anhand aktueller Forschungsarbeiten mit der Komplexität von sogenannten Constraint Satisfaction Problemen beschäftigen. Das sind Verallgemeinerungen des aussagenlogischen Erfüllbarkeitsproblems, die Anwendungen vor allem in der künstlichen Intelligenz und in Datenbanksystemen haben.

Zeit und Raum

Donnerstags 13-15 im Schrödinger Zentrum (Rudower Chaussee 26), Raum 1'308

Literatur

Vortragsthemen und -termine

Datum   Thema Vortrag von ...
23.10.03    Vergabe der Vortragsthemen
30.10.03 Einführung in CSP und Begriffe aus der Komplexitätstheorie   Martin Grohe und Nicole Schweikardt
06.11.03 Der Satz von Ladner
Buch von Papadimitriou (ca S. 329-332) & evtl. Artikel von Ladner   		Ulf Hermann
13.11.03 - frei! -
20.11.03 Charakterisierung von Constraint-Funktionen, Teil 1
Buch von Creignou et al., Kap. 4 (ca S. 25-28) 		Marc Thurley
27.11.03 - Seminar nicht möglich wegen des Streiks -
04.12.03 - Seminar nicht möglich wegen des Streiks -
11.12.03 Charakterisierung von Constraint-Funktionen, Teil 2
Buch von Creignou et al., Kap. 4 (ca S. 29-31) 		Dzifa Ametowobla
18.12.03 "Implementationen" von Funktionen, Teil 1
Buch von Creignou et al., Kap. 5 (ca S. 33-38 & 41) 		Felix Hermann
08.01.04 "Implementationen" von Funktionen, Teil 2
Buch von Creignou et al., Kap. 5 (ca S. 42-48) 		Lukas Dölle
15.01.04 Der Satz von Schaefer
Buch von Creignou et al., Kap. 6 (ca S. 51-54) 		Gunar Maiwald
22.01.04 Klassifikation für #SAT und QSAT
Buch von Creignou et al., Kap. 6 (ca S. 55-58) 		Stefan Ziller
29.01.04 Die Komplexität des "Meta-Problems"
Buch von Creignou et al., Kap. 9 (S. 89-93) 		Thomas Böttcher
05.02.04 Artikel von Jeavons et al., Teil 1 (ca S. 528-534) Matthias Beick
12.02.04 Artikel von Jeavons et al., Teil 2 (ca S. 535-540) Nicolas Rocca
19.02.04 Artikel von Jeavons et al., Teil 3 (ca S. 541-547) Nicole Schweikardt

Last modified: Wed Mar 31 10:20:19 CEST 2004
Martin Grohe