Дискретная математика и математическая кибернетика НИР

Источник финансирования НИР

госбюджет, раздел 0110 (для тем по госзаданию)

Этапы НИР

# Сроки Название
4 1 января 2014 г.-31 декабря 2014 г. Дискретная математика и математическая кибернетика
Результаты этапа: В области синтеза и сложности функциональных систем получены оценки сложности реализации индивидуальных булевых функций схемами в базисах специального вида, а также булевых функций из ряда классов, допускающих «достаточно простую» схемную реализацию над различными функционально полными базисами. Получен ряд результатов о соотношении глубины и сложности реализации функций k-значной логики формулами в конечных базисах. Исследовано поведение функции Шеннона глубины для реализации функций многозначной логики схемами из функциональных элементов в произвольном бесконечном полном базисе. В области надежности и контроля управляющих систем получен ряд результатов в задаче проверки исправности и диагностики состояний набора функциональных элементов путем составления из них схем с одним выходом, а также проверки исправности и диагностики набора контактов путем составления из них двухполюсных контактных схем. В области теории функциональных систем исследовано семейство замкнутых классов функций k-значной логики с операцией замыкания специального вида на основе кодирования функций в двоичной системе счисления. Рассматривалась задача о представлении булевых функций обобщенными формулами над множеством автоматных функций, для некоторых классов булевых функций найдены универсальные множества формул. Получено описание ряда семейств предполных классов монотонных функций многозначной логики, которые имеют конечную порождающую систему. В области изучения сложности вычислений установлено, что сложность конечной абелевой группы растет (с ростом порядка группы) асимптотически не медленнее чем сумма числа примарных компонент группы и логарифма максимального порядка среди элементов группы. Для почти всех наборов степеней установлены верхняя и нижние оценки сложности для задач Р. Беллмана и Д. Кнута, дающие при широком диапазоне соотношения параметров (число переменных или вычисляемых степеней, значение максимального показателя степени и произведение всех показателей степеней) асимптотику роста сложности, а также гарантирующие при любом соотношении параметров превышение верхней оценки над нижней оценкой асимптотически не более чем в 5/3 раз. Рассматривалось среднее время вычисления значений булевых функций неветвящимися программами с условной остановкой с распределением Бернулли на n-мерном булевом кубе. Получено асимптотически точная формула для соответствующей функции Шеннона. Получены новые верхние оценки ранга хеш-функций произвольных множеств при растущем размере кластера. Получены верхние и нижние оценки сложности вычисления некоторых линейных преобразований (биномиального, Стирлинга, Лаха, Гаусса, Серпинского, Сильвестра) в различных базисах. В рамках исследования преобразований распределений бесповторными формулами в конечных полях рассматривался вопрос о выражении распределений в виде бесповторной формулы над конечным полем с независимыми случайными аргументами, имеющими заданное распределение. Построены подмножества распределений, которые сохраняются операциями конечного поля, и, как следствие, бесповторными формулами над конечным полем. В области теории формальных слов исследовалась периодическая структура символьных последовательностей. Получены оптимальные по порядку асимптотические оценки для максимального числа периодичностей произвольного заданного порядка в последовательностях фиксированной длины, где под порядком периодичности понимается отношение ее длины к ее минимальному периоду. В области исследования криптографических свойств булевых функций найден новый подход, использующий обобщение понятия подходящих матриц, с помощью которого построены m-устойчивые булевы функции от n переменных с максимально возможной нелинейностью 2n-1-2m+1 для m > cn(1+o(1)), где c=0.5789, при этом оценка константы c улучшена. Показано, как дальнейшие продвижения в сформулированных сопутствующих комбинаторных задачах позволят ещё сильнее уменьшить константу c. Установлены условия существования m-устойчивых булевых функций от n переменных с максимально возможной нелинейностью для некоторого диапазона параметров (m,n).
5 1 января 2015 г.-31 декабря 2015 г. Дискретная математика и математическая кибернетика
Результаты этапа:

Прикрепленные к НИР результаты

Для прикрепления результата сначала выберете тип результата (статьи, книги, ...). После чего введите несколько символов в поле поиска прикрепляемого результата, затем выберете один из предложенных и нажмите кнопку "Добавить".