Konstrukce minimálních DNF reprezentací 2-intervalových funkcí.
Název práce v češtině: | Konstrukce minimálních DNF reprezentací 2-intervalových funkcí. |
---|---|
Název v anglickém jazyce: | A construction of minimum DNF representations of 2-interval functions. |
Klíčová slova: | boolovská funkce, intervalová funkce, konstrukce reprezentace, aproximace |
Klíčová slova anglicky: | boolean function, interval function, representation construction, approximation |
Akademický rok vypsání: | 2011/2012 |
Typ práce: | diplomová práce |
Jazyk práce: | angličtina |
Ústav: | Katedra teoretické informatiky a matematické logiky (32-KTIML) |
Vedoucí / školitel: | prof. RNDr. Ondřej Čepek, Ph.D. |
Řešitel: | skrytý - zadáno a potvrzeno stud. odd. |
Datum přihlášení: | 02.11.2011 |
Datum zadání: | 12.02.2012 |
Datum potvrzení stud. oddělením: | 13.04.2012 |
Datum a čas obhajoby: | 21.05.2012 11:00 |
Datum odevzdání elektronické podoby: | 12.04.2012 |
Datum odevzdání tištěné podoby: | 13.04.2012 |
Datum proběhlé obhajoby: | 21.05.2012 |
Oponenti: | RNDr. Petr Kučera, Ph.D. |
Zásady pro vypracování |
Úkolem diplomanta je zpracovat přehled výsledků o intervalových Booleovských funkcích a pokusit se zobecnit známé výsledky pro 1-intervalové funkce (ze článku Scheiber et.al.) na případ 2-intervalových funkcí. V případě, že konstrukce minimální DNF bude příliš obtížná, tak se diplomant zaměří buď na aproximace (konstrukce DNF které nejsou minimální, ale od minimálních se liší jen o jistou garantovanou odchylku) nebo na přesnou minimalizaci u vybraných podtříd 2-intervalových funkcí. |
Seznam odborné literatury |
Crama, Y., Hammer, P.L., Boolean Functions : Theory, Algorithms, and Applications, Cambridge University Press
Scheiber, B., Geist, D., Zaks, A., Computing the minimum DNF representation of Boolean functions defined by intervals, Discrete Applied Mathematics 149 (2005) Čepek, O., Kronus, D., and Kučera, P., Recognition of interval Boolean functions. Annals of Mathematics and Artificial Intelligence, Volume 52, Number 1 (2008). |