наверх

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

 width=
  • 10 недель

    длительность курса

  • 3 зачётных единицы

    для зачета в своем вузе

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

О курсе

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

Формат

В состав курса входят видео-лекции, интерактивные демонстрации, упражнения и виртуальные лаборатории. Длительность курса составляет 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)

Лисицына Любовь Сергеевна

Доктор технических наук, профессор
Должность: заведующий кафедрой компьютерных образовательных технологий

сертификат об окончании курса

Сертификат

Похожие курсы