n • 2" + (n - 1) • 2" . Каждая половина фазы (за немногими исключениями) сливает 2" или 2"" и перематывает 2"~ + 2"" начальных серий.

27. Стратегия работает тогда и только тогда, когда наибольший обш;ий делитель чисел распределения равен 1. Например, пусть имеется шесть лент; если мы распределим {a,b,c,d,e) на ленты Т1-Т5, где a>b>c>d>e>0, то после первой фазы получится распределение (а-е,Ь-е,с-e,d-е,е) и gcd(a-е,Ь-е,с-e,d-е,е) = gcd(a,b,c, d, е). (Любой общий делитель одного из этих множеств чисел делит также числа другого множества.) Рассматриваемый процесс уменьшает количество серий на каждой фазе до тех пор, пока на одной ленте не останется gcd(a, 6, с, d, е) серий.

[Заметим, что эти не многофазные распределения иногда оказываются лучше многофазного при определенном расположении фиктивных серий, как показано в упр. 18. Это свойство впервые было замечено Б. Сэкманом примерно в 1963 году.]

28. Мы получаем любую такую пятерку (а, Ь, с, d, е), начав с (1,0,0,0,0) и выполнив ровно п раз следующую операцию: выбрать х из {a,b,c,d,e} и добавить х к каждому из остальных четырех элементов (а, Ь, с, d, е).

Чтобы доказать, что a + b + c + d + e < tn, докажем по индукции, что если а > Ь > с > d > е, то всегда имеем а < an, b < Ьп, с < Сп, d < dn, е < вп- В предположении, что сказанное справедливо для уровня п, это также должно быть справедливо для уровня п + 1, поскольку распределения (п + 1)-го уровня суть {b+a,c+a,d+a,e+a,a), {a+b,c+b,d+b,e+b,b), {a+c,b+c,d+c,e+c,c), (a+d,b+d,c+d,e+d,d), {a+e,b+e,c+e,d+e,e).

30. Дж. A. Мортенсон (J. A. Mortenson) свел результаты вычислений в следующую таблицу.

31. [Random Structures & Aigoritiims, 5 (1994), 102-104.] К{п) = = -n-d-i- Имеем n - d - 1 = oi -f • • • -b Or, если в дереве г -f 1 листьев и (к + 1)-й лист имеет ojt - 1 предков, отличных от предков первых к листьев. (Приведенные семь примеров деревьев соответствуют суммам в правой части 1-f 1-f 1-f 1, 1-f 1-f 2, 1-f 2-f 1, 1-f 3, 2-f 1-f 1, 2-f 2 и 3-f 1.)

РАЗДЕЛ 5.4.3

1. Выясняя с помощью табл. 5.4.2-6, сколько раз в среднем обрабатывается каждая запись, видим, что многофазный метод с расщеплением лент лучше, если имеется 6, 7 или 8 лент.

2. Методы, по существу, тождественны, если число начальных серий является числом Фибоначчи; в противном случае способ распределения фиктивных серий лучше у многофазного метода. Каскадный алгоритм помещает 1 на Т1, 1 на Т2, 1 на Т1, 2 на Т2, 3 на Т1, 5 на Т2 и т. д. Поэтому на шаге С8 никогда не обнаружится, что D\p - 1] = М\р - 1], если р = 2. В результате все фиктивные серии оказываются на одной ленте, а это менее эффективно, чем метод алгоритма 5.4.2D.

3. (Распределение заканчивается после того, как 12 серий помещаются на ТЗ на шаге (3,3).)

4. Доказывается по индукции (см. упр. 5.4.2-28).

5. Если имеется Оп начальных серий, то к-й проход выводит ап-к серий длиной ок, затем Ьп-к - длиной Ьк и т. д.

/1 1 1 1 1\

11110

1110 0 110 0 0

Vl о о о оУ

