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





Дискретная математика
Статус:
Курс обязательный (Прикладная математика и информатика)
Направление:
01.03.02. Прикладная математика и информатика
Кто читает:
Департамент информатики
Когда читается:
1-й курс, 1, 2, 4 модуль
Формат изучения:
без онлайн-курса
Охват аудитории:
для всех кампусов НИУ ВШЭ
Язык:
русский
Кредиты:
4
Программа дисциплины
Аннотация
Дисциплина базовой части профессионального цикла. Данная дисциплина служит основой для профессиональной ориентации студентов при выборе дисциплин из вариативной части Программы. Дисциплина направлена на изучение основных методов современной дискретной математики (теория множеств, теория графов, комбинаторный анализ), ее связей с информатикой, многочисленными приложениями в современной технике, в том числе, бытовой.
Цель освоения дисциплины
- Формирование у студентов теоретических знаний и практических навыков по основам теории множеств, теории графов, комбинаторного анализа как основного математического аппарата для построения моделей дискретных структур, освоение методов математического моделирования и анализа таких структур.
Планируемые результаты обучения
- Знает основные математические модели, применяющие теорию графов. Умеет модифицировать основные математические модели, основанные на теории графов, в соответствии со спецификой задачи.
- Знает основные методы работы с графами и дискретными структурами. Умеет строить математические модели практических задач на основе графов.
- Использует методы работы с графами для решения практических задач профессиональной области. Умеет модифицировать основные математические модели, основанные на теории графов, в соответствии со спецификой задачи
- Знает основные понятия и факты теории графов, такие, как деревья, циклы, связность в графах, паросочетания, раскраски графов, планарные графы, классические и обобщенные постановки комбинаторных задач, комбинаторный смысл основных операций над производящими функциями.
- Умеет находить кратчайшие и минимальные пути в графе, медианы и центры графа, остовные деревья, эйлеровы и гамильтоновы циклы, совершенные или максимальные паросочетания, оптимальную раскраску графа, решать линейные рекуррентные соотношения как с помощью производящих функций, так и без них, перечислять основные дискретные объекты (графы, деревья, плоские деревья).
- Имеет навыки использования методов решения основных комбинаторных задач с помощью производящих функций, использования основных алгоритмов работы с графами.
- Знает основные понятия и факты теории графов, такие, как деревья, циклы, связность в графах, паросочетания, раскраски графов, планарные графы, классические и обобщенные постановки комбинаторных задач
- Имеет навыки использования методов решения основных комбинаторных задач с помощью производящих функций. Знает комбинаторный смысл основных операций над производящими функциями. Умеет применять производящие функции для решения рекуррентных соотношений.
- Владеет основными концепциями, связанными с понятиями мощности множества, булевой формулы, доказательства. Свободно формулирует математические свойства объектов на языке теории множеств и строит формальные доказательства простых утверждений в рамках логики высказываний.
- Знает постановки задач помехоустойчивого кодирования, а так же базовыми ограничениями, которые следуют из этих постановок. Умеет работать с конечными полями и применять их для построения кодов Рида-Соломона и БЧХ. Умеет реализовывать основные алгоритмы кодирования и декодирования.
Содержание учебной дисциплины
- Раздел 1. Элементарная комбинаторика
- Раздел 2. Элементарная теория графов
- Раздел 3. Математическая логика
- Раздел 4. Производящие функции
- Раздет 5. Конечные поля и коды
- Раздел 6. Остовные деревья, циклы и разрезы. Связность в графах
- Раздел 7. Паросочетания в графах. Раскраска графов. Планарные графы.
Элементы контроля
- Экзамен №3Письменный экзамен №3 проводится в форме ответов на вопросы экзаменационного билета. На подготовку ответа выделяется 2,5 часа.
- Экзамен №2Письменный экзамен №2 проводится в форме ответов на вопросы экзаменационного билета. На подготовку ответа выделяется 2,5 часа.
- Экзамен №4Письменный экзамен №4 проводится в форме ответов на вопросы экзаменационного билета. На подготовку ответа выделяется 2,5 часа.
- Контрольная работа №1Контрольная работа проводится в письменной форме. Каждый студент получает список из 5 задач. Для получения положительной оценки он должен решить не менее трех из них. На проведение контрольной работы отводится 1,5 часа.
- Экзамен №1Письменный экзамен №1 проводится в форме ответов на вопросы экзаменационного билета. На подготовку ответа выделяется 2,5 часа.
- Домашнее заданиеДомашнее задание выдается студентам в одном варианте и состоит из 9-10 задач. Каждой задаче присвоен свой балл. Срок выполнения домашнего задания - 2 недели. Форма предоставления обучающимися домашнего задания - представленные в письменном виде решения задач.
- Коллоквиум №1
- Контрольная работа
- Контрольная работа №2
Промежуточная аттестация
- 2024/2025 1st module0.4 * Домашнее задание + 0.3 * Коллоквиум №1 + 0.3 * Контрольная работа №1
- 2024/2025 2nd module0.4 * Домашнее задание + 0.3 * Контрольная работа №2 + 0.3 * Экзамен №1
- 2024/2025 4th module0.4 * Домашнее задание + 0.6 * Экзамен №2
- 2025/2026 2nd moduleМодуль1 = 0,5*к/р + 0,25*д/з1 + 0,25*д/з2 Модуль2 = 0,4*Экзамен + 0,6*Практика Итог за семестр = 0,5*(Модуль1+Модуль2)
- 2025/2026 4th module0.5 * Домашнее задание + 0.5 * Экзамен №4
Список литературы
Рекомендуемая основная литература
- 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
- Richard P. Stanley. (2013). Topics in algebraic combinatorics. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsbas&AN=edsbas.21998FFA
- Rigo, M. (2016). Advanced graph theory and combinatorics. ISTE-John Wiley & Sons. https://doi.org/10.1002/9781119008989
- Ronald L. Graham, Donald E. Knuth, & Oren Patashnik. (1994). Concrete Mathematics : A Foundation for Computer Science. [N.p.]: Addison-Wesley Professional. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=1601594
- Верещагин, Н. К. Лекции по математической логике и теории алгоритмов : учебное пособие / Н. К. Верещагин, А. Шень. — 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 (дата обращения: 27.08.2024).
- Иванов, Б. Н. Дискретная математика и теория графов : учебное пособие для вузов / Б. Н. Иванов. — Москва : Издательство Юрайт, 2023. — 177 с. — (Высшее образование). — ISBN 978-5-534-14470-3. — Текст : электронный // Образовательная платформа Юрайт [сайт]. — URL: https://urait.ru/bcode/520078 (дата обращения: 27.08.2024).
- Ландо, С. К. Введение в дискретную математику : учебное пособие / С. К. Ландо. — Москва : МЦНМО, 2012. — 264 с. — ISBN 978-5-4439-2019-1. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/56405 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.
- Ландо, С. К. Лекции о производящих функциях : учебное пособие / С. К. Ландо. — 3-е изд., испр. — Москва : МЦНМО, 2007. — 144 с. — ISBN 978-5-94057-042-4. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/9364 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.
- Теория и практика кодов, контролирующих ошибки, Блейхут, Р., 1986
- Теория кодов, исправляющих ошибки, Мак-Вильямс, Ф. Дж., 1979
- Успенский, В. А. Вводный курс математической логики / В.А. Успенский, Н.К. Верещагин, В.Е. Плиско. - 2-e изд. - Москва : ФИЗМАТЛИТ, 2007. - 128 с. ISBN 978-5-9221-0278-0, 2000 экз. - Текст : электронный. - URL: https://znanium.com/catalog/product/129565