Введение в структуры данных — различия между версиями

Материал из Public ATP Wiki
Перейти к: навигация, поиск
(→‎План курса)
(→‎Общие сведения)
Строка 1: Строка 1:
 
= Общие сведения =
 
= Общие сведения =
−
* Семестр: 2 (первый курс курс)
+
* Семестр: 1 (первый курс курс)
 
* Форма контроля: дифференцированный зачет
 
* Форма контроля: дифференцированный зачет
  
Строка 22: Строка 22:
 
|-
 
|-
  
−
|-
+
|1|| Асимптотические обозначения: O, Ω, Θ. Независимость от стартового индекса.
−
 
 
−
|1|| Пять шагов для решения задачи на динамическое программирование.
 
−
 
 
−
|-
 
−
 
 
−
|2|| Задача о кузнечике (набор максимальной суммы на массиве). Неоптимальность жадного алгоритма.
 
−
 
 
−
|-
 
−
 
 
−
|3|| Задача о черепашке (набор максимальной суммы на таблице). Динамика “назад” и “вперёд”.
 
−
 
 
−
|-
 
−
 
 
−
|4|| Задача о наибольшей общей подпоследовательности.
 
−
 
 
−
|-
 
−
 
 
−
|5|| Задача о наибольшей возрастающей подпоследовательности: решение за O(n 2 ).
 
−
 
 
−
|-
 
−
 
 
−
|6|| Задача о наибольшей возрастающей подпоследовательности: решение за O(n log n) с помощью дерева отрезков или дерева Фенвика со сжатием координат.
 
−
 
 
−
|-
 
−
 
 
−
|7|| Задача о наибольшей возрастающей подпоследовательности: решение за O(n log n) с помощью бинарного поиска.
 
−
 
 
−
|-
 
−
 
 
−
|8|| Задача о рюкзаке: решения с динамикой по весу или по стоимости, что лучше выбрать. Восстановление ответа.
 
−
 
 
−
|-
 
−
 
 
−
|9|| Задача о рюкзаке: сверхполиномиальность известных алгоритмов. Неоптимальность жадного алгоритма.
 
−
 
 
−
|-
 
−
 
 
−
|10|| Бинарное возведение чисел и матриц в степень, асимптотика.
 
−
 
 
−
|-
 
−
 
 
−
|11|| Подсчёт n-го числа Фибоначчи (по модулю m) за O(log n).
 
−
 
 
−
|-
 
−
 
 
−
|12|| Подсчёт n-го члена рекурренты an = λan−1+µan−2+1 (по модулю m) за O(log n) для произвольных констант λ и µ.
 
−
 
 
−
|-
 
−
 
 
−
|13|| Количество путей между двумя вершинами длины ровно k за O(n 3 log k).
 
−
 
 
−
|-
 
−
 
 
−
|14|| Нахождение A + A2 + . . . + Ak за O(n 3 log k) для матрицы A размера n × n.
 
  
 
|-
 
|-
  
−
|15|| Количество путей между двумя вершинами длины не более k за O(n 3 log k).
+
|2|| Сумма на отрезке в статическом массиве: префиксные суммы.
  
 
|-
 
|-
  
−
|16|| Кодирование подмножеств {0, 1, . . . , n − 1} с помощью масок. Процедура извлечения бита (bit).
+
|3|| Проверка вхождения числа в отсортированный массив: бинарный поиск.
  
 
|-
 
|-
  
−
|17|| Операции над множествами (масками): объединение, пересечение, разность. Реализация в программе. Проверка, что одна маска является подмножеством другой. Проверка, что число является степенью двойки.
+
|4|| Структура данных стек: реализация на указателях, использование std::stack.
  
 
|-
 
|-
  
−
|18|| Задача о самом дешёвом гамильтоновом пути: решение за O(2n · n 2 ).
+
|5|| Поиск ближайшего меньшего/большего слева/справа в статическом массиве.
  
 
|-
 
|-
  
−
|19|| Задача о максимальной клике: решения за O(2n · n 2 ), O(2n · n) и O(2n ).
+
|6|| Поддержка минимума в стеке.
  
 
|-
 
