Constraint-Satisfaction-Probleme - Übersicht
Dozenten: Prof. Dr. Bernhard Nebel, Dr. Stefan Wölfl und Dr. Julien Hué
Übungen: Dr. Matthias Westphal
Termine
Vorlesung: Montags 16:15-18:00 und Mittwochs 16:15-17:00
Übungen: Mittwochs 17:15-18:00
Keine Vorlesung am 14.05., 16.5. und 13.6.
Keine Übung am 16.5. und 13.6.
Ort
Vorlesung: Gebäude 101, Hörsaal 00-036
Übungen: Gebäude 101, Hörsaal 00-036
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.
Prüfung
Bachelor- und Masterstudenten im Fach Informatik und Studenten im Master-Studiengang Angewandte Informatik (Applied Computer Science) können die Veranstaltung als Spezialvorlesung im Vertiefungsgebiet Künstliche Intelligenz und Robotik anrechnen lassen. Voraussetzung ist im Bachelor-Studiengang das Bestehen einer mündlichen Prüfung, im Master-Studiengang je nach Teilnehmerzahl das Bestehen einer schriftlichen oder mündlichen Prüfung. Die Prüfungen werden nach Vereinbarung in der vorlesungsfreien Zeit nach dem Vorlesungssemester abgehalten.
Für Studierende mit Nebenfach Informatik hängen die Prüfungsregelungen vom jeweiligen Studiengang ab und sollten daher individuell besprochen werden.
In dieser Vorlesung können sechs Kreditpunkte erworben werden.
Übungen und Zulassungsvoraussetzung zur Prüfung
Während des Semesters werden wöchentlich theoretische Übungen (Aufgaben) und in unregelmäßigen Abständen praktische Übungen (Projekte) gestellt. Um zur Teilnahme an der Abschlussprüfung zugelassen zu werden, muss man mindestens 50% der Übungen und Projekte sinnvoll bearbeitet haben.
Aufgaben und Projekte können in Gruppen von je zwei Studenten bearbeitet werden. Größere Gruppen und abgeschriebene oder kopierte Lösungen werden nicht akzeptiert und führen im Wiederholungsfall zur Nichtzulassung zur Abschlussprüfung.
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.