\input style
%% !! ష��������, ��� M �  sM?
\ex[��20] �����~$S$---������²� �~$\cM$---�����ÿ����� ��� 
���������². �����������, �¾~$p$---�ý�Ƹ�, �������� �� ������²�� ��~$\cM$,
 ��������ɰ� �� ��� ����²�µ�̽˵ ���ǵ���, � �¾ $p(M)$~������ǰ�� 
�����½���� ¾��, �¾ "���ǰ���" �˱����˹ ͻ����� ��~$S$ �����������~$M$. 
ޱ��ɸµ �����������~� �~D °�, �¾�� ����Ǹ�� ž��ȵ� ����������� ����¸� 
$k\hbox{-��������������}$ ���������µ�̽��¸~$\<Z_n>$ ͻ����¾� 
������²�~$S$ �� �½�ȵ��� � ������������� �����½��µ�~$p$.

\rex[��30] (ӵ���� ҵ���.) ߾����µ, �¾ ���������µ�̽����~$\<U_n>$ 
$k\hbox{-������������}$ ��~$[0, 1)$ � ¾� � ¾�̺� ¾� ���ǰ�, �����
\EQ{
\lim_{N\to\infty}{1\over N}\sum_{0\le n < N} \exp(2\pi i(c_1U_n+\cdots+c_kU_{n+k-1}))=0
}
��� ������� ������²� Ƶ��� Ǹ���~$c_1$, $c_2$,~\dots, $c_k$, ��� �� 
���~$c_j$ ������������ ����� �û�.

\ex[�34] ߾����µ, �¾ $b\hbox{-�ǽ��}$ ���������µ�̽����~$\<X_n>$ 
$k\hbox{-������������}$ � ¾� � ¾�̺� ¾� ���ǰ�, ����� ��� 
���������µ�̽��¸~$\<c_1X_n+c_2X_{n+1}+\cdots+c_kX_{n+k-1}>$ 
\emph{���������� ������������} ��� �������, �¾~$c_1$, $c_2$,~\dots, $c_k$ 
ϲ������ Ƶ�˼� Ǹ����� �~$\���(c_1,~\ldots, c_k)=1$.

\ex[�30] ߾����µ, �¾ ���������µ�̽����~$\<U_n>$ $k\hbox{-������������}$ 
��~$[0,1)$ � ¾� � ¾�̺� ¾� ���ǰ�, ����� ��� 
���������µ�̽��¸~$\<c_1U_n+c_2U_{n+1}+\cdots+c_kU_{n+k-1}>$ 
\emph{���������� ������������} ��� �������, �¾~$c_1$, $c_2$,~\dots, 
$c_k$---����¾�˵ Ƶ�˵ Ǹ���, �� ����˵ �û� ������������.

\ex[��20] ߾�������µ�̽���� ���˲����� "����� ���������µ�̽�����", ���� 
��� ����ĸƸ���� ���������µ�̽�� �������Ƹ� ����� �û�, �.~�.\ 
���� ���½�ȵ��� �� �����²��~S ����������� ��� \emph{����}~$k\ge1$. (ڰ� 
����� �� �����²��~S, $\infty\hbox{-��������������}$ ���������µ�̽���� 
ϲ�ϵ��� �����.) ߾����µ, �¾ ���� $[0,1)\hbox{-���������µ�̽����}$ 
���������� ������������, ¾ ��� ϲ�ϵ��� ����� ¾��� � ¾�̺� ¾���, �����
\EQ{
\lim_{n\to\infty}{1\over n}\sum_{0\le j < n} (U_j-1/2)(U_{j+k}-1/2)=0 
\rem{��� ����~$k\ge 1$.}
}

\ex[��34] (Զ. ��ͽ����.) ޿���������� � ����˴�ɵ� ÿ�������� ����� 
���������µ�̽����, ����������, ����� �� ���� ���ǰ����. ����� $U_0$, 
$U_1$,~\dots{} ���� $\infty\hbox{-��������������}$ ���������µ�̽����. 
޿������� ���������µ�̽���� $V_0$, $V_1$,~\dots{} ������ɸ� �������:
\EQ{
\eqalignter{
(V_{2n-1}, V_{2n})&=(U_{2n-1}, U_{2n}), & \rem{���� $(U_{2n-1}, U_{2n})\in 
G$,}\cr
(V_{2n-1}, V_{2n})&=(U_{2n}, U_{2n-1}), & \rem{���� $(U_{2n-1}, 
U_{2n})\notin G$},\cr
}
}
���~$G$---������²�~$\set{(x,y) \mid x-(1/2)\le y \le x \ror  x+(1/2)\le y}$.
 ߾����µ, �¾
(a)~$V_0$, $V_1$,~\dots{} ���� ���������� �������������� � ����� 
���������µ�̽����,
(b)~$\Pr(V_n>V_{n+1})=5/8$. (���δ� ����� �������� µ�° ���������µ�̽�� �������Ƹ�.)

\ex[��49] �����~$\<V_n>$---���������� �������������� ����� 
���������µ�̽����. ﲻϵ��� �� Ǹ���~$5/8$ � ����˴�ɵ� ÿ�������� 
�������ȸ� �������˼ ���ǵ���� ����Ǹ��~$\Pr(V_n>V_{n+1})$?

\rex[�24] �����̷�� ���������µ�̽����~\eqref[11], �������µ 
$3\hbox{-��������������}$ ��~$[0,1)$ ���������µ�̽����, ��� ��¾���~$\Pr(U_{2n}\ge1/2)=3/4$.

