|
|
Lineární verze Holubova algoritmu
Tvrdý, David ; Holub, Štěpán (vedoucí práce) ; Žemlička, Jan (oponent)
Tato práce studuje lineární algoritmus, který pro zadané slovo rozhodne, zda existuje netriviální homomorfismus, jehož je dané slovo pevným bodem. Dále jsou v práci popsány pomocné datové struktury, které jsou pro lineární časovou složitost důležité. Součástí práce je i vlastní implementace tohoto algoritmu v jazyce Java včetně vizualizace chodu algoritmu pro konkrétní vstupy. 1
|
|
|
Zobecněná integrální vlastnost
Hrúzová, Jana ; Žemlička, Jan (vedoucí práce) ; Příhoda, Pavel (oponent)
Tato bakalářská práce vychází z odborného článku C. Boura a A. Canteaut, Another View of the Division Property, který pojednává o dělící vlastnosti množin z Fn 2 . V této práci nejprve zopakujeme důležité pojmy a tvrzení o booleovských funkcích, polynomech a Reed-Mullerových kódech. Následně definujeme množinu parit množiny z Fn 2 . Pomocí množiny parit zjednodušíme dělící vlastnost a ukážeme, jak vypadají množiny splňující různé stupně dělící vlastnosti. Díky tomu budeme moci určit, jak se dělící vlastnost šíří substitučně-permutační sítí. 1
|
|
|
Testování projektivity modulů
Matoušek, Cyril ; Šaroch, Jan (vedoucí práce) ; Žemlička, Jan (oponent)
Tato práce se zabývá otázkou existence testovacích modulů pro projektivitu. Testovacím modulem rozumíme pravý R-modul T takový, že pro každý pravý R-modul M platí, že M je projektivní, pokud T ∈ M⊥ . Ukážeme, že testovací moduly existují nad zprava perfektními okruhy, ale pro okruhy zprava neperfektní je jejich existence nedokazatelná v ZFC. K tomu užijeme Shelahův uniformizační princip, který je nezávislý na axiomech ZFC. Dále ukážeme, že za předpokladu slabého diamantového principu, rovněž nezávislého na ZFC, existují testovací moduly v okruzích konečné pravé globální dimenze. 1
|
|
|
Racionální lineární závislosti periodických bodů logistického zobrazení
Mik, Matěj ; Žemlička, Jan (vedoucí práce) ; Růžička, Pavel (oponent)
Body s periodou n polynomu f jsou právě kořeny, a tedy i prvky rozk- ladového nadtělesa, polynomu fn (x)−x, kde fn značí n-tou iteraci polynomu f. V práci se budeme zabývat popisem racionálních lineárních závislostí bodů s periodou n polynomu 4x(1−x), který určuje takzvané logistické zobrazení. Předvedeme popis závislostí pro n = 1, . . . , 5 a uvedeme poznatky získané o případu n = 6. Využívat při tom budeme počítačem spočtené rozklady polynomů nad racionálními čísly a jejich konečnými rozšířeními. Z rozkladů pomocí znalostí z komutativní a lineární algebry odvodíme souřadnice period- ických bodů vzhledem k nějaké bázi jejich lineárního obalu, což nám umožní jednoduše popsat jejich závislosti. Na závěr práce zformulujeme algoritmus na popis závislostí pro obecné n.
|
|
|
Krátké invertibilní prvky v cyklotomických okruzích
Kroutil, Jaroslav ; Žemlička, Jan (vedoucí práce) ; Příhoda, Pavel (oponent)
Tato bakalářská práce vychází z odborného článku, který pojednává o kritériu invertibility prvků ve speciálně volených cyklotomických okruzích. V této práci nejprve zopakujeme důležité pojmy a tvrzení z algebry, jež budeme potřebovat. Následně se budeme zabývat existencí nekonečně mnoha prvočísel splňujících podmínky, které využijeme k ireducibilnímu rozkladu cyklotomických polynomů. Na základě těchto polynomů definujeme cyklotomický okruh, ve kterém v závěru práce dokážeme invertibilitu prvků v závislosti na velikosti jejich normy.
|
|
|
Modules over string algebras
Löwit, Jakub ; Šťovíček, Jan (vedoucí práce) ; Žemlička, Jan (oponent)
Cı́lem této práce je prozkoumat kategorie modulůnad takzvanými řetězcovými algebrami. Přitom se předevšı́m budeme soustředit na porozuměnı́ kotorznı́m párům v těchto kategoriı́ch, jejichž pochopenı́ se redukuje na určenı́ direktnı́ch rozkladů extenzı́ mezi moduly nad danou algebrou. V přı́padě těch řetězcových algeber, jejichž toulec je pouze orientovaný strom, se nám skutečně povede popsat jisté třı́dy dané těmito kotorznı́mi páry, a to pouze pomocı́čistě kombinatorických uzávěrových vlastnostı́. Pro obecné řetězcové algebry se odpovı́dajı́cı́ kombina- torika zdá být poměrně podobná, ačkoli mnohem techničtějšı́.
|
|
|
Problém LWE a bezpečnost schémat pro výměnu klíče
Václavek, Jan ; Příhoda, Pavel (vedoucí práce) ; Žemlička, Jan (oponent)
Hrozba silného kvantového počítače vede ke snaze založit kryptosystémy na problémech, které budou těžké i pro kvantový počítač. V této práci si předsta- víme problém LWE, o kterém se předpokládá, že by takovým problémem mohl být. Nejprve si představíme mříže, které s problémem LWE úzce souvisí. Zave- deme základní pojmy, popíšeme mřížové problémy a vyřešíme cvičení týkající se pokrývajícího poloměru mříže. Poté definujeme problém LWE, představíme jeho varianty a ukážeme redukce dvou mřížových problémů na vhodnou variantu pro- blému LWE. K tomuto účelu definujeme pojem statistické vzdálenosti a dokážeme o něm tvrzení, která potřebujeme pro redukci. Nakonec ukážeme konkrétní vyu- žití problému LWE. Popíšeme schéma na výměnu klíče a naznačíme, jak dokázat jeho bezpečnost za předpokladu, že problém LWE je těžký. 1
|
|
|
Důkazy bezpečností hashovacích funkcí
Zpěváček, Marek ; Příhoda, Pavel (vedoucí práce) ; Žemlička, Jan (oponent)
Tato práce se zaměřuje na důkaz redukce přibližného SBP na SIS. Důkaz provedl již Miklós Ajtai v roce 1996 ve své přelomové práci, avšak jeho důkaz je místy často nejasný a některé kroky nejsou dostatečně rozepsány. Redukce je typu nejhorší případ převeden na průměrný případ. Před zmíněnou prací Ajtaie nebyla známa žádná redukce takového typu. Proto nám přijde vhodné se k důkazu vrátit a rozepsat všechny jeho kroky do většího detailu. Dále je v práci shrnuta složitost základních problémů na mřížkách. Na základě těchto složitostí a dokázané redukce je možné definovat hashovací funkce odolné vůči kolizím. Na takové funkce se tato práce také zběžně zaměřuje. 1
|
|
|
Max okruhy
Beneš, Daniel ; Žemlička, Jan (vedoucí práce) ; Šaroch, Jan (oponent)
V této práci se zabýváme max okruhy, což jsou okruhy, u kterých každý mo- dul má maximální podmodul. Nejprve dokazujeme charakterizaci komutativních okruhů jako okruhů s T-nilpotentním Jacobsonovým radikálem a von Neuman- novsky regulárním faktorem podle Jacobsonova radikálu. Dále se zaměřujeme na grupové okruhy, kde popíšeme všechny komutativní gruové max okruhy. To jsou právě ty grupové okruhy, které jsou složeny z komutativního max okruhu a torzní abelovské grupy obsahující jen konečně mnoho prvků řádu pn takového, že p není invertibilní jako prvek okruhu. Nakonec využijeme této charakterizace ke kon- strukci nekomutativních grupových okruhů, které jsou max, ale nejsou perfektní.
|
|
|
Algorithms for the computation of Galois groups
Kubát, David ; Žemlička, Jan (vedoucí práce) ; Růžička, Pavel (oponent)
Tato práce se zabývá algoritmy pro výpočet Galoisovy grupy nad racionálnímy čísly. Jako první je představen klasický algoritmus R. Stauduhara. Pozornost je poté věnována výkladu teorie nutné pro vysvětlení modulárního algoritmu K. Yokoyamy. Definujeme pojem univerzálního rozkladového okruhu polynomu. Pro separabilní polynom studujeme idempotenty tohoto okruhu. Práce zahrnuje příklady pro polynomy stupně 3 a 4.
|
host ::
RSS.