Читается в осенне-весеннем семестре 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