Алгоритмы и структуры данных, часть 1
Новосибирск, осень 2019
Описание
Цели курса
- научиться оценивать время работы и потребление памяти программы;
- узнать алгоритмы и структуры данных, позволяющие улучшить время работы программы;
- научиться доказывать правильность работы программы и оценку времени работы;
- научиться решать сложные алгоритмические задачи и писать программы с высокой алгоритмический нагрузкой.
Домашние задания
Оценка за курс выставляется по результатам домашних заданий. В ходе курса будет предложено 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
Преподаватели
Список лекций
Основные ресурсы: память и время. О-символика. Примеры моделей вычисления: машина Тьюринга, RAM-машина. Сложность в среднем и худшем случаях.
Анализ учетных стоимостей операций. Банковский метод. Метод потенциалов: функция потенциала, истинные и учетные стоимости. Задача о двоичном счетчике.
Массивы переменного размера: аддитивная и мультипликативная схемы реаллокации. Анализ мультипликативной схемы для массива переменного размера с помощью банковского метода.
Стеки и очереди. Реализация на основе массива переменного размера и на основе связанного списка. Моделирование очереди с помощью двух стеков.
Изменяемые (mutable) и неизменяемые (immutable) структуры данных. Структуры данных с хранением истории (persistent). Immutable-стек и immutable-очередь. Проблема множественного будущего при анализе учетных cтоимоcтей в persistent-структурах.
Задача о поддержании динамического максимума в стеке и очереди.
Задача сортировки. Разрешающие деревья. Нижняя оценка сложности в модели разрешающих деревьев. Сортировка сравнениями. Понятия устойчивости и in-place
. Понятие о методе «разделяй и властвуй»: quicksort и mergesort. Алгоритм Quick-Sort. Процедура Partition, два варианта её in-place реализации. Примеры неудачного выбора опорных элементов. Рандомизированный выбор опорного элемента. Сложность Quick-Sort в худшем и среднем случаях. Глубина рекурсии в худшем и среднем случаях. Подробности реализации (кратко): сортировка вставками для малых подмассивов, удаление хвостовой рекурсии, медиана трёх, переход в другому виду сортировки. Алгоритм Merge-Sort. Слияние двух упорядоченных списков. Оценка сложности. Нерекурсивная реализация. Сортировка слиянием без использования дополнительной памяти: swap вместо присваивания, использование части массива в качестве буфера, слияние с перекрыванием входа и выхода.
Видео для студентов заочного отделения: https://compscicenter.ru/courses/algorithms-1/nsk/2018-autumn/classes/4124/
Понятие очереди с приоритетом. Деревья со свойствами кучи. Почти полные бинарные деревья: нумерация вершин, навигация. Двоичная куча. Операция просеивания вниз и вверх. Реализация операций вставки, удаления и поиска минимума. Сложность операций. Поддержание указателей на элементы кучи. Преобразование произвольного массива ключей в кучу (операция Make-Heap), линейность времени работы. k-ичные кучи, зависимость сложности операций от выбора k
Видео для студентов заочного отделения: https://compscicenter.ru/courses/algorithms-1/nsk/2018-autumn/classes/4192/
Биномиальные (binomial), левацкие (leftlist) и косые (skew) кучи.
Видео для студентов заочного отделения: https://compscicenter.ru/courses/algorithms-1/nsk/2018-autumn/classes/4212/
Слияние двух упорядоченных последовательностей различной длины. Теоретико-информационная нижняя оценка. Бинарный поиск от края
(galloping). Нахождение порядковых статистик с помощью рандомизированной модификации алгоритма Quick-Sort. Линейность матожидания времени работы. Приближенные медианы. Выбор k-й порядковой статистики за линейное в худшем случае.
Видео для студентов заочного отделения: https://compscicenter.ru/courses/algorithms-1/nsk/2018-autumn/classes/4233/
Хеш-функции. Коллизии. Разрешение коллизий методом цепочек, методом последовательных проб и методом двойного хеширования. Гипотеза простого равномерного хеширования, оценка средней длины цепочки. Универсальные семейства хеш-функций, оценка средней длины цепочки. Построение универсального семейства для целочисленных ключей. Совершенные хеш-функции. Построение совершенной хеш-функции с помощью универсального семейства (размер m = O(n^2)). Двухуровневая хеш-таблица (размер m = O(n)).
Видео для студентов заочного отделения: https://compscicenter.ru/courses/algorithms-1/nsk/2018-autumn/classes/4267/
Определение дерева поиска. Вставка и удаление элементов. Inorder-обход дерева. Красно-черные деревья: определение и основные свойства. Реализация операций вставки для красно-черного дерева. Splay-деревья. Операция splay: zig, zig-zig и zig-zag шаги. Реализация операций вставки, удаления, слияния и разделения для splay-деревьев.
Видео для студентов заочного отделения: https://compscicenter.ru/courses/algorithms-1/nsk/2018-autumn/classes/4275/
Декартовы деревья (дучи). Единственность декартова дерева для заданного набора различных ключей и приоритетов. Логарифмическая оценка матожидания высоты дучи. Операции слияния и разделения для дуч. Операции вставки и удаления элементов для дуч. Построение декартового дерева за линейное время при условии предварительной сортировки ключей. B+ деревья: определения и основные свойства. Операции поиска, вставки и удаления для B+ деревьев.
Видео для студентов заочного отделения: https://compscicenter.ru/courses/algorithms-1/nsk/2018-autumn/classes/4269/
Статические задачи 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.
Видео для студентов заочного отделения: https://compscicenter.ru/courses/algorithms-1/nsk/2018-autumn/classes/4377/
Системы непересекающихся множеств. Реализация с использованием леса. Ранги вершин, эвристика ранга. Логарифмическая оценка ранга через количество элементов. Рандомизированная ранговая эвристика. Эвристика сжатия путей. Оценка учетной стоимости операций (без доказательства).
Видео для студентов заочного отделения: https://compscicenter.ru/courses/algorithms-1/nsk/2018-autumn/classes/4393/
Location problem, stabbing problem. Деревья интервалов. Сведение системы интервалов к двумерной задаче. Задача поиска точек в коридоре. Priority search tree. Задача поиска точек в прямоугольнике. Дерево отрезков по координате X, упорядоченные по Y списки точек в каждой вершине. Сложность O(n log n) для построения и O(log^2 n) для запроса. Уменьшение времени поиска до O(log n). Задача одновременного поиска в наборе упорядоченных списков. Fractional cascading.
Видео для студентов заочного отделения: https://compscicenter.ru/courses/algorithms-1/nsk/2018-autumn/classes/4400/
Задача о динамической связности: вставки и удаления ребер, запросы о связности. Частный случай задачи для случая лесов. Деревья эйлеровых обходов: слияние и разделение.
Видео для студентов заочного отделения: https://compscicenter.ru/courses/algorithms-1/nsk/2018-autumn/classes/4414/