Лабораторная работа №5 / LAB_5

Санкт-Петербургский государственный электротехнический университет

Кафедра МОЭВМ

Отчет по лабораторной работе №5.

Анализ структурной сложности графовых моделей программ.

Выполнил:

Студент гр.3351

Сергеев М.В.

Санкт-Петербург

2007г.

1. Постановка задачи

Выполнить оценивание структурной сложности двух программ с помощью критериев:

• Минимального покрытия дуг графа;

• Выбора маршрутов на основе цикломатического числа графа.

Варианты программ:

• Программа с заданной преподавателем структурой управляющего графа;

• Программа из 1-ой лабораторной работы (управляющий граф составить самостоятельно).

Оцениваемые характеристики структурной сложности:

• Число учитываемых маршрутов проверки программы для заданного критерия;

• Цикломатическое число;

• Суммарное число ветвлений по всем маршрутам.

2. Заданная программа

Критерий 1

Минимальный набор путей:

(1) 1 - 2 - 4 - 10 - 13 - 14 - 15 – 16 s1 = 3

(2) 1 - 2 - 5 - 10 - 13 - 14 - 15 – 16 s2 = 4

(3) 1 - 2 - 5 - 11 - 13 - 14 - 15 – 16 s3 = 4

(4) 1 - 3 - 7 - 9 - 7 - 9 - 12 - 13 - 14 - 15 – 16 s4 = 5

(5) 1 - 3 - 6 - 8 - 12 - 13 - 14 - 15 – 16 s5 = 4

(6) 1 - 3 - 6 - 8 - 11 - 13 - 14 - 15 - 14 - 15 – 16 s6 = 5

Структурная сложность: = 3+4+4+5+4+5 = 25.

Критерий 2

Z = Y - N + 2P = 22 - 16 + 21 = 8

Линейно-независимые циклы:

(1) 7-9 s1 = 1

(2) 14-15 s2 = 1

Линейно-независимые ациклические маршруты

(3) 1 - 2 - 4 - 10 - 13 - 14 - 15 – 16 s3 = 3

(4) 1 - 2 - 5 - 10 - 13 - 14 - 15 – 16 s4 = 4

(5) 1 - 2 - 5 - 11 - 13 - 14 - 15 – 16 s5 = 4

(6) 1 - 3 - 6 - 8 - 11 - 13 - 14 - 15 – 16 s6 = 4

(7) 1 - 3 - 6 - 8 - 12 - 13 - 14 - 15 – 16 s7 = 4

(8) 1 - 3 - 7 - 9 - 12 - 13 - 14 - 15 – 16 s8 = 4

Структурная сложность: = 1+1+3+4+4+4+4+4=25

Протокол

Min ways....

-------------- Path #1 ---------------

-> 1 -> 2 -> 4 -> 10 -> 13 -> 14 -> 15 -> 14 -> 15 -> 16

2 Выполнение работы 5

---------Press a key to continue ---------

-------------- Path #2 ---------------

-> 1 -> 3 -> 6 -> 8 -> 11 -> 13 -> 14 -> 15 -> 16

---------Press a key to continue ---------

-------------- Path #3 ---------------

-> 1 -> 2 -> 5 -> 10 -> 13 -> 14 -> 15 -> 16

---------Press a key to continue ---------

-------------- Path #4 ---------------

-> 1 -> 2 -> 5 -> 11 -> 13 -> 14 -> 15 -> 16

---------Press a key to continue ---------

-------------- Path #5 ---------------

-> 1 -> 3 -> 7 -> 9 -> 7 -> 9 -> 12 -> 13 -> 14 -> 15 -> 16

---------Press a key to continue ---------

-------------- Path #6 ---------------

-> 1 -> 3 -> 6 -> 8 -> 12 -> 13 -> 14 -> 15 -> 16

---------Press a key to continue ---------

Complexity = 25

Z ways....

-------------- Path #1 ---------------

-> 7 -> 9 -> 7

---------Press a key to continue ---------

-------------- Path #2 ---------------

-> 14 -> 15 -> 14

---------Press a key to continue ---------

-------------- Path #1 ---------------

-> 1 -> 2 -> 4 -> 10 -> 13 -> 14 -> 15 -> 16

---------Press a key to continue ---------

-------------- Path #2 ---------------

-> 1 -> 2 -> 5 -> 10 -> 13 -> 14 -> 15 -> 16

---------Press a key to continue ---------

-------------- Path #3 ---------------

-> 1 -> 2 -> 5 -> 11 -> 13 -> 14 -> 15 -> 16

---------Press a key to continue ---------

-------------- Path #4 ---------------

-> 1 -> 3 -> 6 -> 8 -> 11 -> 13 -> 14 -> 15 -> 16

---------Press a key to continue ---------

-------------- Path #5 ---------------

-> 1 -> 3 -> 6 -> 8 -> 12 -> 13 -> 14 -> 15 -> 16

---------Press a key to continue ---------

-------------- Path #6 ---------------

-> 1 -> 3 -> 7 -> 9 -> 12 -> 13 -> 14 -> 15 -> 16

---------Press a key to continue ---------

Complexity = 25

3. Быстрая сортировка

Граф программы быстрой сортировки:

Критерий 1

Минимальный набор путей:

(1) 1 - 2 - 3 - 4 – 24 -

- 2 - 3 - 5 - 6 - 11 - 12 - 13 - 14 - 13 - 14 - 15 - 16 - 15 - 16- 17 - 19 - 20 - 21 - 22 – 24 -

