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