Изучение свойств и разработка алгоритмов для дискретных структур и функциональных системНИР

Study of properties and development of algorithms for discrete structures and functional systems

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

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

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

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

Этапы НИР

# Сроки Название
1 1 января 2016 г.-31 декабря 2016 г. Изучение свойств и разработка алгоритмов для дискретных структур и функциональных систем
Результаты этапа: Доказано, что любой предполный класс в алгебре всюду определенных k-значных функций, состоящий из функций, монотонных относительно частичного порядка, в котором для любых двух элементов имеется наименьшая верхняя грань и для любых двух элементов имеется наибольшая нижняя грань, содержится в конечном числе замкнутых классов в частичной k-значной логике. Доказано, что оператор замыкания относительно систем функциональных уравнений (FE-оператор) порождает на множестве функций счетнозначной логики гиперконтинуальное семейство предполных классов. Доказано, что любая алгебра одноместных функций с носителем из счетного примитивно рекурсивно замкнутого класса и операцией композиции имеет континуальное число максимальных подалгебр, содержащих все одноместные функции из класса E2 Гжегорчика. Доказано, что для произвольного счетного частично-рекурсивно замкнутого класса функций группа всех перестановок, принадлежащих этому классу, имеет континуальное число максимальных подгрупп. Получены нижние оценки длины спада l(n) (т.е. числа элементов в (3k+1)-последовательности с началом в числе n) в (3k+1)-проблеме. Задача о существовании универсальных функций для класса линейных k-значных решена полностью при составном k. Доказана нетривиальная оценка мощности области определения универсальной функции для класса линейных булевых функций n переменных. Получены достаточные условия возможности одновременного порождения литералов. Получен порядок длины функций алгебры логики в классе псевдополиномиальных форм. При каждом составном k найдена асимптотика числа полиномиальных функций k-значной логики, зависящих от n переменных. Найдены необходимые и достаточные условия, при которых последовательность симметрических периодических функций с одним и тем же периодом является сложной в классе поляризованных полиномиальных форм (при простых k). Найдены все тривиальные (состоящие только из констант и селекторных функций) пересечения предполных классов семейства C \ T в четырехзначной логике. Построена решетка пересечений предполных классов четырехзначной логики из объединения семейств M и U. Установлены девять универсальных (справедливых при любом k>2) свойств пересечений предполных классов k-значной логики.
2 1 января 2017 г.-31 декабря 2017 г. Изучение свойств и разработка алгоритмов для дискретных структур и функциональных систем
Результаты этапа: Найдены новые замкнутые классы всюду определенных k-значных функций, монотонных относительно заданного частичного порядка, которые содержатся лишь в конечном числе замкнутых классов частичной k-значной логики. В частности, доказано, что при k=3 таким свойством обладает любой замкнутый класс всех функций, монотонных относительно заданного частичного порядка. Введен новый сильный оператор замыкания – оператор CQ-замыкания. Установлены основные свойства этого оператора. Найдены все 15 CQ-замкнутых классов булевых функций. Проведено сравнение оператора CQ-замыкания с другими известными операторами замыкания. Получена классификация вычислительной сложности задачи выполнимости мультилинейных форм над конечным полем. Найдено точное значение наибольшей сложности систем из m функций над конечным полем нечетной характеристики, зависящих от n переменных, в классе поляризованных полиномиальных форм. Найдена верхняя оценка длины функций над произвольным конечным полем в классе псевдополиномиальных форм. Найдены все слабоповторные в элементарном базисе функции, получаемые из бесповторных одним и двумя отождествлениями переменных. Найдены все слабоповторные в бинарном базисе функции, получаемые из бесповторных одним отождествлением переменных. Известно, что билинейный алгоритм сложности r для умножения матриц 3х3 можно задавать с помощью r упорядоченных троек 3х3-матриц. Широко изучаемыми являются алгоритмы, обладающие различными симметриями. В работе найдены два алгоритма сложности 25, обладающие двумя симметриями: 1) в алгоритме присутствует тройка единичных матриц, 2) если в алгоритме присутствует тройка A, B, C, то в нем также присутствуют тройки B, C, A и C, A, B. Доказаны 9 универсальных (справедливых при любом k>2) свойств о вложениях пересечений предполных классов, лежащих в некоторых классах C(k) сохранения центральных предикатов, в некоторые другие предполные классы, а также 3 универсальных свойства о вложениях пересечений предполных классов в классы из C(k). Найдена глубина и ширина решетки основных замкнутых классов, являющихся пересечениями предполных классов четырехзначной логики из объединения семейств M и U. Найдены все тупиковые аксиомы вложения пересечений предполных классов, содержащих все константы, в некоторый предполный класс из семейства M(4). Описан один класс линейных преобразований переменных булевой функции. Получен полиномиальный алгоритм проверки инвариантности относительно описанного класса линейных преобразований переменных булевой функции, заданной полиномом.
3 1 января 2018 г.-31 декабря 2018 г. Изучение свойств и разработка алгоритмов для дискретных структур и функциональных систем
Результаты этапа: Установлен простой критерий, который по частичному порядку, задающему предполный класс A всюду определенных монотонных функций, позволяет установить, является ли семейство T(A) всех замкнутых классов в частичной k-значной логике, содержащих A, конечным или бесконечным. Этим завершается решение задачи о конечности T(A) для всех предполных классов k-значной логики. Введен новый класс абстрактных вычислительных устройств - счетчиковые машины с сумма-тором (CS-машины). Доказано, что любую общерекурсивную функцию можно строго вычислить на CS-машине. Определены полиномиально-регистровые машины (PR-машины), близкие к машинам с произ-вольным доступом к памяти. Доказано, что вычисления на PR-машинах можно промоделиро-вать полиномиальными возвратными последовательностями, а вычисление элементов полиномиальной возвратной последовательности - выполнить с помощью подходящей PR-машины. Установлено, что всякое собственное расширение оператора позитивного замыкания с помощью логических связок дает либо оператор с полной системой связок, либо оператор импликативного замыкания. Для оператора импликативного замыкания в терминах полугрупп эндоморфизмов получено описание всех замкнутых классов. Предложена итеративная процедура для подсчета числа n-местных функций k-значной логики с заданным эдоморфизмом. С ее помощью получены формулы для числа n-местных функций трехзначной логики с произвольными эндоморфизмами. Решена задача нахождения минимального количества переменных, требуемого для получения каждой из слабоповторных функций из бесповторной формулы в элементарном решена как для двух семейств из одной функции, так и для трех счетных семейств слабоповторных функций. Установлены свойства особых обобщенных конъюнктивных нормальных форм, представляющих предикаты над конечным множеством, инвариантные относительно некоторой полурешеточной функции. На основе этих свойств улучшена оценка сложности полиномиального алгоритма проверки выполнимости систем предикатов над конечным множеством, которые инвариантны относительно некоторой полурешеточной функции. Построена решетка U5 пересечений классов из U(5). Доказано, что она содержит ровно 271380 узлов. Из них ровно 2542 узлов соответствуют попарно недвойственным классам–пересечениям K. Также получен полный список всех возможных классов, соответствующих узлам этой решетки. Установлено одно свойство полиномов k-значных функций, которое гарантирует достаточно большую длину полинома. Это свойство даёт возможность ограничивать перебор при проверке того, что функция, заданная полиномом, сохраняет определённый класс предикатов.
4 1 января 2019 г.-31 декабря 2019 г. Изучение свойств и разработка алгоритмов для дискретных структур и функциональных систем
Результаты этапа:
5 1 января 2020 г.-31 декабря 2020 г. Изучение свойств и разработка алгоритмов для дискретных структур и функциональных систем
Результаты этапа:

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

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