Sylabus
1. Definice CSP, ekvivalentní přístupy, základní pojmy a vlastnosti
2. Polymorfismy, algebraické redukce
3. Problémy konečné šířky
4. Schaeferova věta o dichotomii pro booleovská CSP
5. Malcevská CSP
Anotace
Problém splnitelnosti omezení (the Constraint Satisfaction Problem, CSP) poskytuje společný rámec pro studium mnoha kombinatorických problémů v umělé inteligenci a informatice. V mnoha případech existují efektivní algoritmy pro řešení tohoto problému, v jiných (například 3SAT) lze ukázat jeho NP-úplnost. Takzvaná dichotomická hypotéza říká, že každý CSP je buď polynomiálně řešitelný, nebo NP-úplný. V přednášce se zaměříme na matematické aspekty CSP, zejména na algebraický přístup k řešení dichotomické hypotézy.
Předmět nemusí být vyučován každý rok, je vyučován alespoň jednou za dva roky.