Категория:Учебный курс «Алгоритмы и структуры данных»: различия между версиями
Перейти к навигации
Перейти к поиску
Ctrlalt (обсуждение | вклад) Нет описания правки |
Ctrlalt (обсуждение | вклад) Нет описания правки |
||
| (не показано 98 промежуточных версий этого же участника) | |||
| Строка 1: | Строка 1: | ||
{| | {| | ||
| | | | ||
* | ;Сортировка и поиск | ||
** | : | ||
*** | :* [[Асимптотический анализ алгоритмов]] | ||
*** | :* [[Анализ рекуррентных соотношений. Мастер-теорема]] | ||
** Базовые структуры данных и | : Простейшие алгоритмы сортировки | ||
*** | :* 📄 [[Сортировка выбором]] | ||
*** | :* 📄 [[Сортировка вставками]] | ||
*** | : Улучшенные алгоритмы сортировки | ||
*** [[ | :* 📄 [[Сортировка слиянием]] | ||
*** [[ | :* 📄 [[Быстрая сортировка]] | ||
*** [[ | : Сортировка за линейное время | ||
*** [[ | :* [[Сортировка подсчётом]] | ||
*** [[ | :* [[Поразрядная сортировка]] | ||
*** [[ | : Алгоритмы поиска | ||
* | :* [[Бинарный поиск]] | ||
* | :* [[Тернарный поиск]] | ||
** | : Применение сортировки | ||
*** [[ | :* [[Сканирующая прямая]] | ||
*** | ;Структуры данных | ||
: | |||
: Базовые структуры и абстрактные типы данных | |||
:* [[Динамический массив]] | |||
:* [[Связный список]] | |||
:* [[Стек]] | |||
:* [[Очередь]] | |||
:* [[Очередь с приоритетами]] | |||
:* [[Множество. Реализация на битовых векторах]] | |||
:* [[Множество и словарь. Реализация на деревьях поиска]] | |||
:* [[Множество и словарь. Реализация на хеш-таблицах]] | |||
:* [[Система непересекающихся множеств]] | |||
: Балансирующиеся деревья | |||
:* 📄 [[АВЛ-дерево]] | |||
:* 📄 [[Красно-чёрное дерево]] | |||
:* [[Декартово дерево]] | |||
:* 📄 [[Расширения декартова дерева]] | |||
: Обработка запросов на отрезках | |||
:* 📄 [[Префиксные суммы]] | |||
:* [[Дерево Фенвика]] | |||
:* 📄 [[Дерево отрезков]] | |||
:* 📄 [[Sparse table]] | |||
:* Sqrt-декомпозиция | |||
:* [[Алгоритм Мо]] | |||
|width=450px| | |||
;Алгоритмы для работы с графами | |||
: | |||
:* [[Основные определения. Представление графов]] | |||
: Поиск в глубину и его приложения | |||
:* 📄 [[Поиск в глубину]]<sup>''O(V+E)''</sup> | |||
:* 📄 [[Компоненты связности]] | |||
:* 📄 [[Циклы в графе. Двудольность]] | |||
:* 📄 [[Топологическая сортировка]] | |||
:* 📄 [[Компоненты сильной связности. Алгоритм Косараю-Шарира|Компоненты сильной связности]] | |||
:* 📄 [[Мосты. Компоненты рёберной двусвязности|Мосты]] | |||
:* 📄 [[Точки сочленения. Компоненты вершинной двусвязности|Точки сочленения]] | |||
:* 📄 [[Эйлеров цикл. Эйлеров путь]] | |||
: Кратчайшие пути из одной вершины | |||
:* 📄 [[Поиск в ширину]]<sup>''O(V+E)''</sup> | |||
:* 📝 [[Алгоритм Дейкстры]]<sup>''O(V<sup>2</sup>+E) или O(ElogV)''</sup> | |||
:* 📄 [[Алгоритм A*]] | |||
:* [[Алгоритм Форда-Беллмана]]<sup>''O(VE)''</sup> | |||
:* [[Кратчайшие пути в ациклических орграфах]]<sup>''O(V+E)''</sup> | |||
: Кратчайшие пути между всеми парами вершин | |||
:* 📄 [[Алгоритм Флойда]]<sup>''O(V<sup>3</sup>)''</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]] | |||
:* [[Алгоритм Тарьяна (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, находящихся в данной категории.