Задачи дискретной многокритериальной оптимизации на динамических (предфрактальных) графах

Кочкаров Р.А.

13.03.18, Вторник, 17:00, ИПМ им. М.В.Келдыша РАН, Главный корпус, подвал, ауд. №9 (бывшая №4)

Базовый семинар: Будущее прикладной математики

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

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

 

Следующий семинар: 10.04.2018 - О проблеме моделирования образования сажи при диффузионном горении углеводородных топлив на основе жестких систем обыкновенных дифференциальных уравнений Колмогорова (докладчик: Исаев А.В.).

Предыдущий семинар: 20.02.2018 - Изучение социальной структуры России с помощью кластерного анализа базы RLMS-HSE (докладчик: Алексеев А.А.).