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 | Czech | ||

Year of introduction | 2015/2016 | Year of cancellation | |

Intended for the faculties | FEI | Intended for study types | Master, Follow-up Master |

Instruction secured by | |||
---|---|---|---|

Login | Name | Tuitor | Teacher giving lectures |

KOT06 | Ing. Martin Kot, Ph.D. | ||

SAW75 | doc. Ing. Zdeněk Sawa, Ph.D. |

Extent of instruction for forms of study | ||
---|---|---|

Form of study | Way of compl. | Extent |

Full-time | Graded credit | 2+2 |

Combined | Graded credit | 0+19 |

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

Lectures

Tutorials

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).

Rina Dechter: Constraint Processing, Morgan Kaufmann, 2003

- 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.

Solving tasks for each tutorial.
Elaborating project, finished by written report.
Final test.

Electronic materials underlying the lectures and tutorials, pointers to software tools, and futher information are accessible from the course web-page.

No additional requirements are placed on the student.

Subject has no prerequisities.

Subject has no co-requisities.

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

Task name | Type of task | Max. number of points
(act. for subtasks) | Min. number of points |
---|---|---|---|

Graded credit | Graded credit | 100 (100) | 51 |

Practical solution of a problem with constraints | Other task type | 60 | 31 |

Test | Written test | 40 | 20 |

Show history

Academic year | Programme | Field of study | Spec. | Form | Study language | Tut. centre | Year | W | S | Type of duty | |
---|---|---|---|---|---|---|---|---|---|---|---|

2019/2020 | (N2647) Information and Communication Technology | (2612T025) Computer Science and Technology | P | Czech | Ostrava | 1 | Choice-compulsory | study plan | |||

2019/2020 | (N2647) Information and Communication Technology | (2612T025) Computer Science and Technology | K | Czech | Ostrava | 1 | Choice-compulsory | study plan | |||

2018/2019 | (N2647) Information and Communication Technology | (2612T025) Computer Science and Technology | P | Czech | Ostrava | 1 | Choice-compulsory | study plan | |||

2018/2019 | (N2647) Information and Communication Technology | (2612T025) Computer Science and Technology | K | Czech | Ostrava | 1 | Choice-compulsory | study plan | |||

2017/2018 | (N2647) Information and Communication Technology | (2612T025) Computer Science and Technology | P | Czech | Ostrava | 1 | Choice-compulsory | study plan | |||

2017/2018 | (N2647) Information and Communication Technology | (2612T025) Computer Science and Technology | K | Czech | Ostrava | 1 | Choice-compulsory | study plan | |||

2016/2017 | (N2647) Information and Communication Technology | (2612T025) Computer Science and Technology | P | Czech | Ostrava | 1 | Choice-compulsory | study plan | |||

2016/2017 | (N2647) Information and Communication Technology | (2612T025) Computer Science and Technology | K | Czech | Ostrava | 1 | Choice-compulsory | study plan | |||

2015/2016 | (N2647) Information and Communication Technology | (2612T025) Computer Science and Technology | P | Czech | Ostrava | 1 | Choice-compulsory | study plan | |||

2015/2016 | (N2647) Information and Communication Technology | (2612T025) Computer Science and Technology | K | Czech | Ostrava | 1 | Choice-compulsory | study plan |

Block name | Academic year | Form of study | Study language | Year | W | S | Type of block | Block owner |
---|