\input style
������, ��� �� ����� ��������������� ���������, ������ � ������� � ������ 
�� ������ ������.

� ���������� ��������� ��������������� ���� ��������� ���������� � 
��� ���������� ���������� �� 1 �, ����� ����, ���� �� 26 ������ 
��������������� ����� �����������. � ���� ������ �������� ��������� 
�����, ������ ����� � �������� ��������� � ��������� ������. � 
����������, ���-�� ����� ��� ������ ���������� 19071 ����� �� ���� 
6.5-������� ������� ����; � ������� �������� 49 ���� � ������! (񐅄��� 
�������� ������� �������� ����� ���������.) 

퀑������ ���������� ��������� �����, � ������ 
����������-������������ ��������� ������������ ��������, ����� 
���������� � ���������� �������� 1900~�., ������� �������� ������� ��� 
���� ������, ����� ������������� ��� ���� ������ � ��������� ������. 
僎 ����� ���������� (��������������� � 1901 � 1904 ��.) ����� 
�������������� ������ ���� � ���������, � ��������, ����� ��� ��, ��� 
����������� ��������� �������������� ������. 葒���� ������ ����� 
��������� � ����������� ������������� �������� 녎��� �. 򐓑������ 
� The Development of Punch Card Tabulation (Washington: U. S. Bureau of the 
Census, 1965); ��. ����� ��������� ������������� ���������: 
{\sl Columbia College School of Mines Quarterly\/}, {\bf 10} (1889), 238--255; 
{\sl J. Franclin Inst.\/}, {\bf 129} (1890), 300-- 306;
{\sl The Electrical Engineer\/}, {\bf 12} (Nov. 11, 1891). 521--530; 
{\sl J. Amer. Statistical Assn.\/}, {\bf 2} (1891), 330--341;{\bf  4} (1895), 365; 
{\sl J. Royal Statistical Soc.\/}, {\bf 55} (1892), 326--327; 
{\sl Alegemeines Statistisches Archiv\/}, {\bf 2} (1892), 78--126;
{\sl J. Soc. Statistique de Paris\/}, {\bf 33} (1892), 87--96;
U.~S. Patents 395781 (1889), 685608 (1901), 777209 (1904). �������� � 
������ ������ �������� ថ� �������� 䆅��� ��� � ���������� 
�������� ������������� ��������, ������� � ����� ������ ����� 
�������������� � ���������� IBM � Remington Rand.

