\input style
\chapnotrue\chapno=5\subchno=4\subsubchno=2
ТАК КАК В ШАГАХ~A3 И~A5 ВЫПОЛНЯЕТСЯ ТОЛЬКО "ПОЛОВИНА ПРОХОДА",
Т.~Е.\ СЭКОНОМЛЕНО ОКОЛО 25\% ВРЕМЕНИ.

т ДЕЙСТВИТЕЛЬНОСТИ МОЖНО ДАЖЕ ПОЛНОСТЬЮ УСТРАНИТЬ КОПИРОВАНИЕ, ЕСЛИ
НАЧАТЬ С $F_n$~ОТРЕЗКОВ НА ЛЕНТЕ~T1 И С $F_{n-1}$~ОТРЕЗКОВ НА~T2,
ГДЕ~$F_n$ И~$F_{n-1}$---ПОСЛЕДОВАТЕЛЬНЫЕ ЧИСЛА ЇИБОНАЧЧИ. ЁАССМОТРИМ,
НАПРИМЕР, СЛУЧАЙ~$n=7$, $S=F_n+F_{n-1}=13+8=21$:
{\def\cm{\hfil$-$\hfil}\def\hd#1{\multispan{3}\hfil#1\hfil}\let\f=\hfil\ctable{
#\bskip&
#&#&#\bskip&\bskip#&#&#\bskip&\bskip#&#&#&#\hfil\cr
       &\hd{ёОДЕРЖИМОЕ~Є1}                      & \hd{ёОДЕРЖИМОЕ~Є2}        & \hd{ёОДЕРЖИМОЕ~T3}       & яРИМЕЧАНИЯ \cr
ЇАЗА~1.& 1, 1, 1, 1, &1, 1, 1, 1, &1, 1, 1, 1, 1& 1, 1, &1, 1, 1, 1, & 1, 1 &          &       &       & эАЧАЛЬНОЕ РАСПРЕДЕЛЕНИЕ\cr
ЇАЗА~2.&             &            &1, 1, 1, 1, 1&       &\cm         &      & 2, 2, 2, & 2,2,  & 2,2,2 & ёЛИЯНИЕ 8~ОТРЕЗКОВ НА~T3\cr
ЇАЗА~3.&             &\cm         &             &       &3, 3, 3, 3, & 3    &          &       & 2,2,2 & ёЛИЯНИЕ 5~ОТРЕЗКОВ НА~T3\cr
ЇАЗА~4.&             &\f  5, 5, 5 &             &       &\f 3,       & 3    &          & \cm   &       & ёЛИЯНИЕ 3~ОТРЕЗКОВ НА~T1\cr
ЇАЗА~5.&             &\f        5 &             &       &\cm         &      &          &\f 8,8 &       & ёЛИЯНИЕ 2~ОТРЕЗКОВ НА~T3\cr
ЇАЗА~6.&             &\cm         &             &       &\f 13 \f    &      &          &\f   8 &       & ёЛИЯНИЕ 1~ОТРЕЗКА НА~T2\cr
ЇАЗА~7.&             &\f 21 \f    &             &       &\cm         &      &          &\cm    &       & ёЛИЯНИЕ 1~ОТРЕЗКА НА~T1\cr
}}%
чДЕСЬ "2, 2, 2, 2, 2, 2, 2, 2", НАПРИМЕР, ОБОЗНАЧАЕТ ВОСЕМЬ
ОТРЕЗКОВ ОТНОСИТЕЛЬНОЙ ДЛИНЫ~2, ЕСЛИ СЧИТАТЬ ОТНОСИТЕЛЬНУЮ ДЛИНУ КАЖДОГО
НАЧАЛЬНОГО ОТРЕЗКА РАВНОЙ~1. тСЮДУ В ЭТОЙ ТАБЛИЦЕ ЧИСЛА ЇИБОНАЧЧИ!

яОЛНЫЙ ПРОХОД ПО ДАННЫМ ОСУЩЕСТВЛЯЮТ ТОЛЬКО ФАЗЫ~1 И~7;
ФАЗА~2 ОБРАБАТЫВАЕТ ЛИШЬ $16/21$~ОБЩЕГО ЧИСЛА НАЧАЛЬНЫХ ОТРЕЗКОВ,
ФАЗА~3---ЛИШЬ~$15/21$ И~Т. Д.; ТАКИМ ОБРАЗОМ, СУММАРНОЕ ЧИСЛО
"ПРОХОДОВ" РАВНО~$(21+16+15+15+16+13+21)/21=5{4\over7}$, ЕСЛИ
ПРЕДПОЛОЖИТЬ, ЧТО НАЧАЛЬНЫЕ ОТРЕЗКИ ИМЕЮТ ПРИМЕРНО РАВНУЮ
ДЛИНУ. фЛЯ СРАВНЕНИЯ ЗАМЕТИМ, ЧТО РАССМОТРЕННАЯ ВЫШЕ ДВУХФАЗНАЯ
ПРОЦЕДУРА ЗАТРАТИЛА БЫ 8~ПРОХОДОВ НА СОРТИРОВКУ ЭТИХ ЖЕ НАЧАЛЬНЫХ ОТРЕЗКОВ.
ьЫ УВИДИМ, ЧТО В ОБЩЕМ СЛУЧАЕ ЭТА СХЕМА ЇИБОНАЧЧИ ТРЕБУЕТ ПРИБЛИЗИТЕЛЬНО
$1.04\log_2 S+0.99$~ПРОХОДОВ, ЧТО ДЕЛАЕТ ЕЕ СРАВНИМОЙ С
\emph{ЧЕТЫРЕХЛЕНТОЧНЫМ} СБАЛАНСИРОВАННЫМ  СЛИЯНИЕМ, ХОТЯ ОНА ИСПОЛЬЗУЕТ
ТОЛЬКО ТРИ ЛЕНТЫ.

¤ТУ ИДЕЮ МОЖНО ОБОБЩИТЬ НА СЛУЧАЙ $T$~ЛЕНТ ПРИ ЛЮБОМ~$T\ge 3$, ИСПОЛЬЗУЯ
$(T-1)\hbox{-ПУТЕВОЕ}$~СЛИЯНИЕ. ьЫ УВИДИМ, НАПРИМЕР, ЧТО В СЛУЧАЕ ЧЕТЫРЕХ
ЛЕНТ ТРЕБУЕТСЯ ТОЛЬКО ОКОЛО $0.703\log_2 S+0.96$~ПРОХОДОВ ПО ДАННЫМ.
юБОБЩЕННАЯ СХЕМА ИСПОЛЬЗУЕТ ОБОБЩЕННЫЕ ЧИСЛА ЇИБОНАЧЧИ. ЁАССМОТРИМ
СЛЕДУЮЩИЙ ПРИМЕР С ШЕСТЬЮ ЛЕНТАМИ:
\ctable{
#\hfil\bskip&$#$\hfil\bskip&$#$\hfil\bskip&$#$\hfil\bskip&$#$\hfil\bskip&$#$\hfil\bskip&$#$\hfil\bskip&\hfil$#$&\hfil$\hbox{}#$\cr
       &       &       &       &       &       &       & \hbox{ўИСЛО ОБРАБАТЫВАЕМЫХ НАЧАЛЬНЫХ ОТРЕЗКОВ}\cr
       & T1    & T2    & T3    & T4    & T5    & T6    &                     \cr
ЇАЗА~1.& 1^{31}& 1^{30}& 1^{28}& 1^{24}& 1^{16}& -     & 31+30+28+24+16 =&129\cr
ЇАЗА~2.& 1^{15}& 1^{14}& 1^{12}& 1^8   & -     & 5^{16}&    16\times  5 =& 80\cr
ЇАЗА~3.& 1^7   & 1^6   & 1^4   & -     & 9^8   & 5^8   &     8\times  9 =& 72\cr
ЇАЗА~4.& 1^3   & 1^2   & -     & 17^4  & 9^4   & 5^4   &     4\times 17 =& 68\cr
ЇАЗА~5.& 1^1   & -     & 33^2  & 17^2  & 9^2   & 5^2   &     2\times 33 =& 66\cr
ЇАЗА~6.& -     & 65^1  & 33^1  & 17^1  & 9^1   & 5^1   &     1\times 65 =& 65\cr
ЇАЗА~7.& 129^1 & -     & -     & -     & -     & -     &     1\times 129=&129\cr
}
%%320

чДЕСЬ $1^{31}$~ОБОЗНАЧАЕТ 31~ОТРЕЗОК ОТНОСИТЕЛЬНОЙ ДЛИНЫ~1 И~Т.Д.;
ВЕЗДЕ ИСПОЛЬЗУЕТСЯ ПЯТИПУТЕВОЕ СЛИЯНИЕ. ¤ТА ОБЩАЯ СХЕМА БЫЛА РАЗРАБОТАНА
Ё.~ы.~уИЛСТЭДОМ
[Proc.\ AFIPS Eastern Jt.\ Computer Conf., 18 (1960), 143--148],
КОТОРЫЙ НАЗВАЛ ЕЕ МНОГОФАЗНЫМ СЛИЯНИЕМ. ёЛУЧАЙ ТРЕХ ЛЕНТ БЫЛ РАНЕЕ ОТКРЫТ
с.~ъ.~сЕТЦЕМ [НЕОПУБЛИКОВАННАЯ ЗАМЕТКА, Minneapolis-Honeywell Regulator
Co.\ (1956)].

ўТОБЫ ЗАСТАВИТЬ МНОГОФАЗНОЕ СЛИЯНИЕ РАБОТАТЬ, КАК В ПРЕДЫДУЩЕМ ПРИМЕРЕ,
НЕОБХОДИМО ПОСЛЕ КАЖДОЙ ФАЗЫ ИМЕТЬ "ТОЧНОЕ ФИБОНАЧЧИЕВО РАСПРЕДЕЛЕНИЕ"
ОТРЕЗКОВ ПО ЛЕНТАМ. ўИТАЯ ПРИВЕДЕННУЮ ВЫШЕ ТАБЛИЦУ СНИЗУ ВВЕРХ, МОЖНО
ЗАМЕТИТЬ, ЧТО ПЕРВЫЕ СЕМЬ ТОЧНЫХ ФИБОНАЧЧИЕВЫХ РАСПРЕДЕЛЕНИЙ ПРИ~$T=6$
СУТЬ $\set{1, 0, 0, 0, 0}$, $\set{1, 1, 1, 1, 1}$, $\set{2, 2, 2, 2, 1}$,
$\set{4, 4, 4, 3, 2}$, $\set{8, 8, 7, 6, 4}$, $\set{16, 15, 14, 12, 8}$
И~$\set{31, 30, 28, 24, 16}$. ЄЕПЕРЬ ПЕРЕД НАМИ СТОЯТ СЛЕДУЮЩИЕ ВАЖНЫЕ ВОПРОСЫ:
\enumerate
\li ъАКОЕ ПРАВИЛО СКРЫТО ЗА ЭТИМИ ТОЧНЫМИ ФИБОНАЧЧИЕВЫМИ РАСПРЕДЕЛЕНИЯМИ?
\li ўТО ДЕЛАТЬ, ЕСЛИ~$S$ НЕ СООТВЕТСТВУЕТ ТОЧНОМУ ФИБОНАЧЧИЕВОМУ
РАСПРЕДЕЛЕНИЮ?
\li ъАК ПОСТРОИТЬ НАЧАЛЬНЫЙ ПРОХОД РАСПРЕДЕЛЕНИЯ, ЧТОБЫ ОН ПОРОЖДАЛ НУЖНОЕ
РАСПОЛОЖЕНИЕ ОТРЕЗКОВ НА ЛЕНТАХ?
\li ёКОЛЬКО "ПРОХОДОВ" ПО ДАННЫМ ПОТРЕБУЕТ $T\hbox{-ЛЕНТОЧНОЕ}$
МНОГОФАЗНОЕ СЛИЯНИЕ (КАК ФУНКЦИЯ ОТ~$S$---ЧИСЛА НАЧАЛЬНЫХ ОТРЕЗКОВ)?
\enumend

ьЫ ОБСУДИМ ЭТИ ЧЕТЫРЕ ВОПРОСА ПО ОЧЕРЕДИ, ПРИ ЭТОМ СНАЧАЛА ДАДИМ "ПРОСТЫЕ
ОТВЕТЫ", А ЗАТЕМ ЗАЙМЕМСЯ БОЛЕЕ ГЛУБОКИМ АНАЛИЗОМ.

ЄОЧНЫЕ ФИБОНАЧЧИЕВЫ РАСПРЕДЕЛЕНИЯ МОЖНО ПОЛУЧИТЬ, "ПРОКРУЧИВАЯ"
РАССМОТРЕННУЮ СХЕМУ В ОБРАТНУЮ СТОРОНУ, ЦИКЛИЧЕСКИ ПЕРЕСТАВЛЯЯ СОДЕРЖИМОЕ
ЛЕНТ. эАПРИМЕР, ПРИ~$T=6$ ИМЕЕМ СЛЕДУЮЩЕЕ РАСПРЕДЕЛЕНИЕ ОТРЕЗКОВ:
$$
\vcenter{\halign{
\hfil # \hfil &\bskip\hfil$#$\bskip&\bskip\hfil$#$\bskip&\bskip\hfil$#$\bskip&\bskip\hfil$#$\bskip&\bskip\hfil$#$\bskip&\bskip\hfil$#$\bskip&\hfil$#$\hfil\cr
єРОВЕНЬ & T1 & T2 & T3 & T4& T5 &  \hbox{ёУММА} & \hbox{ыЕНТА С ОКОНЧАТЕЛЬНЫМ РЕЗУЛЬТАТОМ}\cr
0 &   1 &   0&   0&  0 &  0&   1& T1\cr
1 &   1 &   1&   1&  1 &  1&   5& T6\cr
2 &   2 &   2&   2&  2 &  1&   9& T5\cr
3 &   4 &   4&   4&  3 &  2&  17& T4\cr
4 &   8 &   8&   7&  6 &  4&  33& T3\cr
5 &  16 &  15&  14& 12 &  8&  65& T2\cr
6 &  31 &  30&  28& 24 & 16& 129& T1\cr
7 &  61 &  59&  55& 47 & 31& 253& T6\cr
8 & 120 & 116& 108& 92 & 61& 497& T5\cr
\multispan{8}\dotfill\cr
n   & a_n     & b_n     & c_n     & d_n     & e_n & t_n      & T(k) \cr
n+1 & a_n+b_n & a_n+c_n & a_n+d_n & a_n+e_n & a_n & t_n+4a_n & T(k-1)\cr
\multispan{8}\dotfill\cr
}}
\eqno(1)
$$
%%321
(яОСЛЕ НАЧАЛЬНОГО РАСПРЕДЕЛЕНИЯ ЛЕНТА~T6 ВСЕГДА БУДЕТ ПУСТОЙ.)

шЗ ПРАВИЛА ПЕРЕХОДА ОТ УРОВНЯ~$n$ К УРОВНЮ~$n+1$ ЯСНО, ЧТО УСЛОВИЯ
$$
a_n \ge b_n \ge c_n \ge d_n \ge e_n
\eqno (2)
$$
ВЫПОЛНЯЮТСЯ НА ЛЮБОМ УРОВНЕ. т САМОМ ДЕЛЕ, ЛЕГКО ВИДЕТЬ ИЗ~(1), ЧТО
$$
\eqalign{
e_n &= a_{n-1},\cr
d_n &= a_{n-1}+e_{n-1}=a_{n-1}+a_{n-2},\cr
c_n &= a_{n-1}+d_{n-1}=a_{n-1}+a_{n-2}+a_{n-3},\cr
b_n &= a_{n-1}+c_{n-1}=a_{n-1}+a_{n-2}+a_{n-3}+a_{n-4},\cr
a_n &= a_{n-1}+b_{n-1}=a_{n-1}+a_{n-2}+a_{n-3}+a_{n-4}+a_{n-5},\cr
}
\eqno (3)
$$
ГДЕ~$a_0=1$ И ГДЕ МЫ ПОЛАГАЕМ~$a_n=0$ ПРИ~$n=-1$, $-2$, $-3$, $-4$.
\def\Fib#1,#2.{F^{(#1)}_{#2}}
\dfn{ўИСЛА ЇИБОНАЧЧИ $p\hbox{-ГО}$~ПОРЯДКА~$\Fib p, n.$} ОПРЕДЕЛЯЮТСЯ ПРАВИЛАМИ
$$
\eqalign{
\Fib p, n. &=\Fib p, n-1.+\Fib p, n-2.+\cdots+\Fib p, n-p. \rem{ПРИ $n\ge p$;}\cr
\Fib p, n. &=0 \rem{ПРИ $0\le n \le p-2$;}\cr
\Fib p, p-1. &=1.\cr
}
\eqno (4)
$$

фРУГИМИ СЛОВАМИ, МЫ НАЧИНАЕМ С $p-1$~НУЛЕЙ, ЗАТЕМ ПИШЕМ~1, А КАЖДОЕ
СЛЕДУЮЩЕЕ ЧИСЛО ЯВЛЯЕТСЯ СУММОЙ $p$~ПРЕДЫДУЩИХ ЧИСЕЛ. яРИ~$p=2$ ЭТО
ОБЫЧНАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ ЇИБОНАЧЧИ; ДЛЯ БОЛЬШИХ ЗНАЧЕНИЙ~$p$ ЭТУ
ПОСЛЕДОВАТЕЛЬНОСТЬ ВПЕРВЫЕ ИЗУЧИЛ, ПО-ВИДИМОМУ, т.~°ЛЕГЕЛЬ В
[{\sl El Progreso Matematico,\/} {\bf 4} (1894), 173--174]. °ЛЕГЕЛЬ ВЫВЕЛ
ПРОИЗВОДЯЩУЮ ФУНКЦИЮ
$$
\sum_{n\ge 0}\Fib p, n. z^n=
{z^{p-1}\over 1-z-z^2-\cdots-z^p}=
{z^{p-1}-z^p \over 1-2z+z^{p+1}}.
\eqno (5)
$$
ЇОРМУЛА~(3) ПОКАЗЫВАЕТ, ЧТО ЧИСЛО ОТРЕЗКОВ НА~T1 В
ПРОЦЕССЕ ШЕСТИЛЕНТОЧНОГО МНОГОФАЗНОГО СЛИЯНИЯ ЯВЛЯЕТСЯ ЧИСЛОМ ЇИБОНАЧЧИ
ПЯТОГО ПОРЯДКА~$a_n=\Fib 5, n+4.$.

т ОБЩЕМ СЛУЧАЕ, ЕСЛИ ПОЛОЖИТЬ~$P=T-1$, РАСПРЕДЕЛЕНИЯ В МНОГОФАЗНОМ СЛИЯНИИ
ДЛЯ $T$~ЛЕНТ БУДУТ АНАЛОГИЧНЫМ ОБРАЗОМ СООТВЕТСТВОВАТЬ ЧИСЛАМ ЇИБОНАЧЧИ
$P\hbox{-ГО}$~ПОРЯДКА. т ТОЧНОМ РАСПРЕДЕЛЕНИИ $n\hbox{-ГО}$~УРОВНЯ НА
$k\hbox{-Й}$~ЛЕНТЕ БУДЕТ
$$
\Fib P, n+P-2. + \Fib P, n+P-3. +\cdots+ \Fib P, n+k-2.
$$
%% 322
НАЧАЛЬНЫХ ОТРЕЗКОВ ДЛЯ~$1\le k \le P$, А ОБЩЕЕ КОЛИЧЕСТВО НАЧАЛЬНЫХ
ОТРЕЗКОВ НА ВСЕХ ЛЕНТАХ БУДЕТ, СЛЕДОВАТЕЛЬНО, РАВНО
$$
t_n=P\Fib P, n+P-2. + (P-1)\Fib P, n+P-3. + \cdots + \Fib P, n-1. .
\eqno(6)
$$

¤ТО РЕШАЕТ ВОПРОС О "ТОЧНОМ ФИБОНАЧЧИЕВОМ РАСПРЕДЕЛЕНИИ". эО ЧТО МЫ ДОЛЖНЫ
ДЕЛАТЬ, ЕСЛИ~$S$ НЕ РАВНО В ТОЧНОСТИ~$t_n$ НИ ПРИ КАКОМ~$n$? ъАК
ПЕРВОНАЧАЛЬНО ПОМЕСТИТЬ ОТРЕЗКИ НА ЛЕНТЫ?

хСЛИ~$S$ НЕ ЯВЛЯЕТСЯ ТОЧНЫМ ЧИСЛОМ ЇИБОНАЧЧИ (А ЧИСЕЛ ЇИБОНАЧЧИ НЕ ТАК
УЖ МНОГО), ТО МОЖНО ДЕЙСТВОВАТЬ, КАК В СБАЛАНСИРОВАННОМ
$P\hbox{-ПУТЕВОМ}$ СЛИЯНИИ, ДОБАВЛЯЯ  "ФИКТИВНЫЕ
\picture{ЁИС.~68. ёОРТИРОВКА МНОГОФАЗНЫМ СЛИЯНИЕМ.}
ОТРЕЗКИ"; ПОЭТОМУ МОЖНО СЧИТАТЬ, ЧТО~$S$, В КОНЦЕ КОНЦОВ, БУДЕТ ТОЧНЫМ.
хСТЬ НЕСКОЛЬКО СПОСОБОВ ДОБАВЛЕНИЯ ФИКТИВНЫХ ОТРЕЗКОВ; МЫ ЕЩЕ НЕ ЗНАЕМ,
КАК ЭТО СДЕЛАТЬ "НАИЛУЧШИМ" СПОСОБОМ. т ПЕРВУЮ ОЧЕРЕДЬ РАССМОТРИМ МЕТОД
РАСПРЕДЕЛЕНИЯ ОТРЕЗКОВ И ПРИПИСЫВАНИЯ ФИКТИВНЫХ ОТРЕЗКОВ, КОТОРЫЙ ХОТЯ И
НЕ САМЫЙ ОПТИМАЛЬНЫЙ, НО ЗАТО ДОСТАТОЧНО ПРОСТОЙ И, ПО-ВИДИМОМУ,
ЛУЧШЕ ВСЕХ ДРУГИХ МЕТОДОВ ТАКОЙ ЖЕ СТЕПЕНИ СЛОЖНОСТИ.

\alg D.(ёОРТИРОВКА МНОГОФАЗНЫМ СЛИЯНИЕМ С ИСПОЛЬЗОВАНИЕМ
"ГОРИЗОНТАЛЬНОГО" РАСПРЕДЕЛЕНИЯ.) ¤ТОТ АЛГОРИТМ БЕРЕТ НАЧАЛЬНЫЕ ОТРЕЗКИ
И РАСПРЕДЕЛЯЕТ ИХ ОДИН ЗА ДРУГИМ ПО ЛЕНТАМ, ПОКА ЗАПАС НАЧАЛЬНЫХ ОТРЕЗКОВ
НЕ ИСЧЕРПАЕТСЯ. чАТЕМ ОН ОПРЕДЕЛЯЕТ, КАК НАДО СЛИВАТЬ ЛЕНТЫ, ИСПОЛЬЗУЯ
$P\hbox{-ПУТЕВОЕ}$ СЛИЯНИЕ, В ПРЕДПОЛОЖЕНИИ, ЧТО ИМЕЮТСЯ $T=P+1\ge
3$~ЛЕНТОПРОТЯЖНЫХ УСТРОЙСТВ. ыЕНТУ~$T$ МОЖНО ИСПОЛЬЗОВАТЬ ДЛЯ ХРАНЕНИЯ
ВВОДА, ТАК КАК НА НЕЕ НЕ ЗАПИСЫВАЕТСЯ НИ ОДНОГО НАЧАЛЬНОГО ОТРЕЗКА. т
ПАМЯТИ ХРАНЯТСЯ СЛЕДУЮЩИЕ ТАБЛИЦЫ:

%%323
\descrtable{
$|A|[j]$, $1 \le j \le T$:
 & ЄОЧНОЕ ФИБОНАЧЧИЕВОЕ РАСПРЕДЕЛЕНИЕ, К КОТОРОМУ МЫ СТРЕМИМСЯ. \cr
$|D|[j]$, $1 \le j \le T$:
 & ўИСЛО ФИКТИВНЫХ ОТРЕЗКОВ, КОТОРЫЕ СЧИТАЮТСЯ ПРИСУТСТВУЮЩИМИ В НАЧАЛЕ
 ЛЕНТЫ НА ЛОГИЧЕСКОМ УСТРОЙСТВЕ С НОМЕРОМ~$j$.\cr
$|TAPE|[j]$, $1 \le j \le T$:
 & эОМЕР ФИЗИЧЕСКОГО ЛЕНТОПРОТЯЖНОГО УСТРОЙСТВА, СООТВЕТСТВУЮЩЕГО ЛОГИЧЕСКОМУ
 УСТРОЙСТВУ С НОМЕРОМ~$j$.\cr
}
(юКАЗАЛОСЬ, ЧТО УДОБНО РАБОТАТЬ С "НОМЕРАМИ ЛОГИЧЕСКИХ ЛЕНТОПРОТЯЖНЫХ
УСТРОЙСТВ", СООТВЕТСТВИЕ КОТОРЫХ ФИЗИЧЕСКИМ УСТРОЙСТВАМ МЕНЯЕТСЯ В
ПРОЦЕССЕ ВЫПОЛНЕНИЯ АЛГОРИТМА.)

\st[эАЧАЛЬНАЯ УСТАНОВКА.] єСТАНОВИТЬ~$|A|[j]\asg |D|[j]\asg 1$
И~$|TAPE|[j]\asg j$ ПРИ~$1\le j < T$. єСТАНОВИТЬ~$|A|[T]\asg |D|[T]\asg 0$
И~$|TAPE|[T]\asg T$. чАТЕМ УСТАНОВИТЬ~$l\asg 1$, $j\asg 1$.

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

\st[яРОДВИЖЕНИЕ~$j$.] хСЛИ~$|D|[j]<|D|[j+1]$, ТО УВЕЛИЧИТЬ~$j$ НА~1 И
ВЕРНУТЬСЯ К ШАГУ~\stp{2}. т ПРОТИВНОМ СЛУЧАЕ, ЕСЛИ~$|D|[j]=0$, ПЕРЕЙТИ К
ШАГУ~\stp{4}, А ЕСЛИ~$|D|[j]\ne 0$, УСТАНОВИТЬ~$j\asg 1$ И ВЕРНУТЬСЯ К
ШАГУ~\stp{2}.

\st[яОДНЯТЬСЯ НА ОДИН УРОВЕНЬ.] єСТАНОВИТЬ~$l\asg l+1$, $a\asg |A|[1]$,
ЗАТЕМ ДЛЯ~$j=1$, 2,~\dots, $P$ (ИМЕННО В ЭТОМ ПОРЯДКЕ)
УСТАНОВИТЬ~$|D|[j]\asg a+|A|[j+1]-|A|[j]$ И~$|A|[j]\asg
a+|A|[j+1]$. (ёМ.~(1). юТМЕТИМ, ЧТО~$|A|[P+1]$ ВСЕГДА~0. т ЭТОМ
МЕСТЕ БУДЕМ ИМЕТЬ~$|D|[1]>|D|[2]>\ldots>|D|[T]$.) ЄЕПЕРЬ УСТАНОВИТЬ~$j\asg 1$
И ВЕРНУТЬСЯ К ШАГУ~\stp{2}.

\st[ёЛИЯНИЕ.] хСЛИ~$l=0$, ТО СОРТИРОВКА ЗАВЕРШЕНА, РЕЗУЛЬТАТ НАХОДИТСЯ
НА~$|TAPE|[1]$. т ПРОТИВНОМ СЛУЧАЕ СЛИВАТЬ ОТРЕЗКИ С ЛЕНТ~$|TAPE|[1]$,~\dots,
$|TAPE|[P]$ НА~$|TAPE|[T]$ ДО ТЕХ ПОР, ПОКА~$|TAPE|[P]$ НЕ СТАНЕТ
ПУСТОЙ И~$|D|[P]$ НЕ ОБРАТИТСЯ В~$0$. яРОЦЕСС СЛИЯНИЯ ДЛЯ КАЖДОГО
СЛИВАЕМОГО ОТРЕЗКА ДОЛЖЕН ПРОТЕКАТЬ СЛЕДУЮЩИМ ОБРАЗОМ. хСЛИ~$|D|[j]>0$ ДЛЯ
ВСЕХ~$j$, $1\le j \le P$, ТО УВЕЛИЧИТЬ~$|D|[T]$ НА~1 И УМЕНЬШИТЬ
КАЖДОЕ~$|D|[j]$ НА~1 ДЛЯ~$1\le j \le P$; В ПРОТИВНОМ СЛУЧАЕ СЛИВАТЬ
ПО ОДНОМУ ОТРЕЗКУ С КАЖДОЙ ЛЕНТЫ~$|TAPE|[j]$, ТАКОЙ, ЧТО~$|D|[j]=0$, И
УМЕНЬШИТЬ~$|D|[j]$ НА~1 ДЛЯ ОСТАЛЬНЫХ~$j$. (ЄАКИМ ОБРАЗОМ, СЧИТАЕТСЯ, ЧТО
ФИКТИВНЫЕ ОТРЕЗКИ НАХОДЯТСЯ В \emph{НАЧАЛЕ} ЛЕНТЫ, А НЕ В КОНЦЕ.)

\st[юПУСТИТЬСЯ НА ОДИН УРОВЕНЬ.] єСТАНОВИТЬ~$l\asg l-1$. яЕРЕМОТАТЬ
ЛЕНТЫ~$|TAPE|[P]$ И~$|TAPE|[T]$. (т ДЕЙСТВИТЕЛЬНОСТИ ПЕРЕМОТКА~$|TAPE|[P]$
МОГЛА БЫТЬ НАЧАТА НА ШАГЕ~\stp{5} ПОСЛЕ ВВОДА С НЕЕ ПОСЛЕДНЕГО БЛОКА.)
чАТЕМ УСТАНОВИТЬ~$(|TAPE|[1],
%%324
|TAPE|[2],~\ldots, |TAPE|[T])\asg (|TAPE|[T], |TAPE|[1],~\ldots,
|TAPE|[T-1])$, $(|D|[1], |D|[2],~\ldots, |D|[T])\asg(|D|[T], |D|[1],~\ldots, |D|[T-1])$
И ВЕРНУТЬСЯ К ШАГУ~\stp{5}.
\algend

яРАВИЛО РАСПРЕДЕЛЕНИЯ, КОТОРОЕ ТАК ЛАКОНИЧНО СФОРМУЛИРОВАНО В ШАГЕ~D3
ЭТОГО АЛГОРИТМА, СТРЕМИТСЯ ПО ВОЗМОЖНОСТИ УРАВНЯТЬ ЧИСЛА ФИКТИВНЫХ
ОТРЕЗКОВ НА КАЖДОЙ ЛЕНТЕ. ЁИСУНОК~69 ИЛЛЮСТРИРУЕТ ПОРЯДОК РАСПРЕДЕЛЕНИЯ,
КОГДА МЫ ПЕРЕХОДИМ ОТ УРОВНЯ~4 (33~ОТРЕЗКА) К УРОВНЮ~5 (65~ОТРЕЗКОВ) В
СОРТИРОВКЕ С ШЕСТЬЮ ЛЕНТАМИ; ЕСЛИ БЫЛО БЫ, СКАЖЕМ, ТОЛЬКО 53~НАЧАЛЬНЫХ
\picture{
ЁИС.~69. яОРЯДОК, В КОТОРОМ ОТРЕЗКИ С~34-ГО ПО~65-Й
РАСПРЕДЕЛЯЮТСЯ НА ЛЕНТЫ ПРИ ПЕРЕХОДЕ С УРОВНЯ~4 НА УРОВЕНЬ~5. (ёМ.~ТАБЛИЦУ
ТОЧНЫХ РАСПРЕДЕЛЕНИЙ НА СТР.~320.) чАШТРИХОВАННЫЕ ОБЛАСТИ
СООТВЕТСТВУЮТ ПЕРВЫМ 33~ОТРЕЗКАМ, КОТОРЫЕ БЫЛИ РАСПРЕДЕЛЕНЫ К МОМЕНТУ
ДОСТИЖЕНИЯ УРОВНЯ~4.
}
ОТРЕЗКА, ТО ВСЕ ОТРЕЗКИ С НОМЕРАМИ~54 И ВЫШЕ РАССМАТРИВАЛИСЬ БЫ КАК
ФИКТИВНЫЕ. (эА САМОМ ДЕЛЕ ОТРЕЗКИ ЗАПИСЫВАЮТСЯ В КОНЕЦ ЛЕНТЫ, НО УДОБНЕЕ
СЧИТАТЬ, ЧТО ОНИ ЗАПИСЫВАЮТСЯ В НАЧАЛО, ТАК КАК ПРЕДПОЛАГАЕТСЯ, ЧТО
ФИКТИВНЫЕ ОТРЕЗКИ НАХОДЯТСЯ В НАЧАЛЕ ЛЕНТЫ.)

ьЫ УЖЕ РАССМОТРЕЛИ ПЕРВЫЕ ТРИ ИЗ ПОСТАВЛЕННЫХ ВЫШЕ ВОПРОСОВ, ОСТАЛОСЬ
ВЫЯСНИТЬ ЧИСЛО "ПРОХОДОВ" ПО ДАННЫМ. ёРАВНИВАЯ НАШ ШЕСТИЛЕНТОЧНЫЙ ПРИМЕР
С ТАБЛИЦЕЙ~(1), МЫ ВИДИМ, ЧТО СУММАРНОЕ КОЛИЧЕСТВО ОБРАБОТАННЫХ НАЧАЛЬНЫХ
ОТРЕЗКОВ ПРИ~$S=t_6$ ЕСТЬ~$a_5t_1+a_4t_2+a_3t_3+a_2t_4+a_1t_5+a_0t_6$,
ЕСЛИ ИСКЛЮЧИТЬ НАЧАЛЬНЫЙ ПРОХОД РАСПРЕДЕЛЕНИЯ. т УПР.~4 ВЫВОДЯТСЯ
%%325
ПРОИЗВОДЯЩИЕ ФУНКЦИИ
$$
\eqalign{
a(z)&=\sum_{n\ge0}a_nz^n={1\over 1-z-z^2-z^3-z^4-z^5},\cr
t(z)&=\sum_{n\ge1} t_nz^n={5z+4z^2+3z^3+2z^4+z^5\over 1-z-z^2-z^3-z^4-z^5}.\cr
}
\eqno(7)
$$
юТСЮДА СЛЕДУЕТ, ЧТО В ОБЩЕМ СЛУЧАЕ ЧИСЛО ОБРАБАТЫВАЕМЫХ НАЧАЛЬНЫХ
ОТРЕЗКОВ ПРИ~$S=t_n$ РАВНО КОЭФФИЦИЕНТУ ПРИ~$z^n$ В
ПРОИЗВЕДЕНИИ~$a(z)\cdot t(z)$ ПЛЮС~$t_n$ (ЭТО ДАЕТ НАЧАЛЬНЫЙ ПРОХОД
РАСПРЕДЕЛЕНИЯ). ЄЕПЕРЬ МЫ МОЖЕМ ВЫЧИСЛИТЬ АСИМПТОТИЧЕСКОЕ ПОВЕДЕНИЕ
МНОГОФАЗНОГО СЛИЯНИЯ, КАК ПОКАЗАНО В УПР.~5--7, И ПОЛУЧАЕМ РЕЗУЛЬТАТЫ,
ПРИВЕДЕННЫЕ В ТАБЛ.~1.

т ТАБЛ.~1 "ОТНОШЕНИЕ РОСТА" ЕСТЬ ПРЕДЕЛ~$\lim_{n\to\infty} t_{n+1}t_n$,
ПОКАЗЫВАЮЩИЙ, ВО СКОЛЬКО ПРИБЛИЗИТЕЛЬНО РАЗ ВОЗРАСТАЕТ ЧИСЛО
\htable{ЄАБЛИЦА~1}%
{рППРОКСИМАЦИЯ ПОВЕДЕНИЯ СОРТИРОВКИ МНОГОФАЗНЫМ СЛИЯНИЕМ}%
{\hfill$#$\bskip&&\bskip\hfill$#$\hfill\bskip\cr
\hbox{ыЕНТЫ} &  \hbox{ЇАЗЫ} &    \hbox{яРОХОДЫ}  &  \hbox{яРОХОДЫ/ФАЗЫ,} & \hbox{юТНОШЕНИЕ}\cr
             &              &                    &                       & \hbox{В ПРОЦЕНТАХ РОСТА}\cr
\noalign{\hrule}
 3 & 2.078 \ln S+0.678 & 1.504 \ln S+0.992 & 72 & 1.6180340\cr
 4 & 1.641 \ln S+0.364 & 1.015 \ln S+0.965 & 62 & 1.8392868\cr
 5 & 1.524 \ln S+0.078 & 0.863 \ln S+0.921 & 57 & 1.9275620\cr
 6 & 1.479 \ln S-0.185 & 0.795 \ln S+0.864 & 54 & 1.9659482\cr
 7 & 1.460 \ln S-0.424 & 0.762 \ln S+0.797 & 52 & 1.9835826\cr
 8 & 1.451 \ln S-0.642 & 0.744 \ln S+0.723 & 51 & 1.9919642\cr
 9 & 1.447 \ln S-0.838 & 0.734 \ln S+0.646 & 51 & 1.9960312\cr
10 & 1.445 \ln S-1.017 & 0.728 \ln S+0.568 & 50 & 1.9980295\cr
20 & 1.443 \ln S-2.170 & 0.721 \ln S-0.030 & 50 & 1.9999981\cr
\noalign{\hrule}
}
ОТРЕЗКОВ НА КАЖДОМ УРОВНЕ. "яРОХОДЫ" ОБОЗНАЧАЮТ СРЕДНЕЕ КОЛИЧЕСТВО
ОБРАБОТОК КАЖДОЙ ЗАПИСИ, А ИМЕННО~$(1/S)$, УМНОЖЕННОЕ НА ОБЩЕЕ ЧИСЛО
НАЧАЛЬНЫХ ОТРЕЗКОВ, ОБРАБАТЫВАЕМЫХ В ТЕЧЕНИЕ ФАЗ РАСПРЕДЕЛЕНИЯ И СЛИЯНИЯ.
єСТАНОВЛЕННЫЕ ЧИСЛА ПРОХОДОВ И ФАЗ СПРАВЕДЛИВЫ В КАЖДОМ СЛУЧАЕ С ТОЧНОСТЬЮ
ДО~$O(S^{-\varepsilon})$ ПРИ НЕКОТОРОМ~$\varepsilon>0$ ДЛЯ ТОЧНОГО
РАСПРЕДЕЛЕНИЯ ПРИ~$S\to\infty$.

эА РИС.~70 ИЗОБРАЖЕНЫ В ВИДЕ ФУНКЦИЙ ОТ~$S$ СРЕДНИЕ КОЛИЧЕСТВА СЛИЯНИЙ
КАЖДОЙ ЗАПИСИ ПРИ ИСПОЛЬЗОВАНИИ АЛГОРИТМА~D В СЛУЧАЕ НЕТОЧНЫХ ЧИСЕЛ.
чАМЕТИМ, ЧТО ПРИ ИСПОЛЬЗОВАНИИ ТРЕХ ЛЕНТ КАК РАЗ ПОСЛЕ ТОЧНЫХ
РАСПРЕДЕЛЕНИЙ ПОЯВЛЯЮТСЯ "ПИКИ" ОТНОСИТЕЛЬНОЙ НЕЭФФЕКТИВНОСТИ, НО ЭТО
ЯВЛЕНИЕ В ЗНАЧИТЕЛЬНОЙ СТЕПЕНИ ИСЧЕЗАЕТ ПРИ ЧЕТЫРЕХ ИЛИ БОЛЬШЕМ ЧИСЛЕ ЛЕНТ.
шСПОЛЬЗОВАНИЕ
%%326
ВОСЬМИ ИЛИ БОЛЕЕ ЛЕНТ ДАЕТ СРАВНИТЕЛЬНО МАЛОЕ УЛУЧШЕНИЕ ПО
СРАВНЕНИЮ С ШЕСТЬЮ ИЛИ СЕМЬЮ ЛЕНТАМИ.

\section *сОЛЕЕ ДЕТАЛЬНОЕ РАССМОТРЕНИЕ. т СБАЛАНСИРОВАННОМ СЛИЯНИИ,
 ТРЕБУЮЩЕМ $k$~ПРОХОДОВ, КАЖДАЯ ЗАПИСЬ ОБРАБАТЫВАЕТСЯ В ХОДЕ СОРТИРОВКИ
РОВНО $k$~РАЗ. эО МНОГОФАЗНАЯ ПРОЦЕДУРА НЕ ЯВЛЯЕТСЯ ТАКОЙ БЕСПРИСТРАСТНОЙ:
НЕКОТОРЫЕ ЗАПИСИ МОГУТ ОБРАБАТЫВАТЬСЯ
\picture{ЁИС.~70.  ¤ФФЕКТИВНОСТЬ МНОГОФАЗНОГО СЛИЯНИЯ, ИСПОЛЬЗУЮЩЕГО АЛГОРИТМ~D.}
МНОГО БОЛЬШЕЕ ЧИСЛО РАЗ, ЧЕМ ДРУГИЕ, И МЫ МОЖЕМ УВЕЛИЧИТЬ СКОРОСТЬ, ЕСЛИ
УСЛОВИМСЯ ПОМЕЩАТЬ ФИКТИВНЫЕ ОТРЕЗКИ В ЧАСТО ОБРАБАТЫВАЕМЫЕ ПОЗИЦИИ.

яО ЭТОЙ ПРИЧИНЕ ИЗУЧИМ БОЛЕЕ ПОДРОБНО МНОГОФАЗНОЕ РАСПРЕДЕЛЕНИЕ. тМЕСТО
ТОГО ЧТОБЫ ИНТЕРЕСОВАТЬСЯ ТОЛЬКО ЧИСЛОМ ОТРЕЗКОВ НА КАЖДОЙ ЛЕНТЕ, КАК
В~(1), ПРИПИШЕМ КАЖДОМУ ОТРЕЗКУ ЕГО \emph{ЧИСЛО СЛИЯНИЙ}---СКОЛЬКО РАЗ ОН
ОБРАБАТЫВАЕТСЯ В ТЕЧЕНИЕ ВСЕГО ПРОЦЕССА СОРТИРОВКИ. тМЕСТО~(1) ПОЛУЧИМ СЛЕДУЮЩУЮ ТАБЛИЦУ:
%%327
$$
\matrix{
\hbox{єРОВЕНЬ} & T1 & T2 & T3 & T4 & T5 \cr
0 & 0 & - & - & - & - \cr
1 & 1 & 1 & 1 & 1 & 1 \cr
2 & 21 & 21 & 21 & 21 & 2\cr
3 & 3221 & 3221 & 3221 & 322 & 32 \cr
4 & 43323221 & 43323221 & 4332322 & 433232 & 4332 \cr
5 & 5443433243323221 & 544343324332322 & 54434332433232 & 544343324332 & 54434332 \cr
\multispan{6}{\dotfill}\cr
n  & A_n & B_n & C_n & D_n & E_n \cr
n+1& (A_n+1)B_n & (A_n+1)C_n & (A_n+1)D_n & (A_n+1)E_n & A_n+1\cr
\multispan{6}{\dotfill}\cr
}
\eqno(8)
$$
чДЕСЬ $A_n$~ЕСТЬ ЦЕПОЧКА ИЗ $a_n$~ЗНАЧЕНИЙ, ПРЕДСТАВЛЯЮЩИХ ЧИСЛА СЛИЯНИЙ
КАЖДОГО ОТРЕЗКА НА~$T1$, ЕСЛИ МЫ НАЧИНАЕМ С РАСПРЕДЕЛЕНИЯ
$n\hbox{-ГО}$~УРОВНЯ; $B_n$~ЕСТЬ СООТВЕТСТВУЮЩАЯ ЦЕПОЧКА ДЛЯ~T2 И~Т.~Д.\
юБОЗНАЧЕНИЕ~"$(A_n+1)B_n$" ЧИТАЕТСЯ: "$A_n$, ВСЕ ЗНАЧЕНИЯ КОТОРОЙ
УВЕЛИЧЕНЫ НА~1, А ЗА НЕЮ~$B_n$".

ЁИСУНОК~71~(А), НА КОТОРОМ "СНИЗУ ВВЕРХ" ИЗОБРАЖЕНЫ~$A_5$, $B_5$, $C_5$,
$D_5$, $E_5$, ДЕМОНСТРИРУЕТ, КАКИМ ОБРАЗОМ ЧИСЛА СЛИЯНИЙ ДЛЯ КАЖДОГО
ОТРЕЗКА ПОЯВЛЯЮТСЯ НА ЛЕНТЕ; ЗАМЕТИМ, ЧТО ОТРЕЗОК В НАЧАЛЕ ЛЮБОЙ ЛЕНТЫ
БУДЕТ ОБРАБАТЫВАТЬСЯ 5~РАЗ, В ТО ВРЕМЯ КАК ОТРЕЗОК В КОНЦЕ~T1 БУДЕТ
ОБРАБАТЫВАТЬСЯ ЛИШЬ ОДНАЖДЫ.
\picture{ЁИС.~71.               рНАЛИЗ МНОГОФАЗНОГО РАСПРЕДЕЛЕНИЯ ПЯТОГО
УРОВНЯ НА ШЕСТИ ЛЕНТАХ: (a)---ЧИСЛА СЛИЯНИЙ; (b)---ОПТИМАЛЬНЫЙ ПОРЯДОК РАСПРЕДЕЛЕНИЯ.}
¤ТА "ДИСКРИМИНАЦИЯ" ПРИ МНОГОФАЗНОМ СЛИЯНИИ ПРИВОДИТ К ТОМУ, ЧТО ФИКТИВНЫЕ
ОТРЕЗКИ ЛУЧШЕ ПОМЕЩАТЬ В НАЧАЛО ЛЕНТЫ, А НЕ В КОНЕЦ. эА РИС.~71~(b)
ПРЕДСТАВЛЕН ОПТИМАЛЬНЫЙ ПОРЯДОК РАСПРЕДЕЛЕНИЯ ОТРЕЗКОВ ДЛЯ СЛУЧАЯ
ПЯТИУРОВНЕВОГО МНОГОФАЗНОГО СЛИЯНИЯ; КАЖДЫЙ НОВЫЙ ОТРЕЗОК ПОМЕЩАЕТСЯ В
ПОЗИЦИЮ С НАИМЕНЬШИМ ИЗ ОСТАВШИХСЯ ЧИСЛОМ СЛИЯНИЙ. чАМЕТИМ, ЧТО АЛГОРИТМ~D
%%328
(РИС.~69) НЕСКОЛЬКО ХУЖЕ, ТАК КАК ОН ЗАПОЛНЯЕТ НЕКОТОРЫЕ
ПОЗИЦИИ~"4" ДО ТОГО, КАК ЗАПОЛНЕНЫ ВСЕ ПОЗИЦИИ~"3".
ЁЕКУРРЕНТНЫЕ СООТНОШЕНИЯ~(8) ПОКАЗЫВАЮТ, ЧТО ВСЕ~$B_n$, $C_n$, $D_n$,
$E_n$ ЯВЛЯЮТСЯ НАЧАЛЬНЫМИ ПОДЦЕПОЧКАМИ~$A_n$. т ДЕЙСТВИТЕЛЬНОСТИ,
ИСПОЛЬЗУЯ~(8), МОЖНО ВЫВЕСТИ ФОРМУЛЫ
$$
\eqalign{
E_n&=(A_{n-1})+1,\cr
D_n&=(A_{n-1}A_{n-2})+1,\cr
C_n&=(A_{n-1}A_{n-2}A_{n-3})+1,\cr
B_n&=(A_{n-1}A_{n-2}A_{n-3}A_{n-4})+1,\cr
A_n&=(A_{n-1}A_{n-2}A_{n-3}A_{n-4}A_{n-5})+1,\cr
}
\eqno(9)
$$
ОБОБЩАЮЩИЕ СООТНОШЕНИЯ~(3), КОТОРЫЕ ИМЕЮТ ДЕЛО ТОЛЬКО С ДЛИНАМИ ЭТИХ
ЦЕПОЧЕК. ъРОМЕ ТОГО, ИЗ ПРАВИЛ, ОПРЕДЕЛЯЮЩИХ  ЦЕПОЧКИ~$A$, СЛЕДУЕТ, ЧТО
СТРУКТУРА В НАЧАЛЕ КАЖДОГО УРОВНЯ, В СУЩНОСТИ, ОДНА И ТА ЖЕ; ИМЕЕМ
$$
A_n=n-Q_n,
\eqno(10)
$$
ГДЕ $Q_n$~ЕСТЬ ЦЕПОЧКА ИЗ $a_n$~ЗНАЧЕНИЙ, ОПРЕДЕЛЯЕМАЯ ЗАКОНОМ
$$
\displaynarrow{
Q_n=Q_{n-1}(Q_{n-2}+1)(Q_{n-3}+2)(Q_{n-4}+3)(Q_{n-5}+4) \rem{ПРИ $n\ge 1$},\cr
Q_0=\hbox{'0'}; Q_n=\hbox{(ПУСТО)} \rem{ПРИ $n<0$.}\cr
}
\eqno(11)
$$
ЄАК КАК~$Q_n$ НАЧИНАЕТСЯ С~$Q_{n-1}$, ТО МОЖНО РАССМОТРЕТЬ
\emph{БЕСКОНЕЧНУЮ} ЦЕПОЧКУ~$Q_\infty$, ПЕРВЫЕ $a_n$~ЭЛЕМЕНТОВ КОТОРОЙ
СОВПАДАЮТ С~$Q_n$; ЭТА ЦЕПОЧКА, ПО СУЩЕСТВУ, ОПИСЫВАЕТ ВСЕ ЧИСЛА СЛИЯНИЙ В
МНОГОФАЗНОМ РАСПРЕДЕЛЕНИИ. т СЛУЧАЕ ШЕСТИ ЛЕНТ ИМЕЕМ
$$
Q_\infty=011212231223233412232334233434412232334233434452334344534454512232\ldots\,.
\eqno  (12)
$$

т УПР.~11 СОДЕРЖИТСЯ ИНТЕРЕСНАЯ ИНТЕРПРЕТАЦИЯ ЭТОЙ ЦЕПОЧКИ.

яРИ УСЛОВИИ ЧТО~$A_n$ ЕСТЬ ЦЕПОЧКА~$m_1m_2\ldots m_{a_n}$, ОБОЗНАЧИМ
ЧЕРЕЗ~$A_n(x)=x^{m_1}+x^{m_2}+\cdots+x^{m_{a_n}}$ СООТВЕТСТВУЮЩУЮ
ПРОИЗВОДЯЩУЮ ФУНКЦИЮ, ОПИСЫВАЮЩУЮ, СКОЛЬКО РАЗ ПОЯВЛЯЕТСЯ КАЖДОЕ  ЧИСЛО
СЛИЯНИЙ; АНАЛОГИЧНО ВВЕДЕМ~$B_n(x)$, $C_n(x)$, $D_n(x)$,
$E_n(x)$. эАПРИМЕР, $A_4(x)=x^4+x^3+x^3+x^2+x^3+x^2+x^2+x=x^4+3x^3+3x^2+x$.
 т СИЛУ СООТНОШЕНИЙ~(9) ИМЕЕМ ПРИ~$n\ge1$
$$
\eqalign{
E_n(x)&=x(A_{n-1}(x)),\cr
D_n(x)&=x(A_{n-1}(x)+A_{n-2}(x)),\cr
C_n(x)&=x(A_{n-1}(x)+A_{n-2}(x)+A_{n-3}(x)),\cr
B_n(x)&=x(A_{n-1}(x)+A_{n-2}(x)+A_{n-3}(x)+A_{n-4}(x)),\cr
A_n(x)&=x(A_{n-1}(x)+A_{n-2}(x)+A_{n-3}(x)+A_{n-4}(x)+A_{n-5}(x)),\cr
}
\eqno(13)
$$
%%329
ГДЕ~$A_0(x)=1$ И~$A_n(x)=0$ ПРИ~$n=-1$, $-2$, $-3$, $-4$. ёЛЕДОВАТЕЛЬНО,
$$
\sum_{n\ge 0} A_n(x)z^n={1\over 1-x(z+z^2+z^3+z^4+z^5)}=
\sum_{k\ge 0} x^k(z+z^2+z^3+z^4+z^5)^k.
\eqno(14)
$$
ЁАССМАТРИВАЯ ОТРЕЗКИ НА ВСЕХ ЛЕНТАХ, ПОЛОЖИМ
$$
T_n(x)=A_n(x)+B_n(x)+C_n(x)+D_n(x)+E_n(x), \qquad n\ge 1;
\eqno (15)
$$
ИЗ~(13) НЕМЕДЛЕННО ПОЛУЧАЕМ
$$
T_n(x)=5A_{n-1}(x)+4A_{n-2}(x)+3A_{n-3}(x)+2A_{n-4}(x)+A_{n-5}(x),
$$
А ЗНАЧИТ, И
$$
\sum_{n\ge 1} T_n(x)z^n=
{x(5z+4z^2+3z^3+2z^4+z^5)\over 1-x(z+z^2+z^3+z^4+z^5)}.
\eqno(16)
$$

ёООТНОШЕНИЕ~(16) ПОКАЗЫВАЕТ, ЧТО ЛЕГКО ВЫЧИСЛИТЬ КОЭФФИЦИЕНТЫ~$T_n(x)$:
$$
\matrix{
 & z &z^2 & z^3 & z^4 & z^5 & z^6 & z^7 & z^8 & z^9 & z^{10} & z^{11} & z^{12} & z^{13} & z^{14} \cr
x & 5 & 4 & 3 & 2 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \cr
x^2 & 0 & 5 & 9 & 12 & 14 & 15 & 10 &  6 &  3 &  1 &  0 &  0 &  0 & 0 \cr
x^3 & 0 & 0 & 5 & 14 & 26 & 40 & 55 & 60 & 57 & 48 & 35 & 20 & 10 & 4 \cr
x^4 & 0 & 0 & 0 &  5 & 19 & 45 & 85 & 140 & 195 & 238 & 260 & 255 & 220 & 170\cr
x^5 & 0 & 0 & 0 &  0 &  5 & 24 & 69 & 154 & 294 & 484 & 703 & 918  & 1088
& 1168 \cr
}
\eqno(17)
$$
ёТОЛБЦЫ ЭТОЙ ТАБЛИЦЫ ДАЮТ~$T_n(x)$; НАПРИМЕР, $T_4(x)=2x+12x^2+14x^3+5x^4$.
ъАЖДЫЙ ЭЛЕМЕНТ ЭТОЙ ТАБЛИЦЫ (КРОМЕ ЭЛЕМЕНТОВ ПЕРВОЙ СТРОКИ) ЯВЛЯЕТСЯ
СУММОЙ ПЯТИ ЭЛЕМЕНТОВ, РАСПОЛОЖЕННЫХ В ПРЕДЫДУЩЕЙ СТРОКЕ НЕПОСРЕДСТВЕННО
ЛЕВЕЕ НЕГО.

ўИСЛО ОТРЕЗКОВ В ТОЧНОМ РАСПРЕДЕЛЕНИИ $n\hbox{-ГО}$~УРОВНЯ РАВНО~$T_n(1)$,
А ОБЩЕЕ КОЛИЧЕСТВО ОБРАБАТЫВАЕМЫХ ОТРЕЗКОВ В ПРОЦЕССЕ ИХ СЛИЯНИЯ РАВНО
ПРОИЗВОДНОЙ~$T'_n(1)$. фАЛЕЕ,
$$
\sum_{n\ge 1} T'_n(x)z^n=
{5z+4z^2+3z^3+2z^4+z^5\over (1-x(z+z^2+z^3+z^4+z^5))^2};
\eqno(18)
$$
ПОЛАГАЯ~$x=1$ В~(16) И~(18), ПОЛУЧАЕМ, ЧТО ЧИСЛО СЛИЯНИЙ ДЛЯ ТОЧНОГО
РАСПРЕДЕЛЕНИЯ П-ГО УРОВНЯ ЕСТЬ КОЭФФИЦИЕНТ ПРИ~$z^n$ В~$a(z)t(z)$
[СР.~(7)]. ¤ТО СОГЛАСУЕТСЯ С НАШИМИ ПРЕДЫДУЩИМИ РАССУЖДЕНИЯМИ.

ЇУНКЦИИ~$T_n(x)$ МОЖНО ИСПОЛЬЗОВАТЬ ДЛЯ ОПРЕДЕЛЕНИЯ СОВЕРШАЕМОЙ РАБОТЫ,
КОГДА ФИКТИВНЫЕ ОТРЕЗКИ ДОБАВЛЯЮТСЯ ОПТИМАЛЬНЫМ ОБРАЗОМ. яУСТЬ~$\sum_n (m)$
ЕСТЬ СУММА НАИМЕНЬШИХ $m$~ЧИСЕЛ СЛИЯНИЙ В РАСПРЕДЕЛЕНИИ
$n\hbox{-ГО}$~УРОВНЯ. яОСМОТРЕВ НА СТОЛБЦЫ~(17),
%%330
МЫ БЕЗ ТРУДА ВЫЧИСЛИМ ЭТИ СУММЫ~$\sum_n(m)$:
{\let\i=\infty
$$\vcenter{\halign{
$#$\bskip&&\bskip\hfill$#$\bskip\cr
\span m=1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 \cr
n=1 & 1 & 2 & 3 & 4 & 5 & \i & \i & \i & \i & \i & \i & \i & \i & \i & \i& \i & \i & \i & \i & \i & \i \cr
n=2 & 1 & 2 & 3 & 4 & Б & 8 & 10  & 12 & 14 & \i & \i & \i & \i & \i & \i & \i & \i & \i & \i & \i & \i \cr
n=3 & 1 & 2 & 3 & 5 & 7 & 9 & 11 & 13 & 15 & 17 & 19 & 21 & 24 & 27 & 30 &33 & 36 & \i & \i & \i & \i \cr
n=4 & 1 & 2 & 4 & 6 & 8 & 10 & 12 & 14 & 16 & 18 & 20 & 22 & 24 & 26 & 29& 32 & 35 & 38 & 41 & 44 & 47 \cr
n=5 & 1 & 3 & 5 & 7 & 9 & 11 & 13 & 15 & 17 & 19 & 21 & 23 & 25 & 27 & 29& 32 & 35 & 38 & 41 & 44 & 47 \cr
n=6 & 2 & 4 & 6 & 8 & 10 & 12 & 14 & 16 & 18 & 20 & 22 & 24 & 26 & 28 & 30 & 33 & 36 & 38 & 42 & 45 & 48 \cr
n=7 & 2 & 4 & 6 & 8 & 10 & 12 & 14 & 16 & 18 & 20 & 23 & 26 & 29 & 32 & 35 & 38 & 41 & 44 & 47 & 50 & 53 \cr
}}
\eqno(19)
$$}%
эАПРИМЕР, ЕСЛИ МЫ ХОТИМ ОТСОРТИРОВАТЬ 17~ОТРЕЗКОВ, ИСПОЛЬЗУЯ
РАСПРЕДЕЛЕНИЕ 3-ГО~УРОВНЯ, ТО ОБЩЕЕ КОЛИЧЕСТВО ОПЕРАЦИЙ ЕСТЬ~$\sum_3
(17)=36$, НО ЕСЛИ ИСПОЛЬЗОВАТЬ РАСПРЕДЕЛЕНИЕ~4-ГО ИЛИ 5-ГО~УРОВНЯ, ТО
ОБЩЕЕ КОЛИЧЕСТВО ОПЕРАЦИЙ В ПРОЦЕССЕ СЛИЯНИЯ БУДЕТ
ТОЛЬКО~$\sum_4(17)=\sum_5 (17)=35$. тЫГОДНЕЕ ИСПОЛЬЗОВАТЬ УРОВЕНЬ~4,
ХОТЯ ЧИСЛО~17 СООТВЕТСТВУЕТ ТОЧНОМУ РАСПРЕДЕЛЕНИЮ 3-ГО~УРОВНЯ! т САМОМ
ДЕЛЕ, ПО. МЕРЕ ВОЗРАСТАНИЯ~$S$ ОПТИМАЛЬНЫЙ НОМЕР УРОВНЯ ОКАЗЫВАЕТСЯ
ЗНАЧИТЕЛЬНО БОЛЬШЕ, ЧЕМ ИСПОЛЬЗУЕМЫЙ В АЛГОРИТМЕ~D.

єПРАЖНЕНИЕ~14 ПОКАЗЫВАЕТ, ЧТО СУЩЕСТВУЕТ НЕУБЫВАЮЩАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ
ЧИСЕЛ~$M_n$, ТАКАЯ, ЧТО УРОВЕНЬ~$n$ ОПТИМАЛЕН ДЛЯ~$M_n\le S < M_{n+1}$, НО
НЕ ДЛЯ~$S\ge M_{n+1}$. т СЛУЧАЕ ШЕСТИ ЛЕНТ ТОЛЬКО ЧТО ВЫЧИСЛЕННАЯ
ТАБЛИЦА~$\sum_n (m)$ ДАЕТ
$$
M_0=0,\quad M_1=2,\quad M_2=6,\quad M_3=10,\quad M_4=14.
$$
тЫШЕ МЫ ИМЕЛИ ДЕЛО ТОЛЬКО СО СЛУЧАЕМ ШЕСТИ ЛЕНТ, ОДНАКО ЯСНО, ЧТО ТЕ ЖЕ
ИДЕИ ПРИМЕНИМЫ К МНОГОФАЗНОЙ СОРТИРОВКЕ С~$T$~ЛЕНТАМИ ДЛЯ ЛЮБОГО~$T\ge3$;
ПРОСТО В СООТВЕТСТВУЮЩИХ МЕСТАХ НАДО ЗАМЕНИТЬ~5 НА~$P=T-1$. т ТАБЛ.~2
ИЗОБРАЖЕНЫ ПОСЛЕДОВАТЕЛЬНОСТИ~$M_n$, ПОЛУЧЕННЫЕ ДЛЯ РАЗЛИЧНЫХ
ЗНАЧЕНИЙ~$T$. ЄАБЛИЦА~3 И РИС.~72 ДАЮТ ПРЕДСТАВЛЕНИЕ ОБ ОБЩЕМ
КОЛИЧЕСТВЕ ОБРАБАТЫВАЕМЫХ НАЧАЛЬНЫХ ОТРЕЗКОВ ПОСЛЕ ВЫПОЛНЕНИЯ
ОПТИМАЛЬНОГО РАСПРЕДЕЛЕНИЯ ФИКТИВНЫХ ОТРЕЗКОВ. (ЇОРМУЛЫ ВНИЗУ
ТАБЛ.~3 СЛЕДУЕТ ПРИНИМАТЬ С ОСТОРОЖНОСТЬЮ, ТАК КАК ЭТО ПРИБЛИЖЕНИЕ ПО
МЕТОДУ НАИМЕНЬШИХ КВАДРАТОВ НА ОБЛАСТИ~$1\le S \le 5000$
($1\le S \le 10\, 000$ ПРИ~$T=3$), ЧТО ПРИВОДИТ К НЕКОТОРОМУ ОТКЛОНЕНИЮ,
ПОСКОЛЬКУ ДАННАЯ ОБЛАСТЬ ЗНАЧЕНИЙ~$S$ НЕ ЯВЛЯЕТСЯ ОДИНАКОВО ПОДХОДЯЩЕЙ ДЛЯ
ВСЕХ~$T$. яРИ~$S\to\infty$ ЧИСЛО ОБРАБАТЫВАЕМЫХ НАЧАЛЬНЫХ ОТРЕЗКОВ ПОСЛЕ
ОПТИМАЛЬНОГО МНОГОФАЗНОГО РАСПРЕДЕЛЕНИЯ АСИМПТОТИЧЕСКИ РАВНО~$S\log_p S$,
НО СХОДИМОСТЬ К ЭТОМУ АСИМПТОТИЧЕСКОМУ ПРЕДЕЛУ КРАЙНЕ МЕДЛЕННАЯ.)

яРИ ПОМОЩИ ТАБЛ.~4 МОЖНО СРАВНИТЬ МЕТОД РАСПРЕДЕЛЕНИЯ АЛГОРИТМА~D С
РЕЗУЛЬТАТАМИ ОПТИМАЛЬНОГО РАСПРЕДЕЛЕНИЯ, ПРИВЕДЕННЫМИ В ТАБЛ.~3. ▀СНО,
ЧТО АЛГОРИТМ~D НЕ ОЧЕНЬ БЛИЗОК К ОПТИМАЛЬНОМУ ПРИ БОЛЬШИХ~$S$ И~$T$;
ОДНАКО НЕПОНЯТНО, МОЖНО ЛИ ПОСТУПИТЬ В ЭТИХ СЛУЧАЯХ СУЩЕСТВЕННО ЛУЧШЕ
АЛГОРИТМА~D, НЕ ПРИБЕГАЯ К ЗНАЧИТЕЛЬНЫМ УСЛОЖНЕНИЯМ, ОСОБЕННО ЕСЛИ МЫ НЕ
%%331
ЗНАЕМ~$S$ ЗАРАНЕЕ. ъ СЧАСТЬЮ, ЗАБОТИТЬСЯ О БОЛЬШИХ~$S$ ПРИХОДИТСЯ ДОВОЛЬНО
РЕДКО (СМ.~П.~5.4.6), ТАК ЧТО АЛГОРИТМ~D НА ПРАКТИКЕ НЕ ТАК УЖ ПЛОХ, НА
САМОМ ДЕЛЕ---ДАЖЕ ВЕСЬМА НЕПЛОХ.

ьАТЕМАТИЧЕСКИ МНОГОФАЗНАЯ СОРТИРОВКА ВПЕРВЫЕ БЫЛА ПРОАНАЛИЗИРОВАНА
є.~ъ.~ъАРТЕРОМ [ЁГОС.\ IFIP Congress (1962), 62--66].
\picture{ЁИС.~72.  ¤ФФЕКТИВНОСТЬ МНОГОФАЗНОГО СЛИЯНИЯ С ОПТИМАЛЬНЫМ
НАЧАЛЬНЫМ РАСПРЕДЕЛЕНИЕМ (СР.~С~РИС.~70).}

ьНОГИЕ ИЗ ПРИВЕДЕННЫХ РЕЗУЛЬТАТОВ ОТНОСИТЕЛЬНО ОПТИМАЛЬНОГО РАЗМЕЩЕНИЯ
ФИКТИВНЫХ ОТРЕЗКОВ ПРИНАДЛЕЖАТ с.~ёЭКМАНУ И~Є.~ёИНГЛЕРУ [A vector model
for merge sort analisis, НЕОПУБЛИКОВАННЫЙ ДОКЛАД, ПРЕДСТАВЛЕННЫЙ НА
СИМПОЗИУМ~ACM ПО СОРТИРОВКЕ (НОЯБРЬ 1962), СТР.~21]. яОЗДНЕЕ ёЭКМАН
ПРЕДЛОЖИЛ ГОРИЗОНТАЛЬНЫЙ МЕТОД РАСПРЕДЕЛЕНИЯ, ИСПОЛЬЗУЕМЫЙ В
АЛГОРИТМЕ~D; фОНАЛЬД °ЕЛЛ [{\sl CACM,\/} {\bf 14} (1971), 713--719; {\bf
15} (1972), 28], НЕЗАВИСИМО РАЗВИВ ЭТУ ТЕОРИЮ, УКАЗАЛ НА
СООТНОШЕНИЕ~(10) И ПОДРОБНО ИЗУЧИЛ НЕСКОЛЬКО РАЗЛИЧНЫХ АЛГОРИТМОВ
РАСПРЕДЕЛЕНИЯ. фАЛЬНЕЙШИЕ ПОЛЕЗНЫЕ УСОВЕРШЕНСТВОВАНИЯ И УПРОЩЕНИЯ БЫЛИ
ПОЛУЧЕНЫ фЕРЕКОМ~¤.~чЭЙВОМ [{\sl JACM,\/} БУДЕТ ОПУБЛИКОВАНО].
%%332
\htable{ЄАБЛИЦА 2}%
{ўИСЛО ОТРЕЗКОВ, ПРИ КОТОРОМ ДАННЫЙ УРОВЕНЬ ОПТИМАЛЕН}
{
\hfill$#$\bskip&\hfill\bskip$#$\bskip&\hfill\bskip$#$\bskip&\hfill\bskip$#$\bskip&\hfill\bskip$#$\bskip&\hfill\bskip$#$\bskip&\hfill\bskip$#$\bskip&\hfill\bskip$#$\bskip&\hfill\bskip$#$\bskip&\bskip$#$\hfill\cr
\hbox{єРОВЕНЬ}& T=3 & T=4 & T=5 & T=6 & T=7 & T=8 & T=9 & T=10\cr
\noalign{\hrule}
 1 &  2 &  2 &  2 &  2 &  2 &  2 &  2 &  2 & M_1 \cr
 2 &  3 &  4 &  5 &  6 &  7 &  8 &  9 & 10 & M_2 \cr
 3 &  4 &  6 &  8 & 10 & 12 & 14 & 16 & 18 & M_3 \cr
 4 &  6 & 10 & 14 & 14 & 17 & 20 & 23 & 26 & M_4 \cr
 5 &  9 & 18 & 23 & 29 & 20 & 24 & 28 & 32 & M_5 \cr
 6 & 14 & 32 & 35 & 43 & 53 & 27 & 32 & 37 & M_6 \cr
 7 & 22 & 55 & 76 & 61 & 73 & 88 & 35 & 41 & M_7 \cr
 8 & 35 & 96 &109 &194 & 98 &115 &136 & 44 & M_8 \cr
 9 & 56 &173 &244 &216 &283 &148 &171 &199 & M_9 \cr
10 & 90 &280 &359 &269 &386 &168 &213 &243 & M_{10}\cr
11 &145 &535 &456 &779 &481 &640 &240 &295 & M_{11}\cr
12 &234 &820 &1197&1034&555 &792 &1002&330 & M_{12}\cr
13 &378 &1635&1563&1249&1996&922 &1228&1499& M_{13}\cr
14 &611 &2401&4034&3910&2486&1017&1432&1818& M_{14}\cr
15 &988 &4959&5379&4970&2901&4397&1598&2116& M_{15}\cr
16 &1598&7029&6456&5841&10578&5251&1713&2374&M_{16}\cr
17 &2574&14953&18561&19409&13097&5979&8683&2576&M_{17}\cr
18 &3955&20583&22876&23918&15336&6499&10069&2709&M_{18}\cr
19 &6528&44899&64189&27557&17029&30164&11259&15787& M_{19}\cr
\noalign{\hrule}
}


{\def\m#1#2{\matrix{\hfill #1\cr\hfill #2\cr}}
\htable{ЄАБЛИЦА~3}%
{ўИСЛО НАЧАЛЬНЫХ ОТРЕЗКОВ, ОБРАБАТЫВАЕМЫХ ПРИ ОПТИМАЛЬНОМ \nl МНОГОФАЗНОМ СЛИЯНИИ}%
{\hfill$#$\bskip&&\hfill\bskip$#$\bskip\cr
   S&  T=3 &  T=4 &  T=5 &  T=6 &  T=7 &  T=8 &  T=9 & T=10\cr
\noalign{\hrule}
  10&    36&    24&    19&    17&    15&    14&    13&    12\cr
  20&    90&    60&    49&    44&    38&    36&    34&    33\cr
  50&   294&   194&   158&   135&   128&   121&   113&   104\cr
 100&   702&   454&   362&   325&   285&   271&   263&   254\cr
1000& 10371&  6680&  5430&  4672&  4347&  3872&  3739&  3632\cr
5000& 63578& 41286& 32905& 28620& 26426& 23880& 23114& 22073\cr
\multispan{2} \hfil$
\displaystyle
S\left\{\matrix{
\hfill  (1.51\cr
\hfill +(-.11\cr
}\right.
$ &
\m{0.951}{+.14} & \m{0.761}{+.16} & \m{0.656}{+.19} & \m{0.589}{+.21} &
\m{0.548}{+.20} & \m{0.539}{+.02} &
\multispan{2}
\hfill\bskip$\displaystyle\vcenter{\halign{\hfil$#$&$\hbox{}#$\hfil\cr
0.488)&\cdot S \ln S \cr
+.18)&\cdot S \cr
}}$
\cr
\noalign{\hrule}
}}
яРОИЗВОДЯЩАЯ ФУНКЦИЯ~(16) БЫЛА ВПЕРВЫЕ ИССЛЕДОВАНА є.~сУРЖЕМ
[ЁГОС. IFIP Congress (1971), I, 454--459].

\qsection р КАК ОБСТОИТ ДЕЛО С ВРЕМЕНЕМ ПЕРЕМОТКИ? фО СИХ ПОР МЫ
ИСПОЛЬЗОВАЛИ "ОБРАБАТЫВАЕМЫЕ НАЧАЛЬНЫЕ ОТРЕЗКИ" КАК ЕДИНСТВЕННУЮ МЕРУ
ЭФФЕКТИВНОСТИ ДЛЯ СРАВНЕНИЯ СТРАТЕГИЙ ЛЕНТОЧНОГО СЛИЯНИЯ. эО ПОСЛЕ
КАЖДОЙ ИЗ ФАЗ~2--6 В ПРИМЕРАХ В НАЧАЛЕ ЭТОГО ПУНКТА ¤ть ДОЛЖНА ОЖИДАТЬ
ПЕРЕМОТКИ ДВУХ ЛЕНТ;
КАК ПРЕДЫДУЩАЯ ВЫВОДНАЯ ЛЕНТА, ТАК И НОВАЯ ТЕКУЩАЯ ВЫВОДНАЯ
%%333
\htable{ЄАБЛИЦА~4}%
{ўИСЛО НАЧАЛЬНЫХ ОТРЕЗКОВ, ОБРАБАТЫВАЕМЫХ ПРИ СТАНДАРТНОМ \nl МНОГОФАЗНОМ СЛИЯНИИ}%
{\hfill$#$\bskip&&\hfill\bskip$#$\bskip\cr
   S&  T=3 &  T=4 &  T=5 &  T=6 &  T=7 &  T=8 &  T=9 & T=10\cr
\noalign{\hrule}
  10&    36&    24&    19&    17&    15&    14&    13&    12\cr
  20&    90&    62&    49&    44&    41&    37&    34&    33\cr
  50&   294&   194&   167&   143&   134&   131&   120&   114\cr
 100&   714&   459&   393&   339&   319&   312&   292&   277\cr
1000& 10730&  6920&  5774&  5370&  4913&  4716&  4597&  4552\cr
5000& 64740& 43210& 36497& 32781& 31442& 29533& 28817& 28080\cr
\noalign{\hrule}
}
ЛЕНТА ДОЛЖНЫ БЫТЬ ПЕРЕМОТАНЫ В НАЧАЛО, ПРЕЖДЕ ЧЕМ СМОЖЕТ ВЫПОЛНЯТЬСЯ
СЛЕДУЮЩАЯ ФАЗА. ¤ТО МОЖЕТ ВЫЗВАТЬ СУЩЕСТВЕННУЮ ЗАДЕРЖКУ, ТАК КАК В ОБЩЕМ
СЛУЧАЕ ПРЕДЫДУЩАЯ ВЫВОДНАЯ ЛЕНТА СОДЕРЖИТ ЗНАЧИТЕЛЬНЫЙ ПРОЦЕНТ СОРТИРУЕМЫХ
ЗАПИСЕЙ (СМ. СТОЛБЕЦ "ПРОХОДЫ/ФАЗЫ" В ТАБЛ.~1). фОСАДНО, КОГДА ¤ть
ПРОСТАИВАЕТ ВО ВРЕМЯ ОПЕРАЦИЙ ПЕРЕМОТКИ, ТОГДА КАК МОЖНО БЫЛО БЫ,
ИСПОЛЬЗУЯ ИНУЮ СХЕМУ СЛИЯНИЯ, ВЫПОЛНИТЬ ПОЛЕЗНУЮ РАБОТУ С ОСТАЛЬНЫМИ ЛЕНТАМИ.

¤ТУ ЗАДАЧУ РЕШАЕТ ПРОСТАЯ МОДИФИКАЦИЯ МНОГОФАЗНОЙ ПРОЦЕДУРЫ, ХОТЯ ОНА
ТРЕБУЕТ НЕ МЕНЕЕ ПЯТИ ЛЕНТ [СМ.~ДИССЕРТАЦИЮ ш.~ёЕЗАРИ (Univ.~of~Paris
(1968), 25--27), ГДЕ ЭТА ИДЕЯ ПРИПИСЫВАЕТСЯ фЖ.~ъЭЙРОНУ]. ъАЖДАЯ ФАЗА
СХЕМЫ ъЭЙРОНА СЛИВАЕТ  ОТРЕЗКИ С $(T-3)$~ЛЕНТ НА НЕКОТОРУЮ ДРУГУЮ ЛЕНТУ, В
ТО ВРЕМЯ КАК ОСТАЮЩИЕСЯ ДВЕ ЛЕНТЫ ПЕРЕМАТЫВАЮТСЯ.

ЁАССМОТРИМ, НАПРИМЕР, СЛУЧАЙ ШЕСТИ ЛЕНТ И 49~НАЧАЛЬНЫХ ОТРЕЗКОВ. т
СЛЕДУЮЩЕЙ ТАБЛИЦЕ БУКВОЙ~$R$ ПОМЕЧЕНЫ ЛЕНТЫ, ПЕРЕМАТЫВАЮЩИЕСЯ ВО ВРЕМЯ
ДАННОЙ ФАЗЫ; ПРЕДПОЛАГАЕТСЯ, ЧТО $T5$~СОДЕРЖИТ ПЕРВОНАЧАЛЬНЫЕ ОТРЕЗКИ:
\ctable{
\hfill$#$\bskip&&\bskip\hfill$#$\hfill\bskip\cr
\omit\hfill ЇАЗА\hfill & T1 & T2 & T3 & T4 & T5 & T6 & \omit\hfill тРЕМЯ ЗАПИСИ  \hfill & \omit\hfill тРЕМЯ ПЕРЕМОТКИ \hfill \cr
 1&1^{11}&1^{17}&1^{13}& 1^8& -   & (R)   & 49           & 17\cr
 2&   (R)&   1^9&   1^5&   -& R   & 3^8   & 8\times  3=24& 49-17=32\cr
 3&   1^6&   1^4&   -  &   R& 3^5 &  R    & 5\times  3=15& \max(8,24)\cr
 4&   1^2&     -&    R & 5^4& R   & 3^4   & 4\times  5=20& \max(13,15)\cr
 5&   -  &     R&   7^2&   R& 3^3 & 3^2   & 2\times  7=14& \max(17,20)\cr
 6&    R &  11^2&     R& 5^2& 3^1 & -     & 2\times 11=22& \max(11,14)\cr
 7&  15^1&     R&   7^1& 5^1& -   & R     & 1\times 15=15& \max(22,24)\cr
 8&  R   &  11^1&   7^0&   -& R   & 23^1  & 1\times 23=23& \max(15,16)\cr
 9& 15^1 &  11^1&     -&   R& 33^0& R     & 0\times 33= 0& \max(20,23)\cr
10&(15^0)&     -&     R&49^1& (R) & (23^0)& 1\times 49=49& 14\cr
}
чДЕСЬ ВСЕ ПЕРЕМОТКИ, ПО СУЩЕСТВУ, СОВМЕЩЕНЫ; ЗА ИСКЛЮЧЕНИЕМ ФАЗЫ~9
("ФИКТИВНАЯ ФАЗА", КОТОРАЯ ПОДГОТАВЛИВАЕТ ОКОНЧАТЕЛЬНОЕ СЛИЯНИЕ) И
ПЕРЕМОТКИ ПОСЛЕ НАЧАЛЬНОЙ ФАЗЫ РАСПРЕДЕЛЕНИЯ (КОГДА ПЕРЕМАТЫВАЮТСЯ ВСЕ
ЛЕНТЫ). хСЛИ $t$~ЕСТЬ ВРЕМЯ, НЕОБХОДИМОЕ
%%334
ДЛЯ СЛИЯНИЯ ТАКОГО КОЛИЧЕСТВА ЗАПИСЕЙ, КАКОЕ СОДЕРЖИТСЯ В ОДНОМ
НАЧАЛЬНОМ ОТРЕЗКЕ, А $r$---ВРЕМЯ ПЕРЕМОТКИ НА ОДИН НАЧАЛЬНЫЙ ОТРЕЗОК, ТО
ЭТОТ ПРОЦЕСС ТРАТИТ ОКОЛО~$182t+40r$ ПЛЮС ВРЕМЯ НАЧАЛЬНОГО РАСПРЕДЕЛЕНИЯ И
ЗАВЕРШАЮЩЕЙ ПЕРЕМОТКИ. ёООТВЕТСТВУЮЩИЕ ВЫРАЖЕНИЯ ДЛЯ СТАНДАРТНОГО
МНОГОФАЗНОГО МЕТОДА, ИСПОЛЬЗУЮЩЕГО АЛГОРИТМ~D, ЕСТЬ~$140t+104r$, ЧТО
НЕСКОЛЬКО ХУЖЕ, ЕСЛИ~$r={3\over 4}t$, И НЕСКОЛЬКО ЛУЧШЕ, ЕСЛИ~$r={1\over2}t$.

тСЕ СКАЗАННОЕ О СТАНДАРТНОМ МНОГОФАЗНОМ МЕТОДЕ ПРИЛОЖИМО К МНОГОФАЗНОМУ
МЕТОДУ ъЭЙРОНА; НАПРИМЕР, ПОСЛЕДОВАТЕЛЬНОСТЬ~$a_n$ ТЕПЕРЬ УДОВЛЕТВОРЯЕТ
РЕКУРРЕНТНОМУ СООТНОШЕНИЮ
$$
a_n=a_{n-2}+a_{n-3}+a_{n-4}
\eqno  (20)
$$
ВМЕСТО~(3). ўИТАТЕЛЮ БУДЕТ ПОЛЕЗНО ПРОАНАЛИЗИРОВАТЬ ЭТОТ МЕТОД ТАКИМ ЖЕ
ОБРАЗОМ, КАК МЫ АНАЛИЗИРОВАЛИ СТАНДАРТНЫЙ МНОГОФАЗНЫЙ, ТАК КАК ЭТО
УЛУЧШИТ ПОНИМАНИЕ ОБОИХ МЕТОДОВ (СМ., НАПРИМЕР, УПР.~19 И~20).

т ТАБЛ.~5 СВЕДЕНЫ ФАКТЫ О МНОГОФАЗНОМ МЕТОДЕ ъЭЙРОНА, АНАЛОГИЧНЫЕ ФАКТАМ
ОБ ОБЫЧНОМ МНОГОФАЗНОМ МЕТОДЕ, ПРИВЕДЕННЫМ В ТАБЛ.~1. чАМЕТИМ, ЧТО. НА
САМОМ ДЕЛЕ ПРИ ВОСЬМИ И БОЛЕЕ. ЛЕНТАХ МЕТОД ъЭЙРОНА СТАНОВИТСЯ
\emph{ЛУЧШЕ} МНОГОФАЗНОГО КАК ПО ЧИСЛУ ОБРАБАТЫВАЕМЫХ ОТРЕЗКОВ, ТАК И ПО
ВРЕМЕНИ ПЕРЕМОТКИ, НЕСМОТРЯ НА ТО ЧТО ОН ВЫПОЛНЯЕТ $(T-3)\hbox{-ПУТЕВОЕ}$
СЛИЯНИЕ ВМЕСТО $(T-1)\hbox{-ПУТЕВОГО}$!

¤ТО МОЖЕТ КАЗАТЬСЯ, ПАРАДОКСАЛЬНЫМ, ПОКА МЫ НЕ ПОЙМЕМ, ЧТО \emph{ВЫСОКИЙ
ПОРЯДОК СЛИЯНИЯ НЕ ОБЯЗАТЕЛЬНО ОЗНАЧАЕТ ЭФФЕКТИВНУЮ СОРТИРОВКУ.} т
КАЧЕСТВЕ КРАЙНЕГО РАССМОТРИМ СЛУЧАЙ, КОГДА НА ЛЕНТУ~T1 ПОМЕЩАЕТСЯ
1~ОТРЕЗОК И $n$~ОТРЕЗКОВ---НА~T2, T3,
\htable{ЄАБЛИЦА 5}%
{яРИБЛИЗИТЕЛЬНОЕ ПОВЕДЕНИЕ МНОГОФАЗНОГО СЛИЯНИЯ ъЭЙРОНА}%
{
\hfill$#$\bskip&&\bskip\hfill$#$\hfill\bskip\cr
\hbox{ыЕНТЫ} & \hbox{ЇАЗЫ} & \hbox{яРОХОДЫ} & \hbox{яРОХОДЫ/ФАЗЫ,} & \hbox{юТНОШЕНИЕ}\cr
             &             &                & \hbox{В ПРОЦЕНТАХ}   &
\hbox{РОСТА} \cr
\noalign{\hrule}
 5& 3.566 \ln S +0.158 & 1.463 \ln S + 1.016 & 41 & 1.3247180\cr
 6& 2.616 \ln S -0.166 & 0.951 \ln S + 1.014 & 36 & 1.4655712\cr
 7& 2.337 \ln S -0.472 & 0.781 \ln S + 1.001 & 33 & 1.5341577\cr
 8& 2.216 \ln S -0.762 & 0.699 \ln S + 0.980 & 32 & 1.5701473\cr
 9& 2.156 \ln S -1.034 & 0.654 \ln S + 0.954 & 30 & 1.5900054\cr
10& 2.124 \ln S -1.290 & 0.626 \ln S + 0.922 & 29 & 1.6013473\cr
20& 2.078 \ln S -3.093 & 0.575 \ln S + 0.524 & 28 & 1.6179086\cr
\noalign{\hrule}
}
T4, T5; ЕСЛИ МЫ БУДЕМ ПООЧЕРЕДНО ВЫПОЛНЯТЬ СЛИЯНИЯ НА~T6 И~T1, ПОКА T2, T3,
T4, T5 НЕ СТАНУТ ПУСТЫМИ, ТО ВРЕМЯ ОБРАБОТКИ БУДЕТ РАВНО
$(2n^2+3n)$~ДЛИНАМ НАЧАЛЬНЫХ ОТРЕЗКОВ, Т.~Е., ПО СУЩЕСТВУ,
ПРОПОРЦИОНАЛЬНО~$S^2$, А НЕ~$S\log S$, ХОТЯ ВСЕ ВРЕМЯ ПРОИЗВОДИТСЯ
ПЯТИПУТЕВОЕ СЛИЯНИЕ.

%%335

\section ЁАСЩЕПЛЕНИЕ ЛЕНТ. ¤ФФЕКТИВНОЕ СОВМЕЩЕНИЕ ВРЕМЕНИ
ПЕРЕМОТКИ ЯВЛЯЕТСЯ ПРОБЛЕМОЙ, ВОЗНИКАЮЩЕЙ ВО МНОГИХ ПРИЛОЖЕНИЯХ, А НЕ
ТОЛЬКО В СОРТИРОВКЕ; СУЩЕСТВУЕТ ОБЩИЙ ПОДХОД, КОТОРЫЙ ЧАСТО МОЖЕТ БЫТЬ
ИСПОЛЬЗОВАН. ЁАССМОТРИМ ИТЕРАТИВНЫЙ ПРОЦЕСС, КОТОРЫЙ ИСПОЛЬЗУЕТ ЛЕНТЫ
СЛЕДУЮЩИМ ОБРАЗОМ:
\ctable{
#\bskip\hfill&&\bskip#\bskip\hfill\cr
      &\omit\hfill T1 \hfill&\omit\hfill T2 \hfill\cr
ЇАЗА~1& тЫВОД~1   & \omit\hfill $-$ \hfill \cr
      & яЕРЕМОТКА & \omit\hfill $-$ \hfill \cr
ЇАЗА~2& тВОД~1    & тЫВОД~2\cr
      & яЕРЕМОТКА & яЕРЕМОТКА\cr
ЇАЗА~3& тЫВОД~3   & тВОД~2\cr
      & яЕРЕМОТКА & яЕРЕМОТКА\cr
ЇАЗА~4& тВОД~3    & тЫВОД~4\cr
      & яЕРЕМОТКА & яЕРЕМОТКА\cr
}
И Т. Д., ГДЕ "ВЫВОД~$k$" ОЗНАЧАЕТ ЗАПИСЬ В $k$-Й ВЫВОДНОЙ ФАЙЛ, А
"ВВОД~$k$" ОЗНАЧАЕТ ЕГО ЧТЕНИЕ. ьОЖНО УСТРАНИТЬ ВРЕМЯ ПЕРЕМОТКИ, ЕСЛИ
ИСПОЛЬЗОВАТЬ ТРИ ЛЕНТЫ, КАК БЫЛО ПРЕДЛОЖЕНО ъ.~тЕЙСЕРТОМ
[{\sl CACM,\/} {\bf 5} (1962), 102]:
\ctable{
#\bskip\hfill&&\bskip#\bskip\hfill\cr
      &\omit\hfill T1 \hfill&\omit\hfill T2 \hfill& \omit\hfill T3 \hfill\cr
ЇАЗА~1 & тЫВОД~1.1 & \omit\hfill $-$ \hfill & \omit\hfill $-$ \hfill\cr
       & тЫВОД~1.2 & \omit\hfill $-$ \hfill & \omit\hfill $-$ \hfill\cr
       & яЕРЕМОТКА & тЫВОД~1.3 & \omit\hfill $-$ \hfill\cr
ЇАЗА~2 & тВОД~1.1  & тЫВОД~2.1 & \omit\hfill $-$ \hfill\cr
       & тВОД~1.2  & яЕРЕМОТКА & тЫВОД~2.2\cr
       & яЕРЕМОТКА & тВОД~1.3  & тЫВОД~2.3\cr
ЇАЗА~3 & тЫВОД~3.1 & тВОД~2.1  & яЕРЕМОТКА\cr
       & тЫВОД~3.2 & яЕРЕМОТКА & тВОД~2.2\cr
       & яЕРЕМОТКА & тЫВОД~3.3 & тВОД~2.3\cr
ЇАЗА~4 & тВОД~3.1  & тЫВОД~4.1 & яЕРЕМОТКА\cr
       & тВОД~3.2  & яЕРЕМОТКА & тЫВОД~4.2\cr
       & яЕРЕМОТКА & тВОД~3.3  & тЫВОД~4.3\cr
}
И~Т.~Д. чДЕСЬ "ВЫВОД~$k.j$" ОЗНАЧАЕТ ЗАПИСЬ $j\hbox{-Й}$~ТРЕТИ
$k\hbox{-ГО}$~ВЫВОДНОГО ФАЙЛА, А "ВВОД~$k.j$" ОЗНАЧАЕТ ЕЕ ЧТЕНИЕ. т КОНЦЕ
КОНЦОВ БУДЕТ ИСКЛЮЧЕНО ВСЕ ВРЕМЯ ПЕРЕМОТКИ, ЕСЛИ ПЕРЕМОТКА ПО КРАЙНЕЙ
МЕРЕ ВДВОЕ БЫСТРЕЕ ЧТЕНИЯ/ЗАПИСИ. яОДОБНАЯ ПРОЦЕДУРА, В КОТОРОЙ ВЫВОД В
КАЖДОЙ ФАЗЕ РАЗДЕЛЯЕТСЯ МЕЖДУ ЛЕНТАМИ, НАЗЫВАЕТСЯ "РАСЩЕПЛЕНИЕМ ЛЕНТ".

ы.~ьАК-рЛЛЕСТЕР [{\sl CACM\/}, {\bf 7} (1964), 158--159] ПОКАЗАЛ,
ЧТО РАСЩЕПЛЕНИЕ ЛЕНТ ПРИВОДИТ К ЭФФЕКТИВНОМУ МЕТОДУ СОВМЕЩЕНИЯ ВРЕМЕНИ
ПЕРЕМОТКИ В МНОГОФАЗНОМ СЛИЯНИИ. хГО МЕТОД МОЖНО ИСПОЛЬЗОВАТЬ С ЧЕТЫРЬМЯ
ИЛИ БОЛЬШИМ КОЛИЧЕСТВОМ ЛЕНТ, И ОН ОСУЩЕСТВЛЯЕТ $(T-2)\hbox{-ПУТЕВОЕ}$~СЛИЯНИЕ.

%%336

яРЕДПОЛОЖИМ СНОВА, ЧТО У НАС ЕСТЬ ШЕСТЬ ЛЕНТ И ПОПЫТАЕМСЯ ПОСТРОИТЬ СХЕМУ
СЛИЯНИЯ, КОТОРАЯ РАБОТАЕТ СЛЕДУЮЩИМ ОБРАЗОМ, РАСЩЕПЛЯЯ ВЫВОД НА КАЖДОМ
УРОВНЕ (БУКВЫ~I, ю И~R ОБОЗНАЧАЮТ СООТВЕТСТВЕННО ВВОД, ВЫВОД И ПЕРЕМОТКУ):
$$
\vcenter{\halign{
\hfil$#$\hfil&\bskip\hfill # \hfill\bskip&\bskip\hfill #
\hfill\bskip&\bskip\hfill # \hfill\bskip&\bskip\hfill #
\hfill\bskip&\bskip\hfill # \hfill\bskip&\bskip\hfill # \hfill\bskip&\bskip\hfill$#$\hfill\bskip\cr
        &    &    &    &    &    &    & \hbox{ўИСЛО ВЫВОДИМЫХ}\cr
єРОВЕНЬ & T1 & T2 & T3 & T4 & T5 & T6 & \hbox{ОТРЕЗКОВ}\cr
7 & I & I & I & I & R & O & u_7 \cr
  & I & I & I & I & O & R & v_7 \cr
6 & I & I & I & R & O & I & u_6 \cr
  & I & I & I & O & R & I & v_6 \cr
5 & I & I & R & O & I & I & u_5 \cr
  & I & I & O & R & I & I & v_5 \cr
4 & I & R & O & I & I & I & u_4 \cr
  & I & O & R & I & I & I & v_4 \cr
3 & R & O & I & I & I & I & u_3 \cr
  & O & R & I & I & I & I & v_3 \cr
2 & O & I & I & I & I & R & u_2 \cr
  & R & I & I & I & I & O & v_2 \cr
1 & I & I & I & I & R & O & u_1 \cr
  & I & I & I & I & O & R & v_1 \cr
0 & I & I & I & R & O & I & u_0 \cr
  & I & I & I & O & R & I & \cr
}}
\eqno (21)
$$
ўТОБЫ ЗАКОНЧИТЬ РАБОТУ С ОДНИМ ОТРЕЗКОМ НА Є4 И ПУСТЫМИ ОСТАЛЬНЫМИ ЛЕНТАМИ,
МЫ ДОЛЖНЫ ИМЕТЬ
$$
\eqalign{
v_0 &= 1,\cr
u_0+v_1&= 0,\cr
u_1+v_2 &= u_0+v_0,\cr
u_2+v_3 &= u_1+v_1+u_0+v_0,\cr
u_3+v_4 &= u_2+v_2+u_1+v_1+u_0+v_0,\cr
u_4+v_5 &= u_3+v_3+u_2+v_2+u_1+v_1+u_0+v_0,\cr
u_5+v_6 &= u_4+v_4u_3+v_3+u_2+v_2+u_1+v_1,\cr
}
$$
И~Т.~Д.; В ОБЩЕМ СЛУЧАЕ ТРЕБУЕТСЯ, ЧТОБЫ
$$
u
_n+v_{n+1}=u_{n-1}+v_{n-1}+u_{n-2}+v_{n-2}+u_{n-3}+v_{n-3}+u_{n-4}+v_{n-4}
\eqno (22)
$$
ПРИ ВСЕХ~$n\ge 0$, ЕСЛИ СЧИТАТЬ~$u_j=v_j=0$ ПРИ ВСЕХ~$j<0$.

є ЭТИХ УРАВНЕНИЙ НЕТ ЕДИНСТВЕННОГО РЕШЕНИЯ; В САМОМ ДЕЛЕ, ЕСЛИ ПОЛОЖИТЬ
ВСЕ~$u$ РАВНЫМИ НУЛЮ, ТО ПОЛУЧИМ ОБЫЧНОЕ МНОГОФАЗНОЕ, СЛИЯНИЕ, ПРИЧЕМ
ОДНА ЛЕНТА БУДЕТ ЛИШНЕЙ! эО ЕСЛИ
%%337
ВЫБРАТЬ~$u_n\approx v_{n+1}$,  ТО ВРЕМЯ ПЕРЕМОТКИ БУДЕТ УДОВЛЕТВОРИТЕЛЬНО
СОВМЕЩЕНО.

ьАК-рЛЛЕСТЕР ПРЕДЛОЖИЛ ВЗЯТЬ~$u_n=v_{n-1}+v_{n-2}+v_{n-3}+v_{n-4}$,
$v_{n+1}=u_{n-1}+u_{n-2}+u_{n-3}+u_{n-4}$, ТАК ЧТО ПОСЛЕДОВАТЕЛЬНОСТЬ
$$
\<x_0, x_1, x_2, x_3, x_4, x_5, \ldots > = \<v_0, u_0, v_1, u_1, v_2, u_2, \ldots>
$$
УДОВЛЕТВОРЯЕТ ОДНОРОДНОМУ РЕКУРРЕНТНОМУ СООТНОШЕНИЮ
$$
x_n=x_{n-3}+x_{n-5}+x_{n-7}+x_{n-9}.
$$
юКАЗАЛОСЬ, ОДНАКО, ЧТО ЛУЧШЕ ПОЛОЖИТЬ
$$
\eqalign{
v_{n+1} &= u_{n-1}+v_{n-1}+u_{n-2}+v_{n-2},\cr
u_n &= u_{n-3}+v_{n-3}+u_{n-4}+v_{n-4}.\cr
}
$$
¤ТА ПОСЛЕДОВАТЕЛЬНОСТЬ НЕ ТОЛЬКО НЕМНОГО ЛУЧШЕ ПО ВРЕМЕНИ СЛИЯНИЯ, ЕЕ
БОЛЬШОЕ ПРЕИМУЩЕСТВО В ТОМ, ЧТО СООТВЕТСТВУЮЩЕЕ ВРЕМЯ СЛИЯНИЯ МОЖНО
ПРОАНАЛИЗИРОВАТЬ МАТЕМАТИЧЕСКИ. [тАРИАНТ ьАК-рЛЛЕСТЕРА ДЛЯ АНАЛИЗА
КРАЙНЕ ТРУДЕН, ПОТОМУ ЧТО В ОДНОЙ ФАЗЕ МОГУТ ВСТРЕЧАТЬСЯ ОТРЕЗКИ РАЗНОЙ
ДЛИНЫ; МЫ УВИДИМ, ЧТО ТАКОГО НЕ МОЖЕТ СЛУЧИТЬСЯ ПРИ~(23).]

ьОЖНО ВЫВЕСТИ ЧИСЛО ОТРЕЗКОВ НА КАЖДОЙ ЛЕНТЕ НА КАЖДОМ УРОВНЕ, ДВИГАЯСЬ
НАЗАД ПО СХЕМЕ~(21); МЫ ПОЛУЧАЕМ СЛЕДУЮЩУЮ СХЕМУ СОРТИРОВКИ:
{\def\m#1{\displaystyle\matrix{#1}}\ctable{
\hfil#\hfil&\bskip\hfil$#$\hfil\bskip&\bskip\hfil$#$\hfil\bskip&\bskip\hfil$#$\hfil\bskip&\bskip\hfil$#$\hfil\bskip&\bskip\hfil$#$\hfil\bskip&\bskip\hfil$#$\hfil\bskip&\bskip$#$\hfil\bskip&\bskip\hfil$#$\hfil\bskip\cr
єРОВЕНЬ &  T1 & T2 & T3 & T4 & T5 & T6 & \hbox{тРЕМЯ ЗАПИСИ} & \hbox{тРЕМЯ  ПЕРЕМОТКИ}\cr
       & 1^{23} & 1^{21} & 1^{17} & 1^{10} & -  & 1^{11}    & 82 & 23\cr
7      & 1^{19} & 1^{17} & 1^{13} & 1^6    & R  & 1^{11}4^4 & 4\times 4=16  & 82-23\cr
       & 1^{13} & 1^{11} & 1^7    & -      & 4^6& R         & 6\times 4=24  & 25 \cr
6      & 1^{10} & 1^8    & 1^4    & R      & 4^9& 1^84^4    & 3\times 4=12  & 10 \cr
       & 1^6    & 1^4    & -      & 4^4    & R  & 1^44^4    & 4\times 4=16  & 36 \cr
5      & 1^5    & 1^3    & R      & 4^47^1 & 4^8& 1^34^4    & 1\times 7=7   & 17 \cr
       & 1^2    & -      & 7^3    & R      & 4^5& 4^4       & 3\times 7=21  & 23 \cr
4      & 1^1    & R      &7^3 13^1& 4^37^1 & 4^4& 4^3       & 1\times 13=13 & 21 \cr
       & -      & 13^1   & R      & 4^27^1 & 4^3& 4^2       & 1\times 13=13 & 34 \cr
3      & R      & 13^1 19^1& 7^2 13^1 & 4^1 7^1 & 4^2 & 4^1 & 1\times 19=19 & 23 \cr
       & 19^1   & R      & 7^1 13^1 & 7^1  & 4^1& -         & 1\times 19=19 & 32 \cr
2      & 19^1 31^0& 13^1 19^1 & 7^1 13^1 & 7^1 & 4^1 & R    & 0\times 31=0  & 25 \cr
       & R      & 19^1   & 13^1 & 7^0 & - & 31^1 & 1\times 31=31 & 19 \cr
$\m{ 1\cr \cr 0\cr}$ &
\m{ 19^1 31^0 \cr
    19^1 31^0 \cr
    19^1 31^0 \cr}&
\m{ 19^1 \cr
    19^1 \cr
    19^1 \cr } &
\m{13^1 \cr
   13^1 \cr
   13^1 \cr } &
\m{ 7^0 \cr
    - \cr
    R \cr } &
\m{ R \cr
    52^0 \cr
    52^0 82^0 \cr } &
\m{ 31^1 52^0 \cr
    R \cr
    31^1 52^0 \cr } &
\left.\m{ 0\times 52 = 0 \cr
          0\times 52 = 0 \cr
          0\times 82 = 0 \cr } \right\} \max(36, 31, 23)\span\cr
 & (31^0) & (19^0) & - & 82^1 & (R) & (52^0) & 1\times 82 = 82 & 0\cr
}}
эЕСОВМЕЩЕННАЯ ПЕРЕМОТКА ВСТРЕЧАЕТСЯ ТОЛЬКО ПРИ ПЕРЕМОТКЕ ВВОДНОЙ ЛЕНТЫ~T5
(82~ЕДИНИЦЫ), В ТЕЧЕНИЕ ПЕРВОЙ ПОЛОВИНЫ ФАЗЫ ВТОРОГО УРОВНЯ (25~ЕДИНИЦ) И
В ТЕЧЕНИЕ ОКОНЧАТЕЛЬНЫХ ФАЗ "ФИКТИВНОГО СЛИЯНИЯ" НА УРОВНЯХ~1 И~0 (36
ЕДИНИЦ). ЄАКИМ
%% 338
ОБРАЗОМ, ВРЕМЯ РАБОТЫ МОЖНО ОЦЕНИТЬ ВЕЛИЧИНОЙ~$273t+143r$;
ДЛЯ АЛГОРИТМА~D СООТВЕТСТВУЮЩАЯ ВЕЛИЧИНА~$268t+208r$ ПОЧТИ ВСЕГДА ХУЖЕ.

эЕТРУДНО ВИДЕТЬ (СМ.~УПР.~23), ЧТО ДЛИНЫ ОТРЕЗКОВ, ВЫВОДИМЫХ ВО ВРЕМЯ
КАЖДОЙ ФАЗЫ, СУТЬ ПОСЛЕДОВАТЕЛЬНО
$$
4, 4, 7, 13, 19, 31, 52, 82, 133, \ldots
\eqno(24)
$$
ПРИ ЭТОМ ПОСЛЕДОВАТЕЛЬНОСТЬ~$\< t_1, t_2, t_3,~\ldots>$ УДОВЛЕТВОРЯЕТ ЗАКОНУ
$$
t_n=t_{n-2}+2t_{n-3}+t_{n-4},
\eqno(25)
$$
ЕСЛИ СЧИТАТЬ~$t_n=1$ ПРИ~$n \le 0$. ьОЖНО ТАКЖЕ
ПРОАНАЛИЗИРОВАТЬ ОПТИМАЛЬНОЕ РАЗМЕЩЕНИЕ ФИКТИВНЫХ ОТРЕЗКОВ, РАССМОТРЕВ
СТРОКИ ЧИСЕЛ СЛИЯНИЙ, КАК МЫ ДЕЛАЛИ ДЛЯ СТАНДАРТНОГО МНОГОФАЗНОГО МЕТОДА [СР.~С~(8)]:
$$
\vcenter{\halign{
\hfill$#$\hfill&&\bskip\hfill$#$\hfill\bskip\cr
               &    &    &    &    &    & \hbox{юКОНЧАТЕЛЬНЫЙ} \cr
\hbox{єРОВЕНЬ} & T1 & T2 & T3 & T4 & T6 & \hbox{ВЫВОД НА ЛЕНТЕ}\cr
  1 & 1         & 1        & 1      & 1    & -    & T5 \cr
  2 & 1         & 1        & 1      & -    & 1    & T4 \cr
  3 & 21        & 21       & 2      & 2    & 1    & T3 \cr
  4 & 2221      & 222      & 222    & 22   & 2    & T2 \cr
  5 & 23222     & 23222    & 2322   & 23   & 222  & T1 \cr
  6 & 333323222 & 33332322 & 333323 & 3333 & 2322 & T6 \cr
\multispan{7}\dotfill\cr
  n & A_n  & B_n & C_n & D_n  & E_n & T(k) \cr
n+1 & (A''_n E_n+1)B_n & (A''_nE_n+1)C_n & (A''_n E_n+1)D_n & A''_nE_n+1 & A'_n & T(k-1)\cr
\multispan{7}\dotfill\cr
}}
\eqno(26)
$$
ГДЕ~$A_n=A'nA''_n$ И~$A''_n$ СОСТОИТ ИЗ ПОСЛЕДНИХ $u_n$~ЧИСЕЛ
СЛИЯНИЙ~$A_n$. яРИВЕДЕННОЕ ВЫШЕ ПРАВИЛО ПЕРЕХОДА С УРОВНЯ~$n$ НА
УРОВЕНЬ~$n+1$ СПРАВЕДЛИВО ДЛЯ \emph{ЛЮБОЙ} СХЕМЫ, УДОВЛЕТВОРЯЮЩЕЙ~(22).
хСЛИ МЫ ОПРЕДЕЛЯЕМ~$u$ И~$v$ ПОСРЕДСТВОМ~(23), ТО СТРОКИ~$A_n$,~\dots,
$E_n$ МОЖНО ВЫРАЗИТЬ В СЛЕДУЮЩЕМ, ДОВОЛЬНО ПРОСТОМ ВИДЕ [СР.~С~(9)]:
$$
\eqalign{
A_n &= (W_{n-1}W_{n-2}W_{n-3}W_{n-4})+1,\cr
B_n &= (W_{n-1}W_{n-2}W_{n-3})+1,\cr
C_n &= (W_{n-1}W_{n-2})+1,\cr
D_n &= (W_{n-1})+1,\cr
E_n &= (W_{n-2}W_{n-3})+1,\cr
}
\eqno(27)
$$
ГДЕ
$$
\eqalign{
W_n &= (W_{n-3}W_{n-4}W_{n-2}W_{n-3})+1 \rem{ПРИ $n>0$;}\cr
W_0 &=\hbox{'0'}\hbox{ И } W_n = \hbox{(ПУСТО)} \rem{ ПРИ $n<0$.}\cr
}
\eqno(28)
$$
%%339
шСХОДЯ ИЗ ЭТИХ СООТНОШЕНИЙ, ЛЕГКО ПОДРОБНО ПРОАНАЛИЗИРОВАТЬ СЛУЧАЙ ШЕСТИ ЛЕНТ.

т ОБЩЕМ СЛУЧАЕ, ЕСЛИ ИМЕЕТСЯ $T\ge 5$~ЛЕНТ, ТО
ПОЛОЖИМ~$P=T-2$ И ОПРЕДЕЛИМ ПОСЛЕДОВАТЕЛЬНОСТИ~$\<u_n>$, $\<v_n>$ ПО ПРАВИЛАМ
$$
\eqalign{
v_{n+1}&= u_{n-1}+v_{n-1}+\cdots+u_{n-r}+v_{n-r};\cr
u_n &= u_{n-r-1}+v_{n-r-1}+\cdots+u_{n-P}+v_{n-P}
\rem{ПРИ $n\ge 0$,}\cr
}
\eqno(29)
$$
ГДЕ~$r=\floor{P/2}$, $v_0=1$ И~$u_n=v_n=0$ ПРИ~$n<0$. хСЛИ~$w_n=u_n+v_n$,
 ТО ИМЕЕМ
$$
\eqalign{
w_n &= w_{n-2}+\cdots+w_{n-r}+2w_{n-r-1}+w_{n-r-2}+\cdots+w_{n-P},
\rem{$n>0$,}\cr
w_0&=1 \hbox{ И } w_n=0 \rem{ПРИ $n<0$.}\cr
}
\eqno(30)
$$
яРИ НАЧАЛЬНОМ РАСПРЕДЕЛЕНИИ ДЛЯ УРОВНЯ~$n+1$ НА ЛЕНТУ~$k$ ПОМЕЩАЕТСЯ
$w_n+w_{n-1}+\cdots+w_{n-P+k}$~ОТРЕЗКОВ ПРИ~$1\le k \le P$
И~$w_{n-1}+\cdots+w_{n-r}$--- НА ЛЕНТУ~$T$; ЛЕНТА~$T-1$ ИСПОЛЬЗУЕТСЯ ДЛЯ
ВВОДА. чАТЕМ $u_n$~ОТРЕЗКОВ СЛИВАЮТСЯ НА ЛЕНТУ~$T$, В ТО ВРЕМЯ КАК
ЛЕНТА~$T-1$ ПЕРЕМАТЫВАЕТСЯ; $v_n$~ОТРЕЗКОВ СЛИВАЮТСЯ НА~$T-1$, ПОКА~$T$
ПЕРЕМАТЫВАЕТСЯ; $u_{n-1}$~ОТРЕЗКОВ---НА~$T-1$, ПОКА $T-2$~ПЕРЕМАТЫВАЕТСЯ, И~Т.~Д.
\htable{ЄАБЛИЦА~6}
{яРИБЛИЗИТЕЛЬНОЕ ПОВЕДЕНИЕ МНОГОФАЗНОГО СЛИЯНИЯ С РАСЩЕПЛЕНИЕМ ЛЕНТ}%
{\hfill$#$\hfill&&\hfill\bskip$#$\bskip\hfill\cr
\hbox{ыЕНТЫ} & \hbox{ФАЗЫ} & \hbox{яРОХОДЫ} &
\hbox{яРОХОДЫ/ФАЗЫ} & \hbox{юТНОШЕНИЕ}\cr
      & & & \hbox{В ПРОЦЕНТАХ} & \hbox{РОСТА}\cr
\noalign{\hrule}
 4 & 2.885\ln S+0.000 & 1.443\ln S+1.000 & 50 & 1.4142136\cr
 5 & 2.078\ln S+0.232 & 0.929\ln S+1.022 & 45 & 1.6180340\cr
 6 & 2.078\ln S-0.170 & 0.752\ln S+1.024 & 34 & 1.6180340\cr
 7 & 1.958\ln S-0.408 & 0.670\ln S+1.007 & 34 & 1.6663019\cr
 8 & 2.008\ln S-0.762 & 0.624\ln S+0.994 & 31 & 1.6454116\cr
 9 & 1.972\ln S-0.987 & 0.595\ln S+0.967 & 30 & 1.6604077\cr
10 & 2.013\ln S-1.300 & 0.580\ln S+0.94l & 29 & 1.6433803\cr
20 & 2.069\ln S-3.164 & 0.566\ln S+0.536 & 27 & 1.6214947\cr
\noalign{\hrule}
}
ЄАБЛИЦА~6 ПОКАЗЫВАЕТ ПРИБЛИЗИТЕЛЬНОЕ ПОВЕДЕНИЕ ЭТОЙ ПРОЦЕДУРЫ, КОГДА~$S$
НЕ СЛИШКОМ МАЛО. ёТОЛБЕЦ "ПРОХОДЫ/ФАЗЫ" ПРИМЕРНО УКАЗЫВАЕТ, КАКАЯ ЧАСТЬ
ВСЕГО ФАЙЛА ПЕРЕМАТЫВАЕТСЯ ВО ВРЕМЯ КАЖДОЙ ПОЛОВИНЫ ФАЗЫ И КАКАЯ ЧАСТЬ
ФАЙЛА ЗАПИСЫВАЕТСЯ ЗА ВРЕМЯ КАЖДОЙ ПОЛНОЙ ФАЗЫ. \emph{ьЕТОД РАСЩЕПЛЕНИЯ
ЛЕНТ ПРЕВОСХОДИТ СТАНДАРТНЫЙ МНОГОФАЗНЫЙ НА ШЕСТИ ИЛИ БОЛЕЕ ЛЕНТАХ} И,
ВЕРОЯТНО; ТАКЖЕ НА ПЯТИ ЛЕНТАХ, ПО КРАЙНЕЙ МЕРЕ ДЛЯ БОЛЬШИХ~$S$.

хСЛИ~$T=4$, ТО УКАЗАННАЯ ПРОЦЕДУРА СТАЛА БЫ, ПО СУЩЕСТВУ, ЭКВИВАЛЕНТНОЙ
СБАЛАНСИРОВАННОМУ ДВУХПУТЕВОМУ СЛИЯНИЮ \emph{БЕЗ} СОВМЕЩЕНИЯ ВРЕМЕНИ
ПЕРЕМОТКИ, ТАК КАК~$w_{2n+1}$ БЫЛО БЫ РАВНО~$0$
%$390
ПРИ ВСЕХ~$n$. яОЭТОМУ ЭЛЕМЕНТЫ ТАБЛ.~6 ПРИ~$T=4$ БЫЛИ ПОЛУЧЕНЫ ПОСРЕДСТВОМ
НЕБОЛЬШОЙ МОДИФИКАЦИИ, СОСТОЯЩЕЙ В ТОМ, ЧТО ПОЛАГАЛОСЬ
$$
\displaylines{
v_2=0, u_1=1, v_1=0, u_0=0, v_0=1\hbox{ И } v_{n+1}=u_{n-1}+v_{n-1},\cr
u_n=u_{n-2}+v_{n-2}\rem{ПРИ $n \ge 2$.}\cr
}
$$
¤ТО ПРИВОДИТ К ОЧЕНЬ ИНТЕРЕСНОЙ СХЕМЕ СОРТИРОВКИ (СМ.~УПР.~25 И~26).
\excercises
\ex[16] эА РИС.~69 УКАЗАН ПОРЯДОК, В КОТОРОМ АЛГОРИТМ~D РАСПРЕДЕЛЯЕТ ПО
ПЯТИ ЛЕНТАМ ОТРЕЗКИ С~34-ГО ПО~65-Й; В КАКОМ ПОРЯДКЕ
РАСПРЕДЕЛЯЮТСЯ ОТРЕЗКИ С~1-ГО ПО~33-Й?

\rex[21] тЕРНО ЛИ, ЧТО ПОСЛЕ ДВУХ ФАЗ СЛИЯНИЯ В АЛГОРИТМЕ~D,
Т.~Е.~КОГДА МЫ ВО ВТОРОЙ РАЗ ДОСТИГНЕМ ШАГА~D6, ВСЕ ФИКТИВНЫЕ ОТРЕЗКИ ИСЧЕЗАЮТ?

\rex[22] фОКАЖИТЕ, ЧТО ПО ОКОНЧАНИИ ШАГА~D4 ВСЕГДА ВЫПОЛНЕНО
УСЛОВИЕ $|D|[1]\ge |D|[2] \ge \ldots \ge |D|[T]$. юБоЯСНИТЕ, ВАЖНОСТЬ
ЭТОГО УСЛОВИЯ ДЛЯ ПРАВИЛЬНОЙ РАБОТЫ МЕХАНИЗМА ШАГОВ~D2 И~D3.

\ex[ь20] тЫВЕДИТЕ ПРОИЗВОДЯЩИЕ ФУНКЦИИ~(7).

\ex[ть26] (¤.~я.~ьАЙЛС~МЛ., 1960.) фОКАЖИТЕ, ЧТО ПРИ ВСЕХ~$p\ge 2$
МНОГОЧЛЕН~$f_p(z)=z^p-z^{p-1}-\cdots-z-1$ ИМЕЕТ $p$~РАЗЛИЧНЫХ КОРНЕЙ, ИЗ
КОТОРЫХ РОВНО ОДИН ПРЕВОСХОДИТ~1 ПО АБСОЛЮТНОЙ ВЕЛИЧИНЕ. [\emph{єКАЗАНИЕ:} РАССМОТРИТЕ МНОГОЧЛЕН~$z^{p+1}-2z^p+1$.]

\ex[ть24] ЎЕЛЬ ЭТОГО УПРАЖНЕНИЯ---РАССМОТРЕТЬ СПОСОБ СОСТАВЛЕНИЯ ТАБЛ.~1, 5
И~6. яРЕДПОЛОЖИМ, ЧТО ИМЕЕТСЯ СХЕМА СЛИЯНИЯ, СВОЙСТВА КОТОРОЙ СЛЕДУЮЩИМ
ОБРАЗОМ ХАРАКТЕРИЗУЮТСЯ МНОГОЧЛЕНАМИ~$p(z)$ И~$q(z)$: (1)~ўИСЛО НАЧАЛЬНЫХ
ОТРЕЗКОВ В "ТОЧНОМ РАСПРЕДЕЛЕНИИ", ТРЕБУЮЩЕМ $n$~ФАЗ СЛИЯНИЯ,
РАВНО КОЭФФИЦИЕНТУ ПРИ~$z^n$ В~$p(z)/q(z)$. (2)~ўИСЛО НАЧАЛЬНЫХ ОТРЕЗКОВ,
ОБРАБАТЫВАЕМЫХ В ТЕЧЕНИЕ ЭТИХ $n$~ФАЗ СЛИЯНИЯ, РАВНО КОЭФФИЦИЕНТУ
ПРИ~$z^n$ В~$p(z)/q(z)^2$. (3)~є МНОГОЧЛЕНА~$q(z^{-1})$ ЕСТЬ "ГЛАВНЫЙ
КОРЕНЬ"~$\alpha$, ТАКОЙ, ЧТО~$q(\alpha^{-1})=0$, $q'(\alpha^{-1}) \ne 0$,
$p(\alpha^{-1})\ne 0$, И ИЗ~$q(\beta^{-1})=0$ СЛЕДУЕТ, ЧТО~$\beta=\alpha$ ИЛИ~$\abs{\beta}<\abs{\alpha}$.

фОКАЖИТЕ, ЧТО СУЩЕСТВУЕТ~$\varepsilon > 0$, ТАКОЕ, ЧТО ЕСЛИ $S$~РАВНО
ЧИСЛУ ОТРЕЗКОВ В ТОЧНОМ РАСПРЕДЕЛЕНИИ, ТРЕБУЮЩЕМ $n$~ФАЗ СЛИЯНИЯ, А ВО
ВРЕМЯ ЭТИХ ФАЗ ОБРАБАТЫВАЕТСЯ $\rho S$~ОТРЕЗКОВ, ТО~$n=a\ln
S+b+O(S^\varepsilon)$,
$\rho=c\ln S+d+O(S^{-\varepsilon})$, ГДЕ
$$
\displaylines{
a=(\ln \alpha)^{-1},\quad  b= -a\ln\left({p(\alpha^{-1})\over
-q'(\alpha^{-1})}\right)-1,
\quad c=a{\alpha\over -q'(\alpha^{-1})},\cr
d={(b+1)\alpha-p'(\alpha^{-1})/p(\alpha^{-1})+q''(\alpha^{-1})/q'\alpha^{-1}
\over -q'(\alpha^{-1})}.\cr
}
$$

\ex[ть22] яУСТЬ~$\alpha_p$---ГЛАВНЫЙ КОРЕНЬ МНОГОЧЛЕНА~$f_p(z)$ ИЗ УПР.~5.
ъАКОВО АСИМПТОТИЧЕСКОЕ ПОВЕДЕНИЕ~$\alpha_p$ ПРИ~$p\to\infty$?

\ex[ь20] (¤.~эЕТТО, 1901.) яУСТЬ~$N^{(p)}_m$ ЕСТЬ ЧИСЛО СПОСОБОВ
ВЫРАЗИТЬ~$m$ В ВИДЕ УПОРЯДОЧЕННОЙ СУММЫ ЦЕЛЫХ ЧИСЕЛ~$\set{1, 2,~\ldots,
p}$. эАПРИМЕР, ЕСЛИ~$p=3$ И~$m=5$, ТО ИМЕЕТСЯ 13~СПОСОБОВ:
$1+1+1+1+1=1+1+1+2=1+1+2+1=1+1+3=1+2+1+1 =1+2+2=
1+3+1=2+1+1+1=2+1+2=2+2+1=2+3=3+1+1=3+2$. яОКАЖИТЕ, ЧТО
$N^{(p)}_m$~ЯВЛЯЮТСЯ ОБОБЩЕННЫМИ ЧИСЛАМИ ЇИБОНАЧЧИ.

\ex[ь20] яУСТЬ~$K^{(p)}_m$---ЧИСЛО ПОСЛЕДОВАТЕЛЬНОСТЕЙ ИЗ НУЛЕЙ И ЕДИНИЦ,
ТАКИХ, ЧТО В НИХ НЕТ $p$~ПОСЛЕДОВАТЕЛЬНЫХ ЕДИНИЦ. эАПРИМЕР, ЕСЛИ~$p=3$
И~$m=5$, ИМЕЕТСЯ 24~ВАРИАНТА: $00000$, $00001$, $00010$, $00011$, $00100$,
$00101$, $00110$, $01000$, $01001$,~\dots, $11011$. яОКАЖИТЕ, ЧТО
$K^{(p)}_m$~ЯВЛЯЮТСЯ ОБОБЩЕННЫМИ ЧИСЛАМИ ЇИБОНАЧЧИ.

%%341
\ex[ь27]\exhead(ёИСТЕМА СЧИСЛЕНИЯ С ОБОБЩЕННЫМИ ЧИСЛАМИ ЇИБОНАЧЧИ.)
фОКАЖИТЕ, ЧТО КАЖДОЕ НЕОТРИЦАТЕЛЬНОЕ ЦЕЛОЕ~$n$ ИМЕЕТ ЕДИНСТВЕННОЕ ПРЕДСТАВЛЕНИЕ
В ВИДЕ СУММЫ РАЗЛИЧНЫХ ЧИСЕЛ ЇИБОНАЧЧИ $p\hbox{-ГО}$~ПОРЯДКА~$F^{(p)}_j$
ПРИ~$j\ge p$, УДОВЛЕТВОРЯЮЩЕЕ УСЛОВИЮ, ЧТО НЕ ИСПОЛЬЗУЮТСЯ НИКАКИЕ
$p$~ПОСЛЕДОВАТЕЛЬНЫЕ ЧИСЛА ЇИБОНАЧЧИ.

\ex[ь24] фОКАЖИТЕ, ЧТО $n\hbox{-Й}$~ЭЛЕМЕНТ ЦЕПОЧКИ~$Q_\infty$ В~(12)
РАВЕН КОЛИЧЕСТВУ РАЗЛИЧНЫХ ЧИСЕЛ ЇИБОНАЧЧИ В ПРЕДСТАВЛЕНИИ ЭЛЕМЕНТА
$n-1$~ЧИСЛАМИ ЇИБОНАЧЧИ ПЯТОГО ПОРЯДКА (СМ.~УПР.~10).

\rex[M20] эАЙДИТЕ ЗАВИСИМОСТЬ МЕЖДУ СТЕПЕНЯМИ МАТРИЦЫ
$$
\pmatrix{
0 & 1 & 0 & 0 & 0 \cr
0 & 0 & 1 & 0 & 0  \cr
0 & 0 & 0 & 1 & 0 \cr
0 & 0 & 0 & 0 & 1 \cr
1 & 1 & 1 & 1 & 1 \cr
}
$$
И ТОЧНЫМ ФИБОНАЧЧИЕВЫМ РАСПРЕДЕЛЕНИЕМ В~(1).

\rex[22] фОКАЖИТЕ СЛЕДУЮЩЕЕ ИНТЕРЕСНОЕ СВОЙСТВО ТОЧНЫХ
ФИБОНАЧЧИЕВЫХ РАСПРЕДЕЛЕНИЙ: ЕСЛИ ОКОНЧАТЕЛЬНЫЙ ВЫВОД ОКАЗЫВАЕТСЯ НА ЛЕНТЕ
НОМЕР~$T$, ТО ЧИСЛО ОТРЕЗКОВ НА ВСЕХ ДРУГИХ ЛЕНТАХ \emph{НЕЧЕТНОЕ,} ЕСЛИ
ОКОНЧАТЕЛЬНЫЙ ВЫВОД ОКАЗЫВАЕТСЯ НА НЕКОТОРОЙ ЛЕНТЕ, ОТЛИЧНОЙ ОТ~$T$, ТО
ЧИСЛО ОТРЕЗКОВ БУДЕТ \emph{НЕЧЕТНЫМ} НА ЭТОЙ ЛЕНТЕ И \emph{ЧЕТНЫМ} НА
ОСТАЛЬНЫХ [СМ.~(1)].

\ex[ь35] яУСТЬ~$T_n(x)=\sum_{k\ge0} T_{nk}x^k$, ГДЕ $T_n(x)$---МНОГОЧЛЕНЫ,
ОПРЕДЕЛЕННЫЕ В~(16). (a)~яОКАЖИТЕ, ЧТО ДЛЯ КАЖДОГО~$k$ СУЩЕСТВУЕТ
ЧИСЛО~$n(k)$, ТАКОЕ, ЧТО~$T_{1k}\le T_{2k} \le \ldots \le T_{n(k)k} >
T_{n(k)+1,k}\ge\ldots\,$.. (b)~яРИ УСЛОВИИ ЧТО~$T_{n'k'}<T_{nk'}$ И~$n'<n$,
 ДОКАЖИТЕ, ЧТО~$T_{n'k}\le T_{nk}$ ДЛЯ ВСЕХ~$k\ge k'$. (c)~фОКАЖИТЕ, ЧТО
СУЩЕСТВУЕТ НЕУБЫВАЮЩАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ~$\< M_n >$, ТАКАЯ,
ЧТО~$\sum_n(S) =\min_{j\ge 1} \sum_j (S)$ ПРИ~$M_n\le S < M_{n+1}$,
НО~$\sum_n(S)>\min_{j\ge 1}\sum_j(S)$ ПРИ~$S\ge M_{n+1}$. [ёМ.~(19).]

\ex[ь43] тЕРНО ЛИ, ЧТО~$\sum_{n-1}(m) < \sum_n (m)$
ВЛЕЧЕТ~$\sum_n(m)\le\sum_{n+1}(m)\le \sum_{n+2}(m) \le \ldots?$ (ЄАКОЙ
РЕЗУЛЬТАТ СИЛЬНО УПРОСТИЛ БЫ ВЫЧИСЛЕНИЕ ТАБЛ.~2.)

\ex[M43] юПРЕДЕЛИТЕ АСИМПТОТИЧЕСКОЕ ПОВЕДЕНИЕ МНОГОФАЗНОГО СЛИЯНИЯ С
ОПТИМАЛЬНЫМ РАСПРЕДЕЛЕНИЕМ ФИКТИВНЫХ ОТРЕЗКОВ.

\ex[32] тЕРНО ЛИ, ЧТО ОТРЕЗКИ ДЛЯ ОПТИМАЛЬНОГО МНОГОФАЗНОГО
РАСПРЕДЕЛЕНИЯ МОЖНО РАЗМЕСТИТЬ ТАКИМ ОБРАЗОМ, ЧТО РАСПРЕДЕЛЕНИЕ
$S+1$~НАЧАЛЬНЫХ ОТРЕЗКОВ ПОЛУЧАЕТСЯ ПУТЕМ ДОБАВЛЕНИЯ ОДНОГО ОТРЕЗКА (НА
СООТВЕТСТВУЮЩУЮ ЛЕНТУ) К РАСПРЕДЕЛЕНИЮ $S$~НАЧАЛЬНЫХ ОТРЕЗКОВ?

\ex[30] тЕРНО ЛИ, ЧТО ОПТИМАЛЬНОЕ МНОГОФАЗНОЕ РАСПРЕДЕЛЕНИЕ ДАЕТ НАИЛУЧШУЮ
ВОЗМОЖНУЮ СХЕМУ СЛИЯНИЯ В ТОМ СМЫСЛЕ, ЧТО СУММАРНОЕ КОЛИЧЕСТВО
ОБРАБАТЫВАЕМЫХ НАЧАЛЬНЫХ ОТРЕЗКОВ МИНИМАЛЬНО, ЕСЛИ ТРЕБУЕТСЯ,
ЧТОБЫ НАЧАЛЬНЫЕ ОТРЕЗКИ РАЗМЕЩАЛИСЬ НЕ БОЛЕЕ, ЧЕМ НА $T-1$~ЛЕНТАХ?
(тРЕМЕНЕМ ПЕРЕМОТКИ ПРЕНЕБРЕЧЬ.)

\ex[21] ёОСТАВЬТЕ ТАБЛИЦУ, АНАЛОГИЧНУЮ~(1), ДЛЯ МНОГОФАЗНОГО
МЕТОДА СОРТИРОВКИ ъЭЙРОНА ДЛЯ ШЕСТИ ЛЕНТ.

\ex[ь24] ъАКАЯ ПРОИЗВОДЯЩАЯ ФУНКЦИЯ ДЛЯ КЭЙРОНОВСКОЙ
МНОГОФАЗНОЙ СОРТИРОВКИ НА ШЕСТИ ЛЕНТАХ СООТВЕТСТВУЕТ~(7) И~(16)? ъАКИЕ
СООТНОШЕНИЯ, АНАЛОГИЧНЫЕ~(9) И~(27), ОПРЕДЕЛЯЮТ СТРОКИ ЧИСЕЛ СЛИЯНИЙ?

\ex[11] ўТО ДОЛЖНО ПОЯВИТЬСЯ НА УРОВНЕ~7 В~(26)?

\ex[M21] ъАЖДЫЙ ЧЛЕН ПОСЛЕДОВАТЕЛЬНОСТИ~(24) ПРИБЛИЗИТЕЛЬНО РАВЕН СУММЕ
ДВУХ ПРЕДЫДУЩИХ. эАБЛЮДАЕТСЯ ЛИ ЭТО ЯВЛЕНИЕ ДЛЯ ОСТАЛЬНЫХ
ЧЛЕНОВ ПОСЛЕДОВАТЕЛЬНОСТИ? ёФОРМУЛИРУЙТЕ И ДОКАЖИТЕ ТЕОРЕМУ
О~$t_n-t_{n-1}-t_{n-2}$.

\rex[29] ъАКИЕ ИЗМЕНЕНИЯ НАДО БЫЛО БЫ СДЕЛАТЬ В~(25), (27) И (28), ЕСЛИ БЫ
(23)~ЗАМЕНИЛОСЬ НА~$v_{n+1}=u_{n-1}+v_{n-1}+u_{n-2}$, $u_n=v_{n-2}+u_{n-3}+v_{n-3}+u_{n-4}+v_{n-4}$?
%%342
\ex[ть41] тЫЧИСЛИТЕ АСИМПТОТИЧЕСКОЕ ПОВЕДЕНИЕ МНОГОФАЗНОЙ ПРОЦЕДУРЫ С
РАСЩЕПЛЕНИЕМ ЛЕНТ, ЕСЛИ ЭЛЕМЕНТ~$v_{n+1}$ ОПРЕДЕЛЕН КАК СУММА ПЕРВЫХ$q$
ЧЛЕНОВ~$u_{n-1}+v_{n-1}+\cdots+u_{n-P}+v_{n-P}$ ПРИ РАЗЛИЧНЫХ~$P=T-2$
И~$0\le q \le 2P$. (т ТЕКСТЕ РАССМАТРИВАЕТСЯ ТОЛЬКО
СЛУЧАЙ~$q=2\floor{P/2}$; СР.~С~УПР.~23.)

\ex[19] яРОДЕМОНСТРИРУЙТЕ, КАК МНОГОФАЗНОЕ СЛИЯНИЕ С РАСЩЕПЛЕНИЕМ ЛЕНТ,
УПОМЯНУТОЕ В КОНЦЕ ЭТОГО ПУНКТА, СОРТИРОВАЛО БЫ 32~НАЧАЛЬНЫХ
ОТРЕЗКА. (фАЙТЕ АНАЛИЗ ФАЗА ЗА ФАЗОЙ, КАК ЭТО СДЕЛАНО В ТЕКСТЕ В ПРИМЕРЕ С
82~ОТРЕЗКАМИ И 6~ЛЕНТАМИ.)

\ex[ь21] яРОАНАЛИЗИРУЙТЕ ПОВЕДЕНИЕ МНОГОФАЗНОГО СЛИЯНИЯ С РАСЩЕПЛЕНИЕМ
ЛЕНТ НА ЧЕТЫРЕХ ЛЕНТАХ ПРИ~$S=2^n$ И ПРИ~$S=2^n+2^{n-1}$ (СМ.~УПР.~25).

\ex[23] хСЛИ НАЧАЛЬНЫЕ ОТРЕЗКИ РАСПРЕДЕЛЕНЫ НА ЛЕНТАХ В СООТВЕТСТВИИ С
ТОЧНЫМ РАСПРЕДЕЛЕНИЕМ, ТО МНОГОФАЗНАЯ СТРАТЕГИЯ ПРЕВРАЩАЕТСЯ ПРОСТО В
"СЛИВАТЬ ДО ОПУСТОШЕНИЯ". ьЫ СЛИВАЕМ ОТРЕЗКИ СО ВСЕХ НЕПУСТЫХ
ВХОДНЫХ ЛЕНТ, ПОКА ОДНА ИЗ НИХ НЕ СТАНЕТ ПУСТОЙ, ЗАТЕМ МЫ ИСПОЛЬЗУЕМ ЭТУ
ЛЕНТУ КАК СЛЕДУЮЩУЮ ВЫВОДНУЮ, А ПРЕДЫДУЩУЮ ВЫВОДНУЮ ЛЕНТУ ИСПОЛЬЗУЕМ КАК
ВВОДНУЮ.

тЕРНО ЛИ, ЧТО ЭТА СТРАТЕГИЯ "СЛИВАТЬ ДО ОПУСТОШЕНИЯ" ВСЕГДА
ВЫПОЛНЯЕТ СОРТИРОВКУ НЕЗАВИСИМО ОТ ТОГО, КАК РАСПРЕДЕЛЕНЫ НАЧАЛЬНЫЕ
ОТРЕЗКИ, ПРИ УСЛОВИИ ЧТО МЫ РАСПРЕДЕЛЯЕМ ИХ ПО КРАЙНЕЙ МЕРЕ НА ДВЕ ЛЕНТЫ
(ОДНА ЛЕНТА, КОНЕЧНО, БУДЕТ ОСТАВЛЕНА ПУСТОЙ, ЧТОБЫ ОНА МОГЛА СЛУЖИТЬ
ПЕРВОЙ ВЫВОДНОЙ ЛЕНТОЙ).
\edef\exref{\the\excerno}
\ex[ь26] яРЕДЫДУЩЕЕ УПРАЖНЕНИЕ ОПРЕДЕЛЯЕТ ВЕСЬМА БОЛЬШОЕ СЕМЕЙСТВА СХЕМ
СЛИЯНИЯ. яОКАЖИТЕ, ЧТО МНОГОФАЗНАЯ СХЕМА \emph{НАИЛУЧШАЯ} ИЗ НИХ В
СЛЕДУЮЩЕМ СМЫСЛЕ: ЕСЛИ ИМЕЕТСЯ ШЕСТЬ ЛЕНТ И МЫ РАССМАТРИВАЕМ КЛАСС ВСЕХ
НАЧАЛЬНЫХ РАСПРЕДЕЛЕНИЙ~$(a, b, c, d, e)$, ТАКИХ, ЧТО СТРАТЕГИЯ "СЛИВАТЬ
ДО ОПУСТОШЕНИЯ" ТРЕБУЕТ~$n$ ИЛИ МЕНЬШЕ ФАЗ ДЛЯ СОРТИРОВКИ,
ТО~$a+b+c+d+e\le t_n$, ГДЕ~$t_n$---СООТВЕТСТВУЮЩЕЕ ЧИСЛО ДЛЯ МНОГОФАЗНОЙ СОРТИРОВКИ~(1).

\ex[ь47] єПР.~\exref{} ПОКАЗЫВАЕТ, ЧТО МНОГОФАЗНОЕ РАСПРЕДЕЛЕНИЕ
ОПТИМАЛЬНО СРЕДИ ВСЕХ СХЕМ "СЛИВАТЬ ДО ОПУСТОШЕНИЯ" В СМЫСЛЕ МИНИМАЛЬНОСТИ
ЧИСЛА ФАЗ. эО ЯВЛЯЕТСЯ ЛИ ОНО ОПТИМАЛЬНЫМ ТАКЖЕ В СМЫСЛЕ МИНИМАЛЬНОСТИ ЧИСЛА ПРОХОДОВ?

яУСТЬ ЧИСЛА~$a$ И~$b$ ВЗАИМНО ПРОСТЫЕ, И ПРЕДПОЛОЖИМ, ЧТО $a+b$~ЕСТЬ
ЧИСЛО ЇИБОНАЧЧИ~$F_n$. тЕРНО ЛИ СЛЕДУЮЩЕЕ ПРЕДПОЛОЖЕНИЕ, ВЫСКАЗАННОЕ Ё.~ь.~ъАРПОМ:
ЧИСЛО НАЧАЛЬНЫХ ОТРЕЗКОВ, ОБРАБАТЫВАЕМЫХ СХЕМОЙ "СЛИВАТЬ ДО ОПУСТОШЕНИЯ",
 НАЧИНАЮЩЕЙСЯ С РАСПРЕДЕЛЕНИЯ~$(a, b)$, БОЛЬШЕ ИЛИ
РАВНО~$((n-5)F_{n+1}+(2n+2)F_n)/5$? (єКАЗАННОЕ ЗНАЧЕНИЕ ДОСТИГАЕТСЯ,
КОГДА~$a=F_{n+1}$, $b=F_{n-2}$.)

\ex[42] ёОСТАВЬТЕ ТАБЛИЦУ, АНАЛОГИЧНУЮ ТАБЛ.~2, ДЛЯ МНОГОФАЗНОГО СЛИЯНИЯ
С РАСЩЕПЛЕНИЕМ ЛЕНТ.

\subsubchap{ъАСКАДНОЕ СЛИЯНИЕ}%5.4.3
фРУГАЯ ОСНОВНАЯ СХЕМА, НАЗЫВАЕМАЯ "КАСКАДНЫМ СЛИЯНИЕМ", НА САМОМ ДЕЛЕ БЫЛА
ОТКРЫТА РАНЬШЕ МНОГОФАЗНОЙ [с.~ъ.~сЕТЦ И~є.~ъ.~ъАРТЕР, ACM Nat'1
Conference, {\bf 14} (1959), Paper~14]. эИЖЕ В ТАБЛИЦЕ ЭТОТ ПОДХОД
ИЛЛЮСТРИРУЕТСЯ ДЛЯ 6~ЛЕНТ И~190~НАЧАЛЬНЫХ ОТРЕЗКОВ С ИСПОЛЬЗОВАНИЕМ
ОБОЗНАЧЕНИЙ ИЗ П.~5.4.2:
\ctable{
#\hfil\bskip&\bskip\hfil$#$\bskip\hfil&\bskip\hfil$#$\bskip\hfil
&\bskip\hfil$#$\bskip\hfil&\bskip\hfil$#$\bskip\hfil
&\bskip\hfil$#$\bskip\hfil&\bskip\hfil$#$\bskip\hfil&#\hfil\cr
          & T1     & T2      & T3     & T4     & T5     & T6    & ъОЛИЧЕСТВО ОБРАБОТАННЫХ НАЧАЛЬНЫХ ОТРЕЗКОВ\cr
яРОХОД~1. & 1^{55} & 1^{50}  & 1^{41} & 1^{29} & 1^{15} & -     & 190 \cr
яРОХОД~2. & -      & {1^5}_* & 2^9    & 3^{12} & 4^{14} & 5^{15}& 190 \cr
яРОХОД~3. & 15^5   & 14^4    & 12^3   & 9^2    & {5^1}_*& -     & 190 \cr
яРОХОД~4. & -      & {15^1}_*& 29^1   & 41^1   & 50^1   & 55^1  & 190 \cr
яРОХОД~5. & 190^1  & -       & -      & -      & -      & -     & 190 \cr
}
%%343

\bye