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

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
Строка 47: Строка 47:
:* Основные определения. Представление графов
:* Основные определения. Представление графов
: Поиск в глубину и его приложения
: Поиск в глубину и его приложения
:* Поиск в глубину
:* Поиск в глубину<sup>''O(V+E)''</sup>
:* Циклы в графе. Двудольность
:* Циклы в графе. Двудольность
:* Компоненты связности
:* Компоненты связности
Строка 54: Строка 54:
:* Компоненты сильной связности. Алгоритм Косараю-Шарира
:* Компоненты сильной связности. Алгоритм Косараю-Шарира
: Кратчайшие пути
: Кратчайшие пути
:* Поиск в ширину
:* Поиск в ширину<sup>''O(V+E)''</sup>
:* Кратчайшие пути из одной вершины. Алгоритм Дейкстры
:* Кратчайшие пути из одной вершины. Алгоритм Дейкстры<sup>''O(V<sup>2</sup>+E), O(ElogV)''</sup>
:* Кратчайшие пути из одной вершины. Алгоритм Форда-Беллмана
:* Кратчайшие пути из одной вершины. Алгоритм Форда-Беллмана<sup>''O(VE)''</sup>
:* Кратчайшие пути из одной вершины в ациклических орграфах
:* Кратчайшие пути из одной вершины в ациклических орграфах<sup>''O(V+E)''</sup>
:* Кратчайшие пути между всеми парами вершин. Алгоритм Флойда
:* Кратчайшие пути между всеми парами вершин. Алгоритм Флойда<sup>''O(V<sup>3</sup>)''</sup>
: Минимальное остовное дерево
: Минимальное остовное дерево
:* Алгоритм Краскала
:* Алгоритм Краскала<sup>''O(ElogV)''</sup>
:* Алгоритм Прима
:* Алгоритм Прима<sup>''O(V<sup>2</sup>+E), O(ElogV)''</sup>
|}
|}


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

Версия от 09:56, 26 июля 2013

1. Сортировка и поиск
  • Критерии эффективности алгоритма. Асимптотический анализ
Простейшие алгоритмы сортировки
  • Сортировка выбором
  • Сортировка вставками
Улучшенные алгоритмы сортировки
  • Сортировка слиянием
  • Быстрая сортировка
Сортировка за линейное время
  • Сортировка подсчётом
  • Поразрядная сортировка
Алгоритмы поиска
  • Бинарный поиск
  • Тернарный поиск
1½. Арифметические алгоритмы
  • НОД. Алгоритм Евклида
  • Простые числа. Решето Эратосфена
  • Быстрое возведение в степень
  • Длинная арифметика
2. Структуры данных
  • Введение в ООП. Классы
  • Управление памятью. Указатели
Базовые структуры и абстрактные типы данных
Балансирующиеся деревья
  • Обзор балансирующихся деревьев: 2-3- и LLRB-деревья
  • Декартово дерево
  • Расширения декартова дерева
RSQ/RMQ
3. Алгоритмы для работы с графами
  • Основные определения. Представление графов
Поиск в глубину и его приложения
  • Поиск в глубинуO(V+E)
  • Циклы в графе. Двудольность
  • Компоненты связности
  • Мосты и точки сочленения
  • Топологическая сортировка
  • Компоненты сильной связности. Алгоритм Косараю-Шарира
Кратчайшие пути
  • Поиск в ширинуO(V+E)
  • Кратчайшие пути из одной вершины. Алгоритм ДейкстрыO(V2+E), O(ElogV)
  • Кратчайшие пути из одной вершины. Алгоритм Форда-БеллманаO(VE)
  • Кратчайшие пути из одной вершины в ациклических орграфахO(V+E)
  • Кратчайшие пути между всеми парами вершин. Алгоритм ФлойдаO(V3)
Минимальное остовное дерево
  • Алгоритм КраскалаO(ElogV)
  • Алгоритм ПримаO(V2+E), O(ElogV)

© В. А. Фолунин, УлГТУ, 2012–2013

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

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

H

А

З

И

Источник — https://acm.khpnets.info/w39/index.php?title=Категория:Учебный_курс_«Алгоритмы_и_структуры_данных»&oldid=564