logo
Лабор

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

CALL SIMPLE (X,Y),

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

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

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

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

а его длина

η* = η1* + η2*, будет равна 4. (4)

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

V* = η*log2 η*, (5)

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

Задание:

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

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

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

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

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

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

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

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

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

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

ЛИТЕРАТУРА

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

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

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

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

ЦЕЛЬ РАБОТЫ: оценить сложность программных продуктов с точки зрения оценки сложности потока управления, используя теорию графов, как методическую основу оценки.

1. ОСНОВНЫЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ

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

И в том и в другом случае стало традиционным представление программы в виде управляющего ориентированного графа G = (V, E), где V – вершины, которые соответствуют операторам, а E – дуги, которые соответствуют переходам.

Неупорядоченная пара вершин называется ребром, упорядоченная пара - дугой.

Граф, содержащий только ребра, называется неориентированным; граф, содержащий только дуги - ориентированным (или орграфом).

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

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

Вершины, соединенные ребром или дугой, называются смежными.

Ребра, имеющие общую вершину, тоже называются смежными.

Ребро (или дуга) и любая из его вершин называются инцидентными.

Принято говорить, что ребро (u, v) соединяет вершины u и v, а дуга (u, v) начинается в вершине u и кончается в вершине v.