Введение в структуры данных

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

• Семестр: 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-, декартово и красно-чёрное дерево.

Оценивание

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

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 балл

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

• Преподаватели:
  • Степанов Илья