AOP_Tom3 (1021738), страница 70
Текст из файла (страница 70)
Покажите, что теорема К справедлива длв каждой из 2о производящих функций такого вида. Ь) В силу (а) можно считать Р = 1. Можно также предположить, что исходной является равномерно распределенная последовательность независимых случайных величин в диапазоне между О и 1. Пусть е — е" *, солих<у; а(х,у) = е' =('--. если х > у Пусть у(х) Вх — вероятность тога, что определенная возрастающая серия начинается с х. Докажите, чта (( о(х,у)у(х) Вх) Ву есть вероятность того, что следующая серия 1 начинается с у.
(Указание. Рассмотрите для каждого и > О вероятность того, что х<Х~< <Х„>уприданныххиу.) с) Рассмотрите серии, меняющие направление упорядочения с вероятностью р; другими словами, направление каждой серии, кроме первой, совпадает с направлением предыдущей серии с вероятностью д = (1 — р) и противоположно ему с вероятностью р. (Таким образом, если р = О, то все серии имеют одинаковые направления; егли р = 1, направление серий чередуется, а при р = -' серии случайны и независимы.) Пусть г1 г~ й(х) = 1, г8 ы(у) =р / а(х,у)г'„(1 — х)Их+ у / а(х,у)г'„(х)Их. о е Покажите, что вероятность того, что и-я серия начинается с х, есть у (х) Их, если (и — 1)-н серия восходящая, и у„(1 — х) 8х, если (и — 1)-я серия нисходящая. 6) Найдите решение 1 для уравнения установив~погася режима г~ г~ г~ ~(у) = р/ а(х, у)э'(1 — х) дх+ д / а(х,у)г'(х) <Ь, / г'(х) Их = 1.
е е э [Указание. Покажите, что у" (х) не зависит от х.) е) Покажите, что последовательность у„(х) п. (с) весьма быстро сходится к функции у (х) п. (Й). 1) Покажите, что средняя длина восходящей серии, начинающейся с х, равна е' *. К) Наконец, объединим все предыдущие результаты и докажите следующую теорему. Если направления последовательных серий при выборе с замещением независимо изменяются на противоположные с вероятностью р, то средняя длина серии стремится к (61(З+ р))Р.
(Эта теорема при р = 1 впервые была доказана Кнутом [САСМ 6 (1968), 685-688]; при р = -' ее доказал А. Г. Конхейм (А. С. КопЬепп) в 1920 году.) 25. [Над) Рассмотрите слелуюшую процедуру. Х1. Прочитать запись, поместив ее в "резервуар" емкостью в одно слово. Затем прочитать следующую запись Е, и пусть К будет ее ключом. Х2. Вывести содержимое резервуара, установить ЕАЗТКЕТ равным его ключу и очистить резервуар. ХЗ. Едки К ( 1,АЗТКЕТ, та вывести Е, установить 1,АЗТКЕТ ~- К и перейти к шагу Х5.
Х4. Если резервуар не пуст, вернуться к шагу Х2; в противном сэучае поместить К в резервуар. Х5. Прочитать новую запись Е и установить К равным ее ключу. Перейти к шагу ХЗ. Эта процедура, в сущности, эквивалентна натуральному выбору с Р = 1 и Р' = 1 или 2 (в зависимости от того, в какой момент мы опустошаем резервуар — как только ои эапоэпэится или когда необходимо будет записать в заполненный резервуар новый элемент, переполняющий его), ио она порождает нисходящие серии и ее выполнение никогда не прекращается.
Такие отклонения не приносят вреда, они удобны для достижения нашей цели. Действуя, как в упр. 24, обозначим через Г' (х, у) Идах вероятность того, что х и у суть значения 1.А5ТКЕТ и К соответственна сразу же после и-го выполнения шага Х2. Докажите, что существует функция д„(х) ат одной переменной, такая, что Г„(х, у) = д„(х), если х ( у, и Г' (х,у) = д (х) — е "(д„(х) — д„(у)), если х > у. Функция д„(х) определяется соотношениями д~ (х) = 1: (Ср. с 2.3.1-(10); верхний узел есть голова списка, пунктирными линиями показаны прошитые связи.
В этом примере мы сосредоточим внимание на сортировке с использованием структуры полного двоичного дерева, когда узел 0 (аналог головы списка) добавляется перед узлом 1, как в "дереве проигравших" на рис. бЗ.) Покажите, как организовать 2"+" внутренних узлов большого дерева проигравших на этих 2" основных узлах так, чтобы (>) каждый главный узел удерживал точно 2" узлов большого дерева; (й) в большом дереве подсоединенные узлы подключались либо к одному и тому же главному узлу, либо к главным узлам, подсоединенным рядам друг с другом; (ш) никакие две пары соседних узлов в б<>льшам дереве не разделялись одной и той же связью в главном дереве. [Таким образам, множество виртуальных процессоров в сети большого двоичного дерева можно отобразить на реальные процессоры без нежелательной избыточной перегрузки каналов связи.! ЗО. [МЙ9[ Докажите, чта если а > й > 1, то построение в предыдущем упражнении оптимальна в том смысле, что любое 2~-узловой основной граф, удовлетворяющий условиям (>), (й) н (ш), должен иметь, по меньшей мере, 2 + 2" ' — 1 ребер (связей) между узлами, вб.4.2.
Многофазное слияние Теперь, после того как мы выяснили, как можно образовать начальные серии, рассмотрим различные методы распределения серий по лентам и их слияния до тех пор, пока не получится единственная серия. Предположим сначала, что в нашем распоряжении имеются трн накопителя на магнитных лептах; Т1, Т2 и ТЗ; можно воспользоваться методом сбалансированного слияния, описанным в начале раздела 5.4, назначив Р = 2 н Т = 3. Алгоритм этого метода принимает следующий вид. В1.
Распределить начальные серии попеременно на ленты Т1 и Т2. В2. Выполнить слияние серий с лент Т1 и Т2 на ТЗ, затем остановиться, если ТЗ содержит только одну серию. ВЗ. Скопировать серии с ТЗ попеременно на Т1 и Т2, затем вернуться к шагу В2. 1 Если при начальном распределении получилось Я серий, то при первом проходе слияния будет образовано [Я>'21 серий на ТЗ, при втором — [5~41 и т. д.
Таким образом, если, скажем, 17 < Я < 32, то произойдет 1 проход распределения, 5 проходов слияния и 4 прохода копирования. В общем случае, если Я > 1, число проходов по всем данным будет равно 2[(кЯ1. Проходы копирование в этой процедуре нежелательны, так как они не уменьшают числа серий. Можно наполовину сократить количество копирований, если использовать двухФазную процедуру. А1.
Распределить начальные серии попеременно на ленты Т1 и Т2. А2. Слить серии с лент Т1 и Т2 на ТЗ; остановиться, если на ТЗ содержится только одна серия. АЗ. Скопировать половину серий ТЗ на Т1. А4. Слить серии с лент Т1 и ТЗ на Т2; остановиться, если на Т2 содержится только одна серия. Аб. Скопировать половину серий с Т2 на Т1. Вернуться к шагу А2.
$ Число проходов по всем данным сократилось до -'(!85) + -', так как на шагах АЗ и А5 выполняется только "половина прохода", т, е, сэкономлено около 25% времени. В действительности можно даже полностью устранить копирование, если начать с Гв серий на ленте Т1 и Гв 1 серий на Т2, где Г„и Г„1 — последовательные числа Фибоначчи. Рассмотрим, например, случай, когда и = 7, 5 = Г„+ Г„ 13 + 8 = 21. Содержимое Садерхсимае Т2 ТЗ Содержимое Т1 Примечание Здесь 12' обозначает 31 серию относительной длины 1 и т. д.; везде используется пятипутевае слияние.
Эта общая схема была представлена в работе Н. Ь. Ойвсад, Ргас. Еал1егл,Уон14 Сошригег СолЕ 18 (1960), 143-148, в которой она названа многофазнмм слиянием. Случай для трех лент был открыт В. К, Ветцем (В. К. Вегя) [неопубликованная заметка, М!ппеаро1!в-Напеу1уе!! Нейи!абог Са. (1956)]. Чтобы заставить механизм многофазного слияния работать, квк в предыдущем примере, необходимо после камсдой фазы иметь "точное фибоначчиево распреде- 1 1,1,1,1,1,1,1,1,1,1,1,1,1 1,1,1,1,1,1,1,1 Начальное распределение 2 1,1,1,1,1 — 2,2,2,2,2,2,2,2 Слияние 8 серий на ТЗ 3 — З,З,З,З,З 2,2,2 Слияние 5 серий на Т2 4 5,5,5 З,З Слияние 3 серий на Т1 5 5 8,8 Слияние 2 серий на ТЗ 6 13 8 Слияние 1 серии на Т2 7 21 — — Слияние 1 серии на Т1 Здесь 62,2,2,2,2,2,2,2", например, обозначает восемь серий относительной длины 2, если считать относительную длину каждой начальной серии равной 1.
Всюду в этой таблице присутствуют числа Фибаиаччи! Полный проход но данным осуществляется только на фазах 1 и 7; на фазе 2 обрабатывается лишь 16/21 от общего числа начальных серий, на фазе 3 — лишь 15/21 и т. д, Таким образом„суммарное число "проходов" равно (21+16+15+15+16+ 13+ 21)/21 = 547, если предположить, что начальные серии имеют примерно равную длину. Для сравнения заметим, что рассмотренная выше двухфазная процедура затратила бы 8 проходов на сортировку этой 21 начальной серии.
Мы увидим, что в общем случае данная схема Фибоначчи требует приблизительно 1.04!85 + 0.99 проходов, что делает ее сравнимой с четмрехленточнмм сбалансированным слиянием, хотя она использует только три ленты. Эту идею можно обобщить для Т лент при любом Т > 3, используя (Т вЂ” 1)- путевое слияние. Мы увидим, например, что для четырех лент требуется только около . 703 !8 5+096 проходов по данным. Обобщенная схема использует обобщенные числа Фибоначчи. Рассмотрим следующий пример с шестью лентами.
Фаза Т1 Т2 ТЗ Т4 Т5 Тб Число абрабать1ваемых начальных серий 31+ 30+ 28+ 24+ 16 = 129 2 11В 114 1!2 16 516 16 х 5 = 80 8х9= 72 4 1 1 — 174 94 5 4х17= 68 5 !' — ЗЗ 17 9 52 2хЗЗ= бб 6 — 65' ЗЗ' 17' 9' 5' 1х65= 65 7 129' 1 х 129=129 ление" серий по лентам. Читая приведенную выше таблнпу снизу вверх, можно заметить, что первые семь точных фибоначчиевых распределений при Т = 6 суть (1,0,0,0,0), (1,1,1,1,1), (2,2,2,2,1), (4,4,4,3,2), (8,8,7,6,4), (16,15,14,12,8) и (31,30,28,24,16). Теперь перед нами стоят следующие вал«ные вопросы. 1.
Какое правило скрыто за этими точными фибоначчиевыми распределениями? 2. Что делать, если Я не соответствует фибоначчиевому распределению? 3. Как построить начальный проход распределения, чтобы на нем порождалось нужное расположение серий на лентах? 4. Сколько "проходов" по данным потребует Т-ленточное многофззное слияние (квк функция от 5 — числа начальных серий)? Мы обсудим эти четыре вопроса по очереди; сначала дадим "простые ответы", а затем займемся более глубоким анализом. Точные фибоначчиевы распределения можно получить, «прокручивая«рассмотренную схему в обратном направлении и циклически переставляя содержимое лент. Например, при Т = 6 имеем следующее распределение серий.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
