Diskretnaya Matematika

Journal Information
ISSN / EISSN : 0234-0860 / 2305-3143
Published by: Steklov Mathematical Institute (10.4213)
Total articles ≅ 1,175
Filter:

Latest articles in this journal

Степан Алексеевич Комков
Diskretnaya Matematika, Volume 33, pp 54-63; https://doi.org/10.4213/dm1636

Abstract:
Показано, что в многозначной логике существуют континуальное семейство попарно не сравнимых замкнутых классов функций с минимальным логарифмическим темпом роста и континуальная цепочка вложенных замкнутых классов функций с минимальным логарифмическим темпом роста. Отсюда выводится, что в любом классе сохранения подмножества существуют континуальная цепочка вложений и континуальное семейство таких попарно не сравнимых замкнутых классов функций, что ни один из них не вкладывается целиком ни в какой другой предполный класс.
Дмитрий Владимирович Закаблуков
Diskretnaya Matematika, Volume 33, pp 46-54; https://doi.org/10.4213/dm1653

Abstract:
Рассматриваются обратимые схемы, состоящие из функциональных элементов NOT, CNOT и 2-CNOT и имеющие малое число дополнительных входов. Изучается функция Шеннонa сложности $L(n, q)$ такой схемы, реализующей отображение $f\colon \mathbb Z_2^n \to \mathbb Z_2^n$, при условии, что количество дополнительных входов $q = O(n^2)$. Доказывается соотношение $L(n,q) \asymp n2^n \mathop / \log_2 n$ для указанного диапазона значений $q$. Устанавливается порядок роста $L(n,q) \asymp n2^n \mathop / \log_2 (n+q)$ для всех значений $q \lesssim n2^{n-\lceil n \mathop / \phi(n)\rceil}$, где $\phi(n) \to \infty$ и $n \mathop / \phi(n) - \log_2 n \to \infty$ при $n \to \infty$.
Владимир Гаврилович Михайлов, , Natalia Mikhailovna Mezhennaya, Артем Владимирович Волгин
Diskretnaya Matematika, Volume 33, pp 64-78; https://doi.org/10.4213/dm1656

Abstract:
Рассматривается задача об условиях асимптотической нормальности числа повторений (пар одинаковых значений) в отрезке стационарной (в узком смысле) случайной последовательности величин из $\{1,2,\ldots,N\}$, обладающей свойством равномерно сильного перемешивания. Показано, что при естественных предположениях необходимым условием асимптотической нормальности числа повторений при неограниченном удлинении наблюдаемого отрезка является отличие стационарного распределения последовательности от равновероятного. При определенных условиях для этой предельной теоремы получена оценка точности нормальной аппроксимации в равномерной метрике.
Максим Павлович Савелов
Diskretnaya Matematika, Volume 33, pp 92-106; https://doi.org/10.4213/dm1662

Abstract:
Найдены совместное распределение и предельное совместное распределение статистик следующих критериев пакета NIST: «Monobit Test», «Frequency Test within a Block» и «Cumulative Sums Test» в случае, когда исследуемая последовательность имеет распределение Бернулли. В случае, когда в критерии «Frequency Test within a Block» используются два блока, найдены попарные ковариации данных статистик.
Дмитрий Александрович Буров, Dmitry Alexandrovich Burov
Diskretnaya Matematika, Volume 33, pp 3-40; https://doi.org/10.4213/dm1639

Abstract:
В работе изучаются рассеивающие свойства операции модульного сложения для систем импримитивности группы сдвигов двоичного векторного пространства $V_n = \{0,1\}^n$. Описаны все подпространства пространства $V_n$, индуцирующие системы импримитивности, по которым операция модульного сложения рассеивает хуже всего.
В Г Рябов
Diskretnaya Matematika, Volume 33, pp 79-91; https://doi.org/10.4213/dm1635

Abstract:
Функция от $n$ переменных над полем из $q$ элементов называется максимально нелинейной, если она обладает наибольшей нелинейностью среди всех таких функций. Получены критерии и необходимые условия максимальной нелинейности. Из них следует, что при четных значениях $n$ максимально нелинейные функции является бент-функциями, однако при $q>2$ известные семейства бент-функций не являются максимально-нелинейными. Для произвольного конечного поля найдена связь расстояний Хэмминга от функции до всех аффинных отображений со спектрами Фурье нетривиальных характеров функции.
Кирилл Игоревич Грошев, Cyril Igorevich Groshev
Diskretnaya Matematika, Volume 33, pp 41-45; https://doi.org/10.4213/dm1661

Abstract:
Предъявляется один класс нерегулярных языков, связанный с заменой систем счисления.
Светлана Николаевна Селезнева
Diskretnaya Matematika, Volume 33, pp 107-120; https://doi.org/10.4213/dm1658

Abstract:
Периодом функции алгебры логики $f(x_1, \ldots, x_n)$ называется такой набор $a = (a_1, \ldots, a_n)$ из нулей и единиц, что верно тождество $f(x_1+a_1, \ldots, x_n+a_n) = f(x_1, \ldots, x_n)$. Функция алгебры логики называется периодической, если существует ее ненулевой период. В работе предложен алгоритм, который по многочлену Жегалкина функции алгебры логики $f(x_1, \ldots, x_n)$ находит базис пространства всех ее периодов со сложностью $n^{O(d)}$, где $d$ - степень функции $f$. Как следствие показано, что найти базис пространства всех периодов функции алгебры логики ограниченной степени по ее многочлену Жегалкина можно со сложностью, полиномиальной по числу переменных функции.
Виталий Викторович Юделевич
Diskretnaya Matematika, Volume 33, pp 121-141; https://doi.org/10.4213/dm1655

Abstract:
Существует естественный способ сопоставлять каждому натуральному числу определeнный граф в виде дерева. В настоящей работе мы исследуем средние значения числа рeбер, висячих вершин и высоты деревьев, соответствующих натуральным числам, не превосходящих данной величины.
Виктория Владимировна Высоцкая, Viktoriya Vladimirovna Vysotskaya, Л И Высоцкий, L I Vysotsky
Diskretnaya Matematika, Volume 33, pp 46-65; https://doi.org/10.4213/dm1643

Abstract:
Исследуются матрицы над факторкольцами кольца многочленов от одной переменной над полем из двух элементов. Найдены нижние оценки доли обратимых матриц среди всех таких матриц заданного размера. Предложен и проанализирован эффективный алгоритм вычисления определителя матриц над указанными факторкольцами, а также алгоритм построения случайных обратимых матриц (с равномерным распределением на множестве всех обратимых матриц). Рассмотрен и проанализирован эффективный вариант последнего алгоритма для факторколец по модулю многочленов вида $x^r - 1$. Эти алгоритмы могут найти практическое применение при генерации ключей криптосхем на базе квазициклических кодов, например, LEDAcrypt.
Back to Top Top