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

2020/2021

Учебный год

RUS

Обучение ведется на русском языке

6

Кредиты

Кто читает:

Департамент математики

Статус:

Курс обязательный

Когда читается:

1-й курс, 3, 4 модуль

Преподаватели

Коданева Надежда Михайловна

Михайлец Екатерина Викторовна

Шварц Дмитрий Александрович

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

Аннотация

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

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

• Познакомить студентов с основами современной дискретной математики;
• Показать, как дискретная математика используется в экономических и «программистских» дисциплинах
• Научить студентов работать с формальными математическими понятиями, в том числе строго доказывать простые утверждения

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

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

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

• Логика и множества
  Множества и элементы. Способы задания множеств. Операции над множествами. Диаграммы Венна. Множества и логика. Понятие высказывания. Логические связки и запись утверждений с их помощью. Булевы (логические) функции. Формулы и таблицы истинности. Логические законы. Эквивалентные преобразования логических формул. Кванторы общности и существования. Свободные и связанные переменные. Запись утверждений в логике предикатов. Преобразование формул. Анализ логической информации при принятии управленческих решений. Математическая логика и математические доказательства. Примеры и контрпримеры, доказательства от противного. Метод математической индукции. Простые и сложные проценты.
• Комбинаторика
  Правила суммы, произведения и дополнения. Число подмножеств и перестановок. Немного о криптографии. Сочетания и биноминальные коэффициенты. Бином Ньютона. Треугольник Паскаля. Сочетания с повторениями. Метод точек и перегородок. Принцип включения и исключения. Комбинаторика и вероятность. Оценка рисков при принятии решений.
• Бинарные отношения
  Декартово произведение множеств. Бинарные отношения и их свойства. Бинарные отношения, как отношения предпочтения. Условия классической рациональности. Линейные, частичные и слабые порядки. Представления предпочтений экспертов с помощью отношения порядка. Бинарные отношения в экономике: функции полезности, многокритериальные модели принятия решений. Отношения эквивалентности. Классы эквивалентности. Задачи классификации и кластерный анализ.
• Теория графов
  Общая часть. Неориентированные и ориентированные графы. Примеры: граф дорожной сети, граф интернета. Графы и бинарные отношения. Степени вершин. Способы представления графов. Матрицы смежности и инцидентности. Пути и циклы в графах, простые пути и циклы. Подграфы. Использование графов при анализе социальных сетей. Неориентированные графы. Связность и компоненты связности. Шарниры и мосты. Изоморфизм графов. Деревья. Четыре эквивалентных определения. Остовные деревья. Двудольные графы. Теорема Кенига. Полные двудольные графы. Паросочетания и подбор персонала. Эйлеров цикл, необходимое и достаточное условие существования и алгоритм поиска. Гамильтонов цикл. Теорема Дирака. Задача коммивояжера и оптимальный маршрут курьера. Почему ВВП и другие дороги в аэропортах не должны пересекаться? Планарные и плоские графы. Формула Эйлера. Методы проверки планарности графа. Задача оптимального представления графической информации и планарные графы. Ориентированные графы. Связность: сильная и слабая. Принятие коллективных решений. Внутренне и внешне устойчивые множества. Ядро. Метод Магу. Выбор независимых экспертов с помощью доминирующих множеств. Алгоритмы на графах. Взвешенные графы, как модель решения задач минимизации затрат (времени). Задача выбора при строительстве дорог и остовные графы минимальной стоимости. Алгоритм Прима. Кратчайшие пути. Алгоритм Дейкстры и его использование (Яндекс-карты). Задача о максимальном потоке и ее применения в логистике. Транспортные сети. Потоки и разрезы. Использование: Яндекс-пробки.

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

• Контрольная работа (2 шт)
• Домашнее задание
• Экзаменационная контрольная.

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

• Промежуточная аттестация (4 модуль)
  Итоговая оценка вычисляется по формуле: MAX((0.4*C_1+0.4*C_2+0.2*H),MIN(E,4)), где C_1 и C_2 - оценки за две контрольные работы, H- за домашние задания, E - за экзамен. Блокирующих форм контроля нет. Округление итоговой оценки - математическое, кроме границ 3/4 (в меньшую сторону) и 0/1 (в большую). Т.е. 3,96 округляется до 3, а 4,50 - до 5. Расшифровка формулы: вес контрольных по 40%, домашних заданий - 20%. Если результат не менее 4, то он и будет итоговой оценкой. В противном случае проводится экзамен. Если оценка за него не менее 4, итоговая оценка равна 4, если нет, то студент получает незачет.

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

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

• Дискретная математика для инженера, Кузнецов, О. П., 2004
• Микони С. В. - Дискретная математика для бакалавра: множества, отношения, функции, графы - Издательство "Лань" - 2012 - 192с. - ISBN: 978-5-8114-1386-7 - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/4316

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

• Алескеров Ф.Т., Хабина Э.Л., Шварц Д.А. - Бинарные отношения, графы и коллективные решения - Издательство "Физматлит" - 2012 - 344с. - ISBN: 978-5-9221-1363-2 - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/59762