\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