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. |