\ex[��34] ����� $X_0$, $X_1$, \dots{} ���� $(2k)\hbox{-��������������}$ 
����ǽ�� ���������µ�̽����. ߾����µ, �¾
\EQ{
 \Prsup(X_{2n}=0)\le 1/2+\perm{2k-1}{k}\bigg/2^{2k}.
}

%% 192

\rex[�39] ߾�����µ $(2k)\hbox{-��������������}$ ����ǽ�� 
���������µ�̽����, ��� ��¾��� ����������� ������²�
\EQ{
 \Pr(X_{2n}=0)=1/2+\perm{2k-1}{k}\bigg/ 2^{2k}.
}
(���δ� ����õ�, �¾ ��������²� � ����˴�ɵ� ÿ�������� ���̷� û��ȸ��.)

\ex[�30] ߾����µ, �¾ ��ɵ�²õ� ���������µ�̽���� ��~$[0,1)$ 
ô����²����ɰ� �����������~R5, �� °���, �¾~$\nu_n/n\ge 1/2$ ��� 
����~$n>0$, ��� $\nu_n$~���� Ǹ��� µ�~$j<n$, ��� ��¾���~$U_j<1/2$. (�¾ 
����� ������������� ��� �����ǰ���� �����²� ���������µ�̽��¸.)

\ex[�24] �����~$\<X_n>$---"���ǰ����" $b\hbox{-�ǽ��}$ ���������µ�̽���� � 
������ �����������~R5 �~$\cR$---��Ǹ������ ������� ���������� 
������������µ�̽��¸, ��¾��� �������ϵ� �������ǽ�� 
������������µ�̽����~$\<X_n>\cR$. ߾����µ, �¾ �° ������������µ�̽���� 
�� ¾�̺� $1\hbox{-������������}$, �� � "���ǰ���" � ������ �����������~R5.

\ex[��24] �����~$\<U_{r_n}>$ �~$\<U_{s_n}>$---�������ǽ˵, �� ����ɸ� 
��ɸ� ͻ����¾� ������������µ�̽��¸ ���������µ�̽��¸~$\<U_n>$. (�¾ 
���Ǹ�, �¾ $r_0<r_1<r_2<\ldots$ �~$s_0<s_1<s_2<\ldots$---��� ������°�ɸ� 
���������µ�̽��¸ Ƶ��� Ǹ��� �~$r_m\ne s_n$ ��� �α��~$m$, $n$). ����� 
$\<U_{t_n}>$~���� ���°���� ������������µ�̽����, ��� 
��¾���~$t_0<t_1<t_2<\ldots$ � 
������²�~$\set{t_n}=\set{r_n}\cup\set{s_n}$. ߾����µ, �¾ 
����~$\Pr(U_{r_n}\in A)= \Pr(U_{s_n}\in A)=p$, ¾~$\Pr(U_{t_n}\in A)=p$.

\rex[�25] ޿������µ �������~$\cR_1$, $\cR_2$, $\cR_3$~\dots{} ���������� 
������������µ�̽��µ�, °���, �¾�� �¸ ������� ����� �˻� �� 
�����̷����� � ������¼��~W ��� ����ǵ��� ��ĵ�¸����� ������¼� 
���������� ���������µ�̽��¸ ��~$[0,1)$, ô����²����ɵ� �����������~R1.

\ex[�50] ޱ��ɸµ, ���� �¾ ��������, ������¼~W °�, �¾�� ����ǰ���� 
���������µ�̽��¸, ô����²����ɸ� ����� ������� ������ϼ �����������~R6.

\ex[��30] �����~$\<X_n>$---����ǽ�� ���������µ�̽����, ��¾��� 
ϲ�ϵ��� "���ǰ����" � ������ �����������~R6. ߾����µ, �¾ 
���������µ�̽����~$\<U_n>$ ��~$[0,1)$, ������ɸ� ������� ������������ � 
����ǽ�� ������:
\EQ{
\eqalign{
U_0&=0.X_0\cr
U_1&=0.X_1X_2\cr
U_2&=0.X_3X_4X_5\cr
U_3&=0.X_6X_7X_8X_9\cr
\ldots\cr
}
}
ϲ�ϵ��� ���ǰ���� � ������ �����������~R6.

\ex[�48] ��ɵ�²��� �� ���������µ�̽��¸, ô����²����ɸ� 
�����������~R4, �� ��~R5?

\ex[�50] (�.~�.~ھ��������.) ����� ������~$N$, $n$ �~$\varepsilon$. ݰ�¸ 
�������ȵ� Ǹ��� ������¼�� � ������²�~$A$, °���, �¾�� �� ��ɵ�²����� 
$(n,\varepsilon)\hbox{-���ǰ��˵}$ �� �½�ȵ��� �~$A$ ����ǽ˵ 
���������µ�̽��¸ �����~$N$. (���� ���̷� ����Ǹ�� ¾ǽ˵ ľ��û�, ����� 
�� ���¸ �����¾¸ǵ���� ľ��û�? ӻ����� � �¾� ����ǵ---����������, 
������̺� ������ ����Ǹ��~\eqref[35] � "������ȵ� ���������".)