- 2 - 3 - 5 - 6 - 7 - 8 - 11 - 12 - 13 - 14 - 15 - 16 -17 - 19 - 20 - 21 - 23 - 24 -

- 2 - 3 - 5 - 6 - 7 - 9 - 11 - 12 - 13 - 14 - 15 - 16 -17 - 19 - 20 - 21 - 23 - 24 -

- 2 - 3 - 5 - 6 - 7 - 9 - 10 - 11 - 12 - 13 - 14 - 15 - 16 -17 - 19 -11 - 12 - 13 - 14 - 15 - 16 - 17 - 18 - 19 - 20 - 21 - 23 - 24 – 25

s1 = 40

Структурная сложность: = 40.

Критерий 2

Z = Y - N + 2P = 32 - 25 + 21 = 9

Линейно-независимые циклы:

( 1) 13-14 s1 =1

( 2) 15-16 s2 =1

( 3) 11-12-13-14-15-16-17-19 s3 =3

( 4) 2-3-4-24 s4 =2

( 5) 2-3-5-6-7-8-11-12-13-14-15-16-17-19-20-21-22-24 s5 =8

( 6) 2-3-5-6-7-8-11-12-13-14-15-16-17-19-20-21-23-24 s6 =8

( 7) 2-3-5-6-7-8-9-11-12-13-14-15-16-17-19-20-21-22-24 s7 =9

( 8) 2-3-5-6-7-8-9-11-12-13-14-15-16-17-19-20-21-23-24 s8 =9

( 9) 2-3-5-6-7-8-9-10-11-12-13-14-15-16-17-19-20-21-22-24 s9 =9

(10) 2-3-5-6-7-8-9-10-11-12-13-14-15-16-17-19-20-21-23-24 s10 =9

Структурная сложность: = 1+1+3+2+8+8+9+9+9+9=59.

Протокол

-----

Min ways....

-------------- Path #1 ---------------

-> 1 -> 2 -> 3 -> 4 -> 24 -> 2 -> 3 -> 5 -> 6 -> 7 -> 8 -> 11 -> 12 -> 13 -> 14

-> 13 -> 14 -> 15 -> 16 -> 15 -> 16 -> 17 -> 19 -> 11 -> 12 -> 13 -> 14 -> 15 -

> 16 -> 17 -> 19 -> 20 -> 21 -> 22 -> 24 -> 2 -> 3 -> 5 -> 6 -> 11 -> 12 -> 13 -

> 14 -> 15 -> 16 -> 17 -> 19 -> 20 -> 21 -> 23 -> 24 -> 2 -> 3 -> 5 -> 6 -> 7 ->

9 -> 10 -> 11 -> 12 -> 13 -> 14 -> 15 -> 16 -> 17 -> 19 -> 20 -> 21 -> 22 -> 24

-> 2 -> 3 -> 5 -> 6 -> 7 -> 9 -> 11 -> 12 -> 13 -> 14 -> 15 -> 16 -> 17 -> 19 -

> 20 -> 21 -> 22 -> 24 -> 25

---------Press a key to continue ---------

Complexity = 40

Press a key...

Z ways....

-------------- Path #1 ---------------

-> 13 -> 14 -> 13

---------Press a key to continue ---------

-------------- Path #2 ---------------

-> 15 -> 16 -> 15

---------Press a key to continue ---------

-------------- Path #3 ---------------

-> 11 -> 12 -> 13 -> 14 -> 15 -> 16 -> 17 -> 19 -> 11

---------Press a key to continue ---------

-------------- Path #4 ---------------

-> 2 -> 3 -> 4 -> 24 -> 2

---------Press a key to continue ---------

-------------- Path #1 ---------------

-> 1 -> 2 -> 3 -> 4 -> 24 -> 25

---------Press a key to continue ---------

-------------- Path #2 ---------------

-> 1 -> 2 -> 3 -> 5 -> 6 -> 7 -> 8 -> 11 -> 12 -> 13 -> 14 -> 15 -> 16 -> 17 ->

19 -> 20 -> 21 -> 22 -> 24 -> 25

---------Press a key to continue ---------

-------------- Path #3 ---------------

-> 1 -> 2 -> 3 -> 5 -> 6 -> 7 -> 8 -> 11 -> 12 -> 13 -> 14 -> 15 -> 16 -> 17 ->

19 -> 20 -> 21 -> 23 -> 24 -> 25

---------Press a key to continue ---------

-------------- Path #4 ---------------

-> 1 -> 2 -> 3 -> 5 -> 6 -> 7 -> 9 -> 10 -> 11 -> 12 -> 13 -> 14 -> 15 -> 16 ->

17 -> 19 -> 20 -> 21 -> 22 -> 24 -> 25

---------Press a key to continue ---------

-------------- Path #5 ---------------

-> 1 -> 2 -> 3 -> 5 -> 6 -> 7 -> 9 -> 11 -> 12 -> 13 -> 14 -> 15 -> 16 -> 17 ->

19 -> 20 -> 21 -> 22 -> 24 -> 25

---------Press a key to continue ---------

-------------- Path #6 ---------------

-> 1 -> 2 -> 3 -> 5 -> 6 -> 11 -> 12 -> 13 -> 14 -> 15 -> 16 -> 17 -> 19 -> 20

-> 21 -> 22 -> 24 -> 25

---------Press a key to continue ---------

Complexity = 50

Press a key...

4. Выводы

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

6