Методы и алгоритмы теории графов

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

В состав курса входят видео-лекции, интерактивные демонстрации, упражнения и виртуальные лаборатории. Длительность курса составляет 10 недель. Трудоемкость курса – 3 зачетных единицы. Средняя недельная нагрузка на обучающегося – 10 часов.

1. Осипова В.А. Основы дискретной математики. Уч. пособие. – М.: ФОРУМ: Инфра-М, 2006. – 160 с.
2. Койнов Р.В., Лисицына Л.С. Практикум по дискретной математике в среде виртуальной лаборатории системы дистанционного обучения СПбГУ ИТМО. Уч.-метод. пос. – СПб.: СПбГУ ИТМО, 2004. – 64 с.
3. Романовский И.В. Дискретный анализ. Уч. пособие. – СПб.: Невский Диалект: БХВ-Петербург, 2004. – 320 с.
4. Новиков Ф.А. Дискретная математика. Уч. для вузов. Стандарт третьего поколения. – СПб.: Питер, 2011. – 384 с.
5. Нефедов В.Н., Осипова В.А. Курс дискретной математики. Уч. пособие. – М.: Изд-во МАИ, 1992. – 264 с.
6. Джеймс Андерсон. Дискретная математика и комбинаторика. Пер. с англ. – М.: Изд. дом "Вильямс", 2004. – 960 с.
7. Горбатов В.А. Основы дискретной математики. Уч. пос. для вузов. – М.: Высш.шк., 1986. – 311 с.
8. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. – М.: Наука, 1990. – 384 с.
9. Зыков А.А. Теория конечных графов. – Новосибирск: Наука, 1969. – 543 с.
10. Кристофидес Н. Теория графов. Алгоритмический подход. Пер. с англ. – М.: Мир, 1988. – 432 с.
11. Майника Э. Алгоритмы оптимизации на сетях и графах. Пер. с англ. – М.: Мир, 1981. – 323 с.
12. Оре О. Теория графов. 2-ое изд. – М.: Наука, 1980. – 336 с.

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

В курсе рассматриваются следующие темы:

1. Основы теории графов
2. Связность графов
3. Циклы в графах
4. Деревья
5. Оптимизация на графах
6. Двудольные графы
7. Изоморфизм и гомеоморфизм графов
8. Плоские и планарные графы

Тема "Оптимизация на графах" изучается в течение двух недель, остальные темы изучаются в течение одной недели. На 10-й неделе запланирован интернет-экзамен.

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

• знания в области математических наук (теория графов) (РО-1);
• умения и навыки применения эффективных методов теории графов для решения типовых задач (РО-2).

09.03.01 Информатика и вычислительная техника

• Использовать основные законы естественнонаучных дисциплин в профессиональной деятельности, применяет методы математического анализа и моделирования, теоретического и экспериментального исследования (ОК-10)

09.03.02 Информационные системы и технологии

• Владеть широкой общей подготовкой (базовыми знаниями) для решения практических задач в области информационных систем и технологий (ОПК-1)
• Способность разрабатывать средства реализации информационных технологий (методические, информационные, математические, алгоритмические, технические и программные) (ПК-12)

09.03.03 Прикладная информатика

• Способность применять системный подход и математические методы в формализации решения прикладных задач (ПК-23)
• Способность решать стандартные задачи профессиональной деятельности на основе информационной и библиографической культуры с применением информационно-коммуникационных технологий и с учетом основных требований информационной безопасности (ОПК-4)

09.03.04 Программная инженерия

• Готовность к использованию методов и инструментальных средств исследования объектов профессиональной деятельности (ПК-13)