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

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

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

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

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

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

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

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

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

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

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

Кредиты: 10

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

Дополнительные материалы в LMS Задать вопрос

Аннотация

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

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

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

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

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

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

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

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

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

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

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

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

Авторы

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

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