2.2 Задание на лабораторную работу

В соответствии с разработанным в первой работе Техническим Заданием реализовать программный продукт. Язык программирования Java. Отчет по лабораторной работе должен содержать следующие программные документы:

• Руководство программиста (ГОСТ 19504-79);

• Описание программы (ГОСТ 19.402-78);

• Текст программы (ГОСТ 19.401-78);

• Программа и методика испытаний (ГОСТ 19.301-79).

2.3 Список контрольных вопросов

1. Виды программных документов?

2. Содержание документа «Руководство программиста (ГОСТ 19504-79)».

3. Содержание документа «Описание программы (ГОСТ 19.402-78)»;

4. Содержание документа «Текст программы (ГОСТ 19.401-78)»;

5. Содержание документа «Программа и методика испытаний (ГОСТ 19.301-79)».

3. Расчет метрик холстеда. Лабораторная работа № 3

Цель работы: Изучение основ метрической теории программ Холстеда, расчет количественных характеристик для программных модулей.

3.1 Описание метрик Холстеда

Метрики Холстеда предлагают разумный подход к решению следующих задач:

• предсказание условий, необходимых для программирования по предложенным проектам;

• определение норм первоначальных ошибок;

• количественная оценка языков программирования и эффекта модульности;

• обоснование метода измерения различий между программами, написанными специалистами разного уровня.

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

В основе вычисляемых свойств алгоритма лежат следующие характеристики:

• n1 - число различных операторов данной реализации;

• n2 - число различных операндов данной реализации;

• N1 - общее число всех операторов;

• N2 - общее число всех операндов;

- n2*- число различных входных и выходных операндов (в случае, если операндом является агрегатная структура данных, например, массив, то n2* следует увеличить на ее размерность. Так для одномерного массива на 1, для матрицы на 2 и т.п.).

На основании приведенных выше характеристик вычисляются:

• словарь n = n1 + n2;

• длина реализации N = N1 + N2.

Метрики Холстеда включают следующие характеристики.

1. Длина программы: N'= n1 * log2(n1) + n2 * log2(n2)

Если программа состоит из нескольких модулей (m - число модулей), то для каждого модуля определяется n1 среднее (n1_ср) и n2 среднее (n2_ср). В этом случае длина программы

N' = m*(n1_ср * log2(n1_cp) + n2_cp * log2(n2_cp))

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

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

N ≈ N'

2) Объем программы: V = N * log2(n)

Для двоичной кодировки словаря программы потребуется log2(n) двоичных разрядов. Тогда V интерпретируется как объем программы в битах. Объем зависит от языка программирования, на котором реализован алгоритм.

3) Потенциальный (минимальный) объем: V* = (2+ n2*) * log2(2+ n2*)

Минимально возможный объем предполагает существование языка, в котором действия, выполняемые исследуемой программой, уже определены или реализованы, возможно, в виде процедуры или функции. Тогда, такая «идеальная» программа должна содержать 2 оператора (один для вызова процедуры, второй - для присвоения результата) и список из n2* фактических параметров.

4) Cоотношение между операциями и операндами (зависимость числа операндов n2 от числа операций n1):

n2 = A * n1 + B , где

A = n2* /(n2* +2) * log2(n2*/2),

B = n2* - 2 * A

5) Уровень программы: L = V*/V

где V* - потенциальный объем, V - объем программы.

L=1 для потенциального языка, в котором присутствует любая процедура, которая могла бы понадобиться (число таких процедур должно быть близко к бесконечности).

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

Альтернативное определение уровня L: L' = (n1*) * n2/(n1*N2), где n1*=2

6) Интеллектуальное содержание: I = L' * V или: I = 2 * n2/(n1 * N2)*N * log2(n)

Интеллектуальное содержание - мера того, "сколько было сказано в программе". Не зависит от языка программирования, а зависит от сложности задачи.

Интеллектуальное содержание должно быть близко к значению потенциального объема в пределах 10%. Существенные отличия говорят о несовершенстве реализации алгоритма.

7) Работа по программированию. Это умственная работа, затрачиваемая на превращение заранее разработанного алгоритма в фактическую реализацию на языке программирования. Кодирование алгоритма можно свести к двоичному поиску в словаре n, выполненное N раз, т.е.

V = N * log2(n)

Кроме того, работа будет обратно пропорцинальна сложности, т.е уровню программы. Тогда общее число элементарных мысленных различий, требуемых для порождения программы: E=V/L или E = V ²/ V*,

Так как квадрат суммы не меньше суммы квадратов, то правильное разбиение на модули уменьшает работу по программированию:

E = E1 + E2 + E3 + ...

8) Приближенное время программирования(кодирования алгоритма): T = E/S, где S = 18 моментов (различий)/сек - постоянная Страуда.

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

Альтернативное определение времени Т: Т'= n1*N2*N*log2(n)/(2*S*n2). Если заменить в этой формуле N на N' , то получим время, не зависящее от реализации

Т'= n1*N2* (n1 * log2(n1) + n2 * log2(n))*log2(n)/(2*S*n2)

9) Уровень языка.

Согласно метрике 5 можно выявить полезное соот­ношение между уровнем программы L и ее объемом V. Для любого алгоритма, который переводится с одного язы­ка реализации иа другой, с увеличением объема уровень уменьшается в той же пропорции. В результате произве­дение L на V равняется потенциальному объему V* дан­ного алгоритма.

С другой стороны, если язык реализации остается од­ним и тем же, а разрешено менять сам алгоритм, имеется другое, но похожее соотношение. В этом случае с увеличением потенциального объема V* уровень программы L, уменьшается в том же отношении. Следовательно, произведение L иа V* остается неизменным для любого языка. Это произведение, называемое уровнем языка, обозначает­ся через λ и записывается в виде

λ=LV* или λ= L * L* V

Естественные языки имеют высокое значение уровня, машинный код – низкое.

10) Уравнение ошибок.

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

число переданных ошибок в программе: B = V/E0, или В=Е^2/3/Е0 ,

где E0 = 3000 и расчитано для высокоуровневого естественного языка (например, английского).