Алгоритмы и структуры данных, 1 курс ИС
Весенний семестр
Материалы к лекциям
Лабораторные работы
- Как сдавать задачи
- Cроки посыла задач лабораторных работ в систему ограничены 2-3 неделями.
План курса (каждая лекция может занимать 1-2 пары)
- Лекция 1. Обходы графов.
Обход в глубину: алгоритм. Обход в ширину: алгоритм. Топологическая сортировка. Поиск компонент сильной связности и конденсация графа.
- Лекция 2. Минимальные остовные деревья.
Поиск центра и диаметра дерева через BFS. Обобщенный алгоритм поиска MST. Алгоритмы Крускала и Прима с доказательством времени работы.
- Лекция 3. Алгоритмы поиска кратчайших путей в графах.
Ослабление (релаксация). Теорема нахождении кратчайших путей с помощью BFS. Алгоритмы поиска кратчайших путей из одной врешины: Беллман-Форд + лемма "свойство ослабления пути", DAG, Дейкстра с очередью и массивом. Алгоритм поиска кратчайших путей между всеми парами вершин: Флойд-Уоршалл. Ограничения и время работы для всех алгоритмов.
- Лекция 4. Задача о максимальном потоке.
Определения и постановка задачи. Метод Форда-Фалкерсона. Концепции: остаточная сеть, увеличивающие пути, разрезы.Теорема о максимальном потоке и минимальном разрезе. Алгоритм Форда-Фалкерсона и время работы. Пример работы алгоритма Эдмондса-Крапа .Алгоритм Эдмондса-Карпа: обоснование и время работы. Поиск максимального паросочетания.
- Лекция 5. Поиск подстрок.
Лемма о перекрывающихся суффиксах. Простейший алгоритм поиска подстрок. Алгоритм Рабина-Карпа: итеративное вычисление полиномиальной хеш-функции, пересчет при сдвиге, алгоритм Р-К. Z-функция: тривиальный и эффективный алгоритмы. Построение префикс-функции. Алгоритм Кнута-Морриса-Пратта. Конечные автоматы. Поиск подстрок с помощью конечных атоматов.
Литература
- Кормен, Лейзерсон и др. "Алгоритмы. Построение и анализ."
- Ф. Харари "Теория графов."
- М.О. Асанов, В.А. Баранский, В.В. Расин "Дискретная математика. Графы, матроиды, алгоритмы."
- Ахо, Хопкрофт, Ульман "Структуры данных и алгоритмы."