Бакалавриат
2024/2025
Дискретная математика для экономистов
Статус:
Курс обязательный (Аналитика в экономике)
Направление:
38.03.01. Экономика
Кто читает:
Департамент математики
Где читается:
Санкт-Петербургская школа экономики и менеджмента
Когда читается:
1-й курс, 3, 4 модуль
Формат изучения:
без онлайн-курса
Охват аудитории:
для своего кампуса
Язык:
русский
Кредиты:
6
Программа дисциплины
Аннотация
Настоящий курс Дискретной математики включает в себя разделы, посвященные введению в комбинаторику, разделы теории графов, посвященные связности, деревьям, поиску эйлеровых путей и циклов, поиску максимального потока в сети, вершинным раскраскам графов, поиску кратчайших путей и минимальных остовных деревьев.
Цель освоения дисциплины
- Целью освоения дисциплины «Дискретная математика» является изучение начального курса теории графов, а также необходимых для этого инструментов (базовой комбинаторики и бинарных отношений).
Планируемые результаты обучения
- демонстрирует знание понятия двудольного графа, умение определять двудольность графа с использованием теоремы Кенинга. Демонстрирует знание понятия паросочетания, понимание различий между максимальным и наибольшим паросочетанием, умеет строить наибольшее паросочетание
- демонстрирует знание понятия сети и потока в ней, понимание постановки задачи о максимальном потоке в сети; умеет определять, является ли сеть плоской, умеет решать задачу о максимальном потоке в сети при помощи алгоритмов Форда-Фалкерсона, Эдмондса-Карпа и Диница
- демонстрирует знание понятия минимального остовного дерева взвешенного графа, умение построить минимальное остовное дерево при помощи алгоритмов Прима и Краскаля
- демонстрирует знание понятия кратчайшего пути (во взвешенном и невзвешенном графах). Умеет строить кратчайший путь от фиксированной вершины взвешенного графа до прочих при помощи алгоритмов Дейкстры и Форда-Беллмана. Умеет строить все кратчайшие пути во взвешенном графе при помощи алгоритмов Флойда и Джонсона
- демонстрирует знание понятия производящей функции. Умеет применять аппарат производящих функций для решения рекуррентных уравнений.
- демонстрирует знание понятия бинарного отношения, владение понятиями частичного, линейного, строгого и нестрогого порядков, а также отношения эквивалентности, демонстрирует умение определять тип бинарного отношения по стандартным формам представления, а также транслировать описание бинарного отношения из одной формы представления в другую
- демонстрирует знание определений базовых понятий теории графов, владение понятиями «направленное и ненаправленное ребро», «степень вершины», «путь» (открытый или замкнутый), «простой путь», «цепь», «цикл», «дерево», «полный граф» и так далее. Умеет задавать граф бинарным отношением, списком инцидентности, матрицами смежности и инцидентности, а также транслировать один способ задания в другой, умеет применять алгоритмы поиска (обхода) в ширину и глубину
Содержание учебной дисциплины
- 1. Базовые комбинаторные понятия и приемы
- 2. Бинарные отношения: основные определения, свойства, способы задания
- 3. Теория графов: базовые определения и свойства, примеры
- 4. Связность, k-связность, слабая и сильная связность
- 6. Деревья, остовные деревья, код Прюфера, корневые деревья
- 7. Задача о максимальном потоке в сети
- 8. Двудольные графы, критерий двудольности (теорема Кенинга)
- 9. Минимальные остовные деревья взвешенных графов
- 10. Задача о построении кратчайших путей
- 11. Построение всех кратчайших путей во взвешенном графе
- 12. Вершинные раскраски графа
Элементы контроля
- Домашняя работа 1
- Домашняя работа 2
- Домашняя работа 3
- Домашняя работа 4
- Контрольная работа 1
- Контрольная работа 2
- Контрольная 3
Промежуточная аттестация
- 2024/2025 4th moduleФормула оценивания: О_итог = 0.1 * H_1 + 0.2 * Q_1 + 0.1 * H_2 + 0.1 * H_3 + 0.2 * Q_2 + 0.1 * H_4 + 0.2 * Q_3, где Q_1, Q_2, Q_3 — оценки за контрольные работы, H_1, H_2, H_3, H_4 — оценки за домашние задания.
Список литературы
Рекомендуемая основная литература
- Алгоритмы: построение и анализ : пер.с англ., Кормен, Т., 2013
Рекомендуемая дополнительная литература
- Карпов, Д. В. Теория графов : учебное пособие / Д. В. Карпов. — Москва : МЦНМО, 2022. — 555 с. — ISBN 978-5-4439-3690-1. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/305501 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.
- Рыбин, С. В. Дискретная математика и информатика : учебник для вузов / С. В. Рыбин. — Санкт-Петербург : Лань, 2022. — 748 с. — ISBN 978-5-8114-8566-6. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/193326 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.