\input style
\chapno=5\subchno=4
\chapnotrue

%%438
\htable{ ���� 1}%
{倐����������� ������������ ������ $A_m(n)$, $k_m(n)$ ��� $\alpha=\beta=1$}%
{$n=#$\hfill&
\hfill$\,#\,$&\hfill$\,#\,$&\hfill$\,#\,$&\hfill$\,#\,$&\hfill$\,#\,$&\hfill$\,#\,$&
\hfill$\,#\,$&\hfill$\,#\,$&\hfill$\,#\,$&\hfill$\,#\,$&\hfill$\,#\,$&\hfill$\,#\,$&
\hfill$\,#\,$\hfill&$n=#$\hfill\cr
\omit
  & m=1 &  m=2 & m=3 & m=4 & m=5 & m=6 & m=7 & m=8 & m=9 & m=10& m=11& m=12& \hbox{�������� ������}\cr
1 &  0,0&      &     &     &     &     &     &     &     &     &     &     &-         & 1\cr
2 &  6,2&  0,1 &     &     &     &     &     &     &     &     &     &     &1:1       & 2\cr
3 & 12,3&  6,1 &  0,1&     &     &     &     &     &     &     &     &     &1:1:1     & 3\cr
4 & 20,4& 12,1 &  6,1&  0,1&     &     &     &     &     &     &     &     &1:1:1:1   & 4\cr
5 & 30,5& 18,2 & 12,1&  6,1&  0,1&     &     &     &     &     &     &     &1:1:1:1:1 & 5\cr
6 & 42,2& 24,3 & 18,1& 12,1&  6,1&  0,1&     &     &     &     &     &     & 3:3      & 6\cr
7 & 52,3& 32,3 & 24,1& 18,1& 12,1&  6,1&  0,1&     &     &     &     &     & 1:3:3    & 7\cr
8 & 62,3& 40,4 & 30,2& 24,1& 18,1& 12,1&  6,1&  0,1&     &     &     &     & 2:3:3    & 8\cr
9 & 72,3& 50,4 & 36,3& 30,1& 24,1& 18,1& 12,1&  6,1&  0,1&     &     &     & 3:3:3    & 9\cr
10& 84,3& 60,5 & 44,3& 36,1& 30,1& 24,1& 18,1& 12,1&  6,1&  0,1&     &     & 3:3:4    &10\cr
11& 96,3& 72,4 & 52,3& 42,2& 36,1& 30,1& 24,1& 18,1& 12,1&  6,1&  0,1&     & 3:4:4    &11\cr
12&108,3& 82,4 & 60,4& 48,3& 42,1& 36,1& 30,1& 24,1& 18,1& 12,1&  6,1&  0,1& 4:4:4    &12\cr
13&121,4& 92,4 & 70,4& 56,3& 48,1& 42,1& 36,1& 30,1& 24,1& 18,1& 12,1&  6,1& 3:3:3:4  &13\cr
14&134,4&102,5 & 80,4& 64,3& 54,2& 48,1& 42,1& 36,1& 30,1& 24,1& 18,1& 12,1& 3:3:4:4  &14\cr
15&147,4&114,5 & 90,5& 72,3& 60,3& 54,1& 48,1& 42,1& 36,1& 30,1& 24,1& 18,1& 3:4:4:4  &15\cr
16&160,4&124,7 &102,4& 80,4& 68,3& 60,1& 54,1& 48,1& 42,1& 36,1& 30,1& 24,1& 4:4:4:4  &16\cr
17&175,4&134,8 &112,4& 90,4& 76,3& 66,2& 60,1& 54,1& 48,1& 42,1& 36,1& 30,1& 4:4:4:5  &17\cr
18&190,4&144,9 &122,4&100,4& 84,3& 72,3& 66,1& 60,1& 54,1& 48,1& 42,1& 36,1& 4:4:5:5  &18\cr
19&205,4&156,9 &132,5&110,4& 92,3& 80,3& 72,1& 66,1& 60,1& 54,1& 48,1& 42,1& 4:5:5:5  &19\cr
20&220,4&168,9 &144,4&120,5&100,4& 88,3& 78,2& 72,1& 66,1& 60,1& 54,1& 48,1& 5:5:5:5  &20\cr
21&236,5&180,9 &154,4&132,4&110,4& 96,3& 84,3& 78,1& 72,1& 66,1& 60,1& 54,1& 4:4:4:4:5&21\cr
22&252,3&192,10&164,4&142,4&120,4&104,3& 92,3& 84,1& 78,1& 72,1& 66,1& 60,1& 4:9:9    &22\cr
23&266,3&204,11&174,5&152,4&130,4&112,3&100,3& 90,2& 84,1& 78,1& 72,1& 66,1& 5:9:9    &23\cr
24&282,3&216,12&186,5&162,5&140,4&120,4&108,3& 96,3& 90,1& 84,1& 78,1& 72,1& 5:9:10   &24\cr
25&296,3&229,12&196,7&174,4&150,5&130,4&116,3&104,3& 96,1& 90,1& 84,1& 78,1& 7:9:9    &25\cr
}
��� ����� ���������~$(2)$ ����������, ��� ������, ����� ������������ 
$P+1$~������ �������, ����� ����� ����� �����������~$\alpha\le\beta$. 
���������� ������~$\alpha=\beta$, ���������� � ����.~1 � �� ���.~93, 
��������� �����, ����� ��������� �������������� ���� ����� ������ 
��������������� �� ������� ��������.

�������� � ����� �������������� ������. �� ��� �� �����������, ��� 
�������� ��������� �������; ��� ���������� ������/������/���������� 
����� � ���������� ������ ��������� �� ����� �����������. ��������, ��� 
������� ��������� ��� ����������
\picture{���. 93. ����������� ������ ������� 22 ��������� �������� ������ 
�����, ���� � ������� � $\alpha=\beta$. 풀 ����� ������������ ����� 
������ ��� ��������������, ��������� � ������� (2).
}
������, ������������� �� � ������� ���������; ������ �� ����� �������� 
����� � ������ ����� ��������� � ����� �������. ���, ��������, ����� 
������������, ������, 20\% ������ ��� ��������������� ����� �����/������ 
� ��������� ����� � ����������. 풎 ������� � ���� ��� ������ ������� 
(������������� �������� 60~�!), �� ��������� ����� ��������� �������� 
��~100 ��~64; ���������� ����� ��� ����� ������, ���� ������� ���� ��� 
����� ����������.

