Проекты

Коллектив факультета постоянно развивает свой исследовательский потенциал регулярно выполняя фундаментальные и прикладные научно-исследовательские проекты, поддержанные Минобрнауки и российскими научными фондами. Кроме штатных сотрудников к выполнению проектов привлекаются аспиранты и студенты.


2019

Проект РФФИ №17-07-00823
Разработка и анализ моделей и алгоритмов адаптивной организации передачи данных в коммуникационных сетях динамической структуры

Проект посвящен разработке новых архитектур и алгоритмов сетей передачи данных. Исследуются особенности адаптивной мультиагентной маршрутизации в децентрализованных сетях динамической структуры. Примерами подобных систем являются ad hoc сети, mesh-сети, сенсорные сети, специальные виды радиосетей подвижных объектов и т.п. Новые методы, разрабатываемые в рамках проекта, позволят повысить эффективность и надежность таких систем за счет использования строгих математических подходов к разработке моделей и анализу их семантических свойств. В качестве основного инструмента будет использована теория формальных моделей, и, в частности, моделирование мультиагентных систем при помощи алгебр процессов, сетей Петри и формализмов на их основе. Конкретными задачами проекта являются:

  • создание математических языков моделирования и спецификации различных аспектов целевых систем;
  • разработка эффективных мультиагентных схем адаптивной маршрутизации;
  • выработка и обоснование методологии тестирования и верификации целевых систем.

Грант Президента Российской Федерации для молодых кандидатов наук МК-2620.2018.1
Комбинаторно-геометрический анализ труднорешаемых задач

Многогранник комбинаторной задачи определяется как выпуклая оболочка характеристических векторов всех возможных допустимых решений. Полиэдральным графом задачи называется граф, вершинами которого являются вершины многогранника, а рёбрами – геометрические рёбра, т.е. одномерные грани. Исследованию полиэдральных графов комбинаторных задач посвящено значительное число работ. С одной стороны, смежность вершин в полиэдральном графе представляет наибольший интерес для непосредственной разработки алгоритмов решения задач, основанных на методе локального поиска (когда от текущего решения переход осуществляется к «лучшему» решению среди смежных). На этой идее основаны, например, различные алгоритмы для задачи о совершенном паросочетании, покрытии множества, независимом множестве, ранжировании объектов, задачи с нечёткими мерами и многие другие. С другой стороны, различные характеристики полиэдрального графа задачи, такие как диаметр и кликовое число, служат оценками сложности для различных моделей вычислений и классов алгоритмов.
Объектом исследования выступал полиэдральный граф многогранника задачи коммивояжёра. Известно, что для полиэдрального графа коммивояжёра задача проверки несмежности вершин является NP-полной (Пападимитриу 1978), кликовое число графа сверхполиномиально по размерности пространства (Бондаренко, 1983), а диаметр графа не превосходит 4 (Рисполи, Косарес, 1998).
Гамильтонов цикл называется пирамидальным, если коммивояжёр начинает в городе с номером 1, посещает некоторые города в порядке возрастания номером, достигает города n и возвращается в исходный, проходя все оставшиеся города в порядке убывания номеров. Пирамидальная задача коммивояжёра – один из наиболее известных полиномиально разрешимых частных случаев задачи коммивояжёра (Гилмор, Лоулер, Шмойс, 1985). В рамках проекта установлено, что для многогранника пирамидальных циклов проверка смежности вершин в полиэдральном графе выполняется за линейное время, диаметр графа равен 2, найдена асимптотически точная квадратичная оценка на кликовое число графа, которая соответствует сложности алгоритма динамического программирования для пирамидальных циклов.
Класс пирамидальных циклов с шагами назад является расширением понятия пирамидальных циклов. Коммивояжёру разрешается нарушать порядок возрастания и убывания городов, но с выполнением дополнительных ограничений. Как и для пирамидальных циклов, минимальный пирамидальный цикл с шагами назад может быть найден алгоритмом динамического программирования за полиномиальное время (Еномото, Ода, Ота, 1998). В рамках проекта описаны необходимые и достаточное условия смежности вершин в полиэдральном графе многогранника пирамидальных циклов с шагами назад, проверка которых выполняется за полиномиальное время. Таким образом, свойства многогранников пирамидальных циклов и пирамидальных циклов с шагами назад похожи, и они принципиально отличаются от свойств многогранника общей задачи коммивояжёра.
Известно, что задача проверки несмежности вершин в многограннике задачи коммивояжёра NP-полна (Пападимитриу, 1978). Достаточное условие несмежности вершин можно сформулировать в виде комбинаторной задачи: если из рёбер двух гамильтоновых циклов можно собрать два дополнительных гамильтоновых цикла, то соответствующие вершины многогранника коммивояжёра не смежны. Отметим, что рассматриваемая задача близка к задаче гамильтоновой декомпозиции (разбиении графа на гамильтоновы циклы), которая активно применяется в криптографии.
Для проверки достаточного условия несмежности в рамках проекта был разработан эвристический алгоритм имитации отжига с односторонней ошибкой: если алгоритм возвращает «не смежны», то это всегда верный ответ. Алгоритм работает как с ориентированными, так и с неориентированными графами. В основе лежит подход с построением покрытия мультиграфа циклами без общих вершин и поиск совершенного паросочетания. По результатам тестирования алгоритм показал хорошие практические результаты.
Эвристический алгоритм был реализован в виде программы для ЭВМ «TSPVertexAdjacency – научно-исследовательская программа для проверки смежности вершин в многограннике задачи коммивояжёра» (свидетельство о государственной регистрации № 2019610324 от 10 января 2019 года).

