|
|
|
||
Poslední úprava: doc. Mgr. et Mgr. Jan Žemlička, Ph.D. (14.05.2019)
|
|
||
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: 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: 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: 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
|