Алгоритмы и структуры данных, часть 1
Санкт-Петербург, осень 2016
Описание
Описание курса
Вы наверняка замечали, что некоторые программы работают не очень быстро (говоря профессиональным языком, тормозят
). Часто это бывает связано с тем, что в программе используются неэффективные алгоритмы и структуры данных. Этот курс поможет вам не совершать таких ошибок.
В рамках нашего курса вы, например, узнаете,
- как узнать, быстро будет работать программа или нет, еще до того, как она написана,
- как хранить данные так, чтобы можно было быстро найти нужное значение,
- как умножать числа быстрее, чем школьным методом в столбик,
- как найти пару ближайших точек на плоскости, не проверяя при этом все пары точек,
- как оптимально собирать рюкзак в дорогу (на самом деле нет, но почти).
Первые шесть недель лекции будут идти в формате онлайн-курса, далее вживую. Семинары будут идти вживую в течение всего курса.
Преподаватели
Список лекций
Список, двусвязный
Динамический массив
Стек, очередь, дек (на списках, на массиве)
Минимум на очереди
Удаление из кучи и списка: обратные ссылки
Хранение графа (матрица смежности, список рёбер)
Собственно dfs (алгоритм, время работы, поиск компонент связности)
Классификация рёбер для оррафа, неорграфа: прямые, обратные, перекрёстные
Топологическая сортировка. Определение, алгоритм за время O(V+E).
Покраска в два цвета
Алгоритм поиска цикла в ориентированном графе (бело-серо-чёрный dfs), только орграф! неор будет на практике
Сильная связность: определение, наивный алгоритм за O(VE), алгоритм за O(V+E)
- Поиск мостов и компонент рёберной двухсвязности за \(O(V+E)\)
- Поиск точек сочленения и компонент вершинной двухсвязности за \(O(V+E)\)
- Эйлеров путь, цикл: критерий эйлеровости, алгоритм поиска за \(O(V+E)\)
- 2-SAT, решение за \(O(V+E)\)
bfs
Дейкстра
Флойд
Форд-Беллман
Отрицательные циклы
Джонсон
- DSU на списках за $O(m + n\log n)$ (с доказательством)
- DSU на ссылках к корню за $O((m+n)A^{-1}(n,m))$
- Алгоритм Краскала (сортировка + DSU)
- Алгоритм Прима (аналог Дейкстры)
- Доказываем $O(\log*n)$ на запрос для второго из DSU
Дерево отрезков с операциями сверху
- Построение за O(n), изменение в точке, запрос на отрезке
- Модификация на отрезке
- Динамическое дерево отрезков (координаты до $10^9$)
Идея сканирующей прямой. Обработка событий. На примере задачи: найти самую длинную цепочку точек, возрастающую по обеим координатам.
Дерево отрезков с операциями снизу
Дерево Фенвика для функции на префиксе
- Универсальное семейство хеш-функций
- Совершенное хеширование (двухуровневая схема)
- Хеш-таблица на списках
- Хеш-таблица с открытой адресацией
- Куку-хеширование (без доказательства)
- Приближённое решение задачи о set cover. $\ln n$-прибилижение.
- Приближённое решение задачи о коммивояжёре через MST. $2$-прибилижение и $1.5$-прибилижение.