CSP over oriented trees
| Název práce v češtině: | CSP nad orientovanými stromy |
|---|---|
| Název v anglickém jazyce: | CSP over oriented trees |
| Klíčová slova: | CSP, orientované stromy, NP-úplnost |
| Klíčová slova anglicky: | CSP, oriented trees, NP-completeness |
| Akademický rok vypsání: | 2018/2019 |
| Typ práce: | bakalářská práce |
| Jazyk práce: | angličtina |
| Ústav: | Katedra algebry (32-KA) |
| Vedoucí / školitel: | RNDr. Jakub Bulín, Ph.D. |
| Řešitel: | skrytý - zadáno a potvrzeno stud. odd. |
| Datum přihlášení: | 14.11.2018 |
| Datum zadání: | 14.11.2018 |
| Datum potvrzení stud. oddělením: | 22.11.2018 |
| Datum a čas obhajoby: | 21.06.2019 08:00 |
| Datum odevzdání elektronické podoby: | 09.05.2019 |
| Datum odevzdání tištěné podoby: | 17.05.2019 |
| Datum proběhlé obhajoby: | 21.06.2019 |
| Oponenti: | doc. Mgr. Libor Barto, Ph.D. |
| 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. |