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

%%601

\subchap{�����������} % 6.4
�� ��� ��� �� ������������� ������ ������, ���������� �� ��������� �������
���������~$K$ � ���������� � ������� ������� ��� �� ������������� ���
���� ��� ���������� ��������� ������������. �� ���� � ������ ����: ��
������� ������ �� �����, � ���������� ���~$K$ ��������� ��������������
���������� � �������� �������~$f(K)$, ����������� ����� � �������, ���
��������~$K$ � ��������������� � ��� ����������.

��������, ���������� ����� ��������� �� 31~����������� �����, ������� ��
���������� ����������� ��������� ��������� ������ � �.~6.2.2 � \S~6.3.
�������~1 �������� �������� ��������� ��� \MIX, ������������� ������ ��
31~����� � ���������� �����~$f(K)$ �����~$-10$ �~$30$. ���� �� �������
���� ����� � \MIX-����������� ��� ��� ��������� ���� ������� (��������, �
�������� �������, ����������� ������� �� ������, ������� �������,
�������� ������� �� ������), �� ������, ��� �� ����� ��� � ����� ������
������������, ��� � � ����� ������ ��������; ������ �������� �����
���������� ��������� ������ ������������. � ����� ����, ��� �������������
��������� �� ����.~1 ������� ����� ������ ���������� ����
�����~$17.8u$ (������ � ������� ����� �� ���.~12), � ��� ��������
31~����� ��������� ������� ����� ��� 41~��������.

� ���������, �������� �������� �������~$f(K)$ �������� ������. ����������
$41^{31}\approx10^{50}$~��������� ����������� ��������� �� 31~�������� �
��������� �� 41~��������, �
������ $41\cdot40\cdot\ldots\cdot11=41!/10!\approx10^{43}$ �� ��� ����
��������� �������� ��� ������� ���������; ����� �������, ���� ���� ��
������ 10~��������� ������� ����������� ����������.

�������, ������ ��������������� ��������, ���������� ����� ���� � ������
�������� ������� �������. ��������, ���������� �������� ���� ��������
����������, ���, ���� � ������� ������������ �� ����� 23~�������, �������
������� ���� �� ��, ��� � ���� �� ��� �������� ���� ��������!
����� �������, ���� �� �������� ��������� �������, ������������ 23~����� �
365-���������� �������, �� � ������������~$0.4927$ (����� ��������) ���
����� ������� � ������ �����. ��������, ������������� � ����, �����
���������� ����� ���������� ���� �������� �� ��������� ������� ���������.
[�������� ���� �������� ������� �������� � ������� ���~������ ({\sl Istanbul
%%602
\"Universitesi Fen Fak\"ultesi Mecmuasi,\/} {\bf 4} (1939), 145--163)
�~�.~������� (�������� � ������ ������������ � �� ����������, �., "���",
1964, ��.~2, \S~3).]

� ������ �������, ������, �������������� � ����.~1, �������� ������
[��.~�~�.~��������� �~�.~������, {\sl CACM,\/} {\bf 6} (1963), 322--323],
� ��� ������� �������� ������� ���������� ������� ����� ����� ��������
�� ����. � ����� ����, ����� ������� ������ �������� �����������.

����������, ����� ����� ����� ������������ ����������, ��� ����������
������� ������ ���� �������� �������; ���������� ���� �� ������ �����
����� ��� ���������, � ��� �������� �������� ���������� �� ������ �����.
����� �������� ������� ����� ������ �����, ���� ��������� ����
�������������, �������� ���������� ��������~$f(K)$ ��� ���������
����������, � ������������ ������ ����� ���������� ���������������� �����
����������~$f(K)$.

���� ������������ �������� � ������ ���������� ������ �������, ������
���������� \dfn{������������} ��� \dfn{���������� �������.} ����������
������ "to hash" ����� ����� ��������, ���������� ���-���� ��� ������� ��
����� ������; ���� ����������� ������� � ���, ����� ����� ���������
�������������� ����� � ������������ ���������� ��������� ����������
� �������� ������ ������. �� ��������� \dfn{���-������� $h(K)$} � �����
��� �������� � �������� ������ ������ ������.

�������� ���� �������� ������ ��� ��� ����������������, ���, ��������,
�������� ��������� �����~$K_i\ne K_j$, ��� �������
%%603
$h(K_i)=h(K_j)$. �������� ������� ���������� \dfn{���������;} ���
���������� �������� ���� ����������� ���������� �������. �����
������������ ���������� �������, ����������� ������ ������� ��� �����
����������� �������: �� ������ ������� ���-�������~$h(K)$ � �����
���������� ��������. ��� ��� ������� ������ ������ �� � ���������� �� �������.

\section ���-�������. ��� �������������� �� ���������� ����� ������ �����
��������������, ��� ���-�������~$h$ ����� �� ����� $M$~��������� ��������
� ��� ��� �������� ������������� �������
$$
0\le h(K)<M
\eqno(1)
$$
��� ���� ������~$K$. � �������� ����� ����� ����� ���������� ������,
������� ���������� ������� ���-�������, ������������ �� �� �������. ���
����� ��� ���������� ����� ��������.

������������ ���������� ��� ���������� ���-�������, ����� ��� ���������
��������� ������ �� ����������� �������� ������. �� �� �������� ��������
������� ���������� ������� �������� �����������, ��������� �������
�������������� ��������, ������������� � ��.~3. �� ����� ���� �� �����
��������� ���� �����, ������� ����������� �������� �������� ������ �
����� �� �� ������ ���-�������, ������ ������ ��������; ��� ����� �������
������� ��������� �����.

����������, ��������, ������ ������������� ������ �� ���������� ����������.
 ��� ����� ������������� ��������� ������ ������ ���-�������: ��������~$M$
������, ������, 1000,
%%604
� � ��������~$h(K)$ ����� ��� �����, ��������� �������� �� ��������
20-�������� ������������~$K\times K$. �������� ��, ��� ������ ������
�������� ����������� ������������� �������� �����~$000$ �~$999$ � ������
������������ ��������. � ����� ����, ������������ � ��������� �������
��������, ��� ����� ����� "�������� ��������" ������ ��� �������, ���
����� �� �������� ����� ����� ��� ������ ����� ������. ����������, ������,
��� ���������� ����� �������� � ������� �������, ������� ���� ��� � ��.~3
����� �������� �������� �������� �� ������� ������� �������� ��������� �����.

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

����� ������� �������� �����: ������������ ������� �� ������� ��~$M$
$$
h(K)=K\bmod M.
\eqno(2)
$$
� ���� ������, ��������, ��������� ��������~$M$ ����� ����� ������.
��������, ���� $M$---������ �����, �� ��������~$h(K)$ ����� ������ ���
������~$K$ � �������� � ��������� ������; ����� ��� �������� �
������������ ��������� ������. ������ ����� �����~$M$ ������ �������
��������� ������� ��������� ���, ��� ��� ����� $h(K)$~���� ��� ������
�������� �����~$K$ ($K \bmod M$ �� ������� �� ������ ����). ����������,
$M$ �� ������ ���� ������~$3$, ��� ��������� �����, ������������ ���� ��
����� ���� �������� ����, ����� �� ���� �������� �������, �������� �����
�������� ������~$3$. (������� ������� � ���,
���~$10^n \bmod 3= 4^n \bmod 3= 1$.) ������ �� ������ �� ��������
��������~$M$, �������~$r^k\pm a$, ��� $k$ �~$a$---��������� �����, �
$r$---"��������� ������� ���������" ��� ��������� ������������ �����
(������ $r=64$, 256 �~100), ��� ��� ������� �� ������� �� �����
��������~$M$ ������ ����������� ������� ������������� ���� �����. ����
������������ ������������, ��� ����� ����� \emph{����� � ��������~$M$
����� ������� �����,} �����~$r^k\not\equiv \pm a \pmod{M}$ ���
���������~$k$ �~$a$. ����������� �� ���� �������,  ���� ����� �����������
������ ������������������.

��������, �� ������~\MIX\ ����� ��������~$M=1009$, ��������~$h (K)$
��������� �������:
$$
\mixcode
LDX  &K      & $|rX|\asg K$.
ENTA &0      & $|rA|\asg 0$.
DIV  &=1009= & $|rA|\asg K \bmod 1009$.
\endmixcode
\eqno(3)
$$

����������������� ����� ����������� ����� ����� �����������, ��
��������� ������� �������, ��� ��� ����� �����������, ��� �� �������� �
�������, � �� � ������ �������. ����� $w$~���� ������ ��������� �����
(��� \MIX{} ��� �������� ������
%%605
�����~$10^{10}$ ���~$2^{30}$); ����� �����~$A$ ����� ������������� ���
�����~$A/w$, ���� �������� ��������� ���������� (��� ��������) ����� �����
�� ��������� �����, � ������� ��������~$A$. ����� ������� � ���, �����
�������~$A$ ������� ������� �~$w$ � ��������
$$
h(K)=\floor{M\left(\left({A\over w} K\right)\bmod 1\right)}.
\eqno(4)
$$
�� ��������~���  $M$~������ ����� ������ ������� ������, ��� ���
$h(K)$~������� �� ������� ����� ������ �������� �������� ������������~$AK$.

�� �������� ������ ������~\MIX{} ���~$M=2^m$ �����������������
���-������� ����������� ���:
$$
\mixcode
LDA  & K & $|rA|\asg K$.
MUL & A & $|rAX|\asg AK$.
ENTA& 0 & $|rAX|\asg AK \bmod w$.
SLB   & m & ����� |rAX| �� $m$~����� �����.
\endmixcode
\eqno(5)
$$
��������� ���������� � ��������~|A|. \MIX{} ����� �������� ���������
������� ��������� � ������, �������~(5) �~(3) ����������� ����������
�����; ������ �� ������ ������� ��������� ����������� ������� �������.

� ��������, ���� ����� ����� ������������� ��� ���������~(3), ���������
�� ����� ��, ��������, ����� � ��������~$A$ ����������� �~$w/1009$;
��������� �� �������� �������� ����� ����������� ������� �������. �������,
��� (5)~����� ��������� � ������� �������� ��������, ������ ������� ����
������ �������: � ���������� �� ������, ��� ��������� ��
���������� ��������� ����� ����� �������� �������.

���� �� ��������������� ���� ����������������� ����� ������� � ���, ���
�~(5) �� ���������� ������ ����������; �� ����� �� ����� �����~$K$, ����
���� ����������~$|rAX|$ ����� ���������� ����������~(5). ���� � ���, ���
$A$~������� ������ �~$w$, � ��� ������ ��������� ������� ����� �����
���������~$A'$:~$AA'\bmod w=1$; ������ �������,
���~$K=(A' (AK \bmod w)) \bmod w$. ����� �������, ���� ����������
�����~$f(K)$ ���������� ��������~$X$ ����� ����������� ����������~|SLB|
�~(5), ��
$$
K_1\ne K_2 \hbox{ ������ } f(K_1)\ne f(K_2).
\eqno(6)
$$
�������, $f(K)$~��������� �������� � ��������� ��~0 ��~$w-1$ � �� ��������
�������-������ ���������� ���-��������, �� ��� ����� ���� ����� �������� �
�������� \dfn{������������ �������}, � ������ �������,
���������������~(6) � ������ ���������� � ������������ ������. ��������,
�� ����� ������ ������������ � ��������� � ����������� ������ �� ������
�� �.~6.2.2, ���� ������� ������ ��� �����������, ��� ��� ���
��������� ��������� ���������� ������ ��� ����������� ������ � ������������
%%606
�������. ������������ ������� ������� ����� � ����� �
����������� ��������� ������ �� ������ �� \S~6.3, ���� ���� ��������
������ ����� ��������.

������ ����� ������������������ ������ ����������� ������� � ���, ��� ��
������ ���������� ����������� ��������, ������� �������������� �� ������
������. ����� ��������� �������� ������ �������� �������������� ����������
$\set{K, K+d, K+2d,~\ldots, K+td}$, ��������
�����~$\set{|PART1|,\ |PART2|,\ |PART3|}$
���~$\set{|TYPEA|,\ |TYPEB|,\ |TYPEC|}$. ����������������� �����,
����������� ����������� �������������� ���������� � ������������
\picture{���. 37. ������������ �����������.}
�������������� ����������~$h(K)$, $h(K+d)$, $h(K+2d)$,~\dots{}
������������� �������, �������� ��� ����� ����� �������� �� ��������� ��
��������� ���������. ����� ������� �������� ����� �� ���������.

�������~37 ������������ ���� ������ ������������������ ����������� �
�������� ���������� ������. �����������, ��� $A/w$~����������� �����
��������
�������~$\phi^{-1}=(\sqrt{5}-1)/2=0.6180339887$; ���������
���������������� ��������~$h(K)$, $h(K+1)$, $h(K+2)$,~\dots{} ����� �������,
������������ ��������� �������~$h(0)$, $h(1)$, $h(2)$,~\dots{} ��� �������
��� �� ����� �������� ����� �����������: ������� �������~$[0, 1]$, ��
������� ��������������� ���������� �����~$\{\phi^{-1}\}$, $\{2\phi^{-1}\}$,
$\{3\phi^{-1}\}$,~\dots,  ��� $\{x\}$~���������� ������� �����
�����~($\{x\}=x-\floor{x}=x\bmod1$). ��� �������� �� ���.~37, ��� �����
����������� �� ������� ������ ���� � �����; ������ ����� ����������� �����
%%607
�������� � ���� �� ���������� ���������� ���������� � ����� ��� �������
��������! [��� ������� ���� ������� �������� �.~����������� � ��������
�.~�����������, {\sl Fundamenta Math.,\/} {\bf 46} (1958), 187--189.
������ ���� � �������������� ������ ����� ���������.]

��� ������������� �������� �������� ������� � ���������������� ��������
������� ������� ����� ����� �������, ������������� ���� ����������� �
���������� ����� ����� ��� [{\sl Acta Math.\ Acad.\ Sci.\ Hung.,\/} {\bf
8} (1957), 461--471;
{\sl Ann.\ Univ.\ Sci.\ Budapest.\ E\"otv\"os Sect. Math.,\/} {\bf 1}
(1958), 127--134]:

\proclaim ������� S. ����� $\theta$---����� �������������� �����. ����
��������� �� �������~$[0, 1]$ �����~$\{\theta\}$, $\{2\theta\}$,~\dots,
$\{n\theta\}$, �� ����� ������������ �������� ����� ���������� �� �����
��� ����� ���������� �������. ����� ����, ���������
�����~$\{(n+1)\theta\}$ ������� � ���� �� �������� ���������� �����.\endmark

\noindent ����� �������, �����~$\{\theta\}$, $\{2\theta\}$,~\dots,
$\{n\theta\}$ ������������� �����~0 �~1 ����� ����������. ������� ����� �
��� ������������~$\{\theta\}$, ���� ���� ���������� ��������� ��������
������� �����, ������������ ���~$n$, ������� ��� ������
�����������~$\{\theta\}$. �������������� �������~S ������ � ���������
�������� ����������� �������� ���������� � ���.~8. �����������, ���
������� ������ ����� ��������� � ����������� � �������
"������ ����������---������ �����������". �������, ���������
��������~$\{\theta\}$ ���������������� ������; ��������, ����
�����~$\{\theta\}$ ������� �~0 ���~1, �� ������� ���������� �����
��������� �������� � ���� �������. � ���.~9 ��������, ��� ���
�����~$\phi^{-1}$ �~$\phi^{-2}=1-\phi^{-1}$ �������� � "��������
���������� ��������������" ������������������� ����� ����~$\{\theta\}$
��~0 ��~1.

����������� ����������� �������� ��� � \dfn{������������ �����������,}
����� � ��������~$A$ ������� ��������� �~$\phi^{-1}w$ ����� �����, �������
������� �~$w$. ��������, ���� �� \MIX{} ���� ���������� ���, ����� ���� �����
\picture{���. ���. 607}
���� ��������� ����� ������ ������� ����� ����� |LIST1|, |LIST2|, |LIST3|.
���������, ������, ��� ����������, ���� ����������� ������������������
���������� � ��������� �������, ��� � ������ |SUM1\]|~, |SUM2\]|~, |SUM3\]|~:
������� ����� �����, ��� ���� �� �������~S ��������������
�~$\theta=\{100A/w\}=0.80339887$ ������~$\theta=0.6180339887=A/w$.
�������������� ���������, ������, ����� ���������� �������, �������� �� ��
��� ��� ��������~$\theta$ ����~$\phi^{-1}$. ���� �� ����������� ����������
%%608
�� ������ �������, ��� � ������ |A1\]\]\]|~, |A2\]\]\]|~, |A3\]\]\]|~, ��
�������� ��������~$\theta=0.9887$; �������, ��� ������� ������
�~1. �������, ����� ����, ����� ������~(7) ����� � �������� ���������
\picture{���. ���. 608}
�������� ��������� �������� ���������������� �����, ������������� �
\emph{�����} �������. � ���������, ���� ����� �������� ������ �������,
����������� ���������~$r^k\pm1$: ����� �����~|XY| �~|YX| ������� � ���� �
�� �� �����! ���� �� �������� ����������� ����������� ��������� ������� �
����� ����������� �������� ��������, ������� � ������ �������~S. ���
�������� ������������������� ������ ����� �������� ���� ��������� ������
�������� ������� ����������~$\theta$ � ����������� �����; �������
�������� ������� ������������� ������� ��������� �������������. �������
��������� ��������~$\theta$ ���������� �� ����������
$$
{1\over 4} <\theta<{3\over10},\quad
{1\over 3} <\theta<{3\over7},\quad
{4\over 7} <\theta<{2\over3},\quad
{7\over10} <\theta<{3\over4}.
$$
� ��������~$A$ ����� ����� ����� ��������, ����� ������ �� ��� ������
����� � ������� ��������� � �� ��� ������� ������ � ��������� ������
������ ��� �� �����������, ��������
\picture{���. ���. 608}
����� ��������� ����� �������������. (���������� ���� � ��������
����������� �. ������.)

