\input style леярюу, цде мю йюпре нроептнпхпнбюмш нрбепярхъ, бундър б йнмрюйр я прсрэч мю мхфмеи оюмекх. Б пегскэрюре гюлшйюмхъ яннрберярбсчыеи жеох онйюгюмхе ябъгюммнцн я меи жхтепакюрю хглемъеряъ мю 1 х, йпнле рнцн, ндмю хг 26 йпшьей янпрхпнбюкэмнцн ъыхйю нрйпшбюеряъ. Б щрнр лнлемр ноепюрнп нросяйюер опеяя, йкюдер йюпрс б нрйпшрне нрдекемхе х гюйпшбюер йпшьйс. Он яннаыемхъл, йюй-рн вепег щрс люьхмс опносярхкх 19071 йюпрс гю ндхм 6.5-вюянбни пюанвхи демэ; б япедмел опхлепмн 49 йюпр б лхмсрс! (Япедмхи ноепюрнп пюанрюк опхлепмн брпне ледкеммеи.) Мюяекемхе опнднкфюкн месйкнммн пюярх, х оепбше рюаскърнпш-янпрхпнбыхйх нйюгюкхяэ меднярюрнвмн ашярпшлх, врнаш яопюбхрэяъ я напюанрйни оепеохях 1900~ц., онщрнлс Унккепхр хгнапек еые ндмс люьхмс, врнаш опеднрбпюрхрэ еые ндхм йпхгхя б напюанрйе дюммшу. Ецн мнбне сярпниярбн (гюоюремрнбюммне б 1901 х 1904 цц.) хлекн юбрнлюрхвеяйсч ондювс йюпр х бшцкъдекн, б ясымнярх, онврх рюй фе, йюй янбпелеммше йюпрнвмше янпрхпнбюкэмше люьхмш. Хярнпхъ пюммху люьхм Унккепхрю я хмрепеямшлх ондпнамнярълх хгкнфемю Кенмнл Щ. Рпсядеккнл б The Development of Punch Card Tabulation (Washington: U. S. Bureau of the Census, 1965); ял. рюйфе яннаыемхъ янбпелеммхйнб Унккепхрю: {\sl Columbia College School of Mines Quarterly\/}, {\bf 10} (1889), 238--255; {\sl J. Franclin Inst.\/}, {\bf 129} (1890), 300-- 306; {\sl The Electrical Engineer\/}, {\bf 12} (Nov. 11, 1891). 521--530; {\sl J. Amer. Statistical Assn.\/}, {\bf 2} (1891), 330--341;{\bf 4} (1895), 365; {\sl J. Royal Statistical Soc.\/}, {\bf 55} (1892), 326--327; {\sl Alegemeines Statistisches Archiv\/}, {\bf 2} (1892), 78--126; {\sl J. Soc. Statistique de Paris\/}, {\bf 33} (1892), 87--96; U.~S. Patents 395781 (1889), 685608 (1901), 777209 (1904). Унккепхр х дпсцни ашбьхи яксфюыхи Ачпн оепеохях Дфеиля Оюсщпя б дюкэмеиьел нямнбюкх йнмйспхпсчыхе йнлоюмхх, йнрнпше б йнмже йнмжнб бнькх яннрберярбеммн б йнпонпюжхх IBM х Remington Rand. Янпрхпнбюкэмюъ люьхмю Унккепхрю---щрн, йнмевмн, нямнбю лернднб онпюгпъдмни янпрхпнбйх, хяонкэгселшу б жхтпнбшу ЩБЛ. Б ецн оюремре сонлхмюеряъ, врн вхякнбше щкелемрш, яндепфюыхе дбю ярнкажю, днкфмш янпрхпнбюрэяъ "он нрдекэмнярх дкъ йюфднцн ярнкажю", мн нм ме цнбнпхр, йюйни ярнкаеж (едхмхж хкх деяърйнб) днкфем пюяялюрпхбюрэяъ оепбшл. Дюкейн ме нвебхдмюъ хдеъ янпрхпнбйх ямювюкю он ярнкажс едхмхж ашкю, он-бхдхлнлс, нрйпшрю йюйхл-рн мехгбеярмшл ноепюрнпнл х оепедюмю нярюкэмшл (ял. о.~5.2.5); нмю хлееряъ б яюлнл пюммел янупюмхбьеляъ псйнбндярбе IBM он янпрхпнбйе (1936~ц.). Оепбшл хгбеярмшл сонлхмюмхел щрнцн лерндю "яопюбю мюкебн" ъбкъеряъ яксвюимне гюлевюмхе, бярперхбьееяъ б ярюрэе К. Дф. Йнлпх, {\sl Trans. of the Office Machinery Users' Assoc\/}. (London, 1930), 25--37. Мевюъммн Йнлпх нйюгюкяъ оепбшл, йрн ядекюк бюфмне мюакчдемхе, врн %% 458 рюаскърнпш лнфмн окнднрбнпмн опхлемърэ б мюсвмшу бшвхякемхъу, унръ оепбнмювюкэмн нмх янгдюбюкхяэ дкъ ярюрхярхвеяйху х асуцюкрепяйху опхкнфемхи. Ецн ярюрэъ нянаеммн хмрепеямю, оняйнкэйс, яндепфхр ондпнамне нохяюмхе рюаскърнпнб, хлебьхуяъ б Юмцкхх б 1930~ц. Янпрхпнбюкэмше люьхмш б рн бпелъ напюаюршбюкх нр~360 дн~400 йюпр б лхмсрс х ядюбюкхяэ б юпемдс гю 9 тсмрнб ярепкхмцнб б леяъж. Хдеъ якхъмхъ бняундхр й дпсцнлс сярпниярбс дкъ напюанрйх йюпр---\emph{онданпнвмни люьхме}, йнрнпюъ ашкю хгнаперемю гмювхрекэмн онгдмее (б 1938~ц.). Ямюафеммюъ дбслъ ондючыхлх леуюмхглюлх, нмю лнцкю якхрэ дбе нрянпрхпнбюммше йнкндш йюпр б ндмс бяецн гю ндхм опнунд; лернд бшонкмемхъ щрнцн якхъмхъ унпньн нохяюм б оепбнл псйнбндярбе IBM он лерндюл онданпйх (юопекэ 1939~ц.). [Яп. я James W. Bryce. U.~S. Patent 2189024 (1940).] Гюрел мю яжеме онъбхкхяэ ЩБЛ х пюгпюанрйю лернднб янпрхпнбйх реямн оепеокекюяэ я ху пюгбхрхел. Мю яюлнл деке хлечряъ ябхдерекэярбю рнцн, врн опнцпюллю янпрхпнбйх ашкю оепбни йнцдю-кхан мюохяюммни дкъ бшвхякхрекэмшу люьхм я гюонлхмюелни опнцпюллни. Йнмярпсйрнпш бшвхякхрекэмни люьхмш EDVAC нянаеммн хмрепеянбюкхяэ янпрхпнбйни, оняйнкэйс нмю бшярсоюкю йюй мюханкее уюпюйрепмши опедярюбхрекэ онремжхюкэмшу мевхякеммшу опхкнфемхи ЩБЛ. Нмх онмхлюкх, врн сднбкербнпхрекэмюъ яхярелю йнлюмд днкфмю цндхрэяъ ме рнкэйн дкъ янярюбкемхъ опнцпюллш пеьемхъ пюгмнярмшу спюбмемхи; б меи днкфмю ашрэ днярюрнвмюъ цхайнярэ, врнаш яопюбхрэяъ я йнлахмюрнпмшлх юяоейрюлх "бшанпю пеьемхи" б юкцнпхрлюу. Онщрнлс Дфнм тнм Меилюм ондцнрнбхк б 1945 ц. опнцпюллш дкъ бмсрпеммеи янпрхпнбйх якхъмхел, врнаш саедхрэяъ б менаундхлнярх мейнрнпшу йнднб йнлюмд, йнрнпше нм опедкюцюк дкъ люьхмш EDVAC; ясыеярбнбюкх щттейрхбмше янпрхпнбюкэмше люьхмш яоежхюкэмнцн мюгмювемхъ, х нмх яксфхкх рел еяреярбеммшл ярюмдюпрнл, б янонярюбкемхх я йнрнпшл лнфмн ашкн нжемхрэ днярнхмярбю опедкюцюелни нпцюмхгюжхх бшвхякхрекэмни люьхмш. Ондпнамн щрн хмрепеямне хяякеднбюмхе нохяюмн б ярюрэе Д.~Щ.~Ймсрю [{\sl Computing Surveys\/}, {\bf 2} (1970), 247--260]; оепбсч опнцпюллс янпрхпнбйх тнм Меилюмю б нйнмвюрекэмнл, "нронкхпнбюммнл" бхде ял. б ецн Collected Works, {\bf 5} (New York, Macmillan, 1963), 196--214. Хг-гю нцпюмхвеммнцн на╝елю оюлърх б пюммху люьхмюу опхундхкняэ дслюрэ н бмеьмеи янпрхпнбйе мюпюбме я бмсрпеммеи, х б днйкюде "Progress Report on the EDVAC", ондцнрнбкеммнл Дф. О. Щййепрнл х Дф С. Лнвкх дкъ ьйнкш Лспю он щкейрпнреумхйе [Moore school of Electrical Engineering (September 30, 1945)], сйюгшбюкняэ, врн ЩБЛ, нямюыеммюъ сярпниярбнл я люцмхрмни опнбнкнйни хкх кемрни, лнцкю аш лндекхпнбюрэ %% 459 деиярбхъ йюпрнвмнцн нанпсднбюмхъ, днярхцюъ опх щрнл анкэьеи яйнпнярх янпрхпнбйх. Щрнр днйкюд нохяшбюк яаюкюмяхпнбюммсч дбсуосребсч онпюгпъдмсч янпрхпнбйс х яаюкюмяхпнбюммне дбсуосребне якхъмхе я хяонкэгнбюмхел вершпеу сярпниярб я люцмхрмни опнбнкнйни хкх кемрни, вхрючыху хкх гюохяшбючыху "ме лемее 5000 хлоскэянб б яейсмдс". Дфнм Лнвкх бшярсохк я кейжхеи н "янпрхпнбйе х якхъмхх" мю яоежхюкэмни яеяяхх он бшвхякемхъл, янгшбюбьеияъ б ьйнке Лспю б 1946 ц., х б гюохяъу ецн кейжхх яндепфхряъ оепбне носакхйнбюммне наясфдемхе янпрхпнбйх я онлныэч бшвхякхрекэмшу люьхм [Theory and techniques for the design of electronic digital computers, ed. by G. W. Patterson, {\bf 3} (1946), 22.1--22.20]. Лнвкх мювюк ябне бшярсокемхе я хмрепеямнцн гюлевюмхъ: "Рпеанбюмхе, врнаш ндмю люьхмю на╝едхмъкю бнглнфмнярх бшвхякемхи х янпрхпнбйх, лнфер бшцкъдерэ йюй рпеанбюмхе, врнаш ндхм опханп хяонкэгнбюкяъ йюй йкчв дкъ йнмяепбнб х йюй юбрнпсвйю". Гюрел нм гюлерхк, врн люьхмш, яонянамше бшонкмърэ якнфмше люрелюрхвеяйхе опнжедспш, днкфмш рюйфе хлерэ бнглнфмнярэ янпрхпнбюрэ х йкюяяхтхжхпнбюрэ дюммше; нм онйюгюк, врн янпрхпнбйю лнфер ашрэ онкегмю дюфе б ябъгх я вхякеммшлх пюяверюлх. Нм нохяюк опнярше бярюбйх х ахмюпмше бярюбйх, гюлерхб, врн б оепбнл лернде б япедмел рпеасеряъ нйнкн $N^2/4$ япюбмемхи, б рн бпелъ йюй б онякедмел ху мхйнцдю ме рпеасеряъ анкее $N\log_2N$. Ндмюйн ахмюпмше бярюбйх рпеасчр беяэлю якнфмни ярпсйрспш дюммшу, х Лнвкх гюрел онйюгюк, врн опх дбсуосребнл якхъмхх днярхцюеряъ ярнкэ фе люкне вхякн япюбмемхи, мн хяонкэгсеряъ рнкэйн онякеднбюрекэмне опнунфдемхе яохяйнб. Онякедмъъ вюярэ гюохяеи ецн кейжхи онябъыемю пюганпс лернднб онпюгпъдмни янпрхпнбйх я вюярхвмшлх опнундюлх, йнрнпше лндекхпсчр жхтпнбсч йюпрнвмсч янпрхпнбйс мю вершпеу кемрюу, гюрпювхбюъ лемее вершпеу опнунднб мю жхтпс (яп. я о. 5.4.7). Бяйнпе оняке щрнцн Щййепр х Лнвкх нпцюмхгнбюкх йнлоюмхч, йнрнпюъ бшосяйюкю мейнрнпше хг яюлшу пюммху щкейрпнммшу бшвхякхрекэмшу люьхм BINAC (дкъ бнеммшу опхкнфемхи) х. UNIVAC (дкъ йнллепвеяйху опхкнфемхи). Бмнбэ Ачпн оепеохях ЯЬЮ яшцпюкн пнкэ б щрнл пюгбхрхх, опхнаперъ оепбши UNIVAC. Б щрн бпелъ бнбяе ме ашкн ъямн, врн ЩБЛ ярюмср щйнмнлхвеяйх бшцндмшлх: бшвхякхрекэмше люьхмш лнцкх янпрхпнбюрэ ашярпее, мн нмх днпнфе ярнхкх. Онщрнлс опнцпюллхярш UNIVAC онд псйнбндярбнл Тпюмяхя Щ. Цнкэаепрнм опхкнфхкх гмювхрекэмше сяхкхъ й янгдюмхч опнцпюлл бмеьмеи янпрхпнбйх, пюанрючыху я бшянйни яйнпнярэч, х ху оепбше опнцпюллш онбкхъкх рюйфе мю пюгпюанрйс нанпсднбюмхъ. Он ху нжемйюл, 100 лхккхнмнб гюохяеи он 10 якнб лнцкх ашрэ .нрянпрхпнбюмш мю UNIVAC гю 9000 в (р. е. 375 дмеи). %% 460 UNIVAC I, нтхжхюкэмн на╝ъбкеммюъ б хчке 1951 ц., хлекю бмсрпеммчч оюлърэ б 1000 12-кхрепмшу (72-ахрнбшу) якнб. Б меи опедсялюрпхбюкняэ времхе х гюохяэ мю кемрс акнйнб он 60 якнб ян яйнпнярэч 500 якнб б яейсмдс; времхе лнцкн ашрэ опълшл хкх напюрмшл, дносяйюкняэ ндмнбпелеммне времхе /гюохяэ/ бшвхякемхъ. Б 1948~ц. лхяяхя Цнкэаепрнм опхдслюкю хмрепеямши яоняна бшонкмемхъ дбсуосребнцн якхъмхъ я онкмшл янблеыемхел времхъ, гюохях х бшвхякемхи я хяонкэгнбюмхел ьеярх астепнб ббндю. Осярэ дкъ йюфднцн ббндмнцн тюикю хлечряъ ндхм "рейсыхи астеп" х дбю "бяонлнцюрекэмшу астепю"; якхбюрэ лнфмн рюйхл напюгнл, врн бяъйхи пюг, йнцдю опхундхр бпелъ бшбеярх ндхм акнй, дбю рейсыху астепю ббндю .яндепфюр блеяре йнкхвеярбн дюммшу, пюбмне ндмнлс акнйс. Рюйхл напюгнл, гю бпелъ тнплхпнбюмхъ йюфднцн бшбндмнцн акнйю пнбмн ндхм астеп ббндю ярюмнбхряъ осяршл, х лш лнфел сярпнхрэ рюй, врнаш рпх хкх вершпе бяонлнцюрекэмшу астепю ашкх гюонкмемш бяъйхи пюг, йюй лш вхрюел б нярюбьхияъ астеп. Щрнр лернд всрэ ашярпее лерндю опнцмнгхпнбюмхъ юкцнпхрлю 5.4.6F, рюй йюй мер менаундхлнярх опнбепърэ пегскэрюр ндмнцн ббндю оепед мювюкнл якедсчыецн. [Яп. я Collation Methods for the UNIVAC System (Eckert-Mauchly Computer Corp., 1950) vol. 1,2.] Йскэлхмюжхнммни рнвйни б щрни пюанре ярюк цемепюрнп опнцпюлл янпрхпнбйх, йнрнпши ашк оепбни йпсомни опнцпюллни, пюгпюанрюммни дкъ юбрнлюрхвеяйнцн опнцпюллхпнбюмхъ. Онкэгнбюрекэ сйюгшбюк пюглеп гюохях, онгхжхх йкчвеи (дн оърх) б вюярхвмшу онкъу йюфдни гюохях х "йнмжебше" йкчвх, нрлевючыхе йнмеж тюикю, х цемепюрнп янпрхпнбйх онпнфдюк рпеаселсч опнцпюллс янпрхпнбйх дкъ тюикнб мю ндмни анахме. Оепбшл опнунднл щрни опнцпюллш ашкю бмсрпеммъъ янпрхпнбйю акнйнб он 60 якнб я хяонкэгнбюмхел лерндю япюбмемхъ х ондяверю (юкцнпхрл 5.2Я); гюрел бшонкмъкяъ пъд яаюкюмяхпнбюммшу дбсуосребшу опнунднб якхъмхъ я напюрмшл времхел, хяйкчвючыху яжеокемхе кемр, йюй нохяюмн бшье. [Ял. Master Generating Routine for 2-way Sorting (Eckert---Mauchly Div. of Remington Rand, 1952). Оепбши мюапнянй щрнцн днйкюдю ашк нгюцкюбкем "Нямнбмюъ янярюбкъчыюъ опнцпюллю дбсуосребнцн якхъмхъ" (Master Prefabrication Routine for 2-way Collation)! Ял. рюйфе F. E. Holberton, Symposium on Automatic Programming (Office of Naval Research, 1954), 34--39.] Й 1952~ц. лмнцхе лерндш бмсрпеммеи янпрхпнбйх опнвмн бнькх б опнцпюллхяряйхи тнкэйкнп, мн ренпхъ ашкю пюгбхрю япюбмхрекэмн якюан. Дюмхщкэ Цнкдемаепц [Time analises of various methods of sorting data, Digital Computer Lab. memo M-1680 (Mass. Inst. of Tech.,. October 17, 1952)] гюопнцпюллхпнбюк дкъ люьхмш Whirlwind оърэ пюгкхвмшу лернднб х опнбек юмюкхг %% 461 мюхксвьецн х мюхусдьецн яксвюеб дкъ йюфдни опнцпюллш. Нм мюьек, врн дкъ янпрхпнбйх янрмх 15-ахрнбшу гюохяеи он 8-ахрнбнлс йкчвс мюхксвьхе он яйнпнярх пегскэрюрш онксвючряъ б рнл яксвюе, еякх хяонкэгсеряъ рюакхжю хг 256 якнб х йюфдюъ гюохяэ онлеыюеряъ б едхмярбеммсч яннрберярбсчысч ее йкчвс онгхжхч, ю гюрел щрю рюакхжю яфхлюеряъ. Ндмюйн щрнр лернд хлек нвебхдмши меднярюрнй, хан нм смхврнфюк гюохяэ, еякх онякедсчыюъ хлекю рнр фе йкчв. Нярюкэмше вершпе опнюмюкхгхпнбюммшу лерндю ашкх сонпъднвемш якедсчыхл напюгнл: опълне дбсуосребне якхъмхе ксвье онпюгпъдмни янпрхпнбйх я нямнбюмхел 2, йнрнпюъ ксвье опнярнцн бшанпю, йнрнпши б ябнч нвепедэ ксвье лерндю осгшпэйю. Щрх пегскэрюрш онксвхкх дюкэмеиьее пюгбхрхе б дхяяепрюжхх Цюпнкэдю X. Яэчбнпдю б 1954~ц. [Information sorting in the application of electronic digital computers to business operations, Digital Computer Lab. report R-232 (Mass. Inst. of Tech.. May 24, 1954), 60 pp.]. Яэчбнпд бшяйюгюк хдех пюяопедекъчыецн ондяверю х бшанпю я гюлеыемхел. Нм онйюгюк, врн оепбши нрпегнй яксвюимни оепеярюмнбйх хлеер япедмчч дкхмс $e-1$, х юмюкхгхпнбюк мюпъдс я бмсрпеммеи янпрхпнбйни х бмеьмчч йюй мю пюгкхвмшу рхоюу люяянбни оюлърх, рюй х мю кемрюу. Еые анкее днярнимюъ бмхлюмхъ дхяяепрюжхъ---мю щрнр пюг днйрнпяйюъ--- ашкю мюохяюмю Цнбюпднл А. Делсрнл б 1956~ц. [Electronic Data Sorting (Stanford University, October, 1956), 92 pp.]. Щрю пюанрю онлнцкю гюкнфхрэ нямнбш ренпхх якнфмнярх бшвхякемхи. Б.меи пюяялюрпхбюкхяэ рпх юаярпюйрмше лндекх гюдювх янпрхпнбйх: я хяонкэгнбюмхел жхйкхвеяйни оюлърх, кхмеимни оюлърх х оюлърх я опнхгбнкэмшл днярсонл; дкъ йюфдни лндекх ашкх пюгпюанрюмш норхлюкэмше хкх онврх норхлюкэмше лерндш. (Яп. я соп. 5.3.4--62.) Унръ меоняпедярбеммн хг дхяяепрюжхх Делсрю ме бшрейюер мхйюйху опюйрхвеяйху якедярбхи, б меи яндепфюряъ бюфмше хдех н рнл, йюй ябъгюрэ ренпхч я опюйрхйни. Рюйхл напюгнл, хярнпхъ янпрхпнбйх ашкю реямн ябъгюмю ян лмнцхлх хяунфеммшлх рпноюлх б бшвхякемхъу: я оепбшлх люьхмюлх дкъ напюанрйх дюммшу, оепбшлх гюонлхмюелшлх опнцпюллюлх, оепбшл опнцпюллмшл наеяоевемхел, оепбшлх лерндюлх астепхгюжхх, оепбни пюанрни он юмюкхгс юкцнпхрлнб х якнфмнярх бшвхякемхи. Мх ндхм хг днйслемрнб нрмняхрекэмн ЩБЛ, сонлъмсршу дн яху онп, ме онъбкъкяъ б "нрйпшрни кхрепюрспе". Рюй сф яксвхкняэ, врн анкэьюъ вюярэ пюммеи хярнпхх бшвхякхрекэмшу люьхм яндепфхряъ б япюбмхрекэмн меднярсомшу днйкюдюу, оняйнкэйс нрмняхрекэмн мелмнцхе кхжю ашкх б рн бпелъ ябъгюмш я ЩБЛ. Мюйнмеж б 1955--1956~цц. кхрепюрспю н янпрхпнбйе опнмхйюер б оевюрэ б бхде рпеу анкэьху нагнпмшу ярюреи. %% 462 Оепбюъ ярюрэъ ашкю ондцнрнбкемю Дф. Й. Уняйемнл [Proc. Eastern Joint. Computer Conference, 8 (1955), 39---55]. Нм мювхмюер я рнмйнцн мюакчдемхъ: "Врнаш ямхгхрэ ярнхлнярэ едхмхжш пегскэрюрю, кчдх нашвмн сйпсомъчр ноепюжхх. Мн опх щрху сякнбхъу ярнхлнярэ едхмхжш янпрхпнбйх ме слемэьюеряъ, ю бнгпюярюер". Уняйем нохяюк бяе нанпсднбюмхе яоежхюкэмнцн мюгмювемхъ, хлебьееяъ б опндюфе, ю рюйфе лерндш янпрхпнбйх мю ЩБЛ. Ецн ахакхнцпютхъ хг 54 осмйрнб нямнбюмю анкэьеи вюярэч мю апньчпюу тхпл-хгцнрнбхрекеи. Ондпнамюъ ярюрэъ Щ. X. Тпщмдю [Sorting on Electronic Computer Systems, {\sl JACM\/}, {\bf 3} (1956), 134--168] ъбхкюяэ бюфмни беуни б пюгбхрхх янпрхпнбйх. Унръ гю опньедьее я 1956 ц. бпелъ ашкх пюгпюанрюмш лмнцнвхякеммше лерндш, щрю ярюрэъ бяе еые менашвмн янбпелеммю бн лмнцху нрмньемхъу. Тпщмд дюк рыюрекэмне нохяюмхе беяэлю анкэьнцн вхякю юкцнпхрлнб бмсрпеммеи х бмеьмеи янпрхпнбйх х напюрхк нянане бмхлюмхе мю лерндш астепхгюжхх х уюпюйрепхярхйх люцмхрмшу кемрнопнръфмшу сярпниярб. Нм ббек мейнрнпше мнбше лерндш (мюопхлеп, бшанп хг депебю, лернд дбсцкюбнцн глхъ х опнцмнгхпнбюмхе) х пюгпюанрюк мейнрнпше люрелюрхвеяйхе ябниярбю ярюпшу лернднб. Рперхи нагнп он янпрхпнбйе, йнрнпши онъбхкяъ б рн бпелъ, ашк ондцнрнбкем Д. С. Дщбюиянл [{\sl Proc. Inst. Elect. Engineers\/}, {\bf 103Б}, supplement 1 (1956), 87--93]. Б онякедсчыхе цндш еые меяйнкэйн бшдючыхуяъ нагнпнб ашкн носакхйнбюмн Д. Ю. Аеккнл [{\sl Янmp. J.\/}, {\bf 1} (1958), 71--77]; Ю. Ь. Дсцкюянл [{\sl Comp. J.\/}, {\bf 2} (1959), 1--9]; Д. Д. Люй-Йпюйемнл, Ц. Беияянл х Ж. Кх [Programming Business Computers (New York: Wiley, 1959), chapter~15, 298--332]; Ю. Ткнпеянл [{\sl JACM\/}, {\bf 8} (1961) 41--80]; Й. Щ. Юибепянмнл [A programming language (New York: Wiley, 1962), chapter 6, 176---245]; Й. Й. Цнркханл [{\sl CACM\/}, {\bf 6} (1963), 194--201]; Р. М. Ухааюпднл [{\sl CACM\/},{\bf 6} (1963), 206--213]; Л. Ю. Цнржел [Digital Computer User's Handbook ed. by M. Klerer and G. A. Korn (New York, McGraw-Hill, 1967), chapter~1.10, 1.292--1.320]. Б мнъапе 1962~ц. ACM нпцюмхгнбюкю яхлонгхсл он янпрхпнбйе (анкэьюъ вюярэ пюанр, опедярюбкеммшу мю щрнл яхлонгхсле, носакхйнбюмю б люе 1963 ц. б бшосяйе {\sl CACM\/}). Нмх дючр унпньее опедярюбкемхе н янярнъмхх щрни накюярх б рн бпелъ. Нагнп Й.~Й.~Цнркхаю н янбпелеммшу цемепюрнпюу янпрхпнбйх, нагнп Р.~М.~Ухааюпдю н бмсрпеммеи янпрхпнбйе я лхмхлюкэмни оюлърэч х пюммее хяякеднбюмхе Дф.~Ю.~Уюаащпдю н янпрхпнбйе тюикнб мю дхяйюу---мюханкее гюяксфхбючыхе бмхлюмхъ ярюрэх б щрнл янапюмхх. Гю опньедьхи оепхнд ашкх нрйпшрш мнбше лерндш янпрхпнбйх: бшвхякемхе юдпеяю~(1956), якхъмхе я бярюбйни~(1959), налеммюъ онпюгпъдмюъ янпрхпнбйю~(1959), йюяйюдмне якхъмхе~(1959), лернд Ьеккю я сашбючыхл ьюцнл~(1959), лмнцнтюгмне %% 463 якхъмхе (1960), бярюбйх б депебн (1960), няжхккхпсчыюъ янпрхпнбйю (1962), ашярпюъ янпрхпнбйю Унюпю (1962), охпюлхдюкэмюъ янпрхпнбйю Схкэъляю (1964), налеммюъ янпрхпнбйю ян якхъмхел Ащрвепю (1964). Хярнпхъ йюфднцн нрдекэмнцн юкцнпхрлю опнякефхбюеряъ б реу пюгдекюу мюярнъыеи цкюбш цде щрнр лернд нохяшбюеряъ. Йнмеж 60-у цнднб мюьецн ярнкерхъ нгмюлемнбюкяъ хмремяхбмшл пюгбхрхел яннрберярбсчыеи ренпхх. Онкмюъ ахакхнцпютхъ бяеу пюанр, хгсвеммшу юбрнпнл опх мюохяюмхх щрни цкюбш, хлееряъ б [{\sl Computing Reviews\/}, {\bf 13} (1972), 283--289]. \excercises \ex[05] Ондбедхре хрнц щрни цкюбе; ятнплскхпсире нанаыемхе ренпелш 5.4.6Ю. \ex[20] Яйюфхре, нямнбшбюъяэ мю рюак.~1, йюйни хг лернднб янпрхпнбйх яохяйнб дкъ ьеярхжхтпнбшу йкчвеи асдер мюхксвьхл дкъ люьхмш \MIX. \ex[47]\exhead(Сярнивхбюъ янпрхпнбйю я лхмхлюкэмни оюлърэч.) Цнбнпър, врн юкцнпхрл янпрхпнбйх рпеасер \emph{лхмхлюкэмни оюлърх}, еякх нм хяонкэгсер дкъ ябнху оепелеммшу рнкэйн $O((\log N)^2)$ ахрнб оюлърх ябепу опнярпюмярбю, рпеаселнцн дкъ пюглеыемхъ $N$ гюохяеи. Юкцнпхрл днкфем ашрэ наыхл б рнл ялшяке, врн днкфем пюанрюрэ опх кчашу $N$, ю ме рнкэйн опх нопедекеммнл гмювемхх $N$, еякх, йнмевмн, опедонкюцюеряъ, врн опх бшгнбе юкцнпхрлю дкъ янпрхпнбйх елс наеяоевхбюеряъ днярюрнвмне йнкхвеярбн оюлърх я опнхгбнкэмшл днярсонл. Бн лмнцху хг хгсвеммшу мюлх юкцнпхрлнб янпрхпнбйх щрн рпеанбюмхе лхмхлюкэмни оюлърх мюпсьюеряъ; б вюярмнярх, гюопеыемн хяонкэгнбюмхе $N$ онкеи ябъгх. Ашярпюъ янпрхпнбйю (юкцнпхрл 5.2.2Q) сднбкербнпъер рпеанбюмхч лхмхлюкэмни оюлърх, мн ее бпелъ пюанрш б мюхусдьел яксвюе опнонпжхнмюкэмн $N^2$. Охпюлхдюкэмюъ янпрхпнбйю (юкцнпхрл 5.2.3М) ъбкъеряъ едхмярбеммшл япедх хгсвеммшу мюлх юкцнпхрлнб рхою $O(N\log N)$, йнрнпши хяонкэгсер лхмхлюкэмсч оюлърэ, унръ лнфмн ятнплскхпнбюрэ х еые ндхм онднамши юкцнпхрл, еякх хяонкэгнбюрэ хдеч хг соп.~5.2.4--18. Яюлшл ашярпшл наыхл юкцнпхрлнл, хгсвеммшл мюлх, йнрнпши \emph{сярнивхбн} янпрхпсер йкчвх, ъбкъеряъ лернд якхъмхъ яохяйнб (юкцнпхрл 5.2.4L), ндмюйн нм хяонкэгсер ме лхмхлюкэмсч оюлърэ. Тюйрхвеяйх едхмярбеммшлх сярнивхбшлх юкцнпхрлюлх янпрхпнбйх я лхмхлюкэмни оюлърэч, йнрнпше лш бхдекх, ашкх лерндш рхою $O(N^2)$ (опнярше бярюбйх, лернд осгшпэйю х бюпхюмрш опнярнцн бшанпю). Ясыеярбсер кх сярнивхбши юкцнпхрл янпрхпнбйх я лхмхлюкэмни оюлърэч, рпеасчыхи лемее $O(N^2)$ едхмхж бпелемх б мюхусдьел яксвюе хкх б япедмел? \epigraph Ъ днярхц ябнеи жекх., еякх. пюяянпрхпнбюк х опхбек б кнцхвеяйхи онпъднй унръ аш ъдпн рнцн нцпнлмнцн люрепхюкю н янпрхпнбйе, йнрнпши онъбхкяъ гю онякедмхе меяйнкэйн кер. \signed Дф. Й. Уняйем (1955) %% 464 \chapter{Онхяй} \epigraph Онхыел гюохяэ \signed {Щк Ялхр (1928)% \note{1}{Ялхр, Юкэтпед Щллюмсщкэ (1873--1944) --- юлепхйюмяйхи онкхрхвеяйхи деърекэ.---{\sl Опхл. оепеб.}} } Щрс цкюбс лнфмн ашкн мюгбюрэ хмюве: хкх оперемжхнгмн---"Упюмемхе х бшанпйю хмтнплюжхх", хкх опнярн---"Онхяй он рюакхжюл". Мюя асдер хмрепеянбюрэ опнжеяя мюйнокемхъ хмтнплюжхх б оюлърх бшвхякхрекэмни люьхмш я онякедсчыхл бнглнфмн анкее ашярпшл хгбкевемхел щрни хмтнплюжхх. Хмнцдю лш ярюкйхбюеляъ ян ярнкэ анкэьхл на╝елнл дюммшу, врн пеюкэмн хяонкэгнбюрэ ху бяе ме лнфел. Б щрнл яксвюе яюлшл лсдпшл ашкн аш гюашрэ х пюгпсьхрэ анкэьсч ху вюярэ; мн мепедйн ашбюер бюфмн янупюмхрэ х рюй нпцюмхгнбюрэ хлечыхеяъ тюйрш, врнаш наеяоевхрэ мюхашярпеиьсч ху бшанпйс. Щрю цкюбю онябъыемю б нямнбмнл хгсвемхч нвемэ опнярни онхяйнбни гюдювх: йюй мюундхрэ дюммше, упюмъыхеяъ я нопедекеммни хдемрхтхйюжхеи. Мюопхлеп, б бшвхякхрекэмни гюдюве мюл лнфер онмюднахрэяъ мюирх $f(x)$, хлеъ $x$ х рюакхжс гмювемхи тсмйжхх $f$; б кхмцбхярхвеяйни лнфер хмрепеянбюрэ юмцкхияйхи щйбхбюкемр дюммнцн псяяйнцн якнбю. Бннаые асдел опедонкюцюрэ, врн упюмхряъ лмнфеярбн хг $N$ гюохяеи х менаундхлн нопедекхрэ онкнфемхе яннрберярбсчыеи гюохях. Йюй х б яксвюе янпрхпнбйх, опедонкнфхл, врн йюфдюъ гюохяэ яндепфхр яоежхюкэмне онке, йнрнпне мюгшбюеряъ \emph{йкчвнл}, бнглнфмн, онрнлс, врн лмнцхе кчдх ефедмебмн рпюрър люяяс бпелемх мю онхяй ябнху йкчвеи. Лш нашвмн рпеасел, врнаш $N$ йкчвеи ашкх пюгкхвмш, рюй врн йюфдши йкчв ндмнгмювмн нопедекъер ябнч гюохяэ. Янбнйсомнярэ бяеу гюохяеи мюгшбюеряъ \dfn{рюакхжеи} хкх \dfn{тюикнл}, опхвел онд рюакхжеи, йюй опюбхкн, ондпюгслебюеряъ %% 465 меанкэьни тюик, ю тюикнл нашвмн мюгшбючр анкэьсч рюакхжс. Анкэьни тюик, хкх цпсоою тюикнб, вюярн мюгшбюеряъ \dfn{аюгни дюммшу}. Б юкцнпхрлюу онхяйю опхясрярбсер рюй мюгшбюелши \dfn{юпцслемр онхяйю $K$}, х гюдювю янярнхр б нршяйюмхх гюохях, хлечыеи $K$ ябнхл йкчвнл. Ясыеярбсчр дбе бнглнфмнярх нйнмвюмхъ онхяйю: кхан онхяй нйюгюкяъ \dfn{сдювмшл}, р. е. онгбнкхк нопедекхрэ онкнфемхе яннрберярбсчыеи гюохях, яндепфюыеи $K$, кхан нм нйюгюкяъ \emph{месдювмшл}, р. е. онйюгюк, врн юпцслемр $K$ ме лнфер ашрэ мюидем мх б ндмни хг гюохяеи. Оняке месдювмнцн онхяйю хмнцдю фекюрекэмн бярюбхрэ б рюакхжс мнбсч гюохяэ, яндепфюысч $K$; юкцнпхрл, йнрнпши декюер щрн, мюгшбюеряъ юкцнпхрлнл "онхяйю я бярюбйни". Мейнрнпше реумхвеяйхе сярпниярбю, хгбеярмше йюй "юяянжхюрхбмюъ оюлърэ", пеьючр опнакелс онхяйю юбрнлюрхвеяйх юмюкнцхвмн рнлс, йюй щрн декюер векнбевеяйхи лнгц; лш фе асдел хгсвюрэ лерндш онхяйю мю нашвмни смхбепяюкэмни бшвхякхрекэмни люьхме. Унръ жекэч онхяйю ъбкъеряъ хмтнплюжхъ, йнрнпюъ яндепфхряъ б гюохях, юяянжххпнбюммни я йкчвнл $K$, б юкцнпхрлюу щрни цкюбш нашвмн хцмнпхпсеряъ бяе, йпнле янаярбеммн йкчвеи. Б яюлнл деке, еякх онкнфемхе $K$ нопедекемн, яннрберярбсчыхе дюммше лнфмн мюирх. Мюопхлеп, еякх $K$ бярперхкяъ б ъвеийе~$|TABLE|+i$, юяянжххпнбюммше дюммше (хкх сйюгюрекэ мю мху) лнцср мюундхрэяъ он юдпеяс $|TABLE|+i+1$, хкх $|DATA|+i$ х р. д. Рюйхл напюгнл, ондпнамнярх, йюяючыхеяъ рнцн, врн мсфмн декюрэ, йнцдю мюидем йкчв $K$, лнфмн яонйнимн носярхрэ. Бн лмнцху опнцпюллюу онхяй рпеасер мюханкэьху бпелеммшу гюрпюр, рюй врн гюлемю окнунцн лерндю онхяйю мю унпньхи вюярн бедер й ясыеярбеммнлс сбекхвемхч яйнпнярх пюанрш. Деиярбхрекэмн, мепедйн сдюеряъ рюй нпцюмхгнбюрэ дюммше хкх ярпсйрспс дюммшу, врн онхяй онкмнярэч хяйкчвюеряъ, р. е. лш бяецдю гмюел гюпюмее, цде мюундхряъ мсфмюъ мюл хмтнплюжхъ. Ябъгюммюъ оюлърэ ъбкъеряъ наыеопхмършл лернднл днярхфемхъ щрнцн; мюопхлеп, б яохяйе я дбслъ ябъгълх мер менаундхлнярх хяйюрэ щкелемр, якедсчыхи гю дюммшл хкх опедьеярбсчыхи елс. Дпсцни яоняна хгаефюрэ онхяйю нрйпшбюеряъ оепед мюлх, еякх опеднярюбкемю ябнандю бшанпю йкчвеи. Ядекюел ху вхякюлх $\{1,2, \ldots, N\}$, х рнцдю гюохяэ, яндепфюыюъ $K$, лнфер ашрэ опнярн онлеыемю б ъвеийс $|TABLE|+K$. Наю щрх яонянаю хяонкэгнбюкхяэ дкъ сярпюмемхъ онхяйю хг юкцнпхрлю рнонкнцхвеяйни янпрхпнбйх, наясфдюбьецняъ б о.~2.2.3. Рел ме лемее бн лмнцху яксвюъу онхяй менаундхл (мюопхлеп, йнцдю на╝ейрюлх рнонкнцхвеяйни янпрхпнбйх ъбкъчряъ яхлбнкхвеяйхе хлемю, ю ме вхякю), рюй врн беяэлю бюфмн хлерэ щттейрхбмше юкцнпхрлш онхяйю. Лерндш онхяйю лнфмн йкюяяхтхжхпнбюрэ меяйнкэйхлх яонянаюлх. Лш лнцкх аш пюгдекхрэ ху мю бмсрпеммхи х бмеьмхи %% 466 онхяй б яннрберярбхх я пюгдекемхел юкцнпхрлнб янпрхпнбйх б цк.~5 мю бмсрпеммчч х бмеьмчч янпрхпнбйс. Хкх лш лнцкх аш пюгкхвюрэ ярюрхвеяйхи х дхмюлхвеяйхи лерндш онхяйю, цде "ярюрхвеяйхи" нгмювюер, врн яндепфхлне рюакхжш нярюеряъ мехглеммшл (рюй врн бюфмн лхмхлхгхпнбюрэ бпелъ онхяйю, опемеапецюъ гюрпюрюлх мю оепеярпнийс рюакхжш), ю "дхмюлхвеяйхи" нгмювюер, врн рюакхжю ъбкъеряъ на╝ейрнл вюяршу бярюбнй (х, лнфер ашрэ, сдюкемхи). Рперэъ бнглнфмюъ яуелю йкюяяхтхжхпсер лерндш онхяйю б яннрберярбхх я рел, нямнбюмш кх нмх мю япюбмемхх йкчвеи хкх мю жхтпнбшу ябниярбюу йкчвеи, юмюкнцхвмн рнлс, йюй пюгкхвючряъ янпрхпнбйю я онлныэч япюбмемхъ х янпрхпнбйю я онлныэч пюяопедекемхъ. Мюйнмеж, лш лнцкх аш пюгдекхрэ лерндш онхяйю мю лерндш, хяонкэгсчыхе хярхммше йкчвх, х мю лерндш, пюанрючыхе я опенапюгнбюммшлх йкчвюлх. Нпцюмхгюжхъ дюммни цкюбш еярэ. б ясымнярх, йнлахмюжхъ дбсу онякедмху яонянанб йкюяяхтхйюжхх. Б \S~6.1 пюяялюрпхбючряъ лерндш онякеднбюрекэмнцн онхяйю "б кна", ю б \S~6.2 наясфдючряъ сксвьемхъ, йнрнпше лнфмн онксвхрэ мю нямнбе япюбмемхи лефдс йкчвюлх я хяонкэгнбюмхел юктюбхрмнцн хкх вхякнбнцн онпъдйю дкъ сопюбкемхъ пеьемхълх. Б \S~6.3 пюяялюрпхбюеряъ жхтпнбни онхяй, ю б \S~6.4 наясфдюеряъ бюфмши йкюяя лернднб, мюгшбюелшу уеьхпнбюмхел х нямнбюммшу мю юпхтлерхвеяйху опенапюгнбюмхъу хярхммшу йкчвеи. Б йюфднл хг щрху оюпюцпютнб пюяялюрпхбюеряъ йюй бмсрпеммхи, рюй х бмеьмхи онхяй, х дкъ ярюрхвеяйнцн х дкъ дхмюлхвеяйнцн яксвюеб; б йюфднл оюпюцпюте нрлевючряъ япюбмхрекэмше днярнхмярбю х меднярюрйх пюгкхвмшу юкцнпхрлнб. Лефдс онхяйнл х янпрхпнбйни ясыеярбсер нопедекеммюъ бгюхлнябъгэ. Мюопхлеп, пюяялнрпхл якедсчысч гюдювс: $$ \displaylines{ \hbox{Дюмш дбю лмнфеярбю вхяек:}\cr \hbox{$A=\{a_1, a_2, \ldots, a_m\}$ х $B=\{b_1, b_2, \ldots, b_n\}$;}\cr \hbox{нопедекхрэ, ъбкъеряъ кх $A$ ондлмнфеярбнл $B$, р.~е. $A\subseteq B$.}\cr } $$ Мюопюьхбючряъ рпх пеьемхъ, ю хлеммн: \enumerate \li Япюбмхбюрэ йюфдне $a_i$ онякеднбюрекэмн ян бяелх $b_j$ дн сярюмнбкемхъ янбоюдемхъ. \li Ябеярх бяе $b_j$ б рюакхжс, гюрел хяйюрэ йюфдне $a_i$ он рюакхже. \li Сонпъднвхрэ $A$ х~$B$, гюрел янбепьхрэ ндхм онякеднбюрекэмши опнунд он нанхл тюикюл, опнбепъъ яннрберярбсчыхе сякнбхъ. \enumend \noindent Йюфдне хг щрху пеьемхи хлеер ябнх опхбкейюрекэмше ярнпнмш дкъ пюгкхвмшу дхюоюгнмнб гмювемхи $m$ х $n$. Дкъ пеьемхъ 1 онрпеасеряъ опхакхгхрекэмн $c_1mn$ едхмхж бпелемх, цде $c_1$---мейнрнпюъ йнмярюмрю, ю пеьемхе 3 гюилер нйнкн $c_2(m \log_2m+n\log_2n)$ едхмхж, цде $c_2$---мейнрнпюъ (а\'нкэьюъ) йнмярюмрю. Опх ондундъыел %% 467 лернде уеьхпнбюмхъ пеьемхе 2 онрпеасер опхлепмн $c_3m+c_4n$ едхмхж бпелемх, цде $c_3$ х~$c_4$---мейнрнпше (еые а\'нкэьхе) йнмярюмрш. Якеднбюрекэмн, пеьемхе 1 унпньн опх нвемэ люкшу $m$ х~$n$, ю опх бнгпюярюмхх $m$ х $n$ ксвьхл асдер пеьемхе 3. Гюрел, онйю $n$ ме днярхцмер пюглепнб бмсрпеммеи оюлърх, анкее опедонврхрекэмн пеьемхе 2; оняке щрнцн нашвмн пеьемхе 3 ямнбю ярюмнбхряъ ксвье, онйю $n$ ме ядекюеряъ еые цнпюгдн анкэьхл. Гмювхр, лш хлеел яхрсюжхч, цде янпрхпнбйю хмнцдю унпньн гюлемъер онхяй, ю онхяй---янпрхпнбйс. Гювюярсч якнфмше гюдювх онхяйю лнфмн ябеярх й анкее опняршл яксвюъл, пюяялюрпхбюелшл гдеяэ. Мюопхлеп, опедонкнфхл, врн б пнкх йкчвеи бшярсоючр якнбю, йнрнпше лнцкх ашрэ якецйю хяйюфемш; лш унрекх аш мюирх опюбхкэмсч гюохяэ, меялнрпъ мю щрс ньхайс. Еякх ядекюрэ дбе йнохх тюикю, б ндмни хг йнрнпшу йкчвх пюяонкнфемш б нашвмнл юктюбхрмнл онпъдйе, ю б дпсцни нмх сонпъднвемш яопюбю мюкебн (йюй еякх аш якнбю ашкх опнвхрюмш мюнанпнр), хяйюфеммши юпцслемр онхяйю б анкэьхмярбе яксвюеб янбоюдюер дн онкнбхмш ябнеи дкхмш хкх дюкэье я гюохяэч ндмнцн хг щрху дбсу тюикнб. Лерндш онхяйю, яндепфюыхеяъ б \S~6.2 х~6.3, лнфмн, якеднбюрекэмн, опхяонянахрэ дкъ мюунфдемхъ йкчвю, йнрнпши ашк, бепнърмн, хяйюфем. Онунфхе гюдювх опхбкейкх й яеае гюлермне бмхлюмхе б ябъгх я янгдюмхел яхярел опедбюпхрекэмнцн гюйюгю юбхюахкернб х б ябъгх я дпсцхлх опхкнфемхълх, йнцдю ясыеярбсер гмювхрекэмюъ бепнърмнярэ хяйюфемхъ хлемх векнбейю хг-гю мепюганпвхбнцн онвепйю хкх окнуни якшьхлнярх. Мсфмн ашкн мюирх опенапюгнбюмхе юпцслемрю б мейхи йнд, янахпючыее блеяре бяе бюпхюмрш дюммнцн хлемх. Лернд "Soundex", нохяшбюелши мхфе б бхде, б йнрнпнл нм опхлемъеряъ яеивюя, ашк оепбнмювюкэмн пюгбхр Люпцюпер Й.~Нсдекк х Пнаепрнл Й.~Пюяяекнл [ял. U.~S.~Patents 1261167 (1918), 1435663 (1922)]; нм мюьек ьхпнйне опхлемемхе дкъ йндхпнбюмхъ тюлхкхи. \enumerate \li Нярюбхрэ оепбсч асйбс; бяе асйбш ю, е, h, i, н, u, w, с, ярнъыхе мю дпсцху леярюу, бшвепймсрэ. \li Нярюбьхляъ асйбюл (йпнле оепбни) опхябнхрэ якедсчыхе гмювемхъ: $$\matrix{ b, f, p, v \to 1; \hfill & l \to 4;\hfill \cr c, g, j, k, q, s, x, z \to 2; & m, n \to 5;\cr d, t \to 3; \hfill & r \to 0.\hfill\cr } $$ \li Еякх б хяундмнл хлемх (оепед ьюцнл 1) пъднл ярнъкх меяйнкэйн асйб я ндхмюйнбшлх йндюлх, опемеапевэ бяелх, йпнле оепбни хг щрни цпсоош. \li Днохяшбюъ б яксвюе мюднамнярх мскх хкх носяйюъ кхьмхе жхтпш, опенапюгнбюрэ онксвеммне бшпюфемхе б тнплс "асйбю, жхтпю, жхтпю, жхтпю". %% 468 \enumend \noindent Мюопхлеп, тюлхкхх Euler, Gauss, Hilbert, Knuth, Lloyd х~{\L}ukasiewicz хлечр йндш яннрберярбеммн Е460, G200, H416, K530, L300, L222. Пюгслееряъ, рюйюъ яхярелю янахпюер блеяре ме рнкэйн пндярбеммше, мн х днярюрнвмн пюгкхвмше хлемю. Опхбедеммше бшье ьеярэ йнднб лнцкх ашрэ онксвемш хг тюлхкхи Ellery, Ghosh, Heilbronn, Kant, Ladd х Lissajous. Я дпсцни ярнпнмш, рюйхе пндярбеммше хлемю, йюй Rogers х Rodgers, Sinclair х St.~Clair хкх Tchebysheff х Chebyshev, хлечр пюгмсч йндхпнбйс. Мн, бннаые цнбнпъ, яхярелю "Soundex" мюлмнцн сбекхвхбюер бепнърмнярэ намюпсфхрэ хлъ онд ндмни хг ецн люянй. [Дкъ дюкэмеиьецн нгмюйнлкемхъ, ял. Я. П. Bourne, D. F. Ford, {\sl JACM\/}, {\bf 8} (1961), 538--552; Leon Davidson, {\sl CACM\/}, {\bf 5} (1962), 169--171; Federal Population Censuses, 1790--1890 (Washington, D. Я.: National Archives, 1971), 90.] Йнцдю лш хяонкэгсел яхярелш рхою "Soundex", мер менаундхлнярх опедонкюцюрэ, врн бяе йкчвх пюгкхвмш; лнфмн янярюбхрэ яохяйх хг гюохяеи я янбоюдючыхлх йндюлх, пюяялюрпхбюъ йюфдши яохянй йюй на╝ейр онхяйю. Опх хяонкэгнбюмхх анкэьху аюг дюммшу бшанпйю хмтнплюжхх мюлмнцн сякнфмъеряъ, рюй йюй вюярн фекюрекэмн пюяялюрпхбюрэ пюгкхвмше онкъ йюфдни гюохях йюй онремжхюкэмше йкчвх. Гдеяэ бюфмн слерэ мюундхрэ гюохях он меонкмни йкчвебни хмтнплюжхх. Мюопхлеп, хлеъ анкэьни тюик юйрепнб, пефхяяеп лнц аш онфекюрэ мюирх бяеу мегюмършу юйрпхя б бнгпюяре 25--30 кер, унпньн рюмжсчыху х цнбнпъыху я тпюмжсгяйхл юйжемрнл; с яонпрхбмнцн фспмюкхярю лнфер бнгмхймсрэ фекюмхе ондявхрюрэ я онлныэч тюикю аеияанкэмни ярюрхярхйх наыее вхякн нвйнб, мюапюммшу ондючыхлх-кебьюлх йнлюмдш "Йпюямнмнцхе хг Жхмжхмюррх" б ревемхе яедэлшу оепхнднб бевепмху хцп гю 1964~ц. Хлеъ анкэьни тюик дюммшу н вел-кхан, кчдх кчаър гюдюбюрэ бнопняш опнхгбнкэмни якнфмнярх. Мю яюлнл деке лш лнцкх аш пюяялюрпхбюрэ онкмсч ахакхнрейс йюй аюгс дюммшу, б йнрнпни мейрн фекюер мюирх бяе осакхйюжхх н бшанпйе хмтнплюжхх. Ббедемхе б лерндш \emph{онхяйю он лмнцхл опхгмюйюл} онлеыемн б \S~6.5. Опефде вел оепеундхрэ й дерюкэмнлс хгсвемхч онхяйю, онкегмн пюяялнрперэ хярнпхч дюммнцн бнопняю. Б днйнлоэчрепмши оепхнд ашкн янярюбкемн лмнфеярбн рнлнб кнцюпхтлхвеяйху, рпхцнмнлерпхвеяйху х дпсцху рюакхж, рюй врн люрелюрхвеяйхе бшвхякемхъ лнцкх ашрэ гюлемемш онхяйнл. Онрнл щрх рюакхжш ашкх оепемеяемш мю оептнйюпрш х хяонкэгнбюкхяэ дкъ мюсвмшу гюдюв оняпедярбнл пюяонгмючыху, янпрхпнбюкэмшу х дсакхпсчыху оептнпюрнпмшу люьхм. Ндмюйн оняке онъбкемхъ ЩБЛ я гюонлхмюелни опнцпюллни ярюкн нвебхдмн, врн деьебке йюфдши пюг бшвхякърэ $\log x$ х~$\cos x$, мефекх хяйюрэ нрбер он рюакхже. Меялнрпъ мю рн, врн гюдювю янпрхпнбйх опхбкейкю опхярюкэмне %% 469 бмхлюмхе сфе мю гюпе пюгбхрхъ ЩБЛ, дкъ пюгпюанрйх юкцнпхрлнб онхяйю ашкн ядекюмн япюбмхрекэмн люкн. Пюяонкюцюъ меанкэьни бмсрпеммеи оюлърэч х рнкэйн онякеднбюрекэмшлх сярпниярбюлх рхою кемр дкъ упюмемхъ анкэьху тюикнб, нпцюмхгнбюрэ онхяй ашкн кхан янбепьеммн рпхбхюкэмн, кхан онврх мебнглнфмн. Мн пюгбхрхе бяе анкэьеи х анкэьеи оюлърх ян яксвюимшл днярсонл б ревемхе 50-у цнднб опхбекн й онмхлюмхч рнцн, врн онхяй йюй рюйнбни ъбкъеряъ хмрепеямни гюдювеи. Оняке оепхндю фюкна мю нцпюмхвеммше пеяспяш опнярпюмярбю б пюммху люьхмюу опнцпюллхярш бдпсц ярнкймскхяэ я рюйхл на╝елнл оюлърх, йнрнпши нмх ме слекх щттейрхбмн хяонкэгнбюрэ. Оепбше нагнпш гюдюв онхяйю ашкх носакхйнбюмш Ю.~Х.~Дслх [{\sl Computers \& Automation\/}, {\bf 5}, 12 (December 1956), 6--9], С.~С.~Оерепянмнл [{\sl IBM J. Research \& Development}, {\bf 1} (1957), 130--146], Щ.~Д.~Асрнл [{\sl Information and Control\/}, {\bf 1} (1958), 159--164], Ю.~Ь.~Дсцкюянл [{\sl Comp. J.\/}, {\bf 2} (1959), 1--9]. Анкее ондпнамши нагнп ядекюм онгдмее Й.~Щ.~Юибепянмнл [A Programming Language (New York: Wiley, (1962)), 133--158] х Б.~Асуункэжел [{\sl IBM Systems J.\/}, {\bf 2} (1963), 86--111]. Б мювюке 60-у цнднб ашкн пюгпюанрюмн меяйнкэйн мнбшу юкцнпхрлнб онхяйю, нямнбюммшу мю хяонкэгнбюмхх дпебнбхдмшу ярпсйрсп; я мхлх лш онгмюйнлхляъ мхфе. Х б мюье бпелъ бедсряъ юйрхбмше хяякеднбюмхъ он опнакелюл онхяйю. %% 470 \subchap{Онякеднбюрекэмши онхяй} "Мювмх я мювюкю х опндбхцюияъ, онйю ме мюидеьэ мсфмши йкчв; рнцдю нярюмнбхяэ". Рюйюъ онякеднбюрекэмюъ опнжедспю ъбкъеряъ нвебхдмшл яонянанл онхяйю; сднамн мювюрэ мюьх пюяялнрпемхъ я мее, рюй йюй мю меи нямнбюмш лмнцхе анкее якнфмше юкцнпхрлш. Меялнрпъ мю ябнч опнярнрс, онякеднбюрекэмши онхяй яндепфхр пъд нвемэ хмрепеямшу хдеи. Ятнплскхпсел юкцнпхрл анкее рнвмн. \alg S.(Онякеднбюрекэмши онхяй.) Хлееряъ рюакхжю гюохяеи $R_1$, $R_2$, \dots, $R_3$, ямюафеммшу яннрберярбеммн йкчвюлх $K_1$, $K_2$, \dots, $K_n$ Юкцнпхрл опедмюгмювем дкъ онхяйю гюохях я дюммшл йкчвнл $K$. Опедонкюцюеряъ, врн $N\ge 1$. \st [Мювюкэмюъ сярюмнбйю.] Сярюмнбхрэ $i \asg 1$. \st [Япюбмемхе.] Еякх $K=K_i$, юкцнпхрл нйюмвхбюеряъ сдювмн. \st [Опндбхфемхе.] Сбекхвхрэ $i$ мю 1. \st [Йнмеж тюикю?] Еякх $i\le N$, рн бепмсрэяъ й ьюцс \stp{2}. Б опнрхбмнл яксвюе юкцнпхрл нйюмвхбюеряъ месдювмн. \algend Гюлерхл, врн с щрнцн юкцнпхрлю лнфер ашрэ дбю пюгмшу хяундю: \emph{сдювмши} (йнцдю мюидемн онкнфемхе мсфмнцн йкчвю) х \picture{Онякеднбюрекэмши онхяй} \emph{месдювмши} (йнцдю, сярюмнбкемн, врн хяйнлнцн юпцслемрю мер б рюакхже). Щрн яопюбедкхбн дкъ анкэьхмярбю юкцнпхрлнб дюммни цкюбш. Пеюкхгюжхъ б бхде опнцпюллш дкъ люьхмш MIX нвебхдмю. \prog S.(Онякеднбюрекэмши онхяй.) Опедонкнфхл, врн $K_i$ упюмхряъ он юдпеяс $|KEY|+i$, ю нярюбьюъяъ вюярэ гюохях $R_i$---он юдпеяс $|INFO|+i$. Опхбндхлюъ мхфе опнцпюллю хяонкэгсер $|rA|\equiv K$, $|rI1|\equiv i-N$. %% 471 \code START & LDA & K & 1 & S1. Мювюкэмюъ сярюмнбйю. & ENT1 & & 1 & $i\asg 1$. 2H & ЯЛПЮ & KEY+N, 1 & Я & S2. Япюбмемхе. & JE & SUCCESS & Я & Бшунд, еякх $K=K_i$. & INC1 & 1 & C-S & S3.Опндбхфемхе. & J1NP & 2Б & C-S & S4. Йнмеж тюикю? FAILURE & EQU & * &1-S & Бшунд, еякх мер б рюакхже. \endcode Он юдпеяс |SUCCESS| пюяонкнфемю йнлюмдю "|LDA INFO+N,1|"; нмю онлеыюер мсфмсч хмтнплюжхч б |rA|. \progend Юмюкхг дюммни опнцпюллш ме опедярюбкъер рпсдю; бхдмн, врн бпелъ пюанрш юкцнпхрлю S гюбхяхр нр дбсу оюпюлерпнб: $$ \eqalign{ C=&\hbox{ (йнкхвеярбн япюбмемхи йкчвеи)};\cr S=&1\ \hbox{опх сдюве х 0 опх месдюве}.\cr }\eqno (1) $$ Опнцпюллю S рпеасер $5C-2S+3$ едхмхж бпелемх. Еякх лш мюькх $K=K_i$, рн $C=i$, $S=1$; гмювхр, онкмне бпелъ пюбмн $(5i+l)u$. Еякх фе онхяй нйюгюкяъ месдювмшл, рн $C=N$, $S=0$, ю пюанрюкю опнцпюллю пнбмн $(5N+3)u$. Еякх бяе йкчвх онярсоючр мю бунд я пюбмни бепнърмнярэч, рн япедмее гмювемхе~$C$ опх сдювмнл онхяйе янярюбкъер $$ {1+2+\cdots+N\over N}={N+1\over 2}; \eqno(2) $$ япедмейбюдпюрхвмне нрйкнмемхе $C$, пюгслееряъ, днбнкэмн анкэьне---опхлепмн $0.289N$ (ял. соп. 1). Опхбедеммши, юкцнпхрл, меянлмеммн, гмюйнл бяел опнцпюллхярюл. Мн люкн йрн гмюер, врн щрнр яоняна пеюкхгюжхх онякеднбюрекэмнцн онхяйю ме бяецдю яюлши ксвьхи! Нвебхдмне хглемемхе сашярпъер пюанрс юкцнпхрлю (еякх рнкэйн гюохяеи ме якхьйнл люкн): \alg Q.(Ашярпши онякеднбюрекэмши онхяй). Б нркхвхе нр юкцнпхрлю S гдеяэ еые опедонкюцюеряъ, врн б йнмже тюикю ярнхр тхйрхбмюъ гюохяэ $R_{N+1}$. \st [Мювюкэмюъ сярюмнбйю.] Сярюмнбхрэ $i\asg 1$ х~$K_{N+1}\asg K$. \st [Япюбмемхе.] Еякх $K=K_i$, рн оепеирх мю \stp{4}. \st [Опндбхфемхе.] Сбекхвхрэ $i$ мю 1 х бепмсрэяъ й ьюцс \stp{2}. \st [Йнмеж тюикю?] Еякх $i\le N$, юкцнпхрл нйюмвхбюеряъ сдювмн; б опнрхбмнл яксвюе---месдювмн $(i=N+1)$. \algend \prog Q.(Ашярпши онякеднбюрекэмши онхяй.) Гмювемхъ пецхярпнб: $|rA| \equiv K$, $|rI1|\equiv i-N$. %%472 \code BEGIN & LDA & Й & 1 & Q1. Мювюкэмюъ сярюмнбйю & STA & KEY+N+1 & 1 & $K_{N+1}\asg K$. & ENT1 & -N & 1 & $i\asg 0$. & INC1 & 1 & C+1-S & Q3. Опндбхфемхе. & ЯЛПЮ & KEY+N, 1& C+l-S & Q2. Япюбмемхе. & JNE & *-2 & C+1-S & Мю Q3, еякх $K_i\ne K$. & J1NP & SUCCESS & 1 & Q4. Йнмеж тюикю? FAILURE & EQU & * & 1-S & Бшунд, еякх мер б рюакхже. \endcode\progend Хяонкэгсъ оюпюлерпш $C$ х~$S$, ббедеммше опх юмюкхге опнцпюллш $S$, лнфмн гюйкчвхрэ, врн бпелъ пюанрш опнцпюллш слемэьхкняэ дн $(4C-4S+10)u$; щрн дюер сксвьемхе опх $C\ge5$ (дкъ сдювмнцн онхяйю) х опх $N\ge 8$ (дкъ месдювмнцн онхяйю). Опх оепеунде нр юкцнпхрлю S й юкцнпхрлс Q хяонкэгнбюм бюфмши сяйнпъчыхи опхмжхо: еякх бн бмсрпеммел жхйке опнцпюллш опнбепъчряъ дбю хкх анкее сякнбхъ, мсфмн онярюпюрэяъ нярюбхрэ рюл рнкэйн ндмн япюбмемхе. Ясыеярбсер яоняна ядекюрэ опнцпюллс Q \emph{еые} ашярпее. \prog Q'.(Ябепуашярпши онякеднбюрекэмши онхяй.) Гмювемхъ пецхярпнб: $|rA|=K$, $|rI1|\equiv i-N$. \code BEGIN &LDA &Й &1 & Q1. Мювюкэмюъ сярюмнбйю. &STA &KEY + N +1 &1 &$K_{N+1}\asg K$. &ENT1 &-1-N &1 &$i\asg -1$. 3H &INC1 &2 &\lfloor(C-S+2)/2\rfloor & Q3. Опндбхфемхе. (Дбнимне.) &ЯЛПЮ &KEY+N, 1 &\lfloor(C-S+2)/2\rfloor & Q2. Япюбмемхе. &JE &4F &\lfloor(C-S+2)/2\rfloor & Мю Q4, еякх $K=K_i$. &ЯЛПЮ &KEY+N+1,1 &\lfloor(C-S+1)/2\rfloor & Q2. Япюбмемхе. (Якедсчыее.) &JNE &3B &\lfloor(C-S+1)/2\rfloor & Мю Q3, еякх $K\ne K_{i+1}$. &INC1 &1 &(C-5)\bmod 2 &Опндбхмсрэ $i$. 4H &J1NP &SUCCESS & 1 & Q4. Йнмеж тюикю? FAILURE &EQU &* &1-S &Бшунд, еякх мер б рюакхже. \endcode \progend Хмярпсйжхх бмсрпеммецн жхйкю бшохяюмш дбюфдш; щрн хяйкчвюер опхлепмн онкнбхмс ноепюрнпнб "$i\asg i+1$". Рюйхл напюгнл, бпелъ бшонкмемхъ опнцпюллш слемэьхкняэ дн $$ 3.5C-3.5S+10{(C-S)\bmod 2\over 2} $$ едхмхж. Опх онхяйе он анкэьхл рюакхжюл опнцпюллю Q' мю 30\% ашярпее опнцпюллш S; онднамшл напюгнл лнцср ашрэ сксвьемш лмнцхе ясыеярбсчыхе опнцпюллш. Еякх хгбеярмн, врн йкчвх пюяонкнфемш б бнгпюярючыел онпъдйе, онкегмн меяйнкэйн хглемхрэ юкцнпхрл. %% 473 \alg Р.(Онякеднбюрекэмши онхяй б сонпъднвеммни рюакхже.) Хлееряъ рюакхжю гюохяеи $R_1$, $R_2$, \dots, $R_N$, опхвел йкчвх сднбкербнпъчр мепюбемярбюл $K_1K$. \st [Мювюкэмюъ сярюмнбйю.] Сярюмнбхрэ $i\asg1$. \st [Япюбмемхе.] Еякх $K\le K_i$, рн оепеирх мю \stp{4}. \st [Опндбхфемхе.] Сбекхвхрэ $i$ мю 1 х бепмсрэяъ й ьюцс \stp{2}. \st [Пюбемярбн?] Еякх $K=K_i$, рн юкцнпхрл нйюмвхбюеряъ сдювмн. Б опнрхбмнл яксвюе---месдювмн, мсфмни гюохях б рюакхже мер. \algend Еякх бекхвхмю $K$ я пюбмни бепнърмнярэч опхмхлюер бяе бнглнфмше гмювемхъ, рн б яксвюе сдювмнцн онхяйю юкцнпхрл T, он ясыеярбс, ме ксвье юкцнпхрлю Q. Ндмюйн нрясрярбхе мсфмни гюохях юкцнпхрл Р днгбнкъер намюпсфхрэ опхлепмн б дбю пюгю ашярпее. Опхбедеммше бшье юкцнпхрлш б жекъу сднаярбю хяонкэгнбюкх хмдейямше нангмювемхъ дкъ щкелемрнб рюакхжш; юмюкнцхвмше опнжедспш опхлемхлш х й рюакхжюл б ябъгюммнл опедярюбкемхх, рюй йюй б мху дюммше рнфе пюяонкнфемш онякеднбюрекэмн. (Ял. соп.~2, 3 х 4.) \section Вюярнрю напюыемхи. Дн яху онп опедонкюцюкняэ, врн я пюбмни бепнърмнярэч лнфер онрпеанбюрэяъ онхяй кчанцн юпцслемрю, ндмюйн вюярн рюйне опедонкнфемхе ме опюбнлепмн; бннаые цнбнпъ, йкчв $K_j$ асдер пюгшяйхбюрэяъ я бепнърмнярэч $p_i$, цде $p_1+p_2+\cdots+p_N=1$. Бпелъ сдювмнцн онхяйю опх анкэьху $N$ опнонпжхнмюкэмн вхякс япюбмемхи $C$, япедмее .гмювемхе йнрнпнцн пюбмн $$ \overline{C}_N=p_1+2p_2+\cdots+Np_N. \eqno(3) $$ Осярэ еярэ бнглнфмнярэ онлеыюрэ гюохях б рюакхжс б кчанл онпъдйе; рнцдю бекхвхмю $\overline{C}_N$ лхмхлюкэмю опх $$ p_1\ge p_2\ge \ldots \ge p_N, \eqno (4) $$ р. е. йнцдю мюханкее вюярн хяонкэгселше гюохях пюяонкнфемш б мювюке рюакхжш. Онялнрпхл, врн дюер мюл рюйне "норхлюкэмне" пюяонкнфемхе опх пюгкхвмшу пюяопедекемхъу бепнърмняреи. Еякх $p_1=p_2=\ldots=p_N=1/N$, рн тнплскю (3) ябндхряъ й $\overline{C}_N=(N+1)/2$, врн сфе ашкн онксвемн мюлх б (2). Опедонкнфхл реоепэ, врн $$ p_1={1\over2}, p_2={1\over 4}, \ldots, p_{N-1}={1\over2^{N-1}}, p_{N}={1\over2^{N-1}} \eqno(5) $$ %% 474 Янцкюямн соп. 7, $\overline{C}_N=2-2^{1-N}$; япедмее вхякн япюбмемхи лемэье дбсу, еякх гюохях пюяонкнфемш б мюдкефюыел онпъдйе. Дпсцхл мюопюьхбючыхляъ пюяопедекемхел ъбкъеряъ $$ p_1=N_c, p_2=(N-1)c, \ldots, p_N=c, $$ цде $$ c=2/N(N+1). \eqno(6) $$ Щрн "йкхмнбхдмне" пюяопедекемхе дюер анкее опхбшвмши пегскэрюр $$ \overline{C}_N=c\sum_{1\le k\le N} k\cdot(N+1-k)={N+2\over 2}; \eqno(7) $$ норхлюкэмне пюяонкнфемхе щйнмнлхр нйнкн рперх онхяйнбнцн бпелемх, рпеасчыецняъ дкъ гюохяеи б яксвюимнл онпъдйе. Пюгслееряъ, пюяопедекемхъ (5) х~(6) днбнкэмн хяйсяярбеммш, х ху мекэгъ явхрюрэ унпньхл опхакхфемхел й деиярбхрекэмнярх. Анкее рхохвмсч йюпрхмс дюер "гюйнм Гхотю": $$ p_1=c/1, p_2=c/2, \ldots, p_N=c/N, \rem{цде $c=1/H_N$}. \eqno (8) $$ Щрн пюяопедекемхе онксвхкн хгбеярмнярэ акюцндюпъ Дф.~Й~Гхотс, йнрнпши гюлерхк, врн $n$-е мюханкее сонрпеахрекэмне б рейяре мю еяреярбеммнл ъгшйе якнбн бярпевюеряъ я вюярнрни, опхакхгхрекэмн напюрмн опнонпжхнмюкэмни $n$. [The Psicho-Biology of Language (Boston, Mass.: Houghton Miffling, 1935); Human Behavior and the Principle of Least Effort (Reading, Mass.: Addison-Wesley, 1949).] Юмюкнцхвмне ъбкемхе намюпсфемн хл б рюакхжюу оепеохях; рюл ярнкхвмше пюинмш пюяонкнфемш б онпъдйе сашбюмхъ мюяекемхъ. Б яксвюе, еякх вюярнрю йкчвеи б рюакхже ондвхмъеряъ гюйнмс Гхотю, хлеел $$ \overline{C}_N=N/H_N; \eqno(9) $$ онхяй он рюйнлс тюикс опхлепмн б ${1\over2}\ln N$ пюг ашярпее, вел он месонпъднвеммнлс. [Яп. я A.~D.~Booth et al. Mechanical Resolution of Linguistic Problems (New York: Academic Press, 1958), 79.) Дпсцне пюяопедекемхе, акхгйне й пеюкэмнлс, дюер опюбхкн "80--20", йнрнпне вюярн бярпевюеряъ б йнллепвеяйху опхкнфемхъу [яп. я W. P. Heising, {\sl IBM Systems J.\/}, {\bf 2} (1963), 114--115]. Щрн опюбхкн цкюяхр, врн 80\% пюанрш бедеряъ мюд мюханкее юйрхбмни вюярэч тюикю бекхвхмни 20\%; нмн опхлемхлн х й щрхл 20\%, рюй врн 64\% пюанрш бедеряъ я мюханкее юйрхбмшлх 4\% тюикю, х р. д. Хмшлх якнбюлх, $$ {p_1+p_2+\cdots+p_{.20n}\over p_1+p_2+p_3+\cdots+p_n} \approx 0.80 \rem{дкъ бяеу $n$}. \eqno (10) $$ %% 475 Бнр ндмн хг пюяопедекемхи, рнвмн сднбкербнпъчыху опхбедеммнлс опюбхкс опх $n$, йпюрмшу 5: $$ p_1=c, p_2=(2^\theta-1)c, p_3=(3^\theta-2^\theta)c, \ldots, p_N=(N^\theta-(N-1)^\theta)c, \eqno(11) $$ цде $$ c=1/N^\theta; \theta={\log 0.80 \over \log 0.20}=0.1386. \eqno(12) $$ Деиярбхрекэмн, $p_1+p_2+\cdots+p_n=cn^\theta$ опх кчанл $n$. Я бепнърмнярълх (11) ме рюй опнярн пюанрюрэ; хлеел, ндмюйн, $n^\theta-(n-1)^\theta)=\theta n^{\theta-1}(1 + O(1/n))$, р.е. ясыеярбсер анкее опнярне пюяопедекемхе, опхакхфеммн сднбкербнпъчыее опюбхкс "80--20": $$ p_1=c/1^{1-\theta}, p_2=c/2^{1-\theta}, \ldots, p_N=c/N^{1-\theta}, \rem{цде $c=1/H_N^{1-\theta}$}. \eqno (13) $$ Гдеяэ, йюй х пюмэье, $\theta= \log 0.80/\log 0.20$, a $H_N^{(s)}$ еярэ $N$-e цюплнмхвеяйне вхякн онпъдйю $s$, р. е. $1^{-s}+2^{-s}+\cdots+N^{-s}$. Гюлерхл, врн щрн пюяопедекемхе нвемэ мюонлхмюер пюяопедекемхе Гхотю (8); йнцдю $\theta$ хглемъеряъ нр 1 дн 0, бепнърмнярх лемъчряъ нр пюбмнлепмн пюяопедекеммшу й гхотнбяйхл. (Б яюлнл деке, Гхот мюьек, врн $\theta\approx {1\over 2}$ б пюяопедекемхх кхвмшу днунднб.) Опхлемъъ (3) й (13), онксвюел дкъ опюбхкю "80--20" япедмее вхякн япюбмемхи $$ \overline{C}_N=H_N^{(-\theta)}/H_N^{(1-\theta)} ={\theta N \over \theta+1}+O(N^{(1-\theta)})\approx 0.122N \eqno (14) $$ (ял. соп. 8). Ч. Я. Ьбюпж, хгсвюбьхи вюярнрш онъбкемхъ якнб [ял. хмрепеямши цпютхй мю ярп. 422 б {\sl JACM\/}, {\bf 10} (1963)], опедкнфхк анкее ондундъыее бшпюфемхе дкъ'гюйнмю Гхотю: $$ p_1=c/1^{1+\theta}, p_2=c/2^{1+\theta}, \ldots, p_N=c/N^{1+\theta}, \rem{цде $c=1/H_N^{1+\theta}$}, \eqno (15) $$ опх люкшу \emph{онкнфхрекэмшу} $Q$. [Он япюбмемхч я (13) гдеяэ хглемем гмюй $\theta$.] Б щрнл яксвюе $$ \overline{C}_N=H_N^\theta/H_N^{(1+\theta)} =N^{1-\theta}/(1-\theta)\zeta(1+\theta)+O(N^{1-2\theta}), \eqno (16) $$ врн гмювхрекэмн лемэье, вел (9) опх $N\to\infty$. \section "Яюлннпцюмхгсчыхияъ" тюик. Опедшдсыхе бшвхякемхъ унпньх, мн б анкэьхмярбе яксвюеб пюяопедекемхе бепнърмняреи мюл ме хгбеярмн. Лш лнцкх аш б йюфдни гюохях гюбеярх явервхй вхякю напюыемхи, врнаш мю нямнбюмхх онйюгюмхи явервхйнб оепесонпъднвхрэ гюохях. Бшбедеммше тнплскш онйюгшбючр, врн рюйюъ опнжедспю лнфер опхбеярх й гюлермни щйнмнлхх. Мн ме бяецдю %% 476 фекюрекэмн нрбндхрэ лмнцн оюлърх онд явервхйх, рюй йюй ее лнфмн хяонкэгнбюрэ анкее пюжхнмюкэмн (мюопхлеп, опхлемъъ дпсцхе лерндш онхяйю, хгкюцюелше мхфе б дюммни цкюбе). Опнярюъ яуелю, опнхяунфдемхе йнрнпни ме хгбеярмн, хяонкэгсеряъ сфе лмнцхе цндш. Нмю онгбнкъер днбнкэмн унпньн сонпъднвхрэ гюохях аег бяонлнцюрекэмшу онкеи дкъ явервхйнб: йнцдю лш мюундхл мсфмсч гюохяэ, лш онлеыюел ее б мювюкн рюакхжш. Онднамши лернд кецйн пеюкхгнбюрэ, йнцдю рюакхжю опедярюбкемю б бхде ябъгюммнцн кхмеимнцн яохяйю: бедэ вюярн мюл ашбюер мсфмн гмювхрекэмн хглемхрэ мюидеммсч гюохяэ. Хдеъ "яюлннпцюмхгсчыецняъ" лерндю янярнхр б рнл, врн вюярн хяонкэгселше щкелемрш асдср пюяонкнфемш днбнкэмн акхгйн й мювюкс рюакхжш. Осярэ $N$ йкчвеи пюгшяйхбючряъ я бепнърмнярълх $\{p_1, p_2, \ldots, p_N\}$ яннрберярбеммн, опхвел йюфдши онхяй янбепьюеряъ юаянкчрмн \emph{мегюбхяхлн} нр опедшдсыху. Лнфмн онйюгюрэ, врн япедмее вхякн япюбмемхи опх мюунфдемхх гюохях б рюйнл яюлннпцюмхгсчыеляъ тюике ярпелхряъ й опедекэмнлс гмювемхч $$ \overline{C}_N=1+2\sum_{1\le i < j \le N}{p_ip_j\over p_i+p_j} ={1\over 2}+\sum_{i, j}{p_ip_j\over p_i+p_j}. \eqno (17) $$ (Ял. соп. 11.) Мюопхлеп, еякх $p_i=1/N$ опх $1\le i \le N$, яюлннпцюмхгсчыюъяъ рюакхжю бяецдю мюундхряъ б яксвюимнл онпъдйе, ю (17) ябндхряъ й гмюйнлнлс бшпюфемхч $(N+1)/2$, онксвеммнлс пюмее. Онялнрпхл, йюй яюлннпцюмхгсчыюъяъ опнжедспю пюанрюер опх пюяопедекемхх бепнърмняреи он гюйнмс Гхотю (8). Хлеел $$ \eqalign{ \overline{C}_N&={1\over 2}+\sum_{1\le i, j\le N}{(c/i)(c/j)\over c/i+c/j} ={1\over2}+c\sum_{1\le i, j\le N}{1\over i+j}=\cr &={1\over2}+c\sum_{1\le i\le N}(H_{N+i}-H_i) ={1\over2}+c\sum_{1\le i\le 2N}H_i-2c\sum_{1\le i\le N}H_i=\cr &={1\over2}+c((2N+1)H_{2N}-2N-2(N+1)H_N+2N)=\cr &={1\over2}+c(N\ln 4-\ln N+O(1))\approx\cr &\approx 2N/log_2N.\cr } $$ (ял. тнплскш (1.2.7--8,3)). Щрн цнпюгдн ксвье, вел с $N$ опх днярюрнвмн анкэьху $N$, х кхьэ б $\ln4\approx 1.386$ пюг усфе, вел вхякн япюбмемхи опх норхлюкэмнл пюяонкнфемхх гюохяеи (яп. я (9)). Щйяоепхлемрш, опхбндхбьхеяъ я рюакхжюлх яхлбнкнб б йнлохкърнпюу, онйюгюкх, врн яюлннпцюмхгсчыхияъ лернд пюанрюер дюфе ксвье, вел опедяйюгшбюер (18), рюй йюй сдювмше онхяйх %% 477 ме мегюбхяхлш (меанкэьхе цпсоош йкчвеи вюярн онъбкъчряъ блеяре). Яуелс, онднамсч яюлннпцюмхгсчыеияъ, хгсвхкх Ц. Ьюи х Т.~Б.~Дюсщп [{\sl SIAM J. Appl. Math.\/}, {\bf 15} (1967), 874--888.] \section Онхяй мю кемре япедх гюохяеи пюгкхвмни дкхмш. Пюяялнрпхл реоепэ мюьс гюдювс б хмнл пюйспяе. Осярэ рюакхжю, он йнрнпни опнхгбндхряъ онхяй, упюмхряъ мю кемре х гюохях хлечр пюгкхвмше дкхмш. Кемрю я яхярелмни ахакхнрейни б ярюпшу ноепюжхнммшу яхярелюу яксфхр опхлепнл рюйнцн тюикю. Ярюмдюпрмше опнцпюллш яхярелш, рюйхе, йюй йнлохкърнпш, йнлонмнбыхйх, гюцпсгвхйх, цемепюрнпш нрвернб х р. о., ъбкъкхяэ "гюохяълх" мю кемре, ю анкэьхмярбн онкэгнбюрекэяйху пюанр днкфмн ашкн мювхмюрэяъ я онхяйю мсфмни опнцпюллш. Рюйюъ онярюмнбйю гюдювх декюер меопхлемхлшл опедшдсыхи юмюкхг юкцнпхрлю S: реоепэ ьюц S3 бшонкмъеряъ гю пюгкхвмше опнлефсрйх бпелемх. Гмювхр, мюя асдер хмрепеянбюрэ ме рнкэйн вхякн япюбмемхи. Нангмювхл вепег $L_i$ дкхмс гюохях $R_i$, ю вепег $p_i$, бепнърмнярэ рнцн, врн щрю гюохяэ асдер нршяйхбюрэяъ. Бпелъ онхяйю реоепэ опхлепмн опнонпжхнмюкэмн бекхвхме $$ p_1L_1+p_2(L_1+L_2)+\cdots+p_N(L_1+L_2+\cdots+L_N). \eqno (19) $$ Опх $L_1=L_2=\ldots=L_N=1$ щрн, нвебхдмн, ябндхряъ й хгсвеммнлс яксвюч (3). Йюферяъ кнцхвмшл онлеярхрэ мюханкее мсфмше гюохях б мювюкн кемрш, мн гдеяэ гдпюбши ялшяк ондбндхр мюя. Деиярбхрекэмн, осярэ мю кемре гюохяюмш пнбмн дбе опнцпюллш---$A$ х $B$. Опнцпюллю $A$ рпеасеряъ б дбю пюгю вюые $B$, мн дкхммее $B$ б вершпе пюгю, р. е. $N=2$, $p_A={2\over3}$, $L_A=4$, $p_B={1\over3}$, $L_B=1$. Еякх лш, якедсъ "кнцхйе", онярюбхл $A$ мю оепбне леярн, рн япедмее бпелъ онхяйю янярюбхр ${2\over 3}\cdot4+{1\over3}\cdot 5={13\over3}$; мн еякх онярсохрэ "мекнцхвмн", пюяонкнфхб б мювюке $B$, рн онксвхряъ ${1\over3}\cdot1+{2\over3}\cdot5={11\over 3}$. Якедсчыюъ ренпелю онгбнкъер нопедекхрэ норхлюкэмне пюяонкнфемхе ахакхнревмшу опнцпюлл мю кемре. \proclaim Ренпелю S. Осярэ $L_i$ х $p_i$, нопедекемш, йюй х пюмэье. Онпъднй гюохяеи мю кемре норхлюкем рнцдю х рнкэйн рнцдю, йнцдю $$ p_1/L_1\ge p_2/L_2\ge \ldots \ge p_N/L_N. \eqno (20) $$ Хмшлх якнбюлх, лхмхлсл бшпюфемхъ $$ p_{a_1}L_{a_1}+p_{a_2}(L_{a_1}+L_{a_2})+\cdots +p_{a_N}(L_{a_1}+\cdots+L_{a_N}) $$ %% 478 он бяел оепеярюмнбйюл $a_1$ $a-2$ \dots $a_N$ вхяек $\{1,2,\ldots, N\}$ пюбем (19) рнцдю х рнкэйн рнцдю, йнцдю бшонкмъеряъ (20). \proof Опедонкнфхл, врн $R_i$ х $R_{i+1}$ онлемъкхяэ леярюлх; бекхвхмю (19), пюмее пюбмюъ $$ \cdots+p_i(L_1+\cdots+L_{i-1}+L_i)+p_{i+1}(L_1+\cdots+L_{i+1}) +\cdots, $$ реоепэ гюлемхряъ мю $$ \cdots+p_{i+1}(L_1+\cdots+L_{i-1}+L_{i+1})+p_i(L_1+\cdots+L_{i+1}) +\cdots. $$ Хглемемхе пюбмн $p_iL_{i+1}-p_{i+1}L_i$. Рюй йюй пюяонкнфемхе (19) норхлюкэмн, рн $p_iL_{i+1}-p_{i+1}L_i\ge 0$. Гмювхр, $p_i/L_i\ge p_{i+1}/L_{i+1}$, р. е. (20) бшонкмъеряъ. Днйюфел реоепэ днярюрнвмнярэ сякнбхъ (20). Пюгслееряъ, "кнйюкэмюъ" норхлюкэмнярэ пюяонкнфемхъ (19) бхдмю япюгс: еякх лш онлемъел леярюлх дбе гюохях, бпелъ онхяйю хглемхряъ мю $p_iL_{i+1}-p_{i+1}L_i\ge 0$. Ндмюйн "цкнаюкэмюъ" норхлюкэмнярэ рпеасер нанямнбюмхъ. Лш пюяялнрпхл дбю днйюгюрекэярбю: ндмн хг мху хяонкэгсер дхяйпермсч люрелюрхйс, ю дпсцне опедонкюцюер мейнрнпсч люрелюрхвеяйсч хгбнпнркхбнярэ. \proof\ 1. Осярэ (20) бшонкмъеряъ. Лш гмюел, врн кчасч оепеярюмнбйс гюохяеи лнфмн "нрянпрхпнбюрэ", р. е. опхбеярх й пюяонкнфемхч $R_1$, $R_2$, \dots, $R_N$, онякеднбюрекэмн лемъъ леярюлх кхьэ яняедмхе щкелемрш. Йюфдне рюйне хглемемхе оепебндхр \dots$R_j$ $R_i$\dots б \dots$R_i$ $R_j$\dots дкъ мейнрнпшу $i0$ х~$y0$; $N=2k+m+1$. Онйюфхре, врн дпсцне пюяонкнфемхе $q'_1$ $q'_2$~\dots $q'_k$ $s$ $r'_k$~\dots $r'_2$ $r'_1$ $t_1$~\dots $t_m$ ксвье, еякх $q'_i=\min(q_i, r_i)$ х~$r'_i=\max(q_i, r_i)$ (хяйкчвюъ яксвюи $q'_i=q_i$ х~$r'_i=r_i$ дкъ бяеу~$i$ х яксвюи $q'_i=r_i$, $r'_i=q_i$, $t_j=0$ дкъ бяеу~$i$ х~$j$). Србепфдемхе бепмн х опх нрясрярбхх $s$, йнцдю $N=2k+m$.] \ex[Л20] (Опнднкфемхе соп.~18.) Осярэ тсмйжхъ~$d(i,j)$ накюдюер ябниярбнл $d(i,j)+d(j,i)=c$ дкъ бяеу~$i$ х~$j$. Мюидхре норхлюкэмне пюяонкнфемхе дкъ яжеокеммшу онхяйнб. [Рюйюъ яхрсюжхъ бярпевюеряъ опх онхяйе мю кемрюу, йнцдю ме опедсялнрпемю бнглнфмнярэ вхрюрэ б напюрмнл мюопюбкемхх х лш ме гмюел мсфмнцн мюопюбкемхъ онхяйю; опх $i