��

�� -�� k �� . ��, �� -�� k ��, �� k �� (��, ��), �� -��. �� , �� (�� , �� , �� -��).

�� ; �� . �� .

$\scriptstyle{\blacktriangleright}$ 11.2.1. �� -�� ${\hbox{\tt 1}}\ldots{\hbox{\tt k}}$ .�� -�� -��. �� k ��

     ����������: array [1..n] of T;
     ���������: array [1..n] of 1..n;
     ��������: 1..n;
     �������: array [1..k] of 1..n;

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

��. �� ${\hbox{\tt ��[i]}}={\hbox{\tt 0}}$ �� ${\hbox{\tt i}}={\hbox{\tt 1}}\ldots{\hbox{\tt k}}$ , � �� , �� ${\hbox{\tt ��}}={\hbox{\tt 1}}$ � ${\hbox{\tt ��[i]}}={\hbox{\tt i+1}}$ �� ${\hbox{\tt i}}={\hbox{\tt 1}}\ldots{\hbox{\tt n-1}}$ , � �� ${\hbox{\tt ��[n]}}={\hbox{\tt 0}}$ .

  function ����������� (t: T): boolean;
  | var i: integer;
  begin
  | i := �������[h(t)];
  | {�������� ������ � ������, ������� � i}
  | while (i <> 0) and (����������[i] <> t) do begin
  | | i := ���������[i];
  | end; {(i=0) or (���������� [i] = t)}
  | ����������� := (i<>0) and (����������[i]=t);
  end;

  procedure �������� (t: T);
  | var i: integer;
  begin
  | if not �����������(t) then begin
  | | i := ��������;
  | | {�������� <> 0 - �������, ��� �� �������������}
  | | �������� := ���������[��������]
  | | ����������[i]:=t;
  | | ���������[i]:=�������[h(t)];
  | | �������[h(t)]:=i;
  | end;
  end;

  procedure ��������� (t: T);
  | var i, pred: integer;
  begin
  | i := �������[h(t)]; pred := 0;
  | {�������� ������ � ������, ������� � i;  pred -
  |    ����������, ���� �� ����, � 0, ���� ���}
  | while (i <> 0) and (����������[i] <> t) do begin
  | | pred := i; i := ���������[i];
  | end; {(i=0) or (���������� [i] = t)}
  | if i <> 0 then begin
  | | {����������[i]=t, ������� ����, ���� �������}
  | | if pred = 0 then begin
  | | | {������� �������� ������ � ������}
  | | | �������[h(t)] := ���������[i];
  | | end else begin
  | | | ���������[pred] := ���������[i]
  | | end;
  | | {�������� ������� i � ������ ���������}
  | | ���������[i] := ��������;
  | | ��������:=i;
  | end;
  end;`

$\scriptstyle{\blacktriangleright}$ 11.2.2. (�� .) �� -�� k �� , � �� n ��. ��, �� C(1+n/k) , �� (��, ��) �� t �� , �� h(t) �� (�� 1/k ).

��. �� l(i) -- �� , �� -�� i , �� C(1+l(h(t))) ; ��, �� , �� $\sum_i l(i) = n$ . $\scriptstyle\blacktriangleleft$

�� . �� , � �� -�� << ��>>: �� -�� << ��>> ��, �� . ��, �� �� , �� . �� , �� -��, �� .

�� H -- �� , �� T � �� k �� (��, $0\ldots k-1$ ). ��, �� H -- �� -��, �� s � t �� T �� h(s)=h(t) �� h �� H �� 1/k . (�� , �� H , �� h(s)=h(t) , �� 1/k -�� H .)

��. �� H �� , �� s � t �� T �� h(s) � h(t) �� h �� , �� $0\ldots k-1$ .

$\scriptstyle{\blacktriangleright}$ 11.2.3. �� $t_1,\ldots,t_n$ -- �� T . �� , �� $t_1,\ldots,t_n$ � ��, �� h �� H . ��, �� (�� -- �� h �� H ) �� Cn(1+n/k) .

��. �� m_i �� , �� -�� i . (�� $m_0,\ldots,m_{k-1}$ ��, ��, �� -��.) �� , �� , � �� $m_0^2+m_1^2+\ldots+m_{k-1}^2$ .(�� s �� -��, �� $1+2+\ldots+s$ ��.) �� $\langle p, q\rangle$ , �� h(t_p)=h(t_q) . �� , �� p � q , �� 1/k �� $p\ne q$ , �� 1/k , � �� n²/k , � �� n+n²/k , �� p=q . $\scriptstyle\blacktriangleleft$

�� , �� C(1+n/k) ��. � �� n/k �� << �� >> ��-��.

$\scriptstyle{\blacktriangleright}$ 11.2.4. �� , �� (� �� , �� ).

[��. �� , �� , �� -��, �� . �� i -j -�� t_i � t_j . (�� , �� -- � �� h .) �� . �� $t_i\ne t_j$ �� i -j -�� 1/k . �� . �� x �� T � �� . �� : �� -- �� -- �� -- �� -- �� -- �� -- ... �� (�� ), �� , �� x .] $\blacktriangleleft$

�� . ��, �� A � B �� , �� A � B , �� . �� : �� , �� A . (� �� , �� !)

�� . �� ${\Bbb Z}_p$ �� p , �.�. $\{0,1,\ldots,p-1\}$ ; �� p . �� ${\Bbb Z}_p$ . �� , �� $a_1,\ldots,a_n$ -- �� ${\Bbb Z}_p$ ;�� -4mm $\begin{displaymath} h: \langle x_1\ldots x_n \rangle \mapsto a_1x_1+\ldots+a_nx_n\end{displaymath}$ -1mm�� pⁿ �� ${\Bbb Z}^n_p \to {\Bbb Z}_p$ �� $\langle a_1\ldots a_n \rangle$ .

$\scriptstyle{\blacktriangleright}$ 11.2.5. ��, �� .

[��. �� x � y -- �� . �� , �� ? �� , �� , �� x-y ? �� : �� u -- �� ; �� .] $\blacktriangleleft$

� �� ${\Bbb B}=\{0,1\}$

�� 2.

$\scriptstyle{\blacktriangleright}$ 11.2.6. �� ${\Bbb B}^m$ �� . $\scriptstyle\blacktriangleleft$

�� (�� . ��). �� , �� (��) �� , �� . �� : �� N � �� $f_1,\ldots,f_k$ , �� $1\ldots N$ . � �� N �� , �� , �� -�� -�� . �� : ��, �� , �� . (�� , �� .)

pvv
1/8/1999

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

��