Preview

Информатика

Расширенный поиск

ДЕКОМПОЗИЦИЯ ЧАСТИЧНЫХ БУЛЕВЫХ ФУНКЦИЙ – ПОИСК ПОДХОДЯЩЕГО РАЗБИЕНИЯ

Аннотация

Исследуется проблема последовательной двухблочной декомпозиции частичных булевых функций по нестрогому разбиению на множестве аргументов. Рассматривается ключевая комбинаторная задача:  нахождение подходящего разбиения на множестве аргументов, т. е. такого, по которому функция разделима. Предлагается алгоритм, существенно ускоряющий поиск подходящего разбиения путем предварительного обнаружения его следов. Алгоритм формулируется в терминах булевых и троичных векторов и матриц с использованием эффективных параллельных операций над ними.

Об авторе

А. Д. Закревский
Объединенный институт проблем информатики НАН Беларуси
Беларусь


Список литературы

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.

Просмотров: 424


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1816-0301 (Print)
ISSN 2617-6963 (Online)