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

Алгоритмы и структуры данных (углубленный курс)

Статус: Курс обязательный (Прикладная математика и информатика)
Направление: 01.03.02. Прикладная математика и информатика
Когда читается: 1-й курс, 2-4 модуль
Формат изучения: без онлайн-курса
Охват аудитории: для своего кампуса
Преподаватели: Анопренко Михаил Валентинович, Грибов Филипп Юрьевич, Курилкин Александр Сергеевич, Нечаев Сергей Петрович, Сафонов Иван Андреевич, Смирнов Иван Федорович, Фадеева Екатерина Сергеевна
Язык: русский
Кредиты: 13
Контактные часы: 230

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

Аннотация

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

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

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

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

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

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

  • Вводная лекция. Структура курса и оргвопросы. Введение в теорию вероятностей (конечные вероятностные пространства).
  • Введение в теорию вероятностей (математическое ожидание, пример анализа алгоритмов).
  • Модель вычислений. Методы анализа алгоритмов, примеры доказательства корректности и оценки времени работы.
  • Эффективные алгоритмы сортировки сравнениями: сортировка слиянием, быстрая сортировка. Оценка снизу на сложность сортировки сравнениями. Поиск порядковой статистики. Метод бинарного поиска. Алгоритмы сортировки, обращающиеся к непосредственным значениям элементов: сортировка подсчётом, цифровая сортировка, корзинная сортировка.
  • Сортирующие сети.
  • Простые структуры данных: односвязный и двусвязный списки, стек, очередь, дек. Двоичные и k-ичные кучи. Биномиальные кучи.
  • Амортизационный анализ. Метод кредитов и метод потенциалов. Упорядоченное множество «для бедных». Очередь на двух стеках и дек на трёх стеках. Динамический массив, стратегии масштабирования и деамортизация.
  • Фибоначчиевы кучи.
  • Хеширование. Постановка задачи, парадокс дней рождений. Полиномиальный хеш.
  • Хеш-таблицы с открытой и закрытой адресацией. Стратегии удаления элементов и масштабирования таблиц. Фильтр Блума.
  • Статичное идеальное хешироавние. Графовый хеш.
  • Бинарные деревья поиска. Сбалансированные деревья. Декартово дерево. Декартово дерево по неявному ключу. Splay-деревья Тарьяна-Слейтера. 2-3 дерево. B-дерево. Skip list.
  • Персистентность и персистентные структуры данных.
  • Задачи на отрезках. Частичные суммы, разреженные таблицы, деревья отрезков. Метод сканирующей прямой. Многомерные деревья отрезков.
  • Задачи на корневых деревьях, LCA и LA. Сведение LCA к RMQ и наоборот. Метод четырёх русских для обеих задач.
  • Перебор комбинаторных объектов. Динамическое программирование. Генерация комбинаторных объектов. Метод meet-in-the-middle. Ускорение вычислений с помощью битовых операций. Эффективное использование памяти в задачах динамического программирования.
  • Методы асимптотических и эвристических оптимизаций перебора. Эффективный перебор в играх с нулевой суммой.
  • Эффективный перебор в играх с нулевой суммой. Альфа-бета отсечение.
  • Теория графов. Обходы в глубину и ширину, топологическая сортировка, поиск цикла, компоненты сильной связности. Задача 2-выполнимости. Мосты и точки сочленения.
  • Кратчайшие пути во взвешенных графах. Алгоритмы Форда-Беллмана, Флойда-Уоршелла и Дейкстры. Потенциалы Джонсовна, оптимизация А*
  • Задача о минимальном остове. Лемма о безопасном ребре. Алгоритмы Прима, Борувки и Краскалла
  • Графы во внешней памяти. Задача ранжирования списка.
  • Паросочетания в двудольном графе. Алгоритм Куна. Теорема Кёнига-Эгервари. Теорема Дилворта
  • Задача о максимальном потоке. Теорема Форда-Фалкерсона.
  • Полиномиальные алгоритмы решения задачи о максимальном потоке. Алгоритм Эдмондса- Карпа, техника масштабирования, алгоритм Диница.
  • Стоимостной поток. Определения и жадный алгоритм. Алгоритм Дейкстры с потенциалами Джонсона.
  • Задача поиска шаблона в тексте. Префикс-фукнция и z-функция. Автомат префикс-функции. Алгоритм Бойера-Мура.
  • Префиксное дерево. Алгоритм Ахо-Корасик.
  • Сжатое префиксное дерево. Алгоритм Укконена.
  • Формальные языки. Иерархия языков. Определения РВ, ДКА, НКА, eps-НКА. Лемма о накачке. Эквивалентность РВ, ДКА, НКА.
  • Алгоритмы минимизации ДКА и НКА.
  • Проблема P = NP, теорема Кука-Левина. NP-полнота некоторых задач.
  • Классы задач L, P, NP, co-NP, NPC, co-NPC, PSPACE, EXPTIME, BPP, ZP, RP. Некоторые соотношения данных классов.
  • Введение в теоретико-числовые алгоритмы. Быстрое возведение в степень, расширенный алгоритм Евклида, решето Эратосфена и линейное решето, факторизация за O(/n). Первообразный корень и дискретное логарифмирование.
  • Тест на простоту Миллера-Рабина.
  • Передача данных. Шифрование с открытым ключом, схема RSA. Цифровая подпись, установка безопасного соединения.
  • Передача данных. Коды выявляющие и исправляющие ошибки.
  • Передача данных. Сжатие с потерями и без, код Хаффмана, алгоритм LZW, сжатие изображений.
  • Алгоритм Карацубы. Быстрое умножение матриц. Метод деревьев рекурсии и основная теорема.
  • Быстрое преобразование Фурье.
  • Эвристические методы оптимизации: локальные оптимизации, имитация отжига, генетические алгоритмы.
  • Численные методы интегрирования. Метод Монте-Карло.
  • Численные методы оптимизации. Троичный поиск, метод Ньютона.
  • Вычислительная геометрия. Основные примитивы (точка, прямая, окружность) и базовые действия с ними. Выпуклая оболочка за O(n log n), триангуляция невыпуклого многоугольника. Задача поиска двух ближайших точек. Пересечение полуплоскостей.
  • Проверка наличия пересечения отрезков за O(n log n) и задача point location. Трёхмерная выпуклая оболочка за O(n ^2 ).
  • Концепция параметрического поиска Мегиддо.
  • Линейное программирование, постановка задачи и примеры. Двойственная задача, слабая двойственность.
  • Симплекс-метод. Поиск допустимого решения. Доказательство корректности и сильная двойственность.
  • Приближённые алгоритмы. Константные приближения в некоторых задачах. Техника дерандомизации. Задача о покрытии множества. PTAS задачи о рюкзаке.
  • Построение приближённых алгоритмов с помощью задачи линейного программирования. e−1/e - приближение и 3/4 -приближение в задаче MAXSAT.
  • Стриминговые алгоритмы. Задача поиска тяжёлых элементов. Подсчёт количества различных элементов с помощью k-min и HyperLogLog. Подсчёт элементов с заданным значением в потоке с помощью count-min-sketch и count-sketch.
  • Стриминговые алгоритмы. Приближённое вычисление порядковых статистик и суммы к окне, доказательство неулучшаемости оценки.