\ex[��45] (�.~��.) �����~$\<U_n>$---���������µ�̽���� ��~$[0,1)$ 
�~$\nu_n(u)$---Ǹ��� ������ưµ�̽�� Ƶ��� Ǹ���~$j<n$, °���, �¾~$0\le U_j 
<u$.  Ծ����µ, �¾ ��ɵ�²õ� ������µ�̽�� ���¾Ͻ���~$c$, °���, �¾ 
��� �α���~$N$ � �α�� ���������µ�̽��¸~$\<U_n>$ ��~$[0,1)$ ����� ���¾ ��������²�
\EQ{
\abs{\nu_n(u)-un}>c\sqrt{\log N}
}
��� ����¾���~$n$ �~$u$, °���, �¾~$0\le n < N$, $0\le u < 1$. (��ó��� 
�������, ������� ���������µ�̽���� ��~$[0,1)$ �� ����� ���� 
\emph{���Ⱥ��} ���������� ��������������.)

%% 193
\subchap{������} % 3.6
� �¾� ����� �� ������û� ����Ⱦ� ��ó ��������: ��� �������˲��� 
���ǰ��˵ Ǹ���, ��� ��������� ��, ��� �� ����������˲��� � ��� ����ǰ�� 
��Ϸ���˵ � ���� µ���¸ǵ���� ���û�°��. �������� ������, ��¾�˹, 
��������, ��������� �� ����µ��� �¾� ����� � ����ȸ��²� Ǹ°µ���, ����� 
�ľ��û������� ������ɸ� �������: "ڰ��� �� ���û�°� ���� �¾� µ����? 
Ӵ� ����¾� � ��ǵ�²���˹ ���Ǹ�, ��¾�˹ � ��� �� �����̷����� � ����� 
���������� ��� ������˹ ��¾ǽ�� ���ǰ���� Ǹ���?"

ط ����� ��µ�����, ����������� � �¾� �����, ����õ�, �¾ "������ȸ�" � 
"����µ�ȸ�" ���Ǹ� ���ǰ���� Ǹ��� ����ǰ���� ������ɸ� �������. � 
��ǰ�� ��������� ��°����µ ����������~$X$ ������ ����¾���� Ƶ���� 
���ǵ���~$X_0$. �° ����������~$X$ ������ �����̷������� ¾�̺� ��� 
���������� ���ǰ���� Ǹ���. ڰ� ¾�̺� ��� ������ ��������� 
������õ��� ������ɵ� ���ǰ���� Ǹ���, �ö�� ��°������
\EQ[1]{
 X\asg(aX+c) \bmod m
}
� �����̷����� ����� ���ǵ���~$X$ � ��ǵ�²� ���ǰ���� ����Ǹ��. ��� 
�˱��� $X_0$, $a$, $c$ �~$m$ ����ž���� ����δ��� ����¾�˵ ������� � 
�����̷����� ���ǰ��˵ Ǹ��� ����������, �ú�����²���� ������ɸ�� ����Ƹ����.
{\medskip\narrower
\item{i)}����~$X_0$ ����� ���� ��������̽˼. ���� �� ��������� �������� 
������̺� ����ǵ¾� � ����˹ ��� ����µ��� �����ǽ˹ ��¾ǽ�� ���ǰ���� 
Ǹ���, �������µ~$X_0$ ��������� ���ǵ���~$X$, ����ǵ���� �� ����� 
����˴�ɵ�� ����ǵ°, ��� (���� �¾ ����� ô����) ��°����µ~$X_0$ ����˼ 
µ��ɵ�� ������� ������� � ����������� ��µ.

\item{ii)}����~$m$ ������ ���� ������. 㴾��� �˱����� ��� ����˼ 
������� ����� ��Ǹ���µ�̽�� ��ȸ��, ������̺� ��� �¾� ��ĵ�¸��� 
��Ǹ��ϵ���~$(aX+c)\bmod m$. Ҿ�����, ��Ϸ���˵ � �˱����~$m$, ����� 
�������� ����������� � �.~3.2.1.1. ׽�ǵ���~$(aX+c)\bmod m$ ����õ� 
��Ǹ����� \emph{¾ǽ�,} ��� �ȸ��� ���ó�����.

\item{iii)}���� $m$~�����°��ϵ� ����� �µ���� ������ (�.~�.\ 
���� �����̷õ��� ��ȸ��, ����°�ɰ� � ����ǽ�� ���µ�� �Ǹ������), 
�˱���µ~$a$ °���, �¾��~$a\bmod8=5$. ���� $m$~���� �µ����~$10$ 
(�.~�.\ �����̷õ��� ��ȸ��, ����°�ɰ� � ����¸ǽ�� ���µ�� �Ǹ������), 
�˱���µ~$a$ °���, �¾��~$a\bmod 200=21$.
%% 194
��� °��� �˱��� ����Ǹ��~$a$, ��� �������, �¾ $c$~�˱������� �������˼ 
���� ��������, �����¸�õ���, �¾ ���Ǹ� ���ǰ���� Ǹ��� ���� ��� 
$m$~��������� �����ǽ�� ���ǵ���~$X$ ������, ǵ� ��� ��ǽ�� ���¾������ 
(��.~�.~3.2.1.2), �, ����� ¾��, �����¸�õ��� ������� "��ɽ����" (��.~�.~3.2.1.3).

\item{iv)}ܽ���µ��~$a$ ������ ������ž���� ����Ǹ��~$\sqrt{m}$, ����µ�̽�,
 �¾�� �� �˻ ����ȵ~$m/100$, �� ����ȵ~$m-\sqrt{m}$. ߾�������µ�̽���� 
