pS серий, то n = aInS + b + 0(S~) и p = c\nS + d +0{S~), где

-g(a-)

7. [HM22] Пусть Qp - главный корень многочлена fp{z) из упр. 5. Каково асимптотическое поведение Ор при р -> оо?

8. [М20] (Э. Нетто (Е. Netto), 1901.) Пусть Nm есть число способов выражения т в виде упорядоченной суммы целых чисел {1, 2,... ,р}. Например, если р = 3 и m = 5, то имеется 13 способов: 1-Ы-1-1-Ы + 1 = 1-Ы-Ы-Ь2 = 1-Ь1-Ь2-Ы = 1-Ы-1-3 = 1-Ь2-Ы + 1 = 1-Ь2-Ь2 = 1-ЬЗ-Ы = 2-Ь1-Ы-Ы = 2-Ы-Ь2 = 2-Ь2-)-1 = 2--3 = 3-Ы-Ы = 3-Ь2. Покажите, что Nm являются обобщенными числами Фибоначчи.

9. [М20] Пусть АГт - число последовательностей из нулей и единиц, таких, что в них нет р последовательных единиц. Например, если р = 3 и m = 5, имеется 24 варианта: 00000, 00001, 00010, 00011, 00100, 00101, 00110, 01000, 01001,..., 11011. Покажите, что К являются обобщенными числами Фибоначчи.

10. 1М27] {Система счисления с обобщенными числами Фибоначчи.) Докажите, что каждое неотрицательное целое п имеет единственное представление в виде суммы различных чисел Фибоначчи р-го порядка FJ при j > р, удовлетворяющее условию, что не используются никакие р-последовательные числа Фибоначчи.

11. [М24] Докажите, что п-й элемент цепочки Qoo в (12) равен количеству различных чисел Фибоначчи в представлении элемента п - 1 числами Фибоначчи пятого порядка (см. упр. 10).

► 12. [Afi5] Найдите зависимость между степенями матрицы

0 1 О О 0\

0 0 10 0

0 0 0 1 0

0 0 0 0 1

\1 1 1 1 1/

и точным

фибоначчиевым распределением в (1).

► 13. [22] Докажите следующее интересное свойство точных фибоначчиевых распределений: если окончательный вывод оказывается на ленте номер Г, то число серий на всех других лентах нечетное; если окончательный вывод оказывается на некоторой ленте, отличной от Г, то число серий будет нечетным на этой ленте и четным на остальных (см. (1)).

14. [М35] Пусть Тп{х) = X)fc>o" Т„{х) - многочлены, определенные в (16).

a) Покажите, что для каждого к существует число п{к), такое, что Ги < Тгк < ••• <

Т„(к)к > Т(п(к)+1).к > • • •

b) При условии, что Т„1к < Тпк и п < п, докажите, что Т„,к < Тпк для всех fc > fc.

c) Докажите, что существует неубывающая последовательность (М„), такая, что E„{S) = minj>iEj(S) при М„ <S < M„+i, но E„(S) > minj>i Ej(S) при S > M„+i (см. (19)).

15. [M43] Верно ли, что условие E„-i(m) < En(m) влечет за собой En(m) < E„+i(m) < Е„+2(пг) < • • •. (Такой результат сильно упростил бы вычисление табл. 2.)

16. [НМ43] Определите асимптотическое поведение многофазного слияния с оптимальным распределением фиктивных серий.

17. [32] Верно ли, что серии для оптимального многофазного распределения можно разместить таким образом, что распределение S -Ь1 начальных серий получится путем добавления одной серии (на соответствующую ленту) к распределению S начальных серий?

18. [30] Верно ли, что оптимальное многофазное распределение дает наилучшую возможную схему слияния в том смысле, что суммарное количество обрабатываемых начальных серий минимально, если требуется, чтобы начальные серии размещались не более чем на Г - 1 лентах? (Временем перемотки пренебречь.)

19. [21] Составьте таблицу, аналогичную (1), для многофазного метода сортировки Карона для шести лент.

20. [М24] Какая производящая функция для кароновской многофазной сортировки на шести лентах соответствует (7) и (16)? Какие соотношения, аналогичные (9) и (27), определяют строки чисел слияний?

21. [11] Что должно появиться на уровне 7 в (26)?

22. [М21] Каждый член последовательности (24) приблизительно равен сумме двух предыдущих членов. Наблюдается ли это явление для остальных членов последовательности? Сформулируйте и докажите теорему о tn - tn-i - tn-2-

► 23. [29] Какие изменения необходимо выполнить в (25), (27) и (28), если (23) заменить на

Wn+l = Ип-1 + Vn-1 + Un-2, Un = Vn-2 + "п-З + Vn-3 + Ип-4 + Vn-i?

