\input style
\chapno=5\subchno=4\subsubchno=3\chapnotrue

кАСКАДНОЕ СЛИЯНИЕ, ПОДОБНО МНОГОФАЗНОМУ, НАЧИНАЕТСЯ С
"ТОЧНОГО РАСПРЕДЕЛЕНИЯ" ОТРЕЗКОВ ПО ЛЕНТАМ, ХОТЯ ПРАВИЛА ТОЧНОГО
РАСПРЕДЕЛЕНИЯ ОТЛИЧНЫ ОТ ПРАВИЛ П.~5.4.2. кАЖДАЯ СТРОКА
ТАБЛИЦЫ ПРЕДСТАВЛЯЕТ ПОЛНЫЙ ПРОХОД ПО \emph{ВСЕМ} ДАННЫМ. пРОХОД~2,
НАПРИМЕР, ПОЛУЧАЕТСЯ ПОСРЕДСТВОМ ВЫПОЛНЕНИЯ ПЯТИПУТЕВОГО СЛИЯНИЯ С~T1,
T2, T3, T4, T5 НА~T6, ПОКА~T5 НЕ СТАНЕТ ПУСТОЙ (ПРИ ЭТОМ НА~T6 ПОМЕЩАЮТСЯ
15~ОТРЕЗКОВ ОТНОСИТЕЛЬНОЙ ДЛИНЫ~5), ЗАТЕМ ЧЕТЫРЕХПУТЕВОГО СЛИЯНИЯ С~T1, T2,
T3, T4 НА~T5, ЗАТЕМ ТРЕХПУТЕВОГО СЛИЯНИЯ НА~T4, ДВУХПУТЕВОГО СЛИЯНИЯ
НА~T3 И, НАКОНЕЦ, ОДНОПУТЕВОГО СЛИЯНИЯ (ОПЕРАЦИИ КОПИРОВАНИЯ) С~T1
НА~T2. пРОХОД~3 ПОЛУЧАЕТСЯ ТАКИМ ЖЕ ОБРАЗОМ ПУТЕМ ВЫПОЛНЕНИЯ СНАЧАЛА
ПЯТИПУТЕВОГО СЛИЯНИЯ, ПОКА ОДНА ЛЕНТА НЕ СТАНЕТ ПУСТОЙ, ЗАТЕМ
ЧЕТЫРЕХПУТЕВОГО И~Т.~Д. (пОХОЖЕ, ЧТО ЭТОМУ ПУНКТУ КНИГИ СЛЕДОВАЛО БЫ
ПРИСВОИТЬ НОМЕР~5.4.3.2.1, А НЕ~5.4.3!)

яСНО, ЧТО ОПЕРАЦИИ КОПИРОВАНИЯ ИЗЛИШНИ, И ИХ МОЖНО БЫЛО БЫ ОПУСТИТЬ.
фАКТИЧЕСКИ, ОДНАКО, В СЛУЧАЕ ШЕСТИ ЛЕНТ ЭТО КОПИРОВАНИЕ ЗАНИМАЕТ ТОЛЬКО
НЕБОЛЬШОЙ ПРОЦЕНТ ВСЕГО ВРЕМЕНИ. эЛЕМЕНТЫ, КОТОРЫЕ ПОЛУЧАЮТСЯ ПРОСТЫМ
КОПИРОВАНИЕМ, ОТМЕЧЕНЫ В ПРИВЕДЕННОЙ ТАБЛИЦЕ ЗВЕЗДОЧКОЙ. тОЛЬКО~25 ИЗ~950
ОБРАБАТЫВАЕМЫХ ОТРЕЗКОВ ПРИНАДЛЕЖАТ ЭТОМУ КЛАССУ. бОЛЬШАЯ ЧАСТЬ
ВРЕМЕНИ ОТВОДИТСЯ ПЯТИПУТЕВОМУ И ЧЕТЫРЕХПУТЕВОМУ СЛИЯНИЯМ.

нА ПЕРВЫЙ ВЗГЛЯД МОЖЕТ ПОКАЗАТЬСЯ, ЧТО КАСКАДНАЯ СХЕМА---ДОВОЛЬНО ПЛОХОЙ
ВАРИАНТ В СРАВНЕНИИ С МНОГОФАЗНОЙ, ТАК КАК СТАНДАРТНАЯ МНОГОФАЗНАЯ СХЕМА
ИСПОЛЬЗУЕТ ВСЕ ВРЕМЯ $(T-1)\hbox{-ПУТЕВОЕ}$ СЛИЯНИЕ, В ТО ВРЕМЯ КАК
КАСКАДНАЯ ИСПОЛЬЗУЕТ $(T-1)\hbox{-ПУТЕВОЕ}$, $(T-2)\hbox{-ПУТЕВОЕ}$,
$(T-3)\hbox{-ПУТЕВОЕ}$ И~Т.~Д., НО В ДЕЙСТВИТЕЛЬНОСТИ ОНА АСИМПТОТИЧЕСКИ
\emph{ЛУЧШЕ,} ЧЕМ МНОГОФАЗНАЯ, ДЛЯ ШЕСТИ И БОЛЕЕ ЛЕНТ! кАК МЫ ВИДЕЛИ В
П.~5.4.2, ВЫСОКИЙ ПОРЯДОК СЛИЯНИЯ НЕ ЯВЛЯЕТСЯ ГАРАНТИЕЙ ЭФФЕКТИВНОСТИ. в
ТАБЛ.~1 ПОКАЗАНЫ ХАРАКТЕРИСТИКИ ВЫПОЛНЕНИЯ КАСКАДНОГО СЛИЯНИЯ ПО
АНАЛОГИИ С ПОДОБНОЙ ТАБЛИЦЕЙ П.~5.4.2.

нЕТРУДНО ВЫВЕСТИ "ТОЧНЫЕ РАСПРЕДЕЛЕНИЯ" ДЛЯ КАСКАДНОГО СЛИЯНИЯ. дЛЯ ШЕСТИ
ЛЕНТ ИМЕЕМ
$$
\matrix{
\hbox{уРОВЕНЬ} & T1 & T2 & T3 & T4 & T5 \cr
0 &   1 &   0 &   0 &   0 &  0 \cr
1 &   1 &   1 &   1 &   1 &  1 \cr
2 &   5 &   4 &   3 &   2 &  1 \cr
3 &  15 &  14 &  12 &   9 &  6 \cr
4 &  55 &  50 &  41 &  29 & 15 \cr
5 & 190 & 175 & 146 & 105 & 55 \cr
\multispan{6}\dotfill\cr
n & a_n & b_n & c_n & d_n & e_n \cr
n+1 & a_n+b_n+c_n+d_n+e_n & a_n+b_n+c_n+d_n & a_n+b_n+c_n & a_n+b_n & a_n \cr
}
\eqno(1)
$$
%%344
\htable{тАБЛИЦА 1}%
{хАРАКТЕР ПОВЕДЕНИЯ КАСКАДНОГО СЛИЯНИЯ}%
{\strut\hfill # && \bskip\hfill$#$\hfill\bskip\cr
лЕНТЫ  & \hbox{пРОХОДЫ} & \hbox{пРОХОДЫ} & \hbox{оТНОШЕНИЕ}\cr
 & \hbox{(С КОПИРОВАНИЕМ)} & \hbox{(БЕЗ КОПИРОВАНИЯ)} &\hbox{РОСТА}\cr
\noalign{\hrule}
 3 & 2.078\ln S+0.672 & 1.504\ln S+0.992 &  1.6180340\cr
 4 & 1.235\ln S+0.754 & 1.102\ln S+0.820 &  2.2469796\cr
 5 & 0.946\ln S+0.796 & 0.897\ln S+0.800 &  2.8793852\cr
 6 & 0.796\ln S+0.821 & 0.773\ln S+0.808 &  3.5133371\cr
 7 & 0.703\ln S+0.839 & 0.691\ln S+0.822 &  4.1481149\cr
 8 & 0.639\ln S+0.852 & 0.632\ln S+0.834 &  4.7833861\cr
 9 & 0.592\ln S+0.861 & 0.587\ln S+0.845 &  5.4189757\cr
10 & 0.555\ln S+0.869 & 0.552\ln S+0.854 &  6.0547828\cr
20 & 0.397\ln S+0.905 & 0.397\ln S+0.901 & 12.4174426\cr
\noalign{\hrule}
}

оТМЕТИМ ИНТЕРЕСНОЕ СВОЙСТВО ЭТИХ ЧИСЕЛ---ИХ ОТНОСИТЕЛЬНЫЕ ВЕЛИЧИНЫ ЯВЛЯЮТСЯ
ТАКЖЕ И ДЛИНАМИ ДИАГОНАЛЕЙ ПРАВИЛЬНОГО $(2T-1)\hbox{-УГОЛЬНИКА}$. нАПРИМЕР,
ПЯТЬ ДИАГОНАЛЕЙ ОДИННАДЦАТИУГОЛЬНИКА НА РИС.~73 ИМЕЮТ ОТНОСИТЕЛЬНЫЕ ДЛИНЫ,
ОЧЕНЬ БЛИЗКИЕ К~190, 175, 146, 105 И~55! мЫ ДОКАЖЕМ ЭТОТ ЗАМЕЧАТЕЛЬНЫЙ ФАКТ
\picture{рИС.~73. гЕОМЕТРИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ КАСКАДНЫХ ЧИСЕЛ.}
ПОЗДНЕЕ В ЭТОМ ПУНКТЕ, А ТАКЖЕ УВИДИМ, ЧТО ОТНОСИТЕЛЬНЫЕ ВРЕМЕНА,
ЗАТРАЧИВАЕМЫЕ НА $(T-1)\hbox{-ПУТЕВОЕ}$ СЛИЯНИЕ, $(T-2)\hbox{-ПУТЕВОЕ}$
СЛИЯНИЕ,~\dots, ОДНОПУТЕВОЕ СЛИЯНИЕ, ПРИБЛИЗИТЕЛЬНО ПРОПОРЦИОНАЛЬНЫ
\emph{КВАДРАТАМ} ДЛИН ЭТИХ ДИАГОНАЛЕЙ.

\section *нАЧАЛЬНОЕ РАСПРЕДЕЛЕНИЕ ОТРЕЗКОВ. еСЛИ ЧИСЛО НАЧАЛЬНЫХ
ОТРЕЗКОВ В ДЕЙСТВИТЕЛЬНОСТИ НЕ ЕСТЬ ЧИСЛО фИБОНАЧЧИ, МЫ МОЖЕМ,
КАК ОБЫЧНО, ВСТАВИТЬ ФИКТИВНЫЕ ОТРЕЗКИ. пОВЕРХНОСТНЫЙ АНАЛИЗ СИТУАЦИИ
ПОКАЗЫВАЕТ, ЧТО МЕТОД ПРИПИСЫВАНИЯ ФИКТИВНЫХ ОТРЕЗКОВ НЕСУЩЕСТВЕН, ТАК
КАК КАСКАДНОЕ СЛИЯНИЕ ВСЕГДА ОСУЩЕСТВЛЯЕТ
%%345
ПОЛНЫЕ ПРОХОДЫ; ЕСЛИ ИМЕЕТСЯ 190~НАЧАЛЬНЫХ ОТРЕЗКОВ, ТО КАЖДАЯ ЗАПИСЬ
ОБРАБАТЫВАЕТСЯ ПЯТЬ РАЗ, КАК В ПРИВЕДЕННОМ ВЫШЕ ПРИМЕРЕ, НО ЕСЛИ ИМЕЕТСЯ
191~ОТРЕЗОК, ТО, ОЧЕВИДНО, СЛЕДУЕТ УВЕЛИЧИТЬ УРОВЕНЬ, И ТЕПЕРЬ КАЖДАЯ
ЗАПИСЬ БУДЕТ ОБРАБАТЫВАТЬСЯ ШЕСТЬ РАЗ. к СЧАСТЬЮ, В ДЕЙСТВИТЕЛЬНОСТИ МОЖНО
ИЗБЕЖАТЬ ТАКОГО РЕЗКОГО СКАЧКА. дЭВИД~э.~фЕРГЮСОН НАШЕЛ СПОСОБ ТАК
РАСПРЕДЕЛИТЬ НАЧАЛЬНЫЕ ОТРЕЗКИ, ЧТО МНОГИЕ ОПЕРАЦИИ ВО ВРЕМЯ ПЕРВОЙ
\picture{
  рИС.~74. эФФЕКТИВНОСТЬ КАСКАДНОГО СЛИЯНИЯ С РАСПРЕДЕЛЕНИЕМ
  ПО АЛГОРИТМУ~D.
}
ФАЗЫ СЛИЯНИЯ СВОДЯТСЯ К КОПИРОВАНИЮ СОДЕРЖИМОГО ЛЕНТЫ. еСЛИ ОБОЙТИ ТАКИЕ
КОПИРОВАНИЯ (ПРОСТО ИЗМЕНИВ "ЛОГИЧЕСКИЕ" НОМЕРА ЛЕНТОЧНЫХ УСТРОЙСТВ ПО
ОТНОШЕНИЮ К "ФИЗИЧЕСКИМ" НОМЕРАМ, КАК В АЛГОРИТМЕ~5.4.2D), ТО ПОЛУЧИМ
ОТНОСИТЕЛЬНО ПЛАВНЫЙ ПЕРЕХОД С УРОВНЯ НА УРОВЕНЬ, КАК ИЗОБРАЖЕНО НА РИС.~74.

пРЕДПОЛОЖИМ, ЧТО $(a, b, c, d, e)$, ГДЕ~$a\ge b \ge c \ge d \ge e$---ТОЧНОЕ
РАСПРЕДЕЛЕНИЕ. пЕРЕОПРЕДЕЛИВ СООТВЕТСТВИЕ МЕЖДУ ЛОГИЧЕСКИМИ
И ФИЗИЧЕСКИМИ ЛЕНТОЧНЫМИ УСТРОЙСТВАМИ, МЫ МОЖЕМ ПРЕДСТАВИТЬ, ЧТО РЕАЛЬНОЕ
РАСПРЕДЕЛЕНИЕ---ЭТО~$(e, d, c, b, a)$,
%%346
Т.~Е.~$a$~ОТРЕЗКОВ НА~T5, $b$~НА~т4 И~Т.~Д. сЛЕДУЮЩЕЕ ТОЧНОЕ
РАСПРЕДЕЛЕНИЕ---ЭТО $(a+b+c+d+e,  a+b+c+d, a+b+c, a+b, a)$;
И ЕСЛИ ВВОД ИСЧЕРПЫВАЕТСЯ ПРЕЖДЕ, ЧЕМ МЫ ДОСТИГАЕМ ЭТОГО СЛЕДУЮЩЕГО
УРОВНЯ, ТО БУДЕМ СЧИТАТЬ, ЧТО ЛЕНТЫ СОДЕРЖАТ
СООТВЕТСТВЕННО~$(D_1, D_2, D_3, D_4, D_5)$ ФИКТИВНЫХ ОТРЕЗКОВ, ГДЕ
$$
\displaynarrow{
D_1 \le a+b+c+d,\quad D_1 \le a+b+c,\quad D_3\le a+b,\cr
D_4 \le a,\quad D_5=0;\qquad D_1\ge D_2 \ge D_3 \ge D_4 \ge D_5.\cr
}
\eqno(2)
$$

мЫ ВОЛЬНЫ ПРЕДСТАВЛЯТЬ СЕБЕ, ЧТО ЭТИ ФИКТИВНЫЕ ОТРЕЗКИ ПОЯВЛЯЮТСЯ НА
ЛЕНТАХ В ЛЮБОМ УДОБНОМ МЕСТЕ. пРЕДПОЛАГАЕТСЯ, ЧТО ПЕРВЫЙ ПРОХОД СЛИЯНИЯ
ДАСТ $a$~ОТРЕЗКОВ ПОСРЕДСТВОМ ПЯТИПУТЕВОГО СЛИЯНИЯ, ЗАТЕМ $b$~ОТРЕЗКОВ
ПОСРЕДСТВОМ ЧЕТЫРЕХПУТЕВОГО И~Т.~Д. нАША ЦЕЛЬ СОСТОИТ В РАСПОЛОЖЕНИИ
ФИКТИВНЫХ ОТРЕЗКОВ ТАКИМ ОБРАЗОМ, ЧТОБЫ ЗАМЕНИТЬ СЛИЯНИЕ КОПИРОВАНИЕМ.
уДОБНО ВЫПОЛНЯТЬ ПЕРВЫЙ ПРОХОД СЛИЯНИЯ СЛЕДУЮЩИМ ОБРАЗОМ:

1.~еСЛИ~$D_4=a$, ТО ВЫЧЕСТЬ~$a$ ИЗ ВСЕХ~$D_1$, $D_2$, $D_3$, $D_4$ И
ЗАЯВИТЬ, ЧТО~T5---РЕЗУЛЬТАТ СЛИЯНИЯ. еСЛИ~$D_4<a$, ТО СЛИТЬ $a$~ОТРЕЗКОВ С
ЛЕНТ~T1 ПО~T5, ИСПОЛЬЗУЯ МИНИМАЛЬНО ВОЗМОЖНОЕ ЧИСЛО ФИКТИВНЫХ ОТРЕЗКОВ
НА ЛЕНТАХ~T1--T5 ТАК, ЧТОБЫ НОВЫЕ ЗНАЧЕНИЯ~$D_1$, $D_2$, $D_3$, $D_4$
УДОВЛЕТВОРЯЛИ СООТНОШЕНИЯМ
$$
\displaynarrow{
D_1\le b+c+d,\quad D_2\le b+c,\quad D_3\le b,\cr
D_4=0;\qquad  D_1\ge D_2\ge D_3\ge D_4.\cr
}
\eqno(3)
$$
тАКИМ ОБРАЗОМ, ЕСЛИ~$D_2$ БЫЛО ПЕРВОНАЧАЛЬНО~$\le b+c$, ТО МЫ
НЕ ИСПОЛЬЗУЕМ НИ ОДНОГО ФИКТИВНОГО ОТРЕЗКА С ЭТОЙ ЛЕНТЫ НА ДАННОМ ШАГЕ; В
ТО ЖЕ ВРЕМЯ, ЕСЛИ~$b+c<D_2\le a+b+c$, МЫ ИСПОЛЬЗУЕМ РОВНО~$D_2-b-c$
ФИКТИВНЫХ ОТРЕЗКОВ.

2.~(эТОТ ШАГ АНАЛОГИЧЕН ШАГУ~1, НО С НЕКОТОРЫМ "СДВИГОМ".) еСЛИ~$D_3=b$,
ТО ВЫЧЕСТЬ~$b$ ИЗ ВСЕХ~$D_1$, $D_2$, $D_3$ И ЗАЯВИТЬ, ЧТО~T4---РЕЗУЛЬТАТ
СЛИЯНИЯ. еСЛИ~$D_3<b$, ТО СЛИТЬ $b$~ОТРЕЗКОВ С ЛЕНТ~T1--T4, УМЕНЬШАЯ, ЕСЛИ
НЕОБХОДИМО, ЧИСЛО ФИКТИВНЫХ ОТРЕЗКОВ, ЧТОБЫ ДОСТИЧЬ
$$
D_1\le b+c,\quad D_2\le b,\quad D_3=0;\qquad D_1\ge D_2\ge D_3.
$$

3.~и ТАК ДАЛЕЕ.

мЕТОД фЕРГЮСОНА РАСПРЕДЕЛЕНИЯ ОТРЕЗКОВ ПО ЛЕНТАМ МОЖНО ПРОИЛЛЮСТРИРОВАТЬ,
РАССМОТРЕВ ПРОЦЕСС ПЕРЕХОДА С УРОВНЯ~3 НА УРОВЕНЬ~4 В~(1). дОПУСТИМ, ЧТО
"ЛОГИЧЕСКИЕ" ЛЕНТЫ (T1,~\dots, T5) СОДЕРЖАЛИ СООТВЕТСТВЕННО
$(5, 9, 12, 14, 15)$~ОТРЕЗКОВ И ЧТО МЫ ХОТИМ ДОВЕСТИ ЭТО В КОНЕЧНОМ ИТОГЕ
ДО~$(55, 50, 41, 29, 15)$. эТА ПРОЦЕДУРА МОЖЕТ БЫТЬ КРАТКО ЗАПИСАНА ТАК:
%%347
\ctable{
$#$\hfill&&\hfill\bskip$#$\bskip\hfill\cr
 & \hbox{дОБАВИТЬ} &\hbox{дОБАВИТЬ} &\hbox{дОБАВИТЬ} &\hbox{дОБАВИТЬ} &\hbox{дОБАВИТЬ} &\hbox{сЭКОНОМЛЕННАЯ}\cr
\hbox{шАГ} &\hbox{К T1} &\hbox{К T2} &\hbox{К T3} &\hbox{К T4} &\hbox{К T5} &\hbox{ВЕЛИЧИНА}\cr
(1, 1)& 9 &  0 &  0 &  0 &  0 & 15+14+12+5\cr
(2, 2)& 3 & 12 &  0 &  0 &  0 &  15+14+9+5\cr
(2, 1)& 9 &  0 &  0 &  0 &  0 &    15+14+5\cr
(3, 3)& 2 &  2 & 14 &  0 &  0 &    15+12+5\cr
(3, 2)& 3 & 12 &  0 &  0 &  0 &     15+9+5\cr
(3, 1)& 9 &  0 &  0 &  0 &  0 &       15+5\cr
(4, 4)& 1 &  1 &  1 & 15 &  0 &       14+5\cr
(4, 3)& 2 &  2 & 14 &  0 &  0 &       12+5\cr
(4, 2)& 3 & 12 &  0 &  0 &  0 &        9+5\cr
(4, 1)& 9 &  0 &  0 &  0 &  0 &          5\cr
}
сНАЧАЛА ПОМЕЩАЕМ ДЕВЯТЬ ОТРЕЗКОВ НА~T1, ЗАТЕМ $(3, 12)$---НА~T1 И~T2 И~Т.~Д.
еСЛИ ВВОД ИСЧЕРПАЕТСЯ, СКАЖЕМ, ВО ВРЕМЯ ШАГА~$(3, 2)$, ТО "СЭКОНОМЛЕННАЯ
ВЕЛИЧИНА" СОСТАВЛЯЕТ~$15+9+5$. эТО ОЗНАЧАЕТ, ЧТО МЫ ИЗБЕГАЕМ ПЯТИПУТЕВОГО
СЛИЯНИЯ 15~ОТРЕЗКОВ,  ДВУХПУТЕВОГО СЛИЯНИЯ 9~ОТРЕЗКОВ И ОДНОПУТЕВОГО
СЛИЯНИЯ 5~ОТРЕЗКОВ ПОСРЕДСТВОМ ПРИСВОЕНИЯ ФИКТИВНЫХ ОТРЕЗКОВ.
дРУГИМИ СЛОВАМИ, $15+9+5$ ОТРЕЗКОВ, ПРИСУТСТВУЮЩИХ НА УРОВНЕ~3,
НЕ ОБРАБАТЫВАЮТСЯ В ТЕЧЕНИЕ ПЕРВОЙ ФАЗЫ СЛИЯНИЯ.

сЛЕДУЮЩИЙ АЛГОРИТМ ДЕТАЛЬНО ОПИСЫВАЕТ ЭТОТ ПРОЦЕСС.

\alg C.(сОРТИРОВКА КАСКАДНЫМ СЛИЯНИЕМ СО СПЕЦИАЛЬНЫМ РАСПРЕДЕЛЕНИЕМ.) эТОТ
АЛГОРИТМ РАСПРЕДЕЛЯЕТ НАЧАЛЬНЫЕ ОТРЕЗКИ ПО ЛЕНТАМ ОТРЕЗОК ЗА ОТРЕЗКОМ,
ПОКА ЗАПАС НАЧАЛЬНЫХ ОТРЕЗКОВ НЕ ИСЧЕРПАЕТСЯ. зАТЕМ ОН ОПРЕДЕЛЯЕТ, КАК
СЛЕДУЕТ СЛИВАТЬ ЛЕНТЫ, ПРЕДПОЛАГАЯ, ЧТО ИМЕЕТСЯ $T\ge 3$~ЛЕНТОПРОТЯЖНЫХ
УСТРОЙСТВ, ПРИ ЭТОМ ИСПОЛЬЗУЕТСЯ САМОЕ БОЛЬШЕЕ
$(T-1)\hbox{-ПУТЕВОЕ}$~СЛИЯНИЕ И
НЕНУЖНЫЕ ОДНОПУТЕВЫЕ СЛИЯНИЯ УСТРАНЯЮТСЯ. лЕНТА~$T$ МОЖЕТ
БЫТЬ ИСПОЛЬЗОВАНА ДЛЯ ХРАНЕНИЯ ВВОДА, ТАК КАК НА НЕЕ НЕ ПОПАДАЕТ НИ ОДИН
НАЧАЛЬНЫЙ ОТРЕЗОК. аЛГОРИТМ РАБОТАЕТ СО СЛЕДУЮЩИМИ МАССИВАМИ:
{\let\mypar=\par\ctable{
$#$,\bskip\hfill&$#$:\bskip\hfill&
\vtop{\parindent=0pt \hsize=13cm #\mypar}\cr
|A|[j]    & 1 \le j \le T &
   пОСЛЕДНЕЕ ТОЧНОЕ КАСКАДНОЕ РАСПРЕДЕЛЕНИЕ, КОТОРОЕ БЫЛО ДОСТИГНУТО. \cr
|AA|[j]   & 1 \le j \le T &
   тОЧНОЕ КАСКАДНОЕ РАСПРЕДЕЛЕНИЕ, К КОТОРОМУ МЫ СТРЕМИМСЯ. \cr
|D|[j]    & 1 \le j \le T &
   чИСЛО ФИКТИВНЫХ ОТРЕЗКОВ, ПРЕДПОЛАГАЕМЫХ ПРИСУТСТВУЮЩИМИ НА ЛОГИЧЕСКОМ
   ЛЕНТОПРОТЯЖНОМ УСТРОЙСТВЕ С НОМЕРОМ~$j$. \cr
|M|[j]    & 1 \le j \le T &
   мАКСИМАЛЬНОЕ ЧИСЛО ФИКТИВНЫХ ОТРЕЗКОВ, КОТОРОЕ ЖЕЛАТЕЛЬНО ИМЕТЬ НА
   ЛОГИЧЕСКОМ ЛЕНТОПРОТЯЖНОМ УСТРОЙСТВЕ С НОМЕРОМ~$j$. \cr
|TAPE|[j] & 1 \le j \le T &
   нОМЕР ФИЗИЧЕСКОГО ЛЕНТОПРОТЯЖНОГО УСТРОЙСТВА, СООТВЕТСТВУЮЩЕГО
   ЛОГИЧЕСКОМУ ЛЕНТОПРОТЯЖНОМУ УСТРОЙСТВУ С НОМЕРОМ~$j$.\cr
}}
%%348
\st[нАЧАЛЬНАЯ УСТАНОВКА.] уСТАНОВИТЬ $|A|[k]\asg |AA|[k]\asg |D|[k]\asg 0$
ПРИ~$2\le k \le T$; УСТАНОВИТЬ $|A|[1]\asg 0$, $|AA|[1]\asg 1$,
$|D|[1]\asg 1$; УСТАНОВИТЬ~$|TAPE|[k]\asg k$ ПРИ~$1\le k \le T$. нАКОНЕЦ,
УСТАНОВИТЬ~$i\asg T-2$, $j\asg 1$, $k\asg 1$, $l\asg 0$, $m\asg 1$ И
ПЕРЕЙТИ К ШАГУ~\stp{5} (ЭТИ МАНЕВРЫ ЯВЛЯЮТСЯ ОДНИМ ИЗ СПОСОБОВ НАЧАТЬ
РАБОТУ НЕПОСРЕДСТВЕННО ВО ВНУТРЕННЕМ ЦИКЛЕ С СООТВЕТСТВУЮЩЕЙ УСТАНОВКОЙ
УПРАВЛЯЮЩИХ ПЕРЕМЕННЫХ).

\st[нАЧАТЬ НОВЫЙ УРОВЕНЬ.] (мЫ ТОЛЬКО ЧТО ПОЛУЧИЛИ ТОЧНОЕ РАСПРЕДЕЛЕНИЕ.
нО ТАК КАК ЕЩЕ ИМЕЮТСЯ ИСХОДНЫЕ ДАННЫЕ, ТО НЕОБХОДИМО ПОДГОТОВИТЬСЯ К
СЛЕДУЮЩЕМУ УРОВНЮ.) уВЕЛИЧИТЬ~$l$ НА~1. уСТАНОВИТЬ~$|A|[k]\asg |AA|[k]$
ПРИ~$1\le k \le T$, ЗАТЕМ УСТАНОВИТЬ~$|AA|[T-k]\asg |AA|[T-k+1]+|A|[k]$
ПРИ~$k=1$, 2,~\dots, $T-1$ (В ТАКОМ ПОРЯДКЕ). уСТАНОВИТЬ $(|TAPE|[1],
|TAPE|[2],~\ldots, |TAPE|[T-1])\asg (|TAPE|[T-1],~\ldots, |TAPE|[2],
|TAPE|[1])$ И УСТАНОВИТЬ~$|D|[k]\asg |AA|[k+1]$ ПРИ~$1\le k < T$.
нАКОНЕЦ, УСТАНОВИТЬ~$i\asg 1$.

\st[нАЧАТЬ ПОДУРОВЕНЬ~$i$.] уСТАНОВИТЬ~$j\asg i$. (пЕРЕМЕННЫЕ~$i$
И~$j$ ПРЕДСТАВЛЯЮТ "ШАГ~$(i,j)$" В ТАБЛИЦЕ, ИЛЛЮСТРИРУЮЩЕЙ МЕТОД фЕРГЮСОНА.)

\st[нАЧАТЬ ШАГ~$(i, j)$.] уСТАНОВИТЬ~$k\asg j$ И~$m\asg
|A|[T-j-1]$. еСЛИ~$m=0$ И~$i=j$, ТО УСТАНОВИТЬ~$i\asg T-2$ И
ВЕРНУТЬСЯ К~\stp{3}; ЕСЛИ~$m=0$ И~$i\ne j$, ВЕРНУТЬСЯ К~\stp{2}.
(пЕРЕМЕННАЯ~$m$ ПРЕДСТАВЛЯЕТ СОБОЙ ЧИСЛО ОТРЕЗКОВ, КОТОРОЕ ДОЛЖНО
БЫТЬ ЗАПИСАНО НА ЛЕНТУ~$|TAPE|[k]$; $m$~БЫВАЕТ РАВНО~0, ТОЛЬКО ЕСЛИ~$l=1$.)

\st[вВЕСТИ НА ЛЕНТУ~$|TAPE|[k]$.] зАПИСАТЬ ОДИН ОТРЕЗОК НА
ЛЕНТУ НОМЕР~$|TAPE|[k]$ И УМЕНЬШИТЬ~$|D|[k]$ НА~1. зАТЕМ, ЕСЛИ
ВВОД ИСЧЕРПАН, ПЕРЕМОТАТЬ ВСЕ ЛЕНТЫ И ПЕРЕЙТИ К ШАГУ~\stp{7}.

\st[пРОДВИЖЕНИЕ.] уМЕНЬШИТЬ~$m$ НА~1. еСЛИ~$m>0$, ВЕРНУТЬСЯ К ШАГУ~\stp{5}.
 в ПРОТИВНОМ СЛУЧАЕ УМЕНЬШИТЬ~$k$ НА~1; ЕСЛИ~$k>0$, УСТАНОВИТЬ~$m\asg
|A|[T-j-1]-|A|[T-j]$ И ВЕРНУТЬСЯ К~\stp{5}, ЕСЛИ~$m>0$. в ПРОТИВНОМ СЛУЧАЕ
УМЕНЬШИТЬ~$j$ НА~1;
ЕСЛИ~$j>0$, ПЕРЕЙТИ К ШАГУ~\stp{4}. в ПРОТИВНОМ СЛУЧАЕ УВЕЛИЧИТЬ~$i$
НА~1; ЕСЛИ~$i<T<1$, ВЕРНУТЬСЯ К ШАГУ~\stp{3}. в ПРОТИВНОМ СЛУЧАЕ ПЕРЕЙТИ
К~\stp{2}.

\st[пОДГОТОВКА К СЛИЯНИЮ.] (к ЭТОМУ МОМЕНТУ НАЧАЛЬНОЕ РАСПРЕДЕЛЕНИЕ
ЗАВЕРШЕНО, И ТАБЛИЦЫ~|A|, |AA|, |D| И~|TAPE| ОПИСЫВАЮТ СОСТОЯНИЕ ВСЕХ
ЛЕНТ В ДАННЫЙ МОМЕНТ.) уСТАНОВИТЬ~$|M|[k]\asg|AA|[k+1]$ ПРИ~$1\le k < T$ И
УСТАНОВИТЬ~$|FIRST|\asg 1$. (пЕРЕМЕННАЯ~|FIRST| ПРИНИМАЕТ НЕНУЛЕВОЕ
ЗНАЧЕНИЕ ТОЛЬКО ВО ВРЕМЯ ПЕРВОГО ПРОХОДА СЛИЯНИЯ.)

\st[кАСКАД.] еСЛИ~$l=0$, ОСТАНОВИТЬСЯ; СОРТИРОВКА ЗАВЕРШЕНА, ВЫВОД
НАХОДИТСЯ НА~$|TAPE|[1]$. в ПРОТИВНОМ СЛУЧАЕ ПРИ~$p=T-1$, $T-2$,~\dots, 1
(В ТАКОМ ПОРЯДКЕ) ВЫПОЛНЯТЬ $p\hbox{-ПУТЕВОЕ}$ СЛИЯНИЕ С
ЛЕНТ~$|TAPE|[1]$,~\dots, $|TAPE|[p]$ НА~$|TAPE|[p+1]$ СЛЕДУЮЩИМ ОБРАЗОМ:
%% 349

еСЛИ~$p=1$, ТО МОДЕЛИРОВАТЬ ОДНОПУТЕВОЕ СЛИЯНИЕ
ОБЫЧНОЙ ПЕРЕМОТКОЙ~$|TAPE|[2]$ И ЗАМЕНОЙ~$|TAPE|[1]\xchg |TAPE|[2]$. в
ПРОТИВНОМ СЛУЧАЕ, ЕСЛИ~$|FIRST|=1$ И~$|D|[p-1]=|M|[p-1]$, ТО МОДЕЛИРОВАТЬ
$p\hbox{-ПУТЕВОЕ}$ СЛИЯНИЕ, ПРОСТО ПОМЕНЯВ $|TAPE|[p]\xchg |TAPE|[p+1]$,
ПЕРЕМОТАВ~$|TAPE|[p]$ И ВЫЧТЯ~$M[p-1]$ ИЗ КАЖДОГО~$|D|[1]$,~\dots,
$|D|[p-1]$, $|M|[1]$,~\dots, $|M|[p-1]$. в ПРОТИВНОМ СЛУЧАЕ
ВЫЧЕСТЬ~$|M|[p-1]$ ИЗ ВСЕХ~$|M|[1]$,~\dots, $|M|[p-1]$. зАТЕМ СЛИТЬ ПО
ОДНОМУ ОТРЕЗКУ С КАЖДОЙ~$|TAPE|[j]$, ТАКОЙ, ЧТО~$1\le j \le p$
И~$|D|[j]\le |M|[j]$; ВЫЧЕСТЬ ЕДИНИЦУ ИЗ КАЖДОГО~$|D|[j]$, ТАКОГО,
ЧТО~$1\le j \le p$ И~$|D|[j]>|M|[j]$, И ПОМЕСТИТЬ ВЫВОДНОЙ ОТРЕЗОК
НА~$|TAPE|[p+1]$. пРОДОЛЖАТЬ РАБОТУ, ПОКА $|TAPE|[p]$ НЕ СТАНЕТ ПУСТОЙ.
зАТЕМ ПЕРЕМОТАТЬ~$|TAPE|[p]$ И~$|TAPE|[p+1]$.

\st[оПУСТИТЬСЯ НА ОДИН УРОВЕНЬ.] уМЕНЬШИТЬ~$l$ НА~1,
УСТАНОВИТЬ~$|FIRST|\asg 0$, УСТАНОВИТЬ
$(|TAPE|[1],~\ldots, |TAPE|[T])\asg (|TAPE|[T],~\ldots, |TAPE|[1])$. (к
ЭТОМУ МОМЕНТУ ВСЕ~|D| И~|M|---НУЛИ И ТАКОВЫМИ ОСТАНУТСЯ.) вЕРНУТЬСЯ К~\stp{8}.
\algend

шАГИ~C1--C6 ЭТОГО АЛГОРИТМА ВЫПОЛНЯЮТ РАСПРЕДЕЛЕНИЕ, ШАГИ~C7--C9 ВЫПОЛНЯЮТ
СЛИЯНИЕ; ЭТИ ДВЕ ЧАСТИ СОВЕРШЕННО НЕЗАВИСИМЫ ОДНА ОТ ДРУГОЙ, И МОЖНО БЫЛО
БЫ ХРАНИТЬ~$|M|[k]$ И~$|AA|[k+1]$ В ОДНИХ И ТЕХ ЖЕ ЯЧЕЙКАХ ПАМЯТИ.
\picture{рИС.~75. кАСКАДНОЕ СЛИЯНИЕ СО СПЕЦИАЛЬНЫМ РАСПРЕДЕЛЕНИЕМ.}
\section *аНАЛИЗ КАСКАДНОГО СЛИЯНИЯ. кАСКАДНОЕ СЛИЯНИЕ ПОДДАЕТСЯ АНАЛИЗУ
С БОЛЬШИМ ТРУДОМ, ЧЕМ МНОГОФАЗНОЕ. нО ЭТОТ АНАЛИЗ ОСОБЕННО ИНТЕРЕСЕН,
ПОСКОЛЬКУ СОДЕРЖИТ МНОГО ЗАМЕЧАТЕЛЬНЫХ ФОРМУЛ. нАСТОЯТЕЛЬНО РЕКОМЕНДУЕМ
ЧИТАТЕЛЯМ, ИНТЕРЕСУЮЩИМСЯ ДИСКРЕТНОЙ МАТЕМАТИКОЙ, САМОСТОЯТЕЛЬНО
ПРОАНАЛИЗИРОВАТЬ КАСКАДНОЕ РАСПРЕДЕЛЕНИЕ, ПРЕЖДЕ ЧЕМ ЧИТАТЬ ДАЛЬШЕ, ВЕДЬ ЧИСЛА
%%350
ИМЕЮТ ТАК МНОГО НЕОБЫЧНЫХ СВОЙСТВ, ОТКРЫВАТЬ КОТОРЫЕ---ОДНО УДОВОЛЬСТВИЕ! мЫ
ОБСУДИМ ЗДЕСЬ ЛИШЬ ОДИН ИЗ МНОГИХ ПОДХОДОВ, ОБРАЩАЯ ОСОБОЕ ВНИМАНИЕ НА
МЕТОДЫ ПОЛУЧЕНИЯ РЕЗУЛЬТАТОВ.

дЛЯ УДОБСТВА РАССМОТРИМ СЛУЧАЙ ШЕСТИ ЛЕНТ. пРИ ЭТОМ БУДЕМ СТАРАТЬСЯ
ПОЛУЧИТЬ ФОРМУЛЫ, КОТОРЫЕ ОБОБЩАЮТСЯ НА СЛУЧАЙ ЛЮБОГО~$T$. сООТНОШЕНИЯ~(1)
ПРИВОДЯТ К ПЕРВОЙ ОСНОВНОЙ СИСТЕМЕ:
$$
\eqalignter{
a_n &= a_n &=\perm{0}{0}a_n,\cr
b_n &= a_n-e_{n-1}=a_n-a_{n-2} &=\perm{1}{0}a_n-\perm{2}{2}a_{n-2},\cr
c_n &= b_n-d_{n-1}=b_n-a_{n-2}-b_{n-2} &=\perm{2}{0}a_n-\perm{3}{2}a_{n-2}+\perm{4}{4}a_{n-4},\cr
d_n &= c_n-c_{n-1}=c_n-a_{n-2}-b_{n-2}-c_{n-2} &=\perm{3}{0}a_n-\perm{4}{2}a_{n-2}+\perm{5}{4}a_{n-4}-\perm{6}{6}a_{n-6},\cr
e_n &= d_n-b_{n-1}=d_n-a_{n-2}-b_{n-2}-c_{n-2}-d_{n-2} &=\perm{4}{0}a_n-\perm{5}{2}a_{n-2}+\perm{6}{4}a_{n-4}-\perm{7}{6}a_{n-6}+\perm{8}{8}a_{n-8}.\cr
}
\eqno(4)
$$
оБОЗНАЧИМ~$A(z)=\sum_{n\ge0} a_n z^n$,~\dots, $E(z)=\sum_{n\ge0}e_n z^n$ И
ОПРЕДЕЛИМ МНОГОЧЛЕНЫ
$$
\eqalignno{
q_m(z)&=\perm{m}{0}-\perm{m+1}{2}z^2+\perm{m+2}{4}z^4-\cdots=\cr
      &=\sum_{k\ge 0}\perm{m+k}{2k}(-1)^k z^{2k}
        = \sum_{0\le k \le m}\perm{2m-k}{k}(-1)^{m-k} z^{2m-2k}. & (5)\cr
}
$$
рЕЗУЛЬТАТ~(4) КРАТКО МОЖНО ИСТОЛКОВАТЬ ТАК,
ЧТО~$B(z)-q_1(z)\times A(z)$,~\dots, $E(z)-q_4(z)A(z)$ СВОДЯТСЯ К
КОНЕЧНЫМ СУММАМ, СООТВЕТСТВУЮЩИМ
ГРАНИЧНЫМ УСЛОВИЯМ, А ИМЕННО ЗНАЧЕНИЯМ~$a_{-1}$, $a_{-2}$, $a_{-3}$,~\dots,
КОТОРЫЕ ПОЯВЛЯЮТСЯ В~(4) (ПРИ НЕБОЛЬШИХ~$n$), НО НЕ В~$A(z)$. чТОБЫ
ПОЛУЧИТЬ ПОДХОДЯЩИЕ ГРАНИЧНЫЕ УСЛОВИЯ, ПРИМЕНИМ РЕКУРРЕНТНОЕ СООТНОШЕНИЕ
В ОБРАТНУЮ СТОРОНУ ДЛЯ ОТРИЦАТЕЛЬНЫХ УРОВНЕЙ ДО УРОВНЯ~$-8$:
\ctable{
\hfill$#$\bskip&&\hfill\bskip$#$\bskip\cr
\hfill n & \hfill a_n & \hfill b_n & \hfill c_n & \hfill d_n & \hfill e_n \cr
 0 &  1 &   0 &  0 &   0 &  0\cr
-1 &  0 &   0 &  0 &   0 &  1\cr
-2 &  1 &  -1 &  0 &   0 &  0\cr
-3 &  0 &   0 &  0 &  -1 &  2\cr
-4 &  2 &  -3 &  1 &   0 &  0\cr
-5 &  0 &   0 &  1 &  -4 &  5\cr
-6 &  5 &  -9 &  5 &  -1 &  0\cr
-7 &  0 &  -1 &  6 & -14 & 14\cr
-8 & 14 & -28 & 20 &  -7 &  1\cr
}
(дЛЯ СЕМИ ЛЕНТ ТАБЛИЦА БЫЛА БЫ АНАЛОГИЧНОЙ, ОДНАКО СТРОКИ С НЕЧЕТНЫМИ~$n$
БЫЛИ БЫ СДВИНУТЫ ВПРАВО НА ОДИН ЭЛЕМЕНТ.) тАЙНА
ПОСЛЕДОВАТЕЛЬНОСТИ~$a_0$, $a_{-2}$, $a_{-4},~\ldots=1, 1, 2, 5, 14,~\ldots$
МГНОВЕННО РАСКРЫВАЕТСЯ СПЕЦИАЛИСТОМ ПО ИНФОРМАТИКЕ, ТАК КАК
%%351
ЭТА ПОСЛЕДОВАТЕЛЬНОСТЬ ВСТРЕЧАЕТСЯ В СВЯЗИ С ОЧЕНЬ МНОГИМИ РЕКУРРЕНТНЫМИ
АЛГОРИТМАМИ (НАПРИМЕР, В УПР.~2.2.1-4 И ФОРМУЛЕ~2.3.4.4-13)). иТАК, МЫ
ПРЕДПОЛАГАЕМ, ЧТО В СЛУЧАЕ $T$~ЛЕНТ
$$
\eqalignrem{
a_{-2n}&=\perm{2n}{n}{1\over n+1} & ПРИ $0\le n \le T-2$; \cr
a_{-2n-1}&=0 & ПРИ $0\le n \le T-3$.\cr
}
\eqno(6)
$$
чТОБЫ ПРОВЕРИТЬ ПРАВИЛЬНОСТЬ ЭТОГО ПРЕДПОЛОЖЕНИЯ, ДОСТАТОЧНО ПОКАЗАТЬ,
ЧТО~(6) И~(4) ПРИВОДЯТ К ПРАВИЛЬНЫМ РЕЗУЛЬТАТАМ ДЛЯ УРОВНЕЙ~0 И~1. дЛЯ
УРОВНЯ~1 ЭТО ОЧЕВИДНО, А ДЛЯ УРОВНЯ~0 НАМ НАДО ПРОВЕРИТЬ, ЧТО
$$
\perm{m}{0}a_0-\perm{m+1}{2}a_{-2}+\perm{m+2}{4}a_{-4}-\perm{m+3}{6}a_{-6}+\cdots
=\sum_{k\ge0}\perm{m+k}{2k}\perm{2k}{k}{(-1)^k\over k+1}
=\delta_{m0}
\eqno(7)
$$
ДЛЯ~$0\le m \le T-2$. к СЧАСТЬЮ, ЭТУ СУММУ МОЖНО ВЫЧИСЛИТЬ СТАНДАРТНЫМИ
МЕТОДАМИ (ЭТО "ЗАДАЧА~2", ОДИН ИЗ ОСНОВНЫХ ПРИМЕРОВ В ТЕКСТЕ П.~4.2.6).

