\input style
%%122
��� ��������� ����� ${1\over4}N^2$ ��������� � ����� ${1\over4}N^2$ 
�����������. � ����������������� ���, ���������� �������� �������, ��� 
������� ����������� ����� $N\log_2N$ ��������� � ${1\over4}N^2$
�����������. 텑������ ������� ��������� ������, �������� "����������� 
�������", ������ ��������� ����� �����������
�� ${1\over8}N^2$.  ���������� ������� ����� "� ��������� �����"
����� ��������� � ����������� ��������� �������� �� $N^{1.3}$ ��� ��� 
�������� $N$, ������� ����������� �� ��������; ��� $N\to\infty$ ��� ����� 
����� ��������� �� ������� $N(\log_2N)^2$. 䀋������� ���������� �������� 
��������---����� ���������� ��������� ��������� ������---������� ��� � 
�������� � ������,
��� ������� ����������� ����� ${1\over4}N^2$ ���������, 0 �����������
� $2N$ ��������� ������.

쎆�� �� ��������� ������ �������� ���� �������, �������� ����� ��������� 
�� ������� $N\log N$, ��� ��� �������� ��������, � �������� ��� ���� 
����������� ������, ��� ��� ��������
\picture{���. 13. ��� ����� 󈋅�� ��� ������� � ������.}
� ������? �� ��������������: ��� ����������� ��������� � ����������� 
���������. 򀊀� ����������� ���� ������� ����������� ����� 1957~�. 
�.~�.~󈋅���, ������� ��������� ������������ ����������� ������� �� ��� 
���, ���� �� �������� ������������� ���������� ������. 򎃄� ������ ����, 
����� �� ����������, ����������� ��������� �� ����� ������� ������, � ��� 
�� ����� ����� ����������� ����������� �� ���� ���������, ������� ����� 
�������� � ��� ����� ������� ������. ��������� ����� 󈋅�� 
[��. A. S. Douglas, {\sl Comp. J.,\/} {\bf 2} (1959), 5] ������������ 
����� ������� ���������� ���������������� � ��������� ������ � ������ 
����������� �������; ��� ����� ����������� ����� ���� �� ������������ 
������, ���������� �� ���.~13. �����������, �� ����� ������� ����� 
������� � ������ � �������������� �������� �������� ���������� 
%% 123
���������� ����� 1958~�. �.�.~ᅐ���-� 
[��. {\sl Comp. J.\/}, {\bf 3} (1960), 174, 184]. 
� ���� ����� � ��� ������������ ������ ����� ��� ��� ����������, ��� � 
��� ������, ������� �������� ��� ����������� � ��.~ 6.

噅 ���� ���� �������� ������� �������---���������� ��������� ��������� 
��������� ������������. 呋�, ��������, ������� ���� �� 1000 ��������� � 
998 �� ��� ��� �������������, �� �������� S �������� ��� ��� ��������� 
����� (������� ������� $R_{999}$, � ����� $R_{1000}$). �����, ����� 
���������� �����, ���� ������� �������� ����� $K_{999}$ c $K_{1000}$ ����� 
��������, ������� �� ��� ������, � ����� �������� �� \emph{���} �� ���� 
�������� �����. ꎌ������������ �������� ������ ���� ������� ����� 
$(2/3)N$ ��������� � ����������� (��. � ���.~3.4.2--5) ������ ���� 
����������, �������� �� $N/2$ ��������� � ����������� ������.

荀�� ������, ������ ������ ������� "������������" ��������, ������� 
������� ����������� ������, ����� ����� ���� ��������� ��������� �������� 
������. 呋� ������� ��� ���� �� �� ������������� ����������, �� �� ������ 
������� ��� ���� ���������� ����������� �������, ��������� ������, ��� 
�� �������� ��������� �����.

\section 񎐒������ � ����������� ������. 򅏅�� �� ��, ����������,
 ��������� ��� ��������� ������� ����������������� ����� ������� �������, 
�� ������� �������� ���! �������� ����, ��� ��� ���� ������ ���� ������ 
� ���������� ��������� �����-�� �����. ‘� ������---�������� �� � 
���������� ������� � ������� ������ � ��������������� ������� ����. 
󑋛��� ����� �� ����� �, �� ������ ���������� �������� ��� ����� � 
�������� ���� ��������, ����� ��� ����� �� ����� � �����, ��-��������, 
�������� ����� � ������� ���� �������� �~�.~�. ����������� ������ 
����������� ��� ����������� ���� �� ����� �� �������� �������, ���� ����� 
������� � ���� � ��������� �������: ����� ����� �� �����, �� ���������� �� 
�������� ���������, �������� ����� ������� ����� ����������� ��������� � 
�����������. (������������� �������� ����������, ���� �� ����� ������� 
������� ������ �����, ��� ��� ��������� ����������.) 򀊎� ����� �������� 
���������� ������� ���������� 葀�� � 񈍃����, 
[{\sl JACM\/},  {\bf 3} (1956), 169--174];
 �� ������� ���������� �������� � ������ ꐎ����� � 򀐒��� 
[Proc. ACM Nat'l Conf., {\bf 21} (1966), 331--337].

񎐒������ � ����������� ������ ������ ������� ��������������� 
������������ ������ ���� ��� ����, ����� �������� ���������� ���������� 
����� � �� ������ ����� ������ �����������, ���� ��� �������� 
��������������� ������, ������� �� ��������� ��������� ��������������� 
������������� ������. (�. ���������� �������������� ��������� (�������� 
5.2D),
%% 124
\bye
