Syllabus 2010/2011 EDAN01

Syllabus academic year 2010/2011
(Created 2010-07-25.)

CONSTRAINT PROGRAMMING

EDAN01

Credits: 7,5. Grading scale: TH. Cycle: A (Second Cycle). Main field: Technology. Language of instruction: The course might be given in English. EDAN01 overlaps following cours/es: EDA340. Optional for: D4, D4pv, E4, F4, F4pv, Pi4, Pi4pv. Course coordinator: Krzysztof Kuchcinski, Krzysztof.Kuchcinski@cs.lth.se, Dept of Computer Science. Prerequisites: EDA027 Algorithms and Data Structures or EDAA01 Programming - Second Course. Assessment: To qualify for a passing mark, the students must have completed the laboratory work and the project. To qualify for a higher mark a written examination is required. Further information: The course might be given in English. Home page: http://cs.lth.se/edan01.

Aim
The goal of this course is to have each student acquire the knowledge on a new programming paradigm based on constraints over finite domains and provide experience of how to use these methods for solving combinatorial problems.

Knowledge and understanding
For a passing grade the student must

be able to use basic concepts of constraint programming
be able to explain principles of constraint programming and define constraints for simple problems.

Skills and abilities
For a passing grade the student must

be able to model and implement constraint programs for a combinatorial problem
be able to use appropriate heuristics to implement efficient search methods.

Contents

Introduction to constraint programming.
Basic algorithms used in constraint programming systems
(constraint satisfaction and consistency, optimisation).
Finite domain constraints.
Modelling with finite domain constraints.
Searching methods and optimisation.
Selected advanced issues.

Literature
Kuchcinski, K: Modeling and Optimisation of Embedded Systems with Constraint Programming: Principles and Practice. Distributed by the department.