ИСТИНА |
Войти в систему Регистрация |
|
ИПМех РАН |
||
Целью работы является исследование фундаментальных проблем синтеза, сложности, надежности и контроля управляющих систем. Рассматриваются классические модельные классы управляющих систем, изучаются актуальные новые модельные классы управляющих систем, проводятся исследования в области диагностики и надежности основных и новых модельных классов управляющих систем. Разрабатываются новые методы и алгоритмы оптимального синтеза управляющих систем, получения верхних и нижних оценок сложности управляющих систем различных типов. Общий план работ включает поиск и изучение принципиально новых эффектов и явлений в области сложности дискретных функций, сложности арифметических и алгебраических задач, сложности в пространствах непрерывных функций, других классах управляющих систем; изучение вопросов выразимости и полноты в классических и новых функциональных системах; исследование вероятностных свойств управляющих систем; изучение сложности вычислений в группах, кольцах и других алгебраических системах; изучение с точки зрения сложности и контроля наиболее важных индивидуальных булевых и конечнозначных функций, а также классов таких функций, изучение средней сложности булевых функций; разработку новых методов построения минимальных или близких к минимальным самокорректирующихся и легкотестируемых схем для индивидуальных булевых функций в классе схем из функциональных элементов и контактных схем; исследования в области теории формальных языков. Ожидаемые результаты проекта позволят получить существенное продвижение в решении важнейших задач дискретной математики, математической кибернетики и смежных дисциплин. Исследования соответствуют мировому уровню, ожидаемые результаты превосходят результаты зарубежных авторов; ряд задач рассматривается впервые.
госбюджет, раздел 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 г. | Дискретная математика и математическая кибернетика |
Результаты этапа: |
Для прикрепления результата сначала выберете тип результата (статьи, книги, ...). После чего введите несколько символов в поле поиска прикрепляемого результата, затем выберете один из предложенных и нажмите кнопку "Добавить".