\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