тЕПЕРЬ МОЖНО ВЫЧИСЛИТЬ КОЭФФИЦИЕНТЫ~$B(z)-q_1(z)A(z)$ И~Т.~Д. рАССМОТРИМ,
НАПРИМЕР, КОЭФФИЦИЕНТ ПРИ~$z^{2m}$ В~$D(z)-q_3(z)A(z)$. оН РАВЕН
$$
\eqalign{
\sum_{k\ge0}\perm{3+m+k}{2m+2k}(-1)^{m+k}a_{-2k}
&=\sum_{k\ge0}\perm{3+m+k}{2m+2k}\perm{2k}{k}{(-1)^{m+k}\over k+1}=\cr
&=(-1)^m\left(\perm{2+m}{2m-1}-\perm{3+m}{2m}\right)=\cr
&=(-1)^{m+1}\perm{2+m}{2m}\cr
}
$$
ИЗ РЕЗУЛЬТАТА "ЗАДАЧИ~3" В~П.~1.2.6. тАКИМ ОБРАЗОМ, МЫ ВЫВЕЛИ ФОРМУЛЫ
$$
\eqalign{
A(z) &=q_0(z)A(z);\cr
B(z) &=q_1(z)A(z)-q_0(z);\cr
C(z) &=q_2(z)A(z)-q_1(z);\cr
D(z) &=q_3(z)A(z)-q_2(z);\cr
E(z) &=q_4(z)A(z)-q_3(z).\cr
}
\eqno (8)
$$
кРОМЕ ТОГО, ИМЕЕМ~$e_{n+1}=a_n$; СЛЕДОВАТЕЛЬНО, $zA(z)=E(z)$ И
$$
A(z)=q_3(z)/(q_4(z)-z).
\eqno (9)
$$

пРОИЗВОДЯЩИЕ ФУНКЦИИ БЫЛИ ВЫРАЖЕНЫ ПРИ ПОМОЩИ $q\hbox{-МНОГОЧЛЕНОВ}$,
ПОЭТОМУ МЫ ХОТИМ ЛУЧШЕ ИЗУЧИТЬ~$q$. в ЭТОМ ОТНОШЕНИИ ПОЛЕЗНО УПР.~1.2.9-15,
ТАК КАК ОНО ДАЕТ ВЫРАЖЕНИЕ В ЗАМКНУТОМ
%%352
ВИДЕ, КОТОРОЕ МОЖЕТ БЫТЬ ЗАПИСАНО КАК
$$
q_m(z)={((\sqrt{4-z^2}+iz)/2)^{2m+1}+((\sqrt{4-z^2}-iz)/2)^{2m+1}
\over \sqrt{4-z^2}}
\eqno(10) $$
вСЕ УПРОЩАЕТСЯ, ЕСЛИ ТЕПЕРЬ ПОЛОЖИТЬ~$z=2 \sin\theta$:
$$
\eqalignno{
q_m(2\sin\theta)=&
{(\cos\theta+i\sin\theta)^{2m+1}+(\cos\theta-i\sin\theta)^{2m+1}\over 2\cos\theta}=\cr
&={\cos(2m+1)\theta\over \cos\theta}. & (11)\cr
}
$$
(эТО СОВПАДЕНИЕ ЗАСТАВЛЯЕТ ДУМАТЬ, ЧТО МНОГОЧЛЕНЫ~$q_m(z)$ ХОРОШО
ИЗВЕСТНЫ В МАТЕМАТИКЕ; И ДЕЙСТВИТЕЛЬНО, ВЗГЛЯНУВ В СООТВЕТСТВУЮЩИЕ
ТАБЛИЦЫ, ВИДИМ, ЧТО~$q_m(z)$, ПО СУЩЕСТВУ, МНОГОЧЛЕН чЕБЫШИВА ВТОРОГО РОДА,
 А ИМЕННО~$(-1)^m U_{2m}(z/2)$ В ОБЫЧНЫХ ОБОЗНАЧЕНИЯХ.)

тЕПЕРЬ МОЖНО ОПРЕДЕЛИТЬ КОРНИ ЗНАМЕНАТЕЛЯ В~(9):
$q_4(2\sin\theta)=2\sin\theta$ СВОДИТСЯ К
$$
\cos 9\theta = 2 \sin \theta \cos \theta = \sin 2\theta.
$$
рЕШЕНИЯ ЭТОГО СООТНОШЕНИЯ ПОЛУЧАЕМ, ЕСЛИ
ТОЛЬКО~$\pm9\theta=2\theta+\left(2n-{1\over2}\right)\pi$; ВСЕ
ТАКИЕ~$\theta$ ДАЮТ КОРНИ ЗНАМЕНАТЕЛЯ В~(9) ПРИ УСЛОВИИ,
ЧТО~$\cos\theta\ne 0$. (еСЛИ~$\cos\theta=0$, ТО~$q_m(\pm2)=\pm(2m+1)$,
НИКОГДА НЕ РАВНО~$\pm2$.) сЛЕДОВАТЕЛЬНО, ПОЛУЧАЕМ 8~РАЗЛИЧНЫХ КОРНЕЙ:
$$
\displaylines{
q_4(z)-z=0 \qquad \hbox{ ПРИ }  z=2\sin{-5\over 14}\pi,\quad
2\sin{-1 \over 14}\pi,\quad 2\sin{3 \over 14}\pi, \cr
2\sin{-7 \over 22}\pi,\quad 2\sin{-3 \over 22}\pi,\quad
2\sin{1 \over 22}\pi, \quad 2\sin{5 \over 22}\pi,\quad 2\sin{9 \over 22}\pi.\cr
}
$$
тАК КАК~$q_4(z)$---МНОГОЧЛЕН СТЕПЕНИ~8, МЫ УЧЛИ ВСЕ КОРНИ. пЕРВЫЕ ТРИ ИЗ
ЭТИХ ЗНАЧЕНИЙ ДАЮТ~$q_3(z)=0$, ТАК ЧТО~$q_3(z)$ И~$q_4(z)-z$  ИМЕЮТ ОБЩИМ
ДЕЛИТЕЛЕМ МНОГОЧЛЕН ТРЕТЬЕЙ СТЕПЕНИ. оСТАЛЬНЫЕ ПЯТЬ КОРНЕЙ УПРАВЛЯЮТ
АСИМПТОТИЧЕСКИМ ПОВЕДЕНИЕМ КОЭФФИЦИЕНТОВ~$A(z)$, ЕСЛИ РАЗЛОЖИТЬ~(9) В
ЭЛЕМЕНТАРНЫЕ ДРОБИ.

пЕРЕЙДЯ К РАССМОТРЕНИЮ ОБЩЕГО СЛУЧАЯ $T$~ЛЕНТ,
ПОЛОЖИМ~$\theta_k=(4k+1)\pi/(4T-2)$. пРОИЗВОДЯЩАЯ ФУНКЦИЯ~$A(z)$ ДЛЯ
$T\hbox{-ЛЕНТОЧНЫХ}$ КАСКАДНЫХ ЧИСЕЛ ПРИНИМАЕТ ВИД
$$
{4\over 2T-1}\sum_{-T/2<k<\floor{T/2}}{\cos^2\theta_k\over 1-z/(2\sin\theta_k)}
\eqno(12)
$$
(СМ.~УПР.~8); СЛЕДОВАТЕЛЬНО,
$$
a_n={4\over 2T-1}\sum_{-T/2<k<\floor{T/2}}\cos^2\theta_k \left({1\over 2\sin\theta_k}\right)^n.
\eqno(13)
$$
%% 353
сООТНОШЕНИЯ~(8) ПРИВОДЯТ ТЕПЕРЬ К АНАЛОГИЧНЫМ ФОРМУЛАМ:
$$
\eqalign{
b_n&={4\over 2T-1}\sum_{-T/2<k<\floor{T/2}}\cos\theta_k\cos3\theta_k\left({1\over 2\sin\theta_k}\right)^n;\cr
c_n&={4\over 2T-1}\sum_{-T/2<k<\floor{T/2}}\cos\theta_k\cos5\theta_k\left({1\over 2\sin\theta_k}\right)^n;\cr
d_n&={4\over 2T-1}\sum_{-T/2<k<\floor{T/2}}\cos\theta_k\cos7\theta_k\left({1\over 2\sin\theta_k}\right)^n\cr
}
\eqno(14)
$$
И~Т.~Д. в УПР.~9 ПОКАЗАНО, ЧТО ЭТИ УРАВНЕНИЯ СПРАВЕДЛИВЫ ДЛЯ ВСЕХ~$n\ge0$,
А НЕ ТОЛЬКО ДЛЯ БОЛЬШИХ~$n$. в КАЖДОЙ СУММЕ ЧЛЕН С~$k=0$ ЗНАЧИТЕЛЬНО
ПРЕВОСХОДИТ ВСЕ ОСТАЛЬНЫЕ, ОСОБЕННО ЕСЛИ~$n$ ДОСТАТОЧНО ВЕЛИКО;
СЛЕДОВАТЕЛЬНО, "ОТНОШЕНИЕ РОСТА" ЕСТЬ
$$
{1\over 2\sin\theta_0}={2\over\pi}T-{1\over\pi}+{\pi\over 48T}+O(T^{-2}).
\eqno(15)
$$

кАСКАДНАЯ СОРТИРОВКА ВПЕРВЫЕ БЫЛА ИССЛЕДОВАНА у.~к.~кАРТЕРОМ
[Proc.\ IFIP Congress (1962), 62--66], КОТОРЫЙ ПОЛУЧИЛ ЧИСЛЕННЫЕ РЕЗУЛЬТАТЫ
ДЛЯ НЕБОЛЬШИХ ЗНАЧЕНИЙ~$T$, И дЭВИДОМ фЕРГЮСОНОМ
[{\sl CACM,\/} {\bf 7} (1964), 297], КОТОРЫЙ ОТКРЫЛ ПЕРВЫЕ ДВА ЧЛЕНА В
АСИМПТОТИЧЕСКОМ ПОВЕДЕНИИ~(15)  ОТНОШЕНИЯ РОСТА.
лЕТОМ 1964~Г.\ р.~у.~фЛОЙД ПОЛУЧИЛ ЯВНЫЙ ВИД~$1/(2\sin\theta_0)$
ДЛЯ ОТНОШЕНИЯ РОСТА, ТАК ЧТО ТОЧНЫЕ ФОРМУЛЫ
МОГЛИ БЫТЬ ИСПОЛЬЗОВАНЫ ДЛЯ ВСЕХ~$T$. гЛУБОКИЙ АНАЛИЗ КАСКАДНЫХ ЧИСЕЛ БЫЛ
НЕЗАВИСИМО ВЫПОЛНЕН дЖ.~н.~рЭЙНИ
[{\sl Canadian J.~Math.,\/} {\bf 18} (1966), 332--349],
КОТОРЫЙ НАТКНУЛСЯ НА НИХ СОВЕРШЕННО ДРУГИМ ПУТЕМ,
НЕ ИМЕЯ ДЕЛА С СОРТИРОВКОЙ. рЭЙНИ ПОДМЕТИЛ АНАЛОГИЮ С ДИАГОНАЛЯМИ
(РИС.~73) И ВЫВЕЛ МНОГО ДРУГИХ ИНТЕРЕСНЫХ СВОЙСТВ ЭТИХ ЧИСЕЛ. фЛОЙД
И~рЭЙНИ В СВОИХ ДОКАЗАТЕЛЬСТВАХ ОПЕРИРОВАЛИ С МАТРИЦАМИ (СМ.~УПР.~6).

\section мОДИФИКАЦИЯ КАСКАДНОЙ СОРТИРОВКИ. еСЛИ ДОБАВЛЕНА ЕЩЕ ОДНА ЛЕНТА,
ТО ПОЧТИ ВСЕ ВРЕМЯ ПЕРЕМОТКИ В ТЕЧЕНИЕ КАСКАДНОЙ СОРТИРОВКИ МОЖНО
СОВМЕСТИТЬ. нАПРИМЕР, МЫ МОЖЕМ СЛИВАТЬ~T1--T5 НА~T7, ЗАТЕМ~T1--T4 НА~T6,
ЗАТЕМ~T1--T3 НА~T5 (КОТОРАЯ К ЭТОМУ МОМЕНТУ УЖЕ ПЕРЕМОТАНА), ЗАТЕМ~T1--T2
НА~T4 И НАЧАТЬ СЛЕДУЮЩИЙ ПРОХОД, КОГДА НА~T4 БУДЕТ ПЕРЕМОТАНО
СРАВНИТЕЛЬНО НЕМНОГО ДАННЫХ. эФФЕКТИВНОСТЬ ЭТОГО ПРОЦЕССА МОЖНО
ПРЕДСКАЗАТЬ НА ОСНОВАНИИ ИЗЛОЖЕННОГО ВЫШЕ АНАЛИЗА КАСКАДНОГО
МЕТОДА (ДАЛЬНЕЙШИЕ ПОДРОБНОСТИ СМ.~В~П.~5.4.6).

сХЕМА "КОМПРОМИССНОГО СЛИЯНИЯ", КОТОРАЯ ВКЛЮЧАЕТ МНОГОФАЗНУЮ И КАСКАДНУЮ
СХЕМЫ КАК ЧАСТНЫЕ СЛУЧАИ, БЫЛА ПРЕДЛОЖЕНА д.~э.~кНУТОМ В [{\sl CACM,\/}
{\bf 6} (1963), 585--587]. кАЖДАЯ ФАЗА СОСТОИТ ИЗ~$(T-1)\hbox{-ПУТЕВОГО}$,
$(T-2)\hbox{-ПУТЕВОГО}$,~\dots, $P\hbox{-ПУТЕВОГО}$ СЛИЯНИЙ, ГДЕ $P$---ЛЮБОЕ
ФИКСИРОВАННОЕ ЧИСЛО МЕЖДУ~1 И~$T-1$. еСЛИ~$P=T-1$, ТО ЭТО---МНОГОФАЗНЫЙ
МЕТОД; ЕСЛИ~$P=1$, ЭТО---ЧИСТЫЙ
%%354
КАСКАДНЫЙ МЕТОД; ЕСЛИ~$P=2$, ЭТО---КАСКАДНЫЙ МЕТОД БЕЗ ФАЗ
КОПИРОВАНИЯ. аНАЛИЗ ТАКОЙ СХЕМЫ БЫЛ ПРОДЕЛАН ч.~рАДКЕ
[{\sl IBM Systems J.,\/} {\bf 5} (1966), 226--247] И~у.~х.~бУРЖЕМ
[Proc. IFIP Congress, {\bf 1} (1971), 454---459]. бУРЖ НАШЕЛ
ПРОИЗВОДЯЩУЮ ФУНКЦИЮ~$\sum T_n(x) z^n$ ДЛЯ
КАЖДОГО~$(P, T)\hbox{-КОМПРОМИССНОГО}$ СЛИЯНИЯ,
ОБОБЩАЮЩУЮ СООТНОШЕНИЕ~(5.4.2-16); ОН
ПОКАЗАЛ, ЧТО НАИЛУЧШЕЕ ЗНАЧЕНИЕ~$P$ (С ТОЧКИ ЗРЕНИЯ НАИМЕНЬШЕГО ЧИСЛА
ОБРАБАТЫВАЕМЫХ НАЧАЛЬНЫХ ОТРЕЗКОВ), КАК ФУНКЦИИ ОТ~$S$
ПРИ~$S\to\infty$ (ЕСЛИ НЕПОСРЕДСТВЕННО ИСПОЛЬЗОВАТЬ СХЕМУ РАСПРЕДЕЛЕНИЯ
И ПРЕНЕБРЕЧЬ ВРЕМЕНЕМ ПЕРЕМОТКИ), ЕСТЬ СООТВЕТСТВЕННО
$(2, 3, 3, 4, 4, 4, 3, 3, 4)$ ПРИ~$T=(3, 4, 5, 6, 7, 8, 9, 10, 11)$.
эТИ ЗНАЧЕНИЯ~$P$ С
РОСТОМ~$T$ СИЛЬНЕЕ ОТКЛОНЯЮТСЯ В СТОРОНУ КАСКАДНОГО, А НЕ МНОГОФАЗНОГО
МЕТОДА, И ОКАЗЫВАЕТСЯ, ЧТО КОМПРОМИССНОЕ СЛИЯНИЕ НИКОГДА НЕ СТАНЕТ
СУЩЕСТВЕННО ЛУЧШЕ КАСКАДНОГО. с ДРУГОЙ СТОРОНЫ, ПРИ ОПТИМАЛЬНОМ ВЫБОРЕ
УРОВНЕЙ И РАСПРЕДЕЛЕНИИ ФИКТИВНЫХ ОТРЕЗКОВ, КАК ОПИСАНО В П.~5.4.2, ЧИСТЫЙ
МНОГОФАЗНЫЙ МЕТОД КАЖЕТСЯ НАИЛУЧШИМ СРЕДИ ВСЕХ КОМПРОМИССНЫХ СЛИЯНИЙ.
к СОЖАЛЕНИЮ, ОПТИМАЛЬНОЕ РАСПРЕДЕЛЕНИЕ СРАВНИТЕЛЬНО ТРУДНО РЕАЛИЗОВАТЬ.

т.~л.~йОНСЕН [{\sl BIT,\/} {\bf 6} (1966), 129--143] ИССЛЕДОВАЛ
СОЧЕТАНИЯ СБАЛАНСИРОВАННОГО И МНОГОФАЗНОГО СЛИЯНИЙ; МОДИФИКАЦИЯ
СБАЛАНСИРОВАННОГО СЛИЯНИЯ С СОВМЕЩЕНИЕМ ПЕРЕМОТОК БЫЛА ПРЕДЛОЖЕНА
м.~гОТЦЕМ [Digital Computer User's Handbook, ed.~by.~M.~Klerer
and~G.~A.~Korn (New York: McGraw-Hill, 1967), 1.311--1.312]; МОЖНО
ПРЕДСТАВИТЬ СЕБЕ И МНОГИЕ ДРУГИЕ ГИБРИДНЫЕ СХЕМЫ.

\excercises
\ex[10] иСПОЛЬЗУЯ ТАБЛ.~1, СРАВНИТЕ КАСКАДНОЕ СЛИЯНИЕ С ОПИСАННОЙ
В П.~5.4.2 ВЕРСИЕЙ МНОГОФАЗНОГО СЛИЯНИЯ С "РАСЩЕПЛЕНИЕМ ЛЕНТ". кАКОЙ
МЕТОД ЛУЧШЕ? (вРЕМЕНЕМ ПЕРЕМОТКИ ПРЕНЕБРЕЧЬ.)

\rex[22] сРАВНИТЕ КАСКАДНУЮ СОРТИРОВКУ С ТРЕМЯ ЛЕНТАМИ,
ИСПОЛЬЗУЮЩУЮ АЛГОРИТМ~C, И МНОГОФАЗНУЮ СОРТИРОВКУ С ТРЕМЯ ЛЕНТАМИ,
ИСПОЛЬЗУЮЩУЮ АЛГОРИТМ~5.4.2D кАКИЕ СХОДСТВА И РАЗЛИЧИЯ ВЫ ЗaМeТИТe?

\ex[20] сОСТАВЬТЕ ТАБЛИЦУ, ПОКАЗЫВАЮЩУЮ, ЧТО ПРОИСХОДИТ ПРИ СОРТИРОВКЕ НА
ШЕСТИ ЛЕНТАХ 100~НАЧАЛЬНЫХ ОТРЕЗКОВ ПРИ ПОМОЩИ АЛГОРИТМА~C.

\ex[м20] (дЖ.~н.~рЭЙНИ.) "кАСКАДНОЕ РАСПРЕДЕЛЕНИЕ $n\hbox{-ГО}$ УРОВНЯ"
ЕСТЬ МУЛЬТИМНОЖЕСТВО, ОПРЕДЕЛЕННОЕ СЛЕДУЮЩИМ ОБРАЗОМ (В СЛУЧАЕ ШЕСТИ ЛЕНТ):
$\set{1, 0, 0, 0, 0}$ ЕСТЬ КАСКАДНОЕ РАСПРЕДЕЛЕНИЕ НУЛЕВОГО УРОВНЯ;
ЕСЛИ~$\set{a, b, c, d, e}$---КАСКАДНОЕ РАСПРЕДЕЛЕНИЕ $n\hbox{-ГО}$~УРОВНЯ,
ТО~$\set{a+b+c+d+e, a+b+c+d, a+b+c, a+b, a}$ БУДЕТ КАСКАДНЫМ
РАСПРЕДЕЛЕНИЕМ $(n+1)\hbox{-ГО}$ УРОВНЯ (тАК КАК МУЛЬТИМНОЖЕСТВО НЕ
УПОРЯДОЧЕНО, ТО ИЗ ЕДИНСТВЕННОГО РАСПРЕДЕЛЕНИЯ $n\hbox{-ГО}$~УРОВНЯ МОЖНО
ОБРАЗОВАТЬ ДО~5 РАЗЛИЧНЫХ РАСПРЕДЕЛЕНИЙ $(n+1)\hbox{-ГО}$~УРОВНЯ.)
(a)~дОКАЖИТЕ, ЧТО \emph{ЛЮБОЕ}
МУЛЬТИМНОЖЕСТВО~$\set{a, b, c, d, e}$ ИЗ ВЗАИМНО ПРОСТЫХ ЧИСЕЛ ЯВЛЯЕТСЯ
КАСКАДНЫМ РАСПРЕДЕЛЕНИЕМ $n\hbox{-ГО}$~УРОВНЯ ПРИ НЕКОТОРОМ~$n$.
(b)~дОКАЖИТЕ, ЧТО РАСПРЕДЕЛЕНИЕ, ИСПОЛЬЗУЕМОЕ В КАСКАДНОЙ СОРТИРОВКЕ,
\emph{ОПТИМАЛЬНО} В ТОМ СМЫСЛЕ, ЧТО ЕСЛИ~$\set{a, b, c, d, e}$---ЛЮБОЕ
РАСПРЕДЕЛЕНИЕ $n\hbox{-ГО}$~УРОВНЯ, ПРИЧЕМ~$a\ge b \ge c \ge d \ge e$, ТО
БУДЕМ ИМЕТЬ~$a\le a_n$, $b\le b_n$, $c\le c_n$, $d\le d_n$, $e\le e_n$,
ГДЕ~$\set{a_n, b_n, c_n, d_n, e_n}$---РАСПРЕДЕЛЕНИЕ, ОПРЕДЕЛЕННОЕ В~(1).

\rex[20] дОКАЖИТЕ, ЧТО КАСКАДНЫЕ ЧИСЛА, ОПРЕДЕЛЕННЫЕ В~(1), УДОВЛЕТВОРЯЮТ
%%355
ЗАКОНУ
$$
a_k a_{n-k}+b_k b_{n-k}+c_k c_{n-k}+d_k d_{n-k}+e_k e_{n-k}=a_n
\rem{ПРИ~$ 0\le k \le n$.}
$$
[\emph{уКАЗАНИЕ:} ДЛЯ ЛУЧШЕГО ПОНИМАНИЯ ЭТОГО СООТНОШЕНИЯ РАССМОТРИТЕ,
СКОЛЬКО ОТРЕЗКОВ РАЗЛИЧНОЙ ДЛИНЫ ВЫВОДИТСЯ В ТЕЧЕНИЕ $k\hbox{-ГО}$~ПРОХОДА
ПОЛНОЙ КАСКАДНОЙ СОРТИРОВКИ.]

\ex[м20] нАЙДИТЕ $5\times5$-МАТРИЦУ~$Q$, ТАКУЮ, ЧТО ПЕРВАЯ СТРОКА~$Q^n$
СОДЕРЖИТ КАСКАДНЫЕ ЧИСЛА ДЛЯ ШЕСТИ ЛЕНТ~$a_n b_n c_n d_n e_n$ ПРИ
ВСЕХ~$n\ge 0$.

\ex[м20] пРИ УСЛОВИИ ЧТО КАСКАДНОЕ СЛИЯНИЕ ПРИМЕНЯЕТСЯ К
ТОЧНОМУ РАСПРЕДЕЛЕНИЮ $a_n$~НАЧАЛЬНЫХ ОТРЕЗКОВ, НАЙДИТЕ ФОРМУЛУ ДЛЯ
ВЕЛИЧИНЫ СЭКОНОМЛЕННОЙ РАБОТЫ, КОГДА ИСКЛЮЧАЕТСЯ ОДНОПУТЕВОЕ СЛИЯНИЕ.

\ex[вм23] вЫВЕДИТЕ ФОРМУЛУ~(12).

\ex[вм26] вЫВЕДИТЕ ФОРМУЛУ~(14).

\rex[м28] вМЕСТО СИСТЕМЫ~(4) ДЛЯ ИЗУЧЕНИЯ КАСКАДНЫХ ЧИСЕЛ ВОСПОЛЬЗУЙТЕСЬ
В КАЧЕСТВЕ ИСХОДНЫХ ТОЖДЕСТВАМИ
$$
\eqalignter{
e_n&=a_{n-1}  &= \perm{1}{1}a_{n-1};\cr
d_n&=2a_{n-1}-e_{n-2} &=\perm{2}{1}a_{n-1}-\perm{3}{3}a_{n-3};\cr
c_n&=3a_{n-1}-d_{n-2}-2e_{n-2} &=\perm{3}{1}a_{n-1}-\perm{4}{3}a_{n-3}+\perm{5}{5}a_{n-5}\cr
}
$$
И~Т.~Д. пОЛАГАЯ
$$
r_m(z)=\perm{m}{1}z-\perm{m+1}{3}z^3+\perm{m+2}{5}z^5-\ldots,
$$
ВЫРАЗИТЕ~$A(z)$, $B(z)$ И~Т.~Д.\ ЧЕРЕЗ ЭТИ $r\hbox{-МНОГОЧЛЕНЫ}$.

\ex[м38] пУСТЬ
$$
f_m(z)=\sum_{0\le k \le m} \perm{\floor{(m+k)/2}}{k}(-1)^{\ceil{k/2}}z^k.
$$
дОКАЖИТЕ, ЧТО ПРОИЗВОДЯЩАЯ ФУНКЦИЯ~$A(z)$ ДЛЯ $T\hbox{-ЛЕНТОЧНЫХ}$
КАСКАДНЫХ ЧИСЕЛ РАВНА~$f_{T-3}(z)/f_{T-1}(z)$, ПРИЧЕМ ЧИСЛИТЕЛЬ И
ЗНАМЕНАТЕЛЬ ЭТОГО ВЫРАЖЕНИЯ НЕ ИМЕЮТ ОБЩИХ ДЕЛИТЕЛЕЙ.

\ex[м40] дОКАЖИТЕ, ЧТО СХЕМА РАСПРЕДЕЛЕНИЯ фЕРГЮСОНА ОПТИМАЛЬНА В ТОМ
СМЫСЛЕ, ЧТО ПРИ ЛЮБОМ ДРУГОМ МЕТОДЕ РАЗМЕЩЕНИЯ ФИКТИВНЫХ ОТРЕЗКОВ,
УДОВЛЕТВОРЯЮЩЕМ~(2), ВО ВРЕМЯ ПЕРВОГО ПРОХОДА БУДЕТ ОБРАБАТЫВАТЬСЯ
НЕ МЕНЬШЕ НАЧАЛЬНЫХ ОТРЕЗКОВ, \emph{ПРИ УСЛОВИИ} ЧТО ВО ВРЕМЯ ЭТОГО
ПРОХОДА ИСПОЛЬЗУЕТСЯ СТРАТЕГИЯ ШАГОВ~C7--C9.

