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

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

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

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

уметь

Содержание разделов дисциплины (предварительный вариант)

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

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