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

Mathematical methods and algorithms of theoretical informatics 2021-2025

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

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

Этапы НИР

# Сроки Название
1 1 января 2021 г.-31 декабря 2021 г. Математические методы и алгоритмы теоретической информатики 2021-2025. Этап 1.
Результаты этапа: Основания теоретической информатики. Доказано, что множество всех обобщенно нильпотентных элементов псевдонормированного коммутативного кольца является замкнутым идеалом, и фактор-кольцо по нему не содержит ненулевых обобщенно нильпотентных элементов. Доказана верхняя оценка старшего коэффициента характеристического многочлена градуированного идеала в кольце обобщенных многочленов. Исследованы некоторые вопросы комбинаторной теории графов, актуальные для проведения исследований в области когнитивных систем, искусственного интеллекта и эпигенетических перестроек. В частности, для ряда серий простых сборных графов получена оценка минимального числа петель, которое необходимо добавить, чтобы сборное число графа увеличилось на единицу. Опубликованная в 2021 г. монография И.Б. Кожухова, А.В. Михалева, А.В. Тищенко «Избранные вопросы теории полугрупп. Представления и многообразия полугрупп», посвящена результатам последних 20 лет в этих актуальных направлениях. В цикле опубликованных в 2021 г. пяти статей А.В. Михалева и Е.Е. Ширшовой по упорядоченным алгебраическим системам и их приложениям рассмотрены следующие проблемы: строение интерполяционно упорядоченных алгебраических систем; структура псевдоупорядоченных колец; техника использования выпуклых идеалов алгебраических систем; радикалы упорядоченных колец; проективная геометрия над частично упорядоченными телами. Введены и изучены матрицы смежности простых сборных графов. Изучены возможные значения классических матричных инвариантов на матрицах инцидентности и смежности простых сборных графов. Выведены явные формулы, в зависимости от свойств делимости числа вершин графа на 2 и 3. Пары Белого и пары Фрида описаны как предельные величины при компактификации пространств модулей алгебраических кривых. Рассмотрены приложения к исследованию простых сборных графов. Большие данные. Методы и алгоритмы. Разработан новый метод кластеризации данных в многомерном пространстве, основанный на использовании связности элементов данных, исходя из осредненных значений плотности распределения точек данных в метрическом пространстве. Исследованы алгоритмы быстрого умножения и обращения квадратных матриц. Получен алгоритм обращения со сложностью двух умножений. При этом обращение имеет минимальную потерю точности за счет единственного обращения одного числа, соответствующего детерминанту. Проведены исследования теоретических моделей и технологических инструментов для интеллектуального анализа больших наборов данных. В частности были исследованы: – алгоритмы для поиска ассоциативных правил, включая их имплементацию на "чистом" Python (Efficient-apriori и Python FP-Growth); – возможность использования методов интеллектуального анализа процессов в контексте гибкой разработки программного обеспечения (Agile) и визуализация получаемых на его основе результатов с помощью пакета Fluxicon Disco; – инфраструктурная миграция для аналитической базы данных в рамках методологии DevOps. Результаты исследований были внедрены в учебный процесс. Исследования в области искусственного интеллекта. Разработаны нейронные сети и развиты методы глубокого обучения для решения задач распознавания образов в условиях неполной или нечеткой визуальной информации. Продолжены исследования в области компьютерного/ машинного зрения/ машинного обучения, компьютерной графики и сжатия данных. Спектральный анализ изображений В рамках данного направления исследованы данные полученные многоспектральной (каналов 4, а то и 12) и гиперспектральной камерой (сотня каналов), а также спектрометром (несколько сотен спектральных подддипизонов). К многоспектральной съемке относится и спутниковая съемка земли. Предполагается, что за счет того, что такие данные содержат больше информации чем то, что видит человек, они позволят выявить некоторые вещи до того как их заметит человек. Либо просто автоматизируют разметку. Данные исследованы на предмет выявления определенных эффектов или распознавания объектов. Например, выявление картофельных болезней и сорта по съемке БПЛА. Последнее важно для соответствующих хозяйств. В частности, важна именно ранняя диагностика болезней, а не когда уже все видно и человеку. Определение сорта важно для выявления однородности урожая в поле, т.е. вычисления объема примеси. Спутниковые данные позволили определить сорт древесной породы. Фактически выполнить таксацию лесного массива дистанционно. Также были выявлены засеянные культуры и спрогнозирован урожай. В мире животных. В рамках данного направления рассмотрены методы компьютерного зрения при наблюдении за животным миром, как крупных (свиней, коров и подобных), так и мелких (крылатых насекомых). В обоих случаях целью было снижение ручного труда по анализу изображений человеком к минимуму. Также были рассмотрены методы автоматизации анализа поведения животных. Исследования в области компьютерной геометрии и приложений к медицине Проводилась работа по созданию гидродинамической модели кровообращения в области сердца, целью которой является неинвазивная диагностика ишемической болезни сердца на основе данных компьютерной томографии. Проект включает построение трехмерной модели коронарных артерий сердца и части аорты с целью последующего гидродинамического расчета течения крови путем численного решения уравнений гидродинамики (уравнения Навье-Стокса, уравнения состояния и др.). Была реализована программа для практического расчета параметров кровообращения в области сердца (Фракционный Резерв Кровотока FFR, давление, скорость потока и т.п.) для реальных пациентов, с ее помощью были проведены расчеты и сравнение полученных результатов с результатами инвазивных измерений для нескольких десятков пациентов. В программе, помимо реализации полуавтоматического алгоритма трехмерной сегментации, реализовано построение триангуляции внутренней поверхности сосудов с помощью комбинированного алгоритма трехмерного восстановления, использующего как полученную в результате сегментации воксельную модель, так и тетраэдрическую сеть Хан-Пуризма-Скала, которая строится в окрестности границы воксельной модели. Реализованы также алгоритмы сглаживания триангуляции, использующие дискретный оператор Лапласа и метод сглаживания Таубина. Кроме того, разработан алгоритм упрощения триангуляции с сохранением топологии модели, с помощью которого размер модели сокращается с нескольких миллионов треугольников до нескольких сотен тысяч без видимого изменения формы модели; этот алгоритм также включен в программу вычисления трехмерной модели.
2 1 января 2022 г.-31 декабря 2022 г. Математические методы и алгоритмы теоретической информатики 2021-2025. Этап 2.
Результаты этапа: 1. Проведение исследований в области обработки больших данных. Продолжены исследования в методах кластеризации. Большинство известных методов дают существенно различающиеся результаты не только при малых изменениях значений данных, но и при изменении нумерации (порядка подачи данных) точек. Разработан метод кластеризации, который дает устойчивые результаты даже при относительно больших перемещениях, либо при малых деформациях. Это свойство полезно в задачах распознавания. Продолжено изучение бигрупповых алгебр и их приложений в различных областях математики, физики. Разработана теория преобразований Фурье в алгебре матриц. Продолжены исследования в области осреднения и получения скрытой информации из больших данных. Продолжено исследование понятия равномерности и его связи со статистическими характеристиками, с осреднением и с большими данными. Продолжены исследования в области градуированных вычислений. Велись исследования в области оптимизации реализации алгоритмов машинного обучения с помощью использования векторизации вычислений (в частности, SIMD-расширений современных процессоров) для улучшения сходимости и скорости работы численных методов оптимизации. Реализованы прототипы для задач регрессии и классификации. 2. Исследования в алгебраических основаниях теоретической информатики. Получено модульное развитие проблематики Бэра-Капланского и теории Голубчика-Михалева-Зельманова об изоморфизмах линейных групп над кольцами. Изучены свойства множества L(R) всех выпуклых направленных идеалов частично псевдоупорядоченных колец R. Доказано, что если R является интерполяционным кольцом, то в решетке L(R) операция объединения вполне дистрибутивна относительно операции пересечения. Доказаны вторая и третья теоремы о порядковых изоморфизмах интерполяционных псевдоупорядоченных колец. Для главных выпуклых направленных идеалов в интерполяционных псевдоупорядоченных кольцах доказан аналог третьей теоремы о порядковых изоморфизмах колец. Исследованы свойства множества всех выпуклых направленных идеалов частично псевдоупорядоченных алгебр над частично упорядоченными полями. Развита теория топологических радикалов Джекобсона, в том числе, для неассоциативных алгебр (в квазирегулярном и модульном вариантах определения). Этот вклад продолжает более раннее исследование авторов по топологическим радикалам ассоциативных колец. Проведены исследования в теории топологических колец и модулей. Построена криптографическая схема на основе топологически неприводимых модулей. Введено понятие топологически первичных колец и идеалов, предложен новый топологический радикал колец. 3. Научные исследования по комбинаторной и алгебраической теории графов, актуальных для когнитивных систем, искусственного интеллекта и эпигенетических перестроек. Исследованы приложения графов Гротендика к доказательству интегрируемости в смысле Дэвиса диагонализуемых и недиагонализуемых матриц. Вычислены примеры пар Белого на приводимых кривых. Построено их вложение в компактификацию пространств модулей алгебраических кривых. Вычислены конкретные пары Фрида, слияние критических значений которых определяет найденные пары Белого. Посчитано количество детских рисунков с паспортами, близкими к регулярным паспортам типов (3,3,3), (2,4,4) и (2,3,6) до 40 ребер. Полученные результаты позволили сформулировать большое количество гипотез о производящих функциях количеств таких рисунков. Многие из этих последовательностей находятся в Online Encyclopedia of Integer Sequences (OEIS), они выражаются через тета-функции. 4. Исследования в компьютерной графике: построение трехмерных моделей изоповерхностей; построение оптимальных тетраэдрических сетей. Разработка алгоритмов сегментации, применение методов оптимизации при построении изображений с приложениями в медицине. В рамках проекта по разработке неинвазивного метода исследования кровоснабжения сердца пациента на основе результатов томографического обследования разрабатывалось и внедрялось программное обеспечение для практического решения этой задачи. В программе использовались различные алгоритмы восстановления изоповерхности и сегментации трехмерных объектов: как автоматические, так и интерактивные. Также были разработаны и реализованы алгоритмы удаления кальцинатов из просвета кровеносного сосуда. Был реализован алгоритм упрощения триангуляции поверхности трехмерного объекта с сохранением ее формы и топологии. 5. Разработка нейронных сетей и методов глубокого обучения для решения задач распознавания образов в условиях неполной или нечеткой визуальной информации. Исследования в области компьютерного/ машинного зрения/ машинного обучения, компьютерной графики и сжатия данных. В мире животных. В рамках данного проекта рассматриваются методы компьютерного зрения для наблюдения за животным миром, как крупных особей (свиней, коров и др.), так и мелких (крылатых насекомых). Целью анализа поведения свиней, коров является минимизация их контактов с человеком. В рамках анализа крупных животных (свиней) необходимо составить журнал поведения животного по видеоданным. Данный журнал впоследствии анализируется методами машинного обучения на предмет выявления зависимостей качественных характеристик (увеличение массы или надоя) от режима кормления и других вещей. В 2022 году разработанный проект был реализован на базе 3D-студии Maya как автоматизированная система рендеринга свиней и других объектов. Анализ «поведения» крылатых насекомых связан с целью восстановления траектории их полета. В данной задаче используются 4 высокочастотные камеры для съемки крылатых насекомых. В 2022 году были получены результаты с использованием традиционных методов цифрового анализа изображений, а именно – был восстановлен анализ механики полета. Спектральный анализ изображений В рамках данного проекта изучаются данные, полученные многоспектральной (от 4-х до 12-ти каналов) и гиперспектральной камерой (100 каналов), а также спектрометром (несколько сотен спектральных поддиапазонов). К многоспектральной съемке относится и спутниковая съемка Земли. Спутниковые данные позволяют определить также сорт древесной породы. Также он позволяет выявить засеянные культуры и спрогнозировать урожай. Например, пшеницы, ячменя и других. 6. Представления и информационные структуры. Проведен анализ применимости основных конструкций теории категорий (определений и основных теорем) к социально-экономическим объектам и их отношениям. Установлено их соответствие, достаточное для содержательного описания предметно-смысловых областей в терминах подхода, получившего в настоящих работах термин “категорный метод”. Категорный подход использован для описания инвестиционного цикла экономического воспроизводства, с выработкой принципов создания информационной системы автоматизированного управления предприятиями. 7. Студенческое конструкторское бюро. В рамках данного направления различные методы обработки аудио и визуальной информации переносятся на микросхемы. В частности, методы машинного обучения, компьютерного зрения и методы сжатия данных. В рамках данного проекта студентами была создана умная колонка на базе микроконтроллера raspberry pi. Данная колонка подключается к облачным сервисам/серверам для выполнения распознавания и синтеза речи, а также для самого непосредственного общения, т.е. формирование ответов по текстовым репликам пользователя. Набор создан в формате обучающего конструктора, который любой желающий может собрать и модифицировать под свои частные задачи. В рамках СКБ студенты взаимодействуют, создают различные аппаратные поделки. 8. Большинство результатов исследований внедрено в учебный процесс.
3 1 января 2023 г.-31 декабря 2023 г. Математические методы и алгоритмы теоретической информатики 2021-2025. Этап 3.
Результаты этапа: 1. Проведение исследований в области обработки больших данных. Создание новых и адаптация ранее созданных алгоритмов интеллектуального анализа данных. Были продолжены исследования в области анализа больших данных и разработки эффективных методов и алгоритмов искусственного интеллекта (ИИ). В частности: – были исследованы возможности применения векторных баз данных в крупномасштабных приложениях искусственного интеллекта, включая индексирование с помощью алгоритмов, основанные на деревьях (k-d-деревья) и на построении специального графа близости на объектах выборки (Hierarchical navigable small world); – с помощью расширения pgvector (version 0.5.X) для СУБД PostgreSQL разрабатывалась и адаптировалась к методам ИИ концепция, которая включает в себя представление объектов, таких как слова, документы или сущности, в виде векторов в многомерном пространстве (Word2Vec, GloVe, Doc2Vec). В рамках Научной школы МГУ "Мозг, когнитивные системы, искусственный интеллект" разрабатывались модели и алгоритмы создания генеративных моделей машинного обучения для оценки устойчивости моделей предсказания временных рядов с использованием архитектуры Temporal Fusion Transformers в PyTorch. Продолжены исследования в области градуированных вычислений в некоммутативных алгебрах. Получены эффективные способы вычисления скрещенных сверток в бигрупповых алгебрах, играющих роль сверток в групповых алгебрах для коммутативного случая. Изучена группа автоморфизмов бигрупповой алгебры. Автоморфизмы позволяют осуществлять быстрые вычисления произведений матриц, разложение матрицы на диагональную часть и ортогональную части, что, в свою очередь, дает эффективное вычисление обратной матрицы. Получены тесты на простоту натурального числа через рекурсивно определенные последовательности высоких порядков (аналог теста Фробениуса для рекурсивно определенных последовательностей второго порядка). Продолжено изучение больших многомерных данных с помощью представления в виде непрерывных объектов малой размерности. 2. Исследования в основаниях теоретической информатики. Доказано, что квазиунитарные полигоны над вполне простой полугруппой и квазиунитарные полигоны с нулём над вполне 0-простыми полугруппами являются канторовыми. Получена характеризация простых (в смысле подполигонов) и простых (в смысле конгруэнций) полигонов над вполне простыми полугруппами. Охарактеризованы конгруэнц-простые полигоны над прямоугольными группами. Доказано, что копроизведение конечного числа кохопфовых полигонов над произвольной полугруппой является кохопфовым. Описан способ построения любой конгруэнции свободного унара. Предложен способ кодирования квазипорядков и конгруэнций конечной цепи. Для исследования унаров полезны представления унаров некоторыми стандартными унарами аналогично представлениям групп матрицами, линейными операторами или подстановками. Доказано существование изоморфного вложения любого конечного унара в унар определенного вида. Предложен единый метод доказательства теорем о том, что как полугруппа всех преобразований, так и полугруппа всех частичных преобразований или полугруппа всех бинарных отношений (многозначных преобразований) множества определяют однозначно это множество. Простым следствием этих теорем является тот факт, что все автоморфизмы этих полугрупп внутренние. Доказано, что произвольное рефлексивное бинарное отношение на множестве определяется полугруппой всех сохраняющих его преобразований «почти однозначно». Вопрос о связи свойства полноты кольца и полноты его фактор-кольца является важным в теории топологических колец. Доказано, что любое локально ограниченное кольцо с хаусдорфовой топологией изоморфно фактор-кольцу некоторого полного топологического кольца. Предложен новый способ подсчёта числа всех неизоморфных строгих порядков на конечном множестве на основе идеи рассмотрения только топологически упорядоченных порядков, а также идеи вычисления канонических представителей для заданной орбиты на основе канонических представителей уровнем ниже. Для заданного вида бинарных отношений, не только строгих порядков, вычислена нижняя оценка этого числа, зависящая от количества всех отношений и количества орбит. Создано программное обеспечение на языке C++, реализующее вышеприведённые алгоритмы. Исследованы приложения консервативных многочленов и связанных с ними плоских деревьев к доказательству отсутствия интегрируемости матриц в смысле Дэвиса. Исследованы границы возможностей применения машинного обучения для вычисления пар Белого. Рассмотрена адаптированная модель. Посчитаны некоторые примеры. Получена полная характеризация линейных отображений неотрицательных матриц, сохраняющих индекс цикличности. Показано, что, в отличие от тропического случая, такие отображения автоматически инъективны. 3. Исследования в компьютерной графике: построение трехмерных моделей изоповерхностей; построение оптимальных тетраэдрических сетей. Проводилась работа в рамках проекта по созданию гидродинамической модели кровообращения в области сердца по данным компьютерной томографии пациента. Целью является неинвазивная диагностика ишемической болезни сердца и других проблем пациента, связанных с нарушением кровоснабжения сердечных мышц из-за стеноза и кальцинирования коронарных артерий. Главной целью было определение параметра ФРК (Фракционный Резерв Кровотока, или FFR), на основе которого в медицине решается вопрос о необходимости установки расширителя артерии (стента) в области стеноза. Исследовалась возможность определения параметра ФРК на основании только трехмерной геометрии сосудов без необходимости численного решения уравнений гидродинамики. При построении трехмерной модели исследовались два различных алгоритма: 1) создание воксельной модели, на основе которой строится триангуляция поверхности, которая затем сглаживается с помощью метода Таубина, основанного на применении к триангуляции дискретного оператора Лапласа; 2) применение ячеечного метода построения триангуляции изоповерхности, основанного на разбиении пространства на тетраэдры, при этом используется тетраэдрическая сеть Хан-Пуризма-Скала, обладающая наилучшим параметром Aspect Ratio из известных тетраэдрических сетей. Рассматривался также и комбинированный алгоритм построения триангуляции изоповерхности. В области компьютерной графики исследовались методы увеличения размера изображений с сохранением четкости линий, которые при применении традиционных методов кубической интерполяции расплываются. Рассматривался метод построения векторной модели изображения на основе выделения контуров, построенных по массиву пороговых значений, и плавному заполнению цветом пространства между контурами. Второй разрабатываемый метод основан на комбинации обычного пиксельного метода увеличения изображения путем бикубической интерполяции и векторного метода, основанного на определении контуров изображения, в которых нарушается его гладкость, с использованием алгоритма Canny Edge Detector и других подобных алгоритмов. 4. Разработка нейронных сетей и методов глубокого обучения для решения задач распознавания образов в условиях неполной или нечеткой визуальной информации. Исследования в области компьютерного/ машинного зрения/ машинного обучения, компьютерной графики и сжатия данных. Велись исследования в области оптимизации подборов гиперпараметров регрессионных и классификационных алгоритмов машинного обучения с использованием генетических алгоритмов. Получены работающие прототипы решения, позволяющие увеличить скорость подбора. В мире животных. В рамках данного проекта рассматриваются методы компьютерного зрения для наблюдения за животным миром, как крупных (свиней, коров и подобных), так и мелких (крылатых насекомых). В обоих случаях целью является снижение ручного труда по анализу изображений человеком к минимуму. Так, необходимо автоматизировать анализ поведение животных. В рамках анализа поведения крупных животных (свиней, финансировалось заказчиком) необходимо составить журнал поведения животного по видео данным. Видеоданные анализируются современными методами компьютерного зрения. В частности, предполагается применения принципов sim2real, когда обучающая выборка синтезируется 3D-студией, а потом используется на реальных данных. Данный журнал впоследствии анализируется методами машинного обучения на предмет выявления зависимостей качественных характеристик (увеличение массы или надоя) от режима кормления и других вещей. В 2022 ПО было закодировано на базе 3D-студии Maya автоматизированная система рендеринга свиней и других объектов. В 2023 был написан код по автоматическому формированию разметки по задачам определения положения объекта (свиней) на изображении. Были запущены нейросетевые методы на базе такой разметки. Спектральный анализ изображений. В рамках данного проекта изучаются данные полученные многоспектральной (каналов 4, а то и 12) и гиперспектральной камерой (сотня каналов), а также спектрометром (несколько сотен спектральных поддиапазонов). К многоспектральной съемке относится и спутниковая съемка Земли. Данные изучаются на предмет выявления определенных эффектов или распознавания объектов. Например, выявление картофельных болезней и сорта по съемке БПЛА. Последнее важно для соответствующих хозяйств. В частности, важна именно ранняя диагностика болезней, а не когда уже все видно и человеку. Определение сорта важно для выявления однородности урожая в поле, т.е. вычисления объема примеси. Спутниковые данные позволяют определить сорт древесной породы. Фактически выполнить таксацию лесного массива дистанционно. Также он позволяет выявить засеянные культуры и спрогнозировать урожай. Например, пшеница, ячменя и других. 5. Представления и информационные структуры. Исследования приложений теории категорий (ТК) до настоящего времени являются узко направленными, и проводятся специалистами прикладных областей для обобщения и концептуального охвата накопленных знаний. Нами делается попытка последовательного переноса идей и образов теории категорий на широкий ряд областей знаний и практической деятельности исходя из того, что математика является адекватным средством отражения реальности во всех её проявлениях. Областями категорного анализа в настоящих работах являются физика, химия, биология, экология, социология и экономика. Полученные результаты: – установлена применимость основных конструкций теории категорий (определений и основных теорем) к социально-экономическим объектам и их отношениям; – категорный подход использован для анализа социальных и бизнес-экосистем. 6. В рамках студенческого конструкторского бюро. В рамках СКБ студенты взаимодействуют, создают различные аппаратные изделия. В частности, различные методы обработки аудио и визуальной информации переносятся на «железо». К ним относятся методы машинного обучения, компьютерного зрения и методы сжатия данных. В рамках СКБ студентами была создана умная колонка на базе микроконтроллера «raspberry pi». Данная колонка подключается к облачным сервисам/серверам для выполнения распознавания и синтеза речи, а также для самого непосредственного общения, т.е. формирование ответов по текстовым репликам пользователя. Набор создан в формате обучающего конструктора (при поддержке Наносемантики). В рамках выполнения исследования по данному проекту также был рассмотрен и вариант на базе микроконтроллера ESP 8266. Исследование показало, что, в целом, система может быть доведена до готового решения. Необходимо лишь решить ряд технических проблем. В 2023 был выигран конкурс грантов с проектом "Исследование интеллектуальной робототехнической системы, оснащенной ветроэнергетической установкой и предназначенной для работы в удаленных локациях". Изучена и настроена система симуляции для проведения исследований в её рамках, а не в реальности. Чат-бот "Знайка". Чат-боты постепенно все чаще встречаются в нашей жизни. Целевые чат боты пишутся под конкретную задачу. В частности, строится план/скрипт общения с различными ветвлениями и циклами в зависимости от того или иного действия пользователя. Для построения текстовых реплик используется информация из баз данных. В ряде случаев, необходимо быстро построить такого робота. В частности, такое было летом 2021 года по теме ковида. В рамках взаимодействия с аналитическим центром была необходимость быстрого построения робота по базе данных. Цель разработки системы чат-бота заключалась в сокращении нагрузки на операторов, путем автоматизации сценарных запросов, другими словами, перевод обращения пользователя в SQL-запрос, результаты которого визуализировались той или иной форме и возвращались пользователю. Для этого разрабатывается чат-бот, который настраивается под произвольную базу данных (пока был рассмотрен только частный случай, MVP).
4 1 января 2024 г.-31 декабря 2024 г. Математические методы и алгоритмы теоретической информатики 2021-2025. Этап 4.
Результаты этапа:
5 1 января 2025 г.-31 декабря 2025 г. Математические методы и алгоритмы теоретической информатики 2021-2025. Этап 5.
Результаты этапа:

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

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