������� ���-������� ������ ������������� ���� �����������:
\medskip
\item{a)}~�� ���������� ������ ���� ����� �������;
\item{b)}~��� ������ �������������� ����� ��������.
\medskip
\noindent ��������~(a) ������� ������� �� ������������ ������, �
��������~(b)---�� ��������� ������. ���� �� ����� ����
������������� ����������, ����� ���� �� ������ �������� ��������� ����� �
������������ �� ��� ���-�������, �� �� ��������, ����� �������������~(b),
����� ������ ����� �������, ��������� �� ���� �����.

�� ��� ��� �� ������������� ����������� ������, ��������� �� ������
�����. � �������, ���������� �� ���������� ���� ��� �������� ����������
�����, ����� �������� ���
%%609
� ��������������� � ������������ ��������� ������� � ��������� � ���
������������� ������. ������ ������ ����������� ����������� ����� �������
���������, ����� ��������� ����� ������� ������������� � ����, � �����
������������ ������������ ��������� ��� �������. ��� ��������������
����� ������������ �������� �� ������~$w$ ��� �������� "����������� ���"
(�� �������� ���). ������������ ����� �������� �������� �� �����������,
�.~�.~�� ��������� ������� �� ���� ����� ����������, ������ "�����������
���" ������ ����������������, ��� ��� �� ����� �������� �
��������������� ������������. �������, ��� ��� �������� ������������,
������� �����~$(X, Y)$ �~$(Y, X)$ ����� "�������" �� ������ ������. �����
�������� �����, �.~�.~����� ��������� �������������� ������ ����������� �����.

���� ��������� ����� ������ ������� �����������, �� �� ���� �� ��� ��
�������� ���������������� ��������� ���� ������� ���� ������� � ���������.
����� ��������� ������� � �� ��������� �������������� �������������� ���
������ � ��������� ������� ����� ����� � ������
[V.~Y.~Lum, �.~S.~�.~Yuen, M.~Dodd, {\sl CACM,\/} {\bf 14} (1971), 228--239].

�� ������ ���������� ������� �����������, �������, �������� ����������
�������� ������, ���������� �� �������������� ������ �����������. ����
���������� ������ �������, ������ ������ ������� �� ����� �����
������������ ������� �� ��������� �� ������~2. (��� ���� �������� � \S~4.6,
 ��� �������� ������������ ����� ������ �������, ��� �� ���
��������---������ "������������ ���".) ��� ������������� ������ $M$~������
���� ��������~2: $M=2^m$; ����� ����, ������������ ���������
$m\hbox{-�}$~������� $P(x)=x^m+p_{m-1}x^{m-1}+\cdots+p_0$. ��������
����~$K=(k_{n-1}\ldots{}k_1k_0)_2$ ����� ������������� ���
���������~$K(x)=k_{n-1}x^{n-1}+\cdots+k_1x+k_0$, � ���������
�������~$K(x) \bmod P(x) = h_{m-1}x^{m-1}+\cdots+h_1x+h_0$,
��������� �������������� ���������� �� ������~2:
$h(K)=(h_{m-1}\ldots{}h_1h_0)_2$. ��� ���������� ������~$P(x)$ �����
���-������� ��������� �������� ��������, ����� ����� ������� �������.
��������, ���� $n=15$, $m=10$ �
$$
P(x)=x^{10}+x^8+x^5=x^4+x^2+x+1,
\eqno(10)
$$
�� ����� ��������, ���~$h(K_1)\ne h(K_2)$, �����~$K_1\ne K_2$ �~$K_1$
���������� ��~$K_2$ ����� ��� ����� ������. (� ���.~7 �� �������
�������������� ���������� �� ���� �����; ����������, ��� ��� ������
�������� ���������� ��� ����������������, � �� ����������� ����������.)

��� ������� ����, ��� ������� �������� ������ ������������ ����������
���-�������~$h(K)=0$; ��� ��� ��� �����
%% 610
����� ��������� ������; �����������~$h(K)$ ����� ���� ������� �������.

\section ���������� �������� ������� �������. �� ��� ��������,
��� ��������� ������ ����� ����������� ����������� �������. �������,
�������� ��������� ������ ������� �������� ������� � ���, �����
������������ $M$~��������� �������, �� ������ �� ������ ���������
���-�����. ��� ������ ������ ��������� ����~|LINK|; ����� ����, �����
����� $M$~�������� ����� �������~$|HEAD|[i]$, ��� $i$~�������� ��~1
��~$M$. ����� �����������
\picture{���.~38.           ���������� �������.}
����� �� ������ ��������� ���������������� ����� � ������ �
�������~$h(K)+1$. (��.~���.~6.1-2. �������� ���������� ����������
��������� � ��������� �������---��������� 5.2.1M.)
�������~38 ������������ ���� ������� ����� ������� ���~$M=9$ ���
������������������ ���� ������
$$
K=|EN|, |TO|, |TRE|, |FIRE|, |FEM|, |SEKS|, |SYV|
\eqno   (11)
$$
(��� ���������� ����� ��~1 ��~7 ��-���������), ������� ���������������
���-����
$$
h(K)+1=3, 1, 4, 1, 5, 9, 2.
\eqno(12)
$$
������ ������ �������� ��� ��������, ��� ������ �����.

����� ������� �������� ������ �������, ��������� ������ �������. ���� �
����� ������� ������� 365~�������, ��� �������� ����� ���, ������� ����
� ��� �� ���� ��������, �� ������ ���� �������� � ������� ����� ���� ����
�������! ������, ���� ������� $N$~������ � $M$~�������, �������
������ ������ �����~$N/M$; ����� �������, ����������� ��������� ����������
������, ��������� �� ���������������� �����, �������� � $M$~���. (������
������� �������� � ���.~34.)

%%611

���� ����� ������������ ����� ��������� ���������� ������������� �����
�������, ������� ��� ����� �������� ��������� �������� ��� ����������
������ � ���������. ����� ������� ��������� ���������  ������
��������������  �� ������;
��� ��������� ������� � ��������� �����. ���, ���� ������ ������
�������������, �� ���.~38 ��������� �� �������� ������� ����~|TO| �~|FIRE|,
 � ��� ������ ������ �������� �� ��������� �� ��������������� ������
�~$\infty$ � �������� ����� (��. �������� 6.1T). ������ ��������� ��������
�������� ������������� ������� "������������������� �����",
������� ����������� � \S~6.1; ������ ������������ �� ������ ����������
������������ �� ������� ���������� ��������� � ������.

� ����� �������� ������� ���������� �������~$M$, �� � ���� ������ ������
������ ����� �������, ��� ��� �\'������ ����� ������������, ���������� ���
$M$~�������� �����, ���������� ���. ��� ��������� �� ������� �������
������������� ������ ������: ����� �������� ������������ ��� ������� ��
������������ ��� �������� �����, ������ � ������� ����� ���
$M$~������� � $M$~������, � �� ��� $N$~������� � $M+N$~������.
������ ����� ��������� ���� ������ �� ������ � ��������, ����� ��������
���� ����� ��������������, �������� �� ��������� ������� "�������������"
������ � ��������� ����. �����, ������, ��� ������������ ��� ����������;
��� �������� �� ����� �����, ��� ������� ������ ������ ��������������
���� ���� ���, ��� ������ ����������� � �������. ��������� ��������,
������������� �.~�������� [{\sl CACM,\/} {\bf 2}, 6 (June 1959), 21--24],
�������� ������������ �������� ������� ���� ������.

\alg C.(����� � �������� �� ���������� ������� � ���������.) ������������
�������� ��������� �������� � ������� �� $M$~��������� ������ ����~$K$.
���� $K$~��� � ������� � ��� �� �����, $K$ ����������� � ���.

�������� ������� ������������ ����� $|TABLE| [i]$, $0\le i\le M$, � �����
���� ���� ��������� �����: \emph{���������} �~\emph{�������.} ������� ����
�������� �������� ����~$|KEY|[i]$, ���� ������~$|LINK|[i]$ �, ��������,
������ ����.

�������� ���������� ���-�������~$h(K)$. ��� ���������� ������ ����������
������������ ������������ ��������������� ����������~|R|; ���� �������
�����, $|R|=M+1$; �� ���� ����������  ������� ����� ���������� � ����
�����������, ��� ����~$|TABLE|[j]$ ������ ��� ����~$j$ � ���������~$|R|\le
j\le M$. ���������, ��� ����~$|TABLE|[0]$ ������ ����� ��������.

\st[�����������.] ����������~$i\asg h(K)+1$. (������~$1\le i\le M$.)
\st[������?] ���� ����~$|TABLE|[i]$ ��������, �� ������� ��~\stp{6}.
(� ��������� ������  ���� ����  �����, � �� ��������� �� ��������� �����
������ ������� �����).

%% 612
\st[���������.] ���� $K=|KEY|[i]$, ����� �������� ������.

\st[������� � ����������.] ���� $|LINK|[i]\ne0$,
����������~$i\asg|LINK|[i]$ � ��������� ��~\stp{3}.

\st[����� ��������� ����.] (����� ��� ���������, � �� ����� ����� �
������� ��������� �����.) ���������~|R| �� ��� ���, ���� �� ����� ��������
����� ��������, ��� ����~$|TABLE|[|R|]$ ��������. ����~$|R|=0$, ��������
������������� �� ������������ (��������� ����� ������ ���); � ���������
������ ����������~$|LINK|[i]\asg|R|$, $i\asg|R|$.

\st[�������� ����� ����.] ��������~$|TABLE|[i]$ ��� ������� ����
�~$|KEY|[i]\asg K$ �~$|LINK|[i]\asg0$.
\algend

� ��������� ����������� ��������� ���������� �������, ��� ��� �����
������� � ������� ������ ���������� �� �����.
\picture{���. 39.  ����� � �������� �� ���������� ������� � ���������.}
[��., ��������, ���.~40, ��� |SEKS| �������� � ������, ����������~|TO|
�~|FIRE|, ��� ��� ��������� ���� ��� ��� �������� � �������~9.]
\picture{���. 40. ��������� ������.}

����� �������� ������ � ������ ��������� ���� �����, ������� ���������
��������� ��� \MIX{} (��� �����������
%%613
��������� �����������, ��� ������,  ��� �������, ����� ���������).

\prog C.(����� � �������� �� ���������� ������� � ���������.)
��� �������� ����� �������, ��� ����� ������� �� ���� ������, � ���� �����
��������� ������:
\picture{���. ���. 613}
� �������� ������� �������~$M$ ������� ������� �����;
$|TABLE|[i]$~�������� �� ������~$|TABLE|+i$; $|rI1|\equiv i$,
$|rA|\equiv K$.
\code
KEY   &EQU  & 3:5
LINK  &EQU  & 0:2
START &LDX  & �             & 1     & C1. �����������.
      &ENTA & 0             & 1
      &DIV  & =M=           & 1
      &STX  & *+1(0:2)      & 1
      &ENT1 & *             & 1     & $i\asg h(K)+1$.
      &INC1 & 1             & 1
      &LDA  & K             & 1
      &LD2  & TABLE, 1(LINK)& 1     & C2. ������?
      &J2N  & 6F            & 1     & �� C6, ���� � $|TABLE|[i]$ ��������.
      &���� & TABLE, 1(KEY) & A     & C3. ���������.
      &JE   & SUCCESS       & A     & �����, ���� $K=|KEY|[i]$.
      &J2Z  & 5F            & A-S1  & �� C5, ���� $|LINK|[i]=0$.
4H    &ENT1 & 0,2           & C-1   & C4. ������� � ����������.
      &���� & TABLE, 1(KEY) & C-1   & C3. ���������.
      &JE   & SUCCESS       & C-1   & �����, ���� $K=|KEY|[i]$.
      &LD2  & TABLE,1(L1NK) & C-1-S2
      &J2NZ & 4B            & C-1-S2& ������������, ���� $|LINK|[i]\ne0$.
5H    &LD2  & R             & A-S    & C5. ����� ��������� ����.
      &DEC2 & 1             & T      & $|R|\asg|R|-1$.
      &LDX  & TABLE,2       & T
      &JXNN & *-2           & �      & ���������, ���� ����� $|TABLE|[|R|]$.
      &J2Z  & OVERFLOW      & A-S    & �����, ���� ��� �������. �����
      &ST2  & TABLE, 1(LINK)& A-S    & $|LINK|[i]\asg|R|$.
      &ENT1 & 0,2           & A-S    & $i\asg|R|$.
      &ST2  & R             & A-S    & ��������~|R| � ������.
6H    &STZ  & TABLE, 1(LINK)& 1-S    & C6. �������� ����� ����.
      &STA  & TABLE, 1(KEY) & 1-S    & $|KEY|[i]\asg K$.
\endcode
\progend
����� ������ ���� ��������� ���������� ��������� ���������:

\medskip
\item{$C=$}����� ��������� �������, ����������� �� ����� ������;
%%614
\item{$A=$}1, ���� ������ ������������� ���� �������� �������;

\item{$S=$}1 ��� ������� ������, 0 ��� ���������;

\item{$T=$}����� ��������� �������, ��������������� � �������� ������
���������� ������������.
\medskip
\noindent ����� $S=S1+S2$, ���~$S1=1$, ���� ������ ����� ����
�������. ��������� ����� ������ ���� ������ ���������~C
�����~$(7C+4A+17-3S+2S1)u$, ������� ������ ����� ���~$S=0$ �������
��������������� �������~$(8A+4T+4)u$.

�����������, ��� � ������ ������ ��������� ������� �������� $N$~������,
� ������
$$
\alpha=N/M=\hbox{����������� ���������� (��������) �������.}
\eqno (14)
$$
����� ������� ��������~$A$ ��� ��������� ������, ��������,
�����~$\alpha$ (��� ��������� ������� �����������); � ���.~39
������������, ��� ������� ��������~$C$ ��� ��������� ������ ����������
$$
C'_N=1+{1\over4}\left(\left(1+{2\over M}\right)^N-1-{2N\over M}\right)
\approx 1+{1\over4}(e^{2\alpha}-1-2\alpha).
\eqno(15)
$$

����� �������, ���� ������� ��������� ����������, ������� ����� ����,
������������ �� ����� ���������� ������,
����������� �����~${1\over4}(e+2)\approx 1.18$; ���� ���� �������
����������� ���������, ������� ����� ���� ��� ������� ���������� ��������
���������� ���� �����~${1\over4}(e^2+1)\approx 2.10$. ��� ������������ �
���.~40, ������������������ ���������� ����� ����. ��� �������� ����������,
 ��� ��� ��������� ������� ����������� \emph{������ �������� ���������,
�������� �� ����������� ���������.} ����������, $C$~����� ����� ������~$N$,
 ���� ���-������� ����� ��� ���� ��� ������� �� �������.

��� �������� ������ $A$~������ �����~1. ������� ����� ���� ����� ���������,
 ������������� ��������~$C+A$ �� ������~$N$ ��������� ������� � �������
