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

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

Статус: Курс обязательный (Прикладная математика и информатика)
Направление: 01.03.02. Прикладная математика и информатика
Когда читается: 1-й курс, 2, 4 модуль
Охват аудитории: для своего кампуса
Язык: русский
Кредиты: 9

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

Аннотация

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

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

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

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

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

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

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

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

  • неблокирующий Контесты
  • неблокирующий Листки
  • неблокирующий Контрольные
  • неблокирующий Экзамен
    Экзамен проходит в письменной форме с синхронным проторингом. Технические требования: web-камера, микрофон, наушники / колонки, Zoom.
Промежуточная аттестация

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

  • Промежуточная аттестация (2 модуль)
    0.3 * Контесты + 0.15 * Контрольные + 0.25 * Листки + 0.3 * Экзамен
  • Промежуточная аттестация (4 модуль)
    0.3 * Контесты + 0.15 * Контрольные + 0.25 * Листки + 0.3 * Экзамен
Список литературы

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

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

  • Седжвик Р. - Алгоритмы на С++ - Национальный Открытый Университет "ИНТУИТ" - 2016 - 1772с. - ISBN: - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/100565

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

  • Вирт Н. - Алгоритмы и структуры данных. Новая версия для Оберона - Издательство "ДМК Пресс" - 2010 - 272с. - ISBN: 978-5-94074-584-6 - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/1261