񎐒���������� ������ ���������---���, �������, ������ ������� 
����������� ����������, ������������ � �������� ���. � ��� ������� 
�����������, ��� �������� ��������, ���������� ��� �������, ������ 
������������� "�� ����������� ��� ������� �������", �� �� �� �������, 
����� ������� (������ ��� ��������) ������ ��������������� ������. 
䀋��� �� ��������� ���� ���������� ������� �� ������� ������ ����, 
��-��������, ������� �����-�� ����������� ���������� � �������� 
��������� (��. �.~5.2.5); ��� ������� � ����� ������ ������������� 
����������� IBM �� ���������� (1936~�.). ��� ��������� ����������� 
����� ������ "������ ������" �������� ��������� ���������, ������������� 
� ������ �. �. ꎌ��, 
{\sl Trans. of the Office Machinery Users' Assoc\/}. (London, 1930), 25--37. 
텗����� ꎌ�� �������� ������, ��� ������ ������ ����������, ���
%% 458
���������� ����� ����������� ��������� � ������� �����������, ���� 
������������� ��� ����������� ��� �������������� � ������������� 
����������. 僎 ������ �������� ���������, ���������, �������� 
��������� �������� �����������, ��������� � ������ � 1930~�. 
񎐒���������� ������ � �� ����� ������������ ��~360 ��~400 ���� � 
������ � ��������� � ������ �� 9 ������ ���������� � �����.

脅� ������� �������� � ������� ���������� ��� ��������� 
����---\emph{����������� ������}, ������� ���� ���������� ����������� ������� 
(� 1938~�.). 񍀁������ ����� ��������� �����������, ��� ����� ����� 
��� ��������������� ������ ���� � ���� ����� �� ���� ������; ����� 
���������� ����� ������� ������ ������ � ������ ����������� IBM �� 
������� �������� (������ 1939~�.). [�. � James W. Bryce. U.~S. Patent 
2189024 (1940).]

瀒�� �� ����� ��������� ��� � ���������� ������� ���������� ����� 
����������� � �� ���������. � ����� ���� ������� ������������� ����, 
��� ��������� ���������� ���� ������ �����-���� ���������� ��� 
�������������� ����� � ������������ ����������. ꎍ��������� 
�������������� ������ EDVAC �������� �������������� �����������, 
��������� ��� ��������� ��� �������� ����������� ������������� 
������������� ����������� ���������� ���.  ��������, ��� 
������������������ ������� ������ ������ �������� �� ������ ��� 
����������� ��������� ������� ���������� ���������; � ��� ������ ���� 
����������� ��������, ����� ���������� � �������������� ��������� 
"������ �������" � ����������. ���� 䆎� ��� 텉��� ���������� � 
1945 �. ��������� ��� ���������� ���������� ��������, ����� ��������� � 
������������� ��������� ����� ������, ������� �� ��������� ��� 
������ EDVAC; ������������ ����������� �������������� ������ 
������������ ����������, � ��� ������� ��� ������������ ����������, � 
������������� � ������� ����� ���� ������� ����������� ������������ 
����������� �������������� ������. ����� ��� ���������� 
������������ ������� � ������ 
�.~�.~ꍓ�� [{\sl Computing Surveys\/}, {\bf 2} (1970), 247--260]; ������ 
��������� ���������� ��� 텉���� � �������������, "��������������" 
���� ��. � ��� Collected Works, {\bf 5} (New York, Macmillan, 1963), 
196--214.

�-�� ������������� ������ ������ � ������ ������� ����������� 
������ � ������� ���������� ������� � ����������, � � ������� "Progress 
Report on the EDVAC", �������������� �. �. �������� � � �. 쎗�� 
��� ����� 쓐� �� �������������� [Moore school of Electrical Engineering 
(September 30, 1945)], �����������, ��� ���, ���������� ����������� � 
��������� ���������� ��� ������, ����� �� ������������
%% 459
�������� ���������� ������������, �������� ��� ���� ������� �������� 
����������. ���� ������ �������� ���������������� ����������� 
����������� ���������� � ���������������� ����������� ������� � 
�������������� ������� ��������� � ��������� ���������� ��� ������, 
�������� ��� ������������ "�� ����� 5000 ��������� � �������".

䆎� 쎗�� �������� � ������� � "���������� � �������" �� 
����������� ������ �� �����������, ������������ � ����� 쓐� � 1946 �., 
� � ������� ��� ������ ���������� ������ �������������� ���������� 
���������� � ������� �������������� ����� [Theory and techniques for 
the design of electronic digital computers, ed. by G. W. Patterson, 
{\bf 3} (1946), 22.1--22.20]. 
쎗�� ����� ���� ����������� � ����������� ���������: 
"򐅁������, ����� ���� ������ ���������� ����������� ���������� � 
����������, ����� ��������� ��� ����������, ����� ���� ������ 
������������� ��� ���� ��� ��������� � ��� ���������". 瀒�� �� �������, 
��� ������, ��������� ��������� ������� �������������� ���������, 
������ ����� ����� ����������� ����������� � ���������������� 
������; �� �������, ��� ���������� ����� ���� ������� ���� � ����� � 
���������� ���������. � ������ ������� ������� � �������� �������, 
�������, ��� � ������ ������ � ������� ��������� ����� $N^2/4$ 
���������, � �� ����� ��� � ��������� �� ������� �� ��������� ����� 
$N\log_2N$. ��� �������� ������� ������� ������ ������� ��������� 
������, � 쎗�� ����� �������, ��� ��� ����������� ������� ����������� 
����� �� ����� ����� ���������, �� ������������ ������ ���������������� 
����������� �������. ������ ����� ������� ��� ������ ��������� 
������� ������� ����������� ���������� � ���������� ���������, 
������� ���������� �������� ��������� ���������� �� ������� ������, 
���������� ����� ������� �������� �� ����� (��. � �. 5.4.7).

⑊��� ����� ����� ������ � 쎗�� ������������ ��������, ������� 
��������� ��������� �� ����� ������ ����������� �������������� 
����� BINAC (��� ������� ����������) �. UNIVAC (��� ������������ 
����������). ⍎�� ថ� �������� ��� ������� ���� � ���� ��������, 
��������� ������ UNIVAC. � ��� ����� ����� �� ���� ����, ��� ��� 
������ ������������ ���������: �������������� ������ ����� 
����������� �������, �� ��� ������ ������. ���� ������������ 
UNIVAC ��� ������������ ������� �. ㎋������� ��������� 
������������ ������ � �������� �������� ������� ����������, 
���������� � ������� ���������, � �� ������ ��������� �������� ����� 
�� ���������� ������������. � �� �������, 100 ��������� ������� �� 10 
���� ����� ���� .������������� �� UNIVAC �� 9000 � (�. �. 375 ����).
%% 460

UNIVAC I, ���������� ����������� � ���� 1951 �., ����� ���������� 
������ � 1000 12-�������� (72-�������) ����. � ��� ����������������� 
������ � ������ �� ����� ������ �� 60 ���� �� ��������� 500 ���� � 
�������; ������ ����� ���� ������ ��� ��������, ����������� 
������������� ������ /������/ ����������. � 1948~�. ������ ㎋������� 
��������� ���������� ������ ���������� ������������ ������� � ������ 
����������� ������, ������ � ���������� � �������������� ����� 
������� �����. �� ��� ������� �������� ����� ������� ���� "������� 
�����" � ��� "��������������� ������"; ������� ����� ����� �������, ��� 
������ ���, ����� �������� ����� ������� ���� ����, ��� ������� ������ 
����� .�������� ������ ���������� ������, ������ ������ �����. 򀊈� 
�������, �� ����� ������������ ������� ��������� ����� ����� ���� 
����� ����� ���������� ������, � �� ����� �������� ���, ����� ��� ��� 
������ ��������������� ������ ���� ��������� ������ ���, ��� �� ������ 
� ���������� �����. ���� ����� ���� ������� ������ ��������������� 
��������� 5.4.6F, ��� ��� ��� ������������� ��������� ��������� ������ 
����� ����� ������� ����������. [�. � Collation Methods for the UNIVAC 
System (Eckert-Mauchly Computer Corp., 1950) vol. 1,2.]

꓋������������ ������ � ���� ������ ���� ��������� �������� 
����������, ������� ��� ������ ������� ����������, ������������� ��� 
��������������� ����������������. ��������� �������� ������ ������, 
������� ������ (�� ����) � ��������� ����� ������ ������ � "��������" 
�����, ���������� ����� �����, � ��������� ���������� �������� 
��������� ��������� ���������� ��� ������ �� ����� ������. ��� 
�������� ���� ��������� ���� ���������� ���������� ������ �� 60 ���� � 
�������������� ������ ��������� � �������� (�������� 5.2�); ����� 
���������� ��� ���������������� ����������� �������� ������� � 
�������� �������, ����������� ��������� ����, ��� ������� ����. [�. 
Master Generating Routine for 2-way Sorting (Eckert---Mauchly Div. of 
Remington Rand, 1952). ��� �������� ����� ������� ��� ���������� 
"����� ������������ ��������� ������������ �������" (Master 
Prefabrication Routine for 2-way Collation)! �. ����� F. E. Holberton, 
Symposium on Automatic Programming (Office of Naval Research, 1954), 
34--39.]

� 1952~�. ������ ������ ���������� ���������� ������ ����� � 
��������������� ��������, �� ������ ���� ������� ������������ �����. 
䀍���� ㎋������� [Time analises of various methods of sorting data, Digital 
Computer Lab. memo M-1680 (Mass. Inst. of Tech.,. October 17, 1952)] 
���������������� ��� ������ Whirlwind ���� ��������� ������� � ������ 
������
%% 461
���������� � ���������� ������� ��� ������ ���������. � �����, ��� 
��� ���������� ����� 15-������� ������� �� 8-�������� ����� ��������� 
�� �������� ���������� ���������� � ��� ������, ���� ������������ 
������� �� 256 ���� � ������ ������ ���������� � ������������ 
��������������� �� ����� �������, � ����� ��� ������� ���������. 
��� ���� ����� ���� ��������� ����������, ��� �� ��������� ������, 
���� ����������� ����� ��� �� ����. ������ ������ 
������������������ ������ ���� ����������� ��������� �������:
������ ����������� ������� ����� ����������� ���������� � ���������� 
2, ������� ����� �������� ������, ������� � ���� ������� ����� ������ 
��������.

��� ���������� �������� ���������� �������� � ����������� 【����� 
X. 񜞂���� � 1954~�. [Information sorting in the application of electronic 
digital computers to business operations, Digital Computer Lab. report R-232 
(Mass. Inst. of Tech.. May 24, 1954), 60 pp.]. 񜞂��� �������� ���� 
��������������� �������� � ������ � ����������. � �������, ��� ������ 
������� ��������� ������������ ����� ������� ����� $e-1$, � 
������������ ������ � ���������� ����������� � ������� ��� �� 
��������� ����� �������� ������, ��� � �� ������.

噅 ����� ��������� �������� �����������---�� ���� ��� ����������---
���� �������� ㎂����� �. 䅌���� � 1956~�. [Electronic Data Sorting 
(Stanford University, October, 1956), 92 pp.]. ��� ������ ������� �������� 
������ ������ ��������� ����������. �.��� ��������������� ��� 
����������� ������ ������ ����������: � �������������� ����������� 
������, �������� ������ � ������ � ������������ ��������; ��� ������ 
������ ���� ����������� ����������� ��� ����� ����������� ������. 
(�. � ���. 5.3.4--62.) ���� ��������������� �� ����������� 䅌��� �� 
�������� ������� ������������ ���������, � ��� ���������� ������ ���� � 
���, ��� ������� ������ � ���������.

򀊈� �������, ������� ���������� ���� ����� ������� �� ������� 
����������� ������� � �����������: � ������� �������� ��� ��������� 
������, ������� ������������� �����������, ������ ����������� 
������������, ������� �������� �����������, ������ ������� �� ������� 
���������� � ��������� ����������.

� ���� �� ���������� ������������ ���, ���������� �� ��� ���, �� 
��������� � "�������� ����������". � �� ���������, ��� ������� ����� 
������ ������� �������������� ����� ���������� � ������������ 
����������� ��������, ��������� ������������ �������� ���� ���� � �� 
����� ������� � ���. 퀊���� � 1955--1956~��. ���������� � ���������� 
��������� � ������ � ���� ���� ������� �������� ������.
%% 462
��� ������ ���� ������������ �. �. �������� [Proc. Eastern Joint. 
Computer Conference, 8 (1955), 39---55]. � �������� � ������� ����������: 
"����� ������� ��������� ������� ����������, ���� ������ ��������� 
��������. � ��� ���� �������� ��������� ������� ���������� �� 
�����������, � ����������". ������ ������ ��� ������������ ������������ 
����������, ��������� � �������, � ����� ������ ���������� �� ���. 僎 
������������ �� 54 ������� �������� ������� ������ �� �������� 
����-�������������.

������ ������ �. X. ������ [Sorting on Electronic Computer Systems, 
{\sl JACM\/}, {\bf 3} (1956), 134--168] ������� ������ ����� � �������� 
����������. ���� �� ��������� � 1956 �. ����� ���� ����������� 
�������������� ������, ��� ������ ��� ��� �������� ���������� �� 
������ ����������. ����� ��� ���������� �������� ������ �������� 
����� ���������� ���������� � ������� ���������� � ������� ������ 
�������� �� ������ ����������� � �������������� ��������� 
�������������� ���������. � ���� ��������� ����� ������ (��������, 
����� �� ������, ����� ���������� ���� � ���������������) � ���������� 
��������� �������������� �������� ������ �������.

򐅒�� ����� �� ����������, ������� �������� � �� �����, ��� 
����������� �. �. 䝂����� [{\sl Proc. Inst. Elect. Engineers\/}, {\bf 103�}, 
supplement 1 (1956), 87--93]. � ����������� ���� ��� ��������� 
���������� ������� ���� ������������ �. �. ᅋ��� [{\sl �mp. J.\/}, 
{\bf 1} (1958), 71--77]; �. �. 䓃����� 
[{\sl Comp. J.\/}, {\bf 2} (1959), 1--9]; �. �. 쀊-ꐀ�����, �. ⅉ���� � 
�. � [Programming Business Computers (New York: Wiley, 1959), chapter~15, 
298--332]; �. 􋎐���� [{\sl JACM\/}, {\bf 8} (1961) 41--80];
�. �. ���������� [A programming language (New York: Wiley, 1962), 
chapter 6, 176---245]; �. �. ㎒����� [{\sl CACM\/}, {\bf 6} (1963), 194--201]; 
�. �. ��������� [{\sl CACM\/},{\bf  6} (1963), 206--213];
�. �. ㎒��� [Digital Computer User's Handbook ed. by M. Klerer and G. 
A. Korn (New York, McGraw-Hill, 1967), chapter~1.10, 1.292--1.320]. � 
������ 1962~�. ACM ������������ ��������� �� ���������� (������� 
����� �����, �������������� �� ���� ����������, ������������ � ��� 1963 
�. � ������� {\sl CACM\/}).  ���� ������� ������������� � ��������� 
���� ������� � �� �����. �� �.~�.~㎒���� � ����������� ����������� 
����������, ����� �.~�.~�������� � ���������� ���������� � 
����������� ������� � ������ ������������ �.~�.~�������� � 
���������� ������ �� ������---�������� ������������� �������� ������ � 
���� ��������.

� ��������� ������ ���� ������� ����� ������ ����������: 
���������� ������~(1956), ������� � ��������~(1959), �������� 
����������� ����������~(1959), ��������� �������~(1959), ����� ����� � 
��������� �����~(1959), �����������
%% 463
������� (1960), ������� � ������ (1960), ������������� ���������� (1962), 
������� ���������� ����� (1962), ������������� ���������� 󈋜���� 
(1964), �������� ���������� �� �������� ᝒ���� (1964). 葒���� ������� 
���������� ��������� �������������� � ��� �������� ��������� ����� ��� 
���� ����� �����������. ꎍ�� 60-� ����� ������ �������� ������������� 
����������� ��������� ��������������� ������.

��� ������������ ���� �����, ��������� ������� ��� ��������� 
���� �����, ������� � [{\sl Computing Reviews\/}, {\bf 13} (1972), 283--289].

\excercises
\ex[05] ������ ���� ���� �����; ������������� ��������� ������� 5.4.6�.

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

\ex[47]\exhead(󑒎������ ���������� � ����������� �������.) ㎂����, ��� 
�������� ���������� ������� \emph{����������� ������}, ���� �� ���������� ��� 
����� ���������� ������ $O((\log N)^2)$ ����� ������ ����� ������������, 
���������� ��� ���������� $N$ �������. �������� ������ ���� ����� � ��� ������, 
��� ������ �������� ��� ����� $N$, � �� ������ ��� ������������ �������� $N$, 
����, �������, ��������������, ��� ��� ������ ��������� ��� ���������� ��� 
�������������� ����������� ���������� ������ � ������������ ��������. � ������ 
�� ��������� ���� ���������� ���������� ��� ���������� ����������� ������ 
����������; � ���������, ��������� ������������� $N$ ����� �����. ᛑ���� 
���������� (�������� 5.2.2Q) ������������� ���������� ����������� ������, �� 
�� ����� ������ � ��������� ������ ��������������� $N^2$. ���������� 
���������� (�������� 5.2.3�) �������� ������������ ����� ��������� ���� 
���������� ���� $O(N\log N)$, ������� ���������� ����������� ������, ���� ����� 
�������������� � ��� ���� �������� ��������, ���� ������������ ���� �� 
���.~5.2.4--18.

񀌛� ������� ����� ����������, ��������� ����, ������� \emph{���������} 
��������� �����, �������� ����� ������� ������� (�������� 5.2.4L), ������ �� 
���������� �� ����������� ������. 􀊒������ ������������� ����������� 
����������� ���������� � ����������� �������, ������� �� ������, ���� ������ 
���� $O(N^2)$ (������� �������, ����� �������� � �������� �������� ������).

񓙅������ �� ���������� �������� ���������� � ����������� �������, ��������� 
����� $O(N^2)$ ������ ������� � ��������� ������ ��� � �������?

\epigraph
� ������ ����� ����., ����. ������������� � ������ � ���������� 
������� ���� �� ���� ���� ��������� ��������� � ����������, 
������� �������� �� ��������� ��������� ���.
\signed �. �. ������ (1955)

%% 464
\chapter{��}
\epigraph
��� ������
\signed {�� 񌈒 (1928)%
\note{1}{񌈒, ������� ��������� (1873--1944) --- ������������ 
������������ �������.---{\sl �. �����.}}
}

��� ����� ����� ���� ������� �����: ��� ������������---"�������� � ������� 
����������", ��� ������---"�� �� ��������". 퀑 ����� ������������ ������� 
���������� ���������� � ������ �������������� ������ � ����������� �������� 
����� ������� ����������� ���� ����������. 荎��� �� ������������ �� ����� 
������� ������� ������, ��� ������� ������������ �� ��� �� �����. � ���� ������ 
����� ������ ���� �� ������ � ��������� ������� �� �����; �� ������� ������ 
����� ��������� � ��� ������������ ��������� �����, ����� ���������� 
������������� �� �������.

��� ����� ��������� � �������� �������� ����� ������� ��������� ������: ��� 
�������� ������, ���������� � ������������ ��������������. 퀏�����, � 
�������������� ������ ��� ����� ������������ ����� $f(x)$, ���� $x$ � ������� 
�������� ������� $f$; � ��������������� ����� ������������ ���������� 
���������� ������� �������� �����.

⎎��� ����� ������������, ��� �������� ��������� �� $N$ ������� � ���������� 
���������� ��������� ��������������� ������. ꀊ � � ������ ����������, 
�����������, ��� ������ ������ �������� ����������� ����, ������� ���������� 
\emph{������}, ��������, ������, ��� ������ ���� ��������� ������ ����� ������� 
�� ����� ����� ������. � ������ �������, ����� $N$ ������ ���� ��������, ��� 
��� ������ ���� ���������� ���������� ���� ������. 񎂎�������� ���� ������� 
���������� \dfn{��������} ��� \dfn{������}, ������ ��� ��������, ��� �������, 
���������������
%% 465
��������� ����, � ������ ������ �������� ������� �������. ᎋ���� ����, ��� 
������ ������, ����� ���������� \dfn{����� ������}.

� ���������� ������ ������������ ��� ���������� \dfn{�������� ������ $K$}, � 
������ ������� � ��������� ������, ������� $K$ ����� ������. 񓙅������ ��� 
����������� ��������� ������: ���� ����� �������� \dfn{�������}, �. �. �������� 
���������� ��������� ��������������� ������, ���������� $K$, ���� �� �������� 
\emph{���������}, �. �. �������, ��� �������� $K$ �� ����� ���� ������ �� � 
����� �� �������. �� ���������� ������ ������ ���������� �������� � ������� 
����� ������, ���������� $K$; ��������, ������� ������ ���, ���������� 
���������� "������ � ��������". 텊������ ����������� ����������, ��������� ��� 
"������������� ������", ������ �������� ������ ������������� ���������� 
����, ��� ��� ������ ������������ ����; �� �� ����� ������� ������ ������ �� 
������� ������������� �������������� ������.

���� ����� ������ �������� ����������, ������� ���������� � ������, 
��������������� � ������ $K$, � ���������� ���� ����� ������ ������������ ���, 
����� ���������� ������. � ����� ����, ���� ��������� $K$ ����������, 
��������������� ������ ����� �����. 퀏�����, ���� $K$ ���������� � 
������~$|TABLE|+i$, ��������������� ������ (��� ��������� �� ���) ����� 
���������� �� ������ $|TABLE|+i+1$, ��� $|DATA|+i$ � �. �. 򀊈� 
�������, �����������, ���������� ����, ��� ����� ������, ����� ������ ���� $K$, 
����� �������� ��������.

� ������ ���������� ����� ������� ���������� ��������� ������, ��� ��� ������ 
������� ������ ������ �� ������� ����� ����� � ������������� ���������� �������� 
������. 䅉����������, ������� ������� ��� ������������ ������ ��� ��������� 
������, ��� ����� ��������� �����������, �. �. �� ������ ����� �������, ��� 
��������� ������ ��� ����������. 񂟇����� ������ �������� ������������ ������� 
���������� �����; ��������, � ������ � ����� ������� ��� ������������� ������ 
�������, ��������� �� ������ ��� �������������� ���. 䐓��� ������ �������� 
������ ����������� ����� ����, ���� ������������� ������� ������ ������. 
񄅋��� �� ������� $\{1,2, \ldots, N\}$, � ����� ������, ���������� $K$, ����� 
���� ������ �������� � ������ $|TABLE|+K$.  ��� ������� �������������� ��� 
���������� ������ �� ��������� �������������� ����������, �������������� � 
�.~2.2.3. � �� ����� �� ������ ������� ����� ��������� (��������, ����� 
��������� �������������� ���������� �������� ������������� �����, � �� �����), 
��� ��� ������ ����� ����� ����������� ��������� ������.

셒��� ������ ����� ���������������� ����������� ���������. � ����� �� 
��������� �� �� ���������� � �������
%% 466
����� � ������������ � ����������� ���������� ���������� � ��.~5 �� ���������� 
� ������� ����������. 苈 �� ����� �� ��������� ����������� � ������������ 
������ ������, ��� "�����������" ��������, ��� ���������� ������� �������� 
���������� (��� ��� ����� �������������� ����� ������, ����������� ��������� �� 
����������� �������), � "������������" ��������, ��� ������� �������� �������� 
������ ������� (�, ����� ����, ��������). 򐅒�� ��������� ����� �������������� 
������ ������ � ������������ � ���, �������� �� ��� �� ��������� ������ ��� �� 
�������� ��������� ������, ���������� ����, ��� ����������� ���������� � 
������� ��������� � ���������� � ������� �������������. 퀊����, �� ����� �� 
��������� ������ ������ �� ������, ������������ �������� �����, � �� ������, 
���������� � ���������������� �������.

�������� ������ ����� ����. � ��������, ���������� ���� ��������� �������� 
�������������. � \S~6.1 ��������������� ������ ����������������� ������ "� ���", 
� � \S~6.2 ����������� ���������, ������� ����� �������� �� ������ ��������� 
����� ������� � �������������� ����������� ��� ��������� ������� ��� ���������� 
���������. � \S~6.3 ��������������� �������� �����, � � \S~6.4 ����������� 
������ ����� �������, ���������� ������������ � ���������� �� �������������� 
��������������� �������� ������. � ������ �� ���� ���������� ��������������� 
��� ����������, ��� � ������� �����, � ��� ������������ � ��� ������������� 
�������; � ������ ��������� ���������� ������������� ����������� � ���������� 
��������� ����������.

셆�� ������� � ����������� ���������� ������������ �����������. 퀏�����, 
���������� ��������� ������:
$$
\displaylines{
\hbox{䀍� ��� ��������� �����:}\cr
\hbox{$A=\{a_1, a_2, \ldots, a_m\}$ � $B=\{b_1, b_2, \ldots, b_n\}$;}\cr
\hbox{����������, �������� �� $A$ ������������� $B$, 
�.~�. $A\subseteq B$.}\cr
}
$$
퀏���������� ��� �������, � ������:
\enumerate
\li 񐀂������ ������ $a_i$ ��������������� �� ����� $b_j$ �� ������������ 
    ����������.
\li 񂅑�� ��� $b_j$ � �������, ����� ������ ������ $a_i$ �� �������.
\li 󏎐������� $A$ �~$B$, ����� ��������� ���� ���������������� ������ �� 
    ����� ������, �������� ��������������� �������.
\enumend
\noindent ꀆ��� �� ���� ������� ����� ���� ��������������� ������� ��� 
��������� ���������� �������� $m$ � $n$. 䋟 ������� 1 ����������� 
�������������� $c_1mn$ ������ �������, ��� $c_1$---��������� ���������, � 
������� 3 ������ ����� $c_2(m \log_2m+n\log_2n)$ ������, ��� $c_2$---��������� 
(�\'������) ���������.  ����������
%% 467
������ ����������� ������� 2 ��������� �������� $c_3m+c_4n$ ������ �������, ��� 
$c_3$ �~$c_4$---��������� (��� �\'������) ���������. 񋅄���������, ������� 1 
������ ��� ����� ����� $m$ �~$n$, � ��� ����������� $m$ � $n$ ������ ����� 
������� 3. 瀒��, ���� $n$ �� ��������� �������� ���������� ������, ����� 
��������������� ������� 2; ����� ����� ������ ������� 3 ����� ���������� �����, 
���� $n$ �� ��������� ��� ������� �������. 獀���, �� ����� ��������, ��� 
���������� ������ ������ �������� �����, � �����---����������.

瀗����� ������� ������ ������ ����� ������ � ����� ������� �������, 
��������������� �����. 퀏�����, �����������, ��� � ���� ������ ��������� �����, 
������� ����� ���� ������ ��������; �� ������ �� ����� ���������� ������, 
�������� �� ��� ������. 呋� ������� ��� ����� �����, � ����� �� ������� ����� 
����������� � ������� ���������� �������, � � ������ ��� ����������� ������ 
������ (��� ���� �� ����� ���� ��������� ��������), ���������� �������� ������ 
� ����������� ������� ��������� �� �������� ����� ����� ��� ������ � ������� 
������ �� ���� ���� ������. 셒��� ������, ������������ � \S~6.2 �~6.3, �����, 
�������������, ������������ ��� ���������� �����, ������� ���, ��������, 
�������.

���� ������ ��������� � ���� �������� �������� � ����� � ��������� ������ 
���������������� ������ ����������� � � ����� � ������� ������������, ����� 
���������� ������������ ����������� ��������� ����� �������� ��-�� 
�������������� ������� ��� ������ ����������. 퓆�� ���� ����� �������������� 
��������� � ����� ���, ���������� ������ ��� �������� ������� �����. 셒�� 
"Soundex", ����������� ���� � ����, � ������� �� ����������� ������, ��� 
������������� ������ 쀐����� �.~��� � �������� �.~�������� 
[��. U.~S.~Patents 1261167 (1918), 1435663 (1922)]; �� ����� ������� ���������� 
��� ����������� �������.
\enumerate
\li ����� ������ �����; ��� ����� �, �, h, i, �, u, w, �, ������� �� ������ 
    ������, ����������.
\li ������� ������ (����� ������) ��������� ��������� ��������:
$$\matrix{ 
b, f, p, v \to 1; \hfill & l \to 4;\hfill \cr 
c, g, j, k, q, s, x, z \to 2; &  m, n \to 5;\cr
d, t \to 3; \hfill & r \to 0.\hfill\cr
}
$$
\li 呋� � �������� ����� (����� ����� 1) ����� ������ ��������� ���� � 
    ����������� ������, ���������� �����, ����� ������ �� ���� ������.
\li 䎏������ � ������ ���������� ���� ��� ������� ������ �����, ������������� 
    ���������� ��������� � ����� "�����, �����, �����, �����".
%% 468
\enumend
\noindent 퀏�����, ������� Euler, Gauss, Hilbert, Knuth, Lloyd 
�~{\L}ukasiewicz ����� ���� �������������� �460, G200, H416, K530, L300, L222. 
����������, ����� ������� �������� ������ �� ������ �����������, �� � 
���������� ��������� �����. �������� ���� ����� ����� ����� ���� �������� �� 
������� Ellery, Ghosh, Heilbronn, Kant, Ladd � Lissajous. � ������ �������, 
����� ����������� �����, ��� Rogers � Rodgers, Sinclair � St.~Clair ��� 
Tchebysheff � Chebyshev, ����� ������ ���������. �, ������ ������, ������� 
"Soundex" ������� ����������� ����������� ���������� ��� ��� ����� �� ��� 
�����. [䋟 ����������� ������������, ��. 
�. �. Bourne, D. F. Ford, {\sl JACM\/}, {\bf 8} (1961), 538--552; 
Leon Davidson, {\sl CACM\/}, {\bf 5} (1962), 169--171; 
Federal Population Censuses, 1790--1890 (Washington, D. �.: National Archives, 
1971), 90.]

ꎃ�� �� ���������� ������� ���� "Soundex", ��� ������������� ������������, ��� 
��� ����� ��������; ����� ��������� ������ �� ������� � ������������ ������, 
������������ ������ ������ ��� ������ ������.

 ������������� ������� ��� ������ ������� ���������� ������� �����������, 
��� ��� ����� ���������� ������������� ��������� ���� ������ ������ ��� 
������������� �����. 焅�� ����� ����� �������� ������ �� �������� �������� 
����������. 퀏�����, ���� ������� ���� �������, �������� ��� �� �������� 
����� ���� ��������� ������ � �������� 25--30 ���, ������ ��������� � ��������� 
� ����������� ��������; � ����������� ���������� ����� ���������� ������� 
���������� � ������� ����� ����������� ���������� ����� ����� �����, ��������� 
���������-������� ������� "ꐀ�������� �� ����������" � ������� ������� 
�������� �������� ��� �� 1964~�. 茅� ������� ���� ������ � ���-����, 
���� ����� �������� ������� ������������ ���������. � ����� ���� �� ����� �� 
������������� ������ ���������� ��� ���� ������, � ������� ����� ������ ����� 
��� ���������� � ������� ����������. ₅����� � ������ 
\emph{������ �� ������ ���������} �������� � \S~6.5.

��� ��� ���������� � ���������� �������� ������, ������� ����������� 
������� ������� �������. � �������������� ������ ���� ���������� ��������� 
����� ���������������, ������������������ � ������ ������, ��� ��� 
�������������� ���������� ����� ���� �������� �������. �� ��� ������� ���� 
���������� �� ���������� � �������������� ��� ������� ����� ����������� 
������������, �������������� � ����������� ������������� �����. ��� ����� 
��������� ��� � ������������ ���������� ����� ��������, ��� ������� ������ ��� 
��������� $\log x$ �~$\cos x$, ������ ������ ����� �� �������.

텑����� �� ��, ��� ������ ���������� ��������� �����������
%% 469
�������� ��� �� ���� �������� ���, ��� ���������� ���������� ������ ���� 
������� ������������ ����. ���������� ��������� ���������� ������� � ������ 
����������������� ������������ ���� ���� ��� �������� ������� ������, 
������������ ����� ���� ���� ���������� ����������, ���� ����� ����������.

� �������� ��� ������� � ������� ������ �� ��������� �������� � ������� 50-� 
����� ������� � ��������� ����, ��� ����� ��� ������� �������� ���������� 
�������. �� ������� ����� �� ������������ ������� ������������ � ������ 
������� ������������ ����� ����������� � ����� ������� ������, ������� ��� �� 
����� ���������� ������������.

��� ������ ����� ������ ���� ������������ 
�.~�.~䓌� [{\sl Computers \& Automation\/}, {\bf 5}, 12 (December 1956), 6--9], 
�.~�.~������� [{\sl IBM J. Research \& Development}, {\bf 1}  (1957), 130--146], 
�.~�.~ᓒ�� [{\sl Information and Control\/}, {\bf 1} (1958), 159--164], 
�.~�.~䓃����� [{\sl Comp. J.\/}, {\bf 2} (1959), 1--9]. 
ᎋ�� ��������� ����� ������ ������� 
�.~�.~���������� [A Programming Language (New York: Wiley, (1962)), 133--158] � 
�.~ᓕ������� [{\sl IBM Systems J.\/}, {\bf 2} (1963), 86--111].

� ������ 60-� ����� ���� ����������� ��������� ����� ���������� ������, 
���������� �� ������������� ����������� ��������; � ���� �� ������������ ����. 
� � ���� ����� ������� �������� ������������ �� ��������� ������.
%% 470
\subchap{������������� �����}
"퀗�� � ������ � �����������, ���� �� ������� ������ ����; ����� ����������". 
򀊀� ���������������� ��������� �������� ��������� �������� ������; ������ 
������ ���� ������������ � ���, ��� ��� �� ��� �������� ������ ����� ������� 
���������. 텑����� �� ���� ��������, ���������������� ����� �������� ��� 
����� ���������� ����.

񔎐�������� �������� ����� �����.
\alg S.(������������� �����.) 茅���� ������� ������� 
$R_1$, $R_2$, \dots, $R_3$, ���������� �������������� ������� 
$K_1$,  $K_2$, \dots, $K_n$ �������� ������������ ��� 
������ ������ � ������ ������ $K$. �����������, ��� $N\ge 1$.
\st [퀗������ ���������.] 󑒀������ $i \asg 1$.
\st [񐀂�����.] 呋� $K=K_i$, �������� ������������ ������.
\st [��������.] 󂅋����� $i$ �� 1.
\st [ꎍ�� �����?] 呋� $i\le N$, �� ��������� � ���� \stp{2}.
� ��������� ������ �������� ������������ ��������. 
\algend

瀌����, ��� � ����� ��������� ����� ���� ��� ������ ������: \emph{�������} 
(����� ������� ��������� ������� �����) � 
\picture{������������� �����}
\emph{���������} (�����, �����������, ��� �������� ��������� ��� � �������). 
��� ����������� ��� ����������� ���������� ������ �����.

���������� � ���� ��������� ��� ������ MIX ��������.
\prog S.(������������� �����.) ��������, ��� $K_i$ �������� �� ������ 
$|KEY|+i$, � ���������� ����� ������ $R_i$---�� ������ $|INFO|+i$. 
������� ���� ��������� ���������� $|rA|\equiv K$, $|rI1|\equiv i-N$.
%% 471
\code
START     &  LDA     & K           & 1    & S1. 퀗������ ���������. 
          &  ENT1    &             & 1    & $i\asg 1$.
2H        &  ����    & KEY+N, 1    & �    & S2. 񐀂�����.
          &   JE     & SUCCESS     & �    & ⛕��, ���� $K=K_i$. 
          & INC1     & 1           & C-S  & S3.��������.
          & J1NP     & 2�          & C-S  & S4. ꎍ�� �����? 
 FAILURE  &  EQU     & *           &1-S   & ⛕��, ���� ��� � �������. 
\endcode
� ������ |SUCCESS| ����������� ������� "|LDA INFO+N,1|";
��� �������� ������ ���������� � |rA|.
\progend
������ ������ ��������� �� ������������ �����; �����, ��� ����� ������ 
��������� S ������� �� ���� ����������:
$$
\eqalign{
C=&\hbox{ (���������� ��������� ������)};\cr
S=&1\ \hbox{��� ����� � 0 ��� �������}.\cr
}\eqno (1)
$$
������ S ������� $5C-2S+3$ ������ �������. 呋� �� ����� $K=K_i$, 
�� $C=i$, $S=1$; ������, ������ ����� ����� $(5i+l)u$. 呋� �� ����� 
�������� ���������, �� $C=N$, $S=0$, � �������� ��������� ����� $(5N+3)u$. 
呋� ��� ����� ��������� �� ���� � ������ ������������, �� ������� 
��������~$C$ ��� ������� ������ ����������
$$
{1+2+\cdots+N\over N}={N+1\over 2};
\eqno(2)
$$
������������������ ���������� $C$, ����������, �������� �������---�������� 
$0.289N$ (��. ���. 1).

��������, ��������, ����������, ������ ���� �������������. � ���� ��� 
�����, ��� ���� ������ ���������� ����������������� ������ �� ������ ����� 
������! ������ ��������� ��������� ������ ��������� (���� ������ ������� 
�� ������� ����):

\alg Q.(ᛑ���� ���������������� �����). � ������� �� ��������� S ����� ��� 
��������������, ��� � ����� ����� ����� ��������� ������ $R_{N+1}$.
\st [퀗������ ���������.] 󑒀������ $i\asg 1$  �~$K_{N+1}\asg K$.
\st [񐀂�����.] 呋� $K=K_i$, �� ������� �� \stp{4}.
\st [��������.] 󂅋����� $i$ �� 1 � ��������� � ���� \stp{2}.
\st [ꎍ�� �����?] 呋� $i\le N$, �������� ������������ ������;
� ��������� ������---�������� $(i=N+1)$.
\algend

\prog Q.(ᛑ���� ���������������� �����.) 獀����� ���������: 
$|rA| \equiv K$, $|rI1|\equiv i-N$.
%%472
\code
 BEGIN   & LDA   & �       & 1     & Q1. 퀗������ ���������
         & STA   & KEY+N+1 & 1     & $K_{N+1}\asg K$.
         & ENT1  & -N      & 1     & $i\asg 0$.
         & INC1  & 1       & C+1-S & Q3. ��������.
         & ����  & KEY+N, 1& C+l-S & Q2. 񐀂�����.
         & JNE   & *-2     & C+1-S & � Q3, ���� $K_i\ne K$.
         & J1NP  & SUCCESS &   1   & Q4. ꎍ�� �����?
 FAILURE & EQU   & *       & 1-S   & ⛕��, ���� ��� � �������.
\endcode\progend
葏������ ��������� $C$ �~$S$, ��������� ��� ������� 
��������� $S$, ����� ���������, ��� ����� ������ ��������� 
����������� �� $(4C-4S+10)u$; ��� ���� ��������� ��� $C\ge5$ 
(��� �������� ������) � ��� $N\ge 8$ (��� ���������� ������).
 �������� �� ��������� S � ��������� Q ����������� ������ ���������� 
�������: ���� �� ���������� ����� ��������� ����������� ��� ��� ����� �������, 
����� ����������� �������� ��� ������ ���� ���������.
񓙅������ ������ ������� ��������� Q \emph{���} �������.
\prog Q'.(񂅐�������� ���������������� �����.) 獀����� 
���������: $|rA|=K$,  $|rI1|\equiv i-N$.
\code	
 BEGIN   &LDA   &�           &1        & Q1. 퀗������ ���������.
         &STA   &KEY + N +1  &1        &$K_{N+1}\asg K$. 
         &ENT1  &-1-N        &1        &$i\asg -1$. 
3H       &INC1  &2           &\lfloor(C-S+2)/2\rfloor & Q3. ��������. (䂎����.) 
         &����  &KEY+N, 1    &\lfloor(C-S+2)/2\rfloor & Q2. 񐀂�����.
         &JE    &4F          &\lfloor(C-S+2)/2\rfloor & � Q4, ���� $K=K_i$. 
         &����  &KEY+N+1,1   &\lfloor(C-S+1)/2\rfloor & Q2. 񐀂�����. (񋅄�����.) 
         &JNE   &3B          &\lfloor(C-S+1)/2\rfloor & � Q3, ���� $K\ne K_{i+1}$. 
         &INC1  &1           &(C-5)\bmod 2            &������� $i$.	
4H       &J1NP  &SUCCESS     &       1                & Q4. ꎍ�� �����? 
FAILURE  &EQU   &*           &1-S                     &⛕��, ���� ��� � �������. 
\endcode
\progend
荑������� ����������� ����� �������� ������; ��� ��������� �������� �������� 
���������� "$i\asg i+1$". 򀊈� �������, ����� ���������� ��������� ����������� 
��
$$
3.5C-3.5S+10{(C-S)\bmod 2\over 2}
$$
������.  ������ �� ������� �������� ��������� Q' �� 30\% ������� 
��������� S; �������� ������� ����� ���� �������� ������ ������������ 
���������. 呋� ��������, ��� ����� ����������� � ������������ �������, 
������� ��������� �������� ��������.

%% 473
\alg �.(������������� ����� � ������������� �������.) 茅���� ������� 
������� $R_1$, $R_2$, \dots, $R_N$, ������ ����� ������������� ������������ 
$K_1<K_2<\ldots<K_N$. �������� ��������������� ��� ������ ������� ����� $K$. 
� ����� �������� � ���������� �������� ������ ��������������, ��� � ����� 
������� ����������� ��������� ������ $R_{N+1}$, ���� ������� 
$K_{N+1}=\infty>K$.
\st [퀗������ ���������.] 󑒀������ $i\asg1$.
\st [񐀂�����.] 呋� $K\le K_i$, �� ������� �� \stp{4}.
\st [��������.] 󂅋����� $i$ �� 1 � ��������� � ���� \stp{2}.
\st [���������?] 呋� $K=K_i$, �� �������� ������������ ������.
� ��������� ������---��������, ������ ������ � ������� ���.
\algend

呋� �������� $K$ � ������ ������������ ��������� ��� ��������� ��������, �� � 
������ �������� ������ �������� T, �� ��������, �� ����� ��������� Q. ��� 
���������� ������ ������ �������� � ��������� ���������� �������� � ��� ���� 
�������.

�������� ���� ��������� � ����� �������� ������������ ��������� ����������� 
��� ��������� �������; ����������� ��������� ��������� � � �������� � ��������� 
�������������, ��� ��� � ��� ������ ���� ����������� ���������������. 
(�. ���.~2, 3 � 4.)

\section ������� ���������. � ��� ��� ��������������, ��� � ������ 
������������ ����� ������������� ����� ������ ���������, ������ ����� ����� 
������������� �� ����������; ������ ������, ���� $K_j$ ����� ������������� � 
������������ $p_i$, ��� $p_1+p_2+\cdots+p_N=1$. ␅�� �������� ������ ��� 
������� $N$ ��������������� ����� ��������� $C$, ������� .�������� �������� 
�����
$$
\overline{C}_N=p_1+2p_2+\cdots+Np_N.
\eqno(3)
$$
�� ���� ����������� �������� ������ � ������� � ����� �������; ����� 
�������� $\overline{C}_N$  ���������� ���
$$
p_1\ge p_2\ge \ldots \ge p_N,
\eqno (4)
$$
�. �. ����� �������� ����� ������������ ������ ����������� � ������ �������.

������, ��� ���� ��� ����� "�����������" ������������ ��� ��������� 
�������������� ������������. 呋� $p_1=p_2=\ldots=p_N=1/N$,  �� ������� (3) 
�������� � $\overline{C}_N=(N+1)/2$, ��� ��� ���� �������� ���� � (2). 
�������� ������, ���
$$
p_1={1\over2}, p_2={1\over 4}, \ldots, p_{N-1}={1\over2^{N-1}}, p_{N}={1\over2^{N-1}}
\eqno(5)
$$
%% 474
񎃋���� ���. 7, $\overline{C}_N=2-2^{1-N}$; ������� ����� ��������� 
������ ����, ���� ������ ����������� � ���������� �������. 䐓��� 
��������������� �������������� ��������
$$
p_1=N_c, p_2=(N-1)c, \ldots, p_N=c,
$$
���
$$
c=2/N(N+1).
\eqno(6)
$$
��� "�����������" ������������� ���� ����� ��������� ���������
$$
\overline{C}_N=c\sum_{1\le k\le N} k\cdot(N+1-k)={N+2\over 2};
\eqno(7)
$$
����������� ������������ �������� ����� ����� ���������� �������, 
������������ ��� ������� � ��������� �������.

����������, ������������� (5) �~(6) �������� ������������, � �� ������ 
������� ������� ������������ � ����������������. ᎋ�� �������� ������� 
���� "����� 爏��":
$$
p_1=c/1, p_2=c/2, \ldots, p_N=c/N, \rem{��� $c=1/H_N$}.
\eqno (8)
$$

��� ������������� �������� ����������� ��������� 
�.~�~爏��, ������� �������, ��� $n$-� �������� ��������������� � ������ 
�� ������������ ����� ����� ����������� � ��������, �������������� ������� 
���������������� $n$. 
[The Psicho-Biology of Language (Boston, Mass.: Houghton Miffling, 1935);
Human Behavior and the Principle of Least Effort (Reading, Mass.: 
Addison-Wesley, 1949).] ����������� ������� ���������� �� � �������� 
��������; ��� ��������� ������ ����������� � ������� �������� ���������. � 
������, ���� ������� ������ � ������� ����������� ������ 爏��, �����
$$
\overline{C}_N=N/H_N;
\eqno(9)
$$
����� �� ������ ����� �������� � ${1\over2}\ln N$ ��� �������, ��� ��
����������������. [�. � A.~D.~Booth et al. Mechanical Resolution of 
Linguistic Problems (New York: Academic Press, 1958), 79.)

䐓��� �������������, ������� � ���������, ���� ������� "80--20", ������� 
����� ����������� � ������������ ����������� [��. � W. P. Heising, 
{\sl IBM Systems J.\/}, {\bf 2} (1963), 114--115]. ��� ������� ������, ��� 80\% 
������ ������� ��� �������� �������� ������ ����� ��������� 20\%; ��� 
��������� � � ���� 20\%, ��� ��� 64\% ������ ������� � �������� ��������� 
4\% �����, � �. �. 荛�� �������,
$$
{p_1+p_2+\cdots+p_{.20n}\over p_1+p_2+p_3+\cdots+p_n}
\approx 0.80 \rem{��� ���� $n$}.
\eqno (10)
$$
%% 475
⎒ ���� �� �������������, ����� ��������������� ������������ ������� 
��� $n$, ������� 5:
$$
p_1=c, p_2=(2^\theta-1)c, p_3=(3^\theta-2^\theta)c, \ldots, 
  p_N=(N^\theta-(N-1)^\theta)c,
\eqno(11)
$$
���
$$
c=1/N^\theta; \theta={\log 0.80 \over \log 0.20}=0.1386.
\eqno(12)
$$
䅉����������, $p_1+p_2+\cdots+p_n=cn^\theta$  ��� ����� $n$. � 
������������� (11) �� ��� ������ ��������; �����, ������, 
$n^\theta-(n-1)^\theta)=\theta n^{\theta-1}(1 + O(1/n))$, �.�. ���������� 
����� ������� �������������, ����������� ��������������� ������� "80--20":
$$
p_1=c/1^{1-\theta}, p_2=c/2^{1-\theta}, \ldots, p_N=c/N^{1-\theta},
\rem{��� $c=1/H_N^{1-\theta}$}.
\eqno (13)
$$
焅��, ��� � ������, $\theta= \log 0.80/\log 0.20$, a $H_N^{(s)}$ ���� 
$N$-e ������������� ����� ������� $s$, �. �. $1^{-s}+2^{-s}+\cdots+N^{-s}$. 
瀌����, ��� ��� ������������� ����� ���������� ������������� 爏�� (8); 
����� $\theta$ ���������� �� 1 �� 0, ����������� ��������
�� ���������� �������������� � ����������. (� ����� ����,
爏� �����, ��� $\theta\approx {1\over 2}$ � ������������� ������ �������.)
����� (3) � (13), �������� ��� ������� "80--20" ������� ����� ���������
$$
\overline{C}_N=H_N^{(-\theta)}/H_N^{(1-\theta)}
 ={\theta N \over \theta+1}+O(N^{(1-\theta)})\approx 0.122N
\eqno (14)
$$
(��. ���. 8).

�. �. �����, ��������� ������� ��������� ���� [��. ���������� ������ �� 
���. 422 � {\sl JACM\/}, {\bf 10} (1963)], ��������� ����� ���������� 
��������� ���'������ 爏��:
$$
p_1=c/1^{1+\theta}, p_2=c/2^{1+\theta}, \ldots, p_N=c/N^{1+\theta},
\rem{��� $c=1/H_N^{1+\theta}$},
\eqno (15)
$$
��� ����� \emph{�������������} $Q$. [� ��������� � (13) ����� ������� 
���� $\theta$.] � ���� ������
$$
\overline{C}_N=H_N^\theta/H_N^{(1+\theta)}
  =N^{1-\theta}/(1-\theta)\zeta(1+\theta)+O(N^{1-2\theta}),
\eqno (16)
$$
��� ����������� ������, ��� (9) ��� $N\to\infty$.
\section "񀌎��������������" ����. ������� ���������� ������, �� � 
����������� ������� ������������� ������������ ��� �� ��������. � ����� 
�� � ������ ������ ������� ������� ����� ���������, ����� �� ��������� 
��������� ��������� ��������������� ������. ⛂������� ������� 
����������, ��� ����� ��������� ����� �������� � �������� ��������. � ��
������
%% 476
���������� �������� ����� ������ ��� ��������, ��� ��� �� ����� 
������������ ����� ����������� (��������, �������� ������ ������ ������, 
���������� ���� � ������ �����).

���� �����, ������������� ������� �� ��������, ������������ ��� 
������ ����.  ��������� �������� ������ ����������� ������ ��� 
��������������� ����� ��� ���������:
����� �� ������� ������ ������, �� �������� �� � ������ �������. ����� 
����� ����� �����������, ����� ������� ������������ � ���� ���������� 
��������� ������: ���� ����� ��� ������ ����� ����������� �������� 
��������� ������.

脅� "�������������������" ������ ������� � ���, ��� ����� ������������ 
�������� ����� ����������� �������� ������ � ������ �������. �� $N$ 
������ ������������� � ������������� $\{p_1, p_2, \ldots, p_N\}$ 
��������������, ������ ������ ����� ����������� ��������� 
\emph{����������} �� ����������. 쎆�� ��������, ��� ������� ����� 
��������� ��� ���������� ������ � ����� ������������������ ����� ��������� 
� ����������� ��������
$$
\overline{C}_N=1+2\sum_{1\le i < j \le N}{p_ip_j\over p_i+p_j}
={1\over 2}+\sum_{i, j}{p_ip_j\over p_i+p_j}.
\eqno (17)
$$
(�. ���. 11.) 퀏�����, ���� $p_i=1/N$ ��� $1\le i \le N$, 
������������������ ������� ������ ��������� � ��������� �������, � 
(17) �������� � ��������� ��������� $(N+1)/2$, ����������� �����.

������, ��� ������������������ ��������� �������� ��� ������������� 
������������ �� ������ 爏�� (8). 茅��
$$
\eqalign{
\overline{C}_N&={1\over 2}+\sum_{1\le i, j\le N}{(c/i)(c/j)\over c/i+c/j}
    ={1\over2}+c\sum_{1\le i, j\le N}{1\over i+j}=\cr
&={1\over2}+c\sum_{1\le i\le N}(H_{N+i}-H_i)
   ={1\over2}+c\sum_{1\le i\le 2N}H_i-2c\sum_{1\le i\le N}H_i=\cr
&={1\over2}+c((2N+1)H_{2N}-2N-2(N+1)H_N+2N)=\cr
&={1\over2}+c(N\ln 4-\ln N+O(1))\approx\cr
&\approx 2N/log_2N.\cr
}
$$
(��. ������� (1.2.7--8,3)). ��� ������� �����, ��� � $N$ ��� ���������� 
������� $N$, � ���� � $\ln4\approx 1.386$ ��� ����, ��� ����� ��������� 
��� ����������� ������������ ������� (��. � (9)).

������������, ������������� � ��������� �������� � ������������, 
��������, ��� ������������������ ����� �������� ���� �����, ��� 
������������� (18), ��� ��� ������� ������
%% 477
�� ���������� (��������� ������ ������ ����� ���������� ������).

񕅌�, �������� ������������������, ������� �. ��� � �.~�.~䀓�� 
[{\sl SIAM J.  Appl. Math.\/}, {\bf 15} (1967), 874--888.]

\section �� �� ����� ����� ������� ��������� �����. ���������� ������ 
���� ������ � ���� �������. �� �������, �� ������� ������������ �����,
 �������� �� ����� � ������ ����� ��������� �����. 녍�� � ��������� 
����������� � ������ ������������ �������� ������ �������� ������ �����. 
񒀍������� ��������� �������, �����, ��� �����������, ������������, 
����������, ���������� ������� � �. �., �������� "��������" �� �����, � 
����������� ���������������� ����� ������ ���� ���������� � ������ ������ 
���������. 򀊀� ���������� ������ ������ ������������ ���������� 
������ ��������� S: ������ ��� S3 ����������� �� ��������� ���������� 
�������. 獀���, ��� ����� ������������ �� ������ ����� ���������.

������ ����� $L_i$ ����� ������ $R_i$, � ����� $p_i$, ����������� ����, 
��� ��� ������ ����� ������������. ␅�� ������ ������ �������� 
��������������� ��������
$$
p_1L_1+p_2(L_1+L_2)+\cdots+p_N(L_1+L_2+\cdots+L_N).
\eqno (19)
$$
 $L_1=L_2=\ldots=L_N=1$ ���, ��������, �������� � ���������� ������ (3).

ꀆ���� �������� ��������� �������� ������ ������ � ������ �����, �� ����� 
������� ����� �������� ���. 䅉����������, ����� �� ����� �������� ����� 
��� ���������---$A$ � $B$. ������ $A$ ��������� � ��� ���� ���� $B$, �� 
������� $B$ � ������
����, �. �. $N=2$, $p_A={2\over3}$, $L_A=4$, $p_B={1\over3}$, $L_B=1$. 
呋� ��, ������ "������", �������� $A$ �� ������ �����, �� ������� �����
������ �������� ${2\over 3}\cdot4+{1\over3}\cdot 5={13\over3}$; �� ���� 
��������� "���������",
���������� � ������ $B$, �� ��������� 
${1\over3}\cdot1+{2\over3}\cdot5={11\over 3}$.
񋅄����� ������� ��������� ���������� ����������� ������������ 
������������ �������� �� �����.
\proclaim 򅎐��� S. �� $L_i$ � $p_i$, ����������, ��� � ������. 
���� ������� �� ����� ��������� ����� � ������ �����, �����
$$
p_1/L_1\ge p_2/L_2\ge \ldots \ge p_N/L_N.
\eqno (20)
$$

荛�� �������, ������� ���������
$$
p_{a_1}L_{a_1}+p_{a_2}(L_{a_1}+L_{a_2})+\cdots
 +p_{a_N}(L_{a_1}+\cdots+L_{a_N})
$$
%% 478
�� ���� ������������� $a_1$ $a-2$ \dots $a_N$ ����� $\{1,2,\ldots, N\}$ 
����� (19) ����� � ������ �����, ����� ����������� (20).

\proof ��������, ��� $R_i$ � $R_{i+1}$ ���������� �������; �������� 
(19), ����� ������
$$
\cdots+p_i(L_1+\cdots+L_{i-1}+L_i)+p_{i+1}(L_1+\cdots+L_{i+1})
+\cdots,
$$
������ ��������� ��
$$
\cdots+p_{i+1}(L_1+\cdots+L_{i-1}+L_{i+1})+p_i(L_1+\cdots+L_{i+1})
+\cdots.
$$
臌������ ����� $p_iL_{i+1}-p_{i+1}L_i$. � ��� ������������ 
(19) ����������, �� $p_iL_{i+1}-p_{i+1}L_i\ge 0$. 獀���, $p_i/L_i\ge 
p_{i+1}/L_{i+1}$, �. �. (20) �����������.

䎊���� ������ ������������� ������� (20). ����������, "���������" 
������������� ������������ (19) ����� �����:
���� �� �������� ������� ��� ������, ����� ������ ��������� �� 
$p_iL_{i+1}-p_{i+1}L_i\ge 0$. ��� "����������" ������������� ������� 
�����������. � ���������� ��� ��������������: ���� �� ��� ���������� 
���������� ����������, � ������ ������������ ��������� �������������� 
��������������.

\proof\ 1. �� (20) �����������. � �����, ��� ����� ������������ 
������� ����� "�������������", �. �. �������� � ������������ $R_1$, 
$R_2$, \dots,  $R_N$, ��������������� ����� ������� ���� �������� ��������.
 ꀆ��� ����� ��������� ��������� \dots$R_j$ $R_i$\dots � \dots$R_i$ 
$R_j$\dots ��� ��������� $i<j$, 
�. �. ��������� ����� ������ �� ��������������� �������� 
$p_iL_j-p_jL_i$. 獀���,  ������� $R_1$  $R_2$ \dots $R_N$ ���������.

\proof\ 2. 瀌���� ����������� $p_i$ ��
$$
p_i(\varepsilon)=p_i+\varepsilon^i-(\varepsilon^1+\varepsilon^2+\cdots
+\varepsilon^N)/N,
$$
��� $\varepsilon$---����� ������������� ��������. ��������� 
$x_1p_1(\varepsilon) +\cdots+x_Np_N(\varepsilon)
=y_1p_1(\varepsilon)+\cdots+y_Np_N(\varepsilon)$ ����������� ��� 
���������� ����� $\varepsilon$ ���� ��� $x_1=y_1$, \dots, $x_N=y_N$;
 � ���������, � (20) ������ ������������ ��������� 
${p_i\over L_i}={p_j\over L_j}$ ���������� $N!$
������������ �������. 񐅄� ��� ���� �� ������� ���� ���� �����������; � 
���� ������ ����� ������� ��� ������������� (20), �� � ���� ���������� 
�������� ������� (20) ������������� ���� ���� ������������. 򀊈� 
�������, (20) ���������� ���������� ����������� ������������ ������� � 
������� ��� ������������ $p_i(\varepsilon)$ ��� ���������� ����� 
$\varepsilon$. � ������������� ���� �� ������� ��������� � ��� 
$\varepsilon$. (򀊎� ����� ������������� ����� ������������ � 
������������� �����������.)
\proofend

򅎐��� S ����������� �. �. 񌈒� [{\sl Naval Research Logistics 
Quarterly\/}, {\bf 3} (1956), 59--66]. 󏐀������ �������� 
�������������� ���������� �� ����������� ����������� ������.
%% 479
\section 󏋎������ ������. ������������� ����� �� ����� � ������ 
������� ������������ ����������� ��������� �������;
���� ������ �������� ������ �����, ������� ������� ����������� ��������� 
��������� �������� ������������� ������ � �������. � ������ ����� 
���������� ����� � ����� ����.

��, ��������, ��������� ������� ������� ����� �� �������� ��� 
���������� �� ��������� 12-������� �����. (�. � �.~4.5.4.) 򀊈� ����� 
������� 78498; ��������� 20 ����� ��� ������� �� ���, �� ������� ���� 
����� 1\ 569\ 960 �����. ��� ����� ���������������, ��� ��� ����� ����� 
�������-������� �������, � ������� �������, ��������������� ������� ������,
 ����� 1. ������ ��� ������� ����� (����� ������) �������, ���������� 
����� ������� � 500000 �����.

䐓��� �������� ���������� ����� ����� �������� �������� �� ����� 
������� �����, � ���������� ����� ����. � ������������ � ����.~1 �������� 
$(p_{k+1}-p_k)/2$ ������ 64 ��� ���� ������� ����� � �������� 1\ 357\ 201, 
�. �. ��� ���������� ��������� 78\ 496 �������������� ����� (������ 
���������)/2. 򀊀� ������� ����� ����� �������� 471\ 000 �����. 
䀋�������� ���������� ����� ��������, ��������� ��� 
������������� ���������� �������� ���� ���������� ����� (��. � �~ 6.2.2).
\htable{򀁋��� 1}%
{򀁋��� ���������� ����� ����������������� �������� �������}%
{\strut\hfill#\hfill&\hfill#\hfill&\vrule\hfill#\hfill&\hfill#\hfill\cr
荒����� $(p_{k+1}-p_k)$ & $p_k$  & 荒����� $(p_{k+1}-p_k)$ & $p_k$ \cr
 1 &     2 &  52 &    19609 \cr
 2 &     3 &  72 &    31397 \cr
 4 &     7 &  86 &   155921 \cr
 6 &    23 &  96 &   360653 \cr
 8 &    89 & 112 &   370261 \cr
14 &   113 & 114 &   492113 \cr
18 &   523 & 118 &  1349533 \cr
20 &   887 & 132 &  1357201 \cr
23 &  1129 & 148 &  2010733 \cr
34 &  1327 & 154 &  4652353 \cr
36 &  9551 & 180 & 17051707 \cr
44 & 15683 & 310 & 20831323 \cr
}
� ������� �������� ��������� $p_{k+1}-p_k$, ����������� $p_{j+1}-p_j$ 
��� ���� $j<k$. ᎋ�� �������� ��. F. Gruenberger, G. Armerding, 
"Statistics on the first six million prime numbers", RAND Corp. report 
P-2460 (October, 1961).

%% 480

\excercises
\ex[�20] �� ��� �����, �� ������� ���������� �����, 
�������������. ������� ������������������ ���������� ����� ��������� 
��� ������� ������ � ������� �� $N$~�������.

\ex[16] 臌����� ��������~S, ����������� ��� ��� ������ � ��������� � 
��������� �������������. (呋� |P| ��������� �� ������ � �������, �� 
��������������, ��� $|KEY|(|P|)$ ���� ����, 
$|INFO|(|P|)$---��������������� ���������� �~$|LINK|(|P|)$---��������� �� 
��������� ������. ꐎ�� ����, ��������������, ��� |FIRST| ��������� �� 
������ ������, � ��������� ������ ��������� ��~$\NULL$.)

\ex[16] 퀏����� \MIX-��������� ��� ��������� ���.~2. ⛐����� 
����� ������ ����� ��������� ����� ��������~$C$ �~$S$, ������������ �~(1). 
\rex[17] ������ �� ���� ���������~Q � �������� � ��������� 
�������������? (�. � ���.~2.)

\ex[20] ������~$Q'$, ����������, ������� ������� ���������~Q 
��� �������~$C$. 񓙅������ �� ����� ��������~$C$ �~$S$, ��� ������� 
���������~$Q'$ ������� ������ �������, ���~Q?

\rex[20] 󂅋���� ���������~$Q'$ �� ��� �������, ������� ����� �� ������ 
� $(3.33C+\hbox{\rm const}) u$.

\ex[�20] ������� ������� ����� ��������� (3), ��������� 
"��������" ������������� (5).

\ex[��22] 퀉���� ��������������� ��� ��� $H^{(x)}_n$ ���~$n\to\infty$; $x\ne1$.

\rex[�23] � ������ ��������, ��� ������������� ������������~(11) 
�~(13) �������������� ������������ � ��� ������� ����� ��������� �~(13) 
����� $\theta N/(\theta+1)+O(N^{1-\theta})$. ����� �� ����� �� ����� 
������� ����� ��������� ��� ������������� �������������~(11)?

\ex[�20] 퀈������ ������������ ������� � ������� ������������ 
��������~(4); ������ \emph{���������} ������������? �����, ��� 
������� ����� ��������� ��� ��������� � ��������� ������������� ��������� ������� �����������.

\ex[�30] ����� ����� ���������� �������� ������ ��������� 
������������������� �����. 񍀗��� ���������� ������ �������� ������� 
�����������. ���� $f_m(x_1, x_2,~\ldots, x_m)$ ������ ����������� 
����� ���� ��������� ������������� ������������ $x_{i_1}x_{i_2}\ldots 
x_{i_k}$, ��� $1\le i_1$,~\dots, $i_k\le m$ � ������ $x_i$, $1\le i\le m$, 
������ �� ��� ������������. 퀏�����,
$$
f_2(x,y)=\sum_{j,k\ge 0} (x^{1+j}y(x+y)^k+y^{1+j}x(x+y)^k)=
{xy\over 1-x-y}\left({1\over 1-x}+{1\over 1-y}\right).
$$
茅� ��������� $X=\{\, x_1,~\ldots, x_n\,\}$ �� $n$~����������, �������
$$
\eqalign{
P_{nm}&=\sum_{1\le j_1<\ldots<j_m\le n} f_m(x_{j_1},~\ldots, x_{j_m});\cr
Q_{nm}&=\sum_{1\le j_1<\ldots<j_m\le n}{1\over 1-x_{j_1}-\cdots-x_{j_m}}.\cr
}
$$
퀏�����, $P_{32}=f_2(x_1, x_2)+f_2(x_1, x_3)+f_2(x_2, x_3)$, 
�~$Q_{32}=1/(1-x_1-x_2)+1/(1-x_1-x_3)+1/(1-x_2-x_3)$. � ����������� 
�������� $P_{n0}=Q_{n0}=1$.

\item{a)} ��������, ��� � ������������������ ���� ������� �� 
�������~$R_i$ ��������� � ������������~$p_i$. �����, ��� ����� 
���������� ������ ������� �������~$R_i$ �������� �� $m\hbox{-�}$~����� �� 
������ ����� � ���������� ������������~$p_iP_{N-1, m-1}$, ��� $X=\{\,p_1,
~\ldots, p_{i-1}, p_{i+1},~\ldots, p_N\,\}$.

\item{b)} 񓌌���� ��������� (a) ��� $m=1$, 2,~\dots, �������� ���������
$$
P_{nn}+P_{n,n-1}+\cdots+P_{n0}=Q_{nn}.
$$
%%481
⛂����� ������, ���
$$
\displaylines{
P_{nm}+\perm{n-m+1}{1}P_{n,m-1}+\cdots+\perm{n-m+m}{m}P_{n0}=Q_{nm};\cr
Q_{nm}-\perm{n-m+1}{1}Q_{n,m-1}+\cdots+(-1)^m\perm{n-m+m}{m}Q_{n0}=P_{nm}.\cr
}
$$
\item{c)} �������� ������ �������� ���������� $d_i=\sum_{m\ge1} 
mp_iP_{N-1,m-1}$ ��������~$R_i$ �� ������ �������; ����� ������� 
$\overline{C}_N=\sum_{1\le i\le n} p_id_i$.

