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 [2024/01/31 00:47] kalishenko |
courses:algorithms_building_and_analysis:lectures [2024/04/25 21:46] kalishenko |
||
---|---|---|---|
Line 1: | Line 1: | ||
====== Программа ====== | ====== Программа ====== | ||
===== Сложность алгоритмов ===== | ===== Сложность алгоритмов ===== | ||
- | - Виды сложности | + | - Виды сложности: |
+ | * Операции | ||
+ | * Время | ||
+ | * Память | ||
- Понятие вычислительной сложности в зависимости от размера входа | - Понятие вычислительной сложности в зависимости от размера входа | ||
- Константная сложность на примере vector и unordered_set: | - Константная сложность на примере vector и unordered_set: | ||
* Амортизированная | * Амортизированная | ||
* В среднем | * В среднем | ||
+ | * В худшем | ||
===== Поиск с возвращением ===== | ===== Поиск с возвращением ===== | ||
Line 15: | Line 19: | ||
* Пример на площади фигуры | * Пример на площади фигуры | ||
* Ограничения и условия применимости | * Ограничения и условия применимости | ||
+ | |||
+ | ===== Жадные алгоритмы ===== | ||
+ | - Задача об оптимальном расписании | ||
+ | - Задача о префиксном кодировании | ||
+ | - Принцип доказательства оптимальности работы жадного алгоритма | ||
===== Графы ===== | ===== Графы ===== | ||
Line 35: | Line 44: | ||
- Алгоритм REACH | - Алгоритм REACH | ||
- Алгоритм Arc flags | - Алгоритм Arc flags | ||
- | |||
- | ==== Топологическая сортировка ==== | ||
- | - Ограничения на циклы | ||
- | - Алгоритм нумерацией шагов обхода | ||
- | - Алгоритм исключения вершины с минимальным количеством входящих рёбер | ||
==== Задача о коммивояжёре ==== | ==== Задача о коммивояжёре ==== | ||
Line 79: | Line 83: | ||
- Наивное построение префикс-функции и его сложность | - Наивное построение префикс-функции и его сложность | ||
- Построение префикс-функции за линейное время | - Построение префикс-функции за линейное время | ||
+ | - Оптимизация сложности по памяти | ||
==== Алгоритм Ахо-Корасик ==== | ==== Алгоритм Ахо-Корасик ==== | ||
Line 91: | Line 96: | ||
* Сведение к графу | * Сведение к графу | ||
* Выделение подзадачи | * Выделение подзадачи | ||
- | - Задача о рюкзаке: | ||
- | * Без повторений (одномерный случай) | ||
- | * С повторениями (двумерный случай) | ||
- Задача о порядке перемножения матриц | - Задача о порядке перемножения матриц | ||
Line 131: | Line 133: | ||
- Применения и сложность задачи построения клик графа | - Применения и сложность задачи построения клик графа | ||
- Алгоритм нахождения клик на основе поиска с возвращением. | - Алгоритм нахождения клик на основе поиска с возвращением. | ||
+ | |||
+ | ==== Топологическая сортировка ==== | ||
+ | - Ограничения на циклы | ||
+ | - Алгоритм нумерацией шагов обхода | ||
+ | - Алгоритм исключения вершины с минимальным количеством входящих рёбер | ||
==== Алгоритм Рабина-Карпа ==== | ==== Алгоритм Рабина-Карпа ==== | ||
Line 142: | Line 149: | ||
- Метод расщепления | - Метод расщепления | ||
- Сведения | - Сведения | ||
+ | |||
+ | ===== Динамическое программирование ===== | ||
+ | - Задача о рюкзаке: | ||
+ | * Без повторений (одномерный случай) | ||
+ | * С повторениями (двумерный случай) | ||
</WRAP> | </WRAP> |