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

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

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

Кто читает: Департамент больших данных и информационного поиска

Где читается: Факультет компьютерных наук

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

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

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

Кредиты: 6

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

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

Аннотация

Дискретная математика — базовый вводный курс, прививающий студентам азы математической культуры, нужные для последующего изучения других математических дисциплин. Курс знакомит с такими фундаментальными понятиями как множества, алгебра логики, функции и отображения, отношения и графы. Эти понятия являются фундаментальными в изучении математики и её приложений.

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

• Знать базовые комбинаторные числа: число перестановок, сочетаний, размещений, сочетаний с повторениями.
• Знать основы теории графов.
• Знать основы теории множеств, владеть формулами алгебр множеств и логики.
• Знать базовые свойства бинарных отношений: рефлексивность, симметричность, транзитивность, антисимметричность, антирефлексивность, линейность; отношения эквивалентности, отношения частичного порядка.

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

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

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

• Способы доказательств, булевы связки, высказывания, тавтологии. Множества, операции, связь с булевыми связками
• Методы математических доказательств: метод перебора, доказательство от противного.
• Натуральные числа и конечные множества.
• Формальное определение функций.
• Подсчеты слов и функций.
• Монотонные пути.
• Мультиномиальные коэффициенты. Сочетания с повторениями.
• Формула включений и исключений. Симметрия в подсчетах: примеры.
• Бинарные отношения, простые неориентированные графы. Отношения эквивалентности. Связность. Компоненты связности.
• Отношения эквивалентности. Графы: ключевые определения.
• Связность и сильная связность. Эйлеровы графы.
• Деревья. Остовные деревья в графе.
• Остовные деревья специального вида
• Планарные графы

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

• Коллоквиум
• Итоговый экзамен
  Экзамен проводится в письменной форме. Письменный экзамен служит для проверки умения творчески использовать полученные знания при решении новых для студента задач. Задания в итоговом письменном экзамене возможны по всем темам, которые изучались в первых двух модулях.
• Контрольная работа
  На контрольной работе будут выданы задачи, выдаваемые ранее в качестве домашних заданий и не вошедшие в оценку за домашние задания.
• Самостоятельные работы
  Проводятся в письменном виде на лекциях или семинарах по материалам последней лекции. Предполагается 5-7 самостоятельных работ в семестре. Длительность одной самостоятельной работы — не более 10 минут.
• Домашнее задание

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

• 2026/2027 2nd module
  0.4 * Итоговый экзамен + 0.1 * Домашнее задание + 0.275 * Коллоквиум + 0.05 * Самостоятельные работы + 0.175 * Контрольная работа
• 2026/2027 4th module
  0.4 * Итоговый экзамен + 0.275 * Коллоквиум + 0.175 * Контрольная работа + 0.05 * Самостоятельные работы + 0.1 * Домашнее задание

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

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

• Алгебра и теория чисел. Сборник задач для математических школ - Алфутова Н.Б., Устинов А.В. - Московский центр непрерывного математического образования - 978-5-94057-550-4 - 2009 - русский - https://e.lanbook.com/book/9279 - ЛАНЬ - 9279
• Введение в математическую логику, Мендельсон, Э., 1984
• Вероятность: примеры и задачи - Шень А. - Московский центр непрерывного математического образования - 978-5-94057-284-8 - 2008 - русский - https://e.lanbook.com/book/9442 - ЛАНЬ - 9442
• Комбинаторика, Виленкин, Н. Я., 2015
• Лекции по дискретной математике / Нац. исслед. ун-т «Высшая школа экономики». — 3-е изд., эл., пересмотр. — (Учебники Высшей школы экономики) - 978-5-7598-2880-8 - Вялый М. Н., Подольский В. В., Рубцов А. А., Шварц Д. А. и др. - 2024 - Москва: ВШЭ - https://ibooks.ru/products/392827 - 392827 - iBOOKS
• Лекции по математической логике и теории алгоритмов. Часть 1. Начала теории множеств - Верещагин Н.К., Шень А. - Московский центр непрерывного математического образования - 978-5-94057-321-0 - 2008 - русский - https://e.lanbook.com/book/9306 - ЛАНЬ - 9306
• Теория графов, Оре, О., 1980

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

• Как же называется эта книга?, Смаллиан, Р., 1981
• Логика для всех: от пиратов до мудрецов - Раскина И.В. - Московский центр непрерывного математического образования - 978-5-4439-3022-0 - 2016 - русский - https://e.lanbook.com/book/80155 - ЛАНЬ - 80155
• Математическая индукция - Шень А. - Московский центр непрерывного математического образования - 978-5-94057-772-0 - 2011 - русский - https://e.lanbook.com/book/9444 - ЛАНЬ - 9444
• Математическая логика : учеб. пособие для вузов, Колмогоров, А. Н., 2005
• Простейшие примеры математических доказательств - Успенский В.А. - Московский центр непрерывного математического образования - 978-5-94057-492-7 - 2009 - русский - https://e.lanbook.com/book/9427 - ЛАНЬ - 9427
• Рассказы о множествах - Виленкин Н.Я. - Московский центр непрерывного математического образования - 978-5-94057-036-3 - 2007 - русский - https://e.lanbook.com/book/9309 - ЛАНЬ - 9309

Авторы

• Оноприенко Анастасия Александровна