|
|
Abstraction in Automata Algorithms
Kocourek, Tomáš ; Lengál, Ondřej (oponent) ; Holík, Lukáš (vedoucí práce)
The goal of this thesis is to implement and experimentally compare antichain-based algorithms with and without abstraction, which decide the emptiness of alternating finite automata. The author also proposes his own algorithms using abstraction and comes up with a few optimizations of existing abstract algorithms. The thesis introduces the theoretical background of studied algorithms and describes efficient ways to implement data structures which are used by these algorithms. The experimental evaluation over random automata shows that the algorithms without abstraction give us better results in general because they do not perform costly evaluation of closed set intersection and complementation. However, in case of automata with high transition density, the algorithms without abstraction tend to decelerate, while the abstract ones accelerate.
|
|
| |
|
|
Abstraction in Automata Algorithms
Kocourek, Tomáš ; Lengál, Ondřej (oponent) ; Holík, Lukáš (vedoucí práce)
The goal of this thesis is to implement and experimentally compare antichain-based algorithms with and without abstraction, which decide the emptiness of alternating finite automata. The author also proposes his own algorithms using abstraction and comes up with a few optimizations of existing abstract algorithms. The thesis introduces the theoretical background of studied algorithms and describes efficient ways to implement data structures which are used by these algorithms. The experimental evaluation over random automata shows that the algorithms without abstraction give us better results in general because they do not perform costly evaluation of closed set intersection and complementation. However, in case of automata with high transition density, the algorithms without abstraction tend to decelerate, while the abstract ones accelerate.
|
|
|
Algoritmus pro pevné body homomorfismů na slovech
Matocha, Vojtěch ; Holub, Štěpán (vedoucí práce) ; Žemlička, Jan (oponent)
V předložené práci studuji polynomiální algoritmus, který pro dané slovo rozhoduje, zda je pevným bodem nějakého netriviálního homomorfismu. Součástí práce je zpřesněný odhad složitosti, algoritmus v nejhorším případě pracuje v čase O(m · n), kde n značí délku slova a m velikost použité abecedy. V práci se dále zabývám problémem union-find, který je stěžejní součástí popisovaného algoritmu, a s odhadem jeho složitosti související Ackermannovou funkcí. V práci jsou shrnuty používané metody a důkazy jejich složitostí a je popsán postup, kterým lze řešit speciální případ union-find vyskytující se ve zkoumaném algoritmu. Následuje konkrétní implementace algoritmu, jejíž testovaná složitost odpovídá zpřesněnému odhadu. Součástí práce je také vizualizace chodu algoritmu na konkrétních vstupech.
|
|
|
Aritmetická úplnost logiky R
Holík, Lukáš ; Švejdar, Vítězslav (vedoucí práce) ; Bílková, Marta (oponent)
Cílem práce bylo s použitím novodobé notace vystavět teorii Rosserovy logiky, vysvětlit do detailu její vztah s Peanovou aritmetikou, ukázat kripkovskou sémantiku a nakonec pomocí autoreference v množném čísle zpracovat důkaz aritmetické úplnosti. V poslední kapitole se pak ukazují některé z vlastností rosserovských sentencí. Powered by TCPDF (www.tcpdf.org)
|
|
|
Komutující spojité funkce bez společného pevného bodu
Karasová, Klára ; Vejnar, Benjamin (vedoucí práce) ; Cúth, Marek (oponent)
Tématem práce jsou společné pevné body komutujících funkcí. Pomocí Mountain climbing theorem dokážeme větu o rozšiřování komutujících funkcí, která nám umožní zkonstruovat komutující funkce intervalu [0, 1] na sebe, které nemají společný pevný bod. Dále jsou dokázány různé verze věty o rozšiřování komutujících funkcí pomocí růz- ných verzí Mountain climbing theorem. Také dokážeme, že je-li X dendroid, S abelovská semigrupa monotónních zobrazení na X a f : X → X komutuje se všemi prvky S, pak f a S mají společný pevný bod. 1
|
|
|
Fixed point theorems in the theory of differential equations
Zelina, Michael ; Pražák, Dalibor (vedoucí práce) ; Bárta, Tomáš (oponent)
Tato diplomová práce si klade za cíl demonstrovat řadu aplikací vět o pevných bodech v problematice diferenciálních rovnic. Na začátku uvedeme pojem topolog- ického stupně pomocí něhož dospějeme k několika větám o pevných bodech, především jde o větu Brouwerovu, Schauderovu a Kakutani-Ky Fanovu. Tyto poté užijeme na širší spektrum v zásadě jednoduchých úloh z obyčejných a parciálních diferenciálních rovnic. Nakonec se tyto věty pokusíme aplikovat na pár složitějších problémů. První je záležitost existence řešení pro model popisující mechanický oscilátor s nemonotónní závislostí na výchylce i rychlosti. Dále se jedná o řešení takzvaného Gauseho modelu dravec-kořist se skrýší. Na závěr budeme zkoumat jednu parciální diferenciální rovnici s vazbou, která nás dovede k maximálnímu monotónnímu grafu. 1
|
|
|
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
|
|
|
Aritmetická úplnost logiky R
Holík, Lukáš ; Švejdar, Vítězslav (vedoucí práce) ; Bílková, Marta (oponent)
Cílem práce bylo s použitím novodobé notace vystavět teorii Rosserovy logiky, vysvětlit do detailu její vztah s Peanovou aritmetikou, ukázat kripkovskou sémantiku a nakonec pomocí autoreference v množném čísle zpracovat důkaz aritmetické úplnosti. V poslední kapitole se pak ukazují některé z vlastností rosserovských sentencí. Powered by TCPDF (www.tcpdf.org)
|
|
|
Analysis of the CubeHash proposal
Stankovianska, Veronika ; Tůma, Jiří (vedoucí práce) ; Hojsík, Michal (oponent)
Předkládaná práce se zabývá analýzou návrhu hašovací funkce CubeHash a zvláštní důraz klade na následující články: "Inside the Hyper- cube" [1], "Symmetric States and Their Improved Structure" [7] a "Lineari- sation Framework for Collision Attacks" [6]. Krátce představuje algoritmus hašovací funkce CubeHash a dokazuje, že její rundovní funkce R : ({0, 1}32 )32 → ({0, 1}32 )32 je permutací. Výsledky uváděné v článcích [1] a [7], týkající se symetrických stavů pro CubeHash, jsou posouzené, opravené a doložené důkazy. Přesněji, pomocí definice D-symetrického stavu, založené na [7], práce dokazuje, že pro vektorový prostor V = Z4 2 a jeho lineární podpros- tor D existuje 22 |V | |D| D-symetrických stavů a vnitřní stav x je D-symetrický právě tehdy, když stav R(x) je D-symetrický. V reakci na [1] diplomová práce uvádí úplný výpočet dolní meze pro počet symetrických stavů, vysvětluje, proč vylepšené hledání prvního vzoru nefunguje tak, jak je představeno, a v neposlední řadě objasňuje matematické pozadí hledání pevných bodů rundovní funce R. Následně poukazuje na skutečnost, že linearizační metoda z [6] neuvažuje rovnici (A ⊕ α) + β = (A + β) ⊕ α (∗), která se v algo- ritmu CubeHash vyskytuje během...
|
host ::
RSS.