|
|
Knihovna pro boolovské funkce v algebraické normální formě
Vasilišin, Maroš ; Mrázek, Vojtěch (oponent) ; Dobai, Roland (vedoucí práce)
Táto bakalárska práca sa zaoberá návrhom a implementáciou knižnice v jazyku C pre manipuláciu Boolovych funkcií v Algebraickej Normálnej Forme. Väčšina existujúcich reprezentácií Boolovych funkcií je založená na binárnych rozhodovacích diagramoch. Algebraická Normálna Forma poskytuje oproti binárnym rozhodovacím diagramom určité výhody, napríklad tú, že sa dá z nej v lineárnom čase určiť Boolova hodnota funkcie. Implementovaná knižnica za pomoci jednoduchých štruktúr poskytuje efektívnu reprezentáciu Boolovej funkcie v programe. Výskumom sme zistili, že reprezentácia pomocou Algebraickej Normálnej Formy má svoj využitie, a v určitých prípadoch dosahuje lepšie výsledky ako reprezentácia pomocou binárnych rozhodovacích diagramov.
|
|
|
Konstrukce minimálních DNF reprezentací 2-intervalových funkcí.
Dubovský, Jakub ; Čepek, Ondřej (vedoucí práce) ; Kučera, Petr (oponent)
Název práce: Konstrukce minimálních DNF reprezentací 2-intervalových funkcí Autor: Jakub Dubovský Katedra: Katedra teoretické informatiky a matematické logiky Vedoucí diplomové práce: doc.RNDr.Ondřej Čepek, Ph.D. Abstrakt: Tato práce se věnuje intervalovým boolovským funkcím. Je zaměřena na konstrukci jejich reprezentací pomocí disjunktivních normálních forem s co nej- menším počtem termů. Shrnuje známé výsledky v této oblasti pro 1-intervalové funkce. Ukazuje, že používanou metodu důkazu nelze obecně použít pro dva a více intervalové funkce. Pokouší se rozšířit tyto poznatky na 2-intervalové funkce. Je navrhnut optimalizační algoritmus pro speciální podtřídu 2-intervalových funkcí. Dokazuje se přesný odhad chyby pro jednoduchý aproximační algoritmus. Sou- částí práce je softwerová utilita pro experimentování s intervalovými funkcemi. Klíčová slova: boolovská funkce, intervalová funkce, konstrukce reprezentace, aproximace 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
|
|
|
APN functions with non-classical Walsh spectra
Maršálek, Michal ; Göloglu, Faruk (vedoucí práce) ; Drápal, Aleš (oponent)
Zajímavá třída Booleovských funkcí jsou APN funkce - tyto funkce jsou "co možná nejdále" od lineárních funkcí. Většina kvadratických APN funkcí má stejné (=klasické) Walshovo spektrum - jakýsi otisk funkce. Cílem této práce je popsat postup, který může vést k zobecnění příkladu kvadratické APN funkce s neklasickým Walshovým spektrem. Až donedávna se mělo za to, že žádná taková funkce neexistuje. Tato domněnka se ukázala jako nepravdivá, když byl v roce 2009 představen příklad takové funkce v dimenzi 6. V této práci popíšeme konstrukci a odvodíme nutné podmínky pro některé volné koeficienty, abychom zúžili prohledávací prostor natolik, abychom mohli provést prohledání počítačem. 1
|
|
|
Knihovna pro boolovské funkce v algebraické normální formě
Vasilišin, Maroš ; Mrázek, Vojtěch (oponent) ; Dobai, Roland (vedoucí práce)
Táto bakalárska práca sa zaoberá návrhom a implementáciou knižnice v jazyku C pre manipuláciu Boolovych funkcií v Algebraickej Normálnej Forme. Väčšina existujúcich reprezentácií Boolovych funkcií je založená na binárnych rozhodovacích diagramoch. Algebraická Normálna Forma poskytuje oproti binárnym rozhodovacím diagramom určité výhody, napríklad tú, že sa dá z nej v lineárnom čase určiť Boolova hodnota funkcie. Implementovaná knižnica za pomoci jednoduchých štruktúr poskytuje efektívnu reprezentáciu Boolovej funkcie v programe. Výskumom sme zistili, že reprezentácia pomocou Algebraickej Normálnej Formy má svoj využitie, a v určitých prípadoch dosahuje lepšie výsledky ako reprezentácia pomocou binárnych rozhodovacích diagramov.
|
|
|
Kryptografická kriteria pro Booleovské funkce
Luňáčková, Radka ; Hojsík, Michal (vedoucí práce) ; Tůma, Jiří (oponent)
V práci se zabýváme Booleovskými funkcemi. Nejprve studujeme různé reprezentace Booleovských funkcí a přechody mezi jednotlivými reprezen- tacemi. Kromě přirozené reprezentace pravdivostní tabulkou, či vektorem hodnot a často používanou algebraickou normální formou, popisujeme i méně známé re- prezentace polynomem jedné proměnné a stopou. Dále uvádíme základy teorie Booleovských funkcí, jež jsou nezbytné pro studování kryptografických kritérií Booleovských funkcí. V poslední části pak zkoumáme vybrané vlastnosti Boo- leovských funkcí. Vysvětlujeme, jak spolu vlastnosti souvisí a jaké hodnoty jsou pro ně z kryptografického hlediska optimální. Konkrétně popisujeme tato kritéria: algebraický stupeň, nelinearitu, balancovanost, odolnost a korelační imunitu. 1
|
|
|
Konstrukce minimálních DNF reprezentací 2-intervalových funkcí.
Dubovský, Jakub ; Čepek, Ondřej (vedoucí práce) ; Kučera, Petr (oponent)
Název práce: Konstrukce minimálních DNF reprezentací 2-intervalových funkcí Autor: Jakub Dubovský Katedra: Katedra teoretické informatiky a matematické logiky Vedoucí diplomové práce: doc.RNDr.Ondřej Čepek, Ph.D. Abstrakt: Tato práce se věnuje intervalovým boolovským funkcím. Je zaměřena na konstrukci jejich reprezentací pomocí disjunktivních normálních forem s co nej- menším počtem termů. Shrnuje známé výsledky v této oblasti pro 1-intervalové funkce. Ukazuje, že používanou metodu důkazu nelze obecně použít pro dva a více intervalové funkce. Pokouší se rozšířit tyto poznatky na 2-intervalové funkce. Je navrhnut optimalizační algoritmus pro speciální podtřídu 2-intervalových funkcí. Dokazuje se přesný odhad chyby pro jednoduchý aproximační algoritmus. Sou- částí práce je softwerová utilita pro experimentování s intervalovými funkcemi. Klíčová slova: boolovská funkce, intervalová funkce, konstrukce reprezentace, aproximace 1
|
|
| |
host ::
RSS.