\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_1<K_2<\ldots<K_N$. aLGORITM PREDNAZNACHAETSYA DLYA POISKA DANNOGO KLYUCHA $K$. 
v CELYAH UDOBSTVA I UVELICHENIYA SKOROSTI RABOTY PREDPOLAGAETSYA, CHTO V KONCE 
TABLICY RASPOLOZHENA FIKTIVNAYA ZAPISX $R_{N+1}$, KLYUCH KOTOROJ 
$K_{N+1}=\infty>K$.
\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 $i<j$, 
T. E. UMENXSHAET VREMYA POISKA NA NEOTRICATELXNUYU VELICHINU 
$p_iL_j-p_jL_i$. zNACHIT,  PORYADOK $R_1$  $R_2$ \dots $R_N$ OPTIMALEN.

\proof\ 2. zAMENIM VEROYATNOSTI $p_i$ NA
$$
p_i(\varepsilon)=p_i+\varepsilon^i-(\varepsilon^1+\varepsilon^2+\cdots
+\varepsilon^N)/N,
$$
GDE $\varepsilon$---MALAYA POLOZHITELXNAYA VELICHINA. rAVENSTVO 
$x_1p_1(\varepsilon) +\cdots+x_Np_N(\varepsilon)
=y_1p_1(\varepsilon)+\cdots+y_Np_N(\varepsilon)$ VYPOLNYAETSYA DLYA 
DOSTATOCHNO MALYH $\varepsilon$ LISHX PRI $x_1=y_1$, \dots, $x_N=y_N$;
 V CHASTNOSTI, V (20) STANUT NEVOZMOZHNYMI RAVENSTVA 
${p_i\over L_i}={p_j\over L_j}$ rASSMOTRIM $N!$
PERESTANOVOK ZAPISEJ. sREDI NIH ESTX PO KRAJNEJ MERE ODNA OPTIMALXNAYA; V 
SILU PERVOJ CHASTI TEOREMY ONA UDOVLETVORYAET (20), NO V SILU OTSUTSTVIYA 
RAVENSTV USLOVIYU (20) UDOVLETVORYAET LISHX ODNA PERESTANOVKA. tAKIM 
OBRAZOM, (20) ODNOZNACHNO OPREDELYAET OPTIMALXNOE RASPOLOZHENIE ZAPISEJ V 
TABLICE DLYA VEROYATNOSTEJ $p_i(\varepsilon)$ PRI DOSTATOCHNO MALYH 
$\varepsilon$. pO NEPRERYVNOSTI |TOT ZHE PORYADOK OPTIMALEN I PRI 
$\varepsilon$. (tAKOJ METOD DOKAZATELXSTV CHASTO ISPOLXZUETSYA V 
KOMBINATORNOJ OPTIMIZACII.)
\proofend

tEOREMA S PRINADLEZHIT u. e. sMITU [{\sl Naval Research Logistics 
Quarterly\/}, {\bf 3} (1956), 59--66]. uPRAZHNENIYA SODERZHAT 
DOPOLNITELXNYE REZULXTATY PO OPTIMALXNOJ ORGANIZACII TABLIC.
%% 479
\section uPLOTNENIE FAJLOV. pOSLEDOVATELXNYJ POISK NA LENTE I DRUGIH 
VNESHNIH ZAPOMINAYUSHCHIH USTROJSTVAH PROTEKAET BYSTREE;
ESLI DANNYE ZANIMAYUT MENXSHE MESTA, PO|TOMU POLEZNO RASSMOTRETX NESKOLXKO 
RAZLICHNYH SPOSOBOV PREDSTAVLENIYA DANNYH V TABLICE. nE VSEGDA NUZHNO 
ZAPOMINATX KLYUCHI V YAVNOM VIDE.

pUSTX, NAPRIMER, TREBUETSYA TABLICA PROSTYH CHISEL DO MILLIONA DLYA 
RAZLOZHENIYA NA MNOZHITELI 12-ZNACHNYH CHISEL. (sR. S P.~4.5.4.) tAKIH CHISEL 
IMEETSYA 78498; ISPOLXZUYA 20 BITOV DLYA KAZHDOGO IZ NIH, MY POLUCHIM FAJL 
DLINY 1\ 569\ 960 BITOV. eTO YAVNOE RASTOCHITELXSTVO, TAK KAK MOZHNO IMETX 
MILLION-BITOVUYU TABLICU, V KOTOROJ RAZRYADY, SOOTVETSTVUYUSHCHIE PROSTYM CHISLAM,
 RAVNY 1. pOSKOLXKU VSE PROSTYE CHISLA (KROME DVOJKI) NECHETNY, DOSTATOCHNO 
