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

2020/2021

Учебный год

RUS

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

5

Кредиты

Кто читает:

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

Статус:

Курс обязательный

Когда читается:

3-й курс, 1, 2 модуль

Преподаватель

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

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

Аннотация

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

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

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

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

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

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

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

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

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

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

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

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

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

• Князьков В.С., Волченская Т.В. - Введение в теорию автоматов - Национальный Открытый Университет "ИНТУИТ" - 2016 - 89с. - ISBN: - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/100715
• Лекции по математической логике и теории алгоритмов. Ч.1: Начала теории множеств, Верещагин, Н. К., 2008

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

• Задачи по теории множеств, математической логике и теории алгоритмов, Лавров, И. А., 2004