Псевдокод алгоритма
Рис.4.6. Псевдокод алгоритма самотестирующейся
программы для полинома f
Пусть матрицы А и В матрицы размером n´n определены над конечным полем F.
Время выполнения программы, реализующей чекер Фрейвалдса, составляет O(n2élog(1/k)ù).
Используя чекер Фрейвалдса, можно построить самотестирующуюся/ самокорректирующуюся программную пару для умножения матриц (рис.4.8 – 4.9).
Program C_F(A,B,C,k); {вход
A,B,C,k, выход («Норма»,«Сбой»)}
begin
for i=1 to élog(1/k)ù
do
begin
R:=random(F); {random - функция случайного равновероятного выбора 0-1-вектора размером (n´1) из F};
if C×R¹A×(B×R) then output «Сбой»;
end;
output «Норма»;
end.
Рис.4.7. Псевдокод алгоритма, реализующего чекер Фрейвалдса
Program S_K_multAB(A,B,k); {вход A,B,k, выход С}
begin
for i=1 to ¥ do
begin
A1:=random(F); {random - функция случайного равновероятного выбора матрицы размером (n´n) из F};
B1:=random(F); {random - функция случайного равновероятного выбора матрицы размером (n´n) из F};
A2:=A-A1;
B2:=B-B1;
C:=P(A1,B1)+P(A1,B2)+P(A2,B1)+P(A2,B2);
if C_F(A,B,C,k)=«Норма» then output С
and goto 1;
end;
1:end.