IMETX TABLICU V 500000 BITOV.

dRUGIM SPOSOBOM UMENXSHENIYA DLINY FAJLA YAVLYAETSYA HRANENIE NE SAMIH 
PROSTYH CHISEL, A INTERVALOV MEZHDU NIMI. v SOOTVETSTVII S TABL.~1 VELICHINA 
$(p_{k+1}-p_k)/2$ MENXSHE 64 DLYA VSEH PROSTYH CHISEL V PREDELAH 1\ 357\ 201, 
T. E. NAM DOSTATOCHNO ZAPOMNITX 78\ 496 SHESTIRAZRYADNYH CHISEL (RAZMER 
INTERVALA)/2. tAKAYA TABLICA IMEET DLINU PRIMERNO 471\ 000 BITOV. 
dALXNEJSHEGO UPLOTNENIYA MOZHNO DOBITXSYA, ISPOLXZUYA DLYA 
PREDSTAVLENIYA INTERVALOV DVOICHNYE KODY PEREMENNOJ DLINY (SR. S P~ 6.2.2).
\htable{tABLICA 1}%
{tABLICA INTERVALOV MEZHDU POSLEDOVATELXNYMI PROSTYMI CHISLAMI}%
{\strut\hfill#\hfill&\hfill#\hfill&\vrule\hfill#\hfill&\hfill#\hfill\cr
iNTERVAL $(p_{k+1}-p_k)$ & $p_k$  & iNTERVAL $(p_{k+1}-p_k)$ & $p_k$ \cr
 1 &     2 &  52 &    19609 \cr
 2 &     3 &  72 &    31397 \cr
 4 &     7 &  86 &   155921 \cr
 6 &    23 &  96 &   360653 \cr
 8 &    89 & 112 &   370261 \cr
14 &   113 & 114 &   492113 \cr
18 &   523 & 118 &  1349533 \cr
20 &   887 & 132 &  1357201 \cr
23 &  1129 & 148 &  2010733 \cr
34 &  1327 & 154 &  4652353 \cr
36 &  9551 & 180 & 17051707 \cr
44 & 15683 & 310 & 20831323 \cr
}
v TABLICE POMESHCHENY INTERVALY $p_{k+1}-p_k$, PREVYSHAYUSHCHIE $p_{j+1}-p_j$ 
DLYA VSEH $j<k$. bOLEE PODROBNO SM. F. Gruenberger, G. Armerding, 
"Statistics on the first six million prime numbers", RAND Corp. report 
P-2460 (October, 1961).

%% 480

\excercises
\ex[m20] pUSTX VSE KLYUCHI, PO KOTORYM PROVODITSYA POISK, 
RAVNOVEROYATNY. oPREDELITE SREDNEKVADRATICHNOE OTKLONENIE CHISLA SRAVNENIJ 
PRI UDACHNOM POISKE V TABLICE IZ $N$~ZAPISEJ.

\ex[16] iZMENITE ALGORITM~S, PRISPOSOBIV EGO DLYA RABOTY S TABLICAMI V 
SVYAZANNOM PREDSTAVLENII. (eSLI |P| UKAZYVAET NA ZAPISX V TABLICE, TO 
PREDPOLAGAETSYA, CHTO $|KEY|(|P|)$ ESTX KLYUCH, 
$|INFO|(|P|)$---ASSOCIIROVANNAYA INFORMACIYA I~$|LINK|(|P|)$---UKAZATELX NA 
SLEDUYUSHCHUYU ZAPISX. kROME TOGO, PREDPOLAGAETSYA, CHTO |FIRST| UKAZYVAET NA 
PERVUYU ZAPISX, A POSLEDNYAYA ZAPISX UKAZYVAET NA~$\NULL$.)

\ex[16] nAPISHITE \MIX-PROGRAMMU DLYA ALGORITMA UPR.~2. vYRAZITE 
VREMYA RABOTY VASHEJ PROGRAMMY CHEREZ VELICHINY~$C$ I~$S$, OPREDELENNYE V~(1). 
\rex[17] pRIMENIMA LI IDEYA ALGORITMA~Q K TABLICAM V SVYAZANNOM 
PREDSTAVLENII? (sR. S UPR.~2.)

