Данный репозиторий содержит материалы курса, посвящённого алгоритмам и структурам данных, который читался в осеннем семестре 2024 года и весеннем семестре 2025 года.
Лектор - Илья Осокин
Репозиторий постепенно обновляется по мере продвижения курса. Здесь Вы можете найти:
Кроме того, у данного курса есть:
- Страница в Google Classroom - тут сдаются теоретические домашние задания
- Страница с записями занятий - тут есть записи занятий
- Группа на codeforces - здесь проходят контесты
Вы также можете ознакомиться со списком рекомендованной литературы:
- Алгоритмы. Построение и анализ. Кормен. - тут есть все. Можно использовать как справочник или как инструмент самообороны
- Алгоритмы. Дасгупта. - покороче, с пассажами пояснительного характера
Вы можете ознакомиться полным списком литературы на нашем Яндекс.Диске. Все книги доступны по ссылкам в формате PDF.
Курс разделен на две части: первая читалась осенью 2024-го года и включала в себя теоретическую часть по алгоритмам. Вторая часть читалась весной 2025-го года и включала в себя практические занятия по пройденным темам.
| Тема занятия | Дата занятия | Конспект | Домашнее задание | Дедлайн |
|---|---|---|---|---|
| Введение. Понятие асимптотической сложности алгоритма. введение в нотацию для оценки асимптотической сложности. | 13.09.2024 | lecture | assignment | 19.09.2024 |
| Введение в рекурсию. Рекурсивные алгоритмы вычисления чисел Фибоначчи. Алгоритм быстрого возведения в степень. Вычисление чисел Фибоначчи при помощи быстрого возведения в степень. | 20.09.2024 | lecture | assignment | 26.09.2024 |
| Основная теорема о рекуррентных соотношениях. Применение мастер-теоремы для оценки сложности рекуррентных алгоритмов. Сортировка слиянием. Бинарный поиск в отсортированном массиве. Метод Акра-Баззи. | 27.09.2024 | lecture | assignment | 03.10.2024 |
| Алгоритм быстрой сортировки (quicksort). Выбор опорного элемента. Поиск k-ой порядковой статистики за линейное время (quickselect). | 04.10.2024 | lecture | assignment | 10.10.2024 |
| Алгоритм Евклида. Битовое представление чисел. Атомарные битовые операции. Поиск в массиве. Линейный поиск элемента, удовлетворяющего условию. Бинарный поиск. | 11.10.2024 | lecture | assignment | 17.10.2025 |
| Повторение пройденного материала. k-ая порядковая статистика. Majority Element. Расширенный алгоритм Евклида. | 18.10.2025 | lectures | assignment | 24.10.2024 |
| Решение диофантовых уравнений | 01.11.2024 | lecture | - | - |
| Стек. Очередь. Бинарное дерево. Куча. Построение кучи из линейной последовательности. Сортировка кучей. Задачи планирования и похода к точке в пространстве. Графы. Основные понятия. Методы хранения графов в памяти. Поиск в глубину (DFS). Поиск в ширину (BFS). | 08.11.2024 | lecture | assignment | 17.11.2024 |
| Алгоритмы на графах. Выделение компонент сильной связности. Топологическая сортировка. Проверка графа на двудольность. Простейшие алгоритмы поиска кратчайшего пути. Алгоритм Дейкстры. | 15.11.2024 | lectures | assignments | 24.11.2024 |
| Поиск кратчайшего пути из одной вершины (single source). Случай отрицательных весов. Алгоритм Беллмана-Форда. Решения задач на поиск пути наименьшей стоимости в графе. | 22.11.2024 | lectures | assignment | 30.11.2024 |
| Сильная связность в ориентированном графе. Дополнение ориентированного графа до сильно связного. Алгоритм Эсварана-Тарьяна. | 29.11.2024 | lectures | assignments | 05.12.2024 |
| Повторение. Графы. Алгоритмы обхода графа. Использование различных методов обхода в практических задачах. Алгоритмы поиска кратчайших путей. | 06.12.2024 | lectures | assignment | 12.12.2024 |
| Минимальные остовные деревья. Алгоритм Краскала поиска минимального остовного дерева. Система непересекающихся множеств (Disjoint-set). Методы оптимизации поиска минимального остовного дерева. | 13.12.2024 | lectures | - | - |
| Повторение. Минимальные остовные деревья. Алгоритм Краскала. Disjoint-set и его оптимизации. Введение в динамическое программирование. Поиск наименьшего редакционного расстояния (Расстояние Левенштейна). | 20.02.2025 | lecture | assignment | 26.02.2025 |
| Продолжение динамического программирования. Алгоритм Флойда-Уоршелла. Задача о рюкзаке. Метод Ветвей и Границ. Применение динамического программирования для упрощения вычислений. Разложение числа на сумму других чисел. Задача о банкоматах. | 28.02.2025 | lecture | assignment | 06.03.2025 |
| Представление графа в виде матрицы. Матрицы смежности. Операции над матрице смежности. Проверка наличия пути длины k. Проверка графа на связность методом возведения матрицы смежности в степень. | 06.03.2025 | lecture | assignment | 12.03.2025 |
| Тема занятия | Дата занятия | Код | Домашнее задание | Дедлайн |
|---|---|---|---|---|
| Поиск k-го числа Фибоначчи. Использование быстрого возведения в степень. Измерение времени выполнения программы. Алгоритмы поиска максимума. Сравнение поиска полным перебором и линейного алгоритма поиска. | 06.03.2025 | code | - | - |