����ϴ�� � ����ǽ�� ��� ����¸ǽ�� �����°������~$a$ \emph{��} ������ 
����� ����¾��, ���û������ ����. ߾ �¾�� ������ ��., ��������, 
�.~3.2.1.3 � ÿ�.~3.2.1.3-8. ���ȵ ����� � ��ǵ�²� �¾�� �����µ�� 
�˱���� ��ô��� ����¾��� ���¾Ͻ���, ��������,
\EQ[2]{
 a=3141592621.
}
(�° ���¾Ͻ��� ô����²��ϵ� ����� ������ϼ ��~(iii).) ����������� 
����������� ���ǽ� �˲��� ���°¾ǽ� ��� ����ǵ��� ô����²���µ�̽��� 
�����µ��, ������, ���� ���Ǹ� ���ǰ���� Ǹ���, �����̷õ��� ��µ������, 
�����µ��~$a$, ����� ¾��, ����õ� �˱����� °�, �¾�� ô����²��ϻ�� 
"῵�����̽˹ µ��" (�.~3.3.4).

\item{v)}߾�¾Ͻ���~$c$ ������ ���� ����� ��ǵ½��� Ǹ��� (����� $m$~���� 
�µ���� ������) � ����� ¾�� �� ������ ���� ���½��~$5$ (����� $m$~���� 
�µ����~$10$). ֵ��µ�̽� �˱�����~$c$ °��� �������, �¾�� 
�½�ȵ���~$c/m$ �˻� �� ��������µ�̽� ����� ����Ǹ��, ����������� � 
�.~3.3.3, ���½�ȵ���~\eqref[41].

\item{vi)}ܵ��� ���Ǹ�˵ (����˵) ����ϴ�~$X$ �� �ǵ�� ž��ȸ � ¾Ǻ� 
������ ���ǰ����¸, ���¾�� ��� �����̷������ Ǹ���~$X$ �������� ���� 
������ ������ �������� ���Ǹ�˵ ����ϴ�. Ҿ��ɵ ������, ���ȵ 
�������������~$X$ ��� ���ǰ���� �����~$X/m$ � ��µ����� �����~$0$ �~$1$, 
�.~�.\ �����°�����~$X$ � ����¸ǽ�� ¾Ǻ�� �����, ǵ� ��� ���ǰ���� 
Ƶ��� Ǹ���; ������������� �����~$0$ �~$m-1$. Ի� ¾��, �¾�� ����Ǹ�� 
���ǰ���� Ƶ��� Ǹ���, ������������� �����~$0$ �~$k-1$, ����õ� 
ü������~$X$ ��~$k$ � �±������ ��Ƚ�� ����ϴ� (��.\ ��ǰ�� �.~3.4.2).
\medskip}

� �¸� ȵ�¸ "��������" �����ǵ�� ��� �������� ������ �� ¾��, �¾ �ö�� 
����� � ���ǰ���� Ǹ����, ����ǰ���� �� ��Ǹ���µ�̽�� ��ȸ��. � ���������,
� ���Ǹµ�̽�� ǰ�¸ ��µ�����, ��ñ����������� � ������� ��������� �¾� 
�����, ��������õ��� �����̷����� ���Ǹ��, � ��¾��� ��ȸ 
������� ����Ȱ����. Ҿ ������ �°���� ������� ����˵ 
µ���¸ǵ���� ���û�°�� �� ������º� ���ǰ���� Ǹ���, ������ 
����������˵ � ��� ������½˵ ��¾�� �������ȵ���, �¾ �˻� �����ö��� �� 
��¾���� ���Ⱥ�� ������.

Ҿ������, �¾ � ��������õ�˵ ���� ���Ǹ�� ���ǰ���� Ǹ���
%% 195
� �ô�ɵ� �ô�� �������� ��ô����²���µ�̽˼�. �� ��������, �¾ �¾�� 
�� ����������, ������ ���Ȼ�� �Ǹ� ��� ��¾������¸. ݰ������ 
��������ü�� �˻� �� ����ÿ��� °�: ������ ǵ� ����̵� �½������� � 
���û�°°� ���ǵ° �� ����������, �����̷��ɸ� ��¾� ܾ�µ-ڰ���, ����õ� 
�Ǹ°�� �� ������� ���� ������, �����̷�� �����ȵ��� �����ǽ˵ ��¾ǽ��� 
���ǰ���� Ǹ���. ⰺ�� ���ž� �� ¾�̺� �����¸�õ� 
��¾�Ǹ����� ���û�°¾�, �� � ���������õ� ��ǵ�²� ���Ǹ��. (�α�� 
���Ǹ� ���ǰ���� Ǹ��� �ô�� ������ ���Ÿ� ���û�°�� �� ������� ���� � 
����� ������ ����������.)

��� ������˵ ������ͽ½˵ ���������µ�̽��¸, �������ǽ˵ �������˼ �����,
 ���ǽ� ϲ������ ô����²���µ�̽˼ ��¾ǽ���� ���ǰ���� Ǹ���, � 
�.~3.3.4 (��.~(3.3.4-13)) ú����� ������ ������ǵ��� �� ��ǵ�²�. ط 
ÿ�.~3.3.4-27 ����õ�, �¾ ������˵ ������ͽ½˵ ���������µ�̽��¸ �� 
������� ��� ���ǵ¾� �� ��¾�� ܾ�µ-ڰ��� � "������� �����ȵ����". ���� 
����õ��� ����Ȱ� ������������� ���ǰ���� Ǹ���, ����ž���� �����̷����� 
��¾�� �.~3.2.2.

