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

Санкт-Петербург, осень 2016

Описание

Описание курса

Вы наверняка замечали, что некоторые программы работают не очень быстро (говоря профессиональным языком, тормозят). Часто это бывает связано с тем, что в программе используются неэффективные алгоритмы и структуры данных. Этот курс поможет вам не совершать таких ошибок.

В рамках нашего курса вы, например, узнаете,

  • как узнать, быстро будет работать программа или нет, еще до того, как она написана,
  • как хранить данные так, чтобы можно было быстро найти нужное значение,
  • как умножать числа быстрее, чем школьным методом в столбик,
  • как найти пару ближайших точек на плоскости, не проверяя при этом все пары точек,
  • как оптимально собирать рюкзак в дорогу (на самом деле нет, но почти).

Первые шесть недель лекции будут идти в формате онлайн-курса, далее вживую. Семинары будут идти вживую в течение всего курса.

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

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

Базовые структуры данных
  • Список, двусвязный

  • Динамический массив

  • Стек, очередь, дек (на списках, на массиве)

  • Минимум на очереди

  • Удаление из кучи и списка: обратные ссылки

Графы. Поиск в глубину
  • Хранение графа (матрица смежности, список рёбер)

  • Собственно dfs (алгоритм, время работы, поиск компонент связности)

  • Классификация рёбер для оррафа, неорграфа: прямые, обратные, перекрёстные

  • Топологическая сортировка. Определение, алгоритм за время O(V+E).

  • Покраска в два цвета

  • Алгоритм поиска цикла в ориентированном графе (бело-серо-чёрный dfs), только орграф! неор будет на практике

  • Сильная связность: определение, наивный алгоритм за O(VE), алгоритм за O(V+E)

Поиск в глубину, часть 2
  • Поиск мостов и компонент рёберной двухсвязности за \(O(V+E)\)
  • Поиск точек сочленения и компонент вершинной двухсвязности за \(O(V+E)\)
  • Эйлеров путь, цикл: критерий эйлеровости, алгоритм поиска за \(O(V+E)\)
  • 2-SAT, решение за \(O(V+E)\)
Кратчайшие пути
  • bfs

  • Дейкстра

  • Флойд

Крачтайшие пути, часть 2
  • Форд-Беллман

  • Отрицательные циклы

  • Джонсон

MST и DSU
  • 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\)-прибилижение.