С.А. Абрамов - Лекции о сложности алгоритмов (pdf) (1123764), страница 45
Текст из файла (страница 45)
можно запасти константы, нужные в вычислениях). Вычислительный раздел программы состоит изприсваиваний видаpi := pk , k < i,(D.)иpi := pk ⋄ pl ,k, l < i, ⋄ ∈ {+, ·}.(D.)Значение индекса в левой части будем считать номером шага, предполагая, что все используемые в программе значения индекса заполняют целиком некоторый отрезок множества целых чисел.
Шагвида (D.) будем называть аддитивным или мультипликативнымв зависимости от вида ⋄ (+ или ·). Шаг вида (D.) будем называтьнейтральным. Каждую программу такого вида, вычисляющую значение (D.) и обладающую тем свойством, что, не меняя ее вычислительного раздела, а лишь варьируя правые части в (D.), мы можемполучать значения любых полиномов степени n в любых точках, мыназовем n-программой.Наша цель состоит в доказательстве того, что каким бы ни было неотрицательное целое n, любая n-программа содержит не менее n аддитивных и не менее n мультипликативных шагов.Если в n-программе изменить шаги с номерами 0, −1, ..., −n − 1,подставляя в правые части присваиваний (D.) вместо чисел x, a0 ,a1 , ..., an их буквенные обозначения, и интерпретировать +, · в вычислительном разделе как знаки полиномиальных операций, то в результате выполнения n-программы значениями p1 , p2 , ...
будут полиномы (т. е. буквенные выражения, «картинки»). В частности, будетпостроен полином an x n + ... + a1 x + a0 , причем an , ..., a1 , a0 и x являются переменными этого полинома (степень по x которого равна n, а степень, например, по an равна 1). При таком подходе каждаяn-программа вычисления значения полинома превращается в программу построения полиномаP(x, a0 , a1 , ..., an ) = an x n + ... + a1 x + a0 ∈ Q[x, a0 , a1 , ..., an ](D.)с помощью операций сложения и умножения, исходя из переменныхx, a0 , a1 , ..., an . Программу обсуждаемого вида, содержащую в под-Оптимальность схемы Горнераготовительном разделе формализованные указанным способом шаги с номерами −n − 1, −n, ..., 0, назовем формальной n-программой.Если мы докажем, что любая формальная n-программа содержит неменее n аддитивных и не менее n мультипликативных шагов, то поставленная цель будет достигнута.Лемма D..
Пусть n ¾ 0, S — формальная n-программа, t — положительное целое, не превосходящее наибольшего значения индекса переменной p в S. Пусть среди шагов S с номерами 1, 2, ..., t нет аддитивных, в которых по крайней мере один операнд правой частизависит от an (имеет положительную степень по an как полиномот x, a0 , a1 , ..., an ). Тогда после выполнения S каждый из полиномовp1 , p2 , ..., pt либо не зависит от an , либо кратен an (может бытьзаписан в виде an Q , где Q ∈ Q[x, a0 , a1 , ..., an ]).Доказательство.
Индукция по t.Для t = 1 утверждение очевидно.Пусть t > 1 и утверждение леммы верно для 1, 2, ..., t − 1. Для шагас номером t имеется три возможности:pt := pk ,pt := pk + pl ,pt := pk · pl ,k, l ¶ t − 1. При осуществлении первой возможности требуемое непосредственно следует из предположения индукции. При второй возможности из сказанного в условии леммы относительно аддитивныхшагов следует, что pt не зависит от an .
При третьей возможностилюбой из полиномов pk , pl может быть либо кратным an , либо независеть от an ; в обоих случаях получаем то, что нам нужно.Лемма D.. Каждая формальная n-программа S, n ¾ 0, построенияполинома P вида (D.) содержит не менее n аддитивных шагов.Доказательство. Индукция по n.Для n = 0 утверждение очевидно.Пусть n > 0 и утверждение леммы верно для 0, 1, ..., n − 1. Предположим, что S содержит менее n аддитивных шагов. Ясно, что в S имеется по крайней мере один аддитивный шаг такой, что по крайнеймере один из его операндов зависит от an . В силу леммы D. первыйтакой шаг будет иметь по крайней мере один операнд, являющийсякратным an полиномом.
Пусть этот шаг имеет вид pi := pk + pl , и значением pk (именно этот операнд мы берем только для определенности) является полином an Q, Q ∈ Q[x, a0 , a1 , ..., an ]. Если в S заменитьшаг p−n−1 := an на p−n−1 := 0, а шаг pi := pk + pl — на pi := pl , то, очевидно, получится формальная (n − 1)-программа построения полино-Приложение Dма an−1 x n−1 + ... + a1 x + a0 , содержащая менее чем n − 1 аддитивныхшагов.
Противоречие.Исследуя число мультипликативных шагов, мы докажем утверждение более сильное, чем то, которое непосредственно нас интересует.Во-первых, мы будем рассматривать формальные n-программы,которые строят полином, возможно лишь «по модулю x n+1 » равный P(x, a0 , a1 , ..., an ), т. е. некоторый полином вида Ux n+1 + an x n + ...... + a1 x + a0 , где U ∈ Q[x, a0 , a1 , ..., an ], и при этом конкретный вид Uможет быть любым, и он нас не будет интересовать. Мы согласны, таким образом, получить любой полином W (x, a0 , a1 , ..., an ) такой, чторазность W(x, a0 , a1 , ..., an ) − P(x, a0 , a1 , ..., an ) делится на x n+1 :W (x, a0 , a1 , ..., an ) ≡ P(x, a0 , a1 , ..., an ) (mod x n+1 )(D.)(этим мы фактически расширяем понятие формальной n-программы).
Во-вторых, мы будем исследовать число существенно мультипликативных шагов, т. е. таких шагов вида pi := pk · pl , для которыхk, l ¾ −n − 1; последнее означает, что операнды таких шагов не являются заранее запасенными константами. Ясно, что если для построения любого полинома W (x, a0 , a1 , ..., an ), удовлетворяющего (D.),не существует формальной n-программы, содержащей менее n существенно мультипликативных шагов, то, в частности, не существуети формальной n-программы для построения P(x, a0 , a1 , ..., an ), содержащей менее n мультипликативных шагов.Лемма D..
Пусть n ¾ 0, S — формальная n-программа, t — положительное целое, не превосходящее наибольшего значения индекса переменной p в S. Пусть среди шагов S с номерами 1, 2, ..., t нет существенно мультипликативных, в которых по крайней мере один операнд правой части зависит от an . Тогда после выполнения S каждыйиз полиномов p1 , p2 , ..., pt либо не зависит от an , либо имеет видcan + Q , где c ∈ Q \ {0} и полином Q не зависит от an .Доказательство аналогично доказательству леммы D..Лемма D..
Каждая формальная n-программа S построения какого-либо W , удовлетворяющего (D.) при P = an x n + ... + a1 x + a0 , содержит не менее n существенно мультипликативных шагов.Доказательство. Индукция по n.Для n = 0 утверждение очевидно.Пусть n > 0 и утверждение леммы верно для 0, 1, ..., n − 1. ПустьS — формальная n-программа построения некоторого полиномаОптимальность схемы ГорнераW (x, a0 , a1 , ...an ), удовлетворяющего (D.). Предположим, что в Sменьше чем n существенно мультипликативных шагов. Покажем,что в таком случае можно построить формальную (n − 1)-программу,в которой меньше чем n − 1 существенно мультипликативных шагов,и тем самым получить противоречие с предположением индукции.В силу леммы D. формальная n-программа S содержит по крайней мере один существенно мультипликативный шаг, по крайней мереодин из операндов которого зависит от an .
Пустьpi := pk · pl(D.)будет самым первым таким шагом, и пусть значением pk является полином вида can + Q(x, a0 , a1 , ..., an−1 ), c 6= 0. Тогда удаление из S всех шагов с номерами, большими i − 1, и замена шагаp−n−1 := an шагом p−n−1 := 0 дает программу S′ , получающую полином Q(x, a0 , a1 , ..., an−1 ) в качестве значения переменной pk . Пустьm — наименьшее значение индекса переменной p, встречающееся в S′ .Добавим к S′ шаг pm−1 := c′ , где c′ = −1/c, и шаг pi := pm−1 · pk , который,заметим, не является существенно мультипликативным. Получаемая1программа строит полином − Q(x, a0 , a1 , ..., an−1 ); существенно мульcтипликативных шагов в ней на единицу меньше, чем среди шаговс номерами 1, 2, ..., i в S. Обозначим эту программу через S′′ .Дальнейшие преобразования программы S имеют целью получение такой программы, которая содержит не более n − 1 существенномультипликативных шагов и при этом находит некоторый полином,по модулю x n равный an−1 x n−1 + ...
+ a1 x + a0 . Мы видим, что еслибы значением p−n−1 было не an , а тот полином, который строитсяс помощью S′′ , то i-й шаг S привел бы к присваиванию переменной pi значения 0, а после окончания выполнения всех шагов мы быполучилиW ′ = W (x, a0 , a1 , ..., an−1 , c′ Q(x, a0 , a1 , ..., an−1 )).В силу (D.) подстановка an = c′ Q(x, a0 , a1 , ..., an−1 ) в W даст намW ′ = P(x, a0 , a1 , ..., an−1 , c′ Q(x, a0 , a1 , ..., an−1 )) ++ U ′ (x, a0 , a1 , ..., an−1 )x n+1 .Принимая во внимание равенство P = an x n + ... + a1 x + a0 , получаемW ′ ∈ Q[x, a0 , a1 , ... an−1 ] иW ′ ≡ an−1 x n−1 + ...
+ a1 x + a0 (mod x n ).Отбросим предварительный раздел формальной n-программы S изапишем шаги ее вычислительного раздела вслед за S′′ , преобразуяПриложение Dэти шаги следующим образом:(a) если шаг не является шагом (D.) или существенно мультипликативным шагом вида pt := pr · ps , t ¶ k, то увеличиваем на i индексв левой части и увеличиваем на i каждый из положительных индексов в правой части (неположительные индексы не изменяются);(b) в правых частях всюду заменяем p−n−1 на pi ;(c) каждый существенно мультипликативный шаг вида pt := pr · ps ,t ¶ k, заменяем нейтральным шагом pt +i := pt ;(d) шаг (D.) заменяем нейтральным шагом p2i := p−n−1 .Прибегая к замене (c), мы пользуемся независимостью от an полиномов, являющихся значениями pr и ps , это позволяет не дублироватьсущественно мультипликативные шаги, содержащиеся в S′′ ; завершающая замена (d) приводит нас к формальной (n − 1)-программе построения W ′ , имеющей менее n − 1 существенно мультипликативныхшагов.В силу сказанного ранее, из лемм D., D. следует теорема D. .Заметим, что замена каждого вычитания сложением с дополнительным домножением второго операнда на −1 не меняет числа существенно мультипликативных шагов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
