..., (Ipi, ,lpk), где lij - некоторые неотрицательные целые числа, удовлетворяющие соотношению Y2i<i<phj = lj при I <] <к. Отсюда получаем

ар(ь • • ,fc) = ai(/ii,...,Zifc)...ai(/pi,...,/pfc),

что эквивалентно искомому результату.

В разделе 5.1.3 было проанализировано среднее значение Lk - длины k-Vi серии при Р = \ (эти значения приведены в табл. 5.1.3-2). Из теоремы К следует, что средняя длина k-Vi серии при любом Р в Р раз больше средней длины при F = 1; она равна LkP- Дисперсия также в Р раз больше, так что стандартное отклонение длины серии пропорционально л/Р. Эти результаты были впервые получены Б. Дж. Гэсснер (В. Y. Gassner) около 1958 года.

Таким образом, первая серия, полученная для случайных данных алгоритмом R, будет иметь длину, приближенно равную (е - 1)F « 1.718F записей, вторая - (е - 2е)Р W 1.952F, третья - 1.996F; длина следующих серий будет очень близка к 2Р, пока мы не дойдем до последних двух серий (упр. 14). Стандартное отклонение длины большинства этих серий приближенно равно у/{4е- 10)Р « 0.934л/Р [САСМ 6 (1963), 685-687]. Кроме того, согласно упр. 5.1.3-10 суммарная длина первых к серий будет довольно близка к (2А;-1)F со стандартным отклонением (4- )F) Производящие функции gi{z,z,... ,z) и gi{l,... ,l,z) выводятся в упр. 5.1.3-9 и П.

В приведенном выше анализе предполагалось, что исходный файл бесконечно длинный, но доказательство теоремы К показывает, что такая же вероятность ap(/i,... ,/fc) получилась бы при наличии любой случайной исходной последовательности, содержащей, по крайней мере, /i Н-----hh+P элементов. Значит, полученные

результаты применимы для файла размером, скажем, N > {2к + 1)Р в силу малой величины стандартного отклонения.

В дальнейшем мы познакомимся с рядом приложений, в которых схема слияния требует, чтобы одни серии были восходящими, а другие - нисходящими. Поскольку остаток, накапливающийся в памяти у конца восходящей серии, как правило, содержит числа, в среднем меньшие, чем случайные данные, то изменение направления упорядочения приводит к уменьшению средней длины серий. Рассмотрим, например, снегоочиститель, который должен разворачиваться каждый раз по достижении конца прямой дороги; он будет очень быстро передвигаться по только что очищенному участку. В случае изменяемого направления длина серий для случайных данных изменяется между 1.5F и 2Р (см. упр. 24).

УПРАЖНЕНИЯ

1. [10] Каким будет шаг 4 в примере для четырехпутевого слияния, приведенном в начале этого раздела?

2. [12] Какие изменения произошли бы в дереве на рис. 63, если бы ключ 061 был заменен ключом 612?

3. [16] (Э. Ф. Мур (Е. Р. Moore).) Что получится в результате применения четырехпутевого выбора с замещением к последовательным слова.м приведенного ниже предложения:

fourscore ernd seven years ago our fathers brought forth on this continent a new nation conceived in liberty and dedicated to the proposition that all men are created equal.

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

4. [16] Примените четырехпутевой натуральный выбор к предложению из упр. 3, используя дополнительный буфер емкостью 4.

5. [00] Верно ли, что выбор с замещением, использующий дерево, работает, только если Р есть степень 2 или сумма двух степеней 2?

6. [15] В алгоритме R указывается, что Р должно быть > 2. Какие относительно небольщие изменения необходимо сделать в этом алгоритме, чтобы он правильно работал для всех Р > 1?

7. [17] Что делает алгоритм R в случае отсутствия исходной информации?

8. [20] Алгоритм R использует искусственный ключ "оо" который должен быть больще любого возможного ключа. Покажите, что если бы какой-нибудь реальный ключ оказался равным оо, то алгоритм мог бы ошибиться, и объясните, как изменить алгоритм в случае, когда реализация "настоящего" оо неудобна.

► 9. [23] Как бы вы изменили алгоритм R, чтобы он выводил одни заданные серии (в зависимости от RC) в порядке возрастания, а другие - в порядке убывания?