\ex[20] pROGRAMMA~$Q'$, RAZUMEETSYA, ZAMETNO BYSTREE PROGRAMMY~Q 
PRI BOLXSHIH~$C$. sUSHCHESTVUYUT LI MALYE VELICHINY~$C$ I~$S$, PRI KOTORYH 
PROGRAMMA~$Q'$ TREBUET BOLXSHE VREMENI, CHEM~Q?

\rex[20] uVELICHIV PROGRAMMU~$Q'$ NA TRI KOMANDY, SVEDITE VREMYA EE RABOTY 
K $(3.33C+\hbox{\rm const}) u$.

\ex[m20] oPREDELITE SREDNEE CHISLO SRAVNENIJ (3), ISPOLXZUYA 
"BINARNOE" RASPREDELENIE (5).

\ex[vm22] nAJDITE ASIMPTOTICHESKIJ RYAD DLYA $H^{(x)}_n$ PRI~$n\to\infty$; $x\ne1$.

\rex[m23] v TEKSTE ZAMECHENO, CHTO RASPREDELENIYA VEROYATNOSTEJ~(11) 
I~(13) PRIBLIZITELXNO |KVIVALENTNY I CHTO SREDNEE CHISLO SRAVNENIJ V~(13) 
RAVNO $\theta N/(\theta+1)+O(N^{1-\theta})$. rAVNO LI |TOMU ZHE CHISLU 
SREDNEE CHISLO SRAVNENIJ PRI ISPOLXZOVANII RASPREDELENIYA~(11)?

\ex[m20] nAILUCHSHEE RASPOLOZHENIE ZAPISEJ V TABLICE OPREDELYAETSYA 
FORMULOJ~(4); KAKOVO \emph{NAIHUDSHEE} RASPOLOZHENIE? pOKAZHITE, CHTO 
SREDNIE CHISLA SRAVNENIJ PRI NAIHUDSHEM I NAILUCHSHEM RASPOLOZHENIYAH SVYAZYVAET PROSTOE SOOTNOSHENIE.

\ex[m30] cELXYU |TOGO UPRAZHNENIYA YAVLYAETSYA ANALIZ POVEDENIYA 
SAMOORGANIZUYUSHCHEGOSYA FAJLA. sNACHALA NEOBHODIMO VVESTI DOVOLXNO SLOZHNYE 
OBOZNACHENIYA. pOLOZHIM $f_m(x_1, x_2,~\ldots, x_m)$ RAVNYM BESKONECHNOJ 
SUMME VSEH RAZLICHNYH UPORYADOCHENNYH PROIZVEDENII $x_{i_1}x_{i_2}\ldots 
x_{i_k}$, GDE $1\le i_1$,~\dots, $i_k\le m$ I KAZHDOE $x_i$, $1\le i\le m$, 
VHODIT VO VSE PROIZVEDENIYA. nAPRIMER,
$$
f_2(x,y)=\sum_{j,k\ge 0} (x^{1+j}y(x+y)^k+y^{1+j}x(x+y)^k)=
{xy\over 1-x-y}\left({1\over 1-x}+{1\over 1-y}\right).
$$
iMEYA MNOZHESTVO $X=\{\, x_1,~\ldots, x_n\,\}$ IZ $n$~PEREMENNYH, POLOZHIM
$$
\eqalign{
P_{nm}&=\sum_{1\le j_1<\ldots<j_m\le n} f_m(x_{j_1},~\ldots, x_{j_m});\cr
Q_{nm}&=\sum_{1\le j_1<\ldots<j_m\le n}{1\over 1-x_{j_1}-\cdots-x_{j_m}}.\cr
}
$$
nAPRIMER, $P_{32}=f_2(x_1, x_2)+f_2(x_1, x_3)+f_2(x_2, x_3)$, 
A~$Q_{32}=1/(1-x_1-x_2)+1/(1-x_1-x_3)+1/(1-x_2-x_3)$. pO OPREDELENIYU 
POLAGAEM $P_{n0}=Q_{n0}=1$.