\ex[40] в ТЕКСТЕ ПРЕДЛАГАЕТСЯ БОЛЬШУЮ ЧАСТЬ ВРЕМЕНИ ПЕРЕМОТКИ СОВМЕЩАТЬ
ПУТЕМ ДОБАВЛЕНИЯ ДОПОЛНИТЕЛЬНОЙ ЛЕНТЫ. рАЗРАБОТАЙТЕ ЭТУ ИДЕЮ. (нАПРИМЕР,
СХЕМА, ИЗЛОЖЕННАЯ В ТЕКСТЕ, ВКЛЮЧАЕТ ОЖИДАНИЕ ПЕРЕМОТКИ ЛЕНТЫ~T4;
НЕ БУДЕТ ЛИ ЛУЧШЕ ИСКЛЮЧИТЬ~T4 ИЗ ПЕРВОЙ ФАЗЫ СЛИЯНИЯ СЛЕДУЮЩЕГО ПРОХОДА?)

\subsubchap{чТЕНИЕ ЛЕНТЫ В ОБРАТНОМ НАПРАВЛЕНИИ} %% 5.4.4
мНОГИЕ ЛЕНТОПРОТЯЖНЫЕ УСТРОЙСТВА ПОЗВОЛЯЮТ ЧИТАТЬ ЛЕНТУ В НАПРАВЛЕНИИ,
ПРОТИВОПОЛОЖНОМ ТОМУ, В КОТОРОМ ШЛА ЗАПИСЬ НА НЕЕ. сХЕМЫ СЛИЯНИЯ, С
КОТОРЫМИ МЫ ВСТРЕЧАЛИСЬ ДО СИХ ПОР, ВСЕГДА ЗАПИСЫВАЮТ ИНФОРМАЦИЮ НА ЛЕНТУ
В ПРЯМОМ НАПРАВЛЕНИИ,
%%  356
ЗАТЕМ ПЕРЕМАТЫВАЮТ ЛЕНТУ, ЧИТАЮТ ЕЕ В ПРЯМОМ НАПРАВЛЕНИИ И ВНОВЬ
ПЕРЕМАТЫВАЮТ. (фАЙЛЫ НА ЛЕНТЕ, СЛЕДОВАТЕЛЬНО, ВЕДУТ СЕБЯ КАК ОЧЕРЕДИ
"ПЕРВЫМ ВКЛЮЧАЕТСЯ---ПЕРВЫМ ИСКЛЮЧАЕТСЯ".) оБРАТНОЕ ЧТЕНИЕ ПОЗВОЛЯЕТ
ОБОЙТИСЬ БЕЗ ОБЕИХ ОПЕРАЦИЙ ПЕРЕМОТКИ:
МЫ ЗАПИСЫВАЕМ НА ЛЕНТУ В ПРЯМОМ НАПРАВЛЕНИИ И ЧИТАЕМ ЕЕ В ОБРАТНОМ. (в
ЭТОМ СЛУЧАЕ ФАЙЛЫ ВЕДУТ СЕБЯ КАК СТЕКИ, ПОСКОЛЬКУ ЗДЕСЬ ДЕЙСТВУЕТ ПРАВИЛО
"ПОСЛЕДНИМ ВКЛЮЧАЕТСЯ---ПЕРВЫМ ИСКЛЮЧАЕТСЯ".)

сХЕМЫ СБАЛАНСИРОВАННОГО, МНОГОФАЗНОГО И КАСКАДНОГО СЛИЯНИЙ МОЖНО
ПРИСПОСОБИТЬ ДЛЯ ОБРАТНОГО ЧТЕНИЯ. оСНОВНОЕ ОТЛИЧИЕ СОСТОИТ В ТОМ, ЧТО
\emph{СЛИЯНИЕ ИЗМЕНЯЕТ ПОРЯДОК ОТРЕЗКОВ,} ЕСЛИ МЫ ЧИТАЕМ В ПРЯМОМ
НАПРАВЛЕНИИ И ЗАПИСЫВАЕМ В ОБРАТНОМ. еСЛИ ДВА ОТРЕЗКА НАХОДЯТСЯ НА ЛЕНТЕ В
ВОЗРАСТАЮЩЕМ ПОРЯДКЕ, ТО ИХ МОЖНО СЛИТЬ, ЧИТАЯ В ОБРАТНОМ НАПРАВЛЕНИИ, НО
ПРИ ЭТОМ ПОРЯДОК СТАНЕТ УБЫВАЮЩИМ. пОЛУЧЕННЫЕ ТАКИМ ПУТЕМ
УБЫВАЮЩИЕ ОТРЕЗКИ СТАНУТ ВОЗРАСТАЮЩИМИ НА СЛЕДУЮЩЕМ ПРОХОДЕ; ТАКИМ ОБРАЗОМ,
 АЛГОРИТМ СЛИЯНИЯ ДОЛЖЕН УМЕТЬ РАБОТАТЬ С ОТРЕЗКАМИ ОБОИХ НАПРАВЛЕНИЙ.
пРОГРАММИСТУ, ВПЕРВЫЕ СТОЛКНУВШЕМУСЯ С ОБРАТНЫМ ЧТЕНИЕМ, МОЖЕТ ПОКАЗАТЬСЯ,
ЧТО ОН СТОИТ НА ГОЛОВЕ!

в КАЧЕСТВЕ ПРИМЕРА ОБРАТНОГО ЧТЕНИЯ РАССМОТРИМ ПРОЦЕСС СЛИЯНИЯ 8~НАЧАЛЬНЫХ
ОТРЕЗКОВ С ИСПОЛЬЗОВАНИЕМ \emph{СБАЛАНСИРОВАННОГО} СЛИЯНИЯ НА 4~ЛЕНТАХ.
мОЖНО СЛЕДУЮЩИМ ОБРАЗОМ ЗАПИСАТЬ НАШИ ДЕЙСТВИЯ:
\ctable{
# \hfil & \bskip\hfil$#$\hfil\bskip & \bskip\hfil$#$\hfil\bskip &
\bskip\hfil$#$\hfil\bskip & \bskip\hfil$#$\hfil\bskip & # \hfil \cr
 & T1 & T2 & T3 & T4 \cr
пРОХОД~1. &  A_1 A_1 A_1 A_1 &  A_1 A_1 A_1 A_1  & -       & -       & нАЧАЛЬНОЕ РАСПРЕДЕЛЕНИЕ \cr
пРОХОД~2. &  -               & -                 & D_2 D_2 & D_2 D_2 & сЛИЯНИЕ НА~$T3$ И~$T4$\cr
пРОХОД~3. &  A_4             & A_4               & -       & -       & сЛИЯНИЕ НА~$T1$ И~$T2$\cr
пРОХОД~4. &  -               & -                 & D_8     & -       & оКОНЧАТЕЛЬНОЕ СЛИЯНИЕ НА~$T3$\cr
}
зДЕСЬ $A_r$~ОБОЗНАЧАЕТ ОТРЕЗОК, ИМЕЮЩИЙ ОТНОСИТЕЛЬНУЮ ДЛИНУ~$r$ И
РАСПОЛОЖЕННЫЙ В ВОЗРАСТАЮЩЕМ ПОРЯДКЕ, ЕСЛИ ЛЕНТА ЧИТАЕТСЯ В ПРЯМОМ
НАПРАВЛЕНИИ, КАК В ПРЕДЫДУЩИХ НАШИХ ПРИМЕРАХ; $D_r$---АНАЛОГИЧНОЕ
ОБОЗНАЧЕНИЕ ДЛЯ УБЫВАЮЩЕГО ОТРЕЗКА ДЛИНЫ~$r$. вО ВРЕМЯ 2-ГО~ПРОХОДА
ВОЗРАСТАЮЩИЕ ОТРЕЗКИ СТАНОВЯТСЯ УБЫВАЮЩИМИ: ОНИ ОКАЗЫВАЮТСЯ УБЫВАЮЩИМИ
ПРИ ВВОДЕ, ТАК КАК МЫ ЧИТАЕМ В ОБРАТНОМ НАПРАВЛЕНИИ. оНИ ВНОВЬ ИЗМЕНЯЮТ
ОРИЕНТАЦИЮ НА 3-М~ПРОХОДЕ.

зАМЕТИМ, ЧТО ОПИСАННЫЙ ПРОЦЕСС ЗАВЕРШАЕТСЯ РЕЗУЛЬТАТОМ НА ЛЕНТЕ~$T3$ В
\emph{УБЫВАЮЩЕМ} ПОРЯДКЕ. еСЛИ ЭТО ПЛОХО (ЧТО ЗАВИСИТ ОТ ТОГО, ДОЛЖЕН ЛИ
РЕЗУЛЬТАТ ЧИТАТЬСЯ В ОБРАТНОМ НАПРАВЛЕНИИ, ИЛИ ЖЕ ЛЕНТА, СОДЕРЖАЩАЯ ЕГО,
ДОЛЖНА БЫТЬ СНЯТА И ОТЛОЖЕНА ДЛЯ БУДУЩЕГО ИСПОЛЬЗОВАНИЯ), МЫ МОЖЕМ
СКОПИРОВАТЬ ЕГО НА ДРУГУЮ ЛЕНТУ, ОБРАТИВ НАПРАВЛЕНИЕ. бОЛЕЕ БЫСТРЫМ
СПОСОБОМ БЫЛА БЫ
%%357
ПЕРЕМОТКА~$T1$ И~$T2$ ПОСЛЕ 3-ГО~ПРОХОДА, ПРИ ЭТОМ ВО ВРЕМЯ 4-ГО~ПРОХОДА
ПОЛУЧАЕТСЯ~$A_8$. еЩЕ БЫСТРЕЕ БЫЛО БЫ НАЧАТЬ С ВОСЬМИ \emph{УБЫВАЮЩИХ}
ОТРЕЗКОВ НА 1-М~ПРОХОДЕ, ТАК КАК ЭТО ПОМЕНЯЕТ МЕСТАМИ ВСЕ~$A$ И~$D$.
оДНАКО ДЛЯ СБАЛАНСИРОВАННОГО СЛИЯНИЯ 16~НАЧАЛЬНЫХ ОТРЕЗКОВ ПОТРЕБОВАЛОСЬ
БЫ, ЧТОБЫ НАЧАЛЬНЫЕ ОТРЕЗКИ БЫЛИ ВОЗРАСТАЮЩИМИ, А ТАК КАК МЫ ОБЫЧНО НЕ
ЗНАЕМ ЗАРАНЕЕ, СКОЛЬКО НАЧАЛЬНЫХ ОТРЕЗКОВ БУДЕТ ОБРАЗОВАНО, ТО НЕОБХОДИМО
 ВЫБРАТЬ ОДНО ПОСТОЯННОЕ НАПРАВЛЕНИЕ. сЛЕДОВАТЕЛЬНО, ИДЕЯ ПЕРЕМОТКИ ПОСЛЕ
3-ГО~ПРОХОДА, ВЕРОЯТНО, НАИЛУЧШАЯ.

\emph{кАСКАДНОЕ} СЛИЯНИЕ ПРЕОБРАЗУЕТСЯ ТАКИМ ЖЕ СПОСОБОМ. рАССМОТРИМ,
НАПРИМЕР, СОРТИРОВКУ 14~НАЧАЛЬНЫХ ОТРЕЗКОВ НА ЧЕТЫРЕХ ЛЕНТАХ:
\ctable{
# \hfil & \bskip\hfil$#$\hfil\bskip & \bskip\hfil$#$\hfil\bskip &
\bskip\hfil$#$\hfil\bskip & \bskip\hfil$#$\hfil\bskip & # \hfil \cr
 & T1 & T2 & T3 & T4 \cr
пРОХОД~1. & A_1 A_1 A_1 A_1 A_1 A_1 & A_1 A_1 A_1 A_1 A_1 &  A_1 A_1 A_1 & - \cr
пРОХОД~2. & -                       & D_1                 &  D_2 D_2     & D_3 D_3 D_3 \cr
пРОХОД~3. & A_6                     & A_5                 &  A_3         & - \cr
пРОХОД~4. & -                       & -                   &  -           & D_{14} \cr
\noalign{\noindent
сНОВА ВМЕСТО~$D_{14}$ МОЖНО ПОЛУЧИТЬ~$A_{14}$, ЕСЛИ ПЕРЕМОТАТЬ~$T1$, $T2$,
$T3$ НЕПОСРЕДСТВЕННО ПЕРЕД ПОСЛЕДНИМ ПРОХОДОМ. зАМЕТИМ, ЧТО ЭТО "ЧИСТОЕ"
КАСКАДНОЕ СЛИЯНИЕ В ТОМ СМЫСЛЕ, ЧТО ВСЕ ОДНОПУТЕВЫЕ СЛИЯНИЯ ВЫПОЛНЕНЫ
ЯВНЫМ ОБРАЗОМ. еСЛИ БЫ МЫ ЗАПРЕТИЛИ ОПЕРАЦИИ КОПИРОВАНИЯ, КАК В
АЛГОРИТМЕ~5.4.3D, ТО ПОСЛЕ 2-ГО~ПРОХОДА СТОЛКНУЛИСЬ БЫ С СИТУАЦИЕЙ
}
& A_1  & - & D_2D_2 & D_3D_3D_3 \cr
}
И БЫЛО БЫ НЕВОЗМОЖНО ПРОДОЛЖАТЬ РАБОТУ, ИСПОЛЬЗУЯ ТРЕХПУТЕВОЕ СЛИЯНИЕ, ТАК
КАК МЫ НЕ МОЖЕМ СЛИВАТЬ ОТРЕЗКИ ПРОТИВОПОЛОЖНЫХ НАПРАВЛЕНИЙ! мОЖНО БЫЛО
БЫ ИЗБЕЖАТЬ ОПЕРАЦИИ КОПИРОВАНИЯ~$T1$ НА~$T2$, ЕСЛИ ПЕРЕМОТАТЬ~$T1$ И
НАЧАТЬ ЧИТАТЬ ЕЕ В ПРЯМОМ НАПРАВЛЕНИИ ВО ВРЕМЯ СЛЕДУЮЩЕЙ ФАЗЫ СЛИЯНИЯ (В
ТО ВРЕМЯ КАК~$T3$ И~$T4$ ЧИТАЮТСЯ В ОБРАТНОМ НАПРАВЛЕНИИ). нО ТОГДА
ПРИШЛОСЬ БЫ ВНОВЬ ПЕРЕМОТАТЬ~$T1$ ПОСЛЕ СЛИЯНИЯ, ТАК ЧТО ЭТОТ
ПРИЕМ ЗАМЕНЯЕТ ОДНО КОПИРОВАНИЕ НА ДВЕ ПЕРЕМОТКИ.

тАКИМ ОБРАЗОМ, МЕТОД РАСПРЕДЕЛЕНИЯ АЛГОРИТМА~5.4.3C РАБОТАЕТ ДЛЯ
ОБРАТНОГО ЧТЕНИЯ НЕ СТОЛЬ ЭФФЕКТИВНО, КАК ДЛЯ ПРЯМОГО ЧТЕНИЯ; ВРЕМЕННЫЕ
ЗАТРАТЫ РЕЗКО ВОЗРАСТАЮТ КАЖДЫЙ РАЗ, КОГДА ЧИСЛО НАЧАЛЬНЫХ ОТРЕЗКОВ
ПРОХОДИТ ЧЕРЕЗ "ТОЧНОЕ" КАСКАДНОЕ РАСПРЕДЕЛЕНИЕ. чТОБЫ ПОЛУЧИТЬ БОЛЕЕ
ГЛАДКИЙ ПРОХОД МЕЖДУ ТОЧНЫМИ КАСКАДНЫМИ РАСПРЕДЕЛЕНИЯМИ, МОЖНО
ИСПОЛЬЗОВАТЬ ИНОЙ МЕТОД РАСПРЕДЕЛЕНИЯ (СМ.~УПР.~17).

\section оБРАТНОЕ ЧТЕНИЕ В МНОГОФАЗНОМ СЛИЯНИИ. нА ПЕРВЫЙ ВЗГЛЯД (И
ДАЖЕ НА ВТОРОЙ И ТРЕТИЙ!) СХЕМА МНОГОФАЗНОГО СЛИЯНИЯ КАЖЕТСЯ СОВЕРШЕННО
НЕПОДХОДЯЩЕЙ ДЛЯ ОБРАТНОГО ЧТЕНИЯ. пРЕДПОЛОЖИМ, НАПРИМЕР, ЧТО ИМЕЮТСЯ
13~НАЧАЛЬНЫХ ОТРЕЗКОВ И ТРИ ЛЕНТЫ.
%%358
\ctable{
# \hfil &  \bskip\hfil$#$\hfil\bskip & \bskip\hfil$#$\hfil\bskip &
\bskip\hfil$#$\hfil\bskip \cr
       & T1                  & T2                              & T3 \cr
фАЗА~1.& A_1 A_1 A_1 A_1 A_1 & A_1 A_1 A_1 A_1 A_1 A_1 A_1 A_1 & - \cr
фАЗА~2.& -                   & A_1 A_1 A_1                     & D_2 D_2 D_2 D_2 D_2\cr
}
зДЕСЬ МЫ ВСТАЕМ В ТУПИК; МОЖНО БЫЛО БЫ ПЕРЕМОТАТЬ~$T2$ ИЛИ~$T3$ И ЗАТЕМ
ЧИТАТЬ ИХ В ПРЯМОМ НАПРАВЛЕНИИ, В ТО ВРЕМЯ КАК ОСТАЛЬНЫЕ ЛЕНТЫ---В
ОБРАТНОМ. нО ЭТО СИЛЬНО ЗАПУТАЛО БЫ ДЕЛО, И ВЫГОДА ОТ ОБРАТНОГО ЧТЕНИЯ
БЫЛА БЫ ОТНОСИТЕЛЬНО МАЛА.

оСТРОУМНАЯ ИДЕЯ, СПАСАЮЩАЯ ПОЛОЖЕНИЕ, СОСТОИТ В ТОМ,
ЧТОБЫ \emph{ЧЕРЕДОВАТЬ НАПРАВЛЕНИЯ ОТРЕЗКОВ НА КАЖДОЙ ЛЕНТЕ.} тОГДА
СЛИЯНИЕ МОЖЕТ ПРОИСХОДИТЬ ВПОЛНЕ СОГЛАСОВАННО:
\ctable{
# \hfil &  \bskip\hfil$#$\hfil\bskip & \bskip\hfil$#$\hfil\bskip & \bskip\hfil$#$\hfil\bskip \cr
фАЗА~1. & A_1 D_1 A_1 D_1 A_1 & D_1 A_1 D_1 A_1 D_1 A_1 D_1 A_1 & - \cr
фАЗА~2. & -                   & D_1 A_1 D_1                     & D_2 A_2 D_2 A_2 D_2 \cr
фАЗА~3. & A_3 D_3 A_3         & -                               & D_2 A_2 \cr
фАЗА~4. & A_3                 & D_5 A_5                         & - \cr
фАЗА~5. & -                   & D_5                             & D_8 \cr
фАЗА~6. & A_{13}              & -                               & - \cr
}
эТОТ ПРИНЦИП БЫЛ КРАТКО УПОМЯНУТ р.~л.~гИЛСТЭДОМ В ЕГО РАННЕЙ СТАТЬЕ О
МНОГОФАЗНОМ СЛИЯНИИ, БОЛЕЕ ПОЛНО ОН ОПИСАЛ ЕГО
В~{\sl CACM,\/} {\bf 6} (1963), 220--223.

эТОТ $ADA\hbox{-МЕТОД}$ ЧЕТКО РАБОТАЕТ ДЛЯ МНОГОФАЗНОГО СЛИЯНИЯ С
\emph{ЛЮБЫМ} ЧИСЛОМ ЛЕНТ; МОЖНО ПОКАЗАТЬ, ЧТО~$A$ И~$D$
СОГЛАСУЮТСЯ СООТВЕТСТВУЮЩИМ ОБРАЗОМ НА КАЖДОЙ ФАЗЕ, ПРИ ТОМ ТОЛЬКО
УСЛОВИИ, ЧТО ПРОХОД НАЧАЛЬНОГО РАСПРЕДЕЛЕНИЯ ПОРОЖДАЕТ ЧЕРЕДУЮЩИЕСЯ
ОТРЕЗКИ~$A$ И~$D$ НА КАЖДОЙ ЛЕНТЕ И ЧТО КАЖДАЯ ЛЕНТА КОНЧАЕТСЯ
ОТРЕЗКОМ~$A$ (ИЛИ КАЖДАЯ ЛЕНТА КОНЧАЕТСЯ ОТРЕЗКОМ~$D$). тАК КАК ПОСЛЕДНИЙ
ОТРЕЗОК, ЗАПИСЫВАЕМЫЙ В ФАЙЛ ВЫВОДА ВО ВРЕМЯ ОДНОЙ ФАЗЫ, ИМЕЕТ НАПРАВЛЕНИЕ,
 ПРОТИВОПОЛОЖНОЕ НАПРАВЛЕНИЮ ПОСЛЕДНЕГО ИСПОЛЬЗОВАННОГО ОТРЕЗКА ИЗ ФАЙЛА
ВВОДА, ТО СЛЕДУЮЩАЯ ФАЗА ВСЕГДА НАХОДИТ СВОИ ОТРЕЗКИ С НАДЛЕЖАЩЕЙ
ОРИЕНТАЦИЕЙ. дАЛЕЕ, МЫ ВИДЕЛИ В УПР.~5.4.2-13, ЧТО БОЛЬШИНСТВО ТОЧНЫХ
ФИБОНАЧЧИЕВЫХ РАСПРЕДЕЛЕНИЙ ТРЕБУЕТ \emph{НЕЧЕТНОГО} ЧИСЛА ОТРЕЗКОВ НА
ОДНОЙ ЛЕНТЕ (ОКОНЧАТЕЛЬНОЙ ВЫВОДНОЙ ЛЕНТЕ) И ЧЕТНОГО ЧИСЛА ОТРЕЗКОВ НА
ВСЕХ ОСТАЛЬНЫХ ЛЕНТАХ. еСЛИ~$T1$ ПРЕДНАЗНАЧЕНА ДЛЯ КОНЕЧНОГО ВЫВОДА, ТО
МЫ МОЖЕМ, СЛЕДОВАТЕЛЬНО, ГАРАНТИРОВАТЬ, ЧТО ВСЕ ЛЕНТЫ БУДУТ КОНЧАТЬСЯ
ОТРЕЗКОМ~$A$, ЕСЛИ ЛЕНТУ~$T1$ НАЧНЕМ С~$A$, А ВСЕ ОСТАЛЬНЫЕ ЛЕНТЫ---С~$D$.
мОЖНО ИСПОЛЬЗОВАТЬ МЕТОД РАСПРЕДЕЛЕНИЯ, АНАЛОГИЧНЫЙ АЛГОРИТМУ~5.4.2D,
ИЗМЕНИВ ЕГО ТАКИМ ОБРАЗОМ, ЧТОБЫ РАСПРЕДЕЛЕНИЕ НА КАЖДОМ УРОВНЕ ИМЕЛО В
КАЧЕСТВЕ ВЫВОДНОЙ ЛЕНТЫ~$T1$.
(мЫ ПРОПУСКАЕМ УРОВНИ~$1$, $T+1$, $2T+1$,~\dots, ТАК КАК ЭТО ТЕ УРОВНИ,
НА КОТОРЫХ КОНЕЧНОЙ ВЫВОДНОЙ ЛЕНТОЙ ЯВЛЯЕТСЯ ПЕРВОНАЧАЛЬНО ПУСТАЯ ЛЕНТА.)
нАПРИМЕР, В СЛУЧАЕ ШЕСТИ ЛЕНТ МОЖНО ИСПОЛЬЗОВАТЬ
%% 358
ВМЕСТО~(5.4.2-1) СЛЕДУЮЩЕЕ РАСПРЕДЕЛЕНИЕ ОТРЕЗКОВ:
$$
\vcenter{\halign{
\hfil$#$\hfil&\bskip\hfil$#$\bskip&\bskip\hfil$#$\bskip&\bskip\hfil$#$\bskip&\bskip\hfil$#$\bskip&\bskip\hfil$#$\bskip&\bskip\hfil$#$\bskip&\bskip\hfil$#$\bskip&\hfil$#$\hfil\cr
& & & & & & & \hbox{оКОНЧАТЕЛЬНЫЙ} \cr
\hbox{уРОВЕНЬ} &  T1 & T2 & T3 & T4 & T5 & \hbox{сУММА} & \hbox{ВЫВОД НА ЛЕНТЕ}\cr
0 &  1 &   0 &   0 &   0 &  0 &   1 & T1 \cr
2 &  1 &   2 &   2 &   2 &  2 &   9 & T1 \cr
3 &  3 &   4 &   4 &   4 &  2 &  17 & T1 \cr
4 &  7 &   8 &   8 &   6 &  4 &  33 & T1 \cr
5 & 15 &  16 &  14 &  12 &  8 &  65 & T1 \cr
6 & 31 &  30 &  28 &  24 & 16 & 129 & T1 \cr
8 & 61 & 120 & 116 & 108 & 92 & 497 & T1 \cr
}}
\eqno(1)
$$
тАКИМ ОБРАЗОМ, НА~$T1$ ВСЕГДА ПОМЕЩАЕТСЯ НЕЧЕТНОЕ ЧИСЛО ОТРЕЗКОВ, ТОГДА
КАК НА ЛЕНТЫ С~$T2$ ПО~$T5$---ЧЕТНЫЕ ЧИСЛА (В УБЫВАЮЩЕМ ПОРЯДКЕ ДЛЯ
УПРОЩЕНИЯ ПРИСВОЕНИЯ ФИКТИВНЫХ ОТРЕЗКОВ). тАКОЕ РАСПРЕДЕЛЕНИЕ ИМЕЕТ ТО
ПРЕИМУЩЕСТВО, ЧТО КОНЕЧНАЯ ВЫВОДНАЯ ЛЕНТА ИЗВЕСТНА ЗАРАНЕЕ НЕЗАВИСИМО ОТ
ЧИСЛА НАЧАЛЬНЫХ ОТРЕЗКОВ, КОТОРЫЕ ПРИДЕТСЯ ОБРАБАТЫВАТЬ. оКАЗЫВАЕТСЯ
(СМ.~УПР.~3), ЧТО ЕСЛИ ИСПОЛЬЗУЕТСЯ ЭТА СХЕМА, ТО РЕЗУЛЬТАТ ВСЕГДА БУДЕТ
НА~$T1$ В ВОЗРАСТАЮЩЕМ ПОРЯДКЕ.

дРУГОЙ СПОСОБ ОСУЩЕСТВИТЬ РАСПРЕДЕЛЕНИЕ ДЛЯ МНОГОФАЗНОЙ СХЕМЫ С ОБРАТНЫМ
ЧТЕНИЕМ БЫЛ ПРЕДЛОЖЕН д.~т.~гУДВИНОМ И~дЖ.~л.~вЕННОМ
[{\sl CACM,\/} {\bf 7} (1964), 315]. мЫ МОЖЕМ РАСПРЕДЕЛЯТЬ ОТРЕЗКИ, ПОЧТИ КАК
В АЛГОРИТМЕ~5.4.2D, НАЧИНАЯ С $D\hbox{-ОТРЕЗКА}$ НА КАЖДОЙ ЛЕНТЕ. кОГДА ВВОД
ИСЧЕРПАН, МЫ ПРЕДСТАВЛЯЕМ СЕБЕ ФИКТИВНЫЙ $A\hbox{-ОТРЕЗОК}$
РАСПОЛОЖЕННЫМ В НАЧАЛЕ ЕДИНСТВЕННОЙ "НЕЧЕТНОЙ" ЛЕНТЫ, ЕСЛИ ТОЛЬКО НЕ
ДОСТИГНУТО РАСПРЕДЕЛЕНИЕ СО ВСЕМИ НЕЧЕТНЫМИ ЧИСЛАМИ. оСТАЛЬНЫЕ ФИКТИВНЫЕ
ОТРЕЗКИ МЫ ПРЕДСТАВЛЯЕМ СЕБЕ РАСПОЛОЖЕННЫМИ В КОНЦЕ ЛЕНТ ИЛИ
СГРУППИРОВАННЫМИ В ПАРЫ В СЕРЕДИНЕ. вОПРОС ОБ ОПТИМАЛЬНОМ РАЗМЕЩЕНИИ
ФИКТИВНЫХ ОТРЕЗКОВ АНАЛИЗИРУЕТСЯ НИЖЕ В УПР.~5.

\section оПТИМАЛЬНЫЕ СХЕМЫ СЛИЯНИЯ. дО СИХ ПОР МЫ ОБСУЖДАЛИ РАЗЛИЧНЫЕ
СХЕМЫ СЛИЯНИЯ С ЛЕНТАМИ, НЕ ПЫТАЯСЬ НАЙТИ МЕТОД, "НАИЛУЧШИЙ ИЗ ВОЗМОЖНЫХ".
оПРЕДЕЛЕНИЕ ОПТИМАЛЬНОЙ СХЕМЫ КАЖЕТСЯ ОСОБЕННО СЛОЖНЫМ В СЛУЧАЕ ПРЯМОГО
ЧТЕНИЯ, ГДЕ ВЗАИМОДЕЙСТВИЕ ВРЕМЕНИ ПЕРЕМОТКИ И ВРЕМЕНИ СЛИЯНИЯ С ТРУДОМ
ПОДДАЕТСЯ АНАЛИЗУ. с ДРУГОЙ СТОРОНЫ, ЕСЛИ СЛИЯНИЕ
ОСУЩЕСТВЛЯЕТСЯ ПОСРЕДСТВОМ ОБРАТНОГО ЧТЕНИЯ И ПРЯМОЙ ЗАПИСИ, ТО, ПО
СУЩЕСТВУ, ВСЕ ПЕРЕМОТКИ УСТРАНЯЮТСЯ И ОКАЗЫВАЕТСЯ ВОЗМОЖНЫМ
ДАТЬ ДОВОЛЬНО ХОРОШУЮ ХАРАКТЕРИСТИКУ ОПТИМАЛЬНЫМ СХЕМАМ СЛИЯНИЯ.
рИЧАРД~м.~кАРП ПРЕДЛОЖИЛ НЕСКОЛЬКО ИНТЕРЕСНЫХ ПОДХОДОВ К ЭТОЙ ЗАДАЧЕ, И
МЫ ЗАВЕРШАЕМ ЭТОТ ПУНКТ ОБСУЖДЕНИЕМ РАЗВИТОЙ ИМ ТЕОРИИ.

вО-ПЕРВЫХ, НАМ НЕОБХОДИМ БОЛЕЕ УДОБНЫЙ СПОСОБ ОПИСАНИЯ СХЕМ СЛИЯНИЯ ВМЕСТО
ДОВОЛЬНО ТАИНСТВЕННЫХ ТАБЛИЦ "СОДЕРЖИМОГО ЛЕНТ", КОТОРЫЕ ИСПОЛЬЗОВАЛИСЬ
ВЫШЕ. кАРП ПРЕДЛОЖИЛ ДВА
%%360
ТАКИХ СПОСОБА---\emph{ВЕКТОРНОЕ ПРЕДСТАВЛЕНИЕ СХЕМЫ СЛИЯНИЯ} И
\emph{ПРЕДСТАВЛЕНИЕ В ВИДЕ ДЕРЕВА.} оБА ПРЕДСТАВЛЕНИЯ ПОЛЕЗНЫ НА ПРАКТИКЕ,
 И МЫ ОПИШЕМ ИХ ПО ОЧЕРЕДИ.

вЕКТОРНОЕ ПРЕДСТАВЛЕНИЕ СХЕМЫ СЛИЯНИЯ СОСТОИТ ИЗ ПОСЛЕДОВАТЕЛЬНОСТИ
"ВЕКТОРОВ СЛИЯНИЯ" $y^m\ldots{}y^1 y^0$, КАЖДЫЙ ИЗ КОТОРЫХ ИМЕЕТ
$T$~КОМПОНЕНТ; $y^{(i)}$ СЛЕДУЮЩИМ ОБРАЗОМ ИЗОБРАЖАЕТ $i\hbox{-Й}$ С КОНЦА
ШАГ СЛИЯНИЯ:
$$
y^{(i)}_j=\cases{
          +1, & ЕСЛИ ЛЕНТА С НОМЕРОМ~$j$ ЯВЛЯЕТСЯ ВВОДНОЙ ДЛЯ ДАННОГО СЛИЯНИЯ; \cr
\phantom{-}0, & ЕСЛИ ЛЕНТА С НОМЕРОМ~$j$ НЕ ИСПОЛЬЗУЕТСЯ В ДАННОМ СЛИЯНИИ;\cr
          -1, & ЕСЛИ НА ЛЕНТУ С НОМЕРОМ~$j$ ВЫВОДИТСЯ РЕЗУЛЬТАТ ДАННОГО СЛИЯНИЯ.\cr
}
\eqno(2)
$$
тАКИМ ОБРАЗОМ, РОВНО ОДНА КОМПОНЕНТА~$y^{(i)}$ РАВНА~$-1$,
ОСТАЛЬНЫЕ КОМПОНЕНТЫ РАВНЫ~0 И~1. иТОГОВЫЙ ВЕКТОР~$y^{(0)}$ ОСОБЫЙ; ЭТО
ЕДИНИЧНЫЙ ВЕКТОР, ИМЕЮЩИЙ~1 В ПОЗИЦИИ~$j$, ЕСЛИ
ОКОНЧАТЕЛЬНЫЙ ОТСОРТИРОВАННЫЙ РЕЗУЛЬТАТ ОКАЗЫВАЕТСЯ НА УСТРОЙСТВЕ~$j$, И~0
В ОСТАЛЬНЫХ МЕСТАХ. иЗ ЭТОГО ОПРЕДЕЛЕНИЯ СЛЕДУЕТ, ЧТО ВЕКТОРНАЯ СУММА
$$
v^{(i)}=y^{(i)}+y^{(i-1)}+\cdots+y^{(0)}
\eqno(3)
$$
ПРЕДСТАВЛЯЕТ СОБОЙ РАСПРЕДЕЛЕНИЕ ОТРЕЗКОВ НА ЛЕНТАХ НЕПОСРЕДСТВЕННО
ПЕРЕД $i\hbox{-М}$ С КОНЦА ШАГОМ СЛИЯНИЯ, ПРИЧЕМ НА ЛЕНТЕ~$j$ НАХОДИТСЯ
$v^{(i)}_j$~ОТРЕЗКОВ. в ЧАСТНОСТИ, ПО~$v^{(m)}$ МОЖНО СУДИТЬ, СКОЛЬКО
ОТРЕЗКОВ ПОМЕЩАЕТ НА КАЖДУЮ ЛЕНТУ НАЧАЛЬНЫЙ ПРОХОД РАСПРЕДЕЛЕНИЯ.

