\input style
%% 562
�����, �� ����� �������� 20. � ���� ��������� ������ �� "��������" �� 7 
����� � ������, ��� �������� ��������� �� ���.~29, � ���� � ������ ������ 
������� �������� ���� ���� ��������, �� ����������� �������� � ��� ���� 
������ ���������, �. �. ����� ��������� � ��� ����!

㐓�������� ����� � ��������, �� ��������, ����������� �������� ������� � 
��������, ��������������� � ������ ��������-���� �� 8 �����. 呋� 
��������� �������� ������� ��������, ��������������� �� 128 ����� ����� 
������� ��������� � �����, �� ����� �������� ��������� ���� � ������� 
�� �������� ���������, ���������� ���� ��� ��������. 쎆�� ��������� 
������� �������� �������� �� ���������� ������;
����� ����������� ���� ��� ��������� � �����, ���� � ����� ������ 
������� �� ���������� ������ ����� �� ����� 254 ������.

����������, �� ������� ������ �������� ����� ��������, ��� ��� ������� 
���������� ������ ���������� � ������ ������� �������� �������� ������ 
�������. ��������, ��������, ��� ������ ��������, ����������� 
������������ �� $m$ �����, �������� $72.5+0.05m$ ��. ␅�� �� ���������� 
��������� ������ �������� �������� ����� $a+b\log m$ ��, ��� $a$ ���� �� 
��������� � $72.5$, ��� ��� ������ �����, ����������� �� ����� � ������� 
�������, �������� ��������������� $\log N$, ����������� ��
$$
(72.5 + 0.05m)/\log m +b.
$$
��� �������� ��������� �������� ��� $m\approx350$; � ���������������� 
���� ������� ����� "�����". 獀�����, ����� ������� � ������������, 
����������� ��� $m$ ��~200 ��~500. � �������� ��������� ��������� 
��������� ������� �������� $m$ ������� �� ������������� ������������ 
������� ������������ ��������� � �� ����� ������� � �������.

�. �. 뀍����� [{\sl IEE Trans.\/}, {\bf EC-12} (1963), 863--871] 
��������� ������� $m$-����� ������� ��������� �������: ��������� ���� 
�� ������ $l+1$, ���� ���� ������� $l$ ����� ��������. ��� ����� ������� 
�������� ������� ������� ���������, ��� ��� ��� ������� ������ ������ 
�������� ����� ������������� ������������� ����������� ������; 
뀍����� ������� �� �������������, ��� ����� ���������� 
����������� ������� ���� ������� � ��������.

呋� ���� �������� �� ����� � �������� �������� ������������ ������ 
������� � ��������, �� ��� ��� ������������� �������� ������������� 
������, ��� ������ ������� ������������ ����������, ����� ������� ����� 
��������������, ��������� ������� ������������ ���������� 
��������������� ������� �� ���� ��������, � ������ ������� �������� ����������
%% 563
������. 򀊎� ����� ���������� \dfn{��������-����������������} 
������������ ����� [��. {\sl JACM\/}, {\bf 16} (1969), 569--571].

�. 잍� � �. 󇃀��� [Proc. Princeton Conf. on Inf. Sciences and Systems, 
4 (1970), 345--349] ���������� ����������� ��������� 6.2.2�, ��� ��� 
������� ��������� ����, ������������� ��� �� ��������, ��� � �� 
�������������� (���� ������ ��� ��������); ���� �������� ��������� ������, 
��������� ����� �������� (���� ������� �������).  �������������� 
���������� ������� � ��������� ������� ����������� ������ ������� 
����� ���������, � �����, ��� ����� ��������, ����������� 
����� $H_N/(H_m-1)$, ��� ���� �������� ������ ����� ��������� � ������ 
���������� ���������� $m$-������ ������ (��. ���.~10).

\section B-�������. � 1970~�. �. ᝉ�� � �. 쀊-ꐝ�� 
[{\sl Acta Informatica\/}, (1972), 173--189] 
� ���������� �� ��� �������� � �� �� ����� �. ꀓ���� [��������������] 
���������� ����� ������ � �������� ������ ����������� ������ ���������� 
��������. � ���� ������������ �� ����������� ������ ���� �������� ������,
 ��������� \dfn{B-���������}, � ��������� ����������� ����� ��� �������� 
������� ���� � "���������������" �������������� � ��������� ������, 
��������� ��� ���� ������������ ������� ���������.

\dfn{B-������� ������� $m$} ���������� ������, ���������� ���������� ����������:
\medskip
\item{i)} ꀆ��� ���� ����� �� ����� $m$ �������.
\item{ii)} ꀆ��� ����, ����� ����� � �������, ����� �� �����
$m/2$ �������.
\item{iii)} ꎐ���, ���� �� �� ����, ����� �� ����� 2 �������.
\item{iv)} ⑅ ������ ����������� �� ����� ������ � �� ��������
����������.
\item{v)} 텋������� ���� � $k$ ��������� �������� $k-1$ ������.
\medskip
\noindent (ꀊ � ������, ����---�������� ����, � ���� ��� ����������. � 
��� ������ �� �������� ����������, �� ����� ������������� ��� ������� 
����, ������� � ���������������� ��� � ������, ��� ��� $\NULL$---��� 
��������� �� ����.)