2017

грант Президента РФ для молодых кандидатов наук
Методы автоматизации построения специализированных тезаурусов с использованием анализа контекста

Целью проекта является создание гибридных методов автоматизации построения специализированного тезауруса, развитие критериев и методов оценки качества автоматически генерируемых тезаурусов, требующих минимального участия экспертов.

Целью первого этапа работ, выполненного в 2016 году, являются выработка критериев оценки качества автоматически генерируемых тезаурусов, не использующих эталонный тезаурус, создание гибридных методов и методики автоматизированного построения тезауруса на основе выбора наилучшего тезауруса с точки зрения разработанных критериев оценки, построение программного прототипа для автоматизированного построения тезаурусов.
На данном этапе исследований предложена комплексная оценка качества узкоспециализированного тезауруса. Оценка включает в себя набор статистических характеристик и параметров связности тезауруса. Следует отметить, что качество тезауруса сильно зависит от набора его связей: чем больше семантических отношений в тезаурусе и чем выше его связность, тем лучше результаты дает информационный поиск с его участием. Соответствующие параметры оцениваются независимо от эталонного тезауруса и в комплексе со статистическими характеристиками позволяют оценить тезаурус как единое целое, что, дает возможность более эффективно разрабатывать методы построения самого тезауруса.

Исследованы методы выделения множества терминов тезауруса. Показано, что методы использующие обучение без учителя оптимально подходят для задачи максимально автоматизировать построение тезауруса, поскольку показывают результаты лишь немного хуже, чем алгоритмы использующие обучение с учителем. Также исследованы методы выделения связей между терминами тезауруса. Показано, что для выделения гиперонимов достаточно хороши два метода, основанные на морфо-синтаксических правилах и тезаурусе WordNet. Кроме того качество выделения гипонимо-гиперонимических связей для всех методов оказалось довольно невысоким. Для определения ассоциативных связей хорошие результаты показал метод LSA (Latent Semantic Analysis). Следует отметить, что существующие методы относительно эффективны в извлечении определенных типов отношений, но недостаточно хороши для построения тезауруса в целом.

На данном этапе проекта предложена идея гибридных методов, представляющих собой различные комбинации существующих алгоритмов выделения синонимических и иерархических отношений между терминами. Эксперименты показали, что преимущество гибридных методов при выделении обоих типов связей заключается в увеличении полноты, при этом точность выделения терминов и связей не ухудшается, кроме того повышается связность итогового тезауруса.

На основе предложенных методов и комплексной оценки тезауруса разработан программный стенд, полностью автоматически генерирующий и оценивающий тезаурус. Стенд позволяет исследовать методы выделения терминов тезауруса и выделения связей между ними.

2016

грант РФФИ №16-37-50035-мол_нр
Модели и алгоритмы повышения уровня защищенности программного обеспечения информационно-телекоммуникационных систем Интернета вещей от атакующих воздействий на основе клиент-серверного подхода

