\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] ПвRсуойфе, рпюенх ретчщк вхжет жбкмб~$2$ ч уфтпле~$6$ тйу.~84 упчуен рхуф. \ex[20] Вхдеф мй бмзптйфн~F тбвпфбфш дпмцощн пвтбъпн, еумй чнеуфп $2P$~вхжетпч ччпдб йнеефус фпмшлп $2P-1$? Еумй дб, дплбцйфе ьфп, еумй оеф--- ртйчедйфе ртйнет, лпздб бмзптйфн фетрйф оехдбюх. \ex[20] Лбл йънеойфш бмзптйфн~F, юфпвщ по тбвпфбм фблце й ртй~$P=1$? \rex[21] Еумй ч тбъмйюощи жбкмби йнеафус тбчоще лмаюй, оепвипдйнп ч ртпгеууе ртпзопъйтпчбойс декуфчпчбфш пюеош бллхтбфоп. ПвRсуойфе, рпюенх, й рплбцйфе, лбл йъвецбфш фтхдопуфек, еумй впмее уфтпзп пртедемйфш претбгйй умйсойс й ртпзопъйтпчбойс ч бмзптйфне~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