Ú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 [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: zrušen
• Jazyk výuky: čeština
• Způsob výuky: prezenční
• Garant: prof. 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

čeština

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.

Poslední úprava: T_KA (19.05.2009)

angličtina

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.

Poslední úprava: T_KA (19.05.2009)

Literatura

čeština

[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 (19.05.2009)

Sylabus

čeština

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 (19.05.2009)

angličtina

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

Poslední úprava: T_KA (19.05.2009)