Лекции о сложности алгоритмов. С. А. Абрамов (1121249), страница 47
Текст из файла (страница 47)
Пусть 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 не меняет числа существенно мультипликативных шагов.
Поэтому доказательство теоремы D. сохраняет силу при рассмотрении сложения и вычитанияв качестве аддитивных операций.Известен алгоритм, который для вычисления значения произвольного полинома n-й степени требует n сложений и n умножений, этоалгоритм («схема») Горнера:an x n + an−1 x n−1 + ... + a1 x + a0 = (...(an x + an−1 )x + ...
+ a1 )x + a0 .Таким образом, мы получили следующий результат:Если рассматривать n в качестве размера входаx, a0 , a1 , ..., an ,то как по числу сложений, так и по числу умножений схема Горнераявляется оптимальным в худшем случае алгоритмом вычисления значения an x n + ... + a1 x + a0 с помощью операций сложения и умножения.Разумеется, полиномы какого-либо частного вида, как, например,x n , могут вычисляться с меньшими затратами.В г. В. Я.
Пан доказал утверждение теоремы D. в несколько более общей форме — см., например, [, разд. .., упр. ]. Главные идеи доказательства, приведенного выше в этом приложении, взяты из [].Приложение EОб одном свойстве сумм неотрицательныхслучайных величинЗдесь доказывается теорема . из § .Пусть ξ1 , ξ2 , ... — последовательность неотрицательных случайных величин на некотором вероятностном пространстве.
Пусть числовая последовательность h1 , h2 , ... такова, что для каждого k ¾ 1выполнено E(ξk |ξ1 , ξ2 , ..., ξk−1 ) ¶ hk при всех значениях ξ1 , ξ2 , ..., ξk−1 .Зафиксируем неотрицательное число q и введем целочисленную случайную величину§nªXτ = min n:ξk ¾ q .k =1Пусть τ < ∞ всюду на рассматриваемом вероятностном пространPτстве. Тогда Ehk ¾ q.k =1Рассмотрим случайные величины χk , k = 1, 2, ..., где χ1 = 1, а приk > 1 выполняется χk = 1, если ξ1 + ξ2 + ... + ξk−1 < q, и χk = 0 в противном случае.
Заметим, что¨1, если τ ¾ k,χk =0, если τ < k,и 1 = χ1 ¾ χ2 ¾ ...Положим pk = P(τ = k) = P(χk = 1) − P(χk+1 = 1), k = 1, 2, ... Ясно,что P(χk = 1) = 1 − p1 − p2 − ... − pk−1 . ИмеемEXτ X∞ Xkhk =h j P(τ = k) =k =1 j =1k =1∞X=k =1(P(χk = 1) − P(χk+1 = 1))kXj =1hj =Приложение E∞X=P(χk = 1)j =1k =1∞X=P(χk = 1)∞XkXj =1k =1=kXP(χk = 1)kXk =1j =1∞XkX=P(χk = 1)j =1k =1= h1 P(χ1 = 1) +hj −hj −hj −hj −∞X∞XP(χk+1 = 1)P(χk = 1)P(χk = 1)hj =Xkj =1k =2∞Xk −1Xj =1k =2∞Xhj =j =1k =1∞XkXP(χk = 1)kXj =1k =2h j − hk =hj +∞XP(χk = 1)hk =k =2hk P(χk = 1) =k =2∞X=hk P(χk = 1).k =1Таким образом,EXτhk =∞Xhk P(χk = 1).(E.)k =1k =1Введем случайные величины ηk = χk ξk , k = 1, 2, ...; из определенияслучайных величин χk следует, что∞Xηk ¾ q.(E.)k =1Докажем, что для k = 1, 2, ...Eηk ¶ hk P(χk = 1).(E.)Рассмотрим полную группу событий W1 , W2 : в W1 попадают те элементы вероятностного пространства, для которых ξ1 + ξ2 + ...
+ ξk−1 < q,в W2 — для которых ξ1 + ξ2 + ... + ξk−1 ¾ q. С учетом определения случайной величины χk , равной 1 на множестве W1 и 0 на множестве W2 ,получаем по формуле полного математического ожидания:Eη k = E(χ k ξ k ) == E(χk ξk |W1 )P(W1 ) + E(χk ξk |W2 )P(W2 ) == E(ξk |W1 )P(W1 ) == E(ξk |W1 )P(χk = 1),Об одном свойстве сумм случайных величинт. е.Eηk = E(ξk |W1 )P(χk = 1).(E.)Так как по условию неравенство E(ξk |ξ1 , ξ2 , ..., ξk−1 ) ¶ hk выполняется при всех значениях ξ1 , ξ2 , ..., ξk−1 , то оно выполняется на W1 .С учетом (E.) имеем E(ξk |W1 )P(χk = 1) ¶ hk , откуда следует (E.).Из (E.), (E.), (E.) получаем X∞X∞∞XτXq = Eq ¶ EEη k ¶ηk =hk P(χk = 1) = Ehk ,k =1k =1k =1k =1что и требовалось .Сходное, но менее подробное доказательство имеется в [, гл.
III, § , теорема ],но там в условии теоремы пропущено требование конечности τ (см. задачу ).Приложение FО сортировке, оптимальной по числусравнений в худшем случаеДолгое время считалось правдоподобным предположение, что сортировкой, оптимальной по числу сравнений в худшем случае, являетсясортировка бинарными вставками, о сложности TB (n) которой, вместе с этим, было известно, что TB (5) = 8, при том, что наибольшаяиз обоснованных нижних границ для числа сравнений, необходимыхдля сортировки пяти элементов, есть ⌈log2 5!⌉ = 7. Это порождало гипотезу, что сложность Topt (n) оптимальной сортировки для некоторыхзначений n больше, чем ⌈log2 n!⌉, и первое такое значение n равнопяти.
Но в г. Г. Б. Демутом был найден алгоритм сортировки пятиэлементов, который требует всего семь сравнений.Этот алгоритм можно легко изобразить с помощью рисунков, накоторых те точки, которые соответствуют сравнивавшимся элементам, соединяются стрелкой, ведущей от большего элемента к меньшему. Сравниваем первый элемент со вторым и третий с четвертым,а потом сравниваем меньшие найденныеэлементы; на это уйдет три сравнения(рис. ). Этим, в частности, для трех элементов из пяти мы устанавливаем их относительный порядок. Затем для пятого элемента, который еще не сравнивался, мы наРис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
