\input style
КОТОРАЯ ЯВЛЯЕТСЯ РАЗНОВИДНОСТЬЮ СОРТИРОВКИ С ВЫЧИСЛЕНИЕМ АДРЕСА.) 
дОПОЛНИТЕЛЬНОЕ ПРОСТРАНСТВО БУДЕТ, ПО-ВИДИМОМУ, ИСПОЛЬЗОВАТЬСЯ НАИЛУЧШИМ 
ОБРАЗОМ, ЕСЛИ ОТВЕСТИ ЕГО ПОД ПОЛЯ СВЯЗИ, КАК В МЕТОДЕ ВСТАВОК В СПИСОК. к 
ТОМУ ЖЕ ОТПАДАЕТ НЕОБХОДИМОСТЬ ВЫДЕЛЯТЬ ОТДЕЛЬНЫЕ ОБЛАСТИ ДЛЯ ВВОДА И ВЫВОДА;
ВСЕ ОПЕРАЦИИ МОЖНО ВЫПОЛНИТЬ В ОДНОЙ И ТОЙ ЖЕ ОБЛАСТИ ПАМЯТИ.

оСНОВНАЯ ИДЕЯ---ТАК ОБОБЩИТЬ МЕТОД ВСТАВОК В СПИСОК, ЧТОБЫ РАСПОЛАГАТЬ НЕ 
ОДНИМ СПИСКОМ, А \emph{НЕСКОЛЬКИМИ.} кАЖДЫЙ СПИСОК СОДЕРЖИТ КЛЮЧИ ИЗ 
ОПРЕДЕЛЕННОГО ДИАПАЗОНА. мЫ ДЕЛАЕМ ВАЖНОЕ ПРЕДПОЛОЖЕНИЕ О ТОМ, ЧТО КЛЮЧИ 
РАСПРЕДЕЛЕНЫ ДОВОЛЬНО РАВНОМЕРНО И НЕ "СКАПЛИВАЮТСЯ" ХАОТИЧЕСКИ В 
КАКИХ-ТО ДИАПАЗОНАХ. мНОЖЕСТВО ВСЕХ ВОЗМОЖНЫХ ЗНАЧЕНИЙ КЛЮЧЕЙ РАЗБИВАЕТСЯ 
НА $M$~ОТРЕЗКОВ И ПРЕДПОЛАГАЕТСЯ, ЧТО ДАННЫЙ КЛЮЧ ПОПАДАЕТ В ДАННЫЙ 
ОТРЕЗОК С ВЕРОЯТНОСТЬЮ~$1/M$. оТВОДИМ ДОПОЛНИТЕЛЬНУЮ ПАМЯТЬ ПОД ГОЛОВЫ 
$M$~СПИСКОВ, А КАЖДЫЙ СПИСОК СТРОИМ, КАК ПРИ ПРОСТЫХ ВСТАВКАХ В СПИСОК.

нЕТ НЕОБХОДИМОСТИ ПРИВОДИТЬ ЗДЕСЬ ЭТОТ АЛГОРИТМ СО ВСЕМИ ПОДРОБНОСТЯМИ. 
дОСТАТОЧНО ВНАЧАЛЕ УСТАНОВИТЬ ВСЕ ГОЛОВЫ СПИСКОВ РАВНЫМИ~$\NULL$, А ДЛЯ 
КАЖДОГО ВНОВЬ ПОСТУПИВШЕГО ЭЛЕМЕНТА ПРЕДВАРИТЕЛЬНО РЕШИТЬ, В КАКОЙ ИЗ 
$M$~ОТРЕЗКОВ ОН ПОПАДАЕТ, ПОСЛЕ ЧЕГО ВСТАВИТЬ ЕГО В СООТВЕТСТВУЮЩИЙ СПИСОК,
КАК В АЛГОРИТМЕ~L.

чТОБЫ ПРОИЛЛЮСТРИРОВАТЬ ЭТОТ МЕТОД В ДЕЙСТВИИ, ПРЕДПОЛОЖИМ, ЧТО НАШИ 
16~КЛЮЧЕЙ РАЗДЕЛЕНЫ НА $M=4$~ДИАПАЗОНА $0$--$249$, $250$--$499$, 
$500$--$749$, $750$--$999$. в ПРОЦЕССЕ СОРТИРОВКИ ПОЛУЧАЮТСЯ СЛЕДУЮЩИЕ 
КОНФИГУРАЦИИ:
\ctable{
#\hfil\bskip&&\bskip#\hfil\bskip\cr
сПИСКИ & пРИШЛО~4     & пРИШЛО~8            & пРИШЛО~12                  & кОНЕЧНОЕ \cr
       & ЭЛЕМЕНТА     & ЭЛЕМЕНТОВ           & ЭЛЕМЕНТОВ                  & СОСТОЯНИЕ\cr
1:     & $061$, $087$ & $061$, $087$, $170$ & $061$, $087$, $154$, $170$ & $061$, $087$, $154$, $170$\cr
2:     &              & $275$               & $275$, $426$               & $275$, $426$ \cr
3:     & $503$, $512$ & $503$, $512$        & $503$, $509$, $512$, $653$ & $503$, $509$, $512$, $612$\cr
       &              &                     &                            & $653$, $677$, $703$ \cr
4:     &              & $897$, $908$        & $897$, $908$               & $765$, $897$, $908$\cr
}
бЛАГОДАРЯ ПРИМЕНЕНИЮ СВЯЗАННОЙ ПАМЯТИ НЕ ВОЗНИКАЕТ ПРОБЛЕМЫ РАСПРЕДЕЛЕНИЯ 
ПАМЯТИ ПРИ ИСПОЛЬЗОВАНИИ СПИСКОВ ПЕРЕМЕННОЙ ДЛИНЫ.

