Discrete Mathematics

2024/2025

Academic Year

RUS

Instruction in Russian

6

ECTS credits

Delivered at:

Big Data and Information Retrieval School

Course type:

Elective course

When:

1 year, 1-3 module

Instructors

Валинкин Михаил Валерьевич

Vyalyi, Michael

Sokolov, Pavel

Stasenko, Roman

Chistopolskaia, Anastasiia

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

Аннотация

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

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

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

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

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

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

• Множества и логика.
• Комбинаторика.
• Алгебра логики.
• Математические определения, утверждения и доказательства.
• Функции.
• Графы.
• Двудольные графы, паросочетания и функции.
• Бинарные отношения. Отношения эквивалентности.
• Булевы функции.
• Мощность множеств.
• Разрешающие деревья и нижние оценки.

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

• Домашнее задание 1
• Домашнее задание 2
• Коллоквиум — 1
• Промежуточный экзамен
• Коллоквиум-2
• Итоговый экзамен

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

• 2024/2025 2nd module
  0.25 * Домашнее задание 1 + 0.3 * Коллоквиум — 1 + 0.45 * Промежуточный экзамен
• 2024/2025 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
• Лекции по дискретной математике : учебник / М. Н. Вялый, В. В. Подольский, А. А. Рубцов [и др.]. — Москва : Высшая школа экономики, 2021. — 496 с. — ISBN 978-5-7598-2212-7. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/199883 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.

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

• Верещагин, Н. К. Лекции по математической логике и теории алгоритмов : учебное пособие / Н. К. Верещагин, А. Шень. — 3-е изд., доп. — Москва : МЦНМО, [б. г.]. — Часть 2 : Языки и исчисления — 2008. — 288 с. — ISBN 978-5-94057-322-7. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/9307 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.
• Верещагин, Н. К. Лекции по математической логике и теории алгоритмов : учебное пособие / Н. К. Верещагин, А. Шень. — 3-е изд., стер. — Москва : МЦНМО, [б. г.]. — Часть 1 : Начала теории множеств — 2008. — 128 с. — ISBN 978-5-94057-321-0. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/9306 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.

Авторы

• Подольский Владимир Владимирович
• Сысоева Алевтина Александровна
• Вялый Михаил Николаевич