Магистратура 2021/2022

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

Лучший по критерию «Новизна полученных знаний»

Статус: Курс обязательный (Интеллектуальный анализ данных)

Направление: 01.04.02. Прикладная математика и информатика

Кто читает: Кафедра прикладной математики и информатики (Нижний Новгород)

Где читается: Факультет информатики, математики и компьютерных наук (Нижний Новгород)

Когда читается: 1-й курс, 1, 2 модуль

Формат изучения: без онлайн-курса

Охват аудитории: для всех кампусов НИУ ВШЭ

Преподаватели: Малышев Дмитрий Сергеевич

Прогр. обучения: Интеллектуальный анализ данных

Язык: русский

Кредиты: 5

Контактные часы: 60

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

Аннотация

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

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

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

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

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

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

• Модели вычислений.
• Анализ алгоритмов.
• Эффективная разрешимость и «труднорешаемость» дискретных задач.
• Структуры данных.
• Алгоритмы и их эффективные реализации.
• Строковые алгоритмы

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

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

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

• 2021/2022 учебный год 1 модуль
  0.7 * Экзамен 1 + 0.3 * Контрольная работа
• 2021/2022 учебный год 2 модуль
  0.3 * Экзамен 2 + 0.2 * Домашнее задание + 0.5 * 2021/2022 учебный год 1 модуль

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

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

• Алгоритмы : построение и анализ, пер. с англ., 3-е изд., 1323 с., Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К., 2018
• Вычислительные машины и труднорешаемые задачи, 416 с., Гэри, М., Джонсон, Д., 2012

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

• Алексеев, В. Е. Графы и алгоритмы : учебное пособие / В. Е. Алексеев, В. А. Таланов. — 2-е изд. — Москва : ИНТУИТ, 2016. — 153 с. — ISBN 5-9556-0066-3. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/100593 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.

Авторы

• Малышев Дмитрий Сергеевич