Поиск кратчайших путей в дорожных сетях: от теории к реализации
Осень 2016, посмотреть все семестры

Курс даёт уникальную возможность познакомиться с методологией разработки прикладных алгоритмов на конкретной задаче поиска кратчайших путей в дорожных сетях. В ходе курса будут изучаться и реализовываться алгоритмы, используемые миллионами людей в таких сервисах, как Google/Bing/Yandex карты. Предварительный план курса:

  1. Введение в методологию разработки прикладных алгоритмов.
  2. Алгоритм Дейкстры. Двунаправленный алгоритм Дейкстры.
  3. Алгоритм флагов на ребрах.
  4. Алгоритм контракционной иерархии.
  5. Алгоритм меток хабами.
  6. Кратчайшие пуи в условиях динамических изменений графа.
  7. Задача поиска кратчайшего пути от нескольких вершин к нескольким.
Для получения аттестации по курсу необходима реализация графовой структуры данных на языке C++, алгоритма Дейкстры, двунаправленного алгоритма Дейкстры, алгоритма флагов на ребрах и контракционной иерархии.

Дата и время Название Место Материалы
05 ноября
17:20–18:55
Лекция 1. Введение в методологию разработки прикладных алгоритмов, лекция ПОМИ РАН слайдывидео
05 ноября
19:15–20:50
Лекция 2. Обзорная лекция по материалу курса, лекция ПОМИ РАН слайдывидео
06 ноября
11:15–12:50
Лекция 3. Алгоритм Дейкстры и его варианты, лекция ПОМИ РАН слайдывидео
06 ноября
13:00–14:35
Лекция 4. Алгоритм Arc Flags, лекция ПОМИ РАН слайдывидео
06 ноября
15:30–17:00
Лекция 5. Алгоритм Контракционная Иерархия, лекция ПОМИ РАН слайдывидео
26 ноября
17:20–18:55
Лекция 6, лекция ПОМИ РАН Нет
26 ноября
19:15–20:50
Лекция 7, лекция ПОМИ РАН Нет
27 ноября
11:15–12:50
Лекция 8, лекция ПОМИ РАН Нет
27 ноября
13:00–14:35
Лекция 9, лекция ПОМИ РАН Нет
27 ноября
15:30–17:00
Лекция 10, лекция ПОМИ РАН Нет