\input style MESTAH, GDE NA KARTE OTPERFORIROVANY OTVERSTIYA, VHODYAT V KONTAKT S RTUTXYU NA NIZHNEJ PANELI. v REZULXTATE ZAMYKANIYA SOOTVETSTVUYUSHCHEJ CEPI POKAZANIE SVYAZANNOGO S NEJ CIFERBLATA IZMENYAETSYA NA 1 I, KROME TOGO, ODNA IZ 26 KRYSHEK SORTIROVALXNOGO YASHCHIKA OTKRYVAETSYA. v |TOT MOMENT OPERATOR OTPUSKAET PRESS, KLADET KARTU V OTKRYTOE OTDELENIE I ZAKRYVAET KRYSHKU. pO SOOBSHCHENIYAM, KAK-TO CHEREZ |TU MASHINU PROPUSTILI 19071 KARTU ZA ODIN 6.5-CHASOVOJ RABOCHIJ DENX; V SREDNEM PRIMERNO 49 KART V MINUTU! (sREDNIJ OPERATOR RABOTAL PRIMERNO VTROE MEDLENNEJ.) nASELENIE PRODOLZHALO NEUKLONNO RASTI, I PERVYE TABULYATORY-SORTIROVSHCHIKI OKAZALISX NEDOSTATOCHNO BYSTRYMI, CHTOBY SPRAVITXSYA S OBRABOTKOJ PEREPISI 1900~G., PO|TOMU hOLLERIT IZOBREL ESHCHE ODNU MASHINU, CHTOBY PREDOTVRATITX ESHCHE ODIN KRIZIS V OBRABOTKE DANNYH. eGO NOVOE USTROJSTVO (ZAPATENTOVANNOE V 1901 I 1904 GG.) IMELO AVTOMATICHESKUYU PODACHU KART I VYGLYADELO, V SUSHCHNOSTI, POCHTI TAK ZHE, KAK SOVREMENNYE KARTOCHNYE SORTIROVALXNYE MASHINY. iSTORIYA RANNIH MASHIN hOLLERITA S INTERESNYMI PODROBNOSTYAMI IZLOZHENA lEONOM e. tRUSDELLOM V The Development of Punch Card Tabulation (Washington: U. S. Bureau of the Census, 1965); SM. TAKZHE SOOBSHCHENIYA SOVREMENNIKOV hOLLERITA: {\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). hOLLERIT I DRUGOJ BYVSHIJ SLUZHASHCHIJ bYURO PEREPISI dZHEJMS pAU|RS V DALXNEJSHEM OSNOVALI KONKURIRUYUSHCHIE KOMPANII, KOTORYE V KONCE KONCOV VOSHLI SOOTVETSTVENNO V KORPORACII IBM I Remington Rand. sORTIROVALXNAYA MASHINA hOLLERITA---|TO, KONECHNO, OSNOVA METODOV PORAZRYADNOJ SORTIROVKI, ISPOLXZUEMYH V CIFROVYH evm. v EGO PATENTE UPOMINAETSYA, CHTO CHISLOVYE |LEMENTY, SODERZHASHCHIE DVA STOLBCA, DOLZHNY SORTIROVATXSYA "PO OTDELXNOSTI DLYA KAZHDOGO STOLBCA", NO ON NE GOVORIT, KAKOJ STOLBEC (EDINIC ILI DESYATKOV) DOLZHEN RASSMATRIVATXSYA PERVYM. dALEKO NE OCHEVIDNAYA IDEYA SORTIROVKI SNACHALA PO STOLBCU EDINIC BYLA, PO-VIDIMOMU, OTKRYTA KAKIM-TO NEIZVESTNYM OPERATOROM I PEREDANA OSTALXNYM (SM. P.~5.2.5); ONA IMEETSYA V SAMOM RANNEM SOHRANIVSHEMSYA RUKOVODSTVE IBM PO SORTIROVKE (1936~G.). pERVYM IZVESTNYM UPOMINANIEM |TOGO METODA "SPRAVA NALEVO" YAVLYAETSYA SLUCHAJNOE ZAMECHANIE, VSTRETIVSHEESYA V STATXE l. dZH. kOMRI, {\sl Trans. of the Office Machinery Users' Assoc\/}. (London, 1930), 25--37. nECHAYANNO kOMRI OKAZALSYA PERVYM, KTO SDELAL VAZHNOE NABLYUDENIE, CHTO %% 458 TABULYATORY MOZHNO PLODOTVORNO PRIMENYATX V NAUCHNYH VYCHISLENIYAH, HOTYA PERVONACHALXNO ONI SOZDAVALISX DLYA STATISTICHESKIH I BUHGALTERSKIH PRILOZHENIJ. eGO STATXYA OSOBENNO INTERESNA, POSKOLXKU, SODERZHIT PODROBNOE OPISANIE TABULYATOROV, IMEVSHIHSYA V aNGLII V 1930~G. sORTIROVALXNYE MASHINY V TO VREMYA OBRABATYVALI OT~360 DO~400 KART V MINUTU I SDAVALISX V ARENDU ZA 9 FUNTOV STERLINGOV V MESYAC. iDEYA SLIYANIYA VOSHODIT K DRUGOMU USTROJSTVU DLYA OBRABOTKI KART---\emph{PODBOROCHNOJ MASHINE}, KOTORAYA BYLA IZOBRETENA ZNACHITELXNO POZDNEE (V 1938~G.). sNABZHENNAYA DVUMYA PODAYUSHCHIMI MEHANIZMAMI, ONA MOGLA SLITX DVE OTSORTIROVANNYE KOLODY KART V ODNU VSEGO ZA ODIN PROHOD; METOD VYPOLNENIYA |TOGO SLIYANIYA HOROSHO OPISAN V PERVOM RUKOVODSTVE IBM PO METODAM PODBORKI (APRELX 1939~G.). [sR. S James W. Bryce. U.~S. Patent 2189024 (1940).] zATEM NA SCENE POYAVILISX evm I RAZRABOTKA METODOV SORTIROVKI TESNO PEREPLELASX S IH RAZVITIEM. nA SAMOM DELE IMEYUTSYA SVIDETELXSTVA TOGO, CHTO PROGRAMMA SORTIROVKI BYLA PERVOJ KOGDA-LIBO NAPISANNOJ DLYA VYCHISLITELXNYH MASHIN S ZAPOMINAEMOJ PROGRAMMOJ. kONSTRUKTORY VYCHISLITELXNOJ MASHINY EDVAC OSOBENNO INTERESOVALISX SORTIROVKOJ, POSKOLXKU ONA VYSTUPALA KAK NAIBOLEE HARAKTERNYJ PREDSTAVITELX POTENCIALXNYH NECHISLENNYH PRILOZHENIJ evm. oNI PONIMALI, CHTO UDOVLETVORITELXNAYA SISTEMA KOMAND DOLZHNA GODITXSYA NE TOLXKO DLYA SOSTAVLENIYA PROGRAMMY RESHENIYA RAZNOSTNYH URAVNENIJ; V NEJ DOLZHNA BYTX DOSTATOCHNAYA GIBKOSTX, CHTOBY SPRAVITXSYA S KOMBINATORNYMI ASPEKTAMI "VYBORA RESHENIJ" V ALGORITMAH. pO|TOMU dZHON FON nEJMAN PODGOTOVIL V 1945 G. PROGRAMMY DLYA VNUTRENNEJ SORTIROVKI SLIYANIEM, CHTOBY UBEDITXSYA V NEOBHODIMOSTI NEKOTORYH KODOV KOMAND, KOTORYE ON PREDLAGAL DLYA MASHINY EDVAC; SUSHCHESTVOVALI |FFEKTIVNYE SORTIROVALXNYE MASHINY SPECIALXNOGO NAZNACHENIYA, I ONI SLUZHILI TEM ESTESTVENNYM STANDARTOM, V SOPOSTAVLENII S KOTORYM MOZHNO BYLO OCENITX DOSTOINSTVA PREDLAGAEMOJ ORGANIZACII VYCHISLITELXNOJ MASHINY. pODROBNO |TO INTERESNOE ISSLEDOVANIE OPISANO V STATXE d.~e.~kNUTA [{\sl Computing Surveys\/}, {\bf 2} (1970), 247--260]; PERVUYU PROGRAMMU SORTIROVKI FON nEJMANA V OKONCHATELXNOM, "OTPOLIROVANNOM" VIDE SM. V EGO Collected Works, {\bf 5} (New York, Macmillan, 1963), 196--214. iZ-ZA OGRANICHENNOGO OB®EMA PAMYATI V RANNIH MASHINAH PRIHODILOSX DUMATX O VNESHNEJ SORTIROVKE NARAVNE S VNUTRENNEJ, I V DOKLADE "Progress Report on the EDVAC", PODGOTOVLENNOM dZH. p. eKKERTOM I dZH u. mOCHLI DLYA SHKOLY mURA PO |LEKTROTEHNIKE [Moore school of Electrical Engineering (September 30, 1945)], UKAZYVALOSX, CHTO evm, OSNASHCHENNAYA USTROJSTVOM S MAGNITNOJ PROVOLOKOJ ILI LENTOJ, MOGLA BY MODELIROVATX %% 459 DEJSTVIYA KARTOCHNOGO OBORUDOVANIYA, DOSTIGAYA PRI |TOM BOLXSHEJ SKOROSTI SORTIROVKI. eTOT DOKLAD OPISYVAL SBALANSIROVANNUYU DVUHPUTEVUYU PORAZRYADNUYU SORTIROVKU I SBALANSIROVANNOE DVUHPUTEVOE SLIYANIE S ISPOLXZOVANIEM CHETYREH USTROJSTV S MAGNITNOJ PROVOLOKOJ ILI LENTOJ, CHITAYUSHCHIH ILI ZAPISYVAYUSHCHIH "NE MENEE 5000 IMPULXSOV V SEKUNDU". dZHON mOCHLI VYSTUPIL S LEKCIEJ O "SORTIROVKE I SLIYANII" NA SPECIALXNOJ SESSII PO VYCHISLENIYAM, SOZYVAVSHEJSYA V SHKOLE mURA V 1946 G., I V ZAPISYAH EGO LEKCII SODERZHITSYA PERVOE OPUBLIKOVANNOE OBSUZHDENIE SORTIROVKI S POMOSHCHXYU VYCHISLITELXNYH MASHIN [Theory and techniques for the design of electronic digital computers, ed. by G. W. Patterson, {\bf 3} (1946), 22.1--22.20]. mOCHLI NACHAL SVOE VYSTUPLENIE S INTERESNOGO ZAMECHANIYA: "tREBOVANIE, CHTOBY ODNA MASHINA OB®EDINYALA VOZMOZHNOSTI VYCHISLENIJ I SORTIROVKI, MOZHET VYGLYADETX KAK TREBOVANIE, CHTOBY ODIN PRIBOR ISPOLXZOVALSYA KAK KLYUCH DLYA KONSERVOV I KAK AVTORUCHKA". zATEM ON ZAMETIL, CHTO MASHINY, SPOSOBNYE VYPOLNYATX SLOZHNYE MATEMATICHESKIE PROCEDURY, DOLZHNY TAKZHE IMETX VOZMOZHNOSTX SORTIROVATX I KLASSIFICIROVATX DANNYE; ON POKAZAL, CHTO SORTIROVKA MOZHET BYTX POLEZNA DAZHE V SVYAZI S CHISLENNYMI RASCHETAMI. oN OPISAL PROSTYE VSTAVKI I BINARNYE VSTAVKI, ZAMETIV, CHTO V PERVOM METODE V SREDNEM TREBUETSYA OKOLO $N^2/4$ SRAVNENIJ, V TO VREMYA KAK V POSLEDNEM IH NIKOGDA NE TREBUETSYA BOLEE $N\log_2N$. oDNAKO BINARNYE VSTAVKI TREBUYUT VESXMA SLOZHNOJ STRUKTURY DANNYH, I mOCHLI ZATEM POKAZAL, CHTO PRI DVUHPUTEVOM SLIYANII DOSTIGAETSYA STOLX ZHE MALOE CHISLO SRAVNENIJ, NO ISPOLXZUETSYA TOLXKO POSLEDOVATELXNOE PROHOZHDENIE SPISKOV. pOSLEDNYAYA CHASTX ZAPISEJ EGO LEKCIJ POSVYASHCHENA RAZBORU METODOV PORAZRYADNOJ SORTIROVKI S CHASTICHNYMI PROHODAMI, KOTORYE MODELIRUYUT CIFROVUYU KARTOCHNUYU SORTIROVKU NA CHETYREH LENTAH, ZATRACHIVAYA MENEE CHETYREH PROHODOV NA CIFRU (SR. S P. 5.4.7). vSKORE POSLE |TOGO eKKERT I mOCHLI ORGANIZOVALI KOMPANIYU, KOTORAYA VYPUSKALA NEKOTORYE IZ SAMYH RANNIH |LEKTRONNYH VYCHISLITELXNYH MASHIN BINAC (DLYA VOENNYH PRILOZHENIJ) I. UNIVAC (DLYA KOMMERCHESKIH PRILOZHENIJ). vNOVX bYURO PEREPISI ssha SYGRALO ROLX V |TOM RAZVITII, PRIOBRETYA PERVYJ UNIVAC. v |TO VREMYA VOVSE NE BYLO YASNO, CHTO evm STANUT |KONOMICHESKI VYGODNYMI: VYCHISLITELXNYE MASHINY MOGLI SORTIROVATX BYSTREE, NO ONI DOROZHE STOILI. pO|TOMU PROGRAMMISTY UNIVAC POD RUKOVODSTVOM fRANSIS e. gOLXBERTON PRILOZHILI ZNACHITELXNYE USILIYA K SOZDANIYU PROGRAMM VNESHNEJ SORTIROVKI, RABOTAYUSHCHIH S VYSOKOJ SKOROSTXYU, I IH PERVYE PROGRAMMY POVLIYALI TAKZHE NA RAZRABOTKU OBORUDOVANIYA. pO IH OCENKAM, 100 MILLIONOV ZAPISEJ PO 10 SLOV MOGLI BYTX .OTSORTIROVANY NA UNIVAC ZA 9000 CH (T. E. 375 DNEJ). %% 460 UNIVAC I, OFICIALXNO OB®YAVLENNAYA V IYULE 1951 G., IMELA VNUTRENNYUYU PAMYATX V 1000 12-LITERNYH (72-BITOVYH) SLOV. v NEJ PREDUSMATRIVALOSX CHTENIE I ZAPISX NA LENTU BLOKOV PO 60 SLOV SO SKOROSTXYU 500 SLOV V SEKUNDU; CHTENIE MOGLO BYTX PRYAMYM ILI OBRATNYM, DOPUSKALOSX ODNOVREMENNOE CHTENIE /ZAPISX/ VYCHISLENIYA. v 1948~G. MISSIS gOLXBERTON PRIDUMALA INTERESNYJ SPOSOB VYPOLNENIYA DVUHPUTEVOGO SLIYANIYA S POLNYM SOVMESHCHENIEM CHTENIYA, ZAPISI I VYCHISLENIJ S ISPOLXZOVANIEM SHESTI BUFEROV VVODA. pUSTX DLYA KAZHDOGO VVODNOGO FAJLA IMEYUTSYA ODIN "TEKUSHCHIJ BUFER" I DVA "VSPOMOGATELXNYH BUFERA"; SLIVATX MOZHNO TAKIM OBRAZOM, CHTO VSYAKIJ RAZ, KOGDA PRIHODIT VREMYA VYVESTI ODIN BLOK, DVA TEKUSHCHIH BUFERA VVODA .SODERZHAT VMESTE KOLICHESTVO DANNYH, RAVNOE ODNOMU BLOKU. tAKIM OBRAZOM, ZA VREMYA FORMIROVANIYA KAZHDOGO VYVODNOGO BLOKA ROVNO ODIN BUFER VVODA STANOVITSYA PUSTYM, I MY MOZHEM USTROITX TAK, CHTOBY TRI ILI CHETYRE VSPOMOGATELXNYH BUFERA BYLI ZAPOLNENY VSYAKIJ RAZ, KAK MY CHITAEM V OSTAVSHIJSYA BUFER. eTOT METOD CHUTX BYSTREE METODA PROGNOZIROVANIYA ALGORITMA 5.4.6F, TAK KAK NET NEOBHODIMOSTI PROVERYATX REZULXTAT ODNOGO VVODA PERED NACHALOM SLEDUYUSHCHEGO. [sR. S Collation Methods for the UNIVAC System (Eckert-Mauchly Computer Corp., 1950) vol. 1,2.] kULXMINACIONNOJ TOCHKOJ V |TOJ RABOTE STAL GENERATOR PROGRAMM SORTIROVKI, KOTORYJ BYL PERVOJ KRUPNOJ PROGRAMMOJ, RAZRABOTANNOJ DLYA AVTOMATICHESKOGO PROGRAMMIROVANIYA. pOLXZOVATELX UKAZYVAL RAZMER ZAPISI, POZICII KLYUCHEJ (DO PYATI) V CHASTICHNYH POLYAH KAZHDOJ ZAPISI I "KONCEVYE" KLYUCHI, OTMECHAYUSHCHIE KONEC FAJLA, I GENERATOR SORTIROVKI POROZHDAL TREBUEMUYU PROGRAMMU SORTIROVKI DLYA FAJLOV NA ODNOJ BOBINE. pERVYM PROHODOM |TOJ PROGRAMMY BYLA VNUTRENNYAYA SORTIROVKA BLOKOV PO 60 SLOV S ISPOLXZOVANIEM METODA SRAVNENIYA I PODSCHETA (ALGORITM 5.2s); ZATEM VYPOLNYALSYA RYAD SBALANSIROVANNYH DVUHPUTEVYH PROHODOV SLIYANIYA S OBRATNYM CHTENIEM, ISKLYUCHAYUSHCHIH SCEPLENIE LENT, KAK OPISANO VYSHE. [sM. Master Generating Routine for 2-way Sorting (Eckert---Mauchly Div. of Remington Rand, 1952). pERVYJ NABROSOK |TOGO DOKLADA BYL OZAGLAVLEN "oSNOVNAYA SOSTAVLYAYUSHCHAYA PROGRAMMA DVUHPUTEVOGO SLIYANIYA" (Master Prefabrication Routine for 2-way Collation)! sM. TAKZHE F. E. Holberton, Symposium on Automatic Programming (Office of Naval Research, 1954), 34--39.] k 1952~G. MNOGIE METODY VNUTRENNEJ SORTIROVKI PROCHNO VOSHLI V PROGRAMMISTSKIJ FOLXKLOR, NO TEORIYA BYLA RAZVITA SRAVNITELXNO SLABO. dANI|LX gOLDENBERG [Time analises of various methods of sorting data, Digital Computer Lab. memo M-1680 (Mass. Inst. of Tech.,. October 17, 1952)] ZAPROGRAMMIROVAL DLYA MASHINY Whirlwind PYATX RAZLICHNYH METODOV I PROVEL ANALIZ %% 461 NAILUCHSHEGO I NAIHUDSHEGO SLUCHAEV DLYA KAZHDOJ PROGRAMMY. oN NASHEL, CHTO DLYA SORTIROVKI SOTNI 15-BITOVYH ZAPISEJ PO 8-BITOVOMU KLYUCHU NAILUCHSHIE PO SKOROSTI REZULXTATY POLUCHAYUTSYA V TOM SLUCHAE, ESLI ISPOLXZUETSYA TABLICA IZ 256 SLOV I KAZHDAYA ZAPISX POMESHCHAETSYA V EDINSTVENNUYU SOOTVETSTVUYUSHCHUYU EE KLYUCHU POZICIYU, A ZATEM |TA TABLICA SZHIMAETSYA. oDNAKO |TOT METOD IMEL OCHEVIDNYJ NEDOSTATOK, IBO ON UNICHTOZHAL ZAPISX, ESLI POSLEDUYUSHCHAYA IMELA TOT ZHE KLYUCH. oSTALXNYE CHETYRE PROANALIZIROVANNYH METODA BYLI UPORYADOCHENY SLEDUYUSHCHIM OBRAZOM: PRYAMOE DVUHPUTEVOE SLIYANIE LUCHSHE PORAZRYADNOJ SORTIROVKI S OSNOVANIEM 2, KOTORAYA LUCHSHE PROSTOGO VYBORA, KOTORYJ V SVOYU OCHEREDX LUCHSHE METODA PUZYRXKA. eTI REZULXTATY POLUCHILI DALXNEJSHEE RAZVITIE V DISSERTACII gAROLXDA X. sXYUVORDA V 1954~G. [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.]. sXYUVORD VYSKAZAL IDEI RASPREDELYAYUSHCHEGO PODSCHETA I VYBORA S ZAMESHCHENIEM. oN POKAZAL, CHTO PERVYJ OTREZOK SLUCHAJNOJ PERESTANOVKI IMEET SREDNYUYU DLINU $e-1$, I ANALIZIROVAL NARYADU S VNUTRENNEJ SORTIROVKOJ I VNESHNYUYU KAK NA RAZLICHNYH TIPAH MASSOVOJ PAMYATI, TAK I NA LENTAH. eSHCHE BOLEE DOSTOJNAYA VNIMANIYA DISSERTACIYA---NA |TOT RAZ DOKTORSKAYA--- BYLA NAPISANA gOVARDOM b. dEMUTOM V 1956~G. [Electronic Data Sorting (Stanford University, October, 1956), 92 pp.]. eTA RABOTA POMOGLA ZALOZHITX OSNOVY TEORII SLOZHNOSTI VYCHISLENIJ. v.NEJ RASSMATRIVALISX TRI ABSTRAKTNYE MODELI ZADACHI SORTIROVKI: S ISPOLXZOVANIEM CIKLICHESKOJ PAMYATI, LINEJNOJ PAMYATI I PAMYATI S PROIZVOLXNYM DOSTUPOM; DLYA KAZHDOJ MODELI BYLI RAZRABOTANY OPTIMALXNYE ILI POCHTI OPTIMALXNYE METODY. (sR. S UPR. 5.3.4--62.) hOTYA NEPOSREDSTVENNO IZ DISSERTACII dEMUTA NE VYTEKAET NIKAKIH PRAKTICHESKIH SLEDSTVIJ, V NEJ SODERZHATSYA VAZHNYE IDEI O TOM, KAK SVYAZATX TEORIYU S PRAKTIKOJ. tAKIM OBRAZOM, ISTORIYA SORTIROVKI BYLA TESNO SVYAZANA SO MNOGIMI ISHOZHENNYMI TROPAMI V VYCHISLENIYAH: S PERVYMI MASHINAMI DLYA OBRABOTKI DANNYH, PERVYMI ZAPOMINAEMYMI PROGRAMMAMI, PERVYM PROGRAMMNYM OBESPECHENIEM, PERVYMI METODAMI BUFERIZACII, PERVOJ RABOTOJ PO ANALIZU ALGORITMOV I SLOZHNOSTI VYCHISLENIJ. nI ODIN IZ DOKUMENTOV OTNOSITELXNO evm, UPOMYANUTYH DO SIH POR, NE POYAVLYALSYA V "OTKRYTOJ LITERATURE". tAK UZH SLUCHILOSX, CHTO BOLXSHAYA CHASTX RANNEJ ISTORII VYCHISLITELXNYH MASHIN SODERZHITSYA V SRAVNITELXNO NEDOSTUPNYH DOKLADAH, POSKOLXKU OTNOSITELXNO NEMNOGIE LICA BYLI V TO VREMYA SVYAZANY S evm. nAKONEC V 1955--1956~GG. LITERATURA O SORTIROVKE PRONIKAET V PECHATX V VIDE TREH BOLXSHIH OBZORNYH STATEJ. %% 462 pERVAYA STATXYA BYLA PODGOTOVLENA dZH. k. hOSKENOM [Proc. Eastern Joint. Computer Conference, 8 (1955), 39---55]. oN NACHINAET S TONKOGO NABLYUDENIYA: "chTOBY SNIZITX STOIMOSTX EDINICY REZULXTATA, LYUDI OBYCHNO UKRUPNYAYUT OPERACII. nO PRI |TIH USLOVIYAH STOIMOSTX EDINICY SORTIROVKI NE UMENXSHAETSYA, A VOZRASTAET". hOSKEN OPISAL VSE OBORUDOVANIE SPECIALXNOGO NAZNACHENIYA, IMEVSHEESYA V PRODAZHE, A TAKZHE METODY SORTIROVKI NA evm. eGO BIBLIOGRAFIYA IZ 54 PUNKTOV OSNOVANA BOLXSHEJ CHASTXYU NA BROSHYURAH FIRM-IZGOTOVITELEJ. pODROBNAYA STATXYA e. X. fR|NDA [Sorting on Electronic Computer Systems, {\sl JACM\/}, {\bf 3} (1956), 134--168] YAVILASX VAZHNOJ VEHOJ V RAZVITII SORTIROVKI. hOTYA ZA PROSHEDSHEE S 1956 G. VREMYA BYLI RAZRABOTANY MNOGOCHISLENNYE METODY, |TA STATXYA VSE ESHCHE NEOBYCHNO SOVREMENNA VO MNOGIH OTNOSHENIYAH. fR|ND DAL TSHCHATELXNOE OPISANIE VESXMA BOLXSHOGO CHISLA ALGORITMOV VNUTRENNEJ I VNESHNEJ SORTIROVKI I OBRATIL OSOBOE VNIMANIE NA METODY BUFERIZACII I HARAKTERISTIKI MAGNITNYH LENTOPROTYAZHNYH USTROJSTV. oN VVEL NEKOTORYE NOVYE METODY (NAPRIMER, VYBOR IZ DEREVA, METOD DVUGLAVOGO ZMIYA I PROGNOZIROVANIE) I RAZRABOTAL NEKOTORYE MATEMATICHESKIE SVOJSTVA STARYH METODOV. tRETIJ OBZOR PO SORTIROVKE, KOTORYJ POYAVILSYA V TO VREMYA, BYL PODGOTOVLEN d. u. d|VAJSOM [{\sl Proc. Inst. Elect. Engineers\/}, {\bf 103v}, supplement 1 (1956), 87--93]. v POSLEDUYUSHCHIE GODY ESHCHE NESKOLXKO VYDAYUSHCHIHSYA OBZOROV BYLO OPUBLIKOVANO d. a. bELLOM [{\sl sOmp. J.\/}, {\bf 1} (1958), 71--77]; a. sh. dUGLASOM [{\sl Comp. J.\/}, {\bf 2} (1959), 1--9]; d. d. mAK-kRAKENOM, g. vEJSSOM I c. lI [Programming Business Computers (New York: Wiley, 1959), chapter~15, 298--332]; a. fLORESOM [{\sl JACM\/}, {\bf 8} (1961) 41--80]; k. e. aJVERSONOM [A programming language (New York: Wiley, 1962), chapter 6, 176---245]; k. k. gOTLIBOM [{\sl CACM\/}, {\bf 6} (1963), 194--201]; t. n. hIBBARDOM [{\sl CACM\/},{\bf 6} (1963), 206--213]; m. a. gOTCEM [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]. v NOYABRE 1962~G. ACM ORGANIZOVALA SIMPOZIUM PO SORTIROVKE (BOLXSHAYA CHASTX RABOT, PREDSTAVLENNYH NA |TOM SIMPOZIUME, OPUBLIKOVANA V MAE 1963 G. V VYPUSKE {\sl CACM\/}). oNI DAYUT HOROSHEE PREDSTAVLENIE O SOSTOYANII |TOJ OBLASTI V TO VREMYA. oBZOR k.~k.~gOTLIBA O SOVREMENNYH GENERATORAH SORTIROVKI, OBZOR t.~n.~hIBBARDA O VNUTRENNEJ SORTIROVKE S MINIMALXNOJ PAMYATXYU I RANNEE ISSLEDOVANIE dZH.~a.~hABB|RDA O SORTIROVKE FAJLOV NA DISKAH---NAIBOLEE ZASLUZHIVAYUSHCHIE VNIMANIYA STATXI V |TOM SOBRANII. zA PROSHEDSHIJ PERIOD BYLI OTKRYTY NOVYE METODY SORTIROVKI: VYCHISLENIE ADRESA~(1956), SLIYANIE S VSTAVKOJ~(1959), OBMENNAYA PORAZRYADNAYA SORTIROVKA~(1959), KASKADNOE SLIYANIE~(1959), METOD shELLA S UBYVAYUSHCHIM SHAGOM~(1959), MNOGOFAZNOE %% 463 SLIYANIE (1960), VSTAVKI V DEREVO (1960), OSCILLIRUYUSHCHAYA SORTIROVKA (1962), BYSTRAYA SORTIROVKA hOARA (1962), PIRAMIDALXNAYA SORTIROVKA uILXYAMSA (1964), OBMENNAYA SORTIROVKA SO SLIYANIEM b|TCHERA (1964). iSTORIYA KAZHDOGO OTDELXNOGO ALGORITMA PROSLEZHIVAETSYA V TEH RAZDELAH NASTOYASHCHEJ GLAVY GDE |TOT METOD OPISYVAETSYA. kONEC 60-H GODOV NASHEGO STOLETIYA OZNAMENOVALSYA INTENSIVNYM RAZVITIEM SOOTVETSTVUYUSHCHEJ TEORII. pOLNAYA BIBLIOGRAFIYA VSEH RABOT, IZUCHENNYH AVTOROM PRI NAPISANII |TOJ GLAVY, IMEETSYA V [{\sl Computing Reviews\/}, {\bf 13} (1972), 283--289]. \excercises \ex[05] pODVEDITE ITOG |TOJ GLAVE; SFORMULIRUJTE OBOBSHCHENIE TEOREMY 5.4.6a. \ex[20] sKAZHITE, OSNOVYVAYASX NA TABL.~1, KAKOJ IZ METODOV SORTIROVKI SPISKOV DLYA SHESTICIFROVYH KLYUCHEJ BUDET NAILUCHSHIM DLYA MASHINY \MIX. \ex[47]\exhead(uSTOJCHIVAYA SORTIROVKA S MINIMALXNOJ PAMYATXYU.) gOVORYAT, CHTO ALGORITM SORTIROVKI TREBUET \emph{MINIMALXNOJ PAMYATI}, ESLI ON ISPOLXZUET DLYA SVOIH PEREMENNYH TOLXKO $O((\log N)^2)$ BITOV PAMYATI SVERH PROSTRANSTVA, TREBUEMOGO DLYA RAZMESHCHENIYA $N$ ZAPISEJ. aLGORITM DOLZHEN BYTX OBSHCHIM V TOM SMYSLE, CHTO DOLZHEN RABOTATX PRI LYUBYH $N$, A NE TOLXKO PRI OPREDELENNOM ZNACHENII $N$, ESLI, KONECHNO, PREDPOLAGAETSYA, CHTO PRI VYZOVE ALGORITMA DLYA SORTIROVKI EMU OBESPECHIVAETSYA DOSTATOCHNOE KOLICHESTVO PAMYATI S PROIZVOLXNYM DOSTUPOM. vO MNOGIH IZ IZUCHENNYH NAMI ALGORITMOV SORTIROVKI |TO TREBOVANIE MINIMALXNOJ PAMYATI NARUSHAETSYA; V CHASTNOSTI, ZAPRESHCHENO ISPOLXZOVANIE $N$ POLEJ SVYAZI. bYSTRAYA SORTIROVKA (ALGORITM 5.2.2Q) UDOVLETVORYAET TREBOVANIYU MINIMALXNOJ PAMYATI, NO EE VREMYA RABOTY V NAIHUDSHEM SLUCHAE PROPORCIONALXNO $N^2$. pIRAMIDALXNAYA SORTIROVKA (ALGORITM 5.2.3n) YAVLYAETSYA EDINSTVENNYM SREDI IZUCHENNYH NAMI ALGORITMOV TIPA $O(N\log N)$, KOTORYJ ISPOLXZUET MINIMALXNUYU PAMYATX, HOTYA MOZHNO SFORMULIROVATX I ESHCHE ODIN PODOBNYJ ALGORITM, ESLI ISPOLXZOVATX IDEYU IZ UPR.~5.2.4--18. sAMYM BYSTRYM OBSHCHIM ALGORITMOM, IZUCHENNYM NAMI, KOTORYJ \emph{USTOJCHIVO} SORTIRUET KLYUCHI, YAVLYAETSYA METOD SLIYANIYA SPISKOV (ALGORITM 5.2.4L), ODNAKO ON ISPOLXZUET NE MINIMALXNUYU PAMYATX. fAKTICHESKI EDINSTVENNYMI USTOJCHIVYMI ALGORITMAMI SORTIROVKI S MINIMALXNOJ PAMYATXYU, KOTORYE MY VIDELI, BYLI METODY TIPA $O(N^2)$ (PROSTYE VSTAVKI, METOD PUZYRXKA I VARIANTY PROSTOGO VYBORA). sUSHCHESTVUET LI USTOJCHIVYJ ALGORITM SORTIROVKI S MINIMALXNOJ PAMYATXYU, TREBUYUSHCHIJ MENEE $O(N^2)$ EDINIC VREMENI V NAIHUDSHEM SLUCHAE ILI V SREDNEM? \epigraph ya DOSTIG SVOEJ CELI., ESLI. RASSORTIROVAL I PRIVEL V LOGICHESKIJ PORYADOK HOTYA BY YADRO TOGO OGROMNOGO MATERIALA O SORTIROVKE, KOTORYJ POYAVILSYA ZA POSLEDNIE NESKOLXKO LET. \signed dZH. k. hOSKEN (1955) %% 464 \chapter{pOISK} \epigraph pOISHCHEM ZAPISX \signed {eL sMIT (1928)% \note{1}{sMIT, aLXFRED eMMANU|LX (1873--1944) --- AMERIKANSKIJ POLITICHESKIJ DEYATELX.---{\sl pRIM. PEREV.}} } eTU GLAVU MOZHNO BYLO NAZVATX INACHE: ILI PRETENCIOZNO---"hRANENIE I VYBORKA INFORMACII", ILI PROSTO---"pOISK PO TABLICAM". nAS BUDET INTERESOVATX PROCESS NAKOPLENIYA INFORMACII V PAMYATI VYCHISLITELXNOJ MASHINY S POSLEDUYUSHCHIM VOZMOZHNO BOLEE BYSTRYM IZVLECHENIEM |TOJ INFORMACII. iNOGDA MY STALKIVAEMSYA SO STOLX BOLXSHIM OB®EMOM DANNYH, CHTO REALXNO ISPOLXZOVATX IH VSE NE MOZHEM. v |TOM SLUCHAE SAMYM MUDRYM BYLO BY ZABYTX I RAZRUSHITX BOLXSHUYU IH CHASTX; NO NEREDKO BYVAET VAZHNO SOHRANITX I TAK ORGANIZOVATX IMEYUSHCHIESYA FAKTY, CHTOBY OBESPECHITX NAIBYSTREJSHUYU IH VYBORKU. eTA GLAVA POSVYASHCHENA V OSNOVNOM IZUCHENIYU OCHENX PROSTOJ POISKOVOJ ZADACHI: KAK NAHODITX DANNYE, HRANYASHCHIESYA S OPREDELENNOJ IDENTIFIKACIEJ. nAPRIMER, V VYCHISLITELXNOJ ZADACHE NAM MOZHET PONADOBITXSYA NAJTI $f(x)$, IMEYA $x$ I TABLICU ZNACHENIJ FUNKCII $f$; V LINGVISTICHESKOJ MOZHET INTERESOVATX ANGLIJSKIJ |KVIVALENT DANNOGO RUSSKOGO SLOVA. vOOBSHCHE BUDEM PREDPOLAGATX, CHTO HRANITSYA MNOZHESTVO IZ $N$ ZAPISEJ I NEOBHODIMO OPREDELITX POLOZHENIE SOOTVETSTVUYUSHCHEJ ZAPISI. kAK I V SLUCHAE SORTIROVKI, PREDPOLOZHIM, CHTO KAZHDAYA ZAPISX SODERZHIT SPECIALXNOE POLE, KOTOROE NAZYVAETSYA \emph{KLYUCHOM}, VOZMOZHNO, POTOMU, CHTO MNOGIE LYUDI EZHEDNEVNO TRATYAT MASSU VREMENI NA POISK SVOIH KLYUCHEJ. mY OBYCHNO TREBUEM, CHTOBY $N$ KLYUCHEJ BYLI RAZLICHNY, TAK CHTO KAZHDYJ KLYUCH ODNOZNACHNO OPREDELYAET SVOYU ZAPISX. sOVOKUPNOSTX VSEH ZAPISEJ NAZYVAETSYA \dfn{TABLICEJ} ILI \dfn{FAJLOM}, PRICHEM POD TABLICEJ, KAK PRAVILO, PODRAZUMEVAETSYA %% 465 NEBOLXSHOJ FAJL, A FAJLOM OBYCHNO NAZYVAYUT BOLXSHUYU TABLICU. bOLXSHOJ FAJL, ILI GRUPPA FAJLOV, CHASTO NAZYVAETSYA \dfn{BAZOJ DANNYH}. v ALGORITMAH POISKA PRISUTSTVUET TAK NAZYVAEMYJ \dfn{ARGUMENT POISKA $K$}, I ZADACHA SOSTOIT V OTYSKANII ZAPISI, IMEYUSHCHEJ $K$ SVOIM KLYUCHOM. sUSHCHESTVUYUT DVE VOZMOZHNOSTI OKONCHANIYA POISKA: LIBO POISK OKAZALSYA \dfn{UDACHNYM}, T. E. POZVOLIL OPREDELITX POLOZHENIE SOOTVETSTVUYUSHCHEJ ZAPISI, SODERZHASHCHEJ $K$, LIBO ON OKAZALSYA \emph{NEUDACHNYM}, T. E. POKAZAL, CHTO ARGUMENT $K$ NE MOZHET BYTX NAJDEN NI V ODNOJ IZ ZAPISEJ. pOSLE NEUDACHNOGO POISKA INOGDA ZHELATELXNO VSTAVITX V TABLICU NOVUYU ZAPISX, SODERZHASHCHUYU $K$; ALGORITM, KOTORYJ DELAET |TO, NAZYVAETSYA ALGORITMOM "POISKA S VSTAVKOJ". nEKOTORYE TEHNICHESKIE USTROJSTVA, IZVESTNYE KAK "ASSOCIATIVNAYA PAMYATX", RESHAYUT PROBLEMU POISKA AVTOMATICHESKI ANALOGICHNO TOMU, KAK |TO DELAET CHELOVECHESKIJ MOZG; MY ZHE BUDEM IZUCHATX METODY POISKA NA OBYCHNOJ UNIVERSALXNOJ VYCHISLITELXNOJ MASHINE. hOTYA CELXYU POISKA YAVLYAETSYA INFORMACIYA, KOTORAYA SODERZHITSYA V ZAPISI, ASSOCIIROVANNOJ S KLYUCHOM $K$, V ALGORITMAH |TOJ GLAVY OBYCHNO IGNORIRUETSYA VSE, KROME SOBSTVENNO KLYUCHEJ. v SAMOM DELE, ESLI POLOZHENIE $K$ OPREDELENO, SOOTVETSTVUYUSHCHIE DANNYE MOZHNO NAJTI. nAPRIMER, ESLI $K$ VSTRETILSYA V YACHEJKE~$|TABLE|+i$, ASSOCIIROVANNYE DANNYE (ILI UKAZATELX NA NIH) MOGUT NAHODITXSYA PO ADRESU $|TABLE|+i+1$, ILI $|DATA|+i$ I T. D. tAKIM OBRAZOM, PODROBNOSTI, KASAYUSHCHIESYA TOGO, CHTO NUZHNO DELATX, KOGDA NAJDEN KLYUCH $K$, MOZHNO SPOKOJNO OPUSTITX. vO MNOGIH PROGRAMMAH POISK TREBUET NAIBOLXSHIH VREMENNYH ZATRAT, TAK CHTO ZAMENA PLOHOGO METODA POISKA NA HOROSHIJ CHASTO VEDET K SUSHCHESTVENNOMU UVELICHENIYU SKOROSTI RABOTY. dEJSTVITELXNO, NEREDKO UDAETSYA TAK ORGANIZOVATX DANNYE ILI STRUKTURU DANNYH, CHTO POISK POLNOSTXYU ISKLYUCHAETSYA, T. E. MY VSEGDA ZNAEM ZARANEE, GDE NAHODITSYA NUZHNAYA NAM INFORMACIYA. sVYAZANNAYA PAMYATX YAVLYAETSYA OBSHCHEPRINYATYM METODOM DOSTIZHENIYA |TOGO; NAPRIMER, V SPISKE S DVUMYA SVYAZYAMI NET NEOBHODIMOSTI ISKATX |LEMENT, SLEDUYUSHCHIJ ZA DANNYM ILI PREDSHESTVUYUSHCHIJ EMU. dRUGOJ SPOSOB IZBEZHATX POISKA OTKRYVAETSYA PERED NAMI, ESLI PREDOSTAVLENA SVOBODA VYBORA KLYUCHEJ. sDELAEM IH CHISLAMI $\{1,2, \ldots, N\}$, I TOGDA ZAPISX, SODERZHASHCHAYA $K$, MOZHET BYTX PROSTO POMESHCHENA V YACHEJKU $|TABLE|+K$. oBA |TI SPOSOBA ISPOLXZOVALISX DLYA USTRANENIYA POISKA IZ ALGORITMA TOPOLOGICHESKOJ SORTIROVKI, OBSUZHDAVSHEGOSYA V P.~2.2.3. tEM NE MENEE VO MNOGIH SLUCHAYAH POISK NEOBHODIM (NAPRIMER, KOGDA OB®EKTAMI TOPOLOGICHESKOJ SORTIROVKI YAVLYAYUTSYA SIMVOLICHESKIE IMENA, A NE CHISLA), TAK CHTO VESXMA VAZHNO IMETX |FFEKTIVNYE ALGORITMY POISKA. mETODY POISKA MOZHNO KLASSIFICIROVATX NESKOLXKIMI SPOSOBAMI. mY MOGLI BY RAZDELITX IH NA VNUTRENNIJ I VNESHNIJ %% 466 POISK V SOOTVETSTVII S RAZDELENIEM ALGORITMOV SORTIROVKI V GL.~5 NA VNUTRENNYUYU I VNESHNYUYU SORTIROVKU. iLI MY MOGLI BY RAZLICHATX STATICHESKIJ I DINAMICHESKIJ METODY POISKA, GDE "STATICHESKIJ" OZNACHAET, CHTO SODERZHIMOE TABLICY OSTAETSYA NEIZMENNYM (TAK CHTO VAZHNO MINIMIZIROVATX VREMYA POISKA, PRENEBREGAYA ZATRATAMI NA PERESTROJKU TABLICY), A "DINAMICHESKIJ" OZNACHAET, CHTO TABLICA YAVLYAETSYA OB®EKTOM CHASTYH VSTAVOK (I, MOZHET BYTX, UDALENIJ). tRETXYA VOZMOZHNAYA SHEMA KLASSIFICIRUET METODY POISKA V SOOTVETSTVII S TEM, OSNOVANY LI ONI NA SRAVNENII KLYUCHEJ ILI NA CIFROVYH SVOJSTVAH KLYUCHEJ, ANALOGICHNO TOMU, KAK RAZLICHAYUTSYA SORTIROVKA S POMOSHCHXYU SRAVNENIYA I SORTIROVKA S POMOSHCHXYU RASPREDELENIYA. nAKONEC, MY MOGLI BY RAZDELITX METODY POISKA NA METODY, ISPOLXZUYUSHCHIE ISTINNYE KLYUCHI, I NA METODY, RABOTAYUSHCHIE S PREOBRAZOVANNYMI KLYUCHAMI. oRGANIZACIYA DANNOJ GLAVY ESTX. V SUSHCHNOSTI, KOMBINACIYA DVUH POSLEDNIH SPOSOBOV KLASSIFIKACII. v \S~6.1 RASSMATRIVAYUTSYA METODY POSLEDOVATELXNOGO POISKA "V LOB", A V \S~6.2 OBSUZHDAYUTSYA ULUCHSHENIYA, KOTORYE MOZHNO POLUCHITX NA OSNOVE SRAVNENIJ MEZHDU KLYUCHAMI S ISPOLXZOVANIEM ALFAVITNOGO ILI CHISLOVOGO PORYADKA DLYA UPRAVLENIYA RESHENIYAMI. v \S~6.3 RASSMATRIVAETSYA CIFROVOJ POISK, A V \S~6.4 OBSUZHDAETSYA VAZHNYJ KLASS METODOV, NAZYVAEMYH HESHIROVANIEM I OSNOVANNYH NA ARIFMETICHESKIH PREOBRAZOVANIYAH ISTINNYH KLYUCHEJ. v KAZHDOM IZ |TIH PARAGRAFOV RASSMATRIVAETSYA KAK VNUTRENNIJ, TAK I VNESHNIJ POISK, I DLYA STATICHESKOGO I DLYA DINAMICHESKOGO SLUCHAEV; V KAZHDOM PARAGRAFE OTMECHAYUTSYA SRAVNITELXNYE DOSTOINSTVA I NEDOSTATKI RAZLICHNYH ALGORITMOV. mEZHDU POISKOM I SORTIROVKOJ SUSHCHESTVUET OPREDELENNAYA VZAIMOSVYAZX. nAPRIMER, RASSMOTRIM SLEDUYUSHCHUYU ZADACHU: $$ \displaylines{ \hbox{dANY DVA MNOZHESTVA CHISEL:}\cr \hbox{$A=\{a_1, a_2, \ldots, a_m\}$ I $B=\{b_1, b_2, \ldots, b_n\}$;}\cr \hbox{OPREDELITX, YAVLYAETSYA LI $A$ PODMNOZHESTVOM $B$, T.~E. $A\subseteq B$.}\cr } $$ nAPRASHIVAYUTSYA TRI RESHENIYA, A IMENNO: \enumerate \li sRAVNIVATX KAZHDOE $a_i$ POSLEDOVATELXNO SO VSEMI $b_j$ DO USTANOVLENIYA SOVPADENIYA. \li sVESTI VSE $b_j$ V TABLICU, ZATEM ISKATX KAZHDOE $a_i$ PO TABLICE. \li uPORYADOCHITX $A$ I~$B$, ZATEM SOVERSHITX ODIN POSLEDOVATELXNYJ PROHOD PO OBOIM FAJLAM, PROVERYAYA SOOTVETSTVUYUSHCHIE USLOVIYA. \enumend \noindent kAZHDOE IZ |TIH RESHENIJ IMEET SVOI PRIVLEKATELXNYE STORONY DLYA RAZLICHNYH DIAPAZONOV ZNACHENIJ $m$ I $n$. dLYA RESHENIYA 1 POTREBUETSYA PRIBLIZITELXNO $c_1mn$ EDINIC VREMENI, GDE $c_1$---NEKOTORAYA KONSTANTA, A RESHENIE 3 ZAJMET OKOLO $c_2(m \log_2m+n\log_2n)$ EDINIC, GDE $c_2$---NEKOTORAYA (B\'OLXSHAYA) KONSTANTA. pRI PODHODYASHCHEM %% 467 METODE HESHIROVANIYA RESHENIE 2 POTREBUET PRIMERNO $c_3m+c_4n$ EDINIC VREMENI, GDE $c_3$ I~$c_4$---NEKOTORYE (ESHCHE B\'OLXSHIE) KONSTANTY. sLEDOVATELXNO, RESHENIE 1 HOROSHO PRI OCHENX MALYH $m$ I~$n$, A PRI VOZRASTANII $m$ I $n$ LUCHSHIM BUDET RESHENIE 3. zATEM, POKA $n$ NE DOSTIGNET RAZMEROV VNUTRENNEJ PAMYATI, BOLEE PREDPOCHTITELXNO RESHENIE 2; POSLE |TOGO OBYCHNO RESHENIE 3 SNOVA STANOVITSYA LUCHSHE, POKA $n$ NE SDELAETSYA ESHCHE GORAZDO BOLXSHIM. zNACHIT, MY IMEEM SITUACIYU, GDE SORTIROVKA INOGDA HOROSHO ZAMENYAET POISK, A POISK---SORTIROVKU. zACHASTUYU SLOZHNYE ZADACHI POISKA MOZHNO SVESTI K BOLEE PROSTYM SLUCHAYAM, RASSMATRIVAEMYM ZDESX. nAPRIMER, PREDPOLOZHIM, CHTO V ROLI KLYUCHEJ VYSTUPAYUT SLOVA, KOTORYE MOGLI BYTX SLEGKA ISKAZHENY; MY HOTELI BY NAJTI PRAVILXNUYU ZAPISX, NESMOTRYA NA |TU OSHIBKU. eSLI SDELATX DVE KOPII FAJLA, V ODNOJ IZ KOTORYH KLYUCHI RASPOLOZHENY V OBYCHNOM ALFAVITNOM PORYADKE, A V DRUGOJ ONI UPORYADOCHENY SPRAVA NALEVO (KAK ESLI BY SLOVA BYLI PROCHITANY NAOBOROT), ISKAZHENNYJ ARGUMENT POISKA V BOLXSHINSTVE SLUCHAEV SOVPADAET DO POLOVINY SVOEJ DLINY ILI DALXSHE S ZAPISXYU ODNOGO IZ |TIH DVUH FAJLOV. mETODY POISKA, SODERZHASHCHIESYA V \S~6.2 I~6.3, MOZHNO, SLEDOVATELXNO, PRISPOSOBITX DLYA NAHOZHDENIYA KLYUCHA, KOTORYJ BYL, VEROYATNO, ISKAZHEN. pOHOZHIE ZADACHI PRIVLEKLI K SEBE ZAMETNOE VNIMANIE V SVYAZI S SOZDANIEM SISTEM PREDVARITELXNOGO ZAKAZA AVIABILETOV I V SVYAZI S DRUGIMI PRILOZHENIYAMI, KOGDA SUSHCHESTVUET ZNACHITELXNAYA VEROYATNOSTX ISKAZHENIYA IMENI CHELOVEKA IZ-ZA NERAZBORCHIVOGO POCHERKA ILI PLOHOJ SLYSHIMOSTI. nUZHNO BYLO NAJTI PREOBRAZOVANIE ARGUMENTA V NEKIJ KOD, SOBIRAYUSHCHEE VMESTE VSE VARIANTY DANNOGO IMENI. mETOD "Soundex", OPISYVAEMYJ NIZHE V VIDE, V KOTOROM ON PRIMENYAETSYA SEJCHAS, BYL PERVONACHALXNO RAZVIT mARGARET k.~oUDELL I rOBERTOM k.~rASSELOM [SM. U.~S.~Patents 1261167 (1918), 1435663 (1922)]; ON NASHEL SHIROKOE PRIMENENIE DLYA KODIROVANIYA FAMILIJ. \enumerate \li oSTAVITX PERVUYU BUKVU; VSE BUKVY A, E, h, i, O, u, w, U, STOYASHCHIE NA DRUGIH MESTAH, VYCHERKNUTX. \li oSTAVSHIMSYA BUKVAM (KROME PERVOJ) PRISVOITX SLEDUYUSHCHIE ZNACHENIYA: $$\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 eSLI V ISHODNOM IMENI (PERED SHAGOM 1) RYADOM STOYALI NESKOLXKO BUKV S ODINAKOVYMI KODAMI, PRENEBRECHX VSEMI, KROME PERVOJ IZ |TOJ GRUPPY. \li dOPISYVAYA V SLUCHAE NADOBNOSTI NULI ILI OPUSKAYA LISHNIE CIFRY, PREOBRAZOVATX POLUCHENNOE VYRAZHENIE V FORMU "BUKVA, CIFRA, CIFRA, CIFRA". %% 468 \enumend \noindent nAPRIMER, FAMILII Euler, Gauss, Hilbert, Knuth, Lloyd I~{\L}ukasiewicz IMEYUT KODY SOOTVETSTVENNO e460, G200, H416, K530, L300, L222. rAZUMEETSYA, TAKAYA SISTEMA SOBIRAET VMESTE NE TOLXKO RODSTVENNYE, NO I DOSTATOCHNO RAZLICHNYE IMENA. pRIVEDENNYE VYSHE SHESTX KODOV MOGLI BYTX POLUCHENY IZ FAMILIJ Ellery, Ghosh, Heilbronn, Kant, Ladd I Lissajous. s DRUGOJ STORONY, TAKIE RODSTVENNYE IMENA, KAK Rogers I Rodgers, Sinclair I St.~Clair ILI Tchebysheff I Chebyshev, IMEYUT RAZNUYU KODIROVKU. nO, VOOBSHCHE GOVORYA, SISTEMA "Soundex" NAMNOGO UVELICHIVAET VEROYATNOSTX OBNARUZHITX IMYA POD ODNOJ IZ EGO MASOK. [dLYA DALXNEJSHEGO OZNAKOMLENIYA, SM. s. r. 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. s.: National Archives, 1971), 90.] kOGDA MY ISPOLXZUEM SISTEMY TIPA "Soundex", NET NEOBHODIMOSTI PREDPOLAGATX, CHTO VSE KLYUCHI RAZLICHNY; MOZHNO SOSTAVITX SPISKI IZ ZAPISEJ S SOVPADAYUSHCHIMI KODAMI, RASSMATRIVAYA KAZHDYJ SPISOK KAK OB®EKT POISKA. pRI ISPOLXZOVANII BOLXSHIH BAZ DANNYH VYBORKA INFORMACII NAMNOGO USLOZHNYAETSYA, TAK KAK CHASTO ZHELATELXNO RASSMATRIVATX RAZLICHNYE POLYA KAZHDOJ ZAPISI KAK POTENCIALXNYE KLYUCHI. zDESX VAZHNO UMETX NAHODITX ZAPISI PO NEPOLNOJ KLYUCHEVOJ INFORMACII. nAPRIMER, IMEYA BOLXSHOJ FAJL AKTEROV, REZHISSER MOG BY POZHELATX NAJTI VSEH NEZANYATYH AKTRIS V VOZRASTE 25--30 LET, HOROSHO TANCUYUSHCHIH I GOVORYASHCHIH S FRANCUZSKIM AKCENTOM; U SPORTIVNOGO ZHURNALISTA MOZHET VOZNIKNUTX ZHELANIE PODSCHITATX S POMOSHCHXYU FAJLA BEJSBOLXNOJ STATISTIKI OBSHCHEE CHISLO OCHKOV, NABRANNYH PODAYUSHCHIMI-LEVSHAMI KOMANDY "kRASNONOGIE IZ cINCINATTI" V TECHENIE SEDXMYH PERIODOV VECHERNIH IGR ZA 1964~G. iMEYA BOLXSHOJ FAJL DANNYH O CHEM-LIBO, LYUDI LYUBYAT ZADAVATX VOPROSY PROIZVOLXNOJ SLOZHNOSTI. nA SAMOM DELE MY MOGLI BY RASSMATRIVATX POLNUYU BIBLIOTEKU KAK BAZU DANNYH, V KOTOROJ NEKTO ZHELAET NAJTI VSE PUBLIKACII O VYBORKE INFORMACII. vVEDENIE V METODY \emph{POISKA PO MNOGIM PRIZNAKAM} POMESHCHENO V \S~6.5. pREZHDE CHEM PEREHODITX K DETALXNOMU IZUCHENIYU POISKA, POLEZNO RASSMOTRETX ISTORIYU DANNOGO VOPROSA. v DOKOMPXYUTERNYJ PERIOD BYLO SOSTAVLENO MNOZHESTVO TOMOV LOGARIFMICHESKIH, TRIGONOMETRICHESKIH I DRUGIH TABLIC, TAK CHTO MATEMATICHESKIE VYCHISLENIYA MOGLI BYTX ZAMENENY POISKOM. pOTOM |TI TABLICY BYLI PERENESENY NA PERFOKARTY I ISPOLXZOVALISX DLYA NAUCHNYH ZADACH POSREDSTVOM RASPOZNAYUSHCHIH, SORTIROVALXNYH I DUBLIRUYUSHCHIH PERFORATORNYH MASHIN. oDNAKO POSLE POYAVLENIYA evm S ZAPOMINAEMOJ PROGRAMMOJ STALO OCHEVIDNO, CHTO DESHEVLE KAZHDYJ RAZ VYCHISLYATX $\log x$ I~$\cos x$, NEZHELI ISKATX OTVET PO TABLICE. nESMOTRYA NA TO, CHTO ZADACHA SORTIROVKI PRIVLEKLA PRISTALXNOE %% 469 VNIMANIE UZHE NA ZARE RAZVITIYA evm, DLYA RAZRABOTKI ALGORITMOV POISKA BYLO SDELANO SRAVNITELXNO MALO. rASPOLAGAYA NEBOLXSHOJ VNUTRENNEJ PAMYATXYU I TOLXKO POSLEDOVATELXNYMI USTROJSTVAMI TIPA LENT DLYA HRANENIYA BOLXSHIH FAJLOV, ORGANIZOVATX POISK BYLO LIBO SOVERSHENNO TRIVIALXNO, LIBO POCHTI NEVOZMOZHNO. nO RAZVITIE VSE BOLXSHEJ I BOLXSHEJ PAMYATI SO SLUCHAJNYM DOSTUPOM V TECHENIE 50-H GODOV PRIVELO K PONIMANIYU TOGO, CHTO POISK KAK TAKOVOJ YAVLYAETSYA INTERESNOJ ZADACHEJ. pOSLE PERIODA ZHALOB NA OGRANICHENNYE RESURSY PROSTRANSTVA V RANNIH MASHINAH PROGRAMMISTY VDRUG STOLKNULISX S TAKIM OB®EMOM PAMYATI, KOTORYJ ONI NE UMELI |FFEKTIVNO ISPOLXZOVATX. pERVYE OBZORY ZADACH POISKA BYLI OPUBLIKOVANY a.~i.~dUMI [{\sl Computers \& Automation\/}, {\bf 5}, 12 (December 1956), 6--9], u.~u.~pETERSONOM [{\sl IBM J. Research \& Development}, {\bf 1} (1957), 130--146], e.~d.~bUTOM [{\sl Information and Control\/}, {\bf 1} (1958), 159--164], a.~sh.~dUGLASOM [{\sl Comp. J.\/}, {\bf 2} (1959), 1--9]. bOLEE PODROBNYJ OBZOR SDELAN POZDNEE k.~e.~aJVERSONOM [A Programming Language (New York: Wiley, (1962)), 133--158] I v.~bUHHOLXCEM [{\sl IBM Systems J.\/}, {\bf 2} (1963), 86--111]. v NACHALE 60-H GODOV BYLO RAZRABOTANO NESKOLXKO NOVYH ALGORITMOV POISKA, OSNOVANNYH NA ISPOLXZOVANII DREVOVIDNYH STRUKTUR; S NIMI MY POZNAKOMIMSYA NIZHE. i V NASHE VREMYA VEDUTSYA AKTIVNYE ISSLEDOVANIYA PO PROBLEMAM POISKA. %% 470 \subchap{pOSLEDOVATELXNYJ POISK} "nACHNI S NACHALA I PRODVIGAJSYA, POKA NE NAJDESHX NUZHNYJ KLYUCH; TOGDA OSTANOVISX". tAKAYA POSLEDOVATELXNAYA PROCEDURA YAVLYAETSYA OCHEVIDNYM SPOSOBOM POISKA; UDOBNO NACHATX NASHI RASSMOTRENIYA S NEE, TAK KAK NA NEJ OSNOVANY MNOGIE BOLEE SLOZHNYE ALGORITMY. nESMOTRYA NA SVOYU PROSTOTU, POSLEDOVATELXNYJ POISK SODERZHIT RYAD OCHENX INTERESNYH IDEJ. sFORMULIRUEM ALGORITM BOLEE TOCHNO. \alg S.(pOSLEDOVATELXNYJ POISK.) iMEETSYA TABLICA ZAPISEJ $R_1$, $R_2$, \dots, $R_3$, SNABZHENNYH SOOTVETSTVENNO KLYUCHAMI $K_1$, $K_2$, \dots, $K_n$ aLGORITM PREDNAZNACHEN DLYA POISKA ZAPISI S DANNYM KLYUCHOM $K$. pREDPOLAGAETSYA, CHTO $N\ge 1$. \st [nACHALXNAYA USTANOVKA.] uSTANOVITX $i \asg 1$. \st [sRAVNENIE.] eSLI $K=K_i$, ALGORITM OKANCHIVAETSYA UDACHNO. \st [pRODVIZHENIE.] uVELICHITX $i$ NA 1. \st [kONEC FAJLA?] eSLI $i\le N$, TO VERNUTXSYA K SHAGU \stp{2}. v PROTIVNOM SLUCHAE ALGORITM OKANCHIVAETSYA NEUDACHNO. \algend zAMETIM, CHTO U |TOGO ALGORITMA MOZHET BYTX DVA RAZNYH ISHODA: \emph{UDACHNYJ} (KOGDA NAJDENO POLOZHENIE NUZHNOGO KLYUCHA) I \picture{pOSLEDOVATELXNYJ POISK} \emph{NEUDACHNYJ} (KOGDA, USTANOVLENO, CHTO ISKOMOGO ARGUMENTA NET V TABLICE). eTO SPRAVEDLIVO DLYA BOLXSHINSTVA ALGORITMOV DANNOJ GLAVY. rEALIZACIYA V VIDE PROGRAMMY DLYA MASHINY MIX OCHEVIDNA. \prog S.(pOSLEDOVATELXNYJ POISK.) pREDPOLOZHIM, CHTO $K_i$ HRANITSYA PO ADRESU $|KEY|+i$, A OSTAVSHAYASYA CHASTX ZAPISI $R_i$---PO ADRESU $|INFO|+i$. pRIVODIMAYA NIZHE PROGRAMMA ISPOLXZUET $|rA|\equiv K$, $|rI1|\equiv i-N$. %% 471 \code START & LDA & K & 1 & S1. nACHALXNAYA USTANOVKA. & ENT1 & & 1 & $i\asg 1$. 2H & smra & KEY+N, 1 & s & S2. sRAVNENIE. & JE & SUCCESS & s & vYHOD, ESLI $K=K_i$. & INC1 & 1 & C-S & S3.pRODVIZHENIE. & J1NP & 2v & C-S & S4. kONEC FAJLA? FAILURE & EQU & * &1-S & vYHOD, ESLI NET V TABLICE. \endcode pO ADRESU |SUCCESS| RASPOLOZHENA KOMANDA "|LDA INFO+N,1|"; ONA POMESHCHAET NUZHNUYU INFORMACIYU V |rA|. \progend aNALIZ DANNOJ PROGRAMMY NE PREDSTAVLYAET TRUDA; VIDNO, CHTO VREMYA RABOTY ALGORITMA S ZAVISIT OT DVUH PARAMETROV: $$ \eqalign{ C=&\hbox{ (KOLICHESTVO SRAVNENIJ KLYUCHEJ)};\cr S=&1\ \hbox{PRI UDACHE I 0 PRI NEUDACHE}.\cr }\eqno (1) $$ pROGRAMMA S TREBUET $5C-2S+3$ EDINIC VREMENI. eSLI MY NASHLI $K=K_i$, TO $C=i$, $S=1$; ZNACHIT, POLNOE VREMYA RAVNO $(5i+l)u$. eSLI ZHE POISK OKAZALSYA NEUDACHNYM, TO $C=N$, $S=0$, A RABOTALA PROGRAMMA ROVNO $(5N+3)u$. eSLI VSE KLYUCHI POSTUPAYUT NA VHOD S RAVNOJ VEROYATNOSTXYU, TO SREDNEE ZNACHENIE~$C$ PRI UDACHNOM POISKE SOSTAVLYAET $$ {1+2+\cdots+N\over N}={N+1\over 2}; \eqno(2) $$ SREDNEKVADRATICHNOE OTKLONENIE $C$, RAZUMEETSYA, DOVOLXNO BOLXSHOE---PRIMERNO $0.289N$ (SM. UPR. 1). pRIVEDENNYJ, ALGORITM, NESOMNENNO, ZNAKOM VSEM PROGRAMMISTAM. nO MALO KTO ZNAET, CHTO |TOT SPOSOB REALIZACII POSLEDOVATELXNOGO POISKA NE VSEGDA SAMYJ LUCHSHIJ! oCHEVIDNOE IZMENENIE UBYSTRYAET RABOTU ALGORITMA (ESLI TOLXKO ZAPISEJ NE SLISHKOM MALO): \alg Q.(bYSTRYJ POSLEDOVATELXNYJ POISK). v OTLICHIE OT ALGORITMA S ZDESX ESHCHE PREDPOLAGAETSYA, CHTO V KONCE FAJLA STOIT FIKTIVNAYA ZAPISX $R_{N+1}$. \st [nACHALXNAYA USTANOVKA.] uSTANOVITX $i\asg 1$ I~$K_{N+1}\asg K$. \st [sRAVNENIE.] eSLI $K=K_i$, TO PEREJTI NA \stp{4}. \st [pRODVIZHENIE.] uVELICHITX $i$ NA 1 I VERNUTXSYA K SHAGU \stp{2}. \st [kONEC FAJLA?] eSLI $i\le N$, ALGORITM OKANCHIVAETSYA UDACHNO; V PROTIVNOM SLUCHAE---NEUDACHNO $(i=N+1)$. \algend \prog Q.(bYSTRYJ POSLEDOVATELXNYJ POISK.) zNACHENIYA REGISTROV: $|rA| \equiv K$, $|rI1|\equiv i-N$. %%472 \code BEGIN & LDA & k & 1 & Q1. nACHALXNAYA USTANOVKA & STA & KEY+N+1 & 1 & $K_{N+1}\asg K$. & ENT1 & -N & 1 & $i\asg 0$. & INC1 & 1 & C+1-S & Q3. pRODVIZHENIE. & smra & KEY+N, 1& C+l-S & Q2. sRAVNENIE. & JNE & *-2 & C+1-S & nA Q3, ESLI $K_i\ne K$. & J1NP & SUCCESS & 1 & Q4. kONEC FAJLA? FAILURE & EQU & * & 1-S & vYHOD, ESLI NET V TABLICE. \endcode\progend iSPOLXZUYA PARAMETRY $C$ I~$S$, VVEDENNYE PRI ANALIZE PROGRAMMY $S$, MOZHNO ZAKLYUCHITX, CHTO VREMYA RABOTY PROGRAMMY UMENXSHILOSX DO $(4C-4S+10)u$; |TO DAET ULUCHSHENIE PRI $C\ge5$ (DLYA UDACHNOGO POISKA) I PRI $N\ge 8$ (DLYA NEUDACHNOGO POISKA). pRI PEREHODE OT ALGORITMA S K ALGORITMU Q ISPOLXZOVAN VAZHNYJ USKORYAYUSHCHIJ PRINCIP: ESLI VO VNUTRENNEM CIKLE PROGRAMMY PROVERYAYUTSYA DVA ILI BOLEE USLOVIYA, NUZHNO POSTARATXSYA OSTAVITX TAM TOLXKO ODNO SRAVNENIE. sUSHCHESTVUET SPOSOB SDELATX PROGRAMMU Q \emph{ESHCHE} BYSTREE. \prog Q'.(sVERHBYSTRYJ POSLEDOVATELXNYJ POISK.) zNACHENIYA REGISTROV: $|rA|=K$, $|rI1|\equiv i-N$. \code BEGIN &LDA &k &1 & Q1. nACHALXNAYA USTANOVKA. &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. pRODVIZHENIE. (dVOJNOE.) &smra &KEY+N, 1 &\lfloor(C-S+2)/2\rfloor & Q2. sRAVNENIE. &JE &4F &\lfloor(C-S+2)/2\rfloor & nA Q4, ESLI $K=K_i$. &smra &KEY+N+1,1 &\lfloor(C-S+1)/2\rfloor & Q2. sRAVNENIE. (sLEDUYUSHCHEE.) &JNE &3B &\lfloor(C-S+1)/2\rfloor & nA Q3, ESLI $K\ne K_{i+1}$. &INC1 &1 &(C-5)\bmod 2 &pRODVINUTX $i$. 4H &J1NP &SUCCESS & 1 & Q4. kONEC FAJLA? FAILURE &EQU &* &1-S &vYHOD, ESLI NET V TABLICE. \endcode \progend iNSTRUKCII VNUTRENNEGO CIKLA VYPISANY DVAZHDY; |TO ISKLYUCHAET PRIMERNO POLOVINU OPERATOROV "$i\asg i+1$". tAKIM OBRAZOM, VREMYA VYPOLNENIYA PROGRAMMY UMENXSHILOSX DO $$ 3.5C-3.5S+10{(C-S)\bmod 2\over 2} $$ EDINIC. pRI POISKE PO BOLXSHIM TABLICAM PROGRAMMA Q' NA 30\% BYSTREE PROGRAMMY S; PODOBNYM OBRAZOM MOGUT BYTX ULUCHSHENY MNOGIE SUSHCHESTVUYUSHCHIE PROGRAMMY. eSLI IZVESTNO, CHTO KLYUCHI RASPOLOZHENY V VOZRASTAYUSHCHEM PORYADKE, POLEZNO NESKOLXKO IZMENITX ALGORITM. %% 473 \alg t.(pOSLEDOVATELXNYJ POISK V UPORYADOCHENNOJ TABLICE.) iMEETSYA TABLICA ZAPISEJ $R_1$, $R_2$, \dots, $R_N$, PRICHEM KLYUCHI UDOVLETVORYAYUT NERAVENSTVAM $K_1K$. \st [nACHALXNAYA USTANOVKA.] uSTANOVITX $i\asg1$. \st [sRAVNENIE.] eSLI $K\le K_i$, TO PEREJTI NA \stp{4}. \st [pRODVIZHENIE.] uVELICHITX $i$ NA 1 I VERNUTXSYA K SHAGU \stp{2}. \st [rAVENSTVO?] eSLI $K=K_i$, TO ALGORITM OKANCHIVAETSYA UDACHNO. v PROTIVNOM SLUCHAE---NEUDACHNO, NUZHNOJ ZAPISI V TABLICE NET. \algend eSLI VELICHINA $K$ S RAVNOJ VEROYATNOSTXYU PRINIMAET VSE VOZMOZHNYE ZNACHENIYA, TO V SLUCHAE UDACHNOGO POISKA ALGORITM T, PO SUSHCHESTVU, NE LUCHSHE ALGORITMA Q. oDNAKO OTSUTSTVIE NUZHNOJ ZAPISI ALGORITM t DOZVOLYAET OBNARUZHITX PRIMERNO V DVA RAZA BYSTREE. pRIVEDENNYE VYSHE ALGORITMY V CELYAH UDOBSTVA ISPOLXZOVALI INDEKSNYE OBOZNACHENIYA DLYA |LEMENTOV TABLICY; ANALOGICHNYE PROCEDURY PRIMENIMY I K TABLICAM V SVYAZANNOM PREDSTAVLENII, TAK KAK V NIH DANNYE TOZHE RASPOLOZHENY POSLEDOVATELXNO. (sM. UPR.~2, 3 I 4.) \section chASTOTA OBRASHCHENIJ. dO SIH POR PREDPOLAGALOSX, CHTO S RAVNOJ VEROYATNOSTXYU MOZHET POTREBOVATXSYA POISK LYUBOGO ARGUMENTA, ODNAKO CHASTO TAKOE PREDPOLOZHENIE NE PRAVOMERNO; VOOBSHCHE GOVORYA, KLYUCH $K_j$ BUDET RAZYSKIVATXSYA S VEROYATNOSTXYU $p_i$, GDE $p_1+p_2+\cdots+p_N=1$. vREMYA UDACHNOGO POISKA PRI BOLXSHIH $N$ PROPORCIONALXNO CHISLU SRAVNENIJ $C$, SREDNEE .ZNACHENIE KOTOROGO RAVNO $$ \overline{C}_N=p_1+2p_2+\cdots+Np_N. \eqno(3) $$ pUSTX ESTX VOZMOZHNOSTX POMESHCHATX ZAPISI V TABLICU V LYUBOM PORYADKE; TOGDA VELICHINA $\overline{C}_N$ MINIMALXNA PRI $$ p_1\ge p_2\ge \ldots \ge p_N, \eqno (4) $$ T. E. KOGDA NAIBOLEE CHASTO ISPOLXZUEMYE ZAPISI RASPOLOZHENY V NACHALE TABLICY. pOSMOTRIM, CHTO DAET NAM TAKOE "OPTIMALXNOE" RASPOLOZHENIE PRI RAZLICHNYH RASPREDELENIYAH VEROYATNOSTEJ. eSLI $p_1=p_2=\ldots=p_N=1/N$, TO FORMULA (3) SVODITSYA K $\overline{C}_N=(N+1)/2$, CHTO UZHE BYLO POLUCHENO NAMI V (2). pREDPOLOZHIM TEPERX, CHTO $$ 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 sOGLASNO UPR. 7, $\overline{C}_N=2-2^{1-N}$; SREDNEE CHISLO SRAVNENIJ MENXSHE DVUH, ESLI ZAPISI RASPOLOZHENY V NADLEZHASHCHEM PORYADKE. dRUGIM NAPRASHIVAYUSHCHIMSYA RASPREDELENIEM YAVLYAETSYA $$ p_1=N_c, p_2=(N-1)c, \ldots, p_N=c, $$ GDE $$ c=2/N(N+1). \eqno(6) $$ eTO "KLINOVIDNOE" RASPREDELENIE DAET BOLEE PRIVYCHNYJ REZULXTAT $$ \overline{C}_N=c\sum_{1\le k\le N} k\cdot(N+1-k)={N+2\over 2}; \eqno(7) $$ OPTIMALXNOE RASPOLOZHENIE |KONOMIT OKOLO TRETI POISKOVOGO VREMENI, TREBUYUSHCHEGOSYA DLYA ZAPISEJ V SLUCHAJNOM PORYADKE. rAZUMEETSYA, RASPREDELENIYA (5) I~(6) DOVOLXNO ISKUSSTVENNY, I IH NELXZYA SCHITATX HOROSHIM PRIBLIZHENIEM K DEJSTVITELXNOSTI. bOLEE TIPICHNUYU KARTINU DAET "ZAKON zIPFA": $$ p_1=c/1, p_2=c/2, \ldots, p_N=c/N, \rem{GDE $c=1/H_N$}. \eqno (8) $$ eTO RASPREDELENIE POLUCHILO IZVESTNOSTX BLAGODARYA dZH.~k~zIPFU, KOTORYJ ZAMETIL, CHTO $n$-E NAIBOLEE UPOTREBITELXNOE V TEKSTE NA ESTESTVENNOM YAZYKE SLOVO VSTRECHAETSYA S CHASTOTOJ, PRIBLIZITELXNO OBRATNO PROPORCIONALXNOJ $n$. [The Psicho-Biology of Language (Boston, Mass.: Houghton Miffling, 1935); Human Behavior and the Principle of Least Effort (Reading, Mass.: Addison-Wesley, 1949).] aNALOGICHNOE YAVLENIE OBNARUZHENO IM V TABLICAH PEREPISI; TAM STOLICHNYE RAJONY RASPOLOZHENY V PORYADKE UBYVANIYA NASELENIYA. v SLUCHAE, ESLI CHASTOTA KLYUCHEJ V TABLICE PODCHINYAETSYA ZAKONU zIPFA, IMEEM $$ \overline{C}_N=N/H_N; \eqno(9) $$ POISK PO TAKOMU FAJLU PRIMERNO V ${1\over2}\ln N$ RAZ BYSTREE, CHEM PO NEUPORYADOCHENNOMU. [sR. S A.~D.~Booth et al. Mechanical Resolution of Linguistic Problems (New York: Academic Press, 1958), 79.) dRUGOE RASPREDELENIE, BLIZKOE K REALXNOMU, DAET PRAVILO "80--20", KOTOROE CHASTO VSTRECHAETSYA V KOMMERCHESKIH PRILOZHENIYAH [SR. S W. P. Heising, {\sl IBM Systems J.\/}, {\bf 2} (1963), 114--115]. eTO PRAVILO GLASIT, CHTO 80\% RABOTY VEDETSYA NAD NAIBOLEE AKTIVNOJ CHASTXYU FAJLA VELICHINOJ 20\%; ONO PRIMENIMO I K |TIM 20\%, TAK CHTO 64\% RABOTY VEDETSYA S NAIBOLEE AKTIVNYMI 4\% FAJLA, I T. D. iNYMI SLOVAMI, $$ {p_1+p_2+\cdots+p_{.20n}\over p_1+p_2+p_3+\cdots+p_n} \approx 0.80 \rem{DLYA VSEH $n$}. \eqno (10) $$ %% 475 vOT ODNO IZ RASPREDELENIJ, TOCHNO UDOVLETVORYAYUSHCHIH PRIVEDENNOMU PRAVILU PRI $n$, KRATNYH 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) $$ GDE $$ c=1/N^\theta; \theta={\log 0.80 \over \log 0.20}=0.1386. \eqno(12) $$ dEJSTVITELXNO, $p_1+p_2+\cdots+p_n=cn^\theta$ PRI LYUBOM $n$. s VEROYATNOSTYAMI (11) NE TAK PROSTO RABOTATX; IMEEM, ODNAKO, $n^\theta-(n-1)^\theta)=\theta n^{\theta-1}(1 + O(1/n))$, T.E. SUSHCHESTVUET BOLEE PROSTOE RASPREDELENIE, PRIBLIZHENNO UDOVLETVORYAYUSHCHEE PRAVILU "80--20": $$ p_1=c/1^{1-\theta}, p_2=c/2^{1-\theta}, \ldots, p_N=c/N^{1-\theta}, \rem{GDE $c=1/H_N^{1-\theta}$}. \eqno (13) $$ zDESX, KAK I RANXSHE, $\theta= \log 0.80/\log 0.20$, a $H_N^{(s)}$ ESTX $N$-e GARMONICHESKOE CHISLO PORYADKA $s$, T. E. $1^{-s}+2^{-s}+\cdots+N^{-s}$. zAMETIM, CHTO |TO RASPREDELENIE OCHENX NAPOMINAET RASPREDELENIE zIPFA (8); KOGDA $\theta$ IZMENYAETSYA OT 1 DO 0, VEROYATNOSTI MENYAYUTSYA OT RAVNOMERNO RASPREDELENNYH K ZIPFOVSKIM. (v SAMOM DELE, zIPF NASHEL, CHTO $\theta\approx {1\over 2}$ V RASPREDELENII LICHNYH DOHODOV.) pRIMENYAYA (3) K (13), POLUCHAEM DLYA PRAVILA "80--20" SREDNEE CHISLO SRAVNENIJ $$ \overline{C}_N=H_N^{(-\theta)}/H_N^{(1-\theta)} ={\theta N \over \theta+1}+O(N^{(1-\theta)})\approx 0.122N \eqno (14) $$ (SM. UPR. 8). yu. s. shVARC, IZUCHAVSHIJ CHASTOTY POYAVLENIYA SLOV [SM. INTERESNYJ GRAFIK NA STR. 422 V {\sl JACM\/}, {\bf 10} (1963)], PREDLOZHIL BOLEE PODHODYASHCHEE VYRAZHENIE DLYA'ZAKONA zIPFA: $$ p_1=c/1^{1+\theta}, p_2=c/2^{1+\theta}, \ldots, p_N=c/N^{1+\theta}, \rem{GDE $c=1/H_N^{1+\theta}$}, \eqno (15) $$ PRI MALYH \emph{POLOZHITELXNYH} $Q$. [pO SRAVNENIYU S (13) ZDESX IZMENEN ZNAK $\theta$.] v |TOM SLUCHAE $$ \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) $$ CHTO ZNACHITELXNO MENXSHE, CHEM (9) PRI $N\to\infty$. \section "sAMOORGANIZUYUSHCHIJSYA" FAJL. pREDYDUSHCHIE VYCHISLENIYA HOROSHI, NO V BOLXSHINSTVE SLUCHAEV RASPREDELENIE VEROYATNOSTEJ NAM NE IZVESTNO. mY MOGLI BY V KAZHDOJ ZAPISI ZAVESTI SCHETCHIK CHISLA OBRASHCHENIJ, CHTOBY NA OSNOVANII POKAZANIJ SCHETCHIKOV PEREUPORYADOCHITX ZAPISI. vYVEDENNYE FORMULY POKAZYVAYUT, CHTO TAKAYA PROCEDURA MOZHET PRIVESTI K ZAMETNOJ |KONOMII. nO NE VSEGDA %% 476 ZHELATELXNO OTVODITX MNOGO PAMYATI POD SCHETCHIKI, TAK KAK EE MOZHNO ISPOLXZOVATX BOLEE RACIONALXNO (NAPRIMER, PRIMENYAYA DRUGIE METODY POISKA, IZLAGAEMYE NIZHE V DANNOJ GLAVE). pROSTAYA SHEMA, PROISHOZHDENIE KOTOROJ NE IZVESTNO, ISPOLXZUETSYA UZHE MNOGIE GODY. oNA POZVOLYAET DOVOLXNO HOROSHO UPORYADOCHITX ZAPISI BEZ VSPOMOGATELXNYH POLEJ DLYA SCHETCHIKOV: KOGDA MY NAHODIM NUZHNUYU ZAPISX, MY POMESHCHAEM EE V NACHALO TABLICY. pODOBNYJ METOD LEGKO REALIZOVATX, KOGDA TABLICA PREDSTAVLENA V VIDE SVYAZANNOGO LINEJNOGO SPISKA: VEDX CHASTO NAM BYVAET NUZHNO ZNACHITELXNO IZMENITX NAJDENNUYU ZAPISX. iDEYA "SAMOORGANIZUYUSHCHEGOSYA" METODA SOSTOIT V TOM, CHTO CHASTO ISPOLXZUEMYE |LEMENTY BUDUT RASPOLOZHENY DOVOLXNO BLIZKO K NACHALU TABLICY. pUSTX $N$ KLYUCHEJ RAZYSKIVAYUTSYA S VEROYATNOSTYAMI $\{p_1, p_2, \ldots, p_N\}$ SOOTVETSTVENNO, PRICHEM KAZHDYJ POISK SOVERSHAETSYA ABSOLYUTNO \emph{NEZAVISIMO} OT PREDYDUSHCHIH. mOZHNO POKAZATX, CHTO SREDNEE CHISLO SRAVNENIJ PRI NAHOZHDENII ZAPISI V TAKOM SAMOORGANIZUYUSHCHEMSYA FAJLE STREMITSYA K PREDELXNOMU ZNACHENIYU $$ \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) $$ (sM. UPR. 11.) nAPRIMER, ESLI $p_i=1/N$ PRI $1\le i \le N$, SAMOORGANIZUYUSHCHAYASYA TABLICA VSEGDA NAHODITSYA V SLUCHAJNOM PORYADKE, A (17) SVODITSYA K ZNAKOMOMU VYRAZHENIYU $(N+1)/2$, POLUCHENNOMU RANEE. pOSMOTRIM, KAK SAMOORGANIZUYUSHCHAYASYA PROCEDURA RABOTAET PRI RASPREDELENII VEROYATNOSTEJ PO ZAKONU zIPFA (8). iMEEM $$ \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 } $$ (SM. FORMULY (1.2.7--8,3)). eTO GORAZDO LUCHSHE, CHEM U $N$ PRI DOSTATOCHNO BOLXSHIH $N$, I LISHX V $\ln4\approx 1.386$ RAZ HUZHE, CHEM CHISLO SRAVNENIJ PRI OPTIMALXNOM RASPOLOZHENII ZAPISEJ (SR. S (9)). eKSPERIMENTY, PRIVODIVSHIESYA S TABLICAMI SIMVOLOV V KOMPILYATORAH, POKAZALI, CHTO SAMOORGANIZUYUSHCHIJSYA METOD RABOTAET DAZHE LUCHSHE, CHEM PREDSKAZYVAET (18), TAK KAK UDACHNYE POISKI %% 477 NE NEZAVISIMY (NEBOLXSHIE GRUPPY KLYUCHEJ CHASTO POYAVLYAYUTSYA VMESTE). sHEMU, PODOBNUYU SAMOORGANIZUYUSHCHEJSYA, IZUCHILI g. shAJ I f.~v.~dAU|R [{\sl SIAM J. Appl. Math.\/}, {\bf 15} (1967), 874--888.] \section pOISK NA LENTE SREDI ZAPISEJ RAZLICHNOJ DLINY. rASSMOTRIM TEPERX NASHU ZADACHU V INOM RAKURSE. pUSTX TABLICA, PO KOTOROJ PROIZVODITSYA POISK, HRANITSYA NA LENTE I ZAPISI IMEYUT RAZLICHNYE DLINY. lENTA S SISTEMNOJ BIBLIOTEKOJ V STARYH OPERACIONNYH SISTEMAH SLUZHIT PRIMEROM TAKOGO FAJLA. sTANDARTNYE PROGRAMMY SISTEMY, TAKIE, KAK KOMPILYATORY, KOMPONOVSHCHIKI, ZAGRUZCHIKI, GENERATORY OTCHETOV I T. P., YAVLYALISX "ZAPISYAMI" NA LENTE, A BOLXSHINSTVO POLXZOVATELXSKIH RABOT DOLZHNO BYLO NACHINATXSYA S POISKA NUZHNOJ PROGRAMMY. tAKAYA POSTANOVKA ZADACHI DELAET NEPRIMENIMYM PREDYDUSHCHIJ ANALIZ ALGORITMA S: TEPERX SHAG S3 VYPOLNYAETSYA ZA RAZLICHNYE PROMEZHUTKI VREMENI. zNACHIT, NAS BUDET INTERESOVATX NE TOLXKO CHISLO SRAVNENIJ. oBOZNACHIM CHEREZ $L_i$ DLINU ZAPISI $R_i$, A CHEREZ $p_i$, VEROYATNOSTX TOGO, CHTO |TA ZAPISX BUDET OTYSKIVATXSYA. vREMYA POISKA TEPERX PRIMERNO PROPORCIONALXNO VELICHINE $$ p_1L_1+p_2(L_1+L_2)+\cdots+p_N(L_1+L_2+\cdots+L_N). \eqno (19) $$ pRI $L_1=L_2=\ldots=L_N=1$ |TO, OCHEVIDNO, SVODITSYA K IZUCHENNOMU SLUCHAYU (3). kAZHETSYA LOGICHNYM POMESTITX NAIBOLEE NUZHNYE ZAPISI V NACHALO LENTY, NO ZDESX ZDRAVYJ SMYSL PODVODIT NAS. dEJSTVITELXNO, PUSTX NA LENTE ZAPISANY ROVNO DVE PROGRAMMY---$A$ I $B$. pROGRAMMA $A$ TREBUETSYA V DVA RAZA CHASHCHE $B$, NO DLINNEE $B$ V CHETYRE RAZA, T. E. $N=2$, $p_A={2\over3}$, $L_A=4$, $p_B={1\over3}$, $L_B=1$. eSLI MY, SLEDUYA "LOGIKE", POSTAVIM $A$ NA PERVOE MESTO, TO SREDNEE VREMYA POISKA SOSTAVIT ${2\over 3}\cdot4+{1\over3}\cdot 5={13\over3}$; NO ESLI POSTUPITX "NELOGICHNO", RASPOLOZHIV V NACHALE $B$, TO POLUCHITSYA ${1\over3}\cdot1+{2\over3}\cdot5={11\over 3}$. sLEDUYUSHCHAYA TEOREMA POZVOLYAET OPREDELITX OPTIMALXNOE RASPOLOZHENIE BIBLIOTECHNYH PROGRAMM NA LENTE. \proclaim tEOREMA S. pUSTX $L_i$ I $p_i$, OPREDELENY, KAK I RANXSHE. pORYADOK ZAPISEJ NA LENTE OPTIMALEN TOGDA I TOLXKO TOGDA, KOGDA $$ p_1/L_1\ge p_2/L_2\ge \ldots \ge p_N/L_N. \eqno (20) $$ iNYMI SLOVAMI, MINIMUM VYRAZHENIYA $$ 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 PO VSEM PERESTANOVKAM $a_1$ $a-2$ \dots $a_N$ CHISEL $\{1,2,\ldots, N\}$ RAVEN (19) TOGDA I TOLXKO TOGDA, KOGDA VYPOLNYAETSYA (20). \proof pREDPOLOZHIM, CHTO $R_i$ I $R_{i+1}$ POMENYALISX MESTAMI; VELICHINA (19), RANEE RAVNAYA $$ \cdots+p_i(L_1+\cdots+L_{i-1}+L_i)+p_{i+1}(L_1+\cdots+L_{i+1}) +\cdots, $$ TEPERX ZAMENITSYA NA $$ \cdots+p_{i+1}(L_1+\cdots+L_{i-1}+L_{i+1})+p_i(L_1+\cdots+L_{i+1}) +\cdots. $$ iZMENENIE RAVNO $p_iL_{i+1}-p_{i+1}L_i$. tAK KAK RASPOLOZHENIE (19) OPTIMALXNO, TO $p_iL_{i+1}-p_{i+1}L_i\ge 0$. zNACHIT, $p_i/L_i\ge p_{i+1}/L_{i+1}$, T. E. (20) VYPOLNYAETSYA. dOKAZHEM TEPERX DOSTATOCHNOSTX USLOVIYA (20). rAZUMEETSYA, "LOKALXNAYA" OPTIMALXNOSTX RASPOLOZHENIYA (19) VIDNA SRAZU: ESLI MY POMENYAEM MESTAMI DVE ZAPISI, VREMYA POISKA IZMENITSYA NA $p_iL_{i+1}-p_{i+1}L_i\ge 0$. oDNAKO "GLOBALXNAYA" OPTIMALXNOSTX TREBUET OBOSNOVANIYA. mY RASSMOTRIM DVA DOKAZATELXSTVA: ODNO IZ NIH ISPOLXZUET DISKRETNUYU MATEMATIKU, A DRUGOE PREDPOLAGAET NEKOTORUYU MATEMATICHESKUYU IZVOROTLIVOSTX. \proof\ 1. pUSTX (20) VYPOLNYAETSYA. mY ZNAEM, CHTO LYUBUYU PERESTANOVKU ZAPISEJ MOZHNO "OTSORTIROVATX", T. E. PRIVESTI K RASPOLOZHENIYU $R_1$, $R_2$, \dots, $R_N$, POSLEDOVATELXNO MENYAYA MESTAMI LISHX SOSEDNIE |LEMENTY. kAZHDOE TAKOE IZMENENIE PEREVODIT \dots$R_j$ $R_i$\dots V \dots$R_i$ $R_j$\dots DLYA NEKOTORYH $i0$ I~$y0$; $N=2k+m+1$. pOKAZHITE, CHTO DRUGOE RASPOLOZHENIE $q'_1$ $q'_2$~\dots $q'_k$ $s$ $r'_k$~\dots $r'_2$ $r'_1$ $t_1$~\dots $t_m$ LUCHSHE, ESLI $q'_i=\min(q_i, r_i)$ I~$r'_i=\max(q_i, r_i)$ (ISKLYUCHAYA SLUCHAJ $q'_i=q_i$ I~$r'_i=r_i$ DLYA VSEH~$i$ I SLUCHAJ $q'_i=r_i$, $r'_i=q_i$, $t_j=0$ DLYA VSEH~$i$ I~$j$). uTVERZHDENIE VERNO I PRI OTSUTSTVII $s$, KOGDA $N=2k+m$.] \ex[m20] (pRODOLZHENIE UPR.~18.) pUSTX FUNKCIYA~$d(i,j)$ OBLADAET SVOJSTVOM $d(i,j)+d(j,i)=c$ DLYA VSEH~$i$ I~$j$. nAJDITE OPTIMALXNOE RASPOLOZHENIE DLYA SCEPLENNYH POISKOV. [tAKAYA SITUACIYA VSTRECHAETSYA PRI POISKE NA LENTAH, KOGDA NE PREDUSMOTRENA VOZMOZHNOSTX CHITATX V OBRATNOM NAPRAVLENII I MY NE ZNAEM NUZHNOGO NAPRAVLENIYA POISKA; PRI $i