Minimální reprezentace víceintervalových booleovských funkcí
| Název práce v češtině: | Minimální reprezentace víceintervalových booleovských funkcí |
|---|---|
| Název v anglickém jazyce: | Minimum representations of Boolean functions defined by multiple intervals |
| Klíčová slova: | Booleovská minimalizace, disjunktivně normální forma, intervalové funkce. |
| Klíčová slova anglicky: | Boolean minimization, disjunctive normal form, interval functions. |
| Akademický rok vypsání: | 2014/2015 |
| Typ práce: | diplomová práce |
| Jazyk práce: | angličtina |
| Ústav: | Katedra teoretické informatiky a matematické logiky (32-KTIML) |
| Vedoucí / školitel: | RNDr. Petr Kučera, Ph.D. |
| Řešitel: | Mgr. Filip Bártek - zadáno a potvrzeno stud. odd. |
| Datum přihlášení: | 24.03.2015 |
| Datum zadání: | 24.03.2015 |
| Datum potvrzení stud. oddělením: | 14.04.2015 |
| Datum a čas obhajoby: | 04.06.2015 11:00 |
| Datum odevzdání elektronické podoby: | 07.05.2015 |
| Datum odevzdání tištěné podoby: | 07.05.2015 |
| Datum proběhlé obhajoby: | 04.06.2015 |
| Oponenti: | doc. Mgr. Petr Gregor, Ph.D. |
| Zásady pro vypracování |
| Intervalové funkce byly zavedeny v (Schieber et al., 2005). O booleovské funkci f na n proměnných řekneme, že je intervalová, pokud existují dvě čísla 0≤a≤b≤2^n, pro které platí, že f je splněna právě na ohodnoceních v, která splňují a≤v≤b, uvažujeme-li v jako binární reprezentaci n-bitového čísla. Autoři (Schieber et al., 2005) popsali algoritmus pro konstrukci minimální disjunktivně normální formy (DNF) reprezentující intervalovou funkci. Cílem diplomanta je prozkoumat, jak by bylo možno postupy uvedené v (Schieber et al., 2005) zobecnit pro případ funkcí definovovaných více intervaly. Výsledkem mohou být jak optimalizační algoritmy, tak i algoritmy aproximační. Diplomová práce svým způsobem navazuje na diplomovou práci J. Dubovského (Konstrukce minimálních DNF reprezentací 2-intervalových funkcí, ak. rok 2011/12), v níž byly studovány podtřídy 2-intervalových funkcí. |
| Seznam odborné literatury |
| [1] Y. Crama, P.L. Hammer. Boolean Functions: Theory, Algorithms, and Applications, Cambridge University Press, 2011.
[2] B. Schieber, D. Geist, A. Zaks. Computing the minimum DNF representations of boolean functions defined by intervals, Discrete Applied Mathematics 149, 2005, pp. 154-173. [3] J. Dubovský. Konstrukce minimálních DNF reprezentací 2-intervalových funkcí. Diplomová práce na MFF, akademický rok 2011/12. |