ИСТИНА

Цель НИР состоит в разработке и развитии подходов к исследованию свойств дискретных математических моделей и их составляющих (функций на конечных и счетно бесконечных множествах; полиномов над конечными полями и кольцами; графов; комбинаторных множеств, др.), проведении исследований и получении решений серии актуальных задач, связанных с синтезом, анализом и тестированием дискретных управляющих систем, с передачей информации о дискретных функциях, а также с эквивалентностью, оптимизацией и верификацией автоматных вычислительных моделей.

The goal is to establish and to develop approaches for examination of properties for discrete mathematical models and their components (functions of finite sets and of countably infinite sets; graphs; combinatorial sets, etc.), and also to conduct researches and obtain solutions to a series of actual problems related to the synthesis, analysis and testing of discrete control systems, the transfer of information about discrete functions, as well as the equivalence, optimization and verification of automatic computational models.

Развитие подходов к получению новых частей решеток замкнутых классов в многозначных логиках, в частности, классов полиномиальных функций. Разработка подходов к построению новых быстрых алгоритмов распознавания свойств конечных структур, в частности, полиномов над конечными полями и кольцами. Разработка новых моделей абстрактных машинных вычислений, в частности, моделей обратимых вычислений, и их анализ. Развитие подходов к исследованию свойств комбинаторных множеств, в частности, уточнение метода граничных функционалов. Получение асимптотических оценок, имеющих, как правило, высокую степень точности, для сложности "типичных" или "самых сложных" функций в некоторых классах схем. Разработка методов синтеза схем в некоторых моделях, связанных с логическим проектированием дискретных устройств преобразования информации и, в частности, СБИС. Разработка методов "вложения" ("геометрической" реализации) схем в некоторые регулярные структуры, связанные, в частности, с топологическим синтезом СБИС. Исследование индивидуальной сложности и структуры оптимальных схем для ряда "специальных" функций. Построение и анализ тестов для различных задач контроля в некоторых классах схем. Получение простых представлений, оценок на минимальный размер области определения и сложность получения универсальных функций. Исследование ряда фундаментальных проблем программирования, таких как проблемы эквивалентности, оптимизации и верификации автоматных вычислительных моделей.

По тематике НИР в 2021--2024 годах исполнители разработали подходы к решению ряда задач, опубликовали статьи в рецензируемых журналах. 1. Получены с помощью разработанных подходов новые свойства решеток замкнутых классов в k-значной и частичной k-значной логиках. В частности, установлены мощности надрешеток замкнутых классов в частичных k-значных логиках, содержащих некоторые замкнутые классы всюду определенных k-значных функций (полиномиальных функций, некоторые предполные классы, др.). Кроме того, найдены в явном виде отношения, описывающие замкнутый класс полиномиальных функций в некоторых k-значных логиках. Публикации: 1. Alekseev V.B. On the cardinality of interval Int(Pol_k) in partial k-valued logic // Moscow University Mathematics Bulletin, 2022, V. 77, N 3, P. 120-126. DOI: https://doi.org/10.3103/S0027132222030032 (Scopus Q3, Web of Science Q4, Белый список 3, РИНЦ); 2. Селезнева С.Н. Описание замкнутого класса полиномиальных функций по модулю степени простого числа посредством отношения // Дискретная математика. 2023. Т. 35, вып. 4. С. 115-125. DOI: https://doi.org/10.4213/dm1803 (Scopus Q4, Web of Science Q4, Белый список 3, РИНЦ) 2. Доказано совпадение класса BPC, определенного с помощью операции ограниченной префиксной конкатенации, с известным сложностным классом TC0. Благодаря этому прояснен ряд свойств класса BPC и получено простое чисто словарное определение класса TC0. Публикация: 1. Savitskii I.V. On the сoincidence of сomplexity сlasses BPC and TC^0 // Moscow  Moscow University Computational Mathematics and Cybernetics  // 2022. N 46. P. 204-214. DOI: https://doi.org/10.3103/S0278641922040069 (РИНЦ); книга о теории абстрактных вычислительных устройств:   1. Марченков С.С., Савицкий И.В. Машины в теории вычислимых функций. Москва, Вологда: Инфра-Инженерия, 2024. 104 с. ISBN: 978-5-9729-2057-0 https://istina.msu.ru/publications/book/642169751