\input style
\chapnotrue
\chapno=5\subchno=4\subsubchno=6

1) �������� ������� ����������, ��� ���������� ��������, � ��������, 
�������� �� ������������~$N$ �~$C$, � �� ��~$N$ �~$C$ �������. � 
����������� ���������� ������������ �������������� ����������� (��������,
 ��� $B$~���������� ������� $C$), �� ����� ������ �������, ��� 
���������� ������ �������� ������� �� 10 ����� ������ ������ �������� 
������� �� �������, ��� � ���������� 100000 ������� �� 100 ����� ������. 
� ����� ���� ����� ����� ��������� ��������, �� ����������� � 
����� ��������, ��� ��� �� ����� ������ � ���������� 
��������� ������������ ������������ ��� ����� �����. � ����� ������ ������ 
\emph{�����} ���� �� ������ �����-���� �������, ���� ������ ����� �� ����� 
����� �������� � ��������, ��� ���������� ���������� �� ������ �������� �� 
�������.

 ������� ������� � �������� ������ �������������� �������� �����, 
������������� ��, � ����� ���-������ ����������� ������ �������. � ��� 
����, �������, �� ��������: ��� ����� ������ ��������� ������, ��������� 
��������� ������������� ������������ ������� ����� ������� �� �������,
 ������� ����������� �� ������������ ���������� ��������.

2) � ������, ��� ��������� ��~15 ��~19~���, ����� ������������� 
100000~������� �� 100~����� ��� ���������� ����� �������������. 񊎋��� 
������� ������ �� �� ���������� �� ��������� ������������? ���� ������ 
����� ������������ ������� ������, ��� ��������� ������������ ������� 
���. 䎏�����, ��� ������ ������ ����� ���� �������� � 80-�������� ����� 
� ��� ���������� ���� �������� ����� �������, ������
��� ���������� �� ������ ������� ��������� � ������� $1{2\over3}$~�������, 
��������, ��� �� ������ ���������� ������ ����� ����� ������ �������� 
10~���.  �������� 1000 ���� � ������ ��� ������ �� 1000~���, 
�.~�.~����� 17~�. (茅���� ������ ������� �����������, ��� �� ��� ����� 
��������� ����� �������� �������� "�������������" ��� ����� "������" � 
������.)

3)  ��������� ��������� ����������, ������� ������ �������������� 
�����������, ������� ����� ��������� ������� ����� ������ � �������� 
������ � ��������������� ������������ ���������������� ����������. � 
��� ������ ���������� ������� �������� ������, �� ��� ���������, ��� 
��������, �������� �������� ������� ������� � ������������ ��� 
����������� ����������� �����/������ � ������������ 
��������. �������� ������������ �������� ���������, ��� ���������, � 
����� ����� �� �������, ���� ��� �� ���������� �� ��������� ����������!

4) 텊������ �������������� ������� ����� ��� "�����"
%%401
�������������� ���������, �������������� � ��������� "�������" ����� 
��������, ��� ������������� ������ � ������ ����������� ������ ��� ���� �� 
������ ������. 䋟 ����� ������������ ������ ����� �������� 
���������������� �������. ����������, ��������, ������ ����� ���� �� ��� � 
������ ����� � �����������, ��� �� ����� ��������� ����������� ������� 
�~$T=6$. ⎂���� ������������ ������� ��� �� ������� ���� ����� �� � ��� 
�����, ��� ���, ����� ������, ��� ����� ������� ����� �� ����� ��������� � 
�������. ��� ��������� �� ������� ���������� �������������� 40\%, ��� ��� 
���������������� ������� �������� ����� ������������ ���� � 
������ ��������� ������.

5) 퀘 ������ ������ � ���������� ��� �������� ��� "���������" ������, �� 
�����, ������������� �� ��������, ����� ����� ��� ����������� � ��� ��� 
���� �������. (􀊒������ ������ ���� ����� ����������� �����, ��� 
�������������, ������ ����� ��������� � ����.) 򀊈� �������, ���� ���� 
� ������� ����, ��� ��������� ���� �������, �������, ��� ����� � 
���������� ���������������� ������ ����� ���������� ����������. ��� 
������������ ��������� ����������� � ������ ����������� ���������� � 
�������� �������, ��� ��� ������ ���� �������� ��� ��������� ��������; �� 
����� ���� �.~�.~㈋���� (�� ������ ����������� ����������� 
�������) ������������� �� ���� ������� ������ ����� ��������� ������. � 
������� �� �������, ��� ����������� ����������� ����� ��� �� ������ 
������� ������������ �������. ꐎ�� ����, ����������� ����� � �������� 
�������---��� ������������ ����������� �����, ������� ������������ � 
��������� ������� ������, ����� ��� � � ������������.

6) 䐓��� ������������ ������ � ���������� ������� � ���, ��� ���� ����� 
��������� ���������� ��������� ������, ������ � ����������. 呋� �� �� 
������ ��������� ���������� ���������� ��������� ��������---�������� 
������, �������� �� � ����� ��������� �� �� ���� ����, ��� ��� ����������� 
����� ����������,---�� ������ ������������� ����� �� �������� ����� ������ 
�������!

� ������������� ���� ������� ���������� ���������� ��� ������ ���� ����� 
������������ � �������������� ������, ������ � �����������---������������� 
����������. (��� ���� ���� ������������ ��� ���������� �������~10 
�����~�.) �������� ��� ��������, ��� ���������� ������ �������� 
1000~�������, � ������ ���� �� �����---�� 100. 䅉�������� ����� ��������� 
������� (����� $B_1$, $B_2$,~\dots, $B_{10}$ ���������� ���������� ������, 
 ����������� �� 10~������ �� 100~�������).

%% 402

{\sl ��� 0.\/} 瀏������ ������ � ������� ���, ����� �������� $B_2$\dots 
$B_{10}$ ������������� ������������ �������� (� ���������� ��������� � �������).

