Бакалавриат
2022/2023
Дискретная математика
Лучший по критерию «Полезность курса для Вашей будущей карьеры»
Лучший по критерию «Полезность курса для расширения кругозора и разностороннего развития»
Лучший по критерию «Новизна полученных знаний»
Статус:
Курс обязательный (Цифровые платформы и логистика)
Направление:
38.03.02. Менеджмент
Кто читает:
Департамент математики
Где читается:
Санкт-Петербургская школа экономики и менеджмента
Когда читается:
1-й курс, 1, 2 модуль
Формат изучения:
без онлайн-курса
Охват аудитории:
для своего кампуса
Преподаватели:
Казакевич Виктория Григорьевна
Язык:
русский
Кредиты:
4
Контактные часы:
56
Программа дисциплины
Аннотация
Настоящий курс теории графов включает в себя разделы, посвященные связности, деревьям, поиску эйлеровых путей и циклов, поиску максимального потока в сети, построению хроматических многочленов, поиску кратчайших путей и минимальных остовных деревьев.
Цель освоения дисциплины
- Целью освоения дисциплины «Дискретная математика» является изучение начального курса теории графов, а также необходимых для этого инструментов (базовой комбинаторики и бинарных отношений).
Планируемые результаты обучения
- Демонстрирует знание базовых комбинаторных понятий и приемов, в частности, понятий размещения, сочетания и перестановки, принципов сложения и умножения, принципа Дирихле и принципа включения-исключения, демонстрирует умение проводить простые комбинаторные рассуждения и вычисления.
- Демонстрирует знание понятия бинарного отношения, владение поянтиями частичного, линейного, строгого и нестрогого порядков, а также отношения эквивалентности, демонстрирует умение определять тип бинарного отношения по стандартным формам представления, а также транслировать описание бинарного отношения из одной формы представления в другую.
- Демонстрирует знание определений базовых понятий теории графов, владение понятиями «направленное и ненаправленное ребро», «степень вершины», «путь» (открытый или замкнутый), «простой путь», «цепь», «цикл», «дерево», «полный граф» и так далее. Умеет задавать граф бинарным отношением, списком инцидентности, матрицами смежности и инцидентности, а также транслировать один способ задания в другой, умеет применять алгоритмы поиска (обхода) в ширину и глубину.
- Демонстрирует знание понятий связности и k-связности для неориентированного графа, умеет выделять мосты и компоненты связности. Демонстрирует знание понятий слабой и сильной связности для орграфа, умеет вы делять компоненты сильной связности с использованием алгоритма Косарайю, а также строить граф Герца.
- Демонстрирует знание понятий эйлерова пути и эйлерова цикла, а также эйлерова и полуэйлерова графа; умеет определять эйлеровость/полуэйлеровость графа с использованием соответствующих критериев, а при их наличии - строить в графе эйлеров путь/цикл.
- Демонстрирует знание понятия дерева и связанных с ним понятий, умеет строить по дереву его код Прюфера и восстанавливать дерево по его коду Прюфера. Демонстрирует знание понятий остовного дерева, главного цикла и разреза.
- Демонстрирует знание понятия сети и потока в ней, понимание постановки задачи о максимальном потоке в сети; уменет определять, является ли сеть плоской, умеет решать задачу о максимальном потоке в сети при помощи алгоритмов Форда-Фалкерсона, Эдмондса-Карпа и Диница.
- Демонстрирует знание понятия двудольного графа, умение опрее\делять двудольность графа с использованием теоремы Кенинга. Демонстрирует знание понятия паросочетания, понимание различий между максимальным и наибольшим паросочетанием, умеет строить наибольшее паросочетание.
- Демонстрирует зание понятия вершинной раскраски графа, правильной вершинной раскраски, хроматического числа. Демонстрирует знание понятия хроматического многочлена, умение сопоставлять некоторые характеристики графа с некоторыми свойствами хроматического многочлена, умение построить для графа хроматический многочлен при помощи теоремы о разделяющей клике или теоремы о редукции.
- Демонстрирует знание понятия минимального остовного дерева взвешенного графа, умение построить минимальное остовное дерево при помощи алгоритмов Прима и Краскаля.
- Демонстрирует знание понятия кратчайшего пути (во взвешенном и невзвешенном графах). Умеет строить кратчайший путь от фиксированной вершины взвешенного графа до прочих при помощи алгоритмов Дейкстры и Форда-Беллмана.
- Демонстрирует знание понятия кратчайшего пути (во взвешенном и невзвешенном графах). Умеет строить кратчайший путь от фиксированной вершины взвешенного графа до прочих при помощи алгоритмов Дейкстры и Форда-Беллмана. Умеет строить все кратчайшие пути во взвешенном графе при помощи алгоритмов Флойда и Джонсона.
Содержание учебной дисциплины
- Базовые комбинаторные понятия и приемы.
- Бинарные отношения: основные определения, свойства, способы задания.
- Теория графов: базовые определения и свойства, примеры.
- Связность, k-связность, слабая и сильная связность.
- Эйлеровы и полуэйлеровы графы
- Деревья, остовные деревья, код Прюфера, корневые деревья.
- Задача о максимальном потоке в сети
- Двудольные графы, критерий двудольности (теорема Кенинга).
- Вершинные раскраски графа
- Минимальные остовные деревья взвешенных графов.
- Задача о построении кратчайших путей.
- Построение всех кратчайших путей во взвешенном графе
Элементы контроля
- Контрольная работа 1Состоит из 6 задач. Максимальная стоимость задания: 1-4 — 20 баллов, 5,6 — 10 баллов.
- Контрольная работа 2Состоит из 6 задач. Максимальная стоимость задания: 1-4 — 20 баллов, 5,6 — 10 баллов.
- Домашнее задание 1Состоит из 5 заданий по 5 пунктов в каждом. Максимальная оценка за каждый пункт — 4 балла.
- Домашнее задание 2Состоит из 14 заданий. Максимальная стоимость заданий 10-13 — по 10 баллов, остальные — по 6 баллов.
- Домашнее задание 3Состоит из 4 задач. Максимальная стоимость задания: 1,2 — 10 баллов, 3,4 — 40 баллов.