��~$N$. ��������������, ��� ��� ����� �������������. �����
$$
\eqalignno{
C_N&={1\over N}\sum_{0\le k<N}\left(C'_k+{k\over M}\right)
=1+{1\over8}{M\over N}
\left(\left(1+{2\over M}\right)^N-1-{2N\over M}\right)
+{1\over4}{N-1\over M}\approx&\cr
&\approx 1+{1\over 8\alpha}(e^{2\alpha}-1-2\alpha)+{1\over4}\alpha.& (16)\cr
}
$$
���� � ������ ����������� ������� � ������� ��� ���������� ��������
����������� ���� ����� $1.80$~�����! ���������� (��.~���.~42) �������
��������~$S1$ ����������� ������
$$
S1_N=1-{1\over2}((N-1)/M)\approx 1-{1\over2}\alpha.
\eqno(17)
$$
%%615
�� ������ ������ ���~C5 ����� ���������� �������������, ��� ��� � ���
����� ��������� ������� ������������ ���������������. �� �
���������������� � �������� ���������� ������� ��������� ����� ���� �
����~C5 �� ��������� ���������� ��������� � �������; ������, � ������� ��
������ ������� �������� �� ����� ����� ����� �����! � ���.~41 ������������,
��� ��� ���������� ���������� ������~$T\approx \alpha e^\alpha$.

����� ���� �� �������� ��������� �������, ��������������� �������
������������� ��������~C, �� ����� �������� �� ���������� � �����������
�������. ����������, ��������, ��� ���������� ��� ������� ��������~|SEKS|
� �������~9 (��.~���.~40). ����� ������ ���������� �����������, �����
�����������~|FIRE|; ��� ���� ���������� ����� ����, ���������� ������
��~|FIRE|. ��� ������� ���� ������ �����, ��� ��������� ����� ������
�~1962~�., ������ ������������ ������������ ��������� ������, ��� ��� �
������ ������ ������� ���������. ������ ���, ��������, �������� �������
���� ������, ��������� ���~C4 ���������� �������. � ���.~34 ��������,
��� � ������ ���������������� ������� ������� ����� ���� ����������� ��
$$
\eqalignno{
C'_N&=\left(1-{1\over M}\right)^N+{N\over M}\approx e^{-\alpha}+\alpha
\qquad\hbox{(��������� �����);} & (18)\cr
C_N&=1+{N-1\over 2M}\approx 1+{1\over2}\alpha
\qquad\hbox{(������� �����).} & (19) \cr
}
$$
���� �� ����� ���� ������ ��������� �������� ��������.

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

�������, ��� ����� ������� ����� ������������ � ���~$N>M$, ��� ���
������������ �� ������������ ��������� ��������. ���� ������������
���������� ������, �������~(18) �~(19) ����������� ���~$\alpha>1$. �����
�� ������ ����������, ��� � ���������~C, ����� �������� �������������
�������� �� ��������������� ��� ������. ��� ������� �.~�����, �
���� ������ ������� ����� ���� ��� ������� $(M+L+1)\hbox{-��}$~��������
����������~$\left(L/2M+{1\over4}\right)((1+2/M)^M-1)+{1\over2}$.

\section ���������� �������� "�������� ����������". ������ ������ �������
�������� �������� ������� � ���, ����� ��������� ���������� �� ������ �
������ ������������� ���� �� ������ ��������� �������� �������, ���� ��
����� ������� ����~$K$ ��� ��������� �������. �� ����� ���� �� �����
�������, �������� �������� ������ ����~$K$ ���������� ������������������
%%616
����, �.~�.~������������������ ������� � �������, ������� �����
������������� ������ ��� ��� ������� ��� ������~$K$. ���� ��, ���������
������������~$K$ ������������������ ����, ����������� �� ��������� �������,
 �� ����� ������� �����, ��� $K$~��� � �������, ��� ��� �� ��
������������������ ���� ����������� ������ ��� ��� ��������� ������� �����.
 ���� ����� ����� ������� �.~�������� ������ \dfn{��������
����������} [{\sl IBM J.~Research \& Development,\/} {\bf 1} (1957), 130--146].

���������� ����� �������� ���������, ��������� ��� \dfn{��������
�����������,} ���������� ����������� ������������������
$$
h(K), h(K)-1, \ldots, 0, M-1, M-2, \ldots, h(K)+1
\eqno(20)
$$
� ����������� ��������� �������.

\alg L.(����� � �������� �� �������� ���������� �������.)
�������� ��������� ��������� ������ ����~$K$ � ������� �� $M$~�����.
���� $K$~��� � ������� � ��� �� �����, ����~$K$ �����������.

���� ������� ������������ �����~$|TABLE|[i]$, $0\le i<M$, � �����������
���� ��������� ����� �����---\emph{���������} �~\emph{�������}. ������� ����
�������� ����~$|KEY|[i]$ �, ��������, ������ ����. �������� ���������������
����������~|N| ����� ����� ������� �����; ��� ���������� ���������������
��� ����� �������, � ��� ������� ������ ����� �� �������� ������������� ��~1.

������ �������� ���������� ���-�������~$h(K)$ � ��������
������������������ ����~(20) ��� ���������. ����������� ����
������������������ ����������� ����.

\st[�����������.] ���������� $i\asg h(K)$. (������ $0\le i< M$.)

\st[��������.] ���� ����~$|TABLE|[i]$ ��������, �� ������� ��~\stp{4}. �
��������� ������, ����~$|KEY|[i]=K$, �������� ������������� ������.

\st[������� � ����������.] ����������~$i\asg i-1$; ���� ������ $i<0$,
����������~$i\asg i+M$. ��������� ��~\stp{2}.

\st[��������.] (����� ��� ���������.) ����~$|N|=M-1$, ��������
������������� �� ������������. (� ������ ��������� ���������, ���
������� ����� ���~$|N|=M-1$, � �� ���~$|N|=M$; ��.~���.~15.) � ���������
������ ����������~$|N|\asg|N|+1$, ��������, ��� ����~$|TABLE|[i]$ ����� �
����������~$|KEY|[i]\asg K$.
\algend

�� ���.~41 ��������, ��� ���������� ��� ������� � ������� ���������~L ����
"����������" ������~(11), ������� ���� ����������� 2, 7, 1, 8, 2, 8, 1
��������������. ��������� ��� �����---|FEM|, |SEKS| �~|SYV|---������� ��
��������� �� ������ ���������� ��������~$h(K)$.
%%617

\picture{���. 41. �������� �������� ���������.}
\prog L.(����� � �������� �� �������� ���������� �������.)
��������� �������� � �������, ����������� ������ �����; ������ �������
���� ������������ ������, ��� ��� ���� ���������� ��������� ������� �
�������. (������ ����������� ������� � ���, ����� �������� �������
����������������� ������, � � ��������� ������� ��������~$-1$.)
��������������, ��� ������ �������~$M$---������� ����� � ���
����~$|TABLE|[i]$ ����� �����~$|TABLE|+i$, $0\le i < M$. ��� ���������
����������� ����� � ������~$|TABLE|-1$ �������~0.
������~|VACANCIES| �������� ��������~$M-1-N$; $|rA|\equiv K$, $|rI1|\equiv i$.

����� ��� ��������� ����������� ����� ��������� �� ���� ��������
��������~"$i<0$", ��� ��� � ��� �������� ���� ������������ �����
�����~\stp{2} �~\stp{3}. ��������� ���� ������ $(7C+9E+21-4S)u$, � �������
����� ���������� ������ ������� �������������~$9u$.
\code
START & LDX & K         & 1    & L1. �����������.
      & ENTA& 0         & 1
      & DIV & =M=       & 1
      & STX & *+1(0:2)  & 1
      & ENT1& *         & 1    & $i\asg h(K)$.
      & LDA & K         & 1
      & JMP & 2F        & 1
8H    & INC1& M+1       & E    & L3. ������� � ����������.
3H    & DEC1& 1         & C+E-1& $i\asg i-1$.
2H    & CMPA& TABLE,1   & C+E  & L2. ��������.
      & JE  & SUCCESS   & C+E  & �����, ���� $K=|KEY|[i]$.
      & LDX & TABLE,1   & C+E-S
      & JXNZ& 3B        & C+E-S& �� L3, ���� � $|TABLE|[i]$ ������.
      & J1N & 8B        & E+1-S& Ha L3 � $i\asg M$, ����~$i=-1$.
4H    & LDX & VACANCIES & 1-S  & L4. ��������,
      & JXZ & OVERFLOW  & 1-S  & ����� �� ��������., ���� $N=M-1$.
      & DECX& 1         & 1-S
      & STX & VACANCIES & 1-S  & ��������� $N$ ��~1.
      & STA & TABLE, 1  & 1-S  & $|TABLE|[i]\asg K$.
\endcode
\progend
%% 618
��� � � ���������~C, �� ����������~$C$ �� ����� � ����������  ����, ��
����������~$S$---��� �� ����� �������. ����������~$E$  ����� ����������, ���
��� ��� �����~1, ���� ���� ������������� ����� ����������
����~$|TABLE|[-1]$; �� ������� �������� �����~$(C-1)/M$.

������������ � �������� ������������ ����������, ��� ���� ����� ��������
���������, ���� ������� �� ������� ���������, �� � ����� ������ �������
�����������, ������� ����� ���� ���������� ��� ����� �������. �������
������ ��������� ����� ������, ���������� ���������
�������������� ���������� ������� ($M=19$, $N= 9$):
\picture{���. ���. 618}
������������� �������� ���������� ������� �������. ����~$K$,  �������
������ ���� �������� � ������� ���������, �������  � ���� �� ������
��������� �������, �� �� � ������� �������������. � ����� ����, $K$ �����
�������� � �������~$11$, ����  $11\le h(K)\le 15$, � � �������~8 ��
������� ���� ���~$h(K)=8$.  �������������, ����������� ������� �
�������~11 � ���� ���
������, ��� � �������~8; ������� ������ ��������� ����� �ٸ
�������.

�� ��� ������� ���� �� ���� �� ��������� ������������ ������� ���������
��������� �����������, ��� ��� ����������� ���� ���������� � ���
���������~C. (���� ������ �� ������� ��������� �������� ��������� �����
������ �� ������ ��������.) ��������� ��������� ��������� ��� ������� �
������ �����~4 ���~16 (��.~(21)); ��� ��������� ������ ������������.
�������, ��� � ���������~C ������ ���������� �� ����� ��� �� ���� �������.
�������������, �������������� ��������� ����������� ����� ����������,
����� $N$~������������ �~$M$.

����� � ���� ��������� �� �������, ��� ������� ����� ����, ������������
����������~L, ����������� �����
$$
\eqalignno{
C'_N&\approx {1\over 2}\left(1+\left({1\over 1-\alpha}\right)^2\right)
\rem{(��������� �����);} & (22) \cr
C_N&\approx {1\over 2}\left(1+{1\over 1-\alpha}\right)
\rem{(������� �����),} & (23)\cr
}
$$
��� $\alpha=N/M$~���� ����������� ���������� �������. ��� ���, ����
������� ��������� ������ ��� ��~75\%, ���������~L �������� ����� ��� ��
������, ��� � ���������~C, ���� ��������� � �������� � ���������������
��������� �������. � ������ �������, ����� $\alpha$~������������ �~1,
������, ��� ����� ������� � ���������~L, ��� ��, ��� ��� �������� ��������,
�� �����.

%%619
� ����� ����, ����~$N=M-1$, � ������� ������� ���� ���� ��������� �����,
������� ������� ����� ���� ��� ���������� ������ �����~$(M+1)/2$; ��
�������, ��� ������� ����� ���� ��� �������� ������ � ����������� �������
����������� �����~$\sqrt{\pi M/8}$.

������� ����������, ������� ������ �������� ����������� ������������� �
������ ����� ����������� ������, ������������ ��� �������������
����������� ��������, ���� ������ �������� ��������� ����������������
��������
������~$\set{K, K+1, K+2,~\ldots}$, ��� ��� ��� ����� ����� �����
���������������� ���-����. ����������� ���������� ������� ����� ������
���������� ������.

������ ������ ���������� �������� ���������������� ����� �����������
������� � ���, ����� � ����~L3 ������~$i\asg i-1$ ����������~$i\asg i-c$.
������� ����� ������������� ��������~$c$, \emph{������� ������� �~$M$},
��� ��� �� �������� ��� ������� �������. ��� ��������� �������
���������~L ��������� ��������� � �� �������� �������� ����������, ���
��� ��-�������� ����� �������������� ������ �������, ��������� ���� ��
����� ��~$c$; �������~(22) �~(23) ��������� � ����. ������,
������ ��������� ���������������� ������~$\set{K, K+1, K+2,~\ldots}$
�� ������ ����������� � ������.

���� ������������� ��������~$c$ �� ��������� ����������, ����� �����������
�������� ��������, ���� �������~$c$ ��������� ��~$K$. ��� ���� ��������
� ������� ��������� ���������~L, ������� ������� ������ ��� ��~�������
[���������� �����������, Calif. Inst. of Technology (1968), 149--150].
\alg D.(�������� ��������� � ������� ������������.)
���� �������� ����� ��������� � ����������~L, �� ���������� ��������� ����
������������������ ����, �������� ��� ���-�������~$h_1(K)$  �~$h_2(K)$.
��� ������, $h_1(K)$~��������� �������� ��~0 ��~$M-1$ ������������; ��
��������~$h_2(K)$ ������ ������ ��~1 ��~$M-1$ � ���� \emph{������� ������
�~$M$}. (��������, ���� $M$---������� �����, �� $h_2(K)$~����� ����
\emph{�����} ��������� ��~1 ��~$M-1$ ������������, ���, ����~$M=2^m$,
��~$h_2(K)$ ����� ���� ����� \emph{��������} ������ �����~1 �~$2^m-1$.)

\st[������ �����������.] ����������~$i\asg h_1(K)$.
\st[������ �����.] ���� ����~$|TABLE|[i]$ ��������, �� �������
��~\stp{6}. � ��������� ������, ����~$|KEY|[i]=K$, ��������
������������� ������.

\st[������ �����������.] ����������~$c\asg h_2(K)$.
\st[������� � ����������.] ����������~$i\asg i-c$; ���� ������~$i<0$,
����������~$i\asg i+M$.
\st[���������.] ���� ����~$|TABLE|[i]$ ��������, �� �������
%%620
��~\stp{6}. � ��������� ������, ����~$|KEY|[i]=K$, �������� �������������
������; � ��������� ������ ��������� ��~\stp{4}.
\st[�������.] ����~$|N|=M-1$, �������� ������������� �� ������������. �
��������� ������ ����������~$|N|\asg |N|+1$, �������� ����~$|TABLE|[i]$
��� ������� � ����������~$|KEY|[i]\asg K$.
\algend

��� ����������~$h_2(K)$ ���� ���������� ��������� ��������:
���� $M$---������� ����� �~$h_1(K)=K \bmod M$, ����� ��������~$h_2(K)=1+(K
\bmod (M-1))$; �� ��� ��� $M-1$~�����, ���� �� ����� ��������~$h_2(K)=1+(K
\bmod (M-2))$. ��� ������� �� ����� � ����� ������~$M$, �����~$M$ �~$M-2$
���� �������� �������-����������, ��������~1021 �~1019. �����
�����~$h_2(K)=1+(\floor{K/M} \bmod (M-2))$, ��� �������~$\floor{K/M}$
����� �������� � �������� ��� �������� ������� ����������~$h_1(K)$.

����~$M=2^m$ � ������������ ����������� ����������, $h_2(K)$~�����
��������, ��������� ����� ��� �� $m$~����� ����� � �������� �������� "���"
�~1, ��� ��� � ������������������ ������~(5) ����� ��������
$$
\mixcode
ENTA  & 0   &  �������� |rA|.
SLB   & m   &  ����� |rAX| �� $m$~����� �����.
ORR   & =1= &  $|rA|\asg |rA|\lor 1$.
\endmixcode
\eqno(24)
$$
��� ������� ������ �������.

� ������ �� ������������ ���� ������� $h_1(K)$ �~$h_2(K)$ ��������
"������������" � ��� ������, ��� �� ��������� ������ �������� �����
�������~$h_1$  �~$h_2$ ��������� � ������������~$O(1/M^2)$, � �� �
������������~$O(1/M)$. ������������ �������� ����������, ��� ����� ���� �
���������~D ��� ����������� ���-��������, � ��������, �� �������� �� �����
����, ������� �������������, ���� �� ����� ����������� � �������
��������; "����������", �������� ����� � ���������~L, ����� ����������� ���.

����� ����� ��������� �����������~$h_2(K)$ ��~$h_1(K)$ (��� ��������� �
1968~�.\ �.~�����); ��������, ���� $M$---������� �����, �������
$$
h_2(K)=\cases{
1, & ���� $h_1(K)=0$;\cr
M-h_1(K), & ���� $h_1(K)>0$.\cr
}
\eqno(25)
$$
���� ����� ������� ���������� �������, �� �� ��� �� �������� �
\emph{���������� ����������,} ������ ��������� ������ ���� ��-��
���������� ����������� ����, ��� ��� ��� ����� ������ ��������� ����� �
��� �� �����. �������, ���������� ����, ����� ������������, �����
����������, ������������ �� ������� �� ������� ����������� ������ �� ������.

%% 621

���������~L �~D ����� ������, �� ����� � ���������� ��������, �������
������� �������� ������� ������ ��������������� �������� ���~\MIX.


\prog D.(�������� ��������� � ������� ������������.)
��� ��� ��� ��������� ������ ���������� ���������~L, ��� ���������� ���
������������. �����~$|rI2|\equiv c-1$.

\code
START&LDX &K        &1
     &ENTA&0        &1
     &DIV &=M=      &1
     &STX &*+1(0:2) &1
     &ENT1&*        &1
     &LDX &TABLE,1  &1
     &����&K        &1
     &JE  &SUCCESS  &1
     &JXZ &4F       &1-S1
     &SRAX&5        &A-S1
     &DIV &=M-2=    &A-S1
     &STX &*+1(0:2) &A-S1
     &ENT2&*        &A-S1
     &LDA &K        &A-S1
3H   &DEC1&1,2      &C-1
     &J1NN&*+2      &C-1
     &INC1&M        &B
     &CMPA&TABLE,1  &C-1
     &JE  &SUCCESS  &C-1
     &LDX &TABLE,1  &C-1-S2
     &JXNZ&3B       &C-1-S2
4H   &LDX &VACANCIES&1-S
     &JXZ &OVERFLOW &1-S
     &DECX&1        &1-S
     &STX &VACANCIES&1-S
     &LDA &K        &1-S
     &STA &TABLE,1  &1-S
\endcode
\progend
�������� ������~$A$, $C$, $S1$, $S2$ ����� ��� �� �����, ��� �
� ���������~C. ������� �������� ����������~$B$ �������� �����~$(C-1)/2$.
(���� ������ ��������~$h_2(K)$, ������,
��~$1\le h_2(K)\le {1\over2} M$,
��������~$B$ ��������� �� ����~$(C-1)/4$, ��������, ���������� ����� ����
�� ������ �� ��� ��� ���������� ��������.) ���� � ������� $N=\alpha M$~������,
������� ��������~$A$, ����������, �����~$\alpha$ ��� ����������
������ �~1 ��� ��������. ��� � � ���������~C, ������� ��������~$S1$ ���
���������� ������ ����������~$1-{1\over2}((N-1)/M)\approx
1-{1\over2}\alpha$. ������ ����� ���������� ������� ����� ����, ������
������������ �������� ���������� ������� �������� � ����������� ����
��������� ��� "������������ �����������":
$$
\eqalignno{
C'_N&={M+1\over M+1-N}\approx(1-\alpha)^{-1} \rem{(��������� �����)};&(26)\cr
C_N&={M+1\over N}(H_{M+1}-H_{M+1-N}) \approx-\alpha^{-1}\ln (1-\alpha)
\rem{(������� �����)},&(27)\cr
}
$$
����~$h_1(K)$ �~$h_2(K)$ ����������. ����� �� $h_2(K)$~������� ��~$h_1(K)$,
 ��� �~(25), ��������� ���������� �������� ���������� �������
%%622
�������� ��
$$
\eqalignno{
C'_N &={M+1\over M+1-N}-{N\over M+1}+H_{M+1}-H_{M+1-N}+O(M)^{-1}\approx\cr
&\approx(1-\alpha)^{-1}-\alpha-\ln(1-\alpha);&(28)\cr
C_N&=1+H_{M+1}-H_{M+1-N}-{N\over 2(M+1)}
-(H_{M+1}-H_{M+1-N})/N+O(N^{-1})\approx\cr
&\approx 1-\ln(1-\alpha)-{1\over2}\alpha. &(29) \cr
}
$$
(��.~���.~44.) �������, ���, ����� ������� �����������, �.~�.~����� $N
$~��������� �~$M$, ��������~$C_N$ ������������ �~$H_{M+1}-1$,
�~$C'_N$---�~$H_{M+1}-{1\over2}$; ��� ����� �����, ��� � ������ ���������~L,
�� �� ����� ������, ��� � ������� �������.

��������� � ���������~L ����� �������� ��������� ������ �������, �������
����������� ��������������� ���� ��� ����������� �������. �� ���.~42
������������ ������� ������� ������ ��������~L, D � ����������������
���������~D (������ ��� ����������� ������ �� ����� ��������� ����������):
�� �������� �������� ��������� ����������~$h_2(K)$ � �������~10--13 �� ���
�������
$$
\mixcode
ENN2  & -M-1, 1 & $c\asg M-i$.
J1NZ  & *+2
ENT2  & 0       & ���� $i=0$, $c\asg 1$.
\endmixcode
\eqno(30)
$$
\picture{���. 42.  ����� �������� ������ ��� ���� ���� �������� ���������.}
%%623
� ������ ������ ��������� ���������� ����� ������������ ���������� �����������.

�� �������� ��� �� ����� �� ���� �������� �������� ����������~$h_2(K)$,
������� ������~10--13, ������, ��
$$
\mixcode
AND  & =511=   & $|rA|\asg |rA| \bmod 512$.
STA  & *+1(0:2)
ENT2 & *       & $c\asg |rA|+1$.
\endmixcode
\eqno(31)
$$
���� $M$---������� �����, �������~512. ��� ����, ������������ ������ �
���\'� [{\sl CACM,\/} {\bf 13} (1970), 675--677], ���������� ������������
��������~D, ��������� �������� ���������� ���������� ��� ������ ��
��������� �������.

���� ���������� ����� ������ ������������������� ���� � �������� ���������
���������~L, ��, ��-��������, �� ���� �� ��� �� ����� ���������~D. (����
�����, ���������� ���������� �����, ��������� � ���.~20.)
\picture{ ���. 43. ������� ��� ���������� ���� ����� ���������� � ��������
������. ����� �������� ����� ������� � ������� �� �������  ���������.}
\section ���������, ������������ �������. ������ ����� ����� ����� ������
��������� ���������~D, ����� ������� ����� �������� ������ ����������
������������ �� ���� ���������� �������. ��� ����� ������� �� ��� �����,
��� �� ������ �����������
%%624
������� ����� ������������ ������� ���� �������; ������� �� ����������
������ ������ ������ ��� ������� ��������, nepe����� ������, �����
��������� ��������� ����� �������.
[{\sl CACM,\/} {\bf 16} (1973), 105--109.]

��������, �� ���.~43 ��������, ������� ��� ��� ��� ���� �������������
���������� � �������� ��������� ��~PL/1. ���� �� ���� ������, ����������
�~PL/1, ������������ ���������� ������� ��� �������� ���� ����������,
����� ������ ������ ����� ���� ��� ����� ���, � ��������� �� ���� �������.
 ���������� ���� �~���\'� ����������, ��� ���������� �~������ �����������
���� �������� ������ �������� $10988$~��� �� ����� ���������� ��������� �
�������� ���� $735$~�������, �.~�.~�� ���� ��������� ����� �����������
�������� 14~�������.
������ ������� ��������� ������ ���� ��� (��������, ������� �������������
����� �������� � ��������) � ������������ ����� ����� ������������� ���
�������.

����� ��������� ��������� ������� �������� ������� ������� � ���������~D.
�����������, ��� ��� ��������� ������ ���� ���������� ������
$$
p_0, p_1,~\ldots, p_{t-1}, p_t,
$$
���~$p_j=(h_1(K)-jh_2(K))\bmod M$ � ����~$|TABLE|[p_t]$ ����. ����~$t\le
1$, ��, ��� ������, ���������~$K$ � �������~$p_t$, �� ����~$t\ge2$,
���������~$c_0=h_2(K_0)$, ���~$K_0=|KEY|[p_0]$, � �������, �������� ��
�~$|TABLE| [(p_0-c_0)\bmod M$]. ���� ������� ���������, �������� � ������
���� ���������� ������~$|TABLE|[p_0]$ � ���������~$K$ � �������~$p_0$. ���
����������� ����� ������� $K_0$ �� ���� ���, �� ��������� �����
�������~$K$ �� $t\ge2$~�����.  ������� ������. ����������, ����
�~$|TABLE|[(p_0-c_0)\bmod M]$ ������ �~$t\ge3$, �� ������� ������~$|TABLE|
[(p_0-2c_0)\bmod M]$;
���� � ��� ������, ���������~$c_1=h_2(|KEY|[p_1])$ � �������
$|TABLE|[(p_1-c_1)\bmod M]$ �~�.~�. ������,
�����~$c_j=h_2(|KEY|[p_j])$ �~$p_{j,k}=(p_j-kc_j)\bmod M$; ����
�������~$|TABLE|[p_{j,k}]$ ��������� �������� ��� ����~$j, k$, �����,
���~$j+k<r$, � ����~$t\ge r+1$, �������������   ����~$|TABLE|[p_{0,r}]$,
$|TABLE|[p_{1, r-1}]$,~\dots, $|TABLE|[p_{r-1, 1}]$. ���� ������ ���������
��������� �������~$p_{j,r-j}$,
�������������~$|TABLE|[p_{j, r-j}]\asg |TABLE|[p_j]$ �
���������~$K$ � �������~$p_j$.

��� �������� �� ������� ������, ������� ����� ���� � �������� ��������
������ ����������� (��.~���.~44) � ��� ������������ �������� �����������
�����~$2.49$.

�����~$t+1$ ���� ��� ��������� ������ � ���������� ������������� ���������
�� �����������; ��� �������� �� ������,  ��������� ��������~(26), �
���������~$(M+1)/2$ ��� �����������  �������. ��� ������� �������~$h_2$
���������� � ������� ���������
%%625
$\alpha^2+\alpha^5+{1\over3}\alpha^6+\ldots$~���. �������� �������
������, ���~$\alpha\to 1$, ��� �������� ����� �������~$\sqrt{M}$. �������,
����� �� ������, ��� ���������� �������, ����������� �����
$\alpha^2+\alpha^4+{4\over3}\alpha^5+\alpha^6+\ldots$~�������������� ����.

\section ��������. ������ ������������ ����� ����� � ��������� �
����� ����������, ���������, ��� \emph{��������� ������ �������� �������
�� ���������� ������� �� ��������.} ��������, ��� ������� �������
����~|EN| (��.~���.~41) ������ ������ �������� ��� ������� � ������� ���
���������, ��� ������ ����~|FEM| �������� �������� ����������! (��������,
��� EN � FEM ����� ���������� ���-����. ��� ������~|FEM| �� ��������� ��
��������� ����, ��� ��������������� � ���, ��� ����� ��������.)
����������� ����������� ����������� ��� ���������~C, � ������� �����
����� ��������� �������; ����������� ���� �������� ������~|TO| �~|FIRE|
(��.~���.~40).

������ ������, ����� ����������� ��������, ������� � ���������������
������ ����������� ��������, �.~�.~���� ��� ���� ������� � �������:
���������, ������� � ���������. ��� ������ ����� ��������� ������� �����
���������� ��� �������. � ������ ���������� ������ ���� ����� �������� �
������ ����������� ��������� ��� ��������� �������.

������ ��� ���� ��������� ������ ��� ����� ������ ���������, ������ ���
������� ������� ������� �� ����� ����� ����� ���������. ����� �������
������������������ ������� � �������� ��� ��������� ������������ � �����
������ �������� � ������ ��������� ����� ����� ��������� $M$~����!
����� ����, ����� ��������� ������ �������, ��� ��� � ����~D4
���������� ���������, �� ��������� ��~$i$ � ������ ���������� ��������, �
����� ���� ��� ������� ������ ��������� �~$C_N$ ��~$C'_N$.

���� ������������ �������� ����������� (�.~�.~��������~L), �����
����������� ������������, ��� ������� ��� �� �������� ��������� ���������
�������������� ������ �� ��������.

\alg R.(�������� ��� �������� �����������.)
��������� �������� ������� ������ �� ������ �������~$|TABLE| [i]$
�������� ���������� �������, ����������� � ������� ���������~L.

\st[���������� ������.] �������� ������~$|TABLE|[i]$ ��� ��������� �
����������~$j\asg i$.

\st[���������~$i$.] ����������~$i\asg i-1$ �, ���� ��������~$i$ �����
�������������, ����������~$i\asg i+M$.

\st[���������~$|TABLE|[i]$.] ���� �~$|TABLE|[i]$ ��������, ��������
�����������.  � ��������� ������ ����������
%% 626
$r\asg h(|KEY| [i])$---�������������� ���-��� �����, ����������� ������ �
�������~$i$. ����~$i\le r<j$, ���~$r<j<i$, ���~$j<i\le r$ (�������
�������, ���� $r$~����� ���������� �����~$i$ �~$j$), ��������� ��~\stp{2}.

\st[����������� ������.] ����������~$|TABLE| [j]\asg |TABLE| [i]$ �
��������� ��~\stp{1}.
\algend

� ���.~22 ��������, ��� ���� �������� �� �������� ���������
�������������, �.�.~������� ����� ����, ������������� ���������~(22)
�~(23), �������� �������. (����� ������ ��������� ��� �������� �� ������
��� ������� � �������~6.2.2H.) ������ �������������� ���������~R ������
������� �� ���� �����, ��� ������������ �������� �����������; � ������
���������~D �� ���������� ����������� ��������� ��������.

����������, ���� ������������ ����� ������� � ��� ������� ���-���� �������
��������� ������, �������� �� �������� ���������, ��� ��� �������� ������
� �������� �� ���������� ��������� ������. �������� ��� ���������~C
����������� � ���.~23.

\section *������ ����������. ��� ����������� �� ���������� ��
������������� ������, ������� �������� ����� ����� ��������� �������
����������� � �������. ��������� ������ � ���� ���������� �����
��������� ����, ��� ��� ��� ���������� ����������� � ���, ��� ��������� �
������� �������� ����� �������.

������ ��� ���������� � ������� ��������� ����������� �~�.~�., ����������
������ ������������ ������ ������ ��������, ������� ����� �������
\dfn{����������� ������������} (��.~�~W.~W.~Peterson, {\sl IBM J.~Research
\& Development,\/} {\bf 1} (1957), 135--136). � ������ ������
��������������, ��� ����� ��������
� ��������� ������� �������, ��� ��� ��� $\perm{M}{N}$~���������
������������ �� $N$~������� �~$M-N$~��������� ����� �������������. ���
������ ���������� �� ��������� ������� ���������� ��� ����������
����������; � ��������, ��������������, ��� ��������� ����� ������ ��
������� ��. ��������� ������. ��� ��������������� ������ ����������� ����,
��� ��� ������� $(N+1)\hbox{-��}$~�������� ��������� ����� $r$~����,
����� ����� ������������, � ������� ������ $r-1$~������ �����, �
��� ���� ������ ������ ��������, ��������� ��~$\perm{M}{N}$, �.~�.
$$
P_r=\perm{M-r}{N-r+1}\bigg/\perm{M}{N};
$$
�������������, ������� ����� ���� ��� ������������ �����������
%%627
����������
$$
\eqalignno{
C'_N &= \sum_{1\le r\le M} rP_r
=M+1-\sum_{1\le r\le M}(M+1-r)P_r=\cr
&=M+1-\sum_{1\le r\le M} (M+1-r)\perm{M-r}{M-N-1}\bigg/\perm{M}{N}=\cr
&=M+1-\sum_{1\le r\le M}(M-N)\perm{M+1-r}{M-N}\bigg/\perm{M}{N}=\cr
&=M+1-(M-N)\perm{M+1}{M-N+1}\bigg/\perm{M}{N}=\cr
&=M+1-(M-N){M+1\over M-N+1}={M+1\over M-N+1},
\qquad 1\le N\le M. & (32)\cr
}
$$
(�� ��� ������, � ��������, �� �� ������, ����������� � ����� �� ���������
��������; ���.~3.4.2-5.) �������~$\alpha=N/M$, ������ ������� ���~$C'_N$
����� ����������� �������� ��
$$
{1\over 1-\alpha}=1+\alpha+\alpha^2+\alpha^3+\ldots\,.
\eqno(33)
$$
����� ���� ����� ���� ������ ����������� �������������:
� ������������~$\alpha$ ����� ����� ��� ���� �����, �
������������~$\alpha^2$---����� ��� ��� �~�.~�. ��������������� �������
����� ���� ��� ������� ������ �����
$$
\eqalignno{
C_N&={1\over N}\sum_{0\le k<N}C'_k
={M+1\over N}\left({1\over M+1}+{1\over M}+\cdots+{1\over M-N+2}\right)=\cr
&={M+1\over N}(H_{M+1}-H_{M-N+1})
\approx {1\over \alpha}\log{1\over1-\alpha}. & (34)\cr
}
$$
��� ���������� ����, �������������� ����� ��������, ��� ��������~D �
����� ������������ ���-��������� ����� ����,  �� ��������, ��� �����������
�����������, � ��� ���� ������������ ���� ����� ������������
�������~(32)--(34). �� ����� ���� �.~����� � �.~�������� ������� ��������
������� ������� � ���, ��� ������� ����������� ��������������
(���~$M\to\infty$) ������������ ������������ [����� ������������].

�� ���� ������ ������������ ����������� �����������. ����� �������
�������� ����������� � ������ ������� ���������� ��������, ����� �������
������ ����, ����� �������������� ��������. � ������������� ������,
������� �� ����� ������������ ��� ���� ����, ��������������, ��� ���
$M^N$~��������� ���-�������������������
$$
a_1\ a_2\ \ldots\ a_N, \qquad 0\le a_j <M,
\eqno(35)
$$
�������������. ����� $a_j$~���������� �������������� ���-����� �����,
������������ � ������� � �������~$j$, ��� � ����, �������
%%628
����� ���� � ������ �������� ������ ��� ����� ������ ���������
��������� �����~$C_N$. ��� ���� ������� ����� ����, ������ ��� ����������
$k\hbox{-��}$~�����, ����������� ��~$1\le k\le N$ ��� ��������������
������ � �� ���� ���-�������������������~(35), ������� ����� ���������
���������������. ����������, ������� ����� ����, ����������� ��� �������
$N\hbox{-��}$~�����, ��� ������� ��� ��� ������������������~(35)
�������������, ��������� �����~$C'_{N-1}$; ��� ���� ������� ����� ���� �
��������� ������, ���� � ������� $N-1$~���������. ���� ������������
�������� ���������, ��
$$
C_N={1\over N}\sum_{0\le k < N} C'_k,
\eqno (36)
$$
��� ���, ���� ���� ��������, ����� �������� ������, ��� ���� ������� �~(34).

������ ������, ���� ��� ����� ���������� ������ ����� ��� ����������.
��-������, �� ��� ���-������������������ �������������, ������ ��� ����
����� �������� ����������. ��� ������ ����������� ���������~$a_1=a_2$
��������� �������, ���~$1/M$, ������ ��������� ������ ����� ����������,
��� ��� ���������� ���� ��������� ������ � �������� ������ �����
������~$M$. (��.~���.~24.) �����, ������� ���-������� �����
������������ ������������� ������� ������, ����� ���������~$a_1=a_2$
��� ����� ���������; � ���������� ���� ������ ����� ���� �����,
 �����������������. ������ ���������� ������ ������ ������� �� ���.~43:
�����, ����������� ����� (�� ���������� ������������), �������������
����. �������������, ���� ������~$C_N$ ����� ������� �����������������, �
��������� �� �������� ������ �������� ��������� �����, ��� �������������
��� ������.

����� ���� ��������� �� ������ ��������� "������" ������ ��������� �����������%
\note{1}%
{����� ����� �� ����� ���������� �� ��������������� ���������.
������� ������������ ����� ��� ������������� ���� � 1962~�., ������
����� ������ ������ ��� "���������� ���������������� ��� ���". ���
������ �������� ������ �������������� ��������� ������ ������� ������� ��
��������� ���� ����. ��� �� � ������, ��� ������� ����� ������ ���,
������ ��� ���� ����� ������� � ������!
}.
 �����~$f(M,N)$ ��������� ����� ���-�������������������~(35), �����, ���
�������~0 ������� ����� �������� ����� ������� ������ � �������
���������~L. �� �������� ��������� ��������� ����������� �������, ���
�������~0 �������� � ��� �� ������������, ��� � ����� ������ �������,
�.~�.~� ������������~$1-N/M$; ����� �������,
$$
f(M,N)=\left(1-{N\over M}\right)M^N.
\eqno(37)
$$
%%629
�� ����������� ��������~$f(0,0)=1$. �����~$g(M, N, k)$ ��������� �����
���-�������������������~(35), �����, ��� �������� ��������� �������~0
���������, ������� �~1 ��~$k$ ��������, � �������~$k+1$ ���������. �����
$$
g(M, N, k)=\perm{N}{k}f(k+1, k)f(M-k-1, N-k),
\eqno (38)
$$
��� ��� ����� ������������������ ������� �� ���� ����������������������.
���� (���������� $k$~���������~$a_i\le k$) ��������� �������~0 ��������� �
������� �~1 ��~$k$ ��������, � ������ (����������
$N-k$~���������~$a_j\ge k+1$) ��������� �������~$k+1$ ���������. ����������
$f(k+1, k)$~������������������� �������
���� � $f(M-k-1, N-k)$~������� � $\perm{N}{k}$~�������� ������� ���
����� ���������������������. �������, �������~$P_k$ ������ �����������
����, ��� ��� ������� $(N+1)\hbox{-��}$~�������� ����������� �����
$(k+1)$~����; ����� �������� (��.~���.~25), ���
$$
P_k=M^{-N}(g(M, N, k)+g(M, N, k+1)+\cdots+g(M, N, N)).
\eqno(39)
$$
������ $C'_N=\sum_{0\le k\le N} (k+1)P_k$; �����������
�����������~(36)--(39) � ��������� ���� ��������� ���������.

\proclaim ������� �. ������� ����� ����, ������ ��� �������������
���������~L (���� �������, ��� ���~$M^N$
���-�������������������~(35) �������������), �����
$$
\eqalignno{
C_N&={1\over2}(1+Q_0(M, N-1))  \rem{(������� �����);} & (40)\cr
C'_N&={1\over2}(1+Q_1(M, N))     \rem{(��������� �����),} & (41)\cr
}
$$
���
$$
\eqalignno{
Q_r(M,N)&=\perm{r}{0}+\perm{r+1}{1}{N\over M}+\perm{r+2}{2}{N(N-1)\over M^2}+\cdots=\cr
&=\sum_{k\ge0}\perm{r+k}{k}{N\over M}{N-1\over M}\cdots{N-k+1\over M}. &
(42) \cr
}
$$

\proof ��������� ���������� ��������� � ���.~27.\endmark

������������ � ������� �������~$Q_r(M, N)$ �������� �� ����� ������, �� �
���������������� �������� � ��� �����. �����
$$
N^k-\perm{k}{2}N^{k-1}\le N(N-1)\ldots(N-k+1)\le N^k;
$$
%%630
�������������, ����~$N/M=\alpha$, ��
$$
\eqalign{
&\sum_{k\ge0}\perm{r+k}{r}\left(N^k-\perm{k}{2}N^{k-1}\right)
\bigg/M^k\le Q_r(M,N)\le \sum_{k\ge0}\perm{r+k}{k}N^k/M^k,\cr
&\sum_{k\ge0}\perm{r+k}{k}\alpha^k-{\alpha\over M}
\sum_{k\ge0}\perm{r+k}{k}\perm{k}{2}\alpha^{k-2}\le
Q_r(M, \alpha M)\le \sum_{k\ge 0}\perm{r+k}{k}\alpha^k,\cr
}
$$
�.~�.
$$
{1\over (1-\alpha)^{r+1}}-{1\over M}\perm{r+2}{2}
{\alpha\over(1-\alpha)^{r+3}}\le Q_r(M, \alpha M)\le {1\over (1-\alpha)^{r+1}}.
\eqno(43)
$$
��� ����������� ���� ��� ������� ������~$a_r(M, N)$, ����� $M$~������
�~$\alpha$ �� ������� ������ �~1. (������ ������ ����� � ������, ���
�������.) ����~$\alpha$ ������������ �~1, �������~(43) ����������
�����������, ��, � �������, $a_0(M, M-1)$ ���� �������~$a(M)$,
��������������� ��������� ������� �� �������� ������� � �.~1.2.11.3;
�~$a_1(M, M-1)$ ������ �����~$M$ (���.~50).

�.~���~��.\ �~�.~����� ������� ������ ������ � ������� ���������
����������� [{\sl CACM,\/} {\bf 5} (1962), 459--462]. ���� �� ����� ����
���� ����������� � ������ �������� �������~K, �� ��������� ��������������
���� �� ��������, ������� �� ������ ������� ���. ������� ����������
������������ �������� ��������� �����������, ������� ����������
�.~���������� � 1957~�.

\proclaim ������� P. ������� ����� ���� ��� ������� ������ �
������� ���������~L �� ������� �� �������, � ������� ����� ����
���������, � ������� ���� �� ����, ������� ������ ����� ��� ��� ���� ���-�����.

����� �������, ����� ���������������� ���-������������������~$a_1$
$a_2$~\dots $a_N$ ���� ������������������ � ��� �� ������� ���������
������ �� �� ���-�������. (��� ������� ����, �� ������������, ��� ���
����� � ������� ����� ���������� ��������. ���� � ��������� �� ���
���������� ����� ������ ���������, �������, ����������� ���������������
� �������~6.1S, ����� ��������, ��� ������������ ������ ����������,
���� ��� ����������� � ������� �������� ������.)

\proof ���������� ��������, ��� ����� ����� ����, ����������� ��� �������
������ ��� ���-������������������~$a_1$ $a_2$~\dots $a_N$, ����� �����
���� ��� ������������������~$a_1$~\dots $a_{i-1}$ $a_{i+1}$ $a_i$
$a_{i+2}$~\dots $a_N$, $1\le i<N$. ��������, ����� ����������� ���� ������,
 ����� $(i+1)\hbox{-�}$~���� �� ������ ������������������ ����� � �������,
���������� $i\hbox{-�}$~������
%%631
� ������ ������������������. �� ���� $i\hbox{-�}$
�~$(i+1)\hbox{-�}$~�������� ������ ���������� �������, �� ����� ���� ���
$(i+1)\hbox{-��}$~����� ����������� �� �������, �� ������� �����������
����� ���� ��� $i\hbox{-��}$.
\proofend

�������~P ������, ��� ������� ����� ������ ���
���-������������������~$a_1$ $a_2$~\dots $a_N$ ����� �����, ����
�����~$b_0$ $b_1$~\dots $b_{M-1}$, ��� $b_j$~���� ����������
���������~$a_i$, ������~$j$. �� ���� ������������������ ����� ����������
"������������������ ���������"~$c_0$ $c_1$~\dots $c_{M-1}$, ��� $c_j$---�����
������, ��� ������� ������� ������������ ��� �������~$j$ �~$j-1$. ���
������������������ ������������ ��������
$$
c_j=\cases{
0, & ���� $b_j=c_{(j+1)\bmod M}=0$;\cr
b_j+c_{(j+1)\bmod M}-1 & � ��������� ������.\cr
}
\eqno(44)
$$
�����, ��������, $M=10$, $N=8$
�~$b_0\ldots{}b_9=0\ 3\ 2\ 0\ 1\ 0\ 0\ 0\ 2$;
�����~$c_0\ldots{}c_9=2\ 3\ 1\ 0\ 0\ 0\ 0\ 1\ 2\ 3$, ��� ��� ���� ����
����� ��������� �� �������~2 � �������~1, ���---�� �������~1 � �������~0,
���---�� �������~0 � �������~9 �~�.~�. �����~$b_0+b_1+\cdots+b_{M-1}=N$, �
������� ����� ����, ����������� ��� ������� ���� $N$~������, �����
$$
1+(c_0+c_1+\cdots+c_{M-1})/N.
\eqno (45)
$$
�������, ��� �������~(44) ���������� ���������� �����~$c$ ����� ����� ����,
 �� � ���������������� ��� �����~$N<M$ ������� ����� ������������ ������� (��.~���.~32).

�.~��� �~�.~����� ������������ ��� ���� ��� ����������� ������������~$q_k$
(����������� ����, ���~$c_j=k$) ����� �����������~$p_k$ (����������� ����,
���~$b_j=k$). (��� ����������� �� ������� ��~$j$.) ���,
$$
\eqalign{
q_0&=p_0q_0+p_1q_0+p_0q_1,\cr
q_1&=p_2q_0+p_1q_1+p_0q_2,\cr
q_2&=p_3q_0+p_2q_1+p_1q_2+p_0q_3\cr
}
\eqno(46)
$$
�~�.~�., ���������, ��������, ����������� ����, ���~$c_j=2$,
���� ����������� ����, ���~$b_j+c_{(j+1)\bmod M}=3$.
�����~$B(z)=\sum p_kz_k$ �~$C(z)=\sum q_kz^k$---������������ ������� ���
��������������� ������������� �������������; ���������~(46) ������������ �����������
$$
B(z)C(z)=p_0q_0+(q_0-p_0q_0)z+q_1z^2+\cdots=p_0q_0(1-z)+zC(z).
$$
��� ���~$B(1)=1$, ����� ��������~$B(z)=1+(z-1)D(z)$. ������ ��������, ���
$$
C(z)={p_0q_0\over 1-D(z)}={1-D(1)\over 1-D(z)},
\eqno(47)
$$
%%632
���������~$C(1)=1$. �������������, ������� ����� ����, ����������� ���
�������, � ������������ �~(45) ��������
$$
1+{M\over N}C'(1)=1+{M\over N}{D'(1)\over 1-D(1)}
=1+{M\over 2N}{B''(1)\over 1-B'(1)}.
\eqno(48)
$$
� ���� ������������� � ���������������� ���� ���-������������������� �����
$$
\eqalignno{
p_k &= \hbox{(����������� ����, ��� ��� ��������������~$j$ � ��������
$k$~�����~$a_i$ �����~$j$)}=\cr
&=\perm{N}{k}\left({1\over M}^k\right)\left(1-{1\over M}\right)^{N-k}; &(49)\cr
}
$$
�������
$$
B(z)=\left(1+{z-1\over M}\right)^N, \quad
B'(1)={N\over M},\quad
B''(1)={N(N-1)\over M^2}
\eqno (50)
$$
� ������� ����� ����, ��������~(48), ��������
$$
C_N={1\over2}\left(1+{M-1\over M-N}\right).
\eqno(51)
$$
������� �� ��������, ������ ���� ����� ���������� �� ����������
�������~K? (��.~�~���.~33.)

\section *������������ �������������. �� ������� ���������
������������������� ���� ��� �������� ���������, � ����������� ��������,
����� �� ��� �������� "��������� �� ���������" � ��������� �������� ������.
 ���������� ���������� ���� ������ ��������� ��.~������ [{\sl JACM,\/}
{\bf 19} (1972), 569--575]:
������ ���������� "���-������"~$h(K)$ ����� ���������� ������ ����~$K$ �
����� ������������ ���������~$\set{0, 1,~\ldots, M-1}$, ��������������
����� ������������������ ���� ��� �������������~$K$. ������ ��
$M!$~������������ ������������� �����������, � ��������������, ���
���������� ���-������� �������� ������ ������������ � ���� ������������.
������ �������� ���: "��� ����� ��������� ������������� �����������,
����� �������� ��������� ��������������, �.~�.~����� ���������������
������� ����� ����~$C_N$ ���~$C'_N$ ���� �����������?"

����, ��������, ��������� ������ ������������ �����������~$1/M!$, ��,
��� ����� ������, ��������� � �������� ���������  \emph{������������
�����������} (��.~(32), (34)). ������ ������
�������� ������ �~$M=4$ �~$N=2$, � �������~$C'_N$ ������~${5\over3}$
(��� �������� ���������� ��� ����������� �����������). �� ��������
��������� ����������� ���� ��������� ����� �������������:
%%633
$$
\matrix{
\hbox{������������} & \hbox{�����������} & \hbox{������������} & \hbox{�����������}\cr
0\ 1\ 2\ 3 &   (1+2\epsilon)/6  &1\ 0\ 3\ 2 & (1+2\epsilon)/6\cr
2\ 0\ 1\ 3 &   (1- \epsilon)/6  &2\ 1\ 0\ 3 & (1- \epsilon)/6\cr
3\ 0\ 1\ 2 &   (1- \epsilon)/6  &3\ 1\ 0\ 2 & (1- \epsilon)/6\cr
}
\eqno(52)
$$
����� ������, �� ������ ���� �� ������������~2 �~3, � �� ������---0 �~1.
������� ����� ����, ����������� ��� �������
�������� ��������, �����������
������~${5\over3}-{1\over9}\varepsilon+O(\varepsilon^2)$, ���
������~${5\over3}$ ��� ����� �������������~$\varepsilon$.

������ ��� ����� �������������
������������~$C'_1={23\over18}+O(\varepsilon)$,
� ��� ������~${5\over4}$ (��������~$C'_1$ ��� ������������ �����������).
������ �������, ��� ��� ����� ������� ������������ ������������, �����,
���~$C'_N<(M+1)/(M+1-N)$ ��� ���������~$N$, ������ ����������~$n<N$, �����,
 ���~$C'_n > (M+1)/(M+1-n)$;
������ ��� ����� ��������� ����������� �����������.

� ���������������� � �������� ���� ����� �������� ��~$C'_N$, � ����� ����
��� \emph{�������} ������~$C_N$. ������������~(52) �� ���� ���������~$C_N$
�� ��� �����~$N$, � ������� ������ �������� ������������, ��� �������
������������ ������������� ������������ �� ����� �������~$C_N$ ������
"������������" ��������~$((M+1)/N) (H_{M+1}-H_{M+1-N})$.

��� �����������, ��� ����������� ����� ������ �������� ������� �������
������, ��� �������� ������ ������������ ����������� ����� �������
���������; �� �� ������� ����������� ������ ������������ �����������~$1/M!$.
��������, ��������� ������������� ���~$M=4$ ������������ ������������ �����������:
$$
\matrix{
\hbox{������������} & \hbox{�����������} & \hbox{������������} & \hbox{�����������}\cr
0\ 1\ 2\ 3 &   1/6  &0\ 2\ 1\ 3 & 1/12\cr
1\ 2\ 3\ 0 &   1/6  &1\ 3\ 2\ 0 & 1/12\cr
2\ 3\ 0\ 1 &   1/6  &2\ 0\ 3\ 1 & 1/12\cr
}
\eqno(53)
$$
(��������� 16~������������� ������������� ������� �����������).

��������� ������� ������������� \emph{���} ������������� ������������,
������� ���� ��������� ������������ �����������:

\proclaim �������~U. ������������ ������������� ������������ ������� ���
$\perm{M}{N}$~������������ ������� � ��������� ����� ����� N~�������
��������������� ���~$0<N<M$ ����� � ������ �����, �����
%%634
����� ������������, ����������� ���� �������������, ������ $N$~���������
������� ����������� ������� $N\hbox{-�����������}$ ���������,
�����~$1\big/\perm{M}{N}$ ��� ����~$N$ � ���� $N\hbox{-����������}$ ��������.

��������, ����� ������������, ����������� ������ ��
$3!(M-3)!$~������������, ������������ � �����~$\set{0, 1,2}$, ������� �
��������� �������, ������ ����������~$1\big/\perm{M}{3}=3!(M-3)!/M!$.
��������, ��� (53)~������������� ������� �������.

\proof �����~$A\le \set{0, 1,~\ldots, M-1}$, � �����~$\Pi(A)$ ����
��������� ���� ������������, ������ $\Abs{A}$~��������� �������
�����������~$A$. ����� ������������, ����������� ����  �������������,
��������� �����~$S(A)$. ��������~$P_k(A)$ ��������� ����������� ����,
��� ������ $\Abs{A}$~������, ����������� ���������� �������� ���������,
������ ������, ������������ ����������~$A$, � ��� ��������� �������
��������� ����� $k$~����;
�������~$P(A)=P_1(A)+P_2(A)+\cdots$. �������������� ���������� ���������
��~$N\ge 1$; ��������������, ���
$$
P(A)=S(A)=1\bigg/\perm{M}{n}
$$
��� ���� ��������~$A$ �~$\Abs{A}=n<N$. ����� $B$ ����
$N\hbox{-����������}$ ���������. �����
$$
P_k(B)=\sum_{\scriptstyle A\subseteq B \atop \scriptstyle \Abs{A}=k }
\sum_{\pi\in\Pi(A)}\Pr(\pi)P(B\setminus\set{\pi_k}),
$$
��� $\Pr(\pi)$~���� �����������, ����������� ������������~$\pi$, a
 $\pi_k$---�� $k\hbox{-�}$~�������. � ���� ������������ �������������
$$
P_k(B)=\sum_{\scriptstyle A\subseteq B \atop \scriptstyle\Abs{A}=k}{1\over\perm{M}{N-1}}
\sum_{\pi\in\Pi(A)}\Pr(\pi),
$$
��� ���������
$$
\perm{N}{k}\bigg/\perm{M}{N-1}\perm{M}{k},
\rem{���� $k<N$;}
$$
�������������,
$$
P(B)={1\over\perm{M}{N-1}}
\left(S(B)+\sum_{1\le k<N}{\perm{N}{k}\over\perm{M}{k}}\right),
$$
%%635
� ��� ���������~$1\big/\perm{M}{N}$ ����� � ������ �����, �����
$S(B)$~����� ��������� ��������.
\proofend

\section ������� �����. ������ ����������� ������ �������� ��� ��������
������ �� ������������ ����������� � ������ �������� ���� ������ ���
���������. ��� ����� ����������, ��� � � �.~6.2.4, �� ����� ��������������
����� ��������� � �����, � ��� ������ ������ �� ����� ����������:

\enumerate
\li ������� ��������� ������ ������� �� ���������� ���-�������, ������
��� �������� �� ������ ����������� ����� ������ ��������� ���������������
�������, ������� ��� ���������� ������.

\li ������ ������ ������������� � �����, ����� �� ���� ��� ��������� ��
������� ������ ��������� �������.
\enumend

������ ���� ������� �� $M$~������ �� $b$~������� � ������. �������� ��
�������� �����������, ���� �� �������� ����� $b$~������ � ������
���-�������. ��-��������, ���������� ����� ��������� ��� ������� �
���������� ��������.

A) {\sl ���������� �������.\/} ���� � ���� � ��� �� ���� �������� ������
$b$~�������, � ����� ������� ����� ����� �������� ������ ��
"�������������" ������. ������������� ������ �������� � �����������
�������. ������ ��� ������ ����� ����� � ������� ������������, ��� ���
��������� ������������ ���� ������������; ����� �������, �������������
������ ������ ����������� ���� � ������, � �� $(b+k)\hbox{-�}$~������
������ �������� $1+k$~��������� � �������� ����������. ����� �������
�������� ��������� ������������ �� ������ "��������" ��������� �����,
����� ����������� ��������� ����������� � ������ � ���� �� ��������.

���� ����� ����� ��������� ������������ ������� �������������, �����
������������ ������������� ���������� ����, � ������� ����� ������
����������� ����� �������. � ����.~2 �~3 ���������� ������� �����
��������� ��� ������� �� ������������  ����������
$$
\alpha=N/Mb,
\eqno(54)
$$
��� $\alpha$~����������� � $�, N\to\infty$. ��� �� �������, ��
���~$\alpha=1$ ��������������� ����� ��������� � ������ ���������� ������
������ � ������~$b$.

B) {\sl ������������ �������.\/} ������ ��������� ���������
������� ������������, ����� ������������ ��������~C ��� ������ � ��������
�������. ��� �� ����������� ����� ����� ������� � ������������ ������
���������� ������������. ��������
%%636
\htable{������� 2}%
{������� ����� ��������� ��� ��������� ������ � ������� ���������� �������}%
{\hfill#\bskip&&\hfill\bskip$#$\bskip\hfill\cr
\noalign{\hrule}
 &\multispan{10}\hfill\hbox{����������� ����������, $\alpha$}\hfill\cr
������ �����~$b$
&10\%&20\%&30\%&40\%&50\%&60\%&70\%&80\%&90\%&95\%\cr
\noalign{\hrule}
  1&1.0048&1.0187&1.0408&1.0703&1.1065&1.1488&1.197&1.249&1.307&1.3\cr
 2&1.0012&1.0088&1.0269&1.0581&1.1036&1.1638&1.238&1.327&1.428&1.5\cr
 3&1.0003&1.0038&1.0162&1.0433&1.0898&1.1588&1.252&1.369&1.509&1.6\cr
 4&1.0001&1.0016&1.0095&1.0314&1.0751&1.1476&1.253&1.394&1.571&1.7\cr
 5&1.0000&1.0007&1.0056&1.0225&1.0619&1.1346&1.249&1.410&1.620&1.7\cr
10&1.0000&1.0000&1.0004&1.0041&1.0222&1.0773&1.201&1.426&1.773&2.0\cr
20&1.0000&1.0000&1.0000&1.0001&1.0028&1.0234&1.113&1.367&1.898&2.3\cr
50&1.0000&1.0000&1.0000&1.0000&1.0000&1.0007&1.018&1.182&1.920&2.7\cr
\noalign{\hrule}}%
���� �����, ������ ���� �������� ������� ����� ��������� �������; ����
��������� �� ������, ���� ���� ���� ������� ���������� �~0. �����
������������ "���������� ���������" ��� ������������� ������������
(��.~� ���.~2.5-6), ����� � ��������� ������� �� ����������� ������������
��������� ����� ������������. ��������, ������� ����� ��������� ������
���������� ������������ ��� ������ �� ������ �������� ��������� �����.

