Методы решения задач, связанных с построением и исследованием дискретных математических моделей и управляющих системНИР

Methods for solving problems related to the construction and research of discrete mathematical models and control systems

Соисполнители НИР

МГУ имени М.В.Ломоносова Координатор

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

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

Этапы НИР

# Сроки Название
1 1 января 2025 г.-31 декабря 2025 г. Методы решения задач, связанных с построением и исследованием дискретных математических моделей и управляющих систем
Результаты этапа: Установлены новые необходимые условия для существования метода умножения матриц размеров 2х2 и 2х5 с 17 умножениями. Исследование связано с разработкой быстрых алгоритмов для умножения матриц. Получены критерии принадлежности функций k-значной логики к замкнутому классу полиномов по модулю квадрата простого числа. На основе них найдены в явном виде отношения, описывающие этот замкнутый класс. Предложено понятие квазирегулярного частично упорядоченного множества. Для таких множеств суммы граничных функционалов (СГФ) по множествам большой мощности можно оценивать через СГФ по множествам мощности 1. Построен ряд модификаций машинной модели обратимых вычислений, близкой к счётчиковым машинам с сумматором. Построены программы для вычисления ряда конкретных обратимых функций и промоделированы некоторые операции над функциями. Рассмотрен класс обобщенных полиномов с ограничением, а именно, что в них никакие k+1 слагаемое не обращаются одновременно в 1. Получен полиномиальный алгоритм проверки равенства 0 обобщенного полинома из этого класса. Полученные результаты расширяют знания о дискретных структурах. Их можно применять при разработке систем хранения, обработки, передачи и защиты информации. Это соответствует их практической значимости. Получены новые более точные оценки функции Шеннона для глубины булевых функций от $n$ переменных в стандартном базисе, позволяющие установить ее точное значение для почти всех $n$. Разработан метод гомеоморфного вложения полных троичных деревьев в прямоугольные решётки асимптотически минимальной площади с расположением листьев дерева на двух противоположных сторонах решетки. Установлены новые более точные асимптотические оценки сложности как совместной, так и раздельной реализации мультиплексора и дешифратора в классе схем из функциональных элементов (СФЭ) в стандартном базисе. Построена контактная схема, реализующая мультиплексорную функцию, асимптотически оптимальная по сложности и сохраняющая порядок роста новых рассмотренных функционалов статической и динамической активности. Построена контактная схема, реализующая дешифратор, асимптотически оптимальная по сложности и сохраняющая порядок роста новых рассмотренных функционалов статической и динамической активности. Установлены точные (не превосходящие константы 3) значения функции Шеннона длины единичного проверяющего теста относительно произвольных константных неисправностей на выходах элементов в схемах формульного типа над всяким неизбыточным полным базисом из булевых функций не более чем двух переменных, содержащем хотя бы одну линейную функцию, существенно зависящую от двух переменных; для остальных неизбыточных полных базисов из по крайней мере двух булевых функций, зависящих не более чем от двух переменных, установлены растущие с увеличением числа переменных нижние оценки аналогичных функций Шеннона. Получен критерий универсальности с использованием оракула – счетчика четности функций для класса линейных функций. Найдена универсальная с использованием оракула – счетчика четности функция для классов монотонных и поляризуемых функций, линейных функций в зависимости от значности и количества переменных. Предложена модификация градиентного метода для построения универсальных функций. К модели последовательных программ, совмещающей в себе небольшое обобщение синтаксиса дискретных преобразователей Глушкова-Летичевского и семантику пропозициональных программ Захарова, был применён метод совместных вычислений и с его помощью получен ряд эффективных алгоритмов проверки эквивалентности программ, и метод был усовершенствован: ослаблены ограничения на применение, улучшено изложение, исправлены недосказанности, недочёты и вероятные ошибки. Разработаны основные принципы устройства базы знаний для программной системы автоматизации рассуждения, основанной на предложенном Н.П. Брусенцовым алгебраического методе анализа логических взаимосвязей. Предложен алгоритм определения, является ли элементарная конъюнкция булевых переменных импликантой некоторой булевой функции, дана оценка его сложности. Полученные результаты могут быть использованы как теоретиками в области математической кибернетики, так и специалистами по проектированию и тестированию СБИС, что свидетельствует о практической значимости этих результатов.
2 1 января 2026 г.-31 декабря 2026 г. Методы решения задач, связанных с построением и исследованием дискретных математических моделей и управляющих систем
Результаты этапа: -
3 1 января 2027 г.-31 декабря 2027 г. Методы решения задач, связанных с построением и исследованием дискретных математических моделей и управляющих систем
Результаты этапа: -
4 1 января 2028 г.-31 декабря 2028 г. Методы решения задач, связанных с построением и исследованием дискретных математических моделей и управляющих систем
Результаты этапа: -

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

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