Основная часть. ПМ 03: Участие в интеграции программных модулей

Введение.

КУРСОВАЯ РАБОТА

ПМ 03: Участие в интеграции программных модулей

Тема: Модели систем. Графы

Руководитель курсовой работы:

Маградзе Т.А.

___________________________

(подпись)

«___» ________________201__г

Студент(-ка):

ПО 3.11

(группа)

Савинов А.А.

(Ф.И.О.)

Саратов, 2014 г.

Содержание

Введение…………………………………………………………………...3

1. Основная часть………………………………………………………..4

2. Анализ алгоритма……………………………………………………10

3. Спецификация задачи…………………………………………….….13

3.1 Входные и выходные данные…………………………………13

3.2 Используемые процедуры………………………………….….13

4. Программа на языке Turbo Pascal..……………………………….…14

4.1 Листинг программы…………..………….………………….…14

4.2 Контрольный пример для тестирования №1….……………...25

4.3 Контрольный пример для тестирования №2….……………...26

4.4 Руководство пользователя…………………………………….27

5. Результаты тестирования…………………………………………….28

Заключение…………………………………………………………….…33

Список используемой литературы……………………………………...34

Приложение А…………………………………………………………….35

Термин «граф» впервые появился в работах венгерского математика Д.Кенига в 1936 году, хотя ряд задач по теории графов решался еще Л.Эйлером в XVIII веке.

Графы встречаются в сотнях разных задач, и алгоритмы обработки гра­фов очень важны.

Существует множество разработанных алгоритмов для решения различных задач из самых разных областей человеческой деятельности. Формулировка задачи описывает, каким требованиям должно удовлетворять решение задачи, а алгоритм, решающий эту задачу, находит объект, этим требованиям удовлетворяющий.

В этой работе, не будем давать четкого определения алгоритма, а попытаемся проанализировать и изучить алгоритм поиска в ширину в графе.

Поиском по заданному аргументу называется алгоритм, определяющий соответствие ключа с заданным аргументом. Алгоритм поиска в ширину может быть использован для просмотра созданного графа, чтобы узнать состав информационных вершин для последующего поиска.

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

Если заданная информационная вершина найдена, то происходит вывод об успешном окончании поиска, вывод времени поиска и времени поиска ключа.

В данной работе: 7 рисунков, 1 программа, 1 приложение, 35 листов.

Ключевые слова: граф, алгоритм, поиск, ширина, программа, аргумент, элемент, массив, очередь, память, время, сравнение.

Цель работы: Исследовать эффективность алгоритма поиска в графе в ширину.

Результат работы программы: количество сравнений элемента с ключом поиска и время, за которое был найден элемент по данному алгоритму поиска.

Область применение данного алгоритма может быть разнообразна, например, при построении карт местности: вершины графа – города, связи – дороги.

Очевидно, что наиболее понятный и полезный для человека способ представления графа — изображение графа на плоскости в виде точек и соединяющих их линий — будет совершенно бес­полезным, если мы захотим решать с помощью ЭВМ задачи, свя­занные с графами. Выбор соответствующей структуры данных для представления графов имеет принципиальное влияние на эффективность алгоритмов, поэтому мы подробнее остановимся на этой проблеме. Мы покажем несколько различных способов представления и кратко разберем их основные достоинства и не­достатки.

Будем рассматривать как ориентированные, так и нео­риентированные графы. Граф будем всегда обозначать G = (V,E), где V обозначает множество вершин, а Е — мно­жество ребер, причем Е Í V X V для ориентированного графа и ЕÍ{{х,у}: х,у Î V ۸ х¹у} для неориентированного графа. Будем также использовать обозначения |V| = n и |Е| = m.

В теории графов классическим способом представления гра­фа служит матрица инциденций. Это матрица А с n строками, соответствующими вершинам, и m столбцами, соответствующими ребрам. Для ориентированного графа столбец, соответствующий дуге <x, y> Î E, содержит —1 в строке, соответствующей вер­шине х, 1 в строке, соответствующей вершине у, и нули во всех остальных строках (петлю, т. е. дугу вида <x, x>, удобно пред­ставлять иным значением в строке х, например, 2).

В случае неориентированного графа столбец, соответствующий ребру {х,у}, содержит 1 в строках, соответствующих х и у, и нули в остальных строках. Это проиллюстрировано на рисунке 1. С ал­горитмической точки зрения матрица инциденций является, ве­роятно, самым худшим способом представления графа, который только можно себе представить. Во-первых, он требует nm ячеек памяти, причем большинство этих ячеек вообще занято нулями. Неудобен также доступ к информации. Ответ на элементарные вопросы типа «существует ли дуга <x,y>?», «к каким вершинам ведут ребра из х?» требует в худшем случае перебора всех столб­цов матрицы, а, следовательно, m шагов.

Лучшим способом представления графа является матрица смежности, определяемая как матрица В = [b•j] размера nхm,

<1,2>

<1,3>

<3,2>

<3,4>

<5,4>

<5,6>

<6,5>

(а) 1 –1 –1 0 0 0 0 0

2 1 0 1 0 0 0 0

Дата добавления: 2015-08-31