���� ����� ��� �� ���������������, �� �� ������ ��������� ������ ��������.

\htable{������� 3}%
{������� ����� ��������� ��� ������� ������ � ������� ���������� �������}%
{\hfill#\bskip&&\hfill\bskip$#$\bskip\hfill\cr
\noalign{\hrule}
 &\multispan{10}\hfill\hbox{����������� ����������, $\alpha$}\hfill\cr
������ �����~$b$
&10\%&20\%&30\%&40\%&50\%&60\%&70\%&80\%&90\%&95\%\cr
\noalign{\hrule}
 1&1.0500&1.1000&1.1500&1.2000&1.2500&1.3000&1.350&1.400&1.450&1.5\cr
 2&1.0063&1.0242&1.0520&1.0883&1.1321&1.1823&1.238&1.299&1.364&1.4\cr
 3&1.0010&1.0071&1.0216&1.0458&1.0806&1.1259&1.181&1.246&1.319&1.4\cr
 4&1.0002&1.0023&1.0097&1.0257&1.0527&1.0922&1.145&1.211&1.290&1.3\cr
 5&1.0000&1.0008&1.0046&1.0151&1.0358&1.0699&1.119&1.186&1.286&1.3\cr
10&1.0000&1.0000&1.0002&1.0015&1.0070&1.0226&1.056&1.115&1.206&1.3\cr
20&1.0000&1.0000&1.0000&1.0000&1.0005&1.0038&1.018&1.059&1.150&1.2\cr
50&1.0000&1.0000&1.0000&1.0000&1.0000&1.0000&1.001&1.015&1.083&1.2\cr
\noalign{\hrule}}

