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

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

---

13 
Тема 13. Исчерпывающий поиск 
Перебор с возвратом (backtracking), общий алгоритм. Пример задачи о 
ферзях, усовершенствования. Оценка сложности выполнения. Метод ветвей и 
границ. Общая схема. Задача коммивояжера: решение методом ветвей и границ. 
Динамическое программирование. Эвристические методы: ближайшего соседа, 
ближайшего города. Оценки приближения. 
Обосновывание принимаемых проектных решений, осуществление 
постановка и выполнение экспериментов по проверке их корректности и 
эффективности (ПК-4).