\input style
\chapnotrue
\chapno=5\subchno=2\subsubchno=3
%% 188

�� $s_l$---������ ��������� � ������~$l$, 
�~$M_N$---���������������~$\{s_1, s_2, \ldots, s_N\}$ ���� ���� ��������. 
葏������ (14) � (15), ����� ���������~$M_N$ ��� ����� ��������~$N$. � 
���.~5.1.4--20 ��������, ��� ����� ����� �������� ��������� �������� 
�� ����� ����� $\{1, 2, \ldots, N\}$ �����
$$
N!/s_1s_2\ldots s_N= N!/\prod_{s\in M_N} s.
\eqno(16)
$$
퀏�����, ����� �������� ����������� 26 ���� $\{A, B, C, \ldots, Z\}$ �� 
���.~28 ���, ����� �� ��������� ���������� ���������� �������, �����
$$
26!/(26 \cdot 10 \cdot 6 \cdot 2 \cdot 1 \cdot 1^{12} \cdot 3^6 \cdot 7^2 
\cdot 15^1).
$$

򅏅�� �� � ��������� ���������������� ���� ���������� �������� � 
���������~H, �. �. ����������, ������� ����������� �� ����, ��� � ���� H2 
������� ���������� ������� $l=1$. � �������, ��������� ��������� ���� 
������� ������ ���������� �������� ����� ������ � �������� ����������� �������� �������������.

\proclaim 򅎐��� H. 呋� ��������� ������� ��� ��������� H 
������ ��������� ������������ ��������� $\{ 1, 2, \ldots, N\}$, �� � 
���� ���������� �������� � ���������� ������������ ����� ���������� 
����� �� $N! /\left(\prod_{s\in M_N} s\right)$ ��������� �������. ᎋ�� 
mo��,
��� $\floor{N/2}$ �������� �������������, ����������� �� ����� ���� ����, 
"����������" � ��� ������, ��� �� ���������� ���� H8 ��� $s_l$ ��������� 
�������� ����������~$i$ �������������.

\proof ����� �����, ������� � ��������� ������� ���������� ������� 
"�������� ������". �� � �������� ������ �� ��������� ����������� 
�������� ������������� ������ �������� $K_1$ \dots{} $K_N$ � ������ � 
����~$l$; ����� ����, ��� ������� �����~$s_l$ �������� ������������ $K'_1$ 
\dots{} $K'_N$ �����, ������� ����� ������������� ���� ����� ���������. 
⑅ ��� �������� ������������ ����� ��������� �������� $K'_l$, 
�������������, ��������� � �������� �����������, ���������� ����� $s_l$ 
$s_{l+1}$ \dots{} $s_N$ �������� ������������ ��������� 
$\{1, 2, \ldots, N\}$, ������� ����� ���������� �������� ������������� � 
�������~$l$ ���� ������������ $K_1$ \dots{} $K_N$.

񋓗�� $l=1$ �������: ����� $K_1$ \dots{} $K_N$---��������, � ����� $K'_1$ 
\dots{} $K'_N$---����, ������� ������������� � $K_1$ \dots{} $K_N$ � 
���������� ������������� ��� $l=1$, $K=K'_1$. 呋� $K=K_i$, �� ������
����� ����� ��������� $K'_i=K_{\floor{i/2}}$, 
$K'_{\floor{i/2}}=K_{\floor{i/4}}$ � �. �., ��� ���� $K'_j=K_j$ ��� ���� 
$j$, �� ������� �� ���� ��~$1$ �~$i$. ����, ��� �����~$i$ � ���������� 
������ ���������� ���������� ���� $K'_1$ \dots{} $K'_N$, �����, ��� (a) 
�������� ������������� �����������
%% 189
���� $K'_1$ \dots{} $K'_N$ � $K_1$ \dots{} $K_N$ � 
(b) $K_{\floor{j/2}}\ge K_j$ ��� $2 \le \floor{j/2}<j\le N$. 
񋅄���������, �������� �����~$N$ 
����� ������ $K'_1$ \dots{} $K'_N$,  � �������� ������������� ����������. 
(��� �������������� ���� ������� ��. � ���.~22.)\proofend

������ � ��������� $A$, $B$, $C$, $D$ � ������� ���������~H, ����� 
������, ��� ����������� �������� �������������, ������������ ��� 
���������� �������~$s$, ���� ����� $\floor{s/2}/s$ � ������� �������� 
��������~$A$; �� ����� � ������� �������� ��������~$B$ �����
$$
{1\over s}(0+1+1+2+\cdots+\floor{\log_2 s})=
{1\over s}\left(\sum_{1\le k\le s} \floor{\log_2 k}\right)=
{1\over s}((s+1)\floor{\log_2 s}-2^{\floor{\log_2 s}+1}+2)
$$
(��. ���. 1.2.4--42); � ��� ���� �����~$2/s$ ���~$0$ � ������� �������� 
��������~$D$ � ����������� �� ����, �������� ��~$s$ ������ ��� ��������. 
텑������ ������� ���������� ��������������� ����� � ������� �������� 
��������~$C$, ��� ��� ��� ������ ��������������� �������� (��. ���.~26). 
������ ������������ �� ���� ��������� �������������, �������, ��� 
������� �������� ��������~$A$ �� ����� ���������� �������� �����
$$
A'_N=\sum_{s\in M_N} \floor{s/2}/s;
\eqno(17)
$$
����������� ������� ����� ����� � ���~$B$, $C$ �~$D$, ��� ��� ����� ��� 
������� ����� ����� ��������� ��� ������� ��������. � ��������� ������� 
��������� �������� ����������:
\ctable{
\hfill\bskip$#$\bskip&&\hfill\bskip$#$\bskip\cr
N\hfill & A'_N\hfill & B'_N\hfill& C'_N\hfill & D'_N \hfill\cr
  99 &  19.18 &  68.35 &  42.95 & 0.00 \cr
  100&  19.93 &  69.39 &  42.71 & 1.84 \cr
  999&  196.16& 734.66 & 464.53 & 0.00 \cr
 1000&  196.94& 735.80 & 464.16 & 1.92 \cr
 9999& 1966.02& 7428.18&4695.54 & 0.00 \cr
10000& 1966.82& 7429.39&4695.06 & 1.97 \cr
10001& 1966.45& 7430.07&4695.84 & 0.00 \cr
10002& 1967.15& 7430.97& 4695.95& 1.73 \cr
}
��� �������� �����������, �� �~$M_N$ ����� �� �������� �������� �� 
������� ������ �����������, � ����� �� ������, ��������, ���
$$
A'_N={N\over 2}\cdot{0\over1}+{N\over 4}\cdot{1\over3}+
{N\over8}\cdot{3\over7}+\cdots+O(\log N)=
\left(1-{1\over2}\alpha\right)N+O(\log N),
\eqno(18)
$$
%% 190
���
$$
\alpha=\sum_{k\ge 1} {1\over 2^k-1}=
1.60669\ 51524\ 15291\ 76378\ 33015\ 23190\ 92458\ 04805\hbox{---}.
\eqno  (19)
$$
(��� �������� ������� �.~�.~���� �������, ��������� ��������������� 
���� �� ���.~27.)  �������~$N$ ����� ������������ ������������ �������
$$
\eqalign{
A'_N&\approx 0.1967N+0.3 \hbox{ ($N$ ���.)}, 
  \quad 0.1967N-0.3 \hbox{($N$ �����.)};\cr
B'_N&\approx 0.74403N-1.3\ln N;\cr
C'_N&\approx 0.47034N-0.8\ln N;\cr
D'_N&\approx 1.8 \pm 0.2 \hbox{ ($N$ ���.)},
  \quad 0 \hbox{($N$ �����.)}.\cr
}
\eqno(20)
$$
텒����� ���������� ����� ������������ � ����������� ��������. 䋟 
���������� �������� ��������� ����� $O(N)$ ����� (��. � ���.~23).

����, �� ��������, ����������� ������ ���� ���������� �������� � 
���������~H. ������ ���� ������---������ ������ ������, ������� ��� ������� 
������ �������! �� ������������� ���������� ����������� � 
$N$~���������; ��������� ����� $A''_N$, $B''_N$, $C''_N$ �~$D''_N$ ������� 
�������� ������� $A$, $B$, $C$ �~$D$ �� ����� ���� ������. ������ 
���������~H ���������� ������������ ����� ���������� ����� ����������� 
������������� ������� ��������
$$
\eqalign{
A''_N &\approx 0.152N;\cr
B''_N &\approx N\log_2N-2.61N;\cr
C''_N &\approx {1\over2}N\log_2N-1.4N;\cr
D''_N &\approx \ln N\pm 2;\cr
}
\eqno(21)
$$
��� �� ����� �� ��� ��� �� ������� ����������� �������������� ���������� 
���� ����������. ���������� ��������� �������� �������������, �������� 
������� ������� ������, ��������� � ������������ (8), ����, ���� 
������������� �������� ��� �����, ������� ������ ���~$C$, ��-��������, 
������� ���������
�������������� ��~${1\over 2}N\log_2 N$.

\excercises
\ex[10] ߂������ �� ���������� ����������� �������� ������ (�������� S) 
"����������"?

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

%% 191
\ex[�21] (a) 䎊�����, ��� ���� �������� S ����������� � 
��������� ������������ ��������� $\{1, 2, \ldots, N\}$, �� � ���������� 
������� ���������� �����~S2 �~S3 ���������� ��������� ������������ 
��������� $\{1, 2, \ldots, N-1\}$, �� ������� �������~$N$. (荀�� ������, 
���� $K_1$ \dots{} $K_{N-1}$ � ���������� ������������ ����� ���� ����� 
������������� ��������� $\{1, 2, \ldots, N-1\}$.) (b) 񋅄���������, ���� 
����� $B_N$ ���������� ������� �������� ��������~$B$ � ���������~S, �� ��� 
�������, ��� �������� ���� ���������� ��������� �������, 
�����~$B_N=H_N-1+B_{N-1}$. [\emph{󊀇����:} ��. �� 
��������������� ���������������� 1.2.10--16.]

\rex[�35] � ����~S3 ���������~S ������ �� ��������, ���� $i=j$. He 
����� �� ����� ����������� ����~S3 ��������� �������~$i=j$? ���� ����� 
������� ����� ������� ���������� ������� $i=j$ � ����~S3, ���� �������� ���� 
�������?

\ex[20] ���� ����� �������� ��������~$B$ � ������� ���������~S 
��� ��������� ����� $N \ldots 3\ 2\ 1$?

\ex[�29] (a) �� $a_1$ $a_2$~\dots{} $a_N$---������������ ��������� $\{1, 
2, \ldots, N\}$ �~$C$ �������, $I$~���������� � �����, ��� ��� �� 
���������� � ������� ���������~S ������������ $B$~������� �� 
�������������� ��������. 䎊�����, ��� $2B\le I+N-C$. [\emph{󊀇����:} ��.
 ���.~5.2.2--1.] (b) �����, ���~$I+N-C\le\floor{n^2/2}$; �������������, 
$B$ �� ���������~$\floor{n^2/4}$.

\ex[�46] 퀉���� ��������� ��������~$B$ � ���������~S ��� ������� ��~$N$, 
������, ��� �������� ���� �������.

\ex[24] �����, ��� ���� ��� ������~$\max(K_1, \ldots, K_j)$ � ���� S2 
������������� ����� ����� �������: $K_1$, $K_2$, \dots, $K_j$, � �� 
��������: $K_j$, \dots, $K_2$, $K_1$, ��� � ���������~S, �� �� ���� ����� 
����� ���� �� ��������� ����� ��������� ��� ��������� ����������� 
����~S2. 퀏����� \MIX-���������, ���������� �� ���� ����������.

\ex[�25] ���� ����� ������� ����� ���������, ����������� ���������� �� 
���.~8 ��� ���������� ��������� �����?

