| Course Unit Code | 460-4089/01 |
|---|
| Number of ECTS Credits Allocated | 4 ECTS credits |
|---|
| Type of Course Unit * | Choice-compulsory |
|---|
| Level of Course Unit * | Second Cycle |
|---|
| Year of Study * | First Year |
|---|
| Semester when the Course Unit is delivered | Winter Semester |
|---|
| Mode of Delivery | Face-to-face |
|---|
| Language of Instruction | Czech |
|---|
| Prerequisites and Co-Requisites | There are no prerequisites or co-requisites for this course unit |
|---|
| Name of Lecturer(s) | Personal ID | Name |
|---|
| SAW75 | doc. Ing. Zdeněk Sawa, Ph.D. |
| KOT06 | Ing. Martin Kot, Ph.D. |
| Summary |
|---|
Many practical problems share the following feature - a desirable solution must satisfy a lot of constraints resulting from reality (a timetable for teaching, a schedule for working on something, an assignment of radio frequencies, ...). In last several decades, an area called "constraint processing" has been developed, where general forms of description of such constraints are examined and where general methods for solving such problems are studied. Instances of these methods are used successfully in many different areas, from molecular biology, through computer graphics, natural language processing, to, for example, design of logic circuits.
The aim of this course is to introduce students to possible forms of a description of constraints and some selected methods for finding solutions satisfying these constraints, and to illustrate their use on some practical problems. Students will also try to solve such problems in practice in tutorials and in a semestral project, using freely available software libraries and tools (as for example "SAT-solvers", i.e., solvers for satisfiability of boolean formulas). |
| Learning Outcomes of the Course Unit |
|---|
Student after successful completion of this subject:
- understands basic notions from the area "constraint processing"
- can classify practical problems from this area
- is able to find relevant unknowns for practical problem and precisely formulate corresponding constraints
- has an overview of general solution methods
- has an overview of available software tools for solving problems with constraints
- has some practice in solving practical problems using some of those tools |
| Course Contents |
|---|
Lectures:
---------
1. Examples of practical problems with constraints and outline of general solving methods. Exact formulation of problems shown on Huffman-Clowes scene labeling
2. Constraint networks and graph representations, special forms of networks.
3. Constraint propagation (arc consistency, global constraints), relevant algorithms
4. Solution of problems using backtracking, algorithms improving forward phase of backtracking
5. Algorithms improving backward phase of backtracking
6. Problem SAT, its NP-completness, using SAT for solving problems with constraints
7. Variants of SAT with polynomial-time solution, relevant algorithms
8. Solutions for general problem SAT, algorithm DPLL, stochastic algorithms,...
9. Optimization problems, the use of backtracking (Branch and Bound), bucket elimination techniques
10. The use of probabilistic networks (medical diagnosis example)
11. Planning, scheduling
12. Aproximation algorithms (traveling salesman problem)
Outline of tutorials:
---------------------
1. Precise formulation of problems. Introductory session with Gecode tool (constraint solver).
2. Gecode - construction of a model of a problem
3. Gecode - the use of different search methods implemented in this tool
4. Formulation of a problem in a form of an input for a SAT solver. Introductory session with MiniSAT - a simple SAT solver.
5. Solution of practical problems with MiniSAT.
6. UBCSAT - stochastic SAT solver
7. The use of JAVA library Sat4j for SAT solving in own programs
8. Sat4j as a standalone SAT solver, other available SAT solvers, their commonalities and differences
9.-10. Other SW tools for solving problems with constraints
11.-12. Consultation of projects
13. A written test |
| Recommended or Required Reading |
|---|
| Required Reading: |
|---|
| Rina Dechter: Constraint Processing, Morgan Kaufmann, 2003 |
- Rina Dechter: Constraint Processing, Morgan Kaufmann, 2003
|
| Recommended Reading: |
|---|
- Krzysztof Apt: Principles of Constraint Programming, Cambridge University
Press, 2003.
- Malik Ghallab, Dana Nau, Paolo Traverso: Automated Planning: Theory & Practice,
Morgan Kaufmann, 2004.
- Christos H. Papadimitriou, Kenneth Steiglitz: Combinatorial Optimization:
Algorithms and Complexity, Dover Publications, 1998.
- Alexander Schrijver: Combinatorial Optimization (3 volume, A,B, & C),
Springer, 2003.
- Daniel Kroening, Ofer Strichman: Decision Procedures: An Algorithmic Point of View,
Springer, 2008. |
- Krzysztof Apt: Principles of Constraint Programming, Cambridge University
Press, 2003.
- Malik Ghallab, Dana Nau, Paolo Traverso: Automated Planning: Theory & Practice,
Morgan Kaufmann, 2004.
- Christos H. Papadimitriou, Kenneth Steiglitz: Combinatorial Optimization:
Algorithms and Complexity, Dover Publications, 1998.
- Alexander Schrijver: Combinatorial Optimization (3 volume, A,B, & C),
Springer, 2003.
- Daniel Kroening, Ofer Strichman: Decision Procedures: An Algorithmic Point of View,
Springer, 2008. |
| Planned learning activities and teaching methods |
|---|
| Lectures, Tutorials |
| Assesment methods and criteria |
|---|
| Task Title | Task Type | Maximum Number of Points
(Act. for Subtasks) | Minimum Number of Points for Task Passing |
|---|
| Graded credit | Graded credit | 100 (100) | 51 |
| Practical solution of a problem with constraints | Other task type | 60 | 31 |
| Zápočtová písemka | Written test | 40 | 20 |