\input style
\chapno=5\subchno=3\chapnotrue
\def\tape#1{{\hbox{\sl 녍��~#1\/}}\quad}
\subchap {������� ����������} %5.4
��� ����� �������� ����������� ��������, ������������ � ��� ������,
����� ����� ����������� ������� ��������� ����� ������������������
������������ ������������� ����������. ⍅���� ���������� � ����� �������
�� ���������� (���� � ����� ������� ���������� ����������� ������
������� ����� � ����������� �������), � ����������� ��� ���, ��� �����
������� � ������ �� ������� ��������� ��� ����������� ������� ����������.
񒐓����� ������ ������ ���� �����, ����� ������������ ���������
������������ ������������ ���������� (�����, �����, �������� � �.~�.)
����� ���������� � ������������� ��������� ����������. ����
����������� ��������� �� ��� ��� ������� ���������� ���������� (�������,
 �����, �����) ���������� ���������� ��� ������� ����������;
���������� ����������� ��� �������� ������.

��������, ��������, ��� ��������������� ��� ���������� ���� �������
�� 5000~������� $R_1$ $R_2$~\dots{} $R_{5000}$ ������ �� 20~���� (����
�����~$K_i$ �� ����������� ����� �����). ꀊ ����, ���� �� ����������
������ ������ ������ ���������� ������������ ������~1000 �� ���� �������?

񐀇� ������������� ����� �������: ������ � ���������� ������� �� ����
���������~$R_1$~\dots{} $R_{1000}$, $R_{1001}$~\dots{} $R_{2000}$,~\dots,
$R_{4001}$~\dots{} $R_{5000}$ �� ����������� � ����� ����� ����������
��������. � �������, ������� ��������� ������ ����� �������� �����������
������, ������ ��������� ��������, ������ ������� ����� ����������������
�������, ��� ����� ��� �������. ���� ��� ������� ������� ����� �������
������� ������������ ����������.

򎋜�� ��� ��������� �������---���������� ���������� � �����������
"������� ��������"---������ ���������, � ���� �������� ������� ����������
�������� � �������� � ��������� �� ��� ����.

⎇��������� ������������������ �������, ���������� �� ��������� ����
���������� ����������, � ���������� � ���������� ����� ����������
\emph{���������;} ��� ������������ �������� ������ ��������������, ��, �
���������, ��� ������������ ��� ����� ����������������� �������������
������� "�������" � ������ �������� �������������� �����, ��� �� ��������
\emph{������������} ������������������ ��������.  �������� �������-
%%296
����� ��� ���� ���� ������ ���������� �������� ��� �������������
��������� �����, ������� �� ������������ �������� ������������� ���������
��� ������ \emph{���������.} � ������������ � ���� ����� ������������
����� "�������" ��� ����������� ������������� ������ �����. 򀊈� �������,
������������� ������� "������� ��������" � "������� �������" ��
�������� �� � ����� ��������������.

���������� ������� ������� ������� ����������, ������������ � ��������
��������������� ������ \emph{��������� �����.} ⅐�����, ���������� �
�������� ��������������� �������� ������� � ����������� ���� ������
���������������� ����������� �������, � ������ �������� ����� ����,
���������������� ����� � ����������~5.2.4N, S �~L. � �������� �������
��� ����������� ������ "������� �����". � ���������� ������ ����
������������ �������, ���������� ��� ���������� ����������, ����������
���������� �� �����~1 �~2 �� ��� ���, ���� �� ����������� �������� ������.
瀒�� �����~1 �~2 ������������ � ������ � ������� �������, �����������
�� ���� ������, ������� ����� �������, ����� ������� ��������. ��� �����
������� ������������ �� ���� �� ������������ ����������� �� �����~3 �~4.
(呋� �� �����~1 �� ���� ������� ������, ��� �� �����~2, �� ��������������,
 ��� �����~2 �������� �������������� "���������" ������� �����~0.) 瀒��
��� ����� �������������� � ������ � ���������� ����~3 �~4 ��������� �
��������� �� ����� �������, ������������ ���������� �� �����~1 �~2.
���� ������������ (��� ���� ����� �������� ������ ��� �����������) ��
��� ���, ���� �� ��������� ���� ������� (� ������ ���� ������������� ����).
 呋� ����� ���������� ���������� ���� �������� $S$~��������,
������~$2^{k-1}<S\le 2^k$, �� ��������� �����������������
������������ ������� ���������� ����� $k=\ceil{\log_2 S}$~�������� �� ����
������.

퀏�����, � ������������� ���� ��������, ����� ��������� �����������
5000~�������, � ����� ���������� ������ ���������� 1000~�������, ��
�����~$S=5$. 퀗������ ����������������� ���� �������� ����������
�������� ���� �������� �� ����� ��������� �������:
$$
\eqalign{
\tape1 & R_1\ldots R_{1000}; R_{2001}\ldots R_{3000}; R_{4001}\ldots
R_{5000}. \cr
\tape2 & R_{1001}\ldots R_{2000};  R_{3001}\ldots R_{4000}.\cr
\tape3 & \hbox{(������)}\cr
\tape4 & \hbox{(������)}\cr
}
\eqno(1)
$$

�� ������� ������� ������� �� ������~3 �~4 ��������� ����� �������
�������, ��� �� ������~1 �~2:
%%297
$$
\eqalign{
\tape3 & R_1 \ldots R_{2000}; R_{4001}\ldots R_{5000}.\cr
\tape4 & R_{2001} \ldots R_{4000}.\cr
}
\eqno(2)
$$

� ����� �����~2 ������ ����������� ��������� �������, ��� ���
�������~$R_{4001}\ldots{}R_{5000}$ ������ ���������� �� �����~3. ��
��������� ���� ���� � ������ ��������� ������ �� ������ �������� � ������
����������:
$$
\eqalign{
\tape1& R_1 \ldots R_{4000}.\cr
\tape2& R_{4001}\ldots R_{5000}.\cr
}
\eqno(3)
$$
(����~$R_{4001}\ldots{}R_{5000}$ ����� ����������, �� ���� �� �� ������
� 8000~�������, �� � ���� ������ �����~2 ���������
��~$R_{4001}\ldots{}R_{8000}$.) 퀊����, ����� ��� ����� ��������� ��
�����~3 �������� �������~$R_1\ldots{}R_{5000}$, � ���������� ����������.

񁀋������������ ������� ����� ���������� �� ������~$T$ ���� ���
������~$T\ge3$. ⛁���� ������������ �����~$P$, �����, ���~$1\le P < T$, �
�������� $T$~���� �� ��� "�����": $P$~���� � ����� ����� � $T-P$~���� �
������ �����. ����������� �������� ������� ��� ����� ����������� ��
$P$~������ ������ "�����", ����� �������� $P\hbox{-�������}$ ������� �����
�������, ����� �����---$(T-P)\hbox{-�������}$~������� ������ ������ �~�.~�.,
 ���� ���������� �� ����������. ��� ��������~$P$ ����� ����� ��������
������~$\ceil{T/2}$ (��.~���.~3, 4).

~$T=4$, $P=2$ ����� ������� ������---���������������� ����������� �������.
 ⍎�� ���������� ���������� ������, ��������� ������� ���������� ����;
�������~$T=6$ �~$P=3$. 퀗������ ������������� ������ ����� �����:
$$
\eqalign{
\tape1 & R_1\ldots R_{1000}; R_{3001}\ldots R_{4000}.\cr
\tape2 & R_{1001} \ldots R_{2000}; R_{4001}\ldots R_{5000}.\cr
\tape3 & R_{2001} \ldots R_{3000}.\cr
}
\eqno(4)
$$
��� ������ ������� �������� �
$$
\eqalign{
\tape4 & R_1 \ldots R_{3000}.\cr
\tape5 & R_{3001}\ldots R_{5000}.\cr
\tape6 & \hbox{(������)}\cr
}
\eqno(5)
$$
(�����������, ��� �� �����~3 ������� ��������� �������.) � ������
������� ������� ������ ����������� �
�������~$R_1\ldots R_{5000}$ ���������� �� �����~1. ���� �������
������~$T=6$ ������������~$T=5$, ��� ��� ������ ����� ������������ ����
���~$S\ge7$.
%%298

򐅕������� ������� ����������� ���������� ��������� ������ �������
������������ ����������, ��� �����������, �� ��� ������ ������������ ����
�� ��������� � ��������, ����������� ��� ������, ������ � ���������
�����; �� �������� ������ ������ ����� ���������� ����������, ���� ������
�� �������� ������ ��������� �������� ����������� ����. � ����������
������� ((4) �~(5)) ��������� ������ ��� ������� �� ������ � ��������� �
����� ��������� ���~$T=4$. 򀊈� �������, ������� ���~$T=6$ ������ �����
���� ������ ������� �� ��������� � ����������� ������.

