|
|
|
||
Last update: doc. Mgr. et Mgr. Jan Žemlička, Ph.D. (14.05.2019)
|
|
||
Last update: 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. |
|
||
Last update: 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.
|
|
||
Last update: doc. Mgr. et Mgr. Jan Žemlička, Ph.D. (28.10.2019)
Solving problems during semester. |
|
||
Last update: T_KA (14.05.2013)
1. Definition of CSP, its equivalent forms, basic notions and properties 2. Polymorphisms, algebraic reductions 3. Bounded width problems 4. Schaefer's dichotomy theorem for boolean CSPs 5. Maltsev CSPs
|