\prog M.(вСТАВКИ В НЕСКОЛЬКО СПИСКОВ.) в ЭТОЙ ПРОГРАММЕ ДЕЛАЮТСЯ ТЕ ЖЕ 
ПРЕДПОЛОЖЕНИЯ, ЧТО И В ПРОГРАММЕ~L, НО КЛЮЧИ ДОЛЖНЫ БЫТЬ 
\emph{НЕОТРИЦАТЕЛЬНЫМИ;} ТАК ЧТО
$$
0\le|KEY|<(|BYTESIZE|)^3.
$$
эТОТ ДИАПАЗОН ДЕЛИТСЯ В ПРОГРАММЕ НА |M|~РАВНЫХ ЧАСТЕЙ ПУТЕМ УМНОЖЕНИЯ 
КАЖДОГО КЛЮЧА НА ПОДХОДЯЩУЮ КОНСТАНТУ. гОЛОВЫ СПИСКОВ ХРАНЯТСЯ В 
ЯЧЕЙКАХ~$|HEAD|+1$,~\dots, $|HEAD|+|M|$.
%%125
\code
KEY   & EQU  & 1:3
LINK  & EQU  & 4:5
START & ENT2 & м            & 1
      & STZ  & HEAD,2       & M     & $|HEAD|[p]\asg\NULL$.
      & DEC2 & 1            & M
      & J2P  & *-2          & M     & $M\ge p \ge 1$.
      & ENT1 & N            & 1     & $j\asg N$.
2H    & LDA  & INPUT.l(KEY) & N
      & MUL  & =M(1:3)=     & N     & $|rA|\asg\floor{M\times K_j/|BYTESIZE|^3}$. 
      & STA  & *+1(1:2)     & N
      & ENT3 & 0            & N     & $q\asg |rA|$.
      & INC3 & HEAD+1-INPUT & N     & $q\asg |LOC|(|HEAD|[q])$.
      & LDA  & INPUT, 1     & N     & $K\asg K_j$.
      & JMP  & 4F           & N     & уСТАНОВИТЬ~$p$.
3H    & CMPA & INPUT,2(KEY) & B+N-A 
      & JLE  & 5F           & B+N-A & вСТАВИТЬ, ЕСЛИ~$K\le K_p$.
      & ENT3 & 0,2          & B     & $q\asg p$.
4H    & LD2  & INPUT,3(LINK)& B+N   & $p\asg |LINK|(q)$.
      & J2P  & 3B           & B+N   & пЕРЕХОД, ЕСЛИ НЕ КОНЕЦ СПИСКА.
5н    & ST1  & INPUT,3(LINK)& N     & $|LINK|(q)\asg|LOC|(R_j)$.
      & ST2  & INPUT,1(LINK)& N     & $|LINK|(|LOC|(R_j))\asg p$.
6H    & DEC1 & 1            & N
      & J1P  & 2B           & N     & $N\ge j \ge 1$.
\endcode
\algend

эТА ПРОГРАММА НАПИСАНА ДЛЯ ПРОИЗВОЛЬНОГО ЗНАЧЕНИЯ~$M$, НО ЛУЧШЕ 
ЗАФИКСИРОВАТЬ~$M$, ПОЛОЖИВ ЕГО РАВНЫМ НЕКОТОРОМУ УДОБНОМУ ЗНАЧЕНИЮ; 
МОЖНО, НАПРИМЕР, ПОЛОЖИТЬ~$M=|BYTESIZE|$, ТОГДА ГОЛОВЫ СПИСКОВ МОЖНО 
ОПУСТОШИТЬ ОДНОЙ-ЕДИНСТВЕННОЙ КОМАНДОЙ~|MOVE|, А ПОСЛЕДОВАТЕЛЬНОСТЬ 
КОМАНД~08--11, РЕАЛИЗУЮЩИХ УМНОЖЕНИЕ, ЗАМЕНИТЬ КОМАНДОЙ~|LD3 INPUT,1(1:1)|. 
нАИБОЛЕЕ ЗАМЕТНОЕ ОТЛИЧИЕ ПРОГРАММЫ~M ОТ ПРОГРАММЫ~L СОСТОИТ В 
ТОМ, ЧТО В ПРОГРАММЕ~M НУЖНО РАССМАТРИВАТЬ СЛУЧАЙ ПУСТОГО СПИСКА, КОГДА НЕ 
НАДО ДЕЛАТЬ СРАВНЕНИЙ.