C)~{\sl �������� ���������.\/} ����� �������� � ��� ������, ���������
"��������" �����. ��� �������� ������ �������� �����������, ��������,
����� ����������, ��� ��������~$c$ ����� ������� ���, ����� ��������������
������� �������� ����� ����������������� �����������. ����������� ����
������������ ������������� ������ ��������� ����������� ����� ����
�������� ��� ����� ������� ������; ��� ����������, ���
%%637
\htable{������� 4}%
{������� ����� ��������� ��� ������� ������ � ������� ��������� �����������}%
{\hfill#\bskip&&\hfill\bskip$#$\bskip\hfill\cr
\noalign{\hrule}
 &\multispan{10}\hfill\hbox{����������� ����������, $\alpha$}\hfill\cr
������ �����~$b$
&10\%&20\%&30\%&40\%&50\%&60\%&70\%&80\%&90\%&95\%\cr
\noalign{\hrule}
 1&1.0556&1.1250&1.2143&1.3333&1.5000&1.7500&2.167&3.000&5.500&10.5\cr
 2&1.0062&1.0242&1.0553&1.1033&1.1767&1.2930&1.494&1.903&3.147&5.6\cr
 3&1.0009&1.0066&1.0201&1.0450&1.0872&1.1584&1.286&1.554&2.378&4.0\cr
 4&1.0001&1.0021&1.0085&1.0227&1.0497&1.0984&1.190&1.386&2.000&3.2\cr
 5&1.0000&1.0007&1.0039&1.0124&1.0307&1.0661&1.136&1.289&1.777&2.7\cr
10&1.0000&1.0000&1.0001&1.0011&1.0047&1.0154&1.042&1.110&1.345&1.8\cr
20&1.0000&1.0000&1.0000&1.0000&1.0003&1.0020&1.010&1.036&1.144&1.4\cr
50&1.0000&1.0000&1.0000&1.0000&1.0000&1.0000&1.001&1.005&1.040&1.1\cr
\noalign{\hrule}}%
�������� ����������� ������������� �����������������, ���� ������� ��
������� �����. �� ����.~4 �����, ��� ���~$\alpha=90\%$ �~$b=50$ �������
����� ��������� ��� �������� ������ ���������� ����~$1.04$. ��� ����
\emph{�����,} ��� $1.08$~���������, ������� ��������� � ������ �������~(A)
� ��� �� �������� �����!