���� �� ������ �� ������������ ����� � ����������, �� ����������� ������ 
��� $S=100$, $\alpha=0.00145$, $\beta=0.01545$ 
[��. (2)] ����������� ������ ������������. 풎 ������ 10-������� �������, 
����������� �� ��� ������� �� ������. ������� 30~� �� ���������� 
���������� (������, 100~������� ����������), ��������, ��� ��������� 
����������������� ������, �������� ��������
$2{1\over2}$~���, � ������ ������ ������� �������� ����� 5~���; � �����
����� $12.4$~���. ���� �� ������ ������������ ����� � ����������, �� 
����������� ������ ��� $S=64$ ����������� ��������� ������������ (��� 
������� 8-�������� �������); ��������� ����������������� ������ �������� 
�������� $3{1\over2}$~���, ������ ������ �������---����� $4{1\over2}$~���, 
������ ������ ������� ���������� 12.6~���.
%%440
��������, ��� � ����� ���� ������� ���������� ��������� 
����������� ���������� ������/������/����������, ����� ����� ������� 
������ (� ����� ���������� ������� ������). �� ���� �� ���� ������ �� 
�������� �����, ������� ����� ������������� ��� �������� ������������ ������.

�� �������� ��������� ������ ������� ����������� �������� �� ���������; 
��������, �������� ������ ����� ������������� �/��� ������������ �� �����.
 � ����� ������� ������, ������������ ����� �������, ������� �������� � 
�������������� � �������� ���� ����� �������� �������������.

\section *������ ������ ������������� �������. �����~�.~䅐����� ������ 
[{\sl CACM,\/} {\bf 14} (1971), 476--478], ��� ����� ��������� 
����� ������, ���� �� ������ ��� ������ ������ �������. � �� ����� � 
�������� � �� �� ����� ������ � ������ ��� ���������� ����� 
[S.~J.~Waters, {\sl Comp.~J.,\/} {\bf 14} (1971), 109--112; 
Ewing~S.~Walker, Software Age, {\bf 4} (August-September, 1970), 16--17].

�����������, ��� �� ��������� �������������� ������� �������� ������ 
�����~$L_0$, ���� ������ � $M$~�����. ���� �� �������� ������ �� ������ 
������ �������~$B=M/5$, �� ��� ����������� ����� $L_0/B$~������� ��� 
������� �������� ����� � $4L_0/B$~������� ��� ������, ��� � ����� ���� 
$8L_0/B = 40L_0/M$~�������. �� ���� �� ���������� ������ ������ ����� 
�������~$M/6$ � ���� ����� ������ �������~$M/3$, �� ��� ����������� 
����� ���� ����� $4\times(6L_0/M)+4\times(3L_0/M)=36L_0/M$~�������! 
������� �������� � ����� ������� ���������, ��� ��� �� ������ �� 
�������� �� ����� ���������.

� ����� ������ �����������, ��� �� ����� ����� ��������������� �����, 
������� �����~$L_0$,~\dots, $L_p$, � ��������������� ���� 
�����~$L_{P+1}=L_1+\cdots+L_P$, � �����������, ��� ��� $k\hbox{-��}$����� 
������������ ����� �������~$B_k$. ⎃��
$$
B_1+\cdots+B_P+B_{P+1}=M,
\eqno(6)
$$
��� $M$---����� ����� �������� ���������� ������. 爑�� ������� ����� 
�������������� �����
$$
{L_1\over B_1}+\cdots+{L_P\over B_P}+{L_{P+1}\over B_{P+1}}.
\eqno(7)
$$
���������� �������������� ��� �������� ��� �������~(6), ������ ��� 
��������, ��� $B_k$ �� ������� ���� ������. ���� ���������~$B_j$ 
��~$\delta$ � ���������~$B_k$ �� �� �� ��������� ��������, �� ����� 
������� ��������� ��
$$
{L_j\over B_j+\delta}-{L_j\over B_j}+{L_k\over B_k-\delta}-{L_k\over B_k} 
=\left({L_k\over B_k(B_k-\delta)}-{L_j\over B_j(B_j+\delta)}\right)\delta,
$$
�.~�., ������������� ����� ��������, ���� $L_j/B^2_j\ne L_k/B^2_k$. 
ዅ����������,
%% 441
�� ������� ����������� ����� �������, ������ ����
$$
{L_1\over B^2_1}=\cdots={L_P\over B^2_P}={L_{P+1}\over B^2_{P+1}}.
\eqno(8)
$$
  ��� ������� ����������� ����������, �� ������ ����������� ���
$$
B_k=\sqrt{L_k}M/(\sqrt{L_1}+\cdots+\sqrt{L_{P+1}}),\quad 1\le k\le P+1,
\eqno(9)
$$
��������� ��� ������������ ��������~$B_1$,~\dots, $B_{P+1}$, 
��������������� ������������~(6) �~(8). ����������� ���� �������� 
�~(7) ���� ������ ������� ������� ��� ������ ����� �������:
$$
(\sqrt{L_1}+\cdots+\sqrt{L_{P+1}})^2/M,
\eqno(10)
$$
������� ����� �������� � ������ $(P+1)(L_1+\cdots+L_{P+1})/M$,
 ������������ � ��� ������, ���� ��� ������ ����� �� �����.
������� �����~$\sum_{1\le j<k\le P+1}(\sqrt{L_j}-\sqrt{L_k})^2/M$   
�������� ���.~1.2.3-31. � ���������, ������� (10) �� ������� ��� �������� 
����������� ����������� ����� �������, ��� � �������~K (��.~� ���.~14).

\section �������������� �����������. ���� ������������ ��� 
�������� ���������� (���� ��� ������ � ���� ��� ������), �� ����� 
���������� ����� ������� ������ ����� ��������������� ������ ������. 
���� ������������ ����� "���������������" (�.~�.~�� ������� �� ��������� 
���� � ������ ������ �����, ����� ����������, ����� ����� ������ 
�����������), �� ����� ���������� ����� ������� ������. � ���������, 
������� ��������� �������������, ����� ��������� � ��������� 5.4.6F, �� 
������������ ������������ �����/������, ��� ��� ���������� ����� 
������ ��������, ��� �������� ����� � ������ �� ����� ������������ � ���� 
�����. ⎗��� ����� ���������� ������ �������, �, ��������, ����� 
��������������� ������� �������, ����� ����� ���������~$\alpha$ �~$\beta$ 
��� ������������� ������� �������, ��� � �������~H.

���� �� ���������� "���������" ������ (�� ����������� � ����������� �����),
 �� ��� ������ ���� ������ �������, � ����� ������ ��������� ����������� 
���� ������� ������������� �������; ����� ������ ������� ������ ������ 
������, ��� ������ �����. ���� ������������ $2P$~������� ����� 
(������~$P$), �� ��������� ������������ ���� ������� �����, ������ 
��������� ����� ������ �, ��������, ������ �� ��������; ��-��������, 
����� ����� ����� $P+1$ ��� $P+2$~������� �����.
⅏��� �������� ������ ���� ����, ��� ������� ������ ��������� ��� 
����������� ���������� �� ������ �� �����������;
����� ��������� ��������� ����������� ��������� ����� ���������. ������� 
���� ���������������� ������������. 厒� ������,
%%442
�������� � ���� ������, ���� ��������� �������� �������������, ��� 
��� ��������� ������������ ����� ����������������� ������������.

