Категория:Учебный курс «Алгоритмы и структуры данных»: различия между версиями
Перейти к навигации
Перейти к поиску
Ctrlalt (обсуждение | вклад) Нет описания правки |
Ctrlalt (обсуждение | вклад) Нет описания правки |
||
| (не показано 49 промежуточных версий этого же участника) | |||
| Строка 1: | Строка 1: | ||
{| | {| | ||
| | | | ||
; | ;Сортировка и поиск | ||
: | : | ||
:* | :* [[Асимптотический анализ алгоритмов]] | ||
:* [[ | :* [[Анализ рекуррентных соотношений. Мастер-теорема]] | ||
: Простейшие алгоритмы сортировки | : Простейшие алгоритмы сортировки | ||
:* Сортировка выбором | :* 📄 [[Сортировка выбором]] | ||
:* Сортировка вставками | :* 📄 [[Сортировка вставками]] | ||
: Улучшенные алгоритмы сортировки | : Улучшенные алгоритмы сортировки | ||
:* [[Сортировка слиянием]] | :* 📄 [[Сортировка слиянием]] | ||
:* [[Быстрая сортировка]] | :* 📄 [[Быстрая сортировка]] | ||
: Сортировка за линейное время | : Сортировка за линейное время | ||
:* [[Сортировка подсчётом]] | :* [[Сортировка подсчётом]] | ||
:* Поразрядная сортировка | :* [[Поразрядная сортировка]] | ||
: Алгоритмы поиска | : Алгоритмы поиска | ||
:* [[Бинарный поиск]] | :* [[Бинарный поиск]] | ||
:* [[Тернарный поиск]] | :* [[Тернарный поиск]] | ||
; | : Применение сортировки | ||
:* [[Сканирующая прямая]] | |||
;Структуры данных | |||
: | : | ||
: Базовые структуры и абстрактные типы данных | : Базовые структуры и абстрактные типы данных | ||
:* | :* [[Динамический массив]] | ||
:* | :* [[Связный список]] | ||
:* [[Стек]] | :* [[Стек]] | ||
:* [[Очередь]] | :* [[Очередь]] | ||
| Строка 40: | Строка 32: | ||
:* [[Система непересекающихся множеств]] | :* [[Система непересекающихся множеств]] | ||
: Балансирующиеся деревья | : Балансирующиеся деревья | ||
:* | :* 📄 [[АВЛ-дерево]] | ||
:* 📄 [[Красно-чёрное дерево]] | |||
:* [[Декартово дерево]] | :* [[Декартово дерево]] | ||
:* [[Расширения декартова дерева]] | :* 📄 [[Расширения декартова дерева]] | ||
: | : Обработка запросов на отрезках | ||
:* 📄 [[Префиксные суммы]] | |||
:* [[Дерево Фенвика]] | |||
:* 📄 [[Дерево отрезков]] | |||
:* 📄 [[Sparse table]] | |||
:* Sqrt-декомпозиция | :* Sqrt-декомпозиция | ||
:* [[ | :* [[Алгоритм Мо]] | ||
|width=450px| | |||
;Алгоритмы для работы с графами | |||
| | |||
; | |||
: | : | ||
:* Основные определения. Представление графов | :* [[Основные определения. Представление графов]] | ||
: Поиск в глубину и его приложения | : Поиск в глубину и его приложения | ||
:* [[Поиск в глубину]]<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*]] | |||
:* [[Алгоритм Форда-Беллмана]]<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-декомпозиция]] | |||
| | |||
;Полный перебор и методы его оптимизации | |||
: | : | ||
:* [[Полный перебор]] | |||
:* [[Два указателя]] | |||
:* Meet in the middle | |||
:* [[Жадные алгоритмы]] | |||
: Динамическое программирование | |||
:* [[Динамическое программирование]] | :* [[Динамическое программирование]] | ||
:* [[ | :* [[Задача о рюкзаке и связанные задачи]] | ||
:* [[Оптимизации динамического программирования]] | |||
;Математика | |||
: | |||
: Теория чисел | |||
:* 📄 [[НОД. Алгоритм Евклида]] | |||
:* 📄 [[Простые числа. Решето Эратосфена]] | |||
:* 📄 [[Быстрое возведение в степень]] | |||
:* 📄 [[Модульная арифметика]] | |||
:* 📝 [[Длинная арифметика]] | |||
:* 📄 [[Метод Гаусса]] | |||
:* 📄 [[Быстрое преобразование Фурье]] | |||
: Комбинаторика | : Комбинаторика | ||
:* [[Подсчёт и перечисление комбинаторных объектов]] | :* 📄 [[Подсчёт и перечисление комбинаторных объектов]] | ||
:* [[Получение номера по объекту и объекта по номеру]] | :* [[Получение номера по объекту и объекта по номеру]] | ||
:* [[Перестановки]] | :* [[Перестановки]] | ||
: Теория игр | |||
:* [[Игры]] | |||
: Геометрия | : Геометрия | ||
:* [[Выпуклая оболочка]] | :* 📝 [[Геометрические примитивы]] | ||
: | :* 📄 [[Выпуклая оболочка]] | ||
:* [[Хеширование строк]] | |||
:* [[Префикс-функция]] | ; Алгоритмы для работы со строками | ||
:* [[Алгоритм Манакера]] | : | ||
:* 📄 [[Хеширование строк]] | |||
:* 📄 [[Префикс-функция]] | |||
:* 📄 [[Алгоритм Ахо-Корасик]] | |||
:* 📄 [[Z-функция]] | |||
:* 📄 [[Алгоритм Манакера]] | |||
:* 📄 [[Суффиксный массив]] | |||
: Разбор выражений | : Разбор выражений | ||
:* [[ | :* 📝 [[Наивный рекурсивный разбор]] | ||
:* 📄 [[Алгоритм сортировочной станции]] | |||
; Разное | |||
: | |||
:* 📄 [[Часто используемые фрагменты]] | |||
|} | |} | ||
''© В. А. Фолунин, | ''© В. А. Фолунин, 2012–2024'' | ||
Текущая версия от 22:21, 16 февраля 2024
|
|
|
© В. А. Фолунин, 2012–2024
Подкатегории
В этой категории отображается 12 подкатегорий из имеющихся 12.
Страницы в категории «Учебный курс «Алгоритмы и структуры данных»»
Показаны 4 страницы из 4, находящихся в данной категории.