|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ЦЭМИ РАН |
||
Алгоритмические и комбинаторные вопросы в теории многозначных функциональных систем и алгебрНИР
Algorithmic and combinatorial problems in the theory of multiple-valued function systems and algebras
- Руководитель НИР: Алексеев В.Б.
- Ответственный исполнитель: Селезнева С.Н.
- Участники НИР: Бухман А.В., Нагорный А.С., Чокаев Б.В.
- Подразделение: Кафедра математической кибернетики
- Срок исполнения: 1 января 2017 г. - 31 декабря 2019 г.
- Номер договора (контракта, соглашения): 17-01-00782
- Номер ЦИТИС: АААА-А17-117041250008-1
- Тип: Фундаментальная
- Приоритетное направление научных исследований: Математическая кибернетика, математические методы прогнозирования и исследование операций
- ПН России: Информационно-телекоммуникационные системы
- Направление технологического прорыва России: Стратегические информационные технологии
-
Рубрики ГРНТИ:
- 27.17.19 Кольца и модули
- 27.41.41 Алгоритмы решения задач вычислительной и дискретной математики
- 27.47.15 Математическая теория управляющих систем
-
Ключевые слова:
полином, функция k-значной логики, замкнутый класс, сложность, алгоритм
function of k-valued logic, polynomial, complexity, closed class, algorithm -
Описание:
Проект нацелен на решение следующих открытых проблем в теории многозначных функциональных систем и алгебр: построение фрагментов решеток замкнутых классов функций k-значных логик и частичных k-значных логик; нахождение оценок сложности представления функций k-значных логик и их систем полиномиальными формами различных видов; построение быстрых алгоритмов распознавания свойств функций k-значных логик, заданных полиномами; исследование сложности оптимальных алгоритмов для некоторых задач алгебры.
-
Abstract:
The project aims to solve the following open problems in the theory of multivalued functional systems and algebras: building the fragments of the lattices of closed classes of functions in k-valued logics and partial k-valued logic; finding bounds for complexity of representations of functions in k-valued logics and their systems by polynomial forms of different types; construction of fast algorithms for the recognition of properties of functions in k-valued logics, represented by polynomials; study of the complexity of the optimal algorithms for some problems of algebra.
-
Планируемые результаты:
Получение оценок функции Шеннона сложности представления функций k-значных логик и их систем в различных классах полиномиальных форм. Получение быстрых (с полиномиальной сложностью) алгоритмов распознавания по полиномам функций k-значных логик свойств, связанных с инвариантностью функции относительно преобразований переменных и других преобразований, сохранением функцией некоторого отношения, значением веса функции, или доказательство труднорешаемости соответствующих задач. Построение решетки замкнутых классов Pk, являющихся пересечением предполных классов при начальных k>=3; нахождение фрагментов этой решетки при произвольных k; нахождение глубины этой решетки при k=4 и оценки ее глубины при k=5; получение оценки наибольшей мощности базиса Pk. Установление необходимых и достаточных условий на частичный порядок, при которых решетка замкнутых классов в частичной k-значной логике, содержащих заданный предполный класс монотонных функций k-значной логики, является конечной или бесконечной. Получение верхних и нижних оценок для сложности умножения матриц малого порядка, а также нижних оценок граничного ранга некоторых алгебр.
-
Научный задел:
С.Н. Селезневой получены оценки функции Шеннона длины функций k-значных логик в различных классах полиномиальных форм; найдены точные значения функций Шеннона для систем функций. Ею получены полиномиальные алгоритмы распознавания по полиному свойства инвариантности относительно некоторых преобразований функций k-значной логики. А.В. Бухман успешно применил метод, разработанный С.Н. Селезневой, для распознавания других свойств функций k-значной логики. В.Б. Алексеевым и его учениками исследовались некоторые фрагменты решеток замкнутых классов в k-значных и частичных k-значных логиках. Опубликованная им в 1994 году совместная работа с А.А. Вороненко положила начало широкому исследованию решеток замкнутых классов в частичных k-значных логиках. В 2009 году В.Б. Алексеевым описаны фрагменты решеток замкнутых классов в частичных k-значных логиках, связанные с самодвойственными функциями. В 2010 году под руководством В.Б. Алексеева защищена кандидатская диссертация В.Б. Ларионовым на тему "Замкнутые классы k-значной логики, содержащие классы монотонных или самодвойственных функций". А.С. Нагорным построены части решеток пересечений предполных классов в Pk при некоторых начальных k >= 3; получены верхние и нижние оценки наибольшего базиса в P4; найдены базисы P4 из 19 функций. В.Б. Алексеевым установлено точное минимальное значение числа умножений в точных алгоритмах для умножения матрицы размера mх2 на матрицу размера 2х2 при m=3 (В.Б. Алексеев, 1985) и при m=4 (В.Б. Алексеев, А.В. Смирнов, 2013). Для матриц других размеров (кроме двух матриц порядка 2) точное минимальное значение числа умножений не известно. Участник проекта В.Б. Чокаев (2010) разработал методы исследования сложности умножения в коммутативных групповых алгебрах и получил ряд результатов об этой сложности. Также совместно с M. Blaser он исследовал алгебры минимальной мультипликативной сложности и установил, что множество таких алгебр совпадает с множеством алгебр минимального ранга (2012).
- Добавил в систему: Врагова Елена Юрьевна
Соисполнители НИР
| МГУ имени М.В.Ломоносова | Координатор |
Источник финансирования НИР
| грант РФФИ |
Этапы НИР
| # | Сроки | Название |
| 1 | 1 января 2017 г.-31 декабря 2017 г. | Алгоритмические и комбинаторные вопросы в теории многозначных функциональных систем и алгебр |
| Результаты этапа: Доказано, что число замкнутых классов в частичной k-значной логике, содержащих предполный класс монотонных функций k-значной логики, не ограничено сверху никакой константой. Получена классификация вычислительной сложности задачи выполнимости мультилинейных форм над конечным полем. Найдено точное значение наибольшей сложности систем из m функций над конечным полем нечетной характеристики, зависящих от n переменных, в классе поляризованных полиномиальных форм. Найдены два алгоритма сложности 25, обладающие двумя свойствами (симметриями): 1) в алгоритме присутствует тройка единичных матриц, 2) если в алгоритме присутствует тройка A, B, C, то в нем также присутствуют тройки B, C, A и C, A, B. К примеру, такими же свойствами обладает известный алгоритм Штрассена для умножения матриц 2х2. Также многие известные алгоритмы для умножения матриц 3х3 обладают свойством 2. В работе приведены методы нахождения новых алгоритмов. Показано, что найденные алгоритмы являются различными и новыми. Доказаны 9 универсальных (справедливых при любом k>2) свойств о вложениях пересечений предполных классов, лежащих в некоторых классах C(k) сохранения центральных предикатов, в некоторые другие предполные классы, а также 3 универсальных свойства о вложениях пересечений предполных классов в классы из C(k). Найдена глубина и ширина решетки основных замкнутых классов, являющихся пересечениями предполных классов четырехзначной логики из объединения семейств M и U. Найдены все тупиковые аксиомы вложения пересечений предполных классов, содержащих все константы, в некоторый предполный класс из семейства M(4). Описан один класс линейных преобразований переменных булевой функции. Получен полиномиальный алгоритм проверки инвариантности относительно описанного класса линейных преобразований переменных булевой функции, заданной полиномом. | ||
| 2 | 1 января 2018 г.-31 декабря 2018 г. | Алгоритмические и комбинаторные вопросы в теории многозначных функциональных систем и алгебр |
| Результаты этапа: Пусть A – предполный класс (максимальный клон) в k-значной логике, и T(A) – семейство всех замкнутых классов в частичной k-значной логике, содержащих A. Установлен простой критерий, который по частичному порядку, задающему предполный класс монотонных всюду определенных функций, позволяет установить, является ли семейство T(A) конечным или бесконечным. Этим завершается решение задачи о конечности T(A) для всех предполных классов k-значной логики. Для доказательства используются новые найденные семейства замкнутых классов в частичной k-значной логике. Пусть S - конечное множество предикатов на множестве E_k = {0, 1, ..., k-1}. Рассматривается задача распознавания S-ВЫП, в которой требуется выяснить выполнимость произвольной S-формулы. Известно, что если все предикаты из S инвариантны относительно некоторой полурешеточной функции f, то задача S-ВЫП является полиномиальной. Установлены свойства особых конъюнктивных нормальных форм предикатов, инвариантных относительно некоторой полурешеточной функции. На основе этих свойств улучшена оценка сложности полиномиального алгоритма для задачи S-ВЫП в случае, когда все предикаты из S инвариантны относительно одной и той же полурешеточной функции. Изучены симметричные билинейные алгоритмы вычисления коммутатора двух матриц 2х2. Установлены группы симметрий таких алгоритмов. Построена решетка пересечений предполных классов функций пятизначной логики, сохраняющих нетривиальные разбиения (т. е., разбиения, в которых число подмножеств больше 1 и меньше 5) множества E_5. Построен класс подфункций, наличие которых в функции k-значной логики обеспечивает высокую оценку его длины полинома этой функции. Получен алгоритм проверки сохранения предиката функцией k-значной логики со сложностью меньше, чем переборный алгоритм. | ||
| 3 | 1 января 2019 г.-31 декабря 2019 г. | Алгоритмические и комбинаторные вопросы в теории многозначных функциональных систем и алгебр |
| Результаты этапа: Рассмотрена решетка Int(A) всех замкнутых классов в частичной k-значной логике, содержащих заданный замкнутый класс A всюду определенных k-значных функций и состоящих только из функций, доопределимых до функций из класса A. Доказано, что эта решетка с отношением включения изоморфна решетке классов предикатов, замкнутых относительно переименования переменных, добавления и изъятия фиктивных переменных, подстановки в предикат функций из A вместо переменных и дизъюнкции предикатов. Показано, что если I - класс всех селекторов, то Int(I) содержит континуум замкнутых классов. Доказано, что билинейная сложность умножения матрицы порядка 2 на матрицу размера 2 x m над конечным полем с K элементами не меньше, чем (3+3/(K^2+2)) m. Таким образом, увеличен коэффициент в нижней оценке для умножения матрицы порядка 2 на матрицу размера 2 x m над любым конечным полем. Рассмотрены предикаты на конечном множестве, инвариантные относительно некоторой (m+1)-местной функции почти единогласия. Такие предикаты названы m-юнктивными. Доказаны свойства обобщенных конъюнктивных нормальных форм m-юнктивных предикатов. Показано, как на основе этих свойств можно построить полиномиальные алгоритмы проверки выполнимости систем m-юнктивных предикатов, инвариантных относительно одной и той же функции почти единогласия. | ||
Прикрепленные к НИР результаты
Для прикрепления результата сначала выберете тип результата (статьи, книги, ...). После чего введите несколько символов в поле поиска прикрепляемого результата, затем выберете один из предложенных и нажмите кнопку "Добавить".