\section *��������� �� ����������� ��������. � ��������~H �~K ��������� 
����������� ������� ������~$\beta=0$, �������� �� �� ��� ������������ 
�������� ������ �������� � ����������~$0\le\alpha\le\beta$. ����� ������ � 
$n$~�������� ����� ���������� ��������� ����� ���������� ����? ���������, 
��� � ���� ������ ��������� ����������� ����������� �������.

\proclaim ⅎ���� L. ����� ���������� ���� ������ � $n$~�������� ������� 
�� ������, ���
$$
f(n)=\cases{
3qn+2(n-3^q), & ���� $2\cdot 3^{q-1}\le n\le 3^q$;\cr
3qn+4(n-3^q), & ���� $3^q\le n\le 2\cdot 3^q$.\cr
}
\eqno(11)
$$
⅐������ �������~$\cJ_n$, ������������ ���������
\picture{������� �� ���. 442}
����� ����������� ����� ���������� ����.

\proof. ����� ��������, ��� $f (n)$---�������� �������, �. �.
$$
f(n+1)-f(n)\ge f(n)-f(n-1) \rem{��� ���� $n\ge2$}.
\eqno(13)
$$
풎 �������� ����������� ����� ��������� �����.

\proclaim ����� �. �������~$g(n)$, ������������ �� ������������� ����� 
������, ������������� �������
$$
\min_{1\le k\le n} (g(k)+g(n-k))=g(\floor{n/2})+g(\ceil{n/2}), 
\quad n\ge 2,
\eqno (14)
$$
����� � ������ �����, ����� ��� ��������.

\proof. ���� $g(n+1)-g(n)<g(n)- g(n-1)$ ��� ���������~$n>2$, �� ����� 
$g(n+1)+g(n-1)<g(n)+g(n)$, ��� ������������~(14). �������, ����~(13) 
����� ����� ���~$g$ 
�~$1\le k<n-k$, �� � ���� 
����������~$g(k+1)+g(n-k-1)\le g(k)+g(n-k)$.\proofend

��������� ����� �������������� ����� � ����� �������������� �� 
�����~$m\ge2$ � ��������, ���
$$
\min_{n_1+\cdots+n_m=n\atop n_1, \ldots, n_m\ge 1}
 (g(n_1)+\cdots+g(n_m))=g(\floor{n/m})+g(\floor{(n+1)/m})+\cdots
+g(\floor{(n+m-1)/m}),
\eqno(15)
$$
%%443
���� $g$~�������. �����
$$
f_m(n)=f(\floor{n/m})+f(\floor{(n+1)/m})+\cdots+f(\floor{(n+m-1)/m}).
$$
�������������� �������~L ����������� ��������������� ����, 
��� $f_3(n)+3n=f(n)$ �~$f_m(n)+mn\ge f(n)$ ��� ����~$m\ge2$ (��.~���.~11).\proofend

���� �� ����� ������, ���� �� ����������� ������� ������ ����������������� 
��� �� �����, ��� � �������~L. �� ���������� ��� $\alpha=\beta$, ������� 
�� ����� � ����.~1, ����������, ��� �������~$A_1(n)$ �� ������ �������. �� 
����� ���� ����.~1 ����������, ����� ������������ ����������� ������� 
������������� �� ����������� ��������! ��, ������, ����� ������ ����� 
�������~L ��� ������ ������������~$\alpha$ �~$\beta$. �.~苞������� 
� �.~������� ��������, ��� \emph{�������} �������� ������� ������ ����� 
��������.

\proclaim ⅎ���� M. ���� ����~$\alpha$ �~$\beta$, ��� � �������~H, �� 
���������� ����������� ������, � ������� ������� ������ ���� �� �����������
$$
d(\alpha, \beta)=\ceil{\min_{k\ge1}\left(k+\left(1+{1\over k}\right)
\left(1+{\beta\over\alpha}\right)\right)}.
\eqno(17)
$$

\proof. ����� $n_1$,~\dots, $n_m$---������������� ����� �����, �����, ��� 
$n_1+\cdots+n_m=n$, $A(n_1)+\cdots+A(n_m)= A_m(n)$, 
$n_1\le \ldots \le n_m$, � �����������, ��� $m\ge d(\alpha, \beta)+1$. 
����� $k$---�� ��������, ��� ������� ����������� ������� � (17); �������, ���
$$
\alpha n(m-k)+\beta n+A_{m-k}(n)\le \alpha m n +\beta n+A_m(n),
\eqno(18)
$$
�, �������������, ������� � (4) ������ ����������� ��� ���������
$m\le d(\alpha, \beta)$.

�� �����������, ��������� $m\ge k+2$, �� ������ �����
$$
\eqalign{
A_{m-k}(n) &\le A_1(n_1+\cdots+n_{k+1})+A_1(n_{k+2})+\cdots
+A_1(n_m)\le\cr
&\le \alpha(n_1+\cdots+n_{k+1})(k+1)+\beta(n_1+\cdots+n_{k+1})+\cr
&\phantom{\le}+A_1(n_1)+\cdots+A_1(n_m)=\cr
&=(\alpha(k+1)+\beta)(n_1+\cdots+n_{k+1})+A_m(n)\le\cr
&\le(\alpha(k+1)+\beta)(k+1)n/m+A_m(n),\cr
}
$$
������ (18) ����� ���������. (♀������� ������������ ����� 
�������������� ����������, ��� ������~(17) �������� "��������� �� 
���������" � ��� ������, ��� ��������� ����������� ������� ������ ����� 
���� �������~$d(\alpha, \beta)$; ��. ���.~13.) \proofend

���������� � �������~K ������� $O(N^2)$~����� ������ � $O(N^2\log 
N)$~����� ��� ���������� $A_m(n)$ ��� $1\le m\le n\le N$, a
%%444
� �������~M ��������, ��� ��������� ������ $O(N)$~����� � $O(N^2)$~�����. 
苞������� � ������� ������� ��� ��������� ����� ���������� ������� 
����������� �������� 
[Optimal disk merge patterns, {\sl Acta Informatica,\/} {\bf 3} (1973), 25--36].

\section ������������� ���������. �. �. ���� 
[{\sl CACM,\/} {\bf 6} (1963), 245--248]
��������� ���������� ������, ��� ������� ��������� ������� ����������� 
������ � ��������� ����� ����������� ����� ��� ������. ��� ���������� ��� 
���� ��������� ����� ������������� ����� ��������, ����������� �������, 
�� ���� ����, ����� ����������, ��������� �� ������ ������ �������, � 
������� ��� ����� �������� � ������ ������ ������� ������ ����������.

