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

Графы и их применение

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

Авторы

Костюкова Нина Ивановна
Костюкова Нина Ивановна
Кандидат технических наук, доцент кафедры "Программирование" механико-математического факультета Новосибирского государственного университета.
Чему я научусь?
  • Моделировать реальные ситуации и процессы с помощью графов и орграфов.
  • Использовать деревья для решения задач вероятности и анализа структуры данных.
  • Применять методы сетевого планирования для оптимизации бизнес-процессов.
  • Рассчитывать потоки в сетях и решать задачи о паросочетаниях.

Учебный план

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

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

Сертификат

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

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

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

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

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