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

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

ID 1226649

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

Кто читает: Департамент информатики

Где читается: Школа информатики, физики и технологий

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

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

Преподаватели: Имамутдинова Лилия Рафаильевна, Цишевич Павел Дмитриевич

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

Кредиты: 7

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

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

Аннотация

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

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

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

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

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

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

Раздел 1. Элементарная комбинаторика
Раздел 2. Элементарная теория графов
Раздел 3. Теория графов для ПИКИ
Раздел 4. Математическая логика для ПИКИ

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

Экзамен №1
Домашнее задание
Домашнее задание является текущей формой контроля самостоятельной работы студентов.
Экзамен №2
Коллоквиум
Контрольная работа №1
Контрольная работа №2
Контрольная работа №3

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

2026/2027 1st module
0.2 * Домашнее задание + 0.3 * Контрольная работа №1 + 0.5 * Экзамен №1
2026/2027 3rd module
0.1 * Домашнее задание + 0.25 * Экзамен №2 + 0.15 * Контрольная работа №2 + 0.15 * Контрольная работа №3 + 0.25 * Коллоквиум

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

Авторы

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

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