..:: Martin Kot ::..
Constraint processing - school year 2015/16
General facts
Guarantee: 
Number of credits:  4
Hours:  2/2/0/0
Completition:  Credit
Official web-page:  http://www.cs.vsb.cz/kot/ARUO/
Lecturers: 
Exercisers: 
 
Division of points
Credit: 
  • 60pts - homework
  • 40pts - term written test
  • Condition for accreditation is to obtain at least 31 points from homework and at least 20 points from test
 
Annotation
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).
 
Time table
7:15
8:00
8:00
8:45
9:00
9:45
9:45
10:30
10:45
11:30
11:30
12:15
12:30
13:15
13:15
14:00
14:15
15:00
15:00
15:45
16:00
16:45
16:45
17:30
17:45
18:30
18:30
19:15
pondělí                            
úterý                            
středa                            
čtvrtek        
EB207
Kot M.
EB207
Kot M.
           
pátek                            
sobota                            
 
Lectures
  • Examples of practical problems with constraints and outline of general solving methods. Exact formulation of problems, illustrated on example of an assignment of radio frequencies; choice of unknowns and constraints on them.
  • Structure of space of potential solutions Constraint propagation methods.
  • General search strategies for the space of potential solutions.
  • Scheduling problem (lessons, work shifts,...). Application of selected methods.
  • Formulation of logical circuits diagnosis problem and some other problems that can be reduced to SAT (satisfiability of boolean formulas) SAT-solvers.
  • Methods used in SAT-solvers.
  • Stochastic search strategies.
  • Combinatorial optimization. Multicommodity flows, logistic problems.
  • Integer linear constraints and specific solution methods.
  • Planning (assigning tasks to processors).
  • Outline of some advanced topics (decomposition methods, probabilistic networks,...).
  • Hybrid methods.
  • Summary, review
 
Study literature
  • R. Dechter: Constraint processing, Morgan Kaufmann, 2003
Literature is not obligatory. All you need to obtain a credit will be said on lectures and tutorials.