Constraint-Satisfaction-Probleme - Übersicht

Dozenten: Prof. Dr. Bernhard Nebel, Prof. Dr. Christian Becker-Asano und Dr. Stefan Wölfl

Übungen: Dr. Stefan Wölfl

Termine

Vorlesung: Montags 10:15-12:00 und Mittwochs 10:15-11:00
Übungen: Mittwochs 11:15-12:00

Ort

Vorlesung: Gebäude Geb 51, Hörsaal SR 00 006
Übungen: Gebäude 51, Hörsaal SR 00 006

Sprache

Die Vorlesung und Übungsstunden werden auf englisch gehalten. Die Vorlesungsfolien sind in englischer Sprache. Die Übungsblätter können in beiden Sprachen bearbeitet werden.

Vorlesungsinhalt

Die Vorlesung bietet eine ausführliche Einführung in das Gebiet der Constraint-Satisfaction-Probleme. Dabei werden sowohl theoretische als algorithmische Fragestellungen untersucht.

Im Einzelnen sind folgende Themen geplant:

Grundlagen und Einführung: Mengen, Relationen, Graphen, Constraint-Netze und Erfüllbarkeit, binäre Constraint-Netze
Inferenzbasierte Methoden: Kanten- und Pfadkonsistenz, n-Konsistenz und globale Konsistenz
Suchmethoden: Backtracking, Backjumping, Vergleich verschiedener Verfahren, stochastische lokale Suche
Ausgewählte fortgeschrittene Themen: Ausdrucksstärke und Komplexität von Constraint-Sprachen, qualitative Constraint-Netze

Voraussetzungen

Die Veranstaltung richtet sich an Bachelor- und Master-Studenten (Informatik und Applied Computer Science) sowie an Diplom-Studenten und Nebenfächler im Hauptstudium.

Kenntnisse in Aussagenlogik und in theoretischer Informatik (NP-Vollständigkeit, polynomielle Reduktionen) werden erwartet. Grundkenntnisse über Suchverfahren (Tiefensuche, Backtracking, lokale Suche) sind von Vorteil.

Vorlesungsmaterial

Die Vorlesungsfolien werden im Laufe des Semesters auf der Vorlesungsseite bereit gestellt. Weiterführende und ergänzende Texte zu den Inhalten der Vorlesung werden in der Vorlesung angegeben. Es gibt kein Buch oder Skript zur Vorlesung.

Die Vorlesung wird nicht aufgezeichnet.