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

Новосибирск, осень 2020

Описание

Цели курса

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

Домашние задания

Оценка за курс выставляется по результатам домашних заданий. В ходе курса будет предложено N задач, разбитых на блоки. Сдаваться задачи будут на языке C++ в автоматизированную систему проверки — программа должна не только правильно работать, но и делать это быстро и эффективно по памяти и времени. Среди них будут М задач для «полного» решения — помимо исходного кода, нужно будет предоставить теоретическое решение, доказывающие корректность и эффективность программы, а также пройти код-ревью.

Данный курс почти полностью соответствует курсу Алгоритмы и структуры данных поиска Школы анализа данных Яндекса, который в Москве читает Максим Бабенко.

Критерии оценки

Оценка в осеннем семестре выставляется по двум параметрам: F — количество задач, успешно сданных по полной схеме, S — суммарное количество набранных баллов за сдачу задач.

Оценка выводится следующим образом:

  • отлично: (F ≥ 2 и S ≥ 1000) или (F ≥ 3 и S ≥ 700)
  • хорошо: (F ≥ 2 и S ≥ 700) или (F ≥ 3 и S ≥ 500)

  • зачет: (F ≥ 2 и S ≥ 500) или (F ≥ 3 и S ≥ 350)

Инструкция по сдаче заданий

Подробная инструкция к нашему курсу содержится в этом документе: https://yadi.sk/i/e9QaGunR3qLkRg

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

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

Лекция 1, Сложность и модели вычислений

Основные ресурсы: память и время. О-символика. Примеры моделей вычисления: машина Тьюринга, RAM-машина. Сложность в среднем и худшем случаях.

Анализ учетных стоимостей операций. Банковский метод. Метод потенциалов: функция потенциала, истинные и учетные стоимости. Задача о двоичном счетчике.

Массивы переменного размера: аддитивная и мультипликативная схемы реаллокации. Анализ мультипликативной схемы для массива переменного размера с помощью банковского метода.

Стеки и очереди. Реализация на основе массива переменного размера и на основе связанного списка. Моделирование очереди с помощью двух стеков.

Изменяемые (mutable) и неизменяемые (immutable) структуры данных. Структуры данных с хранением истории (persistent). Immutable-стек и immutable-очередь. Проблема множественного будущего при анализе учетных cтоимоcтей в persistent-структурах.

Лекция 2. Сортировки

Задача сортировки. Разрешающие деревья. Нижняя оценка сложности в модели разрешающих деревьев. Сортировка сравнениями. Понятия устойчивости и in-place. Понятие о методе «разделяй и властвуй»: quicksort и mergesort. Алгоритм Quick-Sort. Процедура Partition, два варианта её in-place реализации. Примеры неудачного выбора опорных элементов. Рандомизированный выбор опорного элемента. Сложность Quick-Sort в худшем и среднем случаях. Глубина рекурсии в худшем и среднем случаях. Подробности реализации (кратко): сортировка вставками для малых подмассивов, удаление хвостовой рекурсии, медиана трёх, переход к другому виду сортировки. Алгоритм Merge-Sort. Слияние двух упорядоченных списков. Оценка сложности. Нерекурсивная реализация. Сортировка слиянием без использования дополнительной памяти: swap вместо присваивания, использование части массива в качестве буфера, слияние с перекрыванием входа и выхода. Сортировка подсчётом. Поразрядная сортировка.

Лекция 3. Кучи (начало)

Понятие очереди с приоритетом. Деревья со свойствами кучи. Почти полные бинарные деревья: нумерация вершин, навигация. Двоичная куча. Операция просеивания вниз и вверх. Реализация операций вставки, удаления и поиска минимума. Сложность операций. Поддержание указателей на элементы кучи. Преобразование произвольного массива ключей в кучу (операция Make-Heap), линейность времени работы. k-ичные кучи, зависимость сложности операций от выбора k.

Лекция 4. Кучи (продолжение)

Биномиальные (binomial), левацкие (leftlist) и косые (skew) кучи.

Лекция 5. Порядковые статистики

Слияние двух упорядоченных последовательностей различной длины. Теоретико-информационная нижняя оценка. Бинарный поиск от края (galloping). Нахождение порядковых статистик с помощью рандомизированной модификации алгоритма Quick-Sort. Линейность матожидания времени работы. Приближенные медианы. Выбор k-й порядковой статистики за линейное в худшем случае.

Лекция 6. Хеширование

Хеш-функции. Коллизии. Разрешение коллизий методом цепочек, методом последовательных проб и методом двойного хеширования. Гипотеза простого равномерного хеширования, оценка средней длины цепочки. Универсальные семейства хеш-функций, оценка средней длины цепочки. Построение универсального семейства для целочисленных ключей. Совершенные хеш-функции. Построение совершенной хеш-функции с помощью универсального семейства (размер m = O(n^2)). Двухуровневая хеш-таблица (размер m = O(n)).

Лекция 7. Деревья поиска

Определение дерева поиска. Вставка и удаление элементов. Inorder-обход дерева. Красно-черные деревья: определение и основные свойства. Реализация операций вставки для красно-черного дерева. Splay-деревья. Операция splay: zig, zig-zig и zig-zag шаги. Реализация операций вставки, удаления, слияния и разделения для splay-деревьев.

Лекция 8. Деревья поиска: продолжение

Декартовы деревья (дучи). Единственность декартова дерева для заданного набора различных ключей и приоритетов. Логарифмическая оценка матожидания высоты дучи. Операции слияния и разделения для дуч. Операции вставки и удаления элементов для дуч. Построение декартового дерева за линейное время при условии предварительной сортировки ключей. B+ деревья: определения и основные свойства. Операции поиска, вставки и удаления для B+ деревьев.

Лекция 9. Задачи RMQ и LCA

Статические задачи RMQ/RSQ (range minimum/sum query) и LCA (least common ancestor). Оптимальное решение задачи RSQ. Решение задачи LCA методом бинарного подъёма (O(NlogN) памяти, запрос за O(logN) времени). Сведение от задачи RMQ к задаче LCA: декартово дерево. Сведение задачи LCA к задаче ±1-RMQ: Эйлеров обход дерева. Простейшие алгоритмы для решения задачи RMQ: полная и разреженная таблицы ответов. Алгоритм Фарах-Колтона-Бендера для задачи ±1-RMQ: деление массива на блоки, предподсчёт для префиксов и суффиксов блоков, предподсчёт всех нормализованных блоков. Алгоритм Тарьяна для поиска LCA в режиме offline.

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

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

Лекция 11. Структуры данных для геометрического поиска

Location problem, stabbing problem. Деревья интервалов. Сведение системы интервалов к двумерной задаче. Задача поиска точек в коридоре. Priority search tree. Задача поиска точек в прямоугольнике. Дерево отрезков по координате X, упорядоченные по Y списки точек в каждой вершине. Сложность O(n log n) для построения и O(log^2 n) для запроса. Уменьшение времени поиска до O(log n). Задача одновременного поиска в наборе упорядоченных списков. Fractional cascading.

Лекция 12. Задача о динамической связности в ненаправленном графе

Задача о динамической связности: вставки и удаления ребер, запросы о связности. Частный случай задачи для случая лесов. Деревья эйлеровых обходов: слияние и разделение.