Категория:Учебный курс «Алгоритмы и структуры данных»: различия между версиями

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
 
(не показано 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+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>
:* [[Алгоритм 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(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(ElogV)''</sup>
:* 📄 [[Алгоритм Прима]]<sup>''O(V<sup>2</sup>+E) или O(ElogV)''</sup>
: Максимальный поток
: Максимальный поток
:* [[Алгоритм Форда-Фалкерсона]] 📄<sup>''O(Flow&times;E)''</sup>
:* 📄 [[Алгоритм Форда-Фалкерсона]]<sup>''O(Flow&times;E)''</sup>
:* [[Алгоритм Эдмондса-Карпа]] 📄<sup>''O(VE<sup>2</sup>)''</sup>
:* 📄 [[Алгоритм Эдмондса-Карпа]]<sup>''O(VE<sup>2</sup>)''</sup>
:* [[Алгоритм Диница]] 📄<sup>''O(V<sup>2</sup>E)''</sup>
:* 📄 [[Алгоритм Диница]]<sup>''O(V<sup>2</sup>E)''</sup>
:* [[Максимальный поток минимальной стоимости]] 📝
:* 📝 [[Максимальный поток минимальной стоимости]]
:* [[Применения максимального потока]]
:* [[Применения максимального потока]]
: Максимальное паросочетание
: Максимальное паросочетание
:* [[Алгоритм Куна]] 📄<sup>''O(VE)''</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-декомпозиция]] 📝
:* 📝 [[Heavy-light-декомпозиция]]
|
|
;Полный перебор и методы его оптимизации
;Полный перебор и методы его оптимизации
:
:
:* Полный перебор
:* [[Полный перебор]]
:* [[Два указателя]]
:* [[Два указателя]]
:* Meet in the middle
:* Meet in the middle
Строка 96: Строка 97:
:
:
: Теория чисел
: Теория чисел
:* [[НОД. Алгоритм Евклида]] 📄
:* 📄 [[НОД. Алгоритм Евклида]]
:* [[Простые числа. Решето Эратосфена]] 📄
:* 📄 [[Простые числа. Решето Эратосфена]]
:* [[Быстрое возведение в степень]] 📄
:* 📄 [[Быстрое возведение в степень]]
:* [[Модульная арифметика]] 📄
:* 📄 [[Модульная арифметика]]
:* [[Длинная арифметика]] 📝
:* 📝 [[Длинная арифметика]]
:* [[Метод Гаусса]] 📄
:* 📄 [[Метод Гаусса]]
:* [[Быстрое преобразование Фурье]] 📄
:* 📄 [[Быстрое преобразование Фурье]]
: Комбинаторика
: Комбинаторика
:* [[Подсчёт и перечисление комбинаторных объектов]] 📄
:* 📄 [[Подсчёт и перечисление комбинаторных объектов]]
:* [[Получение номера по объекту и объекта по номеру]]
:* [[Получение номера по объекту и объекта по номеру]]
:* [[Перестановки]]
:* [[Перестановки]]
Строка 110: Строка 111:
:* [[Игры]]
:* [[Игры]]
: Геометрия
: Геометрия
:* [[Геометрические примитивы]] 📄
:* 📝 [[Геометрические примитивы]]
:* [[Выпуклая оболочка]] 📄
:* 📄 [[Выпуклая оболочка]]


; Алгоритмы для работы со строками
; Алгоритмы для работы со строками
:
:
:* [[Хеширование строк]] 📄
:* 📄 [[Хеширование строк]]
:* [[Префикс-функция]] 📄
:* 📄 [[Префикс-функция]]
:* [[Алгоритм Ахо-Корасик]] 📄
:* 📄 [[Алгоритм Ахо-Корасик]]
:* [[Z-функция]] 📄
:* 📄 [[Z-функция]]
:* [[Алгоритм Манакера]] 📄
:* 📄 [[Алгоритм Манакера]]
:* [[Суффиксный массив]] 📄
:* 📄 [[Суффиксный массив]]
: Разбор выражений
: Разбор выражений
:* [[Наивный рекурсивный разбор]] 📄
:* 📝 [[Наивный рекурсивный разбор]]
:* [[Алгоритм сортировочной станции]] 📄
:* 📄 [[Алгоритм сортировочной станции]]
 
; Разное
:
:* 📄 [[Часто используемые фрагменты]]
|}
|}


''&copy; В. А. Фолунин, 2012–2023''
''&copy; В. А. Фолунин, 2012–2024''

Текущая версия от 22:21, 16 февраля 2024

Сортировка и поиск
Простейшие алгоритмы сортировки
Улучшенные алгоритмы сортировки
Сортировка за линейное время
Алгоритмы поиска
Применение сортировки
Структуры данных
Базовые структуры и абстрактные типы данных
Балансирующиеся деревья
Обработка запросов на отрезках
Алгоритмы для работы с графами
Поиск в глубину и его приложения
Кратчайшие пути из одной вершины
Кратчайшие пути между всеми парами вершин
Минимальное остовное дерево
Максимальный поток
Максимальное паросочетание
Наименьший общий предок
Декомпозиции деревьев
Полный перебор и методы его оптимизации
Динамическое программирование
Математика
Теория чисел
Комбинаторика
Теория игр
Геометрия
Алгоритмы для работы со строками
Разбор выражений
Разное

© В. А. Фолунин, 2012–2024

Страницы в категории «Учебный курс «Алгоритмы и структуры данных»»

Показаны 4 страницы из 4, находящихся в данной категории.