text size

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.
Title:
Minimální reprezentace víceintervalových booleovských funkcí
Titile (in english):
Minimum representations of Boolean functions defined by multiple intervals
Type:
Diploma thesis
Author:
Mgr. Filip Bártek
Supervisor:
RNDr. Petr Kučera, Ph.D.
Opponent:
Mgr. Petr Gregor, Ph.D.
Thesis Id:
163753
Faculty:
Faculty of Mathematics and Physics (MFF)
Department:
Department of Theoretical Computer Science and Mathematical Logic (32-KTIML)
Study programm:
Informatics (N1801)
Study branch:
Theoretical Computer Science (ITI)
Degree granted:
Mgr.
Defence date:
04/06/2015
Defence result:
excellent
Language:
English
Keywords (in czech):
Booleovská minimalizace, disjunktivně normální forma, intervalové funkce.
Keywords:
Boolean minimization, disjunctive normal form, interval functions.
Abstract (in czech):
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:
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.
Documents
Download Document Author Type File size
Download Text of the thesis Mgr. Filip Bártek 535 kB
Download Abstract in czech Mgr. Filip Bártek 49 kB
Download Abstract in english Mgr. Filip Bártek 50 kB
Download Supervisor's review RNDr. Petr Kučera, Ph.D. 93 kB
Download Opponent's review Mgr. Petr Gregor, Ph.D. 90 kB
Download Defence's report prof. RNDr. Roman Barták, Ph.D. 89 kB