тРИ СХЕМЫ СЛИЯНИЯ, ОПИСАННЫЕ РАНЕЕ В ЭТОМ ПУНКТЕ В ТАБЛИЧНОЙ ФОРМЕ,
ИМЕЮТ СЛЕДУЮЩИЕ ВЕКТОРНЫЕ ПРЕДСТАВЛЕНИЯ:
{\def\!{\phantom{+}}\def\y#1{y^{(#1)}}\ctable{
$#$&$\hbox{}# \quad$ & $#$&$\hbox{}#\quad $ & $#$&$\hbox{}#$ \cr
\omit \hfil сБАЛАНСИРОВАННАЯ \hfil \span & \omit \hfil  кАСКАДНАЯ  \hfil \span & \omit \hfil мНОГОФАЗНАЯ \hfil \span \cr
\omit \hfil ($T=4$, $S=8$)  \hfil \span & \omit \hfil  ($T=4$, $S=14$) \hfil \span & \omit \hfil  ($T=3$, $S=13$) \hfil\span\cr
v^{(7)} &=(\!4,\!4,\!0,\!0) & v^{(10)} &= (\!6,\!5,\!3,\!0) & v^{(12)} &=(\!5,\!8,\!0)\cr
\y{7} &= (+1, +1, -1,\!0) & \y{10}&= (+1, +1, +1, -1) & \y{12} &= ( +1, +1, -1)\cr
\y{6} &= (+1, +1,\!0, -1) & \y{9} &= (+1, +1, +1, -1) & \y{11} &= (+1, +1, -1)\cr
\y{5} &= (+1, +1, -1,\!0) & \y{8} &= (+1, +1, +1, -1) & \y{10} &=(+1, +1, -1)\cr
\y{4} &= (+1, +1,\!0, -1) & \y{7} &= (+1, +1, -1,\!0) & \y{9} &= (+1, +1, -1)\cr
\y{3} &= (-1,\!0, +1, +1) & \y{6} &= (+1, +1, -1,\!0) & \y{8} &= (+1, +1, -1)\cr
\y{2} &=(\!0, -1, +1, +1) & \y{5} &= (+1, -1,\!0,\!0) & \y{7} &= (-1, +1, +1)\cr
\y{1} &= (+1, +1, -1,\!0) & \y{4} &= (-1, +1, +1, +1) & \y{6} &= (-1, +1, +1)\cr
\y{0} &=(\!0,\!0,\!1,\!0) & \y{3} &=(\!0, -1, +1, +1) & \y{5} &= (-1, +1, +1)\cr
            \omit & \omit & \y{2} &=(\!0,\!0, -1, +1) & \y{4} &= (+1, -1, +1)\cr
            \omit & \omit & \y{1} &= (+1, +1, +1, -1) & \y{3} &= (+1, -1, +1)\cr
            \omit & \omit & \y{0} &=(\!0,\!0,\!0,\!1) & \y{2} &= (+1, +1, -1)\cr
                        \omit & \omit & \omit & \omit & \y{1} &= (-1, +1, +1)\cr
                        \omit & \omit & \omit & \omit & \y{0} &= (\!1,\!0,\!0)\cr
}}
%%361
мОЖЕТ ПОКАЗАТЬСЯ НЕУДОБНЫМ НУМЕРОВАТЬ ЭТИ ВЕКТОРЫ С КОНЦА ТАК, ЧТОБЫ
$y^{(m)}$~ПОЯВЛЯЛСЯ ПЕРВЫМ, А $y^{(0)}$---ПОСЛЕДНИМ, НО ЭТА ОСОБАЯ ТОЧКА
ЗРЕНИЯ ОКАЗЫВАЕТСЯ ПРЕДПОЧТИТЕЛЬНОЙ ПРИ РАЗРАБОТКЕ ТЕОРИИ. дЛЯ ПОИСКА
ОПТИМАЛЬНОГО МЕТОДА НЕПЛОХО НАЧАТЬ С ОТСОРТИРОВАННОГО ВЫВОДА И ПРЕДСТАВИТЬ
СЕБЕ, КАК ЕГО МОЖНО "РАЗЛИТЬ" НА РАЗЛИЧНЫЕ ЛЕНТЫ, ЗАТЕМ "РАЗЛИТЬ" ИХ
И~Т.~Д., РАССМАТРИВАЯ ПОСЛЕДОВАТЕЛЬНЫЕ РАСПРЕДЕЛЕНИЯ~$v^{(0)}$,
$v^{(1)}$, $v^{(2)}$,~\dots В ПОРЯДКЕ, ОБРАТНОМ ТОМУ, В КОТОРОМ ОНИ В
ДЕЙСТВИТЕЛЬНОСТИ ПОЯВЛЯЮТСЯ В ПРОЦЕССЕ СОРТИРОВКИ. фАКТИЧЕСКИ ИМЕННО ЭТОТ
ПОДХОД БЫЛ УЖЕ ИСПОЛЬЗОВАН НАМИ ПРИ АНАЛИЗЕ МНОГОФАЗНОГО И КАСКАДНОГО СЛИЯНИЯ.

кАЖДАЯ СХЕМА СЛИЯНИЯ, ОЧЕВИДНО, ИМЕЕТ ВЕКТОРНОЕ ПРЕДСТАВЛЕНИЕ. и ОБРАТНО,
КАК ЛЕГКО ВИДЕТЬ, ПОСЛЕДОВАТЕЛЬНОСТЬ
ВЕКТОРОВ~$y^{(m)}\ldots{}y^{(1)}y^{(0)}$ СООТВЕТСТВУЕТ РЕАЛЬНОЙ СХЕМЕ
СЛИЯНИЯ ТОГДА И ТОЛЬКО ТОГДА, КОГДА ВЫПОЛНЯЮТСЯ СЛЕДУЮЩИЕ ТРИ УСЛОВИЯ:

{\medskip\narrower
\item{i)}~ВЕКТОР~$y^{(0)}$ ЯВЛЯЕТСЯ ЕДИНИЧНЫМ;

\item{ii)}~РОВНО ОДНА КОМПОНЕНТА ВЕКТОРА~$y^{(i)}$ РАВНА~$-1$, ВСЕ
ОСТАЛЬНЫЕ КОМПОНЕНТЫ РАВНЫ~$0$ ИЛИ~$+1$, $m\ge i \ge 1$;

\item{iii)}~ВСЕ КОМПОНЕНТЫ ВЕКТОРА~$y^{(i)}+\ldots+y^{(1)}+y^{(0)}$
НЕОТРИЦАТЕЛЬНЫ, $m\ge i \ge 1$.
\medskip
}

пРЕДСТАВЛЕНИЕ СХЕМЫ СЛИЯНИЯ В ВИДЕ ДЕРЕВА ДАЕТ ДРУГОЕ ИЗОБРАЖЕНИЕ ТОЙ ЖЕ
ИНФОРМАЦИИ. мЫ СТРОИМ ДЕРЕВО С ОДНИМ ВНЕШНИМ "ЛИСТОВЫМ" УЗЛОМ ДЛЯ КАЖДОГО
НАЧАЛЬНОГО ОТРЕЗКА И С ОДНИМ ВНУТРЕННИМ УЗЛОМ ДЛЯ КАЖДОГО ОТРЕЗКА,
ПОЛУЧЕННОГО В РЕЗУЛЬТАТЕ СЛИЯНИЯ, ТАКИМ ОБРАЗОМ, ЧТО ПОТОМКАМИ
ЛЮБОГО ВНУТРЕННЕГО УЗЛА ЯВЛЯЮТСЯ ОТРЕЗКИ, ИЗ КОТОРЫХ ОН БЫЛ СФОРМИРОВАН.
кАЖДЫЙ ВНУТРЕННИЙ УЗЕЛ ПОМЕЧАЕТСЯ НОМЕРОМ ШАГА, НА КОТОРОМ БЫЛ ОБРАЗОВАН
СООТВЕТСТВУЮЩИЙ ОТРЕЗОК, ПРИ ЭТОМ ШАГИ НУМЕРУЮТСЯ В ОБРАТНОМ ПОРЯДКЕ, КАК
В ВЕКТОРНОМ ПРЕДСТАВЛЕНИИ;
КРОМЕ ТОГО, РЕБРА НЕПОСРЕДСТВЕННО НАД КАЖДЫМ УЗЛОМ ПОМЕЧАЮТСЯ ИМЕНЕМ
ЛЕНТЫ, НА КОТОРОЙ ОКАЗЫВАЕТСЯ ЭТОТ ОТРЕЗОК. нАПРИМЕР, ТРИ ПРИВЕДЕННЫЕ ВЫШЕ
СХЕМЫ ИМЕЮТ ПРЕДСТАВЛЕНИЯ В ВИДЕ ДЕРЕВА, ИЗОБРАЖЕННЫЕ НА РИС.~76, ЕСЛИ МЫ
НАЗОВЕМ ЛЕНТЫ~$A$, $B$, $C$, $D$, А НЕ~$T1$, $T2$, $T3$, $T4$.

эТО УДОБНОЕ И НАГЛЯДНОЕ ПРЕДСТАВЛЕНИЕ МНОГИХ СУЩЕСТВЕННЫХ СВОЙСТВ СХЕМЫ
СЛИЯНИЯ; НАПРИМЕР, ЕСЛИ ОТРЕЗОК НА УРОВНЕ~$0$ ДЕРЕВА (КОРЕНЬ) ДОЛЖЕН БЫТЬ
ВОЗРАСТАЮЩИМ, ТО ОТРЕЗКИ НА УРОВНЕ~$1$ ДОЛЖНЫ БЫТЬ УБЫВАЮЩИМИ, ОТРЕЗКИ НА
УРОВНЕ~$2$---ВОЗРАСТАЮЩИМИ И~Т.~Д.; НЕКОТОРЫЙ НАЧАЛЬНЫЙ ОТРЕЗОК
ЯВЛЯЕТСЯ ВОЗРАСТАЮЩИМ ТОГДА И ТОЛЬКО ТОГДА, КОГДА СООТВЕТСТВУЮЩИЙ ВНЕШНИЙ
УЗЕЛ НАХОДИТСЯ НА УРОВНЕ С ЧЕТНЫМ НОМЕРОМ. дАЛЕЕ, СУММАРНОЕ КОЛИЧЕСТВО
НАЧАЛЬНЫХ ОТРЕЗКОВ, ОБРАБАТЫВАЕМЫХ ПРИ СЛИЯНИИ (НЕ ВКЛЮЧАЯ НАЧАЛЬНОЕ
РАСПРЕДЕЛЕНИЕ), В ТОЧНОСТИ РАВНО \emph{ДЛИНЕ ВНЕШНЕГО ПУТИ} ДЕРЕВА, ТАК
КАК КАЖДЫЙ НАЧАЛЬНЫЙ ОТРЕЗОК НА УРОВНЕ~$k$ ОБРАБАТЫВАЕТСЯ РОВНО $k$~РАЗ.

%%362
\picture{рИС.~76. пРЕДСТАВЛЕНИЯ ТРЕХ СХЕМ СЛИЯНИЯ В ВИДЕ ДЕРЕВА.}

лЮБАЯ СХЕМА СЛИЯНИЯ ИМЕЕТ ПРЕДСТАВЛЕНИЕ В ВИДЕ ДЕРЕВА, НО НЕ КАЖДОЕ ДЕРЕВО
ОПРЕДЕЛЯЕТ СХЕМУ СЛИЯНИЯ. дЕРЕВО, ВНУТРЕННИЕ УЗЛЫ КОТОРОГО ПОМЕЧЕНЫ
ЧИСЛАМИ ОТ~$1$ ДО~$m$ И РЕБРА КОТОРОГО ПОМЕЧЕНЫ ИМЕНАМИ ЛЕНТ, ИЗОБРАЖАЕТ
ПРАВИЛЬНУЮ СХЕМУ СЛИЯНИЯ С ОБРАТНЫМ ЧТЕНИЕМ ТОГДА И ТОЛЬКО ТОГДА, КОГДА

a)~НИКАКИЕ ДВА РЕБРА, СМЕЖНЫЕ С ОДНИМ ВНУТРЕННИМ УЗЛОМ, НЕ ИМЕЮТ
ОДИНАКОВОГО ИМЕНИ ЛЕНТЫ;

b)~ЕСЛИ~$i>j$ И ЕСЛИ $A$~ЕСТЬ ИМЯ ЛЕНТЫ, ТО ДЕРЕВО НЕ СОДЕРЖИТ КОНФИГУРАЦИИ
\picture{p.362}
%%363

c)~ЕСЛИ~$i<j<k<l$ И ЕСЛИ~$A$---ИМЯ ЛЕНТЫ, ТО ДЕРЕВО НЕ СОДЕРЖИТ ТАКИХ ПАР:
\picture{p.363.1}
уСЛОВИЕ~(a) ОЧЕВИДНО, ТАК КАК ВВОДНЫЕ И ВЫВОДНАЯ ЛЕНТЫ СЛИЯНИЯ ДОЛЖНЫ
БЫТЬ РАЗЛИЧНЫ; УСЛОВИЕ~(b) ТАКЖЕ ОЧЕВИДНО. уСЛОВИЕ "НЕПЕРЕСЕЧЕНИЯ"~(c)
ОТРАЖАЕТ ХАРАКТЕРНОЕ ДЛЯ ОПЕРАЦИЙ ОБРАТНОГО ЧТЕНИЯ ЛЕНТЫ ОГРАНИЧЕНИЕ
"ПОСЛЕДНИМ ВКЛЮЧАЕТСЯ --- ПЕРВЫМ ИСКЛЮЧАЕТСЯ". оТРЕЗОК, ОБРАЗОВАННЫЙ НА
ШАГЕ~$k$, ДОЛЖЕН БЫТЬ УДАЛЕН ПРЕЖДЕ ОТРЕЗКА, СФОРМИРОВАННОГО РАНЕЕ
НА ТОЙ ЖЕ ЛЕНТЕ; СЛЕДОВАТЕЛЬНО, КОНФИГУРАЦИИ~(4) НЕВОЗМОЖНЫ. нЕТРУДНО
ПРОВЕРИТЬ, ЧТО ЛЮБОЕ ПОМЕЧЕННОЕ ДЕРЕВО, УДОВЛЕТВОРЯЮЩЕЕ УСЛОВИЯМ~(a),
(b), (c), ДЕЙСТВИТЕЛЬНО СООТВЕТСТВУЕТ НЕКОТОРОЙ СХЕМЕ СЛИЯНИЯ С ОБРАТНЫМ
ЧТЕНИЕМ.

еСЛИ ИМЕЕТСЯ $T$~ЛЕНТОЧНЫХ УСТРОЙСТВ, ТО ИЗ УСЛОВИЯ~(a) СЛЕДУЕТ, ЧТО
СТЕПЕНЬ КАЖДОГО ВНУТРЕННЕГО УЗЛА РАВНА~$T-1$ ИЛИ МЕНЬШЕ. пРИПИСЫВАНИЕ
ПОДХОДЯЩИХ МЕТОК ВСЕМ ТАКИМ ДЕРЕВЬЯМ НЕ ВСЕГДА ВОЗМОЖНО; НАПРИМЕР,
ЕСЛИ~$T=3$, ТО НЕ СУЩЕСТВУЕТ СХЕМЫ СЛИЯНИЯ С ДЕРЕВОМ ВИДА
\picture{p.363.2}
тАКАЯ ФОРМА ДЕРЕВА ПРИВЕЛА БЫ К ОПТИМАЛЬНОЙ СХЕМЕ СЛИЯНИЯ, ЕСЛИ БЫ МЫ
СМОГЛИ СООТВЕТСТВУЮЩИМ ОБРАЗОМ ПРИПИСАТЬ НОМЕРА ШАГОВ И НОМЕРА ЛЕНТ,
ПОСКОЛЬКУ ЭТО ЕДИНСТВЕННОЕ ДЕРЕВО С МИНИМАЛЬНОЙ ДЛИНОЙ ВНЕШНЕГО ПУТИ
СРЕДИ ДЕРЕВЬЕВ, ИМЕЮЩИХ ЧЕТЫРЕ ВНЕШНИХ УЗЛА. нО В СИЛУ СИММЕТРИИ ЭТОЙ
ДИАГРАММЫ ИМЕЕТСЯ, ПО СУЩЕСТВУ, ТОЛЬКО ОДИН СПОСОБ ПОМЕТИТЬ ЕЕ, СОБЛЮДАЯ
УСЛОВИЯ~(a) И~(b):
\picture{p.363.3}
%%364
оДНАКО ПРИ ЭТОМ НАРУШАЕТСЯ УСЛОВИЕ~(c). дЕРЕВО, КОТОРОЕ МОЖЕТ БЫТЬ
ПОМЕЧЕНО В СООТВЕТСТВИИ С УПОМЯНУТЫМИ УСЛОВИЯМИ С ИСПОЛЬЗОВАНИЕМ~$T$ ИЛИ
МЕНЬШЕ ИМЕН ЛЕНТ, НАЗЫВАЕТСЯ $T\hbox{-lifo}$\note{1}%
{"Lifo"---АББРЕВИАТУРА ДЛЯ "last in---first out" (ПОСЛЕДНИМ ВКЛЮЧАЕТСЯ---
ПЕРВЫМ ИСКЛЮЧАЕТСЯ).---{\it пРИМ. ПЕРЕВ.\/}} ДЕРЕВОМ.

дРУГОЙ СПОСОБ ХАРАКТЕРИЗОВАТЬ ВСЕ ПОМЕЧЕННЫЕ ДЕРЕВЬЯ, КОТОРЫЕ МОГУТ
ВОЗНИКНУТЬ ИЗ СХЕМЫ СЛИЯНИЯ, СОСТОИТ В ТОМ, ЧТОБЫ РАССМОТРЕТЬ, КАК ВСЕ
ПОДОБНЫЕ ДЕРЕВЬЯ МОГУТ БЫТЬ "ВЫРАЩЕНЫ". нАЧНЕМ С НЕКОТОРОГО ИМЕНИ ЛЕНТЫ,
СКАЖЕМ~$A$, И С РОСТКА ДЕРЕВА
\picture{p.364.1}
шАГ~$i$ РОСТА ДЕРЕВА СОСТОИТ В ВЫБОРЕ РАЗЛИЧНЫХ ИМЕН ЛЕНТ~$B$, $B_1$,
$B_2$,~\dots, $B_k$ И ЗАМЕНЕ \emph{ПОЗЖЕ ВСЕГО ОБРАЗОВАННОГО} УЗЛА,
 СООТВЕТСТВУЮЩЕГО~$B$,
\picture{p.364.2}
эТО ПРАВИЛО "ПОСЛЕДНИМ ОБРАЗОВАН---ПЕРВЫМ РАСТЕТ" В ТОЧНОСТИ ОПИСЫВАЕТ
СПОСОБ ПОСТРОЕНИЯ ПРЕДСТАВЛЕНИЯ В ВИДЕ ДЕРЕВА НЕПОСРЕДСТВЕННО ИЗ
ВЕКТОРНОГО ПРЕДСТАВЛЕНИЯ.

оПРЕДЕЛЕНИЕ СТРОГО ОПТИМАЛЬНОЙ $T\hbox{-ЛЕНТОЧНОЙ}$ СХЕМЫ СЛИЯНИЯ,
Т.~Е.~ДЕРЕВА, ИМЕЮЩЕГО МИНИМАЛЬНУЮ ДЛИНУ ПУТИ СРЕДИ
ВСЕХ $T\hbox{-lifo}$~ДЕРЕВЬЕВ С ДАННЫМ ЧИСЛОМ ВНЕШНИХ УЗЛОВ, КАЖЕТСЯ
ВЕСЬМА  ТРУДНОЙ ЗАДАЧЕЙ. сЛЕДУЮЩАЯ НЕОЧЕВИДНАЯ СХЕМА, НАПРИМЕР,
ОКАЗЫВАЕТСЯ НАИЛУЧШИМ СПОСОБОМ СЛИТЬ СЕМЬ НАЧАЛЬНЫХ ОТРЕЗКОВ, ИМЕЯ
ЧЕТЫРЕ ЛЕНТЫ И ЧИТАЯ В ОБРАТНОМ НАПРАВЛЕНИИ:
%%365
оДНОПУТЕВОЕ СЛИЯНИЕ НЕОБХОДИМО ПО СУЩЕСТВУ ДЛЯ ДОСТИЖЕНИЯ ОПТИМУМА!
(сМ.~УПР.~8.) с ДРУГОЙ СТОРОНЫ, НЕ ТАК ТРУДНО ДАТЬ КОНСТРУКЦИИ,
\emph{АСИМПТОТИЧЕСКИ} ОПТИМАЛЬНЫЕ ДЛЯ ЛЮБОГО ФИКСИРОВАННОГО~$T$.

пУСТЬ~$K_T(n)$---МИНИМАЛЬНАЯ ДЛИНА ВНЕШНЕГО ПУТИ, ДОСТИЖИМАЯ В
$T\hbox{-lifo}$~ДЕРЕВЕ С $n$~ВНЕШНИМИ УЗЛАМИ. иСПОЛЬЗУЯ ТЕОРИЮ, РАЗВИТУЮ В
П.~2.3.4.5, НЕТРУДНО ДОКАЗАТЬ, ЧТО
$$
K_T(n)\ge nq - \floor{((T-1)^q-n)/(T-2)}, \quad
q=\ceil{\log_{T-1} n},
\eqno(9)
$$
ТАК КАК ЭТО МИНИМАЛЬНАЯ ДЛИНА ВНЕШНЕГО ПУТИ ЛЮБОГО ДЕРЕВА С $n$~ВНЕШНИМИ
УЗЛАМИ И СТЕПЕНЬЮ ЛЮБОГО УЗЛА~$<T$. к НАСТОЯЩЕМУ МОМЕНТУ ИЗВЕСТНЫ
ОТНОСИТЕЛЬНО НЕМНОГИЕ ТОЧНЫЕ ЗНАЧЕНИЯ~$K_T(n)$. зДЕСЬ ПРИВЕДЕНЫ НЕКОТОРЫЕ
ВЕРХНИЕ ОЦЕНКИ, КОТОРЫЕ, ВЕРОЯТНО, ТОЧНЫ:
$$
\vbox{\halign{
\hfil$#$ &&\bskip \hfil$#$ \cr
       n = 1 & 2 & 3 & 4 &  5&  6&  7&  8&  9& 10& 11& 12& 13& 14& 15\cr
K_3(n) \le 0 & 2 & 5 & 9 & 12& 16& 21& 25& 30& 34& 39& 45& 50& 56& 61\cr
K_4(n) \le 0 & 2 & 3 & 6 &  8& 11& 14& 17& 20& 24& 27& 31& 33& 37& 40\cr
}}
\eqno (10)
$$

кАРП ОБНАРУЖИЛ, ЧТО ЛЮБОЕ ДЕРЕВО С ВНУТРЕННИМИ УЗЛАМИ СТЕПЕНИ~$< T$
ЯВЛЯЕТСЯ \emph{ПОЧТИ} $T\hbox{-lifo}$~ДЕРЕВОМ В ТОМ СМЫСЛЕ, ЧТО ОНО МОЖЕТ
БЫТЬ СДЕЛАНО $T\hbox{-lifo}$ С ПОМОЩЬЮ ЗАМЕНЫ НЕКОТОРЫХ ВНЕШНИХ УЗЛОВ НА
ОДНОПУТЕВЫЕ СЛИЯНИЯ. фАКТИЧЕСКИ ПОСТРОЕНИЕ ПОДХОДЯЩЕЙ РАССТАНОВКИ МЕТОК
ВЫПОЛНЯЕТСЯ, ДОВОЛЬНО ПРОСТО. пУСТЬ~$A$---КОНКРЕТНОЕ ИМЯ ЛЕНТЫ. бУДЕМ
ДЕЙСТВОВАТЬ СЛЕДУЮЩИМ ОБРАЗОМ:
\medskip

{\sl шАГ~1.\/} пРИПИСАТЬ ИМЕНА ЛЕНТ РЕБРАМ ДИАГРАММЫ ДЕРЕВА ЛЮБЫМ СПОСОБОМ,
 СОВМЕСТИМЫМ С УСЛОВИЕМ~(a), УКАЗАННЫМ ВЫШЕ, ОДНАКО ТАК, ЧТОБЫ СПЕЦИАЛЬНОЕ
ИМЯ~$A$ ИСПОЛЬЗОВАЛОСЬ ТОЛЬКО В САМОМ ЛЕВОМ РЕБРЕ ВЕТВИ.

\smallskip
{\sl шАГ~2.\/} зАМЕНИТЬ КАЖДЫЙ ВНЕШНИЙ УЗЕЛ ВИДА
\picture{p.365}
ЕСЛИ ТОЛЬКО~$B\ne A$.

\smallskip
{\sl шАГ~3.\/} зАНУМЕРОВАТЬ ВНУТРЕННИЕ УЗЛЫ В ПРЯМОМ ПОРЯДКЕ\note{1}%
{сМ.~П.~2.3.1.---{\sl пРИМ. ПЕРЕВ.\/}}.
рЕЗУЛЬТАТОМ БУДЕТ РАССТАНОВКА МЕТОК, УДОВЛЕТВОРЯЮЩАЯ УСЛОВИЯМ~(a), (b), (c).
\medskip
%%366

нАПРИМЕР, ЕСЛИ МЫ НАЧНЕМ С ДЕРЕВА
\picture{p.366.1}
И ТРЕХ ЛЕНТ, ТО ЭТА ПРОЦЕДУРА МОГЛА БЫ ПРИПИСАТЬ МЕТКИ ТАКИМ ОБРАЗОМ:
\picture{p.366.2}
нЕТРУДНО ПРОВЕРИТЬ, ЧТО КОНСТРУКЦИЯ кАРПА УДОВЛЕТВОРЯЕТ ДИСЦИПЛИНЕ
"ПОСЛЕДНИМ ОБРАЗОВАН---ПЕРВЫМ РАСТЕТ" В СИЛУ СВОЙСТВ ПРЯМОГО ПОРЯДКА (СМ.~УПР.~12).

зАМЕТИМ, ЧТО РЕЗУЛЬТАТОМ ЭТОГО ПОСТРОЕНИЯ ЯВЛЯЕТСЯ СХЕМА СЛИЯНИЯ, В
КОТОРОЙ ВСЕ НАЧАЛЬНЫЕ ОТРЕЗКИ ПОЯВЛЯЮТСЯ НА ЛЕНТЕ~$A$. эТО ПРЕДПОЛАГАЕТ
СЛЕДУЮЩУЮ СХЕМУ РАСПРЕДЕЛЕНИЯ И СОРТИРОВКИ, КОТОРУЮ МОЖНО НАЗВАТЬ
СЛИЯНИЕМ В \emph{ПРЯМОМ ПОРЯДКЕ.}

%% !!! ОПРЕДЕЛИТЬ СТИЛЬ, СВЯЗАННЫЙ С АЛГОРИТМОМ
{\medskip\narrower
\item{\bf P1.}~рАСПРЕДЕЛЯТЬ НАЧАЛЬНЫЕ ОТРЕЗКИ НА ЛЕНТУ~$A$, ПОКА ВВОД НЕ
БУДЕТ ИСЧЕРПАН. пУСТЬ~$S$---ЧИСЛО ВСЕХ НАЧАЛЬНЫХ ОТРЕЗКОВ.

\item{\bf P2.}~вЫПОЛНЯТЬ ПРИВЕДЕННОЕ ВЫШЕ ПОСТРОЕНИЕ, ИСПОЛЬЗУЯ
$(T-1)\hbox{-АРНОЕ}$ ДЕРЕВО С $S$~ВНЕШНИМИ УЗЛАМИ С МИНИМАЛЬНОЙ ДЛИНОЙ
ПУТИ, ПОЛУЧАЯ $T\hbox{-lifo}$~ДЕРЕВО, ДЛИНА ВНЕШНЕГО ПУТИ КОТОРОГО
ПРЕВЫШАЕТ НИЖНЮЮ ГРАНИЦУ~(9) НЕ БОЛЕЕ, ЧЕМ НА~$S$.

\item{\bf P3.}~сЛИВАТЬ ОТРЕЗКИ В СООТВЕТСТВИИ С ЭТОЙ СХЕМОЙ.
\endmark
\medskip}

рЕЗУЛЬТАТ В УКАЗАННОЙ СХЕМЕ ПОЛУЧАЕТСЯ НА КАКОЙ УГОДНО ЛЕНТЕ. нО
\emph{ЭТА СХЕМА ИМЕЕТ ОДИН СЕРЬЕЗНЫЙ ИЗЎЯН.}
(вИДИТ ЛИ ЧИТАТЕЛЬ, ЧТО ИМЕННО ЗДЕСЬ БУДЕТ НЕПРАВИЛЬНО РАБОТАТЬ?) дЕЛО
%%367
В ТОМ, ЧТО СХЕМА ТРЕБУЕТ, ЧТОБЫ ПЕРВОНАЧАЛЬНО НЕКОТОРЫЕ ИЗ ОТРЕЗКОВ НА~$A$
БЫЛИ ВОЗРАСТАЮЩИМИ, А НЕКОТОРЫЕ---УБЫВАЮЩИМИ В ЗАВИСИМОСТИ ОТ ТОГО,
ПОЯВЛЯЕТСЯ ЛИ СООТВЕТСТВУЮЩИЙ ВНЕШНИЙ УЗЕЛ НА НЕЧЕТНОМ ИЛИ ЧЕТНОМ УРОВНЕ.
эТУ ПРОБЛЕМУ МОЖНО РАЗРЕШИТЬ, НЕ ЗНАЯ~$S$ ЗАРАНЕЕ, ПУТЕМ КОПИРОВАНИЯ
ОТРЕЗКОВ, КОТОРЫЕ ДОЛЖНЫ БЫТЬ УБЫВАЮЩИМИ, НА ВСПОМОГАТЕЛЬНУЮ ЛЕНТУ (ИЛИ
ЛЕНТЫ) НЕПОСРЕДСТВЕННО ПЕРЕД ТЕМ, КАК ОНИ ТРЕБУЮТСЯ. тОГДА СУММАРНОЕ
КОЛИЧЕСТВО ОПЕРАЦИЙ, ИЗМЕРЯЕМОЕ В ДЛИНАХ НАЧАЛЬНЫХ ОТРЕЗКОВ, ОКАЖЕТСЯ РАВНЫМ
$$
S \log_{T-1} S+O(S).
\eqno(13)
$$

тАКИМ ОБРАЗОМ, СЛИЯНИЕ В ПРЯМОМ ПОРЯДКЕ ОПРЕДЕЛЕННО ЛУЧШЕ МНОГОФАЗНОГО ИЛИ
КАСКАДНОГО ПРИ~$S\to\infty$; В ДЕЙСТВИТЕЛЬНОСТИ ОНО АСИМПТОТИЧЕСКИ
\emph{ОПТИМАЛЬНО,} ТАК КАК~(9) ПОКАЗЫВАЕТ, ЧТО~$S\log_{T-1} S+O(S)$---ЭТО
НАИЛУЧШЕЕ, ЧТО МЫ ВООБЩЕ МОЖЕМ НАДЕЯТЬСЯ ПОЛУЧИТЬ С $T$~ЛЕНТАМИ. с ДРУГОЙ
СТОРОНЫ, ДЛЯ СРАВНИТЕЛЬНО НЕБОЛЬШИХ ЗНАЧЕНИЙ~$S$, ОБЫЧНО ВСТРЕЧАЮЩИХСЯ
НА ПРАКТИКЕ, СЛИЯНИЕ В ПРЯМОМ ПОРЯДКЕ ВЕСЬМА НЕЭФФЕКТИВНО;
МНОГОФАЗНЫЙ ИЛИ КАСКАДНЫЙ МЕТОДЫ ПРОЩЕ И БЫСТРЕЕ, ЕСЛИ $S$~ОТНОСИТЕЛЬНО
МАЛО. вОЗМОЖНО, УДАСТСЯ ИЗОБРЕСТИ ПРОСТУЮ СХЕМУ РАСПРЕДЕЛЕНИЯ И СЛИЯНИЯ,
КОТОРАЯ СРАВНИМА С МНОГОФАЗНОЙ И КАСКАДНОЙ ДЛЯ НЕБОЛЬШИХ~$S$ И
АСИМПТОТИЧЕСКИ ОПТИМАЛЬНА ПРИ БОЛЬШИХ~$S$.

нИЖЕ В УПРАЖНЕНИЯХ ВТОРОЙ ЧАСТИ ДЕМОНСТРИРУЕТСЯ, КАК кАРП АНАЛОГИЧНЫМ
ОБРАЗОМ ПОСТАВИЛ ВОПРОС ДЛЯ СЛИЯНИЯ С \emph{ПРЯМЫМ ЧТЕНИЕМ.} тЕОРИЯ
ОКАЗЫВАЕТСЯ В ЭТОМ СЛУЧАЕ ЗНАЧИТЕЛЬНО- БОЛЕЕ СЛОЖНОЙ, ХОТЯ БЫЛИ ПОЛУЧЕНЫ
НЕКОТОРЫЕ ВЕСЬМА ИНТЕРЕСНЫЕ РЕЗУЛЬТАТЫ.

\excercises  (первая часть)
\ex[17] пРИ СЛИЯНИИ С ПРЯМЫМ ЧТЕНИЕМ ЧАСТО УДОБНО ОТМЕЧАТЬ КОНЕЦ КАЖДОГО
ОТРЕЗКА НА ЛЕНТЕ ПУТЕМ ДОБАВЛЕНИЯ ИСКУССТВЕННОЙ "КОНЦЕВОЙ" ЗАПИСИ С
КЛЮЧОМ~$+\infty$. кАК СЛЕДУЕТ ВИДОИЗМЕНИТЬ ЭТОТ МЕТОД ПРИ ОБРАТНОМ ЧТЕНИИ?

\ex[20] бУДУТ ЛИ СТОЛБЦЫ ТАБЛИЦЫ, АНАЛОГИЧНОЙ~(1), ВСЕГДА НЕУБЫВАЮЩИМИ,
ИЛИ БЫВАЮТ СЛУЧАИ, КОГДА НАМ ПРИДЕТСЯ "ВЫЧИТАТЬ" ОТРЕЗКИ С НЕКОТОРОЙ
ЛЕНТЫ ПРИ ПЕРЕХОДЕ ОТ ОДНОГО УРОВНЯ К СЛЕДУЮЩЕМУ?

\rex[20] дОКАЖИТЕ, ЧТО МЕТОД МНОГОФАЗНОГО РАСПРЕДЕЛЕНИЯ, ОПИСАННЫЙ В СВЯЗИ
С~(1), ДАЕТ ПОСЛЕ ЗАВЕРШЕНИЯ СОРТИРОВКИ НА ЛЕНТЕ~T1, ВСЕГДА ОТРЕЗОК~$A$,
ЕСЛИ ПЕРВОНАЧАЛЬНО НА~T1 БЫЛО~$ADA\ldots$, А НА~T2--T5 БЫЛО~$DAD\ldots\,$.

\ex[22] кАК ВЫ ОЦЕНИВАЕТЕ ИДЕЮ ВЫПОЛНЯТЬ МНОГОФАЗНОЕ СЛИЯНИЕ С ОБРАТНЫМ
ЧТЕНИЕМ, РАСПРЕДЕЛИВ ВСЕ ОТРЕЗКИ В \emph{ВОЗРАСТАЮЩЕМ} ПОРЯДКЕ И СЧИТАЯ,
 ЧТО ВСЕ ПОЗИЦИИ~"$D$" ПЕРВОНАЧАЛЬНО ЗАПОЛНЕНЫ ФИКТИВНЫМИ ОТРЕЗКАМИ?

\rex[23] кАКИЕ ФОРМУЛЫ ДЛЯ СТРОК ЧИСЕЛ СЛИЯНИЯ ВМЕСТО~(8), (9), (10)
И~(11) ИЗ~5.4.2 БУДУТ СПРАВЕДЛИВЫ ДЛЯ МНОГОФАЗНОГО СЛИЯНИЯ С ОБРАТНЫМ
ЧТЕНИЕМ? иЗОБРАЗИТЕ ЧИСЛА СЛИЯНИЯ ДЛЯ РАСПРЕДЕЛЕНИЯ ПЯТОГО УРОВНЯ НА
ШЕСТИ ЛЕНТАХ, НАРИСОВАВ ДИАГРАММУ, АНАЛОГИЧНУЮ РИС.~71(a).

\ex[07] кАКОВО ВЕКТОРНОЕ ПРЕДСТАВЛЕНИЕ СХЕМЫ СЛИЯНИЯ,
ПРЕДСТАВЛЕНИЕМ КОТОРОЙ В ВИДЕ ДЕРЕВА ЯВЛЯЕТСЯ~(8)?

%%368
\ex[16] нАРИСУЙТЕ ПРЕДСТАВЛЕНИЕ В ВИДЕ ДЕРЕВА СХЕМЫ СЛИЯНИЯ С ОБРАТНЫМ
ЧТЕНИЕМ, ОПРЕДЕЛЕННОЙ СЛЕДУЮЩЕЙ ПОСЛЕДОВАТЕЛЬНОСТЬЮ ВЕКТОРОВ:
{\def\!{\phantom{+}}\def\y#1{y^{(#1)}}\ctable{
$#$&$\hbox{}#$ \bskip & $#$&$\hbox{}#$ \bskip& $#$&$\hbox{}#$ \cr
v^{(33)} &= (\!20,\!9,\!5) & \y{22} &= (+1, -1, +1) & \y{10} &= (+1, +1, -1)\cr
\y{33} &= (+1, -1, +1) & \y{21} &= (-1, +1, +1) & \y{9} &= (+1, -1, +1) \cr
\y{32} &= (+1, +1, -1) & \y{20} &= (+1, +1, -1) & \y{8} &= (+1, +1, -1) \cr
\y{31} &= (+1, +1, -1) & \y{19} &= (-1, +1, +1) & \y{7} &= (+1, +1, -1) \cr
\y{30} &= (+1, +1, -1) & \y{18} &= (+1, +1, -1) & \y{6} &= (+1, +1, -1) \cr
\y{29} &= (+1, -1, +1) & \y{17} &= (+1, +1, -1) & \y{5} &= (-1, +1, +1) \cr
\y{28} &= (-1, +1, +1) & \y{16} &= (+1, +1, -1) & \y{4} &= (+1, -1, +1) \cr
\y{27} &= (+1, -1, +1) & \y{15} &= (+1, +1, -1) & \y{3} &= (-1, +1, +1) \cr
\y{26} &= (+1, -1, +1) & \y{14} &= (+1, -1, +1) & \y{2} &= (+1, -1, +1) \cr
\y{25} &= (+1, +1, -1) & \y{13} &= (+1, -1, +1) & \y{1} &= (-1, +1, +1) \cr
\y{24} &= (+1, -1, +1) & \y{12} &= (-1, +1, +1) & \y{0} &=(\!1,\!0,\!0) \cr
\y{23} &= (+1, -1, +1) & \y{11} &= (+1, +1, -1)\cr
}}

\ex[23] дОКАЖИТЕ, ЧТО~(8)---ОПТИМАЛЬНЫЙ СПОСОБ СЛИЯНИЯ С ОБРАТНЫМ ЧТЕНИЕМ
ПРИ~$S=7$ И~$T=4$ И ЧТО ВСЕ МЕТОДЫ, ИЗБЕГАЮЩИЕ ОДНОПУТЕВОГО СЛИЯНИЯ, ХУЖЕ.

