|
|
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)
|
|
|
Ortogonální báze a Jordanův normální tvar
Kučera, Daniel ; Šaroch, Jan (vedoucí práce) ; Barto, Libor (oponent)
Unitárně diagonalizovatelné endomorfismy jsou popsány jako zobrazení, která komutují s adjungovaným zobrazením. Tato práce z Lineární algebry se snaží popsat endomorfismy komplexního vektorového prostoru, pro které existuje ortogonální báze taková, že matice endomorfismu vzhledem k této bázi je v Jordanově tvaru. Zavádíme pro ně pojem unitárně jordanizovatelný endomorfismus. První dvě kapitoly obsahují charakterizaci unitárně diag- onalizovatelných zobrazení a důkaz existence a jednoznačnosti Jordanova normálního tvaru. V třetí kapitole se objevuje souvislost s bilineárními for- mami; s jejich pomocí je dokázáno, že endomorfismus s jediným vlastním číslem a Jordanovými řetízky délky nejvýše dva je vždy unitárně jordanizo- vatelný. V poslední kapitole je diskutována jednoznačnost ortogonální polární báze bilineární formy a je představen algoritmus, který rozhodne, zda je en- domorfismus unitárně jordanizovatelný. 1
|
|
|
Constraint Satisfaction Problem and Universal Algebra
Kazda, Alexandr ; Barto, Libor (vedoucí práce) ; Růžička, Pavel (oponent) ; Valeriote, Matt (oponent)
Práce sestává ze souboru mých příspěvků v oblasti univerzální algebry. Naší hlavní oblastí zájmu jsou algebry polymorfismů relačních struktur, motivací pak především složitost problému splnitelnosti omezení (CSP). Nejprve ukážeme pomocí univerzální algebry (a stopového množství analýzy), že CSP náhodné relační struktury je skoro jistě NP-úplný. Pokračujeme studiem orientovaných grafů, které mají Mal'cevův polymorfismus. Ukážeme, že takové grafy už nutně musí mít majoritu. Dále pak demonstrujeme použití techniky absorpce: Přinášíme nový důkaz faktu, že kongruenčně modulární reflexivní ori- entované grafy mají vždy NU polymorfismus. Na závěr práce prezentujeme alge- braický důkaz výsledku (poprvé dokázaného kombinatoriky), že 3-konzervativní relační struktury s nejvýše binárními relacemi se vyznačují jednoduchou dicho- tomií: Jejich CSP je bud' NP-úplné, nebo je lze řešit pomocí metody lokální konzistence. 1
|
|
| |
|
| |
|
| |
|
| |
|
| |
|
|
Testování prvočíselnosti pomocí eliptických křivek
Pashchenko, Olha ; Barto, Libor (vedoucí práce) ; Šťovíček, Jan (oponent)
V předložené práci studujeme testy prvočíselnosti. Test prvočíselnosti je algoritmus, který pro zadané přirozené číslo zjistí, jestli je to prvočíslo nebo složené číslo. V první časti práce zopakujeme základní definice a tvrzení z teorie čísel a podívame se na Pocklingtonův algoritmus, který pracuje s prvky z grupy (Z/nZ)∗ . Dále studujeme Zobecněný Pockling- tonův test prvočíselnosti a Pépinův test pro Fermatova čísla. V druhé časti práce před- stavíme základy teorie eliptických křivek. Dále studujeme Goldwasser-Killianův, který je založený na eliptických křivkách. Součástí práce jsou také malé experimenty s Goldwasser- Killianovem testem. 1
|
host ::
RSS.