Constraint-Satisfaction-Probleme - Übersicht

Dozenten: Prof. Dr. Malte Helmert und Dr. Stefan Wölfl

Übungen: Prof. Dr. Malte Helmert, Dr. Gabriele Röger und Dr. Stefan Wölfl

Termine

Vorlesung: Dienstag 14:15-16:00 und Donnerstag 14:15-15:00
Übungen: Donnerstag 15:15-16:00

Ort

Vorlesung: Gebäude 052, Hörsaal 02-017
Übungen: Gebäude 052, Hörsaal 02-017
Prüfungen: nach Vereinbarung

Sprache

Die Vorlesung wird auf englisch gehalten, die Übungsstunden auf deutsch. Die Vorlesungsfolien sind in englischer Sprache. Die Übungen sind in deutscher Sprache gestellt und können in beiden Sprachen bearbeitet werden. Die mündliche Prüfung kann in beiden Sprachen erfolgen.

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, polynomielle Lösbarkeit für DTP, qualitative Constraint-Netze

Voraussetzungen

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

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

Übungen und Prüfung

Diplomstudenten und Nebenfächler im Fach Informatik können in dieser Vorlesung einen benoteten Schein erwerben. Studenten im Bachelor-Studiengang Informatik und Masterstudenten im Fach Informatik oder Applied Computer Science können die Veranstaltung als Spezialvorlesung im Vertiefungsgebiet Künstliche Intelligenz und Robotik anrechnen lassen. Voraussetzung ist dafür jeweils das Bestehen der mündlichen Prüfung gegen Ende der vorlesungsfreien Zeit. In dieser Vorlesung können sechs Kreditpunkte erworben werden.

Während des Semesters werden wöchentlich theoretische Übungen (Aufgaben) und in unregelmäßigen Abständen praktische Übungen (Projekte) gestellt. Die Bearbeitung der Übungen ist für die Teilnahme an der mündlichen Prüfung nicht verpflichtend, wird aber zum Verständnis und zur Vertiefung des Stoffs dringend empfohlen. Außerdem können dabei nach folgenden Regeln Bonuspunkte für die Prüfung erworben werden:

Bis zu 10 Bonuspunkte können durch Bearbeitung der Aufgaben erworben werden. Um überhaupt Bonuspunkte zu erhalten, sind mindenstens 50% der erreichbaren Punkte nötig. Je fünf weitere Prozentpunkte jenseits dieser Grenze ergeben einen Bonuspunkt.
Bis zu 10 Bonuspunkte können in den Projekten erworben werden. Für jedes vollständig bearbeitete Projekt gibt es eine bestimmte Zahl an Bonuspunkten (je nach Umfang; normalerweise 2-4). Jeder Vorlesungsteilnehmer kann an beliebig vielen Projekten teilnehmen und so Bonuspunkte aufaddieren, aber die Maximalzahl an Bonuspunkten aus Projekten ist auf 10 beschränkt.
Je 10 Bonuspunkte entsprechen einer Drittelstufe in der mündlichen Prüfung, also etwa einer Verbesserung von der Note 2,0 auf die Note 1,7.

Aufgaben und Projekte können und sollten in Gruppen von je zwei Studenten bearbeitet werden. Größere Gruppen und abgeschriebene oder kopierte Lösungen werden nicht akzeptiert.

Vorlesungsmaterial

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