Discrete Models and Algorithms Complexity

2020/2021

Academic Year

RUS

Instruction in Russian

5

ECTS credits

Delivered at:

Department of Applied Mathematics and Informatics (Faculty of Informatics, Mathematics, and Computer Science (HSE Nizhny Novgorod))

Course type:

Compulsory course

When:

1 year, 1, 2 module

Instructor

Malyshev, Dmitriy

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

Аннотация

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

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

• Подготовка в области основ гуманитарных, социальных, экономических, математических и естественно-научных знаний.
• Получение высшего профессионально профилированного (на уровне магистра) образования, позволяющего выпускнику успешно работать в избранной сфере деятельности.
• Обладание универсальными и предметно-специализированными компетенциями, способствующими его социальной мобильности и устойчивости на рынке труда.

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

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

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

• Модели вычислений.
  16 проблема Гильберта и ее роль в формировании понятия алгорит-ма. Машина Тьюринга-Поста. Алгорифмы Маркова. Методика Флойда верификации тью-ринговых программ. Понятие об измерении временной и пространственной сложностей алгоритмов.
• Анализ алгоритмов.
  Виды асимптотических оценок алгоритмов. О, Omega, Theta-символика и другие сведения из математического анализа, необходимые для асимптотического оценивания алгоритмов. Амортизационные оценки. Методы доказательства амортизационных оценок. Амортизационный анализ работы двоичного счетчика.
• Эффективная разрешимость и «труднорешаемость» дискретных задач.
  Классы сложности P, NP, NPC, гипотеза P не равно NP. Подходы к решению NP-полных задач: выделение эффективно решаемых случаев, построение приближенных и эвристических алгоритмов.
• Структуры данных.
  Понятие об абстрактных структурах данных. Список, как абстрактная структура данных, ее конкретные реализации в машинной памяти (прямой и последовательный доступы). Структура данных – разделенное множество. Реализации разделенных множеств при помощи списков, с помощью деревьев со сжатием и без сжатия путей. Оценки трудоемкости операций, теорема Тарьяна. Структура данных – приоритетная очередь. Реализация приоритетных очередей на основе завершенных d-арных деревьев. Комбинаторные свойства таких деревьев. Комбинаторные свойства левосторонних деревьев, реализация приоритетных очередей на их основе, оценки выполнения основных операций. Комбинаторные свойства биномиальных деревьев. Реализация приоритетных очередей на основе биномиальных деревьев с оценками трудоемкостей. Фибоначчиевы кучи, оценки трудоемкости операций. Структура данных –поисковое дерево. Критерии и способы балансировки поисковых деревьев. Красно-черные деревья и их комбинаторные свойства. АВЛ-деревья и и их комбинаторные свойства. B-деревья и их комбинаторные свойства.
• Алгоритмы и их эффективные реализации.
  Задача сортировки данных и ее решение пирамидальной сортировкой. Задача о минимальном остовном дереве, ее решение при помощи разделенных множеств. Задача о кратчайших путях в графе и ее решение с использованием приоритетной очереди. Задача о поиске пары пересекающихся отрезков на плоскости, ее решение при помощи поисковых деревьев. Комбинированное использование различных структур данных в рамках одного алгоритма (например, Round Robin).
• Строковые алгоритмы
  Алгоритмы поиска фрагментов в текстах («наивный» и Кнута-Морриса-Пратта). Суффиксные деревья и алгоритмы (по МакКрейту и Укконену) их построения. Доказательство оценок трудоемкости.

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

• Контрольная работа
• Домашнее задание
• Экзамен 1
• Экзамен 2

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

• Промежуточная аттестация (1 модуль)
  0.5 * Домашнее задание + 0.5 * Контрольная работа
• Промежуточная аттестация (2 модуль)
  На оценку за второй экзамен влияют две оценки - за лабораторную работу O_лр и за ответ на экзамене O_ответ. Формула такая: O_э2=1/3*О_лр+2/3*О_ответ. Итоговая оценка следующая - 1/2*(О_э1+O_э2).

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

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

• Алгоритмы : построение и анализ, пер. с англ., 3-е изд., 1323 с., Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К., 2018

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

• Алексеев В.Е., Таланов В.А. - Графы и алгоритмы - Национальный Открытый Университет "ИНТУИТ" - 2016 - 153с. - ISBN: 5-9556-0066-3 - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/100593