Добавил:
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

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

.pdf
Скачиваний:
21
Добавлен:
01.05.2014
Размер:
96.51 Кб
Скачать

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

(ЛЭТИ)

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

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

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

Выполнил студент группы 1382, ФКТИ

Пухкал И.

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

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

2

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

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

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

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

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

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

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

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

Структурная сложность программного модуля может быть определена путем расчета количества маршрутов M в программе и сложности каждого i-го маршрута ξi. Эти показатели в совокупности определяют сложность набора тестов для проверки программных модулей. Сложность программного модуля определяется по формуле:

ξ = ξi,

где ξii - количество условий-предикатов, определяющих i-й маршрут. Выделение маршрутов выполнения программы, минимально необходи-

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

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

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

Критерий 1

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

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

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

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

3

Рис. 1. Графовая модель программы

(1)1 - 2 - 4 - 10 - 13 - 14 - 15 - 16

(2)1 - 2 - 5 - 10 - 13 - 14 - 15 - 16

(3)1 - 2 - 5 - 11 - 13 - 14 - 15 - 16

(4)1 - 3 - 7 - 9 - 7 - 9 - 12 - 13 - 14 - 15 - 16

(5)1 - 3 - 6 - 8 - 12 - 13 - 14 - 15 - 16

(6)1 - 3 - 6 - 8 - 11 - 13 - 14 - 15 - 14 - 15 - 16

Подсчет количества ветвлений:

s1

= (1, 2, 15)

 

 

= 3

s2

= (1, 2,

5,

15)

 

= 4

s3

= (1, 2,

5,

15)

 

= 4

s4

= (1, 3,

9,

15,

9)

= 5

s5

= (1, 3,

8,

15)

 

= 4

s6

= (1, 3,

8,

15, 15)

= 5

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

Критерий 2

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

Z = Y − N + 2 ·

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

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

4

циклов. Величина Ω соответствует количеству связных компонент исходного графа или количеству дуг, необходимых для превращения исходного графа в максимально связный граф. Для большинства правильных (корректных) графов достаточно замыкания начальной и конечной вершин. В этом случае Ω = 1, т.е. требуется одна замыкающая дуга. Если граф (программа) составлены некорректно и в нем имеются тупиковые или висячие вершины, то для его превращения в максимально связный граф потребуется большее количество замыкающих дуг.

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

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

Количество связных компонент Ω = 1. В графе 22 дуги и 16 вершин.

Z = Y − N + 2 · Ω = 22 16 + 2 · 1 = 8

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

(1)7-9

(2)14-15

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

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

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

(5)1 - 2 - 5 - 11 - 13 - 14 - 15 - 16

(6)1 - 3 - 6 - 8 - 11 - 13 - 14 - 15 - 16

(7)1 - 3 - 6 - 8 - 12 - 13 - 14 - 15 - 16

(8)1 - 3 - 7 - 9 - 12 - 13 - 14 - 15 - 16

Подсчет количества ветвлений:

s1

= (9)

 

 

= 1

s2

= (15)

 

 

= 1

s3

= (1, 2, 15)

 

= 3

s4

= (1, 2,

5,

15) = 4

s5

= (1, 2,

5,

15) = 4

s6

= (1, 3,

8,

15)

= 4

s7

= (1, 3,

8,

15)

= 4

s8

= (1, 3,

9,

15)

= 4

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

2.2. Протоколы

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

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

6

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

Рис. 2. Графовая модель программы быстрой сортировки

Критерий 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 -

2

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

 

 

 

7

 

17

- 19

-

 

 

 

 

 

11

- 12

- 13 - 14 - 15 -

16

- 17 -

18 -

19 - 20 - 21 - 23 - 24 - 25

 

Подсчет количества ветвлений:

 

 

 

s1

= (3, 24, 3, 6, 14, 14, 16, 16, 19, 21, 24,

 

3, 6, 7, 14, 16, 19, 21,

24,

 

 

 

 

3, 6, 7, 9, 14, 16, 19, 21,

24,

 

 

 

3, 6, 7, 9, 14, 16, 19, 14, 16, 19, 21,

24) = 40

 

 

Структурная сложность: s = si =

40.

 

 

Критерий 2

Z = Y − N + 2 · Ω = 32 24 + 2 = 10

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

( 1) 13-14 ( 2) 15-16

( 3) 11-12-13-14-15-16-17-19 ( 4) 2-3-4-24

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

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

Подсчет количества ветвлений:

s1

=

(14)

 

 

 

 

= 1

s2

=

(16)

 

 

 

 

= 1

s3

=

( 3,

24)

 

 

 

= 2

s4

=

(14,

16, 19)

 

 

= 3

s5

=

( 3,

6,

7, 14, 16, 19,

21, 24)

= 8

s6

=

( 3,

6,

7, 14, 16, 19,

21, 24)

= 8

s7

=

( 3,

6,

7,

9, 14, 16,

19, 21, 24) = 8

s8

=

( 3,

6,

7,

9, 14, 16,

19, 21, 24) = 8

s9

=

( 3,

6,

7,

9, 14, 16,

19, 21, 24) = 8

s10

= ( 3,

6,

7,

9, 14, 16,

19, 21, 24) = 8

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

si = 55.

 

2.4.

 

Протоколы

 

 

 

-----

 

 

 

 

 

 

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 -

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

8

>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...

3 Заключение

9

3.Заключение

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