• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Discrete Mathematics

2019/2020
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


Sirotkin, Dmitry

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

Аннотация

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

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

  • овладение основами дискретной математики
  • приобретение навыков и их использования при дальнейшем изучении профильных дисциплин
  • приобретение навыков и их использования при проведении прикладных математических исследований
Планируемые результаты обучения

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

  • формулировать основные понятия теории множеств
  • применять свойства множественных операций при преобразовании выражений алгебры множеств
  • доказывать тождества алгебры множеств
  • формулировать и определять основные свойства бинарных отношений
  • применять теорему о факторизации к решению задач
  • определять основные свойства упорядоченных множеств
  • определять основные свойства отображений
  • доказывать счётность множества
  • воспроизводить основные комбинаторные формулы
  • решать задачи подсчёта числа случаев, вариантов, элементов, функций и т.п.
  • решать линейные рекуррентные соотношения 1 и 2 порядка
  • формулировать основные понятия теории графов
  • проверять изоморфизм графов
  • определять метрические характеристики графов
  • описывать основные свойства деревьев
  • строить плоскую укладку планарного графа
  • применять теоремы Понтрягина-Куратовского и Вагнера для доказательства непланарности графа
  • выявлять двудольные графы
  • находить эйлеров цикл в графах или доказывать, что его не существует
  • формулировать основные понятия алгебры логики
  • решать задачи преобразования и упрощения логических формул
  • сравнивать логические функции
  • выявлять свойства логических функций
  • доказывать полноту системы логических функций
  • строить СДНФ, СКНФ, полиномы Жегалкина для логических функций
  • решать задачи минимизации логических формул
  • анализировать и строить схемы функциональных элементов.
  • формулировать основные понятия теории кодирования
  • определять однозначную декодируемость алфавитного кода
  • применять алгоритмы экономного алфавитного кодирования Хаффмана, Фано, Шеннона
  • оценивать эффективность алгоритмов экономного кодирования
  • определять расстояние Хэмминга
  • применять алгоритм кодирования Хэмминга
  • формулировать основные понятия теории формальных языков
  • строить и анализировать конечные автоматы
  • строить и анализировать регулярные выражения
  • строить и анализировать схемы функциональных элементов с задержкой
  • сравнивать конечные автоматы, регулярные выражения и схемы с задержкой
Содержание учебной дисциплины

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

  • Бинарные отношения.
    Основные понятия теории бинарных отношений, функциональные отношения.
  • Кодирование
    Основные понятия и алгоритмы экономного кодирования, кодирования с защитой от сбоев.
  • Комбинаторика
    Основные комбинаторные объекты и формулы.
  • Конечные автоматы и регулярные языки
    Основы теории конечных автоматов, регулярные выражения.
  • Множества
    Основы теории множеств
  • Теория графов
  • Алгебра логики. Схемы из функциональных элементов.
    Алгебра логики, основы теории логических схем.
Элементы контроля

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

  • неблокирующий Активность на семинарах
  • блокирует часть оценки/расчета Домашние контрольные работы
  • блокирующий Экзаменационный тест открытого типа
    Экзамен проводится в форме электронного тестирования с использованием асинхронного прокторинга. Экзамен проводится на платформе Moodle (https://et.hse.ru/), прокторинг на платформе Экзамус (https://hse.student.examus.net). К экзамену необходимо подключиться за 15 минут. На платформе Экзамус доступно тестирование системы. Компьютер студента должен удовлетворять следующим требованиям: https://elearning.hse.ru/data/2020/05/07/1544135594/Технические%20требования%20к%20ПК%20студента.pdf) Для участия в экзамене студент обязан: заранее зайти на платформу прокторинга, провести тест системы, включить камеру и микрофон, подтвердить личность. Во время экзамена студентам запрещено: общаться (в социальных сетях, с людьми в комнате), списывать, открывать в браузере сторонние сайты, за исключением pdf.io, ilovepdf.com, пользоваться техникой за исключением калькулятора и сканера. Кратковременным нарушением связи во время экзамена считается прерывание связи до 5 минут. Долговременным нарушением связи во время экзамена считается прерывание связи 5 минут и более. При долговременном нарушении связи или при многократных кратковременных нарушениях связи (2 и более в течении 20 минут, 4 и более в течении экзамена) студент не может продолжить участие в экзамене. В течение 10 минут после завершения теста студент имеет право прислать фото или сканы черновиков в форму по ссылке https://docs.google.com/forms/d/1wwtOGcpuybXbhwkSQcTiDs-dvyZkUEAP4yg5gTko1O8/prefill для возможной апелляции и повышения оценки. Процедура пересдачи аналогична процедуре сдачи.
Промежуточная аттестация

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

  • Промежуточная аттестация (2 модуль)
    0.3 * Домашние контрольные работы + 0.7 * Экзаменационный тест открытого типа
  • Промежуточная аттестация (4 модуль)
    0.2 * Домашние контрольные работы + 0.3 * Промежуточная аттестация (2 модуль) + 0.5 * Экзаменационный тест открытого типа
Список литературы

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

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

  • - Верещагин Н.К., Щепин Е.В. — Информация, кодирование и предсказание - Московский центр непрерывного математического образования - 2012 - ISBN: 978-5-94057-920-5 - Текст электронный // ЭБС Лань - URL: https://e.lanbook.com/book/71863
  • Введение в дискретную математику, [курс лекций], 264 с., Ландо, С. К., 2012
  • Хаггарти Р. - Дискретная математика для программистов - Издательство "Техносфера" - 2012 - ISBN: 978-5-94836-303-5 - Текст электронный // ЭБС Лань - URL: https://e.lanbook.com/book/73011

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

  • - Верещагин Н.К., Шень А. — Лекции по математической логике и теории алгоритмов. Часть 1. Начала теории множеств - Московский центр непрерывного математического образования - 2008 - ISBN: 978-5-94057-321-0 - Текст электронный // ЭБС Лань - URL: https://e.lanbook.com/book/9306
  • - Иорданский М.А. — Кодирование комбинаторных объектов - Издательство "Лань" - 2018 - ISBN: 978-5-8114-2787-1 - Текст электронный // ЭБС Лань - URL: https://e.lanbook.com/book/102599
  • Лекции по дискретной математике : учеб. пособие / В.Б. Алексеев. — М. : ИНФРА-М, 2018. — 90 с. — (Высшее образование: Бакалавриат). - Режим доступа: http://znanium.com/catalog/product/952158
  • Лекции по дискретной математике: Учебное пособие / В.Б. Алексеев. - М.: НИЦ Инфра-М, 2012. - 90 с.: 60x88 1/16. - (Высшее образование: Бакалавриат). (обложка) ISBN 978-5-16-005559-6 - Режим доступа: http://znanium.com/catalog/product/278874