{\sl ��� 1.\/} 񂅑�� $B_1$\dots$B_{10}$ � ��������, ����� ������� 
���������� 100 ������� � ���������� �� � $B_{10}$.

{\sl ��� 2.\/} 瀏����� �� $B_{10}$; � �� �� ����� ������� ���������� 100 
������� �� $B_1$\dots$B_{9}$ � ��������� �� � $B_9$.

{\sl ��� 3.\/} ������ �~$B_{10}$ � �������� �� $B_9$; � �� �� 
����� ������� ���������� 100~������� �� $B_1$\dots$B_8$ � ��������� �� �~$B_8$.

\dots

{\sl ��� 9.\/} ������ � $B_4$ � �������� ��~$B_3$; � �� �� 
����� ������� ���������� 100~������� �� $B_1$ $B_2$, ��������� �� � $B_2$ 
� ������� ���, ����� ����������� �������� ���� ����������� ��� $B_5$\dots$B_{10}$.

{\sl ��� 10.\/} ������ �~$B_3$ � �������� ��~$B_2$, ��������~$B_1$, � 
�� �� ����� ������� ���, ����� ����������� �������� ���� ����������� ��� $B4$\dots$B_{10}$.

{\sl ��� 11.\/} ������ �~$B_2$ � �������� ��~$B_1$; � �� �� 
����� ������� ���, ����� $B_3$\dots$B_{10}$ ������������� ������������ ��������.

{\sl ��� 12.\/} ������ �~$B_1$, ����� ���, ����� $B_2$\dots$B_{10}$ 
������������� ������������ ��������. ⅐������ � ���� 1. \endmark

7) � ������������, ��� ����� ����������� �������~$N$ �� �������� �������. 
� ����� �� ���� � ����������� �������������� ����� ���� ����������� ��� 
����� ������� �� ������ ������� �� ���� ������, � �� ����� �� �������, ��� 
���� �������������� ������� �������� �������� ��������~$N$. 퀑������ �� 
��� ��� �������? � ���������, �� �����! � ������, ���  ����� � ���������� 
������ �������, �� �� ����� � ���������������� ����� ��������� ��������. � 
���������������� ������� �� ����� �� ������������ ���������� ��~$N$ ��� 
������������ ������ ������� ������~$B$, ����� $S$~���������, ������ �����, 
���� ������ �������~$P$; � ����������� ������������� � 
����������� ����������� ��������� �������� �� ����� �� 
������������ ���������� ��~$N$, ����� ������, ����� ������� ������� (��. 
����. 5.4.2-2).

脟 �� ������� ���� � �� ��������� ������ � ����������, �� ����� �� 
��������� ������� � ������ �������, ��������� � ����� �.~5.4.4, ������� 
��� � ������������� ����������, �������������� ��������� ������� 
���������������� ����������� � ��������������� ������ (������ ���� ����� 
����� �� � "�����~$A$", ��� �������). ���� �����, � ��������, 
\emph{���������} ����� ���� �������, ����������� ���������� ���������� 
��� ������ � ����������, ��� ��� �� ������� � ������������ � ��������� 
��������� $P\hbox{-�����}$ �������, �� �� ��� �� �������� ��������� 
�������, ���������� �� ������ � ����������.

%% 403

8) 녍����������� ���������� ����� ����������� �������� ��������� ������� 
���. ���������� �������� ������ �������� ������ ��� ����������� 
�������������� ��������� ����, ��� ��� ������ ������� ���������� ������, � 
��������� �������������� ������ ������ ����� ������������ ������ ����� 
���� �����. ����� ������� ���� �� ����� ��������� �~10 ��� ����� 
��������������� ������������, ������� �� ��� ������������ ���������� � 
������� ������� ���������. 񋅄���������, ����� ������� �� �������, ��� 
\emph{�������� ������� ����� �� � ���� ������ �� ������ ����������, ���� 
�� ������ ��������, ��� ��� ���������� ����������������� ���������.} � 
��������� �������� �����~A ���������� �������� "�����, ���� �������� �� 
������ �����", �� ���� �� ������� ���������� �������� �������� ������ 
����� ����������� �����-���� ������������� �� ����� ������� ����������.

9)  �������� �� ������ ������ � ��������� ������ �� ����� ���������� 
��������� �����, ����� �� ��������� ��������� ����� �� �����; �� � ����� 
������ ����� ����� ��������! 񕅌�~A ����������, ��� ���� ����� � 
���������������� �������� ������������ ������� �������, �� ����������� 
������ ������������� ����������, ����� ����������� �������� �����.

10) 呋� � ����� ������������ ����� ��������� ���������, �� �� ������ 
����� ������������ �� ��� � ����� ��������� "�������� ������� �������". 
�, ��������, ����� ������� ������� ������� ������ �������� ������� 
������ �����, � ���������� �������� ����� $\log_P S$ �~$\log_{P+1} S$ �� 
����� ������ ��� �������~$P$. ������ ����� � ������ ��������� ���, 
������� ������ ���������� ��� ��� ������� �����. � ������ �������, � 
���.~12 ������ ���������� ������ ������������� �������������� 
�������������� ���������, ������������ ���. ����� ���������� ����� ����� 
� ������ ��� ���������� ������� �������.

11) � �������, �������� \MIX, ������� ����� ������������� � �������� 
��������� ������ ������, ��� ������� ���� �� ��������� ����� ���������� 
������. 焅�� ������������� ���������� ����� ���������������; ��� ��� 
���������� ��������� ��������� ������ ������ � ���������� � ������ �� 
����� �������. � ����� ���� � ���� ������ ����� 
����������������� ������������� ���������� (��� ��������� �.~�.~ᅋ� � 
1962~�.), ������ ����� ��������� ������� � ����� ������ ���, ����� �� 
������� � ������� ����!

12) � ������, ��� ����� �� ���������� ������� ������ ������������� 
��������������� ������ �� �������, ����� �������� ���������� ������ �� 
������������ ����. 􀊒������ ���������������� ������� � ������ �������, 
���� ��� ���������
%% 404
�����������������, ����� ����������� \emph{���} ������ �� 
������� �������������� �������.

