\input style
\chapno=6\subchno=2\chapnotrue
\subchap{�������� �����} % 6.3
⌅��� ���� ����� ���������� ����� ������ �� ��������� ������, �����
��������������� �� �������������� � ���� ������������������ ���� ���
����. ����������, ��������, ��������� �� ������ �������� "�����������
�������"; �� ������ ����� ������� ����� �� ����� ���������� ��������
��������, ���������� ��� �����, ������������ � ���� �����.

呋� ������� ���� "����������� �������", �� ������ � ����� ������,
���������� �� "��������������", ��� �������� � ����.~1. ��������,
��������� ���������, ����������� �� ������ �������� ������ � 31~��������
���������������� ����������� ����� (��.~�~���.~12 �~13, �.~6.2.2). �
����.~1 ������ ������������ � ���� ��� ���������� ��������� "����";
������ ������ �.~��������� [{\sl CACM,\/} {\bf 3} (1960), 490--500]
��� ����� ����� ��{\it ���}��\note{1}%
{� ��������� �������������� trie (���������� "tree") �
re{\it trie}val---{\sl �. �����.\/}}
 (����������). ᎐ � �������� �������� $M\hbox{-�����}$ �������, ����
�������� ���� $M\hbox{-�������}$ ������� � ������������, ����������������
������ ��� ������. ꀆ��� ���� ������~$l$ ������������ ��������� ����
������, ������������ � ������������ ������������������ �� $l$~�����; ����
���������� $M\hbox{-�������}$ ������������ � ����������� ��
$(l+1)\hbox{-�}$ ������.

퀏�����, ��� ����.~1 ����� 12~�����; ����~1---������, � ������ �����
������� ������ �����. 呋� ������ ���������, ������, �����~|N|, �� �������
�����, ��� ����� ������ ����� |NOT| (��� ��, ��� ��� ��� � �������). �
������ �������, ���� ������ �����---|W|, ����~(1) �������� ��� � ����~(9),
��� �� ������ ����������� ������� �������� ������ �����; ����~(9) ������,
��� ���� ������ ������ ����~|A|, |H| ���~|I|.

󇋛-������� � ����.~1 ������������ � ������������ � ����� �����, ��������
��� \MIX. ��� ��������, ��� ����� �� ���� ����� �������� �������, ��� ���
�� ������ ������ �������� ����� �� �������, ��������� � �������� ��������
������ ������ �����. 셒��� �������� ������������� ������������ �
������� �������������� ���������� "���������� ������" ("Table Look-At") �
����������������� "������ �� ��������" ("Table Look-Up")
[��.~P.~M.~Sherman, {\sl CACM,\/} {\bf 4} (1961), 172--173, 175].