� ���.~30 �������� B-������ ������� 7. ꀆ��� ���� (����� ����� � 
�������) ����� ��~$\lceil 7/2\rceil$ ��~7 ���������� � �������� 3, 4, 5 
��� 6 ������. ꎐ����� ���� ����� ��������� ��~1 ��~6 ������ (� ������ 
������ 2). ⑅ ������ ��������� �� ������� ������. 瀌�����, ��� (a) 
����� ����������� � ������������ ������� ����� �������, ���� 
������������ ������������ ��������� ������� ������������� �������, � 
(b) ���������� ������� ����� �� ������� ������ ���������� ������.

B-������� ������� 1 �~2, ��������, �����������; ������� �� ���������� ���� 
������ $m\ge 3$. 瀌�����, ��� (3-2)-�������,
%% 564
\picture{���. 30. B-������ ������� 7}
%% 565
������������ � ����� �.~6.2.3, �������� B-��������� ������� 3;
� �������, B-������ ������� 3 ���� (3-2)-������.

󇅋, ���������� $j$ ������ � $j+1$ ����������, ����� ����������� � ����
\picture{󇅋 B-������}
��� $K_1<K_2<\ldots <K_j$, � $P_i$ ��������� �� ��������� ������, ������� 
$K_i$ � ������� $K_{i+1}$. 񋅄���������, ����� � B-������ ��������� 
�����������: ����� ���� ��� ���� (1) �������� �� ���������� ������, �� 
���� ������ �������� ����� ������ $K_1$, $K_2$, \dots, $K_j$. ( ������� 
$j$, ��������, ������������ �������� �����, � ��� ����� $j$ ��������� 
����� ���������������� �����.) 呋� ����� ������, ������ ���� ������; 
���� ����� �������� � ���� ����, ��� �������� ����� ����� $K_i$,
 �~$K_{i+1}$, �� "�����������" (�������� � ����������� ������) ����, 
��������� $P_i$, � ���������� �������. 󊀇����� $P_0$ ������������, 
���� �������� ������ $K_1$, a $P_j$ ������������, ���� �������� ������ 
$K_j$.  $P_i=\NULL$ ����� ��������.

������������ ������ B-�������� �������� �������������� ��������, � 
������� ������������ �������. ����������, ��������, ���.~30; ������ ���� 
������������� ����� ��������� �������. 呋� ����� �������� ����� ���� 
$337$, �� ������ ������ ����
\picture{⑒���� � B-������}
� ������ �������, ��� ������� �������� ����� ���� $071$ �� ������������, 
��� � ��������������� ���� ������ 2 ��� �����---�� ��� "�����". ��� 
��������� ����� ����������, �������� ���� �� ��� ����� �� ��� ����� � 
������ � ������ ������� ���� �� ������� 1:
\picture{����������� ���� ��� �������}
%% 566 

⎎���, ���� ����� �������� ����� ������� � B-������ ������� $m$, ��� 
������ �������� ����������� �� ������ $l$, ����� ���� ��������� � 
���������� ���� ������ $l-1$. 呋� ���� ������ �������� $m$ ������, �. �. 
����� ��� (1) � $j=m$, ��� ���������� �� ��� ����
\picture{����������� ����: ����� ���}
� ��������� ���� $K_{\lceil m/2\rceil}$ � ����-����. (򀊈� �������, 
��������� $P$ � ��� ���������� ������������������� $P$, $K_{\lceil 
m/2\rceil}$, $P'$.) ��� ������� � ���� ������� ����� �������� � 
����������� ����-����. (�. � ���.~27, ��� ��������� ������ $m=3$.) 
呋� ����� ��������� �������� ����, ������� �� ����� ����, �� ������ 
������� ����� ������ � �������� � ���� ������������ ���� $K_{\lceil 
m/2\rceil}$, � ����� ������ ������ ���������� �� ������� ����.

������ ��������� ������� ��������� ��� �������� B-��������; ����� 
������� ��� ������� ����, �������� ������ ��������� ���.~1. 瀌�����, 
��� ������ ����-������ ������ ����� �� ������� �����, � �� ���� �� ������ 
�����, ��� ��� ������������ �������, ��������� ������� ���� 
������,---����������� �����.

󄀋���� �� B-�������� ���� �������� ������� ������� (��. ���.~7).

\section 【������������ �������������. ����������, � �������� ����� ����� 
����������� ��������� � ��������� ������ ��� ������ � B-������ ������� 
$m$. ��������, ��� ������� $N$ ������, � �� ������ $l$ ����������� 
$N+1$ �������. 򎃄� ����� ����� �� ������� 1, 2, 3, \dots �� ����� 2, 
$2\lceil m/2\rceil$,  $2\lceil m/2\rceil^2$, \dots; �������������,
$$
N+1\ge 2\lceil m/2\rceil^{l-1}.
\eqno (5)
$$

荛�� �������,
$$
l\le 1+\log_{\lceil m/2\rceil}\left({N+1\over2}\right);
\eqno(6)
$$
��� ��������, ��������, ��� ��� $N=1999998$ � $m=199$ ����� $l \le  3$. 
� ��� ��� ������ ���������� ��������� ����� ������� � $l$ �����, ��� 
������� ����������� ����� ����� ������ ���������.

 ������� ������ ����� ����� ������������ ��������� $l$ �����. ��� 
������� ����� ������������ ����� ����� ������, ��� ��� ����� ���������� 
����������� ��� ���������� ������ ����� �� ������� ������ ���������� 
�����, ������� �� ��������� ����� $p$. � ������ �� ����� 
$1 + (\lceil m/2\rceil-1) (p-1)$

\bye