\ex[�23] 葏������~(17), ���������� ������� ����� ���������, ��������� 
��� ������ � ������������������ �����, ���� ������� ����� ����� �������� �������������~(5).

\ex[�27] 葏������~(17), ���������� $\overline{C}_N$ � ������ �������������~(6).

\ex[�21] 茅���� ��� ������������������ �������������� ����� 
$\langle x_1, x_2, \ldots, x_n\rangle$ � $\langle y_1, y_2, \ldots, 
y_n\rangle$. ꀊ�� ������������ �������� $a_1$, $a_2$,~\dots, $a_n$ ������ 
����� $\sum x_i y_{a_i}$ ������������? �����������?

\rex[�22] � ������ ��������, ��� ���������� ����������� �� ����� ��������� 
��������� ����������, ����� ������������� ������ ���� ���������.  
������������ ������ � ������, ���������� ���������� \emph{�����������,} 
����� ������ �������������, ��� ��� ��������� ��������� ��������� ����� 
�����������, ���������� �� ��������� ������������.

� ���� ������ �����������, ��� � ��������~$i$ ���������� � 
������������~$P_i$ ���������� �� ����, ��������� ��� ��� ������ 
������������. 퀏�����, ����������� ����, ��� ��� �� ������ ���������, 
����� $(1-P_1)(1-P_2)\ldots(1-P_N)$; ����������� ��������� ������ ����� 
����� �������� $i\hbox{-��}$~�������� ���������� 
$P_i(1-P_{i+1})\ldots(1-P_N)$. 呋� �����~$L_i$ ���������� 
����� $i\hbox{-�}$ ������������, �� ������� ����� ������ ����� 
��������������� ��������
$$
L_1P_1(1-P_2)\ldots(1-P_N)+(L_1+L_2)P_2(1-P_3)\ldots(1-P_N)+\cdots(L_1+\cdots+L_N)P_N
$$
ꀊ�� ����� � ���� �������������� ����������� ������������ ����������� �� �����?