|-
  
−
|20|| Подсчёт всех значений b(mask) = max s⊂mask a(s) для данного набор значений a(0), . . . , a(2n − 1) за O(2n · n).
+
|7|| Реализация очереди на двух стеках.
  
 
|-
 
|-
  
−
|21|| Задача о максимальной клике: решение за O(2n/2 · n). Опционально: решение за O(2n/2 ).
+
|8|| Поддержка минимума в очереди.
  
 
|-
 
|-
  
−
|22|| Число замощений таблицы n × m доминошками: динамика по прямому профилю.
+
|9|| Проверка правильности скобочной последовательности с несколькими типами скобок.
  
 
|-
 
|-
  
−
|23|| Хеш-таблицы: постановка задачи (запросы insert, erase, find), хеш-функции, коллизии. Разрешение коллизий с помощью цепочек.
+
|10|| Доказательство формулы: log(n!) = Θ(n log n).
  
 
|-
 
|-
  
−
|24|| Универсальное семейство хеш-функций. Теорема о времени работы, если хеш-функция выбирается из универсального семейства. Пример универсального семейства.
+
|11|| Нижняя оценка на число сравнений в сортировке сравнениями.
  
 
|-
 
|-
  
−
|25|| Совершенное хеширование. Постановка и решение за O(n) предподсчёта в среднем и O(1) на запрос. 26. Хеш-таблицы с открытой адресацией: линейное/квадратичное пробирование, двойное хеширование.
+
|12|| Сортировка слиянием (Merge Sort).
  
 
|-
 
|-
  
−
|27|| Определение k-независимого семейства, зависимость асимптотики операций от типа семейства, из которого выбирается хеш-функция и вида пробирования (б/д).
+
|13|| Поиск числа инверсий в массиве.
  
 
|-
 
|-
  
−
|28|| Фильтр Блума: идея. Оптимальные k и m при фиксированных n и FPR (б/д).
+
|14|| Нерекурсивная реализация сортировки слиянием.
  
 
|-
 
|-
  
−
|29|| Определения неориентированного и ориентированного графов, пути, (вершинно) простого пути, рёберно простого пути. Связь вершинной и рёберной простоты. Определение цикла, рёберно простого цикла, (вершинно) простого цикла. Определение достижимости между вершинами, простота пути. Определение связности.
+
|15|| Быстрая сортировка (Quick Sort). Асимптотика — б/д.
  
 
|-
 
|-
  
−
|30|| Отношение сильной связности между вершинами. Компоненты сильной связности. Сильно связный граф.
+
|16|| Поиск k-й порядковой статистики с выбором случайного пивота (Quick Select). Асимптотика — |-
−
 
 
−
|-
 
  
−
|31|| Три способа хранения графа в памяти компьютера, их преимущества и недостатки.
+
б/д.
  
 
|-
 
|-
  
−
|32|| Поиск в глубину: алгоритм dfs на ориентированном графе. Лемма о белых путях.
+
|17|| Детерминированный алгоритм поиска k-й порядковой статистики за O(n), где n — длина массива.
−
|33|| Поиск в глубину: множество посещаемых вершин, поиск цикла, достижимого из s, проверка на ацикличность.
 
  
 
|-
 
|-
  
−
|34|| Топологическая сортировка ориентированного ациклического графа: определение и алгоритм поиска (с доказательством корректности). Число путей в ориентированном ациклическом графе.
+
|18|| Детерминированный алгоритм быстрой сортировки за O(n log n), где n — длина массива.
  
 
|-
 
|-
  
−
|35|| Алгоритм Косарайю. Корректность и время работы.
+
|19|| Стабильная сортировка подсчётом. Сортировка пар чисел.
  
 
|-
 
|-
  
−
|36|| Конденсация ориентированного графа, ацикличность.
+
|20|| Цифровая сортировка (LSD).
  
 
|-
 
|-
  
−
|37|| Постановка и решение задачи 2SAT (применение алгоритма выделения компонент сильной связности).
+
|21|| Двоичная куча: определение и представление в массиве. Требование кучи.
  
 
|-
 
