SL reprezentace Booleovských funkcí vzhedem k nestandardním uspořádáním pravdivostní tabulky.

• Název práce v češtině: SL reprezentace Booleovských funkcí vzhedem k nestandardním uspořádáním pravdivostní tabulky.
• Název v anglickém jazyce: SL representations of Boolean functions with respect to non-standard orderings of the truth table.
• Klíčová slova: Reprezentace Booleovských funkcí|Efektivní algoritmy|Standardní dotazy
• Klíčová slova anglicky: Representations of Boolean functions|Efficient algorithms|Standard queries
• Akademický rok vypsání: 2024/2025
• Typ práce: diplomová práce
• Ústav: Katedra teoretické informatiky a matematické logiky (32-KTIML)
• Vedoucí / školitel: prof. RNDr. Ondřej Čepek, Ph.D.

Zásady pro vypracování

The student is expected to study the related literature from the area of knowledge compilation and then concentrate on switch-list representations (SLR) of Boolean functions. The aim of this research is to study non-standards orderings of the truth table and find out which orderings have interesting or useful properties with respect to SLRs. In particular it should be studied which queries and transformations can be implemented in polynomial time on such non-standard SLRs. The work should be mostly theoretical - study of different non-standard orderings, design of algorithms (for queries and transformations) and analysis of their properties (in particular of their time complexity).

Seznam odborné literatury

Darwiche, A., & Marquis, P. (2002). A knowledge compilation map. Journal Of Artificial Intelligence Research, 17, 229-264.
Čepek,O.; Chromý,M. (2020) Properties of Switch-List Representations of Boolean Functions. Journal of Artificial Intelligence Research, 69, 501-529.