► 3. [20] Докажите, что при использовании метода многофазного слияния, описанного для распределения (1), после завершения сортировки на ленте Т1 всегда оказывается и серия А, если первоначально на Т1 было ADA ..., а на лентах Т2-Т5 было DAD----

4. [М22] Как вы оцениваете идею выполнения многофазного слияния с обратным чтением после распределения всех серий в порядке возрастания, если предположить, что все позиции D первоначально заполнены фиктивными сериями?

► 5. [23] Какие формулы для цепочек слияния чисел вместо (8)-(11) из раздела 5.4.2 будут справедливы для многофазного слияния с обратным чтением? Оцените число слияний для распределения пятого уровня на шести лентах, нарисовав диаграмму, аналогичную показанной на рис. 71, (а).

6. [07] Каково векторное представление схемы слияния, представлением которой в виде дерева является (8)?

7. [16] Нарисуйте представление в виде дерева схемы слияния с обратным чтением, определенной такой последовательностью векторов:

,;(> = (20, 9, 5) 2/(==) = (+1,-1,+1) /(ю) = +i i)

2/(3) = (-Ц,+1,-1) 2/«> = (-1,+1,+1) 2/)

2/(30) = (+1,+1,-1) 2/*1«)=(+1,+1,-1) 2/ =(+1,+1,-1)

у(23)=(+1, 1,+1) 2/(17) =( + 1,+1, 1) (5)

2/(28) = ( 1,+1,+1) j/(16)(+l +l l) yW +

2/(") = (+1,-1,+1) 2/ = (+1,+1,-1) У =(-1,+1,+1)

2/(26) =( + 1, 1,+1) 2/14) (2) =(+1, 1,+1)

2/(=) = (+1,+1,-1) 2/"=(+1,-1,+1) У =(-1,+1,+1)

2/(=) = (+1,-1,+1) 2/< = (-1,+1,+1) 2/*°) =(1, О, 0)

2/(23) (+1, 1 +1) 2/"> = (+1,+1,-1)

8. [23] Докажите, что (8) - оптимальный способ слияния с обратным чтением при 5 = 7иГ = 4и что все методы, избегающие однопутевого слияния, хуже.

9. [М22] Докажите справедливость нижней оценки в (9).

10. [41] При помощи компьютера составьте таблицу точных значений Кт{п).

► 11. [20] Верно ли утверждение, что для любой схемы слияния с обратным чтением, не использующей ничего, кроме (Г - 1)-путевого слияния, необходимо, чтобы серии на каждой ленте чередовались: ADAD ... (т. е. такая схема не будет работать, если две соседние серии окажутся одинаково упорядоченными)?

12. [22] Докажите, что конструкция с прямым порядком Карпа всегда порождает помеченное дерево, удовлетворяющее условиям (а), (Ь) и (с).

13. [16] Улучшите процедуру (12), сделайте ее более эффективной, удалив как можно больше однопутевых слияний, однако так, чтобы прямой порядок все еще приводил к правильной расстановке меток у внутренних узлов.

14. [40] Придумайте алгоритм, который выполняет слияние в прямом порядке без явного построения дерева на шагах Р2 и РЗ, используя только 0(log S) слов памяти для управления слиянием.

15. [Л/59] Конструкция Карпа с прямым порядком порождает деревья с однопутевым слиянием в некоторых терминальных узлах. Докажите, что если Г = 3, то можно построить асимптотические оптимальные 3-lifo-деревья, в которых используется только двухпутевое слияние.

Другими словами, пусть Кт{п) будет минимальной длиной внешнего пути среди всех T-lifo-деревьев с п внешними узлами, таких, что каждый внутренний узел имеет степень Г-1. Докажите, что АГз(п) = nlgn + 0(п).

16. [М46] (Сохраняются обозначения, принятые в упр. 15.) Верно ли, что Кт{п) = nlogy i п + 0(п) для всех Г > 3, если п = 1 (по модулю Г - 2)?

► 17. [28] (Ричард Д. Пратт (Richcird D. Pratt).) Чтобы получить возрастающий порядок в каскадном слиянии с обратным чтением, можно потребовать четного числа проходов слияния. Таким образом, предполагается, что метод начального распределения несколько отличен от метода, приведенного в алгоритме 5.4.3С.

a) Измените 5.4.3-(1) так, чтобы были представлены только точные распределения, для которых требуется четное число проходов слияния.

b) Постройте схему начального распределения, осуществляющую интерполяцию между этими точными распределениями. [Иначе говоря, если число начальных серий находится между точными распределениями, то желательно слить некоторые (но не все) серии дважды, чтобы получить точное распределение.]

► 18. [М38] Предположим, что имеется Г ленточных устройств для некоторого Г > 3 и что на Т1 содержится N записей, в то время как остальные ленты пусты. Возможно ли обратить порядок записей на ленте Т1 за число шагов, меньшее NlogN), без обратного чтения? (Эта опергщия является, конечно, тривиальной, если допускается обратное чтение.) В упр. 5.2.5-14 приводится класс таких алгоритмов, которые, однако, тратят порядка log N шагов.

УПРАЖНЕНИЯ (часть 2)

В скдующих упражнениях теория слияния на лентах с прямым чтением распространяется на случай, когда каждая лента действует, как очередь, а не как стек. Схему слияния можно представить последовательностью векторов 2/" .. уу" точно так же, как в тексте р£1здела, но когда мы преобрадуем векторное представление в представление в виде дерева, правило "последним образован - первым растет" згшеняется правилом "первым образован - первым растет" Таким образом, недопустимая конфигурация (4) должна быть заменена конфигурацией

0 ® О ®

0 © □ ©

Дерево, которое может быть помечено так, чтобы изображались слияния с прямым чтением на Г лентах, называется T-fifo-деревом по аналогии с термином "T-lifo" в случае обратного чтения.

Если ленты можно прочесть в обратном направлении, значит, они образуют очень хорошие стеки. Но, к сожалению, они не могут образовать очень хорошие универсальные очереди. Если в произвольном порядке записывать и считывать по правилу "первым включается - первым исключается", то придется тратить много времени на переход от одной части ленты к другой. Хуже того, мы вскоре проскочим конец ленты! Здесь возникает та же проблема, что и в случае выхода очереди за границу памяти [см. соотношения 2.2.2-(4) и (5)], но решение в виде 2.2.2-(6) и (7) не применимо к лентам, так как их нельзя закольцевать. Поэтому дерево будем называть сильным T-fifo-деревом, если оно может быть помечено так, чтобы соответствующая схема слияния использовала ленты, подчиняясь особой дисциплине: "згшисать, перемотать, прочитать все, перемотать; записать, перемотать, прочитать все, перемотать и т. д."

+ • • + у" и г; = j/C) + • • + 2/".) Будем писать v < w, если г; и tt; - Г-векторы, такие, что сумма наибольших к элементов вектора г; < не превышает суммы наибольших к элементов вектора w при 1 < А; < Г. Так, например, (2,1,2,2,2,1) Ч (1,2,3,0,3,1), поскольку 2<3, 2 + 2<3 + 3, ...,2 + 2 + 2 + 2+1 + 1<3 + 3 + 2+1 + 1--0. Наконец, если v = (vi,... ,vt), to пусть C{v) - {sT,ST-2,ST-3, 0), где Sk есть сумма наибольших А; элементов векторов v.

a) Докажите, что v -> C{v).

b) Докажите, что г; tt; влечет C{v) Ч C(tt;).

c) Считая известным результат упр. 24, докажите, что при каскадном слиянии минимизируется число стадий.

24. [М35] Используя обозначения, принятые в упр. 23, докажите, что г; -> tt; влечет tt; Ч C{v).

25. [М36] (Р. М. Карп.) Будем говорить, что сегмент j/... j/ схемы слияния является фазой, если ни одна из лент не используется и для ввода, и для вывода, т. е. если не существует г, j, к, таких, что q>i>r,q>k>r, j/j = -1-1, и j/j* = -1. Назначение этого упражнения - исследовать схему слияния, которая минимизирует число фад. Будем писать v w, если tt; может быть преобразовано в г; за одну фазу (ср. с подобным обозначением, введенным в упр. 23), и пусть Dk{v) - {sk + tk+\, Sk+tk+2, , Sk+tT, О, ..., 0), где tj обозначает j-й в порядке убывания элемент v и Sk =t\-----\-tk-

a) Док£1жите, что v Dk{v) при 1 < А; < Г.

b) Докажите, что из г; Ч tt; следует Dk{v) Ч Dk{vo) при 1 < А; < Г.

c) Докажите, что из г; tt; следует tt; Ч Dk{v) для некоторого А;, 1 < А; < Г.

d) Следовательно, схема слияния, сортирующая максимальное число начальных серий на Г лентах за q фаз, может быть изображена последовательностью целых чисел A;i А;2 ... А;,, такой, что начальное распределение есть Dki- .{Dk2{Dki{u)))...), где и = (1,0,...,0). Эта стратегия минимума фаз имеет сильное Г-А£о-представление и входит в класс схем из упр. 22. Когда Г = 3, это многофазная схема, а при Г = 4, 5, 6, 7 это вариация сбалансированной схемы.

26. [М.] (Р. М. Карп.) Верно ли, что оптимально последовательность A;i А;2 ... А;,, упомянутая в упр. 25, всегда равна 1 [Г/г] [Г/2] [Г/г] [Г/2] ... для всех Г > 4 и всех достаточно больших 5?

> 20. [22] Сформулируйте условие "сильного T-fifo-дерева" в терминах достаточно простого правила относительно недопустимых конфигураций меток лент, аналогичного (4).

21. [18] Нарисуйте представление в виде дерева схемы слияния с прямым чтением, определенной посредством векторов в упр. 7. Можно ли считать его сильным 3-fifo-деревом?

22. [28] (Р. М. Карп.) Докажите, что представления в виде дерева многофазного и каскадного слияний с точным распределением полностью одинаковы как в случае обратного чтения, так и в случае прямого чтения, за исключением номеров, которыми помечены внутренние узлы. Найдите более широкий класс векторных представлений схем слияния, для которых верно скюанное.

23. [24] (Р. М. Карп.) Будем говорить, что серия j/"... j/ схемы слияния является стадией, если никакая выводная лента не используется в дальнейшем как вводная, т. е. если не существует г, j, к, таких, что 5 > г > А; > г и j/j = -1, j/j* = Назначение этого упражнения - доказать, что при каскадном слиянии минимизируется число стадий среди всех схем слияния с тем же числом лент и начальных серий.

Удобно ввести некоторые обозначения. Будем писать v w, если г; и tt; такие Г-векторы, что существует схема слияния, которая на своей первой стадии переводит tt; в г; (т. е. существует схема слияния j/"*... у-°\ такая, что j/""... j/"*" является стадией, w =