Feder, Vardi a CSP
| Název práce v češtině: | Feder, Vardi a CSP |
|---|---|
| Název v anglickém jazyce: | Feder, Vardi and CSP |
| Akademický rok vypsání: | 2008/2009 |
| Typ práce: | diplomová práce |
| Jazyk práce: | |
| Ústav: | Katedra algebry (32-KA) |
| Vedoucí / školitel: | doc. Mgr. Pavel Růžička, Ph.D. |
| Řešitel: | skrytý - zadáno a potvrzeno stud. odd. |
| Datum přihlášení: | 18.11.2008 |
| Datum zadání: | 18.11.2008 |
| Zásady pro vypracování |
| Cílem práce by bylo zpracování níže uvedeného článku. Je to přelomový a patrně nejvíce citovaný článek týkající se CSP (Constraint Satisfaction Problem). Je obsahově bohatý a inspirující avšak formálně velmi zevrubný. Samotné pochopení, dohledaní a často i dodělání důkazů dává dostatečný materiál pro diplomovou práci a zároveň poskytne dobrý základ pro budoucí samostatný výzkum v této atraktivní oblasti kombinující teorii výpočtové složitosti s univerzální algebrou. |
| Seznam odborné literatury |
| T. Feder, M.Y. Vardi, The Computational Structure of Monotone Monadic SNP and Constrait
Satisfaction: A Study through Datalog and Group Theory, SIAM Journal on Computing archive Volume 28, Issue 1 (February 1999) 57 -- 104 |