24. [HM4I] Вычислите асимптотическое поведение многофазной процедуры с расщеплением лент, если элемент Vn+i определен как сумма первых q членов u„ i -Ь Vn-i -\----+

Un~p + Vn-p при различных Р = Т - 2и0<д< 2Р. (В тексте раздела рассматривается только случай, когда q = 2[P/2J; см. упр. 23.)

25. [19] Продемонстрируйте, как многофазное слияние с расщеплением лент, упомянутое в конце этого раздела, сортировало бы 32 начальные серии. (Проанализируйте каждую фазу, как в тексте, в примере с 82 сериями на шести лентах.)

26. [М21] Проанализируйте ход выполнения многофазного слияния с расщеплением лент на четырех лентах при S = 2" и при S = 2" -Ь 2"~ (см. упр. 25).

27. [23] Если начальные серии распределены на лентах в соответствии с точным распределением, то многофазная стратегия превращается просто в "слияние до опустошения" Сначала сливаем серии со всех непустых входных лент, пока одна из них не станет пустой; затем используем эту ленту как следующую выводную, а предыдущую выводную ленту - как вводную.

Верно ли, что стратегия "сливать до опустошения" всегда позволяет выполнять сортировку независимо от того, как распределены начальные серии, при условии, что мы распределяем их, по крайней мере, на две ленты? (Одна лента, конечно, будет оставлена пустой, чтобы она могла служить первой выводной лентой.)

28. [Л/2б] В предыдущем упражнении определено весьма большое семейство схем слияния. Покажите, что многофазная схема - наилучшая из них в следующем смысле: если имеется шесть лент и мы рассматриваем класс всех начальных распределений {a,b,c,d,e), таких, что стратегия "сливать до опустошения" требует п или меньше фаз для сортировки, то a + b + c + d + e < t„, где tn - соответствующее число для многофазной сортировки (1).

29. [М47] В упр. 28 показано, что многофазное распределение оптимально среди всех схем "сливать до опустошения" в смысле минимальности числа фаз. Но является ли оио оптимальным также в смысле минимальности числа проходов?

Пусть числа а и Ь взаимно простые, и предположим, что а+Ь есть число Фибоначчи F„. Верно ли следующее предположение, высказанное Р. М. Карпом (R. М. Кагр): число начальных серий, которые обрабатываются схемой "сливать до опустошения" начинающейся

с распределения (а, 6), больше или равно ((п -5)F„+i +(2n+2)F„)/5? (Указанное значение достигается, когда а = 6 = Fn-2)

30. [42] Составьте таблицу, аналогичную табл. 2, для многофазного слияния с расщеплением лент.

31. [М22] (Р. Кемп (R. Kemp).) Пусть Ка{п) - число п-узловых упорядоченных деревьев, в которых каждый лист находится на расстоянии d от корня. Например, в изображенных ниже деревьях 3(8) = 7.

Покажите, что Kd{n) является обобщенным числом Фибоначчи, и найдите однозначное соответствие между такими деревьями и упорядоченным разбиением, которое рассматривалось в упр. 8.

*5.4.3. Каскадное слияние

Другая основная схема, называемая каскадным слиянием, на самом деле была изобретена раньше многофазной [см. В. К. Betz, W. С. Carter, АСМ National Conf. 14 (1959), Paper 14]. Ниже, в таблице, этот подход иллюстрируется для шести лент и 190 начальных серий с использованием обозначений из раздела 5.4.2.

Обработанные

Каскадное слияние подобно многофазному начинается с точного распределения серий по лентам, хотя правила точного распределения отличны от правил из раздела 5.4.2. Каждая строка таблицы представляет полный проход по всел« данным. Проход 2, например, получается посредством выполнения пятипутевого слияния с {Т1, Т2, ТЗ, Т4, Т5} на Т6, пока Т5 не станет пустой (при этом на Т6 помещаются 15 серий относительной длиной 5), затем четырехпутевого слияния с {Т1,Т2,ТЗ,Т4} на Т5, затем трехпутевого слияния на Т4, двухпутевого слияния на ТЗ и, наконец, однопутевого слияния (операции копирования) с Т1 на Т2. Проход 3 получается таким же образом, путем выполнения сначала пятипутевого слияния, пока одна лента не станет пустой, затем - четырехпутевого и т. д. (Похоже, что разделу книги следовало бы присвоить номер 5.4.3.2.1, а не 5.4.3!)

Ясно, что операции копирования излишни и их можно было бы опустить. Однако фактически в случае для шести лент это копирование отнимает только небольшую часть всего времени. Элементы, которые получаются в результате простого копирования, отмечены в приведенной выше таблице звездочкой. Только 25 из 950 обрабатываемых серий принадлежат этому классу. Большая часть времени уходит на пятипутевое и четырехпутевое слияния.

На первый взгляд может показаться, что каскадная схема проигрывает в сравнении с многофазной, так как стандартная многофазная схема всегда использует