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

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

Описание

Курс знакомит слушателей с базовыми алгоритмическими приёмами и структурами данных. В частности, мы узнаем следующее:

  • Почему не стоит вычислять числа Фибоначчи рекурсивно.
  • Как отсортировать массив размера n за время \(O(n\log n)\) и почему в общем случае быстрее сделать не получится.
  • Как послать закодированное сообщение другу так, чтобы только он мог его раскодировать, при условии, что канал прослушивается.
  • Как умножать числа быстрее, чем школьным методом в столбик.
  • Как предобработать Войну и мир так, чтобы потом иметь возможность почти мгновенно ответить на вопрос, сколько раз в тексте встречается заданное слово.
  • Как динамическое программирование используется в геномике.
  • Как двоичное дерево поиска может самобалансироваться в процессе добавления, удаления и даже поиска элемента.
  • Когда имеет смысл действовать жадно.
  • Как быстро найти кратчайший путь в графе.
  • Как подкидывание монетки может помочь алгоритму работать быстрее.
  • Как найти пару ближайших точек на плоскости, не проверяя при этом все пары точек.
  • Почему за решение некоторых алгоритмических задач обещан миллион долларов.

Дедлайны:

  • теоретическое доказательство: 21 ноября
  • домашние задания: 28 ноября
  • code review: 9 декабря
  • упражнения: 16 декабря

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

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

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

Элементарные структуры данных

Абстрактные типы данных, интерфейс и реализация. Стек, очередь, дек; моделирование на основе массива и связного списка, визуализации: стек на основе массива, стек на основе списка, очередь на основе массива, очередь на основе списка. Моделирование очереди с помощью двух стеков. Односвязный список, двусвязный список. Корневое дерево: бинарное дерево, дерево с произвольным ветвлением, представление левый ребёнок — правый сосед. Массивы переменного размера: аддитивная и мультипликативная схемы реаллокации. Анализ учётных стоимостей операций: функция потенциала, истинные и учётные стоимости.

Введение

Вычисление чисел Фибоначчи: экспоненциальный рекурсивный алгоритм, полиномиальный алгоритм, более детальный анализ (арифметические и битовые операции), визуализация. Время работы алгоритма, O-символика. Скорость роста функций: логарифм, полином, экспонента.

Метод "разделяй и властвуй"

Метод разделяй и властвуй. Умножение n-битовых чисел: простой рекурсивный алгоритм, улучшенный рекурсивный алгоритм. Рекуррентные соотношения: основная теорема. Двоичный поиск. Сортировка слиянием: с рекурсией и без, визуализация.

Сортировка

Нижняя оценка \(\Omega(nlogn)\) для сортировки сравнениями. Сортировка с помощью кучи: очередь с приоритетами, построение кучи за линейное время, частичная сортировка, визуализация.

Сортировка (продолжение)

Быстрая сортировка: анализ среднего времени работы, анализ глубины рекурсии, элиминация хвостовой рекурсии, IntroSort, массивы с малым количеством различных элементов, QuickSort3. Сортировка подсчётом, устойчивость. Цифровая сортировка. Сравнения различных сортировок: визуализация 1, визуализация 2.

Порядковые статистики

Порядковые статистики, нахождение за линейное в среднем и худшем случае время.

Декомпозиция графов

Графы и способы их представления, способы использования графов. Поиск в глубину в неориентированных графах, выделение компонент связности. Поиск в глубину в ориентированных графах (визуализация): ориентированные ациклические графы, топологическая сортировка вершин — с помощью поиска в глубину (визуализация) и с помощью массива входящих степеней вершин (визуализация), наличие стока и истока в ациклическом графе, выделение компонент сильной связности (визуализация).

Пути в графах

Нахождение кратчайших путей из одной вершины в невзвешенных графах, поиск в ширину (визуализация). Нахождение кратчайших путей из одной вершины в графах с положительными весами, алгоритм Дейкстры (визуализация), оценка времени работы при различных реализациях очереди с приоритетами (массивом, двоичной кучей, d-чной кучей). Нахождение кратчайших путей из одной вершины в графах, в которых есть рёбра отрицательного веса, алгоритм Беллмана-Форда, проверка наличия цикла отрицательного веса.

Жадные алгоритмы

Задача о выборе заявок. Минимальное покрывающее дерево: свойство разреза, жадная стратегия, алгоритм Прима, алгоритм Краскала.

Система непересекающихся множеств

Представление множеств с помощью деревьев, эвристика сжатия путей, верхняя оценка \(O(mlogn)\) на время работы \(m\) операций.

Жадные алгоритмы (продолжение)

Коды Хаффмена. Хорновские формулы. Задача о покрытии множествами.

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

Общие принципы динамического программирования, часто используемые подзадачи. Кратчайшие пути в ациклических ориентированных графах. Наибольшая возрастающая подпоследовательность: подзадачи, порядок на подзадачах, граф подзадач, сравнение с рекурсивным алгоритмом; нахождение не только длины, но и самой подпоследовательности. Редакционное расстояние: граф на подзадачах, нахождение кратчайшего пути в данном графе; нахождение оптимального выравнивания с использованием линейной памяти.

Динамическое программирование (продолжение)

Задача о рюкзаке: рюкзак с повторениями и без, ленивые вычисления. Перемножение последовательности матриц. Независимые множества в деревьях. Кратчайшие пути: кратчайшие пути между всеми парами вершин (алгоритм Флойда-Уоршолла, алгоритм Джонсона), задача о коммивояжёре.

Деревья поиска

Дерево поиска: поиск, вставка, удаление, поиск следующего и предыдущего элемента за время, пропорциональное высоте. АВЛ-дерево: верхняя оценка \(O(logn)\) на высоту, сохранение свойства при помощи малых и больших вращений.