���� ������. ������ ���������� ������� ��������������� ������ ��������� 
����� �� ��������� �� ������ � ������ ������ ���������� ������������ �� 
������ ��� ������� ��������. ����� �������� ����� ������� ������� 
����������, �� ���������� �� � ������� ������� (� ���, ��� �������� 
��������� �������), ���� ���� ������� �� �����. ��� ���� ����� 
������ ������ �������� �� ���.

����� ��� ������������ �������. ���� � ���, ��� �� �� ����� ���������� 
������ �� ��������� ������� ������ ����� �������, ��������� ����������� 
��� ����� ���������� � ������ ������ �� ��������. (�� ����� ��, ���� ��� 
��� �������, ���������� ������ �� ���������� ������� � �� 
��������� ������� ������ ���� � �������� �����������.) ����� 
������� ��������� ������� ������� ����� ��� ������� ������� �����,
 ��������, �������� �� ����� �����. Ꮘ��� ����������-������������ ����� 
��������� ����������� � ������� ������� ������, ��� 1000~����� ��������� 
��������� ��� ����������� 1000~�������.

\qsection ������� �� ���������� ������? ���� ������ �������, � ����� 
��������, ������ ��������� ������� ����� ����, ��������� ������ �� ������ 
������ � ����������� ��������, ������������� �� �������������� ��������� � 
�����. ����� ���������� ����� ����� ������ ����� �������� ����� 
����������������� �������~$1$, $2$,~\dots. ����� ���� ����� ���� ����� 
������������� �� ��������� � �������������� �����, � �� ������� 
������� �������� ����, ��� "�����������" ������, ����� �������������� �� � 
��������� �������.

ᕅ��������� ���������� ������� ���:
\halign{
#\hfill&#\hfill\cr
a) �������� ����           & $(K_1, I_1)$ $(K_2, I_2)$ \dots $(K_N, I_N)$ �������;\cr
b) �������� ����          & $(K_1, 1)$ $(K_2, 2)$ \dots $(K_N, N)$ ��������;\cr
c) ��������������� (b)& $(K_{p_1}, p_1)$ $(K_{p_2}, p_2)$\dots $(K_{p_N}, p_N)$ ��������;\cr
%%445
d) ����������������� (�) & $(1, p_1)$ $(2, p_2)$ \dots $(N, p_N)$ ��������;\cr
e) ���������������   (d)&  $(q_1, 1)$ $(q_2, 2)$ \dots $(q_N, N)$ ��������;\cr
f) ����������������� (a) & $(q_1, I_1)$  $(q_2, I_2)$ \dots $(q_N, I_n)$ �������.\cr
}

\noindent ����� $p_j=k$ ����� � ������ �����, ����� $q_k=j$; ��� 
�������� ���������� � ������� (c) � (c) ������������ ������� (������ ����� 
�������� ���������� �����������), ��� ��� ������ �� ������� �������. �� 
������ (f) �� ����� ������ � ���������� �����, ����� ��������---������ ����� 
$\{1, 2,~\ldots, N\}$; ������ ������ ������ ���������� � �������� �� �����,
���� �� ������� �����������.

�������� �������� ��������������, ���������� ����� ������ (f), ������� 
�� ������ ������ �����������, �� ���������� ��� ����� ������, � ��� ��� �� 
������� �� ������ ������������� �������� ��������� (����������� �������, 
��� ����������). ��, ��������, ����� �� ��������� �������������� �� 
$N$~�����, ��������� ������ ��� �� ����� ������; ��� 
���������� ��������~$N$ ��� �����, ��� $N\log N$ � ������� ����������. 
�� $N$ ������� �� ������ ����� �������; $N$ ������� ������ ���������!

� ����������������� ������� ����� ���������� ��������� �����-���� ����� 
����������� ����������, ��� ��� ����� ����� ������ ����������� 
�������������. �� ������ ���������������� ��� � ����������������� 
������������� ������������ ����� ���������� ��� �������������� 
������������� ����������� ������, ��� ����� ���������� ��� 
�������������� �������; �������������, ����������������� ���������� 
����� ���� ��������� �� ���� �������� (��.~�.~5.4.7, � ����� ���.~17).

��, ��-��������, ������������ ��������� ���������� ������ ���� ��� ����,
 ����� ��������� ����� ������ ����������! ���� �� ������ ����������� 
��������� �������� �������� �������������� ���� ������� �.~�.~䋎����, 
������� ����� ������������� ������ ������� ��� ����� �������, ���������,
 ����� ����������� ������ � �������� ����� 
[Complexity of Computer Computations (New York, Plenum, 1972), 105--109].

��������� 䋎��� ������ �������, ���������������� ��������� � ������, 
��� � �.~5.4.8; �� ���� ��� �� ����� ����� ������ ������ �����, 
�������������� ����� ���������, � �� ���������� ����������. (����������� 
����� \emph{���������} �� ������ ������������ ���������� ��������� 
�������������� � ����������� ������ �������, ��� ��� ���� ��������� 
���������� ���� � ���� � ������� �� ����; ������ ������� �� ������� ������,
  � �� ������������� ��������� ����������� ���������, ����� �������� 
�������� ����.)
%% 446
����� ������������ ������� "���������� ��������"
$$
F(n)=\sum_{1<k\le n}(\ceil{\log_2 k}+1)=B(n)+n-1
=n\ceil{\log_2 n}-2^{\ceil{\log_2 n}}+n,
\eqno(19)
$$
��� $B(n)$ ���� ������� "�������� �������" (��. ������� (5.3.1-3)). 
ᎃ����� (5.3.1-33), ������� $F(n)$ ���� �� ��� ����, ��� ����������� 
����� �������� ���� ��������� ������ � $n$~��������, �  
$$
n\log_2 n\le F(n)\le n\log_2 n+0.0861n.
\eqno(20)
$$
  ��� $F (n)$ ������� � ������������� 
�������~$F(n)=n+F(\floor{n/2})+F(\ceil{n/2})$, �� �� �����~C
$$
F(n)\le F(k)+F(n-k)+n \rem{��� $0\le k\le n$.}
\eqno(21)
$$
풎 ����������� �������� ����� �� ������������� $F$ � ���� ����� �������� 
����; � ���������� ��� �������� �������� ������.

��� � � �.~5.4.8, �� ����� ������������, ��� ���� ������� $b$~�������, 
������ ���� ������� $c$~������� � ������� $n$~������. ����� $s_{ij}$---����� 
�����, ����������� � ������ ������ �� �����~$i$ � ����������� ������� �� 
����~$j$. �� ����������� 
\emph{������ ������������} ������ ������������ ����� � ������ 
����~$\sum_{1\le i,j\le n} F(s_{ij})$.

