Diplomová práce

Algebraické metody pro CSP

Algebraic methods for CSP

Bc. et Bc. Petr Novotný, učo 172743
Anotace

Cílem této diplomové práce je představení pokročilých metod univerzální algebry sloužících ke klasifikaci složitosti problémů s omezujícími podmínkami. Zejména se zajímáme o teorii krotkých kongruencí (TCT). Kromě úvodu do této teorie je v práci ukázáno, jak lze TCT využít k rozhodnutí, zda je nějaký problém s omezujícími podmínkami rozhodnutelný v polynomiálním čase, nebo NP-úplný. V závěru práce …více

Abstract

The aim of this diploma thesis is to introduce the reader into some advanced methods of universal algebra. These methods - especially the tame congruence theory (TCT) - can be used to classify the complexity of constraint satisfaction problems (CSP's). The most important (and yet unresolved) question is whether every CSP is either decidable in polynomial time or NP-complete. The thesis shows how it …více

Klíčová slova
univerzální algebra složitost CSP krotké kongruence pologrupy universal algebra complexity tame congruence theory semigroups
Zadání práce
Obsahem práce bude studium nových výsledků ohledně CSP (Constraint Satisfaction Problem), které se pravidelně objevují na nejprestižnějších informatických konferencích - FOCS, ICALP, STOC a STACS. Zvláštní péče bude při studiu věnována algebraickým metodám v (prozatím neúplných) důkazech dichotomie CSP. Student si doplní znalosti z univerzální algebry, teorie pologrup a teorie grafů. Očekává se též aktivní přístup k řešení některých prozatím otevřených problémů souvisejících s danou problematikou.
Administrativní informace
Práce zkontrolována:
17. 5. 2010 09:48, doc. Mgr. Ondřej Klíma, Ph.D., učo 3868
Plný text práce
678,5 KB / soubor PDF
Jazyk práce
čeština čeština
Termín obhajoby
14. 6. 2010
Práce byla úspěšně obhájena

Vedoucí

doc. Mgr. Ondřej Klíma, Ph.D., učo 3868
ÚMS Ústavy PřF MU

Oponent

doc. Mgr. Michal Kunc, Ph.D., učo 2906
ÚMS Ústavy PřF MU

Literatura

  • BURRIS, Stanley N. Logic for mathematics and computer science. New Jersey: Prentice Hall, 1998, xix, 420 s. ISBN 0-13-285974-2.
  • BURRIS, Stanley a H. P. SANKAPPANAVAR. A course in universal algebra. New York: Springer-Verlag, 1981, 276 s. ISBN 0387905782.
  • MATOUŠEK, Jiří a Jaroslav NEŠETŘIL. Invitation to discrete mathematics. Oxford: Clarendon Press, 1998, xv, 410. ISBN 0198502087.
  • HOBBY, David a Ralph MCKENZIE. The Structure of Finite Algebras. Providence: American Mathematical Society, 1988, 209 s. ISBN 0-8218-3400-2.
Citovat tuto práci
Masarykova univerzita Přírodovědecká fakulta
Studijní program
Matematika
Obor

Práce na příbuzné téma

Seznam prací, které mají shodná klíčová slova.

Podobné práce
 
Název
Vložil
Vloženo
Práva
Archiv závěrečné práce Petr Novotný PřF N-MA ALG, učo 172743 l1k2c/6
Novotný, P.
12. 5. 2010
Složky
Soubory
Anotace anglicky annotation_english.txt
Novotný, P.
12. 5. 2010
Anotace česky annotation.txt
Novotný, P.
12. 5. 2010
Klíčová slova keywords.txt
Novotný, P.
12. 5. 2010
posudek_oponent novotny10.pdf
Kunc, M.
7. 6. 2010
text práce diplomka.pdf
Novotný, P.
12. 5. 2010

  • Přidání souboru

    Soubor nebo složku lze nahrát pomocí tlačítka Přidat.

  • Další operace se soubory

    Podrobnosti lze zjistit označením příslušného řádku.

  • Pohled pro experty

    Pro častou práci je možné zvolit režim Více možností.

  • Vyhledávání souborů

    Vyhledávaný výraz můžete zadat přímo do adresního řádku.

  • Rychlý přístup k souborům

    Pomocí funkce Nedávné je možné se rychle vrátit k právě prohlíženým souborům. Oblíbené soubory je také možné označit Hvězdičkou.