РЕАЛИЗАЦИЯ ЭВРИСТИЧЕСКОГО МЕТОДА ДЕКОМПОЗИЦИИ БУЛЕВЫХ ФУНКЦИЙ
Abstract
Исследуется оригинальный эвристический алгоритм последовательной двухблочной декомпозиции частичных булевых функций по нестрогому разбиению на множестве аргументов. Рассматривается ключевая комбинаторная задача: нахождение пригодного разбиения на множестве аргументов, т. е. такого, по которому функция разделима. Поиск пригодного разбиения существенно ускоряется путем предварительного обнаружения его следов. В рамках экспериментальной системы оценивается эффективность алгоритма, определяются границы его практического применения.
About the Authors
А. Закревский
Объединенный институт проблем информатики НАН Беларуси
Belarus
Belarus
Н. Торопов
Объединенный институт проблем информатики НАН Беларуси
Belarus
Belarus
References
1. Закревский, А.Д. Последовательная декомпозиция булевой функции – поиск подходящего разбиения на множестве аргументов / А.Д. Закревский // Доклады НАН Беларуси. – 2007. – Т. 51, № 1. – С. 7–11.
2. Zakrevskij, A.D. Parallel operations over neighbors in Boolean space / A.D. Zakrevskij // Proceedings of the Sixth International Conference CAD DD-07. – Minsk, 2007. – Vol. 2. – P. 6–13.
3. Закревский, А.Д. Реализация случайных событий с заданной вероятностью / А.Д. Закрев¬ский // Труды СФТИ. – 1965. – Вып. 47. – С. 56–59.
4. Закревский, А.Д. Декомпозиция частичных булевых функций – поиск подходящего разбиения / А.Д. Закревский // Информатика. – 2007. – № 2. – C. 45–52.
Review
For citations:
, . Informatics. 2008;(4(20)):41-49. (In Russ.)
Views: 423
Email this article 