Метрики сложности программ

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

При оценке сложности выделяют 3 группы метрик: 1. Метрики размера .2. Метрики сложности потоков управления программы. 3.Метрики сложности потоков данных программы.

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

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

Т.о., оценка размера программы – оценка по номинальной шкале.

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

Основу метрики Холстеда составляют четыре измеряемые характеристики программы:

η₁ – число уникальных, различных операторов программы, включая символы-разделители, знаки операций, имена процедур и функций (словарь операций).

η₂ – число уникальных, различных операндов программы (словарь операндов).

N₁ – общее количество операторов в программе.

N₂ – общее количество операндов в программе.

Опираясь на эти характеристики, получаемые непосредственно при анализе исходных текстов программ, М.Холстед вводит следующие оценки:

словарь программы η = η₁ + η₂ (1)

длину программы N = N₁+N₂ (2)

объем программы V = Nlog₂ η (3)

Далее М.Холстед вводит η^* - теоретический словарь программы, т.е.словарный запас, необходимый для написания программы с учетом того, что необходимая функция уже реализована в данном языке и, следовательно, программа сводится к вызову этой функции.

Например: согласно М.Холстеду, возможное осуществление процедуры выделения простого числа могло бы выглядеть так:

CALL SIMPLE (X,Y),

где Y- массив численных значений, содержащих искомое число X.

Теоретический словарь в данном случае будет состоять из

η^* : { CALL, SIMPLE (…)}, η₁^*=2

η₂^* : {X,Y}, η₂^* = 2,

а его длина

η^* = η₁^* + η_2*, будет равна 4. (4)

Используя η^*, Холстед вводит характеристику V^*:

V^* = η^*log₂ η^*, (5)

с помощью которой описывается потенциальный объем программы, соответствующий максимально компактному тексту программы, реализующей данный алгоритм.

Задание:

Для одной из своих программ рассчитать:

1) Реальную длину программы, (N).

2) Теоретическую длину программы, (η^*)

3) Реальный объем программы, (V)

4) Потенциальный объем программы(V^*).

КОНТРОЛЬНЫЕ ВОПРОСЫ

1. Перечислите наиболее известные методы оценки метрических характеристик качества программных продуктов.

2. Перечислите основные требования к критериям качества ПО.

3. Перечислите разновидности метрик, шкал. Поясните принципы двух основных подходов в исследовании метрик.

4. Как с помощью метрик сложности программ определить длину и объём программы?

ЛИТЕРАТУРА

1. Липаев В.В. Качество программного обеспечения. – М.: Финансы и статистика, 1983.

2. Холстед М. Начала науки программирования. - М.: Финансы и статистика, 1981.