Алгоритмы и структуры данных II. Базовый поток весна 2025
Содержание
Общие сведения
На курсе рассматриваются классические алгоритмы и структуры данных поиска. В частности алгоритмы вычислительной геометрии и структуры данных, основанные на хеш-функциях. Значительная часть курса посвящена алгоритмам обработки графов: обходы, кратчайшие пути, потоки в транспортных сетях.
Программа курса и сдача домашек
В рамках программы изучаются следующие темы:
- 1. Вычислительная геометрия на плоскости.
- 2. Выпуклые многоугольники.
- 3. Выпуклые оболочки в 2D: алгоритмы Джарвиса, Грэхема, Чана.
- 4. Хеш-таблицы. Простое равномерное хеширование.
- 5. Универсальные семейства хеш-функций.
- 6. Идеальное хеширование статического множества (алгоритм FKS).
- 7. Система непересекающихся множеств.
- 8. Биномиальная пирамида. Фибоначчиева пирамида.
- 9. Графы. Представление графов в памяти.
- 10. Обход в глубину. Лемма о белых путях. Критерий ацикличности.
- 11. Топологическая сортировка. Поиск компонент сильной связности.
- 12. Мосты и точки сочленения.
- 13. Кратчайшие пути: алгоритм Дейкстры, алгоритм Форда-Беллмана.
- 14. Кратчайшие пути: алгоритм Флойда-Уоршелла, алгоритм Джонсона.
- 15. Потоки в графах. Теорема Форда-Фалкерсона.
Руководитель курса
Ибрагимов Булат
Преподаватели курса
Ахтямов Д.Р.
Гордица А.Д.
Хожаев И.С.
Пронякин А.А.
Решетникова Д.Д.
Озернова В.С.
Фирсов С.
Материалы занятий
Критерии получения оценки
Оценка за семестр (с округлением вниз:
0,7*ДЗ + 0,3 * ЗАЧ,
где
ДЗ – средний балл за все задачи, сданные в семестре,
ЗАЧ – оценка за зачет, полученная в семестре.
По курсу будет 3 домашних задания и 1 контрольная работа в конце семестра. Средний балл за домашние задания составляет 80% от итоговой оценки, контрольная - 20%. В каждом задании есть набор обязательных задач, решение которых необходимо для получения положительной оценки.
