Introduction to Discrete Mathematics

2022/2023

Academic Year

RUS

Instruction in Russian

3

ECTS credits

Delivered at:

Department of Mathematics

Course type:

Elective course

When:

3 year, 3 module

Instructors

Polyakov, Nikolay L.

Правдивец Николай Александрович

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

Аннотация

Дисциплина «Введение в дискретную математику» знакомит с фундаментальными математическими понятиями, используемыми для построения формальных моделей. Дисциплина включает в себя элементы теории множеств, теории булевых функций, теории графов, комбинаторики и теории рекуррентных последовательностей. Рассматриваются приложения дискретной математики к созданию и использованию реляционных баз данных, принятию решений, комбинаторной теории вероятностей, теоретической экономике.

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

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

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

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

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

• Элементы теории множеств: основные понятия
• Бинарные соответствия и отношения
• Отношения эквивалентности и порядка
• Функции
• Булевы функции, матрицы и векторы
• Элементы теории графов - 1
• Элементы теории графов - 2
• Элементы бесконечной комбинаторики
• Элементы конечной комбинаторики - 1
• Элементы конечной комбинаторики - 2
• Дискретные процессы и рекуррентные формулы

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

• Контрольная работа
• Экзамен
• Участие в дискуссиях на семинарах

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

• 2022/2023 учебный год 3 модуль
  0.5 * Экзамен + 0.3 * Контрольная работа + 0.2 * Участие в дискуссиях на семинарах

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

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

• Бинарные отношения, графы и коллективные решения. Примеры и задачи : учебное пособие для вузов / Ф. Т. Алескеров, Э. Л. Хабина, Д. А. Шварц, Л. Г. Егорова. — Москва : Издательство Юрайт, 2021. — 458 с. — (Высшее образование). — ISBN 978-5-534-14489-5. — Текст : электронный // Образовательная платформа Юрайт [сайт]. — URL: https://urait.ru/bcode/477702 (дата обращения: 28.08.2023).
• Верещагин, Н. К. Лекции по математической логике и теории алгоритмов : учебное пособие / Н. К. Верещагин, А. Шень. — 3-е изд., стер. — Москва : МЦНМО, [б. г.]. — Часть 1 : Начала теории множеств — 2008. — 128 с. — ISBN 978-5-94057-321-0. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/9306 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.
• Вечтомов, Е. М.  Математика: логика, множества, комбинаторика : учебное пособие для вузов / Е. М. Вечтомов, Д. В. Широков. — 2-е изд. — Москва : Издательство Юрайт, 2021. — 243 с. — (Высшее образование). — ISBN 978-5-534-06612-8. — Текст : электронный // Образовательная платформа Юрайт [сайт]. — URL: https://urait.ru/bcode/473253 (дата обращения: 28.08.2023).
• Гашков, С. Б.  Дискретная математика : учебник и практикум для академического бакалавриата / С. Б. Гашков, А. Б. Фролов. — 2-е изд., испр. и доп. — Москва : Издательство Юрайт, 2019. — 448 с. — (Высшее образование). — ISBN 978-5-534-04435-5. — Текст : электронный // Образовательная платформа Юрайт [сайт]. — URL: https://urait.ru/bcode/433206 (дата обращения: 28.08.2023).
• Гашков, С. Б.  Дискретная математика : учебник и практикум для среднего профессионального образования / С. Б. Гашков, А. Б. Фролов. — 2-е изд., испр. и доп. — Москва : Издательство Юрайт, 2019. — 483 с. — (Профессиональное образование). — ISBN 978-5-534-11558-1. — Текст : электронный // Образовательная платформа Юрайт [сайт]. — URL: https://urait.ru/bcode/445631 (дата обращения: 28.08.2023).
• Гордин, В. А. Дифференциальные и разностные уравнения: Какие явления они описывают и как их решать : учебное пособие / В. А. Гордин. — Москва : Высшая школа экономики, 2016. — 531 с. — ISBN 978-5-7598-1094-0. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/100139 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.
• Лавров, И. А. Задачи по теории множеств, математической логике и теории алгоритмов : учебник / И. А. Лавров, Л. Л. Максимова. — 5-е изд., испр. — Москва : ФИЗМАТЛИТ, 2002. — 256 с. — ISBN 5-9221-0026-2. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/2242 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.
• Марченков, С. С. Основы теории булевых функций : учебное пособие / С. С. Марченков. — Москва : ФИЗМАТЛИТ, 2014. — 136 с. — ISBN 978-5-9221-1562-9. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/59714 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.
• Пак, В. Г.  Дискретная математика: теория множеств и комбинаторный анализ. Сборник задач : учебное пособие для вузов / В. Г. Пак. — Москва : Издательство Юрайт, 2021. — 235 с. — (Высшее образование). — ISBN 978-5-534-09512-8. — Текст : электронный // Образовательная платформа Юрайт [сайт]. — URL: https://urait.ru/bcode/471960 (дата обращения: 28.08.2023).

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

• Алескеров, Ф. Т. Бинарные отношения, графы и коллективные решения : учебное пособие / Ф. Т. Алескеров, Э. Л. Хабина, Д. А. Шварц. — 2-е изд. — Москва : ФИЗМАТЛИТ, 2012. — 344 с. — ISBN 978-5-9221-1363-2. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/59762 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.