|
|
On a matrix approach for constructing quadratic almost perfect nonlinear functions
Rezková, Zuzana ; Göloglu, Faruk (vedoucí práce) ; Žemlička, Jan (oponent)
Hledání nových APN funkcí je v symetrické kryptografii důležitým tématem. V roce 2014 popsali Y. Yu, M. Wang a Y. Li maticový přístup ke konstrukci kvadratických APN funkcí. Tento přístup využívá jednoznačné korespondence mezi kvadratickými homogen- ními APN funkcemi a kvadratickými APN maticemi. Cílem této práce je představit matice používáné v původním článku a ukázat, že podobné matice se dají zkonstruovat přímo z algebraické normální formy dané APN funkce. Ve druhé kapitole vysvětlíme původní metodu a pro snazší pochopení přidáme některá trvzení a kroky důkazů. Ve třetí kapitole definujeme matice získané čistě z algebraické normální formy dané funkce. Ve čtvrté kapitole spočítáme matice pro konkrétní APN funkce a ukážeme, jak spolu souvisí. 1
|
|
|
A Library for Binary Decision Diagrams
Paulovčák, Martin ; Holík, Lukáš (oponent) ; Lengál, Ondřej (vedoucí práce)
The aim of this thesis is to create an easy-to-use library that will provide the basic means for Boolean function manipulation based on six different variants of Binary Decision Diagrams - BDD, ZDD, CBDD, CZDD, TBDD, and ESRBDD. The library is implemented in the ISO C programming language, uses closed hashing, index-based node referencing, mark and sweep based garbage collector and diagram construction is based on classical depth-first traversal. The implemented variants of these diagrams were compared on benchmarks and although the optimal choice of decision diagram variant depends on given problem, in general TBDD proved to be the best choice in terms of the resulting graph size and also CPU time.
|
|
|
Vlastnosti intervalových booleovských funkcí
Hušek, Radek ; Čepek, Ondřej (vedoucí práce)
Tato práce řeší problém rozpoznávání k-intervalových boolovských funkcí. Na vstup bo- olovské funkce můžeme nahlížet jako na binární zápis přirozeného čísla. Funkce je k- intervalová, pokud - při takto interpretovaném vstupu - nabývá hodnoty jedna právě pro vstupy z daných nejvýše k intervalů. Tento problém je pro obecné boolovské funkce zadané DNF coNP-těžký. Proto se zabýváme případem, kdy DNF náleží do dané řešitelné třídy (třída je řešitelná, pokud pro DNF z ní umíme řešit falsifikovatelnost v polynomiál- ním čase a je uzavřená na částečná dosazení), a ukazujeme, že v tomto případě je úloha pro pevné k řešitelná v polynomiálním čase. 1
|
|
|
Graph communication protocols
Folwarczný, Lukáš ; Pudlák, Pavel (vedoucí práce) ; Sgall, Jiří (oponent)
Grafové komunikační protokoly jsou zobecněním klasických komunikačních protokolů na případ, kdy je grafem protokolu orientovaný acyklický graf. Motivováni možnými aplikacemi v důkazové složitosti studujeme varianty grafových komunikačních protokolů a vztahy mezi nimi. Hlavním výsledkem je porovnání síly dvou typů protokolů, protokolů s rovností a protokolů s konjunkcí konstantního počtu nerovností. Dokazujeme, že protokoly prvního typu jsou alespoň tak silné jako protokoly druhého typu v následujícím smyslu: Necht' f je booleovská funkce. Pokud existuje protokol s konjunkcí konstantního počtu nerovností polynomiální velikosti řešící f, pak existuje protokol s rovností polynomiální velikosti řešící f. Rovněž zavádíme dva nové typy grafových komunikačních protokolů, protokoly s disjunktností a protokoly s nedisjunktností, a dokazujeme, že protokoly prvního typu jsou alespoň tak silné jako doposud uvažované protokoly a že protokoly druhého typu jsou příliš silné na to, aby mohly být aplikovány.
|
|
|
Boolean methods in knowledge compilation
Kaleyski, Nikolay Stoyanov ; Čepek, Ondřej (vedoucí práce) ; Gregor, Petr (oponent)
V rámci práce je vyřešen otevřený problém o relativní úspornosti jazyků PI a MODS. Ukazuje se, že PI není alespoň tak úsporný jako MODS tím, že se konstruuje třída Booleovských funkcí s počtem primárních implikantů který je superpolynomiální vzhledem k počtu nulových bodů zkonstruovaných funkcí. Odvozuje se dolní mez (čím se dokazuje, že PI není alespoň tak úsporný jako MODS), horní mez (která ukazuje, že zkonstruovaný protipříklad nemůže poskytnout exponenciální separaci PI a MODS) a vzorec pro přesný počet primárních implikantů zkonstruovaných funkcí. Powered by TCPDF (www.tcpdf.org)
|
|
|
Vlastnosti intervalových booleovských funkcí
Hušek, Radek ; Čepek, Ondřej (vedoucí práce) ; Kučera, Petr (oponent)
Tato práce řeší problém rozpoznávání k-intervalových boolovských funkcí. Na vstup bo- olovské funkce můžeme nahlížet jako na binární zápis přirozeného čísla. Funkce je k- intervalová, pokud - při takto interpretovaném vstupu - nabývá hodnoty jedna právě pro vstupy z daných nejvýše k intervalů. Tento problém je pro obecné boolovské funkce zadané DNF coNP-těžký. Proto se zabýváme případem, kdy DNF náleží do dané řešitelné třídy (třída je řešitelná, pokud pro DNF z ní umíme řešit falsifikovatelnost v polynomiál- ním čase a je uzavřená na částečná dosazení), a ukazujeme, že v tomto případě je úloha pro pevné k řešitelná v polynomiálním čase. 1
|
|
|
Special Classes of Boolean Functions with Respect to the Complexity of their Minimization.
Gurský, Štefan ; Čepek, Ondřej (vedoucí práce) ; Marquis, Pierre (oponent) ; Janota, Mikoláš (oponent)
V práci zkoumáme boolovské funkce ze tří různých hledisek. Zaprvé zkoumáme zložitost minimalizace formulí z několika tříd s polynomiálně řešitelným SATem a uvádíme postačující podmínky pro třídy CNF aby se jejich minimalizace přesunula níž alespoň o jeden stupeň v polynomiální hierarchii. Zadruhé zk- oumáme třídu formulí zvaných matched (párované) pro které je SAT triviální, ale minimalizace zůstává Σp 2 úplná. Dokazujeme, že pro každou párovanou CNF existuje alespoň jedna primární a iredundantní CNF s ní ekvivalentní, která je také párovaná. Použitím tohoto tvrzení ukazujeme hlavní výsledek této části a to, že pro každou párovanou CNF všechny s ní ekvivalentní CNF mající minimální možný počet klauzulí jsou taky párované. Zatřetí se věnujeme vlastnosti propagation completeness (úplnosti pro propagaci) - CNF je úplná pro propagaci, pokud pro každé částečné dosazení jsou všechny vynucené literály odvoditelné jednotkovou propagací. Každá CNF sa dá rozšířit na úplnou pro propagaci přidáváním empowering (zesilujících) imp- likátů. Hlavním výsledkem této části je důkaz coNP úplnosti rozpoznávání formulí úplných pro propagaci. Dále ukazujeme, že existují formule, ke kterým je nutno přidat exponenciálně mnoho zesilujících implikátů, aby se staly úplnými pro propagaci.
|
|
|
Knihovna pro binární rozhodovací diagramy
Janků, Petr ; Hrubý, Martin (oponent) ; Holík, Lukáš (vedoucí práce)
Efektivní manipulace Booleovských funkcí je důležitou součástí mnoha počítačových návrhů. Jako datová struktura pro reprezentaci a manipulaci s Booleovskými funkcemi se běžně používají binární rozhodovací diagramy. Tyto diagramy se běžně používají v mnoha odvětvích, jako je například ověřování modelů, verifikace systému, návrh obvodů apod. V této práci jsou popsány tyto diagramy a jsou zde uvedeny i jejich modifikace. Dále jsou v této práci uvedeny a popsány techniky pro efektivní manipulaci a reprezentaci binárních rozhodovacích diagramů. Mimoto tato práce popisuje návrh a implementaci knihovny, která bude s těmito diagramy pracovat. Dále je diskutována potenciální aplikace vyvinuté knihovny v knihovně VATA pro manipulaci se stromovými automaty. Na závěr je tato knihovna porovnána s dobře známou a silně optimalizovanou knihovnou CUDD, která je volně dostupná a s knihovnou CacBDD. Výsledky experimentů ukázaly, že navrhovaná knihovna je poměrně blízká CUDD a CacBDD (dosahuje srovnatelného a většinou i lehce lepšího výkonu).
|
|
| |
|
|
Representations of Boolean Functions by Perceptron Networks
Kůrková, Věra
Limitations of capabilities of shallow perceptron networks are investigated. Lower bounds are derived for growth of numbers of units and sizes of output weights in networks representing Boolean functions of d variables. It is shown that for large d, almost any randomly chosen Boolean function cannot be tractably represented by shallow perceptron networks, i.e., each its representation requires a network with number of units or sizes of output weights depending on d exponentially
|
host ::
RSS.