Název: Minimální reprezentace víceintervalových booleovských funkcí
Překlad názvu: Minimální reprezentace víceintervalových booleovských funkcí
Autoři: Bártek, Filip ; Kučera, Petr (vedoucí práce) ; Gregor, Petr (oponent)
Typ dokumentu: Diplomové práce
Rok: 2015
Jazyk: eng
Abstrakt: [eng] [cze]
When we interpret the input vector of a Boolean function as a binary number, we define interval Boolean function fn [a,b] so that fn [a,b](x) = 1 if and only if a ≤ x ≤ b. Disjunctive normal form is a common way of representing Boolean functions. Minimization of DNF representation of an interval Boolean function can be per- formed in linear time. The natural generalization to k-interval functions seems to be significantly harder to tackle. In this thesis, we discuss the difficulties with finding an optimal solution and introduce a 2k-approximation algorithm. Pokud interpretujeme vstupní vektory booleovské funkce jako binárně zapsaná čísla, intervalovou booleovskou funkci fn [a,b] definujeme tak, že fn [a,b](x) = 1 právě tehdy když a ≤ x ≤ b. Disjunktivní normální forma je jeden z běžných způsobů reprezentace booleovských funkcí. Minimalizaci DNF reprezentace 1-intervalové booleovské funkce zadané okrajovými hodnotami intervalu lze provést v lineárním čase. Zobecnění na k-intervalové funkce se zdá být složitější. V této diplo- mové práci diskutujeme komplikace s hledáním optimální DNF reprezentace k- intervalové funkce a představíme 2k-aproximační algoritmus pro tento problém.
Klíčová slova: Booleovská minimalizace; disjunktivně normální forma; intervalové funkce; Boolean minimization; disjunctive normal form; interval functions

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/62638

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


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