|
|
CSP over oriented trees
Tatarko, William ; Bulín, Jakub (vedoucí práce) ; Barto, Libor (oponent)
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
|
|
|
Čtverce v posloupnostech čísel
Hudcová, Barbora ; Holub, Štěpán (vedoucí práce) ; Bulín, Jakub (oponent)
V této práci vycházíme z článku, kde bylo zkonstruováno první nekonečné slovo nad konečnou abecedou, které se vyhýbá aditivním třetím mocninám. Ukazujeme konstrukce dalších slov se stejnou vlastností. Dále na jednom z těchto slov ilustrujeme hlavní myš- lenku důkazu, že se dané slovo vyhýbá aditivním třetím mocninám. 1
|
|
|
Finitely generated clones
Draganov, Ondřej ; Barto, Libor (vedoucí práce) ; Bulín, Jakub (oponent)
Klonem rozumíme množinu operací konečné arity, která je uzavřená na sklá- dání a obsahuje projekce. Řekneme, že je konečně generovaný, existuje-li konečná podmnožina {f1, . . . , fn} taková, že všechny ostatní operace lze vyjádřit pomocí skládání f1, . . . , fn. Práce představuje příklady konečně a nekonečně generova- ných klonů na konečné množině. Nejprve ukážeme explicitní konstrukci, pomocí které můžeme najít generátory některých konečně generovaných klonů, a expli- citní vyjádření všech operací těchto klonů jako termy nalezených generátorů. Dále definujeme relace, jejichž kompatibilní operace mají omezenou esenciální aritu, a diskutujeme jejich možné modifikace. Konečně pro každou binární operaci f, pomocí které nelze naskládat esenciálně ternární operaci, nalezneme maximální klon esenciálně binárních operací, který f obsahuje. 1
|
|
|
Constraint satisfaction, graphs and algebras
Bulín, Jakub ; Barto, Libor (vedoucí práce) ; Růžička, Pavel (oponent) ; Bulatov, Andrei (oponent)
CSP, grafy a algebry Jakub Bulín Abstrakt Tato práce sestává ze tří článků v oblasti algebraického přístupu k problému splňování podmínek (CSP). V prvním článku, se spoluautory Deli'cem, Jacksonem a Nivenem, studujeme redukci CSP na orientované grafy. Pro každou relační strukturu A konstruujeme orientovaný graf D(A) takový, že CSP(A) a CSP(D(A)) jsou logspace ekvivalentní a většina rele- vantních vlastností se přenáší z A na D(A). Důsledkem je, že algebraické hypotézy charekterizující CSP řešitelné v P, NL a L jsou ekvivalentní je- jich restrikcím na orientované grafy. Ve druhém článku dokazujeme, že pro danou core relační strukturu A s konečnou šířkou a B ⊆ A lze algorit- micky rozhodnout, zda je B absorbující podalgebra algebry polymorfismů A. Jako vedlejší produkt získáváme, že Jónssonova absorpce se v tomto případě shoduje s obvyklou absorpcí. Ve třetím článku, za použití mod- erních algebraických nástrojů (např. teorie absorpce a pointující operace), potvrzujeme hypotézu o dichotomii CSP pro tzv. speciální orientované stromy. Konkrétně, core speciální stromy řešitelné v P mají konečnou šířku. Klíčová slova: problém splňování omezení, algebra polymorfismů, ab- sorbující podalgebra, konečná...
|
|
|
Algebraický přístup k CSP
Bulín, Jakub
Nechť A je konečná relační struktura. Problém splňování omezení s šablonou A, CSP (a), rozhoduje, zda vstupní struktura X je homomorfní A. Hypotéza o dichotomii CSP Federa a Vardiho říká, že CSP(A) je vždy buď v P nebo NP-úplný. V první části předsdtavíme algebraický přístup k CSP a shrneme známé výsledky o CSP pro orientované grafy, tzv. H-barvení. Ve druhé části se zabýváme jistou třídou orientovaných stromů, tzv. speciálními polyádami. Pomocí algebraického přístupu potvrdíme dichotomickou hypotézu pro speciální polyády. V polynomiálním případě poskytneme jemnější popis a zkontruujeme speciální polyádu T takovou, že CSP(T) je v P, ale T nemá šířku 1 ani žádné near-unanimity polymorfismy.
|
|
|
An elementary proof of the existence of primitive elements
Majerčík, Miroslav ; Kepka, Tomáš (vedoucí práce) ; Bulín, Jakub (oponent)
Názov práce: Elementárny dôkaz vety o primitívnom prvku Autor: Miroslav Majerčík Katedra / Ústav: Katedra algebry Vedúcí bakalárskej práce: prof. RNDr. Tomáš Kepka, DrSc. Abstrakt: Tento text je venovaný elementárnym dôkazom dvoch významných viet teórie čísel a to Gaussovmu kvadratickému zákonu reciprocity a vete o primitívnom prvku. Dôkazy týchto viet sú vo forme menších na seba nadväzujúcich lemmat a dôkazov. Úvod je venovaný historickému priblíženiu a metóde dôkazov viet. Prvá kapitola smeruje k dôkazu Gaussovmu kvadratickému zákonu reciprocity a druhá k dôkazu vety o primitívnom prvku a k určeniu prirodzených čísel n pre ktoré existuje primitívny prvok modulo n a pre ktoré nie. K dôkazu týchto viet bolo potrebné dokázat aj niekol'ko dalších viet, napríklad malú Fermatovu vetu alebo schému rozdielu mocnín. Klúčové slová: Kvadratický zbytok, Primitívny koreň, Rád prvku modulo n, Eulerova funkcia Title: An elementary proof of the existence of primitive elements Author: Miroslav Majerčík Department: Department of Algebra Supervisor: prof. RNDr. Tomáš Kepka, DrSc. Abstract: This text is about elementary proofs of two well known number theory statements, Gauss quadratic reciprocity law and proof of the existence of primitive elements....
|
|
|
Algebraický přístup k CSP
Bulín, Jakub ; Barto, Libor (vedoucí práce) ; Růžička, Pavel (oponent)
Nechť A je konečná relační struktura. Problém splňování omezení s šablonou A, CSP (a), rozhoduje, zda vstupní struktura X je homomorfní A. Hypotéza o dichotomii CSP Federa a Vardiho říká, že CSP(A) je vždy buď v P nebo NP-úplný. V první části předsdtavíme algebraický přístup k CSP a shrneme známé výsledky o CSP pro orientované grafy, tzv. H-barvení. Ve druhé části se zabýváme jistou třídou orientovaných stromů, tzv. speciálními polyádami. Pomocí algebraického přístupu potvrdíme dichotomickou hypotézu pro speciální polyády. V polynomiálním případě poskytneme jemnější popis a zkontruujeme speciální polyádu T takovou, že CSP(T) je v P, ale T nemá šířku 1 ani žádné near-unanimity polymorfismy.
|
|
| |
host ::
RSS.