Специалитет 2021/2022

Дискретная математика

Статус: Курс обязательный (Компьютерная безопасность)

Кто читает: Департамент прикладной математики

Где читается: Московский институт электроники и математики им. А.Н. Тихонова

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

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

Охват аудитории: для своего кампуса

Преподаватели: Славнов Сергей Андреевич

Специальность: 10.05.01. Компьютерная безопасность

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

Кредиты: 5

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

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

Аннотация

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

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

• Ознакомление студентов с основными методами и задачами комбинаторики и теории автоматов
• Ознакомление студентов с основными методами и задачами комбинаторики и теории автоматов

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

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

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

• Элементарные комбинаторные подсчеты
• Автоматы с магазинной памятью и контекстно-свободные языки
• Метод производящих функций в комбинаторике
• Вычислимость
• Разбиения и диаграммы Юнга
• Эффективная вычислимость, сложность, классы P и NP
• Рекуррентные соотношения
• Экспоненциальные производящие функции в комбинаторике
• Конечные автоматы

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

• Контрольные работы
• Итоговая аттестация
• Контрольные работы
• Итоговая аттестация
• Котрольные работы
• Итоговая аттестация
• Котрольные работы
• Итоговая аттестация

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

• 2020/2021 учебный год 4 модуль
  0.5 * Итоговая аттестация + 0.5 * Контрольные работы
• 2021/2022 учебный год 2 модуль
  0.5 * Котрольные работы + 0.5 * Итоговая аттестация

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

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

• Дискретная математика и комбинаторика, Андерсон, Дж. А., 2003
• Князьков, В. С. Введение в теорию автоматов : учебное пособие / В. С. Князьков, Т. В. Волченская. — 2-е изд. — Москва : ИНТУИТ, 2016. — 89 с. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/100715 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.
• Лекции по математической логике и теории алгоритмов. Ч.1: Начала теории множеств, Верещагин, Н. К., 2008

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

• Задачи по теории множеств, математической логике и теории алгоритмов, Лавров, И. А., 2004
• Лекции о производящих функциях, Ландо, С. К., 2007

Авторы

• Славнов Сергей Андреевич