сКОЛЬКО ЖЕ ВРЕМЕНИ МЫ ЭКОНОМИМ, ИМЕЯ $M$~СПИСКОВ ВМЕСТО ОДНОГО? оБЩЕЕ 
ВРЕМЯ РАБОТЫ ПРОГРАММЫ~M РАВНО $7B+31N-3A+4M+2$~ЕДИНИЦ, ГДЕ~$M$---ЧИСЛО 
СПИСКОВ, $N$---ЧИСЛО СОРТИРУЕМЫХ ЗАПИСЕЙ, $A$ И~$B$ РАВНЫ СООТВЕТСТВЕННО 
ЧИСЛУ ПРАВОСТОРОННИХ МАКСИМУМОВ И ЧИСЛУ ИНВЕРСИЙ СРЕДИ КЛЮЧЕЙ, 
ПРИНАДЛЕЖАЩИХ КАЖДОМУ СПИСКУ. (пРИ АНАЛИЗЕ ЭТОГО АЛГОРИТМА В ОТЛИЧИЕ ОТ 
ВСЕХ ДРУГИХ АНАЛИЗОВ В ДАННОМ ПУНКТЕ МЫ СЧИТАЕМ КРАЙНИЙ ПРАВЫЙ ЭЛЕМЕНТ 
НЕПУСТОЙ ПЕРЕСТАНОВКИ ПРАВОСТОРОННИМ МАКСИМУМОМ, А НЕ ИГНОРИРУЕМ ЕГО.) мЫ 
УЖЕ ИЗУЧИЛИ ВЕЛИЧИНЫ~$A$ И~$B$ ПРИ~$M=1$, КОГДА ИХ СРЕДНИЕ ЗНАЧЕНИЯ РАВНЫ 
СООТВЕТСТВЕННО~$H_N$ И~${1\over2}\perm{N}{2}$. сОГЛАСНО ПРЕДПОЛОЖЕНИЮ О 
РАСПРЕДЕЛЕНИИ КЛЮЧЕЙ, ВЕРОЯТНОСТЬ ТОГО, ЧТО ДАННЫЙ СПИСОК В КОНЦЕ 
СОРТИРОВКИ БУДЕТ СОДЕРЖАТЬ РОВНО $n$~ЭЛЕМЕНТОВ, ЕСТЬ "БИНОМИАЛЬНАЯ" ВЕРОЯТНОСТЬ
$$
\perm{N}{n}\left({1\over M}\right)^n\left(1-{1\over M}\right)^{N-n}.
\eqno(10)
$$
%%126
пОЭТОМУ СРЕДНИЕ ЗНАЧЕНИЯ ВЕЛИЧИН~$A$ И~$B$ В ОБЩЕМ СЛУЧАЕВ РАВНЫ
$$
\eqalignno{
A_{ave}&= M\sum_n\perm{N}{n}\left({1\over M}\right)^n
\left(1-{1\over M}\right)^{N-n}H_n; & (11) \cr
B_{ave}&= M\sum_n\perm{N}{n}\left({1\over M}\right)^n
\left(1-{1\over M}\right)^{N-n}\perm{n}{2}. & (12) \cr
}
$$
пО ТЕОРЕМЕ~1.2.7A
$$
\sum_n\perm{N}{n}(M-1)^{-n}H_n=\left(1-{1\over M}\right)^{-N}(H_N-\ln M)+\varepsilon,
\qquad 
0<\varepsilon=\sum_{n>N}{1\over n}\left(1-{1\over M}\right)^{n-N}<{M-1\over N+1};
$$
СЛЕДОВАТЕЛЬНО,
$$
A_{ave}=M(H_N-\ln M)+\delta, 
\qquad 
0<\delta<{M^2\over N+1}\left(1-{1\over M}\right)^{N+1}.
\eqno(13)
$$
(эТА ФОРМУЛА ПРАКТИЧЕСКИ БЕСПОЛЕЗНА, ЕСЛИ~$M\approx N$. бОЛЕЕ ПОДРОБНО 
АСИМПТОТИЧЕСКОЕ ПОВЕДЕНИЕ ВЕЛИЧИНЫ~$A_{ave}$ ПРИ~$M=N/\alpha$  ОБСУЖДАЕТСЯ 
В УПР.~5.2.2-57.) сУММУ~(12) ЛЕГКО ВЫЧИСЛИТЬ С ПОМОЩЬЮ ТОЖДЕСТВА
$$
\perm{N}{n}\perm{n}{2}=\perm{N}{2}\perm{N-2}{n-2},
$$
КОТОРОЕ ПРЕДСТАВЛЯЕТ СОБОЙ ЧАСТНЫЙ СЛУЧАЙ ТОЖДЕСТВА~(1.2.6-20); ПОЛУЧАЕМ
$$
B_{ave}={1\over 2M}\perm{N}{2}.
\eqno(14)
$$
(сТАНДАРТНОЕ ОТКЛОНЕНИЕ ДЛЯ ВЕЛИЧИНЫ~$B$ СМ.\ В УПР.~37.) сЛЕДОВАТЕЛЬНО, 
ОБЩЕЕ ВРЕМЯ РАБОТЫ ПРОГРАММЫ~M ПРИ ФИКСИРОВАННОМ~$M$ И~$N\to\infty$ РАВНО
$$
\eqalign{
\min\qquad& 31N+M+2,\cr
\ave\qquad& 1.75N^2/M+31N-3MH_N+3M\ln M+4M-3-1.75N/M+2,\cr 
\max\qquad& 3.50N^2+24.5N+4M+2.\cr
}
\eqno(15)
$$
зАМЕТИМ, ЧТО ЕСЛИ~$M$ НЕ СЛИШКОМ ВЕЛИКО, \emph{ТО СРЕДНЕЕ ВРЕМЯ РАБОТЫ 
СОКРАЩАЕТСЯ В $M$~РАЗ.} пРИ~$M=10$ СОРТИРОВКА БУДЕТ ПРИМЕРНО В 10~РАЗ 
БЫСТРЕЕ, ЧЕМ ПРИ~$M=1$! оДНАКО МАКСИМАЛЬНОЕ ВРЕМЯ РАБОТЫ ГОРАЗДО БОЛЬШЕ 
СРЕДНЕГО. тАКИМ ОБРАЗОМ, ПОДТВЕРЖДАЕТСЯ НЕОБХОДИМОСТЬ ВЫПОЛНЕНИЯ 
ПРЕДПОЛОЖЕНИЯ О РАВНОМЕРНОСТИ РАСПРЕДЕЛЕНИЯ КЛЮЧЕЙ, ТАК КАК НАИХУДШИЙ 
СЛУЧАЙ ИМЕЕТ МЕСТО, КОГДА ВСЕ КЛЮЧИ ПОПАДАЮТ В ОДИН СПИСОК.

%%127

