Компьютерные науки
Математика и логика

Введение в теорию графов

Программа о базовом знакомстве с графами, их типами и операциями над ними. Включает анализ достижимости, разбиение на сильно связные подграфы, изучение путей и циклов, а также алгоритм Дейкстры для поиска кратчайших путей.
Студентов 3837 Выпускников 888 Для специалистов
690 ₽ 1 200 ₽
или любая сумма на ваше усмотрение
Вы можете оплатить любую сумму, чтобы поддержать наш проект и авторов программы. Объем услуг не зависит от размера вашей оплаты.
Темы:
Алгоритмы и сложность, Математика
Объем
36 час.
Длительность
30 дней
Нагрузка в неделю
9 час.
Формат обучения
Дистанционно (самостоятельно)
Описание Учебная программа посвящена основам теории графов и ее применению для решения дискретных задач. В рамках обучения изучаются способы представления графов, основные операции, многозначные отображения и транзитивные замыкания. Подробно анализируются различные типы графов, вопросы достижимости, поиск путей и циклов. Изучение начинается с основных понятий и затем переходит к алгоритму Дейкстры и методам разбиения графов на сильно связные подграфы. Практические алгоритмы надежно закрепляются через промежуточные тестирования.
Цели
  • Сформировать базовые знания о графах и способах их матричного и визуального представления.
  • Познакомить с основными операциями над графами и их свойствами.
  • Раскрыть методы анализа связности, поиска путей и применения алгоритма Дейкстры.
Чему я научусь?
  • Выполнять объединение, пересечение и другие базовые операции над графами.
  • Находить транзитивные замыкания и определять достижимость вершин в орграфах.
  • Разбивать графы на сильно связные подграфы матричными методами.
  • Применять алгоритм Дейкстры для поиска кратчайших путей.

Авторы

Волченская Тамара Викторовна
Волченская Тамара Викторовна
К.т.н., доцент, декан факультета Информационных технологий Вятского социально-экономического института (ВСЭИ).
Князьков Владимир Сергеевич
Князьков Владимир Сергеевич
Д.т.н., профессор кафедры кафедры ЭВМ Вятского государственного университета.
Чему я научусь?
  • Выполнять объединение, пересечение и другие базовые операции над графами.
  • Находить транзитивные замыкания и определять достижимость вершин в орграфах.
  • Разбивать графы на сильно связные подграфы матричными методами.
  • Применять алгоритм Дейкстры для поиска кратчайших путей.

Учебный план

№ Занятия
Экзамен экстерном Внимание! Экзамен экстерном не обязательный для сдачи. При желании вы можете его пройти, если хотите подтвердить свои знания по данному курсу без его изучения или поверить свои знания по нему. Экзамен экстерном можно сдать только один раз. 90 мин
1 Графы и способы их представления Приводятся начальные сведения о графах и основные понятия и определения такие как орграф, смешанный граф, дубликат... Приводятся начальные сведения о графах и основные понятия и определения такие как орграф, смешанный граф, дубликат графа дуга, петля, полустепени исхода и захода. Даются возможные способы представления графов. Цель лекции: Дать представление о графах и возможных способах их представления. ещё
Графы и способы их представления тест для курса Введение в теорию графов 45 мин
2 Операции над графами Приводятся основные операции над графами такие как объединение, пересечение, кольцевая сумма, удаление вершины, удаление ребра, замыкание... Приводятся основные операции над графами такие как объединение, пересечение, кольцевая сумма, удаление вершины, удаление ребра, замыкание и стягивание. Эти операции рассматриваются для представления графов матрицами смежности. Цель лекции: Дать представление об операциях над графами и возможных способах их представления в матричных структурах. ещё
Операции над графами тест для курса Введение в теорию графов 30 мин
3 Многозначные отображения и транзитивные замыкания Рассматриваются прямые и обратные отображения для орграфов различных порядков. Даются понятия прямого и обратного транзитивного замыкания... Рассматриваются прямые и обратные отображения для орграфов различных порядков. Даются понятия прямого и обратного транзитивного замыкания и способы нахождения транзитивных замыканий по матрице смежности. Цель лекции: Дать представление о многозначных отображениях и транзитивных замыканиях и способах их нахождения. ещё
Многозначные отображения и транзитивные замыкания тест для курса Введение в теорию графов 30 мин
4 Достижимость в графах Рассматриваются вопросы достижимости для орграфов и способы нахождения матриц достижимости и контрдостижимости. Рассматривается матричный способ нахождения... Рассматриваются вопросы достижимости для орграфов и способы нахождения матриц достижимости и контрдостижимости. Рассматривается матричный способ нахождения количества путей между любыми вершинами графа, а также нахождение множества вершин, входящих в путь между парой вершин. Цель лекции: Дать представление о достижимости и контрдостижимости и способах их нахождения ещё
Достижимость в графах тест для курса Введение в теорию графов 30 мин
5 Типы графов Рассматриваются типы графов такие как полный, симметрический, антисимметрический, двудольный, дерево, планарный и их возможные комбинации. Дается... Рассматриваются типы графов такие как полный, симметрический, антисимметрический, двудольный, дерево, планарный и их возможные комбинации. Дается теорема о двудольности графов. Цель лекции: Дать представление о типах графов и их свойствах ещё
Типы графов тест для курса Введение в теорию графов 35 мин
6 Виды подграфов Рассматриваются подграфы такие как остовный, порожденный и различные виды подграфов по связности. Цель лекции: Дать представление... Рассматриваются подграфы такие как остовный, порожденный и различные виды подграфов по связности. Цель лекции: Дать представление о видах подграфов и их свойствах. ещё
Виды подграфов тест для курса Введение в теорию графов 40 мин
7 Методы разбиения графа на максимальные сильно связные подграфы Рассматриваются методы разбиения графов на сильно связные подграфы: метод Мальгранжа и матричный метод. Цель лекции: Дать... Рассматриваются методы разбиения графов на сильно связные подграфы: метод Мальгранжа и матричный метод. Цель лекции: Дать представление о методах разбиения графов на сильно связные подграфы. ещё
Методы разбиения графа на максимальные сильно связные подграфы тест для курса Введение в теорию графов 15 мин
8 Пути и циклы в графах Рассматриваются взвешенные пути и маршруты в графах. Дается понятие веса и длины пути. Приводятся сведения о... Рассматриваются взвешенные пути и маршруты в графах. Дается понятие веса и длины пути. Приводятся сведения о орциклах и циклах и их особенностях. Цель лекции: Дать представление о путях и циклах в графах и весе и длине пути. ещё
Пути и циклы в графах тест для курса Введение в теорию графов 35 мин
9 Алгоритм Дейкстра поиска кратчайших путей в графе Рассматриваются метод Дейкстра нахождения кратчайших путей. Приводятся сведения о методике построения базы для взвешенного графа. Цель... Рассматриваются метод Дейкстра нахождения кратчайших путей. Приводятся сведения о методике построения базы для взвешенного графа. Цель лекции: Дать представление о методе нахождения кратчайших путей во взвешенном графе. ещё
Алгоритм Дейкстра поиска кратчайших путей в графе тест для курса Введение в теорию графов 25 мин
Тренировочный экзамен Внимание! Тренировочный экзамен экстерном не обязательный для сдачи. При желании вы можете его пройти, если хотите проверить свои знания курса перед сдачей экзамена. Тренировочный экзамен можно сдавать сколько угодно один раз. 90 мин
Экзамен 60 мин

Какой документ я получу?

Сертификат

Выдаётся автоматически после успешного завершения программы.

Удостоверение о повышении квалификации

Выдается при наличии среднего специального или высшего образования (необходимые документы).

Стоимость программы

690 ₽ 1 200 ₽
или любая сумма на ваше усмотрение
Вы можете оплатить любую сумму, чтобы поддержать наш проект и авторов программы. Объем услуг не зависит от размера вашей оплаты.
^