2019:2020 Spring - Algocourse/info GitHub Wiki

Занятия проходят по субботам в аудитории В-117. Время: 10:15.

Занятие 3. 14 марта 2020.

• Поиск мостов и точек сочленения. Алгоритм с использованием DFS.
• Топологическая сортировка графа.
• Идея Meet-in-the-middle.

Задание:

• Задача на топологическую сортировку.
• Задача на поиск мостов.
• Задача на Meet-in-the-middle.

Занятие 2. 7 марта 2020.

• Нахождение кратчайших путей между всеми парами вершин. Алгоритм Флойда-Уоршелла.
• Поиск кратчайшего пути во взвешенном графе. Алгоритм Форда-Беллмана. Конспект.
• Поиск цикла отрицательного веса алгоритмом Форда-Беллмана.

Задание:

• Задачи A, С и D из тренировки.
• Задача A, B и C из тренировки.
• Контест.

Занятие 1. 29 февраля 2020.

• Графы. Основные понятия.
• Поиск в ширину.
• Поиск в глубину.
• Дерево обхода в глубину.
• Поиск кратчайшего пути во взвешенном графе с неотрицательными ребрами. Алгоритм Дейкстры.

Задание:

• Поиск в глубину. Задачи.
• Поиск в ширину. Задачи.
• Задачи на Дейкстру - задача F и G из тренировки.
• Задача Транспортировка.
• Задача Короткий путь.
• Задача Пути и деревья.