В процессе разработки и внедрения информационных технологий все более острой становится проблема построения защищенных распределенных кибер-физических информационных систем. Особенностью, характеризующей информационный процесс, протекающий в таких системах, является необходимость обеспечения повышенных требований по безопасности обрабатываемой информации и предоставляемых информационно-технических сервисов. Наличие этих требований обуславливается разнородностью входящих в состав системы встроенных устройств, программно-аппаратных компонентов, сенсоров и способов коммуникаций и представления данных, различиями в режимах работы устройств системы и сценариях ее применения, а также увеличением с течением времени числа угроз информационной безопасности (ИБ). При этом стоит также отметить постоянное возрастание рисков ИБ при работе таких систем, а также появление новых средств программно-технического воздействия.

Целью исследований является повышение уровня защищенности программного обеспечения информационно-телекоммуникационных систем Интернета вещей от атакующих воздействий на основе применения клиент-серверного подхода к организации защиты устройств. Проект ориентирован на построение и практическое применение комбинированных механизмов защиты программного обеспечения от атакующих воздействий для широкого круга систем, которые реализуют принципы и механизмы концепции Интернет вещей. Характерный пример такой системы - система «Интеллектуальный дом», позволяющая при помощи беспроводных Wi-Fi соединений организовать совместную и согласованную работу узкоспециализированных устройств, различных сенсоров и служб для автоматизации, контроля и управления объектами инфраструктуры квартиры, дома или офисного пространства.

В рамках проекта были получены новые результаты в области разработки и реализации систем, использующих концепцию Интернета вещей. В условиях активного развития отраслей, использующих концепцию Интернета вещей, актуальна проблема информационной безопасности. Для того чтобы определить актуальные угрозы, необходимо использовать детальный анализ рисков в соответствии с действующими стандартами ГОСТ. Выбирая защитные меры, необходимо учитывать все идентифицированные актуальные угрозы информационной безопасности. В результате были определены актуальные угрозы и защитные меры, необходимые для разработки и внедрения защищенного фрагмента программно-аппаратной системы Умный дом в части контроля доступа в помещение. Решены следующие задачи: описание системы Умный дом, описание этапов оценки и обеспечения безопасности системы Умный дом; осуществление аппаратной сборки и написания программного кода для выбранного фрагмента системы; оценка безопасности выбранного фрагмента Умного дома и определение актуальных угроз; выработка рекомендаций по противодействию актуальным угрозам; программная реализация одной из актуальных угроз и программная реализация защитных мер для выбранной угрозы. Особенностью работы является комплексный подход к проектированию с использованием моделей нарушителя, анализа активов системы и оценки их защищенности.

грант РФФИ №14-01-00333-А
Исследование комбинаторно-геометрических свойств труднорешаемых задач

Важным направлением в исследовании комбинаторно геометрических свойств труднорешаемых задач является изучение свойств полиэдральных графов задач. При полиэдральном анализе задач с неотрицательным данными как правило изучается полиэдр задачи, который получается как сумма многогранника задачи и положительно ортанта, а также связанная с ним конструкция неотрицательного конусного разбиения пространства. В конусном разбиении каждой вершине полиэдра ставится в соответствие неотрицательный конус, содержащий все возможные целевые вектора, достигающие минимума или максимума на этой вершине. Вершины полиэдра будут смежны тогда и только тогда, когда смежны их конусы (два конуса имеют общую гипергрань). Известно, что кликовое число или плотность (размер максимальной клики) графа конусного разбиения служит нижней оценкой на сложность задачи в широком классе алгоритмов «прямого типа», основанных на линейных сравнениях, включающем алгоритмы сортировки, жадные алгоритмы, динамическое программирование, метод ветвей и границ и др. В рамках проекта исследовались полиэдральные графы задач об остовном дереве при дополнительных ограничениях на степени вершин, число листьев и диаметр искомого дерева, задачи о максимальном разрезе, а также задач о сбалансированном и несбалансированном двудольных подграфах.

Установлено, что задача о минимальном остовном дереве и задачи об остовном дереве с дополнительными ограничениями имеют принципиально отличные полиэдральные характеристики. Для классической задачи известны полиномиальные алгоритмы, построено полное внешнее описание многогранника с полиномиальным числом неравенств, полностью описан полиэдральный граф задачи, и установлено, что его плотность полиномиальна по размерности пространства. При этом задачи с дополнительными ограничениями являются труднорешаемыми, для них не найдено полного внешнего описания соответствующих многогранников, полиэдральные графы задач являются крайне сложными: даже проверка смежности вершин является NP-полной задачей, плотности графов сверхполиномиальны по размерности пространства.

