Курс «Алгоритмы: построение и анализ»

Прочитан осенью 2008-го - весной 2009-го года в GL-Клубе компании Global Logic, Украина.

img 

Программа базируется на курсе «6.046: Introduction to Algorithms» Массачусетского технологического института и на одноимённом учебнике Т. Кормена, Ч Лейзерсона, Р. Ривеста и К. Штайна.

Лекторы:

Рассылка курса: http://groups.google.com/group/kiev-clrs

Конспект лекций

Раздел 1. Анализ алгоритмов
  1. Анализ алгоритмов. Сортировка вставкой и сортировка слиянием
  2. Корректность алгоритма. Схема Горнера
  3. Асимптотическая нотация. Рекуррентные соотношения
  4. Парадигма «Разделяй и властвуй»: алгоритм Штрассена, алгоритм Фибоначчи, умножение матриц
  5. Сортировка Quicksort. Рандомизированные алгоритмы
  6. Пирамидальная сортировка. Очереди с приоритетами
  7. Сортировка за линейное время: нижние оценки, сортировка подсчётом, поразрядная сортировка
  8. Медианы и порядковые статистики
  9. Применение медиан. Блочная сортировка
Раздел 2. Разработка алгоритмов
  1. Хэширование. Хэш-функции
  2. Универсальное хэширование. Идеальное хэширование
  3. Двоичные поисковые деревья. Обход дерева
  4. Связь поискового дерева и Quicksort. Анализ рандомизированного алгоритма
  5. Красно-чёрные деревья. Алгоритмы вращения, вставки, удаления
  6. 2-3 деревья. B-деревья
  7. Расширение структур данных. Динамические порядковые статистики. Деревья отрезков
  8. Деревья расстояний
  9. Списки с пропусками (слоёные списки)
  10. Амортизационный анализ. Динамические таблицы. Метод потенциалов
  11. Конкурентный анализ: самоупорядочивающиеся списки
  12. Конкурентный анализ: задача аренды лыж
  13. Динамическое программирование. Задача о наибольшей общей подпоследовательности
Раздел 3. Алгоритмы на графах
  1. Жадные алгоритмы. Минимальные остовные деревья
  2. Кратчайшие пути: свойства, алгоритм Дейкстры, поиск в ширину
  3. Кратчайшие пути: алгоритм Беллмана-Форда, линейное программирование, ограничения на разности. Поиск в глубину в графе. Топологическая сортировка
  4. Кратчайшие пути: все пары вершин, умножение матриц, алгоритм Флойда-Уоршолла, алгоритм Джонсона
Раздел 4. Дополнительные темы
  1. Параллельные алгоритмы
  2. Параллельные алгоритмы, часть 2