460-4089/02 – Constraint Processing (ARUO)
Gurantor department | Department of Computer Science | Credits | 4 |
Subject guarantor | Ing. Martin Kot, Ph.D. | Subject version guarantor | Ing. Martin Kot, Ph.D. |
Study level | undergraduate or graduate | Requirement | Choice-compulsory |
Year | 1 | Semester | winter |
| | Study language | English |
Year of introduction | 2015/2016 | Year of cancellation | 2022/2023 |
Intended for the faculties | FEI | Intended for study types | Follow-up Master, Master |
Subject aims expressed by acquired skills and competences
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
Teaching methods
Lectures
Tutorials
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).
Compulsory literature:
Rina Dechter: Constraint Processing, Morgan Kaufmann, 2003
Recommended literature:
- 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.
Way of continuous check of knowledge in the course of semester
Solving tasks for each tutorial.
Elaborating project, finished by written report.
Final test.
E-learning
Electronic materials underlying the lectures and tutorials, pointers to software tools, and futher information are accessible from the course web-page.
Other requirements
No additional requirements are placed on the student.
Prerequisities
Subject has no prerequisities.
Co-requisities
Subject has no co-requisities.
Subject syllabus:
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
Conditions for subject completion
Occurrence in study plans
Occurrence in special blocks
Assessment of instruction
Předmět neobsahuje žádné hodnocení.