|
|
Automaty s ohraničeným počtem čistých zásobníků
Soukup, Ondřej ; Zemek, Petr (oponent) ; Meduna, Alexandr (vedoucí práce)
Zásobníkové automaty s omezeným počtem čistých zásobníků jsou specializací čistých zásobníkových automatů. Jejich síla je zkoumána především z pohledu kombinatoriky na slovech. V jazyku definovaném automatem je zaveden termín závislost, který označuje vztah mezi částmi řetězců jazyka. Je ukázáno, jak postupuje definovaný automat při zpracování závislostí. Dále je odvozen vztah mezi rozložením závislostí v jazyku a nutným počtem zásobníků automatu. Je definována nekonečná hierarchie jazyků korespondujících k automatům v závislosti na počtu jejich zásobníků. Nakonec je zkoumáno zařazení třídy jazyků definované zásobníkovými automaty s omezeným počtem čistých zásobníků do Chomského hierarchie jazyků, ovšem je zjištěno, že s Chomského hierarchií nekorespondují. Na základě výsledku je jako další vývoj navrhováno zkoumání možných úprav modelů. Pro demonstraci vlastností zkoumaných automatů je následně vytvořen simulační program.
|
|
| |
|
|
Čtverce v posloupnostech čísel
Hudcová, Barbora ; Holub, Štěpán (vedoucí práce) ; Bulín, Jakub (oponent)
V této práci vycházíme z článku, kde bylo zkonstruováno první nekonečné slovo nad konečnou abecedou, které se vyhýbá aditivním třetím mocninám. Ukazujeme konstrukce dalších slov se stejnou vlastností. Dále na jednom z těchto slov ilustrujeme hlavní myš- lenku důkazu, že se dané slovo vyhýbá aditivním třetím mocninám. 1
|
|
|
Structure of equality sets
Hadravová, Jana ; Holub, Štěpán (vedoucí práce) ; Currie, James (oponent) ; Masáková, Zuzana (oponent)
Název práce: Struktura ekvivalenčních množin Autor: Jana Hadravová Katedra: Katedra algebry Vedoucí disertační práce: doc. Mgr. Štěpán Holub, Ph.D., Katedra algebry Abstrakt: Binární ekvivaleční množina dvou homomorfismů g, h : ⌃⇤ ! A⇤ je množina všech slov w nad dvouprkovou abecedou ⌃ splňujících rovnost g(w) = h(w). Prvky této množiny se nazývají binární ekvivalenční slova. Jedním z důležitých výsledků v oblasti ekvivalenčních množin je důkaz toho, že množina generátorů libovolné binární ekvivalenční množiny je maximálně dvou- prvková za podmínky, že jsou oba homomorfismy g, h neperiodické. Pokud je navíc tato množina generována přesně dvěma prvky, je struktura těchto ge- nerátorů, a tím i celé množiny, jednoznačně dána. Předložená práce se zabývá výzkumem struktury binárních ekvivalenčních množin s jedním generátorem. Důležitou vlastností těchto generátorů je možnost je- jich rozkladu na jednodušší struktury. Generátory, které již nelze dále rozložit, se nazývají jednoduchá ekvivalenční slova. První část práce se věnuje struk- tuře jednoduchých ekvivalenčních slov a jejich podrobné klasifikaci. Hlavním výsledkem této části je nalezení přesné struktury jednoduchých ekvivalenčních...
|
|
|
Čtverce v posloupnostech čísel
Hudcová, Barbora ; Holub, Štěpán (vedoucí práce) ; Bulín, Jakub (oponent)
V této práci vycházíme z článku, kde bylo zkonstruováno první nekonečné slovo nad konečnou abecedou, které se vyhýbá aditivním třetím mocninám. Ukazujeme konstrukce dalších slov se stejnou vlastností. Dále na jednom z těchto slov ilustrujeme hlavní myš- lenku důkazu, že se dané slovo vyhýbá aditivním třetím mocninám. 1
|
|
|
Structure of equality sets
Hadravová, Jana ; Holub, Štěpán (vedoucí práce) ; Currie, James (oponent) ; Masáková, Zuzana (oponent)
Název práce: Struktura ekvivalenčních množin Autor: Jana Hadravová Katedra: Katedra algebry Vedoucí disertační práce: doc. Mgr. Štěpán Holub, Ph.D., Katedra algebry Abstrakt: Binární ekvivaleční množina dvou homomorfismů g, h : ⌃⇤ ! A⇤ je množina všech slov w nad dvouprkovou abecedou ⌃ splňujících rovnost g(w) = h(w). Prvky této množiny se nazývají binární ekvivalenční slova. Jedním z důležitých výsledků v oblasti ekvivalenčních množin je důkaz toho, že množina generátorů libovolné binární ekvivalenční množiny je maximálně dvou- prvková za podmínky, že jsou oba homomorfismy g, h neperiodické. Pokud je navíc tato množina generována přesně dvěma prvky, je struktura těchto ge- nerátorů, a tím i celé množiny, jednoznačně dána. Předložená práce se zabývá výzkumem struktury binárních ekvivalenčních množin s jedním generátorem. Důležitou vlastností těchto generátorů je možnost je- jich rozkladu na jednodušší struktury. Generátory, které již nelze dále rozložit, se nazývají jednoduchá ekvivalenční slova. První část práce se věnuje struk- tuře jednoduchých ekvivalenčních slov a jejich podrobné klasifikaci. Hlavním výsledkem této části je nalezení přesné struktury jednoduchých ekvivalenčních...
|
|
|
Kvadratické rovnice na slovech
Olšák, Miroslav ; Holub, Štěpán (vedoucí práce) ; Stanovský, David (oponent)
Práce se zabývá řešitelnosti kvadratických rovnic na slovech. V upravené podobě opakuje výsledky Robsona a Diekerta a navazuje na otázku jednoduše exponenciální meze na velikost nejkratšího řešení kvadratických rovnic. Kladná odpověď na tuto otázku by znamenala, že je řešitelnost kvadratických rovnic na slovech NP úplný problém. Hypotézu o jednoduše exponenciální mezi se dokázat nepodařilo, ale podařilo se například zúžit třídu rovnic, kterým je třeba se věnovat, a dále ukázat, že se stačí zabývat mezí pro nejkratší proměnnou. V závěru práce je ukázáno chování jisté konkrétní rovnice a dále vysvětlena dualita dvou přístupů ke kvadratickým soustavám. Powered by TCPDF (www.tcpdf.org)
|
|
| |
|
|
Kombinatorika hashovacích funkcí
Sýkora, Jiří ; Holub, Štěpán (vedoucí práce) ; Šaroch, Jan (oponent)
V této práci se zabýváme hašovacími funkcemi. Soustředíme se především na známou Merkle-Damg˚ardovu konstrukci a její zobecnění. Ukazujeme, že ani tato zobecněná kon- strukce není odolná proti útokům hledajícím multikolize. Zásadní roli při tvorbě našeho útoku hraje kombinatorika na slovech. Ukazuje se totiž, že v dostatečně dlouhých slovech s omezeným počtem výskytů jednotlivých symbolů se nutně musí objevovat určité pra- videlnosti. V této oblasti předvádíme vlastní původní výsledky, kterými zlepšujeme dříve publikované odhady, čímž snižujeme složitost útoku. Z toho plyne, že zobecněné hašovací funkce jsou zajímavé spíše z teoretického než praktického hlediska. 1
|
|
|
Automaty s ohraničeným počtem čistých zásobníků
Soukup, Ondřej ; Zemek, Petr (oponent) ; Meduna, Alexandr (vedoucí práce)
Zásobníkové automaty s omezeným počtem čistých zásobníků jsou specializací čistých zásobníkových automatů. Jejich síla je zkoumána především z pohledu kombinatoriky na slovech. V jazyku definovaném automatem je zaveden termín závislost, který označuje vztah mezi částmi řetězců jazyka. Je ukázáno, jak postupuje definovaný automat při zpracování závislostí. Dále je odvozen vztah mezi rozložením závislostí v jazyku a nutným počtem zásobníků automatu. Je definována nekonečná hierarchie jazyků korespondujících k automatům v závislosti na počtu jejich zásobníků. Nakonec je zkoumáno zařazení třídy jazyků definované zásobníkovými automaty s omezeným počtem čistých zásobníků do Chomského hierarchie jazyků, ovšem je zjištěno, že s Chomského hierarchií nekorespondují. Na základě výsledku je jako další vývoj navrhováno zkoumání možných úprav modelů. Pro demonstraci vlastností zkoumaných automatů je následně vytvořen simulační program.
|
host ::
RSS.