\item{a)} pREDPOLOZHIM, CHTO V SAMOORGANIZUYUSHCHIJSYA FAJL ZAPROSY NA 
|LEMENT~$R_i$ POSTUPAYUT S VEROYATNOSTXYU~$p_i$. pOKAZHITE, CHTO POSLE 
DLITELXNOJ RABOTY SISTEMY |LEMENT~$R_i$ OKAZHETSYA NA $m\hbox{-M}$~MESTE OT 
NACHALA FAJLA S PREDELXNOJ VEROYATNOSTXYU~$p_iP_{N-1, m-1}$, GDE $X=\{\,p_1,
~\ldots, p_{i-1}, p_{i+1},~\ldots, p_N\,\}$.

\item{b)} sUMMIRUYA REZULXTAT (a) PRI $m=1$, 2,~\dots, POLUCHAEM TOZHDESTVO
$$
P_{nn}+P_{n,n-1}+\cdots+P_{n0}=Q_{nn}.
$$
%%481
vYVEDITE OTSYUDA, CHTO
$$
\displaylines{
P_{nm}+\perm{n-m+1}{1}P_{n,m-1}+\cdots+\perm{n-m+m}{m}P_{n0}=Q_{nm};\cr
Q_{nm}-\perm{n-m+1}{1}Q_{n,m-1}+\cdots+(-1)^m\perm{n-m+m}{m}Q_{n0}=P_{nm}.\cr
}
$$
\item{c)} pODSCHITAJTE PREDEL SREDNEGO RASSTOYANIYA $d_i=\sum_{m\ge1} 
mp_iP_{N-1,m-1}$ |LEMENTA~$R_i$ OT NACHALA TABLICY; ZATEM NAJDITE 
$\overline{C}_N=\sum_{1\le i\le n} p_id_i$.

\ex[m23] iSPOLXZUYA~(17), OPREDELITE SREDNEE CHISLO SRAVNENIJ, TREBUEMYH 
PRI POISKE V SAMOORGANIZUYUSHCHEMSYA FAJLE, ESLI ISKOMYE KLYUCHI IMEYUT BINARNOE RASPREDELENIE~(5).

\ex[m27] iSPOLXZUYA~(17), OPREDELITE $\overline{C}_N$ V SLUCHAE RASPREDELENIYA~(6).

\ex[m21] iMEYUTSYA DVE POSLEDOVATELXNOSTI DEJSTVITELXNYH CHISEL 
$\langle x_1, x_2, \ldots, x_n\rangle$ I $\langle y_1, y_2, \ldots, 
y_n\rangle$. kAKAYA PERESTANOVKA INDEKSOV $a_1$, $a_2$,~\dots, $a_n$ DELAET 
SUMMU $\sum x_i y_{a_i}$ MAKSIMALXNOJ? MINIMALXNOJ?

\rex[m22] v TEKSTE POKAZANO, KAK OPTIMALXNO RASPOLOZHITX NA LENTE PROGRAMMY 
SISTEMNOJ BIBLIOTEKI, KOGDA RAZYSKIVAETSYA TOLXKO ODNA PROGRAMMA. pRI 
ISSLEDOVANII RABOTY S LENTOJ, SODERZHASHCHEJ BIBLIOTEKU \emph{PODPROGRAMM,} 
NUZHNY DRUGIE PREDPOLOZHENIYA, TAK KAK TREBUETSYA ZAGRUZHATX RAZLICHNOE CHISLO 
PODPROGRAMM, VYZYVAEMYH IZ PROGRAMMY POLXZOVATELYA.

v |TOM SLUCHAE PREDPOLOZHCHM, CHTO K |LEMENTU~$i$ OBRASHCHAYUTSYA S 
VEROYATNOSTXYU~$P_i$ NEZAVISIMO OT TOGO, TREBUYUTSYA ILI NET DRUGIE 
PODPROGRAMMY. nAPRIMER, VEROYATNOSTX TOGO, CHTO NET NI ODNOGO OBRASHCHENIYA, 
RAVNA $(1-P_1)(1-P_2)\ldots(1-P_N)$; VEROYATNOSTX OKONCHANIYA POISKA SRAZU 
POSLE ZAGRUZKI $i\hbox{-GO}$~|LEMENTA SOSTAVLYAET 
$P_i(1-P_{i+1})\ldots(1-P_N)$. eSLI CHEREZ~$L_i$ OBOZNACHITX 
DLINU $i\hbox{-J}$ PODPROGRAMMY, TO SREDNEE VREMYA POISKA BUDET 
PROPORCIONALXNO VELICHINE
$$
L_1P_1(1-P_2)\ldots(1-P_N)+(L_1+L_2)P_2(1-P_3)\ldots(1-P_N)+\cdots(L_1+\cdots+L_N)P_N
$$
kAKIM BUDET V |TIH PREDPOLOZHENIYAH OPTIMALXNOE RASPOLOZHENIE PODPROGRAMM NA LENTE?