񁀋������������ ������� ������� ����� ������� � ������������. � ����
������������ ������������, �� ����� �����, ��� ��� �� ��������� ������ �
����������� ���� ������� �������. ⌅��� ���� ����� ���������� ��~(1)
�~(2) � ������������ ��� �����, ��� ��������� ���������� ������ �������,
 ����� �����~3 �~4 ��������� ��������������~$R_1$~\dots $R_{2000}$ �
 $R_{2001}$~\dots $R_{4000}$, � �����~1 ���� ������ �
����������~$R_{4001}$~\dots $R_{5000}$. 瀒�� �����~2, 3, 4 ����� ����
���������� � ������, � ���������� ����������� �� ����������� �������� ��
�����~2. �� ����� �������, ����������� � ����� � ���� ���� ���������,
 ��������� ��~$4000+5000=9000$ ������~$5000+5000+5000=15000$ �
���������������� �����. 񎎁����������� ������ ����� �� ������� � ���!

茅� ���� �������� � ������ �����, ����� ��������� ��� �����, �����������
������� ��������� �������:
$$
\eqalign{
\tape1 & R_1 \ldots R_{1000}; R_{3001} \ldots  R_{4000}.\cr
\tape2 & R_{1001} \ldots R_{2000};  R_{4001} \ldots R_{5000}.\cr
\tape3 & R_{2001} \ldots R_{3000}.\cr
\tape4 & \hbox{(������)}.\cr
}
$$

򅏅��, �������� ����������� ������� �� �����~4, ����� ��������� ����~3
�~4 � ����������� ����������� �������� �� �����~3, ����� ���� �� ���������
����������, �������� ����� $3000+5000=8000$~�������.

퀊����, ���� �� �� ����� ����� ����, �� ����� ��, �������, ��������
�������� ������� �� �����~1--5 � ��������� ���������� �� ���� ������,
�������� ����������� ������� �� �����~6. ������������ ���� �������
����������, ��� ������� ���������������� ������� �� �������� ���������, �
���� �� ��������� �������� ���������� ����� �������.

� ����������� ������� ���� ����� ������� ���������� ����������� �����
�������. � �.~5.4.1 ��������������� ���� ���������� ����������,
����������� ��������� �������; ������ ������� ������������ ������� "������
� ����������", ������� ���������� �������, �������������� � �����������
������,
%%299
����� �������� ������� �������, ����������� ������������� �������
���������� ������. � �.~5.4.1 ����������� �����, ��������� ������, �������
��� ����� ������������� �������.

 ������ ����� ������� ����������� � �.~5.4.2---5.4.5. � �� �� ������� �
������������ � ������ ����������������� ��������� ���� � ��������
����������� ������, ��� ��� �����, ������ �������������� ���� ����, �����
������ ������� ������������� � ��������� ����������. 퀏�����, ����� �
������ ����� �������� (��� �� ������ �� ��� ���), ��� ��������������
�������� ������ ���������� ��������� ������� � ������� ������
����������������� ����; �� ����� ���� ��� ��������, ����� �������� ����
�� ����� ���� �, ���� �����, ���� ������� �������� ��������� �����, ���
��� ����� �� ����������! 듗�� ����� ���������� ��������� ������������
�������� �� ��� ���, ���� �� ����� ���������� "�������������"
��������� ������������ ���� �������. 瀒�� � �.~5.4.6 �� "��������
�� �����", ���������� ������������ �����������, ������� ������  ������ ��
����� ����� �������. � �.~5.4.6 ������������ �������� ����� ������� ��
�.~5.4.2---5.4.5 � �������������� ��������� ������������� �������������,
������� ����������� �� ��������.

荛� ������� � �������� ������� ����������, �� ���������� �� �������,
����������� � �.~5.4.7 �~5.4.8. 퀘 ����� ������� ���������� �������������
� �.~5.4.9, ��� ��������������� ������ �������� ���������� �� �����
������, ��� ����� � ��������.

\excercises
\ex[15] � ������ ������� ���������� ��������������� �����
����������. ��� ������ ������ ��������� � ����� ���������� ����������,
������ ������ ������ �� ��� ����� � ����� ������� ������� ����� � ������
������?

\ex[10] ꀊ�� ����� ���������� ���� (�����������~(1)--(3)), ����
������~$R_1$~\dots{} $R_{5000}$ ����������� � ������� 3-����������
����������������� ������. ���~$P=2$? 񐀂���� ���� ������ �� �������� ��
4~������; ������� �������� �� ���� ������ ����� ������� �����
��������������� ������������� ��������?

\ex[20] �����, ��� ���������������� $(P, T-P)\hbox{-�������}$ �������,
����������� � $S$~��������� ��������, ���������� $2k$~��������,
����~$P^k(T-P)^{k-1}<S\le  P^k(T-P)^k$,   �  ����������  $2k+l$~ ��������,
����~$P^k(T-P)^k< S\le P^{k+1}(T-P)^k$.

䀉�� ������� ������� ��� ���������� (a)~������� ����� ��������
��� ������� ��~$S$ ���~$T=2P$, (b)~������������� ����� ��������
���~$S\to\infty$ ��� �����~$P$ �~$T$.

\ex[BM15]  ����� ��������~$P$, $1\le P < T$, ��������~$P(T-P)$ �����������?

%%300
\subsubchap{썎��������� ������� � ����� � ����������} % 5.4.1

�~�.~5.2.4 �� ������� ������ ���������� ����������, ���������� ��
����������� �������---�������� ����������� ����
������������� ������������������� � ����. 텒����� ��������� ��� ��
������� $P\hbox{-��������}$ �������, ����� $P$~�������
�������� ������������ � ���� ��������.

�� ������� $P$~������������ ��������, �.~�.~�������������������
�������, ����� ������� ����������� � ����������� �������. ������
�������� �� ������� ����� ���������:
���������� �� ������ ������ ������� ������� � ������� �� ��� ��, �������
������������� ����������� ����; ��� ������ ���������� �� ����� �
����������� �� ������� ������, ����� ������� �����������.

�~$P$ �� ������� ������, ���� ����� ������ ������������,
������ �������� $P-1$~��������� ��� ���������� ����������� �� �������
������. � ����, ������, $P\ge8$, �� ����� ��������� ������, ���������
\emph{������ ������,} ��� ������� � �.~5.2.3;
����� ������ ��� ��������� ������ $\approx \log_2 P$~���������
(����� ���������� ������������ ������). ����������, ��������,
�������������� ������� � ������������� ������� ������:
{\def\tree#1#2#3#4#5#6{
\left\{ \matrix{
#1\left\{\matrix{#3\ \infty\hfill\cr #4\ \infty\hfill\cr}\right.\hfill\cr
#2\left\{\matrix{#5\ \infty\hfill\cr #6\ \infty\hfill\cr}\right.\hfill\cr
}\right.
}
$$
\matrix{
{\sl ���~1.}&                             \hfill 087 &\tree{087}{154}{087\ 503} {170\ 908}{154\ 426\ 653}{612}\hfill\cr
{\sl ���~2.}&                        \hfill 087\ 154 &\tree{170}{154}{503}{170\ 908}{154\ 426\ 653}{612}\hfill\cr
{\sl ���~3.}&                   \hfill 087\ 154\ 170 &\tree{170}{426}{503}{170\ 908}{426\ 653}{612}\hfill\cr
\vdots\hfill    \cr
{\sl ���~9.}& 087\ 154\ 170\ 426\ 503\ 612\ 653\ 908 &\tree{\infty}{\infty}{}{}{}{}\hfill\cr
}
$$}%
%%301
� ���� ������� � ����� ������� ������� ������� ���������� ����~$\infty$,
����� ������� ������������� �����������. � ��� ������� ������� ������
����� ���� � ����� �������� ���������, �� ��� ���������� ������ � ������~$\infty$
�� �������� ����������� ����� ������ ��� ����� ������ ��� �������;
����� ����; ����� "��������" ������ ����� ������ ������� ��������
���������� ������� �����.

� ��������������� �������� ������ ���, ����� �������, ������� �� ���������
����������� �������� ��������� ��������� �� ����� �� ������� � ���������
���������������� ���� � ������ ������. �, �� ����~2 ���������� 3~����,
������� ���������~$087$ �� ����~1; �� ����~3 ���������� 3~����,
�����������~$154$ �� ����~2, � �.~�. ���� ��������� � ������ ������
������ ����� ������ ���������� \emph{������� � ����������.}

