Введение в структуры данных
Содержание
Общие сведения
- Семестр: 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 | Поиск k-й порядковой статистики с выбором случайного пивота (Quick Select). Асимптотика — б/д. |
| 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 с помощью метода потенциалов. |
| 61 | 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-, декартово и красно-чёрное дерево. |
Оценивание
Оценка по курсу состоит из нескольких частей:
- Тесты
- Контесты
- Практические проекты
- Лабораторная работа
Тесты
- Небольшие тесты на 10 минут в начале каждого занятия
- Вопросы по материалам прошлого занятия
- Для прохождения нужен phystech.edu-аккаунт
- За каждый тест - 10 баллов.
Контесты
- Набор задач с автоматической проверкой тестирующей системой Я.Контест (нужен phystech.edu-аккаунт)
- Всего 6 тестов - после каждой темы базового блока
- Срок решения - 2 недели
- За каждый контест - 10 баллов
- Списывание детектируется и наказуемо!
Практические проекты
- 2 проекта - консольное приложение (после ООП) и серверное приложение (после Сети-2)
- Работа над кодом в несколько итераций на GitHub (нужен аккаунт)
- Срок работы - 2 недели + 1 неделя на каждую следующую итерацию
- Список тем проектов будет позднее
- Оценка за проект: зачет / незачет + до 2 доп. баллов (wow-эффект)
Лабораторная работа
- Анализ данных с помощью Pandas и Matplotlib
- Выдается после “Инструменты визуализации”
- Срок работы - 2 недели
- Оценка - 10 баллов
- Является блокирующей! Для получения зачета за курс необходимо набрать хотя бы 1 балл
Команда курса
- Преподаватели:
- Степанов Илья
