Programování s omezujícími podmínkami - NOPT042

• Anglický název: Constraint Programming
• Zajišťuje: Katedra teoretické informatiky a matematické logiky (32-KTIML)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2020
• Semestr: zimní
• E-Kredity: 5
• Rozsah, examinace: zimní s.:2/2, Z+Zk [HT]
• Počet míst: neomezen
• Minimální obsazenost: neomezen
• 4EU+: ne
• Virtuální mobilita / počet míst pro virtuální mobilitu: ne
• Stav předmětu: vyučován
• Jazyk výuky: angličtina, čeština
• Způsob výuky: prezenční
• Další informace: http://ktiml.mff.cuni.cz/~bartak/podminky/
• Garant: prof. RNDr. Roman Barták, Ph.D.
• Vyučující: prof. RNDr. Roman Barták, Ph.D.; RNDr. Jakub Bulín, Ph.D.
• Třída: Informatika Mgr. - Teoretická informatika; Informatika Mgr. - Matematická lingvistika; Informatika Mgr. - Diskrétní modely a algoritmy
• Kategorizace předmětu: Informatika > Optimalizace, Teoretická informatika
• Neslučitelnost : NOPX042
• Záměnnost : NOPX042
• Je neslučitelnost pro: NOPX042
• Je záměnnost pro: NOPX042

Anotace

čeština

Přednáška podává přehled o technikách splňování omezujících podmínek. Zaměřena je na algoritmy splňování podmínek a to jak algoritmy prohledávací (prohledávání do hloubky, lokální prohledávání) tak algoritmy propagační (hranová konzistence, konzistence po cestě). Probíráno je také řešení příliš omezených problémů a různé modelovací techniky. Předpokládány jsou základní programovací znalosti Prologu.

Poslední úprava: Barták Roman, prof. RNDr., Ph.D. (05.06.2017)

angličtina

The course gives a survey of constraint satisfaction techniques. The focus is on algorithms for constraint satisfaction, such as search algorithms (depth-first search and local search) and propagation algorithms (arc and path consistency). Solving over-constrained problems is also discussed as well as some modeling techniques are covered. Basic knowledge of programming language Prolog is expected.

Poslední úprava: Barták Roman, prof. RNDr., Ph.D. (05.06.2017)

Cíl předmětu

čeština

Naučit základní používané techniky používané při úlohách splňování podmínek

Poslední úprava: T_KTI (23.05.2008)

angličtina

The course gives a survey of constraint satisfaction techniques. The focus is on algorithms for constraint satisfaction, such as search algorithms (depth-first search and local search) and propagation algorithms (arc and path consistency). Solving over-constrained problems is also discussed as well as some modeling techniques are covered.

Poslední úprava: BARTAK/MFF.CUNI.CZ (31.03.2008)

Podmínky zakončení předmětu

čeština

Pro úspěšné absolvování předmětu je potřeba získat zápočet a složit zkoušku. Zápočet je udělován za domácí úkoly (constraintové modely) zadávané v rámci cvičení.

Poslední úprava: Barták Roman, prof. RNDr., Ph.D. (08.08.2022)

angličtina

To successfully complete the course, the student is required to do the exam and to get credit. The credit is given for preparing constraint models during practical exercises.

Poslední úprava: Barták Roman, prof. RNDr., Ph.D. (08.08.2022)

Literatura

čeština

R. Dechter: Constraint Processing, Elsevier Science, 2003

K. Marriott, P.J. Stuckey: Programming with Constraints: An Introduction, The MIT Press, 1998

E. Tsang: Foundations of Constraint Satisfaction, Academic Press, 1993

N. Zhou, H. Kjellerstrand, J. Fruhman: Constraint Solving and Planning with Picat, Springer, 2015

Poslední úprava: Barták Roman, prof. RNDr., Ph.D. (08.08.2022)

Metody výuky

čeština

přednáška

Poslední úprava: BARTAK/MFF.CUNI.CZ (31.03.2008)

angličtina

lecture

Poslední úprava: BARTAK/MFF.CUNI.CZ (31.03.2008)

Požadavky ke zkoušce

čeština

Zkouška se skládá z písemné přípravy a ústní části. Požadavky odpovídají sylabu předmětu.

Poslední úprava: Barták Roman, prof. RNDr., Ph.D. (06.10.2017)

angličtina

The exam consists of a written preparation and an oral part. The requirements are given by the course syllabus.

Poslední úprava: Barták Roman, prof. RNDr., Ph.D. (06.10.2017)

Sylabus

čeština

1. Úvod: historické souvislosti, vazba na další obory, aplikační oblasti, definice problému splňování omezujících podmínek, binarizace problémů.

2. Algoritmy lokálního prohledávání: metoda největšího stoupání, minimalizace konfliktů, náhodná procházka, Tabu seznam, GSAT, Genet.

3. Algoritmy prohledávání do hloubky: backtracking, backjumping, dynamický backtracking, backmarking, prohledávání s diskrepancemi, neúplné prohledávání.

4. Konzistenční techniky: vrcholová a hranová konzistence, konzistence po cestě a algoritmy pro jejich dosažení, obecné konzistenční pojmy.

5. Kombinace propagace podmínek a prohledávání: kontrola dopředu, (častěný/úplný) pohled dopředu, heuristiky pro uspořádání proměnných a hodnot, prohledávání bez navracení.

6. Optimalizační problémy, metody větví a mezí. Příliš omezené problémy a jejich modely.

7. Globální podmínky.

8. Modelování problémů a praktické realizace.

Poslední úprava: Barták Roman, prof. RNDr., Ph.D. (26.04.2007)

angličtina

1. Introduction: history and relation to other research areas, application areas, definition of a Constraint Satisfaction Problem and binary problems.

2. Local search techniques: hill climbing, min-conflicts, random walk, Tabu Search, GSAT, Genet.

3. Tree search techniques: backtracking, backjumping, dynamic backtracking, backmarking, limited discrepancy search, incomplete search.

4. Consistency techniques; node, arc, and path consistencies and algorithms to achieve them, general consistency notions.

5. Combining constraint propagation and search: forward checking, (partial/full) look ahead, variable and value ordering heuristics, backtrack-free search.

6. Optimization problems, branch and bound. Over-constrained problems and their models.

7. Global constraints.

8. Modelling problems and constraint programming in practice.

Poslední úprava: Barták Roman, prof. RNDr., Ph.D. (26.04.2007)