Категория:Учебный курс «Алгоритмы и структуры данных»: различия между версиями
Перейти к навигации
Перейти к поиску
Ctrlalt (обсуждение | вклад) Нет описания правки |
Ctrlalt (обсуждение | вклад) Нет описания правки |
||
| (не показано 106 промежуточных версий 2 участников) | |||
| Строка 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, находящихся в данной категории.