\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