Бакалавриат
2025/2026
Дискретная математика
ID 1035940
Статус:
Курс по выбору (Прикладная математика и информатика)
Где читается:
Факультет компьютерных наук
Когда читается:
1-й курс, 1-3 модуль
Охват аудитории:
для своего кампуса
Язык:
русский
Кредиты:
6
Контактные часы:
96
Программа дисциплины
Аннотация
Дискретная математика — базовый вводный курс, прививающий студентам азы математической культуры, нужные для последующего изучения как математических дисциплин, так и компьютерных наук. Курс знакомит с такими фундаментальными понятиями как множества, алгебра логики, функции и отображения, булевы функции, отношения и графы. Они являются фундаментом как для изучения математики и для структур данных в программировании. Раздел "мощность множеств" важен для изучения математического анализа.
Цель освоения дисциплины
- Знакомство с базовыми математическими понятиями.
- Развитие математической культуры (культуры доказательств).
- Изучение фундаментальных разделов, относящихся к дискретной математике, необходимых для успешного прохождения последующих курсов.
Планируемые результаты обучения
- Владеть определениями и математическим аппаратом, связанным с функциями: образы, прообразы, инъекция, сюръекция, биекция.
- Знать базовые свойства бинарных отношений: рефлексивность, симметричность, транзитивность, антисимметричность, антирефлексивность, линейность; отношения эквивалентности, отношения частичного порядка
- Знать основы теории графов
- Изучить доказательство нижних оценок для алгоритмов поиска максимума в массиве и сортировки.
- Уметь строить разложения в ДНФ и КНФ, проверять на полноту базис.
- Знание базовых свойств бинарных отношений: рефлексивность, симметричность, транзитивность, антисимметричность, антирефлексивность, линейность; отношения эквивалентности, отношения частичного порядка
- Знать базовые комбинаторные числа: число перестановок, сочетаний, размещений, сочетаний с повторениями.
- Уметь решать базовые комбинаторные задачи: пользоваться правилами суммы и произведения, формулой включений-исключений.
- Знать основы теории графов.
- Уметь различать счётные множества и множества мощности континуум. Овладеть диагональным методом на примере теоремы Кантора.
- Знать основы теории множеств, владеть формулами алгебр множеств и логики.
- Выработать базовую математическую культуру (культуру доказательств).
- Знать базовые свойства бинарных отношений: рефлексивность, симметричность, транзитивность, антисимметричность, антирефлексивность, линейность; отношения эквивалентности, отношения частичного порядка.
Содержание учебной дисциплины
- Множества и логика.
- Комбинаторика.
- Алгебра логики.
- Математические определения, утверждения и доказательства.
- Функции.
- Графы.
- Двудольные графы, паросочетания и функции.
- Ориентированные графы и отношения порядка.
- Бинарные отношения. Отношения эквивалентности.
- Булевы функции.
- Мощность множеств.
- Разрешающие деревья и нижние оценки.
Элементы контроля
- Коллоквиум-2
- Итоговый экзамен
- Домашнее задание 1
- Коллоквиум — 1
- Промежуточный экзамен
- Домашнее задание 2
Промежуточная аттестация
- 2025/2026 2nd module0.25 * Домашнее задание 1 + 0.45 * Промежуточный экзамен + 0.3 * Коллоквиум — 1
- 2025/2026 3rd moduleОценка 3 модуля = 0.2*Оценка 2 модуля + 0.2* Домашнее задание 2 + 0.24 * Коллоквиум2 + 0.36*Итоговый экзамен
Список литературы
Рекомендуемая основная литература
- Lovász, L., Pelikán, J., & Vsztergombi, K. (2003). Discrete Mathematics : Elementary and Beyond. New York: Springer. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=108108
- Дискретная математика. Углубленный курс - Соболева Т.С., Чечкин А.В. - КУРС - 2020 - https://znanium.com/catalog/product/1015049 - 499991 - ZNANIUM
- Лекции по дискретной математике - Вялый М. Н., Подольский В. В., Рубцов А. А., Шварц Д. А., Шень А. - Издательский дом Высшей школы экономики - 978-5-7598-2212-7 - 2021 - русский - https://e.lanbook.com/book/199883 - ЛАНЬ - 199883
- Лекции по математической логике и теории алгоритмов. Часть 1. Начала теории множеств - Верещагин Н.К., Шень А. - Московский центр непрерывного математического образования - 978-5-94057-321-0 - 2008 - русский - https://e.lanbook.com/book/9306 - ЛАНЬ - 9306
Рекомендуемая дополнительная литература
- Лекции по математической логике и теории алгоритмов. Часть 2. Языки и исчисления - Верещагин Н.К., Шень А. - Московский центр непрерывного математического образования - 978-5-94057-322-7 - 2008 - русский - https://e.lanbook.com/book/9307 - ЛАНЬ - 9307