• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Discrete Mathematics

2022/2023
Academic Year
RUS
Instruction in Russian
4
ECTS credits
Course type:
Compulsory course
When:
1 year, 1, 2 module

Instructor


Казакевич Виктория Григорьевна

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

Аннотация

Настоящий курс теории графов включает в себя разделы, посвященные связности, деревьям, поиску эйлеровых путей и циклов, поиску максимального потока в сети, построению хроматических многочленов, поиску кратчайших путей и минимальных остовных деревьев.
Цель освоения дисциплины

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

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

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

  • Демонстрирует знание базовых комбинаторных понятий и приемов, в частности, понятий размещения, сочетания и перестановки, принципов сложения и умножения, принципа Дирихле и принципа включения-исключения, демонстрирует умение проводить простые комбинаторные рассуждения и вычисления.
  • Демонстрирует знание понятия бинарного отношения, владение поянтиями частичного, линейного, строгого и нестрогого порядков, а также отношения эквивалентности, демонстрирует умение определять тип бинарного отношения по стандартным формам представления, а также транслировать описание бинарного отношения из одной формы представления в другую.
  • Демонстрирует знание определений базовых понятий теории графов, владение понятиями «направленное и ненаправленное ребро», «степень вершины», «путь» (открытый или замкнутый), «простой путь», «цепь», «цикл», «дерево», «полный граф» и так далее. Умеет задавать граф бинарным отношением, списком инцидентности, матрицами смежности и инцидентности, а также транслировать один способ задания в другой, умеет применять алгоритмы поиска (обхода) в ширину и глубину.
  • Демонстрирует знание понятий связности и 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 баллов.
Промежуточная аттестация

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

  • 2022/2023 учебный год 2 модуль
    0.25 * Контрольная работа 2 + 0.25 * Домашнее задание 2 + 0.25 * Контрольная работа 1 + 0.125 * Домашнее задание 3 + 0.125 * Домашнее задание 1
Список литературы

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

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

  • Алгоритмы: построение и анализ : пер.с англ., Кормен, Т., 2013
  • Комбинаторика, Виленкин, Н. Я., 2006
  • Теория графов, Харари, Ф., 2018

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

  • Теория графов : алгоритмический подход, Кристофидес, Н., 1978