еСЛИ ПОЛОЖИТЬ~$M=N$, ТО СРЕДНЕЕ ВРЕМЯ РАБОТЫ БУДЕТ ПРИМЕРНО~$34.36N$, 
ПРИ~$M={1\over2}N$ ОНО НЕСКОЛЬКО БОЛЬШЕ, РАВНО ПРИБЛИЗИТЕЛЬНО~$34.52N$, 
А ПРИ~$M=N/10$ ОНО РАВНО ПРИБЛИЗИТЕЛЬНО~$48.04N$. (зАМЕТИМ, ЧТО~$10N$ ИЗ 
ЭТИХ ЕДИНИЦ ВРЕМЕНИ МАШИНЫ \MIX{} ТРАТЯТСЯ НА ОДНУ ЛИШЬ КОМАНДУ 
УМНОЖЕНИЯ!) \emph{мЫ ПОЛУЧИЛИ МЕТОД СОРТИРОВКИ С ВРЕМЕНЕМ РАБОТЫ 
ПОРЯДКА~$N$ ПРИ УСЛОВИИ, ЧТО КЛЮЧИ ДОВОЛЬНО РАВНОМЕРНО РАСПРЕДЕЛЕНЫ В 
ОБЛАСТИ ИЗМЕНЕНИЯ.}

\excercises
\ex[10] яВЛЯЕТСЯ ЛИ АЛГОРИТМ~S АЛГОРИТМОМ "УСТОЙЧИВОЙ" СОРТИРОВКИ?

\ex[11] бУДЕТ ЛИ АЛГОРИТМ~S ПРАВИЛЬНО СОРТИРОВАТЬ ЧИСЛА, ЕСЛИ В ШАГЕ~S3 
ОТНОШЕНИЕ~"$K\ge K_i$" ЗАМЕНИТЬ НА~"$K>K_i$"?

\rex[30] яВЛЯЕТСЯ ЛИ ПРОГРАММА~S САМОЙ КОРОТКОЙ ПРОГРАММОЙ СОРТИРОВКИ 
ДЛЯ МАШИНЫ \MIX, ИЛИ МОЖНО НАПИСАТЬ БОЛЕЕ КОРОТКУЮ ПРОГРАММУ, КОТОРАЯ БЫ 
ДАВАЛА ТОТ ЖЕ РЕЗУЛЬТАТ?

\rex[м20] нАЙДИТЕ МИНИМАЛЬНОЕ И МАКСИМАЛЬНОЕ ВРЕМЯ РАБОТЫ ПРОГРАММЫ~S КАК 
ФУНКЦИЮ ОТ~$N$.

\rex[м27] нАЙДИТЕ ПРОИЗВОДЯЩУЮ ФУНКЦИЮ~$g_N(z)=\sum_{k\ge0} p_{Nk} z^k$ 
ДЛЯ ОБЩЕГО ВРЕМЕНИ РАБОТЫ ПРОГРАММЫ~S, ГДЕ~$p_{Nk}$---ВЕРОЯТНОСТЬ ТОГО, ЧТО 
НА ВЫПОЛНЕНИЕ ПРОГРАММЫ~S УЙДЕТ РОВНО $k$~ЕДИНИЦ ВРЕМЕНИ ПРИ ЗАДАННОЙ 
ИСХОДНОЙ СЛУЧАЙНОЙ ПЕРЕСТАНОВКЕ МНОЖЕСТВА~$\set{1, 2,~\ldots, N}$. 
вЫЧИСЛИТЕ ТАКЖЕ СТАНДАРТНОЕ ОТКЛОНЕНИЕ ВРЕМЕНИ РАБОТЫ ДЛЯ ДАННОГО ЗНАЧЕНИЯ~$N$.

\ex[33] дЛЯ ДВУХПУТЕВЫХ ВСТАВОК, ПРОИЛЛЮСТРИРОВАННЫХ В ТАБЛ.~2,
ПО-ВИДИМОМУ, НЕОБХОДИМО, ПОМИМО ОБЛАСТИ ВВОДА, СОДЕРЖАЩЕЙ $N$~ЗАПИСЕЙ,
ИМЕТЬ ОБЛАСТЬ ВЫВОДА, В КОТОРОЙ МОЖЕТ ХРАНИТЬСЯ $2N+1$~ЗАПИСЕЙ. пОКАЖИТЕ,
ЧТО МОЖНО ВЫПОЛНЯТЬ ДВУХПУТЕВЫЕ ВСТАВКИ, ИМЕЯ КАК ДЛЯ ВВОДА, ТАК И 
ДЛЯ ВЫВОДА ПРОСТРАНСТВО, ДОСТАТОЧНОЕ ДЛЯ ХРАНЕНИЯ ВСЕГО $N+1$~ЗАПИСЕЙ.

\ex[м20] пУСТЬ~$a_1\,a_2\,\ldots\,a_n$---СЛУЧАЙНАЯ ПЕРЕСТАНОВКА  
МНОЖЕСТВА~$\set{1, 2,~\ldots, n}$; КАКОВО СРЕДНЕЕ ЗНАЧЕНИЕ 
ВЕЛИЧИНЫ~$\abs{a_1-1}+\abs{a_2-2}+\cdots+\abs{a_n-n}$? (оНО РАВНО 
ПРОИЗВЕДЕНИЮ~$n$ НА СРЕДНЕЕ ЧИСТОЕ РАССТОЯНИЕ, НА КОТОРОЕ ПЕРЕМЕЩАЕТСЯ 
ЗАПИСЬ В ПРОЦЕССЕ СОРТИРОВКИ.)

\ex[10] яВЛЯЕТСЯ ЛЯ АЛГОРИТМ~D АЛГОРИТМОМ "УСТОЙЧИВОЙ" СОРТИРОВКИ?

