Понятие вычислительной сложности в зависимости от размера входа
Константная сложность на примере vector и unordered_set:
Амортизированная
В среднем
В худшем
Поиск с возвращением
Идея поиска с возвращением (backtracking)
Пример на задаче о ферзях
Подходы метода ветвей и границ по отсеканию вариантов
Изменение сложности алгоритма за счёт различных оптимизаций
Метод Монте-Карло
Пример на размере дерева
Пример на площади фигуры
Ограничения и условия применимости
Жадные алгоритмы
Задача о построении МОД
Задача об оптимальном расписании
Задача о префиксном кодировании
Принцип доказательства оптимальности работы жадного алгоритма
Графы
Раскраска в 3 цвета
Алгоритм полного перебора
Перебор с учётом выбора только из 2 цветов
Перебор подмножеств размера ⇐ n/3
Вероятностный алгоритм
Сведение к задаче выполнимости
Применение вероятности
Сведение к двудольному графу 2SAT
Применение раскраски на практике
Минимальный разрез
Примеры практических задач
Алгоритм Каргера
Оптимизация Штейна алгоритма Каргера
Кратчайшие пути. A*
Напоминание об алгоритмах поиска пути:
Поиск в ширину
Дейкстра
A:
- Выбор направления пути Дейкстрой при 0-взвешивании рёбер оптимального пути
- Доказательство неизменности пути при перевзвешивании рёбер
- Ограничения и сложность А
Эвристические функции
Проблемы А* для дискретных пространств с препятствиями
Расширения A*
Идеи Тета*
Алгоритм ALT
Задача о коммивояжёре
Сложность полного перебора
Метод ветвей и границ:
Отсечка по текущему найденному пути
Отсечка по весу МОД
Локальный поиск
2-окружение
Имитация отжига
Приближённое решение (2-приближённый алгоритм)
Потоки в графах
Напоминание Форда-Фалкерсона
Идея поиска пути в остаточной сети
Обратные рёбра
Сложность
Краевые случаи
Алгоритм Гольдберга (проталкивания предпотока):
Идея push-relabel алгоритмов
Формализмы и инварианты
Доказательство корректности
Сравнение сложности с Фордом-Фалкерсоном
Изоморфизм графов
Задача изоморфизма:
Точный изоморфизм
Поиск подграфа в графе
Алгоритм Ульмана (переборный с матрицей)
Применение изоморфизма
Симбиоз ИИ и А*
Выбор лучших нейросетевых моделей поиска пути с применением генетических алгоритмов
Применение рекуррентных сетей с динамическими вероятностными эвристиками при многоагентном планировании
Анализ изображения препятствий для коректировки эвристических фукнций с примением свёрточных сетей и трансформеров
Динамические графы
Постановка задачи, отличие от статических графов
Практические примеры
Поддержка динамического МОД после обновлений графа
Строки
Редакционное расстояние
Расстояние Левенштейна (редакционное расстояние)
Вычисление редакционного расстояния методом ДП
Восстановление РП по таблице (обратный ход в методе ДП)
Сведение задачи к путям в графе
Алгоритм Кнута-Морриса-Пратта
Основные определения
Задача точного поиска образца в строке
Наивный алгоритм и его сложность
Алгоритм КМП
Наивное построение префикс-функции и его сложность
Построение префикс-функции за линейное время
Оптимизация сложности по памяти
Алгоритм Ахо-Корасик
Задача точного поиска набора образцов
Бор
Построение суффиксных ссылок
Алгоритм поиска и его сложность
Суффиксные деревья и массивы
Суффиксное дерево - мотивация, сложность, поиск
Суффиксный массив - мотивация, сложность, поиск
Алгоритм Укконена
Динамическое программирование
Примеры вычисления чисел Фибоначчи
Масимальная возрастающая подпоследовательность:
Сведение к графу
Выделение подзадачи
Задача о порядке перемножения матриц
Исключено из программы после переноса в другие курсы
Графы и структуры данных
Графы: определения и примеры. Упорядоченный граф
Представления графов: матрица инциденций, матрица смежности, список пар, структура смежности (списки инцидентности)
Остовные деревья
Задача о связности графа и остовный лес
Минимальное остовное дерево. Теорема «о минимальном ребре»: