courses:algorithms_building_and_analysis:lectures
Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision Last revision Both sides next revision | ||
|
courses:algorithms_building_and_analysis:lectures [2022/04/19 12:32] kalishenko |
courses:algorithms_building_and_analysis:lectures [2024/05/11 23:09] kalishenko |
||
|---|---|---|---|
| Line 1: | Line 1: | ||
| ====== Программа ====== | ====== Программа ====== | ||
| + | ===== Сложность алгоритмов ===== | ||
| + | - Виды сложности: | ||
| + | * Операции | ||
| + | * Время | ||
| + | * Память | ||
| + | - Понятие вычислительной сложности в зависимости от размера входа | ||
| + | - Константная сложность на примере vector и unordered_set: | ||
| + | * Амортизированная | ||
| + | * В среднем | ||
| + | * В худшем | ||
| + | |||
| ===== Поиск с возвращением ===== | ===== Поиск с возвращением ===== | ||
| - Идея поиска с возвращением (backtracking) | - Идея поиска с возвращением (backtracking) | ||
| Line 8: | Line 19: | ||
| * Пример на площади фигуры | * Пример на площади фигуры | ||
| * Ограничения и условия применимости | * Ограничения и условия применимости | ||
| + | |||
| + | ===== Жадные алгоритмы ===== | ||
| + | - Задача об оптимальном расписании | ||
| + | - Задача о префиксном кодировании | ||
| + | - Принцип доказательства оптимальности работы жадного алгоритма | ||
| ===== Графы ===== | ===== Графы ===== | ||
| Line 18: | Line 34: | ||
| ==== Минимальный разрез ==== | ==== Минимальный разрез ==== | ||
| - | - Идея алгоритма на основе поиска потока | ||
| - Примеры практических задач | - Примеры практических задач | ||
| - Алгоритм Каргера | - Алгоритм Каргера | ||
| Line 24: | Line 39: | ||
| ==== Кратчайшие пути. A* ==== | ==== Кратчайшие пути. A* ==== | ||
| - | - Эвристические алгоритмы | + | - Напоминание об алгоритмах поиска пути: |
| - | - Алгоритм A* | + | - Поиск в ширину |
| + | - Дейкстра | ||
| + | - A*: | ||
| + | - Выбор направления пути Дейкстрой при 0-взвешивании рёбер оптимального пути | ||
| + | - Доказательство неизменности пути при перевзвешивании рёбер | ||
| + | - Ограничения А* | ||
| - Эвристические функции | - Эвристические функции | ||
| - | - Применение в ГИС (обзор алгоритма ALT) | ||
| - | ==== Топологическая сортировка ==== | + | ==== Кратчайшие пути. Расширения A* ==== |
| - | - Ограничения на циклы | + | - Алгоритм ALT |
| - | - Алгоритм нумерацией шагов обхода | + | - Алгоритм REACH |
| - | - Алгоритм исключения вершины с минимальным количеством входящих рёбер | + | - Алгоритм Arc flags |
| + | |||
| + | ==== Задача о коммивояжёре ==== | ||
| + | - Сложность полного перебора | ||
| + | - Метод ветвей и границ: | ||
| + | * Отсечка по текущему найденному пути | ||
| + | * Отсечка по весу МОД | ||
| + | - Локальный поиск | ||
| + | * 2-окружение | ||
| + | * Имитация отжига | ||
| + | - Приближённое решение (2-приближённый алгоритм) | ||
| + | |||
| + | ==== Потоки в графах ==== | ||
| + | - Напоминание Форда-Фалкерсона | ||
| + | * Идея поиска пути в остаточной сети | ||
| + | * Обратные рёбра | ||
| + | * Сложность | ||
| + | - Алгоритм Гольдберга (проталкивания предпотока): | ||
| + | * Идея push-relabel алгоритмов | ||
| + | * Формализмы и инварианты | ||
| + | * Доказательство корректности | ||
| + | * Сравнение сложности с Фордом-Фалкерсоном | ||
| + | |||
| + | ==== Изоморфизм графов ==== | ||
| + | - Задача изоморфизма: | ||
| + | * Точный изоморфизм | ||
| + | * Поиск подграфа в графе | ||
| + | - Алгоритм Ульмана (переборный с матрицей) | ||
| + | - Применение изоморфизма | ||
| ===== Строки ===== | ===== Строки ===== | ||
| Line 44: | Line 91: | ||
| - Основные определения | - Основные определения | ||
| - Задача точного поиска образца в строке | - Задача точного поиска образца в строке | ||
| - | - Наивный алгоритм | + | - Наивный алгоритм и его сложность |
| - | - КМП | + | - Алгоритм КМП |
| + | - Наивное построение префикс-функции и его сложность | ||
| + | - Построение префикс-функции за линейное время | ||
| + | - Оптимизация сложности по памяти | ||
| ==== Алгоритм Ахо-Корасик ==== | ==== Алгоритм Ахо-Корасик ==== | ||
| Line 53: | Line 103: | ||
| - Алгоритм Ахо-Корасик | - Алгоритм Ахо-Корасик | ||
| - | ===== Задачи выполнимости ===== | + | ===== Динамическое программирование ===== |
| - | - Локальный поиск | + | - Примеры вычисления чисел Фибоначчи |
| - | - Метод расщепления | + | - Масимальная возрастающая подпоследовательность: |
| - | - Сведения | + | * Сведение к графу |
| - | + | * Выделение подзадачи | |
| - | ===== Разное ===== | + | - Задача о порядке перемножения матриц |
| - | - Сложность алгоритмов. Виды сложности | + | |
| + | ----- | ||
| + | <WRAP> | ||
| ===== Не рассматривается (пересечение с курсами и т.п.) ===== | ===== Не рассматривается (пересечение с курсами и т.п.) ===== | ||
| ==== Графы и структуры данных ==== | ==== Графы и структуры данных ==== | ||
| Line 79: | Line 130: | ||
| ==== Потоки в графах ==== | ==== Потоки в графах ==== | ||
| - Алгоритм Форда-Фалкерсона | - Алгоритм Форда-Фалкерсона | ||
| - | - Алгоритм Гольдберга (проталкивания предпотока) | ||
| ==== Кратчайшие пути. Дейкстра ==== | ==== Кратчайшие пути. Дейкстра ==== | ||
| Line 95: | Line 145: | ||
| - Применения и сложность задачи построения клик графа | - Применения и сложность задачи построения клик графа | ||
| - Алгоритм нахождения клик на основе поиска с возвращением. | - Алгоритм нахождения клик на основе поиска с возвращением. | ||
| + | |||
| + | ==== Топологическая сортировка ==== | ||
| + | - Ограничения на циклы | ||
| + | - Алгоритм нумерацией шагов обхода | ||
| + | - Алгоритм исключения вершины с минимальным количеством входящих рёбер | ||
| ==== Алгоритм Рабина-Карпа ==== | ==== Алгоритм Рабина-Карпа ==== | ||
| Line 101: | Line 156: | ||
| - Алгоритм быстрого вычисления всех хешей текста длины образца | - Алгоритм быстрого вычисления всех хешей текста длины образца | ||
| - Алгоритм Рабина-Карпа | - Алгоритм Рабина-Карпа | ||
| + | |||
| + | ===== Задачи выполнимости ===== | ||
| + | - Локальный поиск | ||
| + | - Метод расщепления | ||
| + | - Сведения | ||
| + | |||
| + | ===== Динамическое программирование ===== | ||
| + | - Задача о рюкзаке: | ||
| + | * Без повторений (одномерный случай) | ||
| + | * С повторениями (двумерный случай) | ||
| + | </WRAP> | ||
courses/algorithms_building_and_analysis/lectures.txt · Last modified: 2024/05/24 07:34 by kalishenko
Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Share Alike 4.0 International