� ����� ��-������� ������������� ����������� �������������� �������. �
����� ����� ������ ��� ������������ ���� ����������� ��������, �����������
���������, ��� �����������; ������ ���� ������ ������ ���������� ���� ��
�������������������, ������������ � ��������� �������. 䅐��� ������, ��
��������, ������������ ��� ������������ ������� � ����������� "����������
�� ���������� ������ �����������".
\picture{���.~62. 򓐍��, ��� ������� ���������� ���������� ����;
������������ ������ �������� ������, ���� �������� ������������ ��������
��~1 ��~23.}

� �� ��� � �.~5.2.3, �� ����� �� ��� ���������� ������������ �������
������������ �� ������ ������, � ��������. (�����, �������, ���� ����
�� ������������ ����� �������, ����� �� ������� ���������
\emph{����������} �������, � �� ����������,
%%302
������� ��� ����� ������� �����������~(5.2.3-3).) � ��� ��������
����� ���������� ������, ����� �������� ������������� �����~$\infty$;
������� �������������, ����� �������� ���������� ������. � ������ �������,
���������� ������� ���������� ������ ����� ���� �� ������������ ��������
�������� � �������, ��� ��� � �������� ����� �������� ������ �����
������ ��������� �� ���; �� ������ ����, ��� ������� ������ �����
��������� ������ ������������ � ������� ����������, ��� ���, ��������, �
������ �������� ����� �������.

\section 䅐��� "�����������". � ���.~62 ���������� ������
�������� ������ � 12~�������� (�����������) ������ �
11~����������� (��������); �� ������� ����� �������� �����, ��
����������--- "����������", ���� ������ ������������� ��� ������ ��� ������
\picture{���.~63.               � �� ������, ��� � �� ���.~62, ��
�������� �����������, � �� ����������; ������� ��������� �� ����� �����.}
����������� �����. ����� �������� ������� ��� ������ ����� ����������
������������ ������ ������������� ���������������� ������� ������ ���
������� ��������� ������.

����� ���������� ����� ��������� ������ ������, ������������� �� ���.~62,
 ����� ���������� ����~$061$ ����� ������� ������ ������, �����
����������� ������ �����~$512$, $087$ �~$154$ � ������� ������. 呋�
���������������� ������ ��� ������, ��������� ��� ����� ������������
����� ����������� � ������ � �������~$061$. ��� ������� �� �����, ��� �� �
���������������� ������ �������� �� ���������� ���� \emph{������������}
%%303
� ������ �����, � �� ����������, ����� ����������, ����������� ���
��������� ������, ����� ��������������.

� ���.~63 ���������� �� �� ������, ��� � �� ���.~62, �� ������
����������� � ��� ������������ �����������. 䎏����������� ���� �
�������~"0" �������� �� ������� ������ ��� �������� �������� �������.
瀌����, ��� ������ ����, ����� ��������, �������� ����������� ����� ����
��� (��.~�.~5.3.3);
����� �������, ������ ���� ���������� ���� ��� �� ������� ���� � ���� ���
�� ����������.

� �������� ������� ����� � ������ ����� ���.~63 ����� ���������������
������ ������� ������, ������������� � ������ ���, � ����������
�����---��������� �� ��� ������. 瀌����, ��� $P\hbox{-�������}$ �������
������� ����� $P$~������� � $P$~���������� ����� �� ������ � ��������
�������, ��� ������� �� ����� � ���� ����������� ������� �������������
������. 텒����� ������, ����� ������� ����� ������������ ������
����������� ��� ������ � ����������. ᎋ�� �������� �� �������
���� �������� � ��������� ������ ���� �����.

\section ������ ��������� �������� ����������� ������ � ����������.
򅕍��� ������ � ���������� ����� �������������� ����� �� ������ ����
������� ����������, ���� ���������� ��������� $P\hbox{-�������}$ �������
������� ������ � ������ �����. � ���� ������ $P$~���������� ����������
�������, ����� ���������, �� ��������, ��� ���������� ������. ꀆ���
������ ��� ������ ���������� ��������� ������� �� �������� ������. 呋� �
���� ����� ������ ���� ������, ��� � ���������� ������, �� �� �� ��������
�� � ������� �������; � ��������� ������ �� ������� ������� �������� �� �
������ ������, ��� ��� ��� �������� ����� �������, ������������ � ������
������. 򀊈� �������, ������ ������� ����� ��������� ������ $P$~�������,
���� � ����� ������ � ������ ������ ��������� �� �����
$P$~�������. 򀁋���~1 ������������ ���� ������� ���~$P=4$ (�����,
����������� � ������, ������� ��������� � ��������� �������).

���� ������ ����� ������������ ��������� �������� ��� ������� ������
【������ �.~񜞂����� [Master's Thesis, Digital Computer Laboratory
Report R-232 (Mass.~Inst.~of~Technology, 1954), 29--30], ������� ������
����������� � ������ ����, ��� ��� ���������� � ��������� ������ �������,
������, ����� ��������� ����� $1.5P$~�������. � �� ���� ���������
�������� � 1950~�.\ �.~�.~䓌� � ����� �� ����������� �����������
��� ����������, ��������������� Engineering Research Associates, �� ��
����������� ��. 񀌎 �������� "����� � ����������" (replacement
selecting) ���� ��������� �.~X.~�������
[{\sl JACM,\/} {\bf 3} (1956), 154], ������� �������, ��� "��������� �����
����������� ������������������ �� ��������� ������ ������������, ��
%%304
\htable{򀁋���~1}%
{��� ��������������� ������ � ����������}%
{
\strut\hfill$#$\bskip\hfill&\hfill\bskip$#$\bskip\hfill&\hfill\bskip$#$\bskip\hfill&\hfill\bskip$#$\bskip\hfill&\bskip$#$\bskip\hfill\cr
\multispan{4}\hfill 񎄅������ ������ \hfill &  \hbox{⛂��}\cr
\noalign{\hrule}
 503 & 087 & 512 & 061 & 061\cr
 603 & 087 & 512 & 908 & 087\cr
 503 & 170 & 512 & 908 & 170\cr
 503 & 897 & 512 & 908 & 503\cr
(275)& 897 & 512 & 908 & 512\cr
(275)& 897 & 653 & 908 & 653\cr
(275)& 897 &(426)& 908 & 897\cr
(275)&(154)&(426)& 908 & 908\cr
(275)&(154)&(426)&(509)& (\hbox{����� �������})\cr
 275 & 154 & 426 & 509 & 154\cr
 275 & 612 & 426 & 509 & 275\cr
\multispan{5}\hfill\hbox{� �.�.}\hfill\cr
\noalign{\hrule}
}
������������ ��������� ������������, ��� �������� ������� �����~$2P$".

�.~�.~쓐 ��������� ������� ������ �������������� ����, ��� ���������
����� ������� �����~$2P$, ������� �������� ��
\picture{���.~64. ⅗��� ��������������� � ����� ������������ �����.}
����������������, ���������� �� ����� [U.~S.~Patent~2983904 (1961),
cols.~3--4]. ���������� ��������, ������������ �� ���.~64: �� ���������
������ ���������� ������ ��������, � ���� ��������������� ����������
������� ����. 񍅃 �������� �� �������,
%%304
��� ������ �� ������������ �� ������� ������. 򎗊� ������
������������ ������������� �������~$x$, $0\le x < 1$; ��������, ��������
� �����~$x$, ������������� ������� ������ � ������~$x$, � ���������������
������������ ����� ����� �������� ������ � ����������.

񊎐���� ��������������� ������� ��������������� ���� �����, �������
����������� �� ��� ����, � �������� ������ ������������, ��� ��� �����
���������� �������� �� ������ � �������� �����~$P$. ꀆ��� ���, �����
��������������� �������� �����~0, �� ������ ����������� ����� �������.
\picture{���.~65. ������� �������, ������������ ���������� ��� �����
����� ����������������, ����� ������� ��������� � �������������� ������.}

荒������� ����, ��� �������, ��������� ��������� �����, ������ ��
�������������� �����, ��� ������� ��������������� ����� ��������� �
���������� ��������� (� ���� �������� ��������� ������). ��� ��������,
��� � �����, ��� ��������� ���������������, ���� ����� ���������� ���, �
������� ��������������� ���� ��� ������� �����������, ��� �������� ��
���.~65. ��� �������, ��� ���������� �����, ���������� �� ����
������ (� ������ ����� �������), ����� ����������� ���������� �����~$P$,
 ��������������� � ����� ������.