������ �������~(A) �~(C) ������ ��������� � � �������������� �����
������; �� �������� ����� ���� ����������, ��������� ����������
������������ ��������� ���.~49 �~55. ������� �������� ��� �������, �����
��������� � $Q\hbox{-���������}$ �������~$K$:
$$
R(\alpha, n)={n\over n+1}+{n^2\alpha\over (n+1)(n+2)}
+{n^3\alpha^2\over (n+1)(n+2)(n+3)}+\cdots
\eqno(55)
$$
�
$$
\eqalignno{
t_n(\alpha)&=e^{-n\alpha}\left({(\alpha n)^n \over (n+1)!}
+2{(\alpha n)^{n+1}\over (n+2)!}+3{(\alpha n)^{n+2}\over (n+3)!}+\cdots\right)=\cr
&={e^{-n\alpha} n^n \alpha^n \over n!} (1-(1-\alpha)R(\alpha, n)). & (56)\cr
}
$$
� ������� ���� ������� ����� �������� ������� ����� ���������,
����������� ��� ��������� ������ � ������� ������~(A)
$$
C'_N=1+\alpha b t_b(\alpha)+O\left({1\over M})\right)
\eqno(57)
$$
($M, N\to\infty$), � ��������������� ����� ��� �������
������
$$
C_N=1+((e^{-b\alpha}
b^b\alpha^b)/2b!)(2+(\alpha-1)b+(\alpha^2+(\alpha-1)^2(b-1))\times
R(\alpha, b))+O(1/M).
\eqno (58)
$$
��� ����������� � ������� ����.~2 �~3.

��������� ����� �������~(A) ������� ��������� ������� ������������,
������� ������� ��������� ���������� ������������. �� ������� �����
����������~$M(C_n'-1)=N t_b(\alpha)$, ��� ���
%%638
$C'_N-1$~���� ����� ������������ � ����� ������ ������. ������� ����.~2
����� ������������ ��� ���������� ������� ���� �������. ���
�������������~$\alpha$ �~$M\to\infty$ ������������������ ���������� ������
����� ������������ ����� �������������� ���������������~$\sqrt{M}$.

��������������� ��������~$C'_N$ �~$C_N$ ��������� � ���.~53, �� ���
����������� �� ����� ������ ��� �����~$b$ ��� �������~$\alpha$; �
�������, ��� ���~$R(\alpha, n)$ �������� ����� ������ ���� ���
�������~$\alpha$, ��� ��� ����� ��� �������� ����� ����������� �������
���������. ��������~$C_N$ �~$C'_N$ ����������� ���~$\alpha=1$ � ����������
���~$b\to\infty$ ���
$$
\eqalignno{
\max C'_N &=1+{e^{-b}b^{b+1}\over b!}=\sqrt{{b\over 2\pi}}+1+O(b^{-1/2}), &(59)\cr
\max C_N &=1+{e^{-b}b^b\over 2b!} (R(b)+1)={5\over4}+\sqrt{{2\over 9\pi
b}}+O(b^{-1}) &(60) \cr
}
$$
�������� ����������� ��������� � ������� �������~$R(n)=R(1,n)-1$,
������������ � �.~1.2.11.3.

������� ����� ��������� ��� ������� ������ � ������� \emph{���������}
����������� ����� ����������� ������� ���:
$$
C_N\approx 1+t_b(\alpha)+t_{2b}(\alpha)+t_{3b}(\alpha)+\ldots\,.
\eqno(61)
$$
��� ����������� ����� �������� ��������� �������: ������� ����� ���������
��� ������ ���� $N$~������ �����~$NC_N$, � ��� ����~$N+T_1+T_2+\ldots$,
��� $T_k$~���������� ������� ����� ������, ����� ������� ������� �����
$k$~���������. �������~P ������, ���, �� �������~$C_N$, ����� �����
��������� � ����� �������; ������ �������, ��� $T_k$~����� �������� �����
������������� �������, ������� ������� �� ��� ������������� ������
������� � $M/k$~������� �������~$kb$, �.~�.~$T_k=Nt_{kb}(\alpha)$, ��� �
������������. ���������� ��������� �������~(61) ��������� � ���.~55.

�������� ���������� ������������ ����������� �� ���������� �������
���������� ������ ��� ������ �����
[{\sl Proc. ACM Nat'1 Conf.,\/} {\bf 24} (1969), 539--549]. ������
�������� ��������� �������� ��������; � ��� �����������, ��� ����������
������������� ������� ����������� �������������, ���� ���� ������ ��������
������ ������� � �������� ��� �������������� �������. ����������� ������
���� ��������, ����������� ��������� ������� � ��~���������.

\section ��������� �������. ����, �� ������� ����� ������� ������;
��� �� ��� ����������������� ��� ������ ���������� �� ���;
��� ����������� ����������? ������ � ���������� ������ ������� ���, ���
��� �������� �� ������ ��� ������ ������ ������, ������ ���������
�����������, �������, ��������
%%639
\picture{���.~44. ��������� ������� ���������� ��������: ����������
�������� �������� ����� ���� ���~$M\to\infty$. (�)---��������� �����
(����������� ����������~$\alpha=N/M$);
(b)---������� �����. ($L$---�������� �����������=��������~L; $U2$---���������
����������� �� ��������� �����������; $U$---�����������
�����������$\approx$��������~D; $B$---��������~D � ���������� ������;
$C$---����� ������� �� ����������=��������~C; $S$---���������� �������;
$SO$---���������� ������� � �������������� ��������.)
}
%%640
�����, ���� �� �������������� � ���������� ������� ������ � ������
���������� ������.

�� ���.~44 �������� ���������� ������������ �������. �����, ��� ���������
������� ���������� �������� �������� � ���������� ����� ����. �� ��� ���
�� ���, ��� ��� � ���������� ������ �������� ����� �����, ��� �������
���������� �� ������� ������ (��.~���.~42). ��� �������� ����������� ����,
 ��� � ������ �������, ���������� ��������� � �������, ���� ���� �����
�����. ����� ����, ������ �������, ��� ���� �������� ����������� ������ ��
������ �� �������: ���� ������� ��������� �� 90\%, ��������~L ������� �
������� ����� $5.5$~����� ��� ����������� ���������� ��������. (������
������� ����� ���� ��� ������� \emph{������} �������� � �������
���������~L �����~$50.5$, ���� ������� ����� �� 90\%.)

�� ���.~44 �����, ��� ������ ������� ������ �������� � ����� ������ �����
����, �� ����������� � �������������� ������������ ������ ��� ����� ������
������ (��� ��������� ������� �������) ������ ����� ���������������
�������� ���������. ��������, ���� ����� ������� ����� ����� �������� �
��������� �� 500~��������� � �������� � �������� ���������� ��
1000~���������, �� ���������, ��������, ����������������, ��� ���
������������ ����������� ����� ����� 500~������� � �������� �������� � ���
���� ������ ������. � ������ �������, ����� � ���� ������� ������� ���
�� ������� ������������ ��� ���� ������ ��������� ���������� ���������
(��.~�~���.~65).

��� ����������� ������ ����������� � ������� ����������� ������,
���������� � ���� �����? ��������� �� �� ��������, ����� ����������, ���
������ ����������� �����, ���� ����� ������� ������, ��������� �������
����� ������ ��� ������� ����������� �������� ������������
���~$N\to\infty$ � ������, ����� ������� �� ���������� ������� �����������.
 ��������, ���������~L ����� ���� 55~������ ������� ��� �������� ������ �
�������, ����������� ��~90\%; ��� ������� ����� ������� �� ��������� ���
\MIX-�������� ��������� ������ (��.~���.~6.2.1-24), ����~$N$ ������~600
��� ����� ����, � ������� �� ��� ���������� ���� 11\%~������������
������. ����� ����, �������� ����� ������� ���� ��� ������������� ������,
 � �� ����� ��� ���������� ������� ��������� ����������� ��������� �������.

�� ����� ����� �������� ���������~L � �������� ������ �� ������,
������������ ������������ �������. ���������~L ���~$\alpha=0.9$ �������
���������~6.2.2T, ���� $N$~��������� ��������������~90, � �������
���������~6.3D (���.~6.3-9), ���� $N$~��������� ��������~75.

%%641
������ ���� ����� ���� ����� � ������ �������� ������ ������ ���������� �
���������� �� ���� ����������� ������, � ������ ��������~D � ����������
������. �� ��������� ��������� $N$~������� � ������� �������~$M=N+1$ � ��������
����� ������ � ������� �� $2{1\over2}$~�����. �� ����� ���������������
������������ ��� ����� ������ �~�.~�.; ������ ��������� ����� �����
������ ���������---�� ��������� ����� ${1\over2}N$~����.

����� �������, ����������� ����� ���� ������������. � ������ �������,
����� � ���������� �������� ��� �� �������� ��������� ����� ������� ��
���� ������ �������.

\medskip
a)~����� ���������� ������ � ���������� ������� �� ����� ���� ��, ���
������� ����� ��� ���. ������ ������, ���������� �� ����������, ������
���� ������ ����������; ��� ��������� ����� ���������� $\hbox{����} \le K$
��� ���������� $\hbox{����}\ge K$ , ��� ����� �� ������ �����������
(��������, ��� ������������ �������� ������� �� ���������� �������).
��� �� ������ ����� ������������ � ��� ���������� ���� ������, �������
\emph{�����} ����� ��������� ����������~$K$ �~$K'$. �����, ���������
������ �� ������~\S~6.2 ��������� ����� ����������� ���������� ������� �
������������ ������� ��� ����������� ����������, � ��� ������ ������ �����.

\medskip
b)~����� �������� ������ ������������ ������ ��� ���������� ������; ���
���-������� ����� ������� ������������ ������� ������, � ������ �� ��
������ ����. ���� ������� ������� ����� ������, �� ����� ����������������
��������� �� ������ ������� ��� �� ������ ������������� ���, ��
���� ������� ���� �����, ������� ������������! ��� ������������ ����������
�������, ��������, ����� ����� "������������" ��, �.~�.~������� ������
������������ � �������� ���-�������, � ����� �������� ������ � �������
�������. �.~������
[{\sl Comp. Bulletin,\/} {\bf 11} (1968), 297--300] ��������� ������������
�������, ���� ����������� ���������� ���������~$\alpha$, �������~$M$
��~$d_0 M$; � ������� ������������ ���� ������� � ������������� ������
����� ���������� ����������� �����, ����� ������������� ���������� �������
���������� ������ � ��� �� ��������, � ��� ����� ������� ��������
����������~$\alpha_0$ �~$d_0$. (�������, ��� ����� ������� �������� ��
����������� ������������ � �� ��������� � �������������, ������ ���
�������������~$M$ � ��������~$N$ ����� ������ ����������
����������������~$N$.) ��������, ��������� ������ �� �������� �� ������ ��
��������� ���������� ���������������; ������� ������ �� ������, ��� ���
����������. ��� ������ � ����������� ������� �����,
%% 642
�� ���� �����������, ������������ ����� �� ������ ��� �������� �����
�� ������ ������ �������� ������� ���������� ������, ���������� ��������
����� �������� ����� ��� ������ ����������� �����.

\medskip
c)~�������, ��� ������������� ������� ����������� ����� ����� ������ �
������ ������������, ��� ��� ���������� ���� � �������, � ��������� ������
������ ������! ��� � � �������� � ��������� ��������� �����, �� �� �����
���� ��������� ���������� � ���, ��� ��� ���������� � ������ ���������
������ ���-������� ����� �������� �����������������. ������� ����������
������ �� ������ �������� ��� ������ � �������� �������� �������, ��������
��� ���������� ��������� ����������, ��������� �� �����
���������� ������������ �����. ��������� �����������������
������ (�.~6.2.3 �~6.2.4) ������� ����������, ���� ��� �����
��������������� ������� ������� ������� ������.

