Рассказова Варвара Андреевна

  • Главная -
  • Рассказова Варвара Андреевна
page.title

Рассказова Варвара Андреевна

Учёная степень Кандидат физико-математических наук
Должность старший преподаватель

Область научных интересов

  • Теория графов, исследование операций
  • Целочисленное линейное программирование

Приложения полученных научных результатов

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

Основные научные результаты

  • Эвристический алгоритм решения задачи о независимом множестве с абсолютной оценкой точности приближенного решения

Информация для студентов дипломников (темы потенциальных дипломных работ с аннотацией, презентации защищенных дипломных работ)

  • Задача о декомпозиции путей сильно связного ориентированного графа и ее приложение в организации грузовых железнодорожных перевозок

Аннотация. Разработка эвристического многокритериального алгоритма декомпозиции путей ориентированного сильно связного графа и его реализация в задаче организации грузовых железнодорожных перевозок на этапе назначения и перемещения заданного множества локомотивов. Исследование задачи на предмет снижения размерности по сравнению с исходной постановкой.

  • Сравнительный анализ эффективности различных алгоритмов поиска наибольшего независимого множества вершин неориентированного графа

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

  • Метод покрытия вершин ориентированного графа для решения прикладных задач о назначениях

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

  • Очередь с приоритетом в задаче о независимом множестве и ее приложение в оперативном планировании грузовых железнодорожных перевозок

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

Информация для студентов практикантов (темы потенциальных заданий на практику с аннотацией, типовые отчеты практикантов по защищенным практикам)

  • Теория NP-полноты и техника сведéния

Исследование классов задач поиска, оптимизации и разрешения. Решение в частных классах полиноминально разрешимых задач. Доказательство NP-полноты некоторых классических задач. Исследование проблемы P=NP на примере «взлома» криптосистемы RSA

  • Приближенные алгоритмы и оптимизация перебора для решения NP-полных задач

Перебор с возвратом и метод ветвей и границ для решения NP-полных задач. Реализации приближенных алгоритмов для решения задачи коммивояжера в приложении к задаче о дереве Штейнера

  • Эвристики локального поиска

Алгоритмы решения типовых NP-полных задач. Программная реализация, тестирование на DIMACS

  • Транспортные сети и транспортные задачи

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

Гранты, конференции

Секционные доклады:

  1. Всероссийская научная конференция «Управление большими системами – 2016»
  2. Международная научная конференция «Математика, информатика и физика, и их приложения в науке и образовании – 2016»
  3. Международная научная конференция «Гагаринские чтения – 2016, 2017»
  4. Международная научная конференция «Системный анализ, управление и навигация – 2016, 2017, 2018»
  5. Balkan Conference on Operational Research (BALCOR-2018)
  6. International Conference on Optimization Problems and Their Applications (OPTA-2018)
  7. International Conference Optimization and Applications (OPTIMA-2018, 2019, 2020)
  8. International Conference on Mathematical Optimization Theory and Operations Research (MOTOR – 2019, 2020)
  9. Learning and Intelligent Optimization Conference (LION – 2020)
  10. International Conference on Variable Neighborhood Search (ICVNS – 2020)

Пленарные доклады:

  1. Winter School on Data Analytics (DA-2018)

Публикации, документы и материалы

# Наименование Тип год
1 Математическое моделирование в задаче оптимального назначения и перемещения локомотивов методами теории графов и комбинаторной оптимизации Статья 2017