䋟 ������� ������������ �������� ����� �������� ��������������� ����� 
���������� ����� ������ ������� � ����������� ������ ���� (��. 
�~�.~5.4.4). ��� ���������� ���� ������� ������������ �.~X.~������� [{\sl 
JACM\/}, {\bf 3}(1956), 166--167] � ����� �.~X.~ᓐ��� [{\sl Information 
and Control,\/} {\bf 1} (1958), 181--197], ������� ��������, ��� 
����������� ������ ������� �������� ������ (��������, ��������) ���� 
���������� � ������� ���������� ������ � ����������� \emph{����������} 
������ ����, ��������� ����� �������� � �������� ����� (��.~�.~2.3.4.5 
�~5.4.9), ���� ���������� �������� ��������� ����. � �����, ���������� 
��������� �����, ��������, ������� ������� �� ������ ��� ������ 
������������ ���������� ������� �������, � �� �� ������.

13) � ����� ���������� ��, �� �����������, ������������, ��� ������� 
����������� ������������ ��������������� ���������� �����/������ � ��� 
������� ������� ��������� ��������� �� ������ ��� ������������ ����� � 
����� ��������������, �� ����� ������������ ������������ ����������. ��� 
��������� ������������� ��������� ��� ���������� � ���� ������� �������, 
� ��� ����� ���� ��������� ������ � ��������������� ��������������� 
������������ ������. ��� ������� ��������, ��� ���������������������� 
� ��������������������� ����� ����������� ��������� ��������.