\ex[�22] (�. ������.) �������� ����� ���������, ����������� 
�� ������������ $n$~������ �������. (퀏�����, �� ������ �����, ����� ��, 
��� $x>0$ �~$y<z^2$, �� ����� �� ����, ����� �� ������� ����� ��������� 
������ ) ��������, ��� �������� �������~$i$ �������� $T_i$~������ 
�������, ����������� ���������� �������~$i$ �����~$p_i$ � �� ������� �� 
������� ������ ��������. � ����� ������� ������ ������������� ��������?

\ex[�23] (�. �. 񌈒.) ��������, ��� ������� $n$~�����, ������ 
$i\hbox{-�}$ ������� $T_i$~������ ������� � ����� \emph{������� ���� 
��������� $D_i$.} 䐓���� �������, ��������������, ��� $i\hbox{-�}$~������ 
������ ���� ��������� �� ������� �������~$D_i$. 񎑒����� ���������� �����,
 �������������� \emph{������������ ������������}, �. �.
$$
\max(T_{a_1}-D_{a_1}, T_{a_1}+T_{a_2}-D_{a_2}, \ldots, T_{a_1}+T_{a_2}+\cdots+T_{a_n}-D_{a_n}).
$$
\ex[�30]\exhead(񖅏������ �����.) ��������, ��� $N$~������� 
����������� � ���� ��������� ������� $R_1$,~\dots, $R_N$ � ������~$R_i$ 
����� ������������� � ������������~$p_i$. ������ ������� ���������� 
"����������", ���� ������ ��������� ����� ���������� � ����� ��������� 
�����������. 呋� ������ ���� �� ������ ������ ����������, �� � ������� ���������
$\sum_{1\le i,j\le N} p_ip_j d(i,j)$~������ �������, ��� ����� $d(i,j)$ 
��������� ���������� �������, ����������� �� ����� ��~$i\hbox{-�}$ �� 
$j\hbox{-�}$ �������. ��� ������
%%482
���������, ��������, � ������ �� ����� [$d(i,j)$---����� ����������� 
����� $i\hbox{-�}$ �~$j\hbox{-�}$ ����������].