\ex[м22] дОКАЖИТЕ НИЖНЮЮ ОЦЕНКУ~(9).

\ex[41] пРИ ПОМОЩИ эвм СОСТАВЬТЕ ТАБЛИЦУ ТОЧНЫХ ЗНАЧЕНИЙ~$K_T(n)$.

\rex[20] вЕРНО ЛИ УТВЕРЖДЕНИЕ, ЧТО ДЛЯ ЛЮБОЙ СХЕМЫ СЛИЯНИЯ С ОБРАТНЫМ
ЧТЕНИЕМ, НЕ ИСПОЛЬЗУЮЩЕЙ НИЧЕГО, КРОМЕ $(T-1)\hbox{-ПУТЕВОГО}$ СЛИЯНИЯ,
НЕОБХОДИМО, ЧТОБЫ ОТРЕЗКИ НА КАЖДОЙ ЛЕНТЕ ЧЕРЕДОВАЛИСЬ: $ADAD\ldots$,
Т.~Е.\ ОНА НЕ БУДЕТ РАБОТАТЬ, ЕСЛИ ДВА СОСЕДНИХ ОТРЕЗКА ОКАЖУТСЯ ОДИНАКОВО УПОРЯДОЧЕННЫМИ?

\ex[22] дОКАЖИТЕ, ЧТО КОНСТРУКЦИЯ С ПРЯМЫМ ПОРЯДКОМ кАРПА ВСЕГДА ПОРОЖДАЕТ
ПОМЕЧЕННОЕ ДЕРЕВО, УДОВЛЕТВОРЯЮЩЕЕ УСЛОВИЯМ~(a), (b), (c).

\ex[1Б] сДЕЛАЙТЕ~(12) БОЛЕЕ ЭФФЕКТИВНЫМ, УДАЛИВ КАК МОЖНО
БОЛЬШЕ ОДНОПУТЕВЫХ СЛИЯНИЙ, ОДНАКО ТАК, ЧТОБЫ ПРЯМОЙ ПОРЯДОК ВСЕ ЕЩЕ ДАВАЛ
ПРАВИЛЬНУЮ РАССТАНОВКУ МЕТОК У ВНУТРЕННИХ УЗЛОВ.

\ex[40] пРИДУМАЙТЕ АЛГОРИТМ, КОТОРЫЙ ВЫПОЛНЯЕТ СЛИЯНИЕ В ПРЯМОМ
ПОРЯДКЕ БЕЗ ЯВНОГО ПОСТРОЕНИЯ ДЕРЕВА В ШАГАХ~P2 И~Pз, ИСПОЛЬЗУЯ ТОЛЬКО
$O(\log S)$~СЛОВ ПАМЯТИ ДЛЯ УПРАВЛЕНИЯ СЛИЯНИЕМ.

\ex[м39] кОНСТРУКЦИЯ кАРПА С ПРЯМЫМ ПОРЯДКОМ ПОРОЖДАЕТ ДЕРЕВЬЯ С
ОДНОПУТЕВЫМ СЛИЯНИЕМ В НЕКОТОРЫХ ТЕРМИНАЛЬНЫХ УЗЛАХ. дОКАЖИТЕ,
ЧТО ЕСЛИ~$T=3$, ТО МОЖНО ПОСТРОИТЬ АСИМПТОТИЧЕСКИЕ ОПТИМАЛЬНЫЕ
$3\hbox{-lifo}$~ДЕРЕВЬЯ, В КОТОРЫХ ИСПОЛЬЗУЕТСЯ ТОЛЬКО ДВУХПУТЕВОЕ СЛИЯНИЕ

дРУГИМИ СЛОВАМИ, ПУСТЬ $\hat K_T(n)$~БУДЕТ МИНИМАЛЬНОЙ ДЛИНОЙ ВНЕШНЕГО
ПУТИ СРЕДИ ВСЕХ $T\hbox{-lifo}$~ДЕРЕВЬЕВ С $n$~ВНЕШНИМИ УЗЛАМИ, ТАКИХ, ЧТО
КАЖДЫЙ ВНУТРЕННИЙ УЗЕЛ ИМЕЕТ СТЕПЕНЬ~$T-1$. дОКАЖИТЕ,
ЧТО~$\hat K_3(n)=n\log_2 n+O(n)$.

\ex[м46] (сОХРАНЯЮТСЯ ОБОЗНАЧЕНИЯ УПР.~15) вЕРНО ЛИ,
ЧТО~$\hat K_T(n)=n\log_{T-1}(n)+O(n)$ ДЛЯ \emph{ВСЕХ}~$T\ge 3$,
ЕСЛИ~$n \equiv 1 \pmod{T-1}$?

\rex[28] (рИЧАРД~д.~пРАТТ.) чТОБЫ ПОЛУЧИТЬ ВОЗРАСТАЮЩИЙ ПОРЯДОК В
КАСКАДНОМ СЛИЯНИИ С ОБРАТНЫМ ЧТЕНИЕМ, МЫ МОГЛИ БЫ ПОТРЕБОВАТЬ
\emph{ЧЕТНОГО} ЧИСЛА ПРОХОДОВ СЛИЯНИЯ; ЭТО ПРЕДПОЛАГАЕТ, ЧТО МЕТОД
НАЧАЛЬНОГО РАСПРЕДЕЛЕНИЯ НЕСКОЛЬКО ОТЛИЧЕН ОТ АЛГОРИТМА~5.4.3C.
(a)~иЗМЕНИТЕ~(5.4.3-1) ТАК, ЧТОБЫ БЫЛИ ПРЕДСТАВЛЕНЫ ТОЛЬКО ТОЧНЫЕ
РАСПРЕДЕЛЕНИЯ, КОТОРЫЕ ТРЕБУЮТ ЧЕТНОГО ЧИСЛА ПРОХОДОВ СЛИЯНИЯ. (b)
сКОНСТРУИРУЙТЕ СХЕМУ НАЧАЛЬНОГО РАСПРЕДЕЛЕНИЯ,
%% 369
ОСУЩЕСТВЛЯЮЩУЮ ИНТЕРПОЛЯЦИЮ МЕЖДУ ЭТИМИ ТОЧНЫМИ
РАСПРЕДЕЛЕНИЯМИ. [иНАЧЕ ГОВОРЯ, ЕСЛИ ЧИСЛО НАЧАЛЬНЫХ ОТРЕЗКОВ ПОПАДАЕТ
МЕЖДУ ТОЧНЫМИ РАСПРЕДЕЛЕНИЯМИ, ТО ЖЕЛАТЕЛЬНО СЛИТЬ НЕКОТОРЫЕ (НО НЕ ВСЕ)
ОТРЕЗКИ ДВАЖДЫ, ЧТОБЫ ДОСТИГНУТЬ ТОЧНОГО РАСПРЕДЕЛЕНИЯ.]

\ex[46] пРЕДПОЛОЖИМ, ЧТО ИМЕЕТСЯ $T$~ЛЕНТОЧНЫХ УСТРОЙСТВ ДЛЯ
НЕКОТОРОГО~$T\ge3$ И ЧТО $T1$~СОДЕРЖИТ $N$~ЗАПИСЕЙ, В ТО ВРЕМЯ КАК
ОСТАЛЬНЫЕ ЛЕНТЫ ПУСТЫ. вОЗМОЖНО ЛИ ОБРАТИТЬ ПОРЯДОК ЗАПИСЕЙ НА~$T1$ ЗА
ЧИСЛО ШАГОВ, МЕНЬШЕЕ~$O(N\log N)$, БЕЗ ОБРАТНОГО ЧТЕНИЯ? (эТА ОПЕРАЦИЯ
ЯВЛЯЕТСЯ, КОНЕЧНО, ТРИВИАЛЬНОЙ, ЕСЛИ ДОПУСКАЕТСЯ ОБРАТНОЕ ЧТЕНИЕ.)
сМ.~В~УПР.~5.2.5-14 КЛАСС ТАКИХ АЛГОРИТМОВ, КОТОРЫЕ, ОДНАКО, ТРАТЯТ
ПОРЯДКА $N \log N$~ШАГОВ.

упражнения. (вторая часть)


сЛЕДУЮЩИЕ УПРАЖНЕНИЯ РАЗВИВАЮТ ТЕОРИЮ ЛЕНТОЧНОГО СЛИЯНИЯ С ПРЯМЫМ ЧТЕНИЕМ.
в ЭТОМ СЛУЧАЕ КАЖДАЯ ЛЕНТА ДЕЙСТВУЕТ КАК ОЧЕРЕДЬ, А НЕ КАК СТЕК. сХЕМУ
СЛИЯНИЯ МОЖНО ПРЕДСТАВИТЬ ПОСЛЕДОВАТЕЛЬНОСТЬЮ
ВЕКТОРОВ~$y^{(n)}\ldots{}y^{(1)}y^{(0)}$ ТОЧНО ТАК ЖЕ, КАК В ТЕКСТЕ, НО
КОГДА МЫ ПРЕОБРАЗУЕМ ВЕКТОРНОЕ ПРЕДСТАВЛЕНИЕ В ПРЕДСТАВЛЕНИЕ В ВИДЕ ДЕРЕВА,
ТО МЫ ЗАМЕНЯЕМ ПРАВИЛО "ПОСЛЕДНИМ ОБРАЗОВАН---ПЕРВЫМ РАСТЕТ" НА "ПЕРВЫМ
ОБРАЗОВАН---ПЕРВЫМ РАСТЕТ". тАКИМ ОБРАЗОМ, НЕДОПУСТИМАЯ КОНФИГУРАЦИЯ~(4)
ДОЛЖНА БЫТЬ ЗАМЕНЕНА НА
\picture{p.369}
дЕРЕВО, КОТОРОЕ МОЖЕТ БЫТЬ ПОМЕЧЕНО ТАК, ЧТОБЫ ИЗОБРАЖАТЬ СЛИЯНИЕ С
ПРЯМЫМ ЧТЕНИЕМ НА $T$~ЛЕНТАХ, НАЗЫВАЕТСЯ~$T\hbox{-fifo}$%
\note{1}%
{"Fifo"---АББРЕВИАТУРА ОТ "first in first out" (ПЕРВЫМ ВКЛЮЧАЕТСЯ---ПЕРВЫМ
ИСКЛЮЧАЕТСЯ).---{\sl пРИМ. ПЕРЕВ.\/}}
ПО АНАЛОГИИ С ТЕРМИНОМ~$T\hbox{-lifo}$ В СЛУЧАЕ ОБРАТНОГО ЧТЕНИЯ.

еСЛИ ЛЕНТЫ МОЖНО ПРОЧИТАТЬ В ОБРАТНОМ НАПРАВЛЕНИИ, ОНИ ОБРАЗУЮТ ОЧЕНЬ
ХОРОШИЕ СТЕКИ. нО, К СОЖАЛЕНИЮ, ОНИ НЕ МОГУТ ОБРАЗОВАТЬ ОЧЕНЬ ХОРОШИЕ
УНИВЕРСАЛЬНЫЕ ОЧЕРЕДИ. еСЛИ МЫ В ПРОИЗВОЛЬНОМ ПОРЯДКЕ ЗАПИСЫВАЕМ И ЧИТАЕМ
ПО ПРАВИЛУ "ПЕРВЫМ ВКЛЮЧАЕТСЯ---ПЕРВЫМ ИСКЛЮЧАЕТСЯ", ТО ПРИХОДИТСЯ ТРАТИТЬ
МНОГО ВРЕМЕНИ НА ПЕРЕМОТКУ ОТ ОДНОЙ ЧАСТИ ЛЕНТЫ К ДРУГОЙ. хУЖЕ ТОГО---МЫ
ВСКОРЕ ПРОСКОЧИМ КОНЕЦ ЛЕНТЫ! мЫ СТАЛКИВАЕМСЯ С ТОЙ ЖЕ ПРОБЛЕМОЙ, ЧТО И
ПРОБЛЕМА ВЫХОДА ОЧЕРЕДИ ЗА ГРАНИЦУ ПАМЯТИ [СМ.\ СООТНОШЕНИЯ~(2.2.2-4)
И~(2.2.2-5)], НО РЕШЕНИЕ В ВИДЕ~(2.2.2-6) И~(2.2.2-7) НЕ ПРИМЕНИМО К
ЛЕНТАМ, ТАК КАК ОНИ НЕ ЯВЛЯЮТСЯ КОЛЬЦЕВЫМИ. пОЭТОМУ ДЕРЕВО БУДЕМ НАЗЫВАТЬ
\emph{СИЛЬНЫМ} $T\hbox{-fifo}$~ДЕРЕВОМ, ЕСЛИ ОНО МОЖЕТ БЫТЬ ПОМЕЧЕНО ТАК,
 ЧТОБЫ СООТВЕТСТВУЮЩАЯ СХЕМА СЛИЯНИЯ ИСПОЛЬЗОВАЛА ЛЕНТЫ, ПОДЧИНЯЯСЬ
ОСОБОЙ ДИСЦИПЛИНЕ: "ЗАПИСАТЬ, ПЕРЕМОТАТЬ, ПРОЧИТАТЬ ВСЕ, ПЕРЕМОТАТЬ;
ЗАПИСАТЬ, ПЕРЕМОТАТЬ, ПРОЧИТАТЬ ВСЕ, ПЕРЕМОТАТЬ; И Т.~Д.".

\ex[22] (р.~м.~кАРП.) нАЙДИТЕ БИНАРНОЕ ДЕРЕВО, КОТОРОЕ НЕ
ЯВЛЯЕТСЯ~$3\hbox{-fifo}$.

\rex[22] сФОРМУЛИРУЙТЕ УСЛОВИЕ "СИЛЬНОГО $T\hbox{-fifo}$" ДЕРЕВА В
ТЕРМИНАХ ДОСТАТОЧНО ПРОСТОГО ПРАВИЛА ОТНОСИТЕЛЬНО НЕДОПУСТИМЫХ
КОНФИГУРАЦИЙ МЕТОК ЛЕНТ, АНАЛОГИЧНОГО ($4'$).

\ex[18] нАРИСУЙТЕ ПРЕДСТАВЛЕНИЕ В ВИДЕ ДЕРЕВА СХЕМЫ СЛИЯНИЯ С ПРЯМЫМ
ЧТЕНИЕМ; ОПРЕДЕЛЕННОЙ ПОСРЕДСТВОМ ВЕКТОРОВ В УПР.~7. яВЛЯЕТСЯ ЛИ
ЭТО ДЕРЕВО СИЛЬНЫМ~$3\hbox{-fifo}$?

\ex[28] (р.~м.~кАРП.) дОКАЖИТЕ, ЧТО ПРЕДСТАВЛЕНИЯ В ВИДЕ ДЕРЕВА
МНОГОФАЗНОГО И КАСКАДНОГО СЛИЯНИЯ С ТОЧНЫМ РАСПРЕДЕЛЕНИЕМ ПОЛНОСТЬЮ ОДИНАКОВЫ
%% 370
КАК В СЛУЧАЕ ОБРАТНОГО ЧТЕНИЯ, ТАК И В СЛУЧАЕ ПРЯМОГО ЧТЕНИЯ, ЗА
ИСКЛЮЧЕНИЕМ НОМЕРОВ, КОТОРЫМИ ПОМЕЧЕНЫ ВНУТРЕННИЕ УЗЛЫ. нАЙДИТЕ БОЛЕЕ
ШИРОКИЙ КЛАСС ВЕКТОРНЫХ, ПРЕДСТАВЛЕНИЙ СХЕМ СЛИЯНИЯ, ДЛЯ КОТОРЫХ ЭТО ВЕРНО.

\ex[24] (р.~м.~кАРП.) бУДЕМ ГОВОРИТЬ, ЧТО ОТРЕЗОК~$y^{(q)}\ldots{}y^{(r)}$
СХЕМЫ СЛИЯНИЯ ЯВЛЯЕТСЯ \dfn{СТАДИЕЙ,} ЕСЛИ НИКАКАЯ ВЫВОДНАЯ ЛЕНТА НЕ
ИСПОЛЬЗУЕТСЯ В ДАЛЬНЕЙШЕМ КАК ВВОДНАЯ, Т.~Е.\ ЕСЛИ НЕ СУЩЕСТВУЕТ~$i$, $j$,
$k$, ТАКИХ, ЧТО~$q\ge i> k \ge r$ И~$y^{(i)}_j=-1$, $y^{(k)}_j=+1$. цЕЛЬ
ЭТОГО УПРАЖНЕНИЯ---ДОКАЗАТЬ, ЧТО \emph{КАСКАДНОЕ СЛИЯНИЕ МИНИМИЗИРУЕТ ЧИСЛО
СТАДИЙ} СРЕДИ ВСЕХ СХЕМ СЛИЯНИЯ С ТЕМ ЖЕ ЧИСЛОМ ЛЕНТ И НАЧАЛЬНЫХ ОТРЕЗКОВ.

уДОБНО ВВЕСТИ НЕКОТОРЫЕ ОБОЗНАЧЕНИЯ. бУДЕМ ПИСАТЬ~$v\to w$, ЕСЛИ~$v$
И~$w$---ТАКИЕ $T\hbox{-ВЕКТОРЫ}$, ЧТО СУЩЕСТВУЕТ СХЕМА СЛИЯНИЯ, КОТОРАЯ В
СВОЕЙ ПЕРВОЙ СТАДИИ ПЕРЕВОДИТ~$w$ В~$v$ (Т.~Е.\ СУЩЕСТВУЕТ СХЕМА
СЛИЯНИЯ~$y^{(m)}\ldots{}y^{(0)}$, ТАКАЯ, ЧТО
$y^{(m)}\ldots{}y^{(l+1)}$~ЯВЛЯЕТСЯ СТАДИЕЙ, $w=y^{(m)}+\cdots+y^{(0)}$
И~$v=y^{(l)}+\cdots+y^{(0)}$). бУДЕМ ПИСАТЬ~$v\preceq w$, ЕСЛИ~$v$
И~$w$---$T\hbox{-ВЕКТОРЫ}$, ТАКИЕ, ЧТО СУММА НАИБОЛЬШИХ $k$~ЭЛЕМЕНТОВ
ВЕКТОРА~$v$ НЕ ПРЕВЫШАЕТ СУММЫ НАИБОЛЬШИХ $k$~ЭЛЕМЕНТОВ ВЕКТОРА~$w$
ПРИ~$1\le k \le T$. тАК, НАПРИМЕР,
$(2, 1, 2, 2, 2, 1) \preceq (1, 2, 3, 0, 3, 1)$,
ТАК КАК $2\le 3$,  $2+2\le 3+3$,~\dots, $2+2+2+2+ 1+1\le 3+3+2+1+1 +0$.
нАКОНЕЦ, ЕСЛИ~$v=(v_1,~\ldots, v_T)$,
ТО ПУСТЬ~$C(v)=(s_T, s_{T-2}, s_{T-3},~\ldots, s_1, 0)$,  ГДЕ $s_k$~ЕСТЬ
СУММА НАИБОЛЬШИХ $k$~ЭЛЕМЕНТОВ ВЕКТОРА~$v$.

%% !!! ССЫЛКА НА УПРАЖНЕНИЕ
(a)~дОКАЖИТЕ, ЧТО~$v\to C(v)$. (b)~дОКАЖИТЕ, ЧТО~$v\preceq w$
ВЛЕЧЕТ~$C(v)\preceq C(w)$. (c)~сЧИТАЯ ИЗВЕСТНЫМ РЕЗУЛЬТАТ УПР.~24,
ДОКАЖИТЕ, ЧТО КАСКАДНОЕ СЛИЯНИЕ МИНИМИЗИРУЕТ ЧИСЛО СТАДИЙ.

%% !!! ССЫЛКА НА УПРАЖНЕНИЕ
\ex[м35] иСПОЛЬЗУЯ ОБОЗНАЧЕНИЯ УПР.~23, ДОКАЖИТЕ, ЧТО~$v\to w$
ВЛЕЧЕТ~$w\preceq C(v)$.

%% !!! ССЫЛКА НА УПРАЖНЕНИЕ
\ex[м36] (р.~м.~кАРП.) бУДЕМ ГОВОРИТЬ, ЧТО
СЕГМЕНТ~$y^{(q)}\ldots{}y^{(r)}$ СХЕМЫ СЛИЯНИЯ ЯВЛЯЕТСЯ \dfn{ФАЗОЙ,} ЕСЛИ
НИ ОДНА ИЗ ЛЕНТ НЕ ИСПОЛЬЗУЕТСЯ И ДЛЯ ВВОДА, И ДЛЯ ВЫВОДА, Т.~Е.\ ЕСЛИ НЕ
СУЩЕСТВУЕТ~$i$, $j$, $k$, ТАКИХ, ЧТО~$q\ge i$, $k\ge r$ И~$y^{(i)}_j=+1$,
$y^{(k)}_j=-1$. цЕЛЬ ЭТОГО УПРАЖНЕНИЯ---ИССЛЕДОВАТЬ СХЕМУ СЛИЯНИЯ, КОТОРАЯ
МИНИМИЗИРУЕТ ЧИСЛО ФАЗ. мЫ БУДЕМ ПИСАТЬ~$v \To w$, ЕСЛИ~$w$ МОЖЕТ БЫТЬ
ПРЕОБРАЗОВАНО В~$v$ ЗА ОДНУ ФАЗУ (СР.~С~ПОДОБНЫМ ОБОЗНАЧЕНИЕМ,
ВВЕДЕННЫМ В УПР.~23), И ПУСТЬ~$D_k(v)=(s_k+t_{k+1}, s_k+t_{k+2},~\ldots,
s_k+t_T, 0,~\ldots, 0)$, ГДЕ~$t_j$ ОБОЗНАЧАЕТ~$j\hbox{-Й}$ В ПОРЯДКЕ
УБЫВАНИЯ ЭЛЕМЕНТ~$v$ И~$s_k=t_1+\cdots+t_k$. (a)~дОКАЖИТЕ, ЧТО~$v\To
D_k(v)$ ПРИ~$1\le k < T$. (b)~дОКАЖИТЕ, ЧТО ИЗ~$v\preceq w$
СЛЕДУЕТ~$D_k(v)\preceq D_k(w)$ ПРИ~$1\le k < T$. (c)~дОКАЖИТЕ, ЧТО
ИЗ~$v\To w$ СЛЕДУЕТ~$w\preceq D_k(v)$ ДЛЯ НЕКОТОРОГО~$k$, $1\le k < T$.
(d)~сЛЕДОВАТЕЛЬНО, СХЕМА СЛИЯНИЯ, СОРТИРУЮЩАЯ МАКСИМАЛЬНОЕ ЧИСЛО НАЧАЛЬНЫХ
ОТРЕЗКОВ НА $T$~ЛЕНТАХ ЗА $q$~ФАЗ, МОЖЕТ БЫТЬ ИЗОБРАЖЕНА
ПОСЛЕДОВАТЕЛЬНОСТЬЮ .ЦЕЛЫХ ЧИСЕЛ~$k_1 k_2~\ldots k_q$, ТАКОЙ,
ЧТО НАЧАЛЬНОЕ РАСПРЕДЕЛЕНИЕ ЕСТЬ~$D_{k_q}(\ldots D_{k_2}(D_{k_1}(u))\ldots)$,
%!!! ССЫЛКА НА УПРАЖНЕНИЕ
ГДЕ~$u=(1, 0,~\ldots, 0)$. эТА СТРАТЕГИЯ МИНИМУМА ФАЗ, ИМЕЕТ СИЛЬНОЕ
$T\hbox{-fifo}$~ПРЕДСТАВЛЕНИЕ, И ОНА ТАКЖЕ ВХОДИТ В КЛАСС СХЕМ УПР.~22.
кОГДА~$T=3$, ЭТО \emph{МНОГОФАЗНАЯ} СХЕМА, А ПРИ~$T=4$, 5, 6, 7 ЭТО
ВАРИАЦИЯ \emph{СБАЛАНСИРОВАННОЙ} СХЕМЫ.

%!!! ССЫЛКА НА УПРАЖНЕНИЕ
\ex[м46] (р.~м.~кАРП). вЕРНО ЛИ, ЧТО ОПТИМАЛЬНАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ~$k_1
k_2~\ldots k_q$, УПОМЯНУТАЯ В УПР.~25, ВСЕГДА
РАВНА~$1\ceil{T/2}\floor{T/2}\ceil{T/2}\floor{T/2}~\ldots$  ДЛЯ ВСЕХ~$T\ge
4$ И ВСЕХ ДОСТАТОЧНО БОЛЬШИХ~$q$?

\subsubchap{оСЦИЛЛИРУЮЩАЯ СОРТИРОВКА}%5.4.5

еЩЕ ОДИН ПОДХОД К СОРТИРОВКЕ СЛИЯНИЕМ БЫЛ ПРЕДЛОЖЕН шЕЛДОНОМ сОБЕЛЕМ В
[{\sl JACM,\/} {\bf 9} (1962), 372--375]. вМЕСТО ТОГО ЧТОБЫ НАЧИНАТЬ С
ПРОХОДА РАСПРЕДЕЛЕНИЯ, КОГДА ВСЕ НАЧАЛЬНЫЕ ОТРЕЗКИ РАСПРЕДЕЛЯЮТСЯ ПО
ЛЕНТАМ, ОН ПРЕДЛОЖИЛ АЛГОРИТМ, КОТОРЫЙ ПЕРЕКЛЮЧАЕТСЯ ТО НА РАСПРЕДЕЛЕНИЕ,
ТО НА СЛИЯНИЕ, ТАК ЧТО БОЛЬШАЯ ЧАСТЬ СОРТИРОВКИ ПРОИСХОДИТ ЕЩЕ ДО ТОГО,
 КАК ВСЯ ИСХОДНАЯ ИНФОРМАЦИЯ БУДЕТ ПОЛНОСТЬЮ ПРОСМОТРЕНА.
%%371
пРЕДПОЛОЖИМ, НАПРИМЕР, ЧТО ДЛЯ СЛИЯНИЯ ИСПОЛЬЗУЕТСЯ ПЯТЬ ЛЕНТ. пО МЕТОДУ
сОБЕЛЯ 16~НАЧАЛЬНЫХ ОТРЕЗКОВ БУДУТ СОРТИРОВАТЬСЯ СЛЕДУЮЩИМ ОБРАЗОМ:
\ctable{
#\hfil\bskip&#\hfil\bskip&\hfil$#$\hfil\bskip&\hfil$#$\hfil\bskip
&\hfil$#$\hfil\bskip&\hfil$#$\hfil\bskip&\hfil$#$\hfil\bskip
&#\hfil\cr
       & \hfil оПЕРАЦИЯ& T1    & T2    & T3  & T4     & T5    & \hbox{сТОИМОСТЬ} \cr
фАЗА~1.& рАСПРЕДЕЛЕНИЕ & A_1   & A_1   & A_1 & A_1    & -     &  4\cr
фАЗА~2.& сЛИЯНИЕ       & -     & -     & -   & -      & D_4   &  4\cr
фАЗА~3.& рАСПРЕДЕЛЕНИЕ & -     & A_1   & A_1 & A_1    & D_4A_1&  4\cr
фАЗА~4.& сЛИЯНИЕ       & D_4   & -     & -   & -      & D_4   &  4\cr
фАЗА~5.& рАСПРЕДЕЛЕНИЕ & D_4A_1& -     & A_1 & A_1    & D_4A_1&  4\cr
фАЗА~6.& сЛИЯНИЕ       & D_4   & D_4   & -   & -      & D_4   &  4\cr
фАЗА~7.& рАСПРЕДЕЛЕНИЕ & D_4A_1& D_4A_1& -   & A_1    & D_4A_1&  4\cr
фАЗА~8.& сЛИЯНИЕ       & D_4   & D_4   & D_4 & -      & D_4   &  4\cr
фАЗА~9.& сЛИЯНИЕ       & -     & -     & -   & A_{16} & -     & 16\cr
}
зДЕСЬ, КАК И В П.~5.4.4, МЫ ИСПОЛЬЗУЕМ~$A_r$ И~$D_r$ ДЛЯ ОБОЗНАЧЕНИЯ
СООТВЕТСТВЕННО ВОЗРАСТАЮЩИХ И УБЫВАЮЩИХ ОТРЕЗКОВ ОТНОСИТЕЛЬНОЙ ДЛИНЫ~$r$.
 рАССМАТРИВАЕМЫЙ МЕТОД НАЧИНАЕТ С ЗАПИСИ ПО ОДНОМУ НАЧАЛЬНОМУ ОТРЕЗКУ НА
КАЖДУЮ ИЗ ЧЕТЫРЕХ ЛЕНТ И СЛИВАЕТ ИХ (ЧИТАЯ В ОБРАТНОМ НАПРАВЛЕНИИ) НА
ПЯТУЮ ЛЕНТУ. оПЯТЬ ВОЗОБНОВЛЯЕТСЯ РАСПРЕДЕЛЕНИЕ, НА ЭТОТ РАЗ
ЦИКЛИЧЕСКИ СДВИНУТОЕ НА~1 ВПРАВО ПО ОТНОШЕНИЮ К ЛЕНТАМ, И ВТОРОЕ СЛИЯНИЕ
ДАЕТ ЕЩЕ ОДИН ОТРЕЗОК~$D_4$. кОГДА ЭТИМ СПОСОБОМ СФОРМИРОВАНЫ ЧЕТЫРЕ
ОТРЕЗКА~$D_4$, ДОПОЛНИТЕЛЬНОЕ СЛИЯНИЕ СОЗДАЕТ~$A_{16}$. пРОЦЕСС МОЖНО
ПРОДОЛЖАТЬ, СОЗДАВАЯ ЕЩЕ ТРИ~$A_{16}$, СЛИВАЯ ИХ В~$D_{64}$ И~Т.~Д.\ ДО
ТЕХ ПОР, ПОКА НЕ ИСЧЕРПАЮТСЯ ИСХОДНЫЕ ДАННЫЕ. нЕ НУЖНО ЗНАТЬ ЗАРАНЕЕ
ДЛИНУ ИСХОДНЫХ ДАННЫХ.

еСЛИ ЧИСЛО НАЧАЛЬНЫХ ОТРЕЗКОВ~$S$ ЕСТЬ~$4^m$, ТО НЕТРУДНО ВИДЕТЬ, ЧТО ЭТОТ
МЕТОД ОБРАБАТЫВАЕТ КАЖДУЮ ЗАПИСЬ РОВНО $m+1$~РАЗ (ОДИН РАЗ ВО ВРЕМЯ
РАСПРЕДЕЛЕНИЯ И $m$~РАЗ ВО ВРЕМЯ СЛИЯНИЯ). еСЛИ~$S$ ЛЕЖИТ МЕЖДУ~$4^{m-1}$
И~$4^m$, ТО МОЖНО С ПОМОЩЬЮ ФИКТИВНЫХ ОТРЕЗКОВ УВЕЛИЧИТЬ~$S$ ДО~$4^m$;
СЛЕДОВАТЕЛЬНО, ОБЩЕЕ ВРЕМЯ СОРТИРОВКИ БУДЕТ ОПРЕДЕЛЯТЬСЯ
$\ceil{\log_4 S}+1$~ПРОХОДАМИ ПО ВСЕМ ДАННЫМ. эТО КАК РАЗ ТО, ЧТО ДОСТИГАЕТСЯ
ПРИ СБАЛАНСИРОВАННОЙ СОРТИРОВКЕ НА \emph{ВОСЬМИ} ЛЕНТАХ; В ОБЩЕМ СЛУЧАЕ
ОСЦИЛЛИРУЮЩАЯ СОРТИРОВКА С $T$~РАБОЧИМИ ЛЕНТАМИ
ЭКВИВАЛЕНТНА СБАЛАНСИРОВАННОМУ СЛИЯНИЮ С $2(T-1)$~ЛЕНТАМИ, ТАК КАК
ОНА ДЕЛАЕТ $\ceil{\log_{T-1} S}+1$~ПРОХОДОВ ПО ДАННЫМ. еСЛИ
$S$~ОКАЗЫВАЕТСЯ СТЕПЕНЬЮ~$T-1$, ТО ЭТО САМОЕ ЛУЧШЕЕ, ЧТО МОЖНО ПОЛУЧИТЬ
ПРИ \emph{ЛЮБОМ} МЕТОДЕ С $T$~ЛЕНТАМИ, ТАК КАК ЗДЕСЬ ДОСТИГАЕТСЯ
НИЖНЯЯ ОЦЕНКА ИЗ СООТНОШЕНИЯ~(5.4.4-9). с ДРУГОЙ СТОРОНЫ,
ЕСЛИ~$S$ РАВНО~$(T-1)^{m-1}+1$, Т.~Е.\ РОВНО НА ЕДИНИЦУ БОЛЬШЕ
СТЕПЕНИ~$T-1$, ТО ЭТОТ МЕТОД ТЕРЯЕТ ПОЧТИ ЦЕЛЫЙ ПРОХОД.

в УПР.~2 ПОКАЗАНО, КАК УСТРАНИТЬ ЧАСТЬ ЭТОЙ ЛИШНЕЙ РАБОТЫ, ИСПОЛЬЗУЯ
СПЕЦИАЛЬНУЮ ПРОГРАММУ ОКОНЧАНИЯ. еЩЕ ОДНО УСОВЕРШЕНСТВОВАНИЕ БЫЛО
ПРЕДЛОЖЕНО В 1966~Г. дЕНИСОМ~л.~бЭНЧЕРОМ,
%% 372
КОТОРЫЙ НАЗВАЛ СВОЮ ПРОЦЕДУРУ ПЕРЕКРЕСТНЫМ СЛИЯНИЕМ.
[сМ.~H.~Wedekind, Datenorganisation (Berlin W. de Gruyter, 1970). 164--166,
 И~U.~S.~Patent~3540000 (10~НОЯБРЯ 1970).] оСНОВНАЯ ИДЕЯ СОСТОИТ В ТОМ,
ЧТОБЫ ОТЛОЖИТЬ СЛИЯНИЕ ДО ТЕХ ПОР, ПОКА НЕ БУДЕТ НАКОПЛЕНО БОЛЬШЕ СВЕДЕНИЙ
ОБ~$S$. мЫ ОБСУДИМ НЕСКОЛЬКО ИЗМЕНЕННУЮ ФОРМУ ПЕРВОНАЧАЛЬНОЙ СХЕМЫ бЭНЧЕРА.

эТА УЛУЧШЕННАЯ ОСЦИЛЛИРУЮЩАЯ СОРТИРОВКА ДЕЙСТВУЕТ СЛЕДУЮЩИМ ОБРАЗОМ:
\ctable{
#\hfil\bskip&#\hfil\bskip&\hfil$#$\hfil\bskip&\hfil$#$\hfil\bskip
&\hfil$#$\hfil\bskip&\hfil$#$\hfil\bskip&\hfil$#$\hfil\bskip
&#\hfil\cr
       & оПЕРАЦИЯ     & T1    & T2    & T3    & T4    & т5  &
\hbox{сТОИМОСТЬ} \cr
фАЗА~1.& рАСПРЕДЕЛЕНИЕ& -     & A_1   & A_1   & A_1   & A_1   & 4\cr
фАЗА~2.& рАСПРЕДЕЛЕНИЕ& -     & A_1   & A_1A_1& A_1A_1& A_1A_1& 3\cr
фАЗА~3.& сЛИЯНИЕ      & D_4   & -     & A_1   & A_1   & A_1   & 4\cr
фАЗА~4.& рАСПРЕДЕЛЕНИЕ& D_4A_1& -     & A_1   & A_1A_1& A_1A_1& 3\cr
фАЗА~5.& сЛИЯНИЕ      & D_4   & D_4   & -     & A_1   & A_1   & 4\cr
фАЗА~6.& рАСПРЕДЕЛЕНИЕ& D_4A_1& D_4A_1& -     & A_1   & A_1A_1& 3\cr
фАЗА~7.& сЛИЯНИЕ      & D_4   & D_4   & D_4   & -     & A_1   & 4\cr
фАЗА~8.& рАСПРЕДЕЛЕНИЕ& D_4A_1& D_4A_1& D_4A_1& -     & A_1   & 3\cr
фАЗА~9.& сЛИЯНИЕ      & D_4   & D_4   & D_4   & D_4   & -     & 4\cr
\noalign{\smallskip
\noindent
в ЭТОТ МОМЕНТ МЫ НЕ СЛИВАЕМ ВСЕ~$D_4$ В~$A_{16}$, (ЕСЛИ ТОЛЬКО НЕ
ОКАЖЕТСЯ, ЧТО ИСХОДНЫЕ ДАННЫЕ ИСЧЕРПАНЫ); ЛИШЬ ПОСЛЕ ТОГО, КАК ЗАКОНЧИТСЯ
\smallskip}
фАЗА~15.& сЛИЯНИЕ & D_4 D_4 & D_4 D_4 & D_4 D_4 & D_4 & - & 4 \cr
\noalign {\smallskip
\noindent БУДЕТ ПОЛУЧЕН ПЕРВЫЙ ОТРЕЗОК~$A_{16}$:
\smallskip}
фАЗА~16. & сЛИЯНИЕ &  D_4 & D_4 & D_4 - & A_{16} & 16 \cr
\noalign{\smallskip
\noindent вТОРОЙ ОТРЕЗОК~$A_{16}$ ПОЯВИТСЯ ПОСЛЕ СОЗДАНИЯ ЕЩЕ ТРЕХ~$D_4$:
\smallskip}
фАЗА~22. & сЛИЯНИЕ & D_4 D_4 & D_4 D_4 & D_4 & - & A_{16}D_4 & 4\cr
фАЗА~23. & сЛИЯНИЕ & D_4 & D_4 & - & A_{16} & A_{16} & 16 \cr
}
И~Т.~Д.\ (СР.~С~ФАЗАМИ~1--5). пРЕИМУЩЕСТВА СХЕМЫ бЭНЧЕРА МОЖНО ВИДЕТЬ,
ЕСЛИ ИМЕЕТСЯ, НАПРИМЕР, ТОЛЬКО ПЯТЬ НАЧАЛЬНЫХ ОТРЕЗКОВ: ОСЦИЛЛИРУЮЩАЯ
СОРТИРОВКА (ЕЕ МОДИФИКАЦИЯ ИЗ УПР.~2) ВЫПОЛНЯЛА БЫ ЧЕТЫРЕХПУТЕВОЕ СЛИЯНИЕ
(НА ФАЗЕ~2), ЗА КОТОРЫМ СЛЕДОВАЛО БЫ ДВУХПУТЕВОЕ СЛИЯНИЕ С ОБЩЕЙ
СТОИМОСТЬЮ~$4+4+4+1+5= 14$, ТОГДА КАК СХЕМА бЭНЧЕРА ВЫПОЛНЯЛА БЫ
ДВУХПУТЕВОЕ СЛИЯНИЕ (НА ФАЗЕ~3), ЗА КОТОРЫМ СЛЕДОВАЛО БЫ ЧЕТЫРЕХПУТЕВОЕ
СЛИЯНИЕ С ОБЩЕЙ СТОИМОСТЬЮ~$4+1+2+5=12$. (оБА МЕТОДА ТАКЖЕ ТРЕБУЮТ
НЕБОЛЬШИХ ДОПОЛНИТЕЛЬНЫХ ЗАТРАТ, ИМЕННО ОДНОКРАТНОЙ ПЕРЕМОТКИ ПЕРЕД
ОКОНЧАТЕЛЬНЫМ СЛИЯНИЕМ.)

%%373

тОЧНОЕ ОПИСАНИЕ МЕТОДА бЭНЧЕРА СОДЕРЖИТСЯ НИЖЕ В АЛГОРИТМЕ~B. к
СОЖАЛЕНИЮ, СООТВЕТСТВУЮЩУЮ ПРОЦЕДУРУ, ПО-ВИДИМОМУ, ТРУДНЕЙ ПОНЯТЬ, ЧЕМ
ЗАПРОГРАММИРОВАТЬ; ЛЕГЧЕ ОБЎЯСНИТЬ ЭТОТ МЕТОД эвм, ЧЕМ ПРОГРАММИСТУ!
чАСТИЧНО ЭТО ПРОИСХОДИТ ПО ТОЙ ПРИЧИНЕ, ЧТО РЕКУРСИВНЫЙ МЕТОД ВЫРАЖЕН В
ИТЕРАТИВНОМ ВИДЕ И ЗАТЕМ ПОДВЕРГНУТ НЕКОТОРОЙ ОПТИМИЗАЦИИ; ЧИТАТЕЛЬ,
ВОЗМОЖНО, ОБНАРУЖИТ, ЧТО НЕОБХОДИМО НЕСКОЛЬКО РАЗ ПРОСЛЕДИТЬ ЗА РАБОТОЙ
АЛГОРИТМА, ЧТОБЫ ДЕЙСТВИТЕЛЬНО ОСОЗНАТЬ, ЧТО ЖЕ ПРОИСХОДИТ.

\alg B.(оСЦИЛЛИРУЮЩАЯ СОРТИРОВКА С ПЕРЕКРЕСТНЫМ РАСПРЕДЕЛЕНИЕМ.) эТОТ
АЛГОРИТМ БЕРЕТ ПЕРВОНАЧАЛЬНЫЕ ОТРЕЗКИ И РАСПРЕДЕЛЯЕТ ИХ НО ЛЕНТАМ, ВРЕМЯ
ОТ ВРЕМЕНИ ПРЕРЫВАЯ ПРОЦЕСС РАСПРЕДЕЛЕНИЯ, ЧТОБЫ СЛИТЬ СОДЕРЖИМОЕ
НЕКОТОРЫХ ЛЕНТ.
\picture{рИС.~77. оСЦИЛЛИРУЮЩАЯ СОРТИРОВКА С ПЕРЕКРЕСТНЫМ РАСПРЕДЕЛЕНИЕМ.}
в АЛГОРИТМЕ ИСПОЛЬЗУЕТСЯ $P\hbox{-ПУТЕВОЕ}$ СЛИЯНИЕ И ПРЕДПОЛАГАЕТСЯ,
ЧТО ЕСТЬ $T=P+1\ge 3$~ЛЕНТОЧНЫХ УСТРОЙСТВ (НЕ СЧИТАЯ УСТРОЙСТВА, КОТОРОЕ
МОЖЕТ БЫТЬ НЕОБХОДИМО ДЛЯ ХРАНЕНИЯ ИСХОДНЫХ ДАННЫХ). лЕНТОЧНЫЕ УСТРОЙСТВА
ДОЛЖНЫ ДОПУСКАТЬ ЧТЕНИЕ КАК В ПРЯМОМ, ТАК И В ОБРАТНОМ НАПРАВЛЕНИИ; ОНИ
ОБОЗНАЧЕНЫ ЧИСЛАМИ~0, 1,~\dots, $P$. иСПОЛЬЗУЮТСЯ СЛЕДУЮЩИЕ МАССИВЫ:
{\medskip\narrower

\item{$|D|[j]$,} $0\le j \le P$---ЧИСЛО ФИКТИВНЫХ ОТРЕЗКОВ, НАЛИЧИЕ КОТОРЫХ
ПРЕДПОЛАГАЕТСЯ В КОНЦЕ ЛЕНТЫ~$j$.


\item{$|A|[l, j]$,} $0\le l \le L$, $0\le j \le P$. зДЕСЬ~$L$---ДОСТАТОЧНО
БОЛЬШОЕ ЧИСЛО, ТАКОЕ, ЧТО БУДЕТ  ВВЕДЕНО НЕ БОЛЕЕ~$P^{L+1}$ НАЧАЛЬНЫХ
ОТРЕЗКОВ. еСЛИ~$|A|[l, j]=k \ge 0$, ТО НА ЛЕНТЕ~$j$ ИМЕЕТСЯ ОТРЕЗОК
НОМИНАЛЬНОЙ ДЛИНЫ~$P^k$, СООТВЕТСТВУЮЩИЙ "УРОВНЮ~$l$" РАБОТЫ АЛГОРИТМА.
эТОТ ОТРЕЗОК ВОЗРАСТАЮЩИЙ, ЕСЛИ $k$~ЧЕТНО, И УБЫВАЮЩИЙ, ЕСЛИ $k$~НЕЧЕТНО.
$|A|[l, j]=-1$~ОЗНАЧАЕТ, ЧТО НА УРОВНЕ~$l$ ЛЕНТА~$j$ НЕ ИСПОЛЬЗУЕТСЯ.
\medskip}

\noindent иНСТРУКЦИЯ "ЗАПИСАТЬ НАЧАЛЬНЫЙ ОТРЕЗОК НА ЛЕНТУ~$j$"
ЯВЛЯЕТСЯ СОКРАЩЕННЫМ ОБОЗНАЧЕНИЕМ СЛЕДУЮЩИХ ДЕЙСТВИЙ:
%%374
{\medskip\narrower
\noindent уСТАНОВИТЬ~$|A|[l, j]\asg 0$. еСЛИ ИСХОДНЫЕ ДАННЫЕ ИСЧЕРПАНЫ, ТО
УВЕЛИЧИТЬ~$|D|[j]$ НА~1; В ПРОТИВНОМ СЛУЧАЕ ЗАПИСАТЬ ОТРЕЗОК НА
ЛЕНТУ~$j$ (В ВОЗРАСТАЮЩЕМ ПОРЯДКЕ).
\medskip}
\noindent иНСТРУКЦИЯ "СЛИТЬ НА ЛЕНТУ~$j$" ИСПОЛЬЗУЕТСЯ КАК КРАТКОЕ
ОБОЗНАЧЕНИЕ СЛЕДУЮЩИХ ДЕЙСТВИЙ:
{\medskip\narrower
\noindent еСЛИ~$|D|[i]>0$ ДЛЯ ВСЕХ~$i\ne j$, ТО УМЕНЬШИТЬ~$|D|[i]$ НА~1
ПРИ ВСЕХ~$i\ne j$ И УВЕЛИЧИТЬ~$|D|[j]$ НА~1. в ПРОТИВНОМ СЛУЧАЕ СЛИТЬ ОДИН
ОТРЕЗОК НА ЛЕНТУ~$j$ СО ВСЕХ ЛЕНТ~$i\ne j$, ТАКИХ, ЧТО~$|D|[i]=0$, И
УМЕНЬШИТЬ~$|D|[i]$ НА~1 ДЛЯ ВСЕХ ОСТАЛЬНЫХ~$i\ne j$.
\medskip}

\st[нАЧАЛЬНАЯ УСТАНОВКА.] уСТАНОВИТЬ~$|D|[j]\asg 0$ ПРИ~$0\le j \le P$.
зАТЕМ ЗАПИСАТЬ НАЧАЛЬНЫЙ ОТРЕЗОК НА ЛЕНТУ~$j$ ПРИ~$1 \le j \le P$.
уСТАНОВИТЬ~$|A|[0,0]\asg -1$, $l\asg 0$, $q\asg 0$.

\st[вВОД ЗАВЕРШЕН?] (в ЭТОТ МОМЕНТ ЛЕНТА~$q$ ПУСТА И ВСЯКАЯ ДРУГАЯ ЛЕНТА
СОДЕРЖИТ САМОЕ БОЛЬШЕЕ ОДИН ОТРЕЗОК.) еСЛИ ЕЩЕ ЕСТЬ ИСХОДНЫЕ ДАННЫЕ,
ПЕРЕЙТИ К ШАГУ~\stp{3}. оДНАКО ЕСЛИ ВВОД ИСЧЕРПАН, ТО ПЕРЕМОТАТЬ ВСЕ
ЛЕНТЫ~$j\ne q$, ТАКИЕ, ЧТО $|A|[0, j]$~ЧЕТНО; ЗАТЕМ СЛИТЬ НА ЛЕНТУ~$q$,
ЧИТАЯ ВСЕ ТОЛЬКО ЧТО ПЕРЕМОТАННЫЕ ЛЕНТЫ В ПРЯМОМ НАПРАВЛЕНИИ, А
ОСТАЛЬНЫЕ ЛЕНТЫ---В ОБРАТНОМ. эТИМ ЗАВЕРШАЕТСЯ СОРТИРОВКА; РЕЗУЛЬТАТ
НАХОДИТСЯ НА ЛЕНТЕ~$q$ В ВОЗРАСТАЮЩЕМ ПОРЯДКЕ.

\st[нАЧАТЬ НОВЫЙ УРОВЕНЬ.] уСТАНОВИТЬ~$l \asg l+1$, $r \asg q$, $s \asg 0$
И~$q\asg (q+1) \bmod T$. зАПИСАТЬ НАЧАЛЬНЫЙ ОТРЕЗОК НА ЛЕНТУ~$(q+j) \bmod T$
ПРИ~$1 \le j \le T-2$. (тАКИМ ОБРАЗОМ, НАЧАЛЬНЫЕ ОТРЕЗКИ ЗАПИСЫВАЮТСЯ НА
ВСЕ ЛЕНТЫ, КРОМЕ ЛЕНТ~$q$ И~$r$.) уСТАНОВИТЬ~$|A|[l, q]\asg -1$
И~$|A|[l, r] \asg -1$.

\st[мОЖНО ЛИ СЛИВАТЬ?] еСЛИ~$|A|[l-1, q]\ne s$, ВЕРНУТЬСЯ К ШАГУ~\stp{3}.

\st[сЛИЯНИЕ.] (в ЭТОТ МОМЕНТ $|A|[l-1, q]=|A|[l, j]=s$ ПРИ
ВСЕХ~$j\ne q$, $j \ne r$.) сЛИТЬ НА ЛЕНТУ~$r$. (сМ.\ ВЫШЕ ОПРЕДЕЛЕНИЕ ЭТОЙ
ОПЕРАЦИИ.) зАТЕМ УСТАНОВИТЬ~$s \asg s+1$, $l \asg l-1$,
$|A|[l, r]\asg s$ И~$|A|[l, q] \asg -1$. уСТАНОВИТЬ~$r \asg (2q-r)\bmod T$.
(в ОБЩЕМ СЛУЧАЕ МЫ ИМЕЕМ~$r=(q-1)\bmod T$, ЕСЛИ $s$~ЧЕТНО,
И~$r=(q+1) \bmod T$, ЕСЛИ $s$~НЕЧЕТНО.)

\st[зАКОНЧЕН ЛИ УРОВЕНЬ?] еСЛИ~$l=0$, ПЕРЕЙТИ К~\stp{2}. в ПРОТИВНОМ
СЛУЧАЕ, ЕСЛИ~$|A|[l, j]=s$ ДЛЯ ВСЕХ~$j\ne q$ И~$j\ne r$, ТО ПЕРЕЙТИ
К~\stp{4}. в ПРОТИВНОМ СЛУЧАЕ ВЕРНУТЬСЯ К~\stp{3}.
\algend

чТОБЫ ПОКАЗАТЬ ПРАВИЛЬНОСТЬ ЭТОГО АЛГОРИТМА, МЫ МОЖЕМ ИСПОЛЬЗОВАТЬ
ДОКАЗАТЕЛЬСТВО ТИПА "РЕКУРСИВНОЙ ИНДУКЦИИ", ТАК ЖЕ КАК МЫ ДЕЛАЛИ ДЛЯ
АЛГОРИТМА~2.3.1T. пРЕДПОЛОЖИМ, ЧТО МЫ НАЧИНАЕМ С ШАГА~B3 С~$l=l_0$,
$q=q_0$, $s_+=|A|[l_0, (q_0+1)\bmod T]$ И~$s_-=|A|[l_0, (q_0-1)\bmod T]$,
И ДОПУСТИМ, КРОМЕ ТОГО, ЧТО ЛИБО~$s_+=0$, ЛИБО~$s_-=1$, ЛИБО~$s_+=2$,
ЛИБО~$s_-=3$, ЛИБО~$\ldots\,$. мОЖНО ПРОВЕРИТЬ ПО ИНДУКЦИИ, ЧТО АЛГОРИТМ В
КОНЦЕ КОНЦОВ ПРИДЕТ К ШАГУ~B5, НЕ ИЗМЕНИВ С НУЛЕВОЙ ПО~$l\hbox{-Ю}$
СТРОКИ~|A| И СО ЗНАЧЕНИЯМИ
%%375
ПЕРЕМЕННЫХ~$l=l_0+1$, $q=q_0\pm 1$, $r=q_0$
И~$s=s_+ \ror s_-$, ПРИЧЕМ МЫ ВЫБИРАЕМ ЗНАК~$+$,
ЕСЛИ~$s_+=0 \ror  (s_+=2 \rand  s_-\ne 1) \ror (s_+=4 \rand s_-\ne 1, 3)
\ror \ldots$, И МЫ ВЫБИРАЕМ ЗНАК~$-$,
ЕСЛИ~$(s_-=1 \rand s_+=0) \ror (s_-=3 \rand s_+\ne 0, 2)\ror \ldots\,$.
пРИВЕДЕННЫЙ ЗДЕСЬ НАБРОСОК ДОКАЗАТЕЛЬСТВА НЕ ОЧЕНЬ ЭЛЕГАНТЕН, НО И
САМ АЛГОРИТМ СФОРМУЛИРОВАН В ВИДЕ, КОТОРЫЙ БОЛЬШЕ ГОДИТСЯ ДЛЯ РЕАЛИЗАЦИИ,
ЧЕМ ДЛЯ ПРОВЕРКИ ПРАВИЛЬНОСТИ.
\picture{рИС.~78 эФФЕКТИВНОСТЬ ОСЦИЛЛИРУЮЩЕЙ СОРТИРОВКИ, ИСПОЛЬЗУЮЩЕЙ
МЕТОД АЛГОРИТМА~B И~УПР.~3.}

нА РИС.~78 ПОКАЗАНА ЭФФЕКТИВНОСТЬ АЛГОРИТМА~B, ВЫРАЖЕННАЯ СРЕДНИМ ЧИСЛОМ
СЛИЯНИЙ КАЖДОЙ ЗАПИСИ В ЗАВИСИМОСТИ ОТ~$S$---ЧИСЛА НАЧАЛЬНЫХ ОТРЕЗКОВ,
ПРИЧЕМ ПРЕДПОЛАГАЕТСЯ, ЧТО НАЧАЛЬНЫЕ ОТРЕЗКИ ПРИБЛИЗИТЕЛЬНО РАВНЫ ПО
ДЛИНЕ. (сООТВЕТСТВУЮЩИЕ ГРАФИКИ ДЛЯ МНОГОФАЗНОЙ И КАСКАДНОЙ СОРТИРОВКИ
ПРИВЕДЕНЫ НА РИС.~70 И~74.) пРИ ПОДГОТОВКЕ РИС.~78 УЧТЕНО НЕБОЛЬШОЕ
УСОВЕРШЕНСТВОВАНИЕ, УПОМЯНУТОЕ В УПР.~3.

%%376

\section пРЯМОЕ ЧТЕНИЕ. сХЕМА ОСЦИЛЛИРУЮЩЕЙ СОРТИРОВКИ, ПО-ВИДИМОМУ,
 ТРЕБУЕТ ВОЗМОЖНОСТИ ОБРАТНОГО ЧТЕНИЯ, ПОСКОЛЬКУ ПРИХОДИТСЯ ГДЕ-ТО
НАКАПЛИВАТЬ ДЛИННЫЕ ОТРЕЗКИ ПО МЕРЕ ТОГО, КАК МЫ СЛИВАЕМ ВНОВЬ ВВЕДЕННЫЕ
КОРОТКИЕ ОТРЕЗКИ. тЕМ НЕ МЕНЕЕ м.~а.~гОТЦ
[Proc. AFIPS Spring Jt. сОТР. Conf.; {\bf 25} (1964), 599--607] НАШЕЛ
СПОСОБ ВЫПОЛНИТЬ ОСЦИЛЛИРУЮЩУЮ СОРТИРОВКУ, ИСПОЛЬЗУЯ ТОЛЬКО ПРЯМОЕ ЧТЕНИЕ
И ПРОСТУЮ ПЕРЕМОТКУ. еГО МЕТОД В КОРНЕ ОТЛИЧАЕТСЯ ОТ ОСТАЛЬНЫХ СХЕМ,
КОТОРЫЕ МЫ ВИДЕЛИ В ЭТОЙ ГЛАВЕ, ПОСКОЛЬКУ

a)~ДАННЫЕ ИНОГДА ЗАПИСЫВАЮТСЯ В НАЧАЛО ЛЕНТЫ, ПРИЧЕМ ПРЕДПОЛАГАЕТСЯ, ЧТО
ДАННЫЕ, НАХОДЯЩИЕСЯ В \emph{СЕРЕДИНЕ} ЭТОЙ ЛЕНТЫ, НЕ РАЗРУШАЮТСЯ;