\ex[12] ꀊ ����� ��������� ������, ������������ �� ���.~23, ����� ���� 
��� ����� ��������~14 ��~16 �������������� ���������?

\ex[10] ꀊ ����� ��������� ������, ������������ �� ���.~24, ����� ������ 
��������~$908$?

\ex[�20] 񊎋��� ��� ����� ��������� ���������~$-\infty$ �~$\infty$, 
���� ��������� "����������" �����, �������������� �� ���.~23, ��� 
������������ ����� �� $2^n$~���������?

\ex[20] (�.~�.~�.~󈋜���.) � ����~H4 ���������~H ����������� ��� 
������: $j<r$, $j=r$ �~$j>r$. �����, ��� ���� $K\ge K_{r+1}$, �� 
����� ���� �� ��� ��������� ���~H4, ����� ������������ ����������� ���� 
�� ���� �����. ꀊ ���� �������� ���~H2, ����� ���������� � �������� 
������������� ���������� ���������� ������� $K\ge K_{r+1}$?

\ex[10] �����, ��� ������� �������---������� ������ 
������������. (������, ����� ����� ����� ����������� ���������, ����� 
��������� "���������� �� ����������---������ �����������" ���� ������������ 
��������� "������ ����������---������ �����������".) ߂������ �� ���� 
����� ������� ������� ������������ �������?

\rex[M22] (�.~�.~������.) ������� ������� �������� ���������� ������� 
������� ����� $\le N$, � ������� ������������ \emph{������������ 
�������} � ����� �������� �������� �������. [\emph{󊀇����.} �� 
���������� ���� � ������������ ������� ����� ���������� �������� ��������� 
������, �������, ��� ����� ��������� �������� �����, ����������� ��� 
�������� � ������� �����. �������� ������ � �������� ����� ��������� 
� ���� �������.]

\ex[20] ������ ����������� ��������, ������� ��������� ����� ���� � 
������ �������� �� � ���������, �������� �������� �� $n+1$~���������.

\ex[20] �������� �� ���.~16 ����� ������������ ��� ���������� �������� 
������ ������ "���������� $l$ ��~$1$", ������������ � ���������~H.

%%192
������ �� ��� ������ �� ������ � ���� �� ��������� ����� ���� � �� �� ��������?

\rex[21] (�.~�.~􋎉�) � ����� ���� ������ � ��������� ������������� 
���������� ���� $K$, ��� �������, ��������� �������� ����� ��������, � 
������� ����� ��� ���� ���������� � ���� H6 ��������������, ��� 
$K<K_j$. ꀊ. ����� �������� ��������, ����� ���� $K$ �� ����������� 
�~$K_j$ � �������� ����� ����������?

\ex[21] ������� �������� ���������� ������� �������� �� �������� 
������� $N$, ����������� �������� �������~$N-1$.

\ex[�20] �����, ��� ������� (14) ������ ������� ������ ����������� ��������.

\ex[�24] 䎊�����, ��� ������� (15) ������ ������� �������� ����������� ��������.

\rex[20] ꀊ�� ������������ ��������� $\{1, 2, 3, 4, 5\}$ ���� 
���������� �������� � ���������~H ����������� � $5\ 3\ 4\ 1\ 2$?

\ex[�28] (a) 䎊�����, ��� ����� ����~$B$ � ��������� 
������������� ������� �� ��������� $\floor{\log_2(r/l)}$. (b) 񎃋���� 
������������ (8), �� ��� ����� ���������� ���������� ���������~H 
��������~$B$ �� ����� ��������� $N\floor{\log_2 N}$. 퀉���� ������������ 
��������~$B$ �� ������������ �������� ������ ��� ������� ��~$N$. (� 
������ ��������, ��� ���������� �������� ����, �� �������~$B$ ��������� 
��� ������������ ��������.)

\ex[�24] ⛂����� ������ ������� ������������ ���������� 
��������~$B'_N$ (��������� ����� ����, ����������� �� ������ �� ����� ���� 
���������� �������� � ���������~H).

\ex[�20] ���� ����� ������� ����� � �������� ��������~$C$ �� ����� ������ 
�������� �������������, ����� $l=1$, a $r=N$, ����~$N=2^{n+1}-1$.

\ex[�30] ������ ���.~25:  (a) ��� $N =26$, (b) ��� �������������~$N$.

\ex[�25] (�.~�.~����~��.) 䎊�����, ��� 
$\sum_{n\ge 1} x^n/(1-x^n)=\sum_{n\ge 1} x^{n^2}(1+x^n)/(1-x^n)$. [���� 
$x={1\over2}$, �������� ����� ������ ���������� ��� ��� ���������� (19). )

\ex[35] ������� ���� \emph{��������� �������}, ���������� �� 
������ ���������, � �� �������� ��������. ᓄ�� �� ��������� ������������� 
���������� ������� ��������?