14) �������� ���� ������� ���� ������� ����������� � ������ 
�.~X.~������� [{\sl JACM,\/} {\bf 3} (1956), 134--165],�.~玁�������� 
[{\sl Electron. Datenverarb.,\/} {\bf 5} (1960), 28--44] � �.~�.~㎒��� 
[Digital Computer User's Handbook (New York, McGraw-Hill, 1967) 1.292--1.320].

\section ������. � ����� ��������� ������� ������� �������� ���, ��� 
������ � ��������� ��������� ���� �������:

\proclaim 򅎐��� �. 򐓄�� ������, ����� ����� ������� �������� 
��������� � ���������� ��������. \endmark

����, ������� �� ������ �� �����~�, ����������, ��� 100000~������� �� 
100~����� (��� 1~������� ������� �� 10~�����), ������������� � ��������� 
�������, ����� �� ���� ������������� � �������������� ����� ���� ��� 
���������� �������������� ��������������. ��� ������ �������� ����� 
�������� ����� � ����� ���� ������������� �������������� �� 15--19 ���;
������ ������������ ��������� ������������ ������ ����������� �� 
������������, � ����� ���������� ����� ������ �� ������ ������� ���������� 
� ��������� �������������� ��~
%%405
������� ����� ��~���� �����. � ����� �������� ����� 3~��� ����������� �� 
��������� ������������� �������� � ���������� ����������, ����� 4.5~���---�� 
������������� ������� � ��������� �������� ����� � ����� 
7.5--11.5~���---�� ������������� ������ �������.

呋� ������� ����� ����, ������� ������ ������ � �������� �����������, �� 
��������� ������� ���������� ��� ����� �������������� ���� "����������� 
������� � ������������ ����" (������~4), � ��� ����, ����������� �������� 
������, ��������� ������� �������� ����������� ����� � �������� ������� �� 
������� ����������� ��������� �������� (������~7). ���������� 
���������� (������~9) �������� ������ �����. � ����� ������� ��������� 
������� ����� ������ � ���� ������������� ��������� (�������~5 �~8). � 
������ ������� ������ ������� ���������������� ������� (������~1) 
��������� ����������� �����������, �������� ��-�� ����� � ���� 
���������� �������, � �������� ��-�� ����, ��� ��� ������ 
������������ ���� ������� �� ���������.

������ ��������� ���������� ��, ���� �� � ����� ������������ ���� 
������ ����� ����.

\section ㅍ������� ����������. � �������� �������� 
������������ ������������� ������ � ������������ ����� ���������� 
�������� ������������ ��������� ������� ����������, ������� ���� �� 
������������������ � ����������� ����������� �������. 򀊆� ������ 
������ ������� ���������, ������� � �������� �������� ���������� 
�������� � �������. 񋅄���������, ������������ ������������ ����������� 
����������---��������������� ������, ��������� ������� ������. 
\dfn{ㅍ������ ����������}---��� ���������, �������, ����������� �� 
����������, ����������� ������ ������ � ������������ ������������,
 ��������� �������� ���������, ���������� ��������������� � ����������� 
���������� ����������. ����� ��������� ����� ������� � ������� �������� 
������, ������, ���~ꎁ�� ���~PL/1, ��� ��� ����� ���� �������� ��� ����� 
���������������� ��� ������������� ��������� � ����������������.

�� �� ������������, ������ �������������� ����������� ����������, 
�������� ����������� ��������� "����������� �������"---������ ����������, 
������� ������ ���������� � ������ � ��������� ������� ��������� 
����������. 񎁑������� ������� ������� ������� ������ ������������, 
����� ��������������� �������� ������, ����� �������� �� ��� 
������������� �������, ����� �������� �� � �����, ����� ������� ��� 
����������. ��, ��������, �������� ������ ������ ���� ������������� �� 
��������������� �����, ������������� ���� � ������� �����-����-���:
%%406
$$
|JUL04| \ |OCT311517| \ |NOV051605| \ |JUL141789| \ |NOV201917|
$$
򐅕��������� ���� ������� ����� ����� � ������� � �������� �������, 
������ �������� �������� ���� ����� ���� �������� �����:
$$
|17760704| \ |15171031| \ |16051105| \ |17890714| \ |19171120|
$$
��� ��������� ����� ������� � ������ ����� ������� ����������� ���������.
 (ꎄ ������ ��� �� ���� ������ ���� ����� ����������.) 񎁑������� 
������� ���������� ������� ����� �������������� ��� �������������� 
��������� ������� �/��� ��� �������� ������ ����������� ��������� � ���� 
�/��� ��� ���������� �����-���� ������� �� �������� �������. ��������� 
�������, ������� �� �������, ������������ ����� �������, ��� ��������� 
������ ����� �������� �� ��������� ��� �������. 瀌����, ��� ���� ������� 
����������� �������, �� ������ ���� �� ������� ���� ��� ������� �� �����, 
���� ���� �� ������������� ��������� � �������. 񎁑������� �������, 
���������� ������ �������, ����� ���������� ���������� ��������� 
�������� �����/������ � ������������� ����������.

ㅍ������� ���������� ����� ��������� � ��������� �������, �����, ��� 
���������� � ������ ����; ��� ����� ����� ������������ ������� 
����������� ����� ��� ���� �������� ����, ��� ������� ����� ����� �� 
������� � �� ����������. 荎��� ������� �������� ��� ��������� ���������� 
� ������� ������ � ������������� �� �������. 񀌛� ������������������ 
���������� ��������� ������� ����� ����������� ���������� ����� [��. 
D.~J.~Waks, {\sl CACM,\/} {\bf 6} (1963), 267--272].

\section *񋈟��� � ������� ������ �������. � ������, ��� $2P+2$~������� 
���������� ��� ����������� �������� �������� ���� � ������� 
$P\hbox{-��������}$ �������. � ���������� ����� ������ �������� 
�������������� ������ ������� ������� � ��� ������, ����� ������� ������ 
$2P+2$~�������.

�����, ��� ���������� ��� ������ ������, ��� ��� �� ������ ���������� 
�� ������ ������, ������� � ��� �� ����� ��������� ���� ������ � ������. 
���� �� ����� ������ �� ������������� ������ ������ � �������� ������ 
������.

䎏�����, ������� $P+Q$~������� �����, ��� $1\le Q\le P$. ⎑���������� 
��� �������� ����� �������� �������, ������������ �.~�.~Ⓞ����� [{\sl 
IBM Systems J.,\/} {\bf 9} (1970), 118--144]. ������ ������ ����� ����� 
�������� ���� ������� �������. 茅���� �����������~$p_0$ ����, ��� � 
������� ����� ������� �� ���� �� ������� ����� �� ������ ������, $p_1$---��� 
���� ����� ������ ������, $p{\ge 2}$---��� ��� ��� ������ ������� ������ 
%%407
������� �~�.~�. � ���������� ������ ����� �� ����������� � ����� 
�� $Q+1$~���������:

\medskip
{\sl 񎑒�����~$0$:\/} $Q$~�������  �����. � �������� ������ 
���� ����������� ����� � ���� �� ���, ��������� ����� ���������������, 
��������� ����� � ���� ������. ����� ���� ������� ������� �� ��������� � 
���������~$1$ � ������������~$p_0$, � ��������� ������ �� �������� � 
���������~$0$.

{\sl 񎑒�����~$1$:\/} $Q-1$~������� �����. � �������� ������ � ���� �� 
���, ������������ ���������� ����. ����� ���� ������� ������� �� ��������� 
� ���������~$2$ � ������������~$p_0$, � ���������~$1$ � ������������~$p_1$ 
� � ���������~$0$ � ������������~$p_{\ge2}$.

$\vdots$

{\sl 񎑒�����~$Q-1$:\/} ���� ����� ����. � �������� ������ � ����, 
������������ ���������� ����. ����� ���� ������� ������� �� ��������� � 
���������~$Q$ � ������������~$p_0$, � ���������~$Q-1$ � 
������������~$p_1$,~\dots, � ���������~$1$ � ������������~$P_{Q-1}$, � � 
���������~$0$ � ������������~$p_{\ge Q}$.

{\sl 񎑒�����~$Q$:\/} ��� ������ ���������. ������ ���� ��������������� 
� ������� �� $\mu$~������ �������, � ����� �� ��������� � ���������~$1$.
\medskip

� �������� � ���������~$0$. ��� ������ �������� ������������� 
����������� �������� (��.~���.~2.3.4.2-26), ������� ����� ���������������� 
� ������� ������������ ������� ��������� ���������� ��������. �� 
$z$---������������ ��������, � �����������, ��� ������ ���, ����� �� 
������ ������ � �����, ������ ��� � ������������~$z$, � � 
������������~$1-z$ ��������� ��������. �� $g_Q(z)=\sum_{n\ge0} 
a_n^{(Q)}z^n(1-z)$ ����� ������� ������ ��������� � ���� �������� 
���������~$Q$; ������ �������, ���  $a_n^{(Q)}$---��� ������� ����� 
��������� ���������~$Q$, ���� ���� ��������� ����� $n$~������. 򎃄� 
$n+a_n\mu$---������� ��������� �����, ����������� �� ���� � ����������. 呋� 
�� ������� ������ ����������, ��� � ��������� � $(2P+2)$~��������, 
�� ��������� ����� �������� �� ������ $n$~������, ��� ��� 
$a_n\mu$~������������ ����� �������� ������.

�� $A_{ij}$---����������� ����, ��� �� ��������� �� ���������~$i$ � 
���������~$j$ � ���� �������� ���~$0\le i$, $j\le Q+1$, ��� $Q+1$---����� 
��������� "���������". 퀏�����, ��� $Q=1$, $2$, $3$ �������~$A$ ����� 
����������:
%%407
$$
\eqalign{
Q&=1:\pmatrix{
p_{\ge1}z & p_0z & 1-z\cr
1 & 0 & 0\cr
0 & 0 & 0\cr
},\cr
Q&=2:\pmatrix{
p_{\ge1}z & p_0z & 0 & 1-z\cr
p_{\ge2}z & p_1z & p_0z& 1-z\cr
0 & 1 & 0 & 0 \cr
0 & 0 & 0 & 0\cr
},\cr
Q&=3:\pmatrix{
p_{\ge1}z & p_0z & 0 & 0 & 1-z\cr
p_{\ge2}z & p_1z & p_0z& 0 & 1-z\cr
p_{\ge3}z & p_2z & p_1z& p_0z & 1-z\cr
0 & 0 & 1 & 0 & 0\cr
0 & 0 & 0& 0 & 0 \cr
}.\cr
}
$$
� ���.~2.3.4.2-26b �����, ��� 
$g_Q(z) =\hbox{ �������������� ���������� $Q_0$}  (I-A)/\det (I-A)$. �, 
��������, ���� $Q=1$, �����
$$
\eqalign{
g_1(z)&=\det\pmatrix{
0 & -p_0z & z-1\cr
1 & 0 & 0 \cr
0 & 0 & 1\cr
}/
\det\pmatrix{
1-p_{\ge1}z & -p_0z & z-1\cr
-1 & 1 & 0\cr
0& 0 & 1\cr
}=\cr
&={p_0z\over 1-p_1z-p_0z}={p_0z\over1-z}=\sum_{n\ge0} np_0z^n(1-z),\cr
}
$$
��� ��� $a_n^{(1)}=np_0$. ���, �������, �������� �������, ��� ��� 
��� $Q=1$ ������ ����� ������. ����������� ���������� ��� 
$Q=2$ (��.~���.~14) ���� ����� ��������� �������:
$$
a_n^{(2)}={p_0^2n\over 1-p_1}-{p_0^2(1-p_1^n)\over(1-p_1)^2}.
\eqno(10)
$$
� ����� ������ ����� ��������, ��� $a_n^{(Q)}$ ����� 
���~$\alpha^{(Q)}n+O(1)$ ��� $n\to\infty$, ��� ���������~$\alpha^{(Q)}$ 
�� ������� ������ ���������. (�. ���.~15.) ꀊ �����������, $\alpha^{(3)}=p_0^3/((1-p_1)^2-p_0p_2)$.

葕��� �� ������� �������, �������� ������� ������������, ��� $\mu=1/P$ � 
��� �����������~$p_k$ ������������� ������������� �������������
$$
p_k=\perm{P}{k}\perm{1}{P}^k{\left({P-1\over P}\right)\hbox to 0pt{.\hss}}^{P-k}
$$
퀏�����, ���� $P=5$, �� $p_0= .32768$, $p_1=.4096$, $p_2= .2048$, 
$p_3=.0512$, $p_4=.0064$ �~$p_5=.00032$; �������������, $\alpha^{(1)}=0.328$, 
$\alpha^{(2)}=0.182$ �~$\alpha^{(3)}=0.127$. 䐓���� �������, ���� �� 
���������� $5+3$~������� ������� ������~$5+5$, �� ����� ������� 
��������������� �������  �������� ������ �������~$0.127/5\approx 2.5\%$.

%% 409

ꎍ����, ��� ������---������ ����� ������ �����������. � �����, ��� ��� 
$Q=P$ ������ ��� ������� ��������, �� ���� ������ �� ������, �� ����. 
䎏����������� ����� �������� ������ ��� �������~$Q$ ����� ����� 
�������������� ������� � ��������� ��������, ���������� �� ������������� 
����� ������� ������, ��� ��� ������� ����� � $Q=P$ ������� �����������.
\excercises

\ex[13] ⛂����� ������� ��� ������� ����� ����� �� �����, ���� ������ 
���� �������� $n$~�����. 񗈒����, ��� ����� ����� �� �������� 
����� 23000000 �����, ���� �� �� ���� ���������� �����������.

\ex[15] ������, ������ ������ ����� �����~$2$ � ������~$6$ ���.~84 
������ ����.

\ex[20] ᓄ�� �� ��������~F �������� ������� �������, ���� ������ 
$2P$~������� ����� ������� ������ $2P-1$? 呋� ��, �������� ���, ���� 
���--- ��������� ������, ����� �������� ������ �������.

\ex[20] ꀊ �������� ��������~F, ����� �� ������� ����� � ���~$P=1$?

\rex[21] 呋� � ��������� ������ ������� ������ �����, ���������� � 
�������� ��������������� ����������� ����� ���������. ������, ������, � 
��������, ��� �������� ����������, ���� ����� ������ ���������� 
�������� ������� � ��������������� � ���������~F.

\ex[22] ꀊ�� ��������� ������� ������� � ���������~5.4.3�, ����� 
������������� ��� � �������� ���������� ������� \emph{� ����������� 
���������} ��  $T+1$~������?

\rex [26] 퀗������ ������������� � �������~7 �����~� ���������
$$
(A_1D_1)^{11}\quad D_1(A_1D_1)^{10}\quad D_1(A_1D_1)^9\quad D_1(A_1D_1)^7
$$
�� ������~1--4, ��� $(A_1D_1)^7$ �������� 
$A_1D_1A_1D_1A_1D_1A_1D_1A_1D_1A_1D_1A_1D_1$. �����, ��� �������� 
�������������� �������~$A_0$ �~$D_0$ ��������� �� ��������� �������� (� 
��� ������, ��� ����� ����� �������������� �� ����� ������� ��������� 
�������� ����� �����������), ����� �������� ������������� �
$$
A(DA)^{14}\quad  (DA)^{28}\quad  (DA)^{26}\quad  (DA)^{22}.
$$
[\emph{󊀇����.} ����� ��������� ��������, ���������� ���������~$A_0$ 
�~$D_0$ � ���� �������� ���. ����� ������� ��� ������� ���������� ������� 
����� ���� ����������, ��� � ���~5.4.4-5; ����� ���������� ��������� 
���������, ��� ��� �������� ������� ������ ����� �������� ����� �������.]

\ex[20] � �����~� �����, ��� ����������� ���� ���������� ������������� 
�������� (�� ����������� ���������� ������������� ��� ���������� �������) 
����� ��������� �������� ���������������� ������� �� ��������� �����. 呋� 
�� ���������������� ������� ������ �� ���� �����, �� �� ����� �� 
���������� ������������ �����; ����� �� ������� ������� ������� 
����� �������� ��������� ������������� ���, ����� ��� ���� ����������� �����?

\rex[22] ����, ������� ������� ����� �� ����������� �������� � �������� 
������� �� �����~�, ���� �� �� ������������ ��� ���������� ��� $T=6$ ����, 
� �� $T=5$, ��� � �������~7. ᛋ� �� ������� �������� ������������� 
������� �����?

\ex[�23] 葏������ ������, ����������� � �.~5.4.2 �~5.4.3, ��������, ��� 
����� ������ ��������� �� ����� ������������ ������������ ������� � ������ 
������� ��� ���������� ������� ����� ��������� 54\% ����� (�������� 
��������� � �������� ���������, ������� ���������� ���� ����).

%%410
\ex[23] 臌���� ���������� �������� ����.~1, �������, ������� 
������� ������ �� ������ ������ �������� �����~�, ���� �� �� ����� 
�������������� ��������� (������� � ���������) 񗈒����, ��� $p=1$, ���� 
����� ��������� ������ ��� �� ���� ��������, � ��� ����� ����������� 
����� ����� ��������� ����� �������������� ���� �������� ���� �� �����, 
������� ���������� �� ��� $\rho=1/5$ 臌����� ������~8 ���, ����� �� 
����������� ��������� ������� � ������������, ��������� ��������� � 
������ ������ � ���� ������ ��������� ����������� [\emph{󊀇����:} 
����������� ��������� ���. 10 ]

\ex[40] ���������� ��������� ����� ���� �� ��� ���� ����, ��� ������ ���� 
������ ���� ����� ����� � ����������� ������� �~$T=3$ � ����� ������ 
���� ����� ��������� �����~$1$, $3$, $5$,~\dots, � ������---�����~$2$, $4$, 
$6$,~\dots, ����� �������� ��, �� ��������, ���������� ����, ����� �� ��� 
����� ������� ��� ������� � ��� �������� ����� ���������� ���������, 
������ ����������� �������� ������� �����������

\item{(a)} 퀉���� ���������� ������ �������������� ��������~F �� ���� ������.

\item{(b)} ���� ����� ����� ����������, ������� ���������� ��, ���� �� 
���� ����� ��� ����������� ��� ���������� 100000~������� �� 100~�����, 
���������� ������ ��� �������, ��� � ��������� ������.

\ex[20] 쎆�� �� ������������� ���������� � ����� �������, � ��� ���� ��� 
��� ���������� � ��������� 5.4.5�, �������������� ��� ���������� ������� 
������ ����� �������� ������ �� ������� �������������� �������?

\ex[�19] ⛂����� (10).

\ex[��29] 䎊�����, ��� $g_Q(z)=h_Q(z)/(1-z)$, ��� $h_Q(z)$~�������� 
������������ ��������~$z$,  �� ������� ������������ ������ ���������� �����;
�������������, $a_n^{(Q)}=h_Q(1)n+O(1)$ ��� $n\to\infty$. � ���������, 
��������, ���
$$
h_3(1)=\det\pmatrix{
0 & -p_0 & 0 & 0 \cr
0 & 1-p_1 & -p_0 & 0 \cr
0 & -p_2 & 1-p_1 & -p_0 \cr
1 & 0 & 0 & 0 \cr
}
/\det\pmatrix{
1 & -p_0 & 0 & 0 \cr
1 & 1-p_1 & -p_0 & 0 \cr
1 & -p_2 & 1-p_1 & -p_0\cr
0 & 0 & -1 & 1 \cr
}.
$$
\ex[M46] ������������ ������� � $P+Q$~�������� ����� ���������, ��� ��� 
���� ������� � ������, ��������� ����� ������ ������.

\ex[41] ������ ��������� �������� ������ ���������� 100000~������� �� 
100~�����, ��������� �����, �������� �����~�, � �������������, 
��� �������~3, 4 ���~5 ����

\subsubchap{*⍅���� ����������� ����������} %5.4.7
� ���������� ������� �� ����������� ������� ���������   ���������� 
��������; �� ���������� � ������ ������ ���������� �� ������, ���������� 
�� �������� ����������� ����������, ������������ � ������������ 
�������������� ������� ��� ��������� (��. � �.~5.2.5). ���� ����� ������ 
�������� �������������� �����������, ���������� �����������, 
��������� �����������, �������� �����������, ����������� ����������� � �. 
�. �, ��� �����������, �� ��������, \emph{��������������} �������!

��������, ��������, ��� � ����� ������������ ������� ������ �����, � 
������ ����� ���� ������ ������: $0$, $1$, $2$, $3$, 
%%411
$4$, $5$, $6$, $7$. 呋� �������� ������ ��������� �� �����~$T1$, 
�� ������ � �������� ���� ������ ������ ��~$T3$ � ���� �������� ��~$T4$:
\ctable{
\hfill#&&\bskip\hfill$#$\hfill\bskip\cr
 & T1 & T2 & T3 & T4 \cr
䀍�    & \{0, 1, 2, 3, 4, 5, 6, 7\} & - & - & - \cr
��� 1& - & - & \{0, 2, 4, 6\} & \{1, 3, 5, 7\}\cr
\noalign{
\noindent 򅏅�� ������������ ����� � ������~$T3$, � ����� ~$T4$, ������� 
$\{0, 1, 4, 5\}$ ��~$T1$ �~$\{2,  3,  6,  7\}$ ��~$T2$:
}
��� 2. &  \{0,4\} \{1,5\}  &     \{2,6\} \{3,7\} & - &- \cr
\noalign{
\noindent(񒐎��~$\{0, 4\}\{1, 5\}$ ���������� ����, ���������� ������ 
������ � �������~$0$ �~$4$, �� �������� ������� ������ ������ � 
�������~$1$ �~$5$. 瀌����, ���~$T1$ ������ �������� �� �����, ������� 
�������� ������ ������� ��������~$0$.) �� ��� ����� ��������� � 
������������� ������~$0$, $1$, $2$, $3$ ��~$T3$ � ������~$4$, $5$, $6$, 
$7$ ��~$T4$ �� �����
}
���~3 & - & & \{0\}\{1\}\{2\}\{3\} &  \{4\} \{5\} \{6\} \{7\} \cr
}
򅏅�� �����������~$T4$ � �����~$T3$ ��������� ������. � ����� ������ ��� 
������ � ��������� ��~$0$ ��~$2^k-1$ ����� ������������� ���� 
����������� �������, ����������� $k$~��������, �� �������� ������� ���� 
������������� "������", ���������� �������� �������� ������ � ����� ����� 
�� ������. 茅� ����� ����, �� ����� ����������� ������� ������������ 
������������� �� ���������~$3$ ��� ���������� ������ ��~$0$ ��~$3^k-1$ �� $k$~��������.

葏��������� ����� ������ � ���������� ���������. ��������, ��������, 
��� ����������� ������ ������ 
$\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$, � ���������� ��������� ���������, 
������������� �.~�.~���������� [{\sl Theory of Switching,\/} {\bf 7} 
(Harvard Univ. Comp. Laboratory: May, 1954), I.1--I.76]:
\ctable{
\hfill#
&\bskip\hfill$#$\hfill\bskip
&\bskip\hfill$#$\hfill\bskip
&\bskip\hfill$#$\hfill\bskip
&\bskip\hfill$#$\hfill\bskip
&\bskip#\hfill\cr
 & T1 & T2 & T3 & T4 \cr
䀍�    & \{0, 1,~\ldots, 9\} & - & - & - \cr
���~1.& - & \{0, 2, 4, 7\} & \{1, 5, 6\} & \{3, 8, 9\} & $1.0$~������ \cr
���~2.& \{0\} & - & \{1, 5, 6\}\{2,7\} & \{3,8,9\}\{4\} &$0.4$~�������\cr
���~3.& \{0\}\{1\}\{2\} & \{6\}\{7\} & - & \{3,8,9\}\{4\}\{5\}& $0.5$~�������\cr
���~4. & \{0\}\{1\}\{2\}\{3\} & \{6\}\{7\}\{8\} & \{9\} &\{4\}\{5\}& $0.3$~�������\cr
񁎐�� & \{0\}\{1\}\{2\}\{3\}\{4\}\ldots\{9\} & & & & $0.6$~�������\cr
& & & & & $\overline{\hbox{$2.8$ �������}}$\cr
}

%%412

呋� ������ �������� ����� ����������� �������� � ����� ������� �������, 
�� ��� ��������� ��� ���������� ������ ������ ����������� ������ 
$2.8$~�������, � �� ����� ��� ������ ������ ������� $3.5$~������� ��� 
���������� ����� ������ ������. 򀊈� �������, �� �����, ��� �������� 
����� ������������� ����� ������� ������������ �������� ��� 
����������� ���������� ����� ��� ��, ��� ��� �������.

񕅌� ������������� ���������� �������� ����������, ��� � ������, 
������������ �����������:
\picture{���. �� ���. 412}
ꐓ���� ���������� ���� ���� �������� ������������~$1$, $2$, $3$,~\dots � 
������������ � ������ ��������~$1$, $2$, $3$,~\dots. 茅�� ����~$A$, $B$, 
$C$, $D$ (������ $T1$, $T2$, $T3$, $T4$) �������� ����� � ������� ������, 
����� �������, ���� �������� ������. ꂀ������� ������� ���� ���������� 
����� �����, ���������� ������ ���� ����, � ���� ���� ��������� ������ 
������� ��� ��������������� �����. ����� ��� ����������� ������ ��� 
�������� ������ �������� ����� ($C$ � ������ �������, $A$ �� ������).

򀊈� �������, ���~3 �������~1 ������� �� ������ � �����~$D$ � ������ 
������~$1$ �~$5$ �� �����~$A$ � ������~$3$ �~$7$ �� �����~$B$. 텒����� 
������, ��� ����� ����������� �������� ����� \emph{����� �������� ����} 
������, �������� �� ����� ������� �����, ���� �� ���������, ��� ��� ����� 
�������������.

� ���� ���������������� ������� ����� � ���������� "������ 
����������---������ �����������", ������� ����������� ������ ������, 
������ ����� �� ������ ����� ������������� \emph{�����} ���������� ������. 
� ������ �������~1 ������ ������������ �� �����~$A$ �� ����~2 � ����~3; 
������, ���������� � ������� ����~2, ���������� ������������ ������ ������,
 ���������� � ������� ����~3. � ����� ������, ���� �� ���������� �� 
����� � ������� �����~$i$ �~$j$, ��� $i < j$, ������� �������
%%413
������������ ������, ���������� � ������� ����~$i$; ���� ������ 
�������� ��� ����� ����
\picture{���. ���. 413}
�� ������ ����������� ������� $k<l$. ꐎ�� ����, �� �� ����� ������ 
���������� �� �����~$A$ \emph{�����} ������~$k$ �~$l$, ��������� ����� 
������� � ������� ���������� ���������.

� ��������, ������� ����������� ���������� �.~5.4.4, ���������� ������, 
��� ���������� ������� ��� ����������� ���������� � ������ ������� �� 
$T$~������---��� � �������� "������� $T\hbox{-fifo}$" �������, ����������� 
���������� \emph{��������} �� $T$~������ � ������ �������! (�. 
���.~5.4.4-20.) 儈��������� �������� ����������� � ���, ��� ��� ������� 
���� ��������������� ����� �������� �������� ����� � ��� �� ������. � 
����� �� ����� ��� �����������, �����������, ��� ���������� 
������������� ���� "������", ����������� ��� ������ �� �������� �����, ��� 
����� �� �������� ��� ����������� � �������� ��� $T\hbox{-fifo}$ ��������, 
����������, ����� ��������� ����������������� ������ ���������� �������� 
��� ���� ������� � ��������������� ������ �������.

荛�� �������, \emph{������ ����� ������� ������������� 
����� ������������� � ������ ����� ������������� ������������� ����� 
�������.} � ��������� ����������� ��� ���������� ��������. ���������� 
���������� ��������, �������� ��� ��������, �.~�.~"�����������" 
������������� �������� ���� � ��������, ������� "�����������" � ������, 
�~�.�.; �������, �� �������� ���� � $S$~��������. ����� ����� 
�������� � ������� ����� � ������ �����, ����� �������� ��������������� 
����� ������������� ��� ����������� ���������� $S$~������. ��� 
�������������� ������� � ������������� ����� �����;
��� �� ����������� ������ � ����� ���������: ������� ����� ������ 
����������� � ������ ������� �������.

��� � ������� �������, ������������� � ������ ����� ������, ��������, 
��������� ����������������� ������� �� ������� ������. ��� � ������� 
������� � ���������� ��������� ������������� ��������� ����� ������� 
������ �������� (���� �� ������ ���� �����������---���� 6--11 � ������):
\ctable{
#\hfill&&\bskip\hfill$#$\hfill\bskip\cr
 & T1 & T2 & T3 & T4 \cr
퀗������ ������������� &   1^4 & 1^3 & 1^1 & 1^2 \cr
��� ������ 5 & 1^3 & 1^2 & - & 1^2 3^1 \cr
%%414
��� ������ 4 & 1^2 &  1^1 &  2^1 & 1^23^1 \cr
��� ������ 3 & 1^1 & - &  2^13^1 & 1^13^1 \cr
��� ������ 2 &  -  & 4^1 & 3^1 & 3^1 \cr
��� ������ 1 &  10^1& - & - & - \cr
}
呋� �������� �� � ����������� �����������, ��-�����, ��� ��� ������ �����,
 � ��������, ���� � �� �� ���������, �� ������� �� ������� � ����� 
�������� ������������ ����������� �� ������: $1^23^1$ (��� ������� 
�����~1 ������, �� �������� ��������� ���� ������� �����~3) 
������������� 
$\{3, 8, 9\}{4} {5}$ (��� ��������, ���������� ������ �� 1~�����, 
����� �������� ���������� ���� �������, ���������� 3~�����).

䂈����� � ������ �������, �� ����� � �������� ��������� ����������� 
����������, ������������ ������������ �������, ���������� ������� � �. �. 
퀏�����, ������������ ������� 21~������� �� ���� ������, ������������� � 
������ �.~5.4.2, ������������� ��������� ���������� ����������� ����������:
\ctable{
\sevenrm#\hfill&&\bskip\hfill$\scriptstyle#$\hfill\cr
 & T1 & T2 & T3 \cr
䀍� & \{0, 1, \ldots, 20\} & - & - \cr
��� 1& - & \{0, 2, 4, 5, 7, 9, 10, 12, 13, 15, 17, 18, 20\} & \{1, 3, 6,
 8, 11, 14, 16, 19\}\cr
��� 2 & \{0, 5, 10, 13, 18\} & - & \{1, 3, 6, 8, 11, 14, 16, 19\}\{2, 4,
 7, 9, 12, 15, 17, 20\}\cr
��� 3 & \{0, 5, 10, 13, 18\} \{1, 6, 11, 14, 19\} \{2, 7, 12, 15, 20\} 
& \{3, 8, 16\} \{4, 9, 17\} & - \cr
��� 4 & - & \{3, 8, 16\}\{4, 9, 17\} \{5, 10, 18\}\{6, 11, 19\}\{7, 12, 
20\} & \{0, 13\}\{1, 14\}\{2,15\}\cr
��� 5 & \{8\}\{9\}\{10\}\{11\}\{12\} & - & \{0, 13\}\{1,14\}\{2, 
15\}\{3,16\}\ldots\{7,20\}\cr
��� 6 & \{8\} \{9\} \{10\} \{11\} \{12\} \{13\}\ldots\{20\} & \{0\} 
\{1\} \ldots \{7\} & - \cr
}
���� �������������, �������� �������� ����� ������������� �� ������ �� 
������ ����, ������� ����������, �� �� ����� ���� ��� ����� ������� 񂟇� 
� �������� ���������, ������������ ����� 􈁎�����! (�. ���.~2.)

\section ����� ������. 䂎����������� ����������� ���������� � ������� 
��������� ����� � � ����������, �������� ����� � �������� �����������. � 
���������� "$T\hbox{-lifo}$ �������" � �.~5.4.4, � �������� ������, ��� 
��� �������� ��� ����������� ���������� � ��� �� ����, ��� � ��� 
���������� ��������.

�������� ���������� � �������� ������� ���� ���������� ����������� 
䆎��� 쎗�� ��� � 1946~�. � ����� �� ������ �������������� ����� �� 
���������� ������ (��. \S~5.5);
쎗�� �� ����� ���� ��� ��������� �����������:
\ctable{
#\hfill&&\bskip\hfill$#$\hfill\bskip\cr
 & T1 & T2 & T3 & T4\cr
䀍� & - & \{0, 1, \ldots, 9\} & - & - \cr
��� 1& \{4, 5\} & - & \{2, 3, 6, 7\} & \{0, 1, 8, 9\}\cr
��� 2&\{4, 5\} \{2, 7\} & \{3, 6\} & - & \{0, 1, 8, 9\}\cr
��� 3&\{4,5\} \{2, 7\} \{0,9\} & \{3, 6\} \{1,8\}& - & - \cr
��� 4& \{4, 5\} \{2, 7\} & \{3, 6\} \{1, 8\} & \{9\} & \{0\}\cr
\hfill\dots \cr
���  8 & - & - & \{9\}\{8\}\{7\}\{6\}\{5\} & \{0\}\{1\}\{2\}\{3\}\{4\}\cr
���������� ������ & - & - & \{0\} \{1\}\{2\}\{3\}\{4\}\{5\}\ldots\{9\}\cr
}
%%415
\bye