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

Графы и алгоритмы

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

Авторы

Алексеев Владимир Евгеньевич
Алексеев Владимир Евгеньевич
Д.ф.-м.н., профессор кафедры математической логики и высшей алгебры Нижегородского государственного\nуниверситета.
Таланов Владимир Александрович
Таланов Владимир Александрович
К.ф.-м.н., доцент кафедры математической логики и высшей алгебры Нижегородского государственного\nуниверситета.
Чему я научусь?
  • Анализировать структуру графов, находить маршруты, циклы и связные компоненты.
  • Применять алгоритмы поиска в ширину и глубину для обхода структур данных.
  • Оценивать трудоемкость и вычислительную сложность алгоритмов на графах.
  • Решать задачи на поиск кратчайших путей, построение оптимальных каркасов и нахождение потоков.

Учебный план

№ Занятия
Экзамен экстерном Внимание! Экзамен экстерном не обязательный для сдачи. При желании вы можете его пройти, если хотите подтвердить свои знания по данному курсу без его изучения или поверить свои знания по нему. Экзамен экстерном можно сдать только один раз. 90 мин
1 Начальные понятия теории графов Начальные понятия теории графов. Определение графа. Графы и бинарные отношения. Откуда берутся графы. Число графов. Смежность,... Начальные понятия теории графов. Определение графа. Графы и бинарные отношения. Откуда берутся графы. Число графов. Смежность, инцидентность, степени. Некоторые специальные графы. Графы и матрицы. Взвешенные графы. Изоморфизм. Инварианты. Операции над графами. Локальные операции. Подграфы. Алгебраические операции. ещё
Начальные понятия теории графов тест для курса Графы и алгоритмы 20 мин
2 Маршруты, связность, расстояния Маршруты, пути, циклы. Связность и компоненты. Метрические характеристики графов. Маршруты и связность в орграфах. Эйлеровы пути... Маршруты, пути, циклы. Связность и компоненты. Метрические характеристики графов. Маршруты и связность в орграфах. Эйлеровы пути и циклы. ещё
Маршруты, связность, расстояния тест для курса Графы и алгоритмы 20 мин
3 Важнейшие классы графов Деревья. Центр дерева. Корневые деревья. Каркасы. Двудольные графы. Планарные графы.
Важнейшие классы графов тест для курса Графы и алгоритмы 25 мин
4 Поиск в ширину Поиск в ширину. Процедура поиска в ширину. BFS-дерево и вычисление расстояний.
Поиск в ширину тест для курса Графы и алгоритмы 15 мин
5 Поиск в глубину Процедура поиска в глубину. DFS-дерево. Глубинная нумерация. Построение каркаса. Шарниры.
Поиск в глубину тест для курса Графы и алгоритмы 15 мин
6 Блоки Блоки. Двусвязность. Блоки и BC-дерево. Выявление блоков.
7 Пространство циклов графа Пространство подграфов. Квазициклы. Фундаментальные циклы. Построение базы циклов. Рационализация.
Пространство циклов графа тест для курса Графы и алгоритмы 25 мин
8 Эйлеровы и гамильтоновы циклы Построение эйлерова цикла. Гамильтоновы пути и циклы.
9 Независимые множества, клики, вершинные покрытия. Независимые множества, клики, вершинные покрытия . Три задачи. Стратегия перебора для задачи о независимом множестве. Эвристики... Независимые множества, клики, вершинные покрытия . Три задачи. Стратегия перебора для задачи о независимом множестве. Эвристики для задачи о независимом множестве. Приближенный алгоритм для задачи о вершинном покрытии. Перебор максимальных независимых множеств. ещё
Независимые множества, клики, вершинные покрытия. тест для курса Графы и алгоритмы 25 мин
10 Раскраски Раскраска вершин. Переборный алгоритм для раскраски. Раскраска ребер.
11 Рационализация переборных алгоритмов Рационализация поиска наибольшего независимого множества. Хордальные графы. Рационализация алгоритма для задачи о раскраске вершин.
Рационализация переборных алгоритмов тест для курса Графы и алгоритмы 20 мин
12 Паросочетания Паросочетания и реберные покрытия. Метод увеличивающих путей. Паросочетания в двудольных графах. Паросочетания в произвольных графах (алгоритм... Паросочетания и реберные покрытия. Метод увеличивающих путей. Паросочетания в двудольных графах. Паросочетания в произвольных графах (алгоритм Эдмондса). ещё
13 Оптимальные каркасы Задача об оптимальном каркасе. Алгоритм Прима. Алгоритм Крускала.
Оптимальные каркасы тест для курса Графы и алгоритмы 25 мин
14 Жадные алгоритмы и матроиды Матроиды. Теорема Радо-Эдмондса. Взвешенные паросочетания.
15 Кратчайшие пути В этой лекции рассматриваются связные графы с неотрицательными весами ребер. А также кратчайшие пути, геодезическое дерево... В этой лекции рассматриваются связные графы с неотрицательными весами ребер. А также кратчайшие пути, геодезическое дерево и алгоритм Дейкстры. ещё
16 Потоки В этой лекции будем рассматривать ориентированные графы без петель и кратных ребер: задачу о максимальном потоке... В этой лекции будем рассматривать ориентированные графы без петель и кратных ребер: задачу о максимальном потоке и метод увеличивающих путей. ещё
Потоки тест для курса Графы и алгоритмы 30 мин
Тренировочный экзамен Внимание! Тренировочный экзамен экстерном не обязательный для сдачи. При желании вы можете его пройти, если хотите проверить свои знания курса перед сдачей экзамена. Тренировочный экзамен можно сдавать сколько угодно один раз. 90 мин
Экзамен 60 мин

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

Сертификат

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

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

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

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

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