Bachelor's thesis

Universal algebra and CSP

Univerzální algebra a CSP

Petr Novotný, UČO 172743
Abstract

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ý …more

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 …more

Keywords
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
Thesis description
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).
Administrative information
The thesis has been checked:
11/10/2008 13:01, (IS automatically)
Full text of thesis
550,7 KB / file PDF
Language used
Czech Czech
Defence date
26/6/2008
The thesis was defended successfully

Supervisor

doc. Mgr. Ondřej Klíma, Ph.D., UČO 3868
Ústavy PřF MU

Reader

doc. Mgr. Michal Kunc, Ph.D., UČO 2906

Literature

  • NEŠETŘIL, Jaroslav and Jiří MATOUŠEK. Invitation to discrete mathematics. Oxford: Clarendon Press, 1998, xv, 410 s. ISBN 0-19-850207-9.
Cite this text
Masaryk University Faculty of Science
Programme
Mathematics
Field of Study

Theses on a related topic

List of theses with an identical keyword.

Similar documents
 
Name
Posted by
Uploaded/Created
Rights
Archive of Thesis/Dissertation Petr Novotný PřF B-MA OM, učo 172743 j7tr3/6
Novotný, P.
1/6/2008
Folders
Files
Abstract (in English) annotation_english.txt
Novotný, P.
2/6/2008
Abstract (in Czech) annotation.txt
Novotný, P.
2/6/2008
Keywords 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.