Feder, Vardi a CSP
| Thesis title in Czech: | Feder, Vardi a CSP |
|---|---|
| Thesis title in English: | Feder, Vardi and CSP |
| Academic year of topic announcement: | 2008/2009 |
| Thesis type: | diploma thesis |
| Thesis language: | |
| Department: | Department of Algebra (32-KA) |
| Supervisor: | doc. Mgr. Pavel Růžička, Ph.D. |
| Author: | hidden - assigned and confirmed by the Study Dept. |
| Date of registration: | 18.11.2008 |
| Date of assignment: | 18.11.2008 |
| Guidelines |
| 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. |
| References |
| 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 |