держателя головок во время слияния управляет относительный порядок последних ключей каждого блока; следовательно, можно изобразить ситуацию следующим способом, удобным для математической интерпретации. Рассмотрим множество из PL упорядоченных пар

(aii,l) (021,1) ... (ар1,1) (ai2,2) (022,2) ... (ар2,2)

(ail,L) {a2L,L) ... {apL,L)

где множество {aij 1 < г < Р, I < j < L} состоит из чисел {1,2,..., PL) в некотором порядке и aij < aijj.,) при 1 < j < L (строки представляют цилиндры, столбцы - исходные файлы). Рассортируем пары по их первым компонентам и будем считать, что получилась последовательность (1, ji) (2,2).. • (PLJpl). Покажите, что если все (PL)!/L! возможных наборов Oij равновероятны, то среднее значение

j2 + \J3 - J2I + + IJPL - JPL-1\

равно

(l + (P-l)2--y(2)).

[Указание. См. упр. 5.2.1-14.] Заметим, что при L - оо это значение асимптотически стремится к i(P - 1)LVH+0{PL).

3. [Ml 5] Предположим, что ограниченный размер внутренней памяти делает нежелательным 10-путевое слияние. Как можно изменить рекуррентные соотношения (3)-(5), чтобы Ai{n) имело минимальное значение aD{T) + 0Е{Т) среди всех деревьев Теп листьями, не имеющих узлов степени, большей, чем 9?

► 4. [М21] Рассмотрим модифицированный вариант квадратичной схемы выделения буферов, при которой все Р входных буферов имеют равные объемы, а объем выходного буфера нужно выбрать из соображения минимизации времени поиска.

a) Выведите формулу, аналогичную (2), для времени выполнения Р-путевого слияния L символов.

b) Покажите, что построение в теореме К можно изменить так, что получится схема слияния, которая будет оптимальной в смысле вашей формулы из п. (а).

5. [М20]. Если используются два диска, причем чтение с одного совмещается с записью на другой, то нельзя применять схему слияния, подобную представленной на рис. 93, так как одни листья находятся на четных уровнях, а другие - на нечетных. Покажите, как изменить построение в теореме К, чтобы получались оптимальные деревья с учетом ограничения, что все листья находятся на четных уровнях или все на нечетных.

► 6. [22] Найдите дерево, оптимальное в смысле упр. 5, если п = 23иа = /3 = 1. (Возможно, у вас появится желание прибегнуть к помощи компьютера.)

► 7. [М24] Если длины начальных серий не равны, то наилучшая схема слияния (в смысле теоремы Н) минимизирует aD{T) -t- /ЗЕ{Т), где D{T) и Е{Т) теперь представляют собой взвешенные длины путей: каждому листу дерева приписываются веса wi,...,Wn (соответствующие длинам начальных серий), а суммы степеней и длины путей умножаются на соответствующие веса. Например, если Т - дерево, представленное на рис. 92, то получим D(T) = бил + 6W2 + 7w3 + 9w4 + 9w5 + 7шз + 4w7 + 4w8, E{T) = 2wi + 2w2 + 2w3 + 3w4 +

3W5 + 2W6 + Wt + Ws-

Докажите, что при некотором к всегда существует оптимальная схема, в которой первыми сливаются к самых коротких серий.

8. [49] Существует ли алгоритм, который при заданных Q, /3 и весах wi,... ,w„ находит оптимальные в смысле упр. 7 деревья, затрачивая только 0{п) шагов при некотором с?

9. [НМ39] (Л. Хьяфил (L. НуаШ), Ф. Прускер (F. Prusker) и Ж. Вуйлемен (J. Vuillemin).) Докажите, что для фиксированных а и /3 получается