Элементы контроля

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

  • неблокирующий Контесты
  • неблокирующий Листки
    Листки являются теоретическими домашними заданиями. Все задачи стоят одинаково, сдавать их можно в электронном виде. Дополнительно предусматривается возможность сдать их во время присутственных часов на консультациях ассистентам.
  • неблокирующий Контрольная работа
  • неблокирующий Экзамен
  • неблокирующий Контесты
  • неблокирующий Листки
    Листки являются теоретическими домашними заданиями. Все задачи стоят одинаково, сдавать их можно в электронном виде. Дополнительно предусматривается возможность сдать их во время присутственных часов на консультациях ассистентам.
  • неблокирующий Контрольная работа
  • неблокирующий Бонус
    Эта графа определяет произвольные баллы, которые могут быть прибавлены к оценке студента за различные виды деятельности и соревнований. Например, в этой графе будут использованы некоторые короткие контесты с необычным форматом.
  • неблокирующий Экзамен
Промежуточная аттестация

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

  • 2022/2023 учебный год 2 модуль
    0.429 * Контесты + 0 * Бонус + 0.214 * Контрольная работа + 0.357 * Листки
  • 2022/2023 учебный год 3 модуль
    0.3 * Контесты + 0.25 * Листки + 0.15 * Контрольная работа + 0.3 * Экзамен + 0 * Бонус
  • 2022/2023 учебный год 4 модуль
    0.3 * Контесты + 0.3 * Экзамен + 0.25 * Листки + 0.15 * Контрольная работа + 0 * Бонус
Список литературы

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

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

  • Алгоритмы: построение и анализ, Кормен, Т., 2007

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

  • Algorithms, DasGupta, S., 2018

Авторы

  • Алиева Эльмира Махир Кызы