10. [26] Начальная установка указателей LOSER на щаге R1 обычно не соответствует никакому действительному турниру, так как внешний узел Р + j может не лежать в поддереве с вершиной во внутреннем узле j. Объясните, почему алгоритм R все равно работает. [Указание. Будет ли работать алгоритм R, если множеству {LOSERCLOCCATfO])),..., LOSERCLOCCATfP - 1]))} присваивается на шаге R1 произвольная перестановка множества {LOC(A[0]),...,LOC(A-[P- 1])}?]

11. [М25] Верно ли утверждение, что для случайных исходных данных вероятность того, что KEY(Q) < LASTKEY на шаге R4, приближенно равна ?

12. [М46] Детально проанализируйте количество выполнений каждой части алгоритма R. Например, как часто выполняется перестановка на шаге R6?

13. [13] Почему вторая серия, полученная при выборе с замещением, обычно длиннее первой?

► 14. [НМ25] Используйте аналогию со снегоочистителем, чтобы оценить среднюю длину двух последних серий, которые получены при выборе с замещением, примененном к длинной последовательности исходных данных.

15. [20] Верно ли, что последняя серия, полученная при выборе с замещением, никогда не содержит более Р записей? Проанализируйте свой ответ.

16. [М26] Найдите "простое" необходимое и достаточное условие того, что файл Ri R2 ... Riv будет полностью упорядочен за один проход Р-путевого выбора с замещением. Какова вероятность этого события как функции Р и N, если исходными данными служит случайная перестановка множества {1,2,..., iV}?

17. [20] Что получается в результате работы алгоритма R, когда исходные ключи представляют собой невозрастающую последовательность A"i > А"2 > • • • > Kn?

► 18. [22] Что произойдет, если вновь применить алгоритм R к файлу, полученному в результате работы алгоритма R?

19. [НМ22] Используйте аналогию со снегоочистителем, чтобы доказать, что первая серия, полученная при выборе с замещением, имеет длину примерно (е - 1)Р записей.

20. [НМ24] Какую примерно длину имеет первая серия, полученная при натуральном выборе, когда Р = Р?

► 21. [НМ23] Определите приблизительную длину серий, полученных посредством натурального выбора при Р < Р.

22. [НМ40] Целью этого упражнения является определение средней длины серий, получаемых при натуральном выборе при Р > Р. Пусть к = к + в - действительное число > 1, где к = [к], а б = к modi. Рассмотрим функцию F{k) = Fk{e), где Fjt(6) - полиномы, определяемые производящей функцией

к>0

Таким образом, Ро{в) = 1, Fi{e) = е-в, р2{в) = - е - ев + \в vl т. д.

Предположим, что в момент времени О снегоочиститель начинает моделировать процесс натурального выбора, и допустим, что за Т единиц времени позади него упадут ровно Р снежинок. В этот момент второй снегоочиститель начинает тот же путь, занимая в момент времени t-fT то же положение, которое занимал первый снегоочиститель в момент t. В конце концов, к моменту кТ позади первого снегоочистителя упадут ровно Р снежинок; второй снегоочиститель очищает остаток дороги и исчезает.

Используя эту модель для интерпретации натурального выбора, покажите, что длина серии еР{к)Р получается при

Р/Р =:к + 1 + е

(KFiK)-YF(K-j)y

23. [НМ35] В предыдущем упражнении проанализирован натуральный выбор в том случае, когда записи из резервуара всегда читаются в том же порядке, в котором они записывались: "первым включается - первым исключается" Оцените длину серий, которая получилась бы, если бы содержимое резервуара, оставшееся от предыдущей серии, читалось в совершенно случайном порядке, как будто записи в резервуаре тщательно перемешивались между сериями.

24. [НМ39] Цель этого упражнения - анализ последствий, вызванных случайным изменением направления упорядочения серий в выборе с замещением.

a) Пусть gp{zi, 22,..., Zk) - та же производящая функция, что и в теореме К, но для каждой из к серий определено, является ли она восходящей либо нисходящей. Например, мы можем считать, что все серии с нечетными номерами - восходящие, а с четными - нисходящие. Покажите, что теорема К справедлива для каждой из 2* производящих функций такого вида.

b) В силу (а) можно считать Р = 1. Можно также предположить, что исходной является равномерно распределенная последовательность независимых случайных величин в диапазоне между О и 1. Пусть

, , / e~- е"", если а; < у; -(le- еслих>у:

Пусть f{x) dx - вероятность того, что определенная возрастающая серия начинается с X. Докажите, что (/ а{х, y)f{x) dx) dy есть вероятность того, что следующая серия начинается с у. [Указание. Рассмотрите для каждого п > О вероятность того, что X <Xi < • • < Х„ > у при данных х и у.]