Heuristické přístupy ke kompilaci do SLR reprezentace

Abstract

Booleovské funkce jsou jedním ze základních pojmů informatiky, které se využívají například v reprezentaci znalostí, teoretické informatice nebo kryptografii. Tato práce se zabývá reprezentací booleovských funkcí pomocí switch-list reprezentace (SLR). Existuje exaktní algoritmus pro kompilaci z DNF do SLR, který však není prakticky použitelný pro větší počet switchů. V této práci se nejdříve věnujeme modifikaci exaktního algoritmu pro CNF a následně navrhneme tři rozdílné heuristické přístupy ke kompilaci do SLR: řadící a shlukovací heuristiky, heuristický přístup založený na strojovém učení a dva lo- kálně optimalizační algoritmy. Rozdílné přístupy jsou implementovány a experimentálně porovnány z hlediska kvality výsledné reprezentace a časové náročnosti. Výsledky uka- zují, že vhodně zvolená heuristika může výrazně zlepšit poměr mezi kvalitou řešení a časovou náročností a že existují heuristiky, které vedou k podstatně kompaktnější SLR reprezentaci, než jiné. Kromě toho ukážeme slibný potenciál ve využití strojového učení pro kompilaci do SLR a velkou efektivitu lokálně optimalizačního sifting algoritmu.

Boolean functions are one of the basic concepts of computer science used, for example, in knowledge representation, theoretical computer science, or cryptography. This work deals with the representation of boolean functions using switch-list representation (SLR). There is an exact algorithm for compiling from DNF to SLR, but it is not suitable for practical applications where the number of switches gets larger. In this work, we first look at modifying the exact algorithm for CNF, and then we design three different heuristic approaches to compiling to SLR: sequencing and clustering heuristics, a machine learning heuristic approach, and two local optimization algorithms. The different approaches are implemented and compared experimentally in terms of the quality of the resulting representation and the time required. The results show that a well-chosen heuristic can significantly improve the ratio between the quality of the solution and time consumption, and that there are heuristics that lead to a significantly more compact SLR representation, than others. In addition, we will show promising potential in using machine learning to compile into SLRs and great efficiency of the locally optimizing sifting algorithm.