Практическая работа №5 «Построение графов алгоритмов, определение сложности алгоритмов»

Цель: Формирование умений и навыков по представлению алгоритмов в виде управляющего графа.

Задачи:

5. научиться строить управляющие графы

6. научиться определять сложность алгоритма по управляющему графу.

Оснащение урока:

· Техническое: ПК, сканер, принтер, интерактивная доска

· Методическое: инструкционная карта, задание для самостоятельного выполнения

· Программное: Windows XP, Microsoft Office 2007.

Теоретические сведения: С целью анализа алгоритм (программу) удобно представлять управляющим графом (родственное понятие - схема алгоритма).

Рисунок 8 – граф

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

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

Для определения средней сложности необходимо оценить частоты выбора ветвей.

Под частотой ветви понимается отношение числа выполнений программы (алгоритма), при которых исполнились операторы, принадлежащие данной ветви, к общему числу исполнений этой программы.

Средняя сложность программы (ее алгоритма) вычисляется как сумма произведений весов ветвей на их частоты.

Если в программе имеются вложенные ветвления, то можно предложить метод оценки, основанный на оценке частоты, с которой встречаются определенные комбинации входных данных. Рассмотрим его.

Ход работы

1. В рабочей тетрадке запишите тему, цель и задачи работы.

2. Приступите к выполнению упражнений.

3. Выполните задание в соответствии с вариантом.

4. Ответьте на контрольные вопросы.

5. Оформите отчет основные определения, рассуждения по решению задач, ответ; вывод по работе

6. Сделайте вывод по работе.

Упражнение1 – Управляющий граф содержит 10 вершин с весом {3, 5, 1,4, 3, 4, 6, 8, 5, 3}. Вершина 3 (вес равен 1) соответствует вычислению условия в операторе if; вершины 4, 5, 6 входят в часть then, вершины 7, 8 входят в часть else (рис. 9)

4 3 4 Then 3 5 1   Else 5 3 6 8

Рисунок 9 – Управляющий граф к упражнению 1

Решение: имеется две ветви с весом 3+5+1+4+3+4+5+3 = 28 и 3+5+1+6+8+5+3 = 31; сложность равна 31.

Упражнение 2 – Тот же граф, что и в примере 1, но вершина 8 соответствует вызову процедуры, имеющей сложность 2V + 1.

В этом случае функция сложности равна max (28, 2V+24 ) = 24+max(4, 2V) = 24 + 2 max ( 2, V ).

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

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

Упражнение 3 - Процедура содержит цикл

for i := 1 to x do

<тело цикла>,

где x - входная переменная, x [1, 100].

Решение: Тело цикла выполняется x раз, худший случай реализуется при x =100.

Если предположить равновероятность различных значений x, то среднее количество выполнений тела цикла равно (1/100)(1+2+3+ ...+100) = 50,5.

Упражнение 4 - Процедура содержит вложенные циклы:

for i := 1 to x do

for j := i to x do

<тело цикла>;

входная переменная xÎ[1, 5].

Решение: Тело цикла выполняется x + (x-1)+(х-2)+ ...+ 1 = x (х+1)/2 раз.

Верхняя граница сложности = max = (x (х+1)/2) = 13.

Среднее значение сложности подсчитать несколько труднее.

Снова положим, что все 5 возможных значений x равновероятны.

Тогда среднее значение сложности равно:

Задания для самостоятельного выполнения

Построить управляющий граф и определить сложность алгоритма.

1. Управляющий граф содержит 9 вершин с весом {4, 3, 6, 8, 2, 2, 1, 5, 6}.

Вершина 2 (вес равен 3) соответствует вычислению условия в операторе if; вершины 3, 4, 5 входят в часть then, вершина 6 входят в часть else .

Вершина 8 (вес равен 5) соответствует вычислению условия в операторе if; вершины 9 входят в часть then.

2. Тот же граф, что и в задании 1, но вершина 5 соответствует вызову процедуры, имеющей сложность 3V, а вершина 8 имеет сложность 2V-1.

3. Процедура содержит цикл

for i := 1 to x do a:= a*(a+1);

Контрольные вопросы

1. Что называется сложность графа?

2. Что называется управляющим графом?

3. Какие управляющие графы вы знаете?