\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