Нечисленные алгоритмы программирования

Отчетность: 
зачёт
Тип: 
по выбору
Часов: 
36
Семестр: 
IV-7

Данный курс доступен на сайте "Университет без границ".

Аннотация

Спецкурс посвящен современным классическим алгоритмам, которые часто встречаются в реальной практике программирования: рассматриваются разные варианты задач сортировки и поиска данных, описываются типовые структуры данных (списки, деревья, хэш-таблицы, деревья цифрового поиска), позволяющие решать эти задачи эффективно, разбираются задачи, требующие рекурсивного программирования, а также схемы ускорения работы алгоритмов за счет применения кэширования данных в быстрой памяти. В ряде случаев проводится теоретический анализ производительности различных вариантов решения задач программирования, для каждого варианта решения описывается сфера его применимости на практике. По каждой теме спецкурса студенты выполняют и сдают индивидуальные практические задания по измерению и сравнению эффективности работы разных алгоритмов решения одной и той же задачи, что позволяет увязать излагаемую теорию с практическими навыками реализации и использования алгоритмов программирования.

Программа

  1. Введение. Содержание курса, литература. Ускорение программ методом барьера. Поиск элемента в массиве - простой и ускоренный (дихотомия). Анализ алгоритмов.
  2. Поиск подстроки. Простой алгоритм, алгоритм Рабина-Карпа, алгоритмы Кнута-Морриса-Пратта и Боуера-Мура. Анализ алгоритмов. Метрика на строках. Алгоритм дистанции Левенштейна.
  3. Сортировка. Основные определения, классификация алгоритмов. Простые методы сортировки массивов: метод включения, метод выделения, метод пузырька (обмена). Анализ алгоритмов.
  4. Улучшенные методы сортировки массивов: методы Шелла, пирамидальная сортировка (HeapSort), быстрая сортировка (QuickSort и его варианты). Анализ алгоритмов. Структура данных Heap и сфера ее применения.
  5. Сортировка за линейное время: сортировка подсчетом, Radix-Sort, сортировка вычерпыванием ("корзинная") как обобщение Radix-Sort.
  6. Битональная сортировка, ее использование в массивно-параллельных алгоритмах.
  7. Методы сортировки последовательностей: сортировка слиянием, ее анализ. Результаты экспериментального сравнения алгоритмов. Многопутевое и многофазное слияние.
  8. Сортировка больших массивов, не помещающихся в оперативную память. Адаптация сортировки слиянием для этой задачи.
  9. Рекурсивные алгоритмы - основные определения и методы. Сведение рекурсии к итерациям. Сложная рекурсия. Хвостовая рекурсия, ее оптимизация в языках программирования. Задачи о фрактальных кривых как пример сложной рекурсии (кривые Гильберта, Серпинского).
  10. Рекурсивные методы при решении поисковых задач искусственного интеллекта. Поиск эвристик. Задача о восьми ферзях.
  11. Динамические структуры данных: алгоритмы обработки списков. Влияние способа сортировки списка на задачу поиска. Кольцевые списки. Многосвязные списки (skip-lists).
  12. Динамические массивы, стеки и очереди (deque).
  13. Деревья и их применение для задач поиска с включением. Бинарные деревья. Балансировка. АВЛ-Деревья. Красно-черные деревья.
  14. В-деревья и B+-деревья. Задачи построения динамических хранилищ. 2-3 деревья.
  15. Хэширование и хэш-таблицы. Хэширование строк. Методы разрешения коллизий: метод цепочек, линейных и квадратичных проб. Совершенное хэширование, кукушкино хэширование. Фильтры Блума.
  16. Цифровой поиск: префиксные деревья, trie, patricia.
  17. Стратегии оперативного кэширования часто используемых данных в быстрой памяти.

Литература

  1. Н. Вирт. «Алгоритмы и структуры данных» М.: ДМК, 2010
  2. Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн. «Алгоритмы: построение и анализ» М.: Вильямс, 2021.
  3. Р. Седжвик. «Фундаментальные алгоритмы на C++» М.: Диасофт, 2003.
  4. М.А. Бабенко, М.В. Левин. «Введение в теорию алгоритмов и структур данных» М.: МЦНМО, 2020.
  5. Д. Кнут. «Искусство программирования для ЭВМ» (т. 1-3) М.: Вильямс, 2001.
  6. А. Axo, Д. Хопкрофт, Д. Ульман. «Разработка и анализ компьютерных алгоритмов» М.: Вильямс, 2021.