?
Оценки на число булевых функций, реализуемых инициальным константным булевым автоматом с тремя состояниями
С. 74–78.
Сысоева Л. Н.
В данной работе, построен пример инициального булевого автомата с тремя константными состояниями реализующего 2^{2^n} − 2^2^{n−1} − 1 различных булевых функций от n фиксированных переменных. Таким образом, в отличие от случая инициальных автоматов с двумя состояниями, среди инициальных булевых автоматов с тремя константными состояниями существуют автоматы, доля функций f(x1,x2,...,xn), реализуемых которыми, стремится к 1 с ростом n. Также получена верхняя оценка числа булевых функций от n фиксированных переменных, реализуемых инициальным булевым автоматом с тремя константными состояниями.
В книге
М.: Издательство ИПМ РАН, 2015.
Ivanov N., Рубцов А. А., Вялый М. Н., , in: Descriptional Complexity of Formal Systems. 26th IFIP WG 1.02 International Conference, DCFS 2025 Loughborough, UK, July 22–24, 2025. Proceedings.: Springer, 2025. P. 137–150.
Добавлено: 24 августа 2025 г.
Учебное пособие адресовано изучающим курс дискретной математики, прежде всего, студентам младших курсов, обучающимся по направлениям укрупненных групп 01.03.00 "Математика и механика", 02.03.00 "Компьютерные и информационные науки", 09.03.00 "Информатика и вычислительная техника".
Настоящий сборник задач является пособием для практических занятий по некоторым разделам дискретной математики и может быть использован преподавателями и студентами для подготовки к семинарским занятиям и ...
Добавлено: 12 ноября 2023 г.
Учебник содержит лекционный материал по дисциплине "Дискретная математика", а также примеры задач с решениями и задачи для самостоятельной работы. Основные разделы учебника: множества, математическая индукция, комбинаторика, булевы функции, логика высказываний и предикатов, графы, автоматы и формальные языки, алгоритмы.
Учебник адресован, прежде всего, студентам младших курсов, обучающихся по направлениям укрупненных групп 01.03.00 "Математика и механика", 02.03.00 "Компьютерные ...
Добавлено: 12 ноября 2023 г.
Коврижных М. А., Фомин Д. Б., Прикладная дискретная математика. Приложение 2021 № 14 С. 181–184
Предложен эвристический алгоритм построения биективных булевых функций с заданными криптографическими свойствами — нелинейностью и дифференциальной δ-равномерностью — на основе обобщённой конструкции. Производится поиск вспомогательных подстановок меньшей размерности в обобщённой конструкции с использованием идей спектрально-линейного и спектрально-разностного методов. Исследована возможность оптимизации вычисления криптографических характеристик на каждой итерации алгоритма. Экспериментально получены 8-битовые 6-равномерные подстановки с нелинейностью 108. ...
Добавлено: 22 сентября 2021 г.
Федоров С. Н., Логачёв О. А., Ященко В. В., Дискретная математика 2021 Т. 33 № 2 С. 66–85
Рассматривается действие на множестве булевых функций расширения G полной аффинной группы преобразований с помощью группы аффинных функций: действие заключается в преобразовании булевых функций невырожденными аффинными заменами переменных и сложением с аффинными булевыми функциями. Введены и исследованы параметры булевых функций, инвариантные относительно действия группы G: амплитуда (тесно связанная с нелинейностью), размерность функции и некоторые другие. Эти ...
Добавлено: 16 июня 2021 г.
Федоров С. Н., Логачёв О. А., Ященко В. В., Discrete Mathematics and Applications 2020 Vol. 30 No. 2 P. 93–101
Добавлено: 16 июня 2021 г.
Федоров С. Н., Логачёв О. А., Сукаев А. А., Информатика и ее применения 2019 Т. 13 № 2 С. 37–46
Как известно, вычислительная задача решения систем нелинейных уравнений над полем из двух элементов является NP-трудной. Этим обстоятельством обуславливается стремление исследователей разрабатывать алгоритмы ее решения, минимизирующие необходимые вычислительные ресурсы для тех или иных классов систем уравнений.
В статье предлагается метод решения систем квадратичных булевых уравнений, использующий представление функций их аффинными нормальными формами, то есть, в некотором смысле, аппроксимацию ...
Добавлено: 16 июня 2021 г.
Федоров С. Н., Логачёв О. А., Ященко В. В., Discrete Mathematics and Applications 2019 Vol. 29 No. 2 P. 89–101
Добавлено: 16 июня 2021 г.
Сысоева Л. Н., Moscow University Mathematics Bulletin 2019 Vol. 74 No. 6 P. 241–245
Добавлено: 22 ноября 2020 г.
Яшунский А. Д., Вестник Московского университета. Серия 1: Математика. Механика 2019 № 4 С. 3–9
Рассматриваются индуцированные системой булевых функций алгебры бернуллиевских распределений, у которых основное множество имеет единственную предельную точку. Доказан критерий того, что алгебра, порождаемая заданным множеством распределений, имеет единственную предельную точку. ...
Добавлено: 9 сентября 2020 г.
Яшунский А. Д., Lobachevskii Journal of Mathematics 2019 Vol. 40 No. 9 P. 1423–1432
We consider Bernoulli distribution algebras, i.e. sets of distributions that are closed under transformations achieved by substituting independent random variables for arguments of Boolean functions from a given system. We establish that, unless the transforming set contains only essentially unary functions, the set of algebra limit points is either empty, single-element or no less than ...
Добавлено: 9 сентября 2020 г.
Яшунский А. Д., Algebra Universalis 2019 Vol. 80 No. 1 (5) P. 1–16
We consider the problem of approximating distributions of Bernoulli random variables by applying Boolean functions to independent random variables with distributions from a given set. For a set B of Boolean functions, the set of approximable distributions forms an algebra, named the approximation algebra of Bernoulli distributions induced by B. We provide a complete description ...
Добавлено: 9 сентября 2020 г.
Ложкин С. А., Данилов Б. Р., Прикладная математика и информатика 2011 № 39 С. 107–129
В работе изучается модель задержки схем из функциональных элементов в произвольном конечном полном базисе Б, в которой задержки базисных элементов по различным входам могут различаться. В рассматриваемой модели получены асимптотические оценки вида τБn±O(1), где τБ ― константа, зависящая только от базиса Б, для задержки мультиплексорной функции порядка n, то есть функции с n адресными и 2n информационными переменными ...
Добавлено: 2 декабря 2019 г.
Lozhkin S. A., Danilov B.R., Computational Mathematics and Modeling 2012 Vol. 23 No. 4 P. 487–506
В работе изучается модель задержки схем из функциональных элементов в произвольном конечном полном базисе Б, в которой задержки базисных элементов по различным входам могут различаться. В рассматриваемой модели получены асимптотические оценки вида τБn±O(1), где τБ ― константа, зависящая только от базиса Б, для задержки мультиплексорной функции порядка n, то есть функции с n адресными и 2n информационными переменными ...
Добавлено: 2 декабря 2019 г.
Данилов Б. Р., Вестник Московского университета. Серия 15: Вычислительная математика и кибернетика 2013 Т. 4 С. 25–33
В~работе изучается модель задержки схем из функциональных элементов в произвольном конечном полном базисе~$\lBase$, в которой задержки базисных элементов задаются произвольными положительными действительными числами для каждого входа и каждого входного набора переменных, поступающих на остальные входы. В~рассматриваемой модели для задержки мультиплексорной функции порядка~$n$ получены асимптотические оценки вида~$\tau_{\lBase} n \pm O(\log n)$, где~$\tau_{\lBase}$ "--- константа, зависящая только ...
Добавлено: 2 декабря 2019 г.