c) Рассмотрите серии, меняющие направление упорядочения с вероятностью р; другими словами, направление каждой серии, кроме первой, совпадает с направлением предыдущей серии с вероятностью q = (1 - р) и противоположно ему с вероятностью р. (Таким образом, если р = О, то все серии имеют одинаковые направления; если р = 1, направление серий чередуется, а при р = 5 серии случайны и независимы.) Пусть

fi{x) = l, fn+i{y)=P [ a{x,y}fn(l-x)dx + q [ a{x,y)fn{x)dx.

Jo Jo

Покажите, что вероятность того, что п-я серия начинается с х, есть fn{x)dx, если (п - 1)-я серия восходящая, и /„(1 - x)dx, если [п - 1)-я серия нисходящая.

d) Найдите решение / для уравнения установившегося режима

/(у)

= pf a{x,y)f(l-x)dx + q f a{x,y)f{x)dx, f f(x)dx = l. Jo Jo Jo

[Указание. Покажите, что f"{x) не зависит от х.]

e) Покажите, что последовательность /п(х) п. (с) весьма быстро сходится к функции /(ж)

п. (d).

f) Покажите, что средняя длина восходящей серии, начинающейся с ж, равна е~.

g) Наконец, объедините все предыдущие результаты и докажите следующую теорему. Если направления последовательных серий при выборе с замещением независимо изменяются на противоположные с вероятностью р, то средняя длина серии стремится к{6/{3+р))Р.

(Эта теорема при р = 1 впервые была доказана Кнутом [САСМ 6 (1963), 685-688]; при р = 5 ее доказал А. Г. Конхейм (А. G. Konheim) в 1970 году.)

25. [НМ4О] Рассмотрите следующую процедуру.

N1. Прочитать запись, поместив ее в "резервуар" емкостью в одно слово. Затем прочитать следующую запись R, и пусть К будет ее ключом.

N2. Вывести содержимое резервуара, установить LASTKEY равным его ключу и очистить резервуар.

N3. Ерли К < LASTKEY, то вывести R, установить LASTKEY К и перейти к шагу N5.

N4. Если резервуар не пуст, вернуться к шагу N2; в противном случае поместить R в резервуар.

N5. Прочитать новую запись R и установить К равным ее ключу. Перейти к шагу N3. I

Эта процедура, в сущности, эквивалентна натуральному выбору сР=1иР = 1 или 2 (в зависимости от того, в какой момент мы опустошаем резервуар - как только он заполнится или когда необходимо будет записать в заполненный резервуар новый элемент, переполняющий его), но она порождает нисходящие серии и ее выполнение никогда не прекращается. Такие отклонения не приносят вреда, они удобны для достижения нашей цели.

Действуя, как в упр. 24, обозначим через /„(ж, у) dydx вероятность того, что ж и у суть значения LASTKEY и К соответственно сразу же после п-го выполнения шага N2. Докажите, что существует функция дп{х) от одной переменной, такая, что fn{x,y) = дп{х), если ж < у, и fn{x,y) = дп{х) - е~(р„(ж) - дп{у)), если ж > у. Функция р„(ж) определяется соотношениями pi (ж) = 1:

9n+i{x)= Г egn{u)du+ Г dv (v + I) f du {{e" - l)gn{u) + gn{v))

Jo Jo Jv

:j\v£du{{e - l)gn{u)+gniv)).

Покажите далее, что ожидаемая длина п-й серии равна

/ dx Г dy {дп{х){е - 1) + дп{у)){2 - у) + г dx (1 - x)g„(x)e Jo Jo Jo

[Замечание. Решение этого уравнения в установившемся режиме оказывается очень сложным; оно было численно найдено Дж. Мак-Кенной (J. МсКеппа). Он показал, что длина серии стремится к предельной к 2.61307209. Теорема К не применима к натуральному выбору, так что случай Р = 1 нельзя распространить на другие Р.]

26. [МЗЗ] Рассмотрев алгоритм упр. 25 как определение натурального выбора для Р = 1, найдите среднюю длину первой серии для Р = г при любом г > О по следующей схеме.

а) Покажите, что первая серия имеет длину п с вероятностью