�����������, ��������, ��� $b=c=n=6$ � ��� ������������� 36~������� 
��������� ������� ������������ ����� �������:
{\obeyspaces
$$
\vbox{
\line{\tt\indent \]\]\]\]\]\]}
\line{\tt\indent 123456 123456 123456 123456 123456 123456 \hfill \rm (22)}
}
$$
}
���� ���� � ��������� �� ����� 1; "\]" ���������� ��������� �����. �� 
������ ����� ��������� �������, ����������� ������� �� ������������ ����,
 ������� ��������~$s_{ij}$. �����~1 � ������ ������������ �����~0. ���� 
������ ���� ������� 6~������� �� ����~2, �� �� ������� ������������
{\obeyspaces
$$
\vbox{
\line{\tt\indent        123456}
\line{\tt\indent \]\]\]\]\]\] 123456 123456 123456 123456 123456 \hfill 
\rm (23)}
}
$$
}
� ������ ������������ ������ ����� $6F(0)+24F(1)+6F(2)=12$. ��������, 
���� ��������� |1|, |1|, |2|, |3|, |3|, |4| �� ����~3:
{\obeyspaces
$$
\vbox{
\line{\tt\indent               112334}
\line{\tt\indent \]\]\]\]\]\] 245566 123456 123456 123456 123456 \hfill 
\rm (24)}
}
$$
}
%%447
������ ������������ ���������� �� $4F(2)+2F(3)=18$. ����� ������ ������� 
����� � ����� ������ ��������� � ������ ����� ����������, ������� 
������������ ����� $6F(6)=96$.

䋎�� �������, ��� ������ ������������ ������� �� ������������� ������, 
��� �� $b+c$ �� ���� ���������, ��� ��� ��������� �� $s$~����� � ������ 
�����������, ����������� � ����������� ���������� ��������~$s'$, 
����������� ������ �� $F(s+s')-F(s)-F(s')\le s+s'$.  �� �������, ����� 
��������� ���������.

\proclaim ⅎ����~F. ����� $t$---������������ ���� ������ ������������ 
���������� ������������ �����. ���� ������ ������� �� ������� ����
$$
\ceil{(nF(c)-t)/(b+c)}
$$
���������, ����� ��������� ���� ����� � �� ����� ����������.\endmark


ᔎ��������� ���� ��������� ������������� � ������. ��������, ������� 
$N$~������� �� $B$ � ������ �����, � �����������, ��� �� ���������� 
������ ������������ ���������� $M$~�������. ��� ������ ������ � ����� ���� 
���� ����������� � ������, � ��� ������ ������ ���� ���� ���������� �� 
����, � $s_{ij}$ ���� ����� ������� � �����~$i$, ������������� 
�����~$j$. ���� $N\ge B^2$, �� ���������� ��������� ������������, ��� 
�������� ��� $s_{ij}\le 1$, �, �������������, ��� �������������� 
������� ���������� ��������� �� ������� ���� 
$(N/B)F(B)/M\approx (N \log_2 B)/M$~������. (���� $B$ ������, �� 
���������~$\log_2 B$ ������ ��� ������ ������ �������������, �� ���� $B=1$,
 �� ������ ������, ��������, ����� ��������.)

\excercises
\ex[M22] � ������ ����������� �����, � ������� �������� ������� 
����� ��������, ��������� ��� ������ ����~$x$ �������, ����������� 
�~${1\over2}$ 
��~${1\over2}(1-x^2)$~��������. 풎 ���������� ��������� �����, ����� 
������� ���� ��������� �������. ������ ��������������� ����������� ����� 
��������, ���� ������� \emph{���} ��������� �������, ����������� �� 
$180^\circ$ (� �������������, ��� � ����� ������ ������ ����� ���������� 
������ ���� �� ����������)?

\ex[M30] (�.~�.~�������.) 態� ���� ������---�����������, �� 
����� ���������� ������ ������������� ��������� ������� �� ����� ������� 
������, ������������� "������������" � ��������� ��������, ������� 
$P$~������, ������ �� ������� �������� $L$~������ �������, � �����������,
��� ������ ���� ������� ����� ��������� �� ��������~1, ������---�� 
��������~2 � �~� ��������� ��������� ������� �� ����� ������� ��������� 
������������� ������� ��������� ������ ������� �����; �������������, 
����� ���������� �������� ��������� ��������, ������� ��� ��������������
%%448
�������������. ���������� ��������� �� $PL$ ������������� ���
$$
\matrix{
(a_{11},1) & (a_{21},1) & \ldots & (a_{P1},1) \cr
(a_{12},2) & (a_{22},2) & \ldots & (a_{P2},2) \cr
\vdots & \vdots & & \vdots \cr
(a_{1L},L) & (a_{2L},L) & \ldots & (a_{PL},L) \cr
}
$$
��� ��������� $\{\, a_{ij} \mid 1\le i\le P, 1\le j\le L\,\}$ 
������������� ��������� ����� $\{\,1, 2, \ldots, PL\,\}$ � ��������� 
������� � $a_{ij}<a_{i,j+1}$ ��� $1\le j<L$ (������ ������������ ��������, 
�������---�������� �����). ����������� ���� �� �� ������ �����������, � 
����� ������������ ������������������� ����� $(1, j_1)$ $(2, j_2)$ \dots{} 
$(PL, j_{PL})$. ��������, ��� ���� ��� $(PL)!/L!^P$ ��������� 
�������~$a_{ij}$ �������������, �� ������� ��������
$$
\abs{j_2-j_1}+\abs{j_3-j_2}+\cdots+\abs{j_{PL}-j_{PL-1}}
$$
�����
$$
(L-1)\left(1+(P-1)2^{2L-2}/\perm{2L}{L}\right).
$$
[\emph{㊀�����:} ��. ���. 5.2.1-14 ] �������, ��� ���  $L\to\infty$ ��� 
�������� �������������� ����� ${1\over4}(P-1)L\sqrt{\pi L}$.

\ex[�15] �����������, ��� ������������ ������ ���������� ������ ������ 
������������� $10\hbox{-�������}$ �������. ��� ����� �������� 
������������ ����������� (3), (4), (5), ����� $A_1(n)$ ����� ����������� 
���������~$\alpha D(\cJ)+\beta E(\cJ)$ ����� ���� ��������~$\cJ$ � 
$n$~��������, �� ������� ����� �������, ������� ���~9?

\rex[�21] (a) �������� �������, ����������� (2), ��� ������� ���������� 
$P\hbox{-��������}$ ������� $L$~�����, ���� ������������ �������������� 
����� ������������� ������������� �������%
\note{1}{�. ����� ������� (9).---{\sl ����. ���.\/}}: ��� $P$~������� ����� 
������ ����� ������ �����, � ������ ������ ������ ������� ������� ���, 
����� �������������� ����� ������.

(b) ��������, ��� ���������� � �������~K ����� �������� ���, ��� 
��������� ����� �������, ������� ����� ����������� � ������ ����� 
������� �� �����~(a).

