О СЛОЖНОСТИ И ГЛУБИНЕ ФОРМУЛ ДЛЯ СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ (60,00 руб.)

Первый автор	Сергеев
Страниц	5

ID	367615
Аннотация	Предложен новый прием реализации формулами оператора подсчета количества единиц в булевом наборе, основанный на приближенном вычислении суммы. С его помощью неконструктивно получены новые верхние оценки сложности и глубины формул для произвольных и некоторых конкретных симметрических функций над базисом В2 всех двухместных булевых функций и над стандартным базисом Во = {∧, ∨,-}. В частности, глубина умножения n-разрядных двоичных чисел оценивается сверху асимптотически как 4, 02 log2 n над базисом В2 и как 5,14 log2 n над базисом Во.
УДК	519.714

Сергеев, И.С. О СЛОЖНОСТИ И ГЛУБИНЕ ФОРМУЛ ДЛЯ СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ / И.С. Сергеев // Вестник Московского университета. Серия 1. Математика. Механика .— 2016 .— №3 .— С. 56-61 .— URL: https://rucont.ru/efd/367615 (дата обращения: 03.05.2024)