|
|
Binární ekvivalenční slova
Hadravová, Jana ; Holub, Štěpán (vedoucí práce) ; Stanovský, David (oponent)
Binární ekvivalenční jazyk pro homomorfismy g, h je množina všech řešení rovnice g (w) = h(w). Je dokázáno, že tato množina je generována maximálně dvěma slovy. Struktura binárního ekvivalečního jazyka je známa v případě, že alespoň jeden z homomorfismů je periodický, nebo pokud je množina řešení generována právě dvěma slovy. Cílem této práce bylo najít strukturu množiny řešení i pro případ, že je tato množina generována pouze jedním slovem. Problém sice zůstává nedořešen, byly však získány speciální výsledky pro bezbloková řešení (tj. řešení, která se skládají pouze z jednoho bloku) markovaných homomorfismů. Metody zavedené v této práci (pokrývání stejnými vzory pro nalezení n-násobného p-převisu a práce se z-kunjogovanou dvojicí (e, f, z))) jsou natolik univerzální, že je lze použít při dalším zkoumání tohoto problému a v krátké době dosáhnout dalších výsledků.
|
|
| |
|
| |
|
|
Searching collisions in hash functions
Joščák, Daniel ; Tůma, Jiří (vedoucí práce) ; Holub, Štěpán (oponent)
Hlavním obsahem této práce je hledání kolizí v hašovací funkci MD5. Představíme náš nový algoritmus založený na metodě hledání kolizí podle Wangové a kol. V průběhu psaní této práce Stevens a Klíma publikovali dva nové algoritmy na hledání kolizí v této funkci. Přineseme popis všech tří algoritmů a také jejich výpočetní složitost.
|
|
| |
|
| |
|
| |
|
|
Kódování a efektivita LDPC kódů
Kozlík, Andrew ; Drápal, Aleš (vedoucí práce) ; Holub, Štěpán (oponent)
LDPC kódy jsou lineární samoopravné kódy, které jednak umožňují přenos dat rychlostí libovolně blízkou kapacitě kanálu, a zároveň pro ně existují vysoce účinné dekódovací algoritmy. Naproti tomu hlavní nevýhodou většiny LDPC kódů je vysoká časová náročnost jejich kódovacího algoritmu. V této práci se nejdříve věnujeme podrobnému rozboru tzv. sum-product dekódovacího algoritmu. Následně zkoumáme výkonnost LDPC kódů na binárním vymazávacím kanálu za použití sum-product algoritmu, čímž získáme kritéria pro design kódů, které umožňují spolehlivý přenos dat rychlostí libovolně blízkou kapacitě kanálu. Na základě těchto kritérií ukážeme, jak probíhá design takovýchto kódů. Poté prezentujeme experimentálně získané výsledky a srovnáváme je s teoretickými odhady. Na závěr poskytneme přehled několika způsobů, kterými lze řešit problém vysoké časové náročnosti kódování.
|
|
|
Algoritmus pro kvantové hledání
Mejdrech, Lukáš ; Barto, Libor (vedoucí práce) ; Holub, Štěpán (oponent)
V předložené práci studujeme Groverův algoritmus, který slibuje na kvantovém počítači vyhledávat v nesetříděné databázi v čase uměrné odmocnině z počtu položek. Po popsaní základních principů kvantových počítačů je uvedena jak původní Groverova formulace a důkaz algoritmu, tak i pozdější geometrický popis tohoto algoritmu. Také je poukázáno na vhodnost těchto popisů k výukovým učelům. Nakonec je zahrnut popis Groverova algoritmu v programovacím jazyce umožňujícím simulovat na klasických počítačích kvantové výpočty.
|
|
| |
host ::
RSS.