Discrete Mathematics

2020/2021

Academic Year

RUS

Instruction in Russian

8

ECTS credits

Delivered at:

Department of Applied Mathematics and Informatics (Faculty of Informatics, Mathematics, and Computer Science (HSE Nizhny Novgorod))

Course type:

Compulsory course

When:

1 year, 1-4 module

Instructors

Gribanov, Dmitry

Malyshev, Dmitriy

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

Аннотация

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

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

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

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

• Знает основные понятия и теоремы. Умеет решать задачи
• Знает основные методы дискретной математики
• Умеет применять на практике методы дискретной математики
• Владеет навыками решения математических задач, возникающих в некоторых прикладных областях

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

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

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

• Экзамен 1
• Экзамен 2
  Экзамен проводится в письменной форме с использованием прокторинга, прокторинг на платформе Экзамус (https://hse.student.examus.net) и на платформе LMS (https://lms.hse.ru). К экзамену необходимо подключиться за 15 минут до начала экзамена. Компьютер студента должен удовлетворять требованиям: поддержка LMS и https://elearning.hse.ru/data/2020/05/07/1544135594/Технические%20требования%20к%20ПК%20студента.pdf. Для участия в экзамене студент обязан: заранее зайти на платформу прокторинга, провести тест системы, включить камеру и микрофон, подтвердить личность, поставить на аватар свою фотографию, явиться на экзамен согласно точному расписанию. Во время экзамена студентам запрещено пользоваться конспектами и подсказками. Кратковременным нарушением связи во время экзамена считается нарушение связи менее 5 минут. Долговременным нарушением связи во время экзамена считается нарушение 5 минут и более. При долговременном нарушении связи студент не может продолжить участие в экзамене. Процедура пересдачи аналогична процедуре сдачи.
• Устный опрос
• Контрольная работа 1
• Контрольная работа 2
• Экзамен 1
  Экзамен проводится в форме часового теста в системе лмс. Варианты экзамена высылаются за 5-10 минут до его начала. Экзамен проводится без прокторинга. Процедура пересдачи аналогична процедуре сдачи.
• Экзамен 2
  Экзамен проводится в письменной форме с использованием прокторинга, прокторинг на платформе Экзамус (https://hse.student.examus.net) и на платформе LMS (https://lms.hse.ru). К экзамену необходимо подключиться за 15 минут до начала экзамена. Компьютер студента должен удовлетворять требованиям: поддержка LMS и https://elearning.hse.ru/data/2020/05/07/1544135594/Технические%20требования%20к%20ПК%20студента.pdf. Для участия в экзамене студент обязан: заранее зайти на платформу прокторинга, провести тест системы, включить камеру и микрофон, подтвердить личность, поставить на аватар свою фотографию, явиться на экзамен согласно точному расписанию. Во время экзамена студентам запрещено пользоваться конспектами и подсказками. Кратковременным нарушением связи во время экзамена считается нарушение связи менее 5 минут. Долговременным нарушением связи во время экзамена считается нарушение 5 минут и более. При долговременном нарушении связи студент не может продолжить участие в экзамене. Процедура пересдачи аналогична процедуре сдачи.
• Контрольная работа 1

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

• Промежуточная аттестация (2 модуль)
  0.33 * Контрольная работа 1 + 0.67 * Экзамен 1
• Промежуточная аттестация (4 модуль)
  0.165 * Контрольная работа 2 + 0.5 * Промежуточная аттестация (2 модуль) + 0.335 * Экзамен 2

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

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

• Введение в дискретную математику, [курс лекций], 264 с., Ландо, С. К., 2012
• Дискретная математика : учеб. пособие / С.А. Канцедал. — М: ФОРУМ : ИНФРА-М, 2017. — 224 с. — (Профессиональное образование). ISBN 978-5-8199-0304-9 - Режим доступа: http://znanium.com/catalog/product/614950

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

• Элементы дискретной математики, учебник, 280 с., Судоплатов, С. В., Овчинникова, Е. В., 2002