� ������ ������������ ����������� ������� ������ \emph{������} �������
��������� ����������---� ��� ��� ���������� ������������ �������;
�������������, �������, ����������� ������� � ����������, ����� ���������
��������� ���� ������, ��� $2P$~�������. � ���������� �� ������, ��� �����,
 ������ ��� ������� ���������� ��������, � ������������ ������� ������� ��
���������� ��������, ����������� ��������� ����������������� �����, ���
��� ����� � ���������� ���������� �������� ���������������; ������ �������
���������� ���������� ��������� �� �������� ����� ������ ���������
��������, ��������� ������� ������ ����������.

򅏅�� �������� ���������� ������� �������� ��������� �������� ������� �
����������. 񋅄����� �������� ����������� 䆎��~�.~󎋒����, 䆅����
����� �~쀐���� 瀋��, ������� ������������ ��� � ���������
���������� ����������� �������, ��� ��� Philco~2000 �~1958~�. � ��������
� ����
%%306
���������� ������ ���������� ������������ ������ ������ � ����������
�������, ������������� ������ ��������, � ����� ������ ���������� �������
�� �������������, ������������ ������� ������. (퀄������� ���������
���������� �������, ������������ ������� � ����������, �����������
�������� �������;
����, �������������� ��� ���������, ����� ������ ������ ������������ ���
������������.) ����� ���� ����������� � ���, ����� ������������� ������
���� ��� ����~$(S, K)$, ��� $K$---�������������� ����, � $S$---����� �������,
�������� ����������� ������ ������. � ������� ��������
������������������, ����������� ������� � ����������, ����
����������������� ���������� ��� ����������� ����� ($S$ ��������� ������~$K$).

������� ���� �������� ���������� ��� ������������� ������ ������
��������� ������, ��������� �� $P$~�����; ��������������, ���
$j\hbox{-�}$~����~$X[j]$ �������� $c$~����,
������������ �~$|LOC|(X[j]])=L_0+cj$ ���~$0\le j < P$, �� ������������ ���
���������� ���� � �������~$j$, ��� � ������� ���� �
�������~$P+j$ (���.~63). � ������ ���� ������� ��������� �����:

% !!!  ����� ����� ��� ������ ��������
{\medskip\narrower
\item{|KEY|} = ����, ����������� � ������ ������� ����;

\item{|RECORD|} = ������, ����������� � ������ ������� ����
(������� |KEY| ��� �������);

\item{|LOSER|} = ��������� �� "������������" � ������ ���������� ����;

\item{|RN|} = ����� �������, ���� �������� ������, �� ������� ���������~|LOSER|;

\item{|FE|} = ��������� �� ���������� ����, ������������� � ������ ������ ����
������� �������� ����;

\item{|FI|} = ��������� �� ���������� ����, ������������� � ������ ������ ����
������� ����������� ����.
\medskip}

퀏�����, ���~$P=12$ ���������� ���� � �������~5 � ������� ���� �
�������~17 �� ���.~63 ��� ����� ������������ �����~$X[5]$ �
������~$|KEY|=170$, $|LOSER|=L_0+9c$ (����� �������� ���� � �������~21),
$|FE|=L_0+8c$, $|FI|=L_0+2c$.

獀����� � �����~|FE| �~|FI| �������� �����������; ����� �������, ������
������, ��� ������������� ������� �� � ����� ����. ��� ������ ��
��������� ���� ������� ���������� ��� ������� ������ � ������������
�����/������ �������� ������� ��� ���������� ����������, ��� ���������
�� ������ ��� ������.

\alg R.(⛁�� � ����������.) ���� �������� ������ ������ ���������������
�� �������� ����� � ���������� �� ��������������� � �������� ����,
��������� |RMAX|~�������� �����~$P$ ��� ������ (�� ����������� ����������
�������). 茅���� $P\ge 2$~����� $X[0],~\ldots, X[P-1]$ � ������, ����������
����.

%%307
\picture{���.~66. ������ ��������� �������� ����������� ������ � ����������.}
\st[퀗������ ���������.] 󑒀������~$|RMAX|\asg0$, $|RC|\asg0$,
 $|LASTKEY|\asg\infty$, $|Q|\asg|LOC|(X[0])$ �~$|RQ|\asg0$. (|RC|---�����
�������� �������, a |LASTKEY|---���� ��������� ���������� ������.
퀗������ ��������~|LASTKEY| ������ ���� ������ ������ ���������� �����;
��.~�~���.~8.) 䋟~$0\le j < P$ ��������� ����������~$X[j]$ ����������
��������� ������� (���~$|J|=|LOC|(X[j]))$:
$$
\displaylines{
|LOSER|(|J|)\asg J; |RN|(|J|)\asg0; \cr
|FE|(|J|)\asg|LOC|(X[\floor{(P+j)/2}]);   |FI|(|J|)\asg|LOC|(X[ \floor{j/2}]).\cr
}
$$
(󑒀�����~$|LOSER|(|J|)$ �~$|RN|(|J|)$ ���� �������������
������ ���������� ��������� ������, ������������ ��������� ������� �
�������~0, ������� ������� �� ���������. ���--- ����� ����; ��.~���.~10.)

\st[ꎍ�� �������?] 呋�~$|RQ|=|RC|$, �� ������� � ����~\stp{3}. (�
��������� ������~$|RQ|=|RC|+1$, � �� ������ ��� ��������� ������� �
�������~$|RC|$; � ���� ����� ������� ��������� �� ����������� ��������,
������� ����� � ������������ �� ������ ������� ��� ����������� ������
����������.) 呋�~$|RQ|>|RMAX|$, �� �������� ��������; � ��������� ������
����������~$|RC|\asg|RQ|$.

\st[⛂�� ������� ������.] (񅉗�� |Q|~��������� �� "��������",
 �~|RQ|---����� ��� �������.) 呋�~$|RQ|\ne 0$, �� �������~$|RECORD|(|Q|)$ �
����������~$|LASTKEY|\asg|KEY|(|Q|)$.

\st[₎� ����� ������.] 呋� ������� ���� ��������,
����������~$|RQ|\asg|RMAX|+1$ � ������� � ����~\stp{5}. � ��������� ������
��������� ����� ������ �� �������� �����
�~$|RECORD|(|Q|)$. 呋�~$|KEY|(|Q|)<|LASTKEY|$ (�.~�.~��� ������ ��
����������� �������� �������), ��~$|RQ|\asg|RQ|+1$, � ������,
����~$|RQ|>|RMAX|$, ����������~$|RMAX|\asg|RQ|$.

%%308

\st[������� � ���������.] (񅉗��~|Q| ��������� �� ����� ������ �
������� �������~|RQ|.) 󑒀������~$|T|\asg|FE|(|Q|)$. (|T|---����������
���������, ������� ����� ��������� �� ������.)

\st[󑒀����� ������ ������������.] 呋�~$|RN|(|T|)<|RQ|$
��� ����~$|RN|(|T|)=|RQ|$ �~$|KEY|(|LOSER|(|T|))<|KEY|(|Q|)$. ��
�������� ������� $|LOSER|(|T|)\xchg |Q|$, $|RN|(|T|)\xchg |RQ|$. (�
����������~|Q| �~|RQ| ������������ ������� ���������� � ����� ��� �������.)

\st[񄂈� �����.] 呋�~$|T|=|LOC|(X[1])$, �� ��������� � ����~\stp{2}, �
��������� ������~$|T|\asg|FI|(|T|)$ � ��������� �~\stp{6}.
\algend

� ���������~R ��������� � ����� � ������ ������� �� �����, ����� ���
����������� ����������� ����� ������ � ���������� ������������ �������
����� �������. 񋅄���������, �� ����� ���� �� �������� �������� ������
����� � ������; �� ����������� � ������ �������� � ����������
��������~$P$. ��� ����� �������� � �.~5.4.6.

�.~X.~����� [{\sl JACM,\/} {bf 3} (1956), 154] ���������
��������� ��������� ������ ������ � ����������. � ��� �������,
����� �������� ���� ������, ���~|LASTKEY| (��� ��� �� �� ������� � �������
�������), �� ������ ��� ����� ���������� �����, �������������
����������� �� ����� (��� ��� ��� ���������� ����� ���� �� ��������� �
������� �������), ��������� ���� ���� ������ ������ ������. ꐎ�� ����,
��������� ��� ����� ��������� "������ ��������" � "������ �� �������",
�.~�.~������� ���������� �� ���������� ������ �� ����������� �
���������������� ������, � "��������" � �������� ��, ������� ��
������ ����. ��� ��������� ��������� ������ ��� ������� � ������� ���
������ ������.

