Discrete Mathematics

2024/2025

Academic Year

RUS

Instruction in Russian

6

ECTS credits

Delivered at:

Big Data and Information Retrieval School

Course type:

Compulsory course

When:

1 year, 1, 2 module

Instructors

Зайцева Анна Тиграновна

Sokolov, Pavel

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

Аннотация

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

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

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

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

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

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

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

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

• Домашние задания
• Самостоятельные работы
• Коллоквиум 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

Авторы

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