Algorithmen und Komplexität

Seminar: Constraint Satisfaction

Dozent: Dr. Manuel Bodirsky

---

Termine

Beginn des Seminars: 18.4.2006.

SE	Dienstag	09:00 - 11:00	(RUD 26, 1.307)

Zuordnung

• Hauptstudium, Seminar

Inhalte und Lernziele

Eine Vielzahl von Berechnungsproblemen kann als Constraint Satisfaction Problem (CSP) formuliert werden. Im Bereich der künstlichen Intelligenz gilt das zum Beispiel für Probleme aus Bildverarbeitung, räumlichen und zeitlichen Schliessen, Typinferenz bei Programmiersprachen und Computerlinguistik. Auch in der Datenbanktheorie sind CSPs von zentraler Bedeutung.

In jüngster Zeit haben Konzepte aus der universellen Algebra und Logik einen wichtigen Beitrag dazu geleistet, systematisch zu verstehen, welche Constraint Satisfaction Probleme von effizienten Algorithmen gelöst werden können, und für welche das nicht erwartet werden kann. In unserem Seminar sollen diese Ergebnisse anhand von konkreten Problemen (unter anderem aus den oben genannten Gebieten) vermittelt werden.

Voraussetzungen

• Gute Kenntnisse der theoretischen Informatik werden vorausgesetzt.
• Die Literatur zu den Vortragsthemen ist englischsprachig.

Vortragsthemen

Vorbesprechung und Themenvergabe finden in der ersten Semesterwoche statt, am Dienstag, den 18.4.2006, um 9 Uhr in Raum 1.307 im Johann von Neumann-Haus. Bei den ersten Terminen wird gemeinsam grundlegende Literatur erarbeitet, und es wird kleinere Hausarbeiten geben. Später im Seminar werden ausgesuchte Themen von Teilnehmern vorgetragen und in der Gruppe diskutiert.

Mögliche Vortragsthemen für Teilnehmer:

1. Graph Homomorphie Probleme
2. Constraint Satisfaction and Conjunctive Queries
3. Qualitative temporale Constraintsprachen
4. CSPs in der Bioinformatik
5. Abschlusseigenschaften von Constraints und der algebraische Ansatz
6. Die Komplexität von boolschen CSPs
7. Constraint Propagation und lokale Konsistenz
8. Quantifizierte CSPs

Übungen

Zu Graph Homomorphie Problemen, in postscript

Teil 2, in postscript

Literatur

• Bulatov, Jeavons, Krokhin, The complexity of constraint satisfaction: an algebraic approach, (die frei verfügbare Vorabversion eines Übersichtsartikels)

---

zuletzt geändert am 23.05.2006 (alkox-www)