Читается в осенне-весеннем семестре 2011 года УНК «ИПСА» НТУУ «КПИ» в рамках факультативного цикла «Программная инженерия».
Курс рассказывает о техниках анализа и разработки эффективных алгоритмов с упором на решение практических программистских задач. Среди рассматриваемых тем будут сортировки и деревья, динамическое программирование и алгоритмы на графах, вычислительная геометрия и строковые алгоритмы, а также многое другое.
Программа базируется на курсе «6.046: Introduction to Algorithms» Массачусетского технологического института и на учебниках Т. Кормена, Р. Седжвика и А. Шеня.
Лекторы:
Второй семестр
Расписание
|
Дата
|
Тема
|
Лектор
|
Аудитория
|
|
TBA
|
Лекция 3-1
|
TBA
|
210-35
|
Конспект лекций
Модуль 3. Алгоритмы на графах
- Графы. Варианты записи графа. Поиск циклов. Поиск в ширину (BFS), в глубину (DFS) и топологическая сортировка. Связность графа. Двудольный граф
- Жадные алгоритмы. Задача минимального остова (MST). Алгоритм Прайма. Алгоритм Краскала
- Кратчайшие пути I. Свойства и применение. Алгоритм Дейкстры
- Кратчайшие пути II. Алгоритм Беллмана-Форда. Задача разностных ограничений
- Кратчайшие пути III. Все пары вершин. Алгоритм Флойда-Уоршолла. Алгоритм Джонсона. Транзитивное замыкание
Модуль 4. Дополнительные темы
- Задача минимума на отрезке (RMQ) и решение корневой декомпозицией. Дерево отрезков
- Offline и online версии задачи RMQ. Задача SRMQ
- Задача наименьшего общего предка (LCA). Сведение LCA к RMQ
- Сбалансированные деревья. Пример реализации вставки в AVL
- Декартово дерево (Treap)
- Порядковые статистики. Динамические порядковые статистики
- Конкурентый анализ на примере самоупорядочивающихся списков
- Вычислительная геометрия I. Векторное представление. Выпуклая оболочка
- Вычислительная геометрия II. Точка в полигоне. Площадь полигона. Метод заметания
- Строковые алгоритмы I. Префикс-функция. Z-функция. Хэширование
- Строковые алгоритмы II. Бор. Алгоритм Рабина-Карпа
- Максимальные поток и минимальный разрез. Алгоритм Форда-Фалкерсона. Паросочетания
Задачи
- Модуль 3
- Модуль 4
Лабораторные работы
- Модуль 3
- Модуль 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. Анализ алгоритмов
- Обзор курса. Анализ алгоритмов. Сортировка вставкой (Insertion sort) и сортировка слиянием (Merge sort). Бинарный поиск
- Асимптотическая нотация. Анализ рекуррентные соотношений. Основная теорема
- Парадигма «Разделяй и властвуй». Быстрое возведение в степень. Числа Фибоначчи. Алгоритм Евклида
- Стеки и очереди. Пирамидальная сортировка (Heapsort). Очереди с приоритетами. Сортировка Quicksort
- Сортировка за линейное время. Сортировка подсчётом (Counting sort). Поразрядная сортировка (Radix sort)
- Рандомизированные алгоритмы
- Хэширование и хэш-функции. Идеальное хэширование
Модуль 2. Построение алгоритмов
- Динамическое программирование I. Задача поиска наибольшей общей подстроки (LCS), задача о кратчайшем двунаправленном пути, задача о наибольшей возрастающей подпоследовательности (LIS), задача о выдаче сдачи
- Динамическое программирование II. Задача о ранце, задача о покрытии шахматной доски
- Двоичные поисковые деревья. Обход дерева и варианты записи дерева. Связь с Quicksort
- Амортизационный анализ. Реализация динамических таблиц (Vector) и cистемы непересекающихся множеств (Disjoint-set)
Задачи
- Модуль 1
- Модуль 2
Лабораторные работы
- Модуль 1
- Модуль 2
Экзамен
- TBA