Том 11, серия 1, номер 2, 2004 г., Стр. 32-40

УДК 519.7
Д. А. Жуков
О вычислении частичных булевых функций клеточными схемами

Аннотация:
Пусть $D$ – некоторое подмножество множества всех $n$-мерных двоичных наборов, состоящее не менее чем из $n^2$ наборов. Для частичных булевых функций, определенных в $D$, построены клеточные схемы, площадь которых по порядку совпадает с размером $D$, а глубина по порядку равна $\log_2|D|$. Показано, что для почти всех частичных функций площадь и глубина этих схем неулучшаемы по порядку.

Жуков Д. А. ¹
1. МГТУ им. Н. Э. Баумана,
2-я Бауманская ул., д. 5, 105005 Москва, Россия
е-mail: oldbug@mail.ru

Статья поступила 6 февраля 2004 г.