AOP_Tom3 (1021738), страница 74
Текст из файла (страница 74)
Эти уравнения не имеют единственного решения. В самом деле, если положить все и равными нулю, то получится обычное многофвзное слияние, причем одна лента будет лишней! Но если выбрать и„ж иве!, то время перемотки будет удовлетворительно совмещено. Т1 Т2 ТЗ 1 1 1 1 1 1 1 1 1 1 1 ! 1 1 В 1 1 О 1 В О 1 О В В О 1 О В 1 О 1 1 В 1 1 1 1 ! 1 1 1 1 1 1 1 1 1 Т4 Тй 1 В 1 О В О О В О 1 В 1 1 1 1 1 1 1 1 1 1 ! 1 1 1 В 1 О В О О В Т6 Число О В 1 1 1 1 1 1 1 1 В О О В 1 1 В указанной работе Мак-Аллестер предложил взять и~ = ио — 1 + ио-г +)о — З + Гв — 4! и +1= и.-)+и -о+и -в+и.-», так что последовательность (хо,х),хг,хз,х»,хз, ) =(ео,ио и),и) ег,иг .) удовлетворяет однородному рекуррентному соотношению х„= хо з+х„а+хо т+ х я.
Оказалось, однако, что лучше положить ио».1 = и„! + Ео 1+ и),-г + ио-г, и„= и„в+и„в +и„»+Со (23) Эта последовательность не только немного лучше по времени с.лияния; ее большое преимущество состоит в том, что соответствующее время слияния можно проанализировать математически. Вариант Мак-Аллестера для анализа крайне труден, потому что в одной фазе могут встречаться серии разной длины; мы увидим, что такого не может случиться, если справедливо (23). Можно вывести число серий на каждой ленте на каждом уровне, двигаясь назад по схеме (21), и получить следующую схему сортировки. Время записи Уровень Т1 Т2 ТЗ Тб 1зз 1!Я 113 1)о 1Я 1з 1) 1! 1м 1 11 1в 14 1з 1н 1)з 14 К 19' 19'31 К 19 31а 191310 19)31о (31') В 31' 31!52о В.
31152о (52а) 0 х 52 = 0 ) 0 х 52 = 0 ~ )пзх(36,31,23) Охбг=о 1 х 82 = 82 Несовмещенная перемотка встречается только при перемотке вводной ленты Т5 (82 единицы) в течение первой половины фазы второго уровня (27 единиц) и в течение окончательных фаз "фиктивного слияния" на уровнях 1 и О (36 единиц). Таким образом, время работы можно оценить величиной 2731+ 145г; для алгоритма Р соответствующий параметр 2681+ 208г почти всегда хуже. Нетрудно видеть (см. упр, 23), что длины серий, выводимых во время каждой фазы, суть (24) 4, 4, 7, 13, 19, 31, 52, 82, 133,..., К 13' 13'19' В. 13'19' 19' 19' 19' 19' (19 ) К 7з 73131 К 7 13' 7'13' 7'13' 13' 13' 13' 13 Т4 Т5 1)о в.
4 з В. 4 44 В 4 В. 4 4з71 4» 4"71 4з 4171 4) 7),11 7' 4' 7о В 52о 520820 82' (В.) 111 111 14 В 1Я44 1444 1144 14 4з ,1г 4' 82 4х4=16 б х 4 = 24 3 х 4 = 12 4 х 4 = 16 1х7=7 3 х 7 = 21 1 х 13 = 13 1 х 13=13 1 х 19 = 19 1 х 19 = 19 0 х 31 = О 1 х 31 = 31 Время перемотка 23 82 — 23 27 10 36 17 23 21 34 23 32 27 19 при етом последовательность (11, 12, 1з,... ) удовлетворяет закону (25) 1« = 1« 2 + 21«-3 + 1«-4~ если считать 1« ае 1 при а < О. Можно также проанализиронать оптимальное разме- щение фиктивных серий, рассмотрев цепочки чисел слияний, как для стандартного многофвэного метода (ср.
с (8)). ТЗ Т4 Т1 «+1 (Ап Е +1)В (АпЕ»4 1)О« (А«Е +1)В АпЕ +1 Ап Т(Ь 1) (26) Здесь Ап тл А„'А'„' н А'„' состоит нз последних ип чисел слияний Ап. Приведенное выше правило перехода с уровня и на уровень и + 1 справедливо для любой схемы, удовлетворяющей (22). Если определить ип и нп, как в (23), то цепочки Ап,..., Еп можно выразить в следующем, довольно простом, виде (ср. с (9)); (И» — 1И и-2И «-ЗИ п-4) + 1, (Ип-1И'«-2И'«-3) + 1, (И'и 1 И'и,) + 1, (И'и ,) + 1, (Ип-2И и-3) + 1 Вп = (27) где Ип = (Ип-ЗИ«-4И«-2И»-3) + 1 прн и > О, И~е — — 0 и ИУ«=е пРип<0.
(28) Исходя из этих соотношений, легко подробно проанализировать случай для шести лент. В общем случае, если имеется Т > 5 лент, положим Р = Т вЂ” 2 и определим последовательности (нп), (еп) по правилам Н»41 — — ип 1+оп 1+ . +и« „+и (29) ип тл ип „1 + Нп „1 + ° + ип р + Нп р Прн и > О, где г = (Р/2), не —- 1 и ип = нп = 0 при и < О.
Если шп = и« + нп, то имеем шп тл шп 2 + . + шп-т+ 2Ш«-т-1 + зла-и-2 + ' + шп-Р ПРИ П > О; (50) ше —— 1 н шп пп 0 при и < О. При начальном распределении для уровня и+1 на ленту К ПОМЕщаЕтСя Шп+Шп 1+ +Ш„рчь СЕрИй Прн 1 < й < Р И Шп 1+ ° +юн,— на ленту Т; лента Т вЂ” 1 используется для ввода. Затем ип серий сливаются на ленту Т, в то время как лента Т вЂ” 1 перематывается; еп серий сливаются на Т вЂ” 1, пока Т ПЕрЕМатЫВавтея; ип 1 СЕрИй СЛИВаЮтСя На Т вЂ” 1, ПОКа Т вЂ” 2 ПЕрЕМатЫВаЕтея, И т. д.
Уровень 1 2 3 4 5 6 1 1 21 2221 23222 ззззгзггг 1 1 21 222 23222 33332322 1 1 2 222 2322 333323 Тб Окончательный результат Т5 Т4 ТЗ Т2 Т1 Тб 1 1 2 1 22 2 23 222 ЗЗЗЗ 2322 Таблица б ПРИБЛИЗИТЕЛЬНЫЕ ДАННЫЕ О ХОДЕ СОРТИРОВКИ МЕТОДОМ МНОГОФАЗНОГО СЛИЯНИЯ С РАСЩЕПЛЕНИЕМ ЛЕНТ Фазы Проходы Проходы/ Отношение фазы, % роста Ленты 5 6 7 8 9 10 20 2.885 1в Н+ 0.000 2. 078 1а Н + О. 232 2.078 !а Я вЂ” 0.170 1.958 !в Н вЂ” 0.408 2.008 !и Н вЂ” 0.762 1.972 !в Н вЂ” О. 987 2.
013 1в Н вЂ” 1. 300 2.069 !па — 3.164 1.4142136 1.6180340 1.6180340 1.6663019 1.6454116 1.6604077 1.6433803 1.6214947 1.4431в б+ 1.000 0.929 !п Н + 1.022 0.752 !и б + 1.024 0.670 !п Н+ 1.007 0.624!а Н+ 0.994 0.595 1и Н + 0.967 0.580 1о Н + 0.941 О. 566 1в 5 + О. 536 50 45 36 34 31 30 29 27 В табл, б показаны приблизительные данные о ходе выполнения этой процедуры, когда Н не слишком мало. В столбце "Проходы/фазыг примерно показано, какая часть всего файла перематывается во время каждой половины фазы и какая часть файла записывается за время каждой полной фазы.
Метпад расщепления лепта превосходит стандартный многофазный метпад па шестпи или более лентах и, вероятно, также на пяти лентах, по крайней мере для больших Н. Если Т = 4, то указанная процедура стала бы, по сушеству, эквивалентной сбалансированному двухпутевому слиянию без совмещения времени перемотки, так как шго~ы было бы равно О при всех и. Поэтому элементы табл. б при Т = 4 были получены посредством небольшой модификации, состоящей в том, что полагалось аз =О,ит — — 1твт =О,ив=О аа=1иа„е! =и„т+а„т,и„.=и„з+в„гприп>2. Это позволяет построить очень интересную схему сортировки (см. упр. 25 и 26).
УПРАЖНЕНИЯ 1. (! б] На рнс. 69 указан порядок, в котором алгоритм П распределяет по пяти лентам серии 34 — 65. В каком порядке распределяются серии 1-33? 2. [21] Верно ли, что после двух фаз слияния в алгоритме П, т. е. когда мы во второй рвз достигаем шага Пб, все фиктивные серии исчезают? 3. [22] Докажите, чта по окончании шага П4 всегда выполняется условие 0(1) > 0(2] > .. > 0(Т) . Объясните важность этого условия для правильной работы на шшах 02 и ПЗ. 4. [М20) Выведите производящие функции (7). 5. [НМ2б] (Э.
П. Майлс (Е. Р. Мйев, Лт.), 1960.) Докажите, что при всех р > 2 многочлен /р(г) = гт-гт ' — — г — 1 имеет р различных корней, из которых ровно один превосходит 1 по абсолютной величине. (Указание. Рассмотрите многочлен гР+' — 2гР+ 1.] 6. (НМ24] Цель этого упражнения — рассмотреть способ составления табл. 1, 5 и 6. Предположим, чта имеется схема слияния, свойства которой следующим образом характеризуются мнагочленами р(г) и д(г).
(т) Числа начальных серий в "точном распределении", требующем и фвз слияния, равно (г"] р(г)/д(в). (й) Число начальных серий, обрабатываемых в течение этих и фаз слиянии, равно [г" ]р(в)/д(г)~. (тй) У многочлеиа д(г ') есть "главный корень" а, такой, что 9(а — ') = О, д'(а — ') Р О, р(а — ') Р О, и из д(Н ') = О следует, чта,З = а или (б] < (а(. Докажите, что существует е > О, такое, чта если 5 равно числу серий при точном распределении, требующем и фэз слияния, а во время выполнения этих фаз обрабатывается рЯ серий, то п = о !и Я+ 5+ 0(2 ') и р = с!пЯ+ г(+ 0(о '), где Ь= — о!и, — 1, с=о (- -') р(а ) ! а — 9'( ') / ' — 9'( ') ' (Ь-!- 1)а — р'(а ')/р(а ') + дн(а ')/д'(а ') -дг(а ') о = (!па) 7.
[НМ22] Пусть ар — — главный корень многочлена /р(х) из упр. 5. Каково асимптотическое поведение ар при р -р со? 8. [М20] (Э. Нетто (Е. Ке!!о), 1901.) Пусть М2~~ есть число способов выражения тп в виде упорядоченной суммы целых чисел (1, 2,..., р). Например, если р = 3 и пг = 5, то имеется 13 способов: 1+1+1+1+1 = 1+1+1+2 = 1+ 1+2+1 = 1+1+ 3 = 1+2+1+1 = 1 +2+2 = 1+3+1 = 2+1+ 1+1 = 2+1 +2 = 2+2-р1 = 2+3 =3+1 +1 = 3+2. Покажите, что?У~~~ являются обобщенными числалги Фибоначчи 9, [М20] Пусть Л„, -- число последовательностей иэ нулей и единиц, таких, что в них ии нет р последовательных единиц Например, если р = 3 и тп = 5, имеется 24 варианта: 00000, 00001г 00010, 00011, 00100, 00101, 00110, 01000, 01001,...,11011. Покажите,что Кы являются обобщенными числами Фибоиаччи. 10.
[М27] (Сиспгеме счисления с обоби!енными числами Фибоноччи.) Докажите, что каждое неот1гицательное целое и имеет единственное представление в виде суммы различных чисел Фибоначчи р-го порядка г' при т > р, удовлетворяющее условию, что не Ы используются никакие р-последовательные числа Фибоначчи. 11. [М24] Докажите, что и-й элемент цепочки С) в (12) равен количеству различных чисел Фибоначчи в представлении элемента п — 1 числами Фибоначчи пятого порядка (см. упр. 10). 0 1 0 0 0 О 0 1 0 0 0 0 0 1 0 ОООО 1 1 1 1 1 ь 12, [М12] Найдите зависимость между степенями матрицы и точным фибоначчиевым распределением в (1). ь 13. [22) Докажите следующее интересное свойство точных фибоиаччиевых распределений.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