������ž��˹ ������ ��µ������, ��ñ��������˹ �� �¾�� ������� �� 1962~�.,
 ���������� � �°�̵ �.~尻�� � �.~Ծ����� "Random Number Generators" 
({\sl SIAM Review,\/} {\bf 4} (1962), 230--254). � ��Ϸ� � �¸� ��� �� 
�ö�� ��������� ��˻�� �� ������ �ñ����Ƹ�, ����� µ�, ��¾�˵ ö� 
ÿ��Ͻ��� � �¾� �����.

����� �����, ��ϲ��ȸ��� ����� 1962~�., �������� ����õ� �¼�¸�� �°��� 
�.~ܰ������� � Զ.~ܰ����̸ "Uniform random Generators" ({\sl JACM,\/} 
{\bf 12} (1965), 83--89), ��¾�� �¾ � ��� �����˵ ú����� �����°º� 
�������� ������ͽ½�� ���Ǹ��� � ��������̽� �˱����˼� �����µ�ϼ�. � 
�¾� �� �°�̵ �˻ ��������� ������¼~3.2.2�. �¾ ž��ȸ� ��¾�, ��¾�˹ 
���Ǹµ�̽� û��Ȱ�� ��ǵ�²� ���Ǹ�� � ����õ� ¾�̺� ����� ����ȵ�� 
������� �ǵ°.

ܽ���� ����Ǹ, ��������˵ � ���¾�ɵ� �����, ��������������� � ����� 
�.~������ "Random Number Generators" (Stockholm, Almqvist and Wiksell, 
1966). � ����� Զ.~尼������ �~�.~�ͽ������� "Monte Carlo Methods" (London,
 Methuen, 1964) �������� ���ǰ���� ���������� ���ǰ���� Ǹ��� � 
��Ǹ���µ�̽�� ��¾���. � �¾� ����� ��������, �¾ ��ĵ�¸������ 
������ Ǹ������� ��¾��� ������°��, ���� �����̷����� "��������ǰ��˵" 
Ǹ���, ���Ƹ��̽� ���������˵ ��� ��ȵ��� ������������ ����Ǹ (� �� 
��Ϸ�µ�̽� ô����²����ɸ� �°¸�¸ǵ���� µ�°�, � ��¾��� �� ������).

� ����������� ���� ÿ��������� ������� ����¾�˵ ��µ����˵ ������� 
��������, �����̷��ɸ� ���ǰ��˵ Ǹ���. Ҿ������, �¾ �������ǽ˵ ������� 
������ � ������ Ǹ°µ��. ߾ ������� ���� ���� ���Ǹ� ���ǰ���� Ǹ��� 
������� ���¸ � �α�� ž��ȵ� ���������.

%%  196

\excercises
\ex[21] ݰ��ȸµ ������������ ��� ��ȸ��~\MIX{} �� ������ɸ�� Ű���µ���¸����:
\descrtable{
�˷��:  & |JMP RANDI|\cr
��¾Ͻ�� ��� �ž��:& $|rA|=k$, ������µ�̽�� Ƶ���~$ < 5000$\cr
��¾Ͻ�� ��� ��ž��: & $|rA|\asg \hbox{���ǰ���� Ƶ���} Y$,
$1\le Y \le k$, ������ Ƶ��� ���ǵ��� ����������½�, $|rX|=?$; ������� 
������������ ����ȵ�.\cr
}
(�����̷ùµ ��¾�, ����������˹ � �¾� �������ĵ, �� ���̼�µ~$c=1$.)

\rex[21] ݵ��¾�˵ ���������, �¾ ��Ǹ���µ�̽˵ ��ȸ�� �� �������� �ô�� 
ÿ������� �����. �� ����������� ��ϲ������, �¾ ��ȸ�� �� ����� ������� 
��ǵ�� ����²�µ�̽� ������, ������̺� ��� ����� ���� �˿���ϵ� ������� 
������ ž�ϸ��, ����������°. ۵�� ۰�����\note{1}%
{�.\ ¾�~1, ���.~25.---{\sl ����. �����.\/}}
 ������ � 1844~�.:
"н���¸ǵ���� ��ȸ�� �� ����Ϸ��� �� \emph{������µ���} ǵ��-����. ޽� 
����� ������ ��� ¾, \emph{�¾ �� �ü��� �� ���������}". ܽ���� ĸ������ 
��������� ��� �����. ޱ�ü��µ �¾ �²��������, ���� � ���� ���Ǹ�� 
���ǰ���� Ǹ���.

\ex[32] "س�� � ���¸". ݰ��ȸµ ���������, ��¾��� �������õ� �������� 
���� ���µ�, �� ������ �� ��¾��� � ������ �����½����� 
�˿����� ���ǵ���~$1$, $2$,~\dots{}, $6$. ���� ��� ������ �������� ��ɰ� 
�ü�� �����~$7$ ���~$11$, ���� �Ǹ°���� �˸�������, ���� ��� �����~$2$, 
$3$ ���~$12$---�����������. ��� �α�� ��ó�� �ü�� (������� ��� �ü�� 
"��������") ���������µ ��������, ���� �� �˿����~$7$ (��������) ��� 
����� ����Ǹ��� "�������" (�˸����).

�˳���µ ������ ���. ൷û�°�� ������� �������� ���µ� ����õ� 
����ǰ°�� � ����~$mn$, ���~$m$ �~$n$---Ƹ��� �� ���� ������, ������� 
���²���²��ɸ�� ������°��ϼ� ����� "�����˵ �����" �~�.~�.

