Heuristické přístupy ke kompilaci do SLR reprezentace

• Název práce v češtině: Heuristické přístupy ke kompilaci do SLR reprezentace
• Název v anglickém jazyce: Heuristic approaches to the compilation to the SLR representation
• Klíčová slova: booleovské funkce|switch list reprezentace
• Klíčová slova anglicky: boolean function|switch list representation
• Akademický rok vypsání: 2023/2024
• Typ práce: bakalářská práce
• Ústav: Katedra teoretické informatiky a matematické logiky (32-KTIML)
• Vedoucí / školitel: RNDr. Petr Kučera, Ph.D.
• Řešitel: Pavel Humlíček - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 12.01.2024
• Datum zadání: 12.01.2024
• Datum potvrzení stud. oddělením: 14.01.2024

Zásady pro vypracování

Reprezentace booleovských funkcí pomocí switch-listů (SLR) byla zavedena jako vhodný cílový jazyk pro kompilaci znalostí v [1]. Autoři též popsali postup kompilace formule v DNF do SLR reprezentace. Pro DNF z vybraných tříd formulí a za předpokladu, že počet switchů je konstantní, má algoritmus popsaný v [1] polynomiální složitost, ovšem stupeň polynomu závisí na počtu switchů závisí. S rostoucím počtem hledaných switchů není tedy algoritmus prakticky použitelný. Základem algoritmu je určení pořadí proměnných, při kterém je dosaženo malého počtu switchů. Podobný problém je potřeba řešit i při konstrukci reprezentace pomocí OBDD. Cílem práce je uvážit heuristické postupy pro hledání vhodného pořadí proměnných, které jsou používané pro konstrukci OBDD, a upravit je pro použití na SLR reprezentacích. Výsledkem práce je jak navržení vhodných heuristických postupů pro kompilaci znalostí do SLR reprezentací, tak jejich implementace a experimentální ověření.

[1] Čepek, O., & Hušek, R. (2017). Recognition of tractable DNFs representable by a constant number of intervals. Discrete Optimization, 23, 1-19.

Seznam odborné literatury

[1] Čepek, O., & Hušek, R. (2017). Recognition of tractable DNFs representable by a constant number of intervals. Discrete Optimization, 23, 1-19.

[2] Čepek, O., & Chromý, M. (2021, January). Switch-list representations in a knowledge compilation map. In Proceedings of the Twenty-Ninth International Conference on International Joint Conferences on Artificial Intelligence (pp. 1651-1657).

[3] Rudell, R. (1993, November). Dynamic variable ordering for ordered binary decision diagrams. In Proceedings of 1993 International Conference on Computer Aided Design (ICCAD) (pp. 42-47). IEEE.

[4] Grumberg, O., Livne, S., & Markovitch, S. (2003). Learning to order BDD variables in verification. Journal of Artificial Intelligence Research, 18, 83-116.