\section *����������� �������� � ���������. �.~�.~䈍����
[{\sl CACM,\/} {\bf 8} (1965), 48] ��������� ���������� ������������������
������ � ����������, ������������ �������, ������� �����
�������� \dfn{�������� �������.} ꀊ �� ������, ������ ���� �������,
����������� �� ����� � ������� �������, �������� ������ � �����������
�������, ��� ��� ������ ������� ����������, � ��������� ����������. �
������� �������� ������ � ���������� ���������� ������� ������� ����� �
��������� ������� ������ �� ������, ��� ���������� ������� � ����������
����� ����� �������; ��� ������������� "1~������� �������". 䈍����
��������� �������� ��� ������� �� "$m$~�������� �������"; ����� �������
�� �������, ����� ���������� ������� ������� ����� ��� �� ������, ���
���������� ������� ����������� �����, �� �� \emph{�� ������ ���� ������,
��� ���������� �������� �����-�� $m$~���������� ������ ���� �� �������.}
瀏��� � ��������� ����� �����������, ��� � �����, �� �������� ����� ��
������� ���� ������� ��������������.

%%309

��������, ��������, ��� ����� �������� ������ �� ��� ������; ���������
������������������ ������ �������� �������� � ����� ��������� �������:
$$
\vert 08\ 50 \vert 06\ 90 \vert 17\ 27 \vert 42\ 67 \vert 51\ 89 \vert
\eqno (1)
$$

񋅄����� ����, ������� ����� ���� ������ ����� �������, ������ ����������
� ��������, �� ��������, ��� ������ �� ������� �������
���������~$\set{50, 90, 27, 67, 89}$, ������ �� �����������, �.~�.\ ��
������~67. ���������������~(1) �� �������� �������� � ����� ���������
�������, ��� ��� 17~������, ���~50 �~90.

���� � $m$~��������� ������� � �������� ������ � ��������� ����
���������� ����� ���� ������������ ����� �������, ��� ��� ����
������������ ����� �� ����� �������� � ������� ������. 퀗��� � ������
������ $m$~������ � $m$~������� � ����� ����������� $m\hbox{-�������}$
������� ��; ����� ���� �� ������� �����������, �������� � ����
$(m+1)\hbox{-�}$~���� �~�.~�. 򀊈� �������, �� ����� ������������
������� � ���� ����� ������������� ������������������, ��� ��� ������
����� ������� ����� ������������ ����� ������ ���� ������ ��� �����
���������� ����� ������ ��� ������������ ����� (���� ��� �� ���� ������,
��� ���������� �������� �����-���� $m$~������, �������������� ���). ����
����� �������������� �������, � ��������, �������� $m\hbox{-�������}$
��������, ������������ ������ ���� ��������� ���������� ��� ���� �������
������!

������ �������������� ��������� ��� �����������, � ������� ����������
������ ���, ����� ����� �������� ���� ��������� ������ �������. � �����
��������������� ��������� ������� � ��������� ��������� ��������� � �
���������� ��������� ������� � ������� ������������ �������---��� � ���� �
�� �� �����. ���, �� ��������, ������� ����, ��� ���� �� �� ��������������
�������, ������������� � ������ ����� ������, ����������� ���� ���
��������� ����������� �������, ������������ ������������.

��� ���������� ���� �� ��� ��� �� ���������������� �� �����. 茅����
��������� ��������������� ����������, ������������, ���, �����
$P$~������ �� ��������� � �������� �����, ����� ������� ���~$m=2$
�������������� �����~$2.1P$, ��� �����~$2.3P$ ���~$m=4$ �~$2.5P$ ���~$m=8$.
򀊎� ����������, ���� �����, ������������, ����� ��������� ����������
���������. � ������ �������, ����� ����� ��������� ��������, ���� ��.
���������� ������� ����� ���������� ���� ����� ��� �������� �������� �����
�������.

%%310

\section *퀒�������� �����. 䐓��� ���� ���������� ����� ��������,
 ����������� ������� � ����������, ��� ���������� �.~�.~���������
�~�.~�.~󎍎�. � ���� ������� � ���, ����� ��������� ���������~R, ��,
����� �� ����~R4 $|KEY|(|Q|)<|LASTKEY|$, ����� ������~$|RECORD|(|Q|)$ ��
�������� � ������,, � ��������� � ��������� ������� \emph{���������} �
�������� ����� ������. ���� ������� ������������ �� ��� ���, ���� �
���������� �� �������� ������������ ���������� �������~$P'$; �����
������� �������� ������� ��������� �� ������, � �������� ����������
������������ � �������� �������� ������ ��� ���������� �������.

���� ����� ������ ��������� ����� ������� �������, ��� ����� � ����������,
��������� �� "�������" ����� ����������� "�������" ������, ������ ����
����� ��������� �� ��������� ������; �� ��� ��������� �������������� �����
�� ����� � �����������. ꎃ��~$P'>P$, ��������� ������ �����
����������� � ���������� ������, �� ���~$P'\le P$ ������ ��������� �� �����.

������� �~�, ������� �������� ������������ ��������� ������ ������,
��������, ���, �����~$P$ ���������� ������ (������, $P\ge 32$) �~$P'=P$,
������� ����� ������� ��� ��������� ������ ����������� ������~$eP$,
���~$e\approx 2.718$---��������� ����������� ����������. ��� �������, �
����� ��� ����, ��� ����� ��� ������� ��� ������������ �������� ��������
������ � ����������, ��������� ��� ��� ����������������
���������� ������� ���� ����� \dfn{����������� �������.}

쎆�� �������� "�����������" ����� ��� ����� �������, �����
���������������� ��������� �� ���������������� �� ���.~64 � ��������
������������ �������������� ������. ��~$L$ ���������� ����� ����,
a~$x(t)$---��������� ��������������� � ������~$t$ ���~$0 \le t \le T$.
��������, ��� � ������~$T$ ��������� �����������; � ���� ������ �������
����� �������� ������������, ���� ��������������� ������������ � ��������
��������� (������ $P$~��������, ���������� �� ��� ����). 񈒓���� �����
��, ��� � �����, ������ "������� ����������" ������---������ $P$~�������� ��
���� ������ � ����� ������ ������� �� ����� $P$~�������� �����
���������������� � ��������� (�� ����������������), ������������� ��
������ � $P$~��������. � ������� ��������� �������~$dt$ ���������������
������������ ��~$dx$, ���� ��������� $h(x, t)dx$~�������, ���~$h(x,
t)$---������� ���� ����� � ������ �������~$t$ � �����~$x=x(t)$, ���������� �
��������������� ��������; �������������, $h(x, t)=h(x, 0)+Kt$ ��� ����~$x$.
 � ��� ����� ������� � ������ �������� ����������, �� $h(x, t)dx$~����
����� ����� �������, �������� \emph{�����} ����������������, �
������~$Kdt(L-x)$, ���~$K$---�������� ������� ����� (���.~67). 򀊈� �������,
$$
{dx\over dt}={K(L-x)\over h(x,t)}.
\eqno(2)
$$
%%311

� �������, �����������, ���~$h(x,t)$---���������, � ��� �����~$KT$ ���
����~$x=x(t)$ �~$0\le t \le T$, ��� ��� ���� ������ ���������� �
�����~$x(t)$ � ������� $T-t$~������ ������� ����� ����, ���
��������������� �������� ��� �����, ���� $t$~������ ������� ����� ���, ���
�� ��������. 荛�� �������, ��������������� ����� ����� ����� ��� �����
���������� ���� ����� �� ���������� ����� ����, ���� ���������, ���
��������� �������������� �����, ����� ���� ���� ��� ����� ���� � ��� ��.
񋅄���������, ����� ���������� ���������� ����� (����� �������)
����~$KTL$,
\picture{���.~67. ₎����� � ��������� ������ ���������� �����; ��
�����~$dt$ ��������������� ������������ ��~$dx$.}
� ���������� ����� � ������ ���� ���������� �����, ���������� �����
�������~$T$, � ������~$KT(L-x(T))$.

�������� ���������~(2) ��� �������, ���~$x(0)=0$, �����
$$
x(t)=L(1-e^{-t/T}).
\eqno(3)
$$
񋅄���������, $P=KTLe^{-1}=\hbox{(����� �������)}/e$---��� ��� ��� ��, ���
�� � ������ ��������.

� ���.~21--23 ��������, ��� ���� ������ ����� �������������� �� ������
�������������~$P'$; ��������, �����~$P'=2P$, ������� ����� �������
����������� ������~$e^\theta(e-\theta)P$,
���~$\theta={1\over2}(e-\sqrt{e^2-4})$,---���������, ������� ���� �� ����� ����
������������ �������! � ����.~2 ���������� ����������� ����� ������
������� � �������� ����������; � ������� ���� ������� ����� �������
���������� ������������ ������ ��� ���������� ������ � ��� ��� ���� ��������.