\ex[40] "Ά�µ�" (����Ͻ�). ݵ��¾�˵ ������ �����Ƶ���� ����� 
�� �������˲���� ����Ͻ�� "����µ�". Ҿ������, �¾ ��¾��¸�� �¾������� � 
� ��� �������. ݰ��ȸµ ���������, ��¾��� (a)~°�õ� 
��������������� ������ ����, (b)~�������˲��� �����-���� ���ǽ˹ ����Ͻ� 
"����µ�", �����˲���� �� ����ǵ���� ���ϴ�� ���� � ������, (c)~��ǰ°�� 
���û�°� ����, �ºô� �ô�� �����, ������̺� ��������� �˻� ������ � 
������. ỵ�õ� �˳���� ������̺� ���. ܾ��� ������� °�, �¾�� �� 
���������� ��������� ��Ǹ���� "��ȵ���ǰ��".

\ex[46] \emph{ܾ����������� ��µ��������� ²��ǵ�²� � ������� 
��Ǹ���µ�̽�� ��ȸ��.} 26~���ϱ�� 1960~�.\ �� µ����������� 
���������~CBS �����˲����� ������ǰ, ������������� "�ü��ɰ� ��ȸ��", � 
��¾���, � ǰ�½��¸, �����̷������� ��� ������ȸ� �̵�� � �¸�� ���µ��, 
���°�����˵ ��� ����ɸ ��������� ��� ���. ݸ�� ���������� ��� �¸� 
�Ƶ����� � ¾� ����, � ��¾��� �� �˴��� ��ȸ��.

\tvscript �Ƶ����� 1. (൲��̲�� � ������ �ú�; ���̳� � ����� �ú�; 
�°��� �� �¾��;
���˻�� �� �¾��; ������ �� �����µ��; �����̲�� ȵ��İ � ������ 
�ú� ȵ��İ; ������ ȵ��İ �� ȵ��ĵ.)
\body
���������& (�����µ�� �� �����.) ش�� � �����; �º�˲��� �����; ���ž��� 
� �����; ����˲��� �����; ���� � ó��; ������ ���̳� � ó��; ���� � �¾��; 
������ �����̲�� �� �¾�; ������� � ������ǰ��; ����� �� �¾���; ����� 
�°��� (���¾�) ������ �ú��; �°��� �°��� �� �¾�; ����� ���˻�� ������ �ú��;
��������; �°��� ���˻�� �� �¾�; ����� �°��� ������ �ú��;
�̵� �� �°����; �°��� �°��� �� �¾�; ����� ���˻�� ������ �ú��; ����� 
�� �¾���; ����� �� �¾���; ���� � ó��; ���� � ����; ���� � �¾��; �°��� 
���˻�� �� �¾�; ������� � ������ǰ��; ����� �� �¾���; ����� � 
������ǰ��; ���� � ����;
���� � �¾��; ����� �°��� ������ �ú��.\cr
%% 197
����� & (���� �� �����.) Ҹ��� �����µ��; (�����µ�� ����� ȵ��İ);\cr
���������& �°��� �°��� �� �¾�; ����� �����̲�� ������ �ú��; ������ϵ� �����̲��.\cr
�����& ִ��; �º�˲��� �����; ����� �����µ��; (�����µ�� ����� ȵ��İ); 
���ž��� � �����.\cr
���������&  ش�� � ����; Ƶ�����; �����ϵ�; ����� ����� ������.\cr
�����& ش�� � ����; Ƶ�����; �����ϵ�; �������������, ���� � �����; ���� � ����.\cr
���������& ش�� � �����; Ƶ�����; Ƶ�����.\cr
�����& 浻����; �����ϵ�; �������������.\cr
���������& �����ϵ�; ����� ����� ������.\cr
�����& ش�� � �����; Ƶ�����; �����ϵ�; �������������; ���ž��� � �����; Ƶ�����.\cr
���������& 浻����; �����ϵ�; �������������; Ƶ�����; �����ϵ�; �������������.\cr
�����& �����ϵ�; �������������; ���� � ����; Ƶ�����; �����ϵ�; 
�������������. \cr
���������& 浻����; �����ϵ�; �������������; Ƶ�����; �����ϵ�, 
�������������; Ƶ�����; �����ϵ�; ����� ����� ������.\cr
�����& 浻����; �����ϵ�; ����� �������� � ���������.\cr
���������& ྽ϵ� �����̲��; �����µ�� ü�����.\cr
�����& ڻ���� �����̲�� � ������; ���� � �¾��; ����� �°��� (���¾�) 
������ �ú��; ����� ����� �ú�� �°��� �� ������ �ú�; ����� ���˻�� 
������ �ú��; ��������; �°��� ���˻�� �� �¾�; ����� ������ �ú�� �°��� 
�� ����� �ú�; �̵� �� �°����; ����� ����� �ú�� �°��� �� ������ �ú�; 
����� ���˻�� ������ �ú��; ��������; �°��� ���˻�� �� �¾�;
����� ������ �ú�� �°��� �� ����� �ú�; �̵� �� �°����;
�°��� �°��� �� �¾�; ���� � ó��; ����� ���̳� ������ �ú��; ���� � 
�����, ���ž��� � �����; ����˲��� �����. �������.\cr
\endtvscript

