Bakalářská práce

Univerzální algebra a CSP

Universal algebra and CSP

Petr Novotný, učo 172743
Anotace

Cílem této bakalářské práce je představit jádro algebraického přístupu ke klasifikaci složitosti problémů s omezujícími podmínkami (CSP). V práci se zabýváme studiem neuniformní varianty tohoto problému. Zejména se zajímáme o to, zda je každý takový problém buďto řešitelný v polynomiálním čase, nebo NP-úplný. Z tohoto důvodu nejprve studujeme omezující podmínky (tj. množiny relací) definující daný …více

Abstract

The aim of this bachelor thesis is to present the core of an algebraic approach to the classification of computational complexity of constraint satisfaction problems (CSPs). Restricted forms of CSP, the non-uniform constraint satisfaction problems, are studied. The ultimate goal of this approach is to decide whether every non-uniform CSP is either tractable or NP-complete. In order to accomplish this …více

Klíčová slova
CSP problémy s omezujícími podmínkami univerzální algebra složitost P-NP dichotomie relační klony klony operací constraint satisfaction problems universal algebra computational complexity relational clones clones of operations P-NP dichotomy
Zadání práce
Obsahem práce bude studium složitostních aspektů CSP (Constraint Satisfaction Problem). Zvláštní péče bude věnována algebraickým metodám při určování složitosti. Student si rozšíří znalosti z univerzalní algebry (malcevovské operace) a také z teorie složitosti (třídy P, NP, #P, dále úplnost, redukce problémů). Dále bude možné studovat souvislosti s diskrétní matematikou a algebrou (základní algoritmické problémy z teorie grafů, řešení rovnic v pologrupách, kontrola identit v algebrách).
Administrativní informace
Práce zkontrolována:
11. 10. 2008 13:01, (IS automaticky)
Plný text práce
550,7 KB / soubor PDF
Jazyk práce
čeština čeština
Termín obhajoby
26. 6. 2008
Práce byla úspěšně obhájena

Vedoucí

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

Oponent

doc. Mgr. Michal Kunc, Ph.D., učo 2906

Literatura

  • NEŠETŘIL, Jaroslav a Jiří MATOUŠEK. Invitation to discrete mathematics. Oxford: Clarendon Press, 1998, xv, 410 s. ISBN 0-19-850207-9.
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 B-MA OM, učo 172743 j7tr3/6
Novotný, P.
1. 6. 2008
Složky
Soubory
Anotace anglicky annotation_english.txt
Novotný, P.
2. 6. 2008
Anotace česky annotation.txt
Novotný, P.
2. 6. 2008
Klíčová slova keywords.txt
Novotný, P.
2. 6. 2008
novotny08_posudek_oponeta.pdf
Matoušková, M.
20. 6. 2008
Text práce bc_csp.pdf
Novotný, P.
2. 6. 2008

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