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:- Graph Homomorphie Probleme
- Constraint Satisfaction and Conjunctive Queries
- Qualitative temporale Constraintsprachen
- CSPs in der Bioinformatik
- Abschlusseigenschaften von Constraints und der algebraische Ansatz
- Die Komplexität von boolschen CSPs
- Constraint Propagation und lokale Konsistenz
- Quantifizierte CSPs
Übungen
Zu Graph Homomorphie Problemen, in postscript
Teil 2, in postscript
Literatur
- , The complexity of constraint satisfaction: an algebraic approach, (die frei verfügbare Vorabversion eines Übersichtsartikels)