\ex[20] кАКИЕ ЗНАЧЕНИЯ~$A$ И~$B$ И КАКОЕ ОБЩЕЕ ВРЕМЯ РАБОТЫ 
ПРОГРАММЫ~D СООТВЕТСТВУЮТ ТАБЛ.~3 И~4? пРОАНАЛИЗИРУЙТЕ ДОСТОИНСТВА МЕТОДА 
шЕЛЛА ПО СРАВНЕНИЮ С ПРОСТЫМИ ВСТАВКАМИ В ЭТОМ СЛУЧАЕ.

\rex[22] в СЛУЧАЕ, КОГДА~$K_j\ge K_{j-h}$, В ШАГЕ~D3 АЛГОРИТМ~D 
ПРЕДПИСЫВАЕТ ВЫПОЛНЕНИЕ МНОЖЕСТВА НЕНУЖНЫХ ДЕЙСТВИЙ. пОКАЖИТЕ, КАК МОЖНО 
ИЗМЕНИТЬ ПРОГРАММУ~D, ЧТОБЫ ИЗБЕЖАТЬ ЭТИХ ИЗБЫТОЧНЫХ ВЫЧИСЛЕНИЙ, И 
ОБСУДИТЕ ПРЕИМУЩЕСТВА ТАКОГО ИЗМЕНЕНИЯ.

\ex[м10] кАКОЙ ПУТЬ НА РЕШЕТКЕ (АНАЛОГИЧНОЙ ПРЕДСТАВЛЕННОЙ НА РИС.~11) 
СООТВЕТСТВУЕТ ПЕРЕСТАНОВКЕ $1\,2\,5\,3\,7\,4\,8\,6\,9\,11\,10\,12$?

\ex[м20] дОКАЖИТЕ, ЧТО СУММА ВЕРТИКАЛЬНЫХ ВЕСОВ ПУТИ НА РЕШЕТКЕ РАВНА 
ЧИСЛУ ИНВЕРСИЙ СООТВЕТСТВУЮЩЕЙ 2-УПОРЯДОЧЕННОЙ ПЕРЕСТАНОВКИ.

\rex[м22] пОЯСНИТЕ, КАК НУЖНО ПРИПИСАТЬ ВЕСА \emph{ГОРИЗОНТАЛЬНЫМ} 
ОТРЕЗКАМ ВМЕСТО ВЕРТИКАЛЬНЫХ, ЧТОБЫ СУММА ГОРИЗОНТАЛЬНЫХ ВЕСОВ ПУТИ НА 
РЕШЕТКЕ РАВНЯЛАСЬ ЧИСЛУ ИНВЕРСИЙ В СООТВЕТСТВУЮЩЕЙ 2-УПОРЯДОЧЕННОЙ ПЕРЕСТАНОВКЕ.

\ex[м24] (a)~пОКАЖИТЕ, ЧТО ДЛЯ СУММ, ОПРЕДЕЛЯЕМЫХ РАВЕНСТВОМ~(2),
$A_{2n+1}=2A_{2n}$. (b)~еСЛИ ПОЛОЖИТЬ~$r=-s-1$, $t=1$, ТО ОБЩЕЕ ТОЖДЕСТВО 
ИЗ УПР.~1.2.6-26 УПРОЩАЕТСЯ ДО
$$
\sum_k\perm{2k+s}{k}z^k={1\over\sqrt{1-4z}}\left({1-\sqrt{1-4z}\over 2z}\right)^s.
$$
%%128
рАССМОТРЕВ СУММУ~$\sum_n A_{2n} z^n$ ПОКАЖИТЕ, ЧТО
$$
A_{2n}=n\cdot 4^{n-1}.
$$

\rex[вм33] пУСТЬ~$g_n(z)$, $\bar g_n(z)$, $h(z)$, $\bar h_n(z)$ 
РАВНЫ~$\sum z^{\hbox{ОБЩИЙ ВЕС ПУТИ}}$, ГДЕ СУММА БЕРЕТСЯ ПО ВСЕМ ПУТЯМ 
ДЛИНЫ~$2n$ НА РЕШЕТКЕ ИЗ~$(0, 0)$ В~$(n, n)$, УДОВЛЕТВОРЯЮЩИМ НЕКОТОРЫМ 
ОГРАНИЧЕНИЯМ НА ВЕРШИНЫ, ЧЕРЕЗ КОТОРЫЕ ЭТИ ПУТИ ПРОХОДЯТ: ДЛЯ~$h_n(z)$ НЕТ 
ОГРАНИЧЕНИЙ, ДЛЯ~$g_n(z)$ ПУТИ НЕ ДОЛЖНЫ ПРОХОДИТЬ ЧЕРЕЗ ВЕРШИНЫ~$(i, j)$, 
ТАКИЕ, ЧТО~$i>j$; $\bar h_n(z)$ И~$\bar g_n(z)$ ОПРЕДЕЛЯЮТСЯ АНАЛОГИЧНО, 
НО НЕ ДОПУСКАЮТСЯ ТАКЖЕ И ВЕРШИНЫ~$(i, i)$ ПРИ~$0<i < n$. тАКИМ ОБРАЗОМ,
$$
\displaylines{
g_0(z)=1, \quad g_1(z)=z, \quad g_2(z)=z^3+z^2; \quad \bar g_1(z)=z, \quad \bar g_2(z)=z^3;\cr
h_0(z)=1,\quad   h_1(z)=z+1, \quad h_2(z)=z^3+z^2+3z+1;\cr
\bar h_1(z)=z+1, \quad \bar h_2(z)=z^3+z.\cr
}
$$
нАЙДИТЕ РЕКУРРЕНТНЫЕ СООТНОШЕНИЯ, ОПРЕДЕЛЯЮЩИЕ ЭТИ ФУНКЦИИ, И 
ВОСПОЛЬЗУЙТЕСЬ ЭТИМИ РЕКУРРЕНТНЫМИ СООТНОШЕНИЯМИ ДЛЯ ДОКАЗАТЕЛЬСТВА РАВЕНСТВА
$$
h''_n(1)+h'_n(1)={7n^3+4n^2+4n\over 30}\perm{2n}{n}.
$$
(оТСЮДА ЛЕГКО НАХОДИТСЯ ТОЧНАЯ ФОРМУЛА ДИСПЕРСИИ ЧИСЛА ИНВЕРСИЙ В 
СЛУЧАЙНОЙ 2-УПОРЯДОЧЕННОЙ ПЕРЕСТАНОВКЕ МНОЖЕСТВА~$\set{1, 2,~\ldots, 2n}$; 
ОНА АСИМПТОТИЧЕСКИ ПРИБЛИЖАЕТСЯ К~$\left({7\over 30}-{\pi\over 16}\right) n^3$.)