\ex[26] (�. �. ᐀��.) ������ �������� ��������� ����������� 
��� ��������� 
�����~$(a_1x^{i_1}+a_2x^{i_2}+\cdots)(b_1x^{j_1}+b_2x^{j_2}+\cdots)$, 
������� �� �������� ������������ ������������ $c_1x^{i_1+j_1}+\cdots$ �� 
�������, �� ���� ���� ��� ������������� ������������ �������� 
�����������. [\emph{󊀇����:} '�������������� ���������� ������������ ��������.]

\ex[�48] 쎆�� �� ��������~$C$ ��������� ${1\over2}N\log_2 N$ ��� 
������������� ���������� �����? ���� ����� ������������ ��������~$C$? 
���� ����� ����������� ��������?

\ex[37] (�.~�.~�.~󈋜���.) �����, ��� ���� ��� �������� ���������� 
������� ���������� "��������� � ���������", �� ��� ���� 
����������� ������������ ���������, � ������� � ����� ������ ����� �� 
$O(\log n)$~����� ��������� ���� ����������, ���� ���������� �������. 
(򀊓� ��������� ����� ������� \emph{������������ �����}.)


\ex[21] ������������ �������� ������� ���� ���������������� ������������ 
��������, �������������� � ���� ������������� ��������, � ����. (� 
���������, ���� ���� �� ������ �������� �������� ����� ���� �������, �� 
��� �������� ����� ��������� ��� � ������ �������.) 

\rex[15] ��� � ������������ �������, �������������� � ���� 
�������������� ������, �������� �������� ����� ����������� ����� �������
%% 193
���� �����������, � �� "�����������" ����� �� ����������� � �������, ��� � ��������?

\ex[�47] 񊎋��� ����� ��������� ������������� �������� �� $N$~�����, ���� 
������������ �������� ����~|KEY|? [��� ������������������ ���������� � 
����� $1$, $1$, $2$, $4$, $8$, $17$, $38$, \dots; ���������� �� 
�����-������ ������� ��������������� �������?]

\ex[26] 呋� � ������������� ������ �~$N$ ������ �������� ����� |UP| (��. 
� ����������� �������� � ����� ������� � �.~6.2.3), �� ��� ���� 
����������� ��������� �� ������������ ������� ������������ ����~|P| 
��������� �������: ����� |LEFT(P)| �~|RIGHT(P)| � ��������� ���������� 
��������� �� �����~|P|, ����� ���������� ����~|DIST| � ������� ����~|P| �� 
��� ���, ���� �� ����� ��������� ���� ������, ���� ����, � �������� 
����~|DIST| �� ��������.

䎊�����, ��� ��� ���� ������� �� ����������� �������� ����� ��� $O(\log 
N)$ �����~|DIST|, �������� ���� �� ��, ��� ������ ����� ���������. ����� 
������� ���������� ����.

\ex[18] \emph{(瀌������ �������� ����� �������������� ��������.)} 
썎��� ������������ ������� ���������� �������� ���������� ����: ��� 
������� ����� ��������� ��� ��������---"�������������" ���� � ��������� 
�������� ����� "���������������" ���� ����� �����. ꀊ�� ��������� ������ 
��������� ���������� �������� ����� "���������������" ����?

\subsubchap{񎐒������ ��������} %5.2.4
\dfn{񋈟���} �������� ����������� ���� ��� ����� ������������� ������ � 
���� ������������� ����. 쎆��, ��������, ����� ��� ��������---$503\ 703\ 
765$ �~$087\ 512\ 677$, 
�������~$087\ 503\ 512\ 677\ 703\ 765$. ���� ������ ������� 
���---�������� ��� ���������� ��������, ������� ���������� �� ��� � 
��������� ��� ���������.

퀗�� �
$$
\left\{\matrix{
 503 & 703 & 765 \cr
 087 & 512 & 677\cr
}\right.,
$$
�������
$$
087\left\{\matrix{
503 & 703 & 765\cr
512 & 677 \cr
}\right.
$$
�����
$$
087\ 503\ \left\{\matrix{
703 & 765\cr
512 & 677\cr
}\right.
$$
�~�.~�. 텎������� ������������ � ��������� �� ������, ����� ����������� 
���� �� ������. ⅑� ������� �������� ������ � ��������� ���������.
\alg �.(䂓�������� �������.) ���� �������� ������������ ������� ���� 
������������� ������ $x_1\le x_2\le\ldots\le x_m$ 
�~$y_1\le y_2 \le \ldots\le y_n$ � ���� ���� 
$z_1\le z_2\le \ldots\le z_{m+n}$.
\st[퀗������ ���������.] 󑒀������ $i\asg 1$, $j\asg 1$, $k\asg 1$.
\st[퀉�� ���������� �������.] 呋� $x_i\le y_j$, �� ������� � 
����~\stp{3}; � ��������� ������ ������� �~\stp{5}.
%%194
\st[⛂���� $x_i$.] 󑒀������ $z_k\asg x_i$,  $k\asg k+1$,  $i\asg i+1$. 
呋�~$i\le m$, �� ������������ � \stp{2}.

\st[⛂���� $y_j, \dots, y_n$.] 󑒀������ 
$(z_k, \ldots, z_{m+n})\asg(y_j, \ldots, y_n)$ � ��������� ������ ���������.

\st[⛂���� $y_j$.] 󑒀������ $z_k\asg y_j$, $k\asg k+1$, $j\asg j+1$.  
呋� $j\le n$, �� ������������ � \stp{2}.
\st[⛂���� $x_i$, \dots, $x_m$.] 󑒀������ 
$(z_k, \ldots, z_{m+n})\asg(x_i, \ldots, x_m)$ � ��������� ������ ���������.
\algend
\picture{���. 29. 񋈟��� $x_1\le \ldots\le x_m$ � $y_1\le\ldots\le y_n$.}

� �.~5.3.2 �� ������, ��� ��� ������� ���������, �� ��������, "��������� 
�� ���������" �������� ������� �� ������������ ���, ���� $m\approx n$. 
(�, ���� $m$ ������� ������ $n$, ����� ����������� ����� ����������� 
��������� ����������, ���� � ����� ������ ��� �������� ������.) ��������~M 
��� ������ ������ ������������� ����� ������� ���������, ������� � 
����� �������� ������ ������������� "�������" $x_{m+1}=y_{n+1}=\infty$ 
� �������������� ����� �������~$\infty$. ������ ���������~M ��. � ���.~2.

�� ����� ������, ����������� ����������~M, �� ��������, 
�������������� $m+n$, ������� ����, ��� �������---����� ������� ������, ��� 
����������. ��� ������ ���������� ����� ������ � ��������, ������ ��� 
����� ������� �������� �� ��� ���, ���� �� ����� ������������ ���� ����. 
򀊎� ������ ����� ������������� ��� �������� ���� ���������� ���������: 
������� ������ �������� � ������������� ����---������� ������ ������� ��� 
$n=1!$ 呋� ����� �������� ������� �������, �� ����� ����������� ������� 
���������� ��������� �� ���, "���������" ��, � ��� ������������ ������� 
�������� � ����� ���� ���������� ��������. � ������������ ����� ������ 
����� �������--- ���� �� ����� ������ �������, ��������������� ��� ����������
%% 195
\picture{򀁋��� 1 񎐒������ ������������ ����������� ��������}
�� ���; �� ��� ��������� 䆎��� ��� 텉����� ��� � 1945~�. (��. \S~5.5).

� �������� �������� ������ ������� � \S~5.4 � ����� � ����������� ������� 
����������, � � ��������� ������ ������������ ���� �������� �� 
���������� � ������� ������ � ������������ ��������.

򀁋���~1 ������������ ���������� ��������, ����� "������ ��������� � 
����� ������", ������� ��� ���������� ��������� ��������� �����, ������� 
����������� ��� ������� ����������, ����������� �������� ���������� �~�.~�.
 � ����������� �������� ���� ����� � ������, �������� � ��������. 
������ ���� ������ ������ � ���������� ������� �� ������ ������ � 
�������. 񋅂� �� ����� ������������ ������� $503$ $703$ $765$, � ������, 
���� ������ ������ ������, ����� ������� $087$ $512$ $677$. 񋈟��� ���� 
���� ������������������� ���� ������� $087$ $503$ $512$ $677$ $703$ $765$, 
������� ���������� ����� � ������~3. 瀒�� ����� $061$ $612$ $908$ � 
������~2 ��������� �~$170$ $509$ $897$, � ��������� $(061$ $170$ $509$ 
$612$ $897$ $908)$ ������������ \emph{������} � ������~3. 퀊����, $154$ 
$275$ $426$ $653$ ��������� � $653$ (���������� �������������� ������, 
��� ��� ����� �������� � ������� ������������), � ��������� ������������ 
�����. 򎗍� ��� �� ������~2 ���������� �� ��������� ����� � ������~1.
 
⅐���������� ������� � ����.~1 �������� ������� ����� ���������. ��� ��� 
���������� "��������� ����", ��� ������� ������� ������� �� �������. � 
�������� ����� ������ ��������� ������������� ��������, ����� ��� �������� 
� ����� ������ �� ����������� ���� � ��� �� ����; ��� �� �������� � 
�����������, ���� �������� ������� ������������, ��� � 
��������� ���������. 򀊎� ����� �� �������� ���������� 
"������������" ��������, ������ ��� �� ���������� �������, ������� 
"�����������" ���������� � �������� �����.

\alg N.(񎐒������ ������������ ����������� ��������.)  ���������� 
������� $R_1$, \dots, $R_N$ ������������ ��� ������� ������, ������ �� 
������� ����� ��������� $N$~�������. 䋟 �������� ��������� ������, 
����������� �� ������ �������,
%%196
����� $R_{N+1}$, \dots, $R_{2N}$, ���� � ���������������� ������~$R_{N+1}$ 
����� � �� ��������� ��������������� �~$R_N$. 퀗������ ���������� ������� 
$R_{N+1}$, \dots, $R_{2N}$ �� ����� ��������. �� ���������� ���������� 
����� ����� �����������: $K_1\le\ldots\le K_N$.
\picture{���. 30.  񎐒������ ��������.}

\st[퀗������ ���������.] 󑒀������ $s\asg0$. ( $s=0$ �� ����� 
���������� ������ �� ������� $(R_1, \ldots, R_N)$ � ������� $(R_{N+1}, 
\ldots, R_{2N})$; ��� $s=1$ ������� �� ��������� � ���������� ���������� ������.)

\st[������� � ���������.] 呋� $s=0$, �� ���������� $i\asg1$, 
$j\asg N$, $k\asg N+1$, $l\asg2N$; ���� $s=1$, �� ���������� $i\asg N+1$, 
$j\asg2N$, $k\asg1$, $l\asg N$. (������� $i$, $j$, $k$, $l$ ��������� 
������� ������� �� ������� "������", ������ ���� ������, � � �������� 
"������", ���� ���� ������.) 󑒀������ $d\asg 1$, $f\asg1$. 
(�������~$d$ ���������� ������� ����������� ������, $f$ 
��������������� ������~0, ���� ���������� ���������� ���������.)

\st[񐀂����� $K_i:K_j$] 呋� $K_i>K_j$, ������� � ����~\stp{8}. 呋� 
$i=j$, ���������� $P_k\asg R_i$ � ������� � ���� \stp{13}.

\st[������ $R_i$.] (���� \stp{4}--\stp{7} ���������� ����� 
M3--M4 ���������~M.) 󑒀������ $R_k\asg R_i$, $k\asg k+d$.

\st[񒓏����� ����?] 󂅋����� $i$ ��~1. 瀒��, ���� $K_{i-1}\le K_i$, 
������������ � ���� \stp{3}.
\st [������ $R_j$.] 󑒀������ $R_k\asg R_j$, 
$k\asg k+d$.
\st[񒓏����� ����?] 󌅍����� $j$ ��~1. 瀒��, ���� $K_{j+1}\le K_j$, 
������������ � ���� \stp{6}; � ��������� ������ ������� � ���� \stp{12}.

%% 197
\st[������ $R_j$.] (���� \stp{8}--\stp{11} ����������� �� ��������� � 
�����~\stp{4}--\stp{7}.) 󑒀������ $R_k\asg R_j$, $k\asg k+d$.

\st[񒓏����� ����?] 󌅍����� $j$ �� 1. 瀒��, ���� 
$K_{j+1}\le K_j$, ������������ � ���� \stp{3}.

\st[������ $R_i$.] 󑒀������~$R_k\asg R_i$, $k\asg k+d$.

\st[񒓏����� ����?] 󂅋����� $i$ ��~$1$. 瀒��, ���� 
$K_{i-1}\le K_i$, ������������ � ���� \stp{10}.

\st[��������� �����������.] 󑒀������ $f\asg0$, $d\asg-d$ � 
�������������� $k\xchg l$. ⎇��������� � ���� \stp{3}.

\st[��������� ��������.] 呋� $f=0$, �� ���������� $s\asg 1-s$ � 
������������ �~\stp{2}. � ��������� ������ ���������� ���������; ���� 
$s=0$, �� ���������� 
$(R_1,~\ldots, R_N)\asg(R_{N+1}, \ldots, R_{2N})$. (呋� ��������� ����� 
�������� � �������~$(R_{N+1}, \ldots, R_{2N})$,  �� ��������� ����������� �������������.)
\algend

� ���� ��������� ���� ���� ��������� ��������, ������� ����������� � ���.~5.

瀏�������������� ��������~N ��� ������~\MIX\ ��������, �� �������� 
�������� � ��� ��������� ����� �������� � ��� ���������� ���� ���������. 
呋� ���� �������, �� � ��� �����
${1\over2}N$ ������������ ��������, ��� ��� $K_i>K_{i+1}$ � 
������������~$1\over2$; ��������� ���������� � ����� �������� ��� 
��������� �������� �������������� ���� �������� � �.~5.1.3.  ������ 
��������� ����� �������� ����������� ����� (�� ����������� ��������� 
�������, �����, ��� ��������, ��������� � ���.~6). 򀊈� �������, ����� 
����������, ��� �������, ���������� �����~$\log_2 N$.  ������ ��������� 
�� ������ ���������� ��� $N$~�������, �, ��� �������� � ���.~2, �\'������ 
����� ������� ������������� � �����~N3, N4, N5, N8, 
N9. 呋� �������, ��� ������ ����� ����������� � ����� ������������, 
�� �����, ������������� �� ���������� �����, ����� 
���������������� ��������� �������:
\ctable{
\hfill# & # & #\cr
\hbox{���}\hfill&\hfill\hbox{�����}\hfill&\hfill\hbox{␅��}\hfill\cr
$\matrix{N3\cr}$ & $\matrix{|CMPA|, |JG|, |JE|\cr}$ & $\matrix{3.5u}$ \cr
$\hbox{눁�}\left\{
\matrix{
N4\cr
N5\cr
}\right.$
& 
$
\matrix{
|STA|, |INC| \hfill\cr
|INC|, |LDA|, |CMPA|, |JGE|\hfill \cr
}
$
&
$\matrix{
\phantom{0.}3u\cr
\phantom{0.}6u\cr
}$
\cr 
$\hbox{눁�}\left\{
\matrix{
N8 \cr
N9 \cr
}\right.$
&
$\matrix{
|STX|, |INC|\hfill \cr
|DEC|, |LDX|, |CMPX|, |JGE|\hfill\cr
}$
&
$\matrix{
\phantom{0.}3u\cr
\phantom{0.}6u\cr
}$
\cr
}
򀊈� �������, ��� ������ ��������� �� ������ ������ ������������� 
$12.5$~������ �������, � ����� ����� ������ �������������� ������������ 
�~$12.5N\log_2 N$ ��� � �������, ��� � � ��������� ������. ��� ��������� 
������� ���������� � �� ��������� ����� ������� ������ ������������� 
����������, ����� ��������� ����� ������� ������ ������, ��� ��� 
��������������� ����� ������ ���������~5.2.3H ����� $16N\log_2 N$.

%% 198

� ���������~N ������� ����� ��������� ��������� ������������ 
"����������� ����". 򀊎� ������ �������� ��� ��������� �������������, 
��� �������� ����� � ������������� ������������� \emph{��� ����������} 
������������ ��������� ����� �������������� ����� ������, �� ��� ���� 
����������� �������� ���� ����������. ⌅��� �������� �������� ���� ����� 
������������� ���������� ����� ��������, ������, ��� ��� 
������� ��������� ����� ����� �����~$1$, ����� ������� ��������� 
��� ������� (�����, ��������, ����������) ����� ����� 2, \dots, 
����� $k\hbox{-�o}$ ��������� ��� ������� (�����, ��������, 
����������) ����� �����~$2^k$. � ������� �� "�������������" ������� � 
���������~N ����� ������ ���������� \emph{�������} ����������� ��������.

�������� �������� ������������ ������� ����� ���������� ��������~N---�� 
�����������, �� ��������, ��� �� ����-������;
��� �� ����� ������ ���������� ���������� ���� �� �����, � ������� ����� 
�������� ���� �������� �������.

\alg S.(񎐒������ ������� ����������� ��������.) ꀊ � � ���������~N, ��� 
���������� ������� $R_1$, \dots, $R_N$ ������������ ��� ������� ������.

\st[퀗������ ���������.] 󑒀������ $s\asg0$, $p\asg1$. 
(񌛑� ����������~$s$, $i$, $j$, $k$, $l$, $d$ ��. � ���������~N. 焅�� 
$p$---������ ������������ ��������, ������� ����� ��������� �� ����� 
�������� ���������; $q$ �~$r$---���������� �������� ��������� � ��������.)

\st[������� � ���������.] 呋� $s=0$, �� ���������� $i\asg1$, 
$j\asg N$, $k\asg N$, $l\asg2N+1$; ���� $s=1$, �� ���������� $i\asg N+1$, 
$j\asg2N$, $k\asg0$, $l\asg N+1$. 瀒�� ���������� $d\asg1$, $q\asg p$, 
$r\asg p$.

\st[񐀂����� $K_i:K_j$.] 呋� $K_i>K_j$, �� ������� � ����~\stp{8}.

\st[������ $R_i$] 󑒀������ $k\asg k+d$, $R_k\asg R_i$.

\st[ꎍ�� �������?] 󑒀������ $i\asg i+1$, $q\asg q-1$. 呋� $q > 0$, �� 
������������ � ����~\stp{3}.

\st[������ $R_j$.] 󑒀������ $k\asg k+d$. 瀒��, ���� $k=l$, ������� � 
����~\stp{13}; � ��������� ������ ����������
$R_k\asg R_j$.

\st[ꎍ�� �������?] 󑒀������ $j\asg j-1$, $r\asg r-1$. 
呋�~$r>0$, ������������ � ���� \stp{6}; � ��������� ������ �������
� ���� \stp{12}.

\st [������ $R_j$.] 󑒀������ $k\asg k+d$, $R_k\asg R_j$ 

\st[ꎍ�� �������?] 󑒀������ $j\asg j-1$, $r\asg r-1$. 
呋�~$r> 0$, �� ������������ � ����~\stp{3}. 
\st[������ $R_i$.] 󑒀������ $k\asg k+d$. 瀒��, ���� $k=l$,
������� � ����~\stp{13}; � ��������� ������ ����������
$R_k\asg R_i$.
%% 199
\st[ꎍ�� �������?] 󑒀������ $i\asg i+1$, $q\asg q-1$. 呋� $q > 0$, �� 
������������ � ���� \stp{10}.

\st[��������� �����������.] 󑒀������ $q\asg p$, $r\asg p$, $d\asg -d$ 
� �������������� $k\xchg l$. ⎇��������� � ���� \stp{3}.

\st[��������� ��������.] 󑒀������ $p\asg p+p$. 呋� $p<N$, �� 
���������� $s\asg 1-s$ � ������������ �~\stp{2}. � ��������� ������ 
���������� ���������; ���� $s=0$, �� ����������
$$
(R_1, \ldots, R_n)\asg (R_{N+1}, \ldots, R_{2N}).
$$
(텇������� �� ������������� ��������� ����� ��������� ����������� ����� 
��������� ����� � ������ �����, ����� ��������~$\ceil{\log_2 N}$ �������. 
� ��� ����� ������� ����������� ��������� ���������������� �����, � 
�����������, ��� �������, �� ���������.)
\algend

{\def|{\mskip\thinmuskip\vert\hidewidth}
 \catcode`\!=\active
 \def!{\mskip\thinmuskip\vrule width 0.5mm\hidewidth}
\htable{򀁋��� 2}%
{񎐒������ ������� ����������� ��������}
{\bskip$#$\bskip&&\bskip$#$\bskip\cr
503|& 087|& 512|& 061|& 908|& 170|& 897|& 275!& 653|& 426|& 154|& 509|& 612|& 677|& 765|& 703\cr
503 & 703|& 512 & 677|& 509 & 908|& 426 & 897!& 653 & 275 & 170 & 154|& 612 & 061|& 765 & 087\cr
087 & 503 & 703 & 765|& 154 & 170 & 509 & 908!& 897 & 653 & 426 & 275|& 677 & 612 & 512 & 061\cr
061 & 087 & 503 & 512 & 612 & 677 & 703 & 765!& 908 & 897 & 653 & 509 & 426 & 275 & 170 & 154\cr
061 & 087 & 154 & 170 & 275 & 426 & 503 & 509 & 512 & 612 & 653 & 677 & 703 & 765 & 897 & 908\cr
}
}

��� ������ ��������� ��. � ����.~2. 䎂����� �����������, ��� ���� 
����� ���������� � �����, ����� $N$ �� �������� ��������~2; ��������� 
������� �� ��� ����� ����� $2^k$, ��� �� ����� ������� ����� ��� 
���������������� �� ������ ����� ���������� �� �������������! (�. 
���.~8.) ����� �������� ���� �������� ����������� ����������~$q$ �~$r$ 
� ��������� �� ��������� ����. ዀ������ ����� ����� ������ �� ������ 
\MIX\ �������������� ������������ � $11N\log_2 N$~��������, ��� ��������� 
����� ��������, �������� ��� ������� �������� � ���������~N.

� �������� ����� ����� ������������� ��������~S � �������� ���������; 
������ ������ ������� ���������� ���������~S ����� �������� ��������� 
������������� ������, ������, �� 16~���������, �������� ����� ������� 
�������� �������������� ��������������� ��������, ��������� �� �������� 
�������� ������. ꀊ �� ��� ������ � ������ ������� ����������, 
����� �������������� ������� �� ������/�� ��������������� ����� ������, �� 
���� ��� �� �����, ������� ������.

���������� ������ ���������~N �~S � ����� ������ �������� ������. ��� 
��� ���������� ������ ��� $2N$, � �� ��� $N$
%% 200
~�������? ���� ������������ ������: �� �������� � �������� �������� 
����������� ������� (��� "������� ������" � ��� "�������� ������" � ������ 
���������); ��� ���� ��� ������ ���� ��������������� �������������� 
������� �� ���������� ����������� �������� "���������� �����", 
������������� � (�.~2.2.2. � � ����� ������ ������� �������� ������ �� 
������������, � ����� ���������� ����������� ���������� ����, ��� � 
����������������, ��� ����� ������� ������� ��������� �� ��������������� 
\emph{���������} �������������� ������. 呋� � ������ �� $N$~������� 
�������� ���� �����, �� ��� ����������� ����� ���������, ��������� 
����������� �������, ������� ���������� ������� ����������� �� ������� � 
������ �� ���������� ���� ������. 䎁������� $N$~����� �����, ��� 
�������, ��������, ��� ���������� ������������ ������ ��� ��� 
$N$~�������, � ����������� �� ����������� �������, �� ����� 
����� ���������� � �����. 蒀�, ��� ����� ����������� ��������, �������� 
����������.

\alg L.(񎐒������ ����������� ������� �������.) �����������, ��� 
������ $R_1$, \dots, $R_N$ �������� ����� $K_1$,~\dots, $K_N$ � "���� 
�����" $L_1$,~\dots, $L_N$, � ������� ����� ��������� ����� ��~$-(N+1)$ 
��~$(N+1)$. � ������ � � ����� ����� ������� ������������� ������~$R_0$ 
�~$R_{N+1}$ � ������ �����~$L_0$ �~$L_{N+1}$ ���� �������� ���������� 
������� ������������� ���� ����� ����� �������, ��� ������ ����������� 
���������� � ������������ �������. �� ���������� ���������� $L_0$ 
��������� �� ������ � ���������� ������; ��� $1\le k \le N$ �����~$L_k$ 
��������� �� ������, ��������� ��~$R_k$, � ���� $R_k$---������ � 
���������� ������, �� $L_k=0$. (�. ������� (5.2.1--9).)

� �������� ���������� ����� ��������� ������~$R_0$ �~$R_{N+1}$ ������ 
"��������" ���� �������� �������, ��������� ������� � ������ ������ 
���������. ���������� ����� �������� ����� ���������, � ������� 
��������, ��� �� ����������; ������� ����� �������� ����� ����� ������. 
�����������, ��� $N\ge 2$.

����� "$\abs{L_s}\asg p$" ���������� �������� "��������� $L_s$ 
��������~$p$ ���~$-p$, �������� ������� ���� $L_s$". 򀊀� 
�������� ����� ����������� �� ������ \MIX, ��, � ���������, ��� �� ��� ��� 
����������� ���. 텒����� �������� ��������, ����� �������� ����� �� 
����������� ����� � ��� ����������� ������ �����.

\st[�������� ��� ������.] 󑒀������ $L_0\asg1$, $L_{N+1}\asg2$,
 $L_i\asg -(i+2)$ ���~$l\le i\le N-2$ �~$L_{N-1}\asg L_N\asg0$. (� 
������� ��� ������, ���������� �������������� ������~$R_1$, $R_3$, $R_5$,
~\dots{} �~$R_2$, $R_4$, $R_6$,~\dots{}; ������������� ����� ������� � ���,
 ��� ������ ������������� "���������" ������� ����� ���� �� ������ 
��������. 䐓��� ������ ��������� ���� ���,
%% 201
�������� ������ �� ���������������, ������� ����� �������������� � 
�������� ������, ��. � ���.~12.)

\st[퀗��� ����� ��������.] 󑒀������ $s\asg 0$, $t\asg N+1$, $p\asg L_s$,
 $q\asg L_t$. 呋� $q=0$, �� ������ ��������� ���������. ( ������ 
��������� $p$ �~$q$ ��������� �� �������, ������� ������������ �������; 
$s$ ������ ��������� �� ��������� ������������ ������ �������� ���������,
 a $t$---�� ����� ������ ��� ����������� ���������.)

\st[񐀂���� $K_p:K_q$.] 呋� $K_p>K_q$, �� ������� �~\stp{6}.

\st[������� $p$.] 󑒀������ $\abs{L_s}\asg p$, $s\asg p$, $p\asg L_p$. 
呋� $p>0$, �� ������������ �~\stp{3}.

\st[瀊������ ���������.] 󑒀������ $L_s\asg q$, $s\asg t$. 
瀒�� ���������� $t\asg q$ �~$q\asg L_q$ ���� ��� ����� ���, ���� 
�� ������ $q\le 0$, ����� ���� ������� �~\stp{8}.

\st[������� $q$.] (���� \stp{6} �~\stp{7} ����������� �� 
��������� �~\stp{4} �~\stp{5}.) 󑒀������ $\abs{L_s}\asg q$, $s\asg q$, 
$q\asg L_q$. 呋�~$q>0$, �� ������������ �~\stp{3}.

\st[瀊������ ���������.] 󑒀������ $L_s\asg p$, $s\asg t$. 
瀒�� ���������� $t\asg p$ �~$p\asg L_p$ ���� ��� ����� ���, ���� �� ������~$p>0$.

\st[ꎍ�� ���������?] (� ����� ������� $p\le 0$ �~$q\le 0$, ��� ��� ��� 
��������� ������������ �� ����� ��������������� ����������.) 
󑒀������~$p\asg -p$,  $q\asg -q$. 呋� $q=0$, 
�� ����������~$\abs{L_s}\asg p$, $\abs{L_t}\asg 0$, � ������������ 
�~\stp{2}; � ��������� ������ ������������ �~\stp{3}.
\algend

��� ������ ����� ��������� �������� � ����.~3, � ������� �������� 
����� � ������� ���������� ����~L2. � ��������� ������ ��������� �����, 
��������� ������� �� ���.~5.2--12, �������������� ������ ���, ����� �� 
����� ���� �����������. 쎆�� �������� ���������� �������� ����� �������� 
������� � ��������� ����������� ����������� (��. �������� 2.2.4�).
{\catcode`\!=\active\def!#1.{\omit\hfill$#1$\hfill}
\htable{򀁋��� 3}%
{񎐒������ ����������� ������� �������}%
{\bskip$#$\bskip&&\hfill$#$\bskip\cr
j   &!0.& !1.& !2.& !3.& !4.& !5.& !6.& !7.& !8.& !9.&!10.&!11.&!12.&!13.&!14.&!15.&!16.&!17.\cr
K_i & - & 503& 087& 512& 061& 908& 170& 897& 275& 653& 426& 154& 509& 612& 677& 765& 703&  -\cr
L_j & 1 &  -3&  -4&  -5&  -6&  -7&  -8&  -9& -10& -11& -12& -13& -14& -15& -16&   0&   0&  2\cr
L_j & 2 &  -6&   1&  -8&   3& -10&   5& -11&   7& -13&   9&  12& -16&  14&   0&   0&  15&  4\cr
L_j & 4 &   3&   1& -11&   2& -13&   8&   5&   7&   0&  12&  10&   9&  14&  16&   0&  15&  6\cr
L_j & 4 &   3&   6&   7&   2&   0&   8&   5&   1&  14&  12&  10&  13&   9&  16&   0&  15& 11\cr
L_j & 4 &  12&  11&  13&   2&   0&   8&   5&  10&  14&   1&   6&   3&   9&  16&   7&  15&  0\cr
}
}

퀏���� ������ \MIX-��������� ��� ���������~L, ����� ��������, ����� �� 
������� ����������� �������� � ����� ������ �������, ��� � � ����� ������ ������������?
%%202
\prog L.(񎐒������ ����������� ������� �������.) 䋟 �������� 
��������������, ��� ������ �������� ���� �����, ������ $L_j$ �������� � 
���� $(0:2)$, � $K_j$---� ���� $(3:5)$ ������ $|INPUT|+j$;
�������� ���������: $|rI1|\equiv p$, $|rI2|\equiv q$, $|rI3|\equiv s$, 
$|rI4|\equiv t$ $|rA|\equiv R_q$; $N\ge 2$.
\code
L    & EQU  & 0:2          &       & �������� ���� �����.
ABSL & EQU  & 1:2
KEY  & EQU  & 3:5
START& ENT1 & N-2          & 1     & L1. �������� ��� ������.
     & ENNA & 2,1          & N-2
     & STA  & INPUT,1(L)   & N-2   & $L_i\asg -(i+2)$.
     & DEC1 & 1            & N-2
     & J1P  & *-3          & N-2   & $N-2\ge i>0$.
     & ENTA & 1            & 1
     & STA  & INPUT(L)     & 1     & $L_0\asg 1$.
     & ENTA & 2            & 1
     & STA  & INPUT+N+1(L) & 1     & $L_{N+1}\asg2$.
     & STZ  & INPUT+ N-1(L)& 1     & $L_{N-1}\asg 0$.
     & STZ  & INPUT +N(L)  & 1     & $L_N\asg 0$.
     & JMP  & L2           & 1     & � L2.
L3Q  & LDA  & INPUT,2      & C''+B'& L3. 񐀂���� $K_p:K_q$.
L3P  & CMPA & INPUT,1(KEY) & C
     & JL   & L6           & C     & � L6, ���� $K_q<K_p$.
L4   & ST1  & INPUT,3(ABSL)& C'    & L4. �������~$p$. $\abs{L_s}\asg p$.
     & ENT3 & 0,1          & C'    & $s-p$.
     & LD1  & INPUT, 1(L)  & C'    & $p\asg L_p$
     & J1P  & L3P          & C'    & � L3, ����~$p>0$.
L5   & ST2  & INPUT,3(L)   & B'    & L5. 瀊������ ���������. $L_s\asg q$.
     & ENT3 & 0,4          & B'    & $s\asg t$.
     & ENT4 & 0,2          & D'    & $t\asg q$.
     & LD2  & INPUT,2(L)   & D'    & $q\asg L_q$.
     & J2P  & *-2          & D'    & ������, ���� $q>0$.
     & JMP  & L8           & B'    & � L8
L6   & ST2  & INPUT,3(ABSL)& C''   & L6. �������~$q$. $\abs{L_s}\asg q$.
     & ENT3 & 0,2          & C''   & $s\asg q$.
     & LD2  & INPUT,2(L)   & C''   & $q\asg L_q$.
     & J2P  & L3Q          & C''   & � L3, ����~$q>0$.
L7   & ST1  & INPUT,3(L)   & B''   & L7. 瀊������ ���������. $L_s\asg p$.
     & ENT3 & 0,4          & B''   & $s\asg t$.
     & ENT4 & 0,1          & D''   & $t\asg p$.
     & LD1  & INPUT, 1(L)  & D''   & $p\asg L_p$.
     & J1P  & *-2          & D''   & ������, ����~$p>0$.
L8   & ENN1 & 0,1          & B     & L8. ꎍ�� ���������? $p\asg -p$.
     & ENN2 & 0,2          & B     & $q\asg -q$.
     & J2NZ & L3Q          & B     & � L3, ���� $q\ne0$.
     & ST1  & INPUT,3(ABSL)& A     & $\abs{L_s}\asg p$.
     & STZ  & INPUT,4(ABSL)& A     & $\abs{L_t}\asg0$.
%%203
L2   & ENT3 & 0            & A+1   & L2. 퀗��� ����� ��������, $s\asg0$.
     & ENT4 & N+1          & A+1   & $t\asg N+1$.
     & LD1  & INPUT (L)    & A+1   & $p\asg L_s$.
     & LD2  & INPUT+N+1(L) & A+1   & $q\asg L_t$.
     & J2NZ & L3Q          & A+1   & � L3, ���� $q \ne 0$.
\endcode

␅�� ������ ���� ��������� ����� ������� ��� ������ �������, �������� �� 
��� �� ��� ������������ (��. ���.~13, 14);
� ������� ��� ����� �������������� $(10N \log_2 N+4.92N)$~������ � 
��������� ����������� ����������� ������� $\sqrt{N}$. � ���.~15 ��������, 
��� �� ���� ���������� ��������� ��������� ����� ��������� ����� �������� 
��~$9N\log_2N$.

蒀�, � ������ ����������� ������� ��������� ������������� ������ ����� 
���������� ������������ ����� ���������������� ��������������: ��������� 
������ ������, � ��������� �������� �� 10--20\% �������. ����������� 
��������� ������������ �.~�.~Ⓞ����� [{\sl IBM Systems J.\/}, {\bf 8} 
(1969), 189--203] � �.~�.~Ⓞ����� [{\sl 񎒐. J.\/}, {\bf 13} (1970), 110--111].

\excercises
\ex[20] ����� ��������~M �� \emph{$k\hbox{-�������}$ �������} �������� 
������ $x_{i1}\le \ldots\le x_{im_i}$ ��� $i=1,$ 2, \dots, $k$.

\ex[�24] 񗈒��, ��� ��� $\perm{m+n}{m}$ ��������� ������������ 
$m$~���������~$x$ ����� $n$~���������~$y$ �������������, ������� 
�������������� �������� � ����������� ���������� ����� ���������� ����~M2 
� ���������~M. ���� ����� ������������ � ����������� �������� ���� ��������?

\rex[20] \exhead(臌������.) 䀍� ������ $R_1$,~\dots, $R_M$ �~$R'_1$,
~\dots, $R'_N$, ����� ������� �������� � �����������, 
�.~�.~$K_1<\ldots<K_M$ � $K'_1<\ldots<K'_N$. 
ꀊ ����� �������� ��������~M, ����� � 
���������� ������� ��������� ����, � ������� ����������� ������~$R_i$ 
������� �����, ���� �� ������ ����� ���� ���� ������ � ����� �� ������?

\ex[21] � ������ ��������, ��� ���������� �������� ����� ������������� ��� 
��������� ���������� ���������. �����, ��� ����� ������� 
����� ���������������� ��������� � � ������ �� ������ (�������������� � 
�������� ����������� ���.~23).

\rex[21] 䎊�����, ��� � �����~N6 �~N10 ����������~$i$ �~$j$ �� ����� 
���� �����. (���� � ���� ����� �������� �� ������ ���������� �������� �~N13 �������������.)

\ex[22] 퀉���� ����� ������������ $K_1 K_2 \ldots K_{16}$ 
���������~$\{1, 2, \ldots, 16\}$, ���
$$
\displaylines{
  K_2>K_3, K_4>K_5, K_6>K_7, K_8>K_9,\cr
  K_{10}<K_{11}, K_{12}<K_{13}, K_{14}<K_{15},\cr
}
$$
������� ��� �� ����� ����� ������������� ��� ������ ���������~N ����� 
�� ��� ���������. (� ��� � ������� ������������ ������� �� ����� 
������ ��������, �� �� ����� �� �������, ��� ����� ������� ��������� 
��������� �� ������� ���� ������ �������, ����� ������� ���������---��� 
�������, � ����������, ��� �������, �� ���������� ������ ��������� 
�������� ���������. ꀊ�� �� ������� ����� �������� ����� ����� �����������?)

%%204
\ex[16] 퀉���� ������ �������, ���������� ����� ���������� ���������~S 
� ���� ������� ��~N.

\ex[22] �����������, ��� �� ����� ������ ��������� ����������~$q$ 
�~$r$� ������������ ����� �������� ������ ��������, �������������� � 
������ ������; � ������ ������ -���~$q$, ��� �~$r$ ��������������� 
�������~$p$, � �� ����� ��� ������� �� ������ ����� ����� �����. ��� �� 
�������� ��� �� ����� �������� ���������?

\ex [24] 퀏����� \MIX-��������� ��� ���������~S. ⛐����� 
������� ���������� ������ ������� ����� ��������, �������� $A$, $B'$, 
$B''$, $C'$, \dots � ���������~L.

\ex[25] (�. �. ᅋ�.) �����, ��� ������� ����������� ������� ������ � 
��������������� �������������� ���������� ����� ���������, ���� ����� 
${3\over2}N$~����� ������, � �� $2N$, ��� � ���������~S.

\ex[21] ߂������ �� ��������~L ���������� "����������" ����������?

\rex[22] 臌����� ���~L1 ���������~L ���, ����� ����������� ������� ����� 
"������������", �������� ������ �� ������� ������������ �������� � 
�������� �����. (� ���������, ���� �������� ������ ��� �����������, 
�� ���~L2 �������� ������ ��������� ����� �� ����� ���������� 
����������� ���� ����~L1.)

\rex[�34] ������������ ������� ����� ������ ���������~L ������� ����, 
��� �� ������������� ������ ��������� � ���� �����. 䀉�� ���������� 
���������~$A$, $B$, $B'$, \dots � ���������, ��� ��������� �� ������ 
������� ��������. 񊎋��� ������� �������� ���������~L �� ���������� 
16~����� � ����.~3?

\ex[�24] �� �������� ������������� �����~$N$---��� 
$2^{e_1}+2^{e_2}+\cdots+2^{e_t}$, ��� $e_1>e_2>\ldots>e_t\ge0$, $t\ge1$. 
䎊�����, ��� ������������ ����� ���������
������, ����������� ����������~L, ����� 
$1-2^{e_t}+\sum{1\le k\le t}(e_k+k-1)2^{e_k}$.

\ex[20] 呋� ��������������� ������� ������ ���������~L, �� �����������, 
��� � ��� ������ ����������� ������ ��������; �������� � �������� 
������� �� ����� ������������ $\abs{L_s}\asg p$, $\abs{L_s}\asg q$ � 
�����~L4 �~L6, ��������� �� ����� $L_s=p$ (���~$q$) ������ ���, ����� 
������������ �� ����~L4 (��� L6) �~L3. ꀊ �������� ���������~L, 
����������� �� ����  ������ ������������?

\ex[28] ������������ �������� ������� �������, �������� ���������~L, �� 
���������� �� ����������� �������.

\ex[20] (�.~쀊-ꀐ��.) �� �������� ������������� �����~$N$ ����� ��, 
��� � ���.~14, � �����������, ��� ���� $N$~�������, �������������� � $t$
������������� ���������, ������� ������� �������������� 
$2^{e_1}$, $2^{e_2}$, \dots, $2^{e_t}$.
�����, ��� ����� ��������� ����� ��������� ��� ���������� 
$(N+1)\hbox{-�}$ ������ �~$N\asg N+1$. (������� �������� ����� ������� 
"�����������" ����������� ��������.)

\ex[40] (�.~�.~ꐎ����.) 쎆�� �� ������������� ���� �� $N$~�������,
 ���������� ����� ��� �������:
$$
K_1\le\ldots\le K_M\quad\hbox{�}\quad K_{M+1}\le\ldots\le K_N,
$$
� $O(N)$ �������� � ������ � ������������ ��������, \emph{��������� ���� 
��������� �������������� ������������ ������ �������������� �������}, �� 
���������� ��~$M$ �~$N$? (⑅ ��������� �������, ��������� � ���� ������,
 ���������� �������������� ������������ ������, ����������������~$N$.)

\ex[26] ���������� ��������������� ������� � $n$~"�������", ��� �������� 
�� ���.~31 ��� $n=5$; ����� ������� ����� ��������� ��������� � 
���������� ���������� � $n$~�����������. � ���.~�~2.2.1--2 ��~2.2.1--5 
�� ����������� �������� � ����� ������. � ������, ��� ���� � ������� 
����� ��������� $N$~�������, �� ����� ����� ��������� ������������ 
��������� ���������� �� $N$~������������ ������������ ���� �������.
%% 205

��������, ��� � ������� � $n$~������� ������ ��������� 
$2^n$~�������. 䎊�����, ��� ��� ������ ���������� ������������������ 
�������� ����� \emph{����� ��������} ����� ��~$2^n!$ ������������ 
������������ ���� �������. (ꀆ��� ���� ���������� �����, � ��� 
������������� � ���� ����� ��������� ��� ������).

\ex[47] � ������������ ���.~2.2.1--4 ��� ������ ��������� � 
$n$~������� ����� �������� �� ����� $a^n_N$~������������ $N$~���������; 
�������������, ���
\picture{���. 31.態������������ ������� � ����� "�������".}
��������� ���� $N!$~������������ ��������� �� ����� $\log N!/\log 
a_N\approx \log_4 N$~������. � ���.~19 ��������, ��� ����� �� ����� 
$\ceil{\log_2 N}$~������. ꀊ��� �������� �������� ����� ������������ 
����� ������ ��� $N\to\infty$?

\ex[23] (�.~�.~񌈒.) ������, ��� ����� �������� ��������~L, ����� ��, 
������ ����������, �������� ����� ����� \emph{��������} � �������� ������������.

\subsubchap{�������������� ����������} % 5.2.5
� �������� ������ � ����������� ������ ������� ����������, �������, ��� 
�������� � �.~5.4.7, �� ��������, ����� \emph{��������������} �������. 
���������, �������� � �������������� �������������, ������ �������� 
����������� ���������, ����������� � ������� ��� ���������� ���� � 
���������� �� ��������� ���� ������; �� �� ���� ����� ������������ � 
��� ����������������.  ������������ ��� ���������� "����������� 
����������", "�������� ����������" ��� "��������� ����������".

��������, ��� ����� ������������� ������ �� 52~��������� ����. 
������ ������������ �� ����������� (�����������) ���� � �����
$$
�<2<3<4<5<6<7<8<9<10<�<�<�,
$$
� ����� �� �����
$$
\clubsuit<\diamondsuit<\heartsuit<\spadesuit
$$
� ����� ������������ ������, ���� ���� (i)~��� ������ �� �����, ���� 
(ii)~����� ����� ���� ���������, �� ��� ������
%%206
�� �����������. (��� ������� ������ \emph{�������������������} 
������������ �� ��������� ������������� ��� ���������; ��.~�~���.~5--2.) 
򀊈� �������,
$$
�\clubsuit<2\clubsuit<\cdots<�\clubsuit<
�\diamondsuit<\cdots<�\spadesuit< �\spadesuit
$$

� ����� �� ������������� ����� ����� �� ������������� ����� �������; ����,
 ��� �������, ���������� ��������, �� ���� ����������� �������� 
����������� ����������. 呒�������� ������������� ����� ������� �� �� 
�����, �������� �� � ������ ������, � ����� ������������� ����� ������ 
������ ������ �� ��� ���, ���� ��� �� ����� ����������� �� �����������.

� ���������� ����� ������� ������! 񍀗��� ��������� ����� � 13~������ 
������� �������� ����� �� �� �����������. 瀒�� ������� ��� ������ ������: 
����� ����, ����� ������, ������ � �. �. � ������ ������ (������� �������� 
�����). �������� ������ ��������� ����� � ����� ���������, �� 
���� ��� � ������ ������ �� �����. 񋎆�� ������ ���������� ������ ���, 
����� ����� ���� �����, ����� �����, ����� � ����, ������� ������������� 
������ ����.

� �� ���� ������� � ��� ���������� �������� � ��������� ������. ��� �� 
��� ���������? ��� ��� (� ����� ������� � ���������� �������), ���� 
��� ����� ��� ��������� �������� ������ � ������ ������, �� ��� ����� 
������ �����, ��� ��� ����� � ������� ������ ������. 呋� �� ����� 
����� �����, �� ��� ��� ��������� � ������ ������� ��������� 
��������������� ����������. 荀�� ������, ��� ������ �������� � ������ 
�� ������� ������ ����� ����� ����������� � ������������ �������. ��� 
�������������� ����� �������� � ��������, ��� ����� �������� ����� 
������������� ����� ��������� � ������������������ �������������; 
����������� ��. � ���.~5--2 (� ������ �����).

򎋜�� ��� ��������� ����� ���������� ����� �� ��������, � �� ����, ��� �� 
������ ���������, ��� �� ��� ������. � ������� �� 19~��������� ��� 
��������� "The Inventory Simplified", �������������� ���������� ����� IBM 
Tabulating Machines Company � 1923~�., ����������� ���������� �������� 
����� ���������� ���� ������������ �� �������������� ������. ��, 
��������, ����� ����������� ��� �����, �������� �������������� � 
��������~1--10 � � ��������~23--25, � ��������� ����� ����� ������������ 
��� �������� ����� ����. 򎃄� ������� ����� ������������� ����� �� 
�������~25 � ����� ��� ������ ������-������������� ������ �������� $a_1$, 
$a_2$,~\dots $a_9$, ��� $a_k$---����� ����� �� ������� 1--10 �� ���� ���������, 
%%207
�� ������� � �������~25 ������� �����~$k$. 瀒�� ����� ������������� 
����� �� �������~24 � ����� ����������� ����� $b_1$, $b_2$,~\dots, $b_9$, 
� ����� �� �������~23, ������� ��������~$c_1$, $c_2$,~\dots, $c_9$. 녃�� 
������, ��� ������� ����� ������������ �����
$$
a_1+2a_2+\cdots+9a_9+10b_1+20b_2+\cdots+90b_9+
100c_1+200c_2+\cdots+900c_9.
$$
򀊎� �������������� ����� ������������� ������������ ������� �������� � 
���� ����������� ���������� "�������-��-�������-�����", ��� ���, 
��-��������, ��� ������� ����� �������� ���������� ���� �����. ��� 
�������������� ������ �� ���� ����� ���������� � ������ ������ 
�.~�.~ꎌ��, ����������� ���������� ��������������� ������������ 
[Transactions of the Office Machinery Users' Assoc., Ltd. (1929), 25--37,
 �������� ���. 28].

����� ��������� ����������� ���������� � ������� ���, ���������� ������, 
��� ������������ ������. �� ������� $M$~������; ����� ���� �� �������� 
$M$~�������� ������ � ���������� ������ �������� ������ � 
��������������� �������. � ��� ������� ��� �� �������������, ������ ��� � 
������ ������� ������ ���� ���������� ����� ��� �������� $N$~���������, 
� ����� ����������� ������������ ��� $(M+1)N$~�������. 򀊀� ���������� 
����������� � ������ ���������� �����������  ������������� ������������ �� 
���������� ����������� ���������� �� �������������� �������, ���� 
X.~񜞂��� [��������� ������, M.I.�. Digital Computer Laboratory 
Report R-232 (Cambridge Mass: 1954), 25--28] �� �������, ��� ���� 
�� ������� ����� ��������, ���� � ������������ ������������ ����� ��� 
$2N$~������� � $M$~���������. 񄅋�� ���� ��������������� �������� 
������, ����� ������ ���������, ������� ��������� ������� � ������ 
�������; ��� ���� ��� ����������� ����� ������������ ������ ��� ������. � 
��� ��������� ��� ���� ��� �������������� ���������� (�������� 5.2D).

蒀�, ����������� ���������� ����� ��������� ��������� �������: ������� 
���������� �������������� ���������� \emph{�� ������� ������ ������} (� 
������� ��������� � ����������~$M$), ���������� ������ �� ������� ����� �� 
��������������� �������, ����� ���������� ��� ���� �������������� 
���������� �� ��������� �����, ���������� ������ ������� � �������� 
������� � �. �., �� ��� ���, ���� ����� ������������ ��������� 
(���������� �� ������� �����) ��� ����� �� �������� �������������� � 
������ �������.

呋� � ��� ������� ���������� ������, � �����---12-��������� ����� � ���� 
$N$~������ ������, �� ����� ������� $M=1000$ (������ ��� ���������� ����� 
�� ���� � ������� ��������� � ���������� 1000); ���������� �� ��������~$N$ 
���������� �����
%% 208
��������� �� ������ ���������. ����������, ���� �� ������� �������� ������,
 � �����---40-������� �������� �����, �� ����� �������� $M=1024$ � ����� 
��������� ���������� �� ������ ���������. 􀊒������ ������ �������� 
������� �� ���� ������ (�������, ������������� ������, �����������); 
����� [{\sl JACM,\/} {\bf 3} (1956), 151] 
��������� ������������� ��� �� ���� ���� ��������, ������� ��� 
$M$~�����: ����������� �������� ��������� ��� $(k+1)\hbox{-��}$ ��������� 
������������ � ������������ �� ����� $k\hbox{-��}$ ���������.

� ����.~1 �������� ���������� ����������� ���������� � ����� 16~������ ��� 
$M=10$.  ����� �����~$N$ ����������� ����������, ��� �������, �� 
�������� �������, ��� ��� ���� ��������� ������ ������������ ������� 
������� ��� ����, ����� ������������������ ������������� ������, � �� ��� 
�������������.

{
\def\subtable#1{
\noalign{
\halign{
##\hfill\bskip&&\bskip\hfill$##$\cr
#1
}}
}
\htable{򀁋��� 1}{�������� ����������}{
#\hfill\bskip&&\bskip$#$\cr
���� �����:           & 503 & 087 & 512 & 061 & 908 & 170 & 897 & 275 & 653 & 426 & 154 & 509 & 612 & 677 & 765 & 703 \cr
\subtable{
񗅒���� ��� ������� ����:           & 1& 1& 2& 3& 1& 2& 1& 3& 1& 1\cr
񎎒����������� ������������� ������:& 1& 2& 4& 7& 8&10&11&14&15&16\cr
}
⑏������������ �������: & 170 & 061 & 512 & 612 & 503 & 653 & 703 & 154 & 275 & 765 & 426 & 087 & 897 & 677 & 908 & 509 \cr
\subtable{
񗅒���� ��� ������� ����:           & 4& 2& 1& 0& 0& 2& 2& 3& 1& 1\cr
񎎒����������� ������������� ������:& 4& 6& 7& 7& 7& 9&11&14&15&16\cr
}
���� �����;           & 503 & 703 & 908 & 509 & 512 & 612 & 426 & 653 & 154 & 061 & 765 & 170 & 275 & 677 & 087 & 897 \cr
\subtable{
񗅒���� ��� ������� ����:           & 2& 2& 1& 0& 1& 3& 3& 2& 1& 1\cr
񎎒����������� ������������� ������:& 2& 4& 5& 5& 6& 9&12&14&15&16\cr
}
⑏������������ �������: & 061 & 087 & 154 & 170 & 275 & 426 & 503 & 509 & 512 & 612 & 653 & 677 & 703 & 765 & 897 & 908 \cr
}
}

葊������� "�����������" �������� �������, ������, ��� ���� ��������� ��� 
������������� ������ ��������� � "�����������" �������� � 
���������������� ������������� ������;
��� �� ��������, ��� ���������� ��� ������ � ���������� ������ 
���������� ����� ��������� \emph{���������} �������������. ���� ��� 
����������� ���������� ����������� ����� ��������������� ���������� 
����������� ������. � ��� ������ ������ ��������������� ���������������, 
�� ���, ��� ��� �����,--- ����� ��� ������ �������� ����-������������ ������ 
�� ��������� �������. ꐎ�� ����, ������� �� �������� ���������� ������: 
���������� ��������������� �����---� ����� ����� ��������� ������ �� 
�������. �� ����������� ������ ����� $(1+\varepsilon)N+2\varepsilon 
M$~�������, ��� $\varepsilon$---������������, ���������� ����� ����� �����. 
䎂����� ��������� ���������� ����������� ����
%%209
���������, ��������� ��� ���� ���������� ������ �������� ����������� �� 
����������� ������, ����������� � ���� ���������������� � ��������� 
������������� ������.
\picture{���. 32. �������� ���������� ������.}

\alg R.(�������� ���������� ������.) �����������, ��� ������ �� 
�������~$R_1$,~\dots, $R_N$ �������� ���� ����� |LINK|, � ����� 
������������ ����� ������������������ �� $p$~���������
$$
(a_p, \ldots, a_2, a_1), \quad 0\le a_i<M,
$$
� ��������� �������---������������������, �. �.
$$
(a_p, \ldots, a_2, a_1)<(b_p, \ldots, b_2, b_1)
$$
����� � ������ �����, ����� ���������� ����� ������~$j$, $1\le j\le p$, 
��� 
$$
a_i=b_i \rem{��� $i>j$, �� $a_j<b_j$.}
$$
ꋞ�� ����� ������������ ����, � ���������, ��� �����, ���������� �  
������� ��������� � ����������~$M$:
$$
a_pM^{p-1}+\cdots+a_2M+a_1,
$$
� � ���� ������ ������������������ ��������� ������� ������������� 
�������� ������������ ��������� ��������������� �����. ꋞ�� ����� ����� 
���� ��������� ���� �������� � �. �.

� ����� ���������� ����������� $M$~"������" ������� ����, ��� ��� 
�������� � �������������� ������ ��� ���������. 񒎏�� ���������� 
������������ ����� ������� � ������ ��.~2, ��������� �� ��������� �� 
������ ����� �������, ��� ��� ������ ��������������� �� �������� "������ 
����������---������ �����������". 䋟 ������ ������ ������� ��� 
����������-���������: $|TOP|[i]$ �~$|BOTM|[i]$, $0\le i<M$, �, ��� � � 
��.~2, ��������������, ���
$$
|LINK|(|LOC|(|BOTM|([i])))\equiv|BOTM|[i].
$$
%% 210
\st[���� ��~$k$.] ⍀���� ����������~$|P|\asg|LOC|(R_N)$, ��������� �� 
��������� ������. 瀒�� ��������� ���� �~\stp{2} ��~\stp{6} ��� $k=1$, 2,
~\dots, $p$ (���� �~\stp{2} ��~\stp{6} ���������� ���� "��������") � 
��������� ������ ���������. �������~$|P|$ ����� ��������� �� ������ � 
���������� ������, $|LINK|(|P|)$--- ��  ������  ��  ���������  ��  �������� 
������, $|LINK|(|LINK|(|P|))$---�� ��������� � �.�.; ����~$|LINK|$
��������� ������ ����� �����~$\NULL$.

\st[������� ������.]  $0\le i<M$ 
����������~$|TOP|[i]\asg|LOC|(|BOTM|[i])$ �~$|BOTM|[i]\asg\NULL$.

\st[⛄����� $k\hbox{-�}$ ����� �����.] �� $|KEY|(|P|)$---���� ������, �� 
������� ���������~$|P|$,---�����~$(a_p,~\ldots, a_2, a_1)$; 
����������~$i\asg a_k$, $k\hbox{-�}$ ������� ����� ����� �����.

\st[񊎐����������� �����.] 󑒀������ $|LINK|(|TOP|[i])\asg|P|$, �����~$|TOP|[i]\asg|P|$.

\st[���� � ��������� ������.] 呋� $k=1$ (������ ��������) � 
����~$|P|=|LOC|(R_j)$ ��� ���������~$j\ne1$, �� 
����������~$|P|\asg|LOC|(R_{j-1})$ � ������������ � ����~\stp{3}. 
呋� $k>1$ (�� ������ ��������), �� ����������~$|P|\asg|LINK|(|P|)$ � 
������������ �~\stp{3}, ����~$|P|\ne\NULL$.

\st[⛏������ ��������~H.] (򅏅�� �� ��� ������������ ��� �������� �� 
�������.) ⛏������ ����������� ���� ��������~H, ������� �������� 
��������� "������" � ���� ������, ������������� �� � ���������� ���������. 
瀒�� ����������~$|P|\asg|BOTM|[0]$, ��������� �� ������ 
������� ������������� ������. (�. ���.~3.)
\algend
\alg H.(񖅏����� ��������.) � $M$~������ �������� �� �������, 
���������������� ����������� ���������~R, ������ �������� ������� ���� 
�������, ����� ��� ���� �� ����� $M$~������. � ���������� $|BOTM|[0]$ 
��������� �� ������ �������, � ������~0 ������������ ������~1, \dots, 
������������ ������~$(M-1)$.

\st[퀗������ ���������.] 󑒀������ $i\asg 0$.

\st[󊀇����� �� ������� ������.] 󑒀������ $|P|\asg|TOP|[i]$.

\st[񋅄����� ������.] 󂅋�����~$i$ ��~1. 呋� $i=M$, ��
����������~$|LINK|(|P|)\asg\NULL$ � ��������� ������ ���������.

\st[񒎏�� �����?] 呋� $|BOTM|[i]=\NULL$, �o ������������ �~\stp{�}.

\st[񖅏��� ������.] 󑒀������ $|LINK| (|P|)\asg|BOTM|[i]$. ⎇��������� �~\stp{2}.
\algend

� ���.~33 �������� ���������� ������ ����� ������� �� ���� ����������, 
����������� ��� ���������� ����� 16~����� �~$M=10$. ��������~R ����� 
������ ����������������� ��� ������~\MIX, ���� ������ ����� �������, 
������ �������� �� ��������� � ��������� �������� � �����~R3 �~R5. � 
���������
%%211
��������� ����� ������� ��������, �� ������� ��������� ����������� 
�����, ����� ��������������� ������ ���� ������ � ���� ���������. 瀌����, 
��� $|TOP|[i]$ �~$|BOTM|[i]$ ����� ��������� � ���� �����.

\picture{���. 33.               �������� ���������� � �������������� 
���������� ������������� ������ (�������� ���������� ���� ������ ������ 
����� ������� ���������).
}
\prog R.(�������� ���������� �������.) �����������, ��� �������� 
����� � ������� ��~$|INPUT|+1$ ��~$|INPUT|+N$ �������� $p=3$~���������� 
($a_3$, $a_2$, $a_1$), ���������� �������������� � ����� $(1:1)$, 
$(2:2)$ �~$(3:3)$. (򀊈� �������, ���������, ��� ��������~$M$ ������ ��� 
����� ������� ����� ������ \MIX.) � ���� $(4:5)$ ������ �������� 
�����~|LINK|. �� 
$|TOP|[i]\equiv |PILES|+i(l :2)$ �~$|BOTM|[i]\equiv |PILES|+i(4:5)$ ��� 
$0\le i<M$. 󄎁�� ��������� � ����� ��������� ������������ ������ |INPUT|,
 ��� ��� $|LOC|(|BOTM|[i])=|PILES|+i- |INPUT|$; ����� ��������
%%212
��������� ������������� ������, ����� ����������� �������~|PILES| 
����� �������~|INPUT|. 獀����� ��������� ���������: $|rI1|\equiv |P|$, 
$|rI2|\equiv i$,  $|rI3|\equiv 3-k$, $|rI4|\equiv|TOP|[i]$; �� ����� 
������ ���������~H $|rI2|\equiv i-M$.
\code
LINK & EQU  & 4:5
TOP  & EQU  & 1:2
START& ENT1 & N  & 1 & R1. ���� �� $k$. $|P|\asg|LOC|(R_N)$.
     & ENT3 & 2  & 1 & $k\asg 1$.
2H   & ENT2 & M-1& 3 & R2. ������� ������.
     & ENTA & PILES-INPUT,2 & 3M & $|LOC|(|BOTM|[i])$
     & STA  & PILES,2 (TOP) & 3M & \hfill$\rasg|TOP|[i]$
     & STZ  & PILES,2(LINK) & 3M & $|BOTM|[i]\asg\NULL$.
     & DEC2 & 1             & 3M
     & J2NN & *-4           & 3M & $M>i\ge 0$.
     & LDA  & R3SW,3        & 3
     & STA  & 3F            & 3  &  臌����� �������
     & LDA  & R5SW,3        & 3  &  ��� $k$-�� ���������.
     & STA  & 5F            & 3
3�   & [LD2 & INPUT, 1(3:3)]&    & R3. ⛄����� $k$-� ����� �����.
4H   & LD4  & PILES,2 (TOP) & 3N & R4. 񊎐����������� �����.
     & ST1  & INPUT,4(LINK) & 3N & $|LINK|(|TOP|[i])\asg|P|$.
     & ST1  & PILES,2(TOP)  & 3N & $|TOP|[i]\asg|P|$.
5H   & [DEC1& 1]            &    & R5. ���� � ��������� ������.
     & J1NZ & 3B            & 3N & � R3, ���� �������� ��������.
6H   & ENN2 & �             & 3  & R6. ⛏������ �������� �.
     & JMP  & 7F            & 3  & � �2 � $i\asg0$.
R3SW & LD2  & INPUT, 1(1:1) & N  & ꎌ���� ��� R3 ��� $k=3$.
     & LD2  & INPUT, 1(2:2) & N  & ꎌ���� ��� R3 ��� $k=2$.
     & LD2  & INPUT, 1(3:3) & N  & ꎌ���� ��� R3 ��� $k=1$.
R5SW & LD1  & INPUT, 1(LINK)& N  & ꎌ���� ��� R5 ��� $k=3$.
     & LD1  & INPUT, 1(LINK)& N  & ꎌ���� ��� R5 ��� $k=2$.
     & DEC1 & 1             & N  & ꎌ���� ��� R5 ��� $k=1$.
9H   & LDA  & PILES+M, 2(LINK)& 3M-3 & �4.񒎏�� �����?
     & JAZ  & 8F              & 3M-3 & �    ��,   ���� $|����|[i]=\NULL$
%%213
     & STA  & INPUT, 1(LINK)  & 3M-3-E & H5. 񖅏��� ������ $|LINK|(|P|)\asg|BOTM|[i]$.
7H   & LD1  & PILES+M, 2(TOP) & 3M-E   & H2. 󊀇����� �� ������� ������.
8H   & INC2 & 1               & 3M     & H3. 񋅄����� ������, $i\asg i+1$.
     & J2NZ & 9B              & 3M     & � �4, ���� $i\ne M$.
     & STZ  & INPUT, 1(LINK)  & 3      & $|LINK|(|P|)\asg\NULL$.
     & LD1  & PILES (LINK)    & 3      & $|P|\asg|BOTM|[0]$.
     & DEC3 & 1               & 3
     & J3NN & 2B              & 3      & $1\le k\le 3$
\endcode

␅�� ������ ���������~R ����� $32N+48M+38-4E$, ��� $N$---����� �������� 
�������, $M$---��������� ������� ��������� (����� ������), � $E$---����� 
������������� ������ ������. 񐀂����� � ������� �����������, 
������������ �� ������ ����������� ������������� (���������~5.2.1�, 
5.2.4L), ������� ���� � ������ ���������~R. ␅�� ������ 
$p\hbox{-����������}$ �������� ���������~R ����� $(11p-1)N+O(pM)$~������; 
����������� ������, �������� �� ����� ������,---���������� ����, ������� 
�������� ���� ��������� � ������ � ���� �������. 䋟 �������� 
�������������� ������ $M=b^r$ �~$p=\ceil{t/r}$, ��� $t$--- ����� ���� � 
������, �������������� � ������� ��������� � ����������~$b$; � ������~$r$ 
�������~$p$, ��� ��� ����� ��������������� ������ ��������� ��� 
����������� "����������" ��������~$r$.

儈��������� ���������� �������� � ������� ������� ������---��� $E$---����� 
������ ������, ������������ � ���� �4. ��������, ��� ��� 
$M^N$~������������������� ���� $M\hbox{-�����}$ ������� ��������� 
�������������. � �������� "�����-�����" � �.~3.3.2D �� ����� ��������� 
����������� ����, ��� � ������ ��������� ���������� ����� $M-r$ ������ 
������; ��� �����
$$
{M(M-1)\ldots(M-r+1)\over M^N}\left\{{N\atop r}\right\},
$$
��� $\left\{{N\atop r}\right\}$---����� 񒈐����� ������� ����. 񎃋���� ���.
 5,
$$
E=\bigl(\min\max (M-N, 0)p, \ave M(1-{1\over M})^Np,\max(M-1)p\bigr).
$$

� ��������� ���� ���������� ��� ������ "��������������", ��� 
"�������������", �������������� �����. ��� ������ ����� ��������� 
�������������� ��������� � ����� "����������", ��� ��� ��������� � 
������ � ���������� ����� � ������������ ������� ����������� �� �������; 
�� �������������
%%214
����� ����� ������� ���������� ��� ������� �������� ���������, ���� 
������ ��� �������� �� ���������� ����� ������ � ����� � ��� �� 
�����������. ⍓������� ���� ����������� ���������� ������ ������������ 
��� ����� �����, ��������� ��� ������� ����������� ����������, �������� 
"������������� �����". ���� \emph{��� ������������� ����� ����������� 
���������� ������ ������ �������� ����������� ������� �� ���� 
��������� ������� ���������� ����������}, ��� ������� ��� $N$ �� ������� 
���� � ����� �� ������� �������.

����������, ���� ����� �� ����� �������, ����������� ���������� �� ��� 
����������. �������� ����, ��������, ��� ����� ������������� ���������� 
�� ����� �� 80~�������; ��� �������, ���������� ����� ���� ��� ����, � 
������� �� ������� ������ ���� �������, ��� ��� ������ 75~���������� 
���������� ����� �������.  ������� �������� ����������� ���������� �� 
����������, ��� ����� �� ����������� ��������� ����� ����� ������, ���� 
������������� �� �� ������ ������, � ����� �������. ���� ������� 
����������� � ���� ����������� ����������, � ������� ����� 
���������������, ������� �� ������� ���� (��), � �� � ������� ���� (��).

� ��� ��������, ��� ��-����������� ���������� ������������ ������� 
�������� �� ��. � ����� ����, �������� ������, ������ ��� ���������� ����� 
� ���������� ����� ���������� ������ ���� �������. ᎋ���� ���������� 
����� ����� ������������� �� ��������� ������, ��������������� 
�������������� ��������; ������ ������ ����� �������� ��� ������� 
���������� �����, ������� ����� ���������� ����������� �� ������ ������, 
��������������� ��� ������� � ������� �������������� �������. 
(����������, ������ ��� ���������� ������ ���������� ����������, �� 
����� ����������� ������� � ����� ����������.) ���� ������� "�������� � 
��������" ������ �������������, � ������������ ������� ��� ������������� 
��� ���������� ��������� � ���, ��� ������� ���������� ������ �������� 
� ��������. ���� �� �������� ����������� ������������� ������������� 
���������~R (���� ����� ������� ��������������� ��), ������ ��� ��� 
������� �� ���������� �������� ����� ��� � $M$~�������� � ������ 
���������� �������� ����� $p$~���. � ������ �������, �������� ��������� 
��-����������� ����� � �������������� ���������� ������������� ������ � 
�������������� ������� ��� ����������� ������ ����� ��������, ��� � 
��������� 5.2.4L. (�. ���. 10.)

����, ��������� ������������� ����� ������ �.~�.~쀊����� [{\sl JACM\/},
 {\bf 13} (1966), 404--411], ������� ��������� ������������ 
��-����������, ��� � ���������~R, \emph{�� ���� � ���������� � ������� 
������}. ��� �� ����� ������ ����������� �����, �� � ���������� ���� 
���������� ����� �������������, �. �.
%%215
� ��� �������� ����� ���� ��������, ��� ��� ��� ���������� ���������� 
����� ��������������� ������� ������� �������. 퀘 ������ ��������� 5.2.1� 
�������� � �-���� ��������;
���� ����� ������������ ����������, �� ����� ���������� ����� �� ������� 
$p$~������ � ��� ��������� � �������
$$
{1\over 4}N(N-1)M^{-p}
$$
��������. [�. �������~(5.2.1--14) � ���.~5.2.1--38.] 쀊����� �������� 
������� ����� ��������� � ������, ������������ �� ���� �������������� 
�������, � ���������, ��� ����������� ����� ��������~$M$ �~$p$ (� 
�������������, ��� $M$---������� ������, ����� ���������� ������������ 
�~$N/M^p\le 0.1$, ���.��� ���������� �� ������������ ������������� 
���������) ����������� ��������� ��������:
\ctable{
\hfill$#$\bskip&&\bskip\hfill$#$\bskip\cr
N= & 100 & 1000 & 5000 & 10000 & 50000 & 100000\cr
\hbox{퀈������ } M=& 32 &  128 &  256 &  512 &  1024 &   1024\cr
\hbox{퀈������ } p=& 2 & 2 & 2 & 2 & 2  & 2\cr
      \bar \beta(N)=& 19.3 & 18.5 & 18.2 &  18.2 &  18.1 &   18.0 \cr
}
焅�� $\bar\beta(N)$---������� ����� ��������� � ������ �� ���� 
����������� �������; ��� �������� ���������� ��� $N\to\infty$, 
���� ����� $p=2$ �~$M>\sqrt N$, ��� ��� ������� ����� ���������� 
���� $O(N)$, � �� $O(N \log N)$. ���� ����� �������� 
������������������� ������ ������� � ��������� ������� (��������~5.2.1�), 
�������, �� ��������, ������������ ����� ������ $p=1$. � ���.~12 
���������� ���������� ��������� 쀊������ ��� 
�������������� �������������� ����� ��������� ���������� ����� � 
�������������� �������.

呋� ��������������� �������� ���������~5.2D � ���.~5.2-13, �� ����� 
�������� ��� ����� �����; ��� ���� � ���������� � ������, ������� ������ 
��������, ����������� ����� $O(\sqrt N)$~�����. 呋� �������� ������ 
������������ ����������, �� ������� ����� ���������� ���������������~$N$.

\excercises
\rex[20] �������� �� ���.~5.2--13 ����������, ��� ����� ��������� 
�������������� ����������, ���� ������������ ������ ����� ��� 
$N$~������� (� $M$~����� ���������), � �� ��� $2N$~�������. ����� �� 
��� ���� � ������������������ ��������� ����������� ����������, 
�������������������� � ����.~1?

\ex[13] ߂������ �� ��������~R ���������� "����������" ����������?
%%216

\ex[15] ������, ������ � ���������~H ���������� $|BOTM|[0]$ 
������������� �������� ��������� �� ������ ������ � "������������" 
�������, 
\emph{�������� �� �� ��� ������ 0 ����� ���� ������.}

\rex[23] � ����� ������ ���������~R ��� $M$~������ �������� � 
���� ��������� �������� (������ ����������---������ �����������). 
葑������� ���� ���������� ��������� ������ ��� � \emph{�����}. (� 
���.~33 ������� ������ �� �����, � ����, � �������~|BOTM| ������ �� 
�����.) �����, ��� ���� �������� ������ � ��������������� �������, �� 
����� ���������� ���������� ����� ����������. ᓄ�� �� ���� �������� 
����� ������� ��� ����� �������?

\ex[M24] �� $g_{MN}(z)=\sum p_{MNk}z^k$, ��� $p_{MNk}$--- ����������� 
����, ��� ����� ���������� ��������� ����������� ����������, ������������ 
$N$~��������� �� $M$~������, ���������� ����� $k$~������ ������. (a) 
�����, ���
$g_{M,N+1}(z)=g_{MN}(z)+((1-z)/M)g'_{MN}(z)$. (b) 퀉���� ��� ������ 
���������� ����������� ������� ��������� ��� ��������������� �������� � 
��������� ����� ������������� ������������ ��� ������� ��~$M$ �~$N$.

\ex[20] ꀊ�� ��������� ���������� ������ � ���������~R, ����� 
��� ����������� �� ������������ �����, � ��������������? 񗈒�����, ��� 
������� ����� �����~$K_i$ �������� � ������ $|KEY|+i(1:5)$, � ��� 
������� �����, ��� � ������,---� ������ $|INPUT|+i(1:3)$. ꀊ��� ����� 
������ ��������� � ����� �����������?

\ex[20] �����, � ��� ������� �������� � ������� ���������~R � 
��������� �������� ����������� ���������� (��������~5.2.2R).

\rex[20] � ���������� ����������� ����������, ������������� � ������,
 ��������������, ��� ��� ����������� ����� ��������������. ꀊ�� 
��������� ������� ������ � ��� ��������� � ��� ������, ����� ������� 
����� ���� � ������������� �����, �������������� � \emph{�������������� 
��� ��������} ����?

\ex[20] (�������� ���.~8.) ꀊ�� ��������� ����� ������ � ��� 
��������� � ������, ����� ������� �������� �����, �������������� � 
���� ���������� �������� �� ������?

\ex[30] 񊎍���������� �������� ����������� ���������� 
"�������-��-�������-�����", ������������ ��������� �������������. (� ��� 
������ ��������� ��� �����������, �� ������� ��������� $M$, � ��� 
���������� �������� ������ ��������� �� ����������� ����������.)

\ex[16] ��������� ����������� �������� �����, ���������� � ����.~1,
 �������� ������� 41 ��������. �� ���������� ���������� ��������, 
����������, ��� ������. 񊎋��� �������� �������� �� � �����, ���� �� 
�� ���������� ������ ��������, � ��������� �� ����������� ���������� 
���� �� ������ �������� � �����? 񊎋��� �������� ���������, ���� 
���������� ��� ������, ��� � ������ ���������?

\ex[24] (�. �. 쀊�����.) ��������, ��������~R ��������� ������ � 
$p$~������� ������ �������� ������; ����� ����, ���� ������ ��� �� 
�������, ���������� �������, ����� ������������, �� �����, � ������� 
������� $p$~���� ���������, ����� ���� �������������. ������� 
�������� �������������� ������� �� ��� �� ����� ���, ����� ����� 
������������� �� �������: $K_1\le K_2\le\ldots\le K_N$. [\emph{󊀇����:} 
������� ������, ����� ���� ��������� ������������, ����� ����� � ������ � 
���. 5.2--12, ��� ����� �������������� � �������� ��������� ��� ������ 
�������������, ��� ��� � ����� �������� ���� ��������.]

\ex[40] ���������� ����� ���������� ����������, ������������ � ������ � 
����� ����� ������, ������� ��������� ���������� ��������� ������ �� 
$O(N)$~������ �������, ��������� ����� $O(N)$ �������������� ����� ������.

\ex[22] ��������������� ��������� ����
%%217
����� ������������� � ������������ �������: |�| |2| \dots |�| |�| |�| �� 
������� ����� � ������, �� ��� ���������, ����������� ����� ������ ��� 
���� � ��� ������: ��������� ����� ������� �������� ���� � ��� ������, 
���������� �������������� |�| |2| |9| |3| |10| � |4| |�| |5| |6| |�| |�| 
|7| |8| (�� ������ ����� � �������); ����� �������� ������ ������ ������ 
������, ��������� ������ ������� �������� ����� � ��������� � ��� ������ 
|�| |2| |3| |4| |5| |6| |7| |8| � |9| |10| |�| |�| |�|.  񎅄����� ��� ��� 
������ � ��������� �� ������� �������� �����. ꎋ��� �������������.

䎊�����, ��� ����������� ���� ������������������ ���� ������ 
������������� � \emph{���������} �������: |�| |�| |�| \dots |2| |�|, �� 
������� ����� � ������, �� ��� ���������, ���� ���� ��������� ������������ 
����� � ��� ������. (񄀂��� �����, ����� ������ ������ ������, 
����������� �� ��� ������� �������� �����. � ������� ������� ����� ������ 
���������� ������, � ������---�����.)

\ex[�25] ����������� ������ �� ���.~14 � ������, ����� ����� 
��������� ������� �������� �����, � �� ����. 򀊈� �������, ���� �������� 
����� ��������� �� �������������� ������������� ������� � ���������. 
񊎋��� ����� ����������?

\bigskip\epigraph
ꀊ ������ �������� ������������� ������, ���, ����������, ��������� 
���������� ���� �������� �����. ⑟��� ���, ����� � �� ������� ����� 
������ �����-���� ���������, ��� �� ��������� ������: ������ �� ��� �� 
��������� �������� �� ���� ������ �� ���������� �����?
\signed ������ ᝁ���� (1864)

%%218
\bye
