Вычисления над матрицами
Одной из первых работ в области вероятностных алгоритмов, которая, в конечном счете, явилась одной из основополагающей в области методологии самотестирования явилась работа Р.Фрейвалдса, написанная им еще в 1979 году. Он предложил следующий простой и элегантный чекер для задачи умножения матриц (рис.4.7).
Program P_S_T(P,e,b,x,f(x)); {вход P,e,b,(x1,f(x1)),...,xd+1,f(xd+1))),
выход («Норма»,«Сбой»)}
begin
for i=1 to O((1/k)log(1/b)) do
begin
x,t:=random(Zp); {random - функция случайного равновероятного выбора из множества вычетов по модулю р};
if
итерациях) then output «Сбой»;
end;
output «Норма»;
for j=0 to d do
begin
for i=1 to O(log(d/b)) do
begin
t:=random(Zp); {random - функция случайного равновероятного выбора из множества вычетов по модулю р};
if
итерациях) then output «Сбой»;
end;
end;
output «Норма»;
end.
