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

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

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

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

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

Требования

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

План курса

№	Тема
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).
16	Кодирование подмножеств {0, 1, . . . , n − 1} с помощью масок. Процедура извлечения бита (bit).
17	Операции над множествами (масками): объединение, пересечение, разность. Реализация в программе. Проверка, что одна маска является подмножеством другой. Проверка, что число является степенью двойки.
18	Задача о самом дешёвом гамильтоновом пути: решение за O(2n · n 2 ).
19	Задача о максимальной клике: решения за O(2n · n 2 ), O(2n · n) и O(2n ).
20	Подсчёт всех значений b(mask) = max s⊂mask a(s) для данного набор значений a(0), . . . , a(2n − 1) за O(2n · n).
21	Задача о максимальной клике: решение за O(2n/2 · n). Опционально: решение за O(2n/2 ).
22	Число замощений таблицы n × m доминошками: динамика по прямому профилю.
23	Хеш-таблицы: постановка задачи (запросы insert, erase, find), хеш-функции, коллизии. Разрешение коллизий с помощью цепочек.
24	Универсальное семейство хеш-функций. Теорема о времени работы, если хеш-функция выбирается из универсального семейства. Пример универсального семейства.
25	Совершенное хеширование. Постановка и решение за O(n) предподсчёта в среднем и O(1) на запрос. 26. Хеш-таблицы с открытой адресацией: линейное/квадратичное пробирование, двойное хеширование.
27	Определение k-независимого семейства, зависимость асимптотики операций от типа семейства, из которого выбирается хеш-функция и вида пробирования (б/д).
28	Фильтр Блума: идея. Оптимальные k и m при фиксированных n и FPR (б/д).
29	Определения неориентированного и ориентированного графов, пути, (вершинно) простого пути, рёберно простого пути. Связь вершинной и рёберной простоты. Определение цикла, рёберно простого цикла, (вершинно) простого цикла. Определение достижимости между вершинами, простота пути. Определение связности.
30	Отношение сильной связности между вершинами. Компоненты сильной связности. Сильно связный граф.
31	Три способа хранения графа в памяти компьютера, их преимущества и недостатки.
32	Поиск в глубину: алгоритм dfs на ориентированном графе. Лемма о белых путях.	33	Поиск в глубину: множество посещаемых вершин, поиск цикла, достижимого из s, проверка на ацикличность.
34	Топологическая сортировка ориентированного ациклического графа: определение и алгоритм поиска (с доказательством корректности). Число путей в ориентированном ациклическом графе.
35	Алгоритм Косарайю. Корректность и время работы.
36	Конденсация ориентированного графа, ацикличность.
37	Постановка и решение задачи 2SAT (применение алгоритма выделения компонент сильной связности).
38	Алгоритм dfs на неориентированном графе. Дерево обхода dfs. Классификация рёбер на древесные и обратные. Проверка связности и ацикличности. Компоненты связности.
39	Мосты, точки сочленения. Введение функции ret. Критерий того, что ребро является мостом.
40	Насчёт ret в неориентированном графе, нахождение мостов.
41	Понятие рёберной двусвязности. Отношение эквивалентности.
42	Выделение компонент рёберной двусвязности в неориентированном графе. Древесность графа со сжатыми компонентами рёберной двусвязности.
43	Нахождение точек сочленения в неориентированном графе.
44	Понятие вершинной двусвязности. Отношение эквивалентности (б/д).
45	Выделение компонент вершинной двусвязности в неориентированном графе (б/д).
46	Определение эйлерова цикла. Критерий наличия эйлерова цикла в неориентированном графе.
47	Реализация алгоритма поиска эйлерова цикла.
48	Определение кратчайшего расстояния в невзвешенном/взвешенном графе.
49	Поиск в ширину: алгоритм bfs с доказательством корректности.
50	Алгоритм 0-K-bfs.
51	Двусторонний bfs.
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	Алгоритм Флойда: поиск попарных кратчайших расстояний в графе без отрицательных циклов. Реализация, асимптотика.
59	Восстановление ответа (пути) в алгоритме Флойда.
60	Алгоритм Форда—Беллмана: поиск кратчайших расстояний от одной вершины до всех. Реализация, асимптотика (в случае отсутствия отрицательных циклов).
61	Алгоритм Форда—Беллмана: нахождение кратчайших расстояний от одной вершины до всех в случае наличия отрицательных циклов.
62	Остовный подграф, остовное дерево. Минимальный остов. Лемма о безопасном ребре.
63	Алгоритм Прима: доказательство корректности и реализации за O(n 2 ), O(m log n), O(m + n log n).
64	Система непересекающихся множеств (СНМ). Виды запросов. Эвристика по рангу, эвристика сжатия путей. Асимптотика ответа на запрос при использовании обеих эвристик (б/д).
65	Асимптотика ответа на запрос в СНМ при использовании только эвристики по рангу.
66	Алгоритм Крускала: корректность, реализация, асимптотика.
67	Алгоритм Борувки: выбор минимального ребра из нескольких, корректность, реализация, асимптотика.
68	Определение паросочетания в произвольном графе, двудольного графа, увеличивающего пути.
69	Лемма об устройстве неориентированного графа, в котором степени всех вершин не превосходят двух.
70	Теорема Бержа.
71	Алгоритм Куна. Корректность, реализация, асимптотика.
72	Лемма об отсутствии увеличивающих путей из вершины при отсутствии таких путей относительного меньшего паросочетания.
73	Определения независимого множества, вершинного покрытия. Связь определений.
74	Алгоритм поиска максимального независимого множества и минимального вершинного покрытия в двудольном графе с помощью разбиения на доли L −, L+, R−, R+ (с доказательством). Теорема Кёнига.
75	Определения сети, потока, величины потока, остаточной сети. Пример, почему нельзя обойтись без обратных рёбер.
76	Определения разреза, величины разреза, величины потока через разрез. Лемма о равенстве величины потока и величины потока через разрез.
77	Лемма о связи величины произвольного потока и величины произвольного разреза.
78	Теорема Форда—Фалкерсона.
79	Алгоритм Форда—Фалкерсона. Корректность, асимптотика. Пример сверхполиномиального (от размера входа) времени работы.
80	Алгоритм Эдмондса—Карпа. Корректность.
81	Лемма о возрастании dist(s, v) между последовательными итерациями алгоритма Эдмондса— Карпа.
82	Лемма о числе насыщений ребра в алгоритме Эдмондса—Карпа. Асимптотика этого алгоритма.
83	Задача о разбиении коллектива на две группы с минимизацией суммарного недовольства.
84	Алгоритм Эдмондса—Карпа с масштабированием, асимптотика.
85	Определение слоистой сети, блокирующего потока. Алгоритм Диница, доказательство корректности.
86	Реализация алгоритма Диница. Асимптотика.
87	Первая теорема Карзанова о числе итераций алгоритма Диница.
88	Быстродействие алгоритма Диница в единичных сетях.
89	Алгоритм Хопкрофта—Карпа поиска максимального паросочетания в двудольном графе. Корректность и асимптотика.
90	Алгоритм Штор—Вагнера поиска минимального глобального разреза.
91	Min cost flow: постановка задачи. Критерий минимальности стоимости потока величины k (б/д). Алгоритм поиска потока величины k минимальной стоимости. Асимптотика.
92	Потенциалы Джонсона. Поиск min cost k-flow с помощью алгоритма Дейкстры.
93	Определение дерева, его свойства (б/д). Определение центроида в дереве. Алгоритм поиска центроида в дереве. Лемма о количестве центроидов.
94	Определение изоморфизма графов. Алгоритм проверки изоморфности двух ориентированных или неориентированных деревьев за O(n log n).
95	Задача LCA. Постановка, решение с помощью двоичных подъёмов.
96	Задача LCA. Решение с помощью эйлерова обхода.
97	Задача LCA. Алгоритм Фарах-Колтона и Бендера.

Оценивание

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

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

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

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