Дисциплина базовой части профессионального цикла. Данная дисциплина служит основой для профессиональной ориентации студентов при выборе дисциплин из вариативной части Программы. Дисциплина направлена на изучение основных методов современной дискретной математики (теория множеств, теория графов, комбинаторный анализ), ее связей с информатикой, многочисленными приложениями в современной технике, в том числе, бытовой.
Цель освоения дисциплины
Формирование у студентов теоретических знаний и практических навыков по основам теории множеств, теории графов, комбинаторного анализа как основного математического аппарата для построения моделей дискретных структур, освоение методов математического моделирования и анализа таких структур.
Планируемые результаты обучения
Знает основные понятия и факты теории графов, такие, как деревья, циклы, связность в графах, паросочетания, раскраски графов, планарные графы, классические и обобщенные постановки комбинаторных задач, комбинаторный смысл основных операций над производящими функциями.
Знает основные понятия и факты теории графов, такие, как деревья, циклы, связность в графах, паросочетания, раскраски графов, планарные графы, классические и обобщенные постановки комбинаторных задач
Владеет основными концепциями, связанными с понятиями мощности множества, булевой формулы, доказательства.
Свободно формулирует математические свойства объектов на языке теории множеств и строит формальные доказательства простых утверждений в рамках логики высказываний.
Умеет применять методы перечислительной комбинаторики для подсчёта количества объектов в задачах на размещения, сочетания, перестановки (в том числе с повторениями), а также для анализа отображений между конечными множествами, включая использование принципа включения-исключения и формул обращения.
Умеет решать линейные рекуррентные соотношения второго порядка с постоянными коэффициентами (однородные и неоднородные), интерпретировать их решения в контексте комбинаторных последовательностей и обосновывать выбор метода решения на основе структуры характеристического уравнения.
Умеет строить и анализировать вероятностные модели дискретных пространств элементарных исходов, вычислять вероятности сложных событий с использованием формул полной вероятности и Байеса, а также оценивать характеристики случайных величин (математическое ожидание, дисперсию) и применять неравенство Чебышёва для получения вероятностных оценок.
Умеет обосновывать комбинаторные и вероятностные утверждения с помощью строгих рассуждений, включая построение биекций, использование диаграмм Эйлера, анализ урновых схем.
Содержание учебной дисциплины
Раздел 1. Элементарная комбинаторика
Раздел 2. Элементарная теория графов
Раздел 3. Математическая логика
Элементы контроля
Экзамен №2
Письменный экзамен №2 проводится в форме ответов на вопросы экзаменационного билета. На подготовку ответа выделяется 2,5 часа.
Контрольная работа №1
Домашнее задание
Домашнее задание выдается студентам в одном варианте и состоит из 9-10 задач. Каждой задаче присвоен свой балл. Срок выполнения домашнего задания - 2 недели. Форма предоставления обучающимися домашнего задания - представленные в письменном виде решения задач.
Экзамен №1
Письменный экзамен №1 проводится в форме ответов на вопросы экзаменационного билета. На подготовку ответа выделяется 2,5 часа.
Diestel R. Graph Theory. – Springer, 2017. – 428 pp.
Kumar, R., & Pattnaik, P. K. (2018). Graph Theory. Bengaluru: Laxmi Publications Pvt Ltd. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=2228702
Верещагин, Н. К. Лекции по математической логике и теории алгоритмов : учебное пособие / Н. К. Верещагин, А. Шень. — 3-е изд., доп. — Москва : МЦНМО, [б. г.]. — Часть 2 : Языки и исчисления — 2008. — 288 с. — ISBN 978-5-94057-322-7. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/9307 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.
Верещагин, Н. К. Лекции по математической логике и теории алгоритмов : учебное пособие / Н. К. Верещагин, А. Шень. — 3-е изд., стер. — Москва : МЦНМО, [б. г.]. — Часть 1 : Начала теории множеств — 2008. — 128 с. — ISBN 978-5-94057-321-0. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/9306 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.
Верещагин, Н. К. Лекции по математической логике и теории алгоритмов : учебное пособие / Н. К. Верещагин, А. Шень. — 3-е изд., стер. — Москва : МЦНМО, [б. г.]. — Часть 3 : Вычислимые функции — 2008. — 192 с. — ISBN 978-5-94057-323-4. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/9308 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.
Верещагин, Н. К. Языки и исчисления : учебное пособие / Н. К. Верещагин, А. Х. Шень. — 2-е изд. — Москва : ИНТУИТ, 2016. — 278 с. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/100547 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.
Гисин, В. Б. Дискретная математика : учебник и практикум для академического бакалавриата / В. Б. Гисин. — Москва : Издательство Юрайт, 2019. — 383 с. — (Высшее образование). — ISBN 978-5-534-00228-7. — Текст : электронный // Образовательная платформа Юрайт [сайт]. — URL: https://urait.ru/bcode/432144 (дата обращения: 28.08.2023).
Гисин, В. Б. Дискретная математика : учебник и практикум для вузов / В. Б. Гисин. — 2-е изд., перераб. и доп. — Москва : Издательство Юрайт, 2023. — 468 с. — (Высшее образование). — ISBN 978-5-534-16763-4. — Текст : электронный // Образовательная платформа Юрайт [сайт]. — URL: https://urait.ru/bcode/531659 (дата обращения: 02.07.2026).
Иванов, Б. Н. Дискретная математика и теория графов : учебное пособие для вузов / Б. Н. Иванов. — Москва : Издательство Юрайт, 2023. — 177 с. — (Высшее образование). — ISBN 978-5-534-14470-3. — Текст : электронный // Образовательная платформа Юрайт [сайт]. — URL: https://urait.ru/bcode/520078 (дата обращения: 02.07.2026).
Успенский, В. А. Вводный курс математической логики / В.А. Успенский, Н.К. Верещагин, В.Е. Плиско. - 2-e изд. - Москва : ФИЗМАТЛИТ, 2007. - 128 с. ISBN 978-5-9221-0278-0, 2000 экз. - Текст : электронный. - URL: https://znanium.com/catalog/product/129565
Рекомендуемая дополнительная литература
Rigo, M. (2016). Advanced graph theory and combinatorics. ISTE-John Wiley & Sons. https://doi.org/10.1002/9781119008989
Программа дисциплины
Аннотация
Цель освоения дисциплины
Планируемые результаты обучения
Содержание учебной дисциплины
Элементы контроля
Промежуточная аттестация
Список литературы
Рекомендуемая основная литература
Рекомендуемая дополнительная литература
Авторы