– общее число простых (отдельных) операндов в программе.
Пример 1.1 Программа вычисления НОД (a,b)
if a=0 then
Begin
NOD:=b; exit;
end;
if b=0 then
Begin
NOD:=a; exit;
end;
while a >0 do
Begin
If (a mod b) = 0 then
Begin
NOD:= b; exit;
end;
r:= a mod b;
end;
| Операторы | Операнды | ||||
| Оператор | № | Количество | Операнд | № | Количество |
| ; | a | ||||
| := | b | ||||
| = | r | ||||
| > | NOD | ||||
| () или begin…end | |||||
| mod | |||||
| if…then | |||||
| While…do | |||||
| exit | |||||
| Всего: | = 9 | = 37 | Всего: | = 5 | = 22 |
Словарь: = 14
Длина: = 59
Пример 1.2 Программа вычисления суммы и произведения
Как в разделе «Масштабы бизнеса» определить потенциальный объем производства?
Program lab1;
Var
i, a, b, p, s:integer;
Begin
read (a, b);
for i:= a to b do
if i>5 then
Else
writeln (s, p);
End.
| Операторы | Операнды | ||||
| Оператор | № | Количество | Операнд | № | Количество |
| ; | a | ||||
| := | b | ||||
| readln | I | ||||
| writeln | p | ||||
| for | s | ||||
| if | |||||
| * | |||||
| + | |||||
| > | |||||
| begin | |||||
| Всего: | = 10 | = 18 | Всего: | = 8 | = 19 |
Словарь: = 18
Длина: = 37
Объем программы
, (1-3)
Потенциальный объем программы
, (1-4)
Уровень программы
, (1-5)
Время разработки программы
, (1-6)
где (число Страуда)
Гипотеза ошибок в программе
, (1-7)
МЕТРИКИ СЛОЖНОСТИ ПОТОКА УПРАВЛЕНИЯ ПРОГРАММ
Рисунок 2.1 — Управляющий граф программы
Цикломатическое число МакКейба
, (2-1)
где e – число дуг ориентированного графа программы,
v – число вершин ориентированного графа программы,
p – число компонент связности ориентированного графа программы.
р — количество дуг, которое необходимо добавить в граф, чтобы он стал сильносвязанным (две любые вершины графа взаимно достижимы).
В графе структурированной программы достаточно добавить дугу, соединяющую начальную и конечную вершины –. р = 1.
Для графа, приведенного на рисунке 2.1:
Z(G) = 15 – 12 + 2 = 5
Метрики Джилба
Абсолютная сложность программы (CL)
CL = количество операторов if в программе (2-2)
Источник: mydocx.ru
Объем программы
Важной характеристикой программы является ее размер. При переводе алгоритма с одного языка на другой размер программы будет меняться. Изучение этих изменений количественными методами требует, чтобы размер был измеримой величиной.
Анализ рынка перед запуском бизнеса. На что обратить внимание?
Кроме того, метрическая характеристика размера должна быть применима к широкому кругу языков без потери общности и объективности и, следовательно, не должна зависеть от набора символов, требуемых для представления алгоритма, то есть символов, практически используемых для записи операторов или имен операндов.
Решение этой проблемы связано с тем, что можно определить абсолютный минимум длины представления самого длинного оператора или имени операнда. Минимальная длина зависит только от числа элементов в словаре h. В общем случае log2 h есть минимальная длина (в битах) всей программы. Под битом здесь понимается логическая единица информации – символ, оператор, операнд – то, чем оперирует программист при создании программы.
Соответствующая метрическая характеристика размера любой реализации какого-либо алгоритма, называемая объемом V, может быть определена как
V = N log2 h (2.2)
где N = N1 + N2 -длина реализации; а h = h1 + h2 — ее словарь.
Очевидно, что если данный алгоритм переводится с одного языка на другой, то его объем меняется. Например, при переводе алгоритма с Паскаля в машинный код какой-либо конкретной машины его объем увеличится. С другой стороны, выражение алгоритма на более развитом языке, нежели тот, на котором он исходно написан, приведет к уменьшению его объема. Последняя возможность чрезвычайно важна и заслуживает специального рассмотрения.
Потенциальный объем V *
Выражение алгоритма в наиболее сжатой форме предполагает существование языка, в котором требуемая операция уже определена или реализована, возможно, в виде процедуры или подпрограммы. Для реализации алгоритма в таком языке требуются лишь имена операндов для его аргументов и результатов.
Обозначив соответствующие программные параметры возможно кратчайшей или наиболее сжатой формы алгоритма звездочками, из уравнения (2.1) получим, что минимальный (или потенциальный) объем равен
Но в минимальной форме ни операторы, ни операнды не требуют повторений, поэтому
Кроме того, известно минимально возможное число операторов h1 * для любого алгоритма. Каждый алгоритм должен включать один оператор для имени функции или процедуры и один в качестве символа присваивания или группировки, т.е. минимальное значение h1 * =2.
Уравнение теперь примет вид:
где h2 * должно представлять собой число различных входных и выходных параметров.
Из уравнения (3.4) следует, что потенциальный объем V * любого алгоритма не должен зависеть от языка, на котором он может быть выражен. Если h2 * расценивается как число единых по смыслу (неизбыточных) операндов, то V * оказывается наиболее полезной мерой содержания алгоритма.
Вернемся к примеру программы для алгоритма Евклида и определим его объем для программ на Паскале и СИ.
Паскаль: V =N * log2 h = 61* log2 18 = 254.4 бита.
СИ: V =N * log2 h = 55* log2 18 = 224.8 бита.
Чтобы найти потенциальный объем, нам нужно подсчитать число требуемых входных и выходных параметров. В данном случае это А, В и GCD, так что h2 * =3. Следовательно, потенциальный объем:
Как уже упоминалось выше, при переводе алгоритма с одного языка на другой его потенциальный объем V * не меняется, но действительный объем V увеличивается или уменьшается в зависимости от развитости рассматриваемых языков. Однако легко заметить, что не может быть гладкого перехода от выражения на потенциальном языке, для которого V = V * , к любому менее развитому языку, для которого V > V * . Такой резкий переход обусловлен тем, что для потенциального языка N * = h * , в то время как для всех других языков применяется уравнение длины и N > h.
Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:
Источник: studopedia.ru
Метрики сложности
Потенциальный объем – предельно сжатое представление программы. Он предполагает, что есть язык, в котором в виде процедур реализован любой необходимый алгоритм.
— уровень программы
— сложность программы
— оценка уровня программы
Инвариантно представлению алгоритма на определенном языке.
Еще один способ вычисления Наибольшего Общего Делителя (НОД): все НОД вычислены и хранятся в таблице:
| Оператор | Операнд |
| , | Table |
| : | A |
| := | B |
| [] | GCD |
Другая распространенная группа метрик программных проектов – показатели, характеризующие их сложность. Эти метрики используются главным образом для апостериорного анализа, однако могут применяться и на ранних стадиях работы при осуществлении проектирования.
Основная цель метрик сложности – выявить наиболее критичные участки программного проекта, которые являются потенциальными источниками ошибок и повышенных рисков на всех стадиях его жизненного цикла.
Сложность определяется количеством маршрутов.
Метрика позволяет определить:
1) Необходимое число тестов
2) Сложность сопровождения
3) Прогнозируемое число ошибок
Маршруты делятся на:
1) Вычислительные маршруты. На каждом маршруте фиксируются данные и для каждого данного выбираются максимальные, минимальные значения, значения в точках разрыва и 1-2 средних значения. Сложность ,
— число вычислительных маршрутов
— число данных в i-м маршруте
2) Маршруты принятия логических решений. Сложность оценивается числом ветвлний на каждом маршруте.
Общая сложность программы ,
где с1 и с2 – весовые коэффициенты, задаваемые в зависимости от назначения программы.
Для оценки структурной сложности при тестировании логики программы вводят упрощенные критерии тестирования, поскольку полное тестирование невозможно.
Критерий 1. Критерий минимального покрытия. Отобранные маршруты должны хотя бы один раз покрывать каждую вершину и каждую дугу графа управления программы. Повторная проверка дуг не требуется.
| М1: 1-2-4-8 |
| М2: 1-2-4-5-6-8 |
| М3: 1-3-4-5-7-8 |
жирным выделены ветвления
| М1: 1-2-14 |
| М2: 1-3-4-6-8-6-8-14 |
| М3: 1-3-5-7-9-10-11-12-13-14 |
| М4: 1-3-4-5-7-9-10-9-10-11-7-9-10-11-12-14 |
Критерий 2. Отбор базовых маршрутов, оцениваемых по цикломатическому числу графа (число McCabe)
Впервые графическое представление программ было предложено Маккейбом. Основной метрикой сложности он предлагает считать цикломатическую сложность графа программы, или, как ее еще называют, цикломатическое число Маккейба, характеризующее трудоемкость тестирования программы.
Одна из самых распространенных таких метрик – цикломатическая сложность, впервые предложенная Томасом МакКейбом (Thomas McCabe) в 1976 г. Данная метрика предназначена для оценивания сложности потока управления программы (control flow graph) и вычисляется на основе ориентированного графа, где вычислительные операторы или выражения представляются в виде узлов, а передача управления между узлами – в виде дуг.
Формула вычисления цикломатической сложности выглядит следующим образом:
где e – число ребер, n – число узлов, p – число соединенных компонент графа управляющей логики. Упрощенно формулу можно рассматривать как количество ветвлений, которые может проходить программа, увеличенное на единицу.
Метрика цикломатической сложности может быть рассчитана для модуля, метода и других структурных единиц программы.
В процессе анализа значений показателя для отдельных структурных элементов можно выявить элементы с высоким значением показателя (к примеру, нормальное значение показателя для метода – не выше 5–7), что свидетельствует о сложности их управляющей логики и, соответственно, высоких трудозатратах на разработку, тестирование и сопровождение.
Вычисление метрики в ходе реализации проекта (а при детальном проектировании оно возможно еще на этом этапе, не дожидаясь стадии кодирования) позволяет своевременно определить наиболее сложные, сопровождающиеся высокими рисками, структурные единицы и принять меры по устранению рисков за счет внесения коррективов.
В целом, метрики цикломатической сложности являются весьма хорошим способом своевременно зажечь перед разработчиками «красный свет», прекратить дальнейшее усложнение отдельных составляющих проекта и упростить их, предупредив вероятные проблемы с запутанным и нестабильным кодом в будущем.
где — число связных компонент графа, равно числу дуг, необходимых для того, чтобы граф стал максимально связным (граф, в котором любая вершина достижима из любой другой вершины)
(если нет тупиков)
Выбираются все линейно-независимые циклы и линейно-независимые ациклические маршруты. При этом каждый маршрут отличается от остальных хотя бы одной вершиной или дугой.
М1: 1 -2- 4 -8
М2: 1 -2- 4 — 5 -6-8
М3: 1 -3- 4 — 5 -7-8
М4: 1 -2- 4 — 5 -7-8
(М5): 1-3-4-8 – возможен, но не включается так как состоит из М1 и М3
(М6): 1-3-4-5-6-8 – возможен, но не включается так как состоит из М2 и М3
М1: 6- 8
М2: 9- 10
М3: 7-9- 10 — 11
М1-М3 – линейно-независимые циклические
М4: 1 -2-14
М5: 1 — 3 — 4 -6- 8 -14
М6: 1 — 3 -5-7-9- 10 — 11 — 12 -13-14
М7: 1 — 3 — 4 -5-7-9- 10 — 11 — 12 -13-14
М8: 1 — 3 — 4 -5-7-9- 10 — 11 — 12 -14
М4-М8 – линейно независимые ациклические
жирным – ветвления
Исследование графов реальных программ позволяют сделать замечания:
1) суммарная структурная сложность в основном определяется числом ветвлений и меньшей степени зависит от других структурных компонент графа
2) при фиксированном числе вершин в «широких» графах будет больше маршрутов, но сами маршруты будут короче, и наоборот, «узкие» графы имеют меньшее число, но более продолжительных маршрутов, в результате чего оценка сложности S2 меняется меньше чем цикломатическое число и больше коррелированна с общим числом графа. Для автоматического анализа графа по второму критерию можно использовать матрицы смежности, в которых элемент aij=1 если вершина j достижима из вершины j за одни шаг, и матрицы достижимости, в которых элемент dij, если вершина j достижима из i за любое число шагов.
n – число вершин
Основным средством анализа является матрица достижимости, в которой единичные диагональные элементы соответствуют циклам, а одинаковые строки образуют тела соответствующих циклов.
Успешно тестируются программы, у которых Z
Могут тестироваться программы с Z
Для программ с Z>30 успешное тестирование практически невозможно
Критерий 3.
Основанный на выделении полного состава базовых маршрутов выполнения программы. При отборе учитываются все ациклические маршруты и все входящие в них циклические маршруты. При этом для каждого ациклического маршрута должны учитываться все достижимые из них циклы.
учет только однократного повторения циклов, в действительности при тестировании необходимо проверить минимально возможное повторение циклов, максимальное значение повторения циклов и 1-2 промежуточных значения
Источник: studopedia.su