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

Бакалавриат 2025/2026

ID 876685

Статус: Курс обязательный (Прикладной анализ данных и искусственный интеллект)

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

Охват аудитории: для своего кампуса

Преподаватели: Жуков Яков Валерьевич, Михайлов Михаил Дмитриевич, Сорокин Константин Сергеевич, Храбров Александр Игоревич, Цишевич Павел Дмитриевич

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

Кредиты: 4

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

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

Аннотация

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

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

Формирование у студентов теоретических знаний и практических навыков по основам теории множеств, теории графов, комбинаторного анализа как основного математического аппарата для построения моделей дискретных структур, освоение методов математического моделирования и анализа таких структур.

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

Знает основные математические модели, применяющие теорию графов. Умеет модифицировать основные математические модели, основанные на теории графов, в соответствии со спецификой задачи.
Знает основные методы работы с графами и дискретными структурами. Умеет строить математические модели практических задач на основе графов.
Использует методы работы с графами для решения практических задач профессиональной области. Умеет модифицировать основные математические модели, основанные на теории графов, в соответствии со спецификой задачи
Знает основные понятия и факты теории графов, такие, как деревья, циклы, связность в графах, паросочетания, раскраски графов, планарные графы, классические и обобщенные постановки комбинаторных задач, комбинаторный смысл основных операций над производящими функциями.
Умеет находить кратчайшие и минимальные пути в графе, медианы и центры графа, остовные деревья, эйлеровы и гамильтоновы циклы, совершенные или максимальные паросочетания, оптимальную раскраску графа, решать линейные рекуррентные соотношения как с помощью производящих функций, так и без них, перечислять основные дискретные объекты (графы, деревья, плоские деревья).
Знает основные понятия и факты теории графов, такие, как деревья, циклы, связность в графах, паросочетания, раскраски графов, планарные графы, классические и обобщенные постановки комбинаторных задач
Имеет навыки использования методов решения основных комбинаторных задач с помощью производящих функций. Знает комбинаторный смысл основных операций над производящими функциями. Умеет применять производящие функции для решения рекуррентных соотношений.
Владеет основными концепциями, связанными с понятиями мощности множества, булевой формулы, доказательства. Свободно формулирует математические свойства объектов на языке теории множеств и строит формальные доказательства простых утверждений в рамках логики высказываний.
Знает постановки задач помехоустойчивого кодирования, а так же базовыми ограничениями, которые следуют из этих постановок. Умеет работать с конечными полями и применять их для построения кодов Рида-Соломона и БЧХ. Умеет реализовывать основные алгоритмы кодирования и декодирования.
Умеет применять методы перечислительной комбинаторики для подсчёта количества объектов в задачах на размещения, сочетания, перестановки (в том числе с повторениями), а также для анализа отображений между конечными множествами, включая использование принципа включения-исключения и формул обращения.
Умеет решать линейные рекуррентные соотношения второго порядка с постоянными коэффициентами (однородные и неоднородные), интерпретировать их решения в контексте комбинаторных последовательностей и обосновывать выбор метода решения на основе структуры характеристического уравнения.
Умеет строить и анализировать вероятностные модели дискретных пространств элементарных исходов, вычислять вероятности сложных событий с использованием формул полной вероятности и Байеса, а также оценивать характеристики случайных величин (математическое ожидание, дисперсию) и применять неравенство Чебышёва для получения вероятностных оценок.
Умеет обосновывать комбинаторные и вероятностные утверждения с помощью строгих рассуждений, включая построение биекций, использование диаграмм Эйлера, анализ урновых схем.

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

Раздел 1. Элементарная комбинаторика
Раздел 2. Элементарная теория графов
Раздел 3. Математическая логика
Раздел 4. Производящие функции
Раздет 5. Конечные поля и коды
Раздел 6. Остовные деревья, циклы и разрезы. Связность в графах
Раздел 7. Паросочетания в графах. Раскраска графов. Планарные графы.

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

Контрольная работа
Контрольная работа проводится в письменной форме. Каждый студент получает список из 5 задач. Для получения положительной оценки он должен решить не менее трех из них. На проведение контрольной работы отводится 1,5 часа.
Экзамен №2
Письменный экзамен №2 проводится в форме ответов на вопросы экзаменационного билета. На подготовку ответа выделяется 2,5 часа.
Экзамен №1
Письменный экзамен №1 проводится в форме ответов на вопросы экзаменационного билета. На подготовку ответа выделяется 2,5 часа.
Экзамен №3
Письменный экзамен №3 проводится в форме ответов на вопросы экзаменационного билета. На подготовку ответа выделяется 2,5 часа.
Экзамен №4
Письменный экзамен №4 проводится в форме ответов на вопросы экзаменационного билета. На подготовку ответа выделяется 2,5 часа.
Домашнее задание
Домашнее задание выдается студентам в одном варианте и состоит из 9-10 задач. Каждой задаче присвоен свой балл. Срок выполнения домашнего задания - 2 недели. Форма предоставления обучающимися домашнего задания - представленные в письменном виде решения задач.
Коллоквиум
Контрольная работа
Контрольная работа
Контрольная работа

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

2024/2025 1st module
0.35 * Домашнее задание + 0.65 * Контрольная работа
2024/2025 2nd module
0.65 * Экзамен №1 + 0.35 * Домашнее задание
2024/2025 4th module
0.17 * Домашнее задание + 0.66 * Экзамен №2
2025/2026 1st module
0.65 * Контрольная работа + 0.35 * Домашнее задание
2025/2026 2nd module
0.35 * Домашнее задание + 0.65 * Экзамен №3
2025/2026 4th module
Оценка за третий модуль вычисляется по формуле: 0,25*Домашние задания+0,25*Контрольная работа+0,5*Коллоквиум Оценка за четвертый модуль вычисляется по формуле: 0,25*Домашние задания+0,25*Контрольная работа+0,5*Экзамен Итоговая оценка — среднее арифметическое оценок за модули.

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

Авторы

Оленчук Ольга Геннадьевна
Храбров Александр Игоревич
Гориховский Вячеслав Игоревич

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