Алгоритмы и структуры данных, часть 1
Новосибирск, осень 2021
Описание
Цели курса
- научиться оценивать время работы и потребление памяти программы;
- узнать алгоритмы и структуры данных, позволяющие улучшить время работы программы;
- научиться доказывать правильность работы программы и оценку времени работы;
- научиться решать сложные алгоритмические задачи и писать программы с высокой алгоритмический нагрузкой.
Домашние задания
Оценка за курс выставляется по результатам домашних заданий. В ходе курса будет предложено 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://disk.yandex.ru/i/Z0eIiaPVrY9pIg.
Преподаватели
Список лекций
Основные ресурсы: память и время. О-символика. Примеры моделей вычисления: машина Тьюринга, RAM-машина. Сложность в среднем и худшем случаях.
Анализ учетных стоимостей операций. Банковский метод. Метод потенциалов: функция потенциала, истинные и учетные стоимости. Задача о двоичном счетчике.
Массивы переменного размера: аддитивная и мультипликативная схемы реаллокации. Анализ мультипликативной схемы для массива переменного размера с помощью банковского метода.
Стеки и очереди. Реализация на основе массива переменного размера и на основе связанного списка. Моделирование очереди с помощью двух стеков. Стек с максимумами.
Изменяемые (mutable) и неизменяемые (immutable) структуры данных. Структуры данных с хранением истории (persistent). Immutable-стек и immutable-очередь. Проблема множественного будущего при анализе учетных cтоимоcтей в persistent-структурах.
Хранение графа, обход в ширину, обход в глубину, топологическая сортировка, связность графа, сильная связность, цикл, Эйлеров цикл
Хеш-функции. Коллизии. Разрешение коллизий методом цепочек, методом последовательных проб и методом двойного хеширования. Гипотеза простого равномерного хеширования, оценка средней длины цепочки. Универсальные семейства хеш-функций, оценка средней длины цепочки. Построение универсального семейства для целочисленных ключей. Совершенные хеш-функции. Построение совершенной хеш-функции с помощью универсального семейства (размер m = O(n^2)). Двухуровневая хеш-таблица (размер m = O(n)).
Определение дерева поиска. Вставка и удаление элементов. Inorder-обход дерева. Красно-черные деревья: определение и основные свойства. Реализация операций вставки для красно-черного дерева. Splay-деревья. Операция splay: zig, zig-zig и zig-zag шаги. Реализация операций вставки, удаления, слияния и разделения для splay-деревьев.
Декартовы деревья (дучи). Единственность декартова дерева для заданного набора различных ключей и приоритетов. Логарифмическая оценка матожидания высоты дучи. Операции слияния и разделения для дуч. Операции вставки и удаления элементов для дуч. Построение декартового дерева за линейное время при условии предварительной сортировки ключей. B+ деревья: определения и основные свойства. Операции поиска, вставки и удаления для B+ деревьев.
Статические задачи 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.
Системы непересекающихся множеств. Реализация с использованием леса. Ранги вершин, эвристика ранга. Логарифмическая оценка ранга через количество элементов. Рандомизированная ранговая эвристика. Эвристика сжатия путей. Оценка учетной стоимости операций (без доказательства).
Location problem, stabbing problem. Деревья интервалов. Сведение системы интервалов к двумерной задаче. Задача поиска точек в коридоре. Priority search tree. Задача поиска точек в прямоугольнике. Дерево отрезков по координате X, упорядоченные по Y списки точек в каждой вершине. Сложность O(n log n) для построения и O(log^2 n) для запроса. Уменьшение времени поиска до O(log n). Задача одновременного поиска в наборе упорядоченных списков. Fractional cascading.