Структуры и алгоритмы обработки данных

Тема 9. Общие понятия о сортировке 
Классификация видов сортировки. Задачи сортировки. Внутренняя и 
внешняя сортировки. 
Алгоритмы внутренней сортировки: оптимальная сортировка; дерево 
сортировки и сортировка деревом; быстрая сортировка; сортировка слиянием; 
сортировка вычерпыванием; пример применения сортировки вычерпыванием: 
проверка изоморфизма деревьев; сортировка цепочек; 
сортировка включением; обменная сортировка; сортировка выбором; 
сортировка слиянием; алгоритм Шелла; быстрая сортировка Хоара, оценка его 
сложности в среднем; пирамидальная сортировка; цифровая сортировка; 
цифровая сортировка строк.
Алгоритмы внешней сортировки: прямое слияние; естественное слияние; 
сбалансированное многопутевое слияние; особенности задачи сортировки 
информации на файлах; сбалансированное слияние; многофазная сортировка, 
ее анализ; особенности практической реализации; порядковые статистики. 
Применение основ информатики и программирования к проектированию, 
конструированию и тестированию программных продуктов (ПК-10); навыки 
моделирования, 
анализа 
и 
использования 
формальных 
методов 
конструирования программного обеспечения (ПК-12); 
Тема 10. Классификация основных методов поиска 
Последовательный и индексно-последовательный поиск. Бинарный 
поиск. Эффективность алгоритмов указанных методов поиска. Поиск в 
таблицах и массивах. Задача поиска. Поиск в неупорядоченном массиве. 
Минимально возможная трудоемкость в наихудшем случае. Дихотомический 
поиск в упорядоченном массиве. Таблица, как база данных. Иерархическая 
упорядоченность в таблице. Косвенная адресация. Поиск по нескольким 
ключам. Включающий поиск. Операции проекции и соединения таблиц, как 
обобщение поиска.

---

12 
Использование деревьев в задачах поиска. Методы поиска в основной 
памяти на основе деревьев: Методы поиска во внешней памяти на основе 
деревьев Разновидности B-деревьев для организации индексов в базах данных 
•R-деревья и их использование для организации индексов в пространственных 
базах данных. Деревья для задачи объединения множеств. В-деревья, их 
применение для файлов.