Бакалавриат 2022/2023

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

Статус: Курс обязательный (Программная инженерия)

Направление: 09.03.04. Программная инженерия

Кто читает: Кафедра прикладной математики и информатики (Нижний Новгород)

Где читается: Факультет информатики, математики и компьютерных наук (Нижний Новгород)

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

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

Охват аудитории: для всех кампусов НИУ ВШЭ

Преподаватели: Мокеев Дмитрий Борисович

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

Кредиты: 10

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

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

Аннотация

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

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

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

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

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

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

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

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

• Контрольная работа 1
  Входят темы: Множества, отношения, функции
• Контрольная работа 2
  Входят темы: комбинаторика, теория графов. Может быть разбита на 2 контрольных работы.
• Контрольная работа 3
  Входят темы: логические функции, схемы из функциональных элементов
• Контрольная работа 4
  Входят темы: кодирование, конечные автоматы (опционально)
• Экзамен
• Экзамен

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

• 2022/2023 учебный год 2 модуль
  0.7 * Экзамен + 0.2 * Контрольная работа 2 + 0.1 * Контрольная работа 1
• 2022/2023 учебный год 4 модуль
  0.15 * Контрольная работа 3 + 0.15 * Контрольная работа 4 + 0.7 * Экзамен

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

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

• Введение в дискретную математику, [курс лекций], 264 с., Ландо, С. К., 2012
• Верещагин, Н. К. Информация, кодирование и предсказание : монография / Н. К. Верещагин, Е. В. Щепин. — Москва : МЦНМО, 2012. — 236 с. — ISBN 978-5-94057-920-5. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/71863 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.

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

• Верещагин, Н. К. Лекции по математической логике и теории алгоритмов : учебное пособие / Н. К. Верещагин, А. Шень. — 3-е изд., стер. — Москва : МЦНМО, [б. г.]. — Часть 1 : Начала теории множеств — 2008. — 128 с. — ISBN 978-5-94057-321-0. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/9306 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.
• Иорданский М.А. - Кодирование комбинаторных объектов - Издательство "Лань" - 2018 - 92с. - 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

Авторы

• Мокеев Дмитрий Борисович