О.В. Казарин, В.Ю. Скиба
4
торого функция
f
(
x
) может быть выражена через вычислимую функ-
цию
F
от
x
,
a
1
, ...,
a
c
и
f
(
a
1
), ...,
f
(
a
c
) и алгоритм
A
2
, работающий за
время, пропорциональное
nO
(1), посредством которого по данному
x
можно вычислить
a
1
, ...,
a
c
, где каждое
a
i
выбирается случайно в со-
ответствии с распределением
.
p
D
Перейдем к рассмотрению вычислительных самотестирующихся и
самокорректирующихся примитивов.
Элементарная арифметика, целочисленная арифметика и
арифметика многократной точности.
Известные элементарные ариф-
метические операции: сложения, вычитания, умножения, деления и воз-
ведения в степень, исходя из их фундаментальной математической
сущности, обладают свойством рандомизированной самосводимости.
Следовательно, для них можно построить самотестирующиеся/само-
корректирующиеся программные пары. Это можно показать на примере
операции сложения.
Пусть необходимо вычислить функцию
f
(
a
+
b
), которая реализу-
ется программой
P
(
a
,
b
). Для этого необходимо: выбрать случайным
образом
a
1
и
b
1
и вычислить
a
2
=
a – a
1
и
b
2
=
b – b
1
. Получение значе-
ния функции
f
(
a
+
b
) =
f
((
a
1
+
a
2
) + (
b
1
+
b
2
)) следует из корректного
выполнения оракульной программы (
T
f
,
C
f
) с 2-кратным вызовом
программы
P
(
a
,
b
), т. е.
P
(
a
1
,
a
2
) +
P
(
b
1
,
b
2
). Алгоритм вычисления
f
(
a
+
b
) выполняется при декомпозиции слагаемых на два компонен-
та. Однако, декомпозиция
a
и
b
при вычислении функции
f
(
a
+
b
)
может осуществляться и на большее число компонентов, что приве-
дет к гораздо большему количеству вызовов программы
P
(
a
,
b
), но в
то же время позволит значительно снизить вероятность ошибки при
выполнении программы
P
(
a
,
b
). Аналогично строятся самотестиру-
ющиеся/самокорректирующиеся программные пары для операций
умножения и возведения в степень, вычитания и деления, а также
операций целочисленной арифметики и арифметики многократной
точности [3].
Тригонометрические и гиперболические функции.
Пусть необ-
ходимо вычислить тригонометрическую функцию
sin .
Выберем случайным образом угол и вычислим угол такой, что
.
Из формул сложения для тригонометрических функций известно,
что
sin
sin cos cos sin ,
а исходя из основного тригоно-
метрического тождества
2
2
sin cos 1,
можно получить
cos
2
1 sin .
Тогда
2
2
sin
sin 1 sin
1 sin sin .
Таким образом, чтобы получить самотестирующуюся программу
для вычисления функции
sin ,
необходимо вызвать 6 раз программу
вычисления синуса для углов
и
, где
=
+
.
