Алгоритмы и структуры данных, часть 2
Санкт-Петербург, весна 2014
Описание
Будем продолжать изучать базовые алгоритмы. Узнаем метод динамического программирования, алгоритмы на строках (z-функция, КМП, Ахо-Корасик, суффиксное дерево, суффиксный массив, неточный поиск), сбалансированные деревья (АВЛ, сплей, декартово), задачи RMQ и LCA, быстрое преобразование Фурье, теорию NP-полноты.
В данном курсе нет записи лекций, видео можно смотреть в курсе 2012 года (весна).
Преподаватели
Список лекций
Наибольшая возрастающая подпоследовательность. Задача о рюкзаке. Перемножение последовательности матриц. Независимые множества в деревьях.
Расстояние редактирования. Алгоритм Хиршберга.
Наивный алгоритм, алгоритм Карпа-Рабина, Z-функция, поиск образца с одной ошибкой, алгоритм Кнута-Морриса-Пратта
Определения суффиксного массива и суффиксного дерева. Решение задачи о поиске длиннейшей общей подстроке. LCP-массив. Построение суффиксного массива за $O(n\log n)$.