\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