7. е2е„ 2 +езе„ з + • • • +епео длин начальных серий (см. упр. 5), что может быть также записано в виде aia„ 3 + а2ап-4 + • • + а„ 2ао; это коэффициент при [г"""] в (А(г) - Aiz)).

8. Знаменатель A{z) имеет различные корни, и его степень выше степени числителя, поэтому A{z) - Е 9з(р)/(1 ~Р)р{1 ~ч4{р)), где сумма берется по всем корням р уравнения 54(р) = р. Этот специальный вид р полезен при вычислении дз{р) и 94(р)-

9. Эти формулы справедливы для всех больших п из (8) и (12), если иметь в виду значение qm{2 sin вк)- Чтобы показать, что они справедливы при всех п, необходимо знать, что Qm-iiz) есть частное от деления qr-iiz)qmiz) на qriz) - z при О < т < г. Это можно доказать, либо используя (10) и учитывая, что при сокращении степень qr-i{z)qm{z) - qT{z)qm-i{z) снижается, либо учитывая, что из результата упр. 5 следует, что A{z) -Ь B{z) -Ь • • -Ь E{z) -> О при г -> оо, либо найдя явную формулу для числителей B{z), C{z) и т. д.

10. E{z) = riiz)A{z); Diz) = r2{z)A(z)-ri{z); C{z) = гз(г)Л(г)-Г2(г); В(г) = r4{z)A{z)-гз(г); A{z) = Г5(г)Л(г) + 1-Г4(2). Таким образом, A{z) = (1-Г4(г))/(1 - Г5(г)). [Обратите внимание на то, что rm(2sin) = sin(2m0)/cos0; следовательно, rm{z) является многочленом Чебышева (-l)"+i72m-i(2/2).]

11. Докажите, что /ш(г) = qirn/2i{z) - ri,n/2}{z) и что fmiz)frn~i{z) = 1 - rrniz). Затем используйте результат упр. 10. (Это выражение для знаменателя в явном виде впервые было выведено Девидом Е. Фергюсоном (David Е. Ferguson).)

13. См. упр. 5.4.6-6.

п+1 Имеем

В„(Л« + 1) С„(Л« + 1) Dn{A + l) Еп{А + 1) А + 1

+ 1,

n > 1,

Qn = Qn-l{Qn~2 + l)(Qn-3 + 2)iQn-4 + 3)(Qn-5 + 4),

Qo = 0 и цепочка Q„ = e при n < 0.

Цепочки An, Bn, ... содержат те же элементы, что и соответствующие цепочки из раздела 5.4.2, но в другом порядке. Заметим, что соседние числа слияний всегда различаются на 1. Начальная серия должна иметь тип А тогда и только тогда, когда число ее слияний четно, D - если нечетно. Простые схемы распределения, такие, как в алгоритме 5.4.2D, уступают в эффективности размещению фиктивных серий в позиции с большими числами слияний; поэтому, вероятно, выгодно вычислять Q„ между фазами 1 и 2, чтобы облегчить управление процессом размещения фиктивных серий.

1. Сначала (перед выводом восходящей серии) следует записать концевую запись, содержащую -00. (Запись с ключом -f-oo по-прежнему должна располагаться в конце серии, если только мы собираемся когда-либо считывать ее в прямом направлении, например на последнем проходе.) Для нисходящих серий поменять ролями -оо и -f оо.

2. Наименьшее число на уровне п + 1 равно наибольшему на уровне п; следовательно, столбцы являются неубывающими независимо от того, как переставлены числа в любой отдельной строке.

3. На самом деле в процессе слияния первая серия на Т2-Т6 всегда будет нисходящей, а на Т1 - восходящей (по индукции).

4. Такой метод требует нескольких операций "копирования" на втором и третьем проходах; дополнительные затраты приблизительно равны (log 2)/(logp) проходам, где р - "отношение роста" (см. табл. 5.4.2-1).

5. Если а - цепочка, обозначим через ее обращение.