velikost textu

CSP over oriented trees

Upozornění: Informace získané z popisných dat či souborů uložených v Repozitáři závěrečných prací nemohou být použity k výdělečným účelům nebo vydávány za studijní, vědeckou nebo jinou tvůrčí činnost jiné osoby než autora.
Název:
CSP over oriented trees
Název v češtině:
CSP nad orientovanými stromy
Typ:
Bakalářská práce
Autor:
Bc. William Tatarko
Vedoucí:
Mgr. Jakub Bulín
Oponent:
Mgr. Libor Barto, Ph.D.
Id práce:
209015
Fakulta:
Matematicko-fyzikální fakulta (MFF)
Pracoviště:
Katedra algebry (32-KA)
Program studia:
Matematika (B1101)
Obor studia:
Obecná matematika (MOM)
Přidělovaný titul:
Bc.
Datum obhajoby:
21. 6. 2019
Výsledek obhajoby:
Výborně
Jazyk práce:
Angličtina
Klíčová slova:
CSP, orientované stromy, NP-úplnost
Klíčová slova v angličtině:
CSP, oriented trees, NP-completeness
Abstrakt:
V této práci představíme orientovaný strom, který má pouze 26 vrcholů a jehož CSP je NP-úplné. Toto slouží jako protipříklad k domněnce, že každý orientovaný strom s touto vlastností má alespoň 39 vrcholů. Práce je rozdělena do tří kapitol. V první představíme základní definice a poznatky tohoto tématu. Následně ukážeme, že orientované stromy určitých tvarů mají CSP řešitelné v polynomiálním čase. Nakonec dokážeme, že CSP jistého orientovaného stromu je NP-úplné. 1
Abstract v angličtině:
In this thesis we present an oriented tree with only 26 vertices, whose CSP is NP-complete. This serves as a counterexample for a conjecture that any oriented tree with this property has at least 39 vertices. The work itself is divided into three chapters. In the first one, basic definitions and tools of this topic are introduced. Then, tractability of trees of special shapes is shown. Finally, NP-completeness of a certain oriented tree is proven. 1
Dokumenty
Stáhnout Dokument Autor Typ Velikost
Stáhnout Text práce Bc. William Tatarko 751 kB
Stáhnout Abstrakt v českém jazyce Bc. William Tatarko 16 kB
Stáhnout Abstrakt anglicky Bc. William Tatarko 16 kB
Stáhnout Posudek vedoucího Mgr. Jakub Bulín 74 kB
Stáhnout Posudek oponenta Mgr. Libor Barto, Ph.D. 501 kB
Stáhnout Záznam o průběhu obhajoby prof. RNDr. Jan Rataj, CSc. 152 kB