Для задачи о максимальном разрезе в графе с неотрицательными весами ребер найдено точное экспоненциальное значение кликового числа графа конусного разбиения, которое значительно улучшает ранее полученные оценки. Задачи о построении оптимальных двудольных подграфов исследовались многими авторами и имеют множество практических применений. В частности, в вычислительной биологии для бикластеризации генов строится двудольный граф, в одну долю которого помещаются гены, а во вторую их свойства, и требуется построить наибольшую биклику. Для задач о сбалансированном подграфе с произвольными весами и несбалансированных подграфах минимального и максимального веса с неотрицательными весами установлены NP-полнота задач и сверхполиномиальные плотности графов многогранников и конусных разбиений.

Во всех рассмотренных случаях полиэдральные характеристики коррелируют со сложностью задачи.

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

Выполнена отработка программного обеспечения в составе опытного образца аппаратно-программных средств сетеориентированной кроссплатформенной системы распределенной обработки и криптозащищенного обмена информацией.  

По результатам отработок разработаны предложения по созданию перспективной аппаратной платформы аппаратуры полносвязной радиосети множественного доступа с распределенным управлением. Предложения разработаны в виде:
- схемно-технические решения, схем электрических принципиальных (соединения) и перечней элементов узлов аппаратной платформы;
- конструктивно-технических решений, данных проектирования печатных плат, данных для разработки конструкции узлов аппаратной платформы.

грант РФФИ №15-07-03038-А
Исследование и разработка методов и средств организации высокоскоростных беспроводных автоконфигурируемых сетей подвижных объектов

Цель исследования – решение задачи создания универсального и переносимого программного обеспечения для операционных систем на базе ядра Линукс, обеспечивающего организацию и функционирование беспроводной сети с высокой пропускной способностью, объединяющей подвижные равноправные объекты.

В качестве ключевого параметра системы маршрутизации рассматриваемой беспроводной подвижной mesh-сети введен т.н. коэффициент доступности узла – функция, зависящая от ряда основных и дополнительных параметров ("mesh-факторов"), характеризующих маршрут между двумя узлами сети. Этот композитный параметр сопоставляется каждой паре (дуга, узел) с целью охарактеризовать "доступность" узла по маршруту, начинающемуся данной дугой. Лучшим ("кратчайшим") маршрутом между двумя узлами считается маршрут с наибольшим коэффициентом доступности.

Описаны правила построения и обновления таблиц маршрутизации узлами сети. Получая анонс от соседа, узел имеет сведения об энергетике соединения, надежности соединения, времени получения анонса, отсутствии промежуточных узлов, а также располагаемой пропускной способности. На основании этой информации ко всем маршрутам, проходящим через данного соседа, может быть применена пенализация (наложение штрафа) или поощрение (увеличение коэффициента доступности). Указанная схема пенализации / поощрения складывается из отдельных аспектов:

  • Пенализация за актуальность информации.
  • Пенализация / вознаграждение за надежность узла.
  • Пенализация за энергетику соединения.
  • Пенализация за располагаемую пропускную способность.

Кроме того, на основании предложенных эвристических алгоритмов разработано следующее программное обеспечение:
– симулятор сети;
– подсистема организации mesh-сети и многофакторной маршрутизации в ней для беспроводного стека Линукс.

Разработан алгоритм адаптивной многопутевой маршрутизации в сенсорных сетях.
В ходе реализации проекта были рассмотрены отдельные аспекты координационной функции для беспроводной mesh-сети с равноправными и, возможно, мобильными узлами и с множественным доступом с временным разделением (TDMA).

На основе разработанных подходов реализована распределенная координационная функция, обеспечивающая организацию (за конечное время) сети с множественным доступом на основе временного разделения произвольной топологии в полностью автоматическом режиме; поддержку ее реконфигурации в связи с изменением топологии и числа узлов; постоянную синхронизацию узлов в сети.
Основные аспекты, присущие полученному решению:
– аппаратная независимость реализации;
– наличие реализации для оборудования семейства стандартов 802.11;
– самоконфигурация сети произвольной топологии;
– поддержка изменения топологии сети / числа узлов в процессе функционирования сети в полностью автоматическом режиме.

грант Президента РФ для молодых кандидатов наук
Релаксационные многогранники труднорешаемых задач

