Алгоритмы и структуры данных, часть 1
Санкт-Петербург, осень 2014
Описание
Курс знакомит слушателей с базовыми алгоритмическими приёмами и структурами данных. В частности, мы узнаем следующее:
- Почему не стоит вычислять числа Фибоначчи рекурсивно.
- Как отсортировать массив размера $n$ за время $O(n\log n)$ и почему в общем случае быстрее сделать не получится.
- Как послать закодированное сообщение другу так, чтобы только он мог его раскодировать, при условии, что канал прослушивается.
- Как умножать числа быстрее, чем школьным методом
в столбик
. - Как предобработать
Войну и мир
так, чтобы потом иметь возможность почти мгновенно ответить на вопрос, сколько раз в тексте встречается заданное слово. - Как динамическое программирование используется в геномике.
- Как двоичное дерево поиска может самобалансироваться в процессе добавления, удаления и даже поиска элемента.
- Когда имеет смысл действовать жадно.
- Как быстро найти кратчайший путь в графе.
- Как подкидывание монетки может помочь алгоритму работать быстрее.
- Как найти пару ближайших точек на плоскости, не проверяя при этом все пары точек.
- Почему за решение некоторых алгоритмических задач обещан миллион долларов.
Первые шесть недель лекции шли в формате онлайн-курса, а семинары читались вживую. Видео и слайды с онлайн курса опубликованы в занятиях-лекциях в курсе. Все видео онлайн-курса можно найти на канале CS центра на YouTube. Остальные лекции курса (с седьмой недели живые лекции) не записывались, по ссылке можно найти лекции 2011 года и смотреть их.
Литература
- S. Dasgupta, C. Papadimitriou, U. Vazirani. Algorithms. McGraw-Hill. 2006.
- А. Х. Шень. Программирование: теоремы и задачи. Издательство МЦНМО. 2007.
- М. А. Бабенко, М. В. Левин. Введение в теорию алгоритмов и структур данных. Издательство МЦНМО. 2012.
- Т. Кормен, Ч. Лейзерсон, И. Ривест, К. Штайн. Алгоритмы: построение и анализ.
Для получения оценки по курсу нужно
Прошлогодние правила осень, весна.
Правила этого года. Если коротко: сдать онлайн курс, сдать задачи в Я.Контест, пройти CodeReview по одной из задач в Я.Контест
Преподаватели
Список лекций
Очные лекции проводились с 30 октября 2015. До 30 октября студенты сдавали онлайн-курс на Stepic. На данной странице опубликованы материалы первой недели онлайн-курса.
Очные лекции проводились с 30 октября 2015. До 30 октября студенты сдавали онлайн-курс на Stepic. На данной странице опубликованы материалы шестой недели онлайн-курса.
Поиск в ширину. Кратчайшие пути в графах с неотрицательными весами. Кратчайшие пути при наличии рёбер отрицательного веса.
Очные лекции проводились с 30 октября 2015. До 30 октября студенты сдавали онлайн-курс на Stepic. На данной странице опубликованы материалы второй недели онлайн-курса.
Умножение чисел. Алгоритм Карацубы. Рекуррентные соотношения. Умножение матриц.
Очные лекции проводились с 30 октября 2015. До 30 октября студенты сдавали онлайн-курс на Stepic. На данной странице опубликованы материалы третьей недели онлайн-курса.
Расширяющийся массив. Куча. Дерево отрезков. Системы непересекающихся множеств.
Очные лекции проводились с 30 октября 2015. До 30 октября студенты сдавали онлайн-курс на Stepic. На данной странице опубликованы материалы четвертой недели онлайн-курса.
Сортировка: простейшие алгоритмы и оценки. Сортировка кучей. Сортировка слиянием. Быстрая сортировка. Порядковые статистики.
Очные лекции проводились с 30 октября 2015. До 30 октября студенты сдавали онлайн-курс на Stepic. На данной странице опубликованы материалы пятой недели онлайн-курса.
Графы и способы их представления. Поиск в глубину в неориентированных графах. Поиск в глубину в ориентированных графах. Компоненты сильной связности.
dfs, кодим стандартные вещи
задачи на dfs
Задача о выборе заявок, задача о минимальном покрывающем дереве, коды Хаффмена, выполнимость Хорновских формул.
Решение задачи о максимальной возрастающей подпоследовательности за время $O(n^2)$. Решение задачи о нахождении расстояния редактирования за время и память $O(nm)$, уменьшения оценки на память до $O(\min{n,m})$ (алгоритм Хиршберга).
Задача о рюкзаке (с повторениями и без). Рекурсия с запоминанием (ленивая рекурсия). Оптимальная триангуляция многоугольника. Независимое множество в дереве максимального веса.
Повторение алгоритма, решающего задачу коммивояжёра за время $O(n^22^n)$ и память $O(n2^n)$. Алгоритм, находящий числов гамильтоновых циклов в графе за время $O^*(2^n)$ и полиномиальную память, основанный на формуле включений-исключений. Нахождение количества всех не обязательно простых путей заданной длины между заданными двумя вершинами с помощью метода динамического программирования и с помощью возведения матрицы смежности в степень.
Двочиное дерево поиска как структура, поддерживающая операции ${\tt Search}$, ${\tt Insert}$, ${\tt Delete}$, ${\tt Min/Max}$, ${\tt Succ/Pred}$, ${\tt LowerBound/UpperBound}$, ${\tt Statistics}$ за время, пропорциональное высоте дерева. Сравнение с хеш-таблицей. АВЛ-дерево: доказательство логарифмической оценки на высоту, малые и большие вращения.
Доказательство верхней оценки $O(\log n)$ на среднюю стоимость операций.
Построение декартова дерева за линейное время при предварительно отсортированных ключах, доказательство логарифмической оценки на глубину в среднем, основные операции через split и merge.
Решение задачи RMQ методом разреженной таблицы.