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

Methods and Algorithms of Graph Theory

2020/2021
Academic Year
RUS
Instruction in Russian
3
ECTS credits
Course type:
Elective course
When:
2 year, 4 module

Instructor

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

Аннотация

Настоящая дисциплина относится к блоку дисциплин по выбору. Дисциплина реализуется в формате смешанного обучения и представляет собой on-line курс Методы и Алгоритмы Теории Графов на платформе Coursera от автора МФТИ и читается преподавателями Купавским А. и Райгородским А. Ссылка на курс: https://www.coursera.org/learn/teoriya-grafov. Изучение данной дисциплины базируется на следующих дисциплинах: Математический анализ. Для освоения учебной дисциплины студент должен владеть следующими знаниями и компетенциями: Способен учиться, приобретать новые знания, умения, в том числе в области, отличной от профессиональной; Способен работать с информацией: находить, оценивать и использовать информацию из различных источников, необходимую для решения научных и профессиональных задач (в том числе на основе системного подхода); Способен собрать и проанализировать исходные данные, необходимые для расчета экономических и социально-экономических показателей, характеризующих деятельность хозяйствующих субъектов. Основные положения дисциплины могут быть использованы в дальнейшем при изучении дисциплин: Прикладная эконометрика панельных и качественных данных, Экономическая политика, Подготовка выпускной квалификационной работы.
Цель освоения дисциплины

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

  • Изучение теории графов и разделов теории алгоритмов на графах.
  • Ознакомление с математическими моделями явлений в экономике, использующими графы, позволяющие студенту ориентироваться в прикладных вопросах, требующих использования математического аппарата
Планируемые результаты обучения

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

  • Владеет методами исследования моделей в области экономики.
  • Демонстрирует навыки интерпретации экономически показателей, используемых в расчетах по модели.
  • Владеет навыками работы с данными, умения вычислять параметры моделей, давать их экономическую интерпретацию.
  • Демонстрирует навыки работы с данными, умения проводить верификацию моделей.
  • Владеет методиками самоорганизации при выполнении профессиональных задач.
  • Умеет использовать в профессиональной работе современные технические средства.
Содержание учебной дисциплины

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

  • Введение. Базовые понятия теории графов
    На первом видео лекции онлайн-курса введено понятие графа, обсуждаются разные виды графов, объяснено, как использовать граф как модель структуры интернета. Обсуждены первые понятия теории графов, такие как маршруты в графах, степень вершины, связность, деревья.
  • Эквивалентные определения дерева. Планарные графы
    Даны четыре определения дерева и понятие правильной раскраски графа, сформулиро-вана теорема о четырех красках, а также критерий Куратовского о том, как определить, можно ли нарисовать данный граф на плоскости без пересечений ребер. В последней части лекции обсуждена формула Эйлера для планарных графов и некоторые из её множественных следствий.
  • Формула Кэли. Унициклические графы. Эйлеровы циклы
    Дан способперечислить все деревья, леса и унициклические графы. Решена задача о Кёнигсбергских мостах
  • Гамильтоновы циклы
    Гамильтоновы циклы Лекция продолжает обсуждать циклы, проходящие через весь граф. На этот раз мы по-говорим про циклы, проходящие через все вершины графа. Даны достаточные условия нали-чия такого цикла. Обсуждены такие характеристики графа, как независимое число и k-связность.
  • Паросочетания. Теорема Холла и Кенига.
    На лекции введено понятие паросочетания и сформулирована достаточное и необходимое условие наличия паросочетания. Введены базовые понятия экстремальной теории графов и дана теорема Турана и аналог теоремы Турана для графов на плоскости.
  • Теория Рамсея.
    Введены первые понятия теории Рамсея на примере задачи о знакомстве среди шести чело-век. Введены оценки для чисел Рамсея.
Элементы контроля

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

  • неблокирующий Онлайн-курс
    Оценка за текущий контроль нормируется до 10 балльной шкалы и округляется по правилам арифметического округления по итогам прохождения онлайн курса.
  • неблокирующий Письменный экзамен
    Экзамен проводится в форме собеседования. Оценка производится по 10-балльной шкале, пропорционально количеству правильно выполненных заданий.
Промежуточная аттестация

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

  • Промежуточная аттестация (4 модуль)
    0.7 * Онлайн-курс + 0.3 * Письменный экзамен
Список литературы

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

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

  • Reinhard Diestel, Alexander Schrijver, & Paul D. Seymour. (2007). Graph Theory. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsbas&AN=edsbas.24E6A4B5

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

  • Kumar, R., & Pattnaik, P. K. (2018). Graph Theory. Bengaluru: Laxmi Publications Pvt Ltd. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=2228702