\ex[m22] (g. rIZELX.) pROGRAMMIST HOCHET PROVERITX, VYPOLNYAYUTSYA 
LI ODNOVREMENNO $n$~DANNYH USLOVIJ. (nAPRIMER, ON ZHELAET ZNATX, VERNO LI, 
CHTO $x>0$ I~$y<z^2$, NO SRAZU NE YASNO, KAKOE IZ USLOVIJ NUZHNO PROVERITX 
PERVYM ) pREDPOLOZHIM, CHTO PROVERKA USLOVIYA~$i$ ZANIMAET $T_i$~EDINIC 
VREMENI, VEROYATNOSTX VYPOLNENIYA USLOVIYA~$i$ RAVNA~$p_i$ I NE ZAVISIT OT 
ISHODOV DRUGIH PROVEROK. v KAKOM PORYADKE DOLZHNY PROIZVODITXSYA PROVERKI?

\ex[m23] (u. e. sMIT.) pREDPOLOZHIM, CHTO IMEETSYA $n$~RABOT, PRICHEM 
$i\hbox{-YA}$ TREBUET $T_i$~EDINIC VREMENI I IMEET \emph{KRAJNIJ SROK 
OKONCHANIYA $D_i$.} dRUGIMI SLOVAMI, PREDPOLAGAETSYA, CHTO $i\hbox{-YA}$~RABOTA 
DOLZHNA BYTX ZAKONCHENA NE POZDNEE VREMENI~$D_i$. sOSTAVXTE RASPISANIE RABOT,
 MINIMIZIRUYUSHCHEE \emph{MAKSIMALXNOE ZAPAZDYVANIE}, T. E.
$$
\max(T_{a_1}-D_{a_1}, T_{a_1}+T_{a_2}-D_{a_2}, \ldots, T_{a_1}+T_{a_2}+\cdots+T_{a_n}-D_{a_n}).
$$
\ex[m30]\exhead(sCEPLENNYJ POISK.) pREDPOLOZHIM, CHTO $N$~ZAPISEJ 
RASPOLOZHENY V VIDE LINEJNOGO MASSIVA $R_1$,~\dots, $R_N$ I ZAPISX~$R_i$ 
BUDET RAZYSKIVATXSYA S VEROYATNOSTXYU~$p_i$. pOISKOVYJ PROCESS NAZYVAETSYA 
"SCEPLENNYM", ESLI KAZHDYJ SLEDUYUSHCHIJ POISK NACHINAETSYA S MESTA OKONCHANIYA 
PREDYDUSHCHEGO. eSLI IDUSHCHIE DRUG ZA DRUGOM POISKI NEZAVISIMY, TO V SREDNEM TREBUETSYA
$\sum_{1\le i,j\le N} p_ip_j d(i,j)$~EDINIC VREMENI, GDE CHEREZ $d(i,j)$ 
OBOZNACHEN PROMEZHUTOK VREMENI, TREBUYUSHCHIJSYA NA POISK OT~$i\hbox{-J}$ DO 
$j\hbox{-J}$ POZICII. eTA MODELX
%%482
PRIMENIMA, NAPRIMER, K POISKU NA DISKE [$d(i,j)$---VREMYA PEREMESHCHENIYA 
MEZHDU $i\hbox{-M}$ I~$j\hbox{-M}$ CILINDRAMI].

