\input style
%% 161
пРИВЕДЕННОЕ НИЖЕ РАССУЖДЕНИЕ ПОКАЖЕТ, ЧТО ЭТА ПОСЛЕДНЯЯ СУММА ЕСТЬ $O(1)$; 
СЛЕДОВАТЕЛЬНО, $U_n-T_n=O(1)$. (сМ. УПР.~47.)

дО СИХ ПОР МЫ ЕЩЕ НЕ ИСПОЛЬЗОВАЛИ НИКАКИХ МЕТОДОВ, КОТОРЫЕ БЫ 
ДЕЙСТВИТЕЛЬНО ОТЛИЧАЛИСЬ ОТ ПРИМЕНЯВШИХСЯ РАНЕЕ, НО
\picture{рИС. 20. кОНТУРЫ ИНТЕГРИРОВАНИЯ ДЛЯ ТОЖДЕСТВ С ГАММА-ФУНКЦИЯМИ.}
ДЛЯ ИЗУЧЕНИЯ РЯДА~$T_n$ ПОТРЕБУЕТСЯ НОВАЯ ИДЕЯ, ОСНОВАННАЯ НА ПРОСТЫХ 
ПРИНЦИПАХ ТЕОРИИ ФУНКЦИЙ КОМПЛЕКСНОГО ПЕРЕМЕННОГО. еСЛИ $x$---ПРОИЗВОЛЬНОЕ 
ПОЛОЖИТЕЛЬНОЕ ЧИСЛО, ТО
$$
e^{-x}={1\over 2\pi i}\int_{1/2-i\infty}^{1/2+i\infty} \Gamma(z)x^{-z}\,dz=
{1\over 2\pi}\int_{-\infty}^\infty\Gamma\left({1\over2}+it\right)x^{-(1/2+it)}\,dt.
\eqno(42)
$$
дЛЯ ДОКАЗАТЕЛЬСТВА ЭТОГО ТОЖДЕСТВА РАССМОТРИМ ПУТЬ ИНТЕГРИРОВАНИЯ, 
ПОКАЗАННЫЙ НА РИС.~20(a), ГДЕ $N$, $N'$ И $M$ ВЕЛИКИ. зНАЧЕНИЕ ИНТЕГРАЛА 
ВДОЛЬ ЭТОГО КОНТУРА РАВНО СУММЕ ВЫЧЕТОВ ВНУТРИ КОНТУРА, А ИМЕННО
$$
\sum_{0\le k<M} x^{-k}\lim_{z\to-k}(z+k)\Gamma(z)=
\sum_{0\le k<M} x^{-k}{(-1)^k\over k!}.
$$
иНТЕГРАЛ ПО ВЕРХНЕЙ ЧАСТИ КОНТУРА ЕСТЬ 
$O\left(\int_{-\infty}^{1/2}\abs{\Gamma(t+iN)}x^{-t}\,dt\right)$,
И У НАС ИМЕЕТСЯ ИЗВЕСТНАЯ ОЦЕНКА
$$
\Gamma(t+iN)=O(N^{t-1/2} e^{-\pi N/2}) \rem{ПРИ $N\to\infty$.}
$$
[сВОЙСТВА ГАММА-ФУНКЦИЙ СМ., НАПРИМЕР, В КНИГЕ A.~Erd\'elyi et al., Higher 
Transcendental Functions, 1 (New York: McGraw-Hill, 1953), ГЛ.~1.] пОЭТОМУ 
ИНТЕГРАЛ ПО ВЕРХНЕМУ ОТРЕЗКУ
БЕСКОНЕЧНО МАЛ: 
$O\left( e^{-\pi N/2}\int_{-\infty}^{1/2} (N/x)^t\,dt\right)$. 
иНТЕГРАЛ ПО НИЖНЕМУ
%% 162
ОТРЕЗКУ ВЕДЕТ СЕБЯ СТОЛЬ ЖЕ БЕЗОБИДНО. дЛЯ ВЫЧИСЛЕНИЯ ИНТЕГРАЛА ПО 
ЛЕВОМУ ОТРЕЗКУ КОНТУРА ВОСПОЛЬЗУЕМСЯ ТЕМ ФАКТОМ, ЧТО
$$
\eqalign{
\Gamma\left({1\over2}+it-M\right)&=
\Gamma\left({1\over2}+it\right)/\left(-M+{1\over2}+it\right)
  \ldots\left(-1+{1\over2}+it\right)=\cr
&=\Gamma\left({1\over2}+it\right) O(1/(M-1)!).\cr
}
$$
сЛЕДОВАТЕЛЬНО, ИНТЕГРАЛ ПО ЛЕВОЙ СТОРОНЕ ЕСТЬ 
$O(x^{M-1/2}/(M-1)!)\times
 \int_{-\infty}^\infty\abs{\Gamma\left({1\over2}+it\right)}\,dt$. 
пОЭТОМУ ПРИ $M$, $N$, $N'\to\infty$ УЦЕЛЕЕТ ЛИШЬ
ИНТЕГРАЛ ПО ПРАВОЙ СТОРОНЕ; ТЕМ САМЫМ ДОКАЗАНО ТОЖДЕСТВО (42). в 
ДЕЙСТВИТЕЛЬНОСТИ ТОЖДЕСТВО (42) ОСТАЕТСЯ В СИЛЕ И В ТОМ СЛУЧАЕ, ЕСЛИ 
ЗАМЕНИТЬ $1\over2$ ЛЮБЫМ ПОЛОЖИТЕЛЬНЫМ ЧИСЛОМ.

тЕМ ЖЕ САМЫМ РАССУЖДЕНИЕМ МОЖНО ВОСПОЛЬЗОВАТЬСЯ ДЛЯ ВЫВОДА ДРУГИХ 
ПОЛЕЗНЫХ СООТНОШЕНИЙ, СОДЕРЖАЩИХ ГАММА-ФУНКЦИИ. вЕЛИЧИНУ $x^{-z}$ МОЖНО 
ЗАМЕНИТЬ ДРУГИМИ ФУНКЦИЯМИ ОТ $z$; МОЖНО
ТАКЖЕ ЗАМЕНИТЬ ДРУГОЙ ВЕЛИЧИНОЙ КОНСТАНТУ $1\over2$. нАПРИМЕР,
$$
{1\over2\pi i}\int_{-3/2-i\infty}^{-3/2+i\infty}\Gamma(z)x^{-z}\,dz
=e^{-x}-1+x,
\eqno(43)
$$
А ЭТО---КРИТИЧЕСКАЯ ВЕЛИЧИНА В ФОРМУЛЕ (41) ДЛЯ $T_n$:
$$
T_n=n\sum_{j\ge1}
{1\over2\pi i}\int_{-3/2-i\infty}^{-3/2+i\infty}\Gamma(z)(n/2^j)^{-1-z}\,dz.
\eqno(44)
$$

