Вычисления над полиномами

Существует достаточно простой способ построения самокорректирующейся программы, который основывается на существовании следующего интерполяционного тождества, соответствующего значения функций между точками: для всех одномерных полиномов f степени не более d, для всех x,tÎF,

, где ai – различные элементы из F, ai=-1 и ai зависит от F,d и не зависит от x,t. Тогда самокорректирующаяся программа для вычисления f(

)=f(x1,...,xn) заключается в выполнении следующего алгоритма. Случайно и равновероятно выбирается

=(t1,...,tn) и выдается

. С вероятностью не менее 2/3 все вызовы программы будут возвращать корректные результаты и, следовательно, выход программы будет корректным. Рис.4.6 демонстрирует самотестирующуюся программу для полинома f.

В ряде работ было показано, как строить самотестирующиеся и самокорректирующиеся программы для задач сложения и умножения полиномов [BLR,GLR] и аппроксимирующие чекеры для полиномов [EKR] (см. далее).

Содержание раздела