Математические методы и алгоритмы теоретической информатикиНИР

Mathematical methods and algorithms of theoretical informatics

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

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

Этапы НИР

# Сроки Название
1 1 января 2016 г.-31 декабря 2016 г. Математические методы и алгоритмы теоретической информатики, этап 1
Результаты этапа: 1. Проведены исследования современных аналитических алгоритмов, алгоритмов прогнозирования и методов машинного обучения в задачах обработки больших данных. 2. Рассмотрено представление бигрупповой алгебры, являющейся цветной, для любой коммутативной группы порядка n, доказано, что существует изоморфизм алгебры матриц порядка n над полем К и бигрупповой алгебры, когда в К имеются корни порядков элементов группы и n не делится на характеристику поля. Тем самым построен новый алгоритм быстрого умножения матриц. 3. Исследованы приложения неассоциативных алгебраических структур в криптографии и кодировании: линейно оптимальные коды в квазигрупповых кольцах; криптосистемы над градуированными кольцами с мультипликативным базисом; криптосхемы на основе луп; группоиды с перестановочными степенями; медиальные квазигруппы на группе точек эллиптической кривой. 4. Рассмотрены прикладные аспекты гомоморфной криптографии, гомоморфные системы шифрования на основе матричных полиномов, сравнительный анализ полностью гомоморфных систем шифрования, системы гомоморфного шифрования с вычислениями ограниченного набора функций. 5. Продолжены исследования, направленные на снижение затрат на проектирование больших автоматизированных систем управления путем привлечения современных технологий метапрограммирования, таких как разработка, управляемая моделями (model driven engineering, MDE), и аспектно-ориентированный подход (aspect-oriented software development). Развит математический аппарат для построения, анализа и оптимизации процедур проектирования больших систем управления на базе теории категорий. Исследованы перспективы реализации математического обеспечения систем управления на базе нестандартных вычислительных устройств алгебраического типа. 6. Продолжены работы в области новых подходов и математических методов цифрового моделирования изделий машиностроения. Предложена концепция программного комплекса, сочетающего разнообразные методы: геометрический анализ, мультифизический расчет посредством метода конечных элементов и бессеточных методов (в том числе воксельных), моделирование методом Монте-Карло, осреднение, прогнозирование при помощи искусственных нейронных сетей. Для совместной верификации методов предложено применять аппарат теории категорий. 7. Построены топологические аналоги первичного и наднильпотентного радикала в топологических неассоциативных кольцах. Рассмотрены вариации топологического квазирадикала для ряда классов топологических неассоциативных колец. 8. Исследовалось пересечение степеней топологического радикала Джекобсона колец, обладающих топологической размерностью Крулля. Рассмотрен топологический аналог результата Джекобсона о равенстве нулю в некоторой порядковой степени радикала Джекобсона нётерова справа кольца. 9. Рассмотрено линейно упорядоченное поле D и подмоноид Gn(D) в линейной группе GLn(D), состоящий из всех обратимых матриц с неотрицательными коэффициентами из D. Доказано, что над линейно упорядоченным телом D при n>2 группа частных моноида Gn(D) совпадает с линейной группой GLn(D). 10. Рассмотрены изоморфизмы линейной группы GL2(R) над произвольным ассоциативным кольцом R с 1/2 и 1/3. В частности, дано полное описание автоморфизмов линейной группы GL2(R), где R – любое коммутативное ассоциативное кольцо с 1 и 1/2, 3 – неделитель нуля в R, R порождается обратимыми элементами. 11. Получена полная характеризация линейных инъективных отображений множества всех матриц над антинегативным полукольцом, монотонных относительно каждого из следующих частичных порядков: минус порядка, шарп-порядка, *-порядка Дрейзина. Доказано, что такие отображения автоматически биективны. Вычислены рода конечных графов Гротендика, соответствующих графам ортогональности и коммутативности матричных алгебр небольшого размера над конечными полями с малым числом элементов. В случае рода 0 найдены соответствующие функции Белого. 12. Продолжена разработка теории классических и постклассических семейств функций на дескриптивных и прескриптивных пространствах с пренебрежимостью. Введены понятия дескриптивных и прескриптивных пространств с пренебрежимостью. Определены семейства пренебрежимо-равномерных и пренебрежимо-распределённых функций на этих пространствах. Доказана замкнутость этих семейств относительно основных алгебраических операций и относительно равномерной сходимости последовательностей. Приведены примеры использования указанных семейств при решении ряда старых задач теории функций, интеграла и меры. 13. Получены новые результаты, касающиеся консервативных многочленов. Исследовано динамическое действие абсолютной группы Галуа на плоских деревьях, возникающее из соответствия между плоскими деревьями и консервативными многочленами. Построено 2-параметрическое семейство консервативных многочленов с рациональными коэффициентами, которые записываются в компактной форме с помощью многочленов Чебышева. Также были найдены 6 исключительных ситуаций, в которых орбита Галуа распадается: (5,3,3), (1,6,6), (12,4,4), (11,5,5), (35,23,23), когда неожиданно существует консервативный многочлен над Q и (7,2,2), когда существует консервативный многочлен над квадратичным полем. 14. Продолжена разработка и усовершенствование математической модели государства-страны и математической модели учреждения как клетки государства-страны. Государство представлено как сложная агрегированная организационно-производственная система, состоящая из основных подсистем, связанных потоками результатов их деятельности. Выписаны эволюционные уравнения. Произведено их приведение и упрощение. Сформулирована задача нахождения оптимального управления для упрощённой модели государства-страны. 15. В 2016 году были подготовлены русские и англоязычные версии четырёх выпусков журнала "Фундаментальная и прикладная математика" (русская версия – 972 страницы, англоязычная – 669 страниц). Информация о новых выпусках размещена на WWW-странице журнала http://mech.math.msu.su/~fpm/. 16. В рамках системы дистанционных учебных курсов разработано приложение для аналитической обработки и представления данных электронного обучения (Learning Analytics), включающее в себя: традиционные варианты бизнес-отчетов; приборные панели (dashboards) различного типа, содержащие графики и диаграммы, показатели KPI и т.д.; OLAP-куб для обработки данных в реальном времени, объединенный с графическими представлениями его значений. Разработан рабочий проект практикума для объединенного курса «Анализ больших данных»: исследованы возможности: SAP HANA Web IDE в качестве интегрированной среды разработки для практикума и Github-клиента в качестве репозитория создаваемых обучающимися объектов/артефактов. 17. Осуществлялась постоянная поддержка учебного процесса в Системе дистанционного обучения. В 2016 году начали обучение 41 дистанционный слушатель (всего 123 подписки на курсы).
2 1 января 2017 г.-31 декабря 2017 г. Математические методы и алгоритмы теоретической информатики, этап 2
Результаты этапа: Разработаны методы гомоморфной криптографии (на основе частично гомоморфных криптографических систем), а также необходимые технологии распределенных вычислений для их реализации при решении прикладных задач. Исследовались: алгоритмы быстрого умножения матриц; вариации информационных энтропий. Проведены исследования современных аналитических алгоритмов, алгоритмов прогнозирования и методов машинного обучения в задачах обработки больших данных. Был разработан новый алгоритм кластеризации больших данных, основанный на плотности распределения данных. Велись исследования в области оптимизации (распределенного) хранения разреженных матриц и векторов, в частности в целях ускорения соответствующих линейных операций для применения регрессионных моделей машинного обучения. Реализован спектр адаптивных структур данных, существенно ускоряющих вычисления. Исследовались: – современные методы использования больших данных, интегрированных в экосистему Hadoop, и среда выполнения Apache Spark, для целей ускорения операций анализа и принятия решений; – специализированные распределенные алгоритмы вычислений in-memory для обработки реляционных данных, временных рядов, графов и объектов JavaScript Object Notation (JSON). Проведена разработка практикума для объединенного спецкурса «Анализ больших данных»: – развернуто программное решение для распределенных вычислений in-memory: SAP Vora 1.4 Developer Edition; – исследованы возможности: – доступа при помощи SQL к данным временных рядов, графов и JSON; – веб-интерфейса с SQL-редактором. Осуществлена модификация алгоритма декодирования свёрточного кода, используемого совместно с QAM-модуляцией. Как результат, модифицируемый алгоритм повышает эффективность работы приёмника, так как понижает пороговое значение сигнал-шум. Было продолжено развитие теории топологических колец и модулей в интересах теоретической информатики. Рассмотрены топологические аналоги первичного и наднильпотентного радикала в топологических неассоциативных кольцах. Исследована структура топологически артиновых колец, в которых все главные левые идеалы замкнуты. Построены различные примеры топологически примитивных дискретных колец. В частности, приведён пример, показывающий различие радикала Джекобсона и его топологического аналога в случае дискретной топологии на кольце. Исследовались полигоны над полугруппами. Рассматривались вопросы об инъективности, проективности, подпрямой неразложимости полигонов, а также условия, при которых решётка конгруэнций модулярна или дистрибутивна. Полностью описаны подпрямо неразложимые полигоны над прямоугольными группами. Выяснено строение полигона над прямоугольной связкой, имеющего модулярную решётку конгруэнций. Проведены исследования: – по алгоритмам в алгебре и теории чисел; – по вычислительным аспектам нелокальной гидромеханики; – по построению СТО с неквадратичной гиперболической метрикой. Получены новые результаты в описании нереализуемых паспортов ветвления разветвленных накрытий 2-мерной сферы. Классифицированы нереализуемые паспорта двуклеточных рисунков на сфере. Доказан арифметический критерий нереализуемости паспортов рода 0. Найдено несколько новых серий нереализуемых паспортов рода 1. Вычислено в явном виде двупараметрическое семейство {(X,f)}, где X - кривая рода 2, а f – функция Абеля степени 8, обладающая свойством самосопряженности относительно биэллиптическая инволюция кривой X. В этом семействе определен одномерный страт, соответствующий семейству Фрида (функциям с 4 критическими значениями). В результате вычислена функция Белого мегакарты степени 40, соответствующей этому семейству Фрида. Проведены исследования применимости аппарата теории категорий в микроэкономике, в частности, для формулировки ряда общих задач, возникающих при разработке систем автоматизированного управления предприятиями. Осуществляется постоянная поддержка учебного процесса в Системе дистанционного обучения. В 2017 году начали обучение 37 дистанционный слушатель (всего 104 подписки на курсы).
3 1 января 2018 г.-31 декабря 2018 г. Математические методы и алгоритмы теоретической информатики, этап 3
Результаты этапа: Проанализированы связи проблем Бернсайда для полугрупп с теорией формальных языков. Исследованы схемы шифрования на основе шахматных партий. Издана двухтомная монография по основаниям современной математики ("Множества. Функции. Меры"), написанная В.К.Захаровым, Т.В.Родионовым и А.В.Михалёвым. Проведено комплексное исследование по теории представлений полугрупп (полигонов): полигоны над вполне (О-) простыми полугруппами (аналог кольцевой теоремы Веддербарна-Артина о классически полупростых кольцах); решётка конгруэнций; подпрямо неразложимые полигоны, решеточные тождества; диагональные полигоны; биполигоны, частичные полигоны. Отмечены связи с автоматами и универсальными алгебрами. Описаны некоторые частичные порядки и монотонные отображения матриц над антинегативными полукольцами специального вида. Изучены семейства пар Фрида, включающие в себя вырожденные пары. Построена компактификация пространства модулей, позволяющая учитывать вырождения. Рассмотрены конкретные вычислительные примеры. Были продолжены теоретические и экспериментальные исследования в области получения общих осредненных уравнений для сплошной среды с реологией. Получены асимптотические виды решений на бесконечности для интегрируемого нелинейного уравнения Шредингера, разработаны основы гиперболической геометрии и ее приложений в физике. Продолжены исследования в области симметрии в приложениях к физике и в алгоритмах. Получены различные результаты с использованием симметрии. Исследованы проблемы перехода от централизованных, реляционных, локальных баз данных к хранилищам данных на современных распределенных платформах и в распределенных реестрах, базирующихся на применении технологии блокчейн. Велась разработка практикума по пространственным базам данных для факультета космических исследований. Велись исследования в области оптимизации представлений линейный регрессионных моделей машинного обучения в целях улучшения времени отклика. Исследован ряд вариантов, в том числе для моделей с применением хеширования признаков и для моделей, построенных на базе унитарного кода. Разработана библиотека для компьютерной системы GAP (вычисления в теории групп и дискретной математике). Библиотека реализует следующие функции: - подсчет количества неэквивалентных накрытий с заданным паспортом ветвления и группой монодромии; - перечисление всех накрытий с заданным паспортом и группой монодромии; - вычисление действия сферической группы кос на множестве накрытий, когда количество точек ветвления больше 3; - определение "скрытых симметрий" накрытия и вычисление фактора по ним; - вычисление накрытия, получаемого из заданного с помощью действия на k-наборах. С помощью созданной библиотеки получены следующие результаты: - найдены нереализуемые паспорта накрытий до степени N=21 включительно; - перечислены накрытия рода 0 со специальными группами монодромии до степени N=63 включительно; - найдены несколько бесконечных серий примеров накрытий рода 0, которые получаются из действия на парах; для одного из этих семейств вычислены реализующие их рациональные функции. Разработан программный комплекс для классификации растений картофеля с различной интенсивностью хозяйственно-значимых заболеваний, физиологических стрессов и сортовой (не)однородностью при помощи современных и классических методов анализа данных. Получены 2 свидетельства о регистрации прав на ПО, базу данных: - программа для классификации (на основе сверточных нейронных сетей) геопривязанных массивов данных, полученных в результате мульти- и гипер-спектральной съемки растений картофеля с различной интенсивностью хозяйственно-значимых заболеваний (вирусных и оомицетных) и физиологических стрессов, а также RGB-изображений, полученных в результате съемки таких растений с БПЛА; - программа для классификации (классические алгоритмы) геопривязанных массивов данных, полученных в результате мульти- и гиперспектральной съемки растений картофеля с различной интенсивностью хозяйственно-значимых заболеваний и физиологических стрессов. Осуществляется постоянная поддержка учебного процесса в Системе дистанционного обучения. Применены нечеткие алгоритмы при создании новых моделей экспертных систем. По результатам проведенных исследований опубликовано около 30-ти научных статей и 2 монографии, сделано более 30-ти докладов на российских и международных конференциях, подготовлены 2 кандидатские диссертации, получено 2 свидетельства о регистрации прав на программное обеспечение, базу данных.
4 1 января 2019 г.-31 декабря 2019 г. Математические методы и алгоритмы теоретической информатики, этап 4
Результаты этапа: Основания теоретической информатики. 1. Рассмотрены бигрупповые алгебры, исследованы их группы автоморфизмов. 2. Обобщена теорема Поттера. Исследовано понятие равномерности и его связь с g-суммами. 3. Рассмотрены гиперболические геометрии, исследованы их связи с релятивистской физикой. 4. Изучен индекс цикличности графа и связанной с ним матрицы. Получена новая характеризация этого индекса в терминах k-раскрашивания графа. Вычислена алгоритмическая сложность нахождения индекса цикличности графов и матриц. 5. Изучено соответствие между простыми сборными графами и матрицами. Найден общий вид матрицы инцидентности такого графа. На матричном языке описана процедура добавления или удаления внутренней петли к графу. 6. Изучались решётки конгруэнций полигонов над полугруппами. Доказано, что решётка конгруэнций полигона над конечной полугруппой удовлетворяет нетривиальному решёточному тождеству в том и только том случае, если полигон конечен. 7. Изучались полигоны над группами. Получены необходимые и достаточные условия хопфовости и кохопфовости унитарного полигона над произвольной группой, а также некоторые необходимые и некоторые достаточные условия хопфовости и кохопфовости неунитарных полигонов над группами. Большие данные. Методы и алгоритмы. 1. Разработаны новые методы и алгоритмы вычислений с большими данными (данными больших размерностей). В частности: - предложен метод градуированных вычислений, более эффективный, нежели метод фильтрации вычислений. Осуществлена оценка сложности алгоритмов, созданных на его основе; - разработан более быстрый, по сравнению с известными, алгоритм для вычисления чисел Бернулли. Гомоморфное шифрование и параллельные вычисления. 1. Распределенные вычисления включены в контекст систем гомоморфного шифрования. Системы кодирования. 1. Продолжен анализ систем кодирования с использованием алгебраических систем (включая контекст квантовых кодов). Алгебраическая теория кодирования. 1. Рассмотрены применения алгебраических систем (включая квазигруппы, неассоциативные кольца и их представления) в возможных системах кодирования (включая квантовые). Представления и информационные структуры. 1. Теория представлений алгебраических систем применена к информационным системам. Прикладные исследования. 1. Разработана система идентификации человека по сосудистому рисунку его пальца. 2. Исследовались алгоритмы трехмерного восстановления изоповерхностей с субпиксельной точностью. Для восстановления поверхности нужных участков трехмерной модели кровеносной системы применялась комбинация ранее известных алгоритмов. 3. Проработан план решения ряда задач для завода «Авиадвигатель». В частности, по выявлению дефектов в лопатках авиационного двигателя/турбин и отслеживанию положения измерительного элемента по визуальной информации. 4. Завершена работа над проектом по определению вирусов и сортовой однородности по визуальной и спектральной информации по картофелю. Развитие технологических инструментов в приложениях. 1. Проведены исследования теоретических моделей и технологических инструментов для интеллектуального анализа больших наборов данных. В частности: - созданы блокноты (Jupyter Notebook) для анализа и визуализации данных; - разработаны SQL-скрипты, которые можно использовать в блокнотах; - проработано извлечение данных для аналитики из экземпляров службы автономного хранилища данных (Autonomous Database). Внедрение результатов исследований в учебный процесс. 1. Материал спецкурса "Аналитика больших данных" был адаптирован и прочитан для магистрантов факультета космических исследований МГУ. 2. Материал спецкурса "Модели данных и базы данных" для студентов механико-математического факультета МГУ был существенно дополнен. 3. Материал спецкурса "Модели данных и базы данных" был адаптирован и прочитан для студентов-бакалавров филиала МГУ имени М.В. Ломоносова в г. Душанбе. 4. Разработана программа учебного курса "Основы проектирования систем геоинформационных баз данных" для магистрантов факультета космических исследований МГУ. 5. Разработана программа спецкурса "Аналитика больших данных" для студентов-бакалавров филиала МГУ имени М.В. Ломоносова в г. Душанбе. 6. Продолжено развитие программы межфакультетских курсов “Информатика и экономика”, переработаны и прочитаны 2 семестровых курса. Публикации и конференции. По результатам проведенных исследований опубликовано около 30-ти научных статей, сделано более 30-ти докладов на российских и международных конференциях.
5 1 января 2020 г.-31 декабря 2020 г. Математические методы и алгоритмы теоретической информатики, этап 5
Результаты этапа:
6 1 января 2021 г.-31 декабря 2021 г. Математические методы и алгоритмы теоретической информатики, этап 6
Результаты этапа:
7 1 января 2022 г.-31 декабря 2022 г. Математические методы и алгоритмы теоретической информатики, этап 7
Результаты этапа:

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

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