5. Метод создания самотестирующейся расчетной программы с эффективным тестирующим модулем

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

В данном случае предлагается метод создания самотестирующихся программ для верификации расчетных программных модулей [КС2]. Данный метод не требует вычисления эталонных значений и является независимым от используемого при написании расчетной программы языка программирования, что существенно повышает оперативность исследования программы и точность оценки вероятности отсутствия в ней программных дефектов.

Пусть для функции Y = f (X) существует пара функций (g_c,h_c)^Yтаких, что:

Y = g_c (f (a₁), ..., f (a_c)),

X = h_c (a₁, ..., a_c).

Легко увидеть, что если значения a_iвыбраны изI_nв соответствии с распределениемD^p, тогда пара функций (g_c,h_c)^Yобеспечивает выполнение для функцииY = f (X) свойства случайной самосводимости. Пару функций (g_c,h_c)^Yбудем называтьST-парой функцийдля функцииY = f (X).

Предположим, что на ST-пару функций можно наложить некоторую совокупность ограничений на сложность программной реализации и время выполнения. В этом случае, пусть длина кода программ, реализующих функцииg_c иh_c , и время их выполнения составляет константный мультипликативный фактор от длины кода и времени выполнения программыP.

Предлагаемый метод верификации расчетной программы Pна основеST-пары функций для некоторого входного значения вектораX^*заключается в выполнении следующего алгоритма. (Всюду далее, если осуществляется случайный выбор значений, этот выбор выполняется в соответствии с распределением вероятностейD^p).

Алгоритм st

1. Определить множество такое, что, гдевыбраны случайно из входного подмножестваI_n.

2. Вызвать программу Pдля вычисления значения

3. Вызвать cраз программуPдля вычисления множества значений

4. Определить значения

5. Если , то принимается решение, что программаPкорректна на множестве значений входных параметровв противном случае данная программа является некорректной.

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

где t_iиt_x- время выполнения программыPпри входных значенияхa_iиX^*соответственно;

t_gи - время определения значения функцииg_cи множестваA^*соответственно:

T_P(X) - временная (не асимптотическая) сложность выполнения программыP;

K_gh (X,c) - коэффициент временной сложности программной реализации функцииg_cи определенияA^*по отношению к временной сложности программыP (по предположению он составляет константный мультипликативный фактор отT_P (X), а его значение меньше 1). Для традиционного вышеуказанного метода тестирования время выполнения и сравнения полученного результата с эталонным значением составляет:

,

где t_i^eиt_x^e- время определения эталонных значений функцииY =f (X) при значенияхa_iиX^*соответственно (в общем случае, не может быть меньше времени выполнения программы).

Следовательно, относительный выигрыш по оперативности предложенного метода верификации (по отношению к методу тестирования программ на основе ее эталонных значений):

Так как, коэффициент K_gh< 1, аc  2, то получаем относительный выигрыш по оперативности испытания расчетных программ указанного типа (обладающих свойством случайной самосводимости) более чем в 1.5 раза.