Курс "Методы и алгоритмы теории графов"

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

О курсе

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

Формат

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

В курсе имеется два типа дедлайна (предельного срока выполнения оценивающих мероприятий):

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

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

Cертификат

Сертификат будет выдан слушателям, выполнившим следующие условия:

  1. Достижение в срок до 30 октяюря 2016 года включительно не менее 60% от максимального количества баллов по следующим задачам:
  • Неделя 2 - "Волновой алгоритм";
  • Неделя 2 - "Алгоритм Форда-Беллмана";
  • Неделя 3 - "Алгоритм Робертса и Флореса";
  • Неделя 4 - "Алгоритм Прима".
  • Неделя 4 - "Алгоритм Краскала".
  • Неделя 5 - "Алгоритм Магу-Вейсмана".
  • Оплата в срок до 4 ноября 2016 года включительно. К оплате допускаются только слушатели, выполнившие пункт 1.
  • Достижение до жесткого дедлайна не менее 60% от максимального количества баллов по следующим задачам:
    • Неделя 6 - "Алгоритм минимальной раскраски графа на основе метода Магу";
    • Неделя 10 - "Интернет-экзамен. Часть A".

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

  • Достижение в срок до 4 декабря 2016 года включительно не менее 60% от максимального количества баллов по курсу.
  • Результаты обучения

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

    Формируемые компетенции

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

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

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

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

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

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

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

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