Математика и логика

Практикум по теории графов

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

Учебный план

№ Занятия
1 Логика предикатов. Графы, общие определения Кванторы всеобщности и существования. Связанные переменные. Область действия квантора. Эквивалентные соотношения в логике предикатов. Чистая логика... Кванторы всеобщности и существования. Связанные переменные. Область действия квантора. Эквивалентные соотношения в логике предикатов. Чистая логика предикатов и прикладные логики предикатов. Понятия графа. Классификация графов: по наличию ориентирования ребер (неориентированный и ориентированный графы), по наличию кратности ребер (простой граф и мультиграф). Отношение смежности между вершинами, матрица смежности. Отношение инцидентности между вершинами и ребрами. Степень вершины. Изолированные вершины, висячие вершины. Пустой граф, полный граф. ещё
2 Теория графов. Основные понятия Матрица смежности, степень вершины. Подграф и часть графа. Звезда вершины графа. Полный граф. Клика. Максимальный и... Матрица смежности, степень вершины. Подграф и часть графа. Звезда вершины графа. Полный граф. Клика. Максимальный и минимальный (относительно некторого свойства) подграф. Изоморфизм графов. Неориентированные графы. Путь, цепь, простая цепь, цикл. Связанные вершины. Связный граф. Компоненты связности. Длина пути. Расстояние между вершинами в связном графе. Аксиомы метрики (расстояния). ещё
3 Теория графов. Основные понятия (продолжение) Радиус графа, центры графа. Эйлеров обход. Задача о кенигсбергских мостах. Алгоритм построения эйлерова цикла. Задача о... Радиус графа, центры графа. Эйлеров обход. Задача о кенигсбергских мостах. Алгоритм построения эйлерова цикла. Задача о гамильтоновом обходе (задача коммивояжера). Ориентированные графы (орграфы). Ориентированный путь, ориентированный цикл. Достижимость. Виды связности: сильная связность, односторонняя связность, слабая связность. Компонента сильной связности. Конденсация, граф конденсации. Ациклический граф. Источники и стоки. Топологическая сортировка. ещё
4 Деревья. Оптимизационные задачи на графах. Задача о кратчайшем пути Неориентированные деревья. Ориентированные деревья. Применение деревьев: классификация, представление формул, бинарное дерево поиска. Оптимизационные задачи на графах.... Неориентированные деревья. Ориентированные деревья. Применение деревьев: классификация, представление формул, бинарное дерево поиска. Оптимизационные задачи на графах. Взвешенные (нагруженные) графы. Задача о кратчайшем пути в неориентированном графе без весов. Ранжирование вершин. Задача о кратчайшем пути в взвешенном графе. Алгоритм Дейкстры. ещё
5 Оптимизационные задачи на графах. Сетевое планирование. Потоки в сетях Сетевой график. Задача поиска максимальных путей в графе. Понятия раннего срока и позднего срока. Критический путь.... Сетевой график. Задача поиска максимальных путей в графе. Понятия раннего срока и позднего срока. Критический путь. Виды резерва: полный резерв, свободный резерв, независимый резерв. Потоки в сетях. Понятие потока, величина потока. Закон Кирхгофа. Увеличивающаяся цепь. ещё
6 Оптимизационные задачи на графах. Алгоритм поиска увеличивающей цепи Алгоритм поиска увеличивающей цепи. Разрезы. Пропускная способность разреза.
7 Матричные методы анализа графов. Графы и бинарные отношения Матричные методы анализа графов. Степень матрицы смежности графа. Сумма степеней матрицы смежности, достижимость и связность. Транзитивное... Матричные методы анализа графов. Степень матрицы смежности графа. Сумма степеней матрицы смежности, достижимость и связность. Транзитивное замыкание. Графы и бинарные отношения. Отношения эквивалентности и отношения порядка в терминах графов. Матричные методы анализа мультиграфов. Двудольные графы. Задача о раскраске графа. ещё
8 Курсовая работа Цель работы: Необходимо составить по три тестовых задания к каждой лекции.

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

Сертификат

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

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

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

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

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