���������� ������� ���������� ��������� ���������������� ����������� 
������������ ������� ��� ���������� ������. ���������� ������, ����� $d(i,
j)$ ���� ������������ ������� ��~$\abs{i-j}$, �.~�. $d (i,
j)=d_{\abs{i-j}}$;  $d_1<d_2<\ldots<d_{N-1}$. (獀�����~$d_0$ 
�����������.) 䎊�����, ��� � ������ ������ ������������ ������� 
$R_1$~\dots $R_N$ ����� ��������� ����� ���� $N!$~������������ ����� � 
������ �����, ����� ��� 
$p_1\le p_N\le p_2\le p_{N-1}\le \ldots\le p_{\floor{N/2}+1}$,
\picture {���. 2.������������ � ���� �������� ���� ������������ ������� 
����� ����������� ������.}
��� $p_N\le p_1\le p_{N-1}\le p_2\le \ldots\le p_{\ceil{N/2}}$. (獀���, 
���������� �� ���.~2 ������������ � ���� "�������� ����" ����������.) 
[\emph{󊀇����.} ����������� ������������ ������������, �������� 
������������� ����������� $q_1$  $q_2$~\dots $q_k$ $s$ $r_k$~\dots $r_2$ 
$r_1$ $t_1$~\dots $t_m$, $m\ge0$, $k>0$; $N=2k+m+1$. �����, ��� ������ 
������������ $q'_1$ $q'_2$~\dots $q'_k$ $s$ $r'_k$~\dots $r'_2$ $r'_1$ 
$t_1$~\dots $t_m$ �����, ���� $q'_i=\min(q_i, r_i)$ �~$r'_i=\max(q_i, 
r_i)$ (�������� ������ $q'_i=q_i$ �~$r'_i=r_i$ ��� ����~$i$ � ������ 
$q'_i=r_i$, $r'_i=q_i$, $t_j=0$ ��� ����~$i$ �~$j$). 󒂅������� ����� � 
��� ���������� $s$, ����� $N=2k+m$.]

