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 Next revision Both sides next revision | ||
|
courses:algorithms_building_and_analysis:lectures [2023/05/31 21:38] kalishenko |
courses:algorithms_building_and_analysis:lectures [2024/04/09 19:02] kalishenko |
||
|---|---|---|---|
| Line 1: | Line 1: | ||
| ====== Программа ====== | ====== Программа ====== | ||
| + | ===== Сложность алгоритмов ===== | ||
| + | - Виды сложности: | ||
| + | * Операции | ||
| + | * Время | ||
| + | * Память | ||
| + | - Понятие вычислительной сложности в зависимости от размера входа | ||
| + | - Константная сложность на примере vector и unordered_set: | ||
| + | * Амортизированная | ||
| + | * В среднем | ||
| + | * В худшем | ||
| + | |||
| ===== Поиск с возвращением ===== | ===== Поиск с возвращением ===== | ||
| - Идея поиска с возвращением (backtracking) | - Идея поиска с возвращением (backtracking) | ||
| Line 8: | Line 19: | ||
| * Пример на площади фигуры | * Пример на площади фигуры | ||
| * Ограничения и условия применимости | * Ограничения и условия применимости | ||
| + | |||
| + | ===== Жадные алгоритмы ===== | ||
| + | - ... | ||
| ===== Графы ===== | ===== Графы ===== | ||
| Line 28: | Line 42: | ||
| - Алгоритм REACH | - Алгоритм REACH | ||
| - Алгоритм Arc flags | - Алгоритм Arc flags | ||
| - | |||
| - | ==== Топологическая сортировка ==== | ||
| - | - Ограничения на циклы | ||
| - | - Алгоритм нумерацией шагов обхода | ||
| - | - Алгоритм исключения вершины с минимальным количеством входящих рёбер | ||
| ==== Задача о коммивояжёре ==== | ==== Задача о коммивояжёре ==== | ||
| Line 72: | Line 81: | ||
| - Наивное построение префикс-функции и его сложность | - Наивное построение префикс-функции и его сложность | ||
| - Построение префикс-функции за линейное время | - Построение префикс-функции за линейное время | ||
| + | - Оптимизация сложности по памяти | ||
| ==== Алгоритм Ахо-Корасик ==== | ==== Алгоритм Ахо-Корасик ==== | ||
| Line 84: | Line 94: | ||
| * Сведение к графу | * Сведение к графу | ||
| * Выделение подзадачи | * Выделение подзадачи | ||
| - | - Задача о рюкзаке: | ||
| - | * Без повторений (одномерный случай) | ||
| - | * С повторениями (двумерный случай) | ||
| - Задача о порядке перемножения матриц | - Задача о порядке перемножения матриц | ||
| - | |||
| - | ===== Сложность алгоритмов ===== | ||
| - | - Виды сложности | ||
| - | - Понятие вычислительной сложности в зависимости от размера входа | ||
| - | - Константная сложность на примере vector и unordered_set: | ||
| - | * Амортизированная | ||
| - | * В среднем | ||
| ----- | ----- | ||
| Line 131: | Line 131: | ||
| - Применения и сложность задачи построения клик графа | - Применения и сложность задачи построения клик графа | ||
| - Алгоритм нахождения клик на основе поиска с возвращением. | - Алгоритм нахождения клик на основе поиска с возвращением. | ||
| + | |||
| + | ==== Топологическая сортировка ==== | ||
| + | - Ограничения на циклы | ||
| + | - Алгоритм нумерацией шагов обхода | ||
| + | - Алгоритм исключения вершины с минимальным количеством входящих рёбер | ||
| ==== Алгоритм Рабина-Карпа ==== | ==== Алгоритм Рабина-Карпа ==== | ||
| Line 142: | Line 147: | ||
| - Метод расщепления | - Метод расщепления | ||
| - Сведения | - Сведения | ||
| + | |||
| + | ===== Динамическое программирование ===== | ||
| + | - Задача о рюкзаке: | ||
| + | * Без повторений (одномерный случай) | ||
| + | * С повторениями (двумерный случай) | ||
| </WRAP> | </WRAP> | ||
courses/algorithms_building_and_analysis/lectures.txt · Last modified: 2024/05/29 17:33 by kalishenko
Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Share Alike 4.0 International
