Národní úložiště šedé literatury Nalezeno 6 záznamů.  Hledání trvalo 0.00 vteřin. 
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.

Viz též: podobná jména autorů
1 BULÍN, Jiří
Chcete být upozorněni, pokud se objeví nové záznamy odpovídající tomuto dotazu?
Přihlásit se k odběru RSS.