\ex[�20] (�������� ���.~18.) �� �������~$d(i,j)$ �������� 
��������� $d(i,j)+d(j,i)=c$ ��� ����~$i$ �~$j$. 퀉���� ����������� 
������������ ��� ���������� �������. [򀊀� �������� ����������� ��� 
������ �� ������, ����� �� ������������� ����������� ������ � �������� 
����������� � �� �� ����� ������� ����������� ������; ��� $i<j$ ����� $d(i,
j)=a+b(L_{i+1}+\cdots+L_j)$ �~$d(j,
i)=a+b(L_{j+1}+\cdots+L_N)+r+b(L_1+\cdots+L_i)$, ��� $r$---����� ��������� 
�����. ]

\ex[�28] (�������� ���.~18.) 퀉���� ����������� ������� ������� ��� 
���������� �������, ���� $d(i,j)=\min(d_{\abs{i-j}}, d_{n-\abs{i-j}})$ 
�~$d_1<d_2<\ldots$. [򀊀� ������ ��������� ��� ������������ ������ � 
����������� ������ � ����� ������� ��� ������������ ���������� � 
������������ ������ � ��� �������.]

\ex[�28] ���������� $n\hbox{-������}$ ���, ������� �������� ����� 
���������� $(d_n,~\ldots, d_1)$, $d_i=0$ ���~1. 䂅 ������� ���������� 
\dfn{���������}, ���� � ��� ����������� ����� �� ����� ����������. 
��������, ��� $2^n$ ����� $x_0\le x_1\le\ldots\le x_{2^n-1}$ ������ 
���� ���������� � ������������ $2^n$~�������� ���, ����� 
�����~$\sum\abs{x_i-x_j}$ ���� ����������; ����� ������� �� ����~$i$ �~$j$,
 �����, ��� $x_i$ �~$x_j$ ���������� � ������������ �������� ��������. 
䎊�����, ��� ������� �����������, ����� ��� ����~$i$ ��������~$x_i$ 
��������� �������, ���������� ������� �������� �������� ��������������~$i$.

\rex[20] ��������, ��� � ������� ����� ����� ����� 1000 
\emph{���������} � ������� ����� �������, �.~�. 1000~�������, ��������� 
���������� �������� ��������� ������� ���������� $d(K_i, K)$. ꀊ�� 
��������� ������ ����� ����� �������� ��� ����������������� ������ � ���� 
������?

%% 483
\bye
