Введение в курс

Тема 1. Основные сведения из теории графов

• 1.1. Графы и матрицы (33мин.)
• 1.2. Маршруты, пути, цепи и циклы (33мин.)
• 1.3. Расстояния, радиусы и диаметры (33мин.)
• 1.4. Деревья (33мин.)
• 1.5. Подграфы и остовы (199мин.)
• Тест:  Основные сведения из теории графов (10мин.)

Тема 2. Минимальные стягивающие деревья и алгоритм Ярника - Прима

• 2.1. Биномиальные пирамидальные очереди (233мин.)
• 2.2. Тонкие (фибоначчиевы) кучи (100мин.)
• Тест:  Минимальные стягивающие деревья и алгоритм Ярника - Прима (10мин.)

Тема 3. Алгоритм Краскала. Быстрые алгоритмы сортировки

• 3.1. Деревья с прямыми ребрами на плоскости (66мин.)
• 3.2. Быстрые алгоритмы сортировки (33мин.)
• 3.3. Сортировка слиянием (66мин.)
• 3.4. Быстрая сортировка (33мин.)
• 3.5. Сортировка малых натуральных чисел (33мин.)
• 3.6. Лексикографическая сортировка (100мин.)
• Тест:  Алгоритм Краскала. Быстрые алгоритмы сортировки (10мин.)

Тема 4. Алгоритмы Дейкстры, Форда - Беллмана - Мура, Флойда для нахождения кратчайших путей в графе

• 4.1. Поиск в ширину и его применение для нахождения кратчайших путей в графах с малыми натуральными весами (133мин.)
• 4.2. Кратчайшие пути в графах с произвольными весами ребер. Алгоритм Форда-Беллмана-Мура (299мин.)
• 4.3. Поиск в глубину, топологическая сортировка ациклических графов и поиск кратчайших и длиннейших путей в них (133мин.)
• 4.4. Календарное планирование (66мин.)
• 4.5. Арбитражные сделки и отрицательные циклы (33мин.)
• 4.6. Нахождение кратчайших путей между всеми парами вершин графа. Алгоритм Флойда (100мин.)
• 4.7. Алгоритм поиска кратчайших расстояний между всеми парами вершин для ориентированных неплотных графов (66мин.)
• Тест:  Алгоритмы Дейкстры, Форда - Беллмана - Мура, Флойда для нахождения кратчайших путей в графе (10мин.)

Тема 5. О вычислении транзитивного замыкания графа

• 5.1. Еще о быстром умножении булевых матриц (100мин.)
• 5.2. Булево умножение матриц на RAM-машинах (66мин.)
• 5.3. Сравнение с алгоритмом "четырех русских" (33мин.)
• Тест:  О вычислении транзитивного замыкания графа (10мин.)

Тема 6. О быстрых алгоритмах линейной алгебры

• 6.1. Алгоритм Штрассена быстрого умножения матриц (100мин.)
• 6.2. Ускорение метода Штрассена (100мин.)
• 6.3. О быстрых алгоритмах арифметики (133мин.)
• 6.4. Несколько замечаний о практическом применении быстрых вычислительных алгоритмов (100мин.)
• Тест:  О быстрых алгоритмах линейной алгебры (12мин.)

Тема 7. Потоки в сетях

• 7.1. Непересекающиеся пути в графах (66мин.)
• 7.2. Паросочетания в двудольных графах (133мин.)
• Тест:  Потоки в сетях (12мин.)

Тема 8. Некоторые задачи вычислительной геометрии

• 8.1. Алгоритмы вычислительной геометрии (399мин.)
• 8.2. Кратчайшие сети Штейнера (199мин.)
• Тест:  Некоторые задачи вычислительной геометрии (10мин.)

Тема 9. Задача коммивояжера

• 9.1. Метод ветвей и границ (66мин.)
• 9.2. Алгоритмы локальной минимизации (33мин.)
• 9.3. Динамическое программирование для коммивояжера (66мин.)

Список рекомендуемой литературы

Завершение курса

• Тест:  Итоговое тестирование (34мин.)