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

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

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

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

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

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

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

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

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

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

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

Аннотация

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

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

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

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

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

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

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

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

• Домашнее задание
• Коллоквиум
• Самостоятельная работа
• Итоговый экзамен

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

• 2025/2026 2nd module
  Аттестация после второго модуля. Оценка 2 модуля = 0.275*Домашнее задание + 0.275*Коллоквиум + 0.05*Самостоятельные работы + 0.4*Итоговый экзамен.

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

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

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

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

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

Авторы

• Солдатова Татьяна Владимировна