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

• Název práce v češtině: Třídy Booleovských funkcí umožňující efektivní hledání ; minimálních reprezentací.
• Název v anglickém jazyce: Classes of Boolean functions which admit an effective; search for minimal representations.
• Akademický rok vypsání: 2008/2009
• 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í: 12.11.2008
• Datum zadání: 12.11.2008
• Datum a čas obhajoby: 31.05.2010 00:00
• Datum odevzdání elektronické podoby: 31.05.2010
• Datum proběhlé obhajoby: 31.05.2010
• Oponenti: doc. Mgr. Petr Gregor, Ph.D.

Zásady pro vypracování

Ú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í.

Seznam odborné literatury

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

Předběžná náplň práce

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.