Подготовка к экзамену
Алгоритмы и структуры данных, часть 2 · разборы билетов, интерактивные визуализации, эталонный код
интерактивпошаговый прогон с кнопками
теорияразбор устного вопроса
задачаразбор задачи + код
День 1 Графы и обходы
DFS/BFS, топологическая сортировка, компоненты связности, мосты и точки сочленения, BFS-модификации.
Вопрос 1 — Топологическая сортировка
Определение, существование, DFS и Кан, корректность, как отвечать.
теория
Задача 2 — Ранг графа
Степени вершин, max суммы по рёбрам. Два прохода.
задача
Задача 3 — Можно ли закрыть курсы
Проверка ацикличности, алгоритм Кана, разбор.
задача
Задача 3 — Кан по шагам
Пошаговая визуализация: indeg, очередь, подсветка кода.
интерактив
Задача 4 — Ребро до дерева
DFS ищет цикл в графе N вершин/N рёбер. Пошагово.
интерактив
Задача 5 — Сигнал, веса {1,2}
1-k BFS по бакетам расстояний. Пошагово.
интерактив
Задача 7 — Число путей в DAG
dp по топосорту, разбор и код.
задача
Задача 10 — Чередование цветов
BFS по состояниям (вершина, цвет). Пошагово.
интерактив
День 2 Взвешенные пути, MST, теория чисел
Дейкстра, A*, Беллман-Форд, отрицательные циклы, Джонсон, Флойд, DSU, MST, Прим, Крускал, RSA, Диффи-Хеллман.
Интерактивные задачи
Теория устных вопросов
Вопросы 6–11 — Кратчайшие пути
Дейкстра, A*, Форд-Беллман, отриц. цикл, Джонсон, Флойд.
теория
Вопросы 14–17 — MST и DSU
DSU, лемма о безопасном ребре, Прим, Крускал.
теория
Вопросы 12–13 — Теория чисел
Эйлер, RSA, показатели, Диффи-Хеллман.
теория
День 3 Строки, автоматы, эвристики
Хеширование, префикс-функция, КМП, бор, Ахо-Корасик, имитация отжига, генетический алгоритм.
Интерактивные задачи
Теория устных вопросов
Инструменты