ДЕКОМПОЗИЦИЯ ЧАСТИЧНЫХ БУЛЕВЫХ ФУНКЦИЙ – ПОИСК ПОДХОДЯЩЕГО РАЗБИЕНИЯ
Аннотация
Исследуется проблема последовательной двухблочной декомпозиции частичных булевых функций по нестрогому разбиению на множестве аргументов. Рассматривается ключевая комбинаторная задача: нахождение подходящего разбиения на множестве аргументов, т. е. такого, по которому функция разделима. Предлагается алгоритм, существенно ускоряющий поиск подходящего разбиения путем предварительного обнаружения его следов. Алгоритм формулируется в терминах булевых и троичных векторов и матриц с использованием эффективных параллельных операций над ними.
Об авторе
А. Д. Закревский
Объединенный институт проблем информатики НАН Беларуси
Беларусь
Список литературы
1. Поваров, Г.Н. О функциональной разделимости булевых функций / Г.И. Поваров // Доклады АН СССР. - Т. 94, № 5. - 1954.
2. Ashenhurst, R.L. The decomposition of switching functions / R.L. Ashenhurst // Proc. International Symposium on the Theory of Switching. Part 1. - Cambridge: Harward University Press, 1959. - P. 75-116.
3. Curtis, H.A. Design of switching circuits / H.A. Curtis. - Van Nostrand, Princeton, N.-J., 1962.
4. Закревский, А.Д. Комбинаторный поиск подходящих разбиений при декомпозиции булевых функций / А.Д. Закревский // Вестник Томского государственного университета. Приложение № 18. - 2006. - С. 4-9.
5. Закревский, А.Д. Декомпозиция частичных булевых функций - проверка на разделимость по заданному разбиению / А.Д. Закревский // Информатика. - 2007. - № 1 (13). - С. 16-21.
6. Закревский А.Д. Универсальная система для решения задач типа синтеза релейных схем / А.Д. Закревский // Труды СФТИ. - Вып. 42. - 1963. - С. 9-37.
7. Харари, Ф. Теория графов / Ф. Харари. - М.: Мир, 1973.
Для цитирования:
Закревский А.Д.
ДЕКОМПОЗИЦИЯ ЧАСТИЧНЫХ БУЛЕВЫХ ФУНКЦИЙ – ПОИСК ПОДХОДЯЩЕГО РАЗБИЕНИЯ. Информатика. 2007;(2(14)):45-52.
Просмотров: 508
Послать статью по эл. почте 