сУММИРОВАНИЕ МОЖНО ВНЕСТИ ПОД ЗНАК ИНТЕГРАЛА, ТАК КАК СХОДИМОСТЬ ЗДЕСЬ 
ДОСТАТОЧНО ХОРОШАЯ; ИМЕЕМ
$$
\sum_{j\le 1}(n/2^j)^w=n^w\sum_{j\le1}(1/2^w)^j=n^w/(2^w-1),
\rem{ЕСЛИ $\Re(w)>0$,}
$$
ТАК КАК $\abs{2^w} = 2^{\Re(w)} > 1$. пОЭТОМУ
$$
T_n={n\over2\pi i}
\int_{-3/2-i\infty}^{-3/2+i\infty}
 {\Gamma(z)n^{-1-z}\over 2^{-1-z}-1}\, dz,
\eqno(45)
$$
И ОСТАЕТСЯ ОЦЕНИТЬ ПОСЛЕДНИЙ ИНТЕГРАЛ.

нА ЭТОТ РАЗ ИНТЕГРИРОВАНИЕ ПРОИЗВОДИТСЯ ПО КОНТУРУ, КОТОРЫЙ БОЛЬШЕ 
ВЫТЯНУТ ВПРАВО, КАК ИЗОБРАЖЕНО НА РИС. 20(b).
%% 163
иНТЕГРАЛ ПО ВЕРХНЕМУ ОТРЕЗКУ ЕСТЬ 
$O\left(n^{1/2}e^{-\pi M/2} \int_{-3/2}^M N^t\,dt\right)$,
ЕСЛИ $2^{iN}\ne1$, А ИНТЕГРАЛ ПО НИЖНЕМУ ОТРЕЗКУ ТАКЖЕ ПРЕНЕБРЕЖИМО   
МАЛ.   иНТЕГРАЛ   ПО   ПРАВОМУ  ОТРЕЗКУ   РАВЕН
$O\left( n^{-1-M} \int_{-\infty}^\infty \abs{\Gamma(M+it)}\,dt\right)$. 
фИКСИРУЯ $M$ И УСТРЕМЛЯЯ $N$, $N'$ К~$\infty$,
МОЖНО ПОКАЗАТЬ, ЧТО $-T_n/n$ ЕСТЬ $O(n^{-1-M})$ ПЛЮС СУММА ВЫЧЕТОВ В 
ОБЛАСТИ $-3/2 < \Re(z)<M$. пУСТЬ $M\to\infty$, $\Gamma(z)$ ИМЕЕТ ПРОСТЫЕ 
ПОЛЮСЫ ПРИ $z=-1$ И~$z=0$, $n^{-1-z}$ НЕ ИМЕЕТ ПОЛЮСОВ, a~$1/(2^{-1-z}-1)$ 
ИМЕЕТ ПРОСТЫЕ ПОЛЮСЫ ПРИ $z=-1+2\pi i k/\ln2$.

нАИБОЛЬШУЮ ТРУДНОСТЬ ПРЕДСТАВЛЯЕТ ДВОЙНОЙ ПОЛЮС В ТОЧКЕ~$z=-1$. еСЛИ 
$w=z+1$ МАЛО, ТО МОЖНО ВОСПОЛЬЗОВАТЬСЯ ИЗВЕСТНЫМ СООТНОШЕНИЕМ
$$
\Gamma(z+1)
=\exp(-\gamma z+\zeta(2)z^2/2-\zeta(3)z^3/3+\zeta(4)z^4/4-\ldots),
$$
ГДЕ~$\zeta(s)=1^{-s}+2^{-s}+3^{-s}+\ldots=H_\infty^{(s)}$, ДЛЯ ВЫВОДА 
СЛЕДУЮЩИХ РАЗЛОЖЕНИЙ:
$$
\eqalign{
\Gamma(z)&={\Gamma(w+1)\over w(w-1)}=-w^{-1}+(\gamma-1)+O(w);\cr
n^{-1-z}&=1-(\ln n)w+O(w^2);\cr
1/(2^{-1-z}-1)&=-w^{-1}/\ln2-{1\over2}+O(w).\cr
}
$$
вЫЧЕТ В ТОЧКЕ~$z=-1$ РАВЕН КОЭФФИЦИЕНТУ ПРИ $w^{-1}$ В ПРОИЗВЕДЕНИИ ЭТИХ 
ТРЕХ ФОРМУЛ, А ИМЕННО ${1\over2}-(\ln n+\gamma-1)/\ln2$. пРИБАВЛЯЯ 
ОСТАЛЬНЫЕ ВЫЧЕТЫ, ПОЛУЧАЕМ ФОРМУЛУ
$$
T_n/n={\ln n+\gamma-1\over \ln 2}-{1\over2}+f(n)+{2\over n},
\eqno(46)
$$
ГДЕ  $f(n)$---ФУНКЦИЯ ДОВОЛЬНО НЕОБЫЧНОГО ВИДА:
$$
f(n)={2\over\ln 2}
\sum_{k\ge1} \Re(\Gamma(-1-2\pi ik/\ln2)\exp(2\pi i k\log_2n)).
\eqno(47)
$$
зАМЕТИМ, ЧТО $f(n)=f(2n)$. сРЕДНЕЕ ЗНАЧЕНИЕ $f(n)$ РАВНО~0, ТАК КАК 
СРЕДНЕЕ ЗНАЧЕНИЕ КАЖДОГО СЛАГАЕМОГО РАВНО 0. (мОЖНО СЧИТАТЬ, ЧТО 
ВЕЛИЧИНА $(\log_2 n) \bmod 1$ РАСПРЕДЕЛЕНА РАВНОМЕРНО, ПРИНИМАЯ ВО 
ВНИМАНИЕ РЕЗУЛЬТАТЫ О ЧИСЛАХ С ПЛАВАЮЩЕЙ ТОЧКОЙ, ПОЛУЧЕННЫЕ В П.~4.2.4.) 
кРОМЕ ТОГО, ПОСКОЛЬКУ 
$\abs{\Gamma(-1+it)}=\abs{\pi/(t(1+t^2)\sinh \pi t)}^{1/2}$, НЕТРУДНО 
ПОКАЗАТЬ, ЧТО
$$
f(n)< 0.0000001725;
$$
ТАКИМ ОБРАЗОМ, В ПРАКТИЧЕСКИХ ПРИЛОЖЕНИЯХ $f(n)$ МОЖНО СПОКОЙНО 
ОТБРОСИТЬ. чТО КАСАЕТСЯ ТЕОРИИ, ТО БЕЗ~$f(n)$ МЫ НЕ МОЖЕМ
%%164
ПОЛУЧИТЬ АСИМПТОТИЧЕСКОГО РЯДА ДЛЯ $U_n$; ИМЕННО ПОЭТОМУ ВЕЛИЧИНА~$U_n$ 
СРАВНИТЕЛЬНО ТРУДНА ДЛЯ АНАЛИЗА. 
иТАК, МЫ ДОКАЗАЛИ, ЧТО
$$
U_n=n\log_2n+n\left({\gamma-1\over\ln2}-{1\over2}+f(n)\right)+O(1).
\eqno(48)
$$
дРУГИЕ ПРИМЕРЫ ПРИМЕНЕНИЯ ЭТОГО МЕТОДА ГАММА-ФУНКЦИЙ МОЖНО НАЙТИ В 
УПР.~51--53 И В \S~6.3.

