|
|
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
|
|
|
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
|
|
|
Weighted Clones
Gaysin, Azza ; Barto, Libor (vedoucí práce) ; Příhoda, Pavel (oponent)
Vážené klony Azza Gaysin 3. ledna 2018 Abstrakt V této práce kompletně popisujeme strukturu všech binárních částí vážených klonů nad booleovskými klony generovanými jednou z polosva- zových operací a jednou nebo dvěma konstantními operacemi. Rovněž po- skytujeme úplný popis všech atomických a maximálných vážených klonů nad těmito klony. Klíčová slova: Relační klony, Vážené klony, VCSP 1
|
|
|
Finitely Related Algebras
Goldstein, Marek ; Barto, Libor (vedoucí práce) ; Stanovský, David (oponent)
Algebraická struktura je konečného relačního stupně, pokud je její klon určen konečným počtem finitárních relací. V této práci zkoumáme grafové algebry s cílem určit, které z nich mají tuto vlastnost. Představujeme stručný souhrn základních teoretických poznatků a uvádíme již známé výsledky o algebrách ko- nečného relačního stupně, zejména klademe důraz na souvislost s Mal'cevskými podmínkami. Dále pak ukazujeme základní poznatky o struktuře grafových al- geber. Těžiště této spočívá v částečné klasifikaci grafových algeber konečného relačního stupně. Provádíme důkazy pro různé třídy grafových algeber, napří- klad algebry určené souvislými bipartitními grafy či grafy obsahujícími určité podgrafy, avšak několik případů zůstává nerozhodnutých. 1
|
|
|
Arita NU polymorfismů
Draganov, Ondřej ; Barto, Libor (vedoucí práce) ; Růžička, Pavel (oponent)
Práce se zabývá aritou NU polymorfismů relačních struktur. Cílem je zjednodušit a přehledně zpracovat již existující příklad relační struktury, která má NU polymorfismus, ale nemá žádný NU polymorfismus "nízké arity vzhledem k aritě relací a počtu prvků nosné množiny. V práci jsou explicitně popsány m-ární relační struktury s n prvky, n ≥ 2, m ≥ 3, které nemají NU polymorfismus arity (m − 1)2n−2 , ale mají NU polymorfismus arity (m − 1)2n−2 + 1, který je v práci zkonstruován, a binární relační struktury s n prvky, n ≥ 3, které nemají NU polymorfismus arity 22n−3 , ale mají NU polymorfismus arity 22n−3 + 1.
|
|
|
Relational Approach to Universal Algebra
Opršal, Jakub ; Barto, Libor (vedoucí práce) ; Růžička, Pavel (oponent) ; Mayr, Peter (oponent)
Název práce: Relační přístup k universální algebře Autor: Jakub Opršal Katedra: Katedra algebry Vedoucí disertační práce: doc. Libor Barto, Ph.D., Katedra algebry Abstrakt: V této práci předkládáme popis některých algebraických vlastnostní pomocí relací a relačních struktur. V první části se zaměřujeme na Neumannův svaz interpretačních typů variet. Charakterizujeme variety definované lineárními rovnostmi a uvádíme příklad několika vlastností, které nejsou charakterizova- telné lineárními rovnostmi. Dále se věnujeme Taylorově domněnce o varietách s modulárními svazy kongruencí. Speciálně ukážeme, že interpretační spojení dvou idempotentních variet, které nemají modulární svazy kongruencí, samo nemá mo- dulární svazy kongruencí. Uvádíme i obdobný výsledek pro variety s krychlovým termem. V druhé části práce uvádíme popis Bulatovových vyšších komutátorů ve varietách s mal'cevským termem. Dále použijeme tento výsledek na to, abychom ukázali, že pro každou algebru s mal'cevskou operací existuje největší klon, který obsahuje tu samou mal'cevskou operaci, má stejný svaz kongruencí a jehož ko- mutátory se shodují s těmi v původní algebře. Nakonec uvádíme další aplikaci tohoto výsledku a to na...
|
|
|
Variety superalgeber
Lišková, Adéla ; Žemlička, Jan (vedoucí práce) ; Barto, Libor (oponent)
Cílem práce je představit základy teorie superalgeber, neboli Z2-graduovaných al- geber nad tělesem charakteristiky různé od dvou. Zároveň jsou doplněny potřebné základy univerzální a multilineární algebry, zejména tenzorový součin a pojmy va- rieta algeber a ideál identit. Předkládáme definice algebry a superalgebry včetně příkladů, dále se zabýváme tenzorovým součinem superalgeber a jeho vlastnostmi, Cliffordovými a Grassmannovými superalgebrami. Část práce je věnována kon- strukci volné neasociativní algebry a objasnění vztahu mezi varietami algeber a ideály identit, včetně upřesnění tohoto vztahu pro superalgebry. Věnujeme po- zornost také varietám superalgeber. 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á...
|
|
|
Vážené klony
Vančura, Jiří ; Barto, Libor (vedoucí práce) ; Příhoda, Pavel (oponent)
Známý problém splnitelnosti dané formule CSP je možné zobecnit na třídu optimalizačních problémů VCSP. V roce 2012 dokázali D. A. Cohen, M. C. Cooper, P. Creed, P. G. Jeavons a S. Živný, že stejnou roli jakou mají klony a relační klony pro CSP mají vážené klony a vážené relační klony pro VCSP. Samotná struktura vážených klonů ale zůstává neprozkoumaná a to i pro dvouprvkový obor hodnot. Tato práce podává detailnější důkaz výše zmíněného výsledku a dále zkoumá strukturu vážených klonů. Pro dvouprvkový obor hodnot uvádíme kompletní klasifikaci vážených klonů nad všemi sedmi minimálními klony. Powered by TCPDF (www.tcpdf.org)
|
|
|
Jak funguje vyhledávač Google
Vaněček, Jaromír ; Tůma, Jiří (vedoucí práce) ; Barto, Libor (oponent)
Tato práce se zabývá vyhledávačem Google, převážně způsobem, jakým jsou vyhledávané stránky řazeny a jeho aplikací v jiných oblastech. Nejprve představíme obecné fungování vyhledávače, vytvoříme Google matici a předvedeme si princip algoritmu PageRank. Následně vše, v čistě matematické části práce, podložíme matematickou teorií zahrnující především Perronovu větu. Další část je věnována použití PageRanku na porovnání týmů ve fotbalové Synot lize. Nakonec ještě uvedeme několik jednoduchých pozorování o tom, jak různé jevy v hypertextové struktuře webu ovlivňují Google matici. Powered by TCPDF (www.tcpdf.org)
|
host ::
RSS.