\section *������ ������ � ����������. ⅐����� ������ � ������ ������ �
���������� ��� ���������������� ����������. �������� �� ����������������
���� �������� ������� ������ ������� ����� ��������, ���������� ��� ������
� ���������� "� �������", ��� �� ����� ����� �������� ����������� �����
������ ���������� �� ���������~R, �������� ����� �� �������� �
�������������, ��������� ���� � �.~5.1.3. 䋟 �������� ����� �������, ���
������� ���� �������� �������������������  (������������ �����)
����������� ��������� �������������� �����, ������������� �����~0 �~1.

%%312
\htable{򀁋��� 2}%
{䋈�� �������� ��� ����������� ������}%
{\strut\hfill$#$\bskip&\bskip\hfill$#$\bskip&\bskip\hfill$#$\bskip&
 \hfill$\qquad#$\bskip&\bskip\hfill$#$\bskip&\bskip\hfill$#$\cr
\omit\hfill ������ \hfill & \omit\hfill 䋈��\hfill & & \omit\hfill ������
\hfill & 䋈�� \hfill\cr
\omit\hfill ���������� \hfill  & \omit\hfill �������\hfill &\omit\hfill
�����\hfill &\omit\hfill ���������� \hfill & \omit\hfill �������\hfill
& \omit\hfill �����\hfill \cr
\noalign{\hrule}
1.00000P & 2.71828P & 1.00000 &  0.38629P &  2.00000P & 0.69315\cr
2.00000P & 3.53487P & 1.43867 &  1.30432P &  3.�����P & 1.15881\cr
3.00000P & 4.16220P & 1.74773 &  2.72294P &  4.00000P & 1.66862\cr
4.00000P & 4.69445P & 2.01212 &  4.63853P &  5.00000P & 2.16714\cr
5.00000P & 5.16369P & 2.24038 & 21.72222P & 10.00000P & 4.66667\cr
10.00000P& 7.00877P & 3.17122 &  5.29143P &  5.29143P & 2.31329\cr
\noalign{\hrule}
\noalign{\hbox{\strut "�����"~$k+\theta$ ��������� � ���.~22}}
}

��
$$
g_P(z_1, z_2,~\ldots, z_k)=\sum_{l_1, l_2,~\ldots, l_k\ge 0}
a_P(l_1, l_2,~\ldots, l_k)z_1^{l_1} z_2^{l_2}\ldots z_k^{l_k}
$$
---������������ ������� ��� ����� �������, �����������
��� $P\hbox{-�������}$~������ � ����������, ����������� �. ������ �����,
 ��� $a_P(l_1, l_2,~\ldots, l_k)$~���� ����������� ����, ��� ������
������� ����� �����~$l_1$, ������---�����~$l_2$,~\dots, $k\hbox{-�}$ �����
�����~$l_k$. ᓄ�� ������������ �� ��������� "������� �������������", �
��� ��� ������ ��� ������ � ������~$P=1$.

\proclaim 򅎐���~K.
$g_P(z_1, z_2,~\ldots, z_k)=g_1(z_1, z_2,~\ldots, z_k)^P$.

\proof �� �������� ����� ����~$X_1$, $X_2$, $X_3$,~$\ldots\,
$. ��������~R ��������� �� �� $P$~���������������������� � ������������
� ���, � ����� ������� ���� ������ ��� ��������;
���������������������, ����������~$X_n$, ������������ ����������~$X_1$,
~\dots, $X_{n-1}$. 򀊈� �������, ��� ���������������������  ��������
������������ �������������������� ����������� ��������� �����,
������������� �����~0 �~1. ꐎ�� ����, ����� ������ � ���������� �
�������� ��������� � ����������� $P\hbox{-��������}$ �������, ���� ���
���������� ��� ����� �����������������������; ��������� �������
����������� $j\hbox{-��}$~������� ��������������������� ����� � ������
�����, ����� �� ����������� $j\hbox{-��}$~�������, ����������� ���
������ � ���������� (��� ��� �� ����~R4 �����~|LASTKEY| �~$|KEY|(|Q|)$
����������� ����� ���������������������).

荀�� ������, ����� �������, ��� ��������~R ����������� � $P$~���������
����������� �������� ������ � ��� ���~R4 ������ ��������� ������ ��
�����, ���������������� �������� ����~|Q|; � ���� ������ ���������������
�������� ������������  $P\hbox{-��������}$ �������, ��� ����� ��������
���������� ��������� ���������.

򀊈� �������, �� ������ ����� ������� ����~$(l_1,~\ldots, l_k)$ ����� �
������ �����, ����� ��������������������� ������� ��
%% 313
�������� ����~$(l_{11},~\ldots, l_{1k})$,~\dots, $(l_{P1},~\ldots,
l_{Pk})$ ��������������; ���~$l_{ij}$---��������� ��������������� �����
�����, ��������������� �����������~$\sum_{1\le i \le P} l_{ij}=l_j$
���~$1\le j \le k$. ��� �������, ���
$$
a_P(l_1,~\ldots, l_k)=\sum_{
{\scriptstyle l_{11}+\cdots+l_{P1}=l_1 \atop
\scriptstyle \vdots} \atop
\scriptstyle l_{1k}+\cdots+l_{Pk}=l_k
}a_1(l_{11},~\ldots, l_{1k})\ldots a_1(l_{P1},~\ldots, l_{Pk}),
$$
��� ������������ �������� ����������.
\proofend

� �.~5.1.3 �� ������� ������� ��������~$L_k$---����� $k\hbox{-��}$~�������
���~$P=1$ (��� �������� ��������� � ����.~5.1.3-2). � �������~K �������,
��� ������� ����� $k\hbox{-��}$~������� ��� �����~$P$ � $P$~��� ������
������� ����� ���~$P=1$, ��� �����~$L_kP$;
��������� ����� � $P$~��� ������, ��� ��� ����������� ���������� �����
������� ���������������~$\sqrt{P}$. ��� ���������� ���� ������� ��������
�.~�.~㝑���� ����� 1958~�.

򀊈� �������, ������ �������, ���������� ��� ��������� ������
����������~R, ����� ����� �����, ����������� ������
$(e-1)P\approx 1.718P$~�������,
������---�����������~$(e^2-2e)P\approx 1.952P$, ������---$1.996P$; �����
��������� �������� ����� ����� ������ �~$2P$, ���� �� �� ������ ��
��������� ���� �������� (��. ���.~14). 񒀍������� ���������� �����
����������� ���� �������� �����������
�����~$\sqrt{(4e-10)P}\approx 0.934 \sqrt{P}$
[{\sl CACM,\/} {\bf 6} (1963), 685--687].

ꐎ�� �����, �������� ���.~5.1.3-10, \emph{���������} ����� ������
$k$~�������� ����� �������� ������ �~$\left(2k-{1\over3}\right)P$ ��
�����������
�����������~$\left(\left({2\over3}k+{2\over9}\right)P\right)^{1/2}$.
��������� �������~$g_1(z, z,~\ldots, z)$ �~$g_1(1,~\ldots, 1, z)$
��������� � ���.~5.1.3-9 �~11.

� ����������� ���� ������� ��������������, ��� �������� ���� ����������
�������, �� �������������� �������~K ����������, ��� ����� ����� ��
�����������~$a_P(l_1,~\ldots, l_k)$ ���������� �� � ������ ����� ���������
�������� ������������������, ���������� �� ������� ����
$l_1+\cdots+l_k+P$~���������. 񋅄���������, ���������� ����������
��������� ��� ����� �������, ������, $N > (2K+1)P$ � ���� ����� ��������
������������ ����������.

� ������������ � ����� ����������, � ������� ����� ������� �������,
����� ��������� ������� ���� �������������, � ���������---����������.
������ �������, ��������������� � ������ � ����� ������������� �������,
����� ��������� ��������� �����, � ������� �������, ��� ��������� ������,
�� ��������� ����������� ������������ ��������� ������� ����� ��������.
����������, ��������, ���������������, ������� ������
%%314
��������� �������� ������ ���, ��� �� ��������� ����� ������ ������;
�� ����� ����� ������ ������������� �� ������ ��� ���������� �������. �
������ ����������� ����������� ����� �������� ��� ��������� ������
���������� �����~$1.5P$ �~$2P$ (��.~���.~24).

\excercises
\ex[10] ꀊ�� ����� ��� 4 � ������� ������� �������� ������� � ������
����� ������?

\ex[12] ꀊ�� ��������� ��������� �� � ������ ���.~63, ���� �� ����~$061$
��� ������� ������~$612$?