\alg �.(�� �� ����.) �������� ��������� ����� ������ ��������~$K$ �
������� �������, ���������� $M\hbox{-�����}$ ���.
%%573
{
\catcode`\!=\active\def!#1.{\boxit{\hbox{\strut\bskip\tt\hbox to 2.5em{#1\hfill}\bskip}}}
\def\putpar#1{(#1)}
\def\@#1{\strut\hfill$(#1)$}
\catcode`\(=\active\def(#1){\boxit{\hbox{\bskip\tt\hbox to 2.5em{\strut$\putpar{#1}$\hfill}\bskip}}}
\offinterlineskip\tabskip=0pt\htable{򀁋��� 1}%
{"᎐" ��� 31 �������� ���������������� ����������� �����}%
{\vbox{\hbox{\strut\tt #}\hbox{}}&&#\hfill\cr
          &\@{1} & \@{2}& \@{3}& \@{4}& \@{5}& \@{6}& \@{7}& \@{8}&  \@{9}& \@{10}&\@{11}&\@{12}\cr
       \] & !---.&   !A.& !---.& !---.& !---.&   !I.& !---.& !---.&  !---.&  !---.&  !HE.& !---.\cr
        A &   (2)& !---.& !---.& !---.&  (10)& !---.& !---.& !---.&  !WAS.&  !---.& !---.&!THAT.\cr
        B &   (3)& !---.& !---.& !---.& !---.& !---.& !---.& !---.&  !---.&  !---.& !---.& !---.\cr
        C & !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.&  !---.&  !---.& !---.& !---.\cr
        D & !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.&  !---.&  !HAD.& !---.& !---.\cr
        E & !---.& !---.&  !BE.& !---.&  (11)& !---.& !---.& !---.&  !---.&  !---.& !---.& !THE.\cr
        F &   (4)& !---.& !---.& !---.& !---.& !---.&  !OF.& !---.&  !---.&  !---.& !---.& !---.\cr
        G & !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.&  !---.&  !---.& !---.& !---.\cr
        H &   (5)& !---.& !---.& !---.& !---.& !---.& !---.&  (12)&!WHICH.&  !---.& !---.& !---.\cr
        I &   (6)& !---.& !---.& !---.& !HIS.& !---.& !---.& !---.& !WITH.&  !---.& !---.&!THIS.\cr
 $\Theta$ & !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.&  !---.&  !---.& !---.& !---.\cr
        J & !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.&  !---.&  !---.& !---.& !---.\cr
        K & !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.&  !---.&  !---.& !---.& !---.\cr
        L & !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.&  !---.&  !---.& !---.& !---.\cr
        M & !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.&  !---.&  !---.& !---.& !---.\cr
        N & !NOT.& !AND.& !---.& !---.& !---.&  !IN.&  !ON.& !---.&  !---.&  !---.& !---.& !---.\cr
        O &   (7)& !---.& !---.& !FOR.& !---.& !---.& !---.&  !TO.&  !---.&  !---.& !---.& !---.\cr
        P & !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.&  !---.&  !---.& !---.& !---.\cr
        Q & !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.&  !---.&  !---.& !---.& !---.\cr
        R & !---.& !ARE.& !---.&!FROM.& !---.& !---.&  !OR.& !---.&  !---.&  !---.& !HER.& !---.\cr
   $\Phi$ & !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.&  !---.&  !---.& !---.& !---.\cr
    $\Pi$ & !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.&  !---.&  !---.& !---.& !---.\cr
        S & !---.&  !AS.& !---.& !---.& !---.&  !IS.& !---.& !---.&  !---.&  !---.& !---.& !---.\cr
        T &   (8)&  !AT.& !---.& !---.& !---.&  !IT.& !---.& !---.&  !---.&  !---.& !---.& !---.\cr
        U & !---.& !---.& !BUT.& !---.& !---.& !---.& !---.& !---.&  !---.&  !---.& !---.& !---.\cr
        V & !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.&  !---.& !HAVE.& !---.& !---.\cr
        W &   (9)& !---.& !---.& !---.& !---.& !---.& !---.& !---.&  !---.&  !---.& !---.& !---.\cr
        X & !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.&  !---.&  !---.& !---.& !---.\cr
        Y & !YOU.& !---.&  !BY.& !---.& !---.& !---.& !---.& !---.&  !---.&  !---.& !---.& !---.\cr
        Z & !---.& !---.& !---.& !---.& !---.& !---.& !---.& !---.&  !---.&  !---.& !---.& !---.\cr
}
}
󇋛 ���� ������������ ����� �������, ������� ������� ���������� ��~$0$
��~$M-1$; ������ ���������� ���� �������� ���� ���� ����, ���� ������
(��������, ������).
\st[퀗������ ���������.) 󑒀������ ���������~|P| ���, ����� �� ��������
�� ������ ����.

\st[������������.] 瀍���� �~$k$ ��������� (������� ������) ������
���������~$K$. (呋� �������� ��������� ���������, �� �������� �~$k$
"������" ��� ������ ����� �����. 눒��� ������ ���� ������������ �����
������ � ���������~$0\le k<M$.) �����~$X$ ��������� $k\hbox{-�}$~������� � ����~$|NODE|(|P|)$.
%%574
呋� $X$---������, ������� �� \stp{3}; ���� $X$---����, �� ������� ��~\stp{4}.

\st[��������.] 呋� $X\ne\NULL$, ���������� $P\asg X$ �
��������� ��~\stp{2}; � ��������� ������ �������� ������������� ��������.

\st[񐀂�����.] 呋� $K=X$, �������� ������������� ������;
� ��������� ������ �� ������������� ��������.
\algend

瀌����, ���, ���� ����� ��������, ��� �� ����� ������ �������, �����
\emph{����� �����������} � ���������� ������. ��� �������� ������� ���
��������� ����������.

����� �������� ����� ������ ��������� � ������ ���������� ������ �����,
����� �������� �������� ��������� ��� \MIX, �����������, ��� ������
�������� ���� ����, � �����--- �� ����� ���� ������.

\prog �.(�� �� ����.) �����������, ��� ��� ����� �������� ���� �����
������~\MIX; ���� ���� ������� ����� ��� �� ���� �����, �� �����������
������ ���������. � ��� �� ���������� ��� ������������� ����� ���~\MIX,
������ ���� ��������� ������ ������ ��������� �����, �������~30.
񑛋�� ������������ ��� ������������� ����� � ����~$0:2$.
獀����� ���������: $|rI1|\equiv|P|$, $|rX|\equiv\hbox{��������������
����� $K$}$.
\code
START  &LDX  &�       &1& T1. 퀗������ ���������.
       &ENT1 &ROOT    &1& $|P|\asg\hbox{��������� �� ������ ����}$.
2H     &SLAX &1       &C& T2. ������������.
       &STA  &*+1(2:2)&C& ⛄������ ��������� ������~$k$.
       &ENT2 &0,1     &C& $|Q|\asg|P|+k$.
       &LD1N &0,2(0:2)&C& $|P|\asg|LINK|(|Q|)$.
       &J1P  &2B      &C& T�. ��������. � T2, ���� |P|---������ $\ne\NULL$.
       &LDA  &0,2     &1& �4. 񐀂�����. $|rA|\asg|KEY|(|Q|)$.
       &CMPA &K       &1
       &JE   &SUCCESS &1& 󄀗��� �����, ���� $|rA|=k$.
FAILURE&EQU  &*       &1& ⛕��, ���� $K$ ��� � ����.
\endcode
␅�� ������ ��������� ����� $(8C+8)u$, ��� $C$---����� ����������� �����.
� ��� $C\le5$, ����� �� ������ ����� 48~������ �������.

呋� ������ �������� ������������� ���� ��������� (������������ ���
����.~1) � ���������~6.2.2� (������������ \emph{�����������} ��������
������ ������ (���.~13)), ����� �������� ���������:

1.~᎐ �������� ������� ������ ������: ��� ������������� 31~�����
������������ 360~����, � �� ����� ��� �������� ������ ������ ��������
62~����� ������. (��� ���.~4 ����������, ���, ������� ���������
�����������������, ����� �������� ��� ����.~1 � 49 ����.)

%%575
\picture{���. 31. ᎐ ����. 1, ��������������� � "���".}
%%576

2.~󄀗��� ����� � ����� ������� ������� ����� 26~������ �������. �
��������� ����� ����������� ����� ������� ��� ���� � ����� ��������� ���
��������� ������ ������. 䋟 ����� ������ ����� ���� ����� ���������,
������ �������, ������� � ����� ������ �������� ��� ����� ��������������.

3.~呋� ������ 31~�������� ���������������� ����������� ����� ����������
���������� ���������~KWIC (���.~15), ��� ������ ���� ������������
���������� ��������� ������. 퀏�����, ��� ������� 12~��������, �����
��������� ����� |COMPUTATION| �~|COMPUTATIONS|. (� ���� ������ ���� ��
����� ��� ��������� ���, ����� ����� �������������� ������ ������, � ��
����� �������.)

��� ���������� � ������� ������ ����������� ���� ��~��~ᐈ����
[Proc.~Western Joint Computer Conf., {\bf 15} (1959), 295--298]. � ������,
 ��� ����� ���������� ������ (�� ���� ���������� ������� ������), ����
������������ ��������� ������ ��� ������� ����-�������, ��� ���
����������� ��������� ����� ������� ������ �����. � ����� ����
������������ ���� ����� � ������ ���� ����.~1 �� ��� ��������,
 ������������ �� ���.~31.  ������ � ����� ���� �� ������� ������,
��������������� ������ ������, ����� ���� ����� �����, ����������������
������ ������, �~�.~�.

􀊒������ � ����� ������ �� �� ᐈ���� �� �������� ������������ ���,
��� �������� � ����.~1 ��� �� ���.~31; ������ ����� �� ����������� ������
���� ������ �� ������� �� ���������� �������� ����� �����. 򀊈� �������,
 � ���������������� ��~��~ᐈ���� ������ ������ "|H|" (���.~31)
����������� ��
\picture{���. ���. 576}
򀊎� ������������� ������� ������ ������, �� ������ ��������� ������
���������� ����� �������� ������. 呋� ������������ �� ������ ��� ����
������, ����� ����� ������������ ������������ ������� � ��������. ᎋ��
����, �� ������ ����������� �������� ������ ��������� � "�������������"
�����, �.~�.~������ ������ �������� ����� �����, � ����� ������ ���������
�������� "��������" ����� ����������� ������.
%%577
%%577

呋� ������������ ������� ������ ������������� �������� � �������� ����,
�� (1) ������������� � �������� ������
(䋟 ������������� ������� ���� ���.~31 ���������� �������� ���������,
������� ��~|H| �������, � ��������� �����~|I|.)  ������ � ���� ��������
������ ������ ��������� ������������ � �������� ������; �� ������� ��
�������~|RLINK|, ���� �� ������ ������ ������; ����� ����� ������~|LLINK|
� ��������� ������ ��������� ������������� ����������� �������.

�� � ����� �������� ������ � ������� ��� ������� ������� �������� �
����������, ������ ������������ ���������� �� �� �������� "������-������",
� �� "�����-�������". ������������ ������ �.~6.2.1 ������, ��� � �������
�� ��, ����� ��������� $N$~������, ����� �� ������� ���� $\log_2 N$~���������;
������� ����� ���������, ������������ ��� ������ ��
������, ��������� ������������� �� ���.~31, �� ������ ����� �������� ���
������������� ������� ��������� ������, ���������� � \S~6.2.

� ������ �������, ��� ����.~1 ��������� �����
����������� $M\hbox{-�������}$ ������������; �� ������, ��� ���
�������~$N$ ����� � ������� �������� ���� �����
$\log_M N=\log_2 N/\log_2 M$~��������,
���� �������� ������---��������� �����. � ������ �����, ���
���������� ����� ���� � "������" ���� (��� � ���������~T) ������� �������
$N/\ln M$~�����, ���� ����� ��������� $N$~��������� ������;
�������������, ������ ���������� ������ �������������� $MN/\ln M$.

��� ����������� ����������, ��� ���� ���� ������ ���� ��� ���������� �����
������� ������� ������. 쎆�� �������� ��������������, ���������� ���
���������: ��� ���������� ������ ����� ������������ ���, � ����� �������
�� ������ ��������. 퀏�����, �.~�.~񀑑�����, ��.\ [�.~�.~Sassenguth,
 {\sl CACM,\/} {\bf 6} (1963), 272--279] ��������� ������������
�������� ������ �� ���������� ��� ����� ������, ��� ��������, ������, ��
����� ����� ������, � ����� ���������� � ���� �������� ������
���������������� �����. 䀋�� �� ������, ��� ����� ��������� ���������
��������� ���������� ����� ���� �������� � ����� ��� ��� �������������
��������� ������� ������.

%%578

\section ������� � ����������� �����. 퀏���������� ����� ���������
�������� ��������� ���� � ����������� ������. ����� �������� �������������
� ��������� �� ��������� ������������, ���������� ��������������
���������������� ����������: �����������, ��� � ������ ��� �����
��������� �������� ������ ������� ����������� �����. 䋟 �����
��������� ���������� ������� ���������� ������, ������ �� 50000~����. 퀘�
���� ������� � ���������� ���������� ������� ������������� �������,
��������������� ��� ���� ���������� ������� �����.

���������� ������ �������---������ ���������. 򐅁����� ��� ������� ������
���������� �������, ��� � ������������ ��������������� �����������������.
䀂���� �� ��������� ����� �������� ���� � ��������� ��������,
������������� � ������ �������� �������.

���� ��������������� ������� �������� ����� 100000~����; ���� �������
�� ����� ������, �� ������������ ��������� ������� ��������� ��������
���� � �������. 呋� �� ���������� ��������� ������� ������, �� ������
������� ����������� ������ ���������. ��������, ��� ����������� �����
� ���������� � ������ �� �����������. 򎃄�, ���� ����� ���������� ��
�����~b, ��� ������ ����� ����������� ������� �� b, c, d, f, g, j, k, m, n,
 p, q, s, t, v, w, x, z. [񋎂� "bdellium" ("�������"--- ��� �������������
�����) ����� � �� �������� � �������!] � ����� ����, �� �� 17~����
�� ����� ������ �� ������ ����� � ������, ������������ � c, d, f, g, h, j,
k, 1, m, n, p, r, t, v, w, x, z. 葊������� ���������� ��������� ����,
������������ � ct, cz, dw, fj, gn, mn, nt, pf, pn, pt, tc, tm, ts, tz, zw,
� �������� ���������� ����, ������������ � kn, ps, tw. � �� ��������
������������ ���� ���� ������� � ����������� ���� (��������, ����� �����
������� �� 26~���� � ��������� ������� ����� "|LD1 TABLE,1|") �����
�������, ����� ��������� b, c, d,~\dots, z ������������ � �����������
�������������, �������, ��� �������� ��� ���������� ���� a, e, h, i, l,
o, r, u, y. 򅏅�� ������ ���� ���� ����� ���� ��������� �� 9-��������
������������; ����������� ������ ������ ������������ ��� �����
������������� ����. 򀊎� ������ ��������� ���������� ������ �� ������
������ ����, ���������������� ��� ����������� �����, � �� ������ ���
��������� ������ �����.

� ������� ��������������� ������� ����� ���������� ���� �~309 ��
$26^2=676$~��������� ���������� ���� ����, � �� ���� 309~��� 88~������
������� 15 ��� ����� ����. (򈏈���� ������� ����� ���: aa, ah, aj, ak,
ao, aq, ay, az, bd, bh,~\dots, xr, yc, yi, yp, yt, yu, yw, za, zu, zw;
����������� ����� ����� ������� �������� �� ������ ����� �� �����������
���� ���������.)
%%579
呋� ����������� ���� �� ��������� ������ ���������, ����� ��
������� ������ ������� � ��������� ������ �����, �������� �
����������������� ������.

䐓��� �������� ���������� ���������� ��� ������� ������  ������ ��������
������������� ���������. 퀏�����, ���� ������ �����, ������������ � re-,
pre-, anti-, trans-, dis-, un- �~�.~�., ����� �������� ��������� � ������
������� �����. 򀊈� ����� ����� ������� ����� ���� ���� reapply
(�������� ���������), recompute (����� ���������), redecorate
(������ ������������), redesign (�����������������), redeposit
(�������������) �~�.~�.; ������ ����� �������� ����� �����
remainder (�������), requirement (����������), retain (���������),
remove (�������), readily (������) � �.~�., ��� ��� �� ��������
��� ��������� "re-" ������� ������. 蒀�, ������� ������� ������ ����� �
���� ����� �������� ������� ���������, ���� ������ ����� �������� ���������.

噅 ������ ������������ ��������. � �������� ��������, ��� ����������
��������� ������� ���������������� � ������� � ������������ �
������������� ����� ���� �� ������� ��������������; ������� � ������
���� ���������. 퀏�����, ��������� ��������� ����� ��������� �� ������
���������� �������, ������� ����� ����������� ����:
\ctable{
-#\bskip\bskip\hfill&-#\bskip\bskip\hfill&-#\bskip\bskip\hfill\cr
e    & es        & ing\cr
ed   & s         & ings\cr
edlv & able      & ingly\cr
er   & ible      & ion\cr
or   & ably      & ions\cr
ers  & ibly      & ional\cr
ors  & ability   & ionally\cr
\omit& abilities & \omit\cr
}
(썎��� �� ���� ��������� ���� ���������� �� ���������.) 呋� ����������
�������� ��� �������� � �������
\ctable{
#-\hfill\cr
comput\cr
calculat\cr
search\cr
suffix\cr
translat\cr
interpret\cr
confus\cr
}
�� ������, ��� ����� ���� ����������; ��� ����������� �����������
����������� ������ �������. ᅇ�������, ��� �����
%% 580
��������� ���������� � ����� �������������� ����, �������� "compution";
������ computat- ����������� ����� �� �����������, ��� � comput-. ���
����� � ���� ���, ��������� ����� ���������� � �� ����� �������
����������� ������, � ���� �� ����� ����� �������� �� ����� "computedly",
�� ����� �� ��� ���� ������� �������. 瀌����, ��� �����������
����� ������� ����� "confusability" (�����������), ���� ��� �����������
� �������� ��������; ��� ������� ����� ������ ���������� ����������. 
���������� ��������� ��������� � ��������� ��� ������� ������ �� �����
���� ���������� ������ "establish" ������� �������� �����
"antidisestablishmentarianism".

����������, ����� ���������� � ���, ����� �������� ����� ���������
������������ ������� � ���������; ���������� ������ ���� ������� � �������
����� �������, ����� �� ����� ���� ����� �� ��������� � ������ ��������.
퀏�����, �������� ����� ������� "socialism" (���������) � "socialist"
(���������) �������� ������ ����� � ����� ��� ������� ����
"organism" (��������) � "organist" (��������)!

쎆�� ������������ ����� ��� ������� ��� ���������� ������ ������. � ���
� ������ ������� ��������� ����������� ������������ �������? ��
������� � ���, ����� ���������� ������� ��� \emph{���������}, ����������
�� ����������� �������� ����� ��� ����������� \emph{����������������
�������} (��.~�~�.~1.43); ������ � ���� ���� ����� ����������
��� \emph{����������}. 퀏�����, � ����.~1 �� ����� ��� ����
"����������", � ���������~T ���������� �������� ��� ��� ��� ��������;
���� ����� �������� ����������� � ������� ���� � ������� � ���������
������ �� ��������� �����������, � �� ����� ��� ���� ���� ��������
��������� ��������� � ������������ ������.

� ���������������� ������� ��� ������ ������� �� ����� �� ����� ��������
��������� �����:
\medskip
\item{$\bullet$}~����� $n$, $\alpha$, $\beta$. "呋� ��������� ������
��������� ���������� ������~$k\le n$, ������� � ������~$\alpha+k$ ��
��������� �����������; � ��������� ������ ������� � ������~$\beta$".

\item{$\bullet$}~񐀂����� $n$, $\alpha$, $\beta$. "񐀂���� ����������
������ ��������� � $n$~�������, �������������� � �������~$\alpha$,
$\alpha+1$,~\dots, $\alpha+n-1$. 呋� ���������� ����� �����
�����~$\alpha+k$, ����� ��������� ������ � "��������" ����� �
������~$\beta+k$,
�� ���� ����������� ����� ���, ����� ��������� ��������".

\item{$\bullet$}~����������� $\alpha$, $\beta$. "񋎂�, ������������ ��
������� �����, ��������, �������� ���������� ��� �������. � �����������
������ ����� ����������� � ������ � �� ��������� �����������. 呋� ����
����� ��������, ���������� ����������
%%681
�����, ������������ ���������� ������ ��������� ��� ����� ��������.
 呋� ���� ����� ������, �������������� ��������� "��������" ��
"���������"~$\beta$".

\noindent ����� �������� ��������� ��������� ������ �� ����, � ��������
��������� ���������� ������� � ����������������� ������. �����
����������� ������ ��� ��������� ��������� � ���������. 쎆��,
����������� �� ����� ��������� �������� ������������� ���� �����������
�����, ���������� ��������� ������ ��������. 䀋������� �������� ������
����������� �� ���� ���������� ���������~$\beta$ �� ������ ����������,
��� ��� ������ ����� ���� ������������ ���, ����� $\beta$~����������� �
�������~$\alpha$, $n$ ��� ������ ����������.

ᎋ�� ������ ���������� �� ����������� ������� ������� � ����������
������� 񈄍�� 띌�� � 󈋜��� ߊ������,~��.\
[{\sl Mechanical Translation,\/} {\bf 6} (1961), 76--107]; �.~�.~������
[{\sl JACM,\/} {\bf 10} (1963), 413--439]; 》�� �~ߌ���
[{\sl IBM Systems J.,\/} {\bf 6} (1967), 192--207].

\section ል����� ������. ���������� ������ ������� ������~$M=2$, ����� �
������ ������ ������� �������������� ���� ��� ��������� ������.
����������� ��� ���������� ������, �������� ���������� ��� ������� ������.

��� �����, ������� �� ����� �������� \emph{�������� �������  �� ������},
 ��������� ꎔ������ �~肎�
[{\sl CACM,\/} {\bf 13} (1970), 427--432, 436].
 � �� ��� � � ���������� ������ �� ������ �� �.~6.2.2, � ����� ������
�������� ������ �����, �� ��� ������ ����� ��� ������ ����� ������������
�� ��������� ��������� ������, � ���� ���������. � ���.~32
���������� ������, ����������� ���� �������; ��� ���������� ��
31~�������� ���������������� ����������� �����, ������ �����
����������� � ������� ���������� ������. ����� �������� �������� ������
��� ���� �����������, ����� ������������ � �������� ���� ������~\MIX\ �
����������� ��������������� � �������� �����, ���������� �� 5~����� �
�����. 򀊈� �������, ����� |WHICH| ����������� � "11010\ 01000\ 01001\
00011\ 01000".

����� ����� |WHICH| �� ���.~32, �� ������� ���������� ��� �� ������~|THE|
� ����� ������. � ��� ��� �� ��������� � ������ ��� �����~|WHICH|
�����~1, ����� ���� ������ � ���������� ��������� �� ������~|OF|. � ���
���������� �� ��������� � ������ ��� |WHICH| �����~1, �� ���� ������
� ���������� ��� �������� �� ������ |WITH| � �.~�.

䅐��� ���.~32 ��������� ��������, ������� �� ������ ���������� ������
���.~12 �� �.~6.2.2, ���� ��� ������������ ������ ��������� ��������������
���� ������, ������� ��������� �������� ������� ����� ����. 呋�
����������� �������� �������, �������� ����� �� ������ ���.~32 �������
%%582
� ������� $3.42$~��������� �� ������� �����; ��� ��������� �����, ���
$4.04$~���������, ������������ ��� ���.~12, ����, ����������, ����� ������
��������� ����� ��������� � ���� ���� �������.

\picture{���. 32. 䅐��� ��������� ������ ��� 31 �������� ����������������
����������� �����, ����� ��������� � ������� ���������� ������.}
\alg D.(�������� ����� �� ������.) ���� �������� ��������� ����� ������
��������~$K$ � ������� �������, ���������� ��������� ���� ��������
�������� ������. 呋� $K$ ��� � �������, � ������ � ���������� �����
����������� ����� ����, ����������~$K$.

ꀊ � � ���������~6.2.2�, ����� ��������������, ��� ������ �������, � ���
���� �������� ����~|KEY|, |LLINK| �~|RLINK|. �������� ������, ��� ���
��������� ����� ���������.

\st[퀗������ ���������.] 󑒀������ $|P|\asg|ROOT|$, $K1\asg K$.

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

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

\st[��� ������.] 呋� $|RLINK|(|P|)\ne\NULL$, ����������
$|P|\asg|RLINK|(|P|)$ � ��������� ��~\stp{2}.
%%583
\st[⑒���� � ������.] ⛏������ $|Q|\Asg|AVAIL|$, $|KEY|(|Q|)\asg K$,
 $|LLINK|(|Q|)\asg|RLINK|(|Q|)\asg\NULL$. 呋�~$b=0$,
���������� $|LLINK|(|P|)\asg |Q|$; � ��������� ������ $|RLINK| (|P|)\asg|Q|$.
\algend

��������~6.2.2T �� ���� ����� ��������, ������ ����������� ��������, ���
�������� ��������, ����� ����� �������������� �� $M\hbox{-�����}$
�������� ����� ��� ������ $M\ge2$ (��.~���.~13).

\picture{���. 33.         ��� ������ � ������ �����.}

䎍���� 쎐����� [{\sl JACM,\/} {\bf 15} (1968), 514--534] �������� �����
��������������� ������ ������������ $N\hbox{-�������}$ �������� ������,
���������� �� �������� ������������� ������, ��� ����������� ������ �
�����. 僎 �����, ��������� "�����" (��������� �������� ��� �������
����������, �������������� ������� � �������)\note{1}%
{� ��������� "Patricia"---Practical Algorithm To Retrieve Information Coded
In Alphanumeric.---{\sl �. �����.\/}},
�������� �������� ��� ������ � ����� �������� ������� ���������� �����,
������, ��� ��������� ��� �����, ���������� � ����� �������� ������.

����� ���� ����� ������� � ���, ����� ������� �������� ������,
������� ����������� ������������, ��� ���� � ������ ���� ���������� �����,
������������, ������� �����
%%584
����� ����������, ����� ��� ��� ������ ��������� ��������. 񓙅������
��������� �������� ���������� ���� ����; ��������, ���������� � �����
������ ���������� ��������� �� ���.~33. 茅���� ������ ����� |TEXT|
(������ �������� �������); �� ����� ��������� �� ������� ����� � ������
��������, ��� ��� ��� ������ ������ ��������� � ���� ���������� ����
���. ꀆ��� ����, ������� ������ ��������� � ����� �������, ������������
������ ������ � ������; ����� �������, ��� �� ���� �� ����� ������ ��
����� ������. (����� �� ���� ������� ��������� ����� ������ �
����������, � ����������, ���������� �� ����, \emph{������������} � ���������.)

� �������, ������������ �� ���.~33, ������� ���� ������, ������������ �
������� ��������� � ����� �����, � ������ "|THIS| |IS| |THE| |HOUSE|
|THAT| |JACK| |BUILT|.", "|IS| |THE| |HOUSE| |THAT| |JACK| |BUILT|.",
~\dots, "|BUILT|.". 퀋������� ������ �����������, ��������� � ���, ���
\emph{���� ���� �� ����� ������� ������� �������;} ��� ������� �����������,
 ���� �� ���������� ����� ����������� ����� ����� ������ (� ������ ������
"|.|"), ������� ����� ������ �� ����������. � �� �����������
��������������� � ����� ���� ���������~T, ��� ��������� ����� ������ "\] ".

䅐���, ������������ ������ ��� ������, ������ ������� ���������� �
����������� ������, ��� ��� ����� ������������ �� ���������� �����,
��������� � �.~6.2.4.  ������� �� ������ � $N-1$~�����, ������ ����
�������� ��������� �����:
\medskip
{\narrower
\noindent|KEY|---��������� �� �����. ��� ���� ������ ����� ����� �� �����
$\log_2 C$~�����, ��� $C$---����� ����� � ������. 񋎂�, ������������ ��
���.~33 ������ �����, �� ����� ���� ������ ���� ������������ �����������
�� �����; ��������, ������ "|(JACK)|" ���� �������� �����~24
(��������� ����� ����� "|JACK BUILT|.").

\noindent|LLINK| �~|RLINK|---������ ������ ������.  ������ ����� ����� ��
����� $\log_2 N$~�����.

\noindent|LTAG| �~|RTAG|---����������� ����, �� ������� �� ����� ������,
�������� �� |LLINK| �~|RLINK| �������������� �������� �� ������� ��� ��
�������. ������� ����� �� ���.~33 ������������� �������, ��� ������� $|TAG|=1$.

\noindent|SKIP|---����� �����, ������� ����� ���������� ��� ������, ���
����������� ����. ��� ���� ������ ���� ���������� ������� ��� ����, �����
�������� ���������� �����~$k$, ��� �������� � ���� ��������� ������
�������� ����������� ���������� �� $k$~�����; ������ ���
������������ ����� ���������� �������, ��� $k$ �� ������� ������, �
��� ���������� �������� ���� |SKIP| �������� ��������� ��
%%585
������. � ���.~33 ���� |SKIP| ���������� ������ ������� ���� �������.
\par}

㎋��� �������� ���� ���� KEY, LLINK � LTAG.\medskip

�� � ������ ����� ����������� ��������� �������:
�����������, �� ���� �����~|THAT| (�������� ������������� $10111\ 01000\
00001\ 10111$). � ����������� ���� |SKIP| � �������� ����~$\alpha$ ��
���������, ��� ������� ����� ��������� ������ ��� ���������. � �����~1,
������� ���� ��������� ������. � |SKIP| ���������� ���� ��������� ���
��������� $1+11=12\hbox{-�}$~��� ���������. � �����~0, � �� ���� �����.
臓��� ���� |SKIP| ���������� ����, �����, ��� ����� ���������
$12+1=13\hbox{-�}$~���, ������� �����~0. � ��� $|LTAG|=1$, �� ���� ��
����~$\gamma$, ������� �������� ��� � ������� |TEXT|. � ���� �� ����
������ ����� ��� ������ ���������, �������� �������� ������������� $1xxxx\
xxxxx\ x00~\ldots$, ������� ����� �������� �������� � ��������� ������.

��������, � ������ �������, ��� �� ���� ��������� ����, ������������
�~|TH|, ��� ��� ����� �����. �� ����������, ��� � ������, �� � �����
������ �� ��������� � (���������������) 12-��~���� ��������������
���������. 򅏅�� ����� �������� �������� � ���������� ������� |TEXT|,
 ������� ��������������� � ������� ���� (� ������ ������~$\gamma$);
���� ���������� �� ���������, �� �� ���������� �����, ������� ��������
������ �������� ������; ���� ���������� ����� �����, �������� ��������
������� ������ �����, �� ������� ��������� ���������� �����, ���������
�� ����~$\gamma$ � ��� ��������.

ᎋ�� ����� ���� ������� ����������� ��������� �������.

\alg P.(�����.) ��������, ��������� ������ |TEXT| � ������ � ����������
���� ������ |KEY|, |LLINK|, |RLINK|, |LTAG|, |RTAG| �~|SKIP| � �����,
��������� ����������, ���������� �� � ������� |TEXT| ����, ������������
� ���������~$K$. (呋� ������� $r\ge1$ ����� ������, ����� �� $O(r)$~�����
���������� ������������ ������� �� ���; ��.~���.~14.) �����������,
��� ���� �� ������� ���� ���� ����.

\st[퀗������ ���������.] 󑒀������ $|P|\asg|HEAD|$
�~$j\asg0$ (�������~|P| �������� ����������, ������� ����� ���������
���� �� ������, � $j$---��� �������, ������������ ������� ����� ���������.)
瀍���� � $n$ ���������� ����� ���������~$K$.

\st[��� �����.] 󑒀������ $|Q|\asg|P|$ �~$|P|\asg|LLINK| (|Q|)$. 呋�
$|LTAG|(|Q|)=1$, ������� ��~\stp{6}.

\st[���� �����.] (� ���� ������ �� �����, ���, ���� ������ $j$~�����
��������� ������������� ���������� �����, ��� ������������� �����,
������������� �~$|KEY|(|P|)$.) 󑒀������ $j\asg j+|SKIP|(|P|)$.
呋�~$j>n$, ������� ��~\stp{6}.

%%586
\st[����� ����.] � ���� ������ �� �����, ���, ���� ������ $(j-1)$~�����
������������� ���������� �����, ��� ������������� �����, �������������
�~$|KEY|(|P|)$. 呋� $j\hbox{-�}$~���~$K$ �����~0, ������� ��~\stp{2}; �
��������� ������ ������� ��~\stp{5}.

\st[��� ������.] 󑒀������ $|Q|\asg|P|$ �~$|P|\asg|RLINK|(|Q|)$.
呋�~$|RTAG|(|Q|)=0$, ������� ��~\stp{3}.

\st[񐀂�����.] (� ���� ������ �� �����, ���, ����~$K$ �������������
���������� �����, �� ������������� �����, ������������� �~$|KEY|(|P|)$.)
񐀂����~$K$ � ������, ������������ � �������~$|KEY|(|P|)$
�������~|TEXT|. 呋� ��������� ���������� $n$~������ �����, ��������
������������� ������;
� ������ ������������ �� ������������� ��������.
\algend

� ���.~15 ������ ����� ��������, ��� ����� ����������� ���������� ������
�����. 茅���� ����� ����������� ��������� � ������ � ��������� �����
����� ��� �������, ��� ����� ��������� �������� ������������ ������������
������������ (��������, �������� ����� ������, �� �������
������� ���������� �����).

�������� ����� ������ ���������, � ��� �� ����������� ������� ����
������������� �����������.

\section ������ ����������. 瀂����� ���� ������ ��������������
��������� �����, �������� ��������� ������ � �����.  ������
������ �� ����� ������� ��������� � ����� �����.
\picture{���. 34.             ��� ���������� ��������� ����.}

���������� ������� �������� ����, �.~�.~���� �~$M=2$. � ���.~34 ���������
�������� ���, ������������, ���� 16~������ �� �������� ���������� ��.~5
������������� ��� ������������� �������� �����. (ꋞ�� ��������� �
������������
%%587
������, ��� ���, ��������, $1144$ ������������ ������������� �����
$(1001100100)_2$.) ꀊ � � ���������~T, �� ���������� ��� ��� ��������
���������� � ����� ����� ������ �� ��� ���, ���� ������� ����������� �����,
 ��� ���� ������������ ����������; ��� �� ������������ ���������.

呋� �������� ���.~34 � ����.~5.2.2-3, ����������� ������������
����������� ����� ������� ������� � �������� ����������� �����������.
(⎇�����, ��� ����������� �������� ���������.) 22~���� ���.~34 � ��������
������������� 22~������� ����������� � ����.~5.2.2-3 (���� �������
���������� � ������ �������). ����� ����������� ����� � ������
����������� ����� ����� ������ � ��������������� ����-� ��� ��������;
����� �������, ����� �������������� ��������� ���������.

\proclaim 򅎐��� T.  呋� $N$ ��������� �������� ����� �������� �
�������� ���, ��� ������� ����, �� (i)~����� ����� ���� ����� ����� ������
�����������, ������ ��� �������� ����������� ���������� ���� �����;
(ii)~������� ����� �������� �����, ��������� ��� ������� ����� � �������
���������~T, �����~$1/N$, ����������� �� ����� �������� ����� ���.
�������� ����������� ����������.\endmark

ዀ������ ������� �� ����� ������������ ���� �������������� �������,
�������� � �.~5.2.2 ��� �������� ����������� ����������. ��������,
��������, ��� ������� �������� ���������, ���������� ��������������
�����~0 �~1 ������������ �����, �������������� � ����������� ���������.
򎃄� ���������� �������� �����, ����������� ��� ������� ����������,
����� �����~$\log_2 N+\gamma/(\ln2)+1/2+f(N)+O(N^{-1})$, � ����� �����
���� ��������~$N/(\ln2)+Ng(N)+O(1)$. 焅��~$f(N)$ �~$g(N)$---������� �������,
 �������� ����� ����������, ��� ��� �� �������� ������ ������~$10^{-6}$
(��.~���.~5.2.2-38,48).

����������, ����� ���� ����� ����� ������� ������: �������� ����������
���������� �� ������ $M\hbox{-�����}$ �����. � ������ ���� ���������
����� ������������, �������� ������������ ������ � �������� ����������.

�� $A_N$---������� ����� ����� � ��������� $M\hbox{-�����}$ ���� ������,
���������� $N$~������. 򎃄� $A_0=A_1=0$, � ��� $N\ge2$ �� �����
$$
A_N=1+\sum_{k_1+\cdots+k_M=N}\left({N!\over k_1!\ldots k_M!}
M^{-N}\right)(A_{k_1}+\cdots+A_{k_M}),
\eqno(3)
$$
��� ��� $N!M^{-N}/k_1!\ldots k_M!$~���� ����������� ����, ��� $k_1$~������
���������� � ������ �������,~\dots, $k_M$---�~$M\hbox{-�}$. ⎑�������������
������������� ��������� � ������� ������������ ��
%%588
$k_2$,~\dots, $k_M$,  ��������� ��� ����������� ���:
$$
\eqalignno{
A_N&=1+M^{1-N}\sum_{k_1+\cdots+k_M=N}
\left({N!\over k_1!\ldots k_M!}\right) A_{k_1}=\cr
&=1+M^{1-N}\sum_k\perm{N}{k}(M-1)^{N-k}A_k, \qquad N\ge2.&(4)\cr
}
$$
����������, ���� ����� $C_N$~���������� ������� ��������� ����������
�������� �����, ������ ��� ������ � ���� ���� $N$~������,  ��
$C_0=C_1=0$, �
$$
C_N=N+M^{1-N}\sum_k\perm{N}{k}(M-1)^{N-k} C_k,\qquad N\ge 2.
\eqno (5)
$$
� ���.~17 ��������, ��� �������� � ������������� ������������� ������
����, � � ���.~18--25 ��������������� ��������������� ������ ���������
�����. [� ������ ����� ������ � �������~$A_N$ ������� �������
�.~�.~䆎���� � �.~쀊-����� [{\sl IBM J.~Res.~and~Devel.,\/} {\bf 8}
(1964), 189--193] � ����� � ������������� ���������-���������������
���������� ����������.]

����� ������ � �������� �������� ��������� ������, �� ������������, ���,
 � ����� �������, ������� ������, � � ������---���������� ��������, � �����
�� ����, ��� ����������� ��������������� ���������. 퀏�����, ���� $\bar
C_N$~���������� ������� ��������� ���������� �������� �����,
������������ ��� ������ ���� $N$~������ � �������� ������ ��������� ������,
 �������� �������, ��� � ������, ��� $\bar C_0=\bar C_1=0$ �
$$
\bar C_{N+1}=N+M^{1-N}\sum_k\perm{N}{k}(M-1)^{N-k}\bar C_k,
\qquad N\ge0.
\eqno(6)
$$
��� ����� ��������� ���������~(5), �� ��������� $N+1$ ������~$N$ � �����,
����� ��������� ���������� ��� ����, ����� �������� ����� ��������
��������������, ��� ��� ������, ������������ ��� ��������~(5), � ������
������ ����������.

���������� ������� �������� ������. � ���.~35 ���������� ������ ���������
������, ��������������� 16~������ ���.~34, ����������� � �������,
�������������� � �������� �� ��.~5. 񐅄��� ����� �������� ����� ���
��������� ������� ������ ����� �����---��� ����� ����� ����������� ����
������, �������� ��~$N$, ��� ��� ����� $l$~��������, ����� ����� ����,
������������� �� ������~$l$. 瀌����, ������, ��� ������� ����� ��������
����� ��� ��������� \emph{���������} ������ \emph{�� ���} ������ ������� �
������ �������� ���� ������, ��� ��������� ����� � ������� ������������
������������ ������ �����; ��������, ����������� ���������� ����� �����
����~$0075$ (���.~35) �����~$1/8$ (��������������� ���������� ������
�����), � � ����� �����
%%589
����~$0232$ �� �������� � ������������, ������ ����~$1/32$. (� ����
������� ��� ����������� ������������� ������ ������� ��������� ������,
��� �������, ����� ��������������, ��� �������� ������� ������,
���������������� � ���������~6.2.2T.)

䋟 �������� ��������������� ������������� �������� ��������� ������
����� ������������ ������������ �������. �� �� ������~$l$ �����������
$a_l$~�����; ���������� ������������ �������~$a(z)=\sum a_l z^l$.
퀏�����, ���.~35 �������������
\picture{���. 35 񋓗����� ������ ��������� ������, ����������� � �������
��������� D.}
�������~$a(z)=1+2z+4z^2+5z^3+4z^4$. 呋� $b_l$~����� ������~$l$ ��������
�������� �~$b(z)=\sum b_l z^l$, �� � ���� ���.~6.2.1-25 �����
$$
b(z)=1+(2z-1)a(z).
\eqno(7)
$$
퀏�����, $1+(2z-1)(1+2z+4z^2+5z^3+4z^4)=3z^3+6z^4+8z^5$. 񐅄��� �����
�������� ����� ��� ��������� ������� ������ �����~$a'(1)/a(l)$, ��� ���
$a'(1)$~���� ����� ����������� ���� ������, � $a(1)$---���������� ����������
�����. 񐅄��� ����� �������� ����� ��� ���������� \emph{����������}
������
�����~$\sum l b_l 2^{-l}={1\over2}b'\left({1\over2}\right)=
a\left({1\over2}\right)$,  ��� ��� �� ��������� �������
�������� ���� ������~$l$ � ������������~$2^{-l}$.  ��������� ������
����� ��������� ��������� � ������ �������� �����, � ��� "�������"---��
������� ������ ����� �����. 䋟 ������
���.~35 ������� ����� � ������� ������� $2{9\over16}$~�������� �����
�~$3{9\over16}$~���������; � �������� ���������� ������
������������ $3{7\over8}$~��������� � �������� (� �������).
%%590

₅��� ������ "�����������" �� ���� �������� � $N$~������ �������~$a(z)$ �
��������� �� �����~$g_N(z)$. 荛�� �������, $g_N(z)=\sum p_T a_T(z)$, ���
����� ������� �� ���� �������� �������� ��������� ������~$T$ �
$N$~����������� ������; $a_T(z)$ ���� ������������ ������� ���
���������� �����~$T$, � $p_T$~���� ����������� ����, ��� ��� �������
$N$~��������� ����� � ������� ���������~D ���������� ������~$T$. 򀊈�
�������, ��� �������� ������ ������� ����� �������� �����
�����~$g'_N(1)/N$, � ���
����������---$g_N\left({1\over2}\right)$.

茈����� ������� ���������� ������, $g_N(z)$ ����� ��������� ���������
�������. 呋� $a(z)$ ���� ������������ ������� ��� ������ � $N$~������,
����� ���������� $N+1$~��������, ����� ������� � ������� ������ ��������
����. ��� ������� ������������ � ������ ������� ���� ������~$l$ �
������������~$2^{-l}$; �������������, ����� ������������ ������� ���
$N+1$~����� ��������, ���������� �� ����������� �� ���������, �����
$a(z)+b\left({1\over2}z\right)=a(z)+1 +(z-1)a\left({1\over2}z\right)$.
󑐅���� �� ���� �������� � $N$~������, ��������
$$
g_{N+1}(z)=g_N(z)+1+(z-1)g_N\left({1\over2}z\right);\qquad
g_0(z)=0.
\eqno(8)
$$
� ��������������� ������������ �������� ��� �������
����� $h_N(z)=1+(2z-1)g_N(z)$ �������� ��������� �����, ��� ���
(8)~������������ �������
$$
h_{N+1}(z)=h_N(z)+(2z-1)h_N\left({1\over2}z\right);
h_0(z)=1.
\eqno(9)
$$
썎�������� �������� ��� �������, �������, ���
$$
\eqalign{
& h_{N+1}(z)=\cr
&=h_{N-1}(z)+2(2z-1)h_{N-1}\left({1\over2}\right)+(2z-1(z-1)h_{N-1}
\left({1\over4}z\right)=\cr
&=h_{N-2}(z)+3(2z-1)h_{N-2}\left({1\over2}\right)+3(2z-l)(z-l)h_{N-2}
\left({1\over4}z\right)+\cr
&\phantom{=}+(2z-1)(z-1)
\left({1\over2}-1\right)h_{N-2}
\left({1\over8}z\right)\cr
}
$$
� �.~�.; ������������ �����
$$
\eqalignno{
h_N(z)&=\sum_k\perm{N}{k}\prod_{0\le j<k} (2^{1-j}z-1); & (10)\cr
g_N(z)&=\sum_{k\ge0}\perm{N}{k+1}
\prod_{0\le j<k}(2^{-j}z-1). & (11)\cr
}
$$
퀏�����, $g_4(z)=4+6(z-l)+4(z-l)\left({1\over2}z-l\right)+(z-1)\times
%%591
\left({1\over2}z-1\right)\left({1\over4}z-1\right)$. ��� ������� ���������
�������� ������� �������� � ���� ���� ������������:
$$
\eqalignno{
\overline{C}_N&=g'_N(1)=\sum_{k\ge0}\perm{N}{k+2}
\prod_{1\le j\le k} (2^{-j}-1); & (12) \cr
g_N\left({1\over2}\right)&=\sum_{k\ge 0}\perm{N}{k+1}
\prod_{1\le j\le k}(2^{-j}-1)=\overline{C}_{N+1}-\overline{C}_N.&(13)\cr
}
$$
񎂑�� �� ��������, ��� ��� ������� ��� $\overline{C}_N$ �������������~(�)!

� ���������, ��������� ��������� ���������� ��� ���������� ��� ���������
��������������� ������, ��� ��� $2^{-j}-1<0$; ��������� ������� ����������
������, ������ �� ������� ����������. ᎋ�� �������� ������� ���
$\overline{C}_N$ ����� �������, �������� ��������� ���.~5.1.1-16. 茅��
$$
\eqalign{
\overline{C}_N&=\left(\prod_{j\ge1}(1-2^{-j})\right)
\sum_{k\ge0}\perm{N}{k+2}(-1)^k\prod_{l\ge0}(1-2^{-l-k-1})^{-1}=\cr
&=\left(\prod_{j\ge1}(1-2^{-j})\right)
\sum_{k\ge0}\perm{N}{k+2}(-1)^k\sum_{m\ge0}(2^{-k-1})^m
\times\prod_{1\le r\le m}(1-2^{-r})^{-1}=\cr
&=\sum_{m\ge0}2^m\left(\sum_k\perm{N}{k}(-2^{-m})^k-1+2^{-m}N\right)
\prod_{j\ge0}(1-2^{-j-m-1})=\cr
&=\sum_{m\ge0}2^m((1-2^{-m})^N-1+2^{-m}N)\sum_{n\ge0}(-2^{-m-1})^n
2^{-n(n-1)/2}\times\prod_{1\le r\le n}(1-2^{-r})^{-1}.\cr
}
\eqno(14)
$$
񐀇� �� ����, ��� ��� ����� ���������~(12), �� ���������� ������� �����
�� ������ ������������, ��� ��� ������ �������� ��� ������
��������������~$n$. � �������� ����������� �������� ��������� � � ������
���� [������� (5.2.2-38)]; � ����� ����, ���� ����������� �~(14) ����
����� �~$n=0$, ���������� ����� $N-1$~���� ����� �������� � ��������
����. 䀋������� ����� ��������������� ������ ����� �������� ��� ���������
��� ��������; ��.~���.~27. �������� ����� � ������� ������� �������
�� �������, ������������ �.~�.~ꎍ������ �~�.~�.~휞����� [{\sl Discrete
Mathematics,\/} {\bf 4} (1973), 56--63].

� �������, �������� �� ����� � ����� ������ ����������. � ��������
������ ������ �� ��������������� �������� ��� � ���� �� �������, ��
������� ������ (��� ����~|SKIP| ��������� ����������� ������������), ���
��� ������� $N-1$~����������
%%592
� $N$~������� �����. � ���.~36 ���������� ������ �����,
��������������� ����������� ������ � ���� ���.~34. �����, ����������� ��
���������� �����, ���������� ���������� ����� |SKIP|; ����� �������
������ � �������� ������, ���� ��������� �� ������������ ���� (�
���������������� ������ ������� ����� ���������� ���������� ������ ��
���������� ����, ������� � ���� ������� ��������� �� ������
|TEXT|). ��� ��� ����� ������� ����� �������, ��� �������
���� ���������� � ��� ����, ��� ��� ���������� �� ���.~36.

� ��� ������� ����� � �������������� ����� ������������ �� �������
�����, ������� ����� �������� �����, ������������ ��� ��������� �������
������, ����� �����
\picture{���. 36.            ����� ������ ��� ������ ������ ���. 34.}
�������� ����, �������� ��~$N$. 呋�, ��� � ����, ������ ������������
�������~$b(z)$ ��� ������� �����, ��� ����� ����� �����~$b'(1)/b(1)$.
\emph{텓������} ����� ����� ��������� �� ������� ����, �� �
������������~$2^{-l}$ ($l$---����� ������, �� ������� ���������� ����),
��� ��� ������� ����� �������� �����
����������~${1\over2}b'\left({1\over2}\right)$. 퀏�����, ��� ���.~36
$b(z)=3z^3+8z^4-3z^5+2z^6$; � ������� ������� ����� �������
$4{1\over4}$~�������� �����, � ���������---$3{25\over32}$.

��������� �������~$b(z)$, ����������� �� ���� �������� �����,
����������� � $N$~�������� ������ � �������������� ����������
�������������� ������, ��������� �����~$h_N(z)$.
%%593
������������ �����������
$$
h_n(z)=2^{1-N}\sum_k\perm{n}{k}h_k(z)(z+\delta_{kn}(1-z)),
\qquad h_0(z)=0, \qquad h_1(z)=1,
\eqno(15)
$$
��-��������, �� ����� �������� �������. �, � �������, ����������
������� ������������ ����������� ��� ������� ����� �������� ����~$h'_n(1)$,
 ���������
$$
\eqalignno{
h'_n(1)&=2^{1-n}\sum_k\perm{n}{k}h'_k(1)+2^{1-n}
\sum_k\perm{n}{k}(1-\delta_{kn})=&\cr
&=n-2^{n-1}n+2^{1-n}\sum_k\perm{n}{k}h'_k(1).&(16)\cr
}
$$
� ��� ��� ����� ���~(6), ��� ����������~$h'_n(1)$ ����� ������������ ���
�������� ������; �����������, ��� $h'_n(1)$ ����� ��~$n$ ������
���������������� ����� �������� ����� � ��������� �������� ����. 򀊈�
�������, ���� |SKIP| ��������� ���������� �������� ���� �������� ���� ���
�������� ������ ��� ��������� ������. (�.~���.~31.) � ����� �� ����
������������ �������� ������ �������� � ������� ��������.

呋� �� ���������� ����� ������� ����� �������� ����� ��� ����������
���������� ������, ������������� ������, �� ������� �����������
$$
a_n=1+{1\over 2^n-2}\sum_{k<n}\perm{n}{k}a_k,
\qquad n\ge2; \qquad a_0=a_1=0.
\eqno(17)
$$
(焅�� $a_n={1\over2}h'_n\left({1\over2}\right)$.)  \emph{��} ������ ��
�� ���� �� ��������� �����������, � ������ ��� � ��� �� ������. � �����
���� �����������, ��� ������� �������� ����� ᅐ�����:
$$
{na_{n-1}\over2}-n+2=\sum_{2\le k<n}\perm{n}{k}{B_k\over 2^{k-1}-1}.
\eqno(18)
$$
��� ������� ��������, ��������, �������� ������� ��������������� �������
�� ����, ������� ��� ����� ���� ��������;
������� � ���.~34 ���� ������������ ����� ������ ����� ��������� ����� �
���������� ��������.

\section ⛂��� �� �������. 񋅄����� ���������� ����������� �����������
��������:

\item{(a)}~����� �����, ����������� ��� �������� $N$~��������� ������ �
$M\hbox{-�����}$ ����, ������������ � ������� ���������� �� ���.���, ����
�� ��������� ������� �� $\le s$~������, �������� �����~$N/(s\ln M)$. (���
����������� ����������� ��� �������~$N$
%%594
� �����~$s$ �~$M$.) � ��� ���� ���� �������� $M$~����� ������, ��, ����
������� $s=M$, ����� ����������� ���� ����� $N/(\ln M)$~����� ������.

\item{(b)}~䋟 ���� ������������� ������� ���������� ���� ��� �����,
����������� � �������� ���������� ������, �������� �����~$\log_M N$. 
$M=2$ ���������� �������� ����� �������� ��������� ����� ������
����������� ��� ����� �������� �����:
\ctable{
#\hfill\bskip &&\bskip \hfill$#$\hfill \cr
                         & \hbox{󄀗���} &\hbox{텓������} \cr
�� �� ����            &\log_2N+1.33275 &\log_2N-0.10995\cr
�������� ����� �� ������ &\log_2N-1.71665 &\log_2N-0.27395\cr
�����                 &\log_2N+0.33275 &\log_2N-0.31875\cr
}
[⑅ ��� ������������ �������� ����� �������� ����� ���������������
�������������� ����������; ��������, �����~$0.31875$ ���������� ��~$(\ln \pi-\gamma)/(\ln2)-1/2$.]

\item{(c)}~"񋓗�������" ������ ����� �������� ��, ��� $M\hbox{-�����}$
����� �������� ���������� ���������������, ��� ���� �� ������� ����
�������������� ����� �����~0 �~1, ���������� � $M\hbox{-�����}$ �������
���������. 셒��� ��������� ������ �� ������������� � �������, � �������
����� �������� � ���� (����������� �������� ��������~D, ���� � �����
������� �������������� � �������); �� ��� ����� ������������� �
������������� ����. 퀏�����, ���� ������� ���� ����������� ������� ����
���������, ������� ����� ������� ����� �������������� �� ��������� �
���������, ����������� ��� ��������� ������. (� ���.~5.2.2-53 ��������
������ ����, ��� ���������� ��� ����� ����������� �� ������.)

\excercises
\ex[00] 呋� ������ ����� ������, �� ��� ����� ���?

\ex[20] ������ �������� ������� ������ ����� � $M\hbox{-�����}$ ���,
������������� ���������� ���������~T.

\ex[21] ������ �������� �������� ����� �� $M\hbox{-������}$ ����,
������������� ���������� ���������~T.

\rex[21] ᎋ�������� �� 360~��������� ����.~1---������� (������
������). ��� ����� ����� ������� �� 49~���������, �������� ����������
�������� � ������ ���������:
\picture{���. �� ���. 594}
%% 595
[󇋛 (1), (2),~\dots, (12) ����.~1 ���������� �������������� � ������� 20,
 19, 3, 14, 1, 17, 1, 7, 3, 20, 18, 4 ������ �������.]

�����, ���, ���� �������� ����� ������ �������� ����.~1,
���������~T ����� �������� � � ���� ������, ������, �� ����� ������.

\rex[�26] (�.~�.~�.) � �������� ���.~31 ����� ����������� �� ��������
������ ������� ���������. ��� �� �������� �����������, � ���� ��, ������
��� ������� �������� ������ ����~(2), ������� ������� ����� ������ �������
���������, ����� ����� ����������. ꀊ�� ���������������� ���.~31 �����
����������� � ���� ����� ������? (葏�������� �������, ������ �� ���.~32,
� ������� ���, �������, ������ ����������� � ���� ��������� ������,
������������ ����� �������� ������.)

\ex[15] ꀊ�� ������ ��������� ������ ���������, ���� ����������
�������������� �������� ������ 0001, 0010, 0011,~\dots, 1111 �������� �
������������ ������� � ������� ���������~D? (퀗���� � �����~0001 �
�������� ���� � ����� ����������� ������������ �������.)

\rex[M26] 呋� ���������� ������ �� ���.~6 ����������� � ������ �������,
����� ���������� ������ ������. ꀊ��� ��������� ����� ����
$15!$~��������� ������������ ���� ������ � ��� ������, ��� ��� ���������
������ � ���������� ������ ����������� ����?

\ex[20] ���������� ��������� ��������� ���������~D, ������� � ����������
����������~$K1$: �������� "$K1$" �� "$K$" � ����~D2 � ���������
��������~"$K1\asg K$" �� ����~D1. ㎄���� �� ���������� �������� ���
������ � �������?

\ex[21] 퀏����� \MIX-��������� ��� ���������~D � �������� �� �
����������~6.2.2T. � ������ ������������ �������� �������� �����
|SLB| (�������� ����� ����� |AX|), |JAE| (�������, ���� |A|~�����) � �.~�.,
 ���� ������� ������. � ������ ����� ������������ ���� ���.~8.

\ex[23] 茅���� ����, ��� ����� �������� ���� $n\hbox{-�������}$
�������� �����, � �������� ������ $K=b_1\ b_2\ \ldots\ b_n$. ��������,
��� �� ����� ����� ������������ �����~$k$, �����, ��� � ����� ����������
����, ������������ � $b_1b_2\ldots b_k$. ꀊ ������� ��� ����������, ����
���� ����������� � ����: (a)~��������� ������ ������
(��.~�~���������� 6.2.2T); (b)~��������� ���� (��.~� ����������~T);
(c)~��������� ������ ��������� ������ (��. � ����������~D)?

\ex[21] 쎆�� �� ������������ ��������~6.2.2D ��� ��������� ��� ��������
���� �� ������ ��������� ������?

\ex[25]  ᓄ�� �� ��������� ������, ���������� � ����������
�������� ���������� �������� �� ���������� ������ ��������� ������,
������������ � ������� ���������~D? (�.~�~���.~11 � � ��������~6.2.2H.)

\ex[20] ($M\hbox{-�����}$ �������� �����). ������, ��� �� ����������~T
�~D ��������� ���������� ��������, ���������� � ���������~D ���~$M=2$.
ꀊ ������� �������� ����.~1, ���� ������������ ��� �������� ���~$M=30?$

\rex[25] ������ ����������� ��������, � ������� �������� ����� �����
�������� ���������� ���������~P ����� ���� �� ����� ��� ����� � �������
|TEXT|, ��� �����������~$K$.

\ex[28] �������, ����������� ��������, ������� ����� ������������ ���
���������� ������ ����� ��� ��� ������� ����� ������ �� |TEXT| � ���
������������ ������. ‘ �������� ������� ������ ���������� � �������
|TEXT| �� ����� ���� ���.

\ex[22] ��� ��� ����� �������� �� ����� ����� �����������, ��� ��
���� ���� �� ������ ������� ������� �������?

\ex[�25] 퀉���� ������ �������� ������� ������������� �����������
$$
x_0=x_1=0; \qquad x_n=a_n+m^{1-n}\sum_k\perm{n}{k}(m-1)^{n-k}x_k,
\qquad n\ge2,
$$
� ������� ������������ ��������������, ������� ����� ���.~5.2.2-36.

\ex[M21] 葏������ ��������� ���.~17, �������� ������� ���������~(4) �~(5)
����� �������~$U_n$ �~$V_n$, ����������� ��������� � ���.~5.2.2-38.

%%596

\ex[��23] 퀉���� ��������������� �������� �������
$$
K(n,s,m)=\sum_{k\ge2}\perm{n}{k}\perm{k}{s}{(-1)^k\over m^{k-1}-1}
$$
� ��������� ��~$O(1)$ ���~$n\to\infty$ ��� ������������� ��������~$s\ge0$
�~$m>1$. [񋓗��~$s=0$ ���������� � ���.~5.2.2-50,
� ������~$s=l$, $m=2$---� ���.~5.2.2-48.]

\rex[M30] ���������� $M\hbox{-�����}$ ������� ������, � �������,
��������� ��������, ����������� �� ����� $s$~������, �� ����������
���������������� �����. (񋓗��~$s=1$ ������������� ��������~T.) ������
���������� ���������� ����������, ����� ����������������: (a)~�������
����� ����� ����;
(b)~������� ����� ����������� ���� ��� ����� ��� ������� ������;
(c)~������� ����� ���������, ������������ ��� ������� ������.
񔎐��������� ������ � ���� ��������������� ������~($N\to\infty$) ���
�������������~$M$ �~$s$,
����� ���~(a) ������ ���� ��� � ��������� ��~$O(1)$, ������ ���~(b)
�~(c)---� ��������� ��~$O(N^{-1})$. [呋�~$M=2$, ���� ������ �������� �����
� ���������������� �������� ����������� ����������, ����� ��������
�������~$<s$ ����������� ����������� �������].

\ex[�25] 񊎋��� ����� � ��������� $M\hbox{-�����}$ ����, ���������� $N$~������,
����� ������ ������ � �������� ������� ����������? (퀏�����, 9 �� 12~�����
����.~1 � ������� "\]" ����� ������ ������. "񋓗�����" �
���� ����������, ��� � ������, ��������, ��� ������ ������ ����������
������������ �����~$0$ �~$M-1$.)

\ex[�25] 񊎋��� ����� ����������� �� 1-� ������ ����������
$M\hbox{-ap�oro}$ ����, ����������� $N$~������, ��� $l=0$, 1, 2,~\dots?

\ex[�26] 񊎋��� �������� ���� ������������ � ������� ���
��������� ������ � $M\hbox{-�����}$ ����, ���������� $N$~��������� ������?

\ex[M30] ���������� $M\hbox{-�����}$ ���, �������������� � ���� ����
(��.~�~���.~31). 퀉���� ������ � ��������������� ��������� ���:
(a)~�������� ����� ����� � ����; (b)~�������� ���������� ����������
������������~$|P|\asg|RLINK|(|P|)$ � �������� ���������� �������� ������.

\rex[�24] 쀒����������� ����� ��������������� ��������, ��������� � ������
������, ������ ������; �������������� ���� ������ ������������ �����������.
䅋� � ���, ��� �� �� ������ �������������� ������� ������ �����������, �
������ ���� ������������� ������. ���� ����� ���������� ������� � ���, �����
������������� �������� �������� ��������� ���������� � ����������� �����,
(a)~䎊����� �� ��������, ��� ������� ���������~(4) ���~$N\ge1$
������������� �����������~$A_N\le M(N-1)/(M-1)$.
(b)~��~$D_N=C_N-NH_{N-1}/(\ln M)$, ��� $C_N$~��������� ��~(5).
䎊�����, ���~$D_N=O(N)$, �������������, $C_N=N\log_MN+O(N)$.
[\emph{󊀇����:} �����������~(a) � �������~1.2.7A.]

\ex[23] ������� ������� �������� ������������ ������������
$$
\left(1-{1\over2}\right)\left(1-{1\over4}\right)
\left(1-{1\over8}\right)\left(1-{1\over16}\right)\cdots
$$
� ��������� ��~$10^{-5}$. [\emph{󊀇����:} ��.~�~���.~5.1.1-16.]

\ex[��31] � ������� �����������~(14) ������� ���������������
��������~$\overline{C}_N$ � ��������� ��~$O(1)$.

\ex[��26] 퀉���� ��������������� ��������� �������� ����� �������� ����
��� ������ � ��������� ������ ��������� ������, $M\ge2$. ����������� ���
�������, ��� � ��������� �����. 䀉�� ����� � ��������� ��~$O(N^{-1})$.

\ex[�46] 퀉���� ����������� �������� ����� ����� � $M\hbox{-�����}$
������ ��������� ������, ��� $M$~������ ������� �����. (葊����� ����� ����,
�� ����� �� ���������� ������; ��.~�~���.~13.)

%% 597

\ex[M24] �����, ��� ������������ ������� �����~$h_n(z)$,
������������ �~(15), ����� �������� � ����� ���������� "�������" ����:
$$
n\sum_{m\ge1} z^m \left(
 \sum_{\scriptstyle a_1+\cdots+a_m=n-1\atop\scriptstyle a_1, \ldots, a_m\ge1}
\perm{n-1}{a_1,\ldots, a_m}\times
{1\over (2^{a_1}-1)(2^{a_1+a_2}-1)\ldots(2^{a_1+\cdots+a_m}-1)}\right).
$$
[򀊈� �������, ���� �� ������������ ������� ������� ���~$h_n(z)$, ��
����� �� ��������� ��� �������� ���������� ���������.]

\ex[M21] 퀉����~$h'_n(1)$ �� �����������~(16).

\ex[M21] ���� ����� ������� �������� ����� ���� ����� |SKIP| � ���������
������ ����� � $N-1$ ����������� ������?

\ex[M30] 䎊�����, ���~[18] ������������� ������������� �����������~(17).
[\emph{󊀇����:}  �����������  ������������
�������~$A(z)=\sum_{n\ge0} a_nz^n/n!$.]

\ex[��40] ����� ����� ���������� �������� ���������� ����������������
��������� �������~(18).

\item{(a)}~䎊�����, ��� ��� $n\ge2$
$$
{1\over n}\sum_{2\le k<n}\perm{n}{k}{B_k\over 2^{k-1}-1}=
\sum_{j\ge1}\left({1^{n-1}+2^{n-1}+\cdots+(2^j-1)^{n-1}\over 2^{j(n-1)}}
-{2^j\over n}+{1\over 2}\right).
$$

\item{(b)}~�����, ��� ��������� � ������ �����~(a) ����� ����������
���������~$1/(e^x-1)-1/x+1/2$, ���~$x=n/2^j$; ������������ ��� ����
����� ���������� �� �������������� ��~$O(n^{-1})$.

\item{(c)}~�����, ��� ��� ���������������~$x>0$
$$
{1\over e^x-1}-{1\over x}+{1\over2}=
{1\over 2\pi
i}\int_{-{1\over2}-i\infty}^{-{1\over2}+i\infty}\zeta(z)\Gamma(z)x^{-z}\,dx.
$$

\item{(d)}~񋅄���������, ��������������� ����� �����
$$
{1\over 2\pi i}\int_{-{1\over2}-i\infty}^{-{1\over2}+i\infty}
{\zeta(z)\Gamma(z)n^{-z}\over 2^{-z}-1}\,dx+O(n^{-1});
$$
������� ���� ��������.

\rex[�20] ꀊ��� ����������� ����, ��� ������ �����, ���������� ����
������, ����� ���
\picture{���. ���. 597}
%%598
������ ���� |SKIP| �������� $a$, $b$, $c$, $d$, ��� �������� �� �������?
(�����������, ��� ����� ����� ����������� ��������� ����; ����� �����
����������� � ���� ������� �� $a$, $b$, $c$ �~$d$.)

\ex[M25] 茅���� ���� �������� �������� � ����� ����������� ������. 呋�
�� ����������, ��� ����� ������ �� ��� ������ �������, ������ �
��������� ���������� (������ �������������� ����������), �� �������
��������� ��������� �����������:
\picture{���. ���. 598 --- � ������� �� ������:}
\ctable{
# &$#$&$#$&$#$&$#$&$#$\cr
   &&&&&\cr
�� �� ������ (�������� 6.2.2.T) & 1\over 6 & 1\over6 & 1\over3 &
1\over6 & 1\over6\cr
�������� ����� �� ������ (�������� D)&1\over8 & 1\over8 & 1\over2 &
1\over8 & 1\over8\cr
����� (�������� �) & 1\over7 & 1\over7 & 3\over7 & 1\over7 & 1\over7\cr
}
(瀌����, ��� ������ ��������� ������ ����� ���������� ��������� �
������������������.) � ���.~6.2.2-5 �� ����� ������� ��� ����������� �
������ ������ �� ������: $\prod(1/s(x))$, ��� ������������ ������� ��
���� ���������� �����~$x$, a~$s(x)$---����� ���������� ����� � ���������,
������ �������� ������~$x$. 퀉���� ����������� ������� ��� �����������
� ������: (a)~���������~D;  (b)~���������~�.

\rex[�22] ���������� �������� ������, �� $l\hbox{-�}$ ������ ��������
����������� $b_l$~������� �����. � ������ �����������, ��� �����
���������� ������ � �������� ��������� ������ �� ������� ��������������� �
������ �������� ����~$\sum lb_l$, �, �� ��������, ���������������
\emph{���������������� ����� �������� ����}~$\sum l b_l 2^{-l}$.
䎊����� ��� ������������ ��������� �����������:
����� ���� �������� � $N$~�������� ������ ����������
���������������� ����� �������� ���� ����� �� ������, ��� ������� ����
�������� ����������� �� ����� ��� �� ���� ������� ������� (��.~� ���.~5.3.1-20).

\ex[�40] ������������ �������� ��� ���������� $n\hbox{-��������}$ ������,
 �������� ����������� �������� ��������
$\alpha\times\hbox{(����� ����������� ����)}+
\beta\times\hbox{(���������������� ����� �������� ����)}$, $\alpha$
�~$\beta$---������ ����� (��.~�~���.~37).

\ex[�43] ������� �������� ���������� ����������� �������� ���������
������, ����������� ����������� �������� �������� ������, �������������
� �.~6.2.2.

\ex[25] �� $a_0a_1a_2\ldots$---������������� �������� ������������������;
$a_{N+k}=a_k$ ��� ����~$k\ge0$. �����, ��� ����� �������������
������� ����� ���� ����� ����������� � $O(N)$~������� ������ ����� �������,
 ��� ��������� �������� ������� ���� $O(n)$~�����: ���� ��������
������� $b_0b_1\ldots b_{n-1}$, ����� ����������, ������� ��� ���
����������� � ������� (�.~�.~����� ���������� ��������~$p$, $0\le p<N$,
�����, ���~$b_k=a_{p+k}$ ���~$0\le k<n$). (䋈�� �������~$n$, ��� � ����
�������, �������� ����������. �����������, ��� ������ ������ ������
���������� ������, ����� �������� ������������ ����� ����� ��~$0$ ��~$N$.)

%%599

\ex[��28] \exhead(������� � ������ �����.) �� $G$---���������
������ ��� ���������~$\set{a_1,~\ldots, a_n}$, �.~�.~��������� ����
������� $\alpha=b_1\ldots{}b_r$, ��� $b_i$~���� ����~$a_j$,
����~$a_j^{-1}$, � ��� ������� ���~$a_ja_j^{-1}$ ���~$a_j^{-1}a_j$.
����� �~$\alpha$ ��������� ��������~$b_r^{-1}\ldots{}b_1^{-1}$; ��
����������� ��� ����� ������� ����� ������������ � ���������� �������
��������������� ���������. �� $H$---��������� ������~$G$, �����������
���������~$\set{\beta_1,~\ldots, \beta_p}$, �.~�.~��������� ���� ���������
��~$G$, ������� ����� �������� � ���� ������������~$\beta_i$
�~$\beta_j^{-1}$. 쎆�� �������� (��.~�.~�.~ꓐ��, 򅎐�� ����� (�.,
"퀓��", 1967), ��.~9], ��� ������ ���������� �������
����������~$\theta_1$,~\dots,$\theta_m$ ���~$H$, $m\le p$, ���������������
"�������� 툋�����", ������� ������, ��� ������� ������ �~$\theta_i$ (���
�� ����� ��� ���� �� ���� ����������� ��������, ���� $\theta_i$~�����
������ �����) ������� �� ����������� � ����������~$\theta_i\theta^e_j$
���~$\theta^e_j\theta_i$, $e=\pm1$ (����� ���������� ����������~$i=j$,
$e=-1$). � ����� ��������, ��������, ��� ���������� ������� ��������
�������� �������������� ������������� ��������~$G$ ���������~$H$:
��������� $2n$~�������� $a_1$,~\dots, $a_n$, $a^{-1}_1$,~\dots, $a^{-1}_n$,
 ������� $2m$~������ $\theta_1$,~\dots, $\theta_m$, $\theta^{-1}_1$,~\dots,
 $\theta^{-1}_m$ � ������, ��������������� �� ����� �� ��������. ��
$\alpha=b_1\ldots{}b_r$---������ ������� ��~$G$; ����~$r=0$, ��
�������~$\alpha$, ����������, �����������~$H$. � ��������� ������
����~$\alpha$, ������ ����� ������� ���������~$b_1\ldots{}b_k$,
��������������� �����. 呋� ����� ��� ���� ���� ����������
�~$b_1\ldots{}b_k$, �� �������~$\alpha$ �� �����������~$H$; � ���������
������ ��������� ���� ������������ ����
�����~$b_1\ldots{}b_kc_1\ldots{}c_l=\theta^e_l$ � �������~$\alpha$
��~$\theta^{-e}_l\alpha=c^{-1}_l\ldots{}c^{-1}_1b_{k+1}\ldots{}b_r$. 呋�
��� ����� ��������~$\alpha$ ������� ������� (�.~�.\ ����~$l>k$),
$\alpha$~�� �����������~$H$; � ��������� ������ ��������� ������� � �����
���������~$\alpha$. 񂎉���� 툋����� ����������� ���������� �����
���������. 呋� ������� ������~$\alpha$ � ������ �������, �� �����
������������ �������� �������������~$\alpha$ � ���� ������������~$\theta_i$.

퀏�����, ����� $\set{\theta_1, \theta_2, \theta_3}=\set{bbb,
b^{-1}a^{-1}b^{-1}, ba^{-1}b}$ �~$\alpha=bbabaab$. 녑
\picture{���. ���. 599}
������ � ��������� ���������� ���������
��������~$\alpha=\theta_1\theta_3^{-1}\theta_1\theta_3^{-1}\theta_2^{-1}$.
���������� ���� ��������, ��������� � �������� ������� ������ ��� �����
���������~$\theta_i$.

\ex[23] \exhead(񆀒�� ������� � �����.) 呋� ����� �������� ������
������������ � �������� ��������� ��� ����������� ����� �������� �����,
�� ��� ����� ������� ������ �����. 퀏�����, ����������� ������ ���.~34
����� ������� ������ ���, ����� ���������� ���������� ���� ��� ��
������������ �����������: $0000$, $0001$, $00100$, $00101$, $010$,~\dots,
$1110001$. 򀊈� ��������� ����� ����� ������������ ��� ����������� �����
�� ���������� ������; ��������, ����� ����� ������� �� ���� ������,
������������ �~$0011$ ���~$010$, � ��������� ����� �������� ��� �����,
������������ �~$111001$, $11101$ ���~$1111$. 󐅇����� ����� �����
����������� ����� ���������, ���� �������� ����� �����, ����� � ����������
������: $0000$, $***1$, $**100$, $****1$, $*10$,~\dots, $******1$. �
����������� ������ ������� �������, ������� �� ����� �������� � �������
����� ����� ����� ���������, � �� ������ ������� ���� �� ����� �
�������� ��������� �����. (� ���� ������ ������ ������ �������
�.~�.~ㅋ��� �~�.~�.~鎍���.)
%%600
�����, ��� ��������� ����� ����� � ������ �����, �������� ��������� �
��������� �� ���� �������, ����� ����� ����� � �������� ����, ����������
��� �����.

(񋅄���������, ������� ��������� ����� ����� ����� �� ����
��������� �������� �����~$N/(\ln 2)$, ��� ���������� ���� �����
$1.44$~���� �� ����. ⎇����� � ��� ������� ������, ��� ��� ��� �����
����������� ���� ��������� ����, ��.~�~�������� 2.3.1A).
\bye
