• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
Бакалавриат 2019/2020

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

Язык: русский
Кредиты: 9

Программа дисциплины

Аннотация

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

Цель освоения дисциплины

  • ознакомление студентов с основными принципами проектирования и анализа алгоритмов и структур данных
  • развитие навыков обоснования корректности алгоритмов, их практической реализации, теоретической и экспериментальной оценки их временной сложности
Планируемые результаты обучения

Планируемые результаты обучения

  • Знать о наиболее важных алгоритмах и структурах данных и основных принципах их проектирования и анализа
  • Уметь обосновывать корректность алгоритмов, проводить теоретическую и экспериментальную оценки их временной сложности
  • Уметь формализовать условие задачи, требующей алгоритмического решения, разбить задачу на подзадачи, сформулировать эффективный алгоритм решения задачи
  • Иметь навыки реализации алгоритмов на языках Python и C++
Содержание учебной дисциплины

Содержание учебной дисциплины

  • Рекурсивные алгоритмы и рекуррентные соотношения
    Рекурсия и дерево рекурсии. Организация перебора вариантов (выход из лабиринта) с помощью рекурсии. Быстрое возведение в степень, бинарный поиск (с оценкой на число вызовов). Элиминация хвостовой рекурсии.
  • Асимптотический анализ
    $O$-, $o$- и $\Theta$-формализм. Асимптотическая иерархия функций. Анализ конкретных алгоритмов: сложность вложенных циклов, сложность бинарного поиска.
  • Динамическое программирование
    Динамическое программирование как "экономная рекурсия", подходы снизу вверх и сверху вниз. Классические применения: наибольшая возрастающая подпоследовательность, вычисление расстояния Левенштейна, целочисленная задача о рюкзаке.
  • Сортировки
    Сортировка вставкой, сортировка слиянием, быстрая сортировка и др.
  • Разделяй и властвуй
    Решение рекуррентных соотношений через дерево рекурсии. Выбор порядковой статистики за время $O(n)$, поиск ближайшей пары точек за время $O(n \log n)$, алгоритм Карацубы для умножения целых чисел, алгоритм Штрассена для умножения матриц.
  • Алгоритмы на графах
    Способы представления графов: матрица смежности и списки смежности. Обход в глубину и в ширину, поиск компонент связности в неориентированных и ориентированных графах, топологическая сортировка. Алгоритмы Флойда – Уоршелла и Беллмана – Форда.
  • Структуры данных
    Линейные структуры данных. Амортизационный анализ. Хеш-функции и хеш-таблицы. Разрешение коллизий при помощи цепочек. Открытая адресация. Двухуровневое идеальное хеширование. Деревья поиска. Сбалансированные деревья поиска. Красно-черные деревья. Динамические порядковые статистики.
  • Жадные алгоритмы
    Основные принципы, примеры алгоритмов. Поиск кратчайших путей в графе при помощи алгоритма Дейкстры. Приоритетная очередь на основе двоичной кучи. Минимальные остовные деревья: алгоритмы Прима и Крускала. Система непересекающихся множеств.
  • Потоки в сетях
    Задача о максимальном потоке. Максимальный поток и минимальный разрез. Алгоритмы Форда – Фалкерсона и Эдмондса – Карпа. Сведение задачи о максимальном паросочетании в двудольном графе к задаче о максимальном потоке. Устойчивые паросочетания и алгоритм Гейла – Шепли.
  • Конечные автоматы, регулярные выражения, контекстно-свободные грамматики
    Конечные автоматы. Регулярные языки. Минимизация конечного автомата. Недетерминированные конечные автоматы. Замкнутость регулярных языков относительно регулярных операций. Регулярные выражения. Эквивалентность регулярных выражений и конечных автоматов. Три подхода к реализации регулярных выражений: детерминированный автомат, поиск с возвратами в недетерминированном автомате, имитация детерминированного автомата по недетерминированному. Нерегулярные языки. Лемма о накачке. Контекстно-свободные грамматики. Автоматы с магазинной памятью. Эквивалентность контекстно-свободных грамматик и автоматов с магазинной памятью. Построение автомата по грамматике. Лемма о накачке для контекстно-свободных языков. Разбор слов по контекстно-свободной грамматике: алгоритм динамического программирования для грамматики в нормальной форме Хомского.
Элементы контроля

Элементы контроля

  • неблокирующий Домашнее задание
  • неблокирующий Контрольная работа 1
  • неблокирующий Работа на семинаре 1
  • неблокирующий Экзамен (письменный) 1
  • неблокирующий Домашнее задание 2
  • неблокирующий Контрольная работа 2
  • неблокирующий Работа на семинаре 2
  • неблокирующий Экзамен (устный)
Промежуточная аттестация

Промежуточная аттестация

  • Промежуточная аттестация (2 модуль)
    0.3 * Домашнее задание + 0.2 * Контрольная работа 1 + 0.1 * Работа на семинаре 1 + 0.4 * Экзамен (письменный) 1
  • Промежуточная аттестация (4 модуль)
    0.2 * Домашнее задание 2 + 0.07 * Контрольная работа 2 + 0.33 * Промежуточная аттестация (2 модуль) + 0.07 * Работа на семинаре 2 + 0.33 * Экзамен (устный)
Список литературы

Список литературы

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

  • Cormen, T. H. (2009). Introduction to Algorithms (Vol. 3rd ed). Cambridge, Mass: The MIT Press. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=343613

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

  • Arora, S., & Barak, B. (2009). Computational Complexity : A Modern Approach. Cambridge: Cambridge eText. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=304712