\ex[м24] нАЙДИТЕ ФОРМУЛУ МАКСИМАЛЬНОГО ЧИСЛА ИНВЕРСИЙ В $h$-УПОРЯДОЧЕННОЙ 
ПЕРЕСТАНОВКЕ МНОЖЕСТВА~$\set{1, 2,~\ldots, n}$. кАКОВО МАКСИМАЛЬНО 
ВОЗМОЖНОЕ ЧИСЛО ПЕРЕМЕЩЕНИЙ, ВЫПОЛНЯЕМЫХ АЛГОРИТМОМ~D, ЕСЛИ ШАГИ 
СОРТИРОВКИ УДОВЛЕТВОРЯЮТ УСЛОВИЮ ДЕЛИМОСТИ~(5)?

\ex[M21] пОКАЖИТЕ, ЧТО ЕСЛИ~$N=2^t$ И~$h_s=2^{s-1}$ ПРИ~$t\ge s\ge 1$, 
ТО СУЩЕСТВУЕТ ЕДИНСТВЕННАЯ ПЕРЕСТАНОВКА МНОЖЕСТВА~$\set{1, 2,~\ldots, N}$, 
МАКСИМИЗИРУЮЩАЯ ЧИСЛО ПЕРЕМЕЩЕНИЙ, ВЫПОЛНЯЕМЫХ АЛГОРИТМОМ~D. нАЙДИТЕ 
ПРОСТОЙ СПОСОБ ОПИСАНИЯ ЭТОЙ ПЕРЕСТАНОВКИ.

\ex[вм24] пРИ БОЛЬШИХ ЗНАЧЕНИЯХ~$N$ СУММУ~(6) МОЖНО ОЦЕНИТЬ ВЕЛИЧИНОЙ
$$
{1\over 4}{N^2\over h_t}+{\sqrt{\pi}\over 8}
\left({N^{3/2}h_t^{1/2}\over h_{t-1}}+\cdots+{N^{3/2}h_2^{1/2}\over h_1}\right).
$$
кАКОВЫ ДЕЙСТВИТЕЛЬНЫЕ ЧИСЛА~$h_t$,~\dots, $h_1$, МИНИМИЗИРУЮЩИЕ ЭТО 
ВЫРАЖЕНИЕ, ЕСЛИ~$N$ И~$t$ ФИКСИРОВАНЫ, a~$h_1=1$?

\rex[м25] кАКОВО СРЕДНЕЕ ЗНАЧЕНИЕ ВЕЛИЧИНЫ~$A$ В АНАЛИЗЕ ВРЕМЕНИ РАБОТЫ
ПРОГРАММЫ~D, ЕСЛИ ШАГИ СОРТИРОВКИ УДОВЛЕТВОРЯЮТ УСЛОВИЮ ДЕЛИМОСТИ~(5)?

\ex[м20] пОКАЖИТЕ, ЧТО ТЕОРЕМА~K СЛЕДУЕТ ИЗ ЛЕММЫ~L.

\ex[м25] пУСТЬ~$h$ И~$k$---ВЗАИМНО ПРОСТЫЕ ЦЕЛЫЕ ПОЛОЖИТЕЛЬНЫЕ 
ЧИСЛА. пОКАЖИТЕ, ЧТО НАИБОЛЬШЕЕ ЦЕЛОЕ ЧИСЛО, КОТОРОЕ НЕЛЬЗЯ ПРЕДСТАВИТЬ В 
ВИДЕ~$ah+bk$, ГДЕ~$a$ И~$b$---\emph{НЕОТРИЦАТЕЛЬНЫЕ} ЦЕЛЫЕ ЧИСЛА, 
РАВНО~$hk-h-k$. сЛЕДОВАТЕЛЬНО, ЕСЛИ ФАЙЛ ЯВЛЯЕТСЯ ОДНОВРЕМЕННО 
$h$-УПОРЯДОЧЕННЫМ И~$k$-УПОРЯДОЧЕННЫМ, ТО~$K_i\le K_j$ ПРИ~$j-i\ge(h-1)(k-1)$.

\ex[M30] дОКАЖИТЕ, ЧТО ЛЮБОЕ ЦЕЛОЕ ЧИСЛО~$\ge 2^h(2^h-1)$ МОЖНО 
ПРЕДСТАВИТЬ В ВИДЕ~$a_0(2^h-1)+a_1(2^{h+1}-1)+a_2(2^{h+2}-1)+\ldots$, 
ГДЕ~$a_j$---НЕОТРИЦАТЕЛЬНЫЕ ЦЕЛЫЕ ЧИСЛА; НО ЧИСЛО~$2^h(2^h-1)-1$ НЕЛЬЗЯ 
ПРЕДСТАВИТЬ В ТАКОМ ВИДЕ. бОЛЕЕ ТОГО, СУЩЕСТВУЕТ РОВНО $2^{h-1}(2^h+h-3)$ 
ЦЕЛЫХ ПОЛОЖИТЕЛЬНЫХ ЧИСЕЛ, КОТОРЫЕ НЕЛЬЗЯ ПРЕДСТАВИТЬ В ТАКОМ ВИДЕ.

