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

Статус:: Курс обязательный

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

Преподаватели

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

Сироткин Дмитрий Валерьевич

Полная версия программы учебной дисциплины

Аннотация

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

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

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

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

формулировать основные понятия теории множеств
применять свойства множественных операций при преобразовании выражений алгебры множеств
доказывать тождества алгебры множеств
формулировать и определять основные свойства бинарных отношений
применять теорему о факторизации к решению задач
определять основные свойства упорядоченных множеств
определять основные свойства отображений
доказывать счётность множества
воспроизводить основные комбинаторные формулы
решать задачи подсчёта числа случаев, вариантов, элементов, функций и т.п.
решать линейные рекуррентные соотношения 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 * Экзаменационный тест открытого типа

Бакалаврская программа «Программная инженерия»

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

Преподаватели

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

Аннотация

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

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

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

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

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

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

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

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