\section �������. ��-��������, ������� ���� ����������� �������� �.~���. �
������ 1953~�., ��������� ���� �� ���������� ���������� �����~IBM, ��
��������� ������������ ����� �������; ��� ������� ����� ����� �� ������
���������� �� ��������� �������� �������. �� ������ �� �������������
������������� ��� �������� ������ ������, ���������� �����
������ ��������. ������ ����� ����� �.~��� ��������� ������ ���� �������
������ � ��������� ����� ��������� ������������ � ������� "�������������
�������"; ��������, ��� ������������ ���������� ����� 2748~������
�������� �� ��������� ����~274; ���� � �� ������������, ������������
��������� ����~27 �~�.~�. ��������������, ��� ���� 10000~��������� ������,
1000~���������, 100~��������� �~�.~�. ������������� ������������ �����
���-������� ���� �������-���������;
��������, ������������ �� ������~10 ���� �������� ���� �����, ���
���~31415926 ��������� ��~4548.

�������� � ��� �� ����� ���� ����������� ��������� � ������ ������
����������� �����~IBM: ���� �����, ����� ����, �.~��������� � ������
�������, ��������� ���������� ��������� ��� IBM~701. ��� ����������
�������� �������� ����� ��������� ���� �������� ��������� � ��������
������������.

� �������� ������ ����������� ������� ���� ������� ��������� ����
[{\sl Computers and Automation,\/} {\bf 5}, 12 (December 1956), 6--9].
������ �� ������� �������� ���� ������� �� ������� ����� � �������������
������� � �������� ���-������. � ������ ���� ����������� ����� �������,
������ �������� ��������� � ��� ���. �.~�.~����� � 1957~�. ����������
������ �������� �������� ��������� [{\sl ��� ����,\/} {\bf 118} (1958),
427--430];
%%643
�� ����������� ������������ ���������� � ����� ����, �����������
�����������, ��� ���~$N/M<2/3$ ������� ����� ���� ��� �������� ������ $<2$.

������������ ������ �.~���������
[{\sl IBM J.~Research \& Development,\/} {\bf 1} (1957), 130--146] ����
������ ������ ������� �� ������� ������ � ������� ������. ��������
��������� �������� ��������� � ����� ������, ���������������
�������������� ������������ ����������� � ������
�������������� �������������� ������ � ��������� �������� ��������
��������� ��� ��������� �������� ������, �������� ���������
�������������, ����������� ��� �������� ���������. ������ ������������
����� �������� ������ ������ ����� ����������� ������ �������� [{\sl IBM
Systems J.,\/} {\bf 2} (1963), 86--111]; �� �������� ������������ ������
���-�������.

� ����� ������� �������� ����������� ���� ������������ ����� �����
�������� ���������, ��������� � ����������, ���� ����������� ��������
���������� ���� ����������� ������ �����, ���������� �� �������������
��������� ����������� � ������� ����������� ���-������� (��.~���.~48). �
������� ���������� ��������� ��� ����������� ����� �������������� �����
������, �� � ��� ���� �� ���� ������������ ���-������ �����. ����� ������
������ ������� ��������� ������� ������� ����� �������� [{\sl CACM,\/}
{\bf 11} (1968), 38--44], � ������� �� ���� ���� ���������� �����������
(�� ��������� �����������). ������ ������� ��������� ������, ��������� �
�������� ���������~D � ��� ������������������.

��������� ��������, ��� ����� "�����������" ("hashing") � ��� ��������
��������, ��������, �� ���������� � ������ �� ����� 60-� �����, ���� �
���� ������� � ������ ������ ����� ��� ��� ����� ������������ ��������.
��-��������, ������� ��� ����� ���� ������������ � ����� ����������
[Digital Computers System Principles (New York, 1967), 152]. �� ��������
60~����������, ����������� � 1953--1967~��., ��������� �������
��� ��������� ������� ���������, ����� "�����������" ����������� ����
�������---� ���������������� ��������� �����, ������������ �.~����������
(1961~�.). ��� �� ����������, ������ "����������" (to hash) � ��������
60-� ����� ���� ����������� �������� ��� �������������� �����, ����
������������ ����� ����������� ����� � ������ ����� �� ����������� �� 1967~�.!

\excercises
\ex[20] �����������, ���   ����� 1, 2, 3 �����~$K$ �������� ���� �����,
�������~30. � ����� �������� ��������� ����������~|rI1|, �����
����������� ����������~|9H| � ����.~1?

\ex[20] ������� �������� ��������� ���������� �����, ������� �����
�������� � ����.~1 ��� ��������� ���������.

%%644
\ex[23] ���������, ������ ��������� � ����.~1 ������ �������� ��
����� �������, ������������ �� ��������� ���� ����������:
\medskip
\centerline{|LD1  K(1:1)| ���~|LD1N  K(1:1)|}
\centerline{|LD2  K(2:2)| ���~|LD2N  K(2:2)|}
\centerline{
\vbox{
 \hbox{\strut|INC1  $a$, 2|}
 \hbox{\strut|LD2   K(3:3)|}
 \hbox{\strut|J2Z   9F|}
}}
\medskip
�� ��� ����� ���������~$a$, ��������, ��� ������ ����� �� ����� �����
���������� ���-������.

\ex[�30] ������� ������� ����� ���������� �� ���������, ����� �
������������ $>{1\over2}$ ������� \emph{����,} ������� ���� � ��� ��
���� ��������?

\ex[15] ������ ������ ����� ���������� � ��������, ��������� ����������
������ \MIX, � ����� ��� ������ ������ �������� ������� �������� ���
�������� ���� ���������� ������������� ���������. ����� ���� ����
���������� ������� ��������. �� ����� ������������ ���������� �������
�~$M=100$ � ������� ���-�������~$h(K)=\hbox{������� ����� ����~$K$}$.
������ �� ���?

\ex[15] ������� �� �������� ������ ��� ���������� �~(3) ��~|LDA K|;
|ENTX 0|?

\ex[��30] \exhead(�������������� �����������.) ���� ����������
����������---����������� ���������� �����������~$P(x)$ ����~(10), �������
����������� $n\hbox{-�������}$ ����� � $m\hbox{-�������}$ ������ � ���
���� ������ �����, ������������ �� ����� ��� $t$~������, ������� ������
������. �� �������� ���������~$n$, $t\le n$, � ������ �����~$k$, ������,
���~$n$ �����~$2^k-1$, �� �������� ���������, ������� �� ��������
�������� ��������~$n$, $t$ �~$k$. (������, ���� ��� ����������,
$n$~�������������, ������� $k$~����� ������� ���������� �����.)

����� $S$---����������� ��������� ����� �����, �����,
���~$\set{1,2,~\ldots, t}\subseteq S$ �~$(2j) \bmod n \in S$ ���
����~$j\in S$. ��������, ����~$n=15$, $k=4$, $t=6$, �����~$S=\set{1, 2, 3,
4, 5, 6, 8, 10, 12, 9}$. ��������� ������ ���������~$P(x)= \prod_{j\in S}
(x-\alpha^j)$, ��� $\alpha$~���� ������� �������~$n$ ���������
����~$GF(2^k)$, � ������������~$P(x)$ ����������� � ���� ����. �������~$m$
����������~$P(x)$ ����� ����� ��������� �~$S$.
����~$\alpha^j$---������~$P(x)$, �� �~$\alpha^2j$---������; ������ �������,
��� ������������~$P(x)$ ������������� �����������~$p^2_i=p_i$, �.~�.~���
�����~0 ���~1.

��������, ��� ����~$R(x)=r_{n-1}x^{n-1}+\cdots+r_1x+r_0$---���������
��������� �� ������~2 � �� ����� ��� $t$~���������� ��������������,
��~$R(x)$ �� ������~$P(x)$ �� ������~2. [������ �������, ���
��������������� ���-������� ����� ���� ��������� �������.]

\ex[�34] \exhead(������� � ���� ������.) �����~$\theta$---��������������
�����, ������� �����~0 �~1, ������������� �������� � ���� ����������
����������� ����� (����������� �.~4.5.3) ����~$\theta=/a_1, a_2, a_3,
~\ldots/$. �����~$q_0=0$, $p_0=1$, $q_1=1$, $p_1=0$
�~$q_{k+1}=a_kq_k+q_{k-1}$, $p_{k+1}=a_kp_k+p_{k-1}$ ���~$k\ge1$.
���������~$x \bmod 1=x-\floor{x}$ �����~$\{x\}$, �~$x-\ceil{x}+1$
�����~$\{x\}^+$. ����� ���������� ������� � ��� �������, ��� ���
���������� ��� ���������������� �������� � ��������~$[0, 1]$
�����~$\{\theta\}$, $\{2\theta\}$, $\{3\theta\}$,~\dots, ��� ��� ������
������� ������ ����� ����� �����~0, ������---�����~1 �~�.~�. ��������, ���
��� ��������� ����������� �����.
����� ������ ��������� �����~$s$ �����~$\{t\theta\}$,
���~$t=rq_k+q_{k-1}$, $0\le r<a_k$, $k$~�����, a~$0\le s <q_k$,
������ �����~$\{s\theta\}$, � ������---�����~$\{(s+t)\theta\}^+$.
����� ������ ��������� �����~$s$ �����~$1-\{t\theta\}$,
���~$t=rq_k+q_{k-1}$, $0 \le r < a_k$, $k$~������� �~$0 \le s < q_k$,
������ �����~$\{(s+t)\theta\}$, � ������---�����~$\{s\theta\}^+$.
����� ����������� ����� ����� ������������ ������� ����������� �
����~$n=rq_k+q_{k-1}+s$ ���~$k\ge 1$, $1 \le r \le a_k$, $0 \le s < q_k$.
� ���� ������������ ����� �������� �����~$\{n\theta\}$ ������� $n$~����������:
%%645
������ $s$~���������� (� ��������~0,~\dots, $s-1$) �����~$\{(-1)^k(rq_k+q_{k-1})\theta\}$;
������ $n-q_k$~���������� (� ��������~0,~\dots, $n-q_k-1$) �����~$\{(-1)^k q_k\theta\}$;
��������� $q_k-s$~���������� (� ��������~$s$,~\dots, $q_k-1$) �����~$\{(-1)^k((r-1)q_k+q_{k-1})\theta\}$.

�������� �������~$\{n\theta\}$ ��������� �������� �����~$s$ ����������
���� � ����������� ��� � �������� �����~$s$ ������� ���� � ��������
�����~$n-q_k$ ������� ����.

\ex[M30] �������~S ����������, ��� ��� ���������������� ��������
�����~$\{\theta\}$, $\{2\theta\}$,~\dots � ��������~$[0, 1]$ ������ �����
����� ��������� ���� ��
���������� ��������� ����������. ���� ��������~$[a, c]$ ������ �����
������� �� ���
�����~$[a, b]$, $[b, c]$, �� ������� ��� \dfn{������ ����������,} �����
���� �� ������ ����� ��� ����� ������� ������, �.~�.~����� $b-a>2(c-b)$
���~$c-b>2(b-a)$.

��������, ��� ����~$\theta\ne \phi^{-1}$ ���~$\theta\ne\phi^{-2}$, �� ���
���������~$n$ �����~$\{n\theta\}$ ���� ������ ���������; ����
��~$\theta=\phi^{-1}$ ���~$\theta=\phi^{-2}$, �� ������ ��������� �� ����������.

\ex[�43] (�.~������.) �������� ��� ������������ ���������
\emph{������������� � $3d$~������:} ����~$\theta$, $\alpha_1$,~\dots,
$\alpha_d$--- ������������ �����, ������~$\alpha_1=0$, ����~$n_1$,~\dots,
$n_d$---����������� ����� � ���� �����~$\{n\theta+\alpha_i\}$ ����������� �
��������~$[0, 1]$ ���~$0\le n < n_i$, $1\le i\le d$, ��
$n_1+\cdots+n_d$~������������ ���������� (��������, ������) ����� �� �����
$3d$~��������� ����.

\ex[16] ������ ������� ������ ������������ ���� ��������� ������� ��
������~12--13 ���������~C �������� ������� �� ��������~10--11?

\rex[21] ��������, ��� ����� ��� ���������� ���������~C, ��� ��
���������� ����� ��������� ���� ���� ���������� ��������� ��������.
�������� ������� ������ ���������������� � �������������� ��������.

\ex[24] \exhead(����������� �����.) ����� $h(K)$---���-�������, a
$g(K)$---����� ������� ��~$K$, ���, ����~$h(K)$ �~$g(K)$, ����� �����~$K$.
��������, ��� ����������� �������� ����� ��������~$h(K)=K \bmod M$
�~$g(K)=\floor{K/M}$; � ����������������� ����������� � ��������~$h(K)$
����� ����� ������� �������~$(AK/w)\bmod 1$, � � ��������~$g(K)$---���������
�������.

��������, ��� ��� ������������� ������ ������� ��� ��������� � ������
������ ������~$K$ ���������� �������~$g(K)$. (��� ������ ��������
������������, ����������� ��� ����� ������.) �������� ��������~C, �����
�� ��� �������� � ������ ������������ �������, �������� ��������� �������,
 �� �� ��������� ��������������� ����� ������ ��� "�������������" �������.

\ex[24] (�.~������.) ��������, ��� ������� ���������� �������
����� ������������ ����� � ������� ���������� �������� ������. �����
������ ����� ��������� ������ �������� ����������� ����~|TAG|, �������
��������� �����:
{\medskip\narrower
\item{$|TAG|(|P|)=0$} ���������� ����� � ������ ���������� ������������;
$|LINK|(|P|)$~��������� �� ��������� ��������� �����.
%
\item{$|TAG|(|P|)=1$} ���������� ������������ �����, �� ���������� ������
���������� �������; ������ ��������� ����� ����� ����� ����������.
%
\item{$|TAG|(|P|)=2$} ���������� ����� � ���������� �������;
$|LINK|(|P|)$~��������� �� ������ �����. ������ ���, ����� ��� ���������
������, �� ����������� ������ ���������� �������, �� ��������� �����
�~$|TAG|(|P|)=2$, ����� ����������~$P\asg|LINK|(|P|)$ �� ��������� �����
�~$|TAG|(|P|)\le 1$. (��� ������������� ����� �������� ���� ��
�������������� ������; ����� �� �������� ����� � ����� ������������� �����
���� � �� �� �������� ���������� �������.)
\medskip}

��������, ��� ���������� ���������� ��������� ��� ������� � ������� ������
�� ����� ��������������� �������, �����������, ��� � �����
�~$|TAG|(|P|)=2$ ������� ��� ���� ���� ������~$|AUX|(|P|)$.

\ex[16] ������ � ����������~L �~D ������� �����������
������������ ���~$N=M-1$, � �� ���~$N=M$?
%%646

\ex[10] � ���������~L ���������, ��� $K$~�� ������ ���������~0. � ����� ��
����� ���� ��� �������� ���� ���~$K=0$?

\ex[15] ������ �� �������� ������~$h_2(K)=h_1(K)$ �~(25), ����~$h_1(K)\ne0$?

\rex[21] ������������� ��~(31) ����������������~(30) � ��������
������ �����~10--13 ���������~D? ����� �����, ������ �� �������
��������~$A$, $S1$ �~$C$.

\ex[40] ��������� ����������� ����������� ����������� �������
��������~$h_2(K)$ � ���������~D ���, ���: (a)~$1\le h_2(K)\le r$ ���~$r=1$,
 2, 3,~\dots, 10;
(b)~$1\le h_2(K)\le\rho M$ ��� $\rho={1\over10}$, ${2\over10}$,
${3\over10}$,~\dots, ${9\over10}$.

