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

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

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

Направление: 09.03.04. Программная инженерия

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

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

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

Формат изучения: без онлайн-курса

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

Преподаватели: Зайцева Анна Тиграновна, Соколов Павел Павлович

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

Кредиты: 6

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

Аннотация

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

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

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

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

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

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

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

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

• Домашние задания
• Самостоятельные работы
• Коллоквиум 1
• Лабораторная работа
• Коллоквиум 2
• Экзамен

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

• 2024/2025 2nd module
  0.175 * Домашние задания + 0.125 * Коллоквиум 1 + 0.125 * Коллоквиум 2 + 0.125 * Лабораторная работа + 0.15 * Самостоятельные работы + 0.3 * Экзамен

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

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

• 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
• Лекции по математической логике и теории алгоритмов. Ч.1: Начала теории множеств, Верещагин, Н. К., 2008

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

• Лекции по математической логике и теории алгоритмов. Ч.2: Языки и исчисления, Верещагин, Н. К., 2017

Авторы

• Кононова Елизавета Дмитриевна