AOP_Tom3 (1021738), страница 195
Текст из файла (страница 195)
16. Назовем ленты А, В и С. Построим несколько видов деревьев, каждый из которых характеризуется определенной структурой корня и листьев (внешних узлов). Тип г(А) Тип е(А, С) Тип т(А) Тип и(А, С) Тип е(А, С) Тип ю(А, С) Корень Корень Корень Корень Корень Корень А А,нет С-листьев А;нет А-листьев .4; нет С-листьев, иет составных В-листьев А, нет С-листьев, нет составных А-листьев А; нет А-листьев, нет составных С-листьев и(и) = и -!- пипл (е(Й) + ю(и — Й) ), е(и) = и+ пипл(и(Й) + ю(и — Й)), ю(и) = тс + ш!пл(и(Й) + е(и — Й)).
г(и) = и+ пипл(в(Й) -Ь г(и — Й)), а(п) = и+ пипл(а(Й) + т[и — Й)), т(и) = и+ тп!пт,.(и(Й) -!- а(и — Й)), Отсюда слглуещ что г(и) < а(тт) < и(и), е(и) < е(и) и г(и) < !(и) < ш(и) для всех и; крол!с того, в(2и) = !(2и -т-1) = сю. (Последнее было очевидно априори.) Пусть А(и) функция, определяемая правилами А(1) = О, А(2и) = 2тс + 2А(и), А(2и + 1) = 2п -г 1 + А(и) + А(и + 1); тогда А(2и) = 2и+ А(и — 1) + А(и Ч- 1) — (О или 1) для всех п > 2. Пусть С -- константа, такая, что при 4 < и < 8 т) для четных и имеелс ю(и) <,4(и) + Си — 1! 0) для нечетных и имеем и(и) и е(и) оба < А(и) + Си — 1. (Это в действительности справедливо для всех С > л.) По индукции получаем, что эти соотношения верны для всех и > 4 (в качестве подходящего Й выберем (и/2] Й 1).
Но А(и) является нижней оценкой в (9), если Т = 3 и г(и) < пип(в(и), е(и), ю(и)), таким образом, мы доказали, что А(и) < Кл(и) < г(и) < А(и) -1- ли — 1. ]Здесь константа -„' может быть уменьшена.) 17. ]Этот метод использовался в программе сортировки для БХ!ЛтЛС 01 и в 1962 году был представлен на симпозиуме АСМ Яогс Бутороа!шп.] Т5 О 1 15 Т4 0 2 29 Уровень О 1 2 Т2 0 4 50 Т1 1 5 55 ТЗ 0 3 41 сл с1„ е„ За„+ЗЬ„+ 2а„+25„-ь а +Ь„+ Ь 4а -!-45шв Зс -ь2с! +е а„ 5а„+4Ь„+ Зс +24,+с 'Составной лист" . это лист, "брат' которого не является листом Можно получить 3-)!(одерево типа г(А), вырастив сначала его левое поддерево типа в(В, С), а затем — правое поддерева типа т(С). Аналогично тип а(А,С) получается из типов э(В,С) и !(С); тип и(А, С) — из е(В, С) и ю(С, В)! тип е(А, С) — из и(В, С) и ш(С, А).
Можно вырастить 3-!!(о-дерево типа т(А), левое поддерево которого имеет тип и(В, А), а правое поддерево— тип е(С, А), позволив вырасти его левому поддереву, за исключением его (иесоставных) С-листьев и его правого поддерева. В этот момент левое поддерево имеет только .4- и В-листья, так что мы можем вырастить правое поддерево всего дерева, затем выбросить А-листья из левого-левого поддерева и, наконец, вырастить левое-правое поддереио. Аналогично дерево типа ю(А, С) можно образовать из и(В, А) и е(С, А).
]Дерево из упр. 7 есть г(А)-дерево, построенное этим способом ] Пусть т(и),,те(и) обозначают минимальную длину внешнего пути среди всех деревьев соответствующего типа с и-листьями, построенных с помощью такой процедуры. Имеем г(1) = в(1) = и(1) = О, г(2) = т(2) = и(2) = 2, !(1) = е(1) = ю(1) = а(2) = и(2) = е(2) = оо. Для и > 3 имеем Чтобы перейти с уровни и на уровень и+ 1 во время начального распределения, введите й~ "подуровней", в которых на лепты (Т1, Т2,, Т5) добавляется соответственно (4, 4, 3, 2, 1) серий йг "подуровней" с (4,3,3,2,1) сериями, йз — - с (3,3, 2, 2, 1), lсз — с (2,2, 2, 1, 1), йз — с (1,1,1,1,0) сериями, где йг < а„, йз < Ььч йз < с„, йа < Н, йз < еь (Есяи (йы..., йа) = (о„,..., е„), значит, достигнут уровень и -ь 1.) Добавьте фиктивные серии, если необходимо допачнить подуровень. Затем выполните слияние йг + йг + йз + йа + йз серий с (Т1,..., Т5) на Тб, й~ + Ч- lса серий с (Т1,..., Т4) на Т5, ..., серии й~ с Т1 на Т2, й~ — с (Т2,..., Тб) на Т1, йз — с (ТЗ,, Тб) на Т2, ...
и йз — с Тб на Т5. 18. (Решение предложено М. С. Патерсоном (М. Б. Рагегзоп),) Предположим, запись у помещена в последовательность на ленте номер г,. По меньшей мере, С~т~ записей могут иметь данную последовательность т, где С зависит от объема внутренней памяти (см. Раздел 5.4.8). Следовательно, (гч! + - . + (тн ( = П(Х 1обт ДГ). 19.
20. Сильное Т-Ио-дерево имеет Т-Ио-расстановку меток, в которой нет трех ветвей, имеющих вид соответственно А , А или А , А илн А для некоторого имени ленты А и некоторых 1 < у' < й < 1 < з. Неформально, чтобы "вырастить" некоторое А, необходимо вырастить все остальные деревья А до создании какого-либо нового Л. 21. 22.
Это действительно для любого представления в виде дерева, образуемого последовательной заменой всех вхождений, например заменой на для некоторых фиксированных имен лент А, В, С, Р. Так как вхождения заменяются по одному и тому же образпу, порядок ЫРО или Р1РО не вызывает различий в структуре дерева. Сформулируем зто условие в терминах векторной модели: всякий раз, когда (у! + ) ЗЬ )ь+!) ум) или)эыпэ) иу)) = — 1,имеему! )+ +у! )+у~~)=0.
! ' ' " 3 ! ! 23. (а) Пусть е! < еэ « ет; "каскадная" стадия которая превращает С(е) в е. (Ь) Очевидно, так как С(е)э < С(ш)ь при всех )э. (с) Если е получено за д стадий, то имеем и -) и!') -) -) и!Э) = е для некоторого единичного вектора и и некоторых других элементов ип), .... Следовательно, и)!) .< С(и), ийл -~ С(С(и)),..., е ~ С)Э)(и) ив!+ +от меньше или равносумме злементов С)Э)(и); последнее достигается при каскадном слиянии. (Эта теорема обобщает результат упр. 5.4.3-4; к сожалению, понятие "стадия", как оно определено здесь, не имеет, по-видимому, никакой практической ценности.] 24. Пусть у!м)...
у!)г!) будет стадией, которая переводит ш в ш Если уо = -1, ур = О, )ь+!) )Э) ..., у, = 0 и у = — 1 для некоторою х < ! — 1, то можно вставить у)ь) между уо) и у!! '). Повторяем эту операцию, пока все ( — 1) во всех столбцах не станут соседними. Тогда, если у,' = 0 и у ' ' ~ О, можно положить у)!) ! 1; в конце концов, все столбцы будут состоять из +1, за которыми следуют — 1, а за ними — О. Таким образом, стадия, которая переводит ш' в е для некоторого е/ ~ ш, построена.
После перестановки столбцов эта стадия принимает внд (1,..., 1, — 1)'г... (1, — 1, О,..., О)" ( — 1, О,..., О)". Последовательность, состоящая из Т вЂ” 1 соотношений (хЭ,..., хт) ~ (хЭ+хт,..., хт-! +хг, 0) .э (хЭ+хт !+хг,...,хт — Э+хт !+хг,хт,О) '< (ХЭ+хт-э+хг-Э+хт,..., хг-э+хт-э+хг-Э+хт, хг-Э+хг, хг, 0) '~ (я!+хе ) хэ+' ' '+хг хэ+ ' ) хт,, хг — !+хг хт 0) показывает теперь, что наилучший выбор величин а есть аг = ег, ат-! = ег-г, аэ = еэ, а! = О.
Результат является оптимальным, если переставить столбцы так, чтобы выполнялось е! « ет. 25. (а) предположите, что ет эе! » . ег > е! » ет ! и используйте (1,...,1,-1,0,...,0)".-э+!... (1,,1,О,....О,-Ц'г. (Ь) Для 1 < 1 < Т вЂ” /г сумма наибольших ( элементов Рь(е) равна (1 — 1)эь + эь+!. (с) Если е ~ ю в фазе, использующей Й выводных лент, то можно, очевидно, считать, что эта фаза имеет внд (1,...,1,— 1,0,...,0)"... (1,...,1,0,...,0,-1)", причем каждая из остальных Т вЂ” )э лент используется как вводная во всех операциях. Выбор а! = ег ь+Э, ..., аь = ет является наилучшим. (д) См. упр.
22, (с). Всегда имеем Аг = 1; А = Т вЂ” 2 всегда лучше, чем А = Т вЂ” 1, так как предполагается, что, по крайней мере, одна компонента вектора е равна нулю. Следовательно, лля Т = 3 имеем lсг... Ач — — 14 и начальное распределение (Рчэн Р„О). Для Т = 4 найдены слегующне недоминирующие стратегии и соответствующие распределения.
12 (3,2,0, 0) 121 (5, 3, 3,0); 122 (5, в,О,О) 1211 (8,8,5,0); 1222 (10, 10,0,0); 1212 (11,8,0, 0) 12121 (19, 11,11, 0); 12222 (20,20, 0,0); 12112 (21, 1б, 0,0) 122222 (40,40,0,0); 121212 (41, 30, О, 0) 124 в (5 2ч — 5 2ч 0 О) 4=2 д=З 4=4 д=б д=б д>7 Таким образом, для Т = 4 и д > б слияние с минимальным числом фаз подобно сбалансированному слиянию с незначительными искажениями в самом конде (переход от (3, 2, О, 0) к (1, О, 1,1), а не к (О, О, 2, 1)).
Когда Т = 5, недоминирующими стратегиями явлнются Ц32)" '2, Ц32)" '3 для д = 2п > 2; Ц32)" '32, Ц32)" 422, Ц32)" '23 для д = 2п+ 1 > 3. (Первая стратегия имеет в своем распределении наибольшее число серий.) На шести лентах они таковы: 13 или 14, 142 или 132 (либо 133), 1333 или 1423 и 134 ' для д > 5.
Т2 АгА, Аг Аг ТО РгАг Р, Т2 Ач А 4Рг А4 А4Аг Ач А4Аг Ач РАЗДЕЛ 5.4.5 1. Следующий алгоритм управляется массивом А Ы вЂ” И ... А [П А[0], который, в сущности, представляет число, записанное в системе счисления с основанием Р. Мы многократно добавляем единипу к этому числу; "переносы" говорят нам, когда следует выполнять слияние.
Ленты пронумерованы от 0 до Р. О1. (Начальная установка.] Присвоить (А[ — П,..., А[0]) 4 — (О,..., 0) и д 4- О. (Во время выполнения этого алгоритма д будет равно (А[ — 1] + +А[0]) шог[Т.) О2. (Распределение.( Записать начальную серию на ленту д в порядке возрастания. Установить 14- О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
