Алгоритмы на графах

v.1.0 (2017.12.17)

Презентации

  1. Algorithm is not a 4-letter word (by Jamis Buck).
  2. Представление графов (с примерами кода).
  3. Поиск на графе. DFS, BFS, IDDFS.
  4. Кратчайшие пути и минимальный остов.
  5. Алгоритмы на основе поиска в глубину. Пример реализации алгоритма топологической сортировки: код.
  6. Эйлеровы и гамильтоновы циклы.
  7. Максимальный поток в сети.
  8. Раскраски и паросочетания. Пример распределённого алгоритма раскраски: код.

Задания

  1. Представления графов.
  2. Разработка и реализация алгоритмов.
  3. Реализация алгоритмов (старое).
  4. Разработка и реализация алгоритмов (старое).

Что не вошло

  1. Направленный и ограниченный поиск (особенно на потенциально бесконечных неявно заданных графах) [best-first/B*, depth-limited/IDA*/fringe, breadth-limited, beam, D*, jump point…]
  2. Двунаправленный поиск (есть в заданиях), обобщение на взвешенные графы.
  3. Теорема Сэвитча. Алгоритм определения существования пути между двумя вершинами, использующий O(logN)-память.
  4. Задача о наиболее длинном пути.
  5. Дерево доминаторов.
  6. Алгоритм Орлина (максимальный поток за O(|V||E|)).
  7. Способы решения задачи о циркуляции.
  8. Проверка графа на планарность и построение плоской укладки.
  9. Раскраска планарного графа в 4 цвета.
  10. Рёберная раскраска (алгоритм Мисры-Гриса).
  11. Правильная раскраска по списку, задачи удовлетворения ограничений.
  12. Наибольшие паросочетания в произвольных графах (алгоритм Эдмондса).
  13. Разбиения графов.
  14. Инварианты графов.
  15. Рандомизация и стохастические методы оптимизации для нахождения субоптимальных решений NP-трудных задач на графах. Применение общих методов оптимизации стохастического типа (генетический алгоритм, имитация отжига, метод муравьиной колонии, поиск кукушки и т.д.).
  16. Визуализация графов.
  17. Вопросы распараллеливания алгоритмов на графах.

Литература

  1. О. Оре. Теория графов.
  2. Ф. Харари. Теория графов.
  3. Н. Кристофидес. Теория графов. Алгоритмический подход.
  4. Р. Седжвик. Фундаментальные алгоритмы на C++. Часть 5: алгоритмы на графах.
  5. Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн. Алгоритмы: построение и анализ.
  6. Дж. Макконнелл. Основы современных алгоритмов.
  7. А. Ахо, Дж. Хопкрофт, Дж. Ульман. Структуры данных и алгоритмы.
  8. А. Ахо, Дж. Хопкрофт, Дж. Ульман. Построение и анализ вычислительных алгоритмов.
  9. Асанов М.О., Баранский В.А., Расин В.В. Дискретная математика: графы, матроиды, алгоритмы.

В уже размещённые файлы периодически вносятся правки и дополнения, поэтому рекомендуется по возможности просматривать их онлайн, а не сохранять.
Если возникли какие-либо вопросы или замечания, можно оставить их в комментарии.

↓ Старая версия ↓

  1. Списки смежности, поиск в ширину.
  2. Минимизация на матрице весов.
  3. Эйлеровы и гамильтоновы циклы.
  4. Максимальный поток в сети.
  5. Паросочетания.
Реклама

Добавить комментарий

Заполните поля или щелкните по значку, чтобы оставить свой комментарий:

Логотип WordPress.com

Для комментария используется ваша учётная запись WordPress.com. Выход / Изменить )

Фотография Twitter

Для комментария используется ваша учётная запись Twitter. Выход / Изменить )

Фотография Facebook

Для комментария используется ваша учётная запись Facebook. Выход / Изменить )

Google+ photo

Для комментария используется ваша учётная запись Google+. Выход / Изменить )

Connecting to %s

%d такие блоггеры, как: