\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