Аннотация:
Исследуется сложность порождения булевых матриц схемами из функциональных элементов и формулами. Рассматриваемые в работе схемы состоят из элементов, выполняющих над булевыми матрицами не более чем $r$-местные покомпонентные операции дизъюнкции и конъюнкции; формулами называются схемы без ветвлений. Найдены асимптотически точные формулы функций Шеннона порождения булевых матриц как схемами, так и формулами.
Библиогр. 5.
Полный текст:
PDF файл (900 kB)