|-
  
−
|38|| Алгоритм dfs на неориентированном графе. Дерево обхода dfs. Классификация рёбер на древесные и обратные. Проверка связности и ацикличности. Компоненты связности.
+
|22|| Операции siftUp и siftDown с доказательством корректности.
  
 
|-
 
|-
  
−
|39|| Мосты, точки сочленения. Введение функции ret. Критерий того, что ребро является мостом.
+
|23|| Выражение insert, getMin, extractMin и decreaseKey через siftUp и siftDown.
−
 
 
−
|-
 
−
|40|| Насчёт ret в неориентированном графе, нахождение мостов.
 
  
 
|-
 
|-
  
−
|41|| Понятие рёберной двусвязности. Отношение эквивалентности.
+
|24|| Построение кучи (heapify) за линейное время (сходимостью ряда можно пользоваться б/д).
  
 
|-
 
|-
  
−
|42|| Выделение компонент рёберной двусвязности в неориентированном графе. Древесность графа со сжатыми компонентами рёберной двусвязности.
+
|25|| Сортировка кучей с привлечением O(1) дополнительной памяти (Heap Sort). Несуществование кучи (основанной на сравнениях), обрабатывающей insert и extractMin за O(1).
  
 
|-
 
|-
  
−
|43|| Нахождение точек сочленения в неориентированном графе.
+
|26|| Технические сложности и их преодоление для операции decreaseKey в куче.
  
 
|-
 
|-
  
−
|44|| Понятие вершинной двусвязности. Отношение эквивалентности (б/д).
+
|27|| Удаление из кучи по значению.
  
 
|-
 
|-
  
−
|45|| Выделение компонент вершинной двусвязности в неориентированном графе (б/д).
+
|28|| Удаление из кучи по указателю.
  
 
|-
 
|-
  
−
|46||Определение эйлерова цикла. Критерий наличия эйлерова цикла в неориентированном графе.
+
|29|| Биномиальное дерево, биномиальная куча: определение.
  
 
|-
 
|-
  
−
|47|| Реализация алгоритма поиска эйлерова цикла.
+
|30|| Операции merge, insert, getMin, extractMin и decreaseKey в биномиальной куче.
  
 
|-
 
|-
  
−
|48|| Определение кратчайшего расстояния в невзвешенном/взвешенном графе.
+
|31|| Амортизационный анализ, учётное время работы: определение.
  
 
|-
 
|-
  
−
|49|| Поиск в ширину: алгоритм bfs с доказательством корректности.
+
|32|| Метод монеток (бухгалтерский учёт).
  
 
|-
 
|-
  
−
|50|| Алгоритм 0-K-bfs.
+
|33|| Структура данных вектор, реализация на массиве и оценка асимптотики методом монеток.
  
 
|-
 
|-
  
−
|51|| Двусторонний bfs.
+
|34|| Метод потенциалов.
−
 
 
−
|-
 
−
 
 
−
|52|| Алгоритм Дейкстры. Условия применимости, доказательство корректности. Реализации за O(n 2 ), O(m log n), O(m + n log n).
 
−
 
 
−
|-
 
−
 
 
−
|53|| Двусторонний алгоритм Дейкстры.
 
−
 
 
−
|-
 
−
 
 
−
|54|| Алгоритм A∗ : определения функций f, g, h; реализация.
 
−
 
 
−
|-
 
−
 
 
−
|55|| Вырожденные случае в алгоритме A∗ : h ≡ 0, h(v) = dist(v, t).
 
−
 
 
−
|-
 
−
 
 
−
|56|| Допустимые и монотонные эвристики в алгоритме A∗ . Примеры монотонных эвристик на разных сетках.
 
−
 
 
−
|-
 
  
−
|57|| Формулировка работоспособности (корректность и время работы) алгоритма A∗ в случае монотонной, допустимой или произвольной эвристики. Доказательство для монотонного случая.
 
 
|-
 
|-
  
−
|58|| Алгоритм Флойда: поиск попарных кратчайших расстояний в графе без отрицательных циклов. Реализация, асимптотика.
+
|35|| Вставка в биномиальной куче в отсутствие других операций, применение метода потенциалов.
  
 
|-
 