\ex[16] (�.~�.~쓐.) ��� ��������� � ���������� ����������
��������������� ������ � ���������� � ���������������� ������ ����������
�����������\note{1}%
{⎑�������� ���� ��� ���� ����� ���� ������ �������� �� ���� ����������
����� �����, ����������� ���� ���� ������� � ���������� � ���, ��� ���
���� ������� �������.---{\sl �. �����.\/}}
{\medskip\narrower\tt\noindent
fourscore and seven years ago our fathers brought forth on this continent
a new nation conceived in liberty and dedicated to the proposition that
all men are created equal.
\medskip\noindent}
(葏�������� ������� ���������� �������, ������������ ������ �����
��� ���� ����.)

\ex[16] ������ �������������� \emph{�����������} ����� � �����������
�� ���.~3, ��������� ��������� �������~4.

\ex[00] ⅐�� ��, ��� ����� � ����������, ������������ ������, ��������,
������ ���� $P$~���� ������� ������ ��� ����� ���� �������� ������?

\ex[15] � ���������~R �����������, ��� $P$~������ ����~$\ge2$;
����� ������������ ��������� ��������� ���� ������� � ���� ���������,
����� �� ��������� ������� ��� ����~$P\ge 1$?

\ex[17] ��� ������ ��������~R � ������ ���������� �������� ����������?

\ex[20] ��������~R ���������� ������������� ����~"$\infty$", �������
������ ���� ������ ������ ���������� �����. �����, ��� ���� ��
�����-������ �������� ���� �������� ������~$\infty$, �� �������� ��� ��
���������, � ���������, ��� �������� �������� � ������, ����� ����������
"���������" ������������� ��������.

\rex[23] ꀊ �� �������� �� ��������~R, ����� �� �������
��������� �������� ������� (������������~|RC|) � ������������ �������, �
������ � ���������?

\ex[26] 퀗������ ��������� ����������~|LOSER| �� ����~R1 ������
�� ������������� �������� ��������������� �������, ��� ��� �������
����~$P+j$ ����� �� ������ � ��������� � �������� �� ����������
����~$j$. ������, ������ ��������~R ��� ����� ��������.
[\emph{󊀇����.} ᓄ�� �� �������� ��������~R, ����
���������~$\set{|LOSER|(|LOC| (X[0])),~\ldots,
|LOSER|(|LOC| (X[P-1]))}$ ������������� �� ����~R1 \emph{������������}
������������ ���������~$\set{|LOC|(X[0]),~\ldots, |LOC|(X[P-1])}$?]

\ex[�25] ⅐�� ��, ��� ��� ��������� �������� ������ ����������� ����,
���~$|KEY|(|Q|)<|LASTKEY|$ �� ����~R4, ����������� �����~1/2?

\ex[M46] ������ ��������� ������������ ����, ������� ��� �����������
������ ����� ���������~R; ��������, ��� ����� ����������� ������������
�� ����~R6?

%%315
\ex[13] ��� ������ �������, ���������� ��� ������ � ����������, ������
������� �������?

\rex[��25] 葏�������� �������� �� ����������������, ����� ������� �������
����� ���� \emph{���������} ��������, ���������� ��� ������ � ����������,
 ����������� � ������� ������������������ �������� ������.

\ex[20] ⅐�� ��, ��� ��������� �������, ���������� ��� ������ �
����������, ������� �� �������� ����� $P$~�������? ����� ��� �����.

\ex[�26] 퀉���� "�������" ����������� � ����������� ������� ����, ���
����~$R_1$~$R_2$~\dots{} $R_N$ ����� ��������� ���������� �� ���� ������
$P\hbox{-��������}$ ������ � ����������. ꀊ��� ����������� ����� �������
��� �������~$P$ �~$N$, ���� ��������� ������� ������ ���������
������������ ���������~$\set{1, 2,~\ldots, N}$?

\ex[20] ��� ���������� � ���������� ������ ���������~R, ����� ��������
����� ������������ ����� ��������������
������������������~$K_1\ge K_2\ge\ldots\ge K_N$?

\rex[22] ��� ����������, ���� ����� ��������� ��������~R � �����,
����������� � ���������� ������ ���������~R?

\ex[��22] 葏�������� �������� �� ����������������, ����� ��������, ���
������ �������, ���������� ��� ������ � ����������, ����� ����� ��������
$(e-1)P$~�������.

\ex[��24] ꀊ�� �������� ����� ����� ������ �������, ���������� ���
����������� ������, �����~$P=P'$?

\rex[��23] ������� ��������������� ����� ��������,
���������� ����������� ������������ ������ ���~$P'<P$.

\ex[��40] ����� ����� ���������� �������� ����������� ������� �����
��������, ���������� ��� ����������� ������ ���~$P'>P$.
��~$\kappa=k+\theta$---�������������� �����~$\ge 1$,
���~$k=\floor{\kappa}$, �~$\theta=\kappa \bmod 1$, � ����������
�������~$F(\kappa)=F_k(\theta)$, ���~$F_k(\theta)$---��������, ������������
������������ ��������
$$
\sum_{k\ge0} F_k(\theta)z^k=e^{-\theta z}/(1-z e^{1-z}).
$$
򀊈� �������, $F_0(\theta)=1$, $F_1(\theta)=e-\theta$,
$F_2(\theta)=e^2-e-e\theta+{1\over2}\theta^2$ �~�.~�.

��������, ��� � ������~$t=0$ ��������������� ��������
������������ ������� ������������ ������, � ��������, ��� �� $T$~������
������� ������ ���� ������ ����� $P$~��������. � ���� ������ ������
��������������� �������� ��� �� ����, ������� � ������ �������~$t+T$ ��
�� ���������, ��� ������� ������ ��������������� � ������~$t$. � �����
������, � �������~$\kappa T$ ������ ������� ��������������� ������ �����
$P'$~��������; �� ��������� ������� ������� ������ � ��������.

葏������ ��� ������ ��� ������������� ������������ ������, ��������, ���
����� �������~$e^\theta F(\kappa) P$ ���������� ���
$$
P'/P=k+1+e^\theta\left(\kappa F(\kappa)-\sum_{0\le j \le \kappa}F(\kappa-j)\right).
$$

\ex[��35] ������� ���������� ����������� ����������� ����� � ��� ������,
 ����� ������ �� ���������� ������ �������� � ��� �� �������, � �������
��� ������������: "������ ����������---������ �����������". ���� �����
��������, ������� ���������� ��, ���� �� ���������� ����������, ����������
�� ����������� �������, �������� � ���������� \emph{���������} �������,
��� ���� �� ������ � ���������� ��������� �������������� ����� ���������.

\ex[��39] ���� ����� ����������---������ �����������, ��������� ���������
���������� ����������� ������������ �������� � ������ � ����������.
%%316
\medskip
\item{a)}~��~$g_P(z_1, z_2,~\ldots, z_k)$---�� �� ������������ �������,
��� � � �������~K, �� ��� ������� �� $k$~�������� ����������, �������� ��
�� ������������ ��� ���������. 퀏�����, �� ����� �������, ��� ���
������� � ��������� �������� ������������, � � ������� ��������� �����,
 ��� �������~K ����������� ��� ������ �� $2^k$~������������ �������
������ ����.

\item{b)}~� ����~(a) ����� �������~$P=1$. 쎆�� ����� ������������,
��� �������� �������� ���������� �������������� ������������������
����������� ��������� �������, ����������� �����~0 �~1 ��
$$
a(x,y)=\cases{
e^{1-x}-e^{y-x}, & ����~$x\le y$;\cr
e^{1-x},               & ����~$x>y$.\cr
}
$$
��~$f(x)\,dx$---����������� ����, ��� ������������ ������������ �������
���������� �~$x$. 䎊�����, ���~$\left(\int_0^1a(x,y) f(x)\,dx\right)\,dy$
���� ����������� ����, ��� ��������� ������� ���������� �~$y$.
[\emph{󊀇����:} ����������� ��� �������~$n\ge0$ ����������� ����,
���~$x\le X_1\le\ldots\le X_n >y$ ��� ������~$x$ �~$y$.]

\item{c)}~����������� �������, �������� ����������� ������������ �
������������~$p$, ������� �������, ����������� ������� �������, �����
�������, ��������� � ������������ ����������� ������� �
������������~$q=1-p$ � �������������� ��� � ������������~$p$. (򀊈�
�������, ����~$p=0$, �� ��� ������� ����� ���������� �����������;
����~$p=1$, ����������� �������� ����������, � ���~$p=1/2$ �������
��������� � �����������) ��
$$
f_1(x)=1,\quad
f_{n+1}(y)=p\int_0^1a(x,y)f_n(1-x)\,dx+q\int_0^1a(x,y)f_n(x)\,dx.
$$
�����, ��� ����������� ����, ��� $n\hbox{-�}$~������� ���������� �~$x$,
����~$f_n(x)\,dx$, ���� $(n-1)\hbox{-�}$~������� ������������,
�~$f_n(1-x)\,dx$, ���� $(n-1)\hbox{-�}$~������� ���������.

