\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