\input style
%% 140
����� ������� �����������; ���� �������� ����� ���� �� ������� 
����������� ����������� ���������!

\MIX-��������� ��� ��������� � ��������� � ���.~12. � ���������, 
���������� ��������������� ��������, ����������� ��� ���������� 
������������������� ���������, ������ ������, ��� ��� ��������� ����� 
����������, ��� ������ ������, ������� �� ���������. ������ �������� 
�������� ����� ������ �������������� ���������: ��� ���������/������, 
������������ ������ ��������� ���� ��, ����� ��������� \emph{������������} 
�� ��� ��� ���������� ������, ������� ��������� ������������
\picture{���. 18.  �������������� ������������� ������ �������,  $N= 16$.}
����������. � ������ ������������� ���������� ���������� ����������� ��  
${1\over 2}\lceil \log_2  N \rceil (\lceil log_2 N \rceil + 1)$ �����, � 
��� ����
�� ����� ������� ��������� ����� �������. ��������, \emph{1024 �������� 
����� ������������� ������� ������� ����� �� 55 ������������ �����}. ��� 
��������� ���������� �������� ����� ������ (��. ���. 5.2.1--30), ������� 
����������� 40 ��� 73 ���� � ����������� �� ����, ��� �������: ���� �� 
������ ��������� ���������� ��������� �� ��� ���, ���� �� ����������� 
��������� ��������������� ������, �� ��� ���������� 1024 ��������� 
������� ������ ��������� ����� 40 ������ ���������/������. ���������� 
��������� ��. � �.~5.3.4.

\section "������� ����������". � ������ ������� 
������������������ ��������� ��������������: ������ ��� ������������ ���� 
� �� �� ���� ������ ���������� �� ����, ��� �� ����� ������ � ����� �� 
���������� ���������. 풎 ����������� � ������� ���� ����������� � 
������������� � ������ ��������, ���� �������� � � ���������� � 
������������ ������� ���������� ��������, � ��� ����� ��������� ���������� 
������ � ������ ����� �����. ��������� ������ � ������ ���� ���������, 
��� ������� ������������ ��������� ������� ���������, ����� ����������, 
����� ����� ���������� ����������.  �� ��������� �� ������� ��� 
������������ ����������, �� ��� ����� ��������� ������������ ��� 
�������������� �����, ���������� ���������������.

%%141

����, ����������. ��������� ����� ���������/�������. ������� ��� ��������� 
$i$ � $j$, ������ ������� $i=l$, a $j=N$. ᐀���� $K_i:K_j$, � ���� ����� 
�� ���������, �� �������� $j$ �� ������� � �������� ���� �������. ����� 
������� ������ �������� $i$ �� ������� � ����� ���������� ���������, 
���������� $i$, ���� �� ���������� ��� ���� �����. ⎃�� ����� �������� 
$j$ � �. �.; ����� "������� ������ � ����� ������", ���� �� ������ $i=j$. 
���������, ��������, ��� ���������� � ����� ������ �� ����������� �����:
{\catcode`\!=\active\def!#1 {\bf#1}
\def\inci{\noalign{\rightline{��������� $i$}}}
\def\decj{\noalign{\rightline{��������� $j$}}}
\ctable{#&&\bskip\hfill$#$\hfill\bskip\cr
����:     &!503 & 087 & 512 & 061 & 908 & 170 & 897 & 275 & 653 & 426 & 154 & 509 & 612 & 677 & 765 &!703\cr
\decj
1-� ����� &!154 & 087 & 512 & 061 & 908 & 170 & 897 & 275 & 653 & 426 &!503 & 509 & 612 & 677 & 765 & 703\cr
\inci
2-� ����� & 154 & 087 &!503 & 061 & 908 & 170 & 897 & 275 & 653 & 426 &!512 & 509 & 612 & 677 & 765 & 703\cr
\decj
3-� ����� & 154 & 087 &!426 & 061 & 908 & 170 & 897 & 275 & 653 &!503 & 512 & 509 & 612 & 677 & 765 & 703\cr
\inci
4-� ����� & 154 & 087 & 426 & 061 &!503 & 170 & 897 & 275 & 653 &!908 & 512 & 509 & 612 & 677 & 765 & 703\cr
\decj
5-� ����� & 154 & 087 & 426 & 061 &!275 & 170 & 897 &!503 & 653 & 908 & 512 & 509 & 612 & 677 & 765 & 703\cr
\inci
6-� ����� & 154 & 087 & 426 & 061 & 275 & 170 &!503 &!897 & 653 & 808 & 512 & 509 & 612 & 677 & 765 & 703\cr
\decj
}
}
(璎�� ������� ��������� $i$ � $j$, ����� $K_i$ � $K_j$ ���������� ������ 
�������.) �������, ��� � ������ ��������� ����� ������� ��������� ���� 
503; ������ � ������ ��������� ����� ����������� �������� ���� $K_1$, 
������ ��� �� ����� ���������� ������������ ������� � ������� ������� 
������ ���, ����� �� ����������� �����������. � �������, ����� $i=j$, 
�������� ������ $R_1$ ������ ���� ������������� �������, ������ ���, ��� 
�������� ������, �����  �� ��� �� ����� ������� ������, � ������---�������. 
�������� ���� �������� �������� ����� �������, ��� �������������� ������ 
�������� � ���� ����� �������: ���������� ����� $R_1$ \dots\ $R_{i-1}$ � 
(����������) ���������� ����� $R_{i+1}$ \dots\ $R_N$. � ������� �� ���� 
��������� ����� ��������� ��� �� ����� �����.

� ����.~2 ��������, ��� ��������� ���� ��� �������� ���� ��������� 
����������� ��� ������ ����� ������ �� 11 ������. � ������ ��������� 
��������, ������� ��� ��������� �������������; � ������ ��� �������� 
����� ������������ ����� ����������� $l$ �~$r$ (������� ���������������� � 
������ ������ �����) � ������ �������������� ��� $(l_k, r_k)$. ������ ���, 
����� ���� ��������������, �� �������� � ���� \emph{�������} �� 
��������� � �������� ������������ ����������, � ��� �� ��� ���, ���� 
�� ������ � ���������� �������� ������; ��� �������� � ���.~20, ����� 
��������� �����������, ��� � ����� ������� �� ����� ���������� �����, ��� 
�������� $\log_2 N$ ���������.
%% 142
\bye
