\input style %% !! rAZOBRATXSYA, GDE M I sM? \ex[vm20] pUSTX~$S$---MNOZHESTVO I~$\cM$---SOVOKUPNOSTX EGO PODMNOZHESTV. pREDPOLOZHIM, CHTO~$p$---FUNKCIYA, ZADANNAYA NA MNOZHESTVAH IZ~$\cM$, PRINIMAYUSHCHAYA NA NIH DEJSTVITELXNYE ZNACHENIYA, I CHTO $p(M)$~OBOZNACHAET VEROYATNOSTX TOGO, CHTO "SLUCHAJNO" VYBRANNYJ |LEMENT IZ~$S$ PRINADLEZHIT~$M$. oBOBSHCHITE OPREDELENIYA~v I~D TAK, CHTOBY POLUCHITX HOROSHEE OPREDELENIE PONYATIYA $k\hbox{-RASPREDELENNOJ}$ POSLEDOVATELXNOSTI~$\$ |LEMENTOV MNOZHESTVA~$S$ PO OTNOSHENIYU K RASPREDELENIYU VEROYATNOSTEJ~$p$. \rex[vm30] (gERMAN vEJLX.) pOKAZHITE, CHTO POSLEDOVATELXNOSTX~$\$ $k\hbox{-RASPREDELENA}$ NA~$[0, 1)$ V TOM I TOLXKO TOM SLUCHAE, KOGDA \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 } DLYA KAZHDOGO MNOZHESTVA CELYH CHISEL~$c_1$, $c_2$,~\dots, $c_k$, GDE NE VSE~$c_j$ ODNOVREMENNO RAVNY NULYU. \ex[m34] pOKAZHITE, CHTO $b\hbox{-ICHNAYA}$ POSLEDOVATELXNOSTX~$\$ $k\hbox{-RASPREDELENA}$ V TOM I TOLXKO TOM SLUCHAE, KOGDA VSE POSLEDOVATELXNOSTI~$\$ \emph{RAVNOMERNO RASPREDELENY} PRI USLOVII, CHTO~$c_1$, $c_2$,~\dots, $c_k$ YAVLYAYUTSYA CELYMI CHISLAMI S~$\NOD(c_1,~\ldots, c_k)=1$. \ex[m30] pOKAZHITE, CHTO POSLEDOVATELXNOSTX~$\$ $k\hbox{-RASPREDELENA}$ NA~$[0,1)$ V TOM I TOLXKO TOM SLUCHAE, KOGDA VSE POSLEDOVATELXNOSTI~$\$ \emph{RAVNOMERNO RASPREDELENY} PRI USLOVII, CHTO~$c_1$, $c_2$,~\dots, $c_k$---NEKOTORYE CELYE CHISLA, NE RAVNYE NULYU ODNOVREMENNO. \ex[vm20] pOSLEDOVATELXNOSTX NAZYVAETSYA "BELOJ POSLEDOVATELXNOSTXYU", ESLI VSE KO|FFICIENTY POSLEDOVATELXNOJ KORRELYACII RAVNY NULYU, T.~E.\ ESLI SOOTNOSHENIE IZ SLEDSTVIYA~S SPRAVEDLIVO PRI \emph{VSEH}~$k\ge1$. (kAK VIDNO IZ SLEDSTVIYA~S, $\infty\hbox{-RASPREDELENNAYA}$ POSLEDOVATELXNOSTX YAVLYAETSYA BELOJ.) pOKAZHITE, CHTO ESLI $[0,1)\hbox{-POSLEDOVATELXNOSTX}$ RAVNOMERNO RASPREDELENA, TO ONA YAVLYAETSYA BELOJ TOGDA I TOLXKO TOGDA, KOGDA \EQ{ \lim_{n\to\infty}{1\over n}\sum_{0\le j < n} (U_j-1/2)(U_{j+k}-1/2)=0 \rem{PRI VSEH~$k\ge 1$.} } \ex[vm34] (dZH. fR|NKLIN.) oPREDELENNAYA V PREDYDUSHCHEM UPRAZHNENII BELAYA POSLEDOVATELXNOSTX, BEZUSLOVNO, MOZHET NE BYTX SLUCHAJNOJ. pUSTX $U_0$, $U_1$,~\dots{} ESTX $\infty\hbox{-RASPREDELENNAYA}$ POSLEDOVATELXNOSTX. oPREDELIM POSLEDOVATELXNOSTX $V_0$, $V_1$,~\dots{} SLEDUYUSHCHIM OBRAZOM: \EQ{ \eqalignter{ (V_{2n-1}, V_{2n})&=(U_{2n-1}, U_{2n}), & \rem{ESLI $(U_{2n-1}, U_{2n})\in G$,}\cr (V_{2n-1}, V_{2n})&=(U_{2n}, U_{2n-1}), & \rem{ESLI $(U_{2n-1}, U_{2n})\notin G$},\cr } } GDE~$G$---MNOZHESTVO~$\set{(x,y) \mid x-(1/2)\le y \le x \ror x+(1/2)\le y}$. pOKAZHITE, CHTO (a)~$V_0$, $V_1$,~\dots{} ESTX RAVNOMERNO RASPREDELENNAYA I BELAYA POSLEDOVATELXNOSTX, (b)~$\Pr(V_n>V_{n+1})=5/8$. (oTSYUDA VIDNA SLABOSTX TESTA POSLEDOVATELXNOJ KORRELYACII.) \ex[vm49] pUSTX~$\$---RAVNOMERNO RASPREDELENNAYA BELAYA POSLEDOVATELXNOSTX. yaVLYAETSYA LI CHISLO~$5/8$ V PREDYDUSHCHEM UPRAZHNENII NAIBOLXSHIM VOZMOZHNYM ZNACHENIEM VELICHINY~$\Pr(V_n>V_{n+1})$? \rex[m24] iSPOLXZUYA POSLEDOVATELXNOSTX~\eqref[11], POSTROJTE $3\hbox{-RASPREDELENNUYU}$ NA~$[0,1)$ POSLEDOVATELXNOSTX, DLYA KOTOROJ~$\Pr(U_{2n}\ge1/2)=3/4$. \ex[vm34] pUSTX $X_0$, $X_1$, \dots{} ESTX $(2k)\hbox{-RASPREDELENNAYA}$ DVOICHNAYA POSLEDOVATELXNOSTX. pOKAZHITE, CHTO \EQ{ \Prsup(X_{2n}=0)\le 1/2+\perm{2k-1}{k}\bigg/2^{2k}. } %% 192 \rex[m39] pOSTROJTE $(2k)\hbox{-RASPREDELENNUYU}$ DVOICHNUYU POSLEDOVATELXNOSTX, DLYA KOTOROJ SPRAVEDLIVO RAVENSTVO \EQ{ \Pr(X_{2n}=0)=1/2+\perm{2k-1}{k}\bigg/ 2^{2k}. } (oTSYUDA SLEDUET, CHTO NERAVENSTVO V PREDYDUSHCHEM UPRAZHNENII NELXZYA ULUCHSHITX.) \ex[m30] pOKAZHITE, CHTO SUSHCHESTVUET POSLEDOVATELXNOSTX NA~$[0,1)$ UDOVLETVORYAYUSHCHAYA OPREDELENIYU~R5, NO TAKAYA, CHTO~$\nu_n/n\ge 1/2$ DLYA VSEH~$n>0$, GDE $\nu_n$~ESTX CHISLO TEH~$j$---"SLUCHAJNAYA" $b\hbox{-ICHNAYA}$ POSLEDOVATELXNOSTX V SMYSLE OPREDELENIYA~R5 I~$\cR$---VYCHISLIMOE PRAVILO POSTROENIYA PODPOSLEDOVATELXNOSTI, KOTOROE OPREDELYAET BESKONECHNUYU PODPOSLEDOVATELXNOSTX~$\\cR$. pOKAZHITE, CHTO |TA PODPOSLEDOVATELXNOSTX NE TOLXKO $1\hbox{-RASPREDELENA}$, NO I "SLUCHAJNA" V SMYSLE OPREDELENIYA~R5. \ex[vm24] pUSTX~$\$ I~$\$---BESKONECHNYE, NE IMEYUSHCHIE OBSHCHIH |LEMENTOV PODPOSLEDOVATELXNOSTI POSLEDOVATELXNOSTI~$\$. (eTO ZNACHIT, CHTO $r_0$~ESTX SOSTAVNAYA PODPOSLEDOVATELXNOSTX, DLYA KOTOROJ~$t_0$---DVOICHNAYA POSLEDOVATELXNOSTX, KOTORAYA YAVLYAETSYA "SLUCHAJNOJ" V SMYSLE OPREDELENIYA~R6. pOKAZHITE, CHTO POSLEDOVATELXNOSTX~$\$ NA~$[0,1)$, SLEDUYUSHCHIM OBRAZOM OPREDELENNAYA V DVOICHNOJ ZAPISI: \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 } } YAVLYAETSYA SLUCHAJNOJ V SMYSLE OPREDELENIYA~R6. \ex[m48] sUSHCHESTVUYUT LI POSLEDOVATELXNOSTI, UDOVLETVORYAYUSHCHIE OPREDELENIYU~R4, NO NE~R5? \ex[m50] (a.~n.~kOLMOGOROV.) pUSTX ZADANY~$N$, $n$ I~$\varepsilon$. nAJTI NAIMENXSHEE CHISLO ALGORITMOV V MNOZHESTVE~$A$, TAKIH, CHTOBY NE SUSHCHESTVOVALI $(n,\varepsilon)\hbox{-SLUCHAJNYE}$ PO OTNOSHENIYU K~$A$ DVOICHNYE POSLEDOVATELXNOSTI DLINY~$N$. (eSLI NELXZYA POLUCHITX TOCHNYE FORMULY, MOZHNO LI NAJTI ASIMPTOTICHESKIE FORMULY? gLAVNOE V |TOJ ZADACHE---OPREDELITX, NASKOLXKO BLIZKA VELICHINA~\eqref[35] K "NAILUCHSHEJ VOZMOZHNOJ".) \ex[vm45] (k.~rOT.) pUSTX~$\$---POSLEDOVATELXNOSTX NA~$[0,1)$ I~$\nu_n(u)$---CHISLO NEOTRICATELXNYH CELYH CHISEL~$j$ NA~$[0,1)$ IMEET MESTO NERAVENSTVO \EQ{ \abs{\nu_n(u)-un}>c\sqrt{\log N} } DLYA NEKOTORYH~$n$ I~$u$, TAKIH, CHTO~$0\le n < N$, $0\le u < 1$. (dRUGIMI SLOVAMI, NIKAKAYA POSLEDOVATELXNOSTX NA~$[0,1)$ NE MOZHET BYTX \emph{SLISHKOM} RAVNOMERNO RASPREDELENNOJ.) %% 193 \subchap{vyvody} % 3.6 v |TOJ GLAVE MY ZATRONULI BOLXSHOJ KRUG VOPROSOV: KAK VYRABATYVATX SLUCHAJNYE CHISLA, KAK PROVERYATX IH, KAK IH PREOBRAZOVYVATX I KAK POLUCHATX SVYAZANNYE S NIMI TEORETICHESKIE REZULXTATY. oSNOVNOJ VOPROS, KOTORYJ, NAVERNOE, VOZNIKNET PO PROCHTENII |TOJ GLAVY U BOLXSHINSTVA CHITATELEJ, MOZHNO SFORMULIROVATX SLEDUYUSHCHIM OBRAZOM: "kAKOV ZHE REZULXTAT VSEJ |TOJ TEORII? gDE PROSTOJ I KACHESTVENNYJ DATCHIK, KOTORYJ YA MOG BY ISPOLXZOVATX V SVOIH PROGRAMMAH KAK NADEZHNYJ ISTOCHNIK SLUCHAJNYH CHISEL?" iZ VSEGO MATERIALA, IZLOZHENNOGO V |TOJ GLAVE, SLEDUET, CHTO "NAILUCHSHIJ" I "PROSTEJSHIJ" DATCHIK SLUCHAJNYH CHISEL POLUCHAETSYA SLEDUYUSHCHIM OBRAZOM. v NACHALE PROGRAMMY USTANOVITE PEREMENNUYU~$X$ RAVNOJ NEKOTOROMU CELOMU ZNACHENIYU~$X_0$. eTA PEREMENNAYA~$X$ DOLZHNA ISPOLXZOVATXSYA TOLXKO DLYA POROZHDENIYA SLUCHAJNYH CHISEL. kAK TOLXKO DLYA RABOTY PROGRAMMY POTREBUETSYA SLEDUYUSHCHEE SLUCHAJNOE CHISLO, NUZHNO USTANOVITX \EQ[1]{ X\asg(aX+c) \bmod m } I ISPOLXZOVATX NOVOE ZNACHENIE~$X$ V KACHESTVE SLUCHAJNOJ VELICHINY. pRI VYBORE $X_0$, $a$, $c$ I~$m$ NEOBHODIMO SOBLYUDATX NEKOTORYE PRAVILA I ISPOLXZOVATX SLUCHAJNYE CHISLA OSMYSLENNO, RUKOVODSTVUYASX SLEDUYUSHCHIMI PRINCIPAMI. {\medskip\narrower \item{i)}chISLO~$X_0$ MOZHET BYTX PROIZVOLXNYM. eSLI PO PROGRAMME DELAETSYA NESKOLXKO PROSCHETOV I KAZHDYJ RAZ ZHELATELEN RAZLICHNYJ ISTOCHNIK SLUCHAJNYH CHISEL, PRISVOJTE~$X_0$ POSLEDNEE ZNACHENIE~$X$, POLUCHENNOE VO VREMYA PREDYDUSHCHEGO PROSCHETA, ILI (ESLI |TO BOLEE UDOBNO) USTANOVITE~$X_0$ RAVNYM TEKUSHCHEMU MOMENTU VREMENI I KALENDARNOJ DATE. \item{ii)}chISLO~$m$ DOLZHNO BYTX VELIKO. uDOBNO VYBIRATX EGO RAVNYM RAZMERU SLOVA VYCHISLITELXNOJ MASHINY, POSKOLXKU PRI |TOM |FFEKTIVNO VYCHISLYAETSYA~$(aX+c)\bmod m$. vOPROSY, SVYAZANNYE S VYBOROM~$m$, BOLEE PODROBNO RAZBIRAYUTSYA V P.~3.2.1.1. zNACHENIE~$(aX+c)\bmod m$ SLEDUET VYCHISLYATX \emph{TOCHNO,} BEZ OSHIBOK OKRUGLENIYA. \item{iii)}eSLI $m$~PREDSTAVLYAET SOBOJ STEPENX DVOJKI (T.~E.\ ESLI ISPOLXZUETSYA MASHINA, RABOTAYUSHCHAYA V DVOICHNOJ SISTEME SCHISLENIYA), VYBERITE~$a$ TAKIM, CHTOBY~$a\bmod8=5$. eSLI $m$~ESTX STEPENX~$10$ (T.~E.\ ISPOLXZUETSYA MASHINA, RABOTAYUSHCHAYA V DESYATICHNOJ SISTEME SCHISLENIYA), VYBERITE~$a$ TAKIM, CHTOBY~$a\bmod 200=21$. %% 194 pRI TAKOM VYBORE VELICHINY~$a$, PRI USLOVII, CHTO $c$~VYBIRAETSYA OPISANNYM NIZHE SPOSOBOM, GARANTIRUETSYA, CHTO DATCHIK SLUCHAJNYH CHISEL DAST VSE $m$~VOZMOZHNYH RAZLICHNYH ZNACHENIJ~$X$ PREZHDE, CHEM ONI NACHNUT POVTORYATXSYA (SM.~P.~3.2.1.2), I, KROME TOGO, GARANTIRUETSYA VYSOKAYA "MOSHCHNOSTX" (SM.~P.~3.2.1.3). \item{iv)}mNOZHITELX~$a$ DOLZHEN PREVOSHODITX VELICHINU~$\sqrt{m}$, ZHELATELXNO, CHTOBY ON BYL BOLXSHE~$m/100$, NO MENXSHE~$m-\sqrt{m}$. pOSLEDOVATELXNOSTX RAZRYADOV V DVOICHNOM ILI DESYATICHNOM PREDSTAVLENII~$a$ \emph{NE} DOLZHNA IMETX PROSTOGO, REGULYARNOGO VIDA. pO |TOMU POVODU SM., NAPRIMER, P.~3.2.1.3 I UPR.~3.2.1.3-8. lUCHSHE VSEGO V KACHESTVE |TOGO MNOZHITELYA VYBRATX NAUDACHU NEKOTORUYU POSTOYANNUYU, NAPRIMER, \EQ[2]{ a=3141592621. } (eTA POSTOYANNAYA UDOVLETVORYAET OBOIM USLOVIYAM IZ~(iii).) vYSKAZANNYH SOOBRAZHENIJ OBYCHNO BYVAET DOSTATOCHNO DLYA POLUCHENIYA UDOVLETVORITELXNOGO MNOZHITELYA, ODNAKO, ESLI DATCHIK SLUCHAJNYH CHISEL, ISPOLXZUETSYA INTENSIVNO, MNOZHITELX~$a$, KROME TOGO, SLEDUET VYBIRATX TAK, CHTOBY UDOVLETVORYALSYA "sPEKTRALXNYJ TEST" (P.~3.3.4). \item{v)}pOSTOYANNAYA~$c$ DOLZHNA BYTX RAVNA NECHETNOMU CHISLU (KOGDA $m$~ESTX STEPENX DVOJKI) I KROME TOGO NE DOLZHNA BYTX KRATNOJ~$5$ (KOGDA $m$~ESTX STEPENX~$10$). zhELATELXNO VYBIRATX~$c$ TAKIM OBRAZOM, CHTOBY OTNOSHENIE~$c/m$ BYLO BY PRIBLIZITELXNO RAVNO VELICHINE, PRIVEDENNOJ V P.~3.3.3, SOOTNOSHENIE~\eqref[41]. \item{vi)}mENEE ZNACHIMYE (PRAVYE) RAZRYADY~$X$ NE OCHENX HOROSHI S TOCHKI ZRENIYA SLUCHAJNOSTI, PO|TOMU PRI ISPOLXZOVANII CHISLA~$X$ OSNOVNUYU ROLX DOLZHNY IGRATX NAIBOLEE ZNACHIMYE RAZRYADY. vOOBSHCHE GOVORYA, LUCHSHE RASSMATRIVATX~$X$ KAK SLUCHAJNUYU DROBX~$X/m$ V INTERVALE MEZHDU~$0$ I~$1$, T.~E.\ PREDSTAVLYATX~$X$ S DESYATICHNOJ TOCHKOJ SLEVA, CHEM KAK SLUCHAJNOE CELOE CHISLO; RASPOLOZHENNOE MEZHDU~$0$ I~$m-1$. dLYA TOGO, CHTOBY POLUCHITX SLUCHAJNOE CELOE CHISLO, RASPOLOZHENNOE MEZHDU~$0$ I~$k-1$, SLEDUET UMNOZHITX~$X$ NA~$k$ I OTBROSITX LISHNIE RAZRYADY (SM.\ NACHALO P.~3.4.2). \medskip} v |TIH SHESTI "PRAVILAH" ZAKLYUCHENO VSE NAIBOLEE VAZHNOE IZ TOGO, CHTO NUZHNO ZNATX O SLUCHAJNYH CHISLAH, POLUCHAEMYH NA VYCHISLITELXNOJ MASHINE. k SOZHALENIYU, V ZNACHITELXNOJ CHASTI MATERIALA, OPUBLIKOVANNOGO K MOMENTU NAPISANIYA |TOJ GLAVY, REKOMENDUETSYA ISPOLXZOVATX DATCHIKI, V KOTORYH NASHI PRAVILA NARUSHAYUTSYA. vO MNOGIH STATXYAH IMEYUTSYA VAZHNYE TEORETICHESKIE REZULXTATY PO VYRABOTKE SLUCHAJNYH CHISEL, ODNAKO PREDLAGAEMYE V NIH KONKRETNYE METODY NESOVERSHENNY, CHTO BYLO OBNARUZHENO IH AVTORAMI SLISHKOM POZDNO. vOZMOZHNO, CHTO I REKOMENDUEMYE NAMI DATCHIKI SLUCHAJNYH CHISEL %% 195 V BUDUSHCHEM BUDUT PRIZNANY NEUDOVLETVORITELXNYMI. mY NADEEMSYA, CHTO |TOGO NE PROIZOJDET, ODNAKO PROSHLOE UCHIT NAS OSTOROZHNOSTI. nAIBOLEE BLAGORAZUMNO BYLO BY POSTUPATX TAK: PREZHDE CHEM VSERXEZ OTNOSITXSYA K REZULXTATAM RASCHETA PO PROGRAMMAM, ISPOLXZUYUSHCHIM METOD mONTE-kARLO, SLEDUET SCHITATX PO KRAJNEJ MERE DVAZHDY, ISPOLXZUYA SOVERSHENNO RAZLICHNYE ISTOCHNIKI SLUCHAJNYH CHISEL. tAKOJ PODHOD NE TOLXKO GARANTIRUET USTOJCHIVOSTX REZULXTATOV, NO I KONTROLIRUET KACHESTVO DATCHIKA. (lYUBOJ DATCHIK SLUCHAJNYH CHISEL BUDET DAVATX PLOHIE REZULXTATY PO KRAJNEJ MERE V ODNOM KLASSE PRILOZHENIJ.) hOTYA LINEJNYE KONGRU|NTNYE POSLEDOVATELXNOSTI, ANALOGICHNYE OPISANNYM ZDESX, OBYCHNO YAVLYAYUTSYA UDOVLETVORITELXNYM ISTOCHNIKOM SLUCHAJNYH CHISEL, V P.~3.3.4 (SM.~(3.3.4-13)) UKAZANO VAZHNOE OGRANICHENIE IH KACHESTVA. iZ UPR.~3.3.4-27 SLEDUET, CHTO LINEJNYE KONGRU|NTNYE POSLEDOVATELXNOSTI NE GODYATSYA DLYA RASCHETOV PO METODU mONTE-kARLO S "VYSOKIM RAZRESHENIEM". eSLI TREBUETSYA BOLXSHAYA NEZAVISIMOSTX SLUCHAJNYH CHISEL, NEOBHODIMO ISPOLXZOVATX METODY P.~3.2.2. pREVOSHODNYJ SPISOK LITERATURY, OPUBLIKOVANNYJ PO |TOMU VOPROSU DO 1962~G., SODERZHITSYA V STATXE t.~hALDA I a.~dOBELLA "Random Number Generators" ({\sl SIAM Review,\/} {\bf 4} (1962), 230--254). v SVYAZI S |TIM NAM NE NUZHNO PRIVODITX SSYLKI NA RANNIE PUBLIKACII, KROME TEH, KOTORYE UZHE UPOMYANUTY V |TOJ GLAVE. sREDI RABOT, POYAVIVSHIHSYA POSLE 1962~G., OSOBENNO SLEDUET OTMETITX STATXYU m.~mAKLARENA I dZH.~mARSALXI "Uniform random Generators" ({\sl JACM,\/} {\bf 12} (1965), 83--89), POTOMU CHTO V NEJ VPERVYE UKAZANY NEDOSTATKI LINEJNYH KONGRU|NTNYH DATCHIKOV S NEPRAVILXNO VYBRANNYMI MNOZHITELYAMI. v |TOJ ZHE STATXE BYL PREDLOZHEN ALGORITM~3.2.2m. eTO HOROSHIJ METOD, KOTORYJ ZNACHITELXNO ULUCHSHAET KACHESTVO DATCHIKA I TREBUET TOLXKO VDVOE BOLXSHEGO VREMENI SCHETA. mNOGIE ZADACHI, ZATRONUTYE V NASTOYASHCHEJ GLAVE, RASSMATRIVAYUTSYA V KNIGE b.~yaNSSONA "Random Number Generators" (Stockholm, Almqvist and Wiksell, 1966). v KNIGE dZH.~hAMMERSLI I~d.~h|NDSKOMBA "Monte Carlo Methods" (London, Methuen, 1964) PODROBNO IZUCHAETSYA PRIMENENIE SLUCHAJNYH CHISEL V VYCHISLITELXNYH METODAH. v |TOJ KNIGE POKAZANO, CHTO |FFEKTIVNOSTX MNOGIH CHISLENNYH METODOV VOZRASTAET, ESLI ISPOLXZOVATX "KVAZISLUCHAJNYE" CHISLA, SPECIALXNO PODOBRANNYE DLYA RESHENIYA OPREDELENNOJ ZADACHI (I NE OBYAZATELXNO UDOVLETVORYAYUSHCHIE STATISTICHESKIM TESTAM, O KOTORYH MY PISALI). v PRIVEDENNYH NIZHE UPRAZHNENIYAH IMEYUTSYA NEKOTORYE INTERESNYE PROEKTY PROGRAMM, ISPOLXZUYUSHCHIH SLUCHAJNYE CHISLA. vOZMOZHNO, CHTO ANALOGICHNYE PROEKTY PRIDUT V GOLOVU CHITATELYU. pO KRAJNEJ MERE ODIN DATCHIK SLUCHAJNYH CHISEL IMEETSYA POCHTI V LYUBOJ HOROSHEJ PROGRAMME. %% 196 \excercises \ex[21] nAPISHITE PODPROGRAMMU DLYA MASHINY~\MIX{} SO SLEDUYUSHCHIMI HARAKTERISTIKAMI: \descrtable{ vYZOV: & |JMP RANDI|\cr sOSTOYANIE PRI VHODE:& $|rA|=k$, POLOZHITELXNOE CELOE~$ < 5000$\cr sOSTOYANIE PRI VYHODE: & $|rA|\asg \hbox{SLUCHAJNOE CELOE} Y$, $1\le Y \le k$, KAZHDOE CELOE ZNACHENIE RAVNOVEROYATNO, $|rX|=?$; TRIGGER PEREPOLNENIYA SBROSHEN.\cr } (iSPOLXZUJTE METOD, PREDLOZHENNYJ V |TOM PARAGRAFE, NO VOZXMITE~$c=1$.) \rex[21] nEKOTORYE OPASALISX, CHTO VYCHISLITELXNYE MASHINY SO VREMENEM BUDUT UPRAVLYATX MIROM. iH USPOKAIVAYUT ZAYAVLENIEM, CHTO MASHINA NE MOZHET SDELATX NICHEGO DEJSTVITELXNO NOVOGO, POSKOLXKU ONA VSEGO LISHX VYPOLNYAET KOMANDY SVOEGO HOZYAINA, PROGRAMMISTA. lEDI lAVLEJS\note{1}% {sM.\ TOM~1, STR.~25.---{\sl pRIM. PEREV.\/}} PISALA V 1844~G.: "aNALITICHESKAYA MASHINA NE PRITYAZAET NA \emph{IZOBRETENIE} CHEGO-LIBO. oNA MOZHET DELATX VSE TO, \emph{CHTO MY SUMEEM EJ PRIKAZATX}". mNOGIE FILOSOFY RAZVIVALI |TU MYSLX. oBDUMAJTE |TO UTVERZHDENIE, IMEYA V VIDU DATCHIKI SLUCHAJNYH CHISEL. \ex[32] "iGRA V KOSTI". nAPISHITE PROGRAMMU, KOTORAYA MODELIRUET BROSANIE DVUH KOSTEJ, NA KAZHDOJ IZ KOTORYH S RAVNOJ VEROYATNOSTXYU VYPADAYUT ZNACHENIYA~$1$, $2$,~\dots{}, $6$. eSLI PRI PERVOM BROSANII OBSHCHAYA SUMMA RAVNA~$7$ ILI~$11$, IGRA SCHITAETSYA VYIGRANNOJ, ESLI ONA RAVNA~$2$, $3$ ILI~$12$---PROIGRANNOJ. pRI LYUBOJ DRUGOJ SUMME (NAZOVEM |TU SUMMU "STRELKOJ") PRODOLZHAJTE BROSANIYA, POKA NE VYPADET~$7$ (PROIGRYSH) ILI OPYATX POLUCHITSYA "STRELKA" (VYIGRYSH). sYGRAJTE DESYATX IGR. rEZULXTATY KAZHDOGO BROSANIYA KOSTEJ SLEDUET NAPECHATATX V VIDE~$mn$, GDE~$m$ I~$n$---CIFRY NA DVUH KOSTYAH, SNABDIV SOOTVETSTVUYUSHCHIMI KOMMENTARIYAMI VRODE "ZMEINYE GLAZA" I~T.~P. \ex[40] "sOLITER" (PASXYANS). nEKOTORYE TRATYAT DRAGOCENNOE VREMYA NA RASKLADYVANIE PASXYANSA "SOLITER". vOZMOZHNO, CHTO AVTOMATIKA VTORGNETSYA I V |TU OBLASTX. nAPISHITE PROGRAMMU, KOTORAYA (a)~TASUET SMODELIROVANNUYU KOLODU KART, (b)~RASKLADYVAET KAKOJ-LIBO OBYCHNYJ PASXYANS "SOLITER", OSNOVYVAYASX NA POLUCHENNOM PORYADKE KART V KOLODE, (c)~PECHATAET REZULXTAT IGRY, OTKUDA BUDET VIDNO, NASKOLXKO PROGRAMMA BYLA BLIZKA K USPEHU. sLEDUET SYGRATX NESKOLXKO IGR. mOZHNO SDELATX TAK, CHTOBY PO TREBOVANIYU PROGRAMMA NACHINALA "MOSHENNICHATX". \ex[46] \emph{mODELIROVANIE LITERATURNOGO TVORCHESTVA S POMOSHCHXYU VYCHISLITELXNOJ MASHINY.} 26~OKTYABRYA 1960~G.\ PO TELEVIZIONNOJ PROGRAMME~CBS POKAZYVALASX PEREDACHA, OZAGLAVLENNAYA "dUMAYUSHCHAYA MASHINA", V KOTOROJ, V CHASTNOSTI, ISPOLXZOVALISX DVE NEBOLXSHIE PXESY V STILE VESTERN, SOSTAVLENNYE PRI POMOSHCHI PROGRAMMY DLYA evm. nIZHE PRIVODYATSYA DVA |TIH SCENARIYA V TOM VIDE, V KOTOROM IH VYDALA MASHINA. \tvscript sCENARIJ 1. (rEVOLXVER V PRAVOJ RUKE; DENXGI V LEVOJ RUKE; STAKAN NA STOLE; BUTYLKA NA STOLE; KOBURA NA GRABITELE; REVOLXVER SHERIFA V PRAVOJ RUKE SHERIFA; KOBURA SHERIFA NA SHERIFE.) \body grabitel'& (gRABITELX ZA OKNOM.) iDET K DVERI; OTKRYVAET DVERX; PROHODIT V DVERX; ZAKRYVAET DVERX; IDET V UGOL; KLADET DENXGI V UGLU; IDET K STOLU; KLADET REVOLXVER NA STOL; SADITSYA I NERVNICHAET; SIDIT ZA STOLOM; BERET STAKAN (PUSTOJ) PRAVOJ RUKOJ; STAVIT STAKAN NA STOL; BERET BUTYLKU PRAVOJ RUKOJ; NALIVAET; STAVIT BUTYLKU NA STOL; BERET STAKAN PRAVOJ RUKOJ; PXET IZ STAKANA; STAVIT STAKAN NA STOL; BERET BUTYLKU PRAVOJ RUKOJ; SIDYAT ZA STOLOM; SIDIT ZA STOLOM; IDET V UGOL; IDET K OKNU; IDET K STOLU; STAVIT BUTYLKU NA STOL; SADITSYA I NERVNICHAET; SIDIT ZA STOLOM; SIDIT I NERVNICHAET; IDET K OKNU; IDET K STOLU; BERET STAKAN PRAVOJ RUKOJ.\cr %% 197 sherif & (shERIF ZA OKNOM.) vIDIT GRABITELYA; (GRABITELX VIDIT SHERIFA);\cr grabitel'& sTAVIT STAKAN NA STOL; BERET REVOLXVER PRAVOJ RUKOJ; PROVERYAET REVOLXVER.\cr sherif& zhDET; OTKRYVAET DVERX; VIDIT GRABITELYA; (GRABITELX VIDIT SHERIFA); PROHODIT V DVERX.\cr grabitel'& iDET K OKNU; CELITSYA; STRELYAET; legko ranit sherifa.\cr sherif& iDET K OKNU; CELITSYA; STRELYAET; promahivaetsya, IDET K DVERI; IDET K OKNU.\cr grabitel'& iDET K DVERI; CELITSYA; CELITSYA.\cr sherif& cELITSYA; STRELYAET; promahivaetsya.\cr grabitel'& sTRELYAET; legko ranit sherifa.\cr sherif& iDET K DVERI; CELITSYA; STRELYAET; promahivaetsya; PROHODIT V DVERX; CELITSYA.\cr grabitel'& cELITSYA; STRELYAET; promahivaetsya; CELITSYA; STRELYAET; promahivaetsya.\cr sherif& sTRELYAET; promahivaetsya; IDET K OKNU; CELITSYA; STRELYAET; promahivaetsya. \cr grabitel'& cELITSYA; STRELYAET; promahivaetsya; CELITSYA; STRELYAET, promahivaetsya; CELITSYA; STRELYAET; legko ranit sherifa.\cr sherif& cELITSYA; STRELYAET; tochno popadaet v grabitelya.\cr grabitel'& rONYAET REVOLXVER; GRABITELX UMIRAET.\cr sherif& kLADET REVOLXVER V KOBURU; IDET K STOLU; BERET STAKAN (PUSTOJ) PRAVOJ RUKOJ; BERET LEVOJ RUKOJ STAKAN IZ PRAVOJ RUKI; BERET BUTYLKU PRAVOJ RUKOJ; NALIVAET; STAVIT BUTYLKU NA STOL; BERET PRAVOJ RUKOJ STAKAN IZ LEVOJ RUKI; PXET IZ STAKANA; BERET LEVOJ RUKOJ STAKAN IZ PRAVOJ RUKI; BERET BUTYLKU PRAVOJ RUKOJ; NALIVAET; STAVIT BUTYLKU NA STOL; BERET PRAVOJ RUKOJ STAKAN IZ LEVOJ RUKI; PXET IZ STAKANA; STAVIT STAKAN NA STOL; IDET V UGOL; BERET DENXGI PRAVOJ RUKOJ; IDET K DVERI, PROHODIT V DVERX; ZAKRYVAET DVERX. zanaves.\cr \endtvscript \tvscript sCENARIJ~2. (rEVOLXVER V PRAVOJ RUKE; DENXGI V LEVOJ RUKE; STAKAN NA STOLE; BUTYLKA NA STOLE; KOBURA NA GRABITELE; REVOLXVER SHERIFA V PRAVOJ RUKE SHERIFA; KOBURA SHERIFA NA SHERIFE.) %% 197 \body grabitel'& (gRABITELX ZA OKNOM.) iDET K DVERI; OTKRYVAET DVERX; PROHODIT V DVERX; ZAKRYVAET DVERX; IDET V UGOL; KLADET DENXGI V UGLU; IDET K OKNU; KLADET REVOLXVER U OKNA; OBLOKACHIVAETSYA I SMOTRIT V OKNO; OBLOKACHIVAETSYA I SMOTRIT V OKNO, IDET V UGOL; SCHITAET DENXGI; IDET K STOLU; BERET STAKAN (PUSTOJ) PRAVOJ RUKOJ; BERET LEVOJ RUKOJ STAKAN IZ PRAVOJ RUKI; BERET BUTYLKU PRAVOJ RUKOJ; NALIVAET; STAVIT BUTYLKU NA STOL; BERET PRAVOJ RUKOJ STAKAN IZ LEVOJ RUKI; PXET IZ STAKANA; STAVIT STAKAN NA STOL; BERET BUTYLKU PRAVOJ RUKOJ; NALIVAET; IDET V UGOL; STAVIT BUTYLKU V UGLU; IDET K OKNU; BERET REVOLXVER PRAVOJ RUKOJ; PROVERYAET REVOLXVER; KLADET REVOLXVER V KOBURU; IDET K STOLU; BERET STAKAN PRAVOJ RUKOJ; PXET IZ STAKANA; IDET K OKNU; STAVIT STAKAN U OKNA.\cr sherif& (shERIF ZA OKNOM.) vIDIT GRABITELYA; (GRABITELX VIDIT SHERIFA); IDET K DVERI.\cr grabitel'& bERET REVOLXVER IZ KOBURY PRAVOJ RUKOJ; PROVERYAET REVOLXVER, IDET K DVERI; PROVERYAET REVOLXVER; KLADET REVOLXVER U DVERI.\cr sherif& oTKRYVAET DVERX; VIDIT GRABITELYA; (GRABITELX VIDIT SHERIFA); PROHODIT V DVERX; IDET K OKNU.\cr grabitel'& bERET REVOLXVER PRAVOJ RUKOJ.\cr sherif& iDET K STOLU.\cr grabitel'& cELITSYA; STRELYAET; promahivaetsya; CELITSYA; STRELYAET; tochno popadaet v sherifa; PRODUVAET STVOL; KLADET REVOLXVER V KOBURU.\cr sherif&rONYAET REVOLXVER; SHERIF UMIRAET.\cr grabitel'& iDET V UGOL; BERET DENXGI PRAVOJ RUKOJ; IDET K DVERI; PROHODIT V DVERX; ZAKRYVAET DVERX. zanaves.\cr \endtvscript eSLI VNIMATELXNO PROCHITATX SCENARII, MOZHNO ZAMETITX, CHTO ONI POLNY NAPRYAZHENNOGO DRAMATIZMA. pROGRAMMA DOSTATOCHNO TOCHNO OPREDELYALA, GDE NAHODITSYA KAZHDOE DEJSTVUYUSHCHEE LICO, CHTO ONO DERZHIT V RUKAH I T.~D.\ dEJSTVIYA AKTEROV SLUCHAJNY I PODCHINYAYUTSYA OPREDELENNYM VEROYATNOSTYAM, VEROYATNOSTX NERAZUMNYH DEJSTVIJ VOZRASTAET V ZAVISIMOSTI OT TOGO, SKOLXKO VYPITO VISKI I SKOLXKO RAZ DEJSTVUYUSHCHEE LICO BYLO RANENO. chITATELX MOZHET IZUCHITX PRIVEDENNYE SCENARII DLYA TOGO, CHTOBY VYYAVITX DRUGIE SVOJSTVA PROGRAMMY. rAZUMEETSYA, DAZHE LUCHSHIE SCENARII PRIHODITSYA PEREDELYVATX, PREZHDE CHEM POSTAVITX, I TEM BOLEE |TO NEOBHODIMO SDELATX SO SCENARIEM, NAPISANNYM NEOPYTNYM AVTOROM. nIZHE PRIVEDENY SCENARII V TOM VIDE, V KOTOROM IH ISPOLXZOVALI V TELEVIZIONNOJ PEREDACHE (kp---KRUPNYJ PLAN, sp-SREDNIJ PLAN, dp---DALXNIJ PLAN). \tvscript sCENARIJ 1. mUZYKA. \body sp.& gRABITELX SMOTRIT V OKNO HIZHINY.\cr kp.& lICO GRABITELYA.\cr sp.& gRABITELX VHODIT V HIZHINU.\cr kp.& gRABITELX VIDIT NA STOLE BUTYLKU VISKI.\cr kp.& shERIF SNARUZHI HIZHINY.\cr sp.& gRABITELX VIDIT SHERIFA.\cr dp.& shERIF V DVERNOM PROEME VIDEN NAD PLECHOM GRABITELYA, OBA HVATAYUTSYA ZA KOBURY.\cr sp.& shERIF VYHVATYVAET REVOLXVER.\cr dp.& sTRELYAET, POPADAET V GRABITELYA.\cr sp.& shERIF BERET MESHKI S DENXGAMI.\cr sp.& gRABITELX SHATAETSYA.\cr sp.& gRABITELX UMIRAET. pYTAETSYA POSLEDNIJ RAZ VYSTRELITX V SHERIFA, PADAET NA STOL.\cr sp.& shERIF VYHODIT IZ DVERI S DENXGAMI.\cr %% 199 sp.& tELO GRABITELYA, NEPODVIZHNO LEZHASHCHEE NA STOLE. kAMERA DVIGAETSYA NAZAD. (sMEH.)\cr \endtvscript \tvscript sCENARIJ 2. mUZYKA. \body kp.& oKNO. pOYAVLYAETSYA GRABITELX.\cr sp.& gRABITELX VHODIT V HIZHINU S DVUMYA MESHKAMI DENEG.\cr sp.& gRABITELX KLADET MESHKI S DENXGAMI NA BOCHKU.\cr kp.& gRABITELX VIDIT NA STOLE VISKI.\cr sp. & gRABITELX NALIVAET SEBE VISKI. nACHINAET SCHITATX DENXGI. sMEETSYA.\cr sp. & shERIF SNARUZHI HIZHINY.\cr sp. & vID CHEREZ OKNO.\cr sp. & gRABITELX VIDIT SHERIFA CHEREZ OKNO.\cr dp. & shERIF VHODIT V HIZHINU. hVATAETSYA ZA REVOLXVER. vYSTREL.\cr kp. & shERIF. kORCHITSYA OT BOLI.\cr sp. & shERIF, SHATAYASX IDET K STOLU, CHTOBY VYPITX, \dots{} PADAET MERTVYJ.\cr sp. & gRABITELX UHODIT IZ HIZHINY S MESHKAMI DENEG% % !!! RAZOBRATXSYA, KUDA DEVAYUTSYA SNOSKI IZ VNUTRENNEJ VERTIKALXNOJ MODY \note{}{\copyright~1962 by Columbia Broadcasting System, Inc. All Rights Reserved. Used by permission. dLYA DALXNEJSHIH SPRAVOK SM. J.~E.~Pfeiffer, The Thinking Machine (New York: J. B. Lippincott, 1962).}.\cr \endtvscript vYSHEIZLOZHENNOE LYUBEZNO SOOBSHCHILI AVTORU t.~vULF, POSTANOVSHCHIK TELEVIZIONNOJ PROGRAMMY, PREDLOZHIVSHIJ IDEYU NAPISANIYA NEBOLXSHOJ PXESY S POMOSHCHXYU evm, A TAKZHE d.~rOSS I~X.~mORS, KOTORYE NAPISALI I OTLADILI PROGRAMMU. bEZ SOMNENIYA, U CHITATELYA VOZNIKNUT SVOI SOOBRAZHENIYA O TOM, KAK BY ON MOG NAPISATX PROGRAMMU MODELIROVANIYA LITERATURNOGO TVORCHESTVA. eTO I ESTX CELX DANNOGO UPRAZHNENIYA. %% 200 \chapter{aRIFMETIKA} %% 4 \epigraph vVIDU TOGO CHTO NET NICHEGO BOLEE HLOPOTNOGO V MATEMATICHESKOJ PRAKTIKE (O VOZLYUBLENNYE STUDENTY-MATEMATIKI!), NICHEGO TAKOGO, CHTO BOLEE DOSAZHDALO BY I MESHALO VYCHISLITELYU, CHEM VYPOLNYAEMYE NAD BOLXSHIMI CHISLAMI UMNOZHENIE, DELENIE, IZVLECHENIE KVADRATNYH I KUBICHESKIH KORNEJ, KOTORYE SOPRYAZHENY OBYCHNO S MASSOJ TRUDNO OBNARUZHIVAEMYH OSHIBOK, YA STAL RAZMYSHLYATX NAD TEM, KAKOE NADEZHNOE I UDOBNOE SREDSTVO MOGLO BY USTRANITX |TI POMEHI. \signed dZHON nEPER (1614) \epigraph tERPETX NE MOGU SKLADYVATX. nET BOLXSHEJ OSHIBKI, CHEM NAZYVATX ARIFMETIKU TOCHNOJ NAUKOJ. sUSHCHESTVUYUT~\dots{} TAJNYE ZAKONY, UPRAVLYAYUSHCHIE CHISLAMI, POSTICHX KOTORYE MOZHET LISHX UM TIPA MOEGO. nAPRIMER, ESLI VY NAHODITE SUMMU, SKLADYVAYA CHISLA STOLBIKOM SNACHALA SNIZU VVERH, A ZATEM SVERHU VNIZ, VY VSEGDA POLUCHAETE RAZNYJ REZULXTAT. \signed gOSPOZHA lA tUSH (19~V.) \epigraph nE MOGU PREDSTAVITX SEBE, CHTOBY KOMU-NIBUDX POTREBOVALOSX VYPOLNYATX UMNOZHENIE SO SKOROSTXYU $40\ 000$ ILI DAZHE $4\ 000$~OPERACIJ V CHAS; TAKOE RADIKALXNOE IZMENENIE, KAK PEREHOD K VOSXMERICHNOJ SISTEME, NE SLEDUET NAVYAZYVATX VSEMU CHELOVECHESTVU RADI NESKOLXKIH LICHNOSTEJ. \signed f.~X.~u|JLS (1936) oSNOVNAYA CELX |TOJ GLAVY---TSHCHATELXNOE RASSMOTRENIE CHETYREH %% !!! bugfix OSNOVYH => OSNOVNYH OSNOVNYH DEJSTVIJ ARIFMETIKI: SLOZHENIYA, VYCHITANIYA, UMNOZHENIYA I DELENIYA. mNOGIE SCHITAYUT ARIFMETIKU TRIVIALXNOJ VESHCHXYU, KOTOROJ OBUCHAYUT DETEJ V SHKOLE I DEJSTVIYA KOTOROJ VYPOLNYAYUT MASHINY, NO, KAK MY UVIDIM, ARIFMETIKA---|TO UVLEKATELXNYJ PREDMET, IMEYUSHCHIJ MNOGO INTERESNYH ASPEKTOV. aRIFMETIKA LEZHIT V OSNOVE STOLX BOLXSHOGO CHISLA MASHINNYH PRILOZHENIJ, CHTO VAZHNO SAMYM DOSKONALXNYM OBRAZOM ISSLEDOVATX |FFEKTIVNYE METODY VYCHISLENIJ S CHISLAMI. aRIFMETIKA---|TO NA SAMOM DELE ZHIVAYA I VSE ESHCHE BYSTRO RAZVIVAYUSHCHAYASYA OBLASTX NAUKI, SYGRAVSHAYA VAZHNUYU ROLX V MIROVOJ ISTORII. v |TOJ GLAVE MY PROANALIZIRUEM ALGORITMY VYPOLNENIYA ARIFMETICHESKIH OPERACIJ NAD MNOGIMI TIPAMI VELICHIN, TAKIMI, KAK CHISLA "S PLAVAYUSHCHEJ TOCHKOJ", OCHENX BOLXSHIE CHISLA, DROBI (RACIONALXNYE CHISLA), MNOGOCHLENY I STEPENNYE RYADY; MY OBSUDIM TAKZHE SVYAZANNYE S |TIM VOPROSY, TAKIE, KAK PREOBRAZOVANIE IZ ODNOJ SISTEMY SCHISLENIYA V DRUGUYU, RAZLOZHENIE CHISEL NA MNOZHITELI I VYCHISLENIE MNOGOCHLENOV. %% 201 \bye