i(n) = (min IHshA nlos n + 0(n) \m>2 logm у

при n 00, где член 0(n) > 0.

10. [HM44] (Л. Хьяфил, Ф. Прускер и Ж. Вуйлемен.) Докажите, что при фиксированных а и р Ai{n) = атп + 0п + Ат{п) для всех достаточно больших п, если т минимизирует коэффициент в упр. 9.

11. [М29] В обозначениях (6) и (11) докажите, что /т(п) + тп > f{n) при всех m > 2 и п > 2, и определите все тип, при которых имеет место равенство.

12. [25] Докажите, что при всех п > О существует дерево с п листьями и минимальной длиной степенного пути соответственно (6), все листья которого расположены на одном уровне.

13. [М24] Покажите, что при 2 < п < d(a,/3), где d{a,p) определено в соотношении (12), единственной наилучшей схемой слияния в смысле теоремы Н является п-путевое слияние.

14. [40] При использовании квадратичного метода распределения буферов время поиска для схемы слияния, представленной на рис. 92, будет пропорционально (\/2 + \/4 + \/l +

значение

представляет собой сумму величин (\/п7Н-----\-y/nZ+Vni Н-----\-Пт) по всем внутренним

узлам, где поддеревья данных узлов имеют {п1,...,Пт) листьев. Напишите программу, которая порождает деревья с минимальным временем поиска, имеющие 1, 2, 3, ... листьев, используя для оценки времени поиска эту формулу.

15. [М22] Покажите, что можно несколько "усилить" теорему F, если лифт первоначально пуст и если F{b)n ф t. В этом случае необходимо не менее \{F{b)n + т -t)/{b + т)] остановок.

16. [23] (Р. У. Флойд.) Найдите график работы лифта, перевозящего всех людей из (28) к их местам назначения через 12 или менее остановок. (В (29) показано положение после одной, а не после двух остановок.)

► 17. [НМ25] (Р. Флойд, 1980.) Покажите, что нижняя оценка в теореме F может быть улучшена до

гг(Ыпп - 1пЬ - 1) In п-(-6(1 -Ь 1п(1-(-т/Ь))

в том смысле, что некоторая исходная конфигурация должна потребовать, по крайней мере, столько остановок. [Указание. Пересчитайте конфигурации, которые могут образоваться после s остановок.]

18. [НМ26] Пусть L - нижняя оценка из упр. 17. Покажите, что среднее число остановок лифта, необходимое для того, чтобы доставить всех пассажиров по назначению, будет не менее L - 1, когда равновероятны все (Ьп)! возможных перестановок Ьп пассажиров.

► 19. [25] (Б. Т. Беннет (В. Т. Bennett) и А. Ч. Мак-Келлар (А. С. McKellar), 1971.) Рассмотрим следующий подход к сортировке ключей, продемонстрированный на примере файла с 10 ключами.

i) Исходный файл: (50,/о)(08,/1)(51,/2)(06,/з)(90,/4)(17,/5)(89,/б)(27,/7)(65,/8)(42,/9)

ii) Файл ключей: (50,0)(08,1)(51, 2)(06,3)(90, 4)(17, 5)(89, 6)(27, 7)(65, 8)(42,9)

iii) Рассортированный файл ключей (ii): (06,3)(08,1)(17, 5)(27, 7)(42, 9)(50, 0)(51, 2)(65, 8) (89,6)(90,4)

iv) Присвоение номеров ящиков (см. ниже): (2,1)(2, 3)(2, 5)(2, 7)(2, 8)(2,9)(1,0)(1, 2)(1,4) (1,6)

v) Рассортированные номера ящиков (iv): (1,0)(2,1)(1, 2)(2, 3)(1, 4)(2, 5)(1, 6)(2, 7)(2, 8) (2,9)

vi) (i) Исходный файл, распределенный по ящикам с использованием рассортированных номеров ящиков (v):

Ящик 1: (50,/о)(51,/2)(90,/4)(89,/б)

Ящик 2: (08,/1)(06,/з)(17,/5)(27,/7)(65,/8)(42,/9)

vii) Результат выбора с замещением (сначала читается ящик 2, затем - ящик 1): (06, /з)(08, /0(17, /5)(27, /7)(42, /9)(50, /о)(51, /2)(65, /8)(89, /б)(90, /4)

Номера ящиков на шаге (iv) присваиваются путем применения к (iii) выбора с замещением справа налево в порядке убывания по второй компоненте. Номер ящика - это номер серии. В приведенном примере используется выбор с замещением только с двумя элементами в дереве. Для выбора с замещением в (iv) и (vii) должен использоваться один и тот же размер дерева выбора. Заметим, что содержимое ящиков необязательно упорядочено.

Докажите, что этот метод позволит выполнять сортировку, т. е. что выбор с замещением в (vii) образует лишь одну серию. (Этот метод уменьшает число ящиков, необходимых для обычной сортировки ключей посредством распределения, особенно если исходные данные уже в значительной степени упорядочены.)

► 20. [25] Некоторые системы предоставляют в распоряжение программиста виртуальную память: можно писать программы, исходя из предположения, что имеется очень большой объем оперативной памяти, способной вместить все данные. Эта память разделена на страницы, и лишь немногие из них действительно в произвольный момент времени находятся в оперативной памяти; остальные же хранятся на дисках или барабанах. Программисту не нужно вникать во все эти подробности, так как система сама обо всем заботится: новые страницы автоматически вызываются в память, когда в них возникает необходимость.

Может показаться, что появление виртуальной памяти приводит к отмиранию методов внешней сортировки, так как эта работа может быть выполнена с помощью методов, предназначенных для внутренней сортировки. Проанализируйте такую ситуацию. Почему специально разработанный метод внешней сортировки может оказаться лучше применения обычной технологии подкачки страниц к методу внутренней сортировки?

► 21. [iW15] Сколько блоков переходит на диск j из L-блочного файла при разделении на D дисков?

22. [22] Пусть сливаются два файла по принципу Гилбрета и желательно сохранить ключи Oj с а блоками и ключи fij с b блоками. В какой блок необходимо поместить Oj для того, чтобы получить при необходимости нужную информацию?

► 23. [20] Какой объем памяти необходим для входных буферов, в которых предполагается довольно продолжительно хранить исходные данные, если выполняется 2-путевое спияние посредством (а) разделения суперблоков; (Ь) принципа Гилбрета?

24. [МЗб] Предположим, что Р серий разделены между D дисками так, что блок j серии к находится на диске (xk + j) mod D. При выполнении Р-путевого слияния эти блоки будут считываться в некотором хронологическом порядке, подобном (19). Если группы из D блоков должны вводится продолжительное время, то в момент времени t мы будем считывать с каждого диска t-u в хронологическом порядке блок, как в (21). Каков минимальный объем буфера в памяти (в количестве записей), необходимый для хранения исходных данных, которые еще не были вовлечены в процесс слияния, если не учитывать хронологический