Алгоритмы и структуры данных

Цели и задачи дисциплины

В результате изучения дисциплины слушатели должны познакомиться с базовыми структурами данных и алгоритмами.

В результате изучения дисциплины слушатели должны знать

уметь

Содержание разделов дисциплины

  1. Анализ сложности алгоритмов. Асимптотические оценки, O-нотация. Анализ рекурсивных алгоритмов, решение рекуррентных соотношений. Общие методы построения алгоритмов (жадные алгоритмы, алгоритмы типа «разделяй и властвуй», рекурсивные алгоритмы, вероятностные алгоритмы). Амортизационный анализ. Метод потенциалов, метод предоплаты.
  2. Базовые структуры данных. Массив, запись. Списки. Стек, очередь, дек. Вектор.
  3. Базовые алгоритмы поиска. Линейный поиск. Двоичный поиск.
  4. Алгоритмы сортировки. Квадратичные сортировки. Сортировка кучей. Сортировка слиянием. Быстрая сортировка. Сортировки за линейное время. Сортирующие сети.
  5. Более сложные структуры данных. Приоритетная очередь, реализация с использованием кучи. Дерево поиска. АВЛ-дерево, красно-черное дерево, декартово дерево. B-деревья. Хеш-таблица. Система непересекающихся множеств.
  6. Динамическое программирование. Задача о наибольшей общей подпоследовательности, задача о наибольшей возрастающей подпоследовательности, задача о кафе у дороги. Динамическое программирование по профилю.
  7. Базовые алгоритмы на графах. Понятие графа. Представление графов в программе. Понятия пути, связности. Обход в ширину. Обход в глубину и его применения. Топологическая сортировка. Декомпозиция графа. Алгоритм Беллмана-Форда. Алгоритм Дейкстры. Алгоритм Флойда. Поиск минимального остовного дерева. Кратчайшее дерево путей в ориентированном графе. Алгоритм Чу Йонджина и Лю Цзенхонга. Задача коммивояжера.
  8. Алгоритмы над строками. Поиск подстроки. Наивный подход. Алгоритм Кнута-Морриса-Пратта. Понятие конечного автомата. Автомат для поиска подстроки в строке. Алгоритм Ахо-Корасик. Суффиксное дерево. Регулярные выражения. Сжатое суффиксное дерево. Алгоритм Укконена.
  9. Алгоритмы сжатия. Количество информации в тексте. Энтропия. Колмогоровская сложность. Сжатие последовательных серий. RLE-кодирование. Префиксные коды. Алгоритм Хаффмана. Арифметическое кодирование. Алгоритмы на базе преобразования Лемпеля-Зива. Преобразование Барроуза-Уиллера.
  10. Алгоритмы комбинаторной оптимизации в сетях. Понятие потока в сети. Алгоритм Форда-Фалкерсона. Градиентная модификация алгоритма Форда-Фалкерсона. Алгоритм Эдмондса-Карпа. Задача о максимальном паросочетании в двудольном графе. Задача о назначениях. Венгерский алгоритм.
  11. Алгоритмы вычислительной геометрии. Базовые геометрические объекты. Базовые геометрические алгоритмы. Пересечение прямых, лучей, отрезков, окружностей. Построение прямой, окружности по заданным точкам. Площадь многоугольника. Формула трапеций. Формула треугольников. Выпуклая оболочка. Алгоритм Грэхема. Алгоритм Джарвиса. Оптимизационные задачи вычислительной геометрии. Пара ближайших точек. Пара наиболее удаленных точек. Задача о наименьшей охватывающей окружности.
  12. Криптографические алгоритмы. Математическая база. Подстановочный и перестановочный шифры. Шифры с закрытым ключом. Шифры с открытым ключом. Шифр RSA. Распределение ключей по открытым каналам с использованием схемы Диффи-Хеллмана.

Рекомендуемая литература