Новая образовательная платформа
Курс НГУ Алгебраическая теория графов
Курс

Алгебраическая теория графов

Алгебраическая теория графов

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

Материалы курса разработала группа исследователей Математического центра в Академгородке (соглашение с Министерством науки и высшего образования РФ № 075-15-2019-1675)

Курс Новосибирского государственного университета

• НГУ входит в 24 международные коллаборации, 19 из них — в области физики элементарных частиц и астрофизики.
• Университет реализует модель «образование через исследования»: 80% преподавателей НГУ — действующие учёные, поэтому студенты с младших курсов работают над реальными исследовательскими проектами.
• Выпускники НГУ работают в ведущих зарубежных университетах и научно-исследовательских центрах.
• НГУ — центр экосистемы новосибирского Академгородка, где в шаговой доступности находятся один из самых высокоэффективных в России технопарков и 35 исследовательских организаций.

Трейлер курса

Превью видеозаписи

Кому подойдёт этот курс

  • Студентам

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

  • IT-специалистам

    Научитесь строить графы и решать задачи криптографии, кодирования, прогнозирования, оптимизации и многого другого, используя инструментарий теории графов и теории групп.

Чему вы научитесь

  1. Работать с базовыми понятиями теории графов и теории групп
  2. Использовать инструменты теории графов для решения прикладных задач в криптографии, физике, естественных и социальных науках
  3. Понимать свойства и особенности различных типов графов
  4. Применять собственные числа и векторы для прогнозирования, доказательства и даже рисования
  5. Строить графы для поиска ответов на исследовательские и популярные вопросы
  6. Разбираться в принципах теории графов на простых примерах

