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

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
(не показано 27 промежуточных версий этого же участника)
Строка 1: Строка 1:
{|
{|
|
|
;1. Сортировка и поиск
;Сортировка и поиск
:
:
:* Критерии эффективности алгоритма. Асимптотический анализ
:* Критерии эффективности алгоритма. Асимптотический анализ
:* [[Асимптотический анализ рекуррентных соотношений]]
: Простейшие алгоритмы сортировки
: Простейшие алгоритмы сортировки
:* Сортировка выбором
:* Сортировка выбором
Строка 11: Строка 12:
:* [[Быстрая сортировка]]
:* [[Быстрая сортировка]]
: Сортировка за линейное время
: Сортировка за линейное время
:* Сортировка подсчётом
:* [[Сортировка подсчётом]]
:* Поразрядная сортировка
:* Поразрядная сортировка
: Алгоритмы поиска
: Алгоритмы поиска
:* [[Бинарный поиск]]
:* [[Бинарный поиск]]
:* [[Тернарный поиск]]
:* [[Тернарный поиск]]
; 1½. Арифметические алгоритмы
: Применение сортировки
:
:* [[Сканирующая прямая]]
:* [[НОД. Алгоритм Евклида]]
;Структуры данных
:* [[Простые числа. Решето Эратосфена]]
:* Быстрое возведение в степень
:* [[Длинная арифметика]]
;2. Структуры данных
:
:
:* Введение в ООП. Классы
:* Введение в ООП. Классы
Строка 38: Строка 35:
:* [[Система непересекающихся множеств]]
:* [[Система непересекающихся множеств]]
: Балансирующиеся деревья
: Балансирующиеся деревья
:* Обзор балансирующихся деревьев: 2-3- и LLRB-деревья
:* Обзор балансирующихся деревьев
:* [[АВЛ-дерево]]
:* [[Декартово дерево]]
:* [[Декартово дерево]]
:* [[Расширения декартова дерева]]
:* [[Расширения декартова дерева]]
: Структуры данных для задач RSQ/RMQ
: Обработка запросов на отрезках
:* Sqrt-декомпозиция
:* [[Дерево Фенвика]]
:* [[Дерево Фенвика]]
:* [[Дерево отрезков]]
:* [[Дерево отрезков]]
:* [[Sparse table]]
:* [[Sparse table]]
:* Sqrt-декомпозиция
:* [[Алгоритм Мо]]
|
|
;3. Алгоритмы для работы с графами
;Алгоритмы для работы с графами
:
:
:* Основные определения. Представление графов
:* Основные определения. Представление графов
Строка 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&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>
:* [[Метод двоичного подъёма]]<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
:* [[Жадные алгоритмы]]
:* [[Динамическое программирование]]
:* [[Динамическое программирование]]
;Математика
:
: Теория чисел
:* [[НОД. Алгоритм Евклида]]
:* [[Простые числа. Решето Эратосфена]]
:* [[Быстрое возведение в степень]]
:* [[Длинная арифметика]]
:* [[Метод Гаусса]]
: Комбинаторика
: Комбинаторика
:* [[Подсчёт и перечисление комбинаторных объектов]]
:* [[Подсчёт и перечисление комбинаторных объектов]]
:* [[Получение номера по объекту и объекта по номеру]]
:* [[Получение номера по объекту и объекта по номеру]]
:* [[Перестановки]]
:* [[Перестановки]]
: Теория игр
:* [[Игры]]
: Геометрия
: Геометрия
:* [[Геометрические примитивы]]
:* [[Выпуклая оболочка]]
:* [[Выпуклая оболочка]]
; Алгоритмы для работы со строками
:
:* [[Хеширование строк]]
:* [[Префикс-функция]]
:* [[Алгоритм Манакера]]
: Разбор выражений
:* [[Наивный рекурсивный разбор]]
|}
|}


''&copy; В. А. Фолунин, УлГТУ, 2012&ndash;2014''
''&copy; В. А. Фолунин, 2012&ndash;2019''

Версия от 18:04, 30 августа 2019

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

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

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

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