\input style
\chapno=6\subchno=1\chapnotrue

%% 483
\subchap{����� ����������� ��������� ������} %% 6.2

� ���� ��������� �� ���������� ������ ������, ���������� �� �������� 
������������ ������ (��������, ������� ����� ���� �������� ��� ����������).
 �� ��������� ������� ���������~$K$ � ������~$K_i$ �� ������� ����� 
������������ ����� �� ���� �������� � ����������� �� ����, ����� �� 
����������� �����: $K<K_i$, $K=K_i$, $K>K_i$.  
���������������� ������ ��, � ��������, ������ �������� ���� �� ���� 
����������� ($K=K_i$ ���~$K\ne K_i$), �� ���� �� ����������� 
�� ����������� ����� ���� ���������������� ������ � �������, �� ������� 
����������� ���������� ������������ ��������� �������.

\subsubchap{ �� � ������������� �������} % 6.2.1

��� �� ������� ������, ���� ��� ������ ������� ���������� ����� � 
�������� ����� ��� ��������, ����� �������� �������� 795-68-41? � 
��������� ������� �������� ��������������� �������� ����������������� 
������, ����������� � \S~6.1. (���, ������ ������� �������� ��� �� 
���������� ������� ����� � ��������, ��� �������; �� ��������� �����, ��� 
� ���� ���� ������ �� ���������� �������, ������� ������ � ������������, 
��� �������� ����������� � ������� ����������� �������.) 䅋� � ���, ��� 
������� ����� ����� ������ �� ������� ��������, � �� �� ������, ���� 
���������� ����� �������� ��� ����������, ������ � ����� �������. 
呋� ���������� ����� ������ � ������� �����, � ���������������� ������ 
����� �� ����� ���� ����, �� ������������� ��������� ������� � �������� 
������� ��������� ������.

� ����� ������������ ���� ����� ������� ���������� (��.~5), ������� ��� 
��� �� �������� ����� ����������� ����, ����� ����� ������� ���������� 
�����. ����������, ���� ����� ���� ����������� ��������, �� ������� 
���������� ��� ���������������, ��� ��������������� ����������. � ���� � 
����� � ��� �� ������� ���������� ����� ����������� �����, �� 
����������� ����������� ��. � ���� ������ �� ������ ������ ������ � 
�������� �� ��������� �������� � �������������� �������
$$
K_1<K_2<\ldots<K_N.
$$
%% 484
�� ��������� $K$ �~$K_i$ �� ����� ���
$$
\eqalign{
&\bullet K < K_i \rem{[$R_i$, $R_{i+1}$,~\dots, $R_N$ ����������� �� ������������],}\cr
\hbox{��� }&\bullet K=K_i \rem{[����� ��������],}\cr
\hbox{��� }&\bullet K>K_i \rem{[$R_1$, $R_2$,~\dots, $R_i$ ����������� �� ������������].}\cr
}
$$
󌅋� �������� � ������ �� ���� �������, �� ��������� ����� ������� �� 
��������� � ���������������� �������, ���� ������ $i$ �� ������� ������ � 
������ �������. 򀊈� �������, ������������ ����� � ����������� ����������.

\section ል����� �����. ����, ������ �������� � ������ ��������� 
��������� �����: ������� ��������~$K$ �� ������� ������ � �������. 
��������� ��������� �������� ����������, � ����� �������� ����� ���������� 
�����, �������� � ��� �� �� ���������, � �. �. �� �� ����� ��� 
�������� $\log_2 N$ ��������� ���� ���� ����� ������, ���� ����� 
����������� ��� ����������. 򀊀� ��������� ������ ���������� 
"��������������� �������" ��� "������� ������� �������", �� �������� 
��������������� ������---\dfn{�������� �����.}

����� ���� ��������� ������ �������� ������, ������ �� ������������, � 
��� ������ ������� ������������� �� ���� ������� �������� ���������� 
��������� ����������� ��������. � �� �������� ���������� ���������� 
������ ���������� ��� ���������---$l$ �~$u$, ��������������� ������� 
� ������ �������� ������, � ������� � ���������.

\alg �.(ል����� �����.) � ������� ������� ��������� ������������� 
��������~$K$ � ������� ������� $R_1$, $R_2$,~\dots, $R_N$, ����� ������� 
����������� � ������������ �������: $K_1<K_2<\ldots<K_N$.

\st[퀗������ ���������.] 󑒀������ $l\asg 1$, $u\asg N$.

\st[퀕������� ��������.] (� ���� ������ �� �����, ��� ���� $K$ ���� � 
�������, �� ����������� ����������� $K_l\le K\le K_u$. ᎋ�� ������ 
�������� �������� ���������� ����, � ���.~1.) 呋� $u<l$, �� �������� 
������������� ��������; � ��������� ������ ���������� 
$i\asg\floor{(l+u)/2}$: ������ $i$~��������� �������� � �������� 
��������������� ����� �������.

\st[񐀂�����.] 呋� $K<K_i$, �� ������� �� \stp{4}; ���� $K>K_i$, �� 
������� ��~\stp{5}; ���� $K=K_i$, �������� ������������� ������.

\st[ꎐ����������~$u$]. 󑒀������ $u\asg i-1$ � ��������� � ����~\stp{2}.

\st[ꎐ����������~$l$.] 󑒀������  $l\asg i+1$ � ��������� � ����~\stp{2}.
\algend
%%485
\picture{���. 3. ል����� �����.}

�������~4 ������������ ��������� ��������� � � ���� �������: ����� 
������������� ��������, ������ ���������� � ������� �����~653, � ����� 
������������� ������������� ��������~400. 񊎁�� ������������� ���������� 
$l$ �~$u$, ������������ ���� ������������~$K_i$. � ����� ������� ����� 
��������� ����� ������� ���������.

