Свойство случайной самосводимости

Свойство случайной самосводимости. Пусть x In и пусть c > 1 есть целое число. Свойство случайной самосводимости заключается в том, что существует алгоритм A1, работающий за время пропорциональное nO(1), посредством которого функция f(x) может быть выражена через вычислимую функцию F от x, a1,...,ac и f(a1),...,f(ac) и алгоритм A2, работающий за время пропорциональное nO(1), посредством которого по данному x можно вычислить a1,...,ac, где каждое ai является случайно распределенным над In в соответствии с Dp.

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

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

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

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

Y = gc (f (a1),..., f (ac)),
X = hc (a1,..., ac).

Легко увидеть, что если значения ai выбраны из In в соответствии с распределением Dp, тогда пара функций (gc, hc)Y обеспечивает выполнение для функции Y = f (X) свойства случайной самосводимости. Пару функций (gc, hc)Y будем называть STпарой функций для функции Y = f (X).

Метод верификации расчетных программ на основе STпары функций.

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


Ведете ли вы блог?

Да
Нет
Планирую


Результаты опроса

Новостной блок