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

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)

О курсе

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

В курсе - следующие 8 тем теории графов: основы теории графов, связность в графах, циклы в графах, деревья, оптимизация на графах, двудольные графы, изоморфизм и гомеоморфизм графов, плоские и планарные графы. Курс является образовательным модулем дисциплины «Дискретная математика» в составе основных образовательных программ по подготовке бакалавров различных направлений.

В результате успешного завершения данного онлайн-курса обучаемый будет способен к самостоятельному изучению других разделов теории графов.

Формат

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

Информационные ресурсы

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

Требования

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

Сертификат

Сертификат участника обычно выдается при достижении 60% от общего рейтинга при условии сдачи работ до жесткого дедлайна. Сертификат с отличием, как правило, выдается при достижении 90% от общего рейтинга при условии сдачи работ до мягкого дедлайна.

Длительность курса: 10 недель
Понадобится для освоения: 10 часов в неделю
Для зачета в своем вузе: 3 зачётных единицы