AOP_Tom3 (1021738), страница 75
Текст из файла (страница 75)
если окончатюгьный вывод оказывается на ленте номер Т, то число серий иа всех других лентах нечетное, если окончательный вывод оказывается на некоторой ленте, отличной от Т, то число серий будет нечесаным на этой ленте и четным на остальных (см. (1)). 14. [Муб] Пусть Т„(х) = 2 р>о Т ех", где 2;,(х) — многочлены, определенные в (16). а) Покажите, что для каждого Ь существует число п(к), такое, гто Тге < Тэе « . Т„„„>Т,„1„„,, > " Ь) При условии, что Т„е < Т„е и и' < и, докажите, что Тять < Теь для всех Ь > к( с) Докажите, что существует неубывающая последовательность (М„), такая, что Е„(Я) = шш >гЕ (Я) при М < 5 < Мр рг, но Е (Я) > ппп;>г Е (Я) при 5 > М ег (см.
(19)). 15. [М42] Верно ли, что условие Е„г(тп) < Е„(тл) влечет за собой Е (тп) < Е„.рг(тп) < Е„~.э(пг) < .. (Такой результат сильно упростил бы вычисление табл. 2.) 16. [НМ42] Определите асимптотическое поведение многофазного слияния с оптималь- ным распределением фиктивных серий.
17. [88) Верке ли, что серии для оптимального мпогофвзного распределения можно разместиты аким образом, что распределение Я+ 1 начальных серий получится путем добавления одиой серии (ца соответствующую ленту) к распределению 3' начальных серий? 18. [80) Верно ли, что оптимальное мцогофазпое распределение дает наилучшую возможную схему слияния в том смысле, что суммарное количество обрабатываемых начальных серий минимально, если требуется, чтобы начальные серии размещались не более чем на Т вЂ” 1 лентах? (Временем перемотки пренебречь.) 19.
[81[ Составьте таблицу, аналогичную (1), для многофазпого метода сортировки Карама для шести лент. 20. [М84) Какая производящая функция для кароповской мпогофазной сортировки иа шести лентах соответствует (7) и (1б)? Какие соотношения, аналогичные (9) и (27), определяют строки чисел слияпий7 21.
[11) Что должно появиться ~а уровне 7 в (2б)? 22. [М81] Кавгдый член последовательности (24) приблизительно равен сумме двух предыдущих членов. Наблюдается ли это явление для остальных членов последовательности? Сформулируйте и докажите теорему о 1 — 1 -~ — 1 -ь в 23. [29) Какие изменения веобходимо выполнить в (25), (27) и (28), если (23) заменить на оеы =и 1+с 1+и«-э,и„=о„ э+ив зч-с -з+и„-4+о -ю ? 24. [НМ41) Вычислите асимптотическое поведевие мпогофазпой процедуры с расщеплением лент, если элемент емы определен как сумма первых д членов и 1 Ч- о„1 + .
+ о„-г + о„-г при различных Р = Т вЂ” 2 и 9 < д < 2Р. (В тексте раздела рассматриваегси только случай, когда 9 = 2 [Р? 2); см. упр. 23.) 25, [19) Продемонстрируйте, как мпогофазнае слияние с расщеплением лент, упомянутое в ковце этого раздела, сортировала бы 32 начальные серии. (Проанализируйте каждую фазу, как в тексте, в примере с 82 сериями на шести лентах.) 26. [М81) Проанализируйте ход выполнения мпагафазного слияния с расщеплением лент на четырех лентах при Я = 2" и при Н = 2" + 2" ' (см. упр.
25). 27. [83) Если начальные серии распределены на лентах в соответствии с точным распределением, то мяогофачная стратегия превращается просто в 'слияние до опустошения". Сначала сливаем серии со всех непустых входных лент, пока одна из них не станет пустой; затем используем зту ленту как следующую выводную, а предыдущую выводную ленту— как вводную. Верно ли, что стратегия "сливать до опустошения" всегда позволяет выполнять сортировку независимо от того, как распределены начальные серии, при условии, что мы распределяем их, по крайней мере, на две ленты? (Одна лента, конечно, будет оставлена пустой, чтобы опа могла служить первой выводной лентой.) 28.
[Мйб) В предыдущем упражнении определено весьма большое семейство схем слияния. Покажите, что моогофазная схема — наилучшая из пих в следующем смысле: если имеется шесть лент и мы рассматриваем класс всех начальных распределений (а, Ь, с, и, е), таких. что стратегия "сливать до опустошения" требует и или меньше фаз для сортировки, то а+ Ь+ с+ о+ е < 1„, где 1„— ссютветствующее число для многофазвой сортировки (1). 29. [М47) В упр. 28 показано, что многофазное распределение оптимально среди всех схем "сливать до опустошении" в смысле минимальности числа фаз. Но является ли оно оптимальным также в смысле минимальности числа проходов? Пусть числа а и Ь взаимно простые, и предположим, что а+Ь есть число Фибоначчи Р . Верно ли следующее предположение, выскэзаиное Р.
М. Карпом (В.. М. Катр): число иачальных серий, которые обрабатываются схемой "сливать до опустошения", вачииающейся с распределения (а, 6), балыке или равно ((н — 5)Е„» ~ + (2п+ 2)Е„)/57 (Указанное значение достигается, когда а = Е„ь 6 = г -ь) 80. (42) Составьте таблицу, аналогичную табл. 2, лля многофазного слияния с расщепле- нием лент. 81. [М28) (Р.
Кемп (Н. Кеп1р).) Пусть Кэ(п) — число н-узловых упорядоченных дере- вьев, в которых каждый лист находится на расстоянии З от карня. Например, в взобра- женных ниже деревьях Кз(8) = 7 Покажите, что Кз(н) является обобщенным числом Фибоначчи, .и найдите однозначное соответствие между такими деревьями и упорядоченным разбиением, которое рассматри- валось в уор. 8.
Обработанные начальные серии 190 190 190 190 190 Т1 Т2 ТЗ Т4 Т5 1зв 1ке 141 129 1ш ь1а 2э Зш 4ы 15ь 144 12з 9" э51 — э 15' 29г 41г 50' 190' Тб Проход 1 Проход 2 Проход 3 Проход 4 Проход 5 5ш 55' Каскадное слияние подобно многофазному начинается с точного распределения серий по лентам, хотя правила точного распределения отличны от правил из раздела 5.4.2. Каждая строка таблицы представляет полный проход по есеж данным. Проход 2, например, получается посредством выполнения пятипутевого слияния с (Т1, Т2, ТЗ, Т4, Т5) на Тб, пока Т5 не станет пустой (при этом на Тб помещаются 15 серий относительной длиной 5), затем четырехпутевого слияния с (Т1, Т2, ТЗ,Т4) на Т5, затем трехпутевого слияния на Т4, двухпутевого слияния на ТЗ и, наконец, однопутевого слияния (операции копирования) с Т1 на Т2.
Проход 3 получается таким же образом, путем выполнения сначала пятипутевого слияния, пока одна лента не станет пустой, затем — четырехпутевого и т. д. (Похоже, что разделу книги следовало бы присвоить номер 5.4.3.2.1, а не 5.4.3!) Ясно, что операции копирования излишни и их можно было бы опустить. Однако фактически в случае для шести лент зто копирование отнимает только небольшую часть всего времени. Элементы, которые получаются в результате простого копирования, отмечены в приведенной выше таблице звездочкой. Только 25 из 950 обрабатываемых серий принадлежат этому классу.
Ббльшан часть времени уходит на пятипутевое и четырехпутевое слияния. На первый взгляд может показаться, что каскадная схема проигрывает в сравнении с многофазной, твк как стандартная многофазная схема всегда использует *5.4.3. Каскадное слияние Другая основная схема, называемая каскадным слиянием, на самом деле была изобретена раныпе многофазной [см. В. К.
Ве1з, Ч'. С. Саг1ег, АСМ Ха6опа! СопЕ 14 (1959), Рарег 14). Ниже, в таблице, этот подход иллюстрируется для шести лент и 190 начальных серий с использованием обозначений из раздела 5.4.2, Таблица 1 ПРИБЛИЗИТЕЛЬНЫЕ ДАННЫЕ О ХОДЕ СОРТИРОВКИ МЕТОДОМ КАСКАДНОГО СЛИЯНИЯ Ленты Проходы (с копированием) Проходы (бвз копировании) Отношение роста (Т вЂ” 1)-путевое слияние в то время как каскадная использует (Т вЂ” 1)-путевое, (Т вЂ” 2)- путевое, (Т вЂ” 3)-путевое и т. д. В действительности же для шести и более лент каскадная схема асимптотически лучше, чем многофазная.
Как мы видели в разделе 5.4.2, высокий порядок слияния не является гарантией эффективности. В табл. 1 показаны характеристики выполнения каскадного слияния по аналогии с подобной таблицей из раздела 5.4.2. Нетрудно, рассуждая "в обратном направлении" от конечного состояния (1,0, ...,О), вывести "точные распределения" для каскадного слияния. В случае для шести лент имеем следуюшее. Уровень Т1 Т2 ТЗ Т4 Т5 а» е» а»+Ь» а» (1) Ь„ а» +Ь» + с» + ~~» а» а„+Ь»+с„+а„+е» с» а»+ Ь»+ с» Отметим интересное свойство этих чисел — их относительные величины являются также н длинами диагоналей правильного (2Т вЂ” 1)-угольника. Например, пять диагоналей одиннадцатиугольника на рис.
73 имеют относительные длины, очень близкие к 190, 175, 146, 105 и 55! У(ы докажем ниже в этом разделе такой замечательный факт и увидим, что значения относительного времени, затрачиваемого на (Т вЂ” 1)-, (Т вЂ” 2)-,..., 1-путевое слияние, приблизительно пропорциональны кеадратпам длин этих диагоналей. Начальное распределение серий. Если число начальных серий в действительности не есть число Фибоначчи, можно, как обычно, вставить фиктивные серии.
Даже из поверхностного анализа ситуации ясно, что метод приписывания фиктивных серий здесь работать не будет, так как при каскадном слиянии всегда выполняются 3 4 5 б 7 8 9 10 20 2.078 1а 5+ 0.672 1.235!п5+ 0.754 0.946 !аЯ+ 0.796 О. 796 !и 3 + 0 821 0.703 1п 5 + 0.839 0.639 !в а + 0.852 0.592 !п Я+ 0.861 0.555 !па + 0.869 0.397 !и Е + 0.905 1 1 5 15 55 190 0 1 4 14 50 175 1.504 1а а + 0.992 1.102 !и а + О 820 О. 897 !а Я + О.
800 0.773 1а 5 + 0.808 0,691 !и 5 + 0.822 0.632 !и 5 + 0,834 0.587 1и 3+ 0.845 О. 552 !а 5 + О. 854 0.397 !п5+ 0.901 0 1 3 12 41 1. 6180340 2.2469796 2.8793852 3.5133371 4.1481149 4.7833861 5.4189757 6.0547828 12.4174426 0 0 1 1 2 1 9 5 29 Рб 105 55 Рис. 73. Геометрическая интерпретация каскадных чисел. полные проходы. Если имеется 190 начальных серий, то каждая запись обрабатывается пять рвз, как в приведенном выше примере, но если имеется 191 серия, то, очевидно, следует увеличить уровень. Теперь каждая запись будет обрабатываться шесть раз. К счастью, на практике мож~о избежать такого резкого скачка. Дзвид Э.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