\ex[�20] ���� ������������ ��� �����, ������ ������ � ������ ����������� 
� ������� �� ������, �� �� �� ����� ��������� ����� �������, �������� 
�������������� �� ���.~93, ��� ��� ��������� ������ ��������� �� ������ 
�������, � ������ �� ��������. ��������, ��� �������� ���������� � 
�������~K, ����� ���������� ����������� ������� � ������ �����������, 
��� ��� ������ ��������� �� ������ ������� ��� ��� �� ��������.

\rex[22] ������� ������, ����������� � ������ ���.~6, ����~$n=23$ 
�~$\alpha=\beta=1$. (��������, � ��� �������� ������� ���������� � ������ ���.)

\rex[�24] ���� ����� ��������� �������� �� �����, �� ��������� 
����� ������� (� ������ �������~H) ������������ $\alpha D(\cJ)+\beta 
E(\cJ)$, ��� $D(\cJ)$ �~$E(\cJ)$ ������ ������������ ����� ���������� 
����� �����: ������� ����� ������ ������������� ���� $w_1$,~\dots, $w_n$ 
(��������������� ������ ��������� ��������), � ����� �������� � ����� 
����� ���������� �� ��������������� ����. ��������, ���� $\cJ$---������, 
�������������� �� ���.~92, �� 
������� $D(\cJ)=6w_1+6w_2+7w_3+9w_4+9w_5+7w_6+4w_7+4w_8$, 
$E (\cJ)=2w_1+2w_2+2w_3+3w_4+3w_5+2w_6+w_7+w_8$.

��������, ��� ��� ��������� $k$ ������ ���������� ����������� �����, � 
������� ������� ��������� $k$ \emph{����� �������� ��������}.

%%449

\ex[49] ᓙ�������, �� ��������, ������� ��� �������� $\alpha$, $\beta$ � 
�����~$w_1$,~\dots, $w_n$ ������� ����������� � ������ ���.~7 �������, 
���������� ������ $O(n^c)$~����� ��� ���������~$c$?

\ex[M49] (苞������� � �������.) ����� ��, ��� ��� ���� $n$, $\alpha$ �~$\beta$
���������� ����������� � ������ �������~H ������� � $n$~��������, � 
������� ��� ������ ��������� ����� ������� �� ���� �������� �������? 
���� $\alpha$ �~$\beta$ �����������, ���������� �� ����� $m$, �����, ��� 
��� ���� ���������� ������� $n$ ����� ����� $A_1(n)=\alpha mn+\beta 
n+A_m(n)$? (��� ��� ������������� ���� ��������� � ������~$\alpha/\beta\ge 4$.)

\ex[��49] ������ ��������������� ��������� $A_1(n)$ ��� $n\to\infty$ 
��� �������� $\alpha$ �~$\beta$?

\ex[�29] � ������������ (11) �~(16) ��������, ��� $f_m(n) + mn\ge 
f(n)$ ��� ���� $m$, $n\ge 2$, � ���������� ��� ���, ��� ������� ����� 
����� ���������.

\ex[25] ��������, ��� ��� ���� $n>0$ ���������� ������ � $n$~�������� � 
����������� ������ ���������� ���� (11), ��� ������ �������� ����������� 
�� ����� ������.

\ex[M24] ��������, ��� ��� $2\le n \le d(\alpha,\beta)$ ������������ 
��������� ������ ������� � ������ �������~H �������� $n\hbox{-�������}$ 
�������. 
(�. � �������� (17).)

\ex[40] ��� ������������� ������������� ������ ������������� ������� ����� 
������ ��� -����� ������� �� ���.~92 ����� ���������������
$(\sqrt{2}+\sqrt{4}+\sqrt{1}+\sqrt{1}+\sqrt{8})^2
+(\sqrt{1}+\sqrt{1}+\sqrt{2})^2+\sqrt{1}+\sqrt{2}
+(\sqrt{1}+\sqrt{4})^2+(\sqrt{1}+\sqrt{1}+\sqrt{2})^2$; 
��� �������� ������������ ����� �����
������� $(\sqrt{n_1}+\cdots+\sqrt{n_m}+\sqrt{n_1+\cdots+n_m})^2$ �� ���� 
���������� �����, ��� ���������� ���� ����� ����� 
$(n_1, \ldots, n_m)$~�������. 
�������� ��������� ��� ���, ������� ��������� ������� � 
����������� �������� ������, ������� $1$, $2$, $3$, \dots{} �������, 
��������� ��� ������ ������� ������ ��� �������.

\ex[M22] ��������, ��� ����� ��������� ������� �������~F, ���� 
���� ������������� ���� � ���� $nF(c)\ne t$: � ���� ������ ���������� �� 
����� $\ceil{(nF(c)+b-t)/(b+c)}$~���������.

\ex[23] (�.~�.~䋎��.) ������� ������ ������ �����, ����������� ���� ����� 
��~(22) � �� ������ ���������� ��~12 ��� ������� ����� ���������. (�~(23) 
�������� ��������� ����� �����, � �� ����� ���� ���������.)

\ex[25] (�.~�.~������ � �.~�.~���-������, 1971.) ���������� ��������� 
����� � ����������� ������, �������������������� �� ������� ����� � 10 �������:
\medskip
\item{a)} �������� ����: $(50, I_0)$ $(08, I_1)$ $(51, I_2)$ $(06, I_3)$ $(90, I_4)$ $(17, I_5)$ $(89, I_6)$ $(27, I_7)$ $(65, I_8)$ $(42, I_9)$.

\item{b)} 䀉� ������: $(50, 0)$ $(08, 1)$ $(51, 2)$ $(06, 3)$ $(90, 4)$ $(17, 5)$ $(89, 6)$ $(27, 7)$ $(65, 8)$ $(42, 9)$.

\item{c)} ��������������� (b): $(06, 3)$ $(08, 1)$ $(17, 5)$ $(27, 7)$ $(42, 9)$ $(50,0)$ $(51,2)$ $(65, 8)$ $(89, 6)$ $(90, 4)$.

\item{d)} ������������ ������� ������: $(3, 3)$ $(3, 9)$ $(2, 1)$ $(2, 5)$ $(2, 7)$ $(2, 8)$ $(1, 0)$ $(1, 2)$ $(1, 4)$ $(1, 6)$.

\item{e)} ��������������� (d): $(1, 0)$ $(2, 1)$ $(1, 2)$ $(3, 3)$ $(1, 4)$ $(2, 5)$ $(1, 6)$ $(2, 7)$ $(2, 8)$ $(3, 9)$.

