Программа

Сложность алгоритмов

Виды сложности:

Операции

Время

Память

Понятие вычислительной сложности в зависимости от размера входа

Константная сложность на примере vector и unordered_set:

Амортизированная

В среднем

В худшем

Поиск с возвращением

Идея поиска с возвращением (backtracking)

Пример на задаче о ферзях

Подходы метода ветвей и границ по отсеканию вариантов

Изменение сложности алгоритма за счёт различных оптимизаций

Метод Монте-Карло

Пример на размере дерева

Пример на площади фигуры

Ограничения и условия применимости

Жадные алгоритмы

Задача о построении МОД

Задача об оптимальном расписании

Задача о префиксном кодировании

Принцип доказательства оптимальности работы жадного алгоритма

Графы

Раскраска в 3 цвета

Алгоритм полного перебора

Перебор с учётом выбора только из 2 цветов

Перебор подмножеств размера ⇐ n/3

Вероятностный алгоритм

Сведение к задаче выполнимости

Применение вероятности

Сведение к двудольному графу 2SAT

Применение раскраски на практике

Минимальный разрез

Примеры практических задач

Алгоритм Каргера

Оптимизация Штейна алгоритма Каргера

Кратчайшие пути. A*

Напоминание об алгоритмах поиска пути:

Поиск в ширину

Дейкстра

A*:

Выбор направления пути Дейкстрой при 0-взвешивании рёбер оптимального пути

Доказательство неизменности пути при перевзвешивании рёбер

Ограничения и сложность А*

Эвристические функции

Проблемы А* для дискретных пространств с препятствиями

Расширения A*

Идеи Тета*

Алгоритм ALT

Задача о коммивояжёре

Сложность полного перебора

Метод ветвей и границ:

Отсечка по текущему найденному пути

Отсечка по весу МОД

Локальный поиск

2-окружение

Имитация отжига

Приближённое решение (2-приближённый алгоритм)

Потоки в графах

Напоминание Форда-Фалкерсона

Идея поиска пути в остаточной сети

Обратные рёбра

Сложность

Алгоритм Гольдберга (проталкивания предпотока):

Идея push-relabel алгоритмов

Формализмы и инварианты

Доказательство корректности

Сравнение сложности с Фордом-Фалкерсоном

Изоморфизм графов

Задача изоморфизма:

Точный изоморфизм

Поиск подграфа в графе

Алгоритм Ульмана (переборный с матрицей)

Применение изоморфизма

Строки

Редакционное расстояние

Расстояние Левенштейна (редакционное расстояние)

Вычисление редакционного расстояния методом ДП

Восстановление РП по таблице (обратный ход в методе ДП)

Сведение задачи к путям в графе

Алгоритм Кнута-Морриса-Пратта

Основные определения

Задача точного поиска образца в строке

Наивный алгоритм и его сложность

Алгоритм КМП

Наивное построение префикс-функции и его сложность

Построение префикс-функции за линейное время

Оптимизация сложности по памяти

Алгоритм Ахо-Корасик

Задача точного поиска набора образцов

Бор

Построение суффиксных ссылок

Алгоритм поиска и его сложность

Суффиксные деревья и массивы

Суффиксное дерево - мотивация, сложность, поиск

Суффиксный массив - мотивация, сложность, поиск

Алгоритм Укконена

Динамическое программирование

Примеры вычисления чисел Фибоначчи

Масимальная возрастающая подпоследовательность:

Сведение к графу

Выделение подзадачи

Задача о порядке перемножения матриц

Не рассматривается (пересечение с курсами и т.п.)

Графы и структуры данных

Графы: определения и примеры. Упорядоченный граф

Представления графов: матрица инциденций, матрица смежности, список пар, структура смежности (списки инцидентности)

Остовные деревья

Задача о связности графа и остовный лес

Минимальное остовное дерево. Теорема «о минимальном ребре»:

Жадный алгоритм (Краскал)

Алгоритм «ближайшего соседа» (Ярник, Прим, Дейкстра)

Алгоритм Борувки (О(m*log n))

Задачи связности

Связные компоненты

Алгоритм нахождения сильно связных компонент (Косарайю)

Потоки в графах

Алгоритм Форда-Фалкерсона

Кратчайшие пути. Дейкстра

Кратчайшие пути от фиксированной вершины

Случай неотрицательных весов: алгоритм Дейкстры

Алгоритм Флойда-Уоршелла вычисления расстояний между всеми парами вершин, одновременное построение путей

Паросочетания

Понятия вершинных и рёберных покрытий

Теорема Галлаи

Алгоритм Куна поиска паросочетания в двудольном графе

Клики

Полные подграфы, клики

Применения и сложность задачи построения клик графа

Алгоритм нахождения клик на основе поиска с возвращением.

Топологическая сортировка

Ограничения на циклы

Алгоритм нумерацией шагов обхода

Алгоритм исключения вершины с минимальным количеством входящих рёбер

Алгоритм Рабина-Карпа

Идея использования хешей для решения задачи точного поиска образца в строке

Полиномиальные хеши для строк

Алгоритм быстрого вычисления всех хешей текста длины образца

Алгоритм Рабина-Карпа

Задачи выполнимости

Локальный поиск

Метод расщепления

Сведения

Динамическое программирование

Задача о рюкзаке:

Без повторений (одномерный случай)

С повторениями (двумерный случай)