»г--г1 п

(п + г)

/(п-Ьг-Ы)!.

Ь) Определите "числа Стирлинга второго порядка" [[]] правилами ;]]=(. + т-1)(

при п > 0.

Докажите, что

с) Докажите, что средняя длина первой серии будет, следовательно, равна Сгв - г - 1, где

Jt=0

► 27. [НМЗО] (В. Добосевич (W. Dobosiewicz).) Если при Р< Р используется натуральный выбор, то не нужно прекращать формирование серии после заполнения вспомогательного буфера. Можно сохранять записи, которые не принадлежат текущей серии, в главной приоритетной очереди, как при выборе с замещением, до тех пор, пока в текущей серии не останется только Р записей. Тогда их можно сбросить на выход и заменить содержимым вспомогательного буфера.

Насколько такой подход лучше более простого подхода, проанализированного в упр. 21?

28. [25] В основном тексте раздела рассматривается только сортировка записей фиксированного размера. Как приспособить выбор с замещением к записям переменной длины?

29. [22] Рассмотрим 2* узлов полностью двоичного правопрошитого дерева, которое ниже показано графически в варианте, когда к = 3:

(Ср. с 2.3.1-(10); верхний узел есть голова списка, пунктирными линиями показаны прошитые связи. В этом примере мы сосредоточим внимание на сортировке с использованием структуры полного двоичного дерева, когда узел О (аналог головы списка) добавляется перед узлом 1, как в "дереве проигравших" на рис. 63.)

Покажите, как организовать 2"+* внутренних узлов большого дерева проигравших на этих 2* основных узлах так, чтобы (i) каждый главный узел удерживал точно 2" узлов большого дерева; (ii) в большом дереве подсоединенные узлы подключались либо к одному и тому же главному узлу, либо к главным узлам, подсоединенным рядом друг с другом; (iii) никакие две пары соседних узлов в большом дереве не разделялись одной и той же связью в главном дереве. [Таким образом, множество виртуальных процессоров в сети большого двоичного дерева можно отобразить на реальные процессоры без нежелательной избыточной перегрузки каналов связи.]

30. [М29] Докажите, что если п > fc > 1, то построение в предыдущем упражнении оптимально в том смысле, что любой 2*-узловой основной граф, удовлетворяющий условиям (i), (ii) и (iii), должен иметь, по меньшей мере, 2* -Ь 2*~ - 1 ребер (связей) между узлами.

*5.4.2. Многофазное слияние

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

Предположим сначала, что в нашем распоряжении имеются три накопителя на магнитных лентах: Т1, Т2 и ТЗ; можно воспользоваться методом сбалансированного слияния, описанным в начале раздела 5.4, назначив F = 2 и Г = 3. Алгоритм этого метода принимает следующий вид.

81. Распределить начальные серии попеременно на ленты Т1 и Т2.

82. Выполнить слияние серий с лент Т1 и Т2 на ТЗ, затем остановиться, если ТЗ содержит только одну серию.

83. Скопировать серии с ТЗ попеременно на Т1 и Т2, затем вернуться к шагу В2. I

Если при начальном распределении получилось S серий, то при первом проходе слияния будет образовано "5/2] серий на ТЗ, при втором - \S/4] и т. д. Таким образом, если, скажем, 17 < 5 < 32, то произойдет 1 проход распределения, 5 проходов слияния и 4 прохода копирования. В общем случае, если 5 > 1, число проходов по всем данным будет равно 2"1§5].

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

А1. Распределить начальные серии попеременно на ленты Т1 и Т2.

А2. Слить серии с лент Т1 и Т2 на ТЗ; остановиться, если на ТЗ содержится только одна серия.

A3. Скопировать половину серий ТЗ на Т1.

А4. Слить серии с лент Т1 и ТЗ на Т2; остановиться, если на Т2 содержится только одна серия.

А5. Скопировать половину серий с Т2 на Т1. Вернуться к шагу А2.