This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision Next revision Both sides next revision | ||
courses:algorithms_building_and_analysis:lectures [2023/03/26 18:16] kalishenko |
courses:algorithms_building_and_analysis:lectures [2024/05/01 19:19] kalishenko |
||
---|---|---|---|
Line 1: | Line 1: | ||
====== Программа ====== | ====== Программа ====== | ||
+ | ===== Сложность алгоритмов ===== | ||
+ | - Виды сложности: | ||
+ | * Операции | ||
+ | * Время | ||
+ | * Память | ||
+ | - Понятие вычислительной сложности в зависимости от размера входа | ||
+ | - Константная сложность на примере vector и unordered_set: | ||
+ | * Амортизированная | ||
+ | * В среднем | ||
+ | * В худшем | ||
+ | |||
===== Поиск с возвращением ===== | ===== Поиск с возвращением ===== | ||
- Идея поиска с возвращением (backtracking) | - Идея поиска с возвращением (backtracking) | ||
Line 8: | Line 19: | ||
* Пример на площади фигуры | * Пример на площади фигуры | ||
* Ограничения и условия применимости | * Ограничения и условия применимости | ||
+ | |||
+ | ===== Жадные алгоритмы ===== | ||
+ | - Задача об оптимальном расписании | ||
+ | - Задача о префиксном кодировании | ||
+ | - Принцип доказательства оптимальности работы жадного алгоритма | ||
===== Графы ===== | ===== Графы ===== | ||
Line 22: | Line 38: | ||
- Оптимизация Штейна алгоритма Каргера | - Оптимизация Штейна алгоритма Каргера | ||
- | ==== Кратчайшие пути. A* ==== | + | ==== Кратчайшие пути. A* и его расширения ==== |
- | - Эвристические алгоритмы | + | - Напоминание об алгоритмах поиска пути: |
- | - Алгоритм A* | + | - Поиск в ширину |
+ | - Дейкстра | ||
+ | - A*: | ||
+ | - Выбор направления пути Дейкстрой при 0-взвешивании рёбер оптимального пути | ||
+ | - Доказательство неизменности пути при перевзвешивании рёбер | ||
+ | - Ограничения А* | ||
- Эвристические функции | - Эвристические функции | ||
- | - Применение в ГИС (обзор алгоритма ALT) | ||
- | ==== Топологическая сортировка ==== | + | ==== Кратчайшие пути. Расширения A* ==== |
- | - Ограничения на циклы | + | - Алгоритм ALT |
- | - Алгоритм нумерацией шагов обхода | + | - Алгоритм REACH |
- | - Алгоритм исключения вершины с минимальным количеством входящих рёбер | + | - Алгоритм Arc flags |
==== Задача о коммивояжёре ==== | ==== Задача о коммивояжёре ==== | ||
Line 42: | Line 62: | ||
* Имитация отжига | * Имитация отжига | ||
- Приближённое решение (2-приближённый алгоритм) | - Приближённое решение (2-приближённый алгоритм) | ||
+ | |||
+ | ==== Потоки в графах ==== | ||
+ | - Алгоритм Гольдберга (проталкивания предпотока): | ||
+ | * Идея push-relabel алгоритмов | ||
+ | * Формализмы и инварианты | ||
+ | * Доказательство корректности | ||
+ | * Сравнение сложности с Фордом-Фалкерсоном | ||
+ | |||
+ | ==== Изоморфизм графов ==== | ||
+ | - Задача изоморфизма: | ||
+ | * Точный изоморфизм | ||
+ | * Поиск подграфа в графе | ||
+ | - Алгоритм Ульмана (переборный с матрицей) | ||
+ | - Применение изоморфизма | ||
===== Строки ===== | ===== Строки ===== | ||
Line 53: | Line 87: | ||
- Основные определения | - Основные определения | ||
- Задача точного поиска образца в строке | - Задача точного поиска образца в строке | ||
- | - Наивный алгоритм | + | - Наивный алгоритм и его сложность |
- | - КМП | + | - Алгоритм КМП |
+ | - Наивное построение префикс-функции и его сложность | ||
+ | - Построение префикс-функции за линейное время | ||
+ | - Оптимизация сложности по памяти | ||
==== Алгоритм Ахо-Корасик ==== | ==== Алгоритм Ахо-Корасик ==== | ||
Line 67: | Line 104: | ||
* Сведение к графу | * Сведение к графу | ||
* Выделение подзадачи | * Выделение подзадачи | ||
- | - Задача о рюкзаке: | ||
- | * Без повторений (одномерный случай) | ||
- | * С повторениями (двумерный случай) | ||
- Задача о порядке перемножения матриц | - Задача о порядке перемножения матриц | ||
- | |||
- | ===== Разное ===== | ||
- | - Сложность алгоритмов. Виды сложности | ||
----- | ----- | ||
Line 95: | Line 126: | ||
==== Потоки в графах ==== | ==== Потоки в графах ==== | ||
- Алгоритм Форда-Фалкерсона | - Алгоритм Форда-Фалкерсона | ||
- | - Алгоритм Гольдберга (проталкивания предпотока) | ||
==== Кратчайшие пути. Дейкстра ==== | ==== Кратчайшие пути. Дейкстра ==== | ||
Line 111: | Line 141: | ||
- Применения и сложность задачи построения клик графа | - Применения и сложность задачи построения клик графа | ||
- Алгоритм нахождения клик на основе поиска с возвращением. | - Алгоритм нахождения клик на основе поиска с возвращением. | ||
+ | |||
+ | ==== Топологическая сортировка ==== | ||
+ | - Ограничения на циклы | ||
+ | - Алгоритм нумерацией шагов обхода | ||
+ | - Алгоритм исключения вершины с минимальным количеством входящих рёбер | ||
==== Алгоритм Рабина-Карпа ==== | ==== Алгоритм Рабина-Карпа ==== | ||
Line 122: | Line 157: | ||
- Метод расщепления | - Метод расщепления | ||
- Сведения | - Сведения | ||
+ | |||
+ | ===== Динамическое программирование ===== | ||
+ | - Задача о рюкзаке: | ||
+ | * Без повторений (одномерный случай) | ||
+ | * С повторениями (двумерный случай) | ||
</WRAP> | </WRAP> |