Категория:Учебный курс «Алгоритмы и структуры данных»: различия между версиями
Перейти к навигации
Перейти к поиску
Ctrlalt (обсуждение | вклад) Нет описания правки |
Ctrlalt (обсуждение | вклад) Нет описания правки |
||
(не показано 27 промежуточных версий этого же участника) | |||
Строка 1: | Строка 1: | ||
{| | {| | ||
| | | | ||
; | ;Сортировка и поиск | ||
: | : | ||
:* Критерии эффективности алгоритма. Асимптотический анализ | :* Критерии эффективности алгоритма. Асимптотический анализ | ||
:* [[Асимптотический анализ рекуррентных соотношений]] | |||
: Простейшие алгоритмы сортировки | : Простейшие алгоритмы сортировки | ||
:* Сортировка выбором | :* Сортировка выбором | ||
Строка 11: | Строка 12: | ||
:* [[Быстрая сортировка]] | :* [[Быстрая сортировка]] | ||
: Сортировка за линейное время | : Сортировка за линейное время | ||
:* Сортировка подсчётом | :* [[Сортировка подсчётом]] | ||
:* Поразрядная сортировка | :* Поразрядная сортировка | ||
: Алгоритмы поиска | : Алгоритмы поиска | ||
:* [[Бинарный поиск]] | :* [[Бинарный поиск]] | ||
:* [[Тернарный поиск]] | :* [[Тернарный поиск]] | ||
: Применение сортировки | |||
:* [[Сканирующая прямая]] | |||
;Структуры данных | |||
: | |||
:* [[ | |||
; | |||
: | : | ||
:* Введение в ООП. Классы | :* Введение в ООП. Классы | ||
Строка 38: | Строка 35: | ||
:* [[Система непересекающихся множеств]] | :* [[Система непересекающихся множеств]] | ||
: Балансирующиеся деревья | : Балансирующиеся деревья | ||
:* Обзор балансирующихся деревьев: | :* Обзор балансирующихся деревьев | ||
:* [[АВЛ-дерево]] | |||
:* [[Декартово дерево]] | :* [[Декартово дерево]] | ||
:* [[Расширения декартова дерева]] | :* [[Расширения декартова дерева]] | ||
: | : Обработка запросов на отрезках | ||
:* [[Дерево Фенвика]] | :* [[Дерево Фенвика]] | ||
:* [[Дерево отрезков]] | :* [[Дерево отрезков]] | ||
:* [[Sparse table]] | :* [[Sparse table]] | ||
:* Sqrt-декомпозиция | |||
:* [[Алгоритм Мо]] | |||
| | | | ||
; | ;Алгоритмы для работы с графами | ||
: | : | ||
:* Основные определения. Представление графов | :* Основные определения. Представление графов | ||
Строка 58: | Строка 57: | ||
:* [[Топологическая сортировка]] | :* [[Топологическая сортировка]] | ||
:* [[Компоненты сильной связности. Алгоритм Косараю-Шарира]] | :* [[Компоненты сильной связности. Алгоритм Косараю-Шарира]] | ||
:* [[Эйлеров цикл. Эйлеров путь]] | |||
: Кратчайшие пути из одной вершины | : Кратчайшие пути из одной вершины | ||
:* [[Поиск в ширину]]<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> | ||
:* [[Алгоритм Форда-Беллмана]]<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> | ||
Строка 69: | Строка 69: | ||
:* [[Алгоритм Краскала]]<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(VE<sup>2</sup>)''</sup> | |||
:* [[Алгоритм Диница]]<sup>''O(V<sup>2</sup>E)''</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 | |||
:* [[Жадные алгоритмы]] | |||
:* [[Динамическое программирование]] | :* [[Динамическое программирование]] | ||
;Математика | |||
: | |||
: Теория чисел | |||
:* [[НОД. Алгоритм Евклида]] | |||
:* [[Простые числа. Решето Эратосфена]] | |||
:* [[Быстрое возведение в степень]] | |||
:* [[Длинная арифметика]] | |||
:* [[Метод Гаусса]] | |||
: Комбинаторика | : Комбинаторика | ||
:* [[Подсчёт и перечисление комбинаторных объектов]] | :* [[Подсчёт и перечисление комбинаторных объектов]] | ||
:* [[Получение номера по объекту и объекта по номеру]] | :* [[Получение номера по объекту и объекта по номеру]] | ||
:* [[Перестановки]] | :* [[Перестановки]] | ||
: Теория игр | |||
:* [[Игры]] | |||
: Геометрия | : Геометрия | ||
:* [[Геометрические примитивы]] | |||
:* [[Выпуклая оболочка]] | :* [[Выпуклая оболочка]] | ||
; Алгоритмы для работы со строками | |||
: | |||
:* [[Хеширование строк]] | |||
:* [[Префикс-функция]] | |||
:* [[Алгоритм Манакера]] | |||
: Разбор выражений | |||
:* [[Наивный рекурсивный разбор]] | |||
|} | |} | ||
''© В. А. Фолунин | ''© В. А. Фолунин, 2012–2019'' |
Версия от 18:04, 30 августа 2019
|
|
|
© В. А. Фолунин, 2012–2019
Подкатегории
В этой категории отображается 12 подкатегорий из имеющихся 12.
Страницы в категории «Учебный курс «Алгоритмы и структуры данных»»
Показаны 4 страницы из 4, находящихся в данной категории.