Содержание курса

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

  • 6 модулей
  • 44 видеоматериала
  1. Модуль 1. Основы алгебраической теории графов

    Основная часть модуля посвящена базовым определениям и понятиям теории графов и теории групп. Вы также узнаете об истории развития этих математических дисциплин и о том, какие задачи лежали в их основе. Кроме того, научитесь решать задачи о перекладывании блинчиков и сборке кубика Рубика. А ещё узнаете про задачу поиска пути в лабиринте, которую решил Эдвард Мур, и про целый класс графов Мура.

      1. Вводное видео. О чём этот курс и как он устроен
      2. Историческое развитие алгебраической теории графов
      3. Базовые понятия теории графов
      4. Дистанционно регулярные графы
      5. Графы Мура
      6. Основы теории групп
      7. Блинчиковый граф и биокомпьютер
      8. Кубик Рубика
  2. Модуль 2. Графы и матрицы

    В этом модуле вы узнаете, что графы есть абсолютно везде: в социальных сетях, поисковых системах и теории шести рукопожатий. Это значит, что множество вопросов можно перевести на язык графов. А где графы, там и их матрицы. Это и есть основа алгебраической теории графов. Мы сфокусируемся на матрицах смежности графов и их спектрах. Вы научитесь слышать, что говорят собственные числа графов, и видеть, в каких свойствах они себя проявляют. Познакомитесь с такими важными классами, как сильно регулярные и дистанционно регулярные графы. Узнаете, как операции на графах меняют их спектры. Эти классы графов применяются в теории кодирования, теории комбинаторных дизайнов, квантовой теории информации и даже в финансовой сфере. Кроме того, вы овладеете различными приёмами поиска спектров графов без вычисления корней характеристических полиномов. А ещё познакомитесь со славной традицией использовать граф Петерсена в качестве примера или контрпримера.

      1. Что линейная алгебра говорит о графах
      2. Собственные числа и векторы графов
      3. Спектры некоторых графов
      4. Спектры после операций над графами
      5. Сильно регулярные графы
      6. Дистанционно регулярные графы
      7. Практикум: считаем спектры
  3. Модуль 3. Графы и группы

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

      1. Группа автоморфизмов графа
      2. Транзитивные и симметричные графы
      3. Дистанционно-транзитивные графы
      4. Графы Кэли
      5. Схематическая связь между регулярными и транзитивными графами
      6. Граф Хэмминга: дистанционно-транзитивный граф Кэли
      7. Графы Джонсона: дистанционно-транзитивный граф, но не всегда граф Кэли
  4. Модуль 4. Спектральная теория графов

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

      1. Алгебраическая теория графов в примерах
      2. Матрица Лапласа
      3. Спектральная визуализация и кластеризация
      4. Теорема Перрона — Фробениуса и задача ранжирования
      5. Характеристический полином и изоспектральные графы
      6. О сплетении/чередовании собственных значений
      7. Граница весового распределения и о чём ещё говорят графы
  5. Модуль 5. Спектр Star графа и теория представлений симметрической группы

    Продолжаем погружение в исследования современной математики и знакомимся с наиболее продвинутым модулем этого курса. Основной объект исследования в этом модуле — Star граф — наиболее изучен в теории межкоммуникационных сетей. На его примере вы увидите связь между спектральной теорией и теорией представлений конечных групп. Научитесь работать со стандартными таблицами Юнга, представлением симметрической группы, элементами Юциса — Мёрфи, спектром Star графа и поймёте, как вычислять кратности собственных значений.

      1. Star граф и его основные свойства
      2. Перестановки и их классы сопряжённости
      3. Разбиения, цикловой тип перестановок и таблицы Юнга
      4. Представление конечной группы
      5. Представление симметрической группы через элементы Юциса — Мёрфи
      6. Элементы Юциса — Мёрфи и спектр Star графа
      7. Формула крюка и кратности собственных значений
  6. Модуль 6. Схемы отношений и когерентные конфигурации

    В заключительном модуле курса вы продолжите знакомство с самыми актуальными математическими вопросами и узнаете о таких понятиях, как схемы отношений и когерентные конфигурации. Однако при ближайшем рассмотрении быстро узнаете в них объекты, которые изучали ранее. А ещё вас ждёт встреча с алгебрами Боуза — Меснера и параметрами Крейна, новый взгляд на дистанционно регулярные графы и возвращение к тому самому графу Мура, про который всё ещё не известно, существует он или нет. Вы научитесь с помощью разных методов описывать один и тот же объект и визуализировать его (например, цветными табличками и треугольниками или набором матриц). И конечно, уже точно будете знать, как проводить эксперименты наиболее удобным способом. Кстати, граф Петерсена тут тоже будет, но в новом амплуа.

      1. Отношения как разбиения
      2. Схемы отношений на языке графов
      3. Через мир матриц к дистанционно регулярным графам
      4. Алгебра Боуза — Меснера
      5. Параметры Крейна, P- и Q-полиномиальность
      6. Возвращение к графу Мура на 3250 вершинах
      7. Когерентные конфигурации как обобщение схем отношений
      8. Алгебраическая теория графов: что дальше?

Спикеры

Елена Константинова

Елена
Константинова

Кандидат технических наук, доцент кафедры теоретической кибернетики
Евгения Сотникова

Евгения
Сотникова

Кандидат физико-математических наук, преподаватель кафедры теоретической кибернетики

Стоимость курса

  • 2 610
  • 3 000
Курс НГУ Алгебраическая теория графов

Выберите вариант оплаты

Заполните контактные данные

Похоже, произошла ошибка. Попробуйте отправить снова или перезагрузите страницу.

Нажимая на кнопку, я соглашаюсь на обработку персональных данных и с правилами пользования Платформой

Нажимая на кнопку, я соглашаюсь с публичной офертой и политикой обработки персональных данных

Спасибо!

Ваша заявка успешно отправлена

Часто задаваемые вопросы

  • Как пройти курс?

    Чтобы получить сертификат о прохождении курса, вам нужно набрать проходной балл по каждому из обязательных заданий: сдать тесты после каждого модуля и итоговый тест по курсу, выполнить практический проект по анализу данных. Видео, материалы для самостоятельного изучения и тренировочные упражнения помогут вам подготовиться к сдаче оцениваемых заданий.
  • Кто будет мне помогать в обучении на платформе?

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