Категория:Учебный курс «Алгоритмы и структуры данных»: различия между версиями
Перейти к навигации
Перейти к поиску
Ctrlalt (обсуждение | вклад) Нет описания правки |
Ctrlalt (обсуждение | вклад) Нет описания правки |
||
| (не показано 7 промежуточных версий этого же участника) | |||
| Строка 6: | Строка 6: | ||
:* [[Анализ рекуррентных соотношений. Мастер-теорема]] | :* [[Анализ рекуррентных соотношений. Мастер-теорема]] | ||
: Простейшие алгоритмы сортировки | : Простейшие алгоритмы сортировки | ||
:* [[Сортировка выбором]] | :* 📄 [[Сортировка выбором]] | ||
:* [[Сортировка вставками]] | :* 📄 [[Сортировка вставками]] | ||
: Улучшенные алгоритмы сортировки | : Улучшенные алгоритмы сортировки | ||
:* [[Сортировка слиянием]] | :* 📄 [[Сортировка слиянием]] | ||
:* [[Быстрая сортировка]] | :* 📄 [[Быстрая сортировка]] | ||
: Сортировка за линейное время | : Сортировка за линейное время | ||
:* [[Сортировка подсчётом]] | :* [[Сортировка подсчётом]] | ||
| Строка 22: | Строка 22: | ||
: | : | ||
: Базовые структуры и абстрактные типы данных | : Базовые структуры и абстрактные типы данных | ||
:* | :* [[Динамический массив]] | ||
:* | :* [[Связный список]] | ||
:* [[Стек]] | :* [[Стек]] | ||
:* [[Очередь]] | :* [[Очередь]] | ||
| Строка 32: | Строка 32: | ||
:* [[Система непересекающихся множеств]] | :* [[Система непересекающихся множеств]] | ||
: Балансирующиеся деревья | : Балансирующиеся деревья | ||
:* [[АВЛ-дерево]] | :* 📄 [[АВЛ-дерево]] | ||
:* [[Красно-чёрное дерево]] | :* 📄 [[Красно-чёрное дерево]] | ||
:* [[Декартово дерево]] | :* [[Декартово дерево]] | ||
:* [[Расширения декартова дерева]] | :* 📄 [[Расширения декартова дерева]] | ||
: Обработка запросов на отрезках | : Обработка запросов на отрезках | ||
:* 📄 [[Префиксные суммы]] | |||
:* [[Дерево Фенвика]] | :* [[Дерево Фенвика]] | ||
:* [[Дерево отрезков]] | :* 📄 [[Дерево отрезков]] | ||
:* [[Sparse table]] | :* 📄 [[Sparse table]] | ||
:* Sqrt-декомпозиция | :* Sqrt-декомпозиция | ||
:* [[Алгоритм Мо]] | :* [[Алгоритм Мо]] | ||
| Строка 45: | Строка 46: | ||
;Алгоритмы для работы с графами | ;Алгоритмы для работы с графами | ||
: | : | ||
:* Основные определения. Представление графов | :* [[Основные определения. Представление графов]] | ||
: Поиск в глубину и его приложения | : Поиск в глубину и его приложения | ||
:* [[Поиск в глубину]] | :* 📄 [[Поиск в глубину]]<sup>''O(V+E)''</sup> | ||
:* [[Компоненты связности]] | :* 📄 [[Компоненты связности]] | ||
:* [[Циклы в графе. Двудольность]] | :* 📄 [[Циклы в графе. Двудольность]] | ||
:* [[Топологическая сортировка]] | :* 📄 [[Топологическая сортировка]] | ||
:* [[Компоненты сильной связности. Алгоритм Косараю-Шарира|Компоненты сильной связности]] | :* 📄 [[Компоненты сильной связности. Алгоритм Косараю-Шарира|Компоненты сильной связности]] | ||
:* [[Мосты. Компоненты рёберной двусвязности|Мосты]] | :* 📄 [[Мосты. Компоненты рёберной двусвязности|Мосты]] | ||
:* [[Точки сочленения. Компоненты вершинной двусвязности|Точки сочленения]] | :* 📄 [[Точки сочленения. Компоненты вершинной двусвязности|Точки сочленения]] | ||
:* [[Эйлеров цикл. Эйлеров путь]] | :* 📄 [[Эйлеров цикл. Эйлеров путь]] | ||
: Кратчайшие пути из одной вершины | : Кратчайшие пути из одной вершины | ||
:* [[Поиск в ширину]] | :* 📄 [[Поиск в ширину]]<sup>''O(V+E)''</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(VElogV)''</sup> | :* [[Алгоритм Джонсона]]<sup>''O(VElogV)''</sup> | ||
: Минимальное остовное дерево | : Минимальное остовное дерево | ||
:* [[Алгоритм Краскала]] | :* 📝 [[Алгоритм Краскала]]<sup>''O(ElogV)''</sup> | ||
:* [[Алгоритм Прима]] | :* 📄 [[Алгоритм Прима]]<sup>''O(V<sup>2</sup>+E) или O(ElogV)''</sup> | ||
: Максимальный поток | : Максимальный поток | ||
:* [[Алгоритм Форда-Фалкерсона]] | :* 📄 [[Алгоритм Форда-Фалкерсона]]<sup>''O(Flow×E)''</sup> | ||
:* [[Алгоритм Эдмондса-Карпа]] | :* 📄 [[Алгоритм Эдмондса-Карпа]]<sup>''O(VE<sup>2</sup>)''</sup> | ||
:* [[Алгоритм Диница]] | :* 📄 [[Алгоритм Диница]]<sup>''O(V<sup>2</sup>E)''</sup> | ||
:* [[Максимальный поток минимальной стоимости]] | :* 📝 [[Максимальный поток минимальной стоимости]] | ||
:* [[Применения максимального потока]] | :* [[Применения максимального потока]] | ||
: Максимальное паросочетание | : Максимальное паросочетание | ||
:* [[Алгоритм Куна]] | :* 📄 [[Алгоритм Куна]]<sup>''O(VE)''</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-декомпозиция]] | ||
| | | | ||
;Полный перебор и методы его оптимизации | ;Полный перебор и методы его оптимизации | ||
: | : | ||
:* Полный перебор | :* [[Полный перебор]] | ||
:* [[Два указателя]] | :* [[Два указателя]] | ||
:* Meet in the middle | :* Meet in the middle | ||
| Строка 96: | Строка 97: | ||
: | : | ||
: Теория чисел | : Теория чисел | ||
:* [[НОД. Алгоритм Евклида]] | :* 📄 [[НОД. Алгоритм Евклида]] | ||
:* [[Простые числа. Решето Эратосфена]] | :* 📄 [[Простые числа. Решето Эратосфена]] | ||
:* [[Быстрое возведение в степень]] | :* 📄 [[Быстрое возведение в степень]] | ||
:* [[Модульная арифметика]] | :* 📄 [[Модульная арифметика]] | ||
:* [[Длинная арифметика]] | :* 📝 [[Длинная арифметика]] | ||
:* [[Метод Гаусса]] | :* 📄 [[Метод Гаусса]] | ||
:* [[Быстрое преобразование Фурье]] | :* 📄 [[Быстрое преобразование Фурье]] | ||
: Комбинаторика | : Комбинаторика | ||
:* [[Подсчёт и перечисление комбинаторных объектов]] | :* 📄 [[Подсчёт и перечисление комбинаторных объектов]] | ||
:* [[Получение номера по объекту и объекта по номеру]] | :* [[Получение номера по объекту и объекта по номеру]] | ||
:* [[Перестановки]] | :* [[Перестановки]] | ||
| Строка 110: | Строка 111: | ||
:* [[Игры]] | :* [[Игры]] | ||
: Геометрия | : Геометрия | ||
:* [[Геометрические примитивы]] | :* 📝 [[Геометрические примитивы]] | ||
:* [[Выпуклая оболочка]] | :* 📄 [[Выпуклая оболочка]] | ||
; Алгоритмы для работы со строками | ; Алгоритмы для работы со строками | ||
: | : | ||
:* [[Хеширование строк]] | :* 📄 [[Хеширование строк]] | ||
:* [[Префикс-функция]] | :* 📄 [[Префикс-функция]] | ||
:* [[Алгоритм Ахо-Корасик]] | :* 📄 [[Алгоритм Ахо-Корасик]] | ||
:* [[Z-функция]] | :* 📄 [[Z-функция]] | ||
:* [[Алгоритм Манакера]] | :* 📄 [[Алгоритм Манакера]] | ||
:* [[Суффиксный массив]] | :* 📄 [[Суффиксный массив]] | ||
: Разбор выражений | : Разбор выражений | ||
:* [[Наивный рекурсивный разбор]] | :* 📝 [[Наивный рекурсивный разбор]] | ||
:* [[Алгоритм сортировочной станции]] 📄 | :* 📄 [[Алгоритм сортировочной станции]] | ||
; Разное | |||
: | |||
:* 📄 [[Часто используемые фрагменты]] | |||
|} | |} | ||
''© В. А. Фолунин, | ''© В. А. Фолунин, 2012–2024'' | ||
Текущая версия от 22:21, 16 февраля 2024
|
|
|
© В. А. Фолунин, 2012–2024
Подкатегории
В этой категории отображается 12 подкатегорий из имеющихся 12.
Страницы в категории «Учебный курс «Алгоритмы и структуры данных»»
Показаны 4 страницы из 4, находящихся в данной категории.