\prog B.(ል����� �����.) ꀊ � � ���������� \S~6.1, ��������������, ��� 
$K_i$ �������� ������ ����� �� ������ $|KEY|+i$. ������� ���� ��������� 
���������� $|rI1|\equiv l$, $|rI2|\equiv u$, $|rI3|\equiv i$.
{\catcode`\!=\active\def!#1.{\underline{#1}}
 \catcode`\[=\active\def[{\hbox to 0pt{\hss$\lbrack$}}
 \catcode`\]=\active\def]{\hbox to 0pt{$\rbrack$\hss}}
$$
\displaylines{
\matrix{
\vbox{\halign{$\phantom{[}#\phantom{]}$\bskip&&$\phantom{[}#\phantom{]}$\bskip\cr
\noalign{\hbox{a)~�� ����� 653:}}
[061 & 087 & 154 & 170 & 275 & 426 & 503 &!509.& 512 & 612 &  653  & 677 & 703 & 765 & 897 & 908]\cr
 061 & 087 & 154 & 170 & 275 & 426 & 503 & 509 &[512 & 612 &  653  &!677.& 703 & 765 & 897 & 908]\cr
 061 & 087 & 154 & 170 & 275 & 426 & 503 & 509 &[512 &!612.&  653] & 677 & 703 & 765 & 897 & 908 \cr
 061 & 087 & 154 & 170 & 275 & 426 & 503 & 509 & 512 & 612 &[!653.]& 677 & 703 & 765 & 897 & 908 \cr
}}\hfill\cr
\vbox{\halign{$#$\bskip&&$#$\bskip\cr
\noalign{\hbox{b)~�� ����� 400:}}
[061 & 087 & 154 & 170 &  275  & 426 & 503 &!509.& 512 & 612 & 653 & 677 & 703 & 765 & 897 & 908]\cr
[061 & 087 & 154 &!170.&  275  & 426 & 503]& 509 & 512 & 612 & 653 & 677 & 703 & 765 & 897 & 908 \cr
 061 & 087 & 154 & 170 & [275  &!426.& 503]& 509 & 512 & 612 & 653 & 677 & 703 & 765 & 897 & 908 \cr
 061 & 087 & 154 & 170 &[!275.]& 426 & 503 & 509 & 512 & 612 & 653 & 677 & 703 & 765 & 897 & 908 \cr
 061 & 087 & 154 & 170 &  275] &[426 & 503 & 509 & 512 & 612 & 658 & 677 & 703 & 765 & 897 & 908 \cr
}}\hfill\cr
}\cr
\hbox{���. 4.             ���� ��������� ������.}\cr
}
$$
}
%%486
\code
START & ENT1 & 1       & 1   & Bl. 퀗������ ���������. $l\asg 1$.
      & ENT2 & N       & 1   & $u\asg N$.
      & JMP  & 2F      & 1   & � B2.
5H    & JE   & SUCCESS & C1  & ����, ���� $K=K_i$.
      & ENT1 & 1,3     & C1-S& B5. ꎐ���������� $l$. $l\asg l+1$.
2H    & ENTA & 0,1     &C+1-S& B2. 퀕������� ��������.
      & INCA & 0,2     &C+1-S& $|rA|\asg l+u$.
      & SRB  & 1       &C+1-S& $|rA|\asg\floor{|rA|/2}$. (셍����� �~|rX|.)
      & STA  & TEMP    &C+1-S&
      & CMP1 & TEMP    &C+1-S&
      & JG   & FAILURE &C+1-S& ����, ���� $u<l$.
      & LD3  & TEMP    &C    & $i\asg\hbox{\rm ��������}$.
3H    & LDA  & K       &C    & B3. 񐀂�����.
      & ���� & KEY,3   &C    &
      & JGE  & 5B      &C    & ����, ���� $K\ge K_i$.
      & ENT2 & -1,3    &C2   & B4. ꎐ����������~$u$.
      & JMP  & 2B      &C2   & � B2.
\endcode
\progend
䀍��� ��������� "�����������" �� ������ \MIX\ ����� ������, ��� 
����������, ��� ��� ����������� ���������� � \MIX\ ��������. ␅��, 
������ ��������� ����� $(18C-10S+12)u$, ���
\picture{���. 5. ል����� ������, ��������������� ��������� ������  ($N=16$).}
$C=C1+C2$---���������� ������������� ��������� (������� ��� ����������� 
���~B3), $S=1$ ���~0 � ����������� �� �������� ��� ���������� ������. 
瀌����, ��� ������~08 ��������� ���������������� ��� "����� ������ �� 
1" (shift right binary 1),
%% 487
��� ��������� ���� � �������� ������� \MIX; � ����� ������ �� ������� 
�������� �� "|MUL =1//24+1=|", ����� ����� ������ ��������� ���������� 
�� $(26C-18S +20)u$.

\section ���������� � ���� ������. ����� ����������� ����������� � 
���������~B, ����� ����� ����������� ��� � ���� ��������� ������ �������. 
(� ���.~5 �������� ����� ������ ��� ������ $N=16$.)

 $N=16$ ������ ������������ ���������~$K:K_8$, ��� ������������ �� 
������� �������� �����~\node{8}. 䀋��, ���� $K<K_8$,  �������� 
������������ ����� ���������, ��������� $K$ �~$K_4$,. ����������,  ���� 
$K>K_8$, ������������ ������ ���������.
텓������ ����� ����� � ���� �� "�������" ���������� �����, �������������� 
��~\leaf{0} ��~\leaf{$N$}; ��������, �� ��������� ����~\leaf{6} ����� � 
������ �����, ����� $K_6<K<K_7$.

ል����� ������, ��������������� ��������� ������ ����� $N$~�������, ����� 
��������� ��������� �������: ��� $N=0$ ������ �������� � ����~\leaf{0}. � 
��������� ������ �������� ����� ��������
\picture{���. ���. 487}
����� ��������� ������������� ��������� ������ � $\ceil{N/2}-1$~������, � 
������---������ � $\floor{N/2}$~������ � ������� � �����, ������������ ��~$\ceil{N/2}$.

����������� ������� \emph{�����} �������� ������ � ������������� ������� 
�����~$N$, ������������� ����� ���������, ����� ����������� �������� 
������� � ������, ����������� ������� ��~$1$ ��~$N$ (��������������, ��� 
�������� �� �������� ������ ���������). ����, ����� �������� ������ 
������������� ���������� ������ ������ � ������������� �������; �� 
������ �������� ����
\picture{���. ���. 487}
� ������������ ������� ����� �������.

呋� �������� ������ � ���������~B ���� $K_{10}$, �� ������������ 
��������� $K>K_8$, $K<K_{12}$, $K=K_{10}$. � ���.~5 ��� ������������� 
���� �� ����� � ����~\node{10}. ���������� ��������� ���������~B ��� 
������~$K$ ������������� ���� �����, ������� �� ����� ������. � ������� 
������ ���������� �������� ��������, ��������������� ���������~B, � 
�������� ��~$N$ ����� ������������

\proclaim 򅎐��� B.  $2^{k-1}\le N <2^k$ ������� �����,  ������������ 
��������~B, ������� $(\min 1, \max k)$~���������. 텓������ �����
%%488
������� $k$~��������� ���~$N= 2^k-1$ ���� $k-1$ ��� $k$~��������� ��� 
$2^{k-1}\le N<2^k-1$. \endmark

\section 䀋������� ������ ��������� ������. [����������� �� 
�������������� ����������� ������� ����� � ������������~(4).] 
���������� � ���� ������ ��������� ����� ���������� \emph{�������} 
����� ���������. ����� $C_N$ ��������� ������� ����� ��������� ��� ������� 
������ � �������������, ��� ������ �� $N$~������ � ������ ������������ 
�������� ���������� ������. 񐅄��� ����� ���������~$C'_N$ ������������� 
���������� ������; ��������������, ��� ��� ��������� (�� $N+1$) ����� 
������� � ��� ������� �������� �������������. 茅�� �� ����������� 
���� ����������� � �������� ����
$$
\eqalign{
C_N&=1+{\hbox{\rm 䋈�� ����������� ���� ������}\over N};\cr
C'_N&={\hbox{\rm 䋈�� �������� ���� ������}\over N+1}.\cr
}
$$
� �������~(2.3.4.5-3) �����, ��� ����� �������� ���� ��~$2N$ ������ ����� 
����������� ����; ������ ������� �������� ����������� ����������� ����� 
$C_N$ �~$C'_N$
$$
C_N=\left(1+{1\over N}\right) C'_N-1.
\eqno(2)
$$
��� �������, ���������� ��������� [{\sl JACM,\/} {\bf 9} (1962), 16--17],
 ����������� ��� ���� ������� ������, ��������������� �������� ��������, 
�.~�.~��� ���� �������, �� ���������� ������ ���������. 䈑������~$C_N$ 
����� ����� ���� �������� ����� ���������~$C'_N$ (��.~���.~25).

� ����������� ������ �����, ��� "����������" ������� ������ ����� 
��������� ������������� ������ � ����������� ������ �������� ���� ����� 
���� �������� ��������, ���������� $N$~���������� �����. � �������, 
����� ��������, ��� ��������~B ��������� � ���� ������, ��� ��� �������� 
������ ����� ����������� ����� ���� ����� � ������ �����, ����� 
��� ������� ���� ��������� �� ����� ��� ���� �������� 
�������. (�.~���.~5.3.1-20.) 񋅄���������, ����� �������� ���� 
��������� ������, ���������������� ���������~B, �����
$$
(N+1)(\floor{\log_2  N}+2)-2^{\floor{\log_2 N}+1}.
\eqno(3)
$$
(�.~(5.3.1-33).) 葏������~(3) �~(2), ����� ����� ��������� ������� ����� 
���������, ���� ������������, ��� ��� ��������� ������ �������������:
{\def\f#1,#2/#3.{#1{#2\over#3}}
\ctable{
\hfill$#$\bskip&&$#$\bskip\hfill\cr
   N=&1&  2     &  3     &  4     &  5     &  6     &  7     &  8     &  9      &  10     &  11     & 12       & 13       &  14      &  15     &  16\cr
 C_N=&1&\f1,1/2.&\f1,2/3.&  2     &\f2,1/5.&\f2,2/6.&\f2,3/7.&\f2,5/8.&\f2,7/9. &\f2,9/10.&  3      &\f3,1/12. &\f3,2/13. &\f3,3/14. &\f3,4/15.&\f3,6/16.\cr
C'_N=&1&\f1,2/3.&  2     &\f2,2/5.&\f2,4/6.&\f2,6/7.&  3     &\f3,2/9.&\f3,4/10.&\f3,6/11.&\f3,8/12.&\f3,10/13.&\f3,12/14.&\f3,14/15.&  4      &\f4,2/17.\cr
}
}
%%489
� ����� ������, ���� $k=\floor{\log_2 N}$, ����� (��.~�~(5.3.1-34))
$$
\matrix{
\hfill C_N &=k+1-(2^{k+1}-k-2)/N\hfill&=\log_2 N-1+\varepsilon+(k+2)/N;\hfill\cr
\hfill C'_N&=k+2-2^{k+1}/(N+1)  \hfill&=\log_2N+\varepsilon',\hfill\cr
}
\eqno(4)
$$
��� $0\le\varepsilon$, $\varepsilon'<0.0861$.

蒀�, ��������~B ������� �������� $\floor{\log_2 N} +1$~���������;
������� ����� ��������� ��� ������� ������ ����������� �����~$\log_2N-1$. 
� ���� �����, ���������� �� ��������� ������, �� ����� ���� ������ 
�����������. 񐅄��� ����� ������ ��������� � ���������� ��������
$$
\eqalign{
&(18\log_2N-15)u\rem{ ��� �������� ������;}\cr 
&(18\log_2N+13)u\rem{ ��� ���������� ������}\cr
}
\eqno(5)
$$
(��������������, ��� ��� ������ ������ �������������).

\section � ������ �����������. 񎁋���������� ������ ���� ���������� 
$l$, $i$, $u$ ������������ ���� ���: ������� ���������~$i$ � �������� ��� 
���������~$\delta$; ����� ������� ���������, �� ������� ���������, �� 
����� �� ���������� $i\asg i\pm\delta$ �~$\delta\asg\delta/2$ 
(��������������). ���� ���� ���������, �� �� ������� ������ ������������ � 
�������, ��� � ����������� ���� ���������;
����� ������� ������� �������� �� �������!

\alg U.(������� �������� �����.) �������� ������ ��� ��������� 
���������~$K$ � ������� ������� $R_1$, $R_2$,~\dots, $R_N$, ����� ������� 
����������� � ������������ �������: $K_1<K_2<\ldots<K_N$.  ������~$N$ 
������ ���������� ��������� � ���������� �����~$K_0$, ������� ���������� 
���������� ������~$-\infty$ (��� ����� ��������, �������~$K$. 
�����������, ��� $N\ge1$.

\st[퀗������ ���������.] 󑒀������ $i\asg\ceil{N/2}$, $m\asg\floor{N/2}$.

\st[񐀂�����.] 呋� $K<K_i$, �� ������� ��~\stp{3}; ���� $K>K_i$, �� 
������� ��~\stp{4}; ��� $K=K_i$ �������� ������������ ������.

\st[󌅍������ $i$.] (� ���������� ��������� ���������, ��� ����� 
���������� �����. � �������� $m$ ��� $m-1$~�������; $i$ ��������� �� 
������ ������� ������ �� ���������.) 呋� $m=0$, �� �������� ������������ 
��������. � ��������� ������ ���������� $i\asg i-\ceil{m/2}$; 
$m\asg\floor{m/2}$ � ��������� ��~\stp{2}.

\st[󂅋������ $i$.] (񈒓���� �� ��, ��� � � ����~\stp{3}, 
������ $i$~��������� �� ������ ������� \emph{�����} �� ���������.) 
呋� $m=0$, �� �������� ������������ ��������. � ���������
������ ���������� $i\asg i+\ceil{m/2}$; $m\asg\floor{m/2}$ � ��������� ��~\stp{2}.
\algend

� ���.~6 ������������ �������� ������, ��������������� ������ ��� $N=10$. 
 ��������� ������ ��� ��� ����� ����������
%%490
������ ��������� ����� ������������� ������ ���������; ����, 
���������� ���� ����������, ������������. 䀍��� ������� ������ ����� 
������� \emph{����������}, ��� ��� �������� ����� ������ � ���� 
������~$\ell$ � ������ � ����-��������������� ������~$\ell-1$ ���� 
���������� ��������~$\delta$ ��� ���� ����� ������~$\ell$.
������� ������������ ���������~U ����� ��������� �������. ��������, 
��� ����� ����� ���������� � ���������
\picture{���. 6. ል����� ������ ��� "�����������" ��������� ������ ($N=10$).}
�����~$n-1$; ��������� �� ������� ��������� (���� $n$ �����) ��� � ����� 
�� ���� ������� (���� $n$ �������) �������� ��� ��������� 
�����~$\floor{n/2}-1$ �~$\ceil{n/2}-1$. �� ���������� ���� ��������� 
$k$~��� �� ������� $2^k$~���������� � ����������� ������~$\floor{n/2^k}-1$ 
� ������������ ������~$\ceil{n/2^k}-1$. 񋅄���������, �� ������ ����� 
����� ���� ���������� ����������� ����� ������� ��~1, ��� ������ ��������� 
����� ����������� "��������" �������� ��� ����������� ������������������ 
������ �������� ����.

 ��� ������������ ���������~U ������� � ���, ��� ��� ������ �� ����� 
��������� ��������~$m$; ����� ���� ��������� �� ����������� ������� 
��������~$\delta$ ��� ������� ������. 򀊈� �������, �������� �������� � 
��������� ���������, ��������� ������� � ��� ��������, � ��� ���������� ���.

\alg C.(������� �������� �����.) �������� ���������� ���������~U, �� 
������ ����������, ����������� �~$m$, ���������� ��������������� ������� �������
$$
|DELTA|[j]=\floor{{N+2^{j-1}\over 2^j}}=\left({N\over 2^j}\right)
\hbox{ �����������}; \qquad 1\le j \le \floor{\log_2 N}+2.
\eqno(6)
$$
\st[퀗������ ���������.] 󑒀������ $i\asg|DELTA| [1]$, $j\asg2$.
%%491
\st[񐀂�����:] 呋� $K<K_i$, �� ������� �� \stp{3}; ���� $K>K_i$, �� 
������� ��~\stp{4}.  $K=K_i$ �������� ������������ ������.

\st[󌅍������ $i$.] 呋� $|DELTA|[j]=0$, �� �������� ������������ 
��������. � ��������� ������ ���������� $i\asg i-|DELTA|[j]$,  $j\asg j+1$ 
� ��������� ��~\stp{2}.

\st[󂅋������~$i$.] 呋� $|DELTA|[j]=0$, �������� ������������ ��������. 
� ��������� ������ ���������� $i\asg i+|DELTA|[j]$, $j\asg j+1$ � 
��������� ��~\stp{2}. 
\algend

� ���.~8 ����� ��������, ��� �������� ��������� �� ��������������� 
����~$K_0=-\infty$ ���� ��� ������~$N$.

\prog C.(������� �������� �����.) ��� ��������� �� ���� ���������~C 
����������� �� �� ������, ��� � ���������~B. 葏��������� $|rA|\equiv K$, 
$|rI1|\equiv i$, $|rI2|\equiv j$, 
$|rI3|\equiv |DELTA| [j]$.
\code
START  & ENT1 & N+1/2  & 1     & C1. 퀗������ ���������.
       & ENT2 & 2      & 1     & $j\asg 2$.
       & LDA  & �      & 1     &
       & JMP  & 2F     & 1     &
3H     & JE   & SUCCESS& C1    & ����, ���� $K=K_i$.
       & J3Z  & FAILURE& C1-S  & ����, ���� $|DELTA|[j]=0$.
       & DEC1 & 0,3    & C1-S-A& C3.  󌅍������~$i$.
5H     & INC2 & 1      & C-1   & $j\asg j+1$.
2H     & LD3  & DELTA,2& C     & C2. 񐀂�����.
       & ���� & KEY.1  & C     &
       & JLE  & 3B     & C     & ����, ���� $K\le K_i$.
       & INC1 & 0,3    & C2    & C4. 󂅋������ $i$.
       & J3NZ & 5B     & C2    & ����, ���� $|DELTA|[j]\ne0$.
FAILURE& EQU  & *      & 1-S   & ⛕��, ���� ��� � �������.
\endcode
\progend

 ������� ������ ���� �������� ������������� ��������� ������ � ��� �� 
������ ����������� ����, ��� � ��������~�, ������� ������� ����� 
���������~$C_N$ ������ ��������~(4).  ��������� ������ ��������~C 
������ ��������� ����� $\floor{\log_2N}+1$~���������. ��� ����� ������ 
���������~C �� ������ ����������� �� ��������� � ����� � ������ ������, 
��� ��� $C1$ ����� ���, ������� ��� $C2$, �� � ���.~9 ����� ��������, 
��� ������ $K>K_i$ ����������� �������� ��� �� �����, ��� �~$K<K_i$;
�������������, ���������~C ������� ��������������
$$
\matrix{
(8.5\log_2N-6)u \hfill& \hbox{�� ������� �����};\cr
(8.5\floor{\log_2N}+12)u &\hbox{�� ��������� �����.}\cr
}
\eqno(7)
$$
%%492
��� ����� ��� � ��� ���� ������� ���������~B, ������ �� ������������ 
����������� �������� �������� ���, � �� ����� ��� � �������~(5) 
��������������, ��� \MIX{} ����� ������� "�������� ����� ������".

䐓��� ����������� ��������� ������, ������������ � 1971~�. �.~�.~�����, 
�� ��������� ��� ��������� ��� ����� ������� ����������, ��� ��� ��� 
��������� ����� �������
\picture{���. 7. ል����� ������ ��� ����� ����������� ������ ���� ($N=10$).}
���� � �� ������� ��������������� �������. 񍀗��� �� ���������� $K$ 
�~$K_i$, ��� $i=2^k$, $k=\floor{\log_2 N}$. 呋� $K<K_i$, �� ���������� 
���������� ����� � ������������������� $\delta=2^{k-1}$, $2^{k-2}$,~\dots, 
$1$, $0$. � ������ �������, ��� $K>K_i$ �~$N>2^k$ ������������� 
$i=i'=N+1-2^\ell$, ��� $\ell=\floor{\log_2(N-2^k)}+1$, �, ����� ���, ��� 
������ ���������� ���� $K>K_{i'}$, ���������� ���������� ����� � 
$\delta=2^{\ell-1}$, $2^{\ell-2}$,~\dots, $1$, $0$.

�������~7 ������������ ����� ���� ��� $N=10$. � ������ ���� ������� �� 
��������� ����� $\floor{\log_2 N}+1$~���������; �������������, �� ���� 
���� �� ������ ������� ����� ���������, �������� �� �� ��� ������ �������� 
����� ��������� ���������������� ���������� ����� (��. � ���.~12).

噅 ���� ����������� ��������� ������, ���������� ��� ������������� ������ 
��� ����� ������� $N$, ����������� � ���.~23. � ���.~24 ������� ��� ����� 
������� �����!

\section 􈁎������� �����.  ������������ ������������ 
������� (�.~5.4.2) �� ������, ��� ����� 􈁎����� ����� ������ ����,
 ����������� ��������~$2$. ���� ������� ����� ����� � � ������ ������,
 ����� � ������� ����� 􈁎����� ��������� ������, ��������� ����������� � 
�������� �������. ��������� ����� ��� ��������� ��� ���������������� 
���������, ��� ��� �� �������� ���� �������� � ���������; ��� 
������������� � ������� ��~$2$. 񋅄��� �������� ���������, ������� �� ����-
%%493
������ ���������, �� ��������� ��������� ��������� "������������ ������",
 ������� ������������ ��� ���������� ��������� ������������� ������� 
[��.~�~Fibonacci Quarterly, 4 (1966), 265--269]; �������� �������� ����� � 
��������� ��������.

� ������ ������ ����������� ����� ������� ������ ������������; ���� 
������ ����� ��������� � ���������� ��������� �� ������, �� ��������� 
�����������, ��� ��� �������� � ������� �����. � ����� �������������� 
���������, ��� ������ �� ��������
\picture{���. 8.   䅐��� 􈁎����� ������� 6.}
��������������� ������ ������. ���� �������� ���������������� ������ 
������ � �������� � "������������� ��������".

� ���.~8 ���������� ������ 􈁎����� �������~$6$. 瀌�����, ��� ��� 
��������� ������ ���������� �������� ����, ��� ����������������� ����� 
�������, ��������, ������, ��� ������ ��������� �������� ������������� 
������ 􈁎�����. ⎎��� ������������ ������ �������~$k$ ����� 
$F_{k+1}-1$~���������� (�������) ����� �~$F_{k+1}$~������� (����������) 
�����; ��� �������� ��������� �������:

{\medskip\narrower
\item{呋�}~$k=0$ ���~$k=1$, ������ �������� ������ �~\leaf{0}.

\item{呋�}~$k\ge2$, ������ ��������~\node{F_k}; ����� ��������� ���� 
������ 􈁎����� �������~$k-1$; ������ ��������� ���� ������ 􈁎����� 
�������~$k-2$ � ������� � �����, ������������ ��~$F_k$.

\medskip}

\noindent 瀌����, ���, �� ����������� ������� �����, �����, 
��������������� ���������� ������� ����������� ����, ���������� �� ����� 
� ���� ���� �� ���� � �� �� ��������, � ������ �� ����� 􈁎�����. �, 
$5=8-F_4$, $11=8+F_4$ (���.~8). 呋� �������� ���� �����~$F_j$, �� �� 
��������� ������ ���������������
%%494
�������� �������� ��� ����� ����� $F_{j-1}$, � ��� ������~$F_{j-2}$. �,
 ��������, $3=5-F_3$, a~$10=11-F_2$.

��� ���������� � ������������ � ���������� ���������� ������������� 
������� ����� ����

\alg F.(􈁎������� �����.) �������� ��������������� ��� ������ 
���������~$K$ � ������� ������� $R_1$, $R_2$,~\dots, $R_N$, ������������� 
� ������� ����������� ������ $K_1<K_2<\ldots<K_N$.

䋟 �������� �������� ��������������, ��� $N+1$ ���� 
����� 􈁎�����~$F_{k+1}$. ������� ��������� ���������� ������ ����� 
����� ������� ��������� ��� ������~$N$ (��.~���.~14).

\st[퀗������ ���������.] 󑒀������ $i\asg F_k$, $p\asg F_{k-1}$, 
$q\asg F_{k-2}$. (� ���� ��������� $p$ �~$q$ ���������� ���������������� 
����� 􈁎�����.)

\st[񐀂�����.] 呋� $K<K_i$, �� ������� ��~\stp{3}; ���� $K>K_i$, �� 
������� ��~\stp{4}; ���� $K=K_i$, �������� ������������� ������.

\st[󌅍������~$i$.] 呋�~$q=0$, �������� ������������� ��������. 
呋�~$q\ne 0$, �� ���������� $i\asg i-q$, �������� $(p, q)$ ��~$(q, p-q)$ 
� ��������� ��~\stp{2}.

\st[󂅋������~$i$.] 呋�~$p=1$,  �������� ������������� ��������. 
呋�~$p\ne1$, ���������� $i\asg i+q$, $p\asg p-q$, $q\asg q-p$ � ��������� ��~\stp{2}.
\algend

� ���������� ���� ���������� ���������~F ��� ������ \MIX\ �������� 
������������� �� ���� ������������ ����������� �����, � ����� �� 
����������� �������� $p$~�������� �~|rI2|, �~$q$---�~|rI3|, � ������ �� 
�������� �������� ������; ��� �������� ���~F3. � ����� ���� ��������� 
������ � ��������� $p-1$ �~$q-1$, ��� �������� �������� "$p=1$?" � ����~F4.

\prog F.(􈁎������� �����.) 獀����� ���������: $|rA|\equiv K$,
 $|rI1|\equiv i$, $(|rI2|, |rI3|)\equiv p-l$, $(|rI3|, |rI2|)\equiv q-l$.
\code
START & LDA & K          & 1   & F1. 퀗������ ���������.
      & ENT1& $F_k$      & 1   & $i\asg F_k$.
      & ENT2& $F_{k-1}-1$& 1   & $p\asg F_{k-1}$.
      & ENT3& $F_{k-2}-1$& 1   & $q\asg F_{k-2}$.
      & JMP & F2A        & 1   &   � F2.
\twocols
F4A & INC1 &1,3    & F4B &INC1 &1,2    & C2-S-A & F4. 󂅋������ $i$. $i\asg i+q$.
    & DEC2 &1,3    &     &DEC3 &1,2    & G2-S-A & $p\asg p-q$.
    & DEC3 &1,2    &     &DEC2 &1,3    & G2-S-A & $q\asg q-p$.
F2A & CMPA &KEY, 1 & F2� &CMPA &KEY,1  & G      & F2. 񐀂�����.
    & JL   &F3A    &     &JL   &F3B    & G      & � F�, ���� $K<K_i$.
    & JE   &SUCCESS&     &JE   &SUCCESS& G2     & ⛕��,  ���� $K=K_i$.
%%495
    & J2NZ &F4A    &     &J3NZ &F4B    & C2-S   & � F4, ���� $p\ne1$.
    & JMP  &FAILURE&     &JMP  &FAILURE& A      & ⛕��,  ���� ��� � �������.
F3A & DEC1 &1,3    & F3B &DEC1 &1,2    & C1     & F3. 󌅍������~$i$. $i\asg i-q$.
    & DEC2 &1,3    &     &DEC3 &1,2    & C1     & $p\asg p-q$.
    & J3NN &F2B    &     &J2NN &F2A    & C1     & 񌅍� ���������, ����~$q>0$.
    & JMP  &FAILURE&     &JMP  &FAILURE& 1-S-A  & ⛕��,  ���� ��� � �������.
\endtwocols
\endcode
\progend

� ���.~18 ������������� ����� ������ ���� ���������. �������~8 ����������, 
� ������ ����������, ��� ����� �� ���� ��������� ����, ��� ������. ����� 
$C$, $C1$ �~$C2-S$ ��������� ����� ���������� ����� F2, F3 �~F4 
��������������. 茅��
$$
\eqalign{
 C&=(\ave \phi k/sqrt{5}+O(1), \max k-1), \cr
C1&=(\ave k/\sqrt{5}+O(1), \max k-1),\cr
C2-S&=(\ave \phi^{-1} k/\sqrt{5}+O(1), \max \floor{k/2}).\cr
}
\eqno(8)
$$
獀���, ����� ����� ���������� �������� � $\phi=1.618$~���� ���� ������ 
(��� ����� ���� ����������, ��� ��� ������ ����� ����� ��������������� 
�������� �� ��� �����, ������ ����� ����� �������� � $\phi$~��� ������� 
������). 񐅄��� ����� ������ ��������� F ���������� ��������
$$
\eqalign{
(6\phi k/\sqrt{5}-(2+22\phi)/5)u &\approx (6.252\log_2 N-4.6)u 
\rem {��� �������� ������;}\cr
(6\phi k/\sqrt{5}+(58/(27\phi))/5)u&\approx (6.252\log_2 N+5.8)u
\rem{��� ���������� ������.}\cr
}
\eqno(9)
$$
��� ��������� �����, ���~(7), ���� � ��������� ������ ���������~F 
�������� �������� $(8.6\log_2 N)u$, �.�. ����-���� ��������� ���������~�.

\section 荒������������� �����. 瀁���� �� ������ � 
�������������� ������� � ��������������, ��� ���������� ����� 
�������. 荎��� ������������ ����� ������������ ���� � �������� ������� 
����������.

��������, ��� �� ����� ����� � �������. 쀋���������, ��� �� ������� 
��������� � �������� �������, ����� ��������� �� ������ ��~$1/4$ ���~$3/4$ 
�~�.~�., ��� � �������� ������, � �� ������ ����������, ��� �� 
�������������� ������������� �������!

呋� ������ ����� ���������� � �����~A, ��, ��-��������, ������� ����� 
���-�� � ������ �������. � ������ ��������
%%496
������� "����������� �������" ��� �������� ������, ������� ���������� 
��������, ��� ���������� ����� �� ������ �����. 򀊓� ��������� ������� 
����� ������������ � ���, ��� ������� �����; ��������������� ��������� 
����������� � \S~6.3.

ꎃ�� ������� ��������� ����� ��� ������, ���� ���������� �������� ���� 
������ �� ������������� ������. 呋� �� ��������, ��� ������ ����� ������ 
���������� ������� ������ �������� ��������, �� ���������� ���������� �� 
����������, ������ ��� ������� ��������� �������. ��� � ����� ���������� 
�� ���������� ����������, ������� �� ������ �������� ����� "����� 
������" � "���� ������".

� �������� � ������ ���������, ����������� "���������������� �������": 
���� ��������, ��� $K$ ����� �����~$K_l$ �~$K_u$, �� ��������� ����� 
������ �������� �� ���������� $(u-l)(K-K_l)/(K_u-K_l)$ ��~$l$, �����������,
��� ����� �������� �������, ������������� �������������� ��� �������������� 
����������.

 荒������������� ����� �������������� ���������������� ���������; �� 
��������, ���� ��� ��������� ������ ���������
���������� "�������������" ������� �~$n$ ��~${1\over2}n$, � ���� ���
����������������� (���� ����� � ������� ������������ ��������� 
�������)---�~$n$ ��~$\sqrt{n}$. 쎆�� ��������, ��� ���������������� ����� 
������� � ������� ����� $\log_2 \log_2 N$~����� (���.~22).

� ���������, ������������ �� ��� ��������, ��� ���������������� ����� 
��������� ����� ��������� �� ���������, ����� �������������� ����������� 
�������������� ������ �������, ����� �������, � ������� ������������ �����,
 �������� �� ���������� ("�������") ������. �������� ����� $\log_2 
\log_2 N$ �~$\log_2 N$ ���������� ������������ ���� ��� ������ �������~$N$,
 � �������� ����� ������������ ��������. 荒��������� ������� �� 
��������� ������� ���� � ���������� � ������ �� \emph{�������} 
������������ �����������. (瀌����, ��� ������ �������� ������� ����, � 
��������, �� ����������, � ������� �����; ��� �������� ����� ����������� 
������������.)

\section 葒���� � ������������. ��� ��������� �������� �������� 
������� ���������, ������������� ��� ���������� ������, �������� 
���������� ����������� ������� �������� ������� Inakibit-Anu, ���������� 
�������� 200~�. ��~�.�. ��� �������� ���������, ��������, ��������� ����� 
�� ���� ��������, ���������� ����� 500 ������������ ����������������� 
����� � �������� �� �������, ��������������� � 
������������������ �������. 퀏�����, ����������� ����� ������������������:
%%497
\ctable{
\bskip$#$\bskip&&\bskip$#$\bskip\cr
01&13&09&34&29&08&08&53&20&\qquad&49&12&27\cr
01&13&14&31&52&30&  &  &  &      &49&09&07&12\cr
01&13&43&40&48&  &  &  &  &      &48&49&41&15\cr
01&13&48&40&30&  &  &  &  &      & 48&46&22&59&25&25&55&33&20\cr
01&14&04&26&40&  &  &  &  &      &48&36\cr
}
񎐒������ 500 �������� ����� ���������� ��� ������ ������� �������������. 
[�. ����� D.~�.~Knuth, {\sl CACM\/}, {\bf 15} (1972), 671--677, ��� 
���������� ����� �������������� ��������.]

䎂����� ����������� ����������� �� ������� �����, �� ��������� ������� 
����� ������� ��� ������� �� �������������� ���� ����� ���������. ��� 
������������������ ��� ����������� ���� �������������� ��� � �������� 
������� ���������. 퀏�����, ������ ���������� ������ �������� �����, 
��������� ���� �� ������ � ������ ���������� �������: ������ 
���� ���������� �~�����, ������ �~���� �~�.~�.; ��� ��������� 
�����������. 荎��� ����������� ������������������ ���� �������������� 
�������� � ������� ��� ����������� �����; ��������, $\alpha$, $\beta$, 
$\gamma$ ���������� 1, 2, 3 ��������������.

��� ������������� ����������� ������� ��� ���� ������� ����, ��������, 
������� ����� ������� ������������; ����, ��������� ������ ���� ��� 
�������, �����-�� ����������� ��������� ��������! 텊������ ���������, 
���������� �������� 300~�. ��~�.�., ��������� �� �������� ��������� ����,
 �������� ������ ������ ���������� ����������� �����; ��� �����������, �� 
������ �� ������ �����, �.~�. ������������ ����� ��������� ���� ������� 
������� ����� ������� ����������� ����������. 㐅������ �������� 
134--135~�. �.~�. �������� ��������� ������, � ������� ������� 
������������������ ����������� �� ������ ���� ������. ��������� 񎔈��%
\note{1}{� �� ����������� ���������, ����� �� �����������.---{\sl �. �����.\/}}
����������� ���������� ������������ �� ������ ����, � ����� � �� 
����������� ������ � ����� "񋎂��� ����������� ����" (I~��� �.~�.). 
臂����� ��������� �������� ����� ������������ ����������� ������������, 
������ ���������� "ꎌ�������� � ㈏�������" 》���%
\note{2}{������� ���� � ������������������, ������� �������� 
��������.---{\sl �. �����.\/}}
 (����� 200~�.), �� ��� ���� ����� ������ ��������. �, � ������� �.~葈����%
\note{3}{葈��� 񅂈������---��������� �������, ���������� ������ � 
��������.---{\sl �. �����.\/}}
 "Etymologiarum" (����� 630~�., �����~X) ����� ����������� ���� �� 
������ �����, � � �������� ������ �� ��������� ���������� �������� "Corpus 
Glossary" (����� 725~�.) --- ������ �� ���� ������. 䂅 ��������� ������ 
����, ��������, ����������� ����������� ������� ������, ����������������� 
� ������� ����.

%% 498

򎋜�� � ����� 䆎����� ㅍ�������� "Catholicon" (1286~�.) �� ������� 
��������� �������� ����������� ����������� �������. � ����������� 䆎����� 
���������, ���
\ctable{
\hfill\it # \bskip & ������������ \it #\hfill\cr
amo & bibo \cr
abeo & adeo \cr
amatus & amor \cr
imprudens & impudens\cr
iusticia & iustus\cr
polisintheton & polissenus \cr
}
(�.~�. �������� ������� ��������, ����� ������� ������������
�� $1$, $2$,~\dots, $6\hbox{-�}$~������) "� ����� ����������". � ��������,
 .��� �������� ����� ������� ����������� ������������.������.
"� ����� ‑, ��������� ��������, �� ��������� ��� ��� ������� ������ � 
���� ������� ��� ����� ������ �� �������".
�������� ����������� ������� �� ������� ����������� �������������� 
�������� ������ �.~�.~䅉�� ({\sl Collection Latomus,\/}
{\bf 90} (1967), 100~pp.). � ��������� ��������� ����������
��������� ���������, �������, ����������, ��������������
��� ��������� ��� ���������� ���� �� ������ ����� (��. ���.~87--90 ��� 
����������).

��� ������� ����������� ����� ������� ꎄ�� "Table
Alphabeticall" (London, 1604) �������� ��������� ����������:

{\narrower

呋� �����, ������� ���� ����� �����, ���������� �~(a), ������ � ������ 
���� �����, � ���� �~(v)---�� � �����. �� ���� ����� ���������� �~(ca), 
������ � ������ �����~(c), � ���� �~(cu) �� � �����. � ��� �� ����� �����.

}
\noindent 荒������ ��������, ��� ꎄ�� �� ����� ���������� �������,
 ��������, ��� ������ ����������� ����� � ���������� �������;
�� ���������� ������ ��������� ����������� ����� ����������� ������� ����, 
���� ������ ����� ������ ����������� �����������.

ል����� ����� ������� �������� 䆎��� 쎗�� � ���������, ������� ����, 
�������, ������ �������������� ����������� ������� ������������ 
���������������� [��. Theory and techniques for the design of electronic 
digital computers, ed. by G.~W.~Patterson, 3 (1946); 22.8--22.9]. � 
������� 50-�~����� ����� ���������� "������ ���������", ��, �������, ����� 
�� ������������ ������ ��������� ���~$N\ne 2^n-1$. [�. A.~D.~Booth, {\sl 
Nature,\/} {\bf 176} (1955), 565;  A.~I.~Dumey, {\sl Computers and 
Automation, \/} {\bf 5} (December, 1956), 7, ��� �������� ����� ����� 
�������� "䂀����� ��������"; D.~D.~McCracken, Digital Computer 
Programming (Wiley, 1957), 201--203; M.~Halpern, {\sl CACM\/} {\bf 1, 
2} (February, 1958), 1--3.]

%%499

�-��������, �������� ��������� ������, ��������� ��� ����~$N$, ������� 
����������� ᎒��������� [{\sl JACM,\/} {\bf 9} (1962), 214]. � 
���������� ���������� ����������� ���������~B, ����� �������� �� ��������� 
������������ � ����� ���������. 葏������ � ����~B2 $i\asg\ceil{(l+u)/2}$ 
������~$\floor{(l+u)/2}$, �� ������������� $l\asg i$ ���~$K\ge K_i$; ����� 
$u-l$ ����������� ����� ������� ����. � �����, ����� $l=u$, ����� $K_l\le 
K<K_{l+1}$, � ����� ���������, ��� �� ����� �������, ��������� ��� 
���� ���������. (� �����������, ��� �������������~$K\ge K_1$.) ��� ���� 
��������� ��������� �������� ���������� ���� �� ������ ���; �� �� ����� � 
��� ���� ������������� � ������ ������ ����������, ������ ����� ��������� 
��������� ���� ��� �������~$N$ (��. ���.~23).

�.~�.~�������� [A Programming Language (Wiley, 1962), 141] ������ 
��������� ���������~B, �� ��� ������������ ����������� ���������� ������.
 �.~ꍓ� ({\sl CACM,\/} {\bf 6} (1963), 556--558) ���������� ��������~B 
��� ������ ������������� �������������� ������� ���������� ����-����. 
������� �������� ����� (��������~C) ��������� ������ �~1971~�. 
�.~�.~������ (񒀍��������� �����������).

􈁎������� ����� ��������� �.~􅐃������ [{\sl CACM,\/} {\bf 3} (1960), 
648], �� ��� ����-����� � ������ ���� �����������. 䅐��� 􈁎����� (��� 
�����) ��������� ������� ������ ��� ������ � ������ ������� ���������� 
����� 㓃� ���������� "쀒����������� �����������" (�., ㎑��������, 1949) 
�� ���.~34;
��� ���� ���������� ������ ���� � ���������, ��� ������� ������; ������ 
����� ���� ������� � ��� ���� ������� �����, ��� ��� ��� ������ ��������� 
�� ����� ������.

荒������������� ����� ��������� �.~�.~������� 
[{\sl IBM J.~Res.~\& Devel.,\/} {\bf 1} (1957), 131--132]. � ��� 
������������� ������ �������� 
����� ��������� ��� ������, ����� ����� �������� ���������� �� ���������� 
�������������� ������������������, ������ ��� ������ ���������� � 
������������������ �������.

\excercises
\rex[21] 䎊�����, ��� ����~$u<l$ � ����~B2 ��������� ������, �� 
$u=l-1$ �~$K_u<K<K_l$. (ᓄ�� �������, ��� $K_0=-\infty$ 
�~$K_{N+1}=\infty$, ���� �������� �� ���������� ��� ���������� �����, �.~�.
 ��� �� ������ �������������� � �������.)

\rex[22] ᓄ�� �� ��������~B �������� ���������, ���� (a)~�������� � 
����~B5 "$l\asg i+1$" ��~"$l\asg i$"? (b) 瀌����� � ����~B4 "$u\asg i-1$" 
�� "$u\asg i$"? (c) ⍅��� ��� ���������?

%% 500
\ex[15] ꀊ�� ����� ������ ������������� ������
\picture{���. ���. 500}
ꀊ��� ������� ����� ��������� ��� ������� ������? ��� ���������?

\ex[20] 呋� �����, ������������ ����������~S �� \S~6.1 
(���������������� �����), ������� 638~������ �������, �� ������� ����� 
�������� ���������~B (�������� �����)?

\ex[�24]  ����� $N$ ���������~B � ������� \emph{���������} 
����������������� ������ (��������� $6.1Q'$), ���� ��������������, ��� 
����� ������?

\ex[28] (�.~�.~��������) � ���� ���.~5 ����� ����� ���� �� ����� 
����� "���������" �����, ����������� �� ��������� ������ � 
�����������������, ����� ����� ����������� ��������� ������ ��������� 
������� ��������� ��������. 퀏����� ����������� ��������� ��� \MIX{} � 
���������� ��������� ������ ����� ������� ������.

\rex[M22] ᓄ�� �� ��������~U �������� ���������, ���� �� ������� ���~U1 
���, ��� (a) ��� $i$, ��� �~$m$ ��������������� ������� $\floor{N/2}$; (b) 
��� $i$, ��� �~$m$ ��������������� �������~$\ceil{N/2}$? [\emph{󊀇����:} 
�����������, ��� ������ ��� �������� �� ���: "󑒀������ $i\asg 0$, $m\asg 
N$ (���~$N+1$), ������� ��~U4".]

\ex[�20] (a)~���� ����� �����~$\sum_{0\le j\le \floor{\log_2N}+2} 
|DELTA|[j]$ ���������� � ���������~C? (b)~ꀊ��� ����������� � 
������������ ��������~$i$, ������� ����� ��������� � ����~C2?

\ex[�26] ������ ��������� ������ ��� ���������~C � ������� 
������ ����������� ������� �������� $C1$, $C2$ �~$A$ ��~$N$ �~$S$.

\ex[20] 񓙅������ �� $N>1$, ��� ������� ���������~� �~� 
��������� ������������ � ��� ������, ��� ��� ��������� ����������, 
������������������ ��������� ��� ���� ���������� ������?

\ex[21] ������, ��� �������� \MIX-��������� ��� ���������~C, ���������� 
�������� $7\log_2 N$~������, ����� ������ ������� �������� 
�������������� $4.5\log_2 N$~������?

\ex[20] 퀐������ ������ ��������� ������, ��������������� ������ ���� ���~$N=12$.

\ex[�24] 瀒���������� ������� ����� ��������� � ������ ���� ��� $1\le 
N<16$, ������������ ��� �������, ��� � ��������� ������.

\ex[21] ������, ��� ������������ ��������~F ��� ������ � �����~$N\ge 1$.

\ex[21] � ���.~9 ���������� ��������� ����������� �������� � �������� 
������ 􈁎����� (��.~�~�.~1.2.8). 񓙅������ �� ������� ����� ����� ���� 
���������� � ������������� ������� �������?

\ex[�19]  ����� ���������~$k$ ������������ ������ �������~$k$ 
���������� ����������� ��������� ������, �.~�. �����, ��� ������� 
������� ����� ��������� ����������?

\ex[�21] � ���.~1.2.8-34 (��� ���.~5.4.2-10) �� �����, ��� ����� 
����������� �����~$n$ ������������ ������� �������������� � ���� ����� 
����� 􈁎�����: $n=F_{a_1}+F_{a_2}+\cdots+F_{a_r}$, ��� $r\ge 1$, $a_j\ge 
a_{j+1}+2$  ���~$1\le j<r$ �~$a_r\ge2$. 䎊�����, ��� � ������������� 
������ �������~$k$ ���� �� ����� �� ����~\node{$n$} ����� �����~$k+1-r-a_r$.

%% 501

\picture{���. 9. � ��������, �������������� �� ������� 􈁎�����.}

\ex[�30] ������ ��������� ������ ��� ���������~F � ������� ������ 
������� ��� ������� �������� $C1$, $C2$ �~$A$ ��� ������� ��~$k$, $F_k$,
 $F_{k+1}$ �~$S$.

\ex[�42] ������ ��������� ������ �������� ������� ������ ���������, 
������������� � ���.~14.

\ex[�22] ����� ���������, ����������� ��� �������� ������, ����������� 
�����~$\log_2N$, ��� �������������---$(\phi/\sqrt{5})\log_\phi N$. ���� 
����� ����������---��������, ��� ��� ������� �������� �������� �������� 
����� ������ ����������.

�� $p$ �~$q$---������������� ����� �~$p+q=1$. ���������� �������� ������ 
�� ������� �� $N$~������� � ������������� �������, �������, ������� �� 
��������� ��������� � $(pN)\hbox{-�}$~������, ��������� ��� ��������� 
��� ������� ������. (䋟 ��������� ������ $p=q=1/2$; ��� 
������������ $p=1/\phi$, $q=1/\phi^2$.)

������ ������� ����� ���������, ��������� ��� ������ � 
������� �������~$N$, ����� $C(N)$; ��� ����������� ������������� ������������
$$
C(1)=0, \quad C(N)=1+pC(pN)+qC(qN) \rem{ ��� $N>1$.}
$$
��� ���������� ������, ��� ����� ������� ��������� ����� �������� � 
������������~$p$ �������� � ������ ����� $pN$~��������� � � 
������������ $q$---� ������ ����� $qN$~���������.  �������~$N$ ����� 
���������� �������� ������� �������, ��������� � ���, ��� �����~$pN$ 
�~$qN$ �� �����.
\medskip
\item{a)} �����, ��� $C(N)=\log_b N$ ����� ������������� ��������� 
������������ ��� ���������~$b$. 䋟 ��������� � ������������ ������� 
��������~$b$ ���������� �� ���������� ����� ������.

\item{b)} 텊�� ��������� ���: "� ������������~$p$ ����� ����������������  
��������� ������� ��~$1/p$, � ������������~$q$---��~$1/q$. 
񋅄��������� �������� ������� � ������� ��~$p(1/p)+q (1/q)=2$, ��� ��� 
�������� � �������� ��� �� �����, ��� � �������� �����, ���������� ��~$p$ 
�~$q$". 呒� �� ������ � ���� ������������?
\medskip

\ex[20] 퀐������ �������� ������, ��������������� ����������������� 
������ ���~$N=10$.

\ex[�43] (�.~�.~ߎ �~�.~�.~ߎ.) �����,, ��� ������� ������� ����������� 
���������������� ����� � ������� ������� (��������������) $\log_2\log_2 
N$~���������, ���� $N$~��������������� ������ ����� 
����������� ����������� �������������. ᎋ�� ����, ��� ��������� ������ �� �����
�������� ������ ��������� � ������� $\log_2 \log_2  N$~��������� (������ ���������������).

\rex[25] �������� ��������� ������ �.~᎒��������, ���������� � 
����� ������, "�����������" �������� �� ��������� �� ������ ����� ������. (�
%%502
����� ������ ��������� �� �����, ��� $K_l\le K<K_{u+1}$, �������� �� 
��������� ���������� ���� ���~$l=u$.) 򀊎� ���� ������ �� ���������~B 
���� ������� ��� �������~$N$, ��� ��� �� ���������� �� �� ������� "|JF|," 
�� ���������� �����. (��� ��� ���� ����������� ���������, ��� ��� 
$\log_2  N$ ������ ���;
���� ���~$N>2^{36}$ �������������� ������������� �������������� ��������!)

�����, ��� \emph{�����} �������� ������, ��������������� ��������� 
������ � ��������������� �� ���� ������������ ($<$, $=$, ���~$>$), ����� 
���������� � ��������, ��������������� �� ���������� ����� ���� �� ���� 
������������ ($<$ ���~$\ge$). � ���������, ������������� ����� �������� ��������~C. 

\rex[23] ��� �������� ������ �������� ������� �������� ������������� 
� ���������������� ������� ������ � ����������� ������ ����. (�. � 
�.~2.3.4.5.) ������� ����������� ����� ������, ���������� �� 
����� �������������. [\emph{󊀇����:} ����� �� � �������� ������ 
������������ ��������� ��~$2$ ������ ������� ��~$2$?]

\rex[�25] ��������, ��� � ��������� ������ ������� $a_k$~���������� � 
$b_k$~������� ����� �� ������~$k$, $k=0$, $1$,~\dots. (ꎐ��� ��������� �� 
������� ������.) �, ��� ���.~8 ����� $(a_0, a_1,~\ldots, a_6)=(1, 2, 4, 4,
 1, 0)$ � $(b_0, b_1,~\ldots, b_6)=(0, 0, 0, 4, 7, 2)$. (a)~�����, ��� 
���������� ������� �������������� �����������, ����������� ������������ 
������� $A(z)=\sum_{k}a_kz^k$ �~$B(z)=\sum_k b_kz^k$. (b)~������������� 
������������ ��� ������� ������ �� ��������� ������ ����� ������������ 
������� $g(z)=zA(z)/N$, � ��� ��������� ������ ������������ ������� ���� 
$h(z)=B(z)/(N+1)$. (� ������������ �.~6.2.1 $C_N=\mean(g)$, 
$C'_N=\mean(h)$, � �����������~(2) ��������� ��� ��������.) 퀉���� 
����������� ����� $\var(g)$ �~$\var(h)$.

\ex[22] �����, ��� ������ 􈁎����� ������� � ����������� ����������� 
�������� �� ���� ������.

\ex[M30] (X.~�.~񒎓� � �.~눍�.) ���������� ������� ������, ���������� 
������ �� ���������� ������ � ������������ ������������ $k$~�����������. 
 ������ ���� ������ ������������ $k$~�������� $i_1$, $i_2$,~\dots, 
$i_k$  � �� ��������� $k$~������������� ���������: ����~$K=K_j$ ��� 
����������~$j$, ����� ��������� ������, � ��������� ������ ��������� � 
���������� ���� ������, ����������� �� $2^k$~��������� �������~$K<K_{i_j}$ 
���~$K>K_{i_j}$, $1\le j\le k$.

�����, ��� ����� ������� ���~$N\to\infty$ ������ ��������� � ������� 
�� ������� ���� $\log_{k+1}N$~�����. (�����������, ��� ��� ����� � 
�������, ����� ��� � �������� ������, �������������.) (獀���, �� 
��������� � ���������������� �������� ������� �� ���������� � �������� 
�� � $k$~���, ��� ����� ���� �� �������, � ���� � $\log_2(k+1)$~���. � 
���� ������ �������� ������ ��������� ������������ ��� ���������� ������, 
� �� ���������� ��.)

\subsubchap{�� �� ��������� ������} %% 6.2.2

� ���������� ������ �� ������, ��� ������������� �������  ��������� 
��������� ������ ��������� ��������� ��������� � ������������ �������. 
������������ ��������������� �������� ��������� ���������, ��� ��� 
������~$N$ ����� ���� ������� ������ ����� ��������� ������ �������� ����� 
��������� ����������� ����� ���������. � ������ ����������� 
������ ������������� ������� ������� ��� ������ �������������� �������, 
��� ��� ���������������� ������������ ������� ������ ������� � �������� 
�������� �����������. 呋� �������
%%503
����������� ����������, �� �������� �� ������������� ��������� ������ �� 
������� ������ �� ����������� �������������� ������������ ������.

\emph{߂���} ������������� ��������� ��������� ������ ��������� ������ 
��������� � ������� ������ � ����������� ����������� ����� �� �������. � 
���������� �� �������� �����, �������� ��� ��� ������, ��� � ��� 
����������. 򀊀� �������� �����������
\picture{���. 10.  ል����� ������ ������.}
����� ���������� � ������ ������ ���� ����� ��� �������� ������.

셒��� ������ �� �������� ��������, ����� �������� \emph{����������� 
������ ��������}, ��� ��� ����������, ����������� � ������ ��������� 
��������� ������ ���������� �� ��� �������� ������������ ������������� 
��������. 퀏�����, ������ ������ � ����������� ����� ������� 
������������� �������������, ������������ ���������� � ��������� ��������� 
�� 􎐒���� ��� ������, � ��������� ���� ������ ����� ��������� 
���������� � ���� ���������� � �� ������������ � ������. 苈 �� ������ 
����� ���� ������ ��������� ��� \MIX, � ���������� ����� ������ ����� 
��������� ���������� ����� �������. ������ ������ � �������� �� ������, 
������� ����� ������� � ���� ������, ������� �������� ��� ������������� � 
�������� ���������� ������ ��������, �������� ���� ���������� 
������������� ������� � ���������� �������. 䐓��� ���������, 
������ �������� ������� � \S~6.3 �~6.4.

%%504

� ���.~10 ���������� �������� ������ ������, ���������� �������� 
����������� ������ �������%
\note{1}{獀�� �������, ������������� �� �������: ꎇ����, ⎄����, 𛁛,
 �, 򅋅�, ወ�����, ���, 녂, 䅂�, ⅑�, 񊎐����, 񒐅���,---{\sl �. �����.\/}}.
 呋� ������, ����������� �� ����� ������, �� ����� ������ ����������� 
��������, |SAGITTARIUS|, �� ������, ��� ��� ������, ��� |CAPRICORN|, 
������� ����� ���� ������; ��� ������, ��� |PISCES|,---����� ���� ������; 
��� ������, ��� |TAURUS|,---���� �����; ��� ������, ��� |SCORPIO|,--- � �� 
�������� �� ������� ����~\leaf{8}. �� ��� ���������; ������ �� 
��������� ������ �� ����� \emph{��������} |SAGITTARIUS|, "����������" ��� 
� ������ ������ �������� ����~\leaf{8}. 򀊈� �������, ������� ����� ����� 
��� ����������� ������������ �������. �������~10 ������� ���������������� 
��������, ������� � ������� ������, ������ |CAPRICORN|, |AQUARIUS|, 
|PISCES|, |ARIES|, |TAURUS|, |GEMINI|, |CANCER|, |LEO|, |VIRGO|, |LIBRA|,
 |SCORPIO| � ��������� �������.

� ���.~10 ��� ����� ������ ��������� ����� ������������ �� �������� 
����� |CAPRICORN|, � � ������ ��������� ����� ����� ����. ����������� 
����������� ����������� ��� ������ � ������� ����������� ������ ����. 
��� �������, ��� ��� ������ ������ � \emph{������������ �������} ����� 
������������� ������ � ���������� �������:
$$
\displaylines{
|AQUARIUS|, |ARIES|, |CANCER|, |CAPRICORN|, |GEMINI|, \cr
|LEO|, \ldots, |VIRGO|,\cr
}
$$
��� ��� ������������ ������� ������� �� ����������� ������� ������ 
��������� ������� ����, ����� ������ ����, � ����� ��� ������� ��������� 
(��. � �.~2.3.1).

툆� ������ ��������� �������� �������� ������ � ��������.

\alg �.(�� � �������� �� ������.) 䀍� ������� �������, ���������� 
�������� ������. ��������� ����� ��������� ���������~$K$. 呋� ��� 
��� � �������, �� � ���������� ����� � ������ ����������� ����� ����, 
����������~$K$.

�����������, ��� ���� ������ �������� �� ������� ���� ��������� ����:
$$
\eqalign{
|KEY|(|P|)&=\hbox{����, ���������� � ���� $|NODE|(|P|)$};\cr
|LLINK|(|P|)&=\hbox{��������� �� ����� ��������� ����~$|NODE|(|P|)$};\cr
|RLINK|(|P|)&=\hbox{��������� �� ������ ��������� ����~$|NODE|(|P|)$}.\cr
}
$$
��� ���������� (������� ���� �� ���.~10) �������������� ������� 
�����������~$\NULL$. �������~|ROOT| ��������� �� ������ ������. 䋟 
�������� ��������������, ��� ������ �� �����
%%505
($|ROOT|\ne\NULL$), ��� ��� ���~$|ROOT|=\NULL$ �������� ���������� 
������������.

\st[퀗������ ���������.] 󑒀������ $|P|\asg |ROOT|$. (󊀇�����~|P| ����� 
������������ ���� �� ������.)

\st[񐀂�����.] 呋�~$K<|KEY|(|P|)$, �� ������� ��~\stp{3}; 
���� $K>|KEY|(|P|)$, �� ������� ��~\stp{4}; ���� $K=|KEY|(|P|)$, 
����� �������� ������.

\st[��� �����.] 呋�~$|LLINK|(|P|)\ne\NULL$, ���������� 
$|P|\asg|LLINK|(|P|)$ � ��������� ��~\stp{2}. � ��������� ������ ������� ��~\stp{5}.

\st[��� ������.] 呋�~$|RLINK|(|P|)\ne\NULL$, ���������� 
$|P|\asg|RLINK|(|P|)$ � ��������� ��~\stp{2}.

\st[⑒���� � ������.] (�� ��������; ������ �� �������� $K$ � ������.) 
⛏������ $|Q|\Asg|AVAIL|$; |Q| ������ ��������� �� ����� ����. 󑒀������ 
$|KEY|(|Q|)\asg K$, $|LLINK|(|Q|)\asg|RLINK|(|Q|)\asg\NULL$. (� ����� 
���� ����� ���������� ��������� ��������� � ������ ����� ������ ����.) 
呋� $K$ ���� ������ $|KEY|(|P|)$, ���������� $|LLINK|(|P|)\asg|Q|$; � 
���������  ������ ���������� $|RLINK|(|P|)\asg|Q|$. (� ���� ������ �� 
����� �� ��������� $|P|\asg|Q|$ � ������ ��������� ������ ���������.)
\algend

�������� ��� ������������ ���������� �� �����~\MIXAL. ��������, 
��������, ��� ���� ������ ����� ��������� ���������:
\picture{���. ���. 505}
⎇�����, ����� ����������� �������������� ����� |INFO|. ꀊ � � ��.~2, 
|AVAIL| ���� ������ ��������� ������. 蒀�, ���������� ��������� ��������� 
��� \MIX.

\prog �.(�� � �������� �� ������.) $|rA|\equiv K$, $|rI1|\equiv|P|$,
 $|rI2|\equiv Q$.
\code
LLINK & EQU  &2:3
RLINK & EQU  &4:5
START & LDA  &�           & 1    & �1. 퀗������ ���������.
      & LD1  &ROOT        & 1    & $|P|\asg|ROOT|$.
      & JMP  &2F          & 1
4H    & LD2  &0,1(RLINK)  & C2   & T4. ��� ������. $|Q|\asg|RLlNK|(|P|)$.
      & J2Z  &5F          & C2   & � T5, ���� $|Q|=\NULL$.
1H    & ENT1 &0,2         & C-l  & $|P|\asg|Q|$.
2H    & CMPA &1,1         & C    & T2. 񐀂�����.
      & JG   & 4�         & C    & � T4, ���� $K>|KEY|(|P|)$.
      & JE   &SUCCESS     & C1   & ⛕��, ���� $K=|KEY|(|P|)$.
      & LD2  &0,1 (LLINK) & C1-S & T�. ��� �����. $|Q|\asg|LLINK|(|P|)$.
%%506
     & J2NZ & 1B         & C1-S  & � T2, ���� $|Q|\ne\NULL$.
5�   & LD2  & AVAIL      & 1-S   & T5 ⑒���� � ������.
     & J2Z  & OVERFLOW   & 1-S
     & LDX  & 0,2(RLINK) & 1-S
     & STX  & AVAIL      & 1-S   & $|Q|\Asg|AVAIL|$.
     & STA  & 1,2        & 1-S   & $|KEY|(|Q|)\asg|K|$.
     & STZ  & 0,2        & 1-S   & $|LLINK|(|Q|)\asg|RLINK|(|Q|)\asg\NULL$.
     & JL   & 1F         & 1-S   & $K$ ��� ������ $|KEY|(|P|)$?
     & ST2  & 0,1(RLINK) & A     & $|RLINK|(|P|)\asg|Q|$.
     & JMP  & *+2        & A
1H   & ST2  & 0,1(LLINK) & 1-S-A & $|LLINK|(|P|)\asg|Q|$.
DONE & EQU  & *          & 1-S   & ⛕�� ����� �������. 
\endcode
\progend
��� 13~����� ��������� ������������ �����, ��������� 11~�����---�������. 
␅�� ������ ��������� ���� ����� $(7C+C1-3S+4)u$, ���
$$
\eqalign{
C &=\hbox{����� ������������� ���������};\cr
Cl& =\hbox{����� �������, ����� $K\le|KEY|(|P|)$};\cr
S& =\hbox{ 1 ��� ������� ������ � 0 � ��������� ������}.\cr
}
$$
� ������� ����� $C1={1\over2}(C+S)$; �������������, $C1+C2=C$ 
� $C1-S\approx C2$. ���� ����� ������ �������� ����� $(7.5C-2.5S+4)u$.
\picture{��� 11. �� � �������� �� ������.}
������ ��������� ������, ������������ ������� �������, �������� ������! 
(�. � ����������~6.2.1�.) ���������� �������, ���. � � 
���������~6.2.1F, ����� ���������� �� ������~08 � ���������~�, �������� 
��� ����� ����� ������ ��~$(6.5C-2.5S+5)u$. 呋� ����� ��������, 
���� ������� ������ ��� ����� $14u$ ���~$15u$.

��������~� ����� ������������ � ������ � ������� � �������� 
\emph{���������� �����}. 퀏�����, ���� �� ������������
%%507
��������� � ������� ������������ ���������������, �������� "��������� 
����������---������ �����������" (LIFO), �� ����� ������ ��������� ���� 
���������� �������; ������ ����� ������~(1) ����� ��������� �����. 򀊎� 
����������� ������������� ������ ������ ��������� ������ ��������, 
���������� �� ����������� ���������, �������� ���������������� ��� 
������������� ������������, ����������� � �����������.

\qsection � ��� ������ ���������� ������? 썎��� ������������ ������� 
����������� ������������ ��������~T. 呋� �� ����� ���.~10 ��������� � 
���������� ������� |AQUARIUS|,~\dots, |VIRGO|, a �� � ����������� 
|CAPRICORN|,~\dots, |SCORPIO|, �� �������� �������� �� ����������� ������, 
�������, � ��������, ���������� \emph{����������������} �����. (⑅ ���� 
|LLINK| ��������� �� ~$\NULL$.) ����������, ���� ����� ��������� � 
��������� �������:
$$
\displaylines{
|AQUARIUS|, |VIRGO|, |ARIES|, |TAURUS|, |CANCER|, |SCORPIO|,\cr
|CAPRICORN|, |PISCES|, |GEMINI|, |LIBRA|, |LEO|,\cr
}
$$
�� ������� ��������������� ������, ��� ������ �� �����. (������ ��� ������!)

� ������ �������, ��� �������� ������ �� ������ ���.~10
��������� � ������� ����� ���� $3{2\over11}$~���������, ��� ��������
������ ������������ �������� ����� ���������~3, ������� ����������� ��� 
������ �� ���������� �� ��������� �������� ��������.

䋟 ���������� ������ ����������������� ������ ����� ������ ��������, 
���������������~$\log_2N$, � ��� ������������ ������---$N$. � ���.~2.3.4.5-5 
������������, ���, ���� ������� ��� �������� ������� �� $N$~����� 
���������������, ������� ����� ������ �������������� 
���������������~$\sqrt{N}$. ���� �� ��� ������� �� ���������~T?

� �������, ����� ��������, ��� ����� �� ������ ������� ���� ����� $2\ln N 
\approx 1.386\log_2 N$ ���������, ���� ����� ����������� � ������ � 
��������� �������; ������ ���������������� �������---�������, � �����������---����������.

䎊����� ���� ���� ����������� ������. ��������, ��� ������ �� 
$N!$~������������ $N$~������ � ������ ������������ ������������ ��� 
���������� ������ ����� �������. ����� ���������, ������ ��� 
���������� �����, ����� �� ������� ������ ����� ���������, ��������������� 
��� ������� ��� � ������. 񋅄���������, ���� ����� $C_N$ ���������� 
������� ����� ��������� ��� ������� ������, � ����� $C'_N$---��� ���������,
 �� �������
$$
C_N=1+{C'_0+C'_1+\cdots+C'_{N-1}\over N}.
\eqno(2)
$$
%%508
� �������� ����������� ����� ������� ����������� � �������� ����� (6.2.1-2)
$$
C_N=\left(1+{1\over N}\right)C'_N-1.
\eqno(3)
$$
������� $C_N$ ��~(3) �~(2), �����
$$
(N+1)C'_N=2N+C'_0+C'_1+\cdots+C'_{N-1}.
\eqno(4)
$$
� ����� ������������� ����������� $C'_N$ ��������� �����. ⛗������ ���������
$$
NC'_{N-1}=2(N-1)+C'_0+C'_1+\cdots+C'_{N-2}
$$
����
$$
\eqalign{
(N+1)C'_N-NC'_{N-1}&=2+C'_{N-1},\cr
C'_N&=C'_{N-1}+2/(N+1).\cr
}
$$
� ��� $C'_0=0$, ��
$$
C'_N=2H_{N+1}-2.
\eqno(5)
$$
�����~(3), ����� ��������� ��������
$$
C_N=2\left(1+{1\over N}\right) H_N-3.
\eqno(3)
$$
󏐀������ 6--8 ���� ����� ��������� ����������: ����� ����� �� ������ 
������� ��������~$C_N$ �~$C'_N$, �� � �� ������������� �������������.

\section 񎐒������ �������� � ������. ��������~T �������������� 
��� ������, �� ��� ����� ������� �� ������ ��������� 
���������� \emph{����������}, ��� ��� �� �������� ������������ ���������� 
��������� ������� � ������~5.2.1L. 󌅋� �������������������, �� ����� 
�������� ���� ������� ��������� ������ ����������, ������������� � ��.~5. 
ꎃ�� ���������� ������ ���������, �������� ����������� ������ ��� 
(��������~2.3.1T)---�� "�������" ������ � ��������������� �������.

��� ���������� ���� ����������. ߑ��, ��� � ����~T2 ��� $K=|KEY|(|P|)$ 
���� ����������� ��-�������, ��� ��� �� ���������, � �� ����. 쎆��, 
��������, ����������� �� $K=|KEY|(|P|)$ ��� ��, ��� � �� $K>|KEY|(|P|)$; 
��� ���� ���������� ����� ����������. (瀌����, �������, ��� ������ ����� 
�� ����������� ������ ���������� � ������� �����, ���� �� ��� ����������� 
��������������� ��� ������������ ������.)  ������� ���������� 
������������� ������ ���� ����� �������� � ������ ������������������� 
������, � ���������� ����������. 䐓��� ������� �������� �������� � ������ 
���� ������ ������� � ����� � ��� �� ������; ����������� 
�������������� ���� ��� ������, �� ��� ������� ���������� � ������, 
����� ����������� ����� ���������� ������.

%%509

򀊈� �������, ��������~T, ����������� ������ ��� ����������, ������, �� 
���� � ������. 呋� �� ����� �������� ����� � ����������, ������������� 
����������� ��������� ������� ������������ �������������.

荒������ �������� ������ ����� ����� �������� ���������� �������� � 
������ � �������� �������� ���������� � ����������� ("������� 
����������"), ���� �� ������ ������ ��� ������ ���������� ��������.  
������� � ������������� ������ ������ $N$~������ � ������� ����������� 
�� �� ����� ���������, ��� � � ���������~5.2.2Q (�� ���������� 
������������). 퀏�����, ��� ������� � ������ ������ ���� ������������ � 
$K_1$, � ������ ����, ������� $K_1$, ������������ � ������ ������, ������� 
$K_1$, � �. �.; ��� ������� ���������� ������ ���� ������������ � ������ 
����������� ���������~$K$, � ����� ������ ����, ������� $K$, 
������������ � ������������, ������� $K$ ��������� � �.~�. 񐅄��� ����� 
��������� � ����� ������� ����� $NC_N$. (���, �� ����� ����, ����� 
�������� ���������� ����, ��������~5.2.2Q ��������� ��������� ������ ���������.)

\section 󄀋����. 荎��� ������ ����� ��������� ��� ������ ���� 
�� ��������� �������. 녃�� ������� "����" (����, ��� ��������� �������� 
�����) ��� ����, � ������� $|LLINK|=\NULL$ ���~$|RLINK|=\NULL$. � ���� 
��� ������ �� �����, ���� ����������� ������ �������---���� ������ � ����� 
����� ������� ��� ���������.

� �������� ������� ����� ���������� ���.~10. ꀊ ������� |CAPRICORN|? ⎒ 
���� �� �������: ������� \emph{���������} ��������� ����, ����� ������ 
�������� �����, � ����� ������� ��� �� ����� ����, ������� ������������� 
��������� �������. 퀏�����, �� ���.~10 ������� ��������� |GEMINI|, 
����� |CAPRICORN| ���������� �� |GEMINI|. 򀊀� �������� ��������� ������� 
��������� �������. ��������~D ��������� ��� ����.

\alg D.(󄀋���� �� ������.) ����� |Q| ��������� ����������, ����������� 
�� ���� ��������� ������ ������, ������� ������������ ��� � ���������~T. 
䀍��� �������� ������� ���� ����, �������� �������� ������ ������. (� 
����� ���� �� ����� ��� $|Q|\equiv|ROOT|$, ��� $|Q|\equiv|LLINK|(|P|)$, 
��� $|Q|\equiv|RLINK|(|P|)$ ��� ���������� ����~|P|. �������� �������� � 
������ ��������~|Q| � ������������ � �������������� ���������.)

\st[񑛋�� |RLINK|  �����?] 󑒀������ $|T|\asg |Q|$. 呋� 
$|RLINK|(|T|)=\NULL$, ���������� $|Q|\asg|LLINK|(|T|)$ � ������� ��~\stp{4}.

\st [퀉�� ���������.] 󑒀������ $|R|\asg|RLINK|(|T|)$. 呋�
$|LLINK|(|R|)=\NULL$, ���������� $|LLINK|(|R|)\asg|LLINK|(|T|)$, 
$|Q|\asg|R|$ � ������� ��~\stp{4}.
%%510
\st[퀉�� ������ ������ |LLINK|.] 󑒀������ $|S|\asg|LLINK|(|R|)$. 呋� 
$|LLINK|(|S|)\ne\NULL$, ���������� $|R|\asg|S|$ � ��������� ��� �� ��� ���,
 ���� �� ������� $|LLINK|(|S|)=\NULL$. (򅏅�� |S| ��������� �� 
��������� ����� |Q| ������� ��� ������������ ������.) 퀊����, ����������  
$|LLINK|(|S|)\asg|LLINK|(|T|)$, $|LLINK|(|R|)\asg|RLINK|(|S|)$, 
$|RLINK|(|S|)\asg|RLINK|(|T|)$, $|Q|\asg|S|$.

\st[������� ����.] ⛏������ $|AVAIL|\Asg|T|$ (�.~�. ������� ���� � ��� 
��������� ������).
\algend

�������� ����� �������� ���� ��������, ������ ���� |AQUARIUS|, |CANCER| 
�~|CAPRICORN| ������ ���.~10; ������ ������ ����� ���� �����������. 
⍈��������� ��������, ��������, �������, ��� �������� �� ������� ������ 
$|RLINK|(|T|)\ne\NULL$, $|LLINK|(|T|)=\NULL$; �� ������� ��� ��������� 
�����, ��� ��� �������� � ��� ����, � ������� �� ����������� �����, 
�������� ������ ����������� ����������.

������ � ���������~D ��� ������� ��������� ����� ������ � �����, �� 
�������, ��� ������� ������������������ ��������� �������� � ������� 
�������������� ������, � ���������� ������ ������������� �������� ����. 
� � ���������������� ���������� ����� �� ����������!

\proclaim {򅎐��� � (�.~�.~�������, 1962)}. �� �������� ����������� 
���������~D ���������� ���� ���������� ������ ����� ���������� ��������� ������.

[� ������� ����������, ����������, ����������, ������ �� (10)!] 򀊀� 
������������ �������, ����������, ������ �������. ��� �������� ����� 
�����. �� $\cJ$---������ �� $n$~���������, � $P(\cJ)$---����������� 
���������~$\cJ$, ���� ��� ����� ����������� ��������� ������� � ������� 
���������~T. 텊������ ������� ���������� � ������� ������������, ��� 
������. ����� $Q(\cJ)$ ��������� ����������� ���������~$\cJ$ ����� 
������� � ��������� ������� $n+1$~������ (����������� ���������~T) � 
������������ �������� � ������� ���������~D ������ �� ���� ���������, 
���������� ��������.  ����������~$P(\cJ)$ ��������������, ��� ��� 
$n~$~������������ ������ �������������;
��� ���������� $Q(\cJ)$ �� �������, ��� $(n+1)(n+1)!$~������������ 
������ � ������� ����� ��� �������� �������������. 򅎐��� ����������, ��� 
$P(\cJ)=Q(\cJ)$ ��� ����~$\cJ$.

\proof � ������� ������������� �� �������, � ������������, ������� 
����� ���������� �������, ������������ � �������� ��������� �������� 
\emph{������������}. ������ ������� �������� �� ������������ � ����� 
�������, ��� "����� �������� �� ��������� ������������ ���������� 
�������� �������� ��������� ������������".

%%511

�� $a_1$ $a_2$~\dots $a_{n+1}$---������������ ��������� 
$\{\,1, 2,~\ldots, n+1\,\}$;
�� ����� ���������� �������� �������� ��������~$a_i$, ������� � ���������� 
������������ $b_1$ $b_2$~\dots $b_n$  ��������� 
$\{\,1, 2,~\ldots, n\,\}$. ��� �������� ������ ���� ����������� � 
�����������~� �~D, �.~�. ���� ����������� �� ������, ������������ 
����������������� ��������� $a_1$, $a_2$,~\dots, $a_{n+1}$, � 
�������~$a_i$  � �������������� ������ ������� ��~1 ��~$n$, �� ��������� 
������, ������� ����� ���� ��������� ����������������� ��������� $b_1$ 
$b_2$~\dots $b_n$.

� �������, ���������� ����� �������� ��������. ⎇����� ��� ������:

\medskip{
\narrower
\noindent{\sl 񋓗�� 1:\/}
 $a_i=n+1$ ���~$a_i+1=a_j$ ��� ���������� $j<i$. (���, � ��������, ���� 
������� "$|RLINK|(a_i)=\NULL$".) 󄀋���~$a_i$ �� ������������������ � 
�������� ������� �� ���� ���������, �������~$a_i$.

\smallskip
\noindent{\sl 񋓗�� 2:\/}
 $a_i+1=a_j$ ��� ���������� $j>i$. 瀌����� $a_i$ ��~$a_j$, ������� $a_j$ 
� �������������� ������� � ��������, ������� �� ���� ���������, �������~$a_i$.

}\medskip

퀏�����, ���������� ������������ 4~6~1~3~5~2. 呋� �������� �������, 
������� ����� �������, �������� ��� � ������, �� ���������
{\def\r#1{\roundit{$#1$}}
$$
\matrix{
\r4 & 6 & 1 & 3 & 5 & 2 & = & 4 & 5 & 1 & 3 & 2 \cr
    4&\r6&1 & 3 & 5 & 2 & = & 4 & 1 & 3 & 5 & 2 \cr
    4& 6 &\r1&3 & 5 & 2 & = & 3 & 5 & 1 & 2 & 4 \cr
}
\qquad
\matrix{
4 & 6 & 1 &\r3& 5 & 2  & = & 3 & 5 & 1 & 4 & 2 \cr
4 & 6 & 1 & 3 &\r5& 2  & = & 4 & 5 & 1 & 3 & 2 \cr
4 & 6 & 1 &3  & 5 &\r2 & = & 3 & 5 & 1 & 2 & 4 \cr
}
$$
}
������ ����� ����� ������� $(n+1)(n+1)!$ ��������� ��������, ������� 
����� �����������, ���� �� �������, ��� ������ ������������ ��������� 
$\{\, 1, 2,~\dots, n\,\}$ ����� �������� ��� ��������� ���������� ����� $(n+1)^2$~��������.

���������� ������������ $b_1$ $b_2$~\dots $b_n$ ��������� 
$\{\, 1, 2,~\dots, n\,\}$. ������ $(n+1)^2$~��������, �� ������ ��� 
������ ���� $i, j$ ($1\le i,j\le n+1$).

呋� $i<j$, ������� ��������� �����
$$
b'_1\ldots b'_{i-1} \roundit{b_i} b'_{i+1}\ldots b'_{j-1} (b_i+1) 
b'_j\ldots b'_n.
\eqno(7)
$$
焅�� � ����� $b'_k$ ���������� $b_k$ ���~$b_k+1$ � ����������� ������, 
������ $b_k$ ����������� �������� ��� ���. ��� �������� ������������� {\sl ������~2.\/}

呋� $i>j$, ������� ��������� �����
$$
b'_1\ldots b'_{i-1} \roundit{b_j} b'_i \ldots b'_n,
\eqno(8)
$$
��� ������������� {\sl ������~1.\/}

%% 512

퀊����, ��� $i=j$ ����� ������ ��������:
\picture{���. ���. 512}
������� ���� ����������� {\sl �������~1.\/}

���� $n=4$, ���������� � �������� ������� 25~��������, ���������� � 
������������ 3~1~4~2:
{\def\r#1{\node{#1}}
\ctable{\hfill$#$\hfill\bskip\bskip&&\hfill$#$\hfill\bskip\bskip\cr
   & i=1 & i=2 & i=3 & i=4 & i=5\cr
j=1&\r5~3~1~4~2 &4~\r3~1~5~2 &4~1~\r3~5~2 &4~1~5~\r3~2 &4~1~5~2~\r3\cr
j=2&\r3~4~1~5~2 &3~\r5~1~4~2 &4~2~\r1~5~3 &4~2~5~\r1~3 &4~2~5~3~\r1\cr
j=3&\r3~1~4~5~2 &4~\r1~2~5~3 &3~1~\r5~4~2 &3~1~5~\r4~2 &3~1~5~2~\r4\cr
j=4&\r3~1~5~4~2 &4~\r1~5~2~3 &3~1~\r4~5~2 &3~1~4~\r5~2 &4~1~5~3~\r2\cr
j=5&\r3~1~5~2~4 &4~\r1~5~3~2 &3~1~\r4~2~5 &4~1~5~\r2~3 &3~1~4~2~\r5\cr
}}

������� ������� ������ ����� � $i\hbox{-�}$ �������, � ��� 
��������������~$i$ �� ��������� $(n+1)$ ��������� ��������, �� ������ 
��� �������~$j$; �������������, ��� ������ ������������ $b_1$ $b_2$~\dots 
$b_n$ ��������� $(n+1)^2$ ��������� ��������. 䋟 ���������� �������������� 
�������, ��� ����� ������� $(n+1)^2!$~��������.
\proofend

䎊����������� �������~H �� ������ ��������� �������� ����� ��������, �� � 
�������� ��� ������� �������� ������� ��������. 󏐀������~12 ����������, 
��� ��� �������� ���������� �������� �� ��������� ������� ���~D2 
����������� � ������� ���� ����, ��� � �������� �������.

���������� ������, ������� ��� ���������� ���� � ����~D3. ��������, ��� 
��������� ����, ������������� �� ������~$l$, � \emph{�������} ����, 
��������������� ��������� �� ��� ��� ������������ ������, ��������� �� 
������~$k$. 퀏�����, ��� �������� ���� |CAPRICORN| (���.~10) ����� 
$l=0$ �~$k=3$, ��� ��� ����~\leaf{4} ���������� �� ������~3. 呋� $k=l+1$, 
�� $|RLINK|(|T|)=\NULL$  � ����~D1; ���� $k>l+1$, �� ����� ����������� 
$|S|\asg |LLINK|(|R|)$ (���~D3) ����� $k-l-2$~���. 񐅄��� ��������~$l$ �����
$$
(\hbox{����� ����������� ����})/N;
$$
������� ��������~$k$ �����
$$
(\hbox{����� �������� ����})/N
-(\hbox{���������� �� ������ ������ �������� ����})/N.
$$
���������� �� ������ ������ �������� ���� ����� ���������� �����~$a_i$ �� 
����������� ������������������, ��� $a_i<a_j$, $1\le j<i$ (�������~$a_1$); 
������� �������� ���� ��������, �������� �.~1.2.10,
%%513
����~$H_N$. � ��� ����� �������� ���� �� $2N$ ������ ����� �����������, 
������� ��������~$k-l-2$ �����~$-H_N/N$. 䎁����� ���� ������� ���������� 
�������, ����� $k-l-2$ ����~$-1$, ��������, ��� ��� ��������� �������� 
\emph{�������� $|S|\asg|LLINK|(|R|)$ � ����~D3 ����������� � ������� ����
$$
{1\over2}+{{1\over2}-H_N\over N}
\eqno(10)
$$
���.} ��� �����������, ��� ��� � ��������� ������ �������� ����� 
������������� �������� �������� (��. ���.~11).

⛘� ����������, ��� � ���������~D ��� �������� $|LLINK|(|T|)=\NULL$, ���� 
������� ����� ������� �����. 쎆�� �������� ����� ��� �����~D1 �~D2:
\medskip
D$1{1\over2}$.~[񑛋�� |LLINK| �����?] 呋� $|LLINK|(|T|)=\NULL$, 
���������� $|Q|\asg|RLINK|(|T|)$ � ������� ��~D4.
\medskip
\noindent 󏐀������~14 ����������, ��� ������ ����� ������ ���������~D 
� �������������� ����� ����� �� ������ �� �������, � ������ ���� ������� 
����� ����, ��� ����� ������ �������� ���������~D. � ��� 
������������������ ������� � �������� � ������� ����������� ���������~D 
�������� � ��������, ������� � ���������������� \emph{�����}, ��� 
������������� ������ ��������� ��������; ������� ����� ������ � �������� 
����� ��������� � ����������.

\section ������� ���������. � ��� ��� ��������������, ��� ��� ����� � 
������ ������������ ����� ���� ����������� ������. ���������� ������ 
����� ����� ������, ����� � ������������~$p_k$ ������������ �������, 
$k\hbox{-�}$ ����������� � �������, ������ $p_1+\cdots+p_N=1$.  
���������� ������������� � ��������� ������� (����� ������ �������� 
���������) ����������� ���������~(2) ����������, ��� ������� ����� 
��������� � �������� �������� ������ ����������
$$
1+\sum_{1\le k\le N} p_k(2H_k-2)=2\sum_{1\le k\le N} p_kH_k-1.
\eqno(11)
$$
(�. �~(5).)

퀏�����, ���� ����������� ����������� ������ 爏�� (6.1-8), ������� ����� 
��������� �������� �
$$
H_N-1+H^{(2)}_N/H_N
\eqno(12)
$$
(��������������, ��� �� ��������� ����� � ������� ���������� .��������; ��.
 ���.~18). 􎐌���~(6) ������������� �������� � ��� ���� ������� ��������; 
��� �������� ������ �� ����� ��������� �� ������ ���������.
%%514
퀏�����, �� ���.~12 ���������� ������, ���������� ����������������� 
��������� � ������� �������� ������ 31~�������� ���������������� 
����������� �����. ���������� ������� �������� ��� ������ ������. [�. 
�.~F.~Gaines, Cryptanalysis (New York: Dover, 1956), 226.] 񐅄��� ����� 
��������� ���
\picture{���. 12 31 �������� ��������������� ���������� �����; ������� � 
������� ���������� ������.}
������� ������ �� ������ ������ �����~$4.042$; ��������������� �������� 
�����, ������������ ��������~6.2.1� ���~C, ���������� �� $4.393$~���������.

\section �������� �������� ������� ������. 󌅑��� ��������, ����� 
������ �������� ��������� ��� ������ �� �������, ���� ����� ������������� 
� ������� ���������? 퀏�����, ����������� ������ ��� 31~�������� 
���������������� ����������� ����� ���������� �� ���.~13; � ������� �� 
������� ����� ��������� 3.437 ���������.

葑������ �������� ���������� ������������ ������. � ������ $N=3$ � ��� 
��������������� ������������ $p$, $q$, $m$ ������
%%515
%%515
\picture{���. 13 �������� ������ ������ ��� 31 �������� 
���������������� ����������� �����.}
%%516
$K_1<K_2<K_3$ �������� ���� ��������:
\picture{���. ���. 516}
� ���.~14 �������� ��������� ������� $p$, $q$, $r$, ��� ������� ������ �� 
�������� ����������; ���������������� ������ �������� ��������� �������� 
� 45\% �������, ���� $p$, $q$, $r$ �������� (��. ���.~21).

\picture{���. 14.             焅�� $(p, q, r)$ ���� ������������� ������� 
$(k_1, k_2, k_3)$, ���� ������� ����������; ����� �� ���� �������� (13) 
�������� ���������. � ����, ��� $p+q+r=1$, ������ ������� ���������, 
�������� �� ������� ���� ���������.
}

� ���������, ��� ������� $N$ ����������
$$
\perm{2N}{N}/(N+1)\approx 4^N/(\sqrt{\pi}N^{3/2})
$$
�������� ��������, ��� ��� �� �� � ��������� ��� �� ��������� � ������� 
���������. ����, ����� ��������� �����
%%517
������� ������ ���������� ����������� �������� ������� ������, ����� ����� 
������������� � �� ����������.

� ��� ��� �� ������� ���� ����������� ��� ������� ������; �����������, 
������ ������� ����� �� �����. 퀏�����, 31 ����� (���.~13) ���������� 
���� ����� 36\% ��������� ����������� ������; ��������� 64\%, ����������, 
�������� �� ��������� ������������ ������ ������.

񋅄���������, �������� ������ ����� �������: ���� $2n+1$~����� $p_1$, 
$p_2$,~\dots, $p_n$ �~$q_0$, $q_1$,~\dots, $q_n$, ���
$$
\eqalign{
p_i&=\hbox{ ����������� ����, ��� ���������� ������ �������� $K_i$};\cr
q_i&=\hbox{ ����������� ����, ��� �������� ������ ����� ����� $K_i$ �~$K_{i+1}$}.\cr
}
$$
(� ����������� $q_0$ ���� ����������� ����, ��� �������� ������ ������ 
$K_1$, a $q_n$ ���� ����������� ����, ��� �������� ������ ������~$K_n$.) 
򀊈� �������, 
$p_1+p_2+\cdots+p_n+q_0+q_1+\cdots+q_n=1$, � �� ����� ����� �������� 
������, �������������� �������������� �������� ����� ��������� ��� ������, 
� ������
$$
\sum_{1\le j\le n} p_i(\hbox{������� (\node{$j$})}+1)
+\sum_{0\le k\le n} q_k(\hbox{������� (\leaf{$k$})}),
\eqno(14)
$$
��� \node{j} ���� $j\hbox{-�}$~���������� ���� ��� ������������ ������, a 
\leaf{$k$} ���� $(k+1)\hbox{-�}$~������� ����; ������ ��������� �� ������� 
������. �, �������������� �������� ����� ��������� ��� ��������� ������
\picture{ ���. ���. 517.}
����� $2q_0+2p_1+3q_1+3p_2+3q_2+p_3+q_3$. 퀇���� ��� \dfn{�����} ������; 
������, ��� ������ � ����������� ����� \emph{����������}.  ����� 
����������� ��� ����� ���������, ����� $p$ �~$q$ ������ � ����� �������, 
����� ������ ������ � ����������� ����� ��� ������ ������������������ 
"�����" ($p_1$,~\dots, $p_n$; $q_0$,~\dots, $q_n$).

� �.~2.3.4.5 �� ������� ��������� �������� ��� ���������� �������� � 
����������� ���������� ������ ����, �� ���� ����� �������, ����� ��� $p$ 
��������� ����, � � ����������� �� ������ ������� ����, ������� ���� 
($q_0$,~\dots, $q_n$), ������ ��
%%518
������������� � ������ ������������ ������� ����� �������. 獀���, 
���������� ����������� �����.

⎑���������� ��������� ���������: \emph{����� ��������� ������������ 
������ ����������}. 퀏�����, ����~(15) ���� ����������� ������ ��� 
����� $(p_1, p_2, p_3; q_0, q_1, q_2, q_3)$, �� ����� ��������� ����� 
������ ���� ����������� ��� 
$(p_1, p_2; q_0, q_1, q_2)$, �.~�. ����� ��������� ��������� ����� � 
��������� ����� ������.

���� ������� ������������ �������������� ���������, � ������� ������� 
�������������� ��������� ��� ������� � ������� ����������� ����������. � 
��������������� ��������� ��� �� ����� � �.~5.4.9 ��� ���������� ���� 
������������ �������; ����� ������, ��������� ��� ��������� 
"������������ ����������������", ����� ������ � ��.~7.

����� $c(i, j)$ ��������� ���� ������������ ��������� � ������ $(p_{i+1},
~\ldots, p_j, q_i,~\ldots, q_j)$, � ����� 
$w(i,j)=p_{i+1}+\cdots+p_j+q_i+\cdots+q_j$ ����� ������ ���� �����; $c(i, 
j)$ �~$w(i,j)$ ������������ ��� $0\le i\le j\le n$. � ��� ���������� 
��������� ���� ������ � ������~\node{$k$} ����� 
$w(i,j)+c(i, k-1)+c(k,j)$, �����
$$
\eqalign{
c(i,i)&=0;\cr
c(i,j)&=w(i,j)+\min_{i\le k <j} (c(i,k-1)+c(k,j)) \rem{ ��� $i<j$.}\cr
}
\eqno(16)
$$
呋� $i<j$, �� ����� $R(i, j)$ ��������� ��������� ����~$k$, ��� ������� 
����������� ������� �~(16); ��� ��������� ���������� ��������� ����� 
����������� �����������.

񎎒�������~(16) ��������� ����� ��������~$c(i, j)$ ���
$j-i=1$, 2, 3,~\dots, $n$; ���������� �������� ${1\over2}n^2$ ����� 
��������, � �������� ����������� ����������� ��� �������������� 
${1\over6}n^3$ �������~$k$. ��� ������, ��� ����������� ������ ����� ����� 
�� $O(n^3)$~������ �������, ��������� $O(n^2)$~����� ������.

� ������ ������� ������ ���������� ������� ���~$n$ ����� ���������, ���� 
��������������� ��������� "������������". �� $r(i,j)$ ���������� 
������� ��~$R(i,j)$; ��� ����� �������� ��� ���������~$R(i,j)$, ��� 
���������� ������ �������������. � ���� ���������� ���.~27 ����� 
���������� $r(i,j-1)$ �~$r(i+1, j)$ �������~$r(i, j)$ ����� ������ � ��������
$$
r(i, j-1)\le r(i,j) \le r(i+1, j)
\eqno(17)
$$
��� ������� ����������������� �����. 򅏅�� �~(16) ������ $i-j$ ����� 
��������� ���� $r(i+1, j)-r(i, j-1)+1$ ��������~$k$.
%%519
��� ����� ������, ���� $j-i=d$, ����������� ������
$$
\sum_{\scriptstyle d\le j\le n\atop\scriptstyle i=j-d}
(r(i+1,j)-r(i, j-1)+1)=
r(n-d+1,n)+r(0, d-1)+n-d+1<2n,
$$
������� ����� ���������� ����������� ��~$O(n^2)$.

��������� ��������� �������� ������� ����.

\alg K.(퀕������� ����������� �������� �������� ������.)
䀍� ��������������� ���� ($p_1$,~\dots, $p_n$; $q_0$, $q_1$,~\dots, 
$q_n$).  �������� ��������� ��������� �������� �������~$t(i,j)$, 
������� ����������� (� ��������� ���� ������) ���� ��� ����� 
($p_{i+1}$,~\dots, $p_j$; $q_i$,~\dots, $q_j$). ⛗�������� ��� �������:
$$
\matrix{
c[i,j]\hbox{---���� $t(i,j)$,\hfill} & 0\le i\le j\le n;\cr
r[i,j]\hbox{---������ $t(i,j)$,\hfill} & 0\le i\le j\le n;\cr
w[i,j]\hbox{---������ ��� $t(i,j)$,\hfill} & 0\le i\le j\le n;\cr
}
$$
���������� ��������� ������������ ��������~$r$: ���� $i=j$, ��
$t(i,j)$ �����; ���� $i\ne j$, �� ����� ���������� ��������
$t(i, r[i,j]-1)$, � ������---$t(r[i,j], j)$.

\st[퀗������ ���������.] 䋟 $0\le i \le n$ ���������� $c[i, i]\asg0$,
$w[i,i]\asg q_i$  �~$w[i,j]\asg w[i,j-1]+p_j+q_j$ ���~$j=i+1$,~\dots, $n$. 
瀒�� ��� $1\le j \le n$ ���������� $c[j-1,j]\asg w[j-1,j]$ �~$r[j-1,
j]\asg j$. (���� ������������ ��� ����������� �������, ��������� �� ������ ����.)

\st[���� �� $d$.] ⛏������ ���~\stp{3} ��� $d=2$, 3,~\dots, $n$; 
����� ����� �������� ��������� ������.

\st[���� �� $j$.] (� �����, ������� ������� ����������� ������� � ����� 
��� $d$~������. ��� ���������� ��� ����������� ������� � $d$~������.) 
⛏������ ���~\stp{4} ��� $j=d$, $d+1$,~\dots, $n$.

\st[퀉�� $c[i,j]$, $r[i,j]$.] 󑒀������ $i\asg j-d$, ����� ����������
$$
c[i,j]\asg w[i,j]+\min_{r[i,j-1]\le k \le r[i+1, j]} (c[i,k-1]+c[k,j])
$$
� ������� � $r[i,j]$ ��������~$k$, ��� ������� ����������� �������. (� 
���.~22 ������������,  ��� $r[i, j-1]\le r[i+1, j]$.)
\algend

ꀊ ������ ������ ���������~K ���������� ���.~15, ��������� 
������������� ��������� KWIC ("key-word-in-context"---"�������� ����� � 
���������"). 瀃������ ���� ������ ������ ������ ����� {\sl ACM Journal\/} 
���� ������������� ����� �������, ����� ������� ����� ������� ��������� 
��������������� ���� ������. ���, ��������� ����� ����� "|THE|" �~"|EQUATION|"
%%520
\picture{  ��� 15. �������� �������� ������ ������ ��� ���������� 
��������� KWIC.}
%%521
���� �������� ���������������� � �� ������ � ���������. ��� ����������� 
����� � ������� �� ��������� ������������ �� ���.~15 ����������� ������. 
瀌����, ��� ����� ��������, ��� "On the solution of an equation for a 
certain new problem" ("� ������� ��������� ��� ��������� ����� ������"), 
���� �� ��������� ���������������, ��� ������ �� ������ �� � ���������! 
脅� ���������~KWIC ����������� �.~�.~뀍� 
[{\sl Amer. Documentation,\/} {\bf 11} (1960), 288--295]. ������ 
���������~KWIC �������� � ������ 
[W.~W.~Youden, {\sl JACM,\/} {\bf 10} (1963), 583--646].

 ���������� ���������~KWIC ����� ���� ������������ �������� ������ 
������ ��� ��������, ����� �� ������� �� ��� ���� ����� � ���������. 
�������� ��������� ����, ���������� � ���������, ������������� ������� 
���� ������ ���.~15;
���, � ���������� ������ {\sl JACM\/} ��~1954--1963~��. ����������� ����� 
277~����, ������������� �� �������� ����� "|PROBLEMS|" �~"|SOLUTION|".

� ���.~15 ���������� ����������� ������, ���������� � ������� ���������~K 
���~$n=35$. 獀�����~$r[0,j]$, ����������� ��� $j=1$, $2$,~\dots, $35$, 
����� (1, 1, 2, 3, 3, 3, 3, 8, 8, 8,  8, 8, 8, 11, 11,~\dots, 11, 21, 21, 
21, 21, 21, 21); ��������~$r[i, 35]$ ���~$i=0$, 1,~\dots, 34 ����� (21, 21,
~\dots, 21, 25, 25, 25, 25, 25, 25, 26, 26, 26, 30, 30, 30, 30, 30, 30, 30,
 33, 33, 33, 35, 35).

"���������� �������"~$q_j$ ������� ������ �� ����������� ��������� 
������; �� ���.~16~(a) ��������� ����������� ������, ������� ���������� �� 
��� �������~$q_j$. � �� ����� � ���������� �������~$p_i$; �� ���.~16~(b) 
���������� ����������� ������ ��� �������~$p_i$. ⅐����� � ������� 
������ ������. 䅐��� ���.~15 ������� � ������� ���� $4.75$~���������, � 
������� ���.~16---��������������~$5.29$ �~$5.32$. (��� �������� ����� � 
������ ������ ��� �� ����� �������� ���.~16.)

� ��� ��������~K ������� $O(n^2)$~������� � ������������, ��� 
������������� ��� �������~$n$ ���������� ��������������. ꎍ����, � ���� 
������ ����� �� ������������ ������ ������ ������, � ����� � ���� ����� 
��� ����� �����������. 䀂���� �����������, ��� ����� ����� ����������� 
��� ����� ����������� ������, ���� $n$ ������.

� ������, ��� ���� ������� ������ � ������� ���������� ������ � ������� 
����� � �������� ������� ��������; �� ������ ����� ���������� � ����� 
������ (��.~���.~20), ��� ��� �� ������������ ����~$q_j$. 䐓��� ������ 
������� � ������ �����~$k$ ����� �������, ����� ������������ ��� 
������������� ��������� $\max(w(0, k-1), w(k, n))$ ��� ��� ����� ������. 
���� ������ ����� ��������, ��� � �������� ����� ����� ���� ������ ���� � 
����� �����~$p_k$. ���  ᝉ�� �������, ��� ������������ ������ 
����� ����� ���������� ����� ����, ������� � �����������.

%%522

�.~�.~󎋊�� �~�.~�.~㎒��� [Graph Theory and Computing (Academic Press, 
1972)] ���������� ����� ������������������ ���������, ���������� ��� 
������������� ������: ����������� �������� ������������� � �������������� 
����, �� ������ ������ ����������� ������ �� ��������� ����� ������ ��� 
����� ��� ���������� ���� � ������������ ������� �����~$p_k$. �������~17
\picture{���. 16. �������� �������� ������� ������, ���������� �� 
�������� ������ ���.~15, (a) �� ����������� ������� �������; (b) �� 
����������� ���������� �������.}
����������, ������ ���� ����� �������: ���� �� ��������� $c(0, k-1)+c(k, 
n)$ ��� ������� ��~$k$ ��� ������ KWIC (��. ���.~15), �� ������, ��� 
��������� ����� ������������ � ��������~$p_k$.

%%523

򀊎� ����� "������ ����" ����� ������������ ��� �������~$n$ ��� ������ 
����� � ��� ��������� ����� � ������ �����������. 呋� ��������� 
���������� ��������� ���������, ����� ��������� ��������~K. 
�������������� ����� ���� �������� ������� ������� (�������� ����������),
 �� 2--3\% ���� ��������, � ������� ���� $O (n)$~������ ������������ � 
$O(n \log n)$~������
\picture{���. 17. ������ ���� ��� ������� �����~$k$ (����� �� ���  
������� ������� ������� ������� ����).
}
�������. � ����� ���� �.~������� �������, ��� ���������� $O(n)$~������ 
�������, ���� ������������ ���������� ��������� ������ [ACM. Symp. Theory 
of Comp., 7 (1975), 240--244].

\section *�������� ��-򀊅��. � ����������� ������, ����� ���~$p$ ����� 
����, �.~�.~�� �~�.~�.~򀊅� ������� ������������� ������ ���������� 
����������� �������� "����� �����"; ��� ������������� ���������� 
�������� ������ �� ����� ������� $O(n)$~������ ������������ �~$O(n\log 
n)$~������ ������� � ������ ������, �� ������� � ������������, � 
\emph{�������������} �����������. �������� ��-򀊅�� ����� ������� ���.

\noindent $\bullet$~{\bf ���� 1.} ꎌ�������. 퀗���� � "������� 
������������������" �����, ���������� ������ \emph{�������} �����
\picture{ ���. ���. 523}
瀒�� ��� �� ����� ������������ ��� ����~$q_i$ �~$q_j$ ���~$i<j$, ������� 
������������ ���~$q_i+q_j$, ��������� $q_j$ �� ������������������ � 
�������� ����, ����������~$q_i$, �� \emph{����������} ����
\picture{ ���. ���. 523}
%%524
ꎌ���������� ����� ������������ ���� �����~$(q_i, q_j)$, 
��������������� ��������� ��������:

{\medskip\narrower
\item{i)}~셆�� $q_i$ �~$q_j$ ��� ������� �����. (��� �������� ������ 
�������, ���������� ������ �������� �� ������ ��������.)

\item{ii)}~񓌌�~$q_i+q_j$ ���������� ����� ����~$(q_i, q_j)$,  
��������������� �������~(i).

\item{iii)}~荄���~$i$ ��������� ����� ����~$(q_i, q_j)$, ��������������� 
�������� (i), (ii).

\item{iv)}~荄���~$j$ ��������� ����� ����~$(q_i, q_j)$, ��������������� 
�������� (i)--(iii).
\medskip}

\noindent $\bullet$~{\bf ���� 2.} ��������� �������. ꎃ�� ����~1 
��������, � ������� ������������������ �������� ������������ 
����. ����� ��� ������� ������~0. 瀒�� ���������� ���� ����~1 � 
�������� �������, ����� ������� ������� ���� �������� �������, ���, ���� 
(19)~����� �������~$l$, ����~$q_i$ �~$q_j$, ����������~(19), �������� 
�����~$l+1$.

\noindent $\bullet$~{\bf ���� 3.} ������������. 򅏅�� � ��� ���� 
������������������ ������� ����� � �������
\picture{���. ���. 524}
⍓������� ����, �������������� � �����~1 �~2, ������ ��������� �� 
�������������---�� ����� ��������� ����� ���� ����� ���������� �����~$(q_i, 
q_j)$ �� ��������� ����� ��������:

{\medskip\narrower
\item{$\hbox{i}'$)}~󇋛, ����������~$q_i$ �~$q_j$, ������ ���� ��������� �
������� ������������������.

\item{$\hbox{ii}'$)}~ ������~$l_i$ �~$l_j$ ������ ���� ������������� 
����� ���� ����������.

\item{$\hbox{iii}'$')}~荄���~$i$ ������ ���� ����������� ����� ����~$(q_i,
 q_j)$, ���������������~($\hbox{i}'$) �~($\hbox{ii}'$).
\medskip}

\noindent 펂��� ����~(19) ������������� �������~$l_i-1$. ል����� 
������, ����������� � ���� ����, ����� ����������� ���������� ����� ���� 
����� ���� �������� ��������, ������� ���� ������� ����� ���� (����� 
�������) $q_0$, $q_1$,~\dots, $q_n$.

�������~18 ������������ ������ ����� ���������; ������ �������� 
������������� ������� ����~\], |A|, |B|,~\dots, |Z| � ���������� ������. 
� ������� ����~1 ������ ����������� ����~\node{6}, ���������� ������� 
����~|J| �~|K|, ����� ����~\node{16} (����������� |P| �~|Q|), �����
\picture{���. ���. 524}
%% 525
\picture{���. 18.  �������� ��-򀊅��, ����������� � ������ � �������� 
����; ����~1 �~2.}
%% 526
� ���� ������ �� ����� ������� ������������������
\picture{���. ���. 526}
����~(i) ��������� ������������� ��������� ����, ������ ���� ��� 
��������� ����������� ������; ��� ��� ����� �������������� $57+57$, 
����� $63 +51$, ����� $58+64$ �~�.~�.

펌��� �������, ����������� �� ����� ����~2, ���������� �� ���.~18 ������ 
�� ������� ����. � ���������� ������������ (����~3) �� �������� ������, 
���������� �� ���.~19; ��������, ��� ������� ���.~18 �~19 ����������� 
��������: ���.~18 �� ��������� ��������������� ����� �������. � ���� � 
���� �������� ���������, ��� ��� ������� ���� ����������� �� ���������� �������.

���������� ������� ������, ��� ���� ����� 4, 3, 2, 4; ����� ��������, ��� 
������������ ����������� ������� ��������
\picture{���. ���. 526}
� ���� ������� �����, ��� � ����������� ������ ��� ���������� ����~2 
�~3 \emph{��} ������ ������� ������������� � ���� ����������� ������, 
���� ���� ��� ��������� ������� �����;
����� ��������� ���������������� ����.

� ����� ����� �� ���������� �������������� �������������� ��������� 
��-򀊅��; ������� �������������� �� ��������, � ����� ��������, ��� ��� 
������� �� ����� �������! ����� ����������������� ��������� �������� 
������ �������� ���������, �������, ��� ����~3 ������ �������������� ��� 
���� � ���� ������, �� ����������� ����� �� ��������. 퀏�����, 
 �����������, ��� ����~1 �~2 ������� � ������
\picture{���. ���. 526}
%%527
\picture{���. 19. �������� ��-򀊅��, ����������� � ������ � �������� 
����; ���� 3.}
%% 528
(�.~�. ���� �������� ���� \node{$a$}, \node{$b$}, \node{$c$}, \node{$d$}, 
\node{$e$} � ��������� �������); ��� ����������� � ��������~(i). 瀒�� 
����� ������������ �����
\picture{���. ���. 528}
�� �� ������ ���������� ����~3, ��� ��� ���� ������~3 ���������! 
����~(i) ���� �� ���� �� ����������� �������������� ���������� ����~3,
 � ���������� ����������, ��� ������������, ��������~(22), 
\emph{�������} �� ���������� �� ����~1.

 ���������� ��������� ��-򀊅�� ����� ������� ������������ ������� ��� 
��������� ����� � �����, ����� �������� ��� ������� �����. 퀏�����, 
(20) ����� ���� �� ����������� ������������� ���������, ����������� 
�������������� 
\picture{���. ���. 528}
� ����������� � ���, ����� �� ����� �������, � ����� ��������� �� 
������� ����� ������� (��� ����� ��� ���������� ������~(iii) �~(iv)). � 
������, "�����������" ������������ ������� ����� ���������� ����� ���� 
���������� ��������� ��������. 񎇄���� ������ ����~$57+57$ �������� 
������� ���� ��������. 呋� ������������ ������� ������������ 
�������������� ��������� (��. �.~5.2.3), �� ������ ��� ����~1 ������� �� 
����� $O(\log n)$~��������; ������, ���~$n\to\infty$ ���������� $O(n \log 
n)$~��������. ꎍ����, ��� ���������~$n$ ����� ����������� ����� 
������������ ����� ������������� $O(n^2)\hbox{-������}$ ����������.

�������� �������� ������ ���.~19 ������� �� ������ ��� ������, �� � ��� 
������ �����������: ��������� 0 ��� ����������� ����� ����� ������ �~1 ��� 
������, �������� ��������� ���� ��������� �����:
$$
\vcenter{
\halign{
|#| \bskip & $#$\hfill \bskip\bskip\bskip &&|#| \bskip & $#$\hfill \bskip\bskip\bskip\cr
\] & 000    & I & 1000    & R & 11001 \cr
A  & 0010   & J & 1001000 & S & 1101 \cr
�  & 001100 & K & 1001001 & T &  1110 \cr
C  & 001101 & L & 100101  & U & 111100\cr
D  & 00111  & M & 10011   & V &  111101 \cr
E  & 010    & N & 1010    & W & 111110 \cr
F  & 01100  & O & 1011    & X & 11111100\cr
G  & 01101  & P & 110000  & Y & 11111101\cr
H  & 0111   & Q & 110001  & Z & 1111111\cr
}
}
\eqno(24)
$$
%%529
򀊈� �������, ��������� ����� "|RIGHT ON|" ����� ������������ ��������
$$
|110011000011010111111000010111010|.
$$
瀌����, ��� ���������� ����� ����� �� ���������� ����������� ����� 
�������, ��� ��� ��������� ������ ������������, ����� ��������� ��� ����� 
����� � ���������� ������. 򀊎� ����� ����������� ��������� ���������� 
������� � ���������� ��� ����������� ����� ����� � ������� ����� 4.2~�����.
 ���� ��� ����� ������������ ��� ���������� ������ ������ ��� ��������� 
������������������� ������� ��������� ����������. (�����~$4.2$ 
���������� ��� ����������� � ������� �������� ��������, ���� ��� ����� 
��������� �� $4.1$~����� �� �����, ���� ���������� �� ���������� 
����������� �������. 󌅍������ � ����������� ����������� ������� 
����������� ������������ �� ��������� ����, � ��� ����.)

荒������� ��������������� ������ ����������� ���������� ����� ���� 
�������� ������ �������� �.~�.~㈋������ �~�.~�.~쓐��:

\proclaim 򅎐��� G. 呋� $p_1=p_2=\cdots=p_n=0$, �� ���������� ����� ���� 
������������ ��������� ������ ������ ��������� �����
$$
\sum_{0\le i \le n} q_i \log_2 (Q/q_i) \hbox{\sl �\/} 
2Q+\sum_{0\le i \le n} q_i \log_2 (Q/q_i),
$$
��� $Q= 2\sum_{0\le i\le n} q_i$.

\proof 䋟 ��������� ������ ������ ���������� �������� ��~$n$.  $n>0$ 
���������� ����� �������� ���� �� ������
$$
Q+\sum_{0\le i <k} q_i\log_2(Q_1/q_i)
+\sum_{k\le i\le n} q_i\log_2((Q-Q_1)/q_i)\ge
\sum_{0\le i\le n} q_i \log_2 (Q/q_i)+f(Q_1)
$$
��� ���������� $k$, ���
$$
Q_1=\sum_{0\le i<k} q_i
$$
 �
$$
f(Q_1)=Q+Q_1\log_2Q_1+(Q-Q_1)\log_2(Q-Q_1)-Q\log_2Q.
$$
�������~$f(Q_1)$ �������������� � ��������� ���������� ��������~0 
���~$Q_1={1\over 2}Q$.

䋟 ��������� ������� ������� ����� �������, ��� $Q=1$. �� $e_0$,~\dots,
 $e_n$---����� �����, �����, ��� $2^{-e_i}\le q_i < 2^{1-e_i}$,
%% 530
$0\le i\le n$. ����� ���� $C_i$ �� ����� � ������, ��������� $e_i+1$ 
������� �������� ���� 
�����~$\sum_{0\le k<i} q_k+{1\over2}q_i$, ���������� � �������� �������. � 
���.~35 ������������, ��� $C_i$ �� �������� ��������� �����������~$C_j$ 
��� $i\ne j$; ������ �������, ��� �� ����� ��������� �������� ������ 
������, ��������������� ���� �����. ⎇�������� � ������� ���.~19, ����� 
��������, ��� $C_0=0001$, $C_1=00110$, $C_2=01000001$, $C_3=0100011$ � 
�.~�.; ������ ���������� �
\picture{���. ���. 530}
(臁������� ���� � ����� ����� ����� ����� ���������.) ⇂������� ����� 
���� ��������� ������, ������������ ����� ����������, �����
$$
\le \sum_{0\le i\le n} (e_i+1)q_i
<\sum_{0\le i\le n}q_i(2+\log_2(1/q_i)).\endmark
$$

셒����, �������������� � ������ ����� ��������������, ����� ����������, 
��� ���������� ����� ���� \emph{������} ���������
������ �� ������, ���  $\sum_{0\le i\le n} q_i\log_2 (Q/q_i)$, ���������� 
�� ������� ����� ����� �������. (���� ��������������� 
��������� ����������� ꋎ�� �������.) 򀊈� �������, ���������� ������� 
����� ����� ������� ����������� ���� ������������ ������ �� ������, ��� �� 
���� ���� �������������� �������, �.~�. �� ��������� ����� �����.

\section 葒���� � ������������. ������������� ������ ������ �� ������ 
���� ������� ���������� ����������� ��������������� � ������ 50-� �����. � 
���������������� ���������, ������������ �������� 1952~�., �.~�.~䓌� 
������ ������� � ������ � ���������� ����:

%%531
\noindent
"�� ������� �������, �� ������� �������� $2^n$~���������, � ������ �� 
��� ����� �������� �����. ������������ ����� ���������:
\enumerate
\li ������� ������ ������� � ��������� ��� �� ������ $2^{n-1}$, �.~�. � 
�������� ������� ������.

\li ������� ��������� �������. 񐀂���� ��� � ������.

\li 呋� �� ������, ��������� ��� �� ������~$2^{n-1}+2^{n-2}$.\goodbreak
呋� �� �� ������, ��������� �� ������~$2^{n-2}$.~\dots"
\enumend

䐓��� ������ ����� ������� � ������ ���� ������� �.~�.~󈋅���; ��, � 
��������, �������� ������������ ������������, �������� ���, ������� 
����� ����������� � �. 6.2.4;
����� ������� � �������� ������ ��� ����� ���������� �������� 
�.~�.~ᅐ�����-� [{\sl Comp. J.,\/} {\bf 2} (1959), 5].

��� �������������� �������� ������� � ������ ����������� �.~�.~󈍄�� 
[{\sl Comp. J.,\/} {\bf 3} (1960), 84--88], �.~�.~ᓒ� �~�.~ꎋ��� [{\sl 
Information and Control,\/} {\bf 3} (1960), 327--334] �~�.~�.~�������� 
[{\sl JACM,\/} {\bf 9} (1962), 13--28]. ⅐�����, ��� ������ ��������� 
���� ����� ����������, � �� �������������� �������~(6) �������� ����� 
��������� ��������� ���������� ���� �� �����. � ����������� ������� ��� 
���������� ����������� ��������� ������� ����� ���������: 󈍄�� �������� 
�������� ���������� �������� � ������, ᓒ �~ꎋ�� ��������� 
������ ���������������� ���������� �� ������ $2^n-1$~��������� �������� 
����������������� ������ (��. ���.~4), ������� ��������� ���� �������� � 
������ ����� ����� �������� ������� � ������ � �������� ������� ����������.

脅� \emph{�����������} �������� �������� ������ ���� ������� ������� ��� 
�������� ������ $p_1=\cdots=p_n=0$ � ����� � �������� ������������ ����. 
� ����� ���������� ������ �.~㈋����� �~�.~쓐� 
[{\sl Bell System Tech.~J.,\/} {\bf 38} (1959), 933--968] 
����������� ��� �������� � �� ����� � 
������� �������� �����������. ㈋���� �~쓐 ��������, ��� ����������� 
������ ����� ��������� �� $O(n^3)$~�����, ��������� �����, �������� 
���������~K, �� ��� �����������~(17). �.~�.~�������� [A Programming 
Language (Wiley, 1962), 142--144] ���������� ���������� 
\emph{������} ������, ����� ���~$q$ �����~0. � �����������, ��� ������ 
����� �����������, ���� ������ ������� ���, ����� ��� ����� ����� �������� 
����������� ������ � ������� �����������; �� ������, ���, � ���������, ��� 
���� �� ��������. �.~�.~ꍓ� [{\sl Acta Informatica,\/} {\bf 1} (1971), 
14--25, 270] ������������ ���������� ������ ����� ����� $p$ �~$q$ � 
�������, ��� �������� ����� ���� ������ � $O(n^2)$~�����; �� ����� ������ 
������ ���������� ������������� ������� � �����������, ��� ������� � 
������ �������� "��������������� �����" ��������������� �����. 
�.~�.~�� ��������� ��� ��������� ����� ����������� ���������� ���
%%532
������~$p=0$; ��-�� ��������� ������ ���� ������ ����� 
������� �������������� �������������� ����� ���������, �� � ����� ������ � 
1969~�. �.~�.~�� �~�.~�.~򀊅� ���������� � ����. 
[{\sl SIAM J.  Applied Math.,\/} {\bf 21} (1971), 514--532.]

\excercises
\ex[15] ��������~T ��� ������������� ���� ��� �������� ��������. ꀊ�� 
����� ������ ���������, ����� �� ����������� � ������ �������?

\ex[20] 臌����� ��������~T ���, ����� �� ������� � \emph{��������������} 
��������� (��.~� �.~2.3.1; �� ����� �������� ����� ��������� ������������ �����).

\rex[20] � \S~6.1 �� ������, ��� ��������� ��������� ��������� 
����������������� ������~6.1S ������ ��� ������� (��������~6.1Q). 쎆�� �� 
�������� �������� ������������ ��� ��������� ������ ���������~T?

\ex[�24] (�.~�.~ᓒ �~�.~ꎋ��.) 䀍� $N$~������ � ��������� �������;
�����������, ��� �� ���������� ������~$2^n-1$ ��� ���������� 
�������� ����������������� ������, ������� $2^k$~������ �� �������~$k$, 
$0\le k<n$. 瀒�� �� ��������� ��������~T ��� ������� ���������� ������. 
퀉���� ������� ����� ��������� ��� ������� ������. [\emph{󊀇����:} 
������������~(2).]
 
\rex[�25] 퀇����� |CAPRICORN|, |AQUARIUS| �~�.~�. ����� 
����������� $11!=39916800$~��������� ��� ������� � �������� ������ ������. 
(a) 񊎋��� ����� ������������ �������� � ���.~10? (b)~񊎋��� 
������������ �������� � ������������ ������, �.~�. �� ���� ����� |LLINK| 
���~|RLINK| ����� ���������~$\NULL$?

\ex[�26] ������ ����� $P_{nk}$ ���������� ������������ $a_1$ 
$a_2$~\dots $a_n$ ��������� $\{\, 1, 2,~\dots, n\,\}$, �����, ���, ���� 
��������~T ������������ ��� ���������������� ������� $a_1$, $a_2$,~\dots, 
$a_n$ � ������������� ������ ������, ����� $k$~��������� ������������ ��� 
�������~$a_n$. [� ���� ������ �� ����������� �����������, ������������� 
��� ������� $a_1$,~\dots, $a_{n-1}$. � �������� � ������ ������������ 
$C'_{n-1}=\left(\sum kP_{nk}\right)/n!$, ��� ��� ��� ���� ������� ����� 
���������, ������� ������������ ��� ��������� ������ �� ������ �� 
$n-1$~���������.]

{\medskip\narrower
\item{a)}~䎊�����, ��� $P_{n+1,k}=2P_{n,k-1}+(n-1)P_{n,k}$. 
[\emph{󊀇����:} ����������, ����������� �� $a_{n+1}$ ����~$a_n$.]

\item{b)}~퀉���� ������� ������� ��� ������������ 
�������~$G_n(z)=\sum_k P_{nk}z^k$ � ����������� �� ��� ��������� $P_{nk}$ 
����� ����� 񒈐�����.

\item{c)}~���� ����� \emph{���������}~$C'_{n-1}$?

\medskip}

\ex[M30] (�.~�.~����� �~�.~�.~䝍�.) ꀊ�� ������� ����� 
��������� ����������� ��� ��������� $m\hbox{-��}$ �� �������� �������� 
����� ������� � ������������� ������ ������ $n$~��������� � ��������� �������?

\ex[�38] �� $p(n, k)$ ���� ����������� ����, ��� ������ ����� 
����������� ���� ������, ������������ ����������~T �� $n$ �������� 
������������� ������, �����~$k$ (����� ����������� ���� ������ ����� ����� 
���������, ������������ ��� ���������� �������� � ������ �� ���� ��� ����������).
(�)~퀉���� ������������ �����������, ������������ ��������������� 
������������ �������. (b)~⛗������ ��������� ����� �������������. 
[焅�� ����� ���� ������� ��������� ���������� �.~1.2.7!]

\ex[41] � ��������, ��� ����� � �������� �� ������ ������� ���� ����� 
$2\ln N$~���������, ���� ����� ����������� � ��������� �������; �� � 
���������������� ������� ����� �� ���� ���������. 葑������� �����������,
��������� ������ ������� � ������ ����������� ������� 
�������� ����������� �/��� ����������. 䀄�� �� �������������� �������� 
������� ��������� ���������� ������ ���������������� �������� ������ ������?

%%533

\rex[22] ��������, ��� ������������ �� ���������� ������� ������ � 
�������� ������ ������, �� ����� �������, ��� ���� ����� ������������� �� 
� ��������� �������. ����� ������, ����������� ��� �� ����� 
������������ ����� �� ������, �������� ��������� ������� �����.

\ex[20] 퀉���� ������������ ���������� ������������ $|S|\asg 
|LLINK|(|R|)$ (� ����~D3) ��� �������� ���� �� ������ �������~$N$.

\ex[�22] ꀊ ����� (� �������) � ����~D1 ���������� �������� ���������� 
��~D4, ���� ��������� ��������� ���� �� ���������� ������ �������~$N$? 
(�. �������������� �������~H.)

\rex[�23] ᓄ�� �� ��������� ������, ���������� � ���������� 
�������� ����� ���������� ������ ����������� ���������~D?

\rex[22] 䎊�����, ��� ����� ���� ������, ������������ ���������� D
� �������������� ����� D$1{1\over2}$, �� ������, ��� ����� ���� ������, 
������������ ������������������ ����������. 퀉���� ������, ����� 
���~D$1{1\over2}$ ������������� ��������� ����� ����.

\ex[�47] 퀉���� ������ ��������� �������� ������� ������ ���������~� 
����� ������� ������������������ ������� � ��������, ���� � ���������~D  
����������� ����� ���~D$1{1\over2}$.

\rex[25] ߂������ �� �������� �������� \emph{�������������}? � ���� 
��������� �� ���� � �� �� ������, ���� � ������� ���������~D ������� 
���� $X$ �~$Y$; ���� ������� $Y$ �~$X$?

\ex[25] �����, ��� ���� � ���������~D ��������� �������� ������ �� 
����� � �������, �� ��� ����� ������������ ��� �������� ������� ���� �� 
\emph{��������������} ������ � ����������� ����������� �����. (�.~�~���.~2.)

\ex[M21]. �����, ��� ����� 爏�� �������� �~(12).

\ex[�23] 퀉���� ����������� ������� ����� ���������~(11), 
���� �����������~$p_k$ ������������� ������ "80-20", ������������� 
��������� (6.1-11) �~(6.1-12).

\ex[�20] �� �� ��������� � ������ ����� � ������� ���������� ������ 
$p_1\ge p_2\ge\ldots\ge p_N$. 쎆�� �� ��� ������ ���� ����������� 
���� ������������ ������ ������?

\ex[�20] �� $p$, $q$ �~$r$---�������� ��������� �����������, 
������������� �������~$p+q+r=1$. ���� ����� ����������� ����, ��� 
������� I, II, III, IV ���~V (��.~(13)) �������� ������������? 
(����������� ��������� �������� ��������������� �������� �� ���.~14.)

\ex[�20] 䎊�����, ��� ��� ���������� ����~K4 ���������~K 
$r[i,j-1]\le r[i+1,j]$.

\rex[M23] 퀉���� (�� �������� � ������ ���) ����������� �������� ������ 
������, ���� $n=40$, $p_1=5$, $p_2=p_3=\cdots=p_{40}=1$, 
$q_0=q_1=\cdots=q_{40}=0$.

\ex[�25] �� $p_n=q_n=0$, � ��� ��������� ���� ��������������. 䎊�����, 
��� ����������� ������ ��� ($p_1$,~\dots, $p_n$; $q_0$,~\dots, $q_n$) 
����� �������� �������
\picture{���. ���. 533}
� ����� ����������� ��� ($p_1$,~\dots, $p_{n-1}$; $q_0$,~\dots, $q_{n-1}$) 
������.

\ex[�20] �� $A$ �~$B$---�������� ��������� �������������� �����. � 
����������� $A\le B$, ���� ����������� ��������� ��������: ($a\in A$, 
$b\in B$, $b<a$) ������ ($a\in B$ �~$b\in A$). (a)~䎊�����, ��� ��� 
��������� �������� �������� �����������. (b)~䎊����� ��� ������������, 
��� $A\le B$ ����� � ������ �����, ����� $A\le A \cup B \le B$.

%%534

\ex[�22] �� ($p_1$,~\dots, $p_n$; $q_0$,~\dots, $q_n$)---��������������� 
���� �~$p_n+q_n=x$. 䎊�����, ��� ��� $x$, ������������ �� 0 ��~$\infty$, 
� ��� ���������� ($p_1$,~\dots, $p_{n-1}$; $q_0$,~\dots, $q_{n-1}$) 
����~$c (0, n)$ ������������ ��������� ������ ������ �������� "�������� 
����������� ������� ��������" ��������~$x$ � ������ �������� 
��������������. 䐓���� �������, ��������, ��� ���������� ������������� 
����� ����� $l_0>l_1>\ldots>l_m$ � �������������� 
����������$0=x_0<x_1<\ldots<x_m<x_{m+1}=\infty$ �~$y_0<y_1<\ldots<y_m$, 
�����, ��� $c (0, n)=y_h+l_hx$ ��� $x_h\le x\le x_{h+1}$, $0\le h\le m$.

\ex[M33] ����� ������� ���������� �������� �������������� ���� �����, ��� 
��������� ������~$R(i,j)$ ����������� �������� �������� ������ 
������������� ��� $j-i\ge2$ �����������
$$
R(i, j-1)\le R(i,j)\le R(i+1, j),
$$
���������� � ���.~25 (���� ($p_1$,~\dots, $p_n$; $q_0$,~\dots, $q_n$) 
�������������� ����������������). 䎊����������� ���������� ��������� 
��~$j-i$; ���� ������---��������, ��� 
$R(0, n-1)\le R(0,n)$ ��� $n\ge2$, � ������������� �������������� 
����������� ��� $j-i<n$. 
[� ���� ��������� ������ �������, ��� $R(0, n)\le R(1, n)$.]

\medskip
\item{a)}~䎊�����, ��� $R(0, n-1)\le R(0, n)$, ���� $p_n=q_n=0$. (�.~���.~24.)

\item{b)}~�� $p_n+q_n=x$. ����� $R_h$ ��������� ���������~$R(0, n)$ 
����������� ������, ���� $x_h<x<x_{h+1}$, � ����� $R'_h$---��������� 
����������� ������ ��� $x_h=x$  (��.~����������� ���.~26). 䎊�����, ���
$$
R'_0\le R_0\le R'_1\le R_1\le\ldots\le R'_m\le R_m.
$$
���, �� �����~(a) � ���.~25 �������, ��� $R(0, n-1)\le R(0, n)$ ��� ����~$x$.
\medskip

[\emph{󊀇����.} ����������� ������~$x=x_h$ � ������������, ��� ��� ��� ������
\picture{���. ���. 534}
����������; $s<r$ �~$l\ge l'$. 葏�������� ������������� �������� ��� 
�������������� ����, ��� ���������� ����������� ������ � ������~\node{r} 
� �����~\leaf{n} �� ������~$l'$, � ����� ����������� ������ � 
������~\node{s} � �����~\leaf{n} �� ������~$l$.]

\ex[24] 葏�������� ��������� ��������� ��� ��������� ���������������� 
"����������� �������� �����", ���������� �������� �������� ��������� 
������������ ������������ ��������� ������.

\ex[40] ꀊ��� \emph{���������} ��������� �������� ������ ������ ��� 
31~�������� ���������������� ����������� �����? (������� ���� ���� �� ���.~12.)

\ex[M41] 䎊����� ��� ������������, ��� ���� ����������� �������� �������� 
������ ������������� �����������~$c(i,j)+c(i+1, j-1)\ge c(i, j-1)+c(i+1, j)$.

\ex[�20] (a)~呋� ���� ($q_0$,~\dots, $q_5$) �~(22) ����� (2, 3, 1, 1, 3, 
2) ��������������, �� ������ ���������� ����� ���� ������? (b)~���� 
����� ���������� ����� ���� ������������ ��������� ������ ������, 
�������� �� �� ������������������ �����?

\rex[�22] (T.~�.~�� �~�.~�.~򀊅�.) 䎊�����, ��� ����~$q_i+q_j$ 
����� �����, ���������� �� ����~1 ��������� ��-򀊅��, ��������� � 
����������� �������.

\ex[�41] ����� ����� �������� ������ ������, �������������� ����� ������ 
���������~T, ����� �������������� �� ������ ����� ���������~$C$, � 
��������~$7C+C1$. ������� �������� ��� ���������� ����������� ��������
%%535
�������� ������, ���� ����� � ������ ����� ������ ����� 
��������� ����. [ꑒ���, ����� ���� ������ ����� � ��� ���� ������ ���� 
����� �����, � ������� ���� ����� �����, ������������ ����������� 
������������ �������. �.~�~L.~�.~Stanfel, 
{\sl JACM,\/} {\bf 17} (1970),  508--517.]

\ex[41] 퀏����� ��������� ��� ��������� ��-򀊅��, 
��������� $O(n)$~������ ������ �~$O(n\log n)$~������ �������.

\ex[�23] �����, ��� ����, ����������� � �������������� �������~G,
 �������� ��� ���������, ��� $C_i$ ������� �� ���������� �~$C_j$ ���~$i\ne j$.

\ex[�40] (�.~�.~ᝉ��.) ���� ������� ������ � �������~G, ��������, 
��� ���� ������ ������������ ��������� ������ ������ � ���������������� 
������ �� ����������� ������� 
����~$S=\sum_{1le i\le n} p_i+\sum_{0\le i\le n} q_i$, ����������� ��~$H+2$,
 ���
$$
H=\sum_{1\le i\le n} (p_i/S)\log_2 (S/p_i)+\sum_{0\le i\le n} (q_i/S)\log_2(S/q_i);
$$
�� ����� ���� ��������� ������ ������, �������������� ������������ 
��� ���������, ��������� ��������� ������ ��������� ������, 
��������������� ���� ������. ����� �����, ��� ���� ������������ 
��������� ������ ������ �� ���������~$S$, ����������� ��~$H-\log_2(2H/e)$.

\rex[�25] (�.~�.~�� �~�.~�.~򀍜.) �� $n+1=2^m+k$, ���~$0\le k\le 2^m$.
񓙅������ $\perm{2^m}{k}$ �������� ��������, � ������� ��� ������� ���� 
����������� �� ������� $m$ �~$m+1$. �����, ��� ����� ���� ���� 
�������� �� ������ ���� � ����������� ���������� ������ ���� ��� 
������������������ ����� ($q_0$,~\dots, $q_n$), ���� �������� �������� 
��-򀊅�� � ������������������ ($M+q_0$,~\dots, $M+q_n$) ��� ���������� 
��������~$M$.

\ex[�35] (�.~�.~򀍜.) 䎊�����, ��� ����� ���� �������� 
������������ ($p_1$,~\dots, $p_n$; $q_0$,~\dots, $q_n$), 
$p_1+\cdots+p_n+q_0+\cdots+q_n=1$ ������ � ����������� ����� �������� 
������, ���� $p_i=0$ ��� ����~$i$, $q_j=0$ ��� ������~$j$ 
�~$q_j=1/\floor{n/2}$ ��� ��������~$j$. [\emph{󊀇����.} 䋟 ������������ 
������������ ($p_1$,~\dots, $p_n$; $q_0$,~\dots, $q_n$) ������� $c_0=q_0$, 
$c_i=p_i+q_i$ ���~$1\le i\le n$  �~$S(0)=\emptyset$, � ���~$1\le r\le 
\ceil{n/2}$ ������� $S(r)=S(r-1)\cup\{\,i,j\,\}$, ��� 
$c_i+c_j$~���������� �� ����~$i<j$, �����, ��� $i, j\notin S(r-1)$ �~$k\in 
S(r-1)$ ��� ����~$i<k<j$. ����� �������� ������~$T$ � �������� ������ 
�� $S(n+1-2^q)$ �� ������~$q+1$ � � ���������� �������� ������ �� 
������~$q$, ��� $q=\floor{\log_2 n}$. 䎊�����, ��� ���� ����� 
������~$\le f(n)$, ���~$f(n)$---���� ������������ ������ ������ ��� ��������� 
"���������" ������������.]

\ex[�30] (�.~�.~� �~��-꓎~���.) ���������� ����� ���������� ��������� 
������ ������ � ������� ���������~T, �� � ����� ��������:
����� ����� ����� ��������� ���~$2^n-1$, ������ ���������� � �������� 
����������������� ����������� ���� � $2^k$~������ �� ������~$k$, $0\le 
k<n$. 䎊�����, ��� ����� ���������, ������������ �� ����� ���������� 
������ ������, � ������� ����������~$M\log_2 N+O(N)$. (텒����� ��������, 
��� �� ����� ������������� ������ ���������  $O(N)$~������ �������.)

\ex[M50] 쎆�� �� �������� �������� ��-򀊅�� ��� ���������� ����������� 
��������, ���� ������ ���� ����� ������� �� ����~$t$? 퀏�����, ��� 
$t=3$ ������, ����������� ��� ������������������ ����� (1, 1, 100, 1, 1),  
�������� ���:
\picture{���. ���. 535}

%%536

\bye