Poslední úprava: doc. Mgr. et Mgr. Jan Žemlička, Ph.D. (14.05.2019)
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.
Poslední úprava: doc. Mgr. et Mgr. Jan Žemlička, Ph.D. (14.05.2019)
The constraint satisfaction problem (CSP) provides a framework in which it is possible to express, in a natural way,
many
combinatorial problems encountered in artificial intelligence and computer science. In many cases effective
algorithms exist
to solve such a problem, and in others (such as 3SAT) we can show it to be NP-complete. It is conjectured that
every CSP
is either in P or NP-complete, which is the so called dichotomy conjecture. In the course, we will study the
mathematics of
CSP and focus on algebraic methods.
The course may not be taught every academic year.
Podmínky zakončení předmětu -
Poslední úprava: doc. Mgr. et Mgr. Jan Žemlička, Ph.D. (10.06.2019)
Předmět bude zakončen zkouškou. Výsledná známka bude určena podle úspěšnosti řešení zadaných problémů během semestru.
Poslední úprava: doc. Mgr. et Mgr. Jan Žemlička, Ph.D. (28.10.2019)
Students have to pass exam. The requirements for the exam correspond to what has been done during lectures.
Literatura -
Poslední úprava: T_KA (14.05.2013)
[1] A. Bulatov, A. Krokhin, P. Jeavons: Constraint satisfaction problems and finite algebras. In: Proc. 27th International Colloquium on Automata, Languages and Programming, ICALP'00. Volume 1853 of LNCS, Springer-Verlag (2000) 272-282.
[2] V. Dalmau: Generalized majority-minority operations are tractable. In Proceedings 20th IEEE Symposium on Logic in Computer Science, (LICS 2005),438-447.
[3] T. Feder, M.Y. Vardi: The computational structure of monotone monadic SNP and constraint satisfaction: a study through Datalog and group theory. SIAM J. Computing, 28 (1), 1998, 57-104.
[4] B. Larose, L. Zádori: Bounded width problems and algebras. Algebra Universalis 56 (3-4), 2007, 439-466.
[5] T. J. Schaefer: The complexity of satisfiability problems, in Proc. 10th ACM Symp. on Theory of Computing, ACM, New York, 1978, 216-226.
Poslední úprava: T_KA (14.05.2013)
[1] A. Bulatov, A. Krokhin, P. Jeavons: Constraint satisfaction problems and finite algebras. In: Proc. 27th International Colloquium on Automata, Languages and Programming, ICALP'00. Volume 1853 of LNCS, Springer-Verlag (2000) 272-282.
[2] V. Dalmau: Generalized majority-minority operations are tractable. In Proceedings 20th IEEE Symposium on Logic in Computer Science, (LICS 2005),438-447.
[3] T. Feder, M.Y. Vardi: The computational structure of monotone monadic SNP and constraint satisfaction: a study through Datalog and group theory. SIAM J. Computing, 28 (1), 1998, 57-104.
[4] B. Larose, L. Zádori: Bounded width problems and algebras. Algebra Universalis 56 (3-4), 2007, 439-466.
[5] T. J. Schaefer: The complexity of satisfiability problems, in Proc. 10th ACM Symp. on Theory of Computing, ACM, New York, 1978, 216-226.
Požadavky ke zkoušce -
Poslední úprava: RNDr. Jakub Bulín, Ph.D. (11.10.2018)
Výsledná známka bude určena podle úspěšnosti řešení zadaných problémů během semestru.
Poslední úprava: doc. Mgr. et Mgr. Jan Žemlička, Ph.D. (28.10.2019)
Solving problems during semester.
Sylabus -
Poslední úprava: T_KA (14.05.2013)
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
Poslední úprava: T_KA (14.05.2013)
1. Definition of CSP, its equivalent forms, basic notions and properties