Метрики Холстеда

Обозначим через η₁ число уникальных различных операторов программы, включая символы-разделители, знаки операций и имена процедур и функций (словарь операторов),η₂ – число уникальных имён операндов (словарь операндов), η=η₁+η₂ (словарь модуля). Тогда N=η₁*log₂(η₁)+η₂*log₂(η₂) – информационная длина программного модуля, V=N*log₂(η) – информационный объём модуля. Пусть N₁ – число строк (операторов), N₂ – число операндов. Тогда L=2*η₂/(η_1*N₂) – уровень записи модуля (показатель антиконцентрированности вычислений в модуле).

Метрика Холстеда сложности. E=V/L – сложность модуля по Холстеду.

Язык	λсредн	dλ (абс. откл. от λсредн)
Английский	2.16	0.74
Fortran	1.14	0.81
PL-1	1.53	0.92
Assembler	0.88	0.42

Метрика Холстеда оценки языков программирования. Оценка языка программирования λ=L²*V. Она характеризует уровень языка программирования.

Метрика Холстеда «интеллектуальности». С помощью этой метрики Холстед собирался измерять интеллектуальное содержание алгоритма, инвариантное по отношению к языкам реализации. I=L*V.

Метрика Холстеда количества ошибок. Количество ошибок B=N/3000, где N – количество строк в программе.

54. Метрика МакКейба. Пример. Метрика «граничных значений». Пример.

Метрика МакКейба. Пусть имеется представление программы в виде ориентированного графа G(V, E), где V – вершины, соответствующие операторам, E – дуги, соответствующие переходам. Обозначим через p количество дуг, которые необходимо добавить для преобразования рассматриваемого графа в сильносвязанный (т.е. граф, любые две вершины которого взаимно достижимы). Для графов корректных программ, т.е. графов, не имеющих недостижимых от точки входа участков и «висячих» точек входа и выхода сильносвязанный граф получается путём замыкания дугой вершины, обозначающей конец программы, на вершину, обозначающую точку входа в эту программу. Тогда Z=E-V+2*p – метрика МакКейба.

Пример. V=8, E=10, p=1. Z=10-8+2*1=4.

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

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

Для получения значения метрики необходимо:

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

2. число вершин, образующих подграф G’, равно скорректированной сложности вершины отбора;

3. каждая принимающая вершина имеет скорректированную сложность равную единице;

4. скорректированная сложность конечной принимающей вершины всего графа равна нулю;

5. сумма скорректированных сложностей всех вершин графа G даёт абсолютную сложность модуля S_A;

6. относительная сложность согласно метрике «граничных значений» вычисляется по формуле S_O=1-(V-1)/S_A.

Пример.

Основные понятия оптимизации. Необходимые и достаточные условия локальных экстремумов.

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

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

Выбор оптимального решения или сравнения двух альтернативных решений проводится с помощью некоторой зависимой величины (функции), которая определяется проектными параметрами. Эта величина называется целевой функцией или критерием качества. В процессе решения задачи оптимизации должны быть найдены такие значения проектных параметров, при которых целевая функция имеет максимум (или минимум). Таким образом, целевая функция — это глобальный критерий оптимальности в математических моделях, с помощью которых описываются инженерные задачи. Целевую функцию можно записать в виде: u=f(x₁, x₂, …, x_n).

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

В случае одного проектного параметра целевая функция является функцией одной переменной и ее графики — некоторая кривая на плоскости. При двух – целевая функция является функцией двух переменных и ее графиком есть поверхность.

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

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

Точка x₀ называется точкой локального минимума функции f(x), если при любом сколь угодно малом h>0,выполняются условия: f(x₀-h) > f(x₀) и f(x₀+h) > f(x₀), т.е для любой точки x в окрестности x₀ выполняется условие f(x) > f(x₀).

Точка x₀ называется точкой локального максимума функции f(x), если при любом сколь угодно малом h > 0,выполняются условия: f(x₀-h) < f(x₀) и f(x₀+h) < f(x₀), т.е для любой точки x в окрестности x₀ выполняется условие: f(x) < f(x₀).

Точки максимума и минимума функции называются точками экстремума.

Необходимое условие экстремума. Если функция y = f(x) в точке х₀ дифференцируема и х₀ – точка экстремума, то производная f’(x₀) равна нулю.

Точка, в которой производная равна нулю, называется стационарной. Стационарная точка не всегда является точкой экстремума функции.

Точка, в которой производная функции равна нулю или не существует, называется критической точкой.

Достаточное условие экстремума. Пусть функция f(x) непрерывна на отрезке [a, b], а точка x₀ из этого отрезка является критической. Тогда:

1. если f’(x) < 0 на интервале (a, x₀) и f’(x) > 0 на интервале (x₀, b), то точка x₀ – точка минимума функции f(x);

2. если f’(x) > 0 на интервале (a, x₀) и f’(x) < 0 на интервале (x₀, b), то точка x₀ – точка максимума функции f(x).

Докажем первое утверждение теоремы. Так как f’(x) < 0 на (a, x₀) и f(x) непрерывна в точке x₀, то f(x) убывает на (a, x₀), и для любого x принадлежащего (a,x₀) выполняется условие f(x) > f(x₀). Так как f’(x) > 0 на (x₀, b) и f(x) непрерывна в точке x₀, то f(x) возрастает на (x₀, b), и для любого x принадлежащего (x₀, b) выполняется условие f(x) > f(x0). В результате получается, что при любом x не равном x₀ из (a, b) выполняется нера­венство f(x)>f(x₀), то есть точка x₀–точка минимума f(x). Второе утверждение теоремы доказывается аналогично.