\tvscript �Ƶ�����~2. (൲��̲�� � ������ �ú�; ���̳� � ����� �ú�; 
�°��� �� �¾��; ���˻�� �� �¾��; ������ �� �����µ��; �����̲�� ȵ��İ 
� ������ �ú� ȵ��İ; ������ ȵ��İ �� ȵ��ĵ.)
%% 197
\body
���������& (�����µ�� �� �����.) ش�� � �����; �º�˲��� �����; ���ž��� 
� �����; ����˲��� �����; ���� � ó��; ������ ���̳� � ó��; ���� � ����; 
������ �����̲�� � ����; ������Ǹ������ � ������� � ����; ������Ǹ������ � 
������� � ����, ���� � ó��; �Ǹ°�� ���̳�; ���� � �¾��; ����� �°��� 
(���¾�) ������ �ú��; ����� ����� �ú�� �°��� �� ������ �ú�;
����� ���˻�� ������ �ú��; ��������; �°��� ���˻�� �� �¾�; ����� ������ 
�ú�� �°��� �� ����� �ú�; �̵� �� �°����; �°��� �°��� �� �¾�; 
����� ���˻�� ������ �ú��;
��������; ���� � ó��; �°��� ���˻�� � ó��; ���� � ����;
����� �����̲�� ������ �ú��; ������ϵ� �����̲��; ������ �����̲�� � 
������; ���� � �¾��; ����� �°��� ������ �ú��; �̵� �� �°����; ���� � 
����; �°��� �°��� � ����.\cr
�����&     (���� �� �����.) Ҹ��� �����µ��; (�����µ�� ����� ȵ��İ);
���� � �����.\cr
���������& ѵ��� �����̲�� �� ������ ������ �ú��; ������ϵ� �����̲��, 
���� � �����; ������ϵ� �����̲��; ������ �����̲�� � �����.\cr
�����& �º�˲��� �����; ����� �����µ��; (�����µ�� ����� ȵ��İ); 
���ž��� � �����; ���� � ����.\cr
���������& ѵ��� �����̲�� ������ �ú��.\cr
�����& ش�� � �¾��.\cr
���������& 浻����; �����ϵ�; �������������; Ƶ�����; �����ϵ�;
����� �������� � ������; ����ò��� �²��; ������ �����̲�� � ������.\cr
�����&྽ϵ� �����̲��; ȵ��� ü�����.\cr
���������& ش�� � ó��; ����� ���̳� ������ �ú��; ���� � �����; 
���ž��� � �����; ����˲��� �����. �������.\cr
\endtvscript

���� �����µ�̽� ���Ǹ°�� �Ƶ�����, ����� ����¸��, �¾ ��� ����� 
����϶������ �����¸���. ��������� ���°¾ǽ� ¾ǽ� �������ϻ�, ��� 
��ž����� ������ ����²��ɵ� ��ƾ, �¾ ��� ������ � �ú�� � �.~�.\ 
Ե��²�� ��µ��� ���ǰ��� � ���Ǹ������ ����������˼ �����½���ϼ, 
�����½���� �����ü��� ����²�� ������°�� � ���������¸ �� ¾��, ����̺� 
�˿�¾ ����� � ����̺� ��� ����²��ɵ� ��ƾ �˻� ������. �°µ�� ����� 
���Ǹ�� ���������˵ �Ƶ����� ��� ¾��, �¾�� ��ϲ��� ��ó��  �����²� ���������.

షü�����, ���� ���ȸ� �Ƶ����� ���ž����� �������˲���, ������ ǵ� 
���°����, � µ� ����� �¾ ����ž���� ������� �� �Ƶ������, ��������˼ 
�����½˼ ��¾���. ݸ�� ��������� �Ƶ����� � ¾� ����, � ��¾��� �� 
�����̷����� � µ����������� ������ǵ (��---��ÿ�˹ ����, ��-������� ����, 
��---���̽�� ����).

\tvscript �Ƶ����� 1. �÷˺�.
\body
��.& �����µ�� ������� � ���� Ÿ����.\cr
��.& ۸ƾ �����µ��.\cr
��.& �����µ�� �ž��� � Ÿ����.\cr
��.& �����µ�� ����� �� �¾�� ���˻�� �����.\cr
��.& ���� ����ö� Ÿ����.\cr
��.& �����µ�� ����� ȵ��İ.\cr
��.& ���� � ������� ������ ����� ��� ���Ǿ� �����µ��, ��� Ų�°���� �� ������.\cr
��.& ���� ��Ų��˲��� �����̲��.\cr
��.& �����ϵ�, �������� � �����µ��.\cr
��.& ���� ����� ��Ⱥ� � ���̳���.\cr
��.& �����µ�� Ȱ°����.\cr
��.& �����µ�� ü�����. ��°���� ��������� ��� ���������� � ȵ��İ, ������ �� �¾�.\cr
��.& ���� ��ž��� �� ����� � ���̳���.\cr
%% 199
��.& ⵻� �����µ��, ���������� ����ɵ� �� �¾��. ڰ���� ��������� �����. (ἵ�.)\cr
\endtvscript