rEZULXTATY DANNOGO UPRAZHNENIYA POZVOLYAYUT OHARAKTERIZOVATX OPTIMALXNOE 
RASPOLOZHENIE ZAPISEJ PRI SCEPLENNOM POISKE. rASSMOTRIM SLUCHAJ, KOGDA $d(i,
j)$ ESTX VOZRASTAYUSHCHAYA FUNKCIYA OT~$\abs{i-j}$, T.~E. $d (i,
j)=d_{\abs{i-j}}$;  $d_1<d_2<\ldots<d_{N-1}$. (zNACHENIE~$d_0$ 
BEZRAZLICHNO.) dOKAZHITE, CHTO V DANNOM SLUCHAE RASPOLOZHENIE ZAPISEJ 
$R_1$~\dots $R_N$ BUDET NAILUCHSHIM SREDI VSEH $N!$~PERESTANOVOK TOGDA I 
TOLXKO TOGDA, KOGDA ILI 
$p_1\le p_N\le p_2\le p_{N-1}\le \ldots\le p_{\floor{N/2}+1}$,
\picture {rIS. 2.rASPOLOZHENIE V VIDE ORGANNYH TRUB MINIMIZIRUET SREDNEE 
VREMYA SCEPLENNOGO POISKA.}
ILI $p_N\le p_1\le p_{N-1}\le p_2\le \ldots\le p_{\ceil{N/2}}$. (zNACHIT, 
POKAZANNOE NA RIS.~2 RASPOLOZHENIE V VIDE "ORGANNYH TRUB" OPTIMALXNO.) 
[\emph{uKAZANIE.} rASSMOTRITE PROIZVOLXNOE RASPOLOZHENIE, KOTOROMU 
SOOTVETSTVUYUT VEROYATNOSTI $q_1$  $q_2$~\dots $q_k$ $s$ $r_k$~\dots $r_2$ 
$r_1$ $t_1$~\dots $t_m$, $m\ge0$, $k>0$; $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<j$ IMEEM $d(i,
j)=a+b(L_{i+1}+\cdots+L_j)$ I~$d(j,
i)=a+b(L_{j+1}+\cdots+L_N)+r+b(L_1+\cdots+L_i)$, GDE $r$---VREMYA PEREMOTKI 
LENTY. ]

\ex[m28] (pRODOLZHENIE UPR.~18.) nAJDITE OPTIMALXNYJ PORYADOK ZAPISEJ DLYA 
SCEPLENNYH POISKOV, ESLI $d(i,j)=\min(d_{\abs{i-j}}, d_{n-\abs{i-j}})$ 
I~$d_1<d_2<\ldots$. [tAKAYA MODELX PRIMENIMA DLYA ISSLEDOVANIYA POISKA V 
CIKLICHESKOM SPISKE S DVUMYA SVYAZYAMI ILI ZAPOMINAYUSHCHEM USTROJSTVE S 
VOZMOZHNOSTXYU SDVIGA V OBE STORONY.]

\ex[m28] rASSMOTRIM $n\hbox{-MERNYJ}$ KUB, VERSHINY KOTOROGO IMEYUT 
KOORDINATY $(d_n,~\ldots, d_1)$, $d_i=0$ ILI~1. dVE VERSHINY NAZYVAYUTSYA 
\dfn{SOSEDNIMI}, ESLI U NIH RAZLICHAYUTSYA TOCHNO PO ODNOJ KOORDINATE. 
pREDPOLOZHIM, CHTO $2^n$ CHISEL $x_0\le x_1\le\ldots\le x_{2^n-1}$ DOLZHNY 
BYTX POSTAVLENY V SOOTVETSTVIE $2^n$~VERSHINAM TAK, CHTOBY 
SUMMA~$\sum\abs{x_i-x_j}$ BYLA MINIMALXNA; SUMMA BERETSYA PO VSEM~$i$ I~$j$,
 TAKIM, CHTO $x_i$ I~$x_j$ POSTAVLENY V SOOTVETSTVIE SOSEDNIM VERSHINAM. 
dOKAZHITE, CHTO MINIMUM DOSTIGAETSYA, KOGDA PRI VSEH~$i$ ZNACHENIE~$x_i$ 
PRISVOENO VERSHINE, KOORDINATY KOTOROJ YAVLYAYUTSYA DVOICHNYM PREDSTAVLENIEM~$i$.

\rex[20] pREDPOLOZHIM, CHTO V BOLXSHOM FAJLE NUZHNO NAJTI 1000 
\emph{BLIZHAJSHIH} K DANNOMU KLYUCHU ZAPISEJ, T.~E. 1000~ZAPISEJ, PRIDAYUSHCHIH 
NAIMENXSHIE ZNACHENIYA NEKOTOROJ FUNKCII RASSTOYANIYA $d(K_i, K)$. kAKAYA 
STRUKTURA DANNYH LUCHSHE VSEGO PODHODIT DLYA POSLEDOVATELXNOGO POISKA V |TOM 
SLUCHAE?

%% 483
\bye
