6 апреля (пятница) в 17 часов в 610 аудитории состоится семинар кафедры алгебры и математической логики.
Докладчик: Кочкаров Р.А. (Институт проблем управления РАН им. В.А. Трапезникова; Финансовый университет при Правительстве РФ)
Название доклада: “Многокритериальные задачи на многовзвешенных предфрактальных графах”
Аннотация: В настоящее время появился интерес не только к динамике распространения информации в статичной сети, но и к изменяющейся во времени структуре связей. Графы с изменяющимися во времени связями называют динамическими графами. Одним из подклассов динамических графов являются фрактальные (предфрактальные) графы – графы большой размерности со свойствами самоподобия. По сути, предфрактальные графы сформировались в отдельный класс графов со своей теорией и самостоятельными методами исследования. В науке и практике имеется потребность обработки графов большой размерности (больших графов), решение задач классическими методами теории графов требует значительного увеличения вычислительных возможностей компьютерной техники. Моделирование задач посредством класса предфрактальных графов и использование специализированных методов решения позволяет сократить время обработки графов. В докладе рассматривается общая постановка многокритериальной задачи дискретной оптимизации на предфрактальном графе с многими весами, в том числе с недетерминированными. Применяются три типа весов – интервальные числа, нечеткие множества и временные ряды. Также рассматриваются классы индивидуальных задач (выделения кратных центров и медиан, остовных лесов и др.), предлагается подход к типовой и структурной классификации модельных задач на предфрактальных графах. Рассматриваются алгоритмы решения индивидуальных задач с расчетами вычислительной сложности и гарантированными оценками. В целом формируется подход к разработке полиномиальных алгоритмов, покрывающих классы индивидуальных задач. В виде приложения предфрактальных графов предлагаются некоторые теоретико-графовые модели (теоретико-графовая модель распространения эпидемии, интервальная модель крупномасштабной кластеризации материи, топологическая модель сети интернет).