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

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

Текущая версия на 05:16, 31 августа 2021

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

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

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

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