Třídy Booleovských funkcí umožňující efektivní hledání minimálních reprezentací.

• Thesis title in Czech: Třídy Booleovských funkcí umožňující efektivní hledání ; minimálních reprezentací.
• Thesis title in English: Classes of Boolean functions which admit an effective; search for minimal representations.
• Academic year of topic announcement: 2008/2009
• Thesis type: diploma thesis
• Thesis language: angličtina
• Department: Department of Theoretical Computer Science and Mathematical Logic (32-KTIML)
• Supervisor: prof. RNDr. Ondřej Čepek, Ph.D.
• Author: hidden - assigned and confirmed by the Study Dept.
• Date of registration: 12.11.2008
• Date of assignment: 12.11.2008
• Date and time of defence: 31.05.2010 00:00
• Date of electronic submission: 31.05.2010
• Date of proceeded defence: 31.05.2010
• Opponents: doc. Mgr. Petr Gregor, Ph.D.

Guidelines

Úkolem diplomanta je zpracovat přehled výsledků o třídách Booleovských formulí, pro které je problém hledání minimální reprezentace řešitelný v polynomiálním čase. Výzkumným úkolem je pak odvodit další zajímavé výsledky o těchto třídách, případně definovat nové třídy s výše uvedenou vlastností.

References

Boolean Functions and Computation Models
Clote, Peter; Kranakis, Evangelos
Springer Verlag 2002
ISBN: 3-540-59436-1

Boolean Functions : Theory, Algorithms, and Applications
Crama, Yves; Hammer, Peter L.
dosud nepublikovaný obsáhlý manuskript dostupný na
http://www.rogp.hec.ulg.ac.be/Crama/Publications/BookPage.html

Preliminary scope of work

Problém hledání minimálních reprezentací Booleovských formulí je prakticky důležitým problémem v mnoha oblastech informatiky. Velmi významné jsou třídy formulí, pro které je minimalizace (hledání logicky ekvivalentní formule minimální délky) řešitelná v polynomiálním čase. Práce se zabývá zkoumáním právě těchto tříd.