Программа

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

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

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

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

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

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

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

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

Графы

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

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

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

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

Вероятностный алгоритм. Сведение к задаче выполнимости

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

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

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

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

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

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

Эвристические алгоритмы

Алгоритм A*

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

Применение в ГИС (обзор алгоритма ALT)

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

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

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

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

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

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

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

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

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

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

2-окружение

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

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

Строки

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

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

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

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

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

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

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

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

Наивный алгоритм

КМП

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

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

Trie

Задача о словаре

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

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

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

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

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

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

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

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

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

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

Разное

Сложность алгоритмов. Виды сложности

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Клики

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

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

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

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

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

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

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

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

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

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

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

Сведения