Характеристика качества программного средства:

Классификация видов сложности программных продуктов и их краткая характеристика.

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

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

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

Динамическая (или вычислительная) сложность характеризует процесс выполнения программы и имеет три взаимосвязанных составляющих:

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

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

Система метрик Холстеда для оценивания характеристик программ. Измеримые параметры программ. Оценки длины и объема программы. Потенциальный объем программы. Причины несоответствия оценок теоретическим значениям.

Одной из интересных интегральных систем оценивания не только сложности, но и качества программ в целом является система метрик, предложенная Холстедом.

Оценивание качества разработки программ на основе метрик Холстеда.

Измеримые свойства алгоритмов

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

В состав измеримых свойств любого представления алгоритма (или программы) могут быть включены следующие метрические характеристики

₁ - число простых (уникальных) операторов появляющихся в данной реализации
₂ - число простых (уникальных) операндов появляющихся в данной реализации
N₁- общее число всех операторов появляющихся в данной реализации
N₂ - общее число всех операндов появляющихся в данной реализации
f₁_j-число вхождений j-го оператора где j = 123 ... ₁
f₂_j-число вхождений j-го операнда где j = 123 ... ₂.

Отправляясь от этих основных метрических характеристик для программы, удобно определить:

словарь   = ₁+ ₂

и длину N N = N₁ + N₂

реализации программы.

В соответствии с данными определениями должны выполняться следующие три соотношения

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

Программа на Паскале

Программа на Си

Function GCD (a,b: integer): integer;

Label L1, L2;

Var G, R : integer;

Begin

If (a=0) then

L1: begin GCD := b; return end;

If (b=0) then

Begin GCD := a; return end;

L2: G := a/b;

R := a - b*G;

If (R=0) GOTO L1;

a :=b; b:=R; GOTO L2;

End.

Int gcd ( int a, int b )

{ int G;

int R;

if (!a) return (b);

if(!b) return (a);

while(1)

{ G = a/b;

R = a – b*G;

If (R)

{ a = b; b = R; }

else return (b);

}

Результаты подсчета числа типов операторов и операндов и их общего количества сведены в таблицу 2 для программы на Паскале и в таблицу 3 для программы на Си. При подсчете использовались следующие соображения

В отношении классификации операторов интуитивно ясно что символы 

= - знак присваивания

= - знак равенства (или знак присваивания в программе на Си)

-- - знак вычитания

/ - знак деления

* - знак умножения

соответствуют их обычному определению

Пара состоящая из открывающих и закрывающих скобок ( ) { } классифицируется как один оператор группировки Поскольку пара слов Begin  End выполняет такую же группирующую функцию она классифицируется как такой же оператор Метки L1 и L2 - не переменные и не константы поэтому они не являются операндами Следовательно, они должны быть операторами или их составными частями Комбинация GO TO и метки L1 определяет ход выполнения программы путем задания для нее счетчика или указателя кода эта комбинация классифицируется как один оператор Неиспользуемая метка трактуется всего лишь как комментарий поэтому ее присутствие в программе необязательно Ограничитель  (точка с запятой) также определяет ход выполнения программы (простым продвижением счетчика) что позволяет классифицировать точку с запятой как оператор По той же причине все управляющие структуры например IF, IF ... THEN ... ELSE, DO ... WHILE, классифицируются как операторы Указатель вызова функции или оператор процедуры также являются операторами. Помимо того, возможность задания помеченных участков и введение новых функций устраняют какие-либо ограничения на рост величины ₁(числа типов операторов) которые в противном случае могли бы быть наложены набором команд машины или разработкой языка

Таблица 2

Оператор	I	F_1i	Операнд	J	F_2j
;	1	14	GCD	1	2
:=	2	6	G	2	2
=	3	3	R	3	3
() или begin end	4	6	A	4	5
If	5	3	B	5	6
/	6	1	0	6	3
*	7	1
-	8	1
GOTO L1	9	1
GOTO L2	10	1
Function GCD	11	1
Return	12	2

Соответственно, измеримые метрики программы на Паскале будут равны

η₁= 12; N₁ = 40; η₂ = 6; N₂ = 21; η = 18; N = N₁ + N₂= 61; 58,53

Таблица 3

Оператор	I	F_1i	Операнд	J	F_2j
;	1	9	GCD	1	1
=	2	4	G	2	2
,	3	1	R	3	3
() или {}	4	11	A	4	5
If	5	3	B	5	6
/	6	1	1	6	1
*	7	1
-	8	1
!	9	2
Int GCD	10	1
Return	11	3

Соответственно, измеримые метрики программы на Си будут равны

η₁= 11; N₁ = 37; η₂ = 6; N₂ = 18; η = 17; N = N₁ + N₂= 55; 53,56

Длина программы

С использованием рассмотренных программных параметров можно получить уравнение для оценки количественного соотношения между длиной программы N и словарем  Это уравнение на первый взгляд может показаться несколько неожиданным Однако тщательный анализ доказывает его правомерность кроме этого его правильность подтверждается экспериментально

Строка длины N образуемая символами входящими в словарь из  символов должна подчиняться ряду ограничений Требование согласно которому каждый символ словаря должен появиться по меньшей мере хотя бы один раз гарантирует выполнение условия

 N

что определяет нижнюю границу для N выраженную через 

Найдем верхнюю границу для N Разобьем строку длины N на подстроки длины  Разделенная таким образом программа для ЭВМ оказывается состоящей из N/ операторов длины  каждый Теперь если мы потребуем чтобы строка не содержала двух одинаковых подстрок длины  то появится искомая верхняя граница

Требование отсутствия дубликатов подстрок длины  является весьма обоснованным в программах для ЭВМ в которых экономия выражений приводит к тому что общему подвыражению дается отдельное имя поэтому его надо вычислять только один раз Следовательно если общее подвыражение длины  необходимо программе более одного раза присваивание его отдельному операнду увеличит  (число типов операторов) на единицу

Число возможных комбинаций из  элементов взятых по  за раз хорошо известно из школьного курса математики и составляет

N  ^⁺¹

Если учесть что операторы и операнды как правило, чередуются, то можно получить другое соотношение

N  ₁^¹₂^²

Верхняя граница для этого неравенства должна включать не только упорядоченное множество из N элементов представляющих исследуемую программу но и его всевозможные подмножества Семейство всевозможных подмножеств из N элементов содержит 2^N элементов. Следовательно мы можем приравнять число возможных комбинаций из операторов и операндов (равное числу подстрок N/) числу подмножеств из N элементов и выразить длину реализации алгоритма через его словарь Из уравнения

2^N = ₁^¹₂^²

получаем

N = log₂ (₁^¹₂^²)

или

N = log₂₁^¹ + log₂ ₂^²
Это дает нам уравнение оценки длины

₁ log₂₁ + ₂ log₂₂ (2.1)

В этом выражении символ N снабдили  для того чтобы отличать вычисленную (теоретическую) оценку длины от значения N полученного в результате непосредственного измерения (опытной длины) Эта оценка соответствует основным концепциям теории информации, по которым частота использования операторов и операндов в программе пропорциональна двоичному логарифму количества их типов. Выражение (2.1) представляет собой идеализированную аппроксимацию измеренной длины N=N₁+N₂, справедливую для программ, не содержащих несовершенств (стилистических ошибок) [1]. Экспериментальные исследования ряда авторов на представительной группе программ показали, что для стилистически корректных программ отклонения в оценке их теоретической длины от опытной не превышают (10-15)% .

<предыдущая страница | следующая страница>