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

Дискретные модели и сложность алгоритмов

Лучший по критерию «Полезность курса для Вашей будущей карьеры»
Лучший по критерию «Полезность курса для расширения кругозора и разностороннего развития»
Лучший по критерию «Новизна полученных знаний»
Статус: Курс обязательный (Интеллектуальный анализ данных)
Направление: 01.04.02. Прикладная математика и информатика
Когда читается: 1-й курс, 1, 2 модуль
Формат изучения: Full time
Прогр. обучения: Интеллектуальный анализ данных
Язык: русский
Кредиты: 5

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

Аннотация

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

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

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

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

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

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

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

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

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

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

  • Промежуточная аттестация (1 модуль)
    0.5 * Контрольная работа + 0.5 * Экзамен 1
  • Промежуточная аттестация (2 модуль)
    0.15 * Домашнее задание + 0.25 * Промежуточная аттестация (1 модуль) + 0.6 * Экзамен 2
Список литературы

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

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

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

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

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