\ex[�25] (�.~������.) �������� ��������~D ��������� �������, ��������
���-�������~$h_2(K)$: � ����~D3 ����������~$c\asg 0$, � � ������
����~D4 ����������~$c\asg c+1$. ��������, ���, ����~$M=2^m$,
��������������� ������������������ ����~$h_1(K)$, $(h_1(K)-1)\bmod M$,
~\dots, $\left(h_1(K)-\perm{M}{2}\right)\bmod M$ �����
������������� ���������~$\set{0, 1,~\dots, M-1}$. ��� ���� �����, ������
������������������� ��� ������~\MIX, �������� �� ��������� � �����
�����������, ���������������� �� ���.~42, ���� ��������� ����������
���������� ����������� �� ��������� �����������?

\rex[20] �����������, ��� �� ������ �� ������� ������ �� �������,
 ����������� � ������� ���������~D, ������� ��������������� �������
��� ���������. ������� �� ��� ���� ��������� �������� ����������~$N$,
����������� ����������~D?

\ex[27] ��������, ��� ��������~R ��������� ������� ����� � ����� �� ����,
��� ���� �� $|KEY|[i]$ �� ��� ������ ��������.

\rex[23] ���������� ��������, ����������� ���������~R, ���
�������� ��������� �� ���������� ������� �������, ����������� � �������
���������~C.

\ex[�20] �����������, ��� ��������� ���� ��������� ������ ������� ��
$MP$~���������, ������ ����� $P$~������ ����� ������ ���-�����. (�
�������� ������� $P$~����� ������; ��������, ���� ������� ��������
������������ ������������� �����, �~$M=10^3$, ��~$P=10^7$.) �����������,
���~$M\ge7$ �~$N=7$. ����� �� ��������� ���� ��������� ������ ���������
������� ���������� ���� ��������� ���������. �������� �����~$M$ �~$P$
������ ����������� ��������� ���-������������������ 1~2~6~2~1~6~1
(�.~�.~$h(K_1)=1$, $h(K_2)=2$,~\dots, $h(K_7)=1$).

\ex[M19] ���������, ������ ����� �������~(39).

\ex[M20] ������� ���-������������������� $a_1\ a_2~\ldots a_9$ ���
������������� ��������� ����������� ����� ������� ������� �����~(21)?

\ex[�27] ��������� �������������� �������~K. [\emph{��������:} �����
$$
s(n,x,y)=\sum_{k\ge0}\perm{n}{k}(x+k)^{k+1}(y-k)^{n-k-1}(y-n);
$$
����������� ������������ ������� ����� [�������~(1.2.6-16)] ���
�������������� ����, ���~$s(n, x, y)=x(x+y)^n+ns(n-1, x+1, y-1)$]

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

��� ���������� ������� �� ����� � ���, ���, ���� ������������ ��������
�����������, ������������������ ���������� ��������~$C'_N$ ��������
������. ������� �������, ���������� ��������� ����� �������~$Q_r$,
������������ � �������~K, � ������� �� ���~$N=\alpha M$ �~$M\to\infty$.

\ex[M21] \exhead(������ � �������.) �� ����� ����� � �������������
��������� ������� $m$~���� ��� �������, ������������� � ��� �
���������������� ��~1 ��~$m$. ��� ����� � ���������� ���� ��������� ����.
�������� ���� ����������� � ������� ���������� ������������. �� ��������
���������������
%%647
�� ������ ��������� �����, �� ���� ��� ��������� ����, � �������
����� ��Į�����, �� ����������� ������� (�.~�.~���� ���� ����������, �����
������ �������� $k\hbox{-��}$~����� ��� �������, �� ��� "�������"~$k$,
$k+1$,~\dots, $m$ ������), ��� �������� ���� ��������� � ���� ������

�����������, ��� ��� ���������� � $n$~���������� ��������, ������
$j-\hbox{�}$~���� ����������� � ������, ����� ������ ��������� �����
������~$a_j$. ������� ������� ����� �������������������~$a_1$~\dots{}$a_n$,
 ��� ������� ��� ������ ������ ������������, �����������, ���
������������� ����� ����� � ����� �� ������� �� �������? ��������,
����~$m=n=9$
�~$a_1\ldots{}a_9=3\ 1\ 4\ 1\ 5\ 9\ 2\ 6\ 5$, ���������� ������������
��������� �������:
\picture{���. ���. 647}
[��������: �������������� �������� ��������� �����������.]

\ex[�28] (����~�������.) ��������, ��� � ������ � ������� ��
���.~29 ���~$n=m$ ��� ������ ������������ ����� � ������ �����, �����
���������� ������������~$p_1$ $p_2$~\dots{} $p_n$ ���������~$\set{1, 2,
~\ldots, �}$, �����,
���~$a_j\le p_j$ ��� ����~$j$.

\ex[�40] ���� � ������ � ������� (���.~29) $n=m$, ����� �������
����������� ������~$(n+1)^{n-1}$, � �� ���.~2.3.4.4-22 �� �����, ��� ���
���� ����� ���������, �������� ���~$n+1$~���������� ���������! �������
���������� ����������� ����� �������������������� ��������� � ���������.

\ex[�26] ��������, ��� ������� ���������~(44) ����� ������������
�������~$(C_0, C_1,~\ldots, C_{M-1})$ ��� ����� �����
���������������~$b_0$, $b_1$,~\dots, $b_{M-1}$, ����� ������� ������~$M$.
��������� �������� ��� ���������� ����� �������.

\ex[�23] ���������, ������~(51) ����� ���� ����������� �
��������� �������� ����� ����, ������������ ����������~L. [�����
����������� ���� �������� ��� ������~(51)?]

\ex[�22] ���� ����� ����������---����������� �������, ����� ���� �
���������� ������� �������, ����� ������ �������� �����������, ��� ��
���~38.
(a)~���� ����� �����������~$P_{Nk}$ ����, ��� ������ ������ �����
�����~$k$, ���� $M^N$~���-�������������������~(35) �������������?
(b)~������� ������������ �������~$P_N(z)\sum_{k\ge0} P_{Nk} z^k$.
(c)~�������� ����� ��� ������������ �������
������� ����� ���� ��� ������� � ��������� ������. (��������������,
��� ��������� ����� � ������ �����~$k$ ������� $k+\delta_{k0}$~����.)

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

\ex[�22] ������� ��������� ����� ���� ��� ������ ���������� �������, ����
����� ��� ���������. (��.~(18).)

\rex[�29] ������� ��������� ����� ���� ��� ������ ���������� �������, ����
����� ��� �������. (��.~(19).)

\ex[�32] \exhead(������������� �������� ��� �����������.) ��������
����������� ��� �� ���������� ������������ � ������ ������� ��������
������� ������ ������ �������� �������, ���������� ����� �������
��������~6.2.2�
� ������������. ��������������� ������� ����� ����, ������ �����
���������������� ��������� � � ������ ��������, � � ������ ����������
������. [\emph{��������:} ��.~� ��������~(5.2.1-11).]

\ex[M30] ���� ����� ����������---���������������� ������� ����� ���� �
���������~C (������������ �������). ��������� �����~$c(k_1, k_2, k_3,
~\dots)$ ���������� ���-�������������������~(35), ������������ ��������~C
���������� ����� $k_1$~������� �����~1, $k_2$~������� �����~2 � �.~�.;
$k_1+2k_2+3k_3+\ldots=N$.  ������� ������������ �����������, ������������
��� �����, � �����������
%%648
��� ��� ������ ������� ������� ��� �����
$$
S_N=\sum_{\scriptstyle j\ge 1\atop \scriptstyle k_1+k_2+\ldots=N}k_jc(k_1,
k_2, \ldots).
$$

��� ������� �������� $S_N$ � ������ ���� �� ����� ���������� ������ �
�������������� ���������~C?

\ex[M33] ������� ��������� ����� ����, ������������ � ���������~C,  ����
����� ��� ��������� (��.~(15).)

\ex[�40] ���������������, ������� ��� � ������� |R|~����������� ��~1 ���
������� $(N+1)\hbox{-��}$~�������� � ������� ���������~C. (��������� ��� �����
�����~$T_N$.)

\ex[�20] ��������~(17).

\ex[�42] ��������������� ����������� ���������~C, ������������ �������
�������~$M'\ge M$. ��� ����������� ������������ ���� ������~$M$ �������,
��� ��� ������ $M'-M$~��������� �����, ��������� � ����~C5, ������������ �
�������������� ����� �������. ����� �����~$M$ ��� �������������~$M'$,
$1\le M \le M'$, ���� ��������� ��������������?

\ex[�43] \exhead(��������� ����������� � ��������� �����������.) ����
�����  ����������---���������� ������� ����� ���� � ����� �������� ���������
 � ������������������� �����������
$$
h(K), (h(K)+p_1)\bmod M, (h(K)+p_2)\bmod M, \ldots, (h(K)+p_{M-1})\bmod M,
$$
��� $p_1$ $p_2$~\dots $p_{M-1}$---��������-��������� ������������
���������~$\set{1, 2,~\ldots, M-1}$, ��������� ��~$h(K)$. ����� �������, �
���� ������ � ���������� ���������~$h(K)$ ���� � �� �� ������������������
�����������, � $(M-1)!^M$~��������� ������� $M$~������������������� ���� �
���� ��������� �������������.

����� ����� ������������� ��������, ���� ��� ������������� ������
 �������� �������� �������~$m$ ��������� ��������� ���������. ������
$n$~���  ����� ��������:
{\medskip\narrower

� ������������~$p$ ������ ������� ����� ��������� �������. � ���������
������ (�.~�.\ �~������������~$q=1-p$) ������� ����� ������� �������,
����� ������� �����, ������ ��� $m-1$~������� �������������. ����
��������� ������� ��������, ������ ��; � ��������� ������ �������
\emph{�����} ��������� ������� (������� ����� �����) � ������ ��, ������,
 ��� ��� ��������� ������� �������������.
\medskip}
��������, ����~$m=5$ �~$n=3$, �� ����� ���������� ���������
��������� ������������ (������, ������, ��������, ������, ��������)
���������� � ������������
$$
{7\over 192}qqq+{1\over6}pqq+{1\over6}qpq+{11\over64}qqp+{1\over3}ppq+{1\over4}pqp+{1\over4}qpp.
$$
(��� ��������� ������������� ���������� ����������� � ���������
�����������, �����~$p=1/m$, ��� ����� �������������� �������� ������� ���,
��� ��������� ������������������ ���� �������� �~0, 1, 2,~\dots, � ���
��������� ����� ����������.)

������� ������� ��� �������� ����� ������� ������� � ����� ����� �������
(��� � ����������� �������). ���������� ����� ��������������� ��������
���� �������� ���~$p=1/m$, $n=\alpha(m+1)$, $m\to\infty$.

\ex[�43] ������ ������ ���.~44 � \emph{��������� �����������,} �����
������������������ ���� ���������� �~$h_1(K)$, $(h_1(K)+h_2(K))\bmod M$;
����� ���������� ���� ������� � ������� ���� ��~$h_1(K)$ �~$h_2(K)$
(�.~�.~$(M-2)!^{M(M-1)}$ ��������� ������� ������������������� ���� � ����
��������� ���������
%%649
���������������). �������� �� ������������ ��������� ��������������
������������� ������������ �����������?

\ex[M42] �������~$C'_N$ �~$C_N$ ��� ������ �������� ���������,
������������� ������������������ ����
$$
h(K), 0, 1, \ldots, h(K-1), h(K)+1, \ldots, M-1.
$$
\ex[M25] ����� ������� ����� ���� ����������� ��� �������� ��������� �
������������������� ����
$$
h(K), h(K)-1, h(K)+1, h(K)-2, h(K)+2,\ldots\,?
$$
��� ������������������ ���� ������� ���������� ��-�� ����, ��� ���
���������� ����� ����������������� ������� ��� ������~$M$ ��������
[\emph{��������: ���������  �������� ����������� �������� ������.}]

\rex[M21] ���� ����������� ������������������ ������� �����������
 ��������� ���-�������~$h_n(K)$. ��������������� ����� �������� ���������,
� ������� ��������� �������~$h_1(K)$, $h_2(K)$, $h_3(K)$,~$\ldots\,$.
��������, ��� �������� ��������� ����������� ����� � ��� �� �������,
�������� ����~$h_1(K)=h_2(K)$, �� ��� ������ ������������.

\ex[��24] ������� ���.~34 �� ������ $b$~������� � �����, ����������
������� ����� ���� (�.~�.~��������� � �����) $C_N$ �~$C'_N$ ���
������������� ���������� �������, �����������, ��� ��������� ����� �
������ �� $k$~��������� �������~$\min(1, k-b+1)$~����. ������ ������
������������~$P_{Nk}$ �� ���.~34 �������������� \dfn{������������ ��������}
$$
\eqalign{
\perm{N}{k}\left({1\over M}\right)^k \left(1-{1\over M}\right)^{N-k}
&={N\over M}{N-1\over M}\ldots{N-k+1\over M}\left(1-{1\over M}\right)^N
\left(1-{1\over M}\right)^{-k}{1\over k!}=\cr
&=e^{-\rho}\rho^k/k!+O(M^{-1}),\cr
}
$$
������������ ���~$N=\rho M$, $M\to\infty$.

\ex[M20] ��������, ��� � ������������~(42) $Q_1(M, N)=M-(M-N-1)Q_0(M, N)$.
[\emph{��������:} �������� �������, ��� $Q_1(M, N)=(N+1)Q_0(M, N)-NQ_0(M, N-1)$.]

\ex[BM16] �������� �������~$R(\alpha, n)$, ������������ �~(55), �����
�������~$Q_0$, ������������ �~(42).

\ex[��20] ��������, ���~$Q_0(M,N)=\int_0^\infty e^{-t}(1+t/M)^N\,dt.$

\ex[��20] ��������, ��� �������~$R(\alpha, n)$ ����� �������� �����
�������� �����-�������, � ����������� ��������� ���.~1.2.11.3-9 ���
���������� ���������������� ��������~$R(\alpha, n)$ � ���������
��~$O(n^{-2})$) ���~$n\to\infty$ � �������������~$\alpha<1$.

\ex[40] ���������� ��������� ���������~C, ���� ��� ������������ �
�������� ������ ���, ��� ��� ������� � ������.

\ex[��43] �������� ������ ���---������, ������������� ����� �������~P, ��
������ $M$~������ �������~$b$. ��������, ���~$C(z)=Q(z)/(B(z)-z^b)$, ���
$Q(z)$---��������� �������~$b$ �~$Q(1)=0$. ��������, ��� ������� ����� ����
�����
$$
1+{M\over N}C'(1)=1+{1\over b}\left({1\over 1-q_1}+\cdots++{1\over
1-q_{b-1}}-{1\over2}{B''(1)-b(b-1)\over B'(1)-b}\right),
$$
���~$q_1$~\dots$q_{b-1}$ ���� ����� ����������~$Q(z)/(z-1)$. �������
������������ ������������� ������������~$B(z)$ ������������
��������~$P(z)=e^{b\alpha(z-1)}$, ��� $\alpha=N/Mb$, � �����������
���������� ������� ��������� (��. � ��������~(2.3.4.4-9) � ���.~4.7-8),
��������� ����� � ����~(61).

\ex[M48] �������� �������~K, ������� ������ ������ ��������� �����������
��� ������������� ������ �������~$b$.

%%650
\ex[�47] ���� �� ������������ ������������������� ����
���������� ������������ ����������� ��������~$C_N$ ����� ���� �������
�������� ���������?

\ex[M21] (�.~�������.) ������� ������ ������������
���������~$\set{0, 1, 2, 3, 4}$, ������������� ������������ ����������� �
������ �������~U.

\ex[�25] ��������, ��� ���� ������������ ������������
������������� ������������ ������������ ����������� (� ������ �������~U),
�� ����� ������������ � ���������� ������������� ����������~$M^a$ ���
����� ������������� ����������~$a$, ���� $M$~���������� ������.

\ex[M48] ����� ��������, ��� ����� �������� ��������� ��������
\emph{������������ �����������,} ���� ������������ �����
$M$~������������������� ����, ������������ �� ���� ���������
��������~$h(K)$ � ������������� � ������������~$1/M$.

��� �������������� ����� (� ������ �������������~$C_N$): ��������� �����
� ������������ ������������ ��� ��������� �����, ����������������� � ���.~44?

\ex[�46] �������� �� �����, ����������������� � ���.~46,
��������� ��������� ������ � ������������ ������������? (��.~�~���.~60.)

\ex[�49] ��������� ������ ����� ���� ����� � ������������ ������������,
���� ����~$p_1$ $p_2$~\dots $p_{M-1}$ (����������� ���.~44) ����������� �
�� ������� ��~$K$? (��������� ����� ������� ������ �������� ����������� �
������������������, ����������������� � ���.~20 �~47.)

\ex[�25] ���� � ���������� ������� ������������ ��������� ������� �
��������, �� ������� ����� � ������� ����������� �������, ����� ���
$M$~������� �������� � ������� ���������?

\ex[M46] ��������������� ��������� ��������� ���������~R. ������� ��� �
������� ����� ����������� ���~R4?

\rex[20] \exhead(����� ���������� �����.) �� ������ �����������
���������� ������ ����� ����� �������� �� ������������� ����� �����. �
����� ������ ������ ������ ��������� ���� � �������, ��� ��� �������� �
���������� ������� ���������. ���������� ������� ������ �������������
���������� ������ ��� �������� ������ ���������� �����, ���� ������
������� �� ������~\MIX.

%% 651
\bye
