velikost textu

Minimální reprezentace víceintervalových booleovských funkcí

Upozornění: Informace získané z popisných dat či souborů uložených v Repozitáři závěrečných prací nemohou být použity k výdělečným účelům nebo vydávány za studijní, vědeckou nebo jinou tvůrčí činnost jiné osoby než autora.
Název:
Minimální reprezentace víceintervalových booleovských funkcí
Název v angličtině:
Minimum representations of Boolean functions defined by multiple intervals
Typ:
Diplomová práce
Autor:
Mgr. Filip Bártek
Vedoucí:
RNDr. Petr Kučera, Ph.D.
Oponent:
Mgr. Petr Gregor, Ph.D.
Id práce:
163753
Fakulta:
Matematicko-fyzikální fakulta (MFF)
Pracoviště:
Katedra teoretické informatiky a matematické logiky (32-KTIML)
Program studia:
Informatika (N1801)
Obor studia:
Teoretická informatika (ITI)
Přidělovaný titul:
Mgr.
Datum obhajoby:
4. 6. 2015
Výsledek obhajoby:
výborně
Jazyk práce:
Angličtina
Klíčová slova:
Booleovská minimalizace, disjunktivně normální forma, intervalové funkce.
Klíčová slova v angličtině:
Boolean minimization, disjunctive normal form, interval functions.
Abstrakt:
Pokud interpretujeme vstupní vektory booleovské funkce jako binárně zapsaná n n čísla, intervalovou booleovskou funkci f[a,b] definujeme tak, že f[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.
Abstract v angličtině:
When we interpret the input vector of a Boolean function as a binary number, we n n define interval Boolean function f[a,b] so that f[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.
Dokumenty
Stáhnout Dokument Autor Typ Velikost
Stáhnout Text práce Mgr. Filip Bártek 535 kB
Stáhnout Abstrakt v českém jazyce Mgr. Filip Bártek 49 kB
Stáhnout Abstrakt anglicky Mgr. Filip Bártek 50 kB
Stáhnout Posudek vedoucího RNDr. Petr Kučera, Ph.D. 93 kB
Stáhnout Posudek oponenta Mgr. Petr Gregor, Ph.D. 90 kB
Stáhnout Záznam o průběhu obhajoby prof. RNDr. Roman Barták, Ph.D. 89 kB