Нечисленные алгоритмы программирования
Аннотация
Спецкурс посвящен современным классическим алгоритмам, которые часто встречаются в реальной практике программирования: рассматриваются разные варианты задач сортировки и поиска данных, описываются типовые структуры данных (списки, деревья, хэш-таблицы, деревья цифрового поиска), позволяющие решать эти задачи эффективно, разбираются задачи, требующие рекурсивного программирования, а также схемы ускорения работы алгоритмов за счет применения кэширования данных в быстрой памяти. В ряде случаев проводится теоретический анализ производительности различных вариантов решения задач программирования, для каждого варианта решения описывается сфера его применимости на практике. По каждой теме спецкурса студенты выполняют и сдают индивидуальные практические задания по измерению и сравнению эффективности работы разных алгоритмов решения одной и той же задачи, что позволяет увязать излагаемую теорию с практическими навыками реализации и использования алгоритмов программирования.
Программа
- Введение. Содержание курса, литература. Ускорение программ методом барьера. Поиск элемента в массиве - простой и ускоренный (дихотомия). Анализ алгоритмов.
- Поиск подстроки. Простой алгоритм, алгоритм Рабина-Карпа, алгоритмы Кнута-Морриса-Пратта и Боуера-Мура. Анализ алгоритмов. Метрика на строках. Алгоритм дистанции Левенштейна.
- Сортировка. Основные определения, классификация алгоритмов. Простые методы сортировки массивов: метод включения, метод выделения, метод пузырька (обмена). Анализ алгоритмов.
- Улучшенные методы сортировки массивов: методы Шелла, пирамидальная сортировка (HeapSort), быстрая сортировка (QuickSort и его варианты). Анализ алгоритмов. Структура данных Heap и сфера ее применения.
- Сортировка за линейное время: сортировка подсчетом, Radix-Sort.
- Методы сортировки последовательностей: сортировка слиянием, ее анализ. Результаты экспериментального сравнения алгоритмов. Многопутевое слияние.
- Сортировка больших массивов, не помещающихся в оперативную память. Адаптация сортировки слиянием для этой задачи.
- Рекурсивные алгоритмы - основные определения и методы. Сведение рекурсии к итерациям. Сложная рекурсия. Фрактальные кривые (Гильберта, Серпинского).
- Рекурсивные методы при решении поисковых задач искусственного интеллекта. Поиск эвристик. Задача о восьми ферзях.
- Динамические структуры данных: алгоритмы обработки списков. Влияние порядка сортировки списка на задачу поиска. Кольцевые списки. Многосвязные списки (skip-lists).
- Динамические массивы и деки (deque).
- Деревья и их применение для задач поиска/включения. Бинарные деревья. Балансировка. АВЛ-Деревья. Красно-черные деревья.
- В-деревья и B+-деревья. Задачи построения динамических хранилищ. 2-3 деревья.
- Хэширование и хэш-таблицы. Методы разрешения коллизий. Открытая адресация, квадратичные пробы. Хэширование строк. Совершенное хэширование.
- Цифровой поиск: префиксные деревья, trie, patricia.
- Стратегии кэширования часто используемых данных в быстрой памяти.
Литература
- Н.Вирт. Алгоритмы и структуры данных.
- Р.Седжвик. Фундаментальные алгоритмы на C++.
- М.А.Бабенко, М.В.Левин. Введение в теорию алгоритмов и структур данных.
- Т.Кормен, Ч.Лейзерсон, Р.Ривест. Алгоритмы: построение и анализ.
- Д.Кнут. Искусство программирования для ЭВМ.
Вложение | Размер |
---|---|
![]() | 226.11 КБ |