\tvscript
�Ƶ����� 2. �÷˺�.
\body
��.& ޺��. ߾ϲ�ϵ��� �����µ��.\cr
��.& �����µ�� �ž��� � Ÿ���� � ��ü� ��Ⱥ��� �����.\cr
��.& �����µ�� ������ ��Ⱥ� � ���̳��� �� ��Ǻ�.\cr
��.& �����µ�� ����� �� �¾�� �����.\cr
��. & �����µ�� �������� ���� �����. ݰǸ���� �Ǹ°�� ���̳�. ἵ����.\cr
��. & ���� ����ö� Ÿ����.\cr
��. & Ҹ� ǵ��� ����.\cr
��. & �����µ�� ����� ȵ��İ ǵ��� ����.\cr
��. & ���� �ž��� � Ÿ����. 岰°���� �� �����̲��. �������.\cr
��. & ����. ھ�Ǹ��� �� ����.\cr
��. & ����, Ȱ°��� ���� � �¾��, �¾�� �˿���, \dots{} ������ ���²˹.\cr
��. & �����µ�� �ž��� �� Ÿ���� � ��Ⱥ��� �����%
% !!! �����������, �ô� �������� ������ �� ���������� ���¸���̽�� ����
\note{}{\copyright~1962 by Columbia Broadcasting System, Inc. All Rights 
Reserved. Used by permission. Ի� ���̽��ȸ� ������� ��. J.~E.~Pfeiffer, 
The Thinking Machine (New York: J. B. Lippincott, 1962).}.\cr
\endtvscript

��ȵ���������� �α���� ����ɸ�� ��¾�� �.~�û�, ���°���ɸ� 
µ����������� ���������, ���������ȸ� ���� ��������� ������Ⱦ� �̵�� � 
������� ���, � °��� �.~��� �~X.~ܾ��, ��¾�˵ �������� � �»����� ���������.

ѵ� ��������, � Ǹ°µ�� ��������� ���� ����������� � ¾�, ��� �� �� ��� 
�������� ��������� ������������� ��µ��������� ²��ǵ�²�. �¾ � ���� Ƶ�� 
������� ÿ��������.

%% 200

\chapter{���ļ�¸��} %% 4
\epigraph
Ҳ��� ¾�� �¾ ��� ��ǵ�� ����� Ż���½��� � ��µ��¸ǵ���� ����¸�� (� 
����α����˵ ��ô����-��µ��¸��!), ��ǵ�� °����, �¾ ����� ��������� �� 
� ��Ȱ�� ��Ǹ���µ��, ǵ� �˿���ϵ�˵ ��� ����ȸ�� Ǹ����� ü�������, 
�������, �����ǵ��� ������½�� � �ñ�ǵ���� ������, ��¾�˵ 
����϶��� ���ǽ� � ������ ��ô�� �����ö������� �ȸ���, � �°� �����Ȼ��� 
��� µ�, ����� �������� � ô����� �����²� ����� �� ��������� �¸ ����Ÿ.
\signed
Զ�� ݵ��� (1614)

\epigraph
������ �� ���� �����˲���. ݵ� ����ȵ� �ȸ���, ǵ� ���˲��� ���ļ�¸�� 
¾ǽ�� ��ú��. ��ɵ�²���~\dots{} °��˵ ������, ÿ������ɸ� Ǹ�����, 
���¸�� ��¾�˵ ����� ���� ü ¸�� �����. ݰ������, ���� �� ��ž��µ 
�ü��, �����˲�� Ǹ��� �¾������ ���ǰ�� ����� �����, � ��µ� ������ ����, 
�� ������ ����ǰ�µ ����˹ ���û�°�.
\signed
Ӿ����� ۰ ��� (19~�.)

\epigraph
ݵ ���� �����°���� ����, �¾�� ����-���ô� ������������� �˿������ 
ü������� �� ��������� $40\ 000$ ��� ���� $4\ 000$~�����Ƹ� � ǰ�; °��� 
�������̽�� ���������, ��� ����ž� � ���̼���ǽ�� ���µ��, �� ����õ� 
���Ϸ˲��� ����� ǵ����ǵ�²� ���� ������̺�� ��ǽ��µ�.
\signed
�.~X.~�͹�� (1936)

�������� Ƶ�� �¾� �����---�ɰµ�̽�� ������������ ǵ�����
%% !!! bugfix  ������� => �������� 
�������� ����²�� ���ļ�¸��: ��������, 
��Ǹ°���, ü������� � �������. ܽ���� �Ǹ°�� ���ļ�¸�� �������̽�� 
�����, ��¾��� ���ǰ�� ��µ� � Ⱥ��� � ����²�� ��¾��� �˿������ ��ȸ��, 
��, ��� �� ò����, ���ļ�¸��---�¾ ò����µ�̽˹ �������, ����ɸ� ����� 
��µ������ �����¾�. ���ļ�¸�� ����� � ������ �¾�� ����Ⱦ�� Ǹ��� 
��ȸ���� ����������, �¾ ����� ���˼ ��������̽˼ ������� ����������� 
��ĵ�¸��˵ ��¾�� ��Ǹ������ � Ǹ�����.

���ļ�¸��---�¾ �� ����� ���� ����� � ��� �ɵ ������ ��������ɰ��� ������� 
��ú�, �˳���Ȱ� ������ ���� � ������� ��¾���. � �¾� ����� �� 
�����������õ� ������¼� �˿������� ���ļ�¸ǵ���� �����Ƹ� ��� ������� 
¸���� ����Ǹ�, °����, ��� Ǹ��� "� ������ɵ� ¾Ǻ��", �ǵ�� ����ȸ� 
Ǹ���, ����� (��Ƹ����̽˵ Ǹ���), �����ǻ��� � �µ����˵ �ϴ�; �� ���ô�� 
°��� ��Ϸ���˵ � �¸� �������, °���, ��� �������������� �� ����� 
���µ�� �Ǹ������ � ��ó��, ���������� Ǹ��� �� �����µ�� � ��Ǹ������ 
�����ǻ����.

%% 201
\bye