нАЙДИТЕ АНАЛОГИЧНЫЕ ФОРМУЛЫ ДЛЯ СЛУЧАЯ, КОГДА В ЭТОМ 
ПРЕДСТАВЛЕНИИ ВЫРАЖЕНИЕ~$2^k-1$ ЗАМЕНЕНО НА~$2^k+1$.

\rex[м22] дОКАЖИТЕ, ЧТО ЕСЛИ~$h_{s+2}$ И~$h_{s+1}$ ВЗАИМНО ПРОСТЫ, ТО 
ЧИСЛО ПЕРЕМЕЩЕНИЙ, ВЫПОЛНЯЕМЫХ АЛГОРИТМОМ~D ПРИ ПРОСМОТРЕ С ШАГОМ~$h_s$, 
ЕСТЬ~$O(Nh_{s+2}h_{s+1}/h_s)$. (\emph{уКАЗАНИЕ:} СМ.~УПР.~21.)
%% 129

\ex[м42] дОКАЖИТЕ, ЧТО ТЕОРЕМА~P---НАИЛУЧШАЯ ИЗ ВОЗМОЖНЫХ ТЕОРЕМ В ТОМ 
СМЫСЛЕ, ЧТО ПОКАЗАТЕЛЬ~$3/2$ НЕЛЬЗЯ УМЕНЬШИТЬ.

\rex[M22] сКОЛЬКО СУЩЕСТВУЕТ ПЕРЕСТАНОВОК МНОЖЕСТВА~$\set{1, 2,~\ldots, n}$, 
ЯВЛЯЮЩИХСЯ ОДНОВРЕМЕННО 3-УПОРЯДОЧЕННЫМИ И 2-УПОРЯДОЧЕННЫМИ? 
кАКОВО МАКСИМАЛЬНОЕ ЧИСЛО ИНВЕРСИЙ В ТАКОЙ ПЕРЕСТАНОВКЕ? чЕМУ РАВНО 
СУММАРНОЕ ЧИСЛО ИНВЕРСИЙ ВО ВСЕХ ТАКИХ ПЕРЕСТАНОВКАХ?

\ex[м35] мОЖЕТ ЛИ 3-, 5- И 7-УПОРЯДОЧЕННЫЙ ФАЙЛ ИЗ $N$~ЭЛЕМЕНТОВ СОДЕРЖАТЬ 
БОЛЕЕ $N$~ИНВЕРСИЙ?

\ex[м50] пРЕДЛОЖИТЕ ЭФФЕКТИВНЫЙ АЛГОРИТМ ПОСТРОЕНИЯ ПЕРЕСТАНОВОК, КОТОРЫЕ 
ТРЕБУЮТ МАКСИМАЛЬНОГО ЧИСЛА ОПЕРАЦИЙ ПЕРЕМЕЩЕНИЯ В АЛГОРИТМЕ~D ПРИ 
ЗАДАННЫХ~$N$, $h_t$, $h_{t-1}$,~\dots, $h_1$.

\ex[15] кАКАЯ ИЗ ПОСЛЕДОВАТЕЛЬНОСТЕЙ ШАГОВ, УКАЗАННЫХ В ТАБЛ.~6, НАИЛУЧШАЯ 
ДЛЯ ПРОГРАММЫ~D С ТОЧКИ ЗРЕНИЯ СУММАРНОГО ВРЕМЕНИ РАБОТЫ?

\ex[м42] нАЙДИТЕ ДЛЯ~$N=1000$ И РАЗЛИЧНЫХ ЗНАЧЕНИЙ~$t$ 
ЭМПИРИЧЕСКИЕ ЗНАЧЕНИЯ~$h_t$,~\dots, $h_1$, КОТОРЫЕ, БЫТЬ МОЖЕТ, 
МИНИМИЗИРУЮТ СРЕДНЕЕ ЧИСЛО ОПЕРАЦИЙ ПЕРЕМЕЩЕНИЯ В АЛГОРИТМЕ~D В ТОМ 
СМЫСЛЕ, ЧТО ЕСЛИ ИЗМЕНИТЬ ОДНУ ИЗ ВЕЛИЧИН~$h$, НЕ МЕНЯЯ ОСТАЛЬНЫХ, ТО 
СРЕДНЕЕ ЧИСЛО ПЕРЕМЕЩЕНИЙ ВОЗРАСТЕТ.

\ex[м23] (в.~пРАТТ.) пОКАЖИТЕ, ЧТО ЕСЛИ МНОЖЕСТВО ШАГОВ 
ЕСТЬ~$\set{2^p3^q \mid 2^p3^q<N}$, ТО ЧИСЛО ПРОСМОТРОВ РАВНО 
ПРИМЕРНО~${1\over2}(\log_2 N)(\log_3 N)$ И НА КАЖДЫЙ ПРОСМОТР ПРИХОДИТСЯ 
НЕ БОЛЕЕ $N/2$~ОПЕРАЦИЙ ПЕРЕМЕЩЕНИЯ. в ДЕЙСТВИТЕЛЬНОСТИ ПРИ ЛЮБОМ 
ПРОСМОТРЕ, ЕСЛИ~$K_{j-h}>K_j$, ТО ВСЕГДА~$K_{j-3h}$, 
$K_{j-2h}>\le K_j<K_{j-h}\le K_{j+h}$, $K_{j+2h}$, ТАК ЧТО МОЖНО ПРОСТО 
ПОМЕНЯТЬ МЕСТАМИ~$K_{j-h}$ И~$K_j$ И УВЕЛИЧИТЬ~$j$ НА~$2h$, СЭКОНОМИВ В 
АЛГОРИТМЕ~D 2~СРАВНЕНИЯ. (\emph{уКАЗАНИЕ:} cМ.~УПР.~25.)

