Время выполнения программы

Рис.4.8. Псевдокод алгоритма самокорректирующейся

программы умножения матриц

Время выполнения программы S_K_multAB составляет О(M(n)+n2log(1/k)), где M(n) – время выполнения программы умножения матриц размером n´n [BLR].

Самотестирующаяся программа для умножения матриц строится достаточно просто.

Program S_T_multAB(A,B,k); {вход A,B,k, выход («Норма»,«Сбой»)}

begin

for i=1 to O(log(1/k))¥ do

begin

A:=random(F); {random - функция случайного равновероятного и независимого выбора матрицы размером (n´n) из F};

B:=random(F); {random - функция случайного равновероятного и независимого выбора матрицы размером (n´n) из F};

C:=P(A,B);

if C_F(A,B,C,1/4)=«Норма» then output 0 and goto 1;

if C_F(A,B,C,1/4)=«Сбой» then output 1 and goto 1;

end;

1:end.