CSP nad orientovanými stromy
| Název práce v češtině: | CSP nad orientovanými stromy |
|---|---|
| Název v anglickém jazyce: | CSP over oriented trees |
| Akademický rok vypsání: | 2019/2020 |
| Typ práce: | bakalářská práce |
| Jazyk práce: | |
| Ústav: | Katedra algebry (32-KA) |
| Vedoucí / školitel: | doc. Mgr. Libor Barto, Ph.D. |
| Řešitel: |
| Zásady pro vypracování |
| Práce se zaměří na studium výpočetní složitosti problému splnitelnosti omezujících podmínek (CSP) nad orientovanými stromy,
konkrétněji na otázku, jaký je nejmenší orientovaný strom, jehož CSP je NP-úplný problém. |
| Seznam odborné literatury |
| [1] T. Feder, M. Vardi: The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory, SIAM J. Comput., 28/1 (1998), 57–104.
[2] L. Barto, M. Kozik, M. Maroti, T. Niven: CSP dichotomy for special triads, Proc. Amer. Math. Soc. 137/9 (2009), 2921-2934 [3] L. Barto, J. Bulín: CSP dichotomy for special polyads with L. Barto, Int. J. Algebra Comput. 23/05 (2013), 1151–1174 |
| Předběžná náplň práce |
| V článku [2] je zkonstruován příklad orientovaného stromu s 39 vrcholy, jehož CSP je NP-úplný problém. Jde o nejmenší takový orientovaný strom?
I když se problém týká výpočetní složitosti, žádné znalosti z teoretické informatiky nejsou potřeba, protože lze problém redukovat na studium operací kompatibilních s orientovanými stromy. Položená otázka je pravděpodobně příliš těžká. Student/ka se může pokusit pro nějaká n ručně ukázat, že všechny menší stromy mají polynomiálně řešitelné CSP, a pro nějaká větší n dokázat totéž za pomoci počítače. Další možností je zaměřit se jen na nějaké speciální třídy stromů, apod. |