Алгоритмы и структуры данных, часть 2

Санкт-Петербург, весна 2014

Описание

Будем продолжать изучать базовые алгоритмы. Узнаем метод динамического программирования, алгоритмы на строках (z-функция, КМП, Ахо-Корасик, суффиксное дерево, суффиксный массив, неточный поиск), сбалансированные деревья (АВЛ, сплей, декартово), задачи RMQ и LCA, быстрое преобразование Фурье, теорию NP-полноты.

В данном курсе нет записи лекций, видео можно смотреть в курсе 2012 года (весна).

Преподаватели

Список лекций

Динамическое программирование

Наибольшая возрастающая подпоследовательность. Задача о рюкзаке. Перемножение последовательности матриц. Независимые множества в деревьях.

Динамическое программирование

Расстояние редактирования. Алгоритм Хиршберга.

Поиск образца в тексте, базовые алгоритмы

Наивный алгоритм, алгоритм Карпа-Рабина, Z-функция, поиск образца с одной ошибкой, алгоритм Кнута-Морриса-Пратта

Суффиксный массив, суффиксное дерево

Определения суффиксного массива и суффиксного дерева. Решение задачи о поиске длиннейшей общей подстроке. LCP-массив. Построение суффиксного массива за $O(n\log n)$.