PředmětyPředměty(verze: 845)
Předmět, akademický rok 2018/2019
   Přihlásit přes CAS
Úvod do složitosti CSP - NALG117
Anglický název: Introduction to Complexity of CSP
Zajišťuje: Katedra algebry (32-KA)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2018
Semestr: zimní
E-Kredity: 3
Rozsah, examinace: zimní s.:2/0 Zk [hodiny/týden]
Počet míst: neomezen
Minimální obsazenost: neomezen
Stav předmětu: zrušen
Jazyk výuky: čeština
Způsob výuky: prezenční
Garant: doc. Mgr. Libor Barto, Ph.D.
Kategorizace předmětu: Matematika > Algebra
Záměnnost : NMAG563
Je neslučitelnost pro: NMAG563
Je záměnnost pro: NMAG563
Anotace -
Poslední úprava: T_KA (19.05.2009)
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.
Literatura -
Poslední úprava: T_KA (19.05.2009)

[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.

Sylabus -
Poslední úprava: T_KA (19.05.2009)

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

 
Univerzita Karlova | Informační systém UK