\excercises
\ex[м20] пУСТЬ $a_1$ \dots $a_n$---ПЕРЕСТАНОВКА МНОЖЕСТВА $\{1, \ldots, n\}$, 
И ПУСТЬ $i$ И $j$ ТАКОВЫ, ЧТО $i<j$ И~$a_i>a_j$. пУСТЬ $a'_1$ \dots 
$a'_n$---ПЕРЕСТАНОВКА, КОТОРАЯ ПОЛУЧАЕТСЯ ИЗ $a_1$ \dots $a_n$, ЕСЛИ 
ПОМЕНЯТЬ МЕСТАМИ $a_i$ И $a_j$. мОЖЕТ ЛИ В $a'_1$ \dots $a'_n$ БЫТЬ БОЛЬШЕ 
ИНВЕРСИЙ, ЧЕМ В $a_1$ \dots $a_n$?

\rex[м25] (a) кАКОВО МИНИМАЛЬНОЕ ЧИСЛО ОБМЕНОВ, НЕОБХОДИМОЕ ДЛЯ ТОГО,
 ЧТОБЫ ОТСОРТИРОВАТЬ ПЕРЕСТАНОВКУ 3\ 7\ 6\ 9\ 8\ 1\ 4\ 5? (b) вООБЩЕ ПУСТЬ 
ДАНА ПЕРЕСТАНОВКА $\pi=a_1\ \ldots\ a_n$ МНОЖЕСТВА $\{1, \ldots, n\}$, И 
ПУСТЬ 
$\mathop{\rm xch}\nolimits (\pi)$---МИНИМАЛЬНОЕ ЧИСЛО ОБМЕНОВ, В РЕЗУЛЬТАТЕ 
КОТОРЫХ ПЕРЕСТАНОВКА $\pi$ БУДЕТ ОТСОРТИРОВАНА В ВОЗРАСТАЮЩЕМ ПОРЯДКЕ. 
вЫРАЗИТЕ $\mathop{\rm xch}\nolimits (\pi)$, ЧЕРЕЗ "БОЛЕЕ ПРОСТЫЕ" 
ХАРАКТЕРИСТИКИ ПЕРЕСТАНОВКИ~$\pi$. (сР. С УПР. 5 2.1--39.)

\ex[10] яВЛЯЕТСЯ ЛИ УСТОЙЧИВОЙ СОРТИРОВКА МЕТОДОМ ПУЗЫРЬКА (АЛГОРИТМ B)?

\ex[м23] еСЛИ В ШАГЕ B4 ПОЛУЧИТСЯ $t=1$, ТО НА САМОМ ДЕЛЕ РАБОТУ 
АЛГОРИТМА~B МОЖНО СРАЗУ ЖЕ ЗАКАНЧИВАТЬ, ПОТОМУ ЧТО В СЛЕДУЮЩЕМ ШАГЕ B2 
НЕ ВЫПОЛНИТСЯ НИКАКИХ ПОЛЕЗНЫХ ДЕЙСТВИЙ. кАКОВА ВЕРОЯТНОСТЬ ТОГО, ЧТО 
ПРИ СОРТИРОВКЕ СЛУЧАЙНОЙ ПЕРЕСТАНОВКИ В ШАГЕ B4 ОКАЖЕТСЯ $t=1$?

\ex[м25] пУСТЬ $b_1$ $b_2$ \dots $b_n$---ТАБЛИЦА ИНВЕРСИЙ ПЕРЕСТАНОВКИ $a_1$ 
$a_2$ \dots $a_n$. пОКАЖИТЕ, ЧТО ПОСЛЕ $r$ ПРОСМОТРОВ СОРТИРОВКИ МЕТОДОМ 
ПУЗЫРЬКА ЗНАЧЕНИЕ ПЕРЕМЕННОЙ |BOUND| РАВНО $\max \{b_i+i \mid b_i\ge 
r\}-r$, ГДЕ 
$0\le r\le \max(b_1, \ldots, b_n)$.

\ex[м22] пУСТЬ $a_1$ \dots{} $a_n$---ПЕРЕСТАНОВКА МНОЖЕСТВА $\{1, \dots, 
n\}$, И ПУСТЬ $a'_1$ \dots{} $a'_n$---ОБРАТНАЯ К НЕЙ ПЕРЕСТАНОВКА. пОКАЖИТЕ, 
ЧТО ЧИСЛО ПРОСМОТРОВ, НЕОБХОДИМЫХ ДЛЯ ТОГО, ЧТОБЫ ОТСОРТИРОВАТЬ $a_1$ 
\dots{} $a_n$" МЕТОДОМ ПУЗЫРЬКА. РАВНО $1+\max(a'_1-1, a'_2-2, \ldots, a'_n-n)$.

\ex[м28] вЫЧИСЛИТЕ СТАНДАРТНОЕ ОТКЛОНЕНИЕ ЧИСЛА ПРОСМОТРОВ 
СОРТИРОВКИ МЕТОДОМ ПУЗЫРЬКА И ВЫРАЗИТЕ ЕГО ЧЕРЕЗ $n$ И ФУНКЦИЮ $P(n)$. [сР.
 С ФОРМУЛАМИ (6) И (7).]

\ex[м24] вЫВЕДИТЕ ФОРМУЛУ (8).

\ex[м48] пРОАНАЛИЗИРУЙТЕ ЧИСЛО ПРОСМОТРОВ И ЧИСЛО СРАВНЕНИЙ В АЛГОРИТМЕ 
ШЕЙКЕР-СОРТИРОВКИ. (\emph{зАМЕЧАНИЕ:} ЧАСТИЧНАЯ ИНФОРМАЦИЯ СОДЕРЖИТСЯ В 
УПР. 5.4.8--9.)

\ex[м26] пУСТЬ $a_1$ $a_2$ \dots{} $a_n$---2-УПОРЯДОЧЕННАЯ ПЕРЕСТАНОВКА 
МНОЖЕСТВА  $\{1, 2, \ldots, n\}$. (a) кАКОВЫ КООРДИНАТЫ КОНЕЧНЫХ ТОЧЕК 
$a_i\hbox{-ГО}$ 
ШАГА СООТВЕТСТВУЮЩЕГО РЕШЕТОЧНОГО ПУТИ 
(СР. С РИС.~11)? (b) дОКАЖИТЕ, ЧТО СРАВНЕНИЕ/ОБМЕН
ЭЛЕМЕНТОВ $a_1$: $a_2$, $a_3$, $a_4$, \dots СООТВЕТСТВУЕТ ПЕРЕГИБАНИЮ ПУТИ ОТНОСИТЕЛЬНО
ДИАГОНАЛИ, КАК НА РИС.~18(b). (С) дОКАЖИТЕ, ЧТО СРАВНЕНИЕ/ОБМЕН ЭЛЕМЕНТОВ
$a_2$: $a_{2+d}$, $a_4$:$a_{4+d}$, \dots{} СООТВЕТСТВУЕТ ПЕРЕГИБАНИЮ ПУТИ 
ОТНОСИТЕЛЬНО ЛИНИИ, 
РАСПОЛОЖЕННОЙ НА $m$ ЕДИНИЦ НИЖЕ ДИАГОНАЛИ, КАК НА РИС. 18(С), (d) И (e), ЕСЛИ
$d=2m-l$.