Одной из основных парадигм при разработке алгоритмов для труднорешаемых задач является релаксация линейного программирования: задача сводится к задаче целочисленного программирования на многограннике, который возникает при снятии ограничения целочисленности с переменных, фигурирующих в задаче.
Объектом исследования в рамках проекта выступали метрический многогранник MET(n), который является релаксацией многогранника CUT(n) задачи о разрезе в графе, а также многогранник SATP(m,n) и его релаксация SATP_LP(m,n).

Рассматриваемый многогранник SATP(m,n) представляет особый интерес для изучения, так как различные постановки задачи 3-выполнимость, в том числе максимальная 3-выполнимость, 3-выполнимость при различных литералах и 3-выполнимость при одном истинном литерале, сводятся к задаче целочисленного программирования или распознавания целочисленности на SATP(m,n). Задача распознавания целочисленности отвечает на вопрос: верно ли, что максимум линейной целевой функции достигается в целой вершине многогранника.

В качестве основного результата описан полиномиальный алгоритм решения задачи распознавания целочисленности на многограннике SATP_LP(m,n) для целевых функций специального вида. Алгоритм основан на двойном применении линейного программирования и дополнительных O(mn(m+n)) шагах для восстановления искомой целой точки. С помощью сведения к задаче распознавания целочисленности на SATP_LP(m,n) построен полиномиальный алгоритм для частного случая задачи о раскраске двудольного графа с ограничениями по ребрам на комбинации цветов.

Метрический многогранник MET(n) определяется наиболее простыми гипергранями разрезного многогранника CUT(n) вида «неравенств треугольника». Известно, что он является плотной релаксацией разрезного многогранника: все вершины, ребра и двумерные грани, а также большинство d-мерных граней CUT(n) являются гранями MET(n).

Большое число работ посвящено исследованию нецелочисленных вершин метрического многогранника. Однако, полного описания множества нецелочисленных вершин до сих пор не построено. Наиболее подробно изученным является класс графических вершин метрического многогранника, порождаемых метрикой на графах.

В рамках проекта описаны новые классы графов, порождающих графические вершины метрического многогранника, и разработана научно-исследовательская программа для построения графических вершин метрического многогранника «GraphicVerticesMaker». Программа на основе метрики на графе находит координаты соответствующей точки метрического многогранника. Проверка является ли построенная точка вершиной осуществляется с помощью алгоритма ic-раскраски графа: ребра графа разбиваются на классы эквивалентности, если они являются противоположными в некотором изометрическом цикле. На выходе программа пошагово расписывает построение всех классов эквивалентности и выделяет их различными цветами на графе.

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

В рамках проекта были получены следующие результаты:

1. Предложены новые классы сингулярно возмущенных дифференциально-разностных уравнений с запаздыванием вольтерровского типа, с помощью которых описывается функционирование как отдельного нейрона, так и нейронных сетей.

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

3.  Для некоторого достаточно общего класса диффеоморфизмов кольца установлен  так называемый принцип кольца, т.е. предлагается набор достаточных условий, при которых каждый диффеоморфизм из приведенного класса имеет странный гиперболический аттрактор типа соленоида Смейла-Вильямса.

4. Показано сосуществование в цепочке нейронов ФитцХью-Нагумо с резисторно-индуктивными связями между соседними элементами при подходящем увеличении количества ее звеньев любого конечного числа устойчивых двумерных инвариантных торов.

5. Для сингулярно возмущенной системы двух дифференциальных уравнений с запаздыванием, моделирующей два связанных автогенератора с нелинейной обратной связью, доказано существование релаксационных периодических решений и условия их устойчивости.

6. Разработан и зарегистрирован пакет программ TracerRet, предназначенный для интерактивного моделирования распределенных задач с запаздыванием на вычислительном кластере.

Полученные в ходе выполнения проекта результаты предназначены для использования биологических идей при разработке моделей нейронных сетей, наделенных новыми свойствами, и применении методов нелинейной динамики, в том числе метода большого параметра, для исследования динамические свойства таких сетей.

Результаты проекта могут быть использованы как для построения нейронных ассоциаций с максимально большим числом сосуществующих аттракторов (моделирование ассоциативной памяти), так и для изучения особенностей решений типа импульсных пакетов (моделирование процесса передачи информации между нейронами или нейронными ассоциациями). Полученные результаты, очевидным образом, применимы к широкому классу физических и биологических моделей.





  • 35
    лет факультету
  • Более 2000
    выпускников
Подавать сертификаты ЕГЭ вместе с другими документами не нужно, ваши баллы будут проверяться в федеральной базе.