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

Mathematical models of discrete control systems and their applications

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

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

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

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

Этапы НИР

# Сроки Название
1 1 января 2019 г.-31 декабря 2019 г. Математические модели дискретных управляющих систем и их приложения
Результаты этапа: Установлено асимптотическое поведение функции Шеннона для сложности скалярных рекурсивных схем из функциональных элементов (СФЭ) над произвольным конечным полным базисом, имеющих ограниченную глубину рекурсии. Разработан метод синтеза СФЭ в некоторых базисах, позволяющий получить как для «типичной», так и для «самой сложной» ФАЛ асимптотически оптимальные - на уровне асимптотических оценок высокой степени точности (АОВСТ) - по сложности схемы, имеющие высокую степень защищенности от раскрытия функциональности. Получены более точные по сравнению с известными ранее нижние оценки сложности реализации стандартной мультиплексорной ФАЛ порядка n. Установлено, что функция Шеннона длины единичного проверяющего теста относительно вставки элемента «стрелка Пирса» в СФЭ над базисом Жегалкина не превосходит 2. Получена экспоненциальная нижняя оценка функции Шеннона длины полного диагностического теста относительно замещений элементов на конъюнкторы и дизъюнкторы в СФЭ. Рассмотрен подкласс монадических стандартных схем программ, в котором используются только одноместные функциональные и предикатные символы, и для данного класса предложен экспоненциальный по сложности (относительно размеров проверяемых программ) переборный алгоритм проверки комбинированной эквивалентности схем программ. Предложен подход к решению задачи проверки совместного останова программ без процедур, позволяющий с учетом известных результатов обосновать разрешимость и полиномиальную разрешимость проблемы эквивалентности программ с процедурами для многих перегородчатых моделей с полугрупповыми законами тождества операций преобразования данных и построить соответствующие решающие и полиномиальные решающие алгоритмы.
2 1 января 2020 г.-31 декабря 2020 г. Математические модели дискретных управляющих систем и их приложения
Результаты этапа: Для ФАЛ от не более чем пяти переменных были построены ориентированные контактные схемы, оптимизированные по динамической активности. Разработаны методы синтеза СФЭ в некоторых новых базисах, позволяющие получить как для «типичной», так и для «самой сложной» ФАЛ асимптотически оптимальные по сложности схемы, имеющие линейную динамическую активность. Описана структура и установлено точное значение глубины минимальных по сложности СФЭ, реализующих ступенчатые ФАЛ. Исследована возможность оптимизации СФЭ, реализующих ступенчатые ФАЛ, как по сложности, так и по глубине. Доказано, что для любого натурального $n$ любую булеву функцию $f$, зависящую от $n$ переменных, можно реализовать неизбыточной схемой из функциональных элементов в базисе $\{ xy, x\vee y, \bar x\}$, допускающей в случае неисправностей вида «закорачивание входа элемента на его выход с инвертированием» единичный проверяющий тест длины 2. Доказано, что в модели последовательных императивных программ с процедурами отношение обобщенной логико-термальной эквивалентности аппроксимирует отношение функциональной эквивалентности. Предложено понятие бисимуляционной эквивалентности моделей систем реального времени, являющейся достаточным условием неотличимости моделей формулами логики ветвящегося реального времени.
3 1 января 2021 г.-31 декабря 2021 г. Математические модели дискретных управляющих систем и их приложения
Результаты этапа: Предложена и рассмотрена достаточно общая модель для вычисляющих булевы функции двоичных программ над произвольными конечными базисами из вычислительных и переадресующихся команд, а также команд вызова подпрограмм. При этом допускается рекурсивный вызов подпрограмм, глубина которого ограничена заданным числом. Разработаны методы синтеза, с помощью которых уставлено асимптотическое поведение функции Шеннона для сложности реализации булевых функций от заданного числа переменных в рамках этой модели. Разработаны алгоритмы поиска оптимальных по статической и динамической активности схем из функциональных элементов (СФЭ) в произвольном конечном полном базисе, реализующих функции алгебры логики(ФАЛ) от малого числа переменных. В основе разработанных алгоритмов лежит подход, основанный на сведении задачи поиска схемы к задаче выполнимости булевых формул. Был создан прототип программной реализации данных подходов на основе системы поиска оптимальных по сложности схем. Предложенные ранее участниками проекта методы синтеза для «типичных» ФАЛ асимптотически оптимальных по сложности СФЭ в стандартном базисе, которые при этом имеют линейную относительно числа переменных реализуемых функций динамическую активность, обобщены на случай базисов более общего вида. Разработаны методы синтеза, с помощью которых получены новые более точные оценки функции Шеннона для глубины усилительных схем из функциональных элементов в некоторых базисах с емкостными параметрами выходов элементов. Установлены новые более точные и близкие к асимптотическим оценкам высокой степени точности (АОВСТ) оценки сложности реализации стандартных мультиплексорных функций в классе контактных схем с более слабыми, по сравнению с известными ранее, ограничениями на их структуру. В рамках модели клеточных схем получены близкие к АОВСТ оценки для сложности мультиплексорной функции, а также установлена асимптотика сложности некоторых связанных с ней операторов в данной модели. Установлены новые оценки функции Шеннона длины единичного проверяющего теста относительно замен элементов на инвенторы в СФЭ, функции Шеннона длины единичного диагностического теста относительно вставок элементов СФЭ, функций Шеннона длины k-диагностического теста относительно инверсных неисправностей элементов СФЭ. Для расширенной модели стандартных схем программ с операторами вызова процедур разработан алгоритм проверки логико-термальной эквивалентности полиномиальной по времени сложности, доказаны завершаемость и корректность предложенного разрешающего алгоритма. Предложен алгоритм проверки эквивалентности пропозициональных операторных программ на левосократимых уравновешенных полугрупповых шкалах, более эффективный по сравнению с имеющимися. Уточнено для соответствия практическим нуждам предложенное ранее понятие бисимуляционной эквивалентности моделей систем реального времени с часами.
4 1 января 2022 г.-31 декабря 2022 г. Математические модели дискретных управляющих систем и их приложения
Результаты этапа:
5 1 января 2023 г.-31 декабря 2023 г. Математические модели дискретных управляющих систем и их приложения
Результаты этапа:
6 1 января 2024 г.-31 декабря 2024 г. Математические модели дискретных управляющих систем и их приложения
Результаты этапа:
7 1 января 2025 г.-31 декабря 2025 г. Математические модели дискретных управляющих систем и их приложения
Результаты этапа:

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

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

Прикрепленные файлы


Имя Описание Имя файла Размер Добавлен