Введение в структуры данных - История изменений

Ryabchikov.andrey: /* Команда курса */

2023-02-02T22:04:54Z

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

Ryabchikov.andrey: /* План курса */

2022-12-04T14:31:40Z

‎План курса

Ryabchikov.andrey: /* Общие сведения */

2022-12-04T14:31:08Z

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

Внесённые изменения

Ryabchikov.andrey: /* План курса */

2022-12-04T14:14:55Z

‎План курса

Ryabchikov.andrey: /* План курса */

2022-12-04T14:13:57Z

‎План курса

Ryabchikov.andrey: /* План курса */

2022-12-04T14:13:21Z

‎План курса

Ryabchikov.andrey: /* План курса */

2022-12-04T14:12:27Z

‎План курса

Ryabchikov.andrey: Новая страница: «= Общие сведения = * Семестр: 2 (первый курс курс) * Форма контроля: дифференцированный заче…»

2022-12-04T14:11:48Z

Новая страница: «= Общие сведения = * Семестр: 2 (первый курс курс) * Форма контроля: дифференцированный заче…»

Новая страница

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

== Важные ссылки ==
* '''Регистрация на курс''' (доступ для физтех-аккаунтов)
* '''Материалы курсa''' (доступ для физтех-аккаунтов)
* '''Чат курса'''
* '''[https://docs.google.com/spreadsheets/d/e/2PACX-1vTMMwi5Al5sqXSAKCrHSFt8Yp3ZA3FymxDqkntP_QXYiOfzrFnJUmFaxIGVM8iQCw/pubhtml?gid=99265951&single=true Таблица с оценками]'''

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

== План курса ==

{| class="wikitable"
|-
! №
! Тема
|-

|-

|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. Алгоритм Фарах-Колтона и Бендера.

|}

== Оценивание ==
Оценка по курсу состоит из нескольких частей:
# Тесты
# Контесты
# Практические проекты
# Лабораторная работа

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

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

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

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

== Команда курса ==
* Преподаватели:
** Сьепанов Илья

@@ Строка 354: / Строка 354: @@
 == Команда курса ==
 * Преподаватели:
-** Сьепанов Илья
+** Степанов Илья

@@ Строка 82: / Строка 82: @@
 |-
-|16|| Поиск k-й порядковой статистики с выбором случайного пивота (Quick Select). Асимптотика — |-
+|16|| Поиск k-й порядковой статистики с выбором случайного пивота (Quick Select). Асимптотика — б/д.
 |-
@@ Строка 264: / Строка 262: @@
 |-
-|61| Splay-дерево: реализация insert, erase и find, связь с операцией splay, оценка времени работы.
+|61|| Splay-дерево: реализация insert, erase и find, связь с операцией splay, оценка времени работы.
 |-

@@ Строка 240: / Строка 240: @@
 |-
-|57|| Формулировка работоспособности (корректность и время работы) алгоритма A∗ в случае монотонной, допустимой или произвольной эвристики. Доказательство для монотонного случая. |-
+|57|| Формулировка работоспособности (корректность и время работы) алгоритма A∗ в случае монотонной, допустимой или произвольной эвристики. Доказательство для монотонного случая.
 |58|| Алгоритм Флойда: поиск попарных кратчайших расстояний в графе без отрицательных циклов. Реализация, асимптотика.
@@ Строка 399: / Строка 400: @@
 |97|| Задача LCA. Алгоритм Фарах-Колтона и Бендера.
 |}

@@ Строка 161: / Строка 161: @@
 |-
-|37|| Постановка и решение задачи 2SAT (применение алгоритма выделения компонент сильной |-
+|37|| Постановка и решение задачи 2SAT (применение алгоритма выделения компонент сильной связности).
 |-
@@ Строка 171: / Строка 169: @@
 |-
-|39|| Мосты, точки сочленения. Введение функции ret. Критерий того, что ребро является мостом. |40|| Насчёт ret в неориентированном графе, нахождение мостов.
+|39|| Мосты, точки сочленения. Введение функции ret. Критерий того, что ребро является мостом.
 |-

@@ Строка 52: / Строка 52: @@
 |-
-|8|| Задача о рюкзаке: решения с динамикой по весу или по стоимости, что лучше выбрать. |-
+|8|| Задача о рюкзаке: решения с динамикой по весу или по стоимости, что лучше выбрать. Восстановление ответа.
 |-
-|9|| Задача о рюкзаке: сверхполиномиальность известных алгоритмов. Неоптимальность жадного |-
+|9|| Задача о рюкзаке: сверхполиномиальность известных алгоритмов. Неоптимальность жадного алгоритма.
 |-
@@ Строка 128: / Строка 124: @@
 |-
-|27|| Определение k-независимого семейства, зависимость асимптотики операций от типа |-
+|27|| Определение k-независимого семейства, зависимость асимптотики операций от типа семейства, из которого выбирается хеш-функция и вида пробирования (б/д).
 |-

@@ Строка 259: / Строка 259: @@
 |-
-|61| Алгоритм Форда—Беллмана: нахождение кратчайших расстояний от одной вершины до всех в случае наличия отрицательных циклов.
+|61|| Алгоритм Форда—Беллмана: нахождение кратчайших расстояний от одной вершины до всех в случае наличия отрицательных циклов.
 |-