Графы/практика

v.0.24 (2017.04.24)

Презентации

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

Задания

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

Литература

  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 такие блоггеры, как: