Методы программирования систем автоматизированного проектирования. Практическое занятие №1

1.

Министерство науки и высшего образования Российской Федерации
Казанский национальный исследовательский технический университет им. А.Н. Туполева - КАИ
Институт компьютерных технологий и защиты информации
МЕТОДЫ ПРОГРАММИРОВАНИЯ СИСТЕМ
АВТОМАТИЗИРОВАННОГО ПРОЕКТИРОВАНИЯ
Практическое занятие № 1
Структура и содержание курсовой работы.
Содержательная постановка задачи.

2.

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

3.

Основные понятия теории графов
Граф – абстрактный математический объект, который представляет собой совокупность двух конечных
множеств G(V,U) : множества вершин V и множества ребер U. При этом каждому ребру соответствует
пара вершин.
2
3
1
4
6
5
Граф
Две вершины являются смежными, если они соединены ребром. Два ребра называются смежными, если
имеют общую вершину.
Если некоторому ребру графа