Název: Vlastnosti intervalových booleovských funkcí
Překlad názvu: Properties of interval Boolean functions
Autoři: Hušek, Radek ; Čepek, Ondřej (vedoucí práce) ; Kučera, Petr (oponent)
Typ dokumentu: Diplomové práce
Rok: 2014
Jazyk: cze
Abstrakt: [cze] [eng]
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 Boolean function f is k-interval if - input vector viewed as n-bit number - f is true for and only for inputs from given (at most) k intervals. Recognition of k-interval fuction given its DNF representation is coNP-hard problem. This thesis shows that for DNFs from a given solvable class (class C of DNFs is solvable if we can for any DNF F ∈ C decide F ≡ 1 in polynomial time and C is closed under partial assignment) and fixed k we can decide whether F represents k-interval function in polynomial time. 1
Klíčová slova: booleovské funkce; intervalové funkce; polynomiální algoritmy; Boolean functions; interval functions; polynomial time algorithms

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/72078

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-341200


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Diplomové práce