• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

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

2019/2020
Учебный год
RUS
Обучение ведется на русском языке
4
Кредиты
Статус:
Курс обязательный
Когда читается:
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 - ISBN: - Текст электронный // ЭБС Лань - URL: https://e.lanbook.com/book/100715
  • Начала теории множеств : лекции по математической логике и теории алгоритмов, Верещагин Н. К., Шень А., 2008

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

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