Курс «Построение и анализ алгоритмов»

Читается в осенне-весеннем семестре 2011 года УНК «ИПСА» НТУУ «КПИ» в рамках факультативного цикла «Программная инженерия».

Курс рассказывает о техниках анализа и разработки эффективных алгоритмов с упором на решение практических программистских задач. Среди рассматриваемых тем будут сортировки и деревья, динамическое программирование и алгоритмы на графах, вычислительная геометрия и строковые алгоритмы, а также многое другое.

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

Лекторы:

Второй семестр

Расписание

Дата Тема Лектор Аудитория
TBA Лекция 3-1 TBA 210-35

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

Модуль 3. Алгоритмы на графах
  1. Графы. Варианты записи графа. Поиск циклов. Поиск в ширину (BFS), в глубину (DFS) и топологическая сортировка. Связность графа. Двудольный граф
  2. Жадные алгоритмы. Задача минимального остова (MST). Алгоритм Прайма. Алгоритм Краскала
  3. Кратчайшие пути I. Свойства и применение. Алгоритм Дейкстры
  4. Кратчайшие пути II. Алгоритм Беллмана-Форда. Задача разностных ограничений
  5. Кратчайшие пути III. Все пары вершин. Алгоритм Флойда-Уоршолла. Алгоритм Джонсона. Транзитивное замыкание
Модуль 4. Дополнительные темы
  1. Задача минимума на отрезке (RMQ) и решение корневой декомпозицией. Дерево отрезков
  2. Offline и online версии задачи RMQ. Задача SRMQ
  3. Задача наименьшего общего предка (LCA). Сведение LCA к RMQ
  4. Сбалансированные деревья. Пример реализации вставки в AVL
  5. Декартово дерево (Treap)
  6. Порядковые статистики. Динамические порядковые статистики
  7. Конкурентый анализ на примере самоупорядочивающихся списков
  8. Вычислительная геометрия I. Векторное представление. Выпуклая оболочка
  9. Вычислительная геометрия II. Точка в полигоне. Площадь полигона. Метод заметания
  10. Строковые алгоритмы I. Префикс-функция. Z-функция. Хэширование
  11. Строковые алгоритмы II. Бор. Алгоритм Рабина-Карпа
  12. Максимальные поток и минимальный разрез. Алгоритм Форда-Фалкерсона. Паросочетания

Задачи

  1. Модуль 3
  2. Модуль 4

Лабораторные работы

  1. Модуль 3
  2. Модуль 4

Первый семестр

Расписание

Дата Тема Лектор Аудитория
29.09 Лекция 1-1 А. Полозов 62-14
06.10 Лекция 1-2 О. Смирнов 147A-16
13.10 Лекция 1-3 О. Смирнов 147А-16
20.10 Лекция 1-4 А. Полозов 147А-16
27.10 Лекция 1-5 О. Смирнов 147А-16
3.11 Лекция 1-6 Д. Кордубан 147А-16
10.11 Лекция 1-7 Д. Кордубан 147А-16
17.11 Лаба 1 А. Полозов 147А-16
24.11 Лекция 2-1 О. Смирнов 147А-16
1.12 Лекция 2-2 А. Полозов 147А-16
8.12 Лекция 2-3 О. Смирнов 147А-16
15.12 Лекция 2-4 А. Полозов 147А-16

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

Модуль 1. Анализ алгоритмов
  1. Обзор курса. Анализ алгоритмов. Сортировка вставкой (Insertion sort) и сортировка слиянием (Merge sort). Бинарный поиск
  2. Асимптотическая нотация. Анализ рекуррентные соотношений. Основная теорема
  3. Парадигма «Разделяй и властвуй». Быстрое возведение в степень. Числа Фибоначчи. Алгоритм Евклида
  4. Стеки и очереди. Пирамидальная сортировка (Heapsort). Очереди с приоритетами. Сортировка Quicksort
  5. Сортировка за линейное время. Сортировка подсчётом (Counting sort). Поразрядная сортировка (Radix sort)
  6. Рандомизированные алгоритмы
  7. Хэширование и хэш-функции. Идеальное хэширование
Модуль 2. Построение алгоритмов
  1. Динамическое программирование I. Задача поиска наибольшей общей подстроки (LCS), задача о кратчайшем двунаправленном пути, задача о наибольшей возрастающей подпоследовательности (LIS), задача о выдаче сдачи
  2. Динамическое программирование II. Задача о ранце, задача о покрытии шахматной доски
  3. Двоичные поисковые деревья. Обход дерева и варианты записи дерева. Связь с Quicksort
  4. Амортизационный анализ. Реализация динамических таблиц (Vector) и cистемы непересекающихся множеств (Disjoint-set)

Задачи

  1. Модуль 1
  2. Модуль 2

Лабораторные работы

  1. Модуль 1
  2. Модуль 2

Экзамен

  1. TBA