Лекции о сложности алгоритмов. С. А. Абрамов (1121249), страница 46
Текст из файла (страница 46)
Можно показать , что если среди коэффициентов унитарного неприводимого полинома f (x) имеется хотя быодин, не являющийся целым рациональным, и если C, D ∈ Z таковы,что Ca является целым алгебраическим для любого корня a полиномаf (x) и Dq(x) ∈ Z[x], то для решения m уравнения (C.) выполненоm ¶ (n − 1) log2 C + log2 D.(C.)Границы (C.) и (C.) приводят к алгоритму решения проблемыорбит.В качестве C может быть взято наименьшее общее кратное знаменателей коэффициентов полинома f (x), в качестве D — наименьшееобщее кратное знаменателей коэффициентов полинома q(x).Неверно, что C всегда можно взять меньшим , чем | f (x) |.
В этом65можно убедиться, вернувшись к f (x) = x 2 − x + 1.См. уже упоминавшуюся работу [].В [] авторы исходили из предположения, что всегда можно взять C < | f (x) |.Приложение DОптимальность схемы ГорнераТеорема D.. Пусть n — произвольное неотрицательное целое число. Не существует алгоритма, который, используя только сложение,вычитание и умножение, позволяет вычислять значениеan x n + ... + a1 x + a0(D.)по числам x, a0 , a1 , ..., an так, что количество сложений или умножений всегда оказывается меньше n.В терминах нижних границ это утверждение можно, очевидно,переформулировать следующим образом.Пусть P — класс алгоритмов, вычисляющих значение (D.) с помощью операций сложения, вычитания и умножения.
Будем рассматривать число n как размер входа x, a0 , a1 , ..., an . Тогда n является нижней границей как аддитивной сложности (измеряемой числом сложений и вычитаний в худшем случае), так и мультипликативной сложности (измеряемой числом умножений в худшем случае) алгоритмовкласса P .Несколько предварительных соглашений и замечаний. Во-первых,будем для определенности считать, что все коэффициенты полинома, а также значение x принадлежат полю рациональных чисел Q,хотя достаточно было бы потребовать, например, чтобы они принадлежали произвольному бесконечному полю. Во-вторых, ограничимсяоперациями сложения и умножения; позднее мы покажем, что привлечение вычитаний не является существенным.
В-третьих, заметим,что любой алгоритм, который использует только операции сложенияи умножения и который вычисляет значение произвольного полинома фиксированной степени n по заданному x, можно записать в виделинейной (неветвящейся) программы, одной и той же для всех полиномов степени n (так как в используемом наборе операций нетопераций сравнения). В качестве программных переменных мы будем использовать p с тем или иным целым индексом.
Шагом про-Приложение Dграммы является некоторое присваивание. Подготовительный разделпрограммы содержит присваиванияp−n−1 := an ;...;p−1 := a0 ;p0 := x(D.)и, возможно, ряд присваиваний вида pk := ..., k < −n − 1, с конкретными числами в правой части (т. е. можно запасти константы, нужные в вычислениях).
Вычислительный раздел программы состоит изприсваиваний вида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..
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