\item{f)} (a), �������������� �� ������ � �������������� (e):
\itemitem{� 1:} $(50, I_0)$ $(51, I_2)$ $(90, I_4)$ $(89, I_6)$.
\itemitem{� 2:} $(08, I_1)$ $(17, I_5)$ $(27, I_7)$ $(65, I_8)$.
\itemitem{� 3:} $(06, I_3)$ $(42, I_9)$.
\item{g)} ��������� ������ � ���������� (������� �������� ����~3, 
����� ����~2, ����� ����~1): $(06, I_3)$ $(08, I_1)$ $(17, I_5)$ $(27, I_7)$ $(42, I_9)$ $(50, I_0)$ $(51, I_2)$ $(65, I_8)$ $(89, I_6)$ $(90, I_4)$.
\medskip
\noindent ������ ������ �� ����~(d) ������������� ����� ���������� �~(�) 
\emph{������ � ���������� ������ ������ � ���������} ������� �� ������ ����������.
%%450
����� �����---��� ����� �������. � ����������� ������� ������������ ����� � 
���������� ������ � ����� ���������� � ������; ��� ������ � ���������� 
�~(d) �~(g) ������ �������������� ���������� ������ ������ ������. �������,
 ��� ���������� ������ �� ����������� �����������.

��������, ��� ���� ����� ����� �����������, �. �. ��� ����� � ���������� 
� (g) �������� ���� ���� �������. (풎� ����� ��������� ����� ������, 
��������� ������� ����������� ������ ����������� �������������, �������� 
���� �������� ������ ��� � ������� ������� �����������.)

\rex[25] ��������� ������� ������������� ������������� 
\emph{����������� ������:} ����� ������ ���������, ������ �� �������������,
 ��� ������� ����� ������� ���������� ������, ��������� �������� ��� 
������. 풀 ������ ��������� �� ��������, � ���� �������� �� ��� 
������������� ��������� �� ���������� ������ � ����� ������ �������, 
��������� �� �������� �� ������ ��� ���������. ������������ �� ����� 
������� �� ��� ��� �����������, ��� ��� ������� ���� ��� ���� ���������: 
����� �������� ������������� ���������� � ������, ����� ��� �����.

����� ����������, ��� ��������� ����������� ������ �������� � ��������� 
������� ������� ����������, ��� ��� ��� ������ ����� ���� ��������� 
������ � ������� �������, ������������� ��� ���������� 
����������. ��������� ��� ��������. ������ ���������� ������������� ����� 
������� ���������� ����� ��������� ����� ���������� ����� ������� 
�������� ������� � ������ ���������� ����������?


\subchap{१. ����� � ����������} % 5.5
⅏���, ����� �� ����� �������� ����� ���� ����� ������� �����, ����� 
"�������������" �������� ������ ����� �� ����� ���������.

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

\emph{���������� ����������} ������������ � ��� �������, ����� ��� ������ 
���������� � ������� ���������� ������ ������. �� ������� � ������ 
�������� ����������� ����� ���� �������� ���������� ���������� ����������, 
�� ���, ��������, ���� �� ���� ���������, ���� �� �� �� ����� ��� ����� 
��������� �������� � ���� ������! �������� ���� ���� ������� ���� �������� 
�����������������. �� ������ ����� ���� ������������ 
�����������---��������� �� ���� ������, ����� ����� ������� ������������ � 
��� ��� ���� ���������� ��������.

���� �� ���������, ���� �� ������ ���� ��� ��� ������ ���������� 
������������ ��� ��������� ��������������� � ���������� ��� ������������ 
������. �� ����� �� ���� ������ ����� ����� ���� �����������, ������ ��� 
�������� �����������. ��������, ����� �������� (��������~5.2.2�) �� ����� 
���� ���������� �����������, ��� ��� ������ ����� ����� ������ ������ 
������� ��, ��� �� ������; �� ���� ���� ����� ����� ���������������� 
��������� ����������� �������� ��� ���������� � ����� ������� (��. 
�.~5.4.8). ����, �������� � ����������, ��� ����� ��� ��������� 
����������� ����, ����� � ��� �������, ��� ��� ���������� ����������, � 
������� ��� ����������� ������ ��������.

� ��������� ������� ������ ���������� �������� ������� �������� ������ 
���������� ���������� ����������, � �������� �� �����������. (��� ������,
 $N$ �������� ����� ������� � �����.)

%%452

1. {\sl �������������� �������.\/} ��������~5.2D ����� �������, ���� 
�������� ������ �������. ����� �������� (�� ���������� ������� ������� � 
������� �������), �� ��������� ������ ��� ��������� � $2N$~�������. ���� 
�� �����������, ���������� $N$ �� ���� ������� ����� ������������, 
����������� � ���. 5.2-13.

2. {\sl ������� �������.\/} �������� 5.2.1S �������� ����� 
��� ����������������, �� ������� ��������������� ������������ � ������ 
���������� ��� �����~$N$ (������, ��� $N\le 25$). ��� �������~$N$ �� 
���������� ���������� ���������, ���� ������ �������� ������ �� �������� 
����� ����� ��������������.

3. {\sl ᎐������� � ��������� �����.\/} �������� 5.2.1D (����� 腋��) ��� 
�� �������� ������ ���������������, ���������� ����������� ����� ������ � 
�������� ���������� ��� �������� �������~$N$ (������, ��� $N\le 1000$).

4. {\sl ������� � ������.\/} �������� 5.2.1L ������� �� ��� �� ����, ��� � 
������� �������, � ������� ������� ������ ��� ���������~$N$. ��� � � 
������ ������� ���������� �������, � ��� ��������� ��������� �� �������� 
���������� ��������� ����������� ������� �������; ��� �������� ������, 
����� ������ ����� ���������� ����� ��� �������� ������ ������ �������� ������.

5. {\sl ᎐������� � ����������� ������\/} ����������, ���� ����� 
 ����������� ���������� (������ ������������) ������ �������������; 
���������� ���������� ����� ������� �������� \emph{������� � ��������� �������}
(�������� 5.2.1�) � ��������������� ����������� ���������� �� 
��������� ��������� (������������� � ����� �.~5.2.5). ��� ���������� 
������ ���������� ����� $O(\sqrt{N})$ �������������� ����� ������.

6. {\sl �������� ���������� �� ��������.\/} �������� 5.2.2� (����� 
�������) � ����������� ��� �������� \emph{�������� 
����������} (���.~5.3.4-10) �������, ���� ����� ������������ 
��������� ������� ����� ���������.

7. {\sl �������� ���������� � �����������\/} (����� 厀��, 
������ ��������� ��� \emph{������� ����������}). �������� 5.2.2Q, ��������,
 ����� �������� ������������� �������� ���������� ����������, ��������� 
�� ������� ����� ���� ������ � ��������� ����� ����������� �� �������� 
������� ���������� �� ����������� �������������� �����. ������ � 
��������� ������ �� ����� �������� ����� ��������. �������, ���� 
����������� ����������� ������ ���������� ������, ���������� 
��������� �������� ����������� �������. ���� ���������� ������� �� ���� 
��������� (��� ������������ � ���. 5.2.2-55), �� �����
%%453
���������, ��� � ��������� ������, ���������� ������ ������������� �, 
����� ����, ��������� ����������� ������� ����� ������.