b)~ВСЕ НАЧАЛЬНЫЕ СТРОКИ ИМЕЮТ ФИКСИРОВАННУЮ МАКСИМАЛЬНУЮ ДЛИНУ.
уСЛОВИЕ~(a) НАРУШАЕТ СВОЙСТВО "ПЕРВЫМ ВКЛЮЧАЕТСЯ---ПЕРВЫМ ИСКЛЮЧАЕТСЯ",
КОТОРОЕ, КАК МЫ ПРЕДПОЛОЖИЛИ, ЯВЛЯЕТСЯ ХАРАКТЕРИСТИКОЙ ПРЯМОГО ЧТЕНИЯ,
ОДНАКО ОНО МОЖЕТ БЫТЬ НАДЕЖНО РЕАЛИЗОВАНО, ЕСЛИ МЕЖДУ ОТРЕЗКАМИ
ОСТАВЛЯТЬ ДОСТАТОЧНОЕ КОЛИЧЕСТВО ЧИСТОЙ ЛЕНТЫ И ЕСЛИ В НУЖНЫЕ МОМЕНТЫ
ПРЕНЕБРЕЧЬ "ОШИБКАМИ ЧЕТНОСТИ". уСЛОВИЕ~(b) ОКАЗЫВАЕТСЯ ДО
НЕКОТОРОЙ СТЕПЕНИ ПРОТИВОРЕЧАЩИМ ЭФФЕКТИВНОМУ ИСПОЛЬЗОВАНИЮ ВЫБОРА С ЗАМЕЩЕНИЕМ.

оСЦИЛЛИРУЮЩАЯ СОРТИРОВКА гОТЦА С ПРЯМЫМ ЧТЕНИЕМ ИМЕЕТ ОДНО ТЕМНОЕ
ПЯТНО---ЭТО ОДИН ИЗ ПЕРВЫХ АЛГОРИТМОВ, КОТОРЫЙ БЫЛ ЗАПАТЕНТОВАН КАК АЛГОРИТМ,
 А НЕ КАК ФИЗИЧЕСКОЕ УСТРОЙСТВО [U.~S.~Patent~3380029 (23~АПРЕЛЯ 1968)].
еСЛИ ПОЛОЖЕНИЕ НЕ ИЗМЕНИТСЯ, ТО ЭТО ОЗНАЧАЕТ, ЧТО АЛГОРИТМ НЕЛЬЗЯ
ИСПОЛЬЗОВАТЬ В ПРОГРАММЕ БЕЗ РАЗРЕШЕНИЯ ВЛАДЕЛЬЦА ПАТЕНТА. мЕТОД
бЭНЧЕРА (ОСЦИЛЛИРУЮЩАЯ СОРТИРОВКА С ОБРАТНЫМ ЧТЕНИЕМ) БЫЛ ЗАПАТЕНТОВАН
IBM НЕСКОЛЬКИМИ ГОДАМИ ПОЗЖЕ. [тАКИМ ОБРАЗОМ, НАСТУПИЛ КОНЕЦ ЭРЫ, КОГДА
УДОВОЛЬСТВИЕ ОТ ОТКРЫТИЯ НОВОГО АЛГОРИТМА СЧИТАЛОСЬ ДОСТАТОЧНЫМ
ВОЗНАГРАЖДЕНИЕМ! тАК КАК ПРОГРАММИРОВАНИЕ НЕОТДЕЛИМО ОТ СОЗДАНИЯ МАШИНЫ,
А ПРОГРАММЫ ДЛЯ эвм ТЕПЕРЬ СТОЯТ ДЕНЕГ, ТО ПАТЕНТОВАНИЕ АЛГОРИТМОВ
ЯВЛЯЕТСЯ НЕИЗБЕЖНЫМ. кОНЕЧНО, ДЕЙСТВИЯ НЕДАЛЬНОВИДНЫХ ЛЮДЕЙ,
СОХРАНЯЮЩИХ НОВЫЕ АЛГОРИТМЫ В СТРОГОМ СЕКРЕТЕ, ЗНАЧИТЕЛЬНО ХУЖЕ,
ЧЕМ ШИРОКАЯ ДОСТУПНОСТЬ АЛГОРИТМОВ, КОТОРЫЕ ЯВЛЯЮТСЯ СОБСТВЕННОСТЬЮ В
ТЕЧЕНИЕ ЛИШЬ ОГРАНИЧЕННОГО ВРЕМЕНИ.]

цЕНТРАЛЬНАЯ ИДЕЯ В МЕТОДЕ гОТЦА СОСТОИТ В ТАКОМ ИСПОЛЬЗОВАНИИ ЛЕНТ,
ЧТОБЫ КАЖДАЯ ЛЕНТА НАЧИНАЛАСЬ С ОТРЕЗКА ОТНОСИТЕЛЬНОЙ ДЛИНЫ~1, ЗА
КОТОРЫМ СЛЕДОВАЛ БЫ ОТРЕЗОК ОТНОСИТЕЛЬНОЙ ДЛИНЫ~$P$, ЗАТЕМ~$P^2$ И~Т.~Д.
нАПРИМЕР, ЕСЛИ~$T=5$, ТО СОРТИРОВКА НАЧИНАЕТСЯ СЛЕДУЮЩИМ ОБРАЗОМ
("."~УКАЗЫВАЕТ ТЕКУЩЕЕ ПОЛОЖЕНИЕ ГОЛОВКИ ЧТЕНИЯ-ЗАПИСИ НА КАЖДОЙ ЛЕНТЕ):
%%377
\ctable{
#\hfil\bskip&#\hfil\bskip&\hfil$#$\hfil\bskip&\hfil$#$\hfil\bskip
&\hfil$#$\hfil\bskip&\hfil$#$\hfil\bskip&\hfil$#$\hfil\bskip
&\hfil$#$\hfil\bskip&#\hfil\cr
        & оПЕРАЦИЯ     & T1            & T2      & T3     & T4     & T5 &
 \hbox{сТОИМОСТЬ} & пРИМЕЧАНИЯ \cr
фАЗА~1. & рАСПРЕДЕЛЕНИЕ& A_1           & .A_1    & .A_1   & .A_1   & A_1.
  &  5& [T5 НЕ ПЕРЕМАТЫВАЕТСЯ]\cr
фАЗА~2. & сЛИЯНИЕ      & A_1.          & A_1.    & A_1.   & A_1.   &
A_1A_4. &  4& [пЕРЕМОТКА ВСЕХ ЛЕТ]\cr
фАЗА~3. & рАСПРЕДЕЛЕНИЕ& A_1           & .A_1    & .A_1   & A_1.   &
.A_1A_4 &  4& [T4 НЕ ПЕРЕМАТЫВАЕТСЯ]\cr
фАЗА~4. & сЛИЯНИЕ      & A_1.          & A_1.    & A_1.   & A_1A_4.&
A_1.A_4 &  4& [пЕРЕМОТКА ВСЕХ ЛЕНТ]\cr
фВЭА~5. & рАСПРЕДЕЛЕНИЕ& A_1           & .A_1    & A_1.   & .A_1A_4&
.A_1A_4 &  4& [T3 НЕ ПЕРЕМАТЫВАЕТСЯ]\cr
фАЗА~6. & сЛИЯНИЕ      & A_1.          & A_1.    & A_1A_4.& A_1.A_4&
A_1.A_4 &  4& [пЕРЕМОТКА ВСЕХ ЛЕНТ]\cr
фАЗА~7. & рАСПРЕДЕЛЕНИЕ& A_1           & A_1.    & .A_1A_4& .A_1A_4&
.A_1A_4 &  4& [T2 НЕ ПЕРЕМАТЫВАЕТСЯ]\cr
фАЗА~8. & сЛИЯНИЕ      & A_1.          & A_1A_4. & A_1.A_4& A_1.A_4&
A_1.A_4 &  4& [пЕРЕМОТКА ВСЕХ ЛЕНТ]\cr
ФАЗА~9. & рАСПРЕДЕЛЕНИЕ& A_1.          & .A_1A_4 & .A_1A_4& .A_1A_4&
.A_1A_4 &  4& [T1 НЕ ПЕРЕМАТЫВАЕТСЯ]\cr
фАЗА~10.& сЛИЯНИЕ      & A_1A_4.       & A_1.A_4 & A_1.A_4& A_1.A_4&
A_1.A_4 &  4& [нЕТ ПЕРЕМОТКИ]\cr
фАЗА~11.& сЛИЯНИЕ      & A_1A_4A_{16}. & A_1A_4. & A_1A_4.& A_1A_4.&
A_1A_4. & 16& [пЕРЕМОТКА ВСЕХ ЛЕНТ]\cr
}
и ТАК ДАЛЕЕ. вО ВРЕМЯ ФАЗЫ~1 ЛЕНТА~T1 ПЕРЕМАТЫВАЕТСЯ И ОДНОВРЕМЕННО
НА~T2 ЗАПИСЫВАЮТСЯ ИСХОДНЫЕ ДАННЫЕ, ЗАТЕМ ПЕРЕМАТЫВАЕТСЯ~T2 И
ОДНОВРЕМЕННО НА~T3 ЗАПИСЫВАЮТСЯ ИСХОДНЫЕ ДАННЫЕ И~Т.~Д. в КОНЦЕ КОНЦОВ,
КОГДА ИСХОДНЫЕ ДАННЫЕ ИСЧЕРПАНЫ, НАЧИНАЮТ ПОЯВЛЯТЬСЯ ФИКТИВНЫЕ ОТРЕЗКИ, И
ИНОГДА НЕОБХОДИМО ВООБРАЗИТЬ, ЧТО ОНИ ЗАПИСАНЫ ЯВНО НА ЛЕНТЕ ПОЛНОЙ
ДЛИНЫ. нАПРИМЕР, ЕСЛИ~$S=18$, ТО ОТРЕЗКИ~$A_1$ НА~T4 И~T5 БУДУТ
ФИКТИВНЫМИ ВО ВРЕМЯ ФАЗЫ~9; НАМ ПРИДЕТСЯ ПРОДВИНУТЬСЯ ВПЕРЕД ПО~T4 И~T5
ПРИ СЛИЯНИИ С~T2 И~T3 НА~T1 ВО ВРЕМЯ ФАЗЫ~10, ТАК КАК НАМ НАДО ДОБРАТЬСЯ
ДО ОТРЕЗКОВ~$A_4$ НА~T4 И~T5 ДЛЯ ПОДГОТОВКИ К ФАЗЕ~11. с ДРУГОЙ СТОРОНЫ,
ФИКТИВНЫЙ ОТРЕЗОК~$A_1$ НА~T1 НЕ ОБЯЗАТЕЛЬНО ДОЛЖЕН СУЩЕСТВОВАТЬ ЯВНО.
тАКИМ ОБРАЗОМ, "КОНЕЦ ИГРЫ" НЕСКОЛЬКО ЗАМЫСЛОВАТ. еЩЕ С ОДНИМ
ПРИМЕРОМ ПРИМЕНЕНИЯ ЭТОГО МЕТОДА МЫ ВСТРЕТИМСЯ В СЛЕДУЮЩЕМ ПУНКТЕ.

\excercises
\ex[22] в ТЕКСТЕ ИМЕЕТСЯ ИЛЛЮСТРАЦИЯ ОСЦИЛЛИРУЮЩЕЙ СОРТИРОВКИ сОБЕЛЯ В ЕЕ
ПЕРВОЗДАННОМ ВИДЕ ДЛЯ~$T=5$ И~$S=16$. дАЙТЕ ТОЧНОЕ ОПРЕДЕЛЕНИЕ АЛГОРИТМА,
 В КОТОРОМ ЭТА ПРОЦЕДУРА ОБОБЩАЕТСЯ И СОРТИРУЮТСЯ $S=P^L$~НАЧАЛЬНЫХ
ОТРЕЗКОВ НА $T=P+1\ge 3$~ЛЕНТАХ. пОСТАРАЙТЕСЬ НАЙТИ АЛГОРИТМ,
КОТОРЫЙ МОЖЕТ БЫТЬ ОЧЕНЬ ПРОСТО ОПИСАН.

\ex[24] еСЛИ В ИЗНАЧАЛЬНОМ МЕТОДЕ сОБЕЛЯ $S=6$, ТО МЫ МОГЛИ БЫ ЗАЯВИТЬ,
 ЧТО~$S=16$ И ЧТО ИМЕЕТСЯ 10~ФИКТИВНЫХ ОТРЕЗКОВ. тОГДА ФАЗА~3 В ПРИМЕРЕ В
ТЕКСТЕ ПОМЕСТИЛА БЫ ФИКТИВНЫЕ ОТРЕЗКИ~$A_0$ НА~T4 И~T5; ФАЗА~4 СЛИЛА
БЫ ОТРЕЗКИ~$A_1$ НА~T2 И~T3 В~$D_2$ НА~T1; ФАЗЫ~5--8 НЕ ДЕЛАЛИ БЫ НИЧЕГО;
ФАЗА~9 ПОРОДИЛА БЫ~$A_6$ НА~T4. лУЧШЕ БЫ ПЕРЕМОТАТЬ~T2 И~T3 СРАЗУ ПОСЛЕ
ФАЗЫ~3 И ЗАТЕМ НЕМЕДЛЕННО ПОЛУЧАТЬ~$A_6$ НА~T4 С ПОМОЩЬЮ ТРЕХПУТЕВОГО СЛИЯНИЯ.

пОКАЖИТЕ, КАК, ОСНОВЫВАЯСЬ НА ЭТОЙ ИДЕЕ, УЛУЧШИТЬ ОКОНЧАНИЕ АЛГОРИТМА ИЗ
УПР.~1, ЕСЛИ~$S$ НЕ ЯВЛЯЕТСЯ ТОЧНОЙ СТЕПЕНЬЮ~$P$.
\rex[24] сОСТАВЬТЕ ТАБЛИЦУ, ПОКАЗЫВАЮЩУЮ ПОВЕДЕНИЕ АЛГОРИТМА~B, ЕСЛИ~$T=3$,
 ПРЕДПОЛАГАЯ, ЧТО ИМЕЕТСЯ 9~НАЧАЛЬНЫХ ОТРЕЗКОВ. пОКАЖИТЕ, ЧТО
ЭТА ПРОЦЕДУРА ОЧЕВИДНО НЕЭФФЕКТИВНА В ОДНОМ МЕСТЕ, И ПРЕДЛОЖИТЕ
ИЗМЕНЕНИЯ В АЛГОРИТМЕ~B, КОТОРЫЕ ИСПРАВЛЯЮТ ПОЛОЖЕНИЕ.

\ex[21] нА ШАГЕ~B3 ИМЕЕТСЯ УСТАНОВКА КАК~$|A|[l, q]$, ТАК И~$|A|[l, r]$
В~$-1$. пОКАЖИТЕ, ЧТО ОДНА ИЗ ЭТИХ ОПЕРАЦИЙ ВСЕГДА ЛИШНЯЯ, ТАК КАК
СООТВЕТСТВУЮЩИЙ ЭЛЕМЕНТ МАССИВА~|A| НИКОГДА НЕ РАССМАТРИВАЕТСЯ.

\ex[м25] пУСТЬ~$S$---ЧИСЛО НАЧАЛЬНЫХ ОТРЕЗКОВ В ИМЕЮЩИХСЯ ИСХОДНЫХ ДАННЫХ
ДЛЯ АЛГОРИТМА~B. пРИ КАКИХ ЗНАЧЕНИЯХ~$S$ НЕ ТРЕБУЕТСЯ \emph{НИ ОДНОЙ
ПЕРЕМОТКИ} НА ШАГЕ~B2?
%%378

\bye\input style
\chapno=5\subchno=4\subsubchno=3\chapnotrue

кАСКАДНОЕ СЛИЯНИЕ, ПОДОБНО МНОГОФАЗНОМУ, НАЧИНАЕТСЯ С
"ТОЧНОГО РАСПРЕДЕЛЕНИЯ" ОТРЕЗКОВ ПО ЛЕНТАМ, ХОТЯ ПРАВИЛА ТОЧНОГО
РАСПРЕДЕЛЕНИЯ ОТЛИЧНЫ ОТ ПРАВИЛ П.~5.4.2. кАЖДАЯ СТРОКА
ТАБЛИЦЫ ПРЕДСТАВЛЯЕТ ПОЛНЫЙ ПРОХОД ПО \emph{ВСЕМ} ДАННЫМ. пРОХОД~2,
НАПРИМЕР, ПОЛУЧАЕТСЯ ПОСРЕДСТВОМ ВЫПОЛНЕНИЯ ПЯТИПУТЕВОГО СЛИЯНИЯ С~T1,
T2, T3, T4, T5 НА~T6, ПОКА~T5 НЕ СТАНЕТ ПУСТОЙ (ПРИ ЭТОМ НА~T6 ПОМЕЩАЮТСЯ
15~ОТРЕЗКОВ ОТНОСИТЕЛЬНОЙ ДЛИНЫ~5), ЗАТЕМ ЧЕТЫРЕХПУТЕВОГО СЛИЯНИЯ С~T1, T2,
T3, T4 НА~T5, ЗАТЕМ ТРЕХПУТЕВОГО СЛИЯНИЯ НА~T4, ДВУХПУТЕВОГО СЛИЯНИЯ
НА~T3 И, НАКОНЕЦ, ОДНОПУТЕВОГО СЛИЯНИЯ (ОПЕРАЦИИ КОПИРОВАНИЯ) С~T1
НА~T2. пРОХОД~3 ПОЛУЧАЕТСЯ ТАКИМ ЖЕ ОБРАЗОМ ПУТЕМ ВЫПОЛНЕНИЯ СНАЧАЛА
ПЯТИПУТЕВОГО СЛИЯНИЯ, ПОКА ОДНА ЛЕНТА НЕ СТАНЕТ ПУСТОЙ, ЗАТЕМ
ЧЕТЫРЕХПУТЕВОГО И~Т.~Д. (пОХОЖЕ, ЧТО ЭТОМУ ПУНКТУ КНИГИ СЛЕДОВАЛО БЫ
ПРИСВОИТЬ НОМЕР~5.4.3.2.1, А НЕ~5.4.3!)

