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

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

Лучший по критерию «Полезность курса для Вашей будущей карьеры»
Статус: Курс обязательный (Прикладная математика и информатика)
Направление: 01.03.02. Прикладная математика и информатика
Когда читается: 1-й курс, 2, 4 модуль
Формат изучения: Full time
Преподаватели: Брагин Сергей Дмитриевич, Густокашин Михаил Сергеевич, Евстропов Глеб Олегович, Объедков Сергей Александрович, Самоненко Илья Юрьевич, Светличный Дмитрий Владимирович, Смирнов Иван Федорович, Строк Федор Владимирович, Техажева София Андреевна, Харитонов Валерий Дмитриевич
Язык: русский
Кредиты: 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