\item{d)}~퀉���� �������~$f$ ��� ��������� "��������������� ������"
$$
f(y)=p\int_0^1a(x,y)f(1-x)\,dx+q\int_0^1a(x,y)f(x)\,dx,\quad \int_0^1f(x)\,dx=1.
$$
[\emph{󊀇����:} ��������, ���~$f''(x)$ �� ������� ��~$x$.]

\item{e)}~�����, ��� ������������������~$f''(x)$ �����~(c) ������
������ �������� � �������~$f(x)$ �����~(d).

\item{f)}~�����, ��� ������� ����� ������������� �������,
������������� �~$x$, �����~$e^{1-x}$.

\item{g)}~퀊����, ���������� ��� ���������� ���������� � ��������
��������� �������. \dfn{呋� ����������� ���������������� �������� ���
������ � ���������� ���������� ���������� �� ��������������� �
������������~$p$, �� ������� ����� ������� ��������� �~$(6/(3+p))P$.} (���
������� ���~$p=1$  ������� ���� �������� ꍓ��� [{\sl CACM,\/} {\bf 6}
(1963), 685--688]; ���~$p=1/2$ �� ������� �.~�.~ꎍ���� �~1978~�.)

\ex[��40]����������� ��������� ���������.
{\medskip\narrower
%!!! ���������� �����, ��������� � ����������
\item{N1.}~������ ������, �������� �� � ��������� �������� � ���� �����.
 瀒�� ��������� ��������� ������~|R|, � �����~|K| ����� �� ������.
%
\item{N2.} ⛂���� ���������� ����������, ����������~|LASTKEY| ������ ���
����� � ���������� ���������.
%
\item{N3.}~呋�~$|K|<|LASTKEY|$, �� �������~|R|,
����������~$|LASTKEY|\asg |K|$ � ������� �~N5.
%%317
\item{N4.}~呋� ��������� �� ����, ��������� �~N2; � ��������� ������
���������~|R|
� ���������.
%
\item{N5.}~������ ����� ������~|R| � ����������~|K| ������ �� �����. ����
�~N3.
\endmark\medskip}

��� ���������, � ��������, ������������ ������������ ������
�~$P=1$ �~$P'=1$ ���~$P'=2$ (� ����������� �� ����, � ����� ������ ��
���������� ���������---��� ������ �� ���������� ��� ����� ��� ���� �����
��������. � ����������� ��������� ����� �������, ������������� ���), ��
����������� ����, ��� ��� ��������� ��������� \emph{���������} ������� �
������� �� ���������������. ��� ���������� �� �������� �����, ��� ������
��� ����� ����.

䅉�����, ��� � ���.~24, ��������� �����~$f_n(x, y)\,dy\,dx$ �����������
����, ��� $(x, y)$~���� ��������~$(|LASTKEY|,|K|)$ �������������� ����� ��
����� $n\hbox{-��}$~���������� ����~N2. 䎊�����, ��� ����������
�������~$g_n(x)$ �� ����� ����������, �����, ���~$f_n(x, y)=g_n(x)$,
����~$x<y$, �~$f_n(x, y)=g_n(x)-e^{-y}(g_n(x)-g_n(y))$, ����~$x>y$.
�������~$g_n(x)$ ������������ �������������~$g_1(x)=1$,
$$
g_{n+1}(x)=\int_0^x e^ug_n(u)\,du+\int_0^x dv\,(v+1)
\int_v^1du\, ((e^v-1)g_n(u)+g_n(v))+
+x\int_x^1dv\,\int_v^1 du\,((e^v-1)g_n(u)+g_n(v)).
$$
����� �����, ��� ��������� ����� $n\hbox{-��}$~������� �����
$$
\int_0^1\,dx\int_0^x\,dy(g_n(x)(e^y-1)+g_n(y))\left(2-{1\over2}y^2\right)
+\int_0^1dx\,(1-x)g_n(x)e^x.
$$
[\emph{瀌������.} ������� ����� ��������� � �������������� ������
����������� ����� �������; ��� ���� �������� ������� �.~쀊-ꅍ���. �
�������, ��� ����� ������� ��������� � ����������� ��������~2.61307209.
򅎐���~K �� ��������� � ������������ ������, ��� ��� ������~$P=1$ ������
�������������� �� ������~$P$.]

\ex[�33] ������������ �������� ���.~25 ��� ����������� ������������ ������
���~$P'=1$, ������� ������� ����� \emph{�������} ������� ���~$P'=r$
��� �����~$r\ge0$ �� ��������� �����:
\medskip
\item{a)}~�����, ��� ������ ������� ����� �����~$n$ � ������������
$$
(n+r)\stir{n+r}{n}\Big/(n+r+1)!.
$$

\item{b)}~������ "����� 񒈐����� ������� �������"~$\Stir{n}{m}$ ���������
$$
\Stir{0}{m}=\delta_{m0},\quad
\Stir{n}{m}=(n+m-1)\left(\Stir{n-1}{m}+\Stir{n-1}{m-1}\right)\rem{��� $n>0$.}
$$
䎊�����, ���
$$
\stir{n+r}{n}=\sum_{0\le k \le r}\perm{n+r}{k+r}\Stir{r}{k}.
$$
%%318
\item{c)}~䎊�����, ��� ������� ����� ������� ������� �����, �������������,
 $c_re-r-1$, ���
$$
c_r=\sum_{0\le k \le r}\left[\left[{r\atop k}\right]\right] (r+k+1)/(r+k)!.
$$

\ex[25] � ������ ��������������� ������ ������ ����������
������� �������������� �������. ꀊ �������� ������� ������������ ����� �
���������� � ������� \emph{���������� �����?}

\subsubchap{썎�������� �������} %5.4.2
򅏅��, ����� ���� ��� �� ��������, ��� ����� ���������� ��������� �������,
 ���������� ��������� ������ �������������  �������� �� ������ � �������
�� �� ��� ���, ���� �� ��������� ������������ �������.

�������� �������, ��� � ����� ������������ ������� ��� ���������
����������: $T1$, $T2$ �~$T3$; ����� ��������������� ����������������
��������, ��������� � ������~\S~5.4, ���~$P=2$ �~$T=3$.  ���������
��������� ���:
%% !!! ���������� �����, ��������� � ����������
{\medskip\narrower
\item{B1.}~������������ ��������� ������� ����������� �� �����~$T1$ �~$T2$.

\item{B2.}~񋈒� ������� � ����~$T1$ �~$T2$ ��~$T3$; ����� ������������,
 ����~$T3$ �������� ������ ���� �������.

\item{B3.}~񊎏������� ������� �~$T3$ ����������� ��~$T1$ �~$T2$,
����� ��������� � ����~B2.\endmark
\medskip\noindent}
呋� ��������� ������������� ���� 5~��������, �� ������ ������ �������
�������� � $\ceil{S/2}$~�������� ��~$T3$, ������---�~$\ceil{S/4}$ �~�.~�.
򀊈� �������, ����, ������, $17\le S \le 32$, �� ���������� 1~������
�������������, 5~�������� ������� � 4~������� �����������; � �����
������ ���~$S>1$ ����� �������� �� ���� ������ ����� �����~$2
\ceil{\log_2 S}$.

���� ����������� � ���� ��������� ������������, ��� ��� ��� ��
��������� ����� ��������. 쎆�� �������� ��������� �����������, ����
������������ \emph{����������} ���������:
%% !!! ���������� �����, ��������� � ����������
{\medskip\narrower
\item{A1.}~������������ ��������� ������� ����������� �� �����~$T1$  �~$T2$.

\item{A2.}~񋈒� ������� � ����~$T1$ �~$T2$ ��~$T3$; ������������, ����
$T3$~�������� ������ ���� �������.

\item{A3.}~񊎏������� \emph{��������} �������� �~$T3$ ��~$T1$.

\item{A4.}~񋈒� ������� � ����~$T1$ �~$T3$ ��~$T2$; ������������, ����
$T2$~�������� ������ ���� �������.

\item{A5.}~񊎏������� \emph{��������} �������� �~$T2$ ��~$T1$. ⅐������
� ����~A2. \endmark
\medskip\noindent}
����� �������� �� ���� ������ �����������
��~${3\over2}\ceil{\log_2 S}+{1\over2}$,
%%319
\bye