яСНО, ЧТО ОПЕРАЦИИ КОПИРОВАНИЯ ИЗЛИШНИ, И ИХ МОЖНО БЫЛО БЫ ОПУСТИТЬ.
фАКТИЧЕСКИ, ОДНАКО, В СЛУЧАЕ ШЕСТИ ЛЕНТ ЭТО КОПИРОВАНИЕ ЗАНИМАЕТ ТОЛЬКО
НЕБОЛЬШОЙ ПРОЦЕНТ ВСЕГО ВРЕМЕНИ. эЛЕМЕНТЫ, КОТОРЫЕ ПОЛУЧАЮТСЯ ПРОСТЫМ
КОПИРОВАНИЕМ, ОТМЕЧЕНЫ В ПРИВЕДЕННОЙ ТАБЛИЦЕ ЗВЕЗДОЧКОЙ. тОЛЬКО~25 ИЗ~950
ОБРАБАТЫВАЕМЫХ ОТРЕЗКОВ ПРИНАДЛЕЖАТ ЭТОМУ КЛАССУ. бОЛЬШАЯ ЧАСТЬ
ВРЕМЕНИ ОТВОДИТСЯ ПЯТИПУТЕВОМУ И ЧЕТЫРЕХПУТЕВОМУ СЛИЯНИЯМ.

нА ПЕРВЫЙ ВЗГЛЯД МОЖЕТ ПОКАЗАТЬСЯ, ЧТО КАСКАДНАЯ СХЕМА---ДОВОЛЬНО ПЛОХОЙ
ВАРИАНТ В СРАВНЕНИИ С МНОГОФАЗНОЙ, ТАК КАК СТАНДАРТНАЯ МНОГОФАЗНАЯ СХЕМА
ИСПОЛЬЗУЕТ ВСЕ ВРЕМЯ $(T-1)\hbox{-ПУТЕВОЕ}$ СЛИЯНИЕ, В ТО ВРЕМЯ КАК
КАСКАДНАЯ ИСПОЛЬЗУЕТ $(T-1)\hbox{-ПУТЕВОЕ}$, $(T-2)\hbox{-ПУТЕВОЕ}$,
$(T-3)\hbox{-ПУТЕВОЕ}$ И~Т.~Д., НО В ДЕЙСТВИТЕЛЬНОСТИ ОНА АСИМПТОТИЧЕСКИ
\emph{ЛУЧШЕ,} ЧЕМ МНОГОФАЗНАЯ, ДЛЯ ШЕСТИ И БОЛЕЕ ЛЕНТ! кАК МЫ ВИДЕЛИ В
П.~5.4.2, ВЫСОКИЙ ПОРЯДОК СЛИЯНИЯ НЕ ЯВЛЯЕТСЯ ГАРАНТИЕЙ ЭФФЕКТИВНОСТИ. в
ТАБЛ.~1 ПОКАЗАНЫ ХАРАКТЕРИСТИКИ ВЫПОЛНЕНИЯ КАСКАДНОГО СЛИЯНИЯ ПО
АНАЛОГИИ С ПОДОБНОЙ ТАБЛИЦЕЙ П.~5.4.2.

нЕТРУДНО ВЫВЕСТИ "ТОЧНЫЕ РАСПРЕДЕЛЕНИЯ" ДЛЯ КАСКАДНОГО СЛИЯНИЯ. дЛЯ ШЕСТИ
ЛЕНТ ИМЕЕМ
$$
\matrix{
\hbox{уРОВЕНЬ} & T1 & T2 & T3 & T4 & T5 \cr
0 &   1 &   0 &   0 &   0 &  0 \cr
1 &   1 &   1 &   1 &   1 &  1 \cr
2 &   5 &   4 &   3 &   2 &  1 \cr
3 &  15 &  14 &  12 &   9 &  6 \cr
4 &  55 &  50 &  41 &  29 & 15 \cr
5 & 190 & 175 & 146 & 105 & 55 \cr
\multispan{6}\dotfill\cr
n & a_n & b_n & c_n & d_n & e_n \cr
n+1 & a_n+b_n+c_n+d_n+e_n & a_n+b_n+c_n+d_n & a_n+b_n+c_n & a_n+b_n & a_n \cr
}
\eqno(1)
$$
%%344
\htable{тАБЛИЦА 1}%
{хАРАКТЕР ПОВЕДЕНИЯ КАСКАДНОГО СЛИЯНИЯ}%
{\strut\hfill # && \bskip\hfill$#$\hfill\bskip\cr
лЕНТЫ  & \hbox{пРОХОДЫ} & \hbox{пРОХОДЫ} & \hbox{оТНОШЕНИЕ}\cr
 & \hbox{(С КОПИРОВАНИЕМ)} & \hbox{(БЕЗ КОПИРОВАНИЯ)} &\hbox{РОСТА}\cr
\noalign{\hrule}
 3 & 2.078\ln S+0.672 & 1.504\ln S+0.992 &  1.6180340\cr
 4 & 1.235\ln S+0.754 & 1.102\ln S+0.820 &  2.2469796\cr
 5 & 0.946\ln S+0.796 & 0.897\ln S+0.800 &  2.8793852\cr
 6 & 0.796\ln S+0.821 & 0.773\ln S+0.808 &  3.5133371\cr
 7 & 0.703\ln S+0.839 & 0.691\ln S+0.822 &  4.1481149\cr
 8 & 0.639\ln S+0.852 & 0.632\ln S+0.834 &  4.7833861\cr
 9 & 0.592\ln S+0.861 & 0.587\ln S+0.845 &  5.4189757\cr
10 & 0.555\ln S+0.869 & 0.552\ln S+0.854 &  6.0547828\cr
20 & 0.397\ln S+0.905 & 0.397\ln S+0.901 & 12.4174426\cr
\noalign{\hrule}
}

оТМЕТИМ ИНТЕРЕСНОЕ СВОЙСТВО ЭТИХ ЧИСЕЛ---ИХ ОТНОСИТЕЛЬНЫЕ ВЕЛИЧИНЫ ЯВЛЯЮТСЯ
ТАКЖЕ И ДЛИНАМИ ДИАГОНАЛЕЙ ПРАВИЛЬНОГО $(2T-1)\hbox{-УГОЛЬНИКА}$. нАПРИМЕР,
ПЯТЬ ДИАГОНАЛЕЙ ОДИННАДЦАТИУГОЛЬНИКА НА РИС.~73 ИМЕЮТ ОТНОСИТЕЛЬНЫЕ ДЛИНЫ,
ОЧЕНЬ БЛИЗКИЕ К~190, 175, 146, 105 И~55! мЫ ДОКАЖЕМ ЭТОТ ЗАМЕЧАТЕЛЬНЫЙ ФАКТ
\picture{рИС.~73. гЕОМЕТРИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ КАСКАДНЫХ ЧИСЕЛ.}
ПОЗДНЕЕ В ЭТОМ ПУНКТЕ, А ТАКЖЕ УВИДИМ, ЧТО ОТНОСИТЕЛЬНЫЕ ВРЕМЕНА,
ЗАТРАЧИВАЕМЫЕ НА $(T-1)\hbox{-ПУТЕВОЕ}$ СЛИЯНИЕ, $(T-2)\hbox{-ПУТЕВОЕ}$
СЛИЯНИЕ,~\dots, ОДНОПУТЕВОЕ СЛИЯНИЕ, ПРИБЛИЗИТЕЛЬНО ПРОПОРЦИОНАЛЬНЫ
\emph{КВАДРАТАМ} ДЛИН ЭТИХ ДИАГОНАЛЕЙ.

\section *нАЧАЛЬНОЕ РАСПРЕДЕЛЕНИЕ ОТРЕЗКОВ. еСЛИ ЧИСЛО НАЧАЛЬНЫХ
ОТРЕЗКОВ В ДЕЙСТВИТЕЛЬНОСТИ НЕ ЕСТЬ ЧИСЛО фИБОНАЧЧИ, МЫ МОЖЕМ,
КАК ОБЫЧНО, ВСТАВИТЬ ФИКТИВНЫЕ ОТРЕЗКИ. пОВЕРХНОСТНЫЙ АНАЛИЗ СИТУАЦИИ
ПОКАЗЫВАЕТ, ЧТО МЕТОД ПРИПИСЫВАНИЯ ФИКТИВНЫХ ОТРЕЗКОВ НЕСУЩЕСТВЕН, ТАК
КАК КАСКАДНОЕ СЛИЯНИЕ ВСЕГДА ОСУЩЕСТВЛЯЕТ
%%345
ПОЛНЫЕ ПРОХОДЫ; ЕСЛИ ИМЕЕТСЯ 190~НАЧАЛЬНЫХ ОТРЕЗКОВ, ТО КАЖДАЯ ЗАПИСЬ
ОБРАБАТЫВАЕТСЯ ПЯТЬ РАЗ, КАК В ПРИВЕДЕННОМ ВЫШЕ ПРИМЕРЕ, НО ЕСЛИ ИМЕЕТСЯ
191~ОТРЕЗОК, ТО, ОЧЕВИДНО, СЛЕДУЕТ УВЕЛИЧИТЬ УРОВЕНЬ, И ТЕПЕРЬ КАЖДАЯ
ЗАПИСЬ БУДЕТ ОБРАБАТЫВАТЬСЯ ШЕСТЬ РАЗ. к СЧАСТЬЮ, В ДЕЙСТВИТЕЛЬНОСТИ МОЖНО
ИЗБЕЖАТЬ ТАКОГО РЕЗКОГО СКАЧКА. дЭВИД~э.~фЕРГЮСОН НАШЕЛ СПОСОБ ТАК
РАСПРЕДЕЛИТЬ НАЧАЛЬНЫЕ ОТРЕЗКИ, ЧТО МНОГИЕ ОПЕРАЦИИ ВО ВРЕМЯ ПЕРВОЙ
\picture{
  рИС.~74. эФФЕКТИВНОСТЬ КАСКАДНОГО СЛИЯНИЯ С РАСПРЕДЕЛЕНИЕМ
  ПО АЛГОРИТМУ~D.
}
ФАЗЫ СЛИЯНИЯ СВОДЯТСЯ К КОПИРОВАНИЮ СОДЕРЖИМОГО ЛЕНТЫ. еСЛИ ОБОЙТИ ТАКИЕ
КОПИРОВАНИЯ (ПРОСТО ИЗМЕНИВ "ЛОГИЧЕСКИЕ" НОМЕРА ЛЕНТОЧНЫХ УСТРОЙСТВ ПО
ОТНОШЕНИЮ К "ФИЗИЧЕСКИМ" НОМЕРАМ, КАК В АЛГОРИТМЕ~5.4.2D), ТО ПОЛУЧИМ
ОТНОСИТЕЛЬНО ПЛАВНЫЙ ПЕРЕХОД С УРОВНЯ НА УРОВЕНЬ, КАК ИЗОБРАЖЕНО НА РИС.~74.

пРЕДПОЛОЖИМ, ЧТО $(a, b, c, d, e)$, ГДЕ~$a\ge b \ge c \ge d \ge e$---ТОЧНОЕ
РАСПРЕДЕЛЕНИЕ. пЕРЕОПРЕДЕЛИВ СООТВЕТСТВИЕ МЕЖДУ ЛОГИЧЕСКИМИ
И ФИЗИЧЕСКИМИ ЛЕНТОЧНЫМИ УСТРОЙСТВАМИ, МЫ МОЖЕМ ПРЕДСТАВИТЬ, ЧТО РЕАЛЬНОЕ
РАСПРЕДЕЛЕНИЕ---ЭТО~$(e, d, c, b, a)$,
%%346
Т.~Е.~$a$~ОТРЕЗКОВ НА~T5, $b$~НА~т4 И~Т.~Д. сЛЕДУЮЩЕЕ ТОЧНОЕ
РАСПРЕДЕЛЕНИЕ---ЭТО $(a+b+c+d+e,  a+b+c+d, a+b+c, a+b, a)$;
И ЕСЛИ ВВОД ИСЧЕРПЫВАЕТСЯ ПРЕЖДЕ, ЧЕМ МЫ ДОСТИГАЕМ ЭТОГО СЛЕДУЮЩЕГО
УРОВНЯ, ТО БУДЕМ СЧИТАТЬ, ЧТО ЛЕНТЫ СОДЕРЖАТ
СООТВЕТСТВЕННО~$(D_1, D_2, D_3, D_4, D_5)$ ФИКТИВНЫХ ОТРЕЗКОВ, ГДЕ
$$
\displaynarrow{
D_1 \le a+b+c+d,\quad D_1 \le a+b+c,\quad D_3\le a+b,\cr
D_4 \le a,\quad D_5=0;\qquad D_1\ge D_2 \ge D_3 \ge D_4 \ge D_5.\cr
}
\eqno(2)
$$

мЫ ВОЛЬНЫ ПРЕДСТАВЛЯТЬ СЕБЕ, ЧТО ЭТИ ФИКТИВНЫЕ ОТРЕЗКИ ПОЯВЛЯЮТСЯ НА
ЛЕНТАХ В ЛЮБОМ УДОБНОМ МЕСТЕ. пРЕДПОЛАГАЕТСЯ, ЧТО ПЕРВЫЙ ПРОХОД СЛИЯНИЯ
ДАСТ $a$~ОТРЕЗКОВ ПОСРЕДСТВОМ ПЯТИПУТЕВОГО СЛИЯНИЯ, ЗАТЕМ $b$~ОТРЕЗКОВ
ПОСРЕДСТВОМ ЧЕТЫРЕХПУТЕВОГО И~Т.~Д. нАША ЦЕЛЬ СОСТОИТ В РАСПОЛОЖЕНИИ
ФИКТИВНЫХ ОТРЕЗКОВ ТАКИМ ОБРАЗОМ, ЧТОБЫ ЗАМЕНИТЬ СЛИЯНИЕ КОПИРОВАНИЕМ.
уДОБНО ВЫПОЛНЯТЬ ПЕРВЫЙ ПРОХОД СЛИЯНИЯ СЛЕДУЮЩИМ ОБРАЗОМ:

1.~еСЛИ~$D_4=a$, ТО ВЫЧЕСТЬ~$a$ ИЗ ВСЕХ~$D_1$, $D_2$, $D_3$, $D_4$ И
ЗАЯВИТЬ, ЧТО~T5---РЕЗУЛЬТАТ СЛИЯНИЯ. еСЛИ~$D_4<a$, ТО СЛИТЬ $a$~ОТРЕЗКОВ С
ЛЕНТ~T1 ПО~T5, ИСПОЛЬЗУЯ МИНИМАЛЬНО ВОЗМОЖНОЕ ЧИСЛО ФИКТИВНЫХ ОТРЕЗКОВ
НА ЛЕНТАХ~T1--T5 ТАК, ЧТОБЫ НОВЫЕ ЗНАЧЕНИЯ~$D_1$, $D_2$, $D_3$, $D_4$
УДОВЛЕТВОРЯЛИ СООТНОШЕНИЯМ
$$
\displaynarrow{
D_1\le b+c+d,\quad D_2\le b+c,\quad D_3\le b,\cr
D_4=0;\qquad  D_1\ge D_2\ge D_3\ge D_4.\cr
}
\eqno(3)
$$
тАКИМ ОБРАЗОМ, ЕСЛИ~$D_2$ БЫЛО ПЕРВОНАЧАЛЬНО~$\le b+c$, ТО МЫ
НЕ ИСПОЛЬЗУЕМ НИ ОДНОГО ФИКТИВНОГО ОТРЕЗКА С ЭТОЙ ЛЕНТЫ НА ДАННОМ ШАГЕ; В
ТО ЖЕ ВРЕМЯ, ЕСЛИ~$b+c<D_2\le a+b+c$, МЫ ИСПОЛЬЗУЕМ РОВНО~$D_2-b-c$
ФИКТИВНЫХ ОТРЕЗКОВ.

2.~(эТОТ ШАГ АНАЛОГИЧЕН ШАГУ~1, НО С НЕКОТОРЫМ "СДВИГОМ".) еСЛИ~$D_3=b$,
ТО ВЫЧЕСТЬ~$b$ ИЗ ВСЕХ~$D_1$, $D_2$, $D_3$ И ЗАЯВИТЬ, ЧТО~T4---РЕЗУЛЬТАТ
СЛИЯНИЯ. еСЛИ~$D_3<b$, ТО СЛИТЬ $b$~ОТРЕЗКОВ С ЛЕНТ~T1--T4, УМЕНЬШАЯ, ЕСЛИ
НЕОБХОДИМО, ЧИСЛО ФИКТИВНЫХ ОТРЕЗКОВ, ЧТОБЫ ДОСТИЧЬ
$$
D_1\le b+c,\quad D_2\le b,\quad D_3=0;\qquad D_1\ge D_2\ge D_3.
$$

3.~и ТАК ДАЛЕЕ.

мЕТОД фЕРГЮСОНА РАСПРЕДЕЛЕНИЯ ОТРЕЗКОВ ПО ЛЕНТАМ МОЖНО ПРОИЛЛЮСТРИРОВАТЬ,
РАССМОТРЕВ ПРОЦЕСС ПЕРЕХОДА С УРОВНЯ~3 НА УРОВЕНЬ~4 В~(1). дОПУСТИМ, ЧТО
"ЛОГИЧЕСКИЕ" ЛЕНТЫ (T1,~\dots, T5) СОДЕРЖАЛИ СООТВЕТСТВЕННО
$(5, 9, 12, 14, 15)$~ОТРЕЗКОВ И ЧТО МЫ ХОТИМ ДОВЕСТИ ЭТО В КОНЕЧНОМ ИТОГЕ
ДО~$(55, 50, 41, 29, 15)$. эТА ПРОЦЕДУРА МОЖЕТ БЫТЬ КРАТКО ЗАПИСАНА ТАК:
%%347
\ctable{
$#$\hfill&&\hfill\bskip$#$\bskip\hfill\cr
 & \hbox{дОБАВИТЬ} &\hbox{дОБАВИТЬ} &\hbox{дОБАВИТЬ} &\hbox{дОБАВИТЬ} &\hbox{дОБАВИТЬ} &\hbox{сЭКОНОМЛЕННАЯ}\cr
\hbox{шАГ} &\hbox{К T1} &\hbox{К T2} &\hbox{К T3} &\hbox{К T4} &\hbox{К T5} &\hbox{ВЕЛИЧИНА}\cr
(1, 1)& 9 &  0 &  0 &  0 &  0 & 15+14+12+5\cr
(2, 2)& 3 & 12 &  0 &  0 &  0 &  15+14+9+5\cr
(2, 1)& 9 &  0 &  0 &  0 &  0 &    15+14+5\cr
(3, 3)& 2 &  2 & 14 &  0 &  0 &    15+12+5\cr
(3, 2)& 3 & 12 &  0 &  0 &  0 &     15+9+5\cr
(3, 1)& 9 &  0 &  0 &  0 &  0 &       15+5\cr
(4, 4)& 1 &  1 &  1 & 15 &  0 &       14+5\cr
(4, 3)& 2 &  2 & 14 &  0 &  0 &       12+5\cr
(4, 2)& 3 & 12 &  0 &  0 &  0 &        9+5\cr
(4, 1)& 9 &  0 &  0 &  0 &  0 &          5\cr
}
сНАЧАЛА ПОМЕЩАЕМ ДЕВЯТЬ ОТРЕЗКОВ НА~T1, ЗАТЕМ $(3, 12)$---НА~T1 И~T2 И~Т.~Д.
еСЛИ ВВОД ИСЧЕРПАЕТСЯ, СКАЖЕМ, ВО ВРЕМЯ ШАГА~$(3, 2)$, ТО "СЭКОНОМЛЕННАЯ
ВЕЛИЧИНА" СОСТАВЛЯЕТ~$15+9+5$. эТО ОЗНАЧАЕТ, ЧТО МЫ ИЗБЕГАЕМ ПЯТИПУТЕВОГО
СЛИЯНИЯ 15~ОТРЕЗКОВ,  ДВУХПУТЕВОГО СЛИЯНИЯ 9~ОТРЕЗКОВ И ОДНОПУТЕВОГО
СЛИЯНИЯ 5~ОТРЕЗКОВ ПОСРЕДСТВОМ ПРИСВОЕНИЯ ФИКТИВНЫХ ОТРЕЗКОВ.
дРУГИМИ СЛОВАМИ, $15+9+5$ ОТРЕЗКОВ, ПРИСУТСТВУЮЩИХ НА УРОВНЕ~3,
НЕ ОБРАБАТЫВАЮТСЯ В ТЕЧЕНИЕ ПЕРВОЙ ФАЗЫ СЛИЯНИЯ.

сЛЕДУЮЩИЙ АЛГОРИТМ ДЕТАЛЬНО ОПИСЫВАЕТ ЭТОТ ПРОЦЕСС.

\alg C.(сОРТИРОВКА КАСКАДНЫМ СЛИЯНИЕМ СО СПЕЦИАЛЬНЫМ РАСПРЕДЕЛЕНИЕМ.) эТОТ
АЛГОРИТМ РАСПРЕДЕЛЯЕТ НАЧАЛЬНЫЕ ОТРЕЗКИ ПО ЛЕНТАМ ОТРЕЗОК ЗА ОТРЕЗКОМ,
ПОКА ЗАПАС НАЧАЛЬНЫХ ОТРЕЗКОВ НЕ ИСЧЕРПАЕТСЯ. зАТЕМ ОН ОПРЕДЕЛЯЕТ, КАК
СЛЕДУЕТ СЛИВАТЬ ЛЕНТЫ, ПРЕДПОЛАГАЯ, ЧТО ИМЕЕТСЯ $T\ge 3$~ЛЕНТОПРОТЯЖНЫХ
УСТРОЙСТВ, ПРИ ЭТОМ ИСПОЛЬЗУЕТСЯ САМОЕ БОЛЬШЕЕ
$(T-1)\hbox{-ПУТЕВОЕ}$~СЛИЯНИЕ И
НЕНУЖНЫЕ ОДНОПУТЕВЫЕ СЛИЯНИЯ УСТРАНЯЮТСЯ. лЕНТА~$T$ МОЖЕТ
БЫТЬ ИСПОЛЬЗОВАНА ДЛЯ ХРАНЕНИЯ ВВОДА, ТАК КАК НА НЕЕ НЕ ПОПАДАЕТ НИ ОДИН
НАЧАЛЬНЫЙ ОТРЕЗОК. аЛГОРИТМ РАБОТАЕТ СО СЛЕДУЮЩИМИ МАССИВАМИ:
{\let\mypar=\par\ctable{
$#$,\bskip\hfill&$#$:\bskip\hfill&
\vtop{\parindent=0pt \hsize=13cm #\mypar}\cr
|A|[j]    & 1 \le j \le T &
   пОСЛЕДНЕЕ ТОЧНОЕ КАСКАДНОЕ РАСПРЕДЕЛЕНИЕ, КОТОРОЕ БЫЛО ДОСТИГНУТО. \cr
|AA|[j]   & 1 \le j \le T &
   тОЧНОЕ КАСКАДНОЕ РАСПРЕДЕЛЕНИЕ, К КОТОРОМУ МЫ СТРЕМИМСЯ. \cr
|D|[j]    & 1 \le j \le T &
   чИСЛО ФИКТИВНЫХ ОТРЕЗКОВ, ПРЕДПОЛАГАЕМЫХ ПРИСУТСТВУЮЩИМИ НА ЛОГИЧЕСКОМ
   ЛЕНТОПРОТЯЖНОМ УСТРОЙСТВЕ С НОМЕРОМ~$j$. \cr
|M|[j]    & 1 \le j \le T &
   мАКСИМАЛЬНОЕ ЧИСЛО ФИКТИВНЫХ ОТРЕЗКОВ, КОТОРОЕ ЖЕЛАТЕЛЬНО ИМЕТЬ НА
   ЛОГИЧЕСКОМ ЛЕНТОПРОТЯЖНОМ УСТРОЙСТВЕ С НОМЕРОМ~$j$. \cr
|TAPE|[j] & 1 \le j \le T &
   нОМЕР ФИЗИЧЕСКОГО ЛЕНТОПРОТЯЖНОГО УСТРОЙСТВА, СООТВЕТСТВУЮЩЕГО
   ЛОГИЧЕСКОМУ ЛЕНТОПРОТЯЖНОМУ УСТРОЙСТВУ С НОМЕРОМ~$j$.\cr
}}
%%348
\st[нАЧАЛЬНАЯ УСТАНОВКА.] уСТАНОВИТЬ $|A|[k]\asg |AA|[k]\asg |D|[k]\asg 0$
ПРИ~$2\le k \le T$; УСТАНОВИТЬ $|A|[1]\asg 0$, $|AA|[1]\asg 1$,
$|D|[1]\asg 1$; УСТАНОВИТЬ~$|TAPE|[k]\asg k$ ПРИ~$1\le k \le T$. нАКОНЕЦ,
УСТАНОВИТЬ~$i\asg T-2$, $j\asg 1$, $k\asg 1$, $l\asg 0$, $m\asg 1$ И
ПЕРЕЙТИ К ШАГУ~\stp{5} (ЭТИ МАНЕВРЫ ЯВЛЯЮТСЯ ОДНИМ ИЗ СПОСОБОВ НАЧАТЬ
РАБОТУ НЕПОСРЕДСТВЕННО ВО ВНУТРЕННЕМ ЦИКЛЕ С СООТВЕТСТВУЮЩЕЙ УСТАНОВКОЙ
УПРАВЛЯЮЩИХ ПЕРЕМЕННЫХ).

\st[нАЧАТЬ НОВЫЙ УРОВЕНЬ.] (мЫ ТОЛЬКО ЧТО ПОЛУЧИЛИ ТОЧНОЕ РАСПРЕДЕЛЕНИЕ.
нО ТАК КАК ЕЩЕ ИМЕЮТСЯ ИСХОДНЫЕ ДАННЫЕ, ТО НЕОБХОДИМО ПОДГОТОВИТЬСЯ К
СЛЕДУЮЩЕМУ УРОВНЮ.) уВЕЛИЧИТЬ~$l$ НА~1. уСТАНОВИТЬ~$|A|[k]\asg |AA|[k]$
ПРИ~$1\le k \le T$, ЗАТЕМ УСТАНОВИТЬ~$|AA|[T-k]\asg |AA|[T-k+1]+|A|[k]$
ПРИ~$k=1$, 2,~\dots, $T-1$ (В ТАКОМ ПОРЯДКЕ). уСТАНОВИТЬ $(|TAPE|[1],
|TAPE|[2],~\ldots, |TAPE|[T-1])\asg (|TAPE|[T-1],~\ldots, |TAPE|[2],
|TAPE|[1])$ И УСТАНОВИТЬ~$|D|[k]\asg |AA|[k+1]$ ПРИ~$1\le k < T$.
нАКОНЕЦ, УСТАНОВИТЬ~$i\asg 1$.

\st[нАЧАТЬ ПОДУРОВЕНЬ~$i$.] уСТАНОВИТЬ~$j\asg i$. (пЕРЕМЕННЫЕ~$i$
И~$j$ ПРЕДСТАВЛЯЮТ "ШАГ~$(i,j)$" В ТАБЛИЦЕ, ИЛЛЮСТРИРУЮЩЕЙ МЕТОД фЕРГЮСОНА.)

\st[нАЧАТЬ ШАГ~$(i, j)$.] уСТАНОВИТЬ~$k\asg j$ И~$m\asg
|A|[T-j-1]$. еСЛИ~$m=0$ И~$i=j$, ТО УСТАНОВИТЬ~$i\asg T-2$ И
ВЕРНУТЬСЯ К~\stp{3}; ЕСЛИ~$m=0$ И~$i\ne j$, ВЕРНУТЬСЯ К~\stp{2}.
(пЕРЕМЕННАЯ~$m$ ПРЕДСТАВЛЯЕТ СОБОЙ ЧИСЛО ОТРЕЗКОВ, КОТОРОЕ ДОЛЖНО
БЫТЬ ЗАПИСАНО НА ЛЕНТУ~$|TAPE|[k]$; $m$~БЫВАЕТ РАВНО~0, ТОЛЬКО ЕСЛИ~$l=1$.)

\st[вВЕСТИ НА ЛЕНТУ~$|TAPE|[k]$.] зАПИСАТЬ ОДИН ОТРЕЗОК НА
ЛЕНТУ НОМЕР~$|TAPE|[k]$ И УМЕНЬШИТЬ~$|D|[k]$ НА~1. зАТЕМ, ЕСЛИ
ВВОД ИСЧЕРПАН, ПЕРЕМОТАТЬ ВСЕ ЛЕНТЫ И ПЕРЕЙТИ К ШАГУ~\stp{7}.

\st[пРОДВИЖЕНИЕ.] уМЕНЬШИТЬ~$m$ НА~1. еСЛИ~$m>0$, ВЕРНУТЬСЯ К ШАГУ~\stp{5}.
 в ПРОТИВНОМ СЛУЧАЕ УМЕНЬШИТЬ~$k$ НА~1; ЕСЛИ~$k>0$, УСТАНОВИТЬ~$m\asg
|A|[T-j-1]-|A|[T-j]$ И ВЕРНУТЬСЯ К~\stp{5}, ЕСЛИ~$m>0$. в ПРОТИВНОМ СЛУЧАЕ
УМЕНЬШИТЬ~$j$ НА~1;
ЕСЛИ~$j>0$, ПЕРЕЙТИ К ШАГУ~\stp{4}. в ПРОТИВНОМ СЛУЧАЕ УВЕЛИЧИТЬ~$i$
НА~1; ЕСЛИ~$i<T<1$, ВЕРНУТЬСЯ К ШАГУ~\stp{3}. в ПРОТИВНОМ СЛУЧАЕ ПЕРЕЙТИ
К~\stp{2}.

\st[пОДГОТОВКА К СЛИЯНИЮ.] (к ЭТОМУ МОМЕНТУ НАЧАЛЬНОЕ РАСПРЕДЕЛЕНИЕ
ЗАВЕРШЕНО, И ТАБЛИЦЫ~|A|, |AA|, |D| И~|TAPE| ОПИСЫВАЮТ СОСТОЯНИЕ ВСЕХ
ЛЕНТ В ДАННЫЙ МОМЕНТ.) уСТАНОВИТЬ~$|M|[k]\asg|AA|[k+1]$ ПРИ~$1\le k < T$ И
УСТАНОВИТЬ~$|FIRST|\asg 1$. (пЕРЕМЕННАЯ~|FIRST| ПРИНИМАЕТ НЕНУЛЕВОЕ
ЗНАЧЕНИЕ ТОЛЬКО ВО ВРЕМЯ ПЕРВОГО ПРОХОДА СЛИЯНИЯ.)

\st[кАСКАД.] еСЛИ~$l=0$, ОСТАНОВИТЬСЯ; СОРТИРОВКА ЗАВЕРШЕНА, ВЫВОД
НАХОДИТСЯ НА~$|TAPE|[1]$. в ПРОТИВНОМ СЛУЧАЕ ПРИ~$p=T-1$, $T-2$,~\dots, 1
(В ТАКОМ ПОРЯДКЕ) ВЫПОЛНЯТЬ $p\hbox{-ПУТЕВОЕ}$ СЛИЯНИЕ С
ЛЕНТ~$|TAPE|[1]$,~\dots, $|TAPE|[p]$ НА~$|TAPE|[p+1]$ СЛЕДУЮЩИМ ОБРАЗОМ:
%% 349

еСЛИ~$p=1$, ТО МОДЕЛИРОВАТЬ ОДНОПУТЕВОЕ СЛИЯНИЕ
ОБЫЧНОЙ ПЕРЕМОТКОЙ~$|TAPE|[2]$ И ЗАМЕНОЙ~$|TAPE|[1]\xchg |TAPE|[2]$. в
ПРОТИВНОМ СЛУЧАЕ, ЕСЛИ~$|FIRST|=1$ И~$|D|[p-1]=|M|[p-1]$, ТО МОДЕЛИРОВАТЬ
$p\hbox{-ПУТЕВОЕ}$ СЛИЯНИЕ, ПРОСТО ПОМЕНЯВ $|TAPE|[p]\xchg |TAPE|[p+1]$,
ПЕРЕМОТАВ~$|TAPE|[p]$ И ВЫЧТЯ~$M[p-1]$ ИЗ КАЖДОГО~$|D|[1]$,~\dots,
$|D|[p-1]$, $|M|[1]$,~\dots, $|M|[p-1]$. в ПРОТИВНОМ СЛУЧАЕ
ВЫЧЕСТЬ~$|M|[p-1]$ ИЗ ВСЕХ~$|M|[1]$,~\dots, $|M|[p-1]$. зАТЕМ СЛИТЬ ПО
ОДНОМУ ОТРЕЗКУ С КАЖДОЙ~$|TAPE|[j]$, ТАКОЙ, ЧТО~$1\le j \le p$
И~$|D|[j]\le |M|[j]$; ВЫЧЕСТЬ ЕДИНИЦУ ИЗ КАЖДОГО~$|D|[j]$, ТАКОГО,
ЧТО~$1\le j \le p$ И~$|D|[j]>|M|[j]$, И ПОМЕСТИТЬ ВЫВОДНОЙ ОТРЕЗОК
НА~$|TAPE|[p+1]$. пРОДОЛЖАТЬ РАБОТУ, ПОКА $|TAPE|[p]$ НЕ СТАНЕТ ПУСТОЙ.
зАТЕМ ПЕРЕМОТАТЬ~$|TAPE|[p]$ И~$|TAPE|[p+1]$.

\st[оПУСТИТЬСЯ НА ОДИН УРОВЕНЬ.] уМЕНЬШИТЬ~$l$ НА~1,
УСТАНОВИТЬ~$|FIRST|\asg 0$, УСТАНОВИТЬ
$(|TAPE|[1],~\ldots, |TAPE|[T])\asg (|TAPE|[T],~\ldots, |TAPE|[1])$. (к
ЭТОМУ МОМЕНТУ ВСЕ~|D| И~|M|---НУЛИ И ТАКОВЫМИ ОСТАНУТСЯ.) вЕРНУТЬСЯ К~\stp{8}.
\algend

шАГИ~C1--C6 ЭТОГО АЛГОРИТМА ВЫПОЛНЯЮТ РАСПРЕДЕЛЕНИЕ, ШАГИ~C7--C9 ВЫПОЛНЯЮТ
СЛИЯНИЕ; ЭТИ ДВЕ ЧАСТИ СОВЕРШЕННО НЕЗАВИСИМЫ ОДНА ОТ ДРУГОЙ, И МОЖНО БЫЛО
БЫ ХРАНИТЬ~$|M|[k]$ И~$|AA|[k+1]$ В ОДНИХ И ТЕХ ЖЕ ЯЧЕЙКАХ ПАМЯТИ.
\picture{рИС.~75. кАСКАДНОЕ СЛИЯНИЕ СО СПЕЦИАЛЬНЫМ РАСПРЕДЕЛЕНИЕМ.}
\section *аНАЛИЗ КАСКАДНОГО СЛИЯНИЯ. кАСКАДНОЕ СЛИЯНИЕ ПОДДАЕТСЯ АНАЛИЗУ
С БОЛЬШИМ ТРУДОМ, ЧЕМ МНОГОФАЗНОЕ. нО ЭТОТ АНАЛИЗ ОСОБЕННО ИНТЕРЕСЕН,
ПОСКОЛЬКУ СОДЕРЖИТ МНОГО ЗАМЕЧАТЕЛЬНЫХ ФОРМУЛ. нАСТОЯТЕЛЬНО РЕКОМЕНДУЕМ
ЧИТАТЕЛЯМ, ИНТЕРЕСУЮЩИМСЯ ДИСКРЕТНОЙ МАТЕМАТИКОЙ, САМОСТОЯТЕЛЬНО
ПРОАНАЛИЗИРОВАТЬ КАСКАДНОЕ РАСПРЕДЕЛЕНИЕ, ПРЕЖДЕ ЧЕМ ЧИТАТЬ ДАЛЬШЕ, ВЕДЬ ЧИСЛА
%%350
ИМЕЮТ ТАК МНОГО НЕОБЫЧНЫХ СВОЙСТВ, ОТКРЫВАТЬ КОТОРЫЕ---ОДНО УДОВОЛЬСТВИЕ! мЫ
ОБСУДИМ ЗДЕСЬ ЛИШЬ ОДИН ИЗ МНОГИХ ПОДХОДОВ, ОБРАЩАЯ ОСОБОЕ ВНИМАНИЕ НА
МЕТОДЫ ПОЛУЧЕНИЯ РЕЗУЛЬТАТОВ.

дЛЯ УДОБСТВА РАССМОТРИМ СЛУЧАЙ ШЕСТИ ЛЕНТ. пРИ ЭТОМ БУДЕМ СТАРАТЬСЯ
ПОЛУЧИТЬ ФОРМУЛЫ, КОТОРЫЕ ОБОБЩАЮТСЯ НА СЛУЧАЙ ЛЮБОГО~$T$. сООТНОШЕНИЯ~(1)
ПРИВОДЯТ К ПЕРВОЙ ОСНОВНОЙ СИСТЕМЕ:
$$
\eqalignter{
a_n &= a_n &=\perm{0}{0}a_n,\cr
b_n &= a_n-e_{n-1}=a_n-a_{n-2} &=\perm{1}{0}a_n-\perm{2}{2}a_{n-2},\cr
c_n &= b_n-d_{n-1}=b_n-a_{n-2}-b_{n-2} &=\perm{2}{0}a_n-\perm{3}{2}a_{n-2}+\perm{4}{4}a_{n-4},\cr
d_n &= c_n-c_{n-1}=c_n-a_{n-2}-b_{n-2}-c_{n-2} &=\perm{3}{0}a_n-\perm{4}{2}a_{n-2}+\perm{5}{4}a_{n-4}-\perm{6}{6}a_{n-6},\cr
e_n &= d_n-b_{n-1}=d_n-a_{n-2}-b_{n-2}-c_{n-2}-d_{n-2} &=\perm{4}{0}a_n-\perm{5}{2}a_{n-2}+\perm{6}{4}a_{n-4}-\perm{7}{6}a_{n-6}+\perm{8}{8}a_{n-8}.\cr
}
\eqno(4)
$$
оБОЗНАЧИМ~$A(z)=\sum_{n\ge0} a_n z^n$,~\dots, $E(z)=\sum_{n\ge0}e_n z^n$ И
ОПРЕДЕЛИМ МНОГОЧЛЕНЫ
$$
\eqalignno{
q_m(z)&=\perm{m}{0}-\perm{m+1}{2}z^2+\perm{m+2}{4}z^4-\cdots=\cr
      &=\sum_{k\ge 0}\perm{m+k}{2k}(-1)^k z^{2k}
        = \sum_{0\le k \le m}\perm{2m-k}{k}(-1)^{m-k} z^{2m-2k}. & (5)\cr
}
$$
рЕЗУЛЬТАТ~(4) КРАТКО МОЖНО ИСТОЛКОВАТЬ ТАК,
ЧТО~$B(z)-q_1(z)\times A(z)$,~\dots, $E(z)-q_4(z)A(z)$ СВОДЯТСЯ К
КОНЕЧНЫМ СУММАМ, СООТВЕТСТВУЮЩИМ
ГРАНИЧНЫМ УСЛОВИЯМ, А ИМЕННО ЗНАЧЕНИЯМ~$a_{-1}$, $a_{-2}$, $a_{-3}$,~\dots,
КОТОРЫЕ ПОЯВЛЯЮТСЯ В~(4) (ПРИ НЕБОЛЬШИХ~$n$), НО НЕ В~$A(z)$. чТОБЫ
ПОЛУЧИТЬ ПОДХОДЯЩИЕ ГРАНИЧНЫЕ УСЛОВИЯ, ПРИМЕНИМ РЕКУРРЕНТНОЕ СООТНОШЕНИЕ
В ОБРАТНУЮ СТОРОНУ ДЛЯ ОТРИЦАТЕЛЬНЫХ УРОВНЕЙ ДО УРОВНЯ~$-8$:
\ctable{
\hfill$#$\bskip&&\hfill\bskip$#$\bskip\cr
\hfill n & \hfill a_n & \hfill b_n & \hfill c_n & \hfill d_n & \hfill e_n \cr
 0 &  1 &   0 &  0 &   0 &  0\cr
-1 &  0 &   0 &  0 &   0 &  1\cr
-2 &  1 &  -1 &  0 &   0 &  0\cr
-3 &  0 &   0 &  0 &  -1 &  2\cr
-4 &  2 &  -3 &  1 &   0 &  0\cr
-5 &  0 &   0 &  1 &  -4 &  5\cr
-6 &  5 &  -9 &  5 &  -1 &  0\cr
-7 &  0 &  -1 &  6 & -14 & 14\cr
-8 & 14 & -28 & 20 &  -7 &  1\cr
}
(дЛЯ СЕМИ ЛЕНТ ТАБЛИЦА БЫЛА БЫ АНАЛОГИЧНОЙ, ОДНАКО СТРОКИ С НЕЧЕТНЫМИ~$n$
БЫЛИ БЫ СДВИНУТЫ ВПРАВО НА ОДИН ЭЛЕМЕНТ.) тАЙНА
ПОСЛЕДОВАТЕЛЬНОСТИ~$a_0$, $a_{-2}$, $a_{-4},~\ldots=1, 1, 2, 5, 14,~\ldots$
МГНОВЕННО РАСКРЫВАЕТСЯ СПЕЦИАЛИСТОМ ПО ИНФОРМАТИКЕ, ТАК КАК
%%351
ЭТА ПОСЛЕДОВАТЕЛЬНОСТЬ ВСТРЕЧАЕТСЯ В СВЯЗИ С ОЧЕНЬ МНОГИМИ РЕКУРРЕНТНЫМИ
АЛГОРИТМАМИ (НАПРИМЕР, В УПР.~2.2.1-4 И ФОРМУЛЕ~2.3.4.4-13)). иТАК, МЫ
ПРЕДПОЛАГАЕМ, ЧТО В СЛУЧАЕ $T$~ЛЕНТ
$$
\eqalignrem{
a_{-2n}&=\perm{2n}{n}{1\over n+1} & ПРИ $0\le n \le T-2$; \cr
a_{-2n-1}&=0 & ПРИ $0\le n \le T-3$.\cr
}
\eqno(6)
$$
чТОБЫ ПРОВЕРИТЬ ПРАВИЛЬНОСТЬ ЭТОГО ПРЕДПОЛОЖЕНИЯ, ДОСТАТОЧНО ПОКАЗАТЬ,
ЧТО~(6) И~(4) ПРИВОДЯТ К ПРАВИЛЬНЫМ РЕЗУЛЬТАТАМ ДЛЯ УРОВНЕЙ~0 И~1. дЛЯ
УРОВНЯ~1 ЭТО ОЧЕВИДНО, А ДЛЯ УРОВНЯ~0 НАМ НАДО ПРОВЕРИТЬ, ЧТО
$$
\perm{m}{0}a_0-\perm{m+1}{2}a_{-2}+\perm{m+2}{4}a_{-4}-\perm{m+3}{6}a_{-6}+\cdots
=\sum_{k\ge0}\perm{m+k}{2k}\perm{2k}{k}{(-1)^k\over k+1}
=\delta_{m0}
\eqno(7)
$$
ДЛЯ~$0\le m \le T-2$. к СЧАСТЬЮ, ЭТУ СУММУ МОЖНО ВЫЧИСЛИТЬ СТАНДАРТНЫМИ
МЕТОДАМИ (ЭТО "ЗАДАЧА~2", ОДИН ИЗ ОСНОВНЫХ ПРИМЕРОВ В ТЕКСТЕ П.~4.2.6).

