Давно и хорошо известно, как для произвольных значений y1, y2, … , yk и произвольных различных значений x1, x2, … , xk построить интерполяционный многочлен f(x) от одной переменной степени не более k-1, т.е. такой, что f(xi)= yi для i=1,…,k (воспользоваться интерполяционной формулой Лагранжа, или решить систему из k линейных уравнений с k неизвестными – коэффициентами многочлена). А что можно сделать, если известны значения yi в n точках x1, x2, … , xn , где n>k, но зато некоторые из этих значений yi (но не более t) неверны, при этом ничего неизвестно про величины ошибок, и, естественно, неизвестно какие значения ошибочны? Тогда естественной целью является построение «почти интерполяционного» многочлена f(x), т.е. такого, что f(xi)= yi как минимум в n-t точках xi. Если число ошибочных значений t меньше чем (n-k+1)/2, то такой многочлен единственный (так как разность двух решений имеет не менее чем n-2t корней, а ее степень не более k-1). Находить такой многочлен оказалось не так-то просто и эффективные алгоритмы были придуманы лишь в 60-ые годы прошлого века: Тренчем для «привычных» полей как вещественные или комплексные числа, и Берлекампом – для конечных полей. Если же число ошибочных значений t превосходит (n-k+1)/2, то, вообще говоря, получается список многочленов-решений. Очевидно, что если t < n-k+1, то число соответствующих многочленов конечно и не превышает C(n,k), так как многочлен степени не более k-1 однозначно задается своими значениями в любых k точках. Однако все попытки придумать непереборный алгоритм для t > (n-k+1)/2 более тридцати лет были безуспешны.
Решение пришло из computer science. Madhu Sudan в 1997 г. предложил следующий неожиданный алгоритм: провести через n точек (xi,yi) на плоскости алгебраическую кривую P(x,y) минимальной «взвешенной» степени (веса x и y в определении степени различны), а тогда все искомые многочлены f(x) содержатся среди «корней» P(x,y), рассматриваемого как многочлен от y с коэффициентами из кольца многочленов от x. Как часто бывает в математике, важнейший компонент алгоритма – поиск «корней», был уже известен, а нахождение P(x,y) Судан свел к решению системы линейных уравнений. В докладе будет рассказан алгоритм Судана и его улучшения, а также обсуждено обобщение этой задачи на случай многочленов от нескольких переменных.
