Hornovské formule

• Thesis title in thesis language (Slovak): Hornovské formule
• Thesis title in Czech: Hornovské formule
• Thesis title in English: Horn Formulas
• Academic year of topic announcement: 2005/2006
• Thesis type: diploma thesis
• Thesis language: slovenš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: 25.11.2005
• Date of assignment: 25.11.2005
• Date and time of defence: 02.02.2010 00:00
• Date of electronic submission: 02.02.2010
• Date of proceeded defence: 02.02.2010
• Opponents: RNDr. Petr Kučera, Ph.D.

Guidelines

Student se podrobně seznámí s doporučenou literaturou pojednávající o Booleovských funkcích obecně a zvláště se zaměří na pasáže týkající se třídy Hornovských funkcí. Prostuduje různé možnosti reprezentace Hornovských funkcí se zvláštním zřetelem na reprezentace pomocí normálních forem. Úkolem diplomanta bude zpracovat přehled o složitosti problému hledání minimální reprezentace Hornovské funkce (pro různé typy reprezentací) a případně zkoumat vlastnosti těchto reprezentací a nové algoritmy (včetně aproximačních) pro hledání těchto reprezentací.

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

Toto téma je vhodné pro studenty kteří navštìvovali přednášku Booleovské funkce a jejich aplikace, na které je několik otevřených otázek spojených s problematikou Hornovských formulí probíráno. Konkrétní téma záleží na vzájemné dohodě se školitelem.