This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision | ||
courses:algorithms_building_and_analysis:lectures [2024/02/10 09:00] kalishenko |
courses:algorithms_building_and_analysis:lectures [2024/05/29 17:33] (current) kalishenko |
||
---|---|---|---|
Line 9: | Line 9: | ||
* Амортизированная | * Амортизированная | ||
* В среднем | * В среднем | ||
+ | * В худшем | ||
===== Поиск с возвращением ===== | ===== Поиск с возвращением ===== | ||
Line 20: | Line 21: | ||
===== Жадные алгоритмы ===== | ===== Жадные алгоритмы ===== | ||
- | - ... | + | - Задача об оптимальном расписании |
+ | - Задача о префиксном кодировании | ||
+ | - Принцип доказательства оптимальности работы жадного алгоритма | ||
===== Графы ===== | ===== Графы ===== | ||
Line 35: | Line 38: | ||
- Оптимизация Штейна алгоритма Каргера | - Оптимизация Штейна алгоритма Каргера | ||
- | ==== Кратчайшие пути. A* и его расширения ==== | + | ==== Кратчайшие пути. A* ==== |
- | - Напоминание о A* | + | - Напоминание об алгоритмах поиска пути: |
+ | - Поиск в ширину | ||
+ | - Дейкстра | ||
+ | - A*: | ||
+ | - Выбор направления пути Дейкстрой при 0-взвешивании рёбер оптимального пути | ||
+ | - Доказательство неизменности пути при перевзвешивании рёбер | ||
+ | - Ограничения А* | ||
- Эвристические функции | - Эвристические функции | ||
+ | |||
+ | ==== Кратчайшие пути. Расширения A* ==== | ||
- Алгоритм ALT | - Алгоритм ALT | ||
- Алгоритм REACH | - Алгоритм REACH | ||
- | - Алгоритм Arc flags | + | - Оптимизация слияния рёбер |
- | + | ||
- | ==== Топологическая сортировка ==== | + | |
- | - Ограничения на циклы | + | |
- | - Алгоритм нумерацией шагов обхода | + | |
- | - Алгоритм исключения вершины с минимальным количеством входящих рёбер | + | |
==== Задача о коммивояжёре ==== | ==== Задача о коммивояжёре ==== | ||
Line 58: | Line 64: | ||
==== Потоки в графах ==== | ==== Потоки в графах ==== | ||
+ | - Напоминание Форда-Фалкерсона | ||
+ | * Идея поиска пути в остаточной сети | ||
+ | * Обратные рёбра | ||
+ | * Сложность | ||
- Алгоритм Гольдберга (проталкивания предпотока): | - Алгоритм Гольдберга (проталкивания предпотока): | ||
* Идея push-relabel алгоритмов | * Идея push-relabel алгоритмов | ||
Line 85: | Line 95: | ||
- Наивное построение префикс-функции и его сложность | - Наивное построение префикс-функции и его сложность | ||
- Построение префикс-функции за линейное время | - Построение префикс-функции за линейное время | ||
+ | - Оптимизация сложности по памяти | ||
==== Алгоритм Ахо-Корасик ==== | ==== Алгоритм Ахо-Корасик ==== | ||
Line 91: | Line 102: | ||
- Задача о словаре | - Задача о словаре | ||
- Алгоритм Ахо-Корасик | - Алгоритм Ахо-Корасик | ||
+ | |||
+ | ==== Суффиксные деревья и массивы ==== | ||
+ | - Суффиксное дерево - мотивация, сложность, поиск | ||
+ | - Суффиксный массив - мотивация, сложность, поиск | ||
+ | - Алгоритм Укконена | ||
===== Динамическое программирование ===== | ===== Динамическое программирование ===== | ||
Line 97: | Line 113: | ||
* Сведение к графу | * Сведение к графу | ||
* Выделение подзадачи | * Выделение подзадачи | ||
- | - Задача о рюкзаке: | ||
- | * Без повторений (одномерный случай) | ||
- | * С повторениями (двумерный случай) | ||
- Задача о порядке перемножения матриц | - Задача о порядке перемножения матриц | ||
Line 137: | Line 150: | ||
- Применения и сложность задачи построения клик графа | - Применения и сложность задачи построения клик графа | ||
- Алгоритм нахождения клик на основе поиска с возвращением. | - Алгоритм нахождения клик на основе поиска с возвращением. | ||
+ | |||
+ | ==== Топологическая сортировка ==== | ||
+ | - Ограничения на циклы | ||
+ | - Алгоритм нумерацией шагов обхода | ||
+ | - Алгоритм исключения вершины с минимальным количеством входящих рёбер | ||
==== Алгоритм Рабина-Карпа ==== | ==== Алгоритм Рабина-Карпа ==== | ||
Line 148: | Line 166: | ||
- Метод расщепления | - Метод расщепления | ||
- Сведения | - Сведения | ||
+ | |||
+ | ===== Динамическое программирование ===== | ||
+ | - Задача о рюкзаке: | ||
+ | * Без повторений (одномерный случай) | ||
+ | * С повторениями (двумерный случай) | ||
</WRAP> | </WRAP> |