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

Бакалавриат 2020/2021

Статус: Курс обязательный (Бизнес-информатика)

Направление: 38.03.05. Бизнес-информатика

Кто читает: Департамент математики

Где читается: Высшая школа бизнеса

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

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

Преподаватели: Коданева Надежда Михайловна, Михайлец Екатерина Викторовна, Шварц Дмитрий Александрович

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

Кредиты: 6

Контактные часы: 90

Полная версия программы учебной дисциплины

Аннотация

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

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

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

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

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

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

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

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

Контрольная работа (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, если нет, то студент получает незачет.

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