\rex[м25] нА КАКОЙ ПЕРЕСТАНОВКЕ МНОЖЕСТВА $\{1, 2, \ldots, 16\}$ 
ДОСТИГАЕТСЯ МАКСИМУМ ЧИСЛА ОБМЕНОВ В АЛГОРИТМЕ бЭТЧЕРА?

\ex[24] нАПИШИТЕ \MIX-ПРОГРАММУ ДЛЯ АЛГОРИТМА M, ПРЕДПОЛАГАЯ, 
ЧТО \MIX---ДВОИЧНАЯ ВЫЧИСЛИТЕЛЬНАЯ МАШИНА С ОПЕРАЦИЯМИ |AND| И |SRB|. 
сКОЛЬКО ВРЕМЕНИ ПОТРЕБУЕТСЯ ВАШЕЙ ПРОГРАММЕ, ЧТОБЫ ОТСОРТИРОВАТЬ 
ШЕСТНАДЦАТЬ ЗАПИСЕЙ ИЗ ТАБЛ.~1?
%%165

\ex [10] уСТОЙЧИВА ЛИ СОРТИРОВКА бЭТЧЕРА?

\ex [м21] пУСТЬ $c(N)$---ЧИСЛО СРАВНЕНИЙ КЛЮЧЕЙ, ПРОИЗВОДИМЫХ ПРИ 
СОРТИРОВКЕ $N$ ЭЛЕМЕНТОВ МЕТОДОМ бЭТЧЕРА; ЭТО РАВНО ЧИСЛУ ВЫПОЛНЕНИИ 
ШАГА M4.
(a) пОКАЖИТЕ, ЧТО ПРИ $t\ge 1$ $c(2^t)=2c(2^{t-1}+(t-1)2^{t-1}+1.$
(b) нАЙДИТЕ ПРОСТОЕ ВЫРАЖЕНИЕ ДЛЯ $c(2^t)$ КАК ФУНКЦИЮ ОТ~$t$. 
(\emph{уКАЗАНИЕ:} РАССМОТРИТЕ ПОСЛЕДОВАТЕЛЬНОСТЬ $x_t=c(2^t)/2^t)$.

\ex[м38] сОДЕРЖАНИЕ ЭТОГО УПРАЖНЕНИЯ---АНАЛИЗ ФУНКЦИИ $c(N)$ ИЗ УПР.~14
И НАХОЖДЕНИЕ ФОРМУЛЫ ДЛЯ $c(N)$, ЕСЛИ $N=2^{e_1}+2^{e_2}+\cdots+2^{e_r}$, 
$e_1>e_2>\ldots>e_r\ge0$. (a) пУСТЬ $a(N)=c(N+1)-c(N)$. дОКАЖИТЕ, ЧТО 
$a(2n)=a(n)+\floor{\log_2(2n)}$, $a(2n+1)=a(n)+1$;  ОТСЮДА
$$
a(N)=\perm{e_1+1}{2}-r(e_1-1)+(e_1+e_2+\cdots+e_r).
$$
(b) пУСТЬ $x(n)=a(n)-a(\floor{n/2})$,  И ТОГДА  
$a(n)=x(n)+x(\floor{n/2})+x(\floor{n/4})+\cdots$. пУСТЬ 
$y(n)=x(1)+x(2)+\cdots+x(n)$, И 
ПУСТЬ~$z(2n)=y(2n)-a(n)$, $z(2n+1)=y(2n+1)$.  дОКАЖИТЕ, ЧТО 
$c(N+1)=z(N)+2z(\floor{N/2})+4z(\floor{N/4})+\cdots$. (c) дОКАЖИТЕ,ЧТО 
$y(N)=N+(\floor{N/2}+1)\times(e_1-1)-2^{e_1}+2$. (d) тЕПЕРЬ СОБЕРИТЕ ВСЕ 
ВМЕСТЕ И НАЙДИТЕ ВЫРАЖЕНИЕ $c(N)$ ЧЕРЕЗ ПОКАЗАТЕЛИ $e_j$ ПРИ ФИКСИРОВАННОМ 
ЗНАЧЕНИИ $r$.

\ex[вм46] нАЙДИТЕ АСИМПТОТИЧЕСКОЕ ЗНАЧЕНИЕ СРЕДНЕГО ЧИСЛА ОБМЕНОВ В СЛУЧАЕ,
 КОГДА АЛГОРИТМ бЭТЧЕРА ПРИМЕНЯЕТСЯ К $N=2^t$ РАЗЛИЧНЫМ ЭЛЕМЕНТАМ, 
РАСПОЛОЖЕННЫМ В СЛУЧАЙНОМ ПОРЯДКЕ.

\rex[20] гДЕ В АЛГОРИТМЕ Q ИСПОЛЬЗУЕТСЯ ТО, ЧТО $K_0$ И~$K_{N+1}$ 
ОБЛАДАЮТ ЗНАЧЕНИЯМИ, ПОСТУЛИРОВАННЫМИ НЕРАВЕНСТВАМИ (13)?

\rex[20] оБ®ЯСНИТЕ, КАК РАБОТАЕТ АЛГОРИТМ Q В СЛУЧАЕ, КОГДА ВСЕ КЛЮЧИ В 
ИСХОДНОМ ФАЙЛЕ РАВНЫ. чТО ПРОИЗОЙДЕТ, ЕСЛИ В ШАГАХ Q3 И Q5 ЗАМЕНИТЬ ЗНАКИ 
"$<$" НА "$\le$"?

\ex[15] бУДЕТ ЛИ АЛГОРИТМ Q ПО-ПРЕЖНЕМУ РАБОТАТЬ ПРАВИЛЬНО, ЕСЛИ ВМЕСТО 
СТЕКА (ПОСЛЕДНИМ ВКЛЮЧАЕТСЯ---ПЕРВЫМ ИСКЛЮЧАЕТСЯ) ВОСПОЛЬЗОВАТЬСЯ ОЧЕРЕДЬЮ 
(ПЕРВЫМ ВКЛЮЧАЕТСЯ---ПЕРВЫМ ИСКЛЮЧАЕТСЯ)?

\ex[м20] вЫРАЗИТЕ НАИБОЛЬШЕЕ ЧИСЛО ЭЛЕМЕНТОВ, КОТОРЫЕ МОГУТ ОДНОВРЕМЕННО 
ОКАЗАТЬСЯ В СТЕКЕ ВО ВРЕМЯ РАБОТЫ АЛГОРИТМА Q, В ВИДЕ ФУНКЦИИ ОТ~M И~$N$.

\ex[20] оБ®ЯСНИТЕ, ПОЧЕМУ ФАЗА РАЗДЕЛЕНИЯ В АЛГОРИТМЕ Q ТРЕБУЕТ КАК РАЗ 
ТАКОГО ЧИСЛА СРАВНЕНИЙ, ПЕРЕСЫЛОК И Т. Д., КАК ЭТО ОПИСАНО В (17).

\ex[м25] пУСТЬ $p_kN$---ВЕРОЯТНОСТЬ ТОГО, ЧТО ВЕЛИЧИНА~$A$ В (14) 
БУДЕТ РАВНА~$k$, ЕСЛИ АЛГОРИТМ Q ПРИМЕНЯЕТСЯ К СЛУЧАЙНОЙ ПЕРЕСТАНОВКЕ МНОЖЕСТВА
$\{1, 2, \ldots, N\}$, И ПУСТЬ~$A_N(z)=\sum_k p_kN^{z^k}$---СООТВЕТСТВУЮЩАЯ 
ПРОИЗВОДЯЩАЯ ФУНКЦИЯ.   дОКАЖИТЕ,   ЧТО~$A_N(z)=1$   ПРИ~$N\le M$,   
И~$A_N(z)= z(\sum_{1\le s\le N} A_{s-1}(z)A_{N-s}(z))/N$ ПРИ~$N>M$. 
нАЙДИТЕ АНАЛОГИЧНЫЕ РЕКУРРЕНТНЫЕ СООТНОШЕНИЯ, ОПРЕДЕЛЯЮЩИЕ ДРУГИЕ 
РАСПРЕДЕЛЕНИЯ ВЕРОЯТНОСТЕЙ $B_N(z)$, $C_N(z)$, $D_N(z)$, $E_N(z)$, 
$L_N(z)$, $X_N(z)$.

\ex[м24] пУСТЬ $A_N$, $B_N$, $D_N$, $E_N$, $L_N$, $X_N$---СРЕДНИЕ ЗНАЧЕНИЯ 
СООТВЕТСТВУЮЩИХ ВЕЛИЧИН В (14) ПРИ СОРТИРОВКЕ СЛУЧАЙНОЙ 
ПЕРЕСТАНОВКИ-МНОЖЕСТВА $\{1, 2, \ldots, N\}$. нАЙДИТЕ ДЛЯ ЭТИХ ВЕЛИЧИН 
РЕКУРРЕНТНЫЕ СООТНОШЕНИЯ, АНАЛОГИЧНЫЕ (18), ЗАТЕМ РАЗРЕШИТЕ ЭТИ 
СООТНОШЕНИЯ И ПОЛУЧИТЕ ФОРМУЛЫ (25).

\ex[м21] оЧЕВИДНО, В АЛГОРИТМЕ Q ПРОИЗВОДИТСЯ НЕСКОЛЬКО БОЛЬШЕ СРАВНЕНИЙ, 
ЧЕМ ЭТО НЕОБХОДИМО, ПОТОМУ ЧТО В ШАГАХ Q3 И Q5 МОЖЕТ ОКАЗАТЬСЯ, ЧТО $i=j$ 
ИЛИ ДАЖЕ $i>j$. сКОЛЬКО СРАВНЕНИЙ $G_N$ ПРОИЗВОДИЛОСЬ БЫ В СРЕДНЕМ, ЕСЛИ 
БЫ ИСКЛЮЧАЛИСЬ ВСЕ СРАВНЕНИЯ ПРИ $i\ge j$?

\ex[м20] чЕМУ РАВНЫ ТОЧНЫЕ ЗНАЧЕНИЯ ВЕЛИЧИН $A$, $B$, $C$, $D$, $E$, $L$, 
$X$ ДЛЯ ПРОГРАММЫ Q В СЛУЧАЕ, КОГДА ИСХОДНЫЕ КЛЮЧИ ПРЕДСТАВЛЯЮТ СОБОЙ 
УПОРЯДОЧЕННЫЙ НАБОР ЧИСЕЛ $1$, $2$, \dots, $N$ В ПРЕДПОЛОЖЕНИИ, ЧТО $N>M$? 

\rex[M21] пОСТРОЙТЕ ИСХОДНЫЙ ФАЙЛ, ПРИ КОТОРОМ ПРОГРАММА Q РАБОТАЛА БЫ 
ЕЩЕ МЕДЛЕННЕЕ, ЧЕМ В УПР.~25. (пОПЫТАЙТЕСЬ НАЙТИ ДЕЙСТВИТЕЛЬНО ПЛОХОЙ СЛУЧАЙ.)

%% 166
\ex[м23] кАКОЙ ИСХОДНЫЙ ФАЙЛ БУДЕТ \emph{НАИЛУЧШИМ} ДЛЯ 
АЛГОРИТМА~Q? нАЙДИТЕ ПРИБЛИЗИТЕЛЬНЫЕ ЗНАЧЕНИЯ ВЕЛИЧИН~$A$, $B$, $C$, $D$, 
$E$, $X$ ДЛЯ ЭТОГО СЛУЧАЯ.

\ex[M26] нАЙДИТЕ РЕКУРРЕНТНОЕ СООТНОШЕНИЕ, АНАЛОГИЧНОЕ~(20), 
КОТОРОМУ УДОВЛЕТВОРЯЕТ СРЕДНЕЕ ЧИСЛО СРАВНЕНИЙ В АЛГОРИТМЕ~Q, 
МОДИФИЦИРОВАННОМ сИНГЛТОНОМ (Т.~Е.\ КОГДА В КАЧЕСТВЕ~$s$ ВЫБИРАЕТСЯ 
НЕ~$s=K_1$, А МЕДИАНА ИЗ~$\set{K_1, K_{\floor{(N+1)/2}}, K_N}$).

\ex[вм40] нАЙДИТЕ АСИМПТОТИЧЕСКОЕ ЗНАЧЕНИЕ ЧИСЛА СРАВНЕНИЙ В АЛГОРИТМЕ 
сИНГЛТОНА "МЕДИАНА ИЗ ТРЕХ" (СМ.~УПР.~28).

\ex[25] (п.~шАКЛЕТОН.) пРИ СОРТИРОВКЕ \emph{КЛЮЧЕЙ ДЛИНОЙ В НЕСКОЛЬКО 
СЛОВ} МНОГИЕ АЛГОРИТМЫ ВСЕ БОЛЕЕ ЗАМЕДЛЯЮТСЯ ПО МЕРЕ ТОГО, КАК ФАЙЛ 
ПРИБЛИЖАЕТСЯ К УПОРЯДОЧЕННОМУ СОСТОЯНИЮ, ПОСКОЛЬКУ ДЛЯ ОПРЕДЕЛЕНИЯ 
ПРАВИЛЬНОГО ЛЕКСИКОГРАФИЧЕСКОГО ПОРЯДКА РАВНЫХ ИЛИ ПОЧТИ РАВНЫХ КЛЮЧЕЙ 
ТРЕБУЕТСЯ СРАВНИТЬ НЕСКОЛЬКО ПАР СЛОВ (СМ.~УПР.~5-5). фАЙЛЫ, КОТОРЫЕ 
ВСТРЕЧАЮТСЯ НА ПРАКТИКЕ, ЧАСТО СОДЕРЖАТ ПОЧТИ РАВНЫЕ КЛЮЧИ, И ЭТО 
ЯВЛЕНИЕ МОЖЕТ ЗАМЕТНО ОТРАЗИТЬСЯ НА ВРЕМЕНИ СОРТИРОВКИ.

тАКОЕ ЗАТРУДНЕНИЕ СУЩЕСТВЕННО ДЛЯ АЛГОРИТМА~Q, НО НЕ ДЛЯ АЛГОРИТМА~R,
ПОСКОЛЬКУ ТАМ КАЖДЫЙ РАЗ ПРОВЕРЯЕТСЯ ТОЛЬКО ОДИН БИТ (ХОТЯ 
ПРИСУТСТВИЕ РАВНЫХ И ПОЧТИ РАВНЫХ КЛЮЧЕЙ МОЖЕТ СИЛЬНО УВЕЛИЧИТЬ ВРЕМЯ 
РАБОТЫ АЛГОРИТМА~R ПО ДРУГИМ ПРИЧИНАМ).

оБ®ЯСНИТЕ, КАК МОЖНО УСОВЕРШЕНСТВОВАТЬ АЛГОРИТМ~Q, ЧТОБЫ ИЗБЕЖАТЬ ЭТОГО 
ЗАТРУДНЕНИЯ; В ПОДФАЙЛЕ, О КОТОРОМ ИЗВЕСТНО, ЧТО СТАРШИЕ $k$~СЛОВ ВО ВСЕХ 
КЛЮЧАХ СОДЕРЖАТ ПОСТОЯННЫЕ ЗНАЧЕНИЯ, СЛЕДУЕТ ПРОВЕРЯТЬ ЛИШЬ 
$(k+1)\hbox{-Е}$~СЛОВА КЛЮЧЕЙ.

\rex[20] (ч.~э.~р.~хОАР) пРЕДПОЛОЖИМ, ЧТО НАМ НУЖНО НЕ ОТСОРТИРОВАТЬ ФАЙЛ, А 
ЛИШЬ ОПРЕДЕЛИТЬ $m\hbox{-Й}$ НАИМЕНЬШИЙ ПО ВЕЛИЧИНЕ ЭЛЕМЕНТ ИЗ 
ЗАДАННОГО МНОЖЕСТВА $n$~ЭЛЕМЕНТОВ. пОКАЖИТЕ, ЧТО "БЫСТРУЮ СОРТИРОВКУ" 
МОЖНО ПРИСПОСОБИТЬ ДЛЯ ЭТОЙ ЦЕЛИ, ИЗБЕЖАВ ЗНАЧИТЕЛЬНОЙ ЧАСТИ ВЫЧИСЛЕНИЙ, 
НЕОБХОДИМЫХ ДЛЯ ПОЛНОЙ СОРТИРОВКИ.

\ex[м40] нАЙДИТЕ ПРОСТОЕ ВЫРАЖЕНИЕ "В ЗАМКНУТОМ ВИДЕ" 
ДЛЯ~$C_{nm}$---СРЕДНЕГО ЧИСЛА СРАВНЕНИЙ КЛЮЧЕЙ, НЕОБХОДИМЫХ ДЛЯ ОТЫСКАНИЯ 
$m\hbox{-ГО}$~НАИМЕНЬШЕГО ИЗ $n$~ЭЛЕМЕНТОВ ПО МЕТОДУ УПР.~31. (дЛЯ 
ПРОСТОТЫ МОЖНО ПРОПУСКАТЬ ВСЕ СРАВНЕНИЯ С~$i\ge j$, КАК В УПР.~24.) кАКОВО 
АСИМПТОТИЧЕСКОЕ ПОВЕДЕНИЕ ВЕЛИЧИНЫ~$C_{(2m-1)m}$---СРЕДНЕГО ЧИСЛА СРАВНЕНИЙ, 
НЕОБХОДИМЫХ ДЛЯ НАХОЖДЕНИЯ МЕДИАНЫ ИЗ $2m-1$~ЭЛЕМЕНТОВ МЕТОДОМ хОАРА?

\rex[20] рАЗРАБОТАЙТЕ АЛГОРИТМ ПЕРЕРАЗМЕЩЕНИЯ ЧИСЕЛ В НЕКОТОРОЙ ЗАДАННОЙ 
ТАБЛИЦЕ ТАКИМ ОБРАЗОМ, ЧТОБЫ ВСЕ ОТРИЦАТЕЛЬНЫЕ ЗНАЧЕНИЯ ПРЕДШЕСТВОВАЛИ 
ПОЛОЖИТЕЛЬНЫМ. эЛЕМЕНТЫ НЕ НУЖНО ПОЛНОСТЬЮ СОРТИРОВАТЬ:
ДОСТАТОЧНО ПРОСТО ОТДЕЛИТЬ ОТРИЦАТЕЛЬНЫЕ ЧИСЛА ОТ ПОЛОЖИТЕЛЬНЫХ. 
вАШ АЛГОРИТМ ДОЛЖЕН ПРОИЗВОДИТЬ МИНИМАЛЬНО ВОЗМОЖНОЕ ЧИСЛО ОБМЕНОВ.

\ex[20] кАК МОЖНО УСКОРИТЬ ЦИКЛЫ ПРОВЕРКИ БИТОВ В ОБМЕННОЙ ПОРАЗРЯДНОЙ 
СОРТИРОВКЕ (ШАГИ ОТ~R3 ДО~R6)?

\ex[м23] пРОАНАЛИЗИРУЙТЕ СТАТИСТИЧЕСКИЕ ХАРАКТЕРИСТИКИ~$A$, $B$, $C$, $G$,
$K$, $L$, $R$, $S$ И~$X$, КОТОРЫЕ ПОЛУЧАЮТСЯ ПРИ ОБМЕННОЙ ПОРАЗРЯДНОЙ 
СОРТИРОВКЕ ДЛЯ "ИСХОДНЫХ ДАННЫХ ТИПА~(i)".

\ex[м27] дЛЯ ЛЮБОЙ ДАННОЙ ПОСЛЕДОВАТЕЛЬНОСТИ ЧИСЕЛ~$\< a_n >=a_0$, $a_1$,
$a_2$,~\dots{} ОПРЕДЕЛИМ ЕЕ \dfn{БИНОМИАЛЬНОЕ-ПРЕОБРАЗОВАНИЕ} 
$\<\hat a>_n=\hat a_0$, $\hat a_1$, $\hat a_2$,~\dots{} ПРАВИЛОМ
$$
\hat a_n = \sum_k \perm{n}{k} (-1)^k a_k.
$$
(a)~дОКАЖИТЕ, ЧТО~$\<\hat {\hat a}_n>=\< a_n>$. (b)~нАЙДИТЕ БИНОМИАЛЬНЫЕ 
ПРЕОБРАЗОВАНИЯ ПОСЛЕДОВАТЕЛЬНОСТЕЙ~$\<1>$; $\<n>$; $\<\perm{n}{m}>$ ПРИ 
ФИКСИРОВАННОМ~$m$; $\<a^n>$ ПРИ ФИКСИРОВАННОМ~$a$; $\<\perm{n}{m}a^n>$ ПРИ 
ФИКСИРОВАННЫХ~$a$ И~$m$. (c)~пРИ УСЛОВИИ, ЧТО
%% 167
ПОСЛЕДОВАТЕЛЬНОСТЬ~$\<x_n>$ УДОВЛЕТВОРЯЕТ СООТНОШЕНИЮ
$$
x_n=a_n+2^{1-n}\sum_{k\ge 2} \perm{n}{k}x_k 
\rem{ПРИ~$n\ge 2$, $x_0=x_1=a_0=a_1=0$,}
$$
ДОКАЖИТЕ, ЧТО
$$
x_n=\sum_{k\ge 2}\perm{n}{k}(-1)^k{2^{k-1}\hat a_k \over 2^{k-1}-1}=
a_n+\sum_{k\ge 2}\perm{n}{k}(-1)^k{\hat a_k \over 2^{k-1}-1}.
$$

\ex[M28] оПРЕДЕЛИТЕ ВСЕ ТАКИЕ ПОСЛЕДОВАТЕЛЬНОСТИ~$\< a_n>$, 
ЧТО~$\<\hat a_n>=\<a_n>$ В СМЫСЛЕ УПР.~36.

\rex[M30] нАЙДИТЕ~$A_N$, $B_N$, $C_N$, $G_N$, $K_N$, $L_N$, $R_N$, 
И~$X_N$---СРЕДНИЕ ЗНАЧЕНИЯ ВЕЛИЧИН~(29)---В СЛУЧАЕ, КОГДА ПОРАЗРЯДНОЙ 
СОРТИРОВКЕ ПОДВЕРГАЮТСЯ "ИСХОДНЫЕ ДАННЫЕ ТИПА~(ii)". вЫРАЗИТЕ ВАШИ ОТВЕТЫ 
ЧЕРЕЗ~$N$ И ФУНКЦИИ
$$
U_n=\sum_{k\ge 2}\perm{n}{k}{(-1)^k \over 2^{k-1}-1},\qquad
V_n=\sum_{k\ge 2}\perm{n}{k}{(-1)^k k \over 2^{k-1}-1}=n(U_n-U_{n-1}).
$$
[\emph{уКАЗАНИЕ:} СМ.~УПР.~36.]

\ex[20] рЕЗУЛЬТАТЫ~(30) ПОКАЗЫВАЮТ, ЧТО ПОРАЗРЯДНАЯ ОБМЕННАЯ СОРТИРОВКА, 
ПРИМЕНЕННАЯ К СЛУЧАЙНЫМ ВХОДНЫМ ДАННЫМ, ТРЕБУЕТ ОКОЛО $1.44$~СТАДИЙ. 
дОКАЖИТЕ, ЧТО БЫСТРАЯ СОРТИРОВКА НИКОГДА НЕ ТРЕБУЕТ БОЛЕЕ $N$~СТАДИЙ, И 
ОБ®ЯСНИТЕ, ПОЧЕМУ ПРИ ОБМЕННОЙ ПОРАЗРЯДНОЙ СОРТИРОВКЕ ЧАСТО 
БЫВАЕТ НЕОБХОДИМО БОЛЕЕ $N$~СТАДИЙ.

\ex[21] оБ®ЯСНИТЕ, КАК НУЖНО ИЗМЕНИТЬ АЛГОРИТМ~R, ЧТОБЫ ОН 
РАБОТАЛ ДОСТАТОЧНО ЭФФЕКТИВНО И ТОГДА, КОГДА СОРТИРУЕМЫЕ ФАЙЛЫ СОДЕРЖАТ 
МНОГО РАВНЫХ КЛЮЧЕЙ.

\ex[23] дАЙТЕ ТОЧНОЕ ОПИСАНИЕ АЛГОРИТМА "ИНТЕРВАЛЬНОЙ ОБМЕННОЙ 
СОРТИРОВКИ" вАН эМДЕНА.

\ex[м43] пРОАНАЛИЗИРУЙТЕ АЛГОРИТМ ИНТЕРВАЛЬНОЙ ОБМЕННОЙ СОРТИРОВКИ ИЗ УПР.~41.

\ex[вм21] дОКАЖИТЕ, 
ЧТО~$\int_0^1 y^{-1}(e^{-y}-1)\,dy +\int_1^\infty y^{-1}e^{-y}\,dy=-\gamma$. 
[\emph{уКАЗАНИЕ:} РАССМОТРИТЕ~$\lim_{a\to 0+} y^{a-1}$.]

\ex[вм24] вЫВЕДИТЕ ФОРМУЛУ~(37), КАК ЭТО ПРЕДЛОЖЕНО В ТЕКСТЕ НАСТОЯЩЕГО ПУНКТА.

\ex[вм20] оБ®ЯСНИТЕ, ПОЧЕМУ ПРИ~$x>0$ СПРАВЕДЛИВО РАВЕНСТВО~(43).

\ex[вм20] кАКОВО ЗНАЧЕНИЕ 
ВЫРАЖЕНИЯ~$(1/2\pi i) \int_{a-i\infty}^{a+i\infty}\Gamma(z) n^{s-z}\,dz/(2^{s-z}-1)$
ПРИ УСЛОВИИ, ЧТО~$s$---ЦЕЛОЕ ПОЛОЖИТЕЛЬНОЕ ЧИСЛО И~$0<a<s$?

\ex[вм21] дОКАЖИТЕ, ЧТО~$\sum_{j\ge1} (n/2^j) e^{-n/2^j}$---ОГРАНИЧЕННАЯ 
ФУНКЦИЯ ОТ~$n$.

\ex[вм24] нАЙДИТЕ АСИМПТОТИЧЕСКОЕ ЗНАЧЕНИЕ ВЕЛИЧИНЫ~$V_n$, ОПРЕДЕЛЕННОЙ 
В УПР.~38, ПРИ ПОМОЩИ МЕТОДОВ, АНАЛОГИЧНЫХ ТЕМ, КОТОРЫМИ В 
ТЕКСТЕ НАСТОЯЩЕГО ПУНКТА ИССЛЕДОВАЛАСЬ ВЕЛИЧИНА~$U_n$, И ПОЛУЧИТЕ ЧЛЕНЫ ДО~$O(1)$.

\ex[вм24] пРОДОЛЖИТЕ АСИМПТОТИЧЕСКУЮ ФОРМУЛУ~(47) ДЛЯ~$U_n$ ДО ЧЛЕНОВ ПОРЯДКА~$O(n^{-1})$.

\ex[вм24] нАЙДИТЕ АСИМПТОТИЧЕСКОЕ ЗНАЧЕНИЕ ФУНКЦИИ
$$
U_{mn}=\sum_{k\ge 2}\perm{n}{k}(-1)^k{1\over m^{k-1}-1},
$$
ГДЕ~$m$---ПРОИЗВОЛЬНОЕ ФИКСИРОВАННОЕ ЧИСЛО, БОЛЬШЕЕ~1. (эТА ВЕЛИЧИНА 
ПРИ~$m$~ЦЕЛОМ БОЛЬШЕМ~$2$ ПОТРЕБУЕТСЯ ПРИ ИССЛЕДОВАНИИ ОБОБЩЕНИЙ ОБМЕННОЙ
ПОРАЗРЯДНОЙ
%%168
СОРТИРОВКИ, А ТАКЖЕ ПРИ ИЗУЧЕНИИ АЛГОРИТМОВ ПОИСКА В 
"БОРОВОЙ ПАМЯТИ" В \S~6.3.)

\rex[вм28] пОКАЖИТЕ, ЧТО ДЛЯ ВЫВОДА АСИМПТОТИЧЕСКОГО РАЗЛОЖЕНИЯ~$r_k(m)$ 
МОЖНО ВОСПОЛЬЗОВАТЬСЯ МЕТОДОМ ИССЛЕДОВАНИЯ АСИМПТОТИЧЕСКИХ ЗАДАЧ ПРИ 
ПОМОЩИ ГАММА-ФУНКЦИЙ ВМЕСТО ФОРМУЛЫ СУММИРОВАНИЯ эЙЛЕРА (СР.~С~(35)). эТО 
ДАЕТ НАМ ЕДИНООБРАЗНЫЙ СПОСОБ ИЗУЧЕНИЯ~$r_k(m)$ ПРИ ВСЕХ~$k$, НЕ 
ПОЛАГАЯСЬ НА ТАКИЕ "ТРЮКИ", КАК ВВЕДЕНИЕ ФУНКЦИИ~$g_{-1}(x)=(e^{-x^2}-1)/x$.

\ex[вм35] (н.~г.~ДЕ~бРЕЙН.) кАКОВО АСИМПТОТИЧЕСКОЕ ПОВЕДЕНИЕ СУММЫ
$$
S_n=\sum_{t\ge 1} \left({2n \over n+t}\right) d(t),
$$
ГДЕ~$d(t)$---КОЛИЧЕСТВО ДЕЛИТЕЛЕЙ ЧИСЛА~$t$? (тАК, $d(1)=1$, $d(2)=d(3)=2$,
 $d(4)=3$, $d(5)=2$ И~Т.~Д. эТОТ ВОПРОС ВОЗНИКАЕТ В СВЯЗИ С АНАЛИЗОМ 
АЛГОРИТМА ПРОХОЖДЕНИЯ ДЕРЕВА; УПР.~2.3.1-11.) нАЙДИТЕ ЗНАЧЕНИЕ 
ВЕЛИЧИНЫ~$S_n/\perm{2n}{n}$ ДО ЧЛЕНОВ ПОРЯДКА~$O(n^{-1})$.

\ex[вм42] пРОАНАЛИЗИРУЙТЕ ЧИСЛО ПРОВЕРОК БИТОВ И ЧИСЛО ОБМЕНОВ,
ВЫПОЛНЯЕМЫХ ПРИ ОБМЕННОЙ ПОРАЗРЯДНОЙ СОРТИРОВКЕ, ЕСЛИ ИСХОДНЫМИ 
ДАННЫМИ СЛУЖАТ ДВОИЧНЫЕ ЧИСЛА С БЕСКОНЕЧНОЙ ТОЧНОСТЬЮ ИЗ ПРОМЕЖУТКА~$[0,1)$,
КАЖДЫЙ БИТ КОТОРЫХ НЕЗАВИСИМО ПРИНИМАЕТ ЗНАЧЕНИЕ~$1$ С 
ВЕРОЯТНОСТЬЮ~$p$. (в ОСНОВНОМ ТЕКСТЕ ПУНКТА ОБСУЖДАЛСЯ ЛИШЬ 
СЛУЧАЙ~$p={1\over 2}$; ПРИМЕНЯВШИЕСЯ МЕТОДЫ МОЖНО ОБОБЩИТЬ НА СЛУЧАЙ 
ПРОИЗВОЛЬНОГО~$p$.) рАССМОТРИТЕ ОСОБО СЛУЧАЙ~$p=1/\phi=.61803\ldots\,$.

\ex[вм24] (с.~о.~рАЙЕ.) пОКАЖИТЕ, ЧТО~$U_n$ МОЖНО ЗАПИСАТЬ В ВИДЕ
$$
U_n=(-1)^n {n!\over 2\pi i} \oint_C {dz \over z(z-1)\ldots(z-n)}{1\over 
2^{z-1}-1},
$$
ГДЕ~$C$---ЗАМКНУТАЯ КРИВАЯ, ОХВАТЫВАЮЩАЯ ОБЛАСТЬ ОКОЛО ТОЧЕК~$2$, $3$,~\dots,
$n$. в РЕЗУЛЬТАТЕ ЗАМЕНЫ~$C$ НА ПРОИЗВОЛЬНО БОЛЬШУЮ ОКРУЖНОСТЬ С 
ЦЕНТРОМ В НАЧАЛЕ КООРДИНАТ ПОЛУЧАЕМ СХОДЯЩИЙСЯ РЯД
$$
U_n=n(H_{n-1}-1)/(\ln 2)-{1\over 2}n +2+{2\over \ln 2}\sum_{m\ge 1}\Re(B(n+1, -1+ibm)),
$$
ГДЕ~$b=2\pi/(\ln 2)$ 
И~$B(n+1, -1+ibm)=\Gamma(n+1)\Gamma(-1+ibm)/\Gamma(n+ibm)=n!/\prod_{0\le k \le n}(k-1+ibm)$.

\rex[22] пОКАЖИТЕ, КАК НУЖНО ИЗМЕНИТЬ ПРОГРАММУ~Q, ЧТОБЫ В КАЧЕСТВЕ
РАЗДЕЛЯЮЩЕГО ЭЛЕМЕНТА ВЫБИРАЛАСЬ МЕДИАНА ИЗ ТРЕХ КЛЮЧЕЙ~(28).

\ex[м44] пРОАНАЛИЗИРУЙТЕ В СРЕДНЕМ ПОВЕДЕНИЕ ВЕЛИЧИН, ОТ КОТОРЫХ ЗАВИСИТ 
ВРЕМЯ РАБОТЫ ПРОГРАММЫ~Q, ЕСЛИ ПРОГРАММА ИЗМЕНЕНА ТАК, ЧТО ОНА ВЫБИРАЕТ 
МЕДИАНУ ИЗ ТРЕХ ЭЛЕМЕНТОВ, КАК В УПР.~55. [(сР.~УПР.~29.)]

\rex[вм24] нАЙДИТЕ АСИМПТОТИЧЕСКОЕ ЗНАЧЕНИЕ ЧИСЛА 
ПРАВОСТОРОННИХ МАКСИМУМОВ, ВСТРЕЧАЮЩИХСЯ ПРИ СОРТИРОВКЕ ВСТАВКАМИ В 
НЕСКОЛЬКО СПИСКОВ (ФОРМУЛА~(5.2.1-11)), ЕСЛИ~$M=N/\alpha$ ПРИ 
ФИКСИРОВАННОМ~$\alpha$ И~$N\to\infty$. 
вЫПОЛНИТЕ РАЗЛОЖЕНИЕ ДО ЧЛЕНОВ ПОРЯДКА~$O(N^{-1})$ И ВЫРАЗИТЕ ВАШ ОТВЕТ 
ЧЕРЕЗ ИНТЕГРАЛЬНУЮ ПОКАЗАТЕЛЬНУЮ ФУНКЦИЮ~$E_1(z)=\int_z^\infty e^{-t}\,dt/t$.

%% 169

\bye