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

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

Лучший по критерию «Полезность курса для расширения кругозора и разностороннего развития»

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

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

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

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

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

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

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

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

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

Кредиты: 5

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

Полная версия программы учебной дисциплины

Аннотация

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

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

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

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

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

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

Автоматы с магазинной памятью и контекстно-свободные языки
1. Автоматы с магазинной памятью. Определение. Детерминированные и недетерминированные МПА. 2. Контекстно-свободные грамматики и языки. Дерево синтаксического разбора. Лемма о накачивании. Иерархия Хомского.
Вычислимость
1. Вычислимость по Тьюрингу. Тезис Тьюринга. Проблема остановки. Теорема Райса. 2. Примитивно-рекурсивные функции. Непримитивно-рекурсивные вычислимые функции. Функция Аккермана. Оператор минимизации. Общая рекурсия.
Эффективная вычислимость, сложность, классы P и NP
1. Эффективная вычислимость, класс P. Недетерминированные алгоритмы, класс FNP, труднорешаемые задачи. Примеры: задача об укладке рюкзака, задача целочисленного линейного программирования задача коммивояжера, задача о клике, задача о вершинном покрытии. Задача о разложении числа на простые множители, задача о дискретном логарифме. 2. Класс NP, разные определения. Сводимость и NP-полнота. Задача SAT. Примеры NP-полных задач: 3-SAT, задача о клике, задача о вершинном покрытии, задача об укладке рюкзака и задача целочисленного линейного программирования в варианте распознавания, задача коммивояжера. Сложность задачи о простоте числа (без доказательства).

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

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

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

Промежуточная аттестация (2 модуль)
0.5 * Итоговая аттестация + 0.5 * Котрольные работы

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