\input style \chapnotrue \chapno=5\subchno=4\subsubchno=6 1) Опхбедеммше тнплскш онйюгшбючр, врн янпрхпнбйю ъбкъеряъ, б ясымнярх, тсмйжхеи нр опнхгбедемхъ~$N$ х~$C$, ю ме нр~$N$ х~$C$ онпнгмэ. Гю хяйкчвемхел меяйнкэйху нрмняхрекэмн мегмювхрекэмшу яннапюфемхи (мюопхлеп, врн $B$~бшахпюеряъ йпюрмшл $C$), хг мюьху тнплск якедсер, врн янпрхпнбйю ндмнцн лхккхнмю гюохяеи он 10 кхреп йюфдюъ гюилер опхлепмн ярнкэйн фе бпелемх, врн х янпрхпнбйю 100000 гюохяеи он 100 кхреп йюфдюъ. Мю яюлнл деке гдеяэ лнфер онъбхрэяъ пюгкхвхе, ме намюпсфхлне б мюьху тнплскюу, рюй йюй бн бпелъ бшанпю я гюлеыемхел мейнрнпне опнярпюмярбн хяонкэгсеряъ дкъ онкеи ябъгх. Б кчанл яксвюе пюглеп \emph{йкчвю} едбю кх нйюфер йюйне-кхан бкхъмхе, еякх рнкэйн йкчвх ме асдср ярнкэ дкхммшлх х якнфмшлх, врн бмсрпеммхе бшвхякемхъ ме ялнцср сцмюрэяъ гю кемрюлх. Опх дкхммшу гюохяъу х йнпнрйху йкчвюу янакюгмхрекэмн бшдекхрэ йкчвх, нрянпрхпнбюрэ ху, ю гюрел йюй-мхасдэ оепеярюбхрэ гюохях жекхйнл. Мн щрю хдеъ, йюферяъ, ме пюанрюер: нмю лнфер рнкэйн нряпнвхрэ юцнмхч, оняйнкэйс опнжедспю нйнмвюрекэмни оепеярюмнбйх рпеасер онврх ярнкэйн фе бпелемх, яйнкэйн онрпеанбюкю аш наыеопхмърюъ янпрхпнбйю якхъмхел. 2) Лш бхдекх, врн рпеасеряъ нр~15 дн~19~лхм, врнаш нрянпрхпнбюрэ 100000~гюохяеи он 100~кхреп опх янакчдемхх мюьху опедонкнфемхи. Яйнкэйн бпелемх гюмъкю аш ху янпрхпнбйю мю йюпрнвмнл янпрхпнбыхйе? Щрнр бнопня хлеер опюйрхвеяйхи хмрепея онрнлс, врн йюпрнвмше янпрхпнбыхйх деьебке ЩБЛ. Дносяйюъ, врн йюфдюъ гюохяэ лнфер ашрэ брхямсрю б 80-йнкнммсч йюпрс х врн юктюбхрмши йкчв гюмхлюер ьеярэ йнкнмнй, опхвел дкъ янпрхпнбйх он йюфдни йнкнмйе рпеасеряъ б япедмел $1{2\over3}$~опнундю, онксвюел, врн лш днкфмш опносярхрэ йюфдсч йюпрс вепег люьхмс опхлепмн 10~пюг. Опх яйнпнярх 1000 йюпр б лхмсрс щрн гюмъкн аш 1000~лхм, р.~е.~онврх 17~в. (Хлееряъ беяэлю анкэьюъ бепнърмнярэ, врн гю щрн бпелъ мейнрнпше йюпрш нйюфсряъ мевюъммн "оепеосрюммшлх" хкх асдср "гюлърш" б люьхме.) 3) Опх мюохяюмхх опнцпюллш янпрхпнбйх, йнрнпюъ днкфмю хяонкэгнбюрэяъ лмнцнйпюрмн, пюгслмн нвемэ рыюрекэмн нжемхрэ бпелъ пюанрш х япюбмхрэ ренпхч я деиярбхрекэмшлх мюакчдюелшлх уюпюйрепхярхйюлх бшонкмемхъ. Рюй йюй ренпхъ янпрхпнбйх пюгбхрю днбнкэмн унпньн, рн щрю опнжедспю, йюй хгбеярмн, яонянамю бмегюомн бшъбхрэ детейрш б нанпсднбюмхх хкх опнцпюллмнл наеяоевемхх ббндю/бшбндю б ясыеярбсчыху яхярелюу. Нйюгшбюеряъ наяксфхбюмхе пюанрюкн ледкеммее, вел якеднбюкн, х мхйрн щрнцн ме гюлевюк, онйю щрн ме опнъбхкняэ мю опнцпюлле янпрхпнбйх! 4) Мейнрнпше бшвхякхрекэмше яхярелш хлечр дбю "аюмйю" %%401 кемрнопнръфмшу сярпниярб, опхянедхмеммшу й нрдекэмшл "йюмюкюл" рюйхл яонянанл, врн ндмнбпелеммне времхе х гюохяэ дносяйюеряъ рнкэйн дкъ кемр хг пюгмшу аюмйнб. Дкъ рюйни йнмтхцспюжхх анкэье бяецн ондундхр яаюкюмяхпнбюммне якхъмхе. Пюяялнрпхл, мюопхлеп, яксвюи ьеярх кемр он рпх б йюфднл аюмйе х опедонкнфхл, врн лш унрхл бшонкмхрэ лмнцнтюгмне якхъмхе я~$T=6$. Бнбпелъ оърхосребнцн якхъмхъ дбе хг ббндмше кемр асдср ме б рнл аюмйе, рюй врн, цпсан цнбнпъ, дбе оършу бпелемх ббндю ме асдср янблеыемш я бшбнднл. Щрн днаюбкъер йн бпелемх янпрхпнбйх опхакхгхрекэмн 40\%, рюй врн яаюкюмяхпнбюммне якхъмхе нйюферяъ ксвье лмнцнтюгмнцн дюфе б яксвюе напюрмнцн времхъ. 5) Мюь юмюкхг бшанпю я гюлеыемхел ашк бшонкмем дкъ "яксвюимшу" тюикнб, мн тюикш, бярпевючыхеяъ мю опюйрхйе, нвемэ вюярн сфе сонпъднвемш б рни хкх хмни яреоемх. (Тюйрхвеяйх хмнцдю кчдх асдср янпрхпнбюрэ тюикш, сфе сонпъднвеммше, рнкэйн врнаш саедхрэяъ б щрнл.) Рюйхл напюгнл, ношр дюфе б анкэьеи лепе, вел сйюгшбючр мюьх тнплскш, онйюгюк, врн бшанп я гюлеыемхел опедонврхрекэмее дпсцху бхднб бмсрпеммеи янпрхпнбйх. Щрн опехлсыеярбн меяйнкэйн някюакъеряъ б яксвюе лмнцнтюгмни янпрхпнбйх я напюрмшл времхел, рюй йюй днкфем ашрэ онпнфдем пъд сашбючыху нрпегйнб; мю яюлнл деке П.~К.~Цхкярщд (нм оепбши носакхйнбюк лмнцнтюгмне якхъмхе) оепбнмювюкэмн он щрни опхвхме нрбепц лернд напюрмнцн времхъ. Мн онгдмее нм гюлерхк, врн вепеднбюмхе мюопюбкемхи асдер бяе фе дюбюрэ дкхммше бнгпюярючыхе нрпегйх. Йпнле рнцн, лмнцнтюгмши лернд я напюрмшл времхел---щрн едхмярбеммши ярюмдюпрмши лернд, йнрнпши акюцняйкнмем й сашбючыхл бундмшл тюикюл, пюбмн йюй х й бнгпюярючыхл. 6) Дпсцне опехлсыеярбн бшанпю я гюлеыемхел янярнхр б рнл, врн щрнр лернд дносяйюер янблеыемхе опнжеяянб времхъ, гюохях х бшвхякемхи. Еякх аш лш опнярн бшонкмъкх бмсрпеммчч янпрхпнбйс нвебхдмшл яонянанл---гюонкмъъ оюлърэ, янпрхпсъ ее х гюрел гюохяшбюъ ее он лепе рнцн, йюй нмю гюонкмъеряъ мнбшл яндепфхлшл,---рн опнунд пюяопедекемхъ гюмък аш опхлепмн бдбне анкэье бпелемх! Хг пюяялнрпеммшу мюлх лернднб бмсрпеммеи янпрхпнбйх еые рнкэйн ндхм лнфмн опхяонянахрэ й ндмнбпелеммнлс времхч, гюохях х бшвхякемхъл---охпюлхдюкэмсч янпрхпнбйс. (Щрю хдеъ ашкю хяонкэгнбюмю опх ондцнрнбйе опхлепю~10 яуелш~Ю.) Опедонкнфхл дкъ сднаярбю, врн бмсрпеммъъ оюлърэ яндепфхр 1000~гюохяеи, ю йюфдши акнй мю кемре---он 100. Деиярбнбюрэ лнфмн якедсчыхл напюгнл (вепег $B_1$, $B_2$,~\dots, $B_{10}$ нангмювемн яндепфхлне оюлърх, пюгдекеммни мю 10~акнйнб он 100~гюохяеи). %% 402 {\sl Ьюц 0.\/} Гюонкмхрэ оюлърэ х ядекюрэ рюй, врнаш щкелемрш $B_2$\dots $B_{10}$ сднбкербнпъкх мепюбемярбюл охпюлхдш (я мюхлемэьхл щкелемрнл б бепьхме). {\sl Ьюц 1.\/} Ябеярх $B_1$\dots$B_{10}$ б охпюлхдс, гюрел бшапюрэ мюхлемэьхе 100 гюохяеи х оепеохяюрэ ху б $B_{10}$. {\sl Ьюц 2.\/} Гюохяюрэ хг $B_{10}$; б рн фе бпелъ бшапюрэ мюхлемэьхе 100 гюохяеи хг $B_1$\dots$B_{9}$ х онлеярхрэ ху б $B_9$. {\sl Ьюц 3.\/} Опнвхрюрэ б~$B_{10}$ х гюохяюрэ хг $B_9$; б рн фе бпелъ бшапюрэ мюхлемэьхе 100~гюохяеи хг $B_1$\dots$B_8$ х онлеярхрэ ху б~$B_8$. \dots {\sl Ьюц 9.\/} Опнвхрюрэ б $B_4$ х гюохяюрэ хг~$B_3$; б рн фе бпелъ бшапюрэ мюхлемэьхе 100~гюохяеи хг $B_1$ $B_2$, онлеярхрэ ху б $B_2$ х ядекюрэ рюй, врнаш мепюбемярбю охпюлхдш ашкх яопюбедкхбш дкъ $B_5$\dots$B_{10}$. {\sl Ьюц 10.\/} Опнвхрюрэ б~$B_3$ х гюохяюрэ хг~$B_2$, янпрхпсъ~$B_1$, б рн фе бпелъ ядекюрэ рюй, врнаш мепюбемярбю охпюлхдш ашкх яопюбедкхбш дкъ $B4$\dots$B_{10}$. {\sl Ьюц 11.\/} Опнвхрюрэ б~$B_2$ х гюохяюрэ хг~$B_1$; б рн фе бпелъ ядекюрэ рюй, врнаш $B_3$\dots$B_{10}$ сднбкербнпъкх мепюбемярбюл охпюлхдш. {\sl Ьюц 12.\/} Опнвхрюрэ б~$B_1$, декюъ рюй, врнаш $B_2$\dots$B_{10}$ сднбкербнпъкх мепюбемярбюл охпюлхдш. Бепмсрэяъ й ьюцс 1. \endmark 7) Лш опедонкюцюел, врн вхякн янпрхпселшу гюохяеи~$N$ ме хгбеярмн гюпюмее. Мю яюлнл фе деке б анкэьхмярбе бшвхякхрекэмшу люьхм еярэ бнглнфмнярэ бяе бпелъ якедхрэ гю вхякнл гюохяеи бн бяеу тюикюу, х лш лнцкх аш явхрюрэ, врн мюью бшвхякхрекэмюъ яхярелю яонянамю яннаыхрэ гмювемхе~$N$. Мюяйнкэйн аш мюл щрн онлнцкн? Й янфюкемхч, ме нвемэ! Лш бхдекх, врн бшанп я гюлеыемхел беяэлю бшцндем, мн нм бедер й меопедяйюгселнлс вхякс мювюкэмшу нрпегйнб. Б яаюкюмяхпнбюммнл якхъмхх лш лнцкх аш хяонкэгнбюрэ хмтнплюжхч на~$N$ дкъ сярюмнбкемхъ рюйнцн пюглепю астепю~$B$, врнаш $S$~нйюгюкняэ, яйнпее бяецн, всрэ лемэье яреоемх~$P$; б лмнцнтюгмнл пюяопедекемхх я норхлюкэмшл пюглеыемхел тхйрхбмшу нрпегйнб лш лнцкх аш хяонкэгнбюрэ хмтнплюжхч на~$N$, врнаш пеьхрэ, йюйни спнбемэ бшапюрэ (ял. рюак. 5.4.2-2). Хдъ он дпсцнлс осрх х ме хяонкэгсъ бшанпю я гюлеыемхел, лш лнцкх аш опхлемхрэ якхъмхе б опълнл онпъдйе, нохяюммне б йнмже о.~5.4.4, бярпнхб ецн б няжхккхпсчысч янпрхпнбйс, пюяопедекъчысч мювюкэмше нрпегйх яннрберярбсчыецн мюопюбкемхъ б яннрберярбсчыхи лнлемр (блеярн рнцн врнаш апюрэ ху я "кемрш~$A$", йюй нохяюмн). Щрнр лернд, б ясымнярх, \emph{норхлюкем} япедх бяеу лернднб, бшонкмъчыху бмсрпеммчч янпрхпнбйс аег бшанпю я гюлеыемхел, рюй йюй нм якхбюер б яннрберярбхх я мюхксвьхл бнглнфмшл $P\hbox{-юпмшл}$ депебнл, мн нм бяе фе пюанрюер ледкеммеи лернднб, нямнбюммшу мю бшанпе я гюлеыемхел. %% 403 8) Кемрнопнръфмше сярпниярбю вюярн нйюгшбючряъ мюхлемее мюдефмшлх вюярълх ЩБЛ. Наяксфхбючыхи оепянмюк нашвмн онксвюер бшгнбш дкъ хяопюбкемхъ кемрнопнръфмшу сярпниярб вюые, вел дкъ кчанцн дпсцнцн йнлонмемрю люьхмш, х ноепюрнпш бшвхякхрекэмни люьхмш днкфмш слерэ бнгнамнбкърэ пюанрс оняке яанъ кемрш. Юбрнп мхйнцдю дюфе ме бхдек сярюмнбнй я~10 хкх анкее кемрнопнръфмшлх сярпниярбюлх, йнрнпше аш бяе ндмнбпелеммн мюундхкхяэ б унпньел пюанвел янярнъмхх. Якеднбюрекэмн, лнфмн опхмърэ гю юйяхнлс, врн \emph{хяундмюъ ббндмюъ кемрю мх б йнел яксвюе ме днкфмю хглемърэяъ, онйю ме ярюмер хгбеярмн, врн бяъ янпрхпнбйю сднбкербнпхрекэмн гюбепьемю.} Б мейнрнпшу опхлепюу яуелш~A ясыеярбсер дняюдмне "бпелъ, онйю ноепюрнп ме ялемхр кемрс", мн ашкн аш якхьйнл пхяйнбюммн гюрхпюрэ хяундмше дюммше ббхдс бнглнфмнярх йюйни-кхан мехяопюбмнярх бн бпелъ дкхммни янпрхпнбйх. 9) Опх оепеунде нр опълни гюохях й напюрмнлс времхч лш лнфел ящйнмнлхрэ мейнрнпне бпелъ, бнбяе ме гюохяшбюъ онякедмхи астеп мю кемрс; нм б кчанл яксвюе асдер бмнбэ опнвхрюм! Яуелю~A онйюгшбюер, врн щрнр опхел б деиярбхрекэмнярх щйнмнлхр япюбмхрекэмн мелмнцн бпелемх, гю хяйкчвемхел яксвюъ няжхккхпсчыеи янпрхпнбйх, йнцдю мюопюбкемхъ лемъчряъ вюярн. 10) Еякх б мюьел пюяонпъфемхх лмнцн кемрнвмшу сярпниярб, рн ме бяецдю ярнхр хяонкэгнбюрэ ху бяе б жекъу онксвемхъ "бшянйнцн онпъдйю якхъмхъ". Рюй, мюопхлеп, анкее бшянйхи онпъднй якхъмхъ нашвмн нгмювюер лемэьхи пюглеп акнйю, ю опнжемрмюъ пюгмнярэ лефдс $\log_P S$ х~$\log_{P+1} S$ ме нвемэ бекхйю опх анкэьху~$P$. Ондслюире рюйфе н аедмнл ноепюрнпе ЩБЛ, йнрнпши днкфем сярюмнбхрэ бяе щрх пюанвхе кемрш. Я дпсцни ярнпнмш, б соп.~12 нохяюм хмрепеямши яоняна хяонкэгнбюмхъ днонкмхрекэмшу кемрнопнръфмшу сярпниярб, цпсоохпселшу рюй. врнаш янблеярхрэ бпелъ ббндю х бшбндю аег сбекхвемхъ онпъдйю якхъмхъ. 11) Мю люьхмюу, онднамшу \MIX, йнрнпше хлечр тхйяхпнбюммши х днбнкэмн люкемэйхи пюглеп акнйнб, дкъ якхъмхъ едбю кх рпеасеряъ лмнцн бмсрпеммеи оюлърх. Гдеяэ няжхккхпсчыюъ янпрхпнбйю анкее опедонврхрекэмю; Онрнлс врн ярюмнбхряъ бнглнфмшл янупюмърэ депебн бшанпю я гюлеыемхел б оюлърх бн бпелъ якхъмхъ. Мю яюлнл деке б щрнл яксвюе лнфмн сянбепьемярбнбюрэ няжхккхпсчысч янпрхпнбйс (йюй опедкнфхк Й.~Дф.~Аекк б 1962~ц.), якхбюъ мнбши мювюкэмши нрпегнй б бшбнд йюфдши пюг, йнцдю лш якхбюел я пюанвху кемр! 12) Лш бхдекх, врн тюикш мю меяйнкэйху анахмюу днкфмш янпрхпнбюрэяъ онякеднбюрекэмн анахмю гю анахмни, врнаш хгаефюрэ впеглепмни пюанрш он оепеярюмнбйе кемр. Тюйрхвеяйх яаюкюмяхпнбюммне якхъмхе я ьеярэч кемрюлх, еякх нмн рыюрекэмн %% 404 гюопнцпюллхпнбюмн, лнфер янпрхпнбюрэ \emph{рпх} анахмш дн лнлемрю нйнмвюрекэмнцн якхъмхъ. Дкъ якхъмхъ нрмняхрекэмн анкэьнцн вхякю нрдекэмн нрянпрхпнбюммшу анахм ашярпеиьхл асдер депебн якхъмхъ я лхмхлюкэмни дкхмни осрх (яп. я~о.~5.4.4). Щрн онярпнемхе ашкн боепбше нясыеярбкемн Щ.~X.~Тпщмднл [{\sl JACM\/}, {\bf 3}(1956), 166--167] х гюрел С.~X.~Аспфел [{\sl Information and Control,\/} {\bf 1} (1958), 181--197], йнрнпше нрлерхкх, врн норхлюкэмши яоняна якхъмхъ нрпегйнб дюммшу (бнглнфмн, мепюбмшу) дкхм онксвюеряъ я онлныэч онярпнемхъ депебю я лхмхлюкэмни \emph{бгбеьеммни} дкхмни осрх, хяонкэгсъ дкхмш нрпегйнб б йювеярбе беянб (ял.~о.~2.3.4.5 х~5.4.9), еякх опемеапевэ бпелемел сярюмнбйх кемр. Мн тюикш, гюмхлючыхе меяйнкэйн анахм, бепнърмн, якедсер упюмхрэ мю дхяйюу хкх дпсцнл гюонлхмючыел сярпниярбе анкэьни елйнярх, ю ме мю кемрюу. 13) Б мюьел наясфдемхх лш, ме гюдслшбюъяэ, опедонкюцюкх, врн хлееряъ бнглнфмнярэ хяонкэгнбюрэ меоняпедярбеммн хмярпсйжхх ббндю/бшбндю х врн мхйюйни якнфмши яхярелмши хмрептеия ме леьюер мюл хяонкэгнбюрэ кемрш я рюйни щттейрхбмнярэч, мю йюйсч пюяявхршбюкх йнмярпсйрнпш юооюпюрспш. Щрх хдеюкэмше опедонкнфемхъ онгбнкхкх мюл опнмхймсрэ б ясрэ опнакел якхъмхъ, х нмх лнцср дюрэ мейнрнпши ондунд й йнмярпсхпнбюмхч яннрберярбсчыху ноепюжхнммшу яхярел. Ндмюйн якедсер онмхлюрэ, врн лскэрхопнцпюллхпнбюмхе х лскэрхопнжеяяхпнбюмхе лнцср гмювхрекэмн сякнфмхрэ яхрсюжхч. 14) Наясфдюелше мюлх бнопняш ашкх боепбше пюяялнрпемш б оевюрх Щ.~X.~Тпщмднл [{\sl JACM,\/} {\bf 3} (1956), 134--165],С.~Гнаепаэепнл [{\sl Electron. Datenverarb.,\/} {\bf 5} (1960), 28--44] х Л.~Ю.~Цнржел [Digital Computer User's Handbook (New York, McGraw-Hill, 1967) 1.292--1.320]. \section Пегчле. Лш лнфел якедсчыхл напюгнл бйпюрже бшпюгхрб бяе, врн сгмюкх н япюбмемхх пюгкхвмшу яуел якхъмхъ: \proclaim Ренпелю Ю. Рпсдмн пеьхрэ, йюйюъ яуелю якхъмхъ ъбкъеряъ мюхксвьеи б йнмйпермни яхрсюжхх. \endmark Опхлепш, йнрнпше лш бхдекх мю яуеле~Ю, онйюгшбючр, йюй 100000~гюохяеи он 100~кхреп (хкх 1~лхккхнм гюохяеи он 10~кхреп), пюяонкнфеммшу б яксвюимнл онпъдйе, лнцкх аш ашрэ нрянпрхпнбюмш я хяонкэгнбюмхел ьеярх кемр опх днярюрнвмн пеюкхярхвеяйху опедонкнфемхъу. Щрх дюммше гюмхлючр нйнкн онкнбхмш кемрш х лнцср ашрэ нрянпрхпнбюмш опхакхгхрекэмн гю 15--19 лхм; ндмюйн ясыеярбсчыее кемрнвмне нанпсднбюмхе яхкэмн пюгкхвюеряъ он бнглнфмняръл, х бпелъ бшонкмемхъ рюйни пюанрш мю пюгмшу люьхмюу хглемъеряъ б дхюоюгнме опхакхгхрекэмн нр~ %%405 вершпеу лхмср дн~дбсу вюянб. Б мюьху опхлепюу нйнкн 3~лхм пюяундсеряъ мю мювюкэмне пюяопедекемхе нрпегйнб х бмсрпеммчч янпрхпнбйс, нйнкн 4.5~лхм---мю нйнмвюрекэмне якхъмхе х оепелнрйс бшбндмни кемрш х нйнкн 7.5--11.5~лхм---мю опнлефсрнвмше ярюдхх якхъмхъ. Еякх хлееряъ ьеярэ кемр, йнрнпше мекэгъ вхрюрэ б напюрмнл мюопюбкемхх, рн мюхксвьхл лернднл янпрхпнбйх опх мюьху опедонкнфемхъу ашкн "лмнцнтюгмне якхъмхе я пюяыеокемхел кемр" (опхлеп~4), ю дкъ кемр, дносяйючыху напюрмне времхе, мюхксвьхл лернднб нйюгюкяъ лмнцнтюгмши лернд я напюрмшл времхел ян якнфмшл пюглеыемхел тхйрхбмшу нрпегйнб (опхлеп~7). Няжхккхпсчыюъ янпрхпнбйю (опхлеп~9) гюмхлюер брнпне леярн. Б нанху яксвюъу йюяйюдмне якхъмхе анкее опнярн х кхьэ мегмювхрекэмн ледкеммее (опхлепш~5 х~8). Б яксвюе опълнцн времхъ нашвмне яаюкюмяхпнбюммне якхъмхе (опхлеп~1) нйюгюкняэ сдхбхрекэмн щттейрхбмшл, вюярхвмн хг-гю сдювх б щрнл йнмйпермнл опхлепе, ю вюярхвмн хг-гю рнцн, врн нмн рпюрхр япюбмхрекэмн люкн бпелемх мю оепелнрйс. Онкнфемхе меяйнкэйн хглемхкняэ аш, еякх аш б мюьел пюяонпъфемхх ашкн дпсцне вхякн кемр. \section Цемепюрнпш янпрхпнбйх. Б сякнбхъу анкэьнцн пюгмннапюгхъ уюпюйрепхярхй дюммшу х нанпсднбюмхъ онврх мебнглнфмн мюохяюрэ едхмярбеммсч опнцпюллс бмеьмеи янпрхпнбйх, йнрнпюъ ашкю аш сднбкербнпхрекэмни б ондюбкъчыел анкэьхмярбе яксвюеб. Рюйфе беяэлю рпсдмн янгдюрэ опнцпюллс, йнрнпюъ б пеюкэмшу сякнбхъу щттейрхбмн пюанрюер я кемрюлх. Якеднбюрекэмн, хгцнрнбкемхе опнцпюллмнцн наеяоевемхъ янпрхпнбйх---яюлнярнърекэмюъ гюдювю, рпеасчыюъ анкэьни пюанрш. \dfn{Цемепюрнп янпрхпнбйх}---щрн опнцпюллю, йнрнпюъ, нямнбшбюъяэ мю оюпюлерпюу, нохяшбючыху тнплюр дюммшу х йнмтхцспюжхч нанпсднбюмхъ, онпнфдюер люьхммсч опнцпюллс, яоежхюкэмн опхяонянакеммсч й йнмйпермнлс опхлемемхч янпрхпнбйх. Онднамюъ опнцпюллю вюярн ябъгюмю я ъгшйюлх бшянйнцн спнбмъ, рюйхлх, йюй~Йнанк хкх~PL/1, хкх нмю лнфер ашрэ мюохяюмю йюй мюанп люйпннопедекемхи дкъ хяонкэгнбюмхъ янблеярмн я люйпнюяяелакепнл. Ндмни хг нянаеммняреи, нашвмн наеяоевхбюелшу цемепюрнпнл янпрхпнбйх, ъбкъеряъ бнглнфмнярэ бярюбкърэ "янаярбеммше йнлюмдш"---нянаше хмярпсйжхх, йнрнпше днкфмш бйкчвюрэяъ б оепбши х онякедмхи опнундш опнцпюллш янпрхпнбйх. Янаярбеммше йнлюмдш оепбнцн опнундю нашвмн хяонкэгсчряъ, врнаш нрпедюйрхпнбюрэ хяундмше гюохях, вюярн янйпюыюъ ху хкх мегмювхрекэмн сдкхмъъ, врнаш опхбеярх ху й тнпле, анкее опнярни дкъ янпрхпнбйх. Осярэ, мюопхлеп, хяундмше гюохях днкфмш ашрэ нрянпрхпнбюмш он дебърхкхрепмнлс йкчвс, хгнапюфючыелс дюрс б тнплюре леяъж-демэ-цнд: %%406 $$ |JUL04| \ |OCT311517| \ |NOV051605| \ |JUL141789| \ |NOV201917| $$ Рпеуасйбеммше йндш леяъжеб лнфмн мюирх б рюакхже х гюлемхрэ вхякюлх, опхвел мюханкее гмювюыхе онкъ лнцср ашрэ онлеыемш якебю: $$ |17760704| \ |15171031| \ |16051105| \ |17890714| \ |19171120| $$ Щрн слемэьюер дкхмс гюохяеи х декюер анкее опняршл онякедсчыее япюбмемхе. (Йнд йкчвеи лнц аш ашрэ ядекюм дюфе анкее йнлоюйрмшл.) Янаярбеммше йнлюмдш онякедмецн опнундю лнцср хяонкэгнбюрэяъ дкъ бняярюмнбкемхъ хяундмнцн тнплюрю х/хкх дкъ бмеяемхъ дпсцху фекюрекэмшу хглемемхи б тюик х/хкх дкъ бшвхякемхъ йюйни-кхан тсмйжхх нр бшбндмшу гюохяеи. Юкцнпхрлш якхъмхъ, йнрнпше лш хгсвхкх, нпцюмхгнбюмш рюйхл напюгнл, врн онякедмхи опнунд кецйн нркхвхрэ нр нярюкэмшу тюг якхъмхъ. Гюлерхл, врн еякх хлечряъ янаярбеммше йнлюмдш, рн днкфмн ашрэ он йпюимеи лепе дбю опнундю он тюикс, дюфе еякх нм оепбнмювюкэмн мюундхкяъ б онпъдйе. Янаярбеммше йнлюмдш, хглемъчыхе пюглеп гюохяеи, лнцср гюрпсдмхрэ янблеыемхе мейнрнпшу ноепюжхи ббндю/бшбндю б няжхккхпсчыеи янпрхпнбйе. Цемепюрнпш янпрхпнбйх рюйфе гюанръряъ н яхярелмшу дерюкъу, рюйху, йюй янцкюьемхъ н лерйюу кемр; нмх рюйфе вюярн наеяоевхбючр ондявер йнмрпнкэмни ясллш хкх хмше опнбепйх рнцн, врн мхйюйюъ вюярэ тюикю ме опноюкю х ме хглемхкюяэ. Хмнцдю хлечряъ япедярбю дкъ нярюмнбйх янпрхпнбйх б сднамшу леярюу х бнгнамнбкемхъ ее онгдмее. Яюлше бшянйнйювеярбеммше цемепюрнпш онгбнкъчр гюохяъл хлерэ дхмюлхвеяйх лемъчыхеяъ дкхмш [ял. D.~J.~Waks, {\sl CACM,\/} {\bf 6} (1963), 267--272]. \section *Якхъмхе я лемэьхл вхякнл астепнб. Лш бхдекх, врн $2P+2$~астепнб днярюрнвмн дкъ онддепфюмхъ ашярпнцн дбхфемхъ кемр б ревемхе $P\hbox{-осребнцн}$ якхъмхъ. Б гюбепьемхе щрнцн осмйрю опнбедел люрелюрхвеяйхи юмюкхг бпелемх якхъмхъ б рнл яксвюе, йнцдю хлееряъ лемэье $2P+2$~астепнб. Нвебхдмн, врн фекюрекэмш дбю астепю бшбндю, рюй йюй лш ялнфел гюохяшбюрэ хг ндмнцн астепю, напюгсъ б щрн фе бпелъ якедсчыхи акнй бшбндю б дпсцнл. Онщрнлс лш лнфел бннаые ме пюяялюрпхбюрэ бнопня бшбндю х гюмърэяъ рнкэйн ббнднл. Дносярхл, хлееряъ $P+Q$~астепнб ббндю, цде $1\le Q\le P$. Бняонкэгселяъ дкъ нохяюмхъ мюьеи яхрсюжхх лндекэч, опедкнфеммни К.~Дф.~Бсдпюлнл [{\sl IBM Systems J.,\/} {\bf 9} (1970), 118--144]. Времхе ндмнцн акнйю кемрш гюмхлюер ндмс едхмхжс бпелемх. Хлееряъ бепнърмнярэ~$p_0$ рнцн, врн б ревемхе щрнцн бпелемх мх ндхм хг астепнб ббндю ме ярюмер осяршл, $p_1$---врн ндхм астеп ярюмер осяршл, $p{\ge 2}$---врн дбю хкх анкэье астепнб ярюмср %%407 осяршлх х~р.~д. Он гюбепьемхх времхъ кемрш лш нйюгшбюеляъ б ндмнл хг $Q+1$~янярнъмхи: \medskip {\sl Янярнъмхе~$0$:\/} $Q$~астепнб осярш. Лш мювхмюел вхрюрэ акнй ондундъыецн тюикю б ндхм хг мху, хяонкэгсъ лернд опнцмнгхпнбюмхъ, нохяюммши пюмее б щрнл осмйре. Вепег ндмс едхмхжс бпелемх лш оепеундхл б янярнъмхе~$1$ я бепнърмнярэч~$p_0$, б опнрхбмнл яксвюе лш нярюеляъ б янярнъмхх~$0$. {\sl Янярнъмхе~$1$:\/} $Q-1$~астепнб осярш. Лш мювхмюел вхрюрэ б ндхм хг мху, опедяйюгшбюъ ондундъыхи тюик. Вепег ндмс едхмхжс бпелемх лш оепеундхл б янярнъмхе~$2$ я бепнърмнярэч~$p_0$, б янярнъмхе~$1$ я бепнърмнярэч~$p_1$ х б янярнъмхе~$0$ я бепнърмнярэч~$p_{\ge2}$. $\vdots$ {\sl Янярнъмхе~$Q-1$:\/} ндхм астеп осяр. Лш мювхмюел вхрюрэ б мецн, опедяйюгшбюъ ондундъыхи тюик. Вепег ндмс едхмхжс бпелемх лш оепеундхл б янярнъмхе~$Q$ я бепнърмнярэч~$p_0$, б янярнъмхе~$Q-1$ я бепнърмнярэч~$p_1$,~\dots, б янярнъмхе~$1$ я бепнърмнярэч~$P_{Q-1}$, х б янярнъмхе~$0$ я бепнърмнярэч~$p_{\ge Q}$. {\sl Янярнъмхе~$Q$:\/} бяе астепш гюонкмемш. Времхе кемр нярюмюбкхбюеряъ б япедмел мю $\mu$~едхмхж бпелемх, х гюрел лш оепеундхл б янярнъмхе~$1$. \medskip Лш мювхмюел я янярнъмхъ~$0$. Щрю лндекэ яхрсюжхх яннрберярбсер люпйнбяйнлс опнжеяяс (ял.~соп.~2.3.4.2-26), йнрнпши лнфмн опнюмюкхгхпнбюрэ я онлныэч опнхгбндъыху тсмйжхи якедсчыхл хмрепеямшл яонянанл. Осярэ $z$---опнхгбнкэмши оюпюлерп, х опедонкнфхл, врн йюфдши пюг, йнцдю лш пеьхкх вхрюрэ я кемрш, декюел щрн я бепнърмнярэч~$z$, ю я бепнърмнярэч~$1-z$ гюбепьюел юкцнпхрл. Осярэ $g_Q(z)=\sum_{n\ge0} a_n^{(Q)}z^n(1-z)$ асдер япедмхл вхякнл онъбкемхи б щрнл опнжеяяе янярнъмхъ~$Q$; нрячдю якедсер, врн $a_n^{(Q)}$---щрн япедмее вхякн онъбкемхи янярнъмхъ~$Q$, еякх ашкн опнвхрюмн пнбмн $n$~акнйнб. Рнцдю $n+a_n\mu$---япедмее ясллюпмне бпелъ, гюрпювеммне мю ббнд х бшвхякемхъ. Еякх аш хлекняэ онкмне янблеыемхе, йюй б юкцнпхрле я $(2P+2)$~астепюлх, рн ясллюпмне бпелъ бйкчвюкн аш рнкэйн $n$~едхмхж, рюй врн $a_n\mu$~опедярюбкъер бпелъ гюдепфйх времхъ. Осярэ $A_{ij}$---бепнърмнярэ рнцн, врн лш оепеундхл хг янярнъмхъ~$i$ б янярнъмхе~$j$ б щрнл опнжеяяе опх~$0\le i$, $j\le Q+1$, цде $Q+1$---мнбне янярнъмхе "нярюмнбйх". Мюопхлеп, дкъ $Q=1$, $2$, $3$ люрпхжш~$A$ асдср якедсчыхлх: %%407 $$ \eqalign{ Q&=1:\pmatrix{ p_{\ge1}z & p_0z & 1-z\cr 1 & 0 & 0\cr 0 & 0 & 0\cr },\cr Q&=2:\pmatrix{ p_{\ge1}z & p_0z & 0 & 1-z\cr p_{\ge2}z & p_1z & p_0z& 1-z\cr 0 & 1 & 0 & 0 \cr 0 & 0 & 0 & 0\cr },\cr Q&=3:\pmatrix{ p_{\ge1}z & p_0z & 0 & 0 & 1-z\cr p_{\ge2}z & p_1z & p_0z& 0 & 1-z\cr p_{\ge3}z & p_2z & p_1z& p_0z & 1-z\cr 0 & 0 & 1 & 0 & 0\cr 0 & 0 & 0& 0 & 0 \cr }.\cr } $$ Хг соп.~2.3.4.2-26b хлеел, врн $g_Q(z) =\hbox{ юкцеапюхвеяйне днонкмемхе $Q_0$} (I-A)/\det (I-A)$. Рюй, мюопхлеп, еякх $Q=1$, хлеел $$ \eqalign{ g_1(z)&=\det\pmatrix{ 0 & -p_0z & z-1\cr 1 & 0 & 0 \cr 0 & 0 & 1\cr }/ \det\pmatrix{ 1-p_{\ge1}z & -p_0z & z-1\cr -1 & 1 & 0\cr 0& 0 & 1\cr }=\cr &={p_0z\over 1-p_1z-p_0z}={p_0z\over1-z}=\sum_{n\ge0} np_0z^n(1-z),\cr } $$ рюй врн $a_n^{(1)}=np_0$. Щрн, йнмевмн, нвебхдмн гюпюмее, рюй йюй опх $Q=1$ гюдювю нвемэ опнярю. Юмюкнцхвмне бшвхякемхе дкъ $Q=2$ (ял.~соп.~14) дюер лемее нвебхдмсч тнплскс: $$ a_n^{(2)}={p_0^2n\over 1-p_1}-{p_0^2(1-p_1^n)\over(1-p_1)^2}. \eqno(10) $$ Б наыел яксвюе лнфмн онйюгюрэ, врн $a_n^{(Q)}$ хлеер бхд~$\alpha^{(Q)}n+O(1)$ опх $n\to\infty$, цде йнмярюмрс~$\alpha^{(Q)}$ ме якхьйнл рпсдмн бшвхякхрэ. (Ял. соп.~15.) Йюй нйюгшбюеряъ, $\alpha^{(3)}=p_0^3/((1-p_1)^2-p_0p_2)$. Хяундъ хг опхпндш якхъмхъ, днбнкэмн пюгслмн опедонкнфхрэ, врн $\mu=1/P$ х врн бепнърмнярх~$p_k$ яннрберярбсчр ахмнлхюкэмнлс пюяопедекемхч $$ p_k=\perm{P}{k}\perm{1}{P}^k{\left({P-1\over P}\right)\hbox to 0pt{.\hss}}^{P-k} $$ Мюопхлеп, еякх $P=5$, рн $p_0= .32768$, $p_1=.4096$, $p_2= .2048$, $p_3=.0512$, $p_4=.0064$ х~$p_5=.00032$; якеднбюрекэмн, $\alpha^{(1)}=0.328$, $\alpha^{(2)}=0.182$ х~$\alpha^{(3)}=0.127$. Дпсцхлх якнбюлх, еякх лш хяонкэгсел $5+3$~ббндмшу астепнб блеярн~$5+5$, рн лнфмн нфхдюрэ днонкмхрекэмнцн бпелемх гюдепфйх времхъ онпъдйю~$0.127/5\approx 2.5\%$. %% 409 Йнмевмн, щрю лндекэ---рнкэйн нвемэ цпсане опхакхфемхе. Лш гмюел, врн опх $Q=P$ бннаые мер бпелемх гюдепфйх, мн еякх ясдхрэ он лндекх, рн еярэ. Днонкмхрекэмне бпелъ гюдепфйх времхъ дкъ лемэьху~$Q$ онврх рнвмн спюбмнбеьхбюер бшхцпшь б мюйкюдмшу пюяундюу, онксвюелши нр хяонкэгнбюмхъ анкее йпсомшу акнйнб, рюй врн опнярюъ яуелю я $Q=P$ йюферяъ нопюбдюммни. \excercises \ex[13] Бшбедхре тнплскс дкъ рнвмнцн вхякю кхреп мю кемре, еякх йюфдши акнй яндепфхр $n$~кхреп. Явхрюире, врн кемрю лнцкю аш блеярхрэ пнбмн 23000000 кхреп, еякх аш ме ашкн лефакнвмшу опнлефсрйнб. \ex[15] На╝ъямхре, онвелс оепбши астеп тюикю~$2$ б ярпнйе~$6$ пхя.~84 янбяел осяр. \ex[20] Асдер кх юкцнпхрл~F пюанрюрэ днкфмшл напюгнл, еякх блеярн $2P$~астепнб ббндю хлееряъ рнкэйн $2P-1$? Еякх дю, днйюфхре щрн, еякх мер--- опхбедхре опхлеп, йнцдю юкцнпхрл репохр месдювс. \ex[20] Йюй хглемхрэ юкцнпхрл~F, врнаш нм пюанрюк рюйфе х опх~$P=1$? \rex[21] Еякх б пюгкхвмшу тюикюу хлечряъ пюбмше йкчвх, менаундхлн б опнжеяяе опнцмнгхпнбюмхъ деиярбнбюрэ нвемэ юййспюрмн. На╝ъямхре, онвелс, х онйюфхре, йюй хгаефюрэ рпсдмняреи, еякх анкее ярпнцн нопедекхрэ ноепюжхх якхъмхъ х опнцмнгхпнбюмхъ б юкцнпхрле~F. \ex[22] Йюйхе хглемемхъ якедсер ядекюрэ б юкцнпхрле~5.4.3Я, врнаш опенапюгнбюрэ ецн б юкцнпхрл йюяйюдмнцн якхъмхъ \emph{я янблеыемхел оепелнрйх} мю $T+1$~кемрюу? \rex [26] Мювюкэмне пюяопедекемхе б опхлепе~7 яуелш~Ю онпнфдюер $$ (A_1D_1)^{11}\quad D_1(A_1D_1)^{10}\quad D_1(A_1D_1)^9\quad D_1(A_1D_1)^7 $$ мю кемрюу~1--4, цде $(A_1D_1)^7$ нгмювюер $A_1D_1A_1D_1A_1D_1A_1D_1A_1D_1A_1D_1A_1D_1$. Онйюфхре, йюй бярюбхрэ днонкмхрекэмше нрпегйх~$A_0$ х~$D_0$ мюхксвьхл хг бнглнфмшу яонянанб (б рнл ялшяке, врн наыее вхякн напюаюршбюелшу бн бпелъ якхъмхъ мювюкэмшу нрпегйнб асдер лхмхлюкэмшл), врнаш опхбеярх пюяопедекемхе й $$ A(DA)^{14}\quad (DA)^{28}\quad (DA)^{26}\quad (DA)^{22}. $$ [\emph{Сйюгюмхе.} Врнаш янупюмхрэ вермнярэ, менаундхлн бярюбкърэ~$A_0$ х~$D_0$ б бхде яняедмху оюп. Вхякю якхъмхъ дкъ йюфднцн мювюкэмнцн нрпегйю лнцср ашрэ ондявхрюмш, йюй б соп~5.4.4-5; гдеяэ онъбкъеряъ мейнрнпне сопныемхе, рюй йюй яняедмхе нрпегйх бяецдю хлечр яняедмхе вхякю якхъмхъ.] \ex[20] Хг яуелш~Ю бхдмн, врн анкэьхмярбн яуел мювюкэмнцн пюяопедекемхъ нрпегйнб (гю хяйкчвемхел мювюкэмнцн пюяопедекемхъ дкъ йюяйюдмнцн якхъмхъ) хлеер ремдемжхч онлеыюрэ онякеднбюрекэмше нрпегйх мю пюгкхвмше кемрш. Еякх аш онякеднбюрекэмше нрпегйх оноюкх мю ндмс кемрс, рн лш лнцкх аш ящйнмнлхрэ ярюпрярномне бпелъ; лнфмн кх онщрнлс явхрюрэ унпньеи лшякэ хглемхрэ юкцнпхрлш пюяопедекемхъ рюй, врнаш нмх пефе оепейкчвюкх кемрш? \rex[22] Нжемхре, яйнкэйн бпелемх гюмък аш лмнцнтюгмши юкцнпхрл я напюрмшл времхел хг яуелш~Ю, еякх аш лш хяонкэгнбюкх дкъ янпрхпнбйх бяе $T=6$ кемр, ю ме $T=5$, йюй б опхлепе~7. Ашкн кх пюгслмн хгаецюрэ хяонкэгнбюмхъ ббндмни кемрш? \ex[Л23] Хяонкэгсъ юмюкхг, опнбедеммши б о.~5.4.2 х~5.4.3, онйюфхре, врн дкхмю йюфдни оепелнрйх бн бпелъ ярюмдюпрмнцн лмнцнтюгмнцн якхъмхъ я ьеярэч кемрюлх хкх йюяйюдмнцн якхъмхъ педйн опебшьюер 54\% тюикю (хяйкчвюъ мювюкэмсч х йнмевмсч оепелнрйх, йнрнпше нубюршбючр беяэ тюик). %%410 \ex[23] Хглемхб ондундъыхе щкелемрш рюак.~1, нжемхре, яйнкэйн бпелемх гюмъкх аш оепбше дебърэ опхлепнб яуелш~Ю, еякх аш лш хлекх дбсуяйнпнярхсч оепелнрйс (ашярпсч х ледкеммсч) Явхрюире, врн $p=1$, еякх кемрю гюонкмемю лемэье вел мю ндмс вербепрэ, ю дкъ анкее гюонкмеммни кемрш бпелъ оепелнрйх пюбмн опхакхгхрекэмн оърх яейсмдюл окчя рн бпелъ, йнрнпне онксвхкняэ аш опх $\rho=1/5$ Хглемхре опхлеп~8 рюй, врнаш нм хяонкэгнбюк йюяйюдмне якхъмхе я йнохпнбюмхел, оняйнкэйс оепелерйю х опълне времхе б щрнл яксвюе ледкеммее йнохпнбюмхъ [\emph{Сйюгюмхе:} хяонкэгсире пегскэрюр соп. 10 ] \ex[40] Пюяялнрпхл пюгахемхе ьеярх кемр мю рпх оюпш кемр, цде йюфдюъ оюпю хцпюер пнкэ ндмни кемрш б лмнцнтюгмнл якхъмхх я~$T=3$ Ндмю кемрю йюфдни оюпш асдер яндепфюрэ акнйх~$1$, $3$, $5$,~\dots, ю дпсцюъ---акнйх~$2$, $4$, $6$,~\dots, рюйхл яонянанл лш, он ясыеярбс, днахбюеляъ рнцн, врнаш бн бяе бпелъ якхъмхъ дбе ббндмше х дбе бшбндмше кемрш нярюбюкхяэ юйрхбмшлх, опхвел щттейрхбмюъ яйнпнярэ якхъмхъ сдбюхбюеряъ \item{(a)} Мюидхре ондундъыхи яоняна пюяопнярпюмхрэ юкцнпхрл~F мю щрнр яксвюи. \item{(b)} Нжемхре наыее бпелъ бшонкмемхъ, йнрнпне онксвхкняэ аш, еякх аш щрнр лернд ашк хяонкэгнбюм дкъ янпрхпнбйх 100000~гюохяеи он 100~кхреп, пюяялнрпеб яксвюи йюй опълнцн, рюй х напюрмнцн времхъ. \ex[20] Лнфер кх няжхккхпсчыюъ янпрхпнбйю я оърэч кемрюлх, б рнл бхде йюй нмю нопедекемю б юкцнпхрле 5.4.5Б, хяонкэгнбюрэяъ дкъ янпрхпнбйх вершпеу онкмшу анахм хяундмшу дюммшу дн лнлемрю нйнмвюрекэмнцн якхъмхъ? \ex[Л19] Бшбедхре (10). \ex[БЛ29] Днйюфхре, врн $g_Q(z)=h_Q(z)/(1-z)$, цде $h_Q(z)$~ъбкъеряъ пюжхнмюкэмни тсмйжхеи~$z$, ме хлечыеи нянаеммняреи бмсрпх едхмхвмнцн йпсцю; якеднбюрекэмн, $a_n^{(Q)}=h_Q(1)n+O(1)$ опх $n\to\infty$. Б вюярмнярх, онйюфхре, врн $$ h_3(1)=\det\pmatrix{ 0 & -p_0 & 0 & 0 \cr 0 & 1-p_1 & -p_0 & 0 \cr 0 & -p_2 & 1-p_1 & -p_0 \cr 1 & 0 & 0 & 0 \cr } /\det\pmatrix{ 1 & -p_0 & 0 & 0 \cr 1 & 1-p_1 & -p_0 & 0 \cr 1 & -p_2 & 1-p_1 & -p_0\cr 0 & 0 & -1 & 1 \cr }. $$ \ex[M46] Опнюмюкхгхпсире якхъмхе я $P+Q$~астепюлх анкее рыюрекэмн, вел щрн ашкн ядекюмн б рейяре, хяонкэгсъ анкее рнвмсч лндекэ. \ex[41] Опнбедхре дерюкэмне хгсвемхе гюдювх янпрхпнбйх 100000~гюохяеи ън 100~кхреп, мюпхясире яуелш, онднамше яуеле~Ю, б опедонкнфемхх, врн хлееряъ~3, 4 хкх~5 кемр \subsubchap{*Бмеьмъъ онпюгпъдмюъ янпрхпнбйю} %5.4.7 Б опедшдсыху осмйрюу лш пюяялнрпекх опнжеяя кемрнвмни янпрхпнбйх якхъмхел; мн ясыеярбсер х дпсцни яоняна янпрхпнбйх мю кемрюу, нямнбюммши мю опхмжхое онпюгпъдмни янпрхпнбйх, хяонкэгселни б леуюмхвеяйху янпрхпнбюкэмшу люьхмюу дкъ оептнйюпр (яп. я о.~5.2.5). Щрнр лернд хмнцдю мюгшбючр пюяопедекъчыеи янпрхпнбйни, онйнкнммни янпрхпнбйни, йюплюммни янпрхпнбйни, жхтпнбни янпрхпнбйни, янпрхпнбйни пюгдекемхел х р. д. Нм, йюй нйюгшбюеряъ, он ясыеярбс, \emph{опнрхбнонкнфем} якхъмхч! Опедонкнфхл, мюопхлеп, врн б мюьел пюяонпъфемхх хлечряъ вершпе кемрш, ю йкчвеи лнфер ашрэ рнкэйн бняелэ: $0$, $1$, $2$, $3$, %%411 $4$, $5$, $6$, $7$. Еякх хяундмше дюммше мюундъряъ мю кемре~$T1$, рн мювмел я оепеохях бяеу вермшу йкчвеи мю~$T3$ х бяеу мевермшу мю~$T4$: \ctable{ \hfill#&&\bskip\hfill$#$\hfill\bskip\cr & T1 & T2 & T3 & T4 \cr Дюмн & \{0, 1, 2, 3, 4, 5, 6, 7\} & - & - & - \cr Опнунд 1& - & - & \{0, 2, 4, 6\} & \{1, 3, 5, 7\}\cr \noalign{ \noindent Реоепэ оепелюршбюел кемрш х вхрюел~$T3$, ю гюрел ~$T4$, онлеыюъ $\{0, 1, 4, 5\}$ мю~$T1$ х~$\{2, 3, 6, 7\}$ мю~$T2$: } Опнунд 2. & \{0,4\} \{1,5\} & \{2,6\} \{3,7\} & - &- \cr \noalign{ \noindent(Ярпнйю~$\{0, 4\}\{1, 5\}$ нангмювюер тюик, яндепфюыхи гюохях рнкэйн я йкчвюлх~$0$ х~$4$, гю йнрнпшлх якедсчр гюохях рнкэйн я йкчвюлх~$1$ х~$5$. Гюлерхл, врн~$T1$ реоепэ яндепфхр ре йкчвх, япедмхи дбнхвмши пюгпъд йнрнпшу яндепфхр~$0$.) Оняке еые ндмни оепелнрйх х пюяопедекемхъ йкчвеи~$0$, $1$, $2$, $3$ мю~$T3$ х йкчвеи~$4$, $5$, $6$, $7$ мю~$T4$ лш хлеел } Опнунд~3 & - & & \{0\}\{1\}\{2\}\{3\} & \{4\} \{5\} \{6\} \{7\} \cr } Реоепэ йнохпнбюмхе~$T4$ б йнмеж~$T3$ гюбепьюер пюанрс. Б наыел яксвюе дкъ йкчвеи б дхюоюгнме нр~$0$ дн~$2^k-1$ лнфмн нрянпрхпнбюрэ тюик юмюкнцхвмшл напюгнл, хяонкэгнбюб $k$~опнунднб, гю йнрнпшлх якедсер тюгю нйнмвюрекэмни "яанпйх", йнохпсчыюъ опхлепмн онкнбхмс дюммшу я ндмни кемрш мю дпсцсч. Хлеъ ьеярэ кемр, лш лнфел юмюкнцхвмшл напюгнл хяонкэгнбюрэ опедярюбкемхъ он нямнбюмхч~$3$ дкъ янпрхпнбйх йкчвеи нр~$0$ дн~$3^k-1$ гю $k$~опнунднб. Хяонкэгсчряъ рюйфе лерндш я вюярхвмшлх опнундюлх. Опедонкнфхл, мюопхлеп, врн дносяйюеряъ деяърэ йкчвеи $\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$, х пюяялнрпхл якедсчысч опнжедспс, опхмюдкефюысч П.~К.~Щьемуепярс [{\sl Theory of Switching,\/} {\bf 7} (Harvard Univ. Comp. Laboratory: May, 1954), I.1--I.76]: \ctable{ \hfill# &\bskip\hfill$#$\hfill\bskip &\bskip\hfill$#$\hfill\bskip &\bskip\hfill$#$\hfill\bskip &\bskip\hfill$#$\hfill\bskip &\bskip#\hfill\cr & T1 & T2 & T3 & T4 \cr Дюмн & \{0, 1,~\ldots, 9\} & - & - & - \cr Опнунд~1.& - & \{0, 2, 4, 7\} & \{1, 5, 6\} & \{3, 8, 9\} & $1.0$~опнунд \cr Опнунд~2.& \{0\} & - & \{1, 5, 6\}\{2,7\} & \{3,8,9\}\{4\} &$0.4$~опнундю\cr Опнунд~3.& \{0\}\{1\}\{2\} & \{6\}\{7\} & - & \{3,8,9\}\{4\}\{5\}& $0.5$~опнундю\cr Опнунд~4. & \{0\}\{1\}\{2\}\{3\} & \{6\}\{7\}\{8\} & \{9\} &\{4\}\{5\}& $0.3$~опнундю\cr Яанпйю & \{0\}\{1\}\{2\}\{3\}\{4\}\ldots\{9\} & & & & $0.6$~опнундю\cr & & & & & $\overline{\hbox{$2.8$ опнундю}}$\cr } %%412 Еякх йюфдне гмювемхе йкчвю бярпевюеряъ опхлепмн б ндмни деяърни яксвюеб, рн щрю опнжедспю дкъ янпрхпнбйх деяърх йкчвеи гюрпювхбюер рнкэйн $2.8$~опнундю, б рн бпелъ йюй оепбши опхлеп рпеасер $3.5$~опнундю дкъ янпрхпнбйх бяецн бняэлх йкчвеи. Рюйхл напюгнл, лш бхдхл, врн хяйсямюъ яуелю пюяопедекемхъ лнфер бшгбюрэ гмювхрекэмне пюгкхвхе дкъ онпюгпъдмни янпрхпнбйх рнвмн рюй фе, йюй дкъ якхъмхъ. Яуелш пюяопедекемхъ опедшдсыху опхлепнб опедярюбхл, йюй х нашвмн, дпебнбхдмшлх ярпсйрспюлх: \picture{пхя. мю ярп. 412} Йпсцкше бмсрпеммхе сгкш щрху депебэеб гюмслепнбюмш~$1$, $2$, $3$,~\dots б яннрберярбхх я ьюцюлх опнжеяяю~$1$, $2$, $3$,~\dots. Хлемю кемр~$A$, $B$, $C$, $D$ (блеярн $T1$, $T2$, $T3$, $T4$) онлеыемш пъднл я пеапюлх депебю, врнаш сйюгюрэ, йсдю оноюдючр гюохях. Йбюдпюрмше бмеьмхе сгкш хгнапюфючр вюярх тюикю, яндепфюыхе рнкэйн ндхм йкчв, х щрнр йкчв хгнапюфем фхпмшл ьпхтрнл онд яннрберярбсчыхл сгкнл. Пеапю мюд йбюдпюрмшлх сгкюлх бяе онлевемш хлемел бшбндмни кемрш ($C$ б оепбнл опхлепе, $A$ бн брнпнл). Рюйхл напюгнл, ьюц~3 опхлепю~1 янярнхр хг времхъ я кемрш~$D$ х гюохях йкчвеи~$1$ х~$5$ мю кемрс~$A$ х йкчвеи~$3$ х~$7$ мю кемрс~$B$. Мерпсдмн бхдерэ, врн вхякн бшонкмъелшу опнунднб пюбмн \emph{дкхме бмеьмецн осрх} депебю, декеммни мю вхякн бмеьмху сгкнб, еякх лш опхмхлюел, врн бяе йкчвх пюбмнбепнърмш. Б яхкс онякеднбюрекэмни опхпндш кемрш х дхяжхокхмш "оепбшл бйкчвюеряъ---оепбшл хяйкчвюеряъ", йнрнпни ондвхмъеряъ опълне времхе, мекэгъ бгърэ гю нямнбс яуелш пюяопедекемхъ \emph{кчане} онлевеммне депебн. Б депебе опхлепю~1 дюммше гюохяшбючряъ мю кемрс~$A$ мю ьюце~2 х ьюце~3; дюммше, гюохяюммше б ревемхе ьюцю~2, менаундхлн хяонкэгнбюрэ пюмэье дюммшу, гюохяюммшу б ревемхе ьюцю~3. Б наыел яксвюе, еякх лш гюохяшбюел мю кемрс б ревемхе ьюцнб~$i$ х~$j$, цде $i < j$, оепбшлх якедсер %%413 хяонкэгнбюрэ дюммше, гюохяюммше б ревемхе ьюцю~$i$; еякх депебн яндепфхр дбе бербх бхдю \picture{пхя. ярп. 413} рн днкфмн бшонкмърэяъ сякнбхе $k