Категория:Учебный курс «Алгоритмы и структуры данных»: различия между версиями
Перейти к навигации
Перейти к поиску
Ctrlalt (обсуждение | вклад) Нет описания правки |
Ctrlalt (обсуждение | вклад) Нет описания правки |
||
| Строка 6: | Строка 6: | ||
:* [[Анализ рекуррентных соотношений. Мастер-теорема]] | :* [[Анализ рекуррентных соотношений. Мастер-теорема]] | ||
: Простейшие алгоритмы сортировки | : Простейшие алгоритмы сортировки | ||
:* [[Сортировка выбором]] | :* [[Сортировка выбором]] 📄 | ||
:* [[Сортировка вставками]] | :* [[Сортировка вставками]] 📄 | ||
: Улучшенные алгоритмы сортировки | : Улучшенные алгоритмы сортировки | ||
:* [[Сортировка слиянием]] | :* [[Сортировка слиянием]] 📄 | ||
:* [[Быстрая сортировка]] | :* [[Быстрая сортировка]] 📄 | ||
: Сортировка за линейное время | : Сортировка за линейное время | ||
:* [[Сортировка подсчётом]] | :* [[Сортировка подсчётом]] | ||
| Строка 32: | Строка 32: | ||
:* [[Система непересекающихся множеств]] | :* [[Система непересекающихся множеств]] | ||
: Балансирующиеся деревья | : Балансирующиеся деревья | ||
:* [[АВЛ-дерево]] | :* [[АВЛ-дерево]] 📄 | ||
:* [[Красно-чёрное дерево]] | :* [[Красно-чёрное дерево]] 📄 | ||
:* [[Декартово дерево]] | :* [[Декартово дерево]] | ||
:* [[Расширения декартова дерева]] | :* [[Расширения декартова дерева]] 📄 | ||
: Обработка запросов на отрезках | : Обработка запросов на отрезках | ||
:* [[Дерево Фенвика]] | :* [[Дерево Фенвика]] | ||
:* [[Дерево отрезков]] | :* [[Дерево отрезков]] 📄 | ||
:* [[Sparse table]] | :* [[Sparse table]] 📄 | ||
:* Sqrt-декомпозиция | :* Sqrt-декомпозиция | ||
:* [[Алгоритм Мо]] | :* [[Алгоритм Мо]] | ||
| Строка 47: | Строка 47: | ||
:* Основные определения. Представление графов | :* Основные определения. Представление графов | ||
: Поиск в глубину и его приложения | : Поиск в глубину и его приложения | ||
:* [[Поиск в глубину]]<sup>''O(V+E)''</sup> | :* [[Поиск в глубину]] 📄<sup>''O(V+E)''</sup> | ||
:* [[Компоненты связности]] | :* [[Компоненты связности]] 📄 | ||
:* [[Циклы в графе. Двудольность]] | :* [[Циклы в графе. Двудольность]] 📄 | ||
:* [[Топологическая сортировка]] | :* [[Топологическая сортировка]] 📄 | ||
:* [[Компоненты сильной связности. Алгоритм Косараю-Шарира]] | :* [[Компоненты сильной связности. Алгоритм Косараю-Шарира|Компоненты сильной связности]] 📄 | ||
:* [[Мосты. Компоненты рёберной двусвязности]] | :* [[Мосты. Компоненты рёберной двусвязности|Мосты]] 📄 | ||
:* [[Точки сочленения. Компоненты вершинной двусвязности]] | :* [[Точки сочленения. Компоненты вершинной двусвязности|Точки сочленения]] 📄 | ||
:* [[Эйлеров цикл. Эйлеров путь]] | :* [[Эйлеров цикл. Эйлеров путь]] 📄 | ||
: Кратчайшие пути из одной вершины | : Кратчайшие пути из одной вершины | ||
:* [[Поиск в ширину]]<sup>''O(V+E)''</sup> | :* [[Поиск в ширину]] 📄<sup>''O(V+E)''</sup> | ||
:* [[Алгоритм Дейкстры]]<sup>''O(V<sup>2</sup>+E) или O(ElogV)''</sup> | :* [[Алгоритм Дейкстры]] 📄<sup>''O(V<sup>2</sup>+E) или O(ElogV)''</sup> | ||
:* [[Алгоритм A*]] | :* [[Алгоритм A*]] 📄 | ||
:* [[Алгоритм Форда-Беллмана]]<sup>''O(VE)''</sup> | :* [[Алгоритм Форда-Беллмана]]<sup>''O(VE)''</sup> | ||
:* [[Кратчайшие пути в ациклических орграфах]]<sup>''O(V+E)''</sup> | :* [[Кратчайшие пути в ациклических орграфах]]<sup>''O(V+E)''</sup> | ||
: Кратчайшие пути между всеми парами вершин | : Кратчайшие пути между всеми парами вершин | ||
:* [[Алгоритм Флойда]]<sup>''O(V<sup>3</sup>)''</sup> | :* [[Алгоритм Флойда]] 📄<sup>''O(V<sup>3</sup>)''</sup> | ||
:* [[Алгоритм Джонсона]]<sup>''O(VElogV)''</sup> | :* [[Алгоритм Джонсона]]<sup>''O(VElogV)''</sup> | ||
: Минимальное остовное дерево | : Минимальное остовное дерево | ||
:* [[Алгоритм Краскала]]<sup>''O(ElogV)''</sup> | :* [[Алгоритм Краскала]] 📝<sup>''O(ElogV)''</sup> | ||
:* [[Алгоритм Прима]]<sup>''O(V<sup>2</sup>+E) или O(ElogV)''</sup> | :* [[Алгоритм Прима]] 📄<sup>''O(V<sup>2</sup>+E) или O(ElogV)''</sup> | ||
: Максимальный поток | : Максимальный поток | ||
:* [[Алгоритм Форда-Фалкерсона]]<sup>''O(Flow×E)''</sup> | :* [[Алгоритм Форда-Фалкерсона]] 📄<sup>''O(Flow×E)''</sup> | ||
:* [[Алгоритм Эдмондса-Карпа]]<sup>''O(VE<sup>2</sup>)''</sup> | :* [[Алгоритм Эдмондса-Карпа]] 📄<sup>''O(VE<sup>2</sup>)''</sup> | ||
:* [[Алгоритм Диница]]<sup>''O(V<sup>2</sup>E)''</sup> | :* [[Алгоритм Диница]] 📄<sup>''O(V<sup>2</sup>E)''</sup> | ||
:* [[Максимальный поток минимальной стоимости]] | :* [[Максимальный поток минимальной стоимости]] 📝 | ||
:* [[Применения максимального потока]] | :* [[Применения максимального потока]] | ||
: Максимальное паросочетание | : Максимальное паросочетание | ||
:* [[Алгоритм Куна]]<sup>''O(VE)''</sup> | :* [[Алгоритм Куна]] 📄<sup>''O(VE)''</sup> | ||
:* [[Минимальное вершинное покрытие, максимальное независимое множество]] | :* [[Минимальное вершинное покрытие, максимальное независимое множество]] 📄 | ||
: Наименьший общий предок | : Наименьший общий предок | ||
:* [[Метод двоичного подъёма]]<sup>''O(NlogN), O(logN)''</sup> | :* [[Метод двоичного подъёма]] 📄<sup>''O(NlogN), O(logN)''</sup> | ||
:* [[Сведение LCA к RMQ и RMQ к LCA]] | :* [[Сведение LCA к RMQ и RMQ к LCA]] | ||
:* [[Алгоритм Тарьяна (offline)]]<sup>''O(N), O(1)''</sup> | :* [[Алгоритм Тарьяна (offline)]]<sup>''O(N), O(1)''</sup> | ||
: Декомпозиции деревьев | : Декомпозиции деревьев | ||
:* [[Heavy-light-декомпозиция]] | :* [[Heavy-light-декомпозиция]] 📝 | ||
| | | | ||
;Полный перебор и методы его оптимизации | ;Полный перебор и методы его оптимизации | ||
| Строка 96: | Строка 96: | ||
: | : | ||
: Теория чисел | : Теория чисел | ||
:* [[НОД. Алгоритм Евклида]] | :* [[НОД. Алгоритм Евклида]] 📄 | ||
:* [[Простые числа. Решето Эратосфена]] | :* [[Простые числа. Решето Эратосфена]] 📄 | ||
:* [[Быстрое возведение в степень]] | :* [[Быстрое возведение в степень]] 📄 | ||
:* [[Модульная арифметика]] | :* [[Модульная арифметика]] 📄 | ||
:* [[Длинная арифметика]] | :* [[Длинная арифметика]] 📝 | ||
:* [[Метод Гаусса]] | :* [[Метод Гаусса]] 📄 | ||
:* [[Быстрое преобразование Фурье]] | :* [[Быстрое преобразование Фурье]] 📄 | ||
: Комбинаторика | : Комбинаторика | ||
:* [[Подсчёт и перечисление комбинаторных объектов]] | :* [[Подсчёт и перечисление комбинаторных объектов]] 📄 | ||
:* [[Получение номера по объекту и объекта по номеру]] | :* [[Получение номера по объекту и объекта по номеру]] | ||
:* [[Перестановки]] | :* [[Перестановки]] | ||
| Строка 110: | Строка 110: | ||
:* [[Игры]] | :* [[Игры]] | ||
: Геометрия | : Геометрия | ||
:* [[Геометрические примитивы]] | :* [[Геометрические примитивы]] 📄 | ||
:* [[Выпуклая оболочка]] | :* [[Выпуклая оболочка]] 📄 | ||
; Алгоритмы для работы со строками | ; Алгоритмы для работы со строками | ||
: | : | ||
:* [[Хеширование строк]] | :* [[Хеширование строк]] 📄 | ||
:* [[Префикс-функция]] | :* [[Префикс-функция]] 📄 | ||
:* [[Алгоритм Ахо-Корасик]] | :* [[Алгоритм Ахо-Корасик]] 📄 | ||
:* [[Z-функция]] | :* [[Z-функция]] 📄 | ||
:* [[Алгоритм Манакера]] | :* [[Алгоритм Манакера]] 📄 | ||
:* [[Суффиксный массив]] | :* [[Суффиксный массив]] 📄 | ||
: Разбор выражений | : Разбор выражений | ||
:* [[Наивный рекурсивный разбор]] | :* [[Наивный рекурсивный разбор]] 📄 | ||
:* [[Алгоритм сортировочной станции]] | :* [[Алгоритм сортировочной станции]] 📄 | ||
|} | |} | ||
''© В. А. Фолунин, 2012–2023'' | ''© В. А. Фолунин, 2012–2023'' | ||
Версия от 15:29, 18 февраля 2023
|
|
|
© В. А. Фолунин, 2012–2023
Подкатегории
В этой категории отображается 12 подкатегорий из имеющихся 12.
Страницы в категории «Учебный курс «Алгоритмы и структуры данных»»
Показаны 4 страницы из 4, находящихся в данной категории.