8.~{\sl ������� �����.\/} ��������~5.2.3S �������� ����� � �������� 
�������� � ������, ����� ������� ����������� ������������ ��� �������� 
������ ����������� �������� � ������.

9.~{\sl ������������� ����������.\/} ��������~5.2.4� ��� ����������� 
����������� ������ ������������ ���������� ������� �������� ����������; 
��� ������� ����� ������, ��� � ������������ ����� �������� ����� ������ 
�������� ������� ������� ����������.

10.~{\sl  ወ���� �������.\/} ��������~5.2.4L ������������ ���������� 
�������, ��� �������, ��� �� ��� � ��� ������������� ����������, 
�������������� ������ ������� �������� ���� � ��������� ������, ����� 
����, ���� ����� �������� �� ��������� � ������ ������.

11.~{\sl  ����������� ���������� � �������������� ���������\/} 5.2.5R---��� 
�� ��� ����, ��� ���������� �������, ������� ��������� ��� ������, ���� 
����� ��������, ���� ������� ��������� ������� ������������������� 
���������. ������ ������ ����� ��������� �������������� ������� 
(�����~1 ������ ������); ����� ��������� ��������� ������������ ��� 
$2N$~������� � ��� �������, ���������, �� ��������� �������� ����������� 
����� ��� �������� ������ ��� ������������ ���---"������������� �����", 
������� ����������� ����������. (\emph{���������������.} ����������� 
���������� �� ������� ������������ ��� �����~$N$.)

12.~{\sl  ᎐������� ��������� � ��������\/} (��.~�.~5.3.1) 
�������� ��������� ��� ����� �����~$N$ � "�������������" 
����������. ��������, ���� ����� �������� �� ���������� � ��� 
�����������, ��� ��������� ����������� ����� ����� �� ���� ��� 
����� �������.

13.  ����� ������������ � ��������� ������, ������������ ���� ��� ����� �� 
����������� ���� �������. ��������, �������� ��������, ����������� ��� 
������� ����������, ����� ����������� �������� � ���������.

14. � �������, ��� ���������� ����������� ������, �������������� � 
������ � ���.~5.2.1-3, ���������, ��-��������, ���������� �� ��������� 
�������� ����������. �� ������� ����� ������ ����� ��������� 
���������������~$N^3$, �.~�.~��� ����� ��������� ��������� ���������� � �����!

���������������� � ��������� �������������� ������ �� ���� �������, 
������������������� ��� \MIX, ������� � ����.~1.
%%454
\picture{ ���� 1, ���. 454}
����� ����� � ����, ��� ����� � ���� ������� �������� ���� ������� 
������������ �������������� ������� ����������. ��� ��������� ������ � 
����� ���, � �������������, ���������� �������� ������, ������ �� ��� ���� 
�������� ��������� ����������. ᐀���������� �������, �������� ����, 
����������� �� ������ �������, �� �� �������� ����� ���� �������,
 ������� ������ �� � ���������� �������! ⅌ �� ����� �������� � ������� 
������ ��������� ������� ���� �� ������� ��������, ������� ������� ������� 
�� ������� ��������� ��� ���������� ������� �� ������ �����, ��� ��� 
\MIX---�������� �������� ������.

ᒎ���� "������������" � ����.~1 �������� ��������� ���������� � 
���������� ��������������� ������, ������������ ������ ����������, � 
�������� ����� ������. ����� ������~$\varepsilon$ ���������� ���� ������, 
��������� ��� ������ ���� �����; ���, ��������, $N(1+\varepsilon)$ 
��������, ��� ����� ������� ������������ ��� $N$~������� � $N$~����� �����.

� ��������������� ������� � ������������ ��������, ������������ � 
����.~1, ����������� ������ ������� �����, ������������ ��� �������~$N$ � 
������������� ��������� �������� ������; $c$~���������� ������������ 
���������. 품 ������� ����� ������ ������ � �����������, ������� 
������� ����� ����������� ����� ������ ��������� ��� ���� ���������� 
������������������� �������� ������. ዓ��� $N=16$, ��������� � 
����������� ������, ��� ����� ������������ � �������� \S~5.2, � ������ 
$N=1000$ ��������� � ������������������ $K_1$, $K_2$,~\dots, $K_{1000}$, 
������������ ���������
$$
K_0=0; \quad K_{n+1}=(3141592621K_n+2113148651)\bmod 10^{10}.
$$
��� ��������� ������������� ������� ���������, ��������������� � �������,
 �������������� ������ "������������������" \MIX-���������, ����� � ������ 
������������������, ������������ � �����������. ������ ����� ��� 
���������� ���� �������� ������ ������ 100.

��� \emph{������� ����������} ���������� ������, ������������ �� ������� 
���������� ����������, ������ ��� � ���� ������ �������������� 
������������� ������������ ������� �������� ������ � ������� �������� 
��������� ���������� ������� �����/������. � �.~5.4.6 ��������������� 
���������� ������, �������� ��� ��������� ����������, � � �.~5.4.9 
����������� ������������� ������ � ���������.

�������, ����������---�� ������������ ���������� ���� �����. ������� �� 
������ ����� � ���, ��� �������� �� ����������� ������, ��� ���������� � 
������� ������� � ��� ������������� ���������, �, ��������, �� ������ 
�������� � � ���, ��� ��������� ����� ���������.
%%456

\section ������ ����������. ����� ��������� ����������� ������� 
���������� ���������� ��� � 19-�~��������, ����� ���� ���������� ������ 
������ ��� ����������. � ᎅ�������� 蒀��� �������� ���� ������� 
���������� ������ 10~���, � ��� � 1880~�. �������� ��������� �������� �� 
������ ������ �������� ����� ����� ������; � � ����� ����, ����� �������� 
(� ������� �� ����� ��������� � �����) � 1880~�. � �������� �����������, ����
\picture{���. 94.  ������ 压������. (䎒������� ������� ������������� 
������� IBM.)
}
��� �����������, ���������� ���� �������. ������ 压�����, �������������� 
�������� ���� ��������, ������� ���������� ������������� ���������, 
���������� ������ ����� ����������, � ����� 100 ��� ����� ������� 
�������������� ��� ��������� ������� �������� 1890~�.

�� ���.~94 ��������� ������ ������� 压������, ���������� � �������� �� 
�������������� �������. ��� ��� �������� ������� ������������ 
"�������������� ����" ������, ������� ������ �  ����� �������� �������� �� 
26 ���������� ���������. �������� ��������� ���������� ������� 
$6{5\over8}\times3{1\over4}$~������ � "�����" � �������� ��������; ��� 
�������� � ����, ��� ������������ �� �������� ����� �� ������� ������ � ���
%%457
\bye