PředmětyPředměty(verze: 945)
Předmět, akademický rok 2023/2024
   Přihlásit přes CAS
Úvod do složitosti CSP - NMAG563
Anglický název: Introduction to complexity of CSP
Zajišťuje: Katedra algebry (32-KA)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2023
Semestr: zimní
E-Kredity: 3
Rozsah, examinace: zimní s.:2/0, Zk [HT]
Počet míst: neomezen
Minimální obsazenost: neomezen
4EU+: ne
Virtuální mobilita / počet míst pro virtuální mobilitu: ne
Stav předmětu: vyučován
Jazyk výuky: angličtina, čeština
Způsob výuky: prezenční
Způsob výuky: prezenční
Garant: Dmitrii Zhuk, Ph.D.
Třída: M Mgr. MMIB
M Mgr. MMIB > Povinně volitelné
M Mgr. MSTR
M Mgr. MSTR > Volitelné
Kategorizace předmětu: Matematika > Algebra
Neslučitelnost : NALG117
Záměnnost : NALG117
Je záměnnost pro: NALG117
Anotace -
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.
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.

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.

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.

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

 
Univerzita Karlova | Informační systém UK