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