\rex[25] нАПИШИТЕ \MIX-ПРОГРАММУ ДЛЯ АЛГОРИТМА СОРТИРОВКИ, ПРЕДЛОЖЕННОГО 
в.~пРАТТОМ (УПР.~30). вЫРАЗИТЕ ЕЕ ВРЕМЯ РАБОТЫ ЧЕРЕЗ ВЕЛИЧИНЫ~$A$, $B$, 
$S$, $T$, $N$, АНАЛОГИЧНЫЕ СООТВЕТСТВУЮЩИМ ВЕЛИЧИНАМ В ПРОГРАММЕ~D.

\ex[10] кАКОВО БУДЕТ ОКОНЧАТЕЛЬНОЕ СОДЕРЖИМОЕ 
СВЯЗЕЙ~$L_0L_1\ldots{}L_{16}$, ЕСЛИ ПРОВЕСТИ ДО КОНЦА СОРТИРОВКУ СПИСКА 
ВСТАВКАМИ В ТАБЛ.~8?

\rex[25] нАЙДИТЕ СПОСОБ УСОВЕРШЕНСТВОВАТЬ ПРОГРАММУ~L, ЧТОБЫ ЕЕ 
ВРЕМЯ РАБОТЫ ОПРЕДЕЛЯЛОСЬ ВЕЛИЧИНОЙ~$5B$, А НЕ~$7B$, ГДЕ~$B$---ЧИСЛО ИНВЕРСИЙ.

\ex[м10] пРОВЕРЬТЕ ФОРМУЛУ~(10).

\ex[18] пРЕДПОЛОЖИМ, ЧТО РАЗМЕР БАЙТА МАШИНЫ~\MIX{} РАВЕН~100 И 
ШЕСТНАДЦАТЬ КЛЮЧЕЙ В ТАБЛ.~8 РАВНЫ НА САМОМ ДЕЛЕ~$503\,000$, $087\,000$, 
$512\,000$,~\dots, $703\,000$. оПРЕДЕЛИТЕ ВРЕМЯ РАБОТЫ ПРОГРАММ~M И~L С 
ЭТИМИ ДАННЫМИ ПРИ~$M=4$.

\ex[вм16] еСЛИ ПРОГРАММА ВЫПОЛНЯЕТСЯ ПРИБЛИЗИТЕЛЬНО ЗА $A/M+B$~ЕДИНИЦ 
ВРЕМЕНИ И ИСПОЛЬЗУЕТ $C+M$~ЯЧЕЕК ПАМЯТИ, ТО ПРИ КАКОМ 
ВЫБОРЕ~$M$ ДОСТИГАЕТСЯ ОПТИМАЛЬНОЕ ЗНАЧЕНИЕ ПРОИЗВЕДЕНИЯ ПРОСТРАНСТВА НА ВРЕМЯ?

\ex[м25] пУСТЬ~$g_n(z)$---ПРОИЗВОДЯЩАЯ ФУНКЦИЯ ДЛЯ ЧИСЛА ИНВЕРСИЙ В 
СЛУЧАЙНОЙ ПЕРЕСТАНОВКЕ $n$~ЭЛЕМЕНТОВ (СР.\ С ФОРМУЛОЙ~(5.1.1-11)). 
пУСТЬ~$g_{NM}(z)$---СООТВЕТСТВУЮЩАЯ ПРОИЗВОДЯЩАЯ ФУНКЦИЯ ДЛЯ ВЕЛИЧИНЫ~$B$ В 
ПРОГРАММЕ~$M$. пОКАЖИТЕ, ЧТО
$$
\sum_{N\ge0} g_{NM}(z) M^N w^N/N!=\left(\sum_{n\ge0} g_n(z)w^n/n!\right)^M,
$$
И ВОСПОЛЬЗУЙТЕСЬ ЭТОЙ ФОРМУЛОЙ ДЛЯ ВЫВОДА ДИСПЕРСИИ ВЕЛИЧИНЫ~$B$.

\ex[вм23] (р.~м.~кАРП.) пУСТЬ~$F(x)$---НЕКОТОРАЯ ФУНКЦИЯ 
РАСПРЕДЕЛЕНИЯ ВЕРОЯТНОСТЕЙ, ПРИЧЕМ~$F(0)=0$ И~$F(1)=1$. дОКАЖИТЕ, ЧТО ЕСЛИ 
КЛЮЧИ~$K_1$, $K_2$,~\dots, $K_N$ НЕЗАВИСИМО ВЫБИРАЮТСЯ СЛУЧАЙНЫМ ОБРАЗОМ 
ИЗ ЭТОГО РАСПРЕДЕЛЕНИЯ И~$M=cN$, ГДЕ~$c$---КОНСТАНТА, А~$N\to\infty$, ТО 
ВРЕМЯ РАБОТЫ ПРОГРАММЫ~M ЕСТЬ~$O(N)$, ЕСЛИ ТОЛЬКО~$F$---ДОСТАТОЧНО ГЛАДКАЯ 
ФУНКЦИЯ. (кЛЮЧ~$K$ ВСТАВЛЯЕТСЯ В СПИСОК~$j$, ЕСЛИ~$\floor{MK}=j-1$; ЭТО 
СЛУЧАЕТСЯ С ВЕРОЯТНОСТЬЮ~$F(j/M)-F((j-1)/M)$. в ТЕКСТЕ РАССМАТРИВАЛСЯ ЛИШЬ 
СЛУЧАЙ~$F(x)=x$, $0\le x \le 1$.)

%%130
\bye