Дополнительные главы алгоритмов, часть 2
Санкт-Петербург, весна 2019
Описание
Вторая часть продвинутого курса по алгоритмам. Курс рассчитан на студентов, сдавших базовые курсы по алгоритмам, предлагаемые в CS центре, и желающих применить свои знания для более сложных задач.
В этой серии мы поговорим про:
- Кратчайшие пути в графах
- Потоки, паросочетания
- Алгоритмы на строках
- Структуры данных для быстрой работы с целыми числами
- Быстрое преобразование Фурье
Оценка будет складываться из:
- Теоретические задачи (50%)
- Задачи на программирование (50%)
Для зачета нужно получить не менее 60% баллов, для оценки хорошо
— не менее 75%, для оценки отлично
— не менее 90%.
Преподаватели
Список лекций
- Модель вычислений
- Быстрая работа с битовыми векторами
- Структура дерева
- Анализ времени работы
- Применения
- Что еще можно делать с целыми числами
- Fusion Tree
Q-куча и Атомарная куча позволяют за \(O(1)\) совершать операции над кучей, в которой хранится не более \(O(log^\frac{1}{5} n)\) и \(O(log^2 n)\) элементов, соответственно.
Потоки, разрезы
Остаточная сеть, теорема Форда-Фалкерсона
Алгоритм Форда-Фалкерсона
Алгоритм Эдмонса-Карпа
Алгоритм Диница
Алгоритм Диница
Ускорение с помощью масштабирования и динамических деревьев
Потоки в графах с единичной пропускной способностью