тЕПЕРЬ МОЖНО ВЫЧИСЛИТЬ КОЭФФИЦИЕНТЫ~$B(z)-q_1(z)A(z)$ И~Т.~Д. рАССМОТРИМ,
НАПРИМЕР, КОЭФФИЦИЕНТ ПРИ~$z^{2m}$ В~$D(z)-q_3(z)A(z)$. оН РАВЕН
$$
\eqalign{
\sum_{k\ge0}\perm{3+m+k}{2m+2k}(-1)^{m+k}a_{-2k}
&=\sum_{k\ge0}\perm{3+m+k}{2m+2k}\perm{2k}{k}{(-1)^{m+k}\over k+1}=\cr
&=(-1)^m\left(\perm{2+m}{2m-1}-\perm{3+m}{2m}\right)=\cr
&=(-1)^{m+1}\perm{2+m}{2m}\cr
}
$$
ИЗ РЕЗУЛЬТАТА "ЗАДАЧИ~3" В~П.~1.2.6. тАКИМ ОБРАЗОМ, МЫ ВЫВЕЛИ ФОРМУЛЫ
$$
\eqalign{
A(z) &=q_0(z)A(z);\cr
B(z) &=q_1(z)A(z)-q_0(z);\cr
C(z) &=q_2(z)A(z)-q_1(z);\cr
D(z) &=q_3(z)A(z)-q_2(z);\cr
E(z) &=q_4(z)A(z)-q_3(z).\cr
}
\eqno (8)
$$
кРОМЕ ТОГО, ИМЕЕМ~$e_{n+1}=a_n$; СЛЕДОВАТЕЛЬНО, $zA(z)=E(z)$ И
$$
A(z)=q_3(z)/(q_4(z)-z).
\eqno (9)
$$

пРОИЗВОДЯЩИЕ ФУНКЦИИ БЫЛИ ВЫРАЖЕНЫ ПРИ ПОМОЩИ $q\hbox{-МНОГОЧЛЕНОВ}$,
ПОЭТОМУ МЫ ХОТИМ ЛУЧШЕ ИЗУЧИТЬ~$q$. в ЭТОМ ОТНОШЕНИИ ПОЛЕЗНО УПР.~1.2.9-15,
ТАК КАК ОНО ДАЕТ ВЫРАЖЕНИЕ В ЗАМКНУТОМ
%%352
ВИДЕ, КОТОРОЕ МОЖЕТ БЫТЬ ЗАПИСАНО КАК
$$
q_m(z)={((\sqrt{4-z^2}+iz)/2)^{2m+1}+((\sqrt{4-z^2}-iz)/2)^{2m+1}
\over \sqrt{4-z^2}}
\eqno(10) $$
вСЕ УПРОЩАЕТСЯ, ЕСЛИ ТЕПЕРЬ ПОЛОЖИТЬ~$z=2 \sin\theta$:
$$
\eqalignno{
q_m(2\sin\theta)=&
{(\cos\theta+i\sin\theta)^{2m+1}+(\cos\theta-i\sin\theta)^{2m+1}\over 2\cos\theta}=\cr
&={\cos(2m+1)\theta\over \cos\theta}. & (11)\cr
}
$$
(эТО СОВПАДЕНИЕ ЗАСТАВЛЯЕТ ДУМАТЬ, ЧТО МНОГОЧЛЕНЫ~$q_m(z)$ ХОРОШО
ИЗВЕСТНЫ В МАТЕМАТИКЕ; И ДЕЙСТВИТЕЛЬНО, ВЗГЛЯНУВ В СООТВЕТСТВУЮЩИЕ
ТАБЛИЦЫ, ВИДИМ, ЧТО~$q_m(z)$, ПО СУЩЕСТВУ, МНОГОЧЛЕН чЕБЫШИВА ВТОРОГО РОДА,
 А ИМЕННО~$(-1)^m U_{2m}(z/2)$ В ОБЫЧНЫХ ОБОЗНАЧЕНИЯХ.)

тЕПЕРЬ МОЖНО ОПРЕДЕЛИТЬ КОРНИ ЗНАМЕНАТЕЛЯ В~(9):
$q_4(2\sin\theta)=2\sin\theta$ СВОДИТСЯ К
$$
\cos 9\theta = 2 \sin \theta \cos \theta = \sin 2\theta.
$$
рЕШЕНИЯ ЭТОГО СООТНОШЕНИЯ ПОЛУЧАЕМ, ЕСЛИ
ТОЛЬКО~$\pm9\theta=2\theta+\left(2n-{1\over2}\right)\pi$; ВСЕ
ТАКИЕ~$\theta$ ДАЮТ КОРНИ ЗНАМЕНАТЕЛЯ В~(9) ПРИ УСЛОВИИ,
ЧТО~$\cos\theta\ne 0$. (еСЛИ~$\cos\theta=0$, ТО~$q_m(\pm2)=\pm(2m+1)$,
НИКОГДА НЕ РАВНО~$\pm2$.) сЛЕДОВАТЕЛЬНО, ПОЛУЧАЕМ 8~РАЗЛИЧНЫХ КОРНЕЙ:
$$
\displaylines{
q_4(z)-z=0 \qquad \hbox{ ПРИ }  z=2\sin{-5\over 14}\pi,\quad
2\sin{-1 \over 14}\pi,\quad 2\sin{3 \over 14}\pi, \cr
2\sin{-7 \over 22}\pi,\quad 2\sin{-3 \over 22}\pi,\quad
2\sin{1 \over 22}\pi, \quad 2\sin{5 \over 22}\pi,\quad 2\sin{9 \over 22}\pi.\cr
}
$$
тАК КАК~$q_4(z)$---МНОГОЧЛЕН СТЕПЕНИ~8, МЫ УЧЛИ ВСЕ КОРНИ. пЕРВЫЕ ТРИ ИЗ
ЭТИХ ЗНАЧЕНИЙ ДАЮТ~$q_3(z)=0$, ТАК ЧТО~$q_3(z)$ И~$q_4(z)-z$  ИМЕЮТ ОБЩИМ
ДЕЛИТЕЛЕМ МНОГОЧЛЕН ТРЕТЬЕЙ СТЕПЕНИ. оСТАЛЬНЫЕ ПЯТЬ КОРНЕЙ УПРАВЛЯЮТ
АСИМПТОТИЧЕСКИМ ПОВЕДЕНИЕМ КОЭФФИЦИЕНТОВ~$A(z)$, ЕСЛИ РАЗЛОЖИТЬ~(9) В
ЭЛЕМЕНТАРНЫЕ ДРОБИ.

пЕРЕЙДЯ К РАССМОТРЕНИЮ ОБЩЕГО СЛУЧАЯ $T$~ЛЕНТ,
ПОЛОЖИМ~$\theta_k=(4k+1)\pi/(4T-2)$. пРОИЗВОДЯЩАЯ ФУНКЦИЯ~$A(z)$ ДЛЯ
$T\hbox{-ЛЕНТОЧНЫХ}$ КАСКАДНЫХ ЧИСЕЛ ПРИНИМАЕТ ВИД
$$
{4\over 2T-1}\sum_{-T/2<k<\floor{T/2}}{\cos^2\theta_k\over 1-z/(2\sin\theta_k)}
\eqno(12)
$$
(СМ.~УПР.~8); СЛЕДОВАТЕЛЬНО,
$$
a_n={4\over 2T-1}\sum_{-T/2<k<\floor{T/2}}\cos^2\theta_k \left({1\over 2\sin\theta_k}\right)^n.
\eqno(13)
$$
%% 353
сООТНОШЕНИЯ~(8) ПРИВОДЯТ ТЕПЕРЬ К АНАЛОГИЧНЫМ ФОРМУЛАМ:
$$
\eqalign{
b_n&={4\over 2T-1}\sum_{-T/2<k<\floor{T/2}}\cos\theta_k\cos3\theta_k\left({1\over 2\sin\theta_k}\right)^n;\cr
c_n&={4\over 2T-1}\sum_{-T/2<k<\floor{T/2}}\cos\theta_k\cos5\theta_k\left({1\over 2\sin\theta_k}\right)^n;\cr
d_n&={4\over 2T-1}\sum_{-T/2<k<\floor{T/2}}\cos\theta_k\cos7\theta_k\left({1\over 2\sin\theta_k}\right)^n\cr
}
\eqno(14)
$$
И~Т.~Д. в УПР.~9 ПОКАЗАНО, ЧТО ЭТИ УРАВНЕНИЯ СПРАВЕДЛИВЫ ДЛЯ ВСЕХ~$n\ge0$,
А НЕ ТОЛЬКО ДЛЯ БОЛЬШИХ~$n$. в КАЖДОЙ СУММЕ ЧЛЕН С~$k=0$ ЗНАЧИТЕЛЬНО
ПРЕВОСХОДИТ ВСЕ ОСТАЛЬНЫЕ, ОСОБЕННО ЕСЛИ~$n$ ДОСТАТОЧНО ВЕЛИКО;
СЛЕДОВАТЕЛЬНО, "ОТНОШЕНИЕ РОСТА" ЕСТЬ
$$
{1\over 2\sin\theta_0}={2\over\pi}T-{1\over\pi}+{\pi\over 48T}+O(T^{-2}).
\eqno(15)
$$

кАСКАДНАЯ СОРТИРОВКА ВПЕРВЫЕ БЫЛА ИССЛЕДОВАНА у.~к.~кАРТЕРОМ
[Proc.\ IFIP Congress (1962), 62--66], КОТОРЫЙ ПОЛУЧИЛ ЧИСЛЕННЫЕ РЕЗУЛЬТАТЫ
ДЛЯ НЕБОЛЬШИХ ЗНАЧЕНИЙ~$T$, И дЭВИДОМ фЕРГЮСОНОМ
[{\sl CACM,\/} {\bf 7} (1964), 297], КОТОРЫЙ ОТКРЫЛ ПЕРВЫЕ ДВА ЧЛЕНА В
АСИМПТОТИЧЕСКОМ ПОВЕДЕНИИ~(15)  ОТНОШЕНИЯ РОСТА.
лЕТОМ 1964~Г.\ р.~у.~фЛОЙД ПОЛУЧИЛ ЯВНЫЙ ВИД~$1/(2\sin\theta_0)$
ДЛЯ ОТНОШЕНИЯ РОСТА, ТАК ЧТО ТОЧНЫЕ ФОРМУЛЫ
МОГЛИ БЫТЬ ИСПОЛЬЗОВАНЫ ДЛЯ ВСЕХ~$T$. гЛУБОКИЙ АНАЛИЗ КАСКАДНЫХ ЧИСЕЛ БЫЛ
НЕЗАВИСИМО ВЫПОЛНЕН дЖ.~н.~рЭЙНИ
[{\sl Canadian J.~Math.,\/} {\bf 18} (1966), 332--349],
КОТОРЫЙ НАТКНУЛСЯ НА НИХ СОВЕРШЕННО ДРУГИМ ПУТЕМ,
НЕ ИМЕЯ ДЕЛА С СОРТИРОВКОЙ. рЭЙНИ ПОДМЕТИЛ АНАЛОГИЮ С ДИАГОНАЛЯМИ
(РИС.~73) И ВЫВЕЛ МНОГО ДРУГИХ ИНТЕРЕСНЫХ СВОЙСТВ ЭТИХ ЧИСЕЛ. фЛОЙД
И~рЭЙНИ В СВОИХ ДОКАЗАТЕЛЬСТВАХ ОПЕРИРОВАЛИ С МАТРИЦАМИ (СМ.~УПР.~6).

\section мОДИФИКАЦИЯ КАСКАДНОЙ СОРТИРОВКИ. еСЛИ ДОБАВЛЕНА ЕЩЕ ОДНА ЛЕНТА,
ТО ПОЧТИ ВСЕ ВРЕМЯ ПЕРЕМОТКИ В ТЕЧЕНИЕ КАСКАДНОЙ СОРТИРОВКИ МОЖНО
СОВМЕСТИТЬ. нАПРИМЕР, МЫ МОЖЕМ СЛИВАТЬ~T1--T5 НА~T7, ЗАТЕМ~T1--T4 НА~T6,
ЗАТЕМ~T1--T3 НА~T5 (КОТОРАЯ К ЭТОМУ МОМЕНТУ УЖЕ ПЕРЕМОТАНА), ЗАТЕМ~T1--T2
НА~T4 И НАЧАТЬ СЛЕДУЮЩИЙ ПРОХОД, КОГДА НА~T4 БУДЕТ ПЕРЕМОТАНО
СРАВНИТЕЛЬНО НЕМНОГО ДАННЫХ. эФФЕКТИВНОСТЬ ЭТОГО ПРОЦЕССА МОЖНО
ПРЕДСКАЗАТЬ НА ОСНОВАНИИ ИЗЛОЖЕННОГО ВЫШЕ АНАЛИЗА КАСКАДНОГО
МЕТОДА (ДАЛЬНЕЙШИЕ ПОДРОБНОСТИ СМ.~В~П.~5.4.6).

сХЕМА "КОМПРОМИССНОГО СЛИЯНИЯ", КОТОРАЯ ВКЛЮЧАЕТ МНОГОФАЗНУЮ И КАСКАДНУЮ
СХЕМЫ КАК ЧАСТНЫЕ СЛУЧАИ, БЫЛА ПРЕДЛОЖЕНА д.~э.~кНУТОМ В [{\sl CACM,\/}
{\bf 6} (1963), 585--587]. кАЖДАЯ ФАЗА СОСТОИТ ИЗ~$(T-1)\hbox{-ПУТЕВОГО}$,
$(T-2)\hbox{-ПУТЕВОГО}$,~\dots, $P\hbox{-ПУТЕВОГО}$ СЛИЯНИЙ, ГДЕ $P$---ЛЮБОЕ
ФИКСИРОВАННОЕ ЧИСЛО МЕЖДУ~1 И~$T-1$. еСЛИ~$P=T-1$, ТО ЭТО---МНОГОФАЗНЫЙ
МЕТОД; ЕСЛИ~$P=1$, ЭТО---ЧИСТЫЙ
%%354
КАСКАДНЫЙ МЕТОД; ЕСЛИ~$P=2$, ЭТО---КАСКАДНЫЙ МЕТОД БЕЗ ФАЗ
КОПИРОВАНИЯ. аНАЛИЗ ТАКОЙ СХЕМЫ БЫЛ ПРОДЕЛАН ч.~рАДКЕ
[{\sl IBM Systems J.,\/} {\bf 5} (1966), 226--247] И~у.~х.~бУРЖЕМ
[Proc. IFIP Congress, {\bf 1} (1971), 454---459]. бУРЖ НАШЕЛ
ПРОИЗВОДЯЩУЮ ФУНКЦИЮ~$\sum T_n(x) z^n$ ДЛЯ
КАЖДОГО~$(P, T)\hbox{-КОМПРОМИССНОГО}$ СЛИЯНИЯ,
ОБОБЩАЮЩУЮ СООТНОШЕНИЕ~(5.4.2-16); ОН
ПОКАЗАЛ, ЧТО НАИЛУЧШЕЕ ЗНАЧЕНИЕ~$P$ (С ТОЧКИ ЗРЕНИЯ НАИМЕНЬШЕГО ЧИСЛА
ОБРАБАТЫВАЕМЫХ НАЧАЛЬНЫХ ОТРЕЗКОВ), КАК ФУНКЦИИ ОТ~$S$
ПРИ~$S\to\infty$ (ЕСЛИ НЕПОСРЕДСТВЕННО ИСПОЛЬЗОВАТЬ СХЕМУ РАСПРЕДЕЛЕНИЯ
И ПРЕНЕБРЕЧЬ ВРЕМЕНЕМ ПЕРЕМОТКИ), ЕСТЬ СООТВЕТСТВЕННО
$(2, 3, 3, 4, 4, 4, 3, 3, 4)$ ПРИ~$T=(3, 4, 5, 6, 7, 8, 9, 10, 11)$.
эТИ ЗНАЧЕНИЯ~$P$ С
РОСТОМ~$T$ СИЛЬНЕЕ ОТКЛОНЯЮТСЯ В СТОРОНУ КАСКАДНОГО, А НЕ МНОГОФАЗНОГО
МЕТОДА, И ОКАЗЫВАЕТСЯ, ЧТО КОМПРОМИССНОЕ СЛИЯНИЕ НИКОГДА НЕ СТАНЕТ
СУЩЕСТВЕННО ЛУЧШЕ КАСКАДНОГО. с ДРУГОЙ СТОРОНЫ, ПРИ ОПТИМАЛЬНОМ ВЫБОРЕ
УРОВНЕЙ И РАСПРЕДЕЛЕНИИ ФИКТИВНЫХ ОТРЕЗКОВ, КАК ОПИСАНО В П.~5.4.2, ЧИСТЫЙ
МНОГОФАЗНЫЙ МЕТОД КАЖЕТСЯ НАИЛУЧШИМ СРЕДИ ВСЕХ КОМПРОМИССНЫХ СЛИЯНИЙ.
к СОЖАЛЕНИЮ, ОПТИМАЛЬНОЕ РАСПРЕДЕЛЕНИЕ СРАВНИТЕЛЬНО ТРУДНО РЕАЛИЗОВАТЬ.

т.~л.~йОНСЕН [{\sl BIT,\/} {\bf 6} (1966), 129--143] ИССЛЕДОВАЛ
СОЧЕТАНИЯ СБАЛАНСИРОВАННОГО И МНОГОФАЗНОГО СЛИЯНИЙ; МОДИФИКАЦИЯ
СБАЛАНСИРОВАННОГО СЛИЯНИЯ С СОВМЕЩЕНИЕМ ПЕРЕМОТОК БЫЛА ПРЕДЛОЖЕНА
м.~гОТЦЕМ [Digital Computer User's Handbook, ed.~by.~M.~Klerer
and~G.~A.~Korn (New York: McGraw-Hill, 1967), 1.311--1.312]; МОЖНО
ПРЕДСТАВИТЬ СЕБЕ И МНОГИЕ ДРУГИЕ ГИБРИДНЫЕ СХЕМЫ.

\excercises
\ex[10] иСПОЛЬЗУЯ ТАБЛ.~1, СРАВНИТЕ КАСКАДНОЕ СЛИЯНИЕ С ОПИСАННОЙ
В П.~5.4.2 ВЕРСИЕЙ МНОГОФАЗНОГО СЛИЯНИЯ С "РАСЩЕПЛЕНИЕМ ЛЕНТ". кАКОЙ
МЕТОД ЛУЧШЕ? (вРЕМЕНЕМ ПЕРЕМОТКИ ПРЕНЕБРЕЧЬ.)

\rex[22] сРАВНИТЕ КАСКАДНУЮ СОРТИРОВКУ С ТРЕМЯ ЛЕНТАМИ,
ИСПОЛЬЗУЮЩУЮ АЛГОРИТМ~C, И МНОГОФАЗНУЮ СОРТИРОВКУ С ТРЕМЯ ЛЕНТАМИ,
ИСПОЛЬЗУЮЩУЮ АЛГОРИТМ~5.4.2D кАКИЕ СХОДСТВА И РАЗЛИЧИЯ ВЫ ЗaМeТИТe?

\ex[20] сОСТАВЬТЕ ТАБЛИЦУ, ПОКАЗЫВАЮЩУЮ, ЧТО ПРОИСХОДИТ ПРИ СОРТИРОВКЕ НА
ШЕСТИ ЛЕНТАХ 100~НАЧАЛЬНЫХ ОТРЕЗКОВ ПРИ ПОМОЩИ АЛГОРИТМА~C.

\ex[м20] (дЖ.~н.~рЭЙНИ.) "кАСКАДНОЕ РАСПРЕДЕЛЕНИЕ $n\hbox{-ГО}$ УРОВНЯ"
ЕСТЬ МУЛЬТИМНОЖЕСТВО, ОПРЕДЕЛЕННОЕ СЛЕДУЮЩИМ ОБРАЗОМ (В СЛУЧАЕ ШЕСТИ ЛЕНТ):
$\set{1, 0, 0, 0, 0}$ ЕСТЬ КАСКАДНОЕ РАСПРЕДЕЛЕНИЕ НУЛЕВОГО УРОВНЯ;
ЕСЛИ~$\set{a, b, c, d, e}$---КАСКАДНОЕ РАСПРЕДЕЛЕНИЕ $n\hbox{-ГО}$~УРОВНЯ,
ТО~$\set{a+b+c+d+e, a+b+c+d, a+b+c, a+b, a}$ БУДЕТ КАСКАДНЫМ
РАСПРЕДЕЛЕНИЕМ $(n+1)\hbox{-ГО}$ УРОВНЯ (тАК КАК МУЛЬТИМНОЖЕСТВО НЕ
УПОРЯДОЧЕНО, ТО ИЗ ЕДИНСТВЕННОГО РАСПРЕДЕЛЕНИЯ $n\hbox{-ГО}$~УРОВНЯ МОЖНО
ОБРАЗОВАТЬ ДО~5 РАЗЛИЧНЫХ РАСПРЕДЕЛЕНИЙ $(n+1)\hbox{-ГО}$~УРОВНЯ.)
(a)~дОКАЖИТЕ, ЧТО \emph{ЛЮБОЕ}
МУЛЬТИМНОЖЕСТВО~$\set{a, b, c, d, e}$ ИЗ ВЗАИМНО ПРОСТЫХ ЧИСЕЛ ЯВЛЯЕТСЯ
КАСКАДНЫМ РАСПРЕДЕЛЕНИЕМ $n\hbox{-ГО}$~УРОВНЯ ПРИ НЕКОТОРОМ~$n$.
(b)~дОКАЖИТЕ, ЧТО РАСПРЕДЕЛЕНИЕ, ИСПОЛЬЗУЕМОЕ В КАСКАДНОЙ СОРТИРОВКЕ,
\emph{ОПТИМАЛЬНО} В ТОМ СМЫСЛЕ, ЧТО ЕСЛИ~$\set{a, b, c, d, e}$---ЛЮБОЕ
РАСПРЕДЕЛЕНИЕ $n\hbox{-ГО}$~УРОВНЯ, ПРИЧЕМ~$a\ge b \ge c \ge d \ge e$, ТО
БУДЕМ ИМЕТЬ~$a\le a_n$, $b\le b_n$, $c\le c_n$, $d\le d_n$, $e\le e_n$,
ГДЕ~$\set{a_n, b_n, c_n, d_n, e_n}$---РАСПРЕДЕЛЕНИЕ, ОПРЕДЕЛЕННОЕ В~(1).

\rex[20] дОКАЖИТЕ, ЧТО КАСКАДНЫЕ ЧИСЛА, ОПРЕДЕЛЕННЫЕ В~(1), УДОВЛЕТВОРЯЮТ
%%355
ЗАКОНУ
$$
a_k a_{n-k}+b_k b_{n-k}+c_k c_{n-k}+d_k d_{n-k}+e_k e_{n-k}=a_n
\rem{ПРИ~$ 0\le k \le n$.}
$$
[\emph{уКАЗАНИЕ:} ДЛЯ ЛУЧШЕГО ПОНИМАНИЯ ЭТОГО СООТНОШЕНИЯ РАССМОТРИТЕ,
СКОЛЬКО ОТРЕЗКОВ РАЗЛИЧНОЙ ДЛИНЫ ВЫВОДИТСЯ В ТЕЧЕНИЕ $k\hbox{-ГО}$~ПРОХОДА
ПОЛНОЙ КАСКАДНОЙ СОРТИРОВКИ.]

\ex[м20] нАЙДИТЕ $5\times5$-МАТРИЦУ~$Q$, ТАКУЮ, ЧТО ПЕРВАЯ СТРОКА~$Q^n$
СОДЕРЖИТ КАСКАДНЫЕ ЧИСЛА ДЛЯ ШЕСТИ ЛЕНТ~$a_n b_n c_n d_n e_n$ ПРИ
ВСЕХ~$n\ge 0$.

\ex[м20] пРИ УСЛОВИИ ЧТО КАСКАДНОЕ СЛИЯНИЕ ПРИМЕНЯЕТСЯ К
ТОЧНОМУ РАСПРЕДЕЛЕНИЮ $a_n$~НАЧАЛЬНЫХ ОТРЕЗКОВ, НАЙДИТЕ ФОРМУЛУ ДЛЯ
ВЕЛИЧИНЫ СЭКОНОМЛЕННОЙ РАБОТЫ, КОГДА ИСКЛЮЧАЕТСЯ ОДНОПУТЕВОЕ СЛИЯНИЕ.

\ex[вм23] вЫВЕДИТЕ ФОРМУЛУ~(12).

\ex[вм26] вЫВЕДИТЕ ФОРМУЛУ~(14).

\rex[м28] вМЕСТО СИСТЕМЫ~(4) ДЛЯ ИЗУЧЕНИЯ КАСКАДНЫХ ЧИСЕЛ ВОСПОЛЬЗУЙТЕСЬ
В КАЧЕСТВЕ ИСХОДНЫХ ТОЖДЕСТВАМИ
$$
\eqalignter{
e_n&=a_{n-1}  &= \perm{1}{1}a_{n-1};\cr
d_n&=2a_{n-1}-e_{n-2} &=\perm{2}{1}a_{n-1}-\perm{3}{3}a_{n-3};\cr
c_n&=3a_{n-1}-d_{n-2}-2e_{n-2} &=\perm{3}{1}a_{n-1}-\perm{4}{3}a_{n-3}+\perm{5}{5}a_{n-5}\cr
}
$$
И~Т.~Д. пОЛАГАЯ
$$
r_m(z)=\perm{m}{1}z-\perm{m+1}{3}z^3+\perm{m+2}{5}z^5-\ldots,
$$
ВЫРАЗИТЕ~$A(z)$, $B(z)$ И~Т.~Д.\ ЧЕРЕЗ ЭТИ $r\hbox{-МНОГОЧЛЕНЫ}$.

\ex[м38] пУСТЬ
$$
f_m(z)=\sum_{0\le k \le m} \perm{\floor{(m+k)/2}}{k}(-1)^{\ceil{k/2}}z^k.
$$
дОКАЖИТЕ, ЧТО ПРОИЗВОДЯЩАЯ ФУНКЦИЯ~$A(z)$ ДЛЯ $T\hbox{-ЛЕНТОЧНЫХ}$
КАСКАДНЫХ ЧИСЕЛ РАВНА~$f_{T-3}(z)/f_{T-1}(z)$, ПРИЧЕМ ЧИСЛИТЕЛЬ И
ЗНАМЕНАТЕЛЬ ЭТОГО ВЫРАЖЕНИЯ НЕ ИМЕЮТ ОБЩИХ ДЕЛИТЕЛЕЙ.

\ex[м40] дОКАЖИТЕ, ЧТО СХЕМА РАСПРЕДЕЛЕНИЯ фЕРГЮСОНА ОПТИМАЛЬНА В ТОМ
СМЫСЛЕ, ЧТО ПРИ ЛЮБОМ ДРУГОМ МЕТОДЕ РАЗМЕЩЕНИЯ ФИКТИВНЫХ ОТРЕЗКОВ,
УДОВЛЕТВОРЯЮЩЕМ~(2), ВО ВРЕМЯ ПЕРВОГО ПРОХОДА БУДЕТ ОБРАБАТЫВАТЬСЯ
НЕ МЕНЬШЕ НАЧАЛЬНЫХ ОТРЕЗКОВ, \emph{ПРИ УСЛОВИИ} ЧТО ВО ВРЕМЯ ЭТОГО
ПРОХОДА ИСПОЛЬЗУЕТСЯ СТРАТЕГИЯ ШАГОВ~C7--C9.

\ex[40] в ТЕКСТЕ ПРЕДЛАГАЕТСЯ БОЛЬШУЮ ЧАСТЬ ВРЕМЕНИ ПЕРЕМОТКИ СОВМЕЩАТЬ
ПУТЕМ ДОБАВЛЕНИЯ ДОПОЛНИТЕЛЬНОЙ ЛЕНТЫ. рАЗРАБОТАЙТЕ ЭТУ ИДЕЮ. (нАПРИМЕР,
СХЕМА, ИЗЛОЖЕННАЯ В ТЕКСТЕ, ВКЛЮЧАЕТ ОЖИДАНИЕ ПЕРЕМОТКИ ЛЕНТЫ~T4;
НЕ БУДЕТ ЛИ ЛУЧШЕ ИСКЛЮЧИТЬ~T4 ИЗ ПЕРВОЙ ФАЗЫ СЛИЯНИЯ СЛЕДУЮЩЕГО ПРОХОДА?)

\subsubchap{чТЕНИЕ ЛЕНТЫ В ОБРАТНОМ НАПРАВЛЕНИИ} %% 5.4.4
мНОГИЕ ЛЕНТОПРОТЯЖНЫЕ УСТРОЙСТВА ПОЗВОЛЯЮТ ЧИТАТЬ ЛЕНТУ В НАПРАВЛЕНИИ,
ПРОТИВОПОЛОЖНОМ ТОМУ, В КОТОРОМ ШЛА ЗАПИСЬ НА НЕЕ. сХЕМЫ СЛИЯНИЯ, С
КОТОРЫМИ МЫ ВСТРЕЧАЛИСЬ ДО СИХ ПОР, ВСЕГДА ЗАПИСЫВАЮТ ИНФОРМАЦИЮ НА ЛЕНТУ
В ПРЯМОМ НАПРАВЛЕНИИ,
%%  356
\bye