Бакалавриат
2026/2027
Дискретная математика
ID 1135714
Статус:
Курс обязательный (Компьютерные науки и анализ данных)
Где читается:
Факультет компьютерных наук
Когда читается:
1-й курс, 1, 2 модуль
Охват аудитории:
для своего кампуса
Язык:
русский
Кредиты:
6
Контактные часы:
84
Программа дисциплины
Аннотация
Дискретная математика — курс, прививающий студентам азы математической культуры, нужные для последующего изучения как математических дисциплин, так и компьютерных наук. Курс знакомит с такими фундаментальными понятиями как множества, алгебра логики, функции и отображения, булевы функции, отношения и графы. Они являются фундаментом как для изучения математики и для структур данных в программировании. Разделы введение в теорию чисел и мощность множеств готовит студентов к изучению алгебры
Цель освоения дисциплины
- Знакомство с базовыми математическими понятиями.
- Развитие математической культуры (формулировки, изложение доказательств и т.п.).
- Изучение фундаментальных разделов, относящихся к дискретной математике (основы алгебры логики, основы теории множеств, использование кванторов, графы, основы комбинаторики, основы теории чисел).
Планируемые результаты обучения
- Владеть арифметикой остатков (вычетов). Уметь проверять элемент на обратимость, находить обратный элемент, решать линейные диофантовы уравнения от двух переменных с помощью алгоритма Евклида, знать базовые теоремы
- Владеть определениями и математическим аппаратом, связанным с функциями: образы, прообразы, инъекция, сюръекция, биекция
- Знать базовые комбинаторные числа: число перестановок, сочетаний, размещений, сочетаний с повторениями
- Знать базовые свойства бинарных отношений: рефлексивность, симметричность, транзитивность, антисимметричность, антирефлексивность, линейность; отношения эквивалентности, отношения частичного порядка
- Знать основы теории графов
- Знать основы теории множеств, владеть формулами алгебр множеств и логики
- Уметь решать базовые комбинаторные задачи: пользоваться правилами суммы и произведения, формулой включений-исключений
- Уметь строить разложениями в ДНФ и КНФ, проверять на полноту базис. Уметь строить булевы схемы, реализующие арифметические операции, уметь использовать их при решении задач. Уметь оценивать асимптотический размер булевых схем.
Содержание учебной дисциплины
- Алгебра логики
- Комбинаторика
- Множества и логика
- Основы теории чисел
- Двудольные графы, паросочетания и функции
- Ориентированные графы и отношения порядка.
- Теория графов
- Булевы функции
Элементы контроля
- Экзамен
- Домашние задания
- Коллоквиум 1
- Контрольная работа
- Проверочные работы на семинарах
- Коллоквиум 2
Промежуточная аттестация
- 2026/2027 2nd module0.3 * Домашние задания + 0.15 * Экзамен + 0.175 * Коллоквиум 1 + 0.125 * Контрольная работа + 0.125 * Коллоквиум 2 + 0.125 * Проверочные работы на семинарах
Список литературы
Рекомендуемая основная литература
- Discrete Mathematics for Computer Science - Mark A. Fitch - Open Educational Resources: libretexts.org - CCBY4_028 - 2022 - русский - https://ibooks.ru/product/336019 - iBOOKS - 336019
- Иванов, Б. Н. Дискретная математика и теория графов : учебник для вузов / Б. Н. Иванов. — Москва : Издательство Юрайт, 2026. — 177 с. — (Высшее образование). — ISBN 978-5-534-14470-3. — Текст : электронный // Образовательная платформа Юрайт [сайт]. — URL: https://urait.ru/bcode/588754 (дата обращения: 02.07.2026).
- Лекции по математической логике и теории алгоритмов. Часть 1. Начала теории множеств - Верещагин Н.К., Шень А. - Московский центр непрерывного математического образования - 978-5-94057-321-0 - 2008 - русский - https://e.lanbook.com/book/9306 - ЛАНЬ - 9306
- Палий, И. А. Дискретная математика и математическая логика : учебник для вузов / И. А. Палий. — 3-е изд., испр. и доп. — Москва : Издательство Юрайт, 2026. — 370 с. — (Высшее образование). — ISBN 978-5-534-12446-0. — Текст : электронный // Образовательная платформа Юрайт [сайт]. — URL: https://urait.ru/bcode/585753 (дата обращения: 02.07.2026).
Рекомендуемая дополнительная литература
- Дискретная математика: графы, матроиды, алгоритмы - Асанов М. О., Баранский В. А., Расин В. В. - Издательство "Лань" - 978-5-507-51384-0 - 2026 - русский - https://e.lanbook.com/book/511503 - ЛАНЬ - 511503
- Лекции по математической логике и теории алгоритмов. Часть 2. Языки и исчисления - Верещагин Н.К., Шень А. - Московский центр непрерывного математического образования - 978-5-94057-322-7 - 2008 - русский - https://e.lanbook.com/book/9307 - ЛАНЬ - 9307