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

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

Сортировка и поиск

Простейшие алгоритмы сортировки

Улучшенные алгоритмы сортировки

Сортировка за линейное время

Алгоритмы поиска

Применение сортировки

Сканирующая прямая

Структуры данных

Базовые структуры и абстрактные типы данных

Балансирующиеся деревья

Обработка запросов на отрезках

Алгоритмы для работы с графами

Основные определения. Представление графов

Поиск в глубину и его приложения

Кратчайшие пути из одной вершины

📄 Поиск в ширину^O(V+E)
📝 Алгоритм Дейкстры^{O(V²+E) или O(ElogV)}
📄 Алгоритм A*
Алгоритм Форда-Беллмана^O(VE)
Кратчайшие пути в ациклических орграфах^O(V+E)

Кратчайшие пути между всеми парами вершин

📄 Алгоритм Флойда^O(V³)
Алгоритм Джонсона^O(VElogV)

Минимальное остовное дерево

📝 Алгоритм Краскала^O(ElogV)
📄 Алгоритм Прима^{O(V²+E) или O(ElogV)}

Максимальный поток

📄 Алгоритм Форда-Фалкерсона^O(Flow×E)
📄 Алгоритм Эдмондса-Карпа^O(VE²)
📄 Алгоритм Диница^O(V²E)
📝 Максимальный поток минимальной стоимости
Применения максимального потока

Максимальное паросочетание

Наименьший общий предок

📄 Метод двоичного подъёма^{O(NlogN), O(logN)}
Сведение LCA к RMQ и RMQ к LCA
Алгоритм Тарьяна (offline)^{O(N), O(1)}

Декомпозиции деревьев

📝 Heavy-light-декомпозиция

Полный перебор и методы его оптимизации

Динамическое программирование

Математика

Теория чисел

Комбинаторика

Теория игр

Игры

Геометрия

Алгоритмы для работы со строками

Разбор выражений

Разное

📄 Часто используемые фрагменты

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

Подкатегории

В этой категории отображается 12 подкатегорий из имеющихся 12.

А

П

Р

Разбор выражений

С

Т

Тренировочные олимпиады

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

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

H

Heavy-light-декомпозиция

А

Анализ рекуррентных соотношений. Мастер-теорема

З

Задачи без статей

И

Игры

@@ Строка 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&times;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
+:* [[Жадные алгоритмы]]
+: Динамическое программирование
+:* [[Динамическое программирование]]
+:* [[Задача о рюкзаке и связанные задачи]]
+:* [[Оптимизации динамического программирования]]
+;Математика
+:
+: Теория чисел
+:* 📄 [[НОД. Алгоритм Евклида]]
+:* 📄 [[Простые числа. Решето Эратосфена]]
+:* 📄 [[Быстрое возведение в степень]]
+:* 📄 [[Модульная арифметика]]
+:* 📝 [[Длинная арифметика]]
+:* 📄 [[Метод Гаусса]]
+:* 📄 [[Быстрое преобразование Фурье]]
+: Комбинаторика
+:* 📄 [[Подсчёт и перечисление комбинаторных объектов]]
+:* [[Получение номера по объекту и объекта по номеру]]
+:* [[Перестановки]]
+: Теория игр
+:* [[Игры]]
+: Геометрия
+:* 📝 [[Геометрические примитивы]]
+:* 📄 [[Выпуклая оболочка]]
-Значком <span style='color: #01DF3A;'>&nabla;</span> отмечены темы, которым необходимо уделить особое внимание при подготовке к [[Тренировочная олимпиада №2: Структуры данных|олимпиаде]].
+; Алгоритмы для работы со строками
+:
+:* 📄 [[Хеширование строк]]
+:* 📄 [[Префикс-функция]]
+:* 📄 [[Алгоритм Ахо-Корасик]]
+:* 📄 [[Z-функция]]
+:* 📄 [[Алгоритм Манакера]]
+:* 📄 [[Суффиксный массив]]
+: Разбор выражений
+:* 📝 [[Наивный рекурсивный разбор]]
+:* 📄 [[Алгоритм сортировочной станции]]
-* Структуры данных
+; Разное
-** Предварительные сведения
+:
-*** Введение в ООП. Классы
+:* 📄 [[Часто используемые фрагменты]]
-*** Управление памятью. Указатели
+|}
-** Базовые структуры данных и АТД
-*** Смежные и связные структуры
-*** Динамические массивы
-*** Списки
-*** [[АТД «Стек»]] <span style='color: #01DF3A;'>&nabla;</span>
-*** [[АТД «Очередь»]]
-*** [[АТД «Очередь с приоритетами»]]
-*** [[АТД «Множество». Реализация на битовых векторах]] <span style='color: #01DF3A;'>&nabla;</span>
-*** [[АТД «Множество» и «Словарь». Реализация на деревьях поиска]] <span style='color: #01DF3A;'>&nabla;</span>
-*** АТД «Множество» и «Словарь». Реализация на хэш-таблицах <span style='color: #01DF3A;'>&nabla;</span>
-** Усложнённые структуры данных
-*** [[Система непересекающихся множеств]] <span style='color: #01DF3A;'>&nabla;</span>
-*** Обзор балансирующихся деревьев: 2-3- и LLRB-деревья
-*** [[Декартово дерево]] <span style='color: #01DF3A;'>&nabla;</span>
-*** Декартово дерево по неявному ключу
+''&copy; В. А. Фолунин, 2012–2024''
-''&copy; В. А. Фолунин, УлГТУ, 2012&ndash;2013''

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

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

Подкатегории

А

Г

З

К

П

Р

С

Т

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

H

А

З

И

Навигация

Поиск