Constraint Satisfaction Problems - Overview
Lecturers: Prof. Dr. Bernhard Nebel, Prof. Dr. Christian Becker-Asano und Dr. Stefan Wölfl
Exercises: Dr. Stefan Wölfl
Time
Lecture: Monday 10:15-12:00 and Wednesday 10:15-11:00
Exercises: Wednesday 11:15-12:00
Location
Lecture: Building 51, Room SR 00 006
Exercises: Building 51, Room SR 00 006
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.
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.