Minimální reprezentace víceintervalových booleovských funkcí
| Thesis title in Czech: | Minimální reprezentace víceintervalových booleovských funkcí |
|---|---|
| Thesis title in English: | Minimum representations of Boolean functions defined by multiple intervals |
| Key words: | Booleovská minimalizace, disjunktivně normální forma, intervalové funkce. |
| English key words: | Boolean minimization, disjunctive normal form, interval functions. |
| Academic year of topic announcement: | 2014/2015 |
| Thesis type: | diploma thesis |
| Thesis language: | angličtina |
| Department: | Department of Theoretical Computer Science and Mathematical Logic (32-KTIML) |
| Supervisor: | RNDr. Petr Kučera, Ph.D. |
| Author: | Mgr. Filip Bártek - assigned and confirmed by the Study Dept. |
| Date of registration: | 24.03.2015 |
| Date of assignment: | 24.03.2015 |
| Confirmed by Study dept. on: | 14.04.2015 |
| Date and time of defence: | 04.06.2015 11:00 |
| Date of electronic submission: | 07.05.2015 |
| Date of submission of printed version: | 07.05.2015 |
| Date of proceeded defence: | 04.06.2015 |
| Opponents: | doc. Mgr. Petr Gregor, Ph.D. |
| Guidelines |
| 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í. |
| References |
| [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. |