Constraint Satisfaction Problems - Overview
Lecturers: Prof. Dr. Bernhard Nebel, Dr. Stefan Wölfl und Dr. Julien Hué
Exercises: Dr. Matthias Westphal
Time
Lecture: Monday 16:15-18:00 and Wednesday 16:15-17:00
Exercises: Wednesday 17:15-18:00
No lecture on 14.05., 16.5, and 13.6.
No exercise on 16.5. and 13.6.
Location
Lecture: Building 101, Room 00-036
Exercises: Building 101, Room 00-036
Language
The lecture and exercises will be given in english. The slides are in english. Exercises can be submitted in english or german.
Contents
The lecture provides an extensive introduction into the domain of constraint satisfaction problems. For this purpose both theoretic and algorithmic questions will be examined.
In particular, the following topics are planed:
- Foundations and introduction: sets, relations, graphs, constraint networks and satisfiability, binary constraint networks.
- Inference-based methods: arc and path consistency, n-consistency and global consistency
- Search: backtracking, backjumping, comparison of methods, stochastic local search.
- Selected advanced topics: expressiveness and complexity of constraint languages, qualitative constraint networks.
Prerequisites
The lecture is intended for Bachelor, Master and Diploma students.
Knowledge of propositional logic and theoretical computer science (NP-completeness, polynomial reductions) are expected. Basic knowledge of search (depth-first, backtracking, local search) will be helpful.
Exam
For Bachelor- and Master students in Computer Science or Master students in Applied Computer Science this course counts as an advanced course ("Spezialvorlesung") in the area "Artificial Intelligence and Robotics". Students studying towards a Bachelor of Science in Computer Science are required to pass an oral exam at the end of the semester. Master students are required to pass either an oral or a written exam, depending on the number of students. This exam will take place at the end of the semester by arrangement.
For students who study Computer Science as a minor subject ("Nebenfach"), the precise regulations depend on the respective degree programme and should be discussed individually.
The course is worth 6 ECTS points.
Exercises and Admission to the Exam
During the semester there will be projects and weekly exercises. For the admission to the exam it is necessary to have reasonably worked on at least 50% of the exercises and projects.
Exercises and projects may be worked on in groups of two. Larger groups or copied solutions will not be accepted and result in nonadmission to the exam in case of recurrence.
Material
Slides used in the lecture will be availbale on the lecture page. Additional material on discussed topics will be anounced in the lecture. There is no book or script of this lecture.
The lecture will not be recorded.