22. Это действительно для любого представления в виде дерева, образуемого последовательной заменой всех вхождений, например заменой

для некоторых фиксированных имен лент А, В, С, D. Так как вхождения заменяются по одному и тому же образцу, порядок LIFO или FIFO не вызывает различий в структуре дерева.

Сформулируем это условие в терминах векторной модели: всякий раз, когда (у*"*" ф или к = т)и yj* = ~1, имеем yf + • • + yj + yj° = 0.

23. (а) Пусть Vl < v2 < < vt; "каскадная" стадия

(!,...,!, -ir (1,..., 1, -l,or-"... (1, -1,0,... ,0Г,

которая превращает C{v) в v. (b) Очевидно, так как C{v)k < C{w)k при всех к. (с) Если

v получено за q стадий, то имеем и -> и и* = v для некоторого единичного вектора и и некоторых других элементов и, .... Следовательно, и < С{и), и* ;< С{С{и)), ..., и Ч С(и) Hvi + - +vt меньше или равно сумме элементов С(и); последнее достигается при каскадном слиянии. [Эта теорема обобщает результат упр. 5.4.3-4; к сожалению, понятие "стадия", как оно определено здесь, не имеет, по-видимому, никакой практической ценности.]

24. Пусть у"*... у*"*" будет стадией, которая переводит wbv. Если yj = -1, yj~ = О, ..., yj* = О и yj* = -1 для некоторого А; < г - 1, то можно вставить у* между у** и у(-1) Повторяем эту операцию, пока все (-1) во всех столбцах не станут соседними. Тогда, если yj = О и yj~ ф О, можно положить yj <- 1; в конце концов, все столбцы будут состоять из -1-1, за которыми следуют -1, а за ними - 0. Таким образом, стадия, которая переводит w в v для некоторого w У w, построена. После перестановки столбцов эта стадия принимает вид (1,..., 1, -1)° ...(1,-1,0,..., 0)°=(-1,0,..., 0)°. Последовательность, состоящая из Т - 1 соотношений

(Х1,...,Хт) (х1+хт,--.,Хт-1+хт,0)

X {xi+xt-1+Хт, ,Хт-2+Хт-1+Хт,Хт,0)

Ч (xi+xt-2+xt-i+xt, . . ,Хт-3+хт-2+хт-1+хт,хт-1+Хт,Хт,0)

-<...

Ч (х1+х2+хз + - +хт,хз + - +хт, . . ,хт-1+хт,хт,0),

показывает теперь, что наилучший выбор величин о есть от = vt, ат-i = vt-i,

02 = v2, ai = 0. Результат является оптимальным, если переставить столбцы так, чтобы

выполнялось vi < < Vt-

25. (а) Предположите, что vt-k+i > > vt > vi > > vt-k и используйте

(1,...,1,-1,0,...,0П-+...(1,...,1,0,...,0,-1П.

(b) Для 1 < / < Т - А; сумма наибольших / элементов Dk{v) равна (/ - l)sk + Sk+i- (с) Если

v w в фазе, использующей А; выводных лент, то можно, очевидно, считать, что эта фаза имеет вид (1,..., 1, -1,0,..., 0)°... (1,..., 1,0,..., О, -1)"*, причем каждая из остальных Т - А; лент используется как вводная во всех операциях. Выбор oi = vt-k+i, . ., ак = vt

является наилучшим, (d) См. упр. 22, (с). Всегда имеем ki = 1; к = Т - 2 всегда лучше, чем к = Т - 1, так как предполагается, что, по крайней мере, одна компонента вектора v равна нулю. Следовательно, для Т = 3 имеем fci... Л, = 1 и начальное распределение {Fq+i, Fq,0). Для Т = 4 найдены следующие недоминирующие стратегии и соответствующие распределения.

q = 2 12(3,2,0,0)

q = 3 121 (5,3,3,0); 122 (5,5,0,0)

q = 4 1211(8,8,5,0); 1222 (10,10,0,0); 1212(11,8,0,0)

q = 5 12121(19,11,11,0); 12222 (20,20,0,0); 12112(21,16,0,0) .

q = 6 122222 (40,40,0,0); 121212 (41,30,0,0)

q>7 12" (5•2•-52"0,0)

Таким образом, для Т = 4 и g > 6 слияние с минимальным числом фаз подобно сбалансированному слиянию с незначительными искажениями в самом конце (переход от (3, 2,0,0) к (1,0,1,1), а не к (0,0,2,1)).

Когда Т = 5, недоминирующими стратегиями являются 1(32)"~2, 1(32)"~3 для q = 2п > 2; 1(32)"-32, 1(32)-22, 1(32)"-23 для g = 2п --1 > 3. (Первая стратегия имеет в своем распределении наибольшее число серий.) На шести лентах они таковы: 13 или 14, 142 или 132 (либо 133), 1333 или 1423 и 13" для g > 5.

РАЗДЕЛ 5.4.5

1. Следующий алгоритм управляется массивом A[Z. - 1] ... А[1]А[0], который, в сущности, представляет число, записанное в системе счисления с основанием Р. Мы многократно добавляем единицу к этому числу; "переносы" говорят нам, когда следует выполнять слияние. Ленты пронумерованы от О до Р.

01. [Начальная установка.] Присвоить (A[Z.-1],..., А[0]) <- (О,...,0) и g <- 0. (Во время выполнения этого алгоритма g будет равно (A[Z.-1] ------1-А[0]) modT.)

02. [Распределение.] Записать начальную серию на ленту g в порядке возрастания. Установить / <- 0.

03. [Добавить единицу.] Если / = L, остановиться; результат находится на ленте (-Z.) mod Т в порядке возрастания тогда и только тогда, когда L четно. В противном случае установить А[/] <- А[/] -I-1, g <- (д -I- 1) mod Т.

04. [Перенос?] Если А [/] < Р, то вернуться к шагу 02. В противном случае выполнить слияние на ленту (д - /) modT, установить А[П <- О и g <- (д -I- 1) modT, увеличить / на 1 и вернуться к шагу 03.

2. Следите за числом серий на каждой ленте. Когда исходные данные будут исчерпаны, добавляйте, если необходимо, фиктивные серии, пока не придете к такому положению, когда на каждой ленте будет находиться максимум одна серия и по крайней мере одна лента не будет занята. Затем завершите сортировку посредством еще одного слияния, перемотав сначала некоторые ленты, если это необходимо. (Ориентацию серий можно извлечь из массива А.)

в этот момент Т2 можно перемотать - и окончательное слияние завершит сортировку.

Чтобы избежать бесполезных операций копирования, при которых серии просто сдвигаются вперед или назад, можно в конце шага ВЗ просто сказать "Если исходные данные исчерпаны, перейти к В7" и добавить новый шаг.

В7. [Завершение.] Установить s <--1 и перейти к В2 после повторения следующей

операции до тех пор, пока 1 = 0. Установить s •<- A[Z - и установить q и г равными индексам, таким, что А[Z - 1, д] = -1 и A[Z - 1, г] =-2. (Мы получим q = г и s < A[Z - 1, j] < s + 1, j ф q, j ф r.) Если s - s нечетно, продвинуть уровень I, в противном случае - откатить его (см. ниже). Затем выполнить

слияние на ленте г, читая в обратном порядке; установить Z •<- / - 1, A[Z,д] i--1,

A[Z, г] •<- s -I- 1, г •<- г и повторить.

Здесь "продвижение" означает повторение следующей операции до тех пор, пока {q -(-(-1)*) modT = г: установить р -к- {q + {-ly) modT и скопировать одну серию с ленты р

на ленту q, затем установить А [Z, д] <- s -I-1, A[Z,p] <--1, g <- p. "Откат" уровня означает

повторение следующей операции до тех пор, пока (д - (-l))modT = г: установить р <- (д - (-1)) modT и скопировать одну серию с ленты р на ленту д, затем установить

А[/, д] <- S, A[Z,p] <--1, q i- р. При операции копирования чтение с ленты р выполняется

в обратном направлении, в результате чего направление копируемой серии изменится на противоположное. Если окажется, что при копировании с р на g D[p] > О, то нужно вместо копирования просто уменьшить D\p] и увеличить D[q].

(Основная идея состоит в том, что, если входные данные исчерпаны, желательно исключить, по крайней мере, по одной серии на каждой ленте. Разряд четности каждого неотрицательного элемента А [Z, укажет, является ли серия восходящей или нисходящей. Наименьшее S, при котором изменение алгоритма хоть как-то сказывается, есть + 1. Если Р велико, такое изменение вряд ли когда-нибудь вызовет большое расхождение, но оно позволит компьютеру не выглядеть слишком глупо при некоторых обстоятельствах. Однако и этот алгоритм можно еще дорабатывать, чтобы более эффективно обрабатывался случай S = 1.)

4. На самом деле можно опустить установку А [0,0] на шаге В1 и A[Z, д] на шагах ВЗ и В5. (Однако A[Z, г] должно устанавливаться на шаге ВЗ.) Новый шаг В7 в ответе к предыдущему упражнению требует значение A[Z,g] (если только в явном виде не учитывает, что д = г, как отмечается в указанном ответе).

5. р2* (р 1)р2*-2 < 5 < р2«: npj, некотором jt > 0.

РАЗДЕЛ 5.4.6

1. [23000480/(п-I- 480)J п.

2. В этот момент все записи правого буфера переданы на вывод. На шаге F2 во время слияния проверка "Полон ли буфер вывода?" предшествует проверке "Пуст ли буфер ввода?"; это существенно, иначе пришлось бы ввести дополнительные проверки (если не внести изменения, как в упр. 4).

3. Нет. Например, мы могли бы достичь состояния, в котором Р буферов заполнены на 1/Р и Р - 1 буферов полны, если бы в файле i находились ключи г, i + Р, i + 2Р, ... при 1 < t < Р. Этот пример показывает, что, даже если разрешить одновременное чтение, необходимо иметь 2Р буферов ввода для поддержания непрерывного вывода, если только мы не перераспределяем память для частей буферов и не используем каким-либо образом "чтение вразброс" [Вообще говоря, если в блоках содержится меньше Р-1 записей, требуется меньше 2Р буферов, но этот случай маловероятен.]

4. Раньше устанавливать S (на шагах F1 и F4, а не F3).