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 |
Jazyk 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. |