|-
  
−
|59|| Восстановление ответа (пути) в алгоритме Флойда.
+
|36|| Sparse Table: модельная задача, построение за O(n log n), ответ на запрос за O(1).
  
 
|-
 
|-
  
−
|60|| Алгоритм Форда—Беллмана: поиск кратчайших расстояний от одной вершины до всех. Реализация, асимптотика (в случае отсутствия отрицательных циклов).
+
|37|| Дерево отрезков: модельная задача. Обработка запросов с доказательством времени работы.
  
 
|-
 
|-
  
−
|61|| Алгоритм Форда—Беллмана: нахождение кратчайших расстояний от одной вершины до всех в случае наличия отрицательных циклов.
+
|38|| Дерево отрезков: двоичный спуск, поиск k-го нуля на отрезке массива за O(log n).
  
 
|-
 
|-
  
−
|62|| Остовный подграф, остовное дерево. Минимальный остов. Лемма о безопасном ребре.
+
|39|| Дерево отрезков, отложенные операции: присвоение константы на отрезке, операция push.
  
 
|-
 
|-
  
−
|63|| Алгоритм Прима: доказательство корректности и реализации за O(n 2 ), O(m log n), O(m + n log n).
+
|40|| Количество чисел на отрезке, значения которых лежат в отрезке: Fractional Cascading.
  
 
|-
 
|-
  
−
|64|| Система непересекающихся множеств (СНМ). Виды запросов. Эвристика по рангу, эвристика сжатия путей. Асимптотика ответа на запрос при использовании обеих эвристик (б/д).
+
|41|| Персистентный массив.
  
 
|-
 
|-
  
−
|65|| Асимптотика ответа на запрос в СНМ при использовании только эвристики по рангу.
+
|42|| Персистентное дерево отрезков.
  
 
|-
 
|-
  
−
|66|| Алгоритм Крускала: корректность, реализация, асимптотика.
+
|43|| Количество чисел на отрезке, значения которых лежат в отрезке: решение с персистентным деревом отрезков.
  
 
|-
 
|-
  
−
|67|| Алгоритм Борувки: выбор минимального ребра из нескольких, корректность, реализация, асимптотика.
+
|44|| Динамическое дерево отрезков.
  
 
|-
 
|-
  
−
|68|| Определение паросочетания в произвольном графе, двудольного графа, увеличивающего пути.
+
|45|| Онлайн vs. оффлайн: сжатие координат.
  
 
|-
 
|-
  
−
|69|| Лемма об устройстве неориентированного графа, в котором степени всех вершин не превосходят двух.
+
|46|| Онлайн vs. оффлайн: дерево поиска оффлайн.
  
 
|-
 
|-
  
−
|70|| Теорема Бержа.
+
|47|| Онлайн vs. оффлайн: количество чисел на отрезке, значения которых лежат в отрезке.
  
 
|-
 
|-
  
−
|71|| Алгоритм Куна. Корректность, реализация, асимптотика.
+
|48|| Дерево Фенвика: классическая задача, операции update и getSum.
  
 
|-
 
|-
  
−
|72|| Лемма об отсутствии увеличивающих путей из вершины при отсутствии таких путей относительного меньшего паросочетания.
+
|49|| Обобщение дерева Фенвика на б´oльшие размерности. Изменение асимптотики.
  
 
|-
 
|-
  
−
|73|| Определения независимого множества, вершинного покрытия. Связь определений.
+
|50|| Обратное дерево Фенвика: максимум на отрезке и изменение (увеличение) в точке (update — без реализации).
  
 
|-
 
|-
  
−
|74|| Алгоритм поиска максимального независимого множества и минимального вершинного покрытия в двудольном графе с помощью разбиения на доли L −, L+, R−, R+ (с доказательством). Теорема Кёнига.
+
|51|| Дерево Фенвика деревьев Фенвика.
  
 
|-
 
|-
  
−
|75|| Определения сети, потока, величины потока, остаточной сети. Пример, почему нельзя обойтись без обратных рёбер.
+
|52|| Дерево поиска: определения и операции (без реализации) find, insert, erase, а также опциональные merge и split.
  
 
|-
 
|-
  
−
|76|| Определения разреза, величины разреза, величины потока через разрез. Лемма о равенстве величины потока и величины потока через разрез.
+
|53|| Наивное дерево поиска, обработка операций.
  
 
|-
 
|-
  
−
|77|| Лемма о связи величины произвольного потока и величины произвольного разреза.
+
|54|| AVL-дерево: определение.
  
 
|-
 
|-
  
−
|78|| Теорема Форда—Фалкерсона.
+
|55|| Оценка глубины AVL-дерева на n вершинах.
  
 
|-
 
|-
  
−
|79|| Алгоритм Форда—Фалкерсона. Корректность, асимптотика. Пример сверхполиномиального (от размера входа) времени работы.
+
|56|| Устранение дисбаланса в AVL-дереве для случая ∆(a) = −2.
  
 
|-
 
|-
  
−
|80|| Алгоритм Эдмондса—Карпа. Корректность.
+
|57|| AVL-дерево: реализация операций insert и erase.
  
 
|-
 
|-
  
−
|81|| Лемма о возрастании dist(s, v) между последовательными итерациями алгоритма Эдмондса— Карпа.
+
|58|| Splay-дерево: определение и практическая значимость.
  
 
|-
 
|-
  
−
|82|| Лемма о числе насыщений ребра в алгоритме Эдмондса—Карпа. Асимптотика этого алгоритма.
+
|59|| Splay-дерево: операции zig, zig-zig и zig-zag, операция splay.
  
 
|-
 
|-
  
−
|83|| Задача о разбиении коллектива на две группы с минимизацией суммарного недовольства.
+
|60|| Амортизированное время работы операции splay с помощью метода потенциалов.
  
 
|-
 
|-
  
−
|84|| Алгоритм Эдмондса—Карпа с масштабированием, асимптотика.
+
|61| Splay-дерево: реализация insert, erase и find, связь с операцией splay, оценка времени работы.
  
 
|-
 
|-
  
−
|85|| Определение слоистой сети, блокирующего потока. Алгоритм Диница, доказательство корректности.
+
|62|| B-дерево: определение и практическая значимость.
  
 
|-
 
|-
  
−
|86|| Реализация алгоритма Диница. Асимптотика.
+
|63|| Оценка глубины B-дерева на n ключах при фиксированном параметре t.
  
 
|-
 
|-
  
−
|87|| Первая теорема Карзанова о числе итераций алгоритма Диница.
+
|64|| Реализация операции insert в B-дереве.
  
 
|-
 
|-
  
−
|88|| Быстродействие алгоритма Диница в единичных сетях.
+
|65|| Реализация операции erase в B-дереве.
  
 
|-
 
|-
  
−
|89|| Алгоритм Хопкрофта—Карпа поиска максимального паросочетания в двудольном графе. Корректность и асимптотика.
+
|66|| Декартово дерево: определение и теорема о глубине (б/д).
  
 
|-
 
|-
  
−
|90|| Алгоритм Штор—Вагнера поиска минимального глобального разреза.
+
|67|| Реализация операций merge и split в декартовом дереве.
  
 
|-
 
|-
  
−
|91|| Min cost flow: постановка задачи. Критерий минимальности стоимости потока величины k (б/д). Алгоритм поиска потока величины k минимальной стоимости. Асимптотика.
+
|68|| Выражение insert и erase в декартовом дереве через merge и split.
  
 
|-
 
|-
  
−
|92|| Потенциалы Джонсона. Поиск min cost k-flow с помощью алгоритма Дейкстры.
+
|69|| Декартово дерево по неявному ключу: в массиве вставить, удалить элемент, узнать сумму на отрезке.
  
 
|-
 
|-
  
−
|93|| Определение дерева, его свойства (б/д). Определение центроида в дереве. Алгоритм поиска центроида в дереве. Лемма о количестве центроидов.
+
|70|| Красно-чёрное дерево: определение.
  
 
|-
 
|-
  
−
|94|| Определение изоморфизма графов. Алгоритм проверки изоморфности двух ориентированных или неориентированных деревьев за O(n log n).
+
|71|| Оценка глубины красно-чёрного дерева на n ключах.
  
 
|-
 
|-
  
−
|95|| Задача LCA. Постановка, решение с помощью двоичных подъёмов.
+
|72|| Реализация операции insert в красно-чёрном дереве.
  
 
|-
 
|-
  
−
|96|| Задача LCA. Решение с помощью эйлерова обхода.
+
|73|| Реализация операции erase в красно-чёрном дереве.
  
 
|-
 
|-
  
−
|97|| Задача LCA. Алгоритм Фарах-Колтона и Бендера.
+
|74|| Сравнительный анализ различных реализаций дерева поиска: наивное, AVL-, splay-, B-, декартово и красно-чёрное дерево.
  
 
|}
 
|}

Версия 17:31, 4 декабря 2022

Общие сведения

  • Семестр: 1 (первый курс курс)
  • Форма контроля: дифференцированный зачет

Важные ссылки

  • Регистрация на курс (доступ для физтех-аккаунтов)
  • Материалы курсa (доступ для физтех-аккаунтов)
  • Чат курса
  • Таблица с оценками

Требования

  • Физтех-почта (домен phystech.edu)
  • Аккаунт на GitHub
  • Ноутбук на занятиях

План курса

№ Тема
1 Асимптотические обозначения: O, Ω, Θ. Независимость от стартового индекса.
2 Сумма на отрезке в статическом массиве: префиксные суммы.
3 Проверка вхождения числа в отсортированный массив: бинарный поиск.
4 Структура данных стек: реализация на указателях, использование std::stack.
5 Поиск ближайшего меньшего/большего слева/справа в статическом массиве.
6 Поддержка минимума в стеке.
7 Реализация очереди на двух стеках.
8 Поддержка минимума в очереди.
9 Проверка правильности скобочной последовательности с несколькими типами скобок.
10 Доказательство формулы: log(n!) = Θ(n log n).
11 Нижняя оценка на число сравнений в сортировке сравнениями.
12 Сортировка слиянием (Merge Sort).
13 Поиск числа инверсий в массиве.
14 Нерекурсивная реализация сортировки слиянием.
15 Быстрая сортировка (Quick Sort). Асимптотика — б/д.
16 -

б/д.

17 Детерминированный алгоритм поиска k-й порядковой статистики за O(n), где n — длина массива.
18 Детерминированный алгоритм быстрой сортировки за O(n log n), где n — длина массива.
19 Стабильная сортировка подсчётом. Сортировка пар чисел.
20 Цифровая сортировка (LSD).
21 Двоичная куча: определение и представление в массиве. Требование кучи.
22 Операции siftUp и siftDown с доказательством корректности.
23 Выражение insert, getMin, extractMin и decreaseKey через siftUp и siftDown.
24 Построение кучи (heapify) за линейное время (сходимостью ряда можно пользоваться б/д).
25 Сортировка кучей с привлечением O(1) дополнительной памяти (Heap Sort). Несуществование кучи (основанной на сравнениях), обрабатывающей insert и extractMin за O(1).
26 Технические сложности и их преодоление для операции decreaseKey в куче.
27 Удаление из кучи по значению.
28 Удаление из кучи по указателю.
29 Биномиальное дерево, биномиальная куча: определение.
30 Операции merge, insert, getMin, extractMin и decreaseKey в биномиальной куче.
31 Амортизационный анализ, учётное время работы: определение.
32 Метод монеток (бухгалтерский учёт).
33 Структура данных вектор, реализация на массиве и оценка асимптотики методом монеток.
34 Метод потенциалов.
35 Вставка в биномиальной куче в отсутствие других операций, применение метода потенциалов.
36 Sparse Table: модельная задача, построение за O(n log n), ответ на запрос за O(1).
37 Дерево отрезков: модельная задача. Обработка запросов с доказательством времени работы.
38 Дерево отрезков: двоичный спуск, поиск k-го нуля на отрезке массива за O(log n).
39 Дерево отрезков, отложенные операции: присвоение константы на отрезке, операция push.
40 Количество чисел на отрезке, значения которых лежат в отрезке: Fractional Cascading.
41 Персистентный массив.
42 Персистентное дерево отрезков.
43 Количество чисел на отрезке, значения которых лежат в отрезке: решение с персистентным деревом отрезков.
44 Динамическое дерево отрезков.
45 Онлайн vs. оффлайн: сжатие координат.
46 Онлайн vs. оффлайн: дерево поиска оффлайн.
47 Онлайн vs. оффлайн: количество чисел на отрезке, значения которых лежат в отрезке.
48 Дерево Фенвика: классическая задача, операции update и getSum.
49 Обобщение дерева Фенвика на б´oльшие размерности. Изменение асимптотики.
50 Обратное дерево Фенвика: максимум на отрезке и изменение (увеличение) в точке (update — без реализации).
51 Дерево Фенвика деревьев Фенвика.
52 Дерево поиска: определения и операции (без реализации) find, insert, erase, а также опциональные merge и split.
53 Наивное дерево поиска, обработка операций.
54 AVL-дерево: определение.
55 Оценка глубины AVL-дерева на n вершинах.
56 Устранение дисбаланса в AVL-дереве для случая ∆(a) = −2.
57 AVL-дерево: реализация операций insert и erase.
58 Splay-дерево: определение и практическая значимость.
59 Splay-дерево: операции zig, zig-zig и zig-zag, операция splay.
60 Амортизированное время работы операции splay с помощью метода потенциалов.
Splay-дерево: реализация insert, erase и find, связь с операцией splay, оценка времени работы.
62 B-дерево: определение и практическая значимость.
63 Оценка глубины B-дерева на n ключах при фиксированном параметре t.
64 Реализация операции insert в B-дереве.
65 Реализация операции erase в B-дереве.
66 Декартово дерево: определение и теорема о глубине (б/д).
67 Реализация операций merge и split в декартовом дереве.
68 Выражение insert и erase в декартовом дереве через merge и split.
69 Декартово дерево по неявному ключу: в массиве вставить, удалить элемент, узнать сумму на отрезке.
70 Красно-чёрное дерево: определение.
71 Оценка глубины красно-чёрного дерева на n ключах.
72 Реализация операции insert в красно-чёрном дереве.
73 Реализация операции erase в красно-чёрном дереве.
74 Сравнительный анализ различных реализаций дерева поиска: наивное, AVL-, splay-, B-, декартово и красно-чёрное дерево.

Оценивание

Оценка по курсу состоит из нескольких частей:

  1. Тесты
  2. Контесты
  3. Практические проекты
  4. Лабораторная работа

Тесты

  • Небольшие тесты на 10 минут в начале каждого занятия
  • Вопросы по материалам прошлого занятия
  • Для прохождения нужен phystech.edu-аккаунт
  • За каждый тест - 10 баллов.

Контесты

  • Набор задач с автоматической проверкой тестирующей системой Я.Контест (нужен phystech.edu-аккаунт)
  • Всего 6 тестов - после каждой темы базового блока
  • Срок решения - 2 недели
  • За каждый контест - 10 баллов
  • Списывание детектируется и наказуемо!

Практические проекты

  • 2 проекта - консольное приложение (после ООП) и серверное приложение (после Сети-2)
  • Работа над кодом в несколько итераций на GitHub (нужен аккаунт)
  • Срок работы - 2 недели + 1 неделя на каждую следующую итерацию
  • Список тем проектов будет позднее
  • Оценка за проект: зачет / незачет + до 2 доп. баллов (wow-эффект)

Лабораторная работа

  • Анализ данных с помощью Pandas и Matplotlib
  • Выдается после “Инструменты визуализации”
  • Срок работы - 2 недели
  • Оценка - 10 баллов
  • Является блокирующей! Для получения зачета за курс необходимо набрать хотя бы 1 балл

Команда курса

  • Преподаватели:
    • Сьепанов Илья
Источник — «http://wiki.atp-fivt.org/index.php?title=Введение_в_структуры_данных&oldid=1497»