\input style
\hyphenation{AV-TO-MO-BI-LEJ}
%% 4
\UDC{681.142.2}
\vfill

tRETIJ TOM IZVESTNOJ MONOGRAFII ODNOGO IZ KRUPNEJSHIH AMERIKANSKIH SPECIALISTOV PO 
PROGRAMMIROVANIYU d. kNUTA (PERVYJ TOM VYSHEL V IZDATELXSTVE \rlq{}mIR\rrq{} V 1976 G., 
VTOROJ---V 1977 G.) SOSTOIT IZ DVUH CHASTEJ: \rlq{}sORTIROVKA\rrq{} I \rlq{}pOISK\rrq{}. v NIH 
PODROBNO ISSLEDUYUTSYA RAZLICHNYE ALGORITMY VNUTRENNEJ I VNESHNEJ SORTIROVKI, IZUCHAYUTSYA 
METODY POISKA INFORMACII V TABLICAH NA OSNOVE SRAVNENIE ILI PREOBRAZOVANIYA KLYUCHEJ, 
DAYUTSYA OCENKI |FFEKTIVNOSTI PREDLAGAEMYH ALGORITMOV. kNIGA SNABZHENA BOLXSHIM 
KOLICHESTVOM ZADACH I PRIMEROV RAZNOJ STEPENI TRUDNOSTI, SUSHCHESTVENNO DOPOLNYAYUSHCHIH 
OSNOVNOJ TEKST.

oT DRUGIH RUKOVODSTV PO PROGRAMMIROVANIYU KNIGA VYGODNO OTLICHAETSYA STROGOSTXYU 
IZLOZHENIYA I SHIROKIM PRIMENENIEM MATEMATICHESKOGO APPARATA. vMESTE S TEM ONA DOSTUPNA 
STUDENTAM PERVOGO KURSA. zNAKOMSTVO S DVUMYA PERVYMI TOMAMI ZHELATELXNO, NO NE 
OBYAZATELXNO. kAZHDYJ, KTO HOCHET NAUCHITXSYA KVALIFICIROVANNO PROGRAMMIROVATX, NAJDET V 
NEJ MNOGO POLEZNOGO.

rASSCHITANA NA SHIROKIJ KRUG PROGRAMMISTOV.
\vfill
\vfill
\centerline{{\it rEDAKCIYA LITERATURY PO MATEMATICHESKIM NAUKAM}}

\line{$k{20204-022\over 041(01)-78}22-78$   \hfill   \copyright\ pEREVOD NA RUSSKIJ 
YAZYK, \rlq{}mIR\rrq{}. 1978}
\eject
%% 5
\chapter{predislovie redaktorov perevoda}
d. e. kNUT HOROSHO ZNAKOM SOVETSKOMU CHITATELYU PO PEREVODAM DVUH PERVYH TOMOV EGO 
OBSHIRNOJ MONOGRAFII "iSKUSSTVO PROGRAMMIROVANIYA DLYA evm" I NE NUZHDAETSYA V 
ATTESTACII. nASTOYASHCHAYA KNIGA PREDSTAVLYAET SOBOJ TRETIJ TOM I POSVYASHCHENA ALGORITMAM 
SORTIROVKI I POISKA INFORMACII.

iSTORICHESKI ZAROZHDENIE METODOV MASHINNOJ SORTIROVKI MOZHNO OTNESTI ESHCHE K PROSHLOMU 
STOLETIYU, I ZA STOLX DLITELXNOE VREMYA MNOGIE SPECIALISTY USPELI ISPROBOVATX SVOI SILY V 
|TOJ OBLASTI. nAPISANO NEMALO OTCHETOV, STATEJ, MONOGRAFIJ. i DAZHE V |TIH USLOVIYAH KNIGA 
d. kNUTA STALA SOBYTIEM. pO SUSHCHESTVU |TO |NCIKLOPEDIYA, V KOTOROJ MOZHNO NAJTI LYUBUYU 
SPRAVKU, KASAYUSHCHUYUSYA ALGORITMOV, METODOV IH OCENOK, ISTORII VOPROSA I NERESHENNYH 
PROBLEM.    

nET NUZHDY GOVORITX O VAZHNOSTI SAMOJ OBLASTI. pRAKTICHESKI SORTIROVKA I POISK V TOJ 
ILI INOJ MERE PRISUTSTVUYUT VO VSEH PRILOZHENIYAH; V CHASTNOSTI, PRI OBRABOTKE BOLXSHIH 
OB�EMOV DANNYH |FFEKTIVNOSTX IMENNO |TIH OPERACIJ OPREDELYAET |FFEKTIVNOSTX, A INOGDA I 
RABOTOSPOSOBNOSTX VSEJ SISTEMY. pO|TOMU, KAK SPRAVEDLIVO OTMECHAET AVTOR, KNIGA 
ADRESOVANA NE TOLXKO SISTEMNYM PROGRAMMISTAM, ZANIMAYUSHCHIMSYA RAZRABOTKOJ PROGRAMM 
SORTIROVKI I POISKA INFORMACII. mOZHNO SKAZATX, CHTO DOSTATOCHNO CHETKIE PREDSTAVLENIYA OB 
|TOJ OBLASTI NUZHNY PRI RESHENII LYUBOJ ZADACHI NA evm KAK OBYAZATELXNYE |LEMENTY 
ISKUSSTVA PROGRAMMIROVANIYA.

kROME TEORETICHESKOJ I PRAKTICHESKOJ CENNOSTI, KNIGA IMEET BOLXSHOE METODICHESKOE 
ZNACHENIE. mNOGIE AVTORY I PREPODAVATELI SMOGUT IZVLECHX IZ NEE NOVYE I POLEZNYE SVEDENIYA 
NE TOLXKO PO SUSHCHESTVU RASSMATRIVAEMYH VOPROSOV, NO I PO SPOSOBU IH IZLOZHENIYA. aVTORU 
MASTERSKI UDAETSYA "RASSLOITX" VESX MATERIAL TAKIM OBRAZOM, CHTO KNIGU MOZHNO ISPOLXZOVATX 
PRAKTICHESKI NA LYUBOM UROVNE ZNAKOMSTVA S PREDMETOM I PRI RAZLICHNOJ OBSHCHEJ 
MATEMATICHESKOJ PODGOTOVLENNOSTI CHITATELYA.

pEREVOD VYPOLNEN PO IZDANIYU 1973 G. (PERVAYA REDAKCIYA) S VNESENIEM MNOGIH (OKOLO 700) 
ISPRAVLENIJ I DOBAVLENIJ, LYUBEZNO PREDOSTAVLENNYH AVTOROM. rAZDELY S 5.1 PO 5.3.2 PERE-
VEDENY. n. i. vXYUKOVOJ; RAZDELY S 5.3.3 PO 5.5 I PREDISLOVIE--- a. b. hODULEVYM; GLAVU B 
PEREVEL v. a. gALATENKO.
\rightline{yu. m. bAYAKOVSKIJ}
\rightline{ v. s. shTARKMAN}
%% 6
\chapter{predislovie}
\epigraph
kULINARIYA STALA ISKUSSTVOM, VYSOKOJ NAUKOJ;\nl
POVARA TEPERX---BLAGORODNYE LYUDI.
\signed
tIT lIVIJ, a' Urbe Condita, XXXIX.vi\nl
(rOBERT bERTON, Anatomy of Melancholy, 1.2.2.2)%
\note{1}{ rOBERT bERTON (1577--1640) --- ANGLIJSKIJ UCHENYJ, PISATELX I TEOLOG.  
{\sl pRIM. pEREV.\/}}

mATERIAL |TOJ KNIGI LOGICHESKI PRODOLZHAET MATERIAL PO INFORMACIONNYM STRUKTURAM, 
IZLOZHENNYJ V GL. 2, POSKOLXKU ZDESX K UZHE RASSMOTRENNYM KONCEPCIYAM STRUKTUR DOBAVLYAETSYA 
PONYATIE LINEJNO UPORYADOCHENNYH DANNYH. pODZAGOLOVOK "sORTIROVKA I POISK" MOZHET 
PRIVESTI K MYSLI, CHTO |TA KNIGA PREDNAZNACHENA LISHX DLYA SISTEMNYH PROGRAMMISTOV, 
ZANIMAYUSHCHIHSYA POSTROENIEM UNIVERSALXNYH PROGRAMM SORTIROVKI ILI SVYAZANNYH S VYBORKOJ 
INFORMACII. oDNAKO V DEJSTVITELXNOSTI PREDMET SORTIROVKI I POISKA DAET NAM PREKRASNUYU 
OSNOVU DLYA OBSUZHDENIYA SHIROKOGO KLASSA VAZHNYH OBSHCHIH VOPROSOV:

kAK NAHODITX HOROSHIE ALGORITMY? 

kAK ULUCHSHATX DANNYE ALGORITMY I PROGRAMMY? 

kAK ISSLEDOVATX |FFEKTIVNOSTX ALGORITMOV MATEMATICHESKI? 

kAK RAZUMNO VYBRATX ODIN IZ NESKOLXKIH ALGORITMOV DLYA RESHENIYA KONKRETNOJ ZADACHI?

v KAKOM SMYSLE MOZHNO DOKAZATX, CHTO NEKOTORYE ALGORITMY YAVLYAYUTSYA "NAILUCHSHIMI IZ 
VOZMOZHNYH"? 

kAK TEORIYA VYCHISLENIJ SOGLASUETSYA S PRAKTICHESKIMI SOOBRAZHENIYAMI?

kAK |FFEKTIVNO ISPOLXZOVATX RAZLICHNYE VIDY VNESHNEJ PAMYATI---LENTY, BARABANY, 
DISKI---DLYA BOLXSHIH BAZ DANNYH?
%% 7
ya DUMAYU, CHTO NA SAMOM DELE V KONTEKSTE SORTIROVKI I POISKA VSTRECHAETSYA PRAKTICHESKI 
\emph{LYUBOJ} VAZHNYJ ASPEKT PROGRAMMIROVANIYA.

nASTOYASHCHIJ TOM SOSTOIT IZ GL.~5 I~6 MONOGRAFII. v GL.~5 RASSMATRIVAETSYA SORTIROVKA 
(UPORYADOCHENIE); |TO OCHENX BOLXSHAYA TEMA, ONA RAZBITA NA DVE GLAVNYE CHASTI---VNUTRENNYUYU I 
VNESHNYUYU SORTIROVKU. v |TU GLAVU VHODYAT TAKZHE DOPOLNITELXNYE RAZDELY, RAZVIVAYUSHCHIE 
VSPOMOGATELXNUYU TEORIYU PERESTANOVOK (\S~5.1) I TEORIYU OPTIMALXNYH ALGORITMOV 
SORTIROVKI (\S~5.3). v GL.~6 MY IMEEM DELO S POISKOM OPREDELENNOGO |LEMENTA V TABLICE ILI 
FAJLE; SODERZHIMOE |TOJ GLAVY PODRAZDELYAETSYA NA METODY POSLEDOVATELXNOGO POISKA, METODY 
POISKA SO SRAVNENIEM KLYUCHEJ, POISKA S ISPOLXZOVANIEM SVOJSTV CIFR, POISKA S POMOSHCHXYU 
"HESHIROVANIYA"; ZATEM RASSMATRIVAETSYA BOLEE SLOZHNAYA ZADACHA VYBORKI PO VTORICHNYM KLYUCHAM. 
oBE GLAVY PORAZITELXNO TESNO PEREPLETAYUTSYA MEZHDU SOBOJ, MEZHDU IH PREDMETAMI IMEYUTSYA 
BLIZKIE ANALOGII. v DOPOLNENIE K GL. 2 RASSMATRIVAYUTSYA DVA VAZHNYH VIDA INFORMACIONNYH 
STRUKTUR, A IMENNO PRIORITETNYE OCHEREDI (P.~5.2.3) I LINEJNYE SPISKI, PREDSTAVLYAEMYE 
POSREDSTVOM SBALANSIROVANNYH DEREVXEV (P.~6.2.3).

chITATELYU, NE ZNAKOMOMU S PERVYM TOMOM |TOJ MONOGRAFII, REKOMENDUETSYA OBRASHCHATXSYA K 
UKAZATELYU OBOZNACHENIJ (PRILOZHENIE v), TAK KAK NEKOTORYE IZ VSTRECHAYUSHCHIHSYA V KNIGE 
OBOZNACHENIJ NE YAVLYAYUTSYA OBSHCHEPRINYATYMI.

eTA KNIGA BEZ BOLXSHEJ CHASTI MATEMATICHESKOGO MATERIALA BYLA ISPOLXZOVANA MNOJ V 
KACHESTVE UCHEBNIKA PO VTOROMU KURSU LEKCIJ "sTRUKTURY DANNYH" DLYA STUDENTOV
MLADSHIH I 
SREDNIH KURSOV. mATEMATICHESKIE CHASTI |TOJ KNIGI, OSOBENNO \S~5.1,
P.5.2.2, \S~6.3 I 6.4,  MOGLI BY SOSTAVITX UCHEBNIK PO ANALIZU ALGORITMOV
DLYA STUDENTOV SREDNIH I STARSHIH KURSOV.  kROME TOGO, NA OSNOVE P.~4.3.3,
4.6.3, 4.6.4, \S~5.3 I P.~5.4.4 MOZHNO POSTROITX KURS LEKCIJ 
"sLOZHNOSTX VYCHISLENIJ" DLYA STARSHEKURSNIKOV.

bYSTROE RAZVITIE INFORMATIKI I VYCHISLITELXNYH NAUK ZADERZHALO VYHOD V SVET |TOJ 
KNIGI POCHTYA NA TRI GODA, POSKOLXKU OCHENX MNOGIE ASPEKTY SORTIROVKI I POISKA PODVERGALISX 
DETALXNOJ RAZRABOTKE. ya OCHENX BLAGODAREN nACIONALXNOMU NAUCHNOMU FONDU, oTDELENIYU 
VOENNO-MORSKIH ISSLEDOVANIJ, iNSTITUTU OBORONY, FIRMAM IBM I Norges 
Almemitenskapelige Forskningsrad ZA POSTOYANNUYU PODDERZHKU MOIH
ISSLEDOVANIJ.

%% 8
v PODGOTOVKE |TOGO TOMA K PECHATI MNE OKAZALI POMOSHCHX MNOGIE LICA, OSOBENNO eDVARD a. 
bENDER, kLARK e. kR|JN, d|VID e. fERGYUSON, rOBERT u. fLOJD, rONALXD l. gR|HEM, lEONIDAS 
gYUIBA, dZHON hOPKROFT, rICHARD m. kARP, g|RI d. kNOTT, rUDOLXF a. kRUTAR, shENX lINX, 
vOGAN r. pRATT, sTEFAN o. rAJE, rICHARD p; sT|NLI, ya. a. VAN DER pUL I dZHON u. rENCH ML., A 
TAKZHE STUDENTY sT|NFORDA I bERKLI, KOTORYM PRISHLOSX ISKATX OSHIBKI V RUKOPISI.

\line{oSLO, nORVEGIYA, \hfill {\sl d. e. kNUT\/} SENTYABRX 1972}
\vskip 1 cm
\epigraph
pISATELX POLXZUETSYA IZVESTNYMI PRIVILEGIYAMI, V BLAGODETELXNOSTI KOTORYH, 
NADEYUSX, NET NIKAKIH OSNOVANIJ SOMNEVATXSYA. tAK, VSTRETIV U MENYA NEPONYATNOE 
MESTO, CHITATELX DOLZHEN PREDPOLOZHITX, CHTO POD NIM KROETSYA NECHTO VESXMA POLEZNOE 
I GLUBOKOMYSLENNOE%
\note{1}{pEREVOD a. a. fRANKOVSKOGO.---{\sl pRIM. pEREV.\/}}).
\signed (dZHONATAN sVIFT, sKAZKA BOCHKI, PREDISLOVIE, 1704)

%% 9
\chapter{zamechaniya ob uprazhneniyah}
uPRAZHNENIYA, POMESHCHENNYE V KNIGAH NASTOYASHCHEJ SERII, PREDNAZNACHENY 
KAK DLYA SAMOSTOYATELXNOJ PRORABOTKI, TAK I DLYA SEMINARSKIH ZANYATIJ. 
tRUDNO, ESLI NE NEVOZMOZHNO IZUCHITX PREDMET, TOLXKO CHITAYA TEORIYU I NE 
PRIMENYAYA POLUCHENNUYU INFORMACIYU DLYA RESHENIYA SPECIALXNYH ZADACH I TEM 
SAMYM NE ZASTAVLYAYA SEBYA OBDUMYVATX TO, CHTO BYLO PROCHITANO. kROME TOGO, 
MY LUCHSHE VSEGO ZAUCHIVAEM TO, CHTO SAMI OTKRYVAEM DLYA SEBYA. pO|TOMU 
UPRAZHNENIYA OBRAZUYUT VAZHNUYU CHASTX DANNOJ RABOTY; BYLI PREDPRINYATY 
OPREDELENNYE POPYTKI, CHTOBY OTOBRATX UPRAZHNENIYA, V KOTORYH BY 
SODERZHALOSX KAK MOZHNO BOLXSHE INFORMACII I KOTORYE BYLO BY INTERESNO 
RESHATX.

vO MNOGIH KNIGAH LEGKIE UPRAZHNENIYA DAYUTSYA VPEREMESHKU S 
ISKLYUCHITELXNO TRUDNYMI. zACHASTUYU |TO OCHENX NEUDOBNO, TAK KAK PERED TEM, 
KAK PRISTUPATX K RESHENIYU ZADACHI, CHITATELX OBYAZATELXNO DOLZHEN 
PREDSTAVLYATX SEBE, SKOLXKO VREMENI UJDET U NEGO NA |TO RESHENIE (INACHE ON 
MOZHET RAZVE TOLXKO PROSMOTRETX VSE ZADACHI). kLASSICHESKIM PRIMEROM ZDESX 
YAVLYAETSYA KNIGA rICHARDA bELLMANA "dINAMICHESKOE PROGRAMMIROVANIE"; |TO 
VAZHNAYA PIONERSKAYA RABOTA, V KOTOROJ V KONCE KAZHDOJ GLAVY POD RUBRIKOJ 
"uPRAZHNENIYA I ISSLEDOVATELXSKIE PROBLEMY" DAETSYA CELYJ RYAD ZADACH, GDE 
NARYADU S GLUBOKIMI ESHCHE NERESHENNYMI PROBLEMAMI VSTRECHAYUTSYA 
ISKLYUCHITELXNO TRIVIALXNYE VOPROSY. gOVORYAT, CHTO ODNAZHDY KTO-TO 
SPROSIL D-RA bELLMANA, KAK OTLICHITX UPRAZHNENIYA OT ISSLEDOVATELXSKIH 
PROBLEM, I TOT OTVETIL: "eSLI VY MOZHETE RESHITX ZADACHU, |TO---UPRAZHNENIE; 
V PROTIVNOM SLUCHAE |TO---PROBLEMA".

mOZHNO PRIVESTI MNOGO DOVODOV V POLXZU TOGO, CHTO V KNIGE TIPA |TOJ 
DOLZHNY BYTX KAK ISSLEDOVATELXSKIE PROBLEMY, TAK I OCHENX PROSTYE 
UPRAZHNENIYA, I DLYA TOGO CHTOBY CHITATELYU NE PRIHODILOSX LOMATX GOLOVU NAD 
TEM, KAKAYA ZADACHA LEGKAYA, A KAKAYA TRUDNAYA, MY VVELI "OCENKI", KOTORYE 
UKAZYVAYUT STEPENX TRUDNOSTI KAZHDOGO UPRAZHNENIYA. eTI OCENKI IMEYUT 
SLEDUYUSHCHEE ZNACHENIE:

\halign{
# & \vtop{\hsize=15cm \noindent#\par} \cr
\bf oCENKA & oB�YASNENIE \cr
00 & chREZVYCHAJNO LEGKOE UPRAZHNENIE, NA KOTOROE MOZHNO OTVETITX SRAZU   
ZHE, ESLI PONYAT MATERIAL TEKSTA, I KOTOROE POCHTI VSEGDA MOZHNO RESHITX "V 
UME". \cr
%% 10
10 & pROSTAYA ZADACHA, KOTORAYA ZASTAVLYAET ZADUMATXSYA NAD 
PROCHITANNYM MATERIALOM, NO NE PREDSTAVLYAET NIKAKIH 
OSOBYH TRUDNOSTEJ. nA RESHENIE TAKOJ ZADACHI TREBUETSYA NE 
BOLXSHE ODNOJ MINUTY; V PROCESSE RESHENIYA MOGUT 
PONADOBITXSYA KARANDASH I BUMAGA. \cr
20 & zADACHA SREDNEJ TRUDNOSTI, POZVOLYAYUSHCHAYA PROVERITX, NASKOLXKO 
HOROSHO PONYAT TEKST. nA TO CHTOBY DATX ISCHERPYVAYUSHCHIJ OTVET, TREBUETSYA 
PRIMERNO 15--20 MINUT.\cr
30 & zADACHA UMERENNOJ TRUDNOSTI I/ILI SLOZHNOSTI, DLYA 
UDOVLETVORITELXNOGO RESHENIYA KOTOROJ TREBUETSYA BOLXSHE DVUH CHASOV. \cr
40 & oCHENX TRUDNAYA ILI TRUDOEMKAYA ZADACHA, KOTORUYU, VEROYATNO, SLEDUET 
VKLYUCHITX V PLAN PRAKTICHESKIH ZANYATIJ. pREDPOLAGAETSYA, CHTO STUDENT MOZHET 
RESHITX TAKUYU ZADACHU, NO DLYA |TOGO EMU POTREBUETSYA ZNACHITELXNYJ OTREZOK 
VREMENI; ZADACHA RESHAETSYA NETRIVIALXNYM OBRAZOM. \cr
50 & iSSLEDOVATELXSKAYA PROBLEMA, KOTORAYA (NASKOLXKO |TO BYLO IZVESTNO 
AVTORU V MOMENT NAPISANIYA) ESHCHE NE POLUCHILA UDOVLETVORITELXNOGO 
RESHENIYA. eSLI CHITATELX NAJDET RESHENIE |TOJ ZADACHI, EGO NASTOYATELXNO 
PROSYAT OPUBLIKOVATX EGO; KROME TOGO, AVTOR DANNOJ KNIGI BUDET OCHENX 
PRIZNATELEN, ESLI EMU SOOBSHCHAT RESHENIE KAK MOZHNO BYSTREE (PRI USLOVII, 
CHTO ONO PRAVILXNO).\cr
}
iNTERPOLIRUYA PO |TOJ "LOGARIFMICHESKOJ" SHKALE, MOZHNO PRIKINUTX, 
CHTO OZNACHAET LYUBAYA PROMEZHUTOCHNAYA OCENKA. nAPRIMER, OCENKA 17 GOVORIT O 
TOM, CHTO DANNOE UPRAZHNENIE CHUTX LEGCHE, CHEM UPRAZHNENIE SREDNEJ 
TRUDNOSTI. zADACHA S OCENKOJ 50, ESLI ONA BUDET RESHENA KAKIM-LIBO 
CHITATELEM, V SLEDUYUSHCHIH IZDANIYAH DANNOJ KNIGI MOZHET IMETX UZHE OCENKU 
45.

aVTOR CHESTNO STARALSYA DAVATX OB�EKTIVNYE OCENKI, NO TOMU, KTO 
SOSTAVLYAET ZADACHI, TRUDNO PREDVIDETX, NASKOLXKO TRUDNYMI |TI ZADACHI 
OKAZHUTSYA DLYA KOGO-TO DRUGOGO; K TOMU ZHE U KAZHDOGO CHELOVEKA SUSHCHESTVUET 
OPREDELENNYJ TIP ZADACH, KOTORYE ON RESHAET BYSTREE. nADEYUSX, CHTO 
VYSTAVLENNYE MNOJ OCENKI DAYUT PRAVILXNOE PREDSTAVLENIE O STEPENI 
TRUDNOSTI ZADACH, NO V OBSHCHEM IH NUZHNO VOSPRINIMATX KAK ORIENTIROVOCHNYE, 
A NE ABSOLYUTNYE.

eTA KNIGA NAPISANA DLYA CHITATELEJ SAMYH RAZNYH STEPENEJ 
MATEMATICHESKOJ PODGOTOVKI I ISKUSHENNOSTI, PO|TOMU NEKOTORYE 
UPRAZHNENIYA PREDNAZNACHENY TOLXKO DLYA CHITATELEJ S MATEMATICHESKIM 
UKLONOM. eSLI V KAKOM-LIBO UPRAZHNENII MATEMATICHESKIE PONYATIYA ILI 
REZULXTATY ISPOLXZUYUTSYA BOLEE SHIROKO, CHEM |TO NEOBHODIMO DLYA TEH, KOGO 
V PERVUYU OCHEREDX INTERESUET PROGRAMMIROVANIE ALGORITMOV, TO PERED 
OCENKOJ TAKOGO UPRAZHNENIYA STAVITSYA BUKVA \rlq{}m". eSLI DLYA RESHENIYA 
UPRAZHNENIYA TREBUETSYA ZNANIE VYSSHEJ MATEMATIKI V BOLXSHEM OB�EME, CHEM 
|TO DANO V NASTOYASHCHEJ
%%11
KNIGE, TO STAVYATSYA BUKVY "vm". pOMETKA "vm" OTNYUDX NE 
YAVLYAETSYA SVIDETELXSTVOM TOGO, CHTO DANNOE UPRAZHNENIE 
TRUDNOE.

pERED NEKOTORYMI UPRAZHNENIYAMI STOIT STRELKA "\btr"; |TO OZNACHAET, 
CHTO DANNOE UPRAZHNENIE OSOBENNO POUCHITELXNO I EGO REKOMENDUETSYA 
OBYAZATELXNO VYPOLNITX. sAMO SOBOJ RAZUMEETSYA, NIKTO NE OZHIDAET, CHTO 
CHITATELX (ILI STUDENT) BUDET RESHATX VSE ZADACHI, POTOMU-TO NAIBOLEE 
POLEZNYE IZ NIH I VYDELENY. eTO SOVSEM NE ZNACHIT, CHTO DRUGIE ZADACHI NE 
STOIT RESHATX! kAZHDYJ CHITATELX DOLZHEN PO KRAJNEJ MERE POPYTATXSYA 
RESHITX VSE ZADACHI S OCENKOJ 10 I NIZHE; STRELKI ZHE POMOGUT VYBRATX, KAKIE 
ZADACHI S BOLEE VYSOKIMI OCENKAMI SLEDUET RESHITX V PERVUYU OCHEREDX.

k BOLXSHINSTVU UPRAZHNENIJ PRIVEDENY OTVETY; ONI POMESHCHENY V 
SPECIALXNOM RAZDELE V KONCE KNIGI. pOLXZUJTESX IMI MUDRO; V OTVET 
SMOTRITE TOLXKO POSLE TOGO, KAK VY PRILOZHILI DOSTATOCHNO USILIJ, CHTOBY 
RESHITX ZADACHU SAMOSTOYATELXNO, ILI ZHE ESLI DLYA RESHENIYA DANNOJ ZADACHI U 
VAS NET VREMENI. eSLI POLUCHEN SOBSTVENNYJ OTVET, LIBO ESLI VY 
DEJSTVITELXNO PYTALISX RESHITX ZADACHU, TOLXKO V |TOM SLUCHAE OTVET, 
POMESHCHENNYJ V KNIGE, BUDET POUCHITELXNYM I POLEZNYM. kAK PRAVILO, 
OTVETY K ZADACHAM IZLAGAYUTSYA OCHENX KRATKO, SHEMATICHNO, TAK KAK 
PREDPOLAGAETSYA, CHTO CHITATELX UZHE CHESTNO PYTALSYA RESHITX ZADACHU 
SOBSTVENNYMI SILAMI. iNOGDA V PRIVEDENNOM RESHENII DAETSYA MENXSHE 
INFORMACII, CHEM SPRASHIVALOSX, CHASHCHE---NAOBOROT. vPOLNE VOZMOZHNO, CHTO 
POLUCHENNYJ VAMI OTVET OKAZHETSYA LUCHSHE OTVETA, POMESHCHENNOGO V KNIGE, ILI 
VY NAJDETE OSHIBKU V |TOM OTVETE; V TAKOM SLUCHAE AVTOR BYL BY OCHENX 
OBYAZAN, ESLI BY VY KAK MOZHNO SKOREE PODROBNO SOOBSHCHILI EMU OB |TOM. v 
POSLEDUYUSHCHIH IZDANIYAH NASTOYASHCHEJ KNIGI BUDET POMESHCHENO UZHE 
ISPRAVLENNOE RESHENIE VMESTE S IMENEM EGO AVTORA.

\halign{
# & # \hfill\cr
\span \bf \hfill sVODKA USLOVNYH OBOZNACHENIJ \cr
\btr & rEKOMENDUETSYA \cr
 m  & s MATEMATICHESKIM UKLONOM \cr
vm & tREBUET ZNANIYA "VYSSHEJ MATEMATIKI"\cr
 00& tREBUET NEMEDLENNOGO OTVETA \cr
10 & pROSTOE (NA ODNU MINUTU) \cr
20 & sREDNEJ TRUDNOSTI (NA CHETVERTX CHASA) \cr
30 & pOVYSHENNOJ TRUDNOSTI. \cr
40 & dLYA "MATPRAKTIKUMA" \cr
50 & iSSLEDOVATELXSKAYA PROBLEMA\cr
}

\excercises
\rex[00] chTO OZNACHAET POMETKA "m20"?

\ex[10] kAKOE ZNACHENIE DLYA CHITATELYA IMEYUT UPRAZHNENIYA, POMESHCHAEMYE V 
UCHEBNIKAH?

\ex[m50] dOKAZHITE, CHTO ESLI $n$---CELOE CHISLO, $n > 2$, TO URAVNENIE 
$x^n+y^n=z^n$ NERAZRESHIMO V CELYH POLOZHITELXNYH CHISLAH $H$, $U$,$z$.

%% 13
\chapnotrue
\chapno=4
\chapter{sORTIROVKA}

\epigraph
nET DELA BOLEE TRUDNOGO PO ZAMYSLU, BOLEE SOMNITELXNOGO PO USPEHU, 
BOLEE OPASNOGO PRI OSUSHCHESTVLENII, CHEM VVODITX NOVYE PORYADKI.
\signed nIKKOLO mAKXYAVELLI, "gOSUDARX" (1513)

\epigraph
"nO MY NE USPEEM, PROSMOTRETX VSE NOMERA AVTOMOBILEJ",---VOZRAZIL 
dREJK. "a NAM I NE NUZHNO |TOGO DELATX. pOL. mY PROSTO RASPOLOZHIM IH PO 
PORYADKU I POISHCHEM ODINAKOVYE".
\signed pERRI mEJSON%
\note{1}{ pERRI mEJSON---GEROJ SERII DETEKTIVNYH ROMANOV POPULYARNOGO 
AMERIKANSKOGO PISATELYA eRLA sTENLI gARDNERA.--- {\sl pRIM. PEREV.\/}}. 
iZ "The Case of Angry Mourner"  (1951)

\epigraph
sORTIROVKA DEREVXEV S ISPOLXZOVANIEM evm.\nl
pRI TAKOM NOVOM, "MASHINNOM PODHODE" K IZUCHENIYU PRIRODY VY POLUCHITE 
VOZMOZHNOSTX BYSTRO RASPOZNAVATX BOLEE 260 RAZLICHNYH DEREVXEV ssha, 
aLYASKI, kANADY, VKLYUCHAYA PALXMY, DEREVXYA PUSTYNX I PROCHUYU |KZOTIKU. 
chTOBY OPREDELITX PORODU DEREVA, DOSTATOCHNO PROSTO VSTAVITX SPICU.
\signed kATALOG "Edmund Scientific Company" (1964)

v |TOJ GLAVE MY IZUCHIM VOPROS, KOTORYJ CHASTO VOZNIKAET V 
PROGRAMMIROVANII: PERERAZMESHCHENIE |LEMENTOV V VOZRASTAYUSHCHEM ILI 
UBYVAYUSHCHEM PORYADKE. pREDSTAVXTE, NASKOLXKO TRUDNO BYLO BY POLXZOVATXSYA 
SLOVAREM, ESLI BY SLOVA V NEM NE RASPOLAGALISX V ALFAVITNOM PORYADKE. 
tOCHNO TAK ZHE OT PORYADKA, V KOTOROM HRANYATSYA |LEMENTY V PAMYATI evm, VO 
MNOGOM ZAVISIT SKOROSTX I PROSTOTA ALGORITMOV, PREDNAZNACHENNYH DLYA IH 
OBRABOTKI.

hOTYA V SLOVARYAH SLOVO "SORTIROVKA" (sorting) OPREDELYAETSYA KAK 
"RASPREDELENIE, OTBOR PO SORTAM; DELENIE NA KATEGORII, SORTA, RAZRYADY", 
PROGRAMMISTY TRADICIONNO ISPOLXZUYUT |TO SLOVO V GORAZDO BOLEE UZKOM 
SMYSLE, OBOZNACHAYA IM SORTIROVKU PREDMETOV V VOZRASTAYUSHCHEM ILI 
UBYVAYUSHCHEM PORYADKE. eTOT PROCESS, POZHALUJ, SLEDOVALO BY NAZVATX NE 
SORTIROVKOJ, A \emph{UPORYADOCHENIEM} (ordering), NO ISPOLXZOVANIE |TOGO 
SLOVA PRIVELO BY K PUTANICE IZ-ZA PEREGRUZHENNOSTI ZNACHENIYAMI SLOVA 
"PORYADOK". rASSMOTRIM, NAPRIMER, SLEDUYUSHCHEE PREDLOZHENIE: "tAK KAK 
TOLXKO DVA NASHIH LENTOPROTYAZHNYH USTROJSTVA V PORYADKE, MENYA PRIZVALI K 
PORYADKU I OBYAZALI V SROCHNOM PORYADKE ZAKAZATX ESHCHE NESKOLXKO USTROJSTV, 
CHTOBY MOZHNO BYLO UPORYADOCHIVATX DANNYE RAZNOGO PORYADKA NA NESKOLXKO 
PORYADKOV BYSTREE%
\note{2}{v ORIGINALE "Since only two of our tape drives were in working 
order I was ordered to order more tape units in short order, in order to order the 
data several orders of magnitude faster".--- {\sl pRIM. PEREV.\/}}. 
v MATEMATICHESKOJ TERMINOLOGII
%% 14
|TO SLOVO TAKZHE IZOBILUET ZNACHENIYAMI (PORYADOK GRUPPY, PORYADOK 
PERESTANOVKI, PORYADOK TOCHKI VETVLENIYA, OTNOSHENIE PORYADKA I T. P.). iTAK, 
SLOVO "PORYADOK" PRIVODIT K HAOSU.

v KACHESTVE OBOZNACHENIYA DLYA PROCESSA UPORYADOCHENIYA PREDLAGALOSX TAKZHE 
SLOVO "RANZHIROVANIE"%
\note{1}{v ORIGINALE "sequencing".---{\sl pRIM. PEREV.\/}}, 
NO ONO VO MNOGIH SLUCHAYAH, PO-VIDIMOMU, NE VPOLNE OTRAZHAET SUTX DELA, 
OSOBENNO ESLI PRISUTSTVUYUT RAVNYE |LEMENTY, I, KROME TOGO, INOGDA NE 
SOGLASUETSYA S DRUGIMI TERMINAMI. kONECHNO, SLOVO "SORTIROVKA" I SAMO 
IMEET DOVOLXNO MNOGO ZNACHENIJ%
\note{2}{eTO V BOLXSHEJ STEPENI OTNOSITSYA K ANGLIJSKOMU SLOVU 
"sorting". zDESX AVTOR PRIVODYAT PRIMER: "nE was sort of out sorts after sorting 
that sort of data". (oN BYL KAK BUDTO NE V DUHE POSLE SORTIROVKI TAKOGO SORTA 
DENNYH), KOTORYJ V RUSSKOM PEREVODE NE STOLX VYRAZITELEN.--- {\sl pRIM. 
PEREV.\/}}, 
NO ONO PROCHNO VOSHLO V PROGRAMMISTSKIJ ZHARGON. pO|TOMU MY BEZ 
DALXNEJSHIH IZVINENIJ BUDEM ISPOLXZOVATX SLOVO "SORTIROVKA" V UZKOM 
SMYSLE "SORTIROVKA PO PORYADKU".
\medskip
vOT NEKOTORYE IZ NAIBOLEE VAZHNYH PRIMENENIJ SORTIROVKI:
\item{a)} rESHENIE ZADACHI "GRUPPIROVKI", KOGDA NUZHNO SOBRATX VMESTE 
VSE |LEMENTY S ODINAKOVYM ZNACHENIEM NEKOTOROGO PRIZNAKA. dOPUSTIM, 
IMEETSYA 10000 |LEMENTOV, RASPOLOZHENNYH V SLUCHAJNOM PORYADKE, PRICHEM 
ZNACHENIYA MNOGIH IZ NIH RAVNY; I PREDPOLOZHIM, NAM NUZHNO 
PEREUPORYADOCHITX FAJL TAK, CHTOBY |LEMENTY S RAVNYMI ZNACHENIYAMI 
ZANIMALI SOSEDNIE POZICII V FAJLE. eTO, PO SUSHCHESTVU, ZADACHA "SORTIROVKI" 
V SHIROKOM SMYSLE SLOVA, I ONA LEGKO MOZHET BYTX RESHENA PUTEM SORTIROVKI 
FAJLA V UZKOM SMYSLE SLOVA, A IMENNO RASPOLOZHENIEM |LEMENTOV V 
NEUBYVAYUSHCHEM PORYADKE $v_1\le v_2 \le \ldots \le v_{10000}$. 
eFFEKTIVNOSTXYU, KOTORAYA MOZHET BYTX DOSTIGNUTA V |TOJ PROCEDURE, I 
OB�YASNYAETSYA IZMENENIE PERVONACHALXNOGO SMYSLA SLOVA "SORTIROVKA".

\item{b)} eSLI DVA ILI BOLEE FAJLA OTSORTIROVATX V ODNOM I TOM ZHE 
PORYADKE, TO MOZHNO OTYSKATX V NIH VSE OBSHCHIE |LEMENTY ZA ODIN 
POSLEDOVATELXNYJ PROSMOTR VSEH FAJLOV, BEZ VOZVRATOV. eTO TOT SAMYJ 
PRINCIP, KOTORYM VOSPOLXZOVALSYA pERRI mEJSON DLYA RASKRYTIYA DELA OB 
UBIJSTVE (SM. |PIGRAFY K |TOJ GLAVE). oKAZYVAETSYA, CHTO, KAK PRAVILO, 
GORAZDO |KONOMNEE PROSMATRIVATX SPISOK POSLEDOVATELXNO, A NE 
PERESKAKIVAYA S MESTA NA MESTO SLUCHAJNYM OBRAZOM, ESLI TOLXKO SPISOK NE 
NASTOLXKO MAL, CHTO ON CELIKOM POMESHCHAETSYA V OPERATIVNOJ PAMYATI. 
sORTIROVKA POZVOLYAET ISPOLXZOVATX POSLEDOVATELXNYJ DOSTUP K BOLXSHIM 
FAJLAM V KACHESTVE PRIEMLEMOJ ZAMENY PRYAMOJ ADRESACII.

\item{c)} kAK MY UVIDIM V GL. 6, SORTIROVKA POMOGAET I PRI POISKE, S EE 
POMOSHCHXYU MOZHNO SDELATX VYDACHI evm BOLEE UDOBNYMI DLYA CHELOVECHESKOGO 
VOSPRIYATIYA. v SAMOM DELE, LISTING (NAPECHATANNYJ 
%% 15
MASHINOJ DOKUMENT), OTSORTIROVANNYJ V ALFAVITNOM PORYADKE, ZACHASTUYU 
VYGLYADIT VESXMA VNUSHITELXNO, DAZHE ESLI SOOTVETSTVUYUSHCHIE CHISLOVYE 
DANNYE BYLI RASSCHITANY NEVERNO.

hOTYA SORTIROVKA TRADICIONNO I BOLXSHEJ CHASTXYU ISPOLXZOVALASX DLYA 
OBRABOTKI KOMMERCHESKIH DANNYH, NA SAMOM DELE ONA YAVLYAETSYA 
INSTRUMENTOM, POLEZNYM V SAMYH RAZNYH SITUACIYAH, I PO|TOMU O NEM NE 
SLEDUET ZABYVATX; v UPR. 2.3.2--17 MY OBSUDILI EE PRIMENENIE DLYA 
UPROSHCHENIYA ALGEBRAICHESKIH FORMUL. uPRAZHNENIYA, PRIVEDENNYE NIZHE, 
ILLYUSTRIRUYUT RAZNOOBRAZIE TIPICHNYH PRIMENENIJ SORTIROVKI.

oDNOJ IZ PERVYH KRUPNYH SISTEM PROGRAMMNOGO OBESPECHENIYA, 
PRODEMONSTRIROVAVSHIH BOGATYE VOZMOZHNOSTI SORTIROVKI, BYL KOMPILYATOR 
Larc Scientific Compiler, RAZRABOTANNYJ FIRMOJ Computer Sciences 
Corporation V 1960~G. v |TOM OPTIMIZIRUYUSHCHEM KOMPILYATORE DLYA 
RASSHIRENNOGO fortranA SORTIROVKA ISPOLXZOVALASX VESXMA INTENSIVNO, 
TAK CHTO RAZLICHNYE ALGORITMY KOMPILYACII RABOTALI S OTNOSYASHCHIMISYA K NIM 
CHASTYAMI ISHODNOJ PROGRAMMY, RASPOLOZHENNYMI V UDOBNOJ 
POSLEDOVATELXNOSTI. pRI PERVOM PROSMOTRE OSUSHCHESTVLYALSYA LEKSICHESKIJ 
ANALIZ, T. E. VYDELENIE V ISHODNOJ PROGRAMME LEKSICHESKIH EDINIC (LEKSEM), 
KAZHDAYA IZ KOTORYH SOOTVETSTVUET LIBO IDENTIFIKATORU (IMENI 
PEREMENNOJ), LIBO KONSTANTE, LIBO OPERATORU I T. D. kAZHDAYA LEKSEMA 
POLUCHALA NESKOLXKO PORYADKOVYH NOMEROV. v REZULXTATE SORTIROVKI PO 
IMENAM I SOOTVETSTVUYUSHCHIM PORYADKOVYM NOMERAM VSE ISPOLXZOVANIYA 
DANNOGO IDENTIFIKATORA OKAZYVALISX SOBRANNYMI VMESTE. "oPREDELYAYUSHCHIE 
VHOZHDENIYA", SPECIFICIRUYUSHCHIE IDENTIFIKATOR KAK IMYA FUNKCII, PARAMETR 
ILI MNOGOMERNUYU PEREMENNUYU, POLUCHALI MENXSHIE NOMERA, PO|TOMU ONI 
OKAZYVALISX PERVYMI V POSLEDOVATELXNOSTI LEKSEM, OTVECHAYUSHCHIH |TOMU 
IDENTIFIKATORU. tEM SAMYM OBLEGCHALASX PROVERKA PRAVILXNOSTI 
UPOTREBLENIYA IDENTIFIKATOROV, RASPREDELENIE PAMYATI S UCHETOM DEKLARACIJ 
|KVIVALENTNOSTI I T. D. sOBRANNAYA TAKIM OBRAZOM INFORMACIYA O KAZHDOM 
IDENTIFIKATORE PRISOEDINYALASX K SOOTVETSTVUYUSHCHEJ LEKSEME. pO|TOMU NE 
BYLO NEOBHODIMOSTI HRANITX V OPERATIVNOJ PAMYATI "TABLICU SIMVOLOV", 
SODERZHASHCHUYU SVEDENIYA OB IDENTIFIKATORAH. pOSLE TAKOJ OBRABOTKI LEKSEMY 
SNOVA SORTIROVALISX PO DRUGOMU PORYADKOVOMU NOMERU; V REZULXTATE V 
PROGRAMME, PO SUSHCHESTVU, VOSSTANAVLIVALSYA PERVONACHALXNYJ PORYADOK, ESLI 
NE SCHITATX TOGO, CHTO ARIFMETICHESKIE VYRAZHENIYA OKAZYVALISX ZAPISANNYMI 
V BOLEE UDOBNOJ, "POLXSKOJ PREFIKSNOJ" FORME. sORTIROVKA 
ISPOLXZOVALASX I NA POSLEDUYUSHCHIH FAZAH KOMPILYACII---DLYA OBLEGCHENIYA 
OPTIMIZACII CIKLOV, VKLYUCHENIYA V LISTING SOOBSHCHENIJ OB OSHIBKAH I T. D. 
kOROCHE GOVORYA, KOMPILYATOR BYL USTROEN TAK, CHTO VSYU OBRABOTKU FAJLOV, 
HRANYASHCHIHSYA NA BARABANAH, FAKTICHESKI MOZHNO BYLO VESTI POSLEDOVATELXNO. 
pO|TOMU-TO DANNYE I SNABZHALISX TAKIMI PORYADKOVYMI NOMERAMI,
%% 16
KOTORYE POZVOLYALI UPORYADOCHIVATX |TI DANNYE RAZLICHNYMI UDOBNYMI 
SPOSOBAMI.

dRUGOE, BOLEE OCHEVIDNOE PRIMENENIE SORTIROVKI VOZNIKAET PRI 
REDAKTIROVANII FAJLOV, GDE KAZHDAYA STROKA SNABZHENA KLYUCHOM. pOKA 
POLXZOVATELX VNOSIT S KLAVIATURY IZMENENIYA I DOBAVLENIYA, NEOBYAZATELXNO 
DERZHATX VESX FAJL V OPERATIVNOJ PAMYATI. vSE IZMENYAEMYE STROKI MOZHNO 
POZDNEE OTSORTIROVATX (A ONI I TAK OBYCHNO V OSNOVNOM UPORYADOCHENY) I 
SLITX S ISHODNYM FAJLOM. eTO DAET VOZMOZHNOSTX RAZUMNO ISPOLXZOVATX 
PAMYATX V REZHIME MULXTIPROGRAMMIROVANIYA. 
[sR. S s. s. Foster, {\sl Comp. J.\/}, {\bf  11} (1968), 134--137].

pOSTAVSHCHIKI VYCHISLITELXNYH MASHIN SCHITAYUT, CHTO V SREDNEM BOLEE 25\% 
MASHINNOGO VREMENI SISTEMATICHESKI TRATITSYA NA SORTIROVKU. vO MNOGIH 
VYCHISLITELXNYH SISTEMAH NA NEE UHODIT BOLXSHE POLOVINY MASHINNOGO 
VREMENI. iZ |TOJ STATISTIKI MOZHNO ZAKLYUCHITX, CHTO LIBO (i) SORTIROVKA 
IMEET MNOGO VAZHNYH PRIMENENIJ, LIBO (ii) EYU CHASTO POLXZUYUTSYA BEZ NUZHDY, 
LIBO (iii) PRIMENYAYUTSYA V OSNOVNOM NE|FFEKTIVNYE ALGORITMY SORTIROVKI. 
pO-VIDIMOMU, KAZHDOE IZ TREH PREDPOLOZHENIJ SODERZHIT DOLYU ISTINY. vO 
VSYAKOM SLUCHAE YASNO, CHTO SORTIROVKA ZASLUZHIVAET SERXEZNOGO IZUCHENIYA S 
TOCHKI ZRENIYA EE PRAKTICHESKOGO ISPOLXZOVANIYA.

nO DAZHE ESLI BY SORTIROVKA BYLA POCHTI BESPOLEZNA, NASHLASX BY MASSA 
DRUGIH PRICHIN ZANYATXSYA EYU! iZOBRETATELXNYE ALGORITMY SORTIROVKI 
GOVORYAT O TOM, CHTO ONA I SAMA PO SEBE INTERESNA KAK OB�EKT ISSLEDOVANIYA. v 
|TOJ OBLASTI SUSHCHESTVUET MNOZHESTVO UVLEKATELXNYH NERESHENNYH ZADACH 
NARYADU S VESXMA NEMNOGIMI UZHE RESHENNYMI.

rASSMATRIVAYA VOPROS V BOLEE SHIROKOM PLANE, MY OBNARUZHIM, CHTO 
ALGORITMY SORTIROVKI PREDSTAVLYAYUT SOBOJ INTERESNYJ CHASTNYJ PRIMER 
TOGO, KAK SLEDUET PODHODITX K RESHENIYU PROBLEM PROGRAMMIROVANIYA VOOBSHCHE. 
mY POZNAKOMIMSYA SO MNOGIMI VAZHNYMI PRINCIPAMI MANIPULIROVANIYA SO 
STRUKTURAMI DANNYH I PROSLEDIM ZA |VOLYUCIEJ RAZLICHNYH METODOV 
SORTIROVKI, PRICHEM CHITATELYU CHASTO BUDET PREDOSTAVLYATXSYA VOZMOZHNOSTX 
SAMOMU "OTKRYVATX" TE ZHE IDEI, KAK BUDTO BY DO NEGO NIKTO S PODOBNYMI 
ZADACHAMI NE STALKIVALSYA. oBOBSHCHENIE |TIH CHASTNYH METODOV POZVOLIT NAM V 
ZNACHITELXNOJ STEPENI OVLADETX TEMI SPOSOBAMI MYSHLENIYA, KOTORYE 
POMOGUT SOZDAVATX DOBROTNYE ALGORITMY DLYA RESHENIYA DRUGIH PROBLEM, 
SVYAZANNYH S evm.

mETODY SORTIROVKI SLUZHAT VELIKOLEPNOJ ILLYUSTRACIEJ IDEJ 
\emph{ ANALIZA ALGORITMOV}, T. E. IDEJ, POZVOLYAYUSHCHIH OCENIVATX RABOCHIE 
HARAKTERISTIKI ALGORITMOV, A ZNACHIT, RAZUMNO VYBIRATX SREDI. KAZALOSX BY, 
RAVNOCENNYH METODOV. chITATELI, IMEYUSHCHIE SKLONNOSTX K MATEMATIKE, NAJDUT 
V |TOJ GLAVE NEMALO SPOSOBOV OCENKI SKOROSTI RABOTY ALGORITMOV I 
METODOV RESHENIYA SLOZHNYH REKURRENTNYH                                        
%% 17
SOOTNOSHENIJ. s DRUGOJ STORONY, IZLOZHENIE POSTROENO TAK, CHTO CHITATELI, NE 
IMEYUSHCHIE TAKOJ SKLONNOSTI, MOGUT BEZBOLEZNENNO PROPUSKATX VYKLADKI.

pREZHDE CHEM DVIGATXSYA DALXSHE, NEOBHODIMO BOLEE CHETKO OPREDELITX 
ZADACHU I VVESTI SOOTVETSTVUYUSHCHUYU TERMINOLOGIYU. pUSTX NADO UPORYADOCHITX 
$N$ |LEMENTOV
$$
 R_1, R_2, \ldots, R_N.
$$
nAZOVEM IH \dfn{ZAPISYAMI}, A VSYU SOVOKUPNOSTX N ZAPISEJ NAZOVEM 
\dfn{FAJLOM}. kAZHDAYA ZAPISX $R_j$ IMEET \dfn{KLYUCH} $K_j$, KOTORYJ I 
UPRAVLYAET PROCESSOM SORTIROVKI. pOMIMO KLYUCHA, ZAPISX MOZHET SODERZHATX 
DOPOLNITELXNUYU, "SOPUTSTVUYUSHCHUYU INFORMACIYU", KOTORAYA NE VLIYAET NA 
SORTIROVKU, NO VSEGDA OSTAETSYA V |TOJ ZAPISI.

oTNOSHENIE PORYADKA "$<$" NA MNOZHESTVE KLYUCHEJ VVODITSYA TAKIM 
OBRAZOM, CHTOBY DLYA LYUBYH TREH ZNACHENIJ KLYUCHEJ $a$, $b$, $c$ 
VYPOLNYALISX SLEDUYUSHCHIE USLOVIYA:

\item{i)} SPRAVEDLIVO ODNO I TOLXKO ODNO IZ SOOTNOSHENIJ $a<b$, 
$a=b$, $b<a$  (ZAKON TRIHOTOMII);

\item{ii)} ESLI $a<b$  I $b<c$, TO $a<c$ (ZAKON TRANZITIVNOSTI).

eTI DVA SVOJSTVA OPREDELYAYUT MATEMATICHESKOE PONYATIE \dfn{LINEJNOGO 
UPORYADOCHENIYA}, NAZYVAEMOGO ESHCHE \dfn{SOVERSHENNYM UPORYADOCHENIEM}. lYUBOE 
MNOZHESTVO S OTNOSHENIEM "$<$", UDOVLETVORYAYUSHCHIM SVOJSTVAM (i) I (ii), 
PODDAETSYA SORTIROVKE BOLXSHINSTVOM METODOV, OPISANNYH V |TOJ GLAVE, HOTYA 
NEKOTORYE IZ NIH GODYATSYA TOLXKO DLYA CHISLOVYH I BUKVENNYH KLYUCHEJ S 
OBYCHNYM OTNOSHENIEM PORYADKA.

zADACHA SORTIROVKI---NAJTI TAKUYU PERESTANOVKU ZAPISEJ 
$R(1)$ $R(2)$ \dots\ $R(N)$, POSLE KOTOROJ KLYUCHI RASPOLOZHILISX BY V 
NEUBYVAYUSHCHEM PORYADKE:
$$
K_{R (1)} \le  K_{p (2)} \le \cdots \le K_{p(n)}. \eqno  (1)
$$

sORTIROVKA NAZYVAETSYA \dfn{USTOJCHIVOJ}, ESLI ONA UDOVLETVORYAET 
DOPOLNITELXNOMU USLOVIYU, CHTO ZAPISI S ODINAKOVYMI KLYUCHAMI OSTAYUTSYA V 
PREZHNEM PORYADKE, T. E. 
$$
p(i)<p(j), \rem{ESLI  $K_{p(i)}=K_{p(j)}$  I $i<j$.} \eqno  (2)
$$

v RYADE SLUCHAEV MOZHET POTREBOVATXSYA FIZICHESKI PEREMESHCHATX ZAPISI V 
PAMYATI TAK, CHTOBY IH KLYUCHI, BYLI UPORYADOCHENY; V DRUGIH SLUCHAYAH 
DOSTATOCHNO SOZDATX VSPOMOGATELXNUYU TABLICU, KOTORAYA NEKOTORYM OBRAZOM 
OPISYVAET PERESTANOVKU I OBESPECHIVAET DOSTUP K ZAPISYAM V SOOTVETSTVII S 
PORYADKOM IH KLYUCHEJ.

nEKOTORYE METODY SORTIROVKI PREDPOLAGAYUT SUSHCHESTVOVANIE VELICHIN 
"$\infty$" I "$-\infty$" ILI ODNOJ IZ NIH. vELICHINA "$\infty$" SCHITAETSYA 
BOLXSHE, A VELICHINA "$-\infty$" MENXSHE LYUBOGO KLYUCHA:
$$
 -\infty < K_j <\infty, \qquad  1\le j \le N. \eqno (3)
$$
%% 18
eTI VELICHINY ISPOLXZUYUTSYA V KACHESTVE ISKUSSTVENNYH KLYUCHEJ, A TAKZHE KAK 
GRANICHNYE PRIZNAKI. rAVENSTVO V (3), VOOBSHCHE GOVORYA, ISKLYUCHENO. eSLI ZHE 
ONO TEM NE MENEE DOPUSKAETSYA, ALGORITMY MOZHNO MODIFICIROVATX TAK, 
CHTOBY ONI VSE-TAKI RABOTALI, HOTYA NEREDKO PRI |TOM IH IZYASHCHESTVO I 
|FFEKTIVNOSTX OTCHASTI UTRACHIVAYUTSYA.

oBYCHNO SORTIROVKU PODRAZDELYAYUT NA DVA KLASSA: \emph{VNUTRENNYUYU}, 
KOGDA VSE ZAPISI HRANYATSYA V BYSTROJ OPERATIVNOJ PAMYATI, I 
\emph{VNESHNYUYU}, KOGDA VSE ONI TAM NE POMESHCHAYUTSYA. pRI VNUTRENNEJ 
SORTIROVKE IMEYUTSYA BOLEE GIBKIE VOZMOZHNOSTI DLYA POSTROENIYA STRUKTUR 
DANNYH I DOSTUPA K NIM, VNESHNYAYA ZHE POKAZYVAET, KAK POSTUPATX V USLOVIYAH 
SILXNO OGRANICHENNOGO DOSTUPA.

dOSTATOCHNO HOROSHIJ OBSHCHIJ ALGORITM ZATRACHIVAET NA SORTIROVKU $N$ 
ZAPISEJ VREMYA PORYADKA $N \log N$; PRI |TOM TREBUETSYA OKOLO $\log N$ 
"PROHODOV" PO DANNYM. kAK MY UVIDIM V P.~5.3.1, |TO MINIMALXNOE VREMYA. 
tAK, ESLI UDVOITX CHISLO ZAPISEJ, TO I VREMYA PRI PROCHIH RAVNYH USLOVIYAH 
VOZRASTET NEMNOGIM BOLEE CHEM VDVOE. (nA SAMOM DELE, KOGDA $N$ STREMITSYA K 
$\infty$, VREMYA"RASTET KAK $N(\log N)^2$, ESLI VSE KLYUCHI RAZLICHNY, TAK KAK I 
RAZMERY KLYUCHEJ UVELICHIVAYUTSYA S ROSTOM $N$; NO PRAKTICHESKI $N$ VSEGDA 
OSTAETSYA OGRANICHENNYM.)

\excercises  (pervaya chast')
\ex[m20] dOKAZHITE, CHTO IZ ZAKONOV TRIHOTOMII I TRANZITIVNOSTI 
VYTEKAET \emph{EDINSTVENNOSTX} PERESTANOVKI $R(1)$, $R(2)$, \dots, $R(N)$, 
ESLI SORTIROVKA USTOJCHIVA.

\ex[21] pUSTX KAZHDAYA ZAPISX $R$. NEKOTOROGO FAJLA IMEET \emph{DVA} 
KLYUCHA: "BOLXSHOJ KLYUCH" $K_j$ I "MALYJ KLYUCH" $k_j$, PRICHEM OBA MNOZHESTVA 
KLYUCHEJ LINEJNO UPORYADOCHENY. tOGDA MOZHNO OBYCHNYM SPOSOBOM VVESTI 
"LEKSIKOGRAFICHESKIJ PORYADOK" NA MNOZHESTVE PAR KLYUCHEJ $(k, k)$:
$$
(K_i, k_i) < (K_j, k_j),
\rem{ ESLI $K_i<K_j$  ILI ESLI $K_i=K_j$  I $k_i<k_j$}.
$$

nEKTO (NAZOVEM EGO MISTER $a$) OTSORTIROVAL |TOT FAJL SNACHALA PO 
BOLXSHIM KLYUCHAM, POLUCHIV $n$ GRUPP ZAPISEJ S ODINAKOVYMI BOLXSHIMI 
KLYUCHAMI V KAZHDOJ GRUPPE:
$$
K_{p(1)}=\cdots=K_{p(i_1)}<K_{p(i_1+1)}=\cdots=K_{p(i_2)}<\cdots 
< K_{p(i_{n-1}+1)} = \cdots = K_{p(i_n)},
$$
GDE $i_n=N$. zATEM KAZHDUYU IZ  $n$ GRUPP $R_{p(i_{j-1}+1)}$, \dots, 
$R_{p(i_j)}$ ON OTSORTIROVAL  PO MALYM KLYUCHAM.

tOT ZHE ISHODNYJ FAJL VZYAL MISTER $v$ I OTSORTIROVAL EGO SNACHALA PO 
MALYM KLYUCHAM, A POTOM POLUCHIVSHIJSYA FAJL OTSORTIROVAL PO BOLXSHIM 
KLYUCHAM.

vZYAV TOT ZHE ISHODNYJ FAJL, MISTER $s$ OTSORTIROVAL EGO ODIN RAZ, 
POLXZUYASX LEKSIKOGRAFICHESKIM PORYADKOM MEZHDU PARAMI KLYUCHEJ 
$(K_j, k_j)$.

pOLUCHILOSX. LI U VSEH TROIH ODNO I TO ZHE?
%% 19
\ex [M25] pUSTX NA MNOZHESTVE $K_1$, \dots, $K_N$  OPREDELENO OTNOSHENIE 
$<$, DLYA KOTOROGO ZAKON TRIHOTOMII VYPOLNYAETSYA, A ZAKON TRANZITIVNOSTI---
\emph{NET}. dOKAZHITE, CHTO I V |TOM SLUCHAE VOZMOZHNA USTOJCHIVAYA SORTIROVKA 
ZAPISEJ, T. E. TAKAYA, CHTO VYPOLNYAYUTSYA USLOVIYA (1) I (2); NA SAMOM DELE 
SUSHCHESTVUYUT PO KRAJNEJ MERE TRI RASPOLOZHENIYA ZAPISEJ, UDOVLETVORYAYUSHCHIH 
|TIM USLOVIYAM!

\ex[15] mISTER tUPICA (PROGRAMMIST) ZAHOTEL UZNATX, NAHODITSYA LI V 
YACHEJKE |a| MASHINY \MIX\ CHISLO, BOLXSHEE CHISLA IZ YACHEJKI |v|, MENXSHEE ILI ZHE 
RAVNOE EMU. oN NAPISAL
$$
\eqalign{
&|LDA a |\cr
&|SUB v|\cr
}
 $$
A POTOM PROVERIL, KAKOJ REZULXTAT POLUCHILSYA V |rA|: POLOZHITELXNOE CHISLO, 
OTRICATELXNOE ILI NULX. kAKUYU SERXEZNUYU OSHIBKU ON DOPUSTIL I KAK DOLZHEN 
BYL POSTUPITX?

\ex [17] nAPISHITE \MIX-PODPROGRAMMU DLYA SRAVNENIYA KLYUCHEJ, ZANIMAYUSHCHIH 
NESKOLXKO SLOV, ISHODYA IZ SLEDUYUSHCHIH USLOVIJ:
\ctable{#\hfill\bskip&\hsize=10cm\noindent\vtop{#}\hfill\cr
vYZOV: &   |JMP COMPARE| \cr
sOSTOYANIE PRI VHODE:  &     
$|rI1|=n$; $|CONTENTS|(A+k)=a_k$, $|CONTENTS|(B+k)=b_k$ PRI 
$1\le{} k\le{} n$; PREDPOLAGAETSYA, CHTO $n \ge{} 1$.\cr
sOSTOYANIE PRI VYHODE: &      
$|sI|=+1$, ESLI $(a_n, \dots, a_1) > (b_n, ..., b_1)$; \cr
 & $|sI|=0$, ESLI $(a_n, \dots, a_1) = (b_n, ..., b_1)$;\cr
& $|CI|=-1$, ESLI $(a_n, \dots, a_1)< (b_n, ..., b_1)$; \cr
& |rX| I |rI1|, VOZMOZHNO, IZMENILISX.\cr
}
zDESX OTNOSHENIE $(a_n, \dots, a_1) < (b_n, ..., b_1)$ OBOZNACHAET 
LEKSIKOGRAFICHESKOE UPORYADOCHENIE SLEVA NAPRAVO, T. E. SUSHCHESTVUET INDEKS $j$, 
TAKOJ, CHTO $a_k=b_k$ PRI $P\ge{} k > j$, NO $A_j < b_j$.

\ex[30] v YACHEJKAH |A| I |v| SODERZHATSYA SOOTVETSTVENNO CHISLA $A$ I~$b$. 
pOKAZHITE, CHTO MOZHNO NAPISATX \MIX-PROGRAMMU, KOTORAYA BY VYCHISLYALA 
$\min (a, b)$ I ZAPISYVALA REZULXTAT V YACHEJKU |s|, \emph{NE POLXZUYASX 
KOMANDAMI PEREHODA.} (\emph{pREDOSTEREZHENIE:} POSKOLXKU ARIFMETICHESKOE 
PEREPOLNENIE NEVOZMOZHNO OBNARUZHITX BEZ KOMAND PEREHODA, RAZUMNO TAK 
POSTROITX PROGRAMMU, CHTOBY PEREPOLNENIE NE MOGLO VOZNIKNUTX NI PRI KAKIH 
ZNACHENIYAH $A$ I~$b$)

\ex[m27] kAKOVA VEROYATNOSTX TOGO, CHTO POSLE SORTIROVKI V NEUBYVAYUSHCHEM 
PORYADKE |N| NEZAVISIMYH RAVNOMERNO RASPREDELENNYH NA OTREZKE $[0, 1]$ 
SLUCHAJNYH VELICHIN $r$-E OT NACHALA CHISLO OKAZHETSYA $\le{} x$?

\excercises uprazhneniya (vtoraya chast')
v KAZHDOM IZ |TIH UPRAZHNENIJ POSTAVLENA ZADACHA, S KOTOROJ MOZHET 
STOLKNUTXSYA PROGRAMMIST. pREDLOZHITE "HOROSHEE" RESHENIE ZADACHI, 
PREDPOLAGAYA, CHTO IMEETSYA SRAVNITELXNO NEBOLXSHAYA OPERATIVNAYA PAMYATX I 
OKOLO POLUDYUZHINY, LENTOPROTYAZHNYH USTROJSTV (|TOGO KOLICHESTVA DOSTATOCHNO 
DLYA SORTIROVKI).

\ex[75] iMEETSYA LENTA, NA KOTOROJ ZAPISAN MILLION SLOV DANNYH. kAK 
OPREDELITX, SKOLXKO NA |TOJ LENTE RAZLICHNYH SLOV?

\ex[18] vOOBRAZITE SEBYA V ROLI uPRAVLENIYA VNUTRENNIH DOHODOV mINISTERSTVA
FINANSOV ssha. vY POLUCHAETE MILLIONY "INFORMACIONNYH" KARTOCHEK OT 
ORGANIZACIJ O TOM, SKOLXKO, DENEG ONI VYPLATILI RAZLICHNYM LICAM, I 
MILLIONY "NALOGOVYH" KARTOCHEK OT RAZLICHNYH LIC OB IH DOHODAH. kAK BY VY 
STALI OTYSKIVATX LYUDEJ, KOTORYE SOOBSHCHILI NE OBO VSEH SVOIH DOHODAH?

%% 20
\ex[m25]{\sl (tRANSPONIROVANIE MATRICY.)\/} iMEETSYA MAGNITNAYA LENTA, 
SODERZHASHCHAYA MILLION SLOV, KOTORYE PREDSTAVLYAYUT SOBOJ |LEMENTY 
$1000\times1000$-MATRICY, ZAPISANNYE PO STROKAM: $a_{1,1}$ $a_{1,2}$ \dots 
$a_{1,1000}$ $a_{2,1}$ \dots $a_{2,1000}$ \dots $a_{1000, 1000}$. vASHA 
ZADACHA---POLUCHITX LENTU, NA KOTOROJ |LEMENTY |TOJ MATRICY BYLI BY 
ZAPISANY PO STOLBCAM: $a_{1,1}$ $a_{2,1}$ \dots $a_{1000,1}$ $a_{1,2}$\dots 
$a_{1,2}$\dots $a_{1000,2}$ \dots $a_{1000, 1000}$ (pOSTARAJTESX SDELATX NE 
BOLEE DESYATI PROSMOTROV DANNYH.)

\ex[m26] v VASHEM RASPORYAZHENII DOVOLXNO BOLXSHOJ FAJL IZ $N$ SLOV. 
kAK BY VY EGO "PERETASOVALI" SLUCHAJNYM OBRAZOM?

 \rex[24] v NEKOM UNIVERSITETE RABOTAET OKOLO 1000 PREPODAVATELEJ I 
IMEETSYA 500 KOMITETOV. sCHITAETSYA, CHTO KAZHDYJ PREPODAVATELX YAVLYAETSYA 
CHLENOM PO KRAJNEJ MERE DVUH KOMITETOV. vAM NUZHNO PODGOTOVITX S POMOSHCHXYU 
MASHINY UDOBOCHITAEMYE SPISKI CHLENOV VSEH KOMITETOV. vY RASPOLAGAETE 
KOLODOJ IZ PRIBLIZITELXNO 1500 PERFOKART, SLOZHENNYH PROIZVOLXNYM 
OBRAZOM I SODERZHASHCHIH SLEDUYUSHCHUYU INFORMACIYU:

{\it chLENSKIE KARTOCHKI:\/} KOLONKA 1---PROBEL; KOLONKI 2--18---FAMILIYA S 
POSLEDUYUSHCHIMI PROBELAMI; KOLONKI 19--20---INICIALY; 
KOLONKI 21--23---NOMER PERVOGO kOMITETA; 
KOLONKI 24--26---NOMER VTOROGO KOMITETA; \dots; 
KOLONKI 78--80--- NOMER DVADCATOGO KOMITETA (ESLI NUZHNO) ILI PROBELY.

{\it kOMITETSKIE KARTOCHKI:\/} KOLONKA 1---"*"; KOLONKI 2--77---NAZVANIE 
KOMITETA; KOLONKI 78--80---NOMER KOMITETA. kAK VY DOLZHNY DEJSTVOVATX? 
(oPISHITE SVOJ METOD DOSTATOCHNO PODROBNO.)

\ex[20] vY RABOTAETE S DVUMYA VYCHISLITELXNYMI SISTEMAMI, V KOTORYH 
PO-RAZNOMU UPORYADOCHENY LITERY (BUKVY I CIFRY). kAK ZASTAVITX PERVUYU 
evm SORTIROVATX FAJLY S BUKVENNO-CIFROVOJ INFORMACIEJ, 
PREDNAZNACHENNYE DLYA ISPOLXZOVANIYA NA VTOROJ evm?

\ex[18] iMEETSYA DOVOLXNO BOLXSHOJ SPISOK LYUDEJ, RODIVSHIHSYA V ssha, S 
UKAZANIEM SHTATA, V KOTOROM ONI RODILISX. kAK PODSCHITATX CHISLO LYUDEJ, 
RODIVSHIHSYA V KAZHDOM SHTATE? (pREDPOLAGAETSYA, CHTO NI ODIN CHELOVEK NE UKAZAN 
V SPISKE BOLEE ODNOGO RAZA.)

\ex[20] chTOBY OBLEGCHITX VNESENIE IZMENENIJ V BOLXSHIE PROGRAMMY, 
NAPISANNYE NA fortranE, VY HOTITE NAPISATX PROGRAMMU, 
VYPECHATYVAYUSHCHUYU TABLICU "PEREKRESTNYH SSYLOK". vHODNYMI DANNYMI DLYA 
NEE SLUZHIT PROGRAMMA NA fortranE, A V REZULXTATE POLUCHAETSYA LISTING 
ISHODNOJ PROGRAMMY, SNABZHENNYJ UKAZATELEM VSEH SLUCHAEV UPOTREBLENIYA 
KAZHDOGO IDENTIFIKATORA (T. E. IMENI) V PROGRAMME. kAK NAPISATX TAKUYU 
PROGRAMMU?

{\def\cell#1{\vtop{\hsize=.49\hsize\noindent #1\par}}
 \def\+#1&#2\cr{\line{\cell{#1}\hfil\cell{#2}}\smallskip}
\ex[33] (sORTIROVKA KATALOZHNYH KARTOCHEK.) sPOSOBY SOSTAVLENIYA 
ALFAVITNYH KATALOGOV V RAZNYH BIBLIOTEKAH NESKOLXKO OTLICHAYUTSYA DRUG OT 
DRUGA. v SLEDUYUSHCHEM "ALFAVITNOM" SPISKE SODERZHATSYA REKOMENDACII, VZYATYE 
IZ PRAVIL REGISTRACII I HRANENIYA KATALOZHNYH KARTOCHEK aMERIKANSKOJ 
BIBLIOTECHNOJ ASSOCIACII (chIKAGO, 1942):
\medskip
\+ \centerline{\bf tEKST KARTOCHKI}%
  &\centerline{\bf zAMECHANIYA}\cr
\+ R. Accademia nazionale dei Lincei, Rome 
  &v NAZVANIYAH INOSTRANNYH (KROME BRITANSKIH) UCHREZHDENIJ SLOVO "royalty" 
   (KOROLEVSKIJ) IGNORIRUETSYA\cr
\+ 1812; ein historischer roman.  
  &Achtzehnhundert zw\"olf \cr
\+ Biblioth\`eque d'histoire r\'evolutionnaire. 
  &vO FRANCUZSKOM TEKSTE  APOSTROF RASSMATRIVAETSYA KAK PROBEL \cr
\+ Biblioth\`eque des curiosit\'es.       
  &nADSTROCHNYE ZNAKI IGNORIRUYUTSYA \cr
\+ Brown, Mrs. J. Crosby       
  &uKAZANIE POLOZHENIYA (Mrs.) IGNORIRUETSYA \cr
\+ Brown, John   
  &fAMILII S DATAMI SLEDUYUT ZA FAMILIYAMI BEZ DAT~\dots \cr
\+ Brown, John, mathematician   
  &\dots{} KOTORYE UPORYADOCHIVAYUTSYA PO \cr
\+ Brown, John, of Boston
  &OPISATELXNYM SLOVAM \cr
\+ Brown, John, 1715--1766
  &oDINAKOVYE FAMILII UPORYADOCHIVAYUTSYA PO DATAM ROZHDENIYA \cr
%% 21
\+ BROWN, JOHN, 1715--1766 
  &rABOTY "O NEM" IDUT POSLE EGO RABOT \cr
\+ Brown, John, d. 1811
  &iNOGDA GOD ROZHDENIYA OPREDELYAETSYA PRIBLIZITELXNO \cr
\+ Brown, Dr. John, 1810--1882 
  &uKAZANIE POLOZHENIYA (Dr.) IGNORIRUETSYA \cr
\+ Brown-Williams, Reginald Makepeace
  &dEFIS RASSMATRIVAETSYA KAK PROBEL \cr
\+ Brown America. 
  &nAZVANIYA KNIG IDUT POSLE SOSTAVNYH FAMILIJ \cr
\+ Brown \& Dallison's Nevada directory.  
  &\& V ANGLIJSKOM TEKSTE PREVRASHCHAETSYA V "and" \cr
\+ Brownjohn, Alan
  &\cr
\+ Den', Vladimir \'Eduardovich, 1867--
  &aPOSTROF V IMENAH IGNORIRUETSYA\cr
\+ The den.  
  &aRTIKLX V NACHALE TEKSTA IGNORIRUETSYA\cr
\+ Den lieben s\"ussen m\"adeln. 
  &\dots{} ESLI SUSHCHESTVITELXNOE STOIT V IMENITELXNOM PADEZHE\cr
\+ Dix, Morgan, 1827--1908  
  &fAMILII IDUT RANXSHE DRUGIH SLOV \cr
\+ 1812 ouverture.
  &Dix-huit cent douze \cr
\+ Le XIXe si\`ecle fran\c{c}ais.
  &Dix-neuvi\`eme \cr
\+ The 1847 issue of U. S. stamps.
  &Eighteen forty-seven \cr
\+ 1812 overture.
  &Eighteen twelve \cr
\+ I am a mathematician,
  &(by Norbert Weiner)\cr
\+ IBM journal of research and development.
  &aBBREVIATURY RASSMATRIVAYUTSYA KAK RYAD ODNOBUKVENNYH SLOV \cr
\+ ha-I ha-e\d had.
  &aRTIKLX V NACHALE TEKSTA IGNORIRUETSYA \cr
\+ Ia; a love story.
  &zNAKI PREPINANIYA V NAZVANIYAH IGNORIRUYUTSYA \cr
\+ International Business Machines Corporation
  &\cr
\+ al-Khuw\={a}rizm\={\i}, Mu\d{h}ammad ibn M\={u}s\={a}, {\it fl.\/} 813--846 
  &nACHALXNOE "Al-" V ARABSKIH IMENAH IGNORIRUETSYA \cr
\+ Labour; a magazine for all workers. 
  &zAMENYAETSYA NA "Labor" \cr
\+ Labor research association 
  &\cr
\+ Labour, {\it see\/} Labor
  &sSYLKA NA DRUGUYU KARTOCHKU V KARTOTEKE \cr
\+ McCall's cookbook 
  &aPOSTROF V ANGLIJSKOM TEKSTE IGNORIRUETSYA \cr
\+ McCarthy, John, 1927--
  &Mc = Mac \cr
\+ Machine-independent computer programming. 
  &dEFIS RASSMATRIVAETSYA KAK PROBEL \cr
\+ MacMahon, Maj. Percy  Alexander, 1854--1929 
  &uKAZANIE POLOZHENIYA (Maj) IGNORIRUETSYA \cr
\+ Mrs. Dalloway. 
  &"Mrs. "= "Mistress" \cr
\+ Mistress of mistresses.
  &\cr
\+ Royal society of London
  &\cr
\+ St. PetersburgerZeitung.
  &"St."= "Saint"   DAZHE  V NEMECKOM TEKSTE \cr
\+ Saint-Sa\"ens, Camille, 1835--1921 
  &dEFIS RASSMATRIVAETSYA KAK PROBEL \cr
\+ Ste. Anne des Monts, Quebec
  &Sainte \cr
\+ Seminumerical algorithms.
  &\cr
\+ Uncle Tom's cabin.
  &\cr
\+ U.S. Bureau of the census.  
  &"U.S." = "United States" \cr
\+ Vandermonde, Alexander Th\'eophile, 1735--1796
  &\cr
\+ Van Valkenburg, Mac Elwyn, 1921--
  & pROBEL POSLE PREFIKSA V FAMILIYAH IGNORIRUETSYA \cr
\+ Von Neumann, John, 1903--1957
  &\cr
\+ The whole art of legerdemain.
  &\cr
%% 22
\+ Who's afraid of Virginia Woolf?
 & aPOSTROF V ANGLIJSKOM TEKSTE IGNORIRUETSYA\cr
\+ Wijngaarden, Adriaan van, 1916--
 & fAMILIYA  NIKOGDA NE  NACHINAETSYA S MALOJ BUKVY \cr
\medskip
\noindent(u BOLXSHINSTVA IZ |TIH PRAVIL ESTX ISKLYUCHENIYA; KROME TOGO, SUSHCHESTVUET 
MNOGO DRUGIH PRAVIL, KOTORYE ZDESX NE UPOMYANUTY.)
\par
}

pREDPOLOZHIM, VAM PRISHLOSX SORTIROVATX BOLXSHOE KOLICHESTVO TAKIH 
KARTOCHEK S POMOSHCHXYU VYCHISLITELXNOJ MASHINY I VPOSLEDSTVII OBSLUZHIVATX 
OGROMNUYU KARTOTEKU, PRICHEM U VAS NET VOZMOZHNOSTI IZMENITX UZHE 
SLOZHIVSHIESYA PORYADKI ZAPOLNENIYA KARTOCHEK. kAK BY VY ORGANIZOVALI 
INFORMACIYU, CHTOBY UPROSTITX OPERACII VKLYUCHENIYA NOVYH KARTOCHEK I 
SORTIROVKI?

\ex[m21]\exhead(dISKRETNYE LOGARIFMY.) pUSTX IZVESTNO, CHTO 
$p$---(DOVOLXNO BOLXSHOE) PROSTOE CHISLO, A $a$---PERVOOBRAZNYJ KORENX PO MODULYU 
$p$. sLEDOVATELXNO, DLYA LYUBOGO $b$ V DIAPAZONE $1\le{} b < p$ SUSHCHESTVUET 
EDINSTVENNOE $n$, TAKOE, CHTO $a^n \bmod p=b$, $1\le{} n < R$. kAK PO 
ZADANNOMU $b$ NAJTI $n$ MENEE CHEM ZA $o(n)$ SHAGOV? [uKAZANIE. pUSTX 
$m=\lceil\sqrt p\rceil$. pOPYTAJTESX RESHITX URAVNENIE 
$a^{mn_1}\equiv b a^{-n_2} \pmod{p}$  PRI $0 \le{} n_1$, $n_2 < m$.]

\ex[m25] (e. t. pARKER.) eJLER VYDVINUL PREDPOLOZHENIE, CHTO URAVNENIE
$$
u^6+v^6+ w^6 + H^6 + y^6 = z^6
$$
NE IMEET RESHENIJ (ZA ISKLYUCHENIEM TRIVIALXNYH) SREDI CELYH 
NEOTRICATELXNYH CHISEL $u$, $v$, $w$, $x$, $y$, $z$, KOGDA PO KRAJNEJ MERE 
CHETYRE PEREMENNYE RAVNY NULYU. pOMIMO |TOGO, ON PREDPOLAGAL, CHTO 
URAVNENIE
$$
x_1^n+\cdots+x_{n-1}^n=x_n^n
$$
NE IMEET NETRIVIALXNYH RESHENIJ PRI $n\ge 3$, NO |TO PREDPOLOZHENIE BYLO 
OPROVERGNUTO: S POMOSHCHXYU VYCHISLITELXNOJ MASHINY NAJDENO TOZHDESTVO 
$27^5+84^5+110^5+133^5=144^5$; SM. l. dZH. l|NDER, t. r. pARKIN I dZH. l. 
sELFRIDZH, {\sl Math. Comp.\/}, {\bf 21} (1967), 446--459. pRIDUMAJTE, KAK 
MOZHNO BYLO BY ISPOLXZOVATX SORTIROVKU DLYA POISKA PRIMEROV, 
OPROVERGAYUSHCHIH PREDPOLOZHENIE eJLERA PRI $n=6$.

\rex[24] fAJL SODERZHIT BOLXSHOE KOLICHESTVO 30-RAZRYADNYH DVOICHNYH SLOV:
$x_1$, \dots $x_N$. pRIDUMAJTE HOROSHIJ SPOSOB NAHOZHDENIYA V NEM VSEH 
\emph{DOPOLNITELXNYH} PAR $(x_i, H_j)$. (dVA SLOVA NAZYVAYUTSYA 
DOPOLNITELXNYMI, ESLI VTOROE SODERZHIT 0 VO VSEH RAZRYADAH, V KOTORYH BYLI 1 
V PERVOM SLOVE, I OBRATNO; TAKIM OBRAZOM, ONI DOPOLNITELXNY TOGDA I TOLXKO 
TOGDA, KOGDA IH SUMMA RAVNA $(11\ldots1)_2$, ESLI ONI RASSMATRIVAYUTSYA KAK 
DVOICHNYE CHISLA.) 

\rex[25] iMEETSYA FAJL. SODERZHASHCHIJ 1000 30-RAZRYADNYH DVOICHNYH SLOV 
$x_1$, \dots, $x_{1000}$. kAK BY VY STALI SOSTAVLYATX SPISOK VSEH PAR 
$(x_i, x_j)$, TAKIH, CHTO $x_i$ OTLICHAETSYA OT $x_j$  NE BOLEE CHEM V DVUH 
RAZRYADAH?

\ex[22] kAK BY VY POSTUPILI PRI OTYSKANII VSEH PYATIBUKVENNYH ANAGRAMM, 
TAKIH, KAK \strong{CARET, CARTE, CATER, CRATE, REACT, 
TRACE; CRUEL, LUCRE, ULCER; DOWRY, ROWDY, WORDY?} [eSLI 
BY VY, SKAZHEM, ZAHOTELI UZNATX, SUSHCHESTVUYUT LI V ANGLIJSKOM YAAYKE NABORY 
IZ DESYATI ILI BOLEE ANAGRAMM, KROME ZAMECHATELXNOJ SERII:
$$
\vtop{\strong{
APERS, ASPER,PARES,PARSE,PEARS, PRASE, RAPES, REAPS, 
SPARE, SPEAR,
}}
$$
K KOTOROJ MOZHNO DOBAVITX ESHCHE FRANCUZSKOE SLOVO \strong{APRES.}]

\ex[m28] pUSTX DANY OPISANIYA VESXMA BOLXSHOGO CHISLA NAPRAVLENNYH 
GRAFOV. kAKIM PUTEM MOZHNO SGRUPPIROVATX \emph{IZOMORFNYE} GRAFY? (dVA 
NAPRAVLENNYH GRAFA NAZYVAYUTSYA IZOMORFNYMI, ESLI SUSHCHESTVUET VZAIMNO 
ODNOZNACHNOE SOOTVETSTVIE MEZHDU IH VERSHINAMI I VZAIMNO ODNOZNACHNOE 
SOOTVETSTVIE
%% 23
MEZHDU IH DUGAMI, PRICHEM |TI SOOTVETSTVIYA SOHRANYAYUT INCIDENTNOSTX VERSHIN 
I DUG.)

\ex[30] v NEKOTOROJ GRUPPE IZ 4096 CHELOVEK KAZHDYJ IMEET OKOLO 100 
ZNAKOMYH. bYL SOSTAVLEN SPISOK VSEH PAR LYUDEJ, ZNAKOMYH MEZHDU SOBOJ. (eTO 
OTNOSHENIE SIMMETRICHNO, T. E. ESLI $H$ ZNAKOM S $U$, TO I $U$ ZNAKOM S $H$. 
pO|TOMU SPISOK SODERZHIT PRIMERNO 200000 PAR.) pRIDUMAJTE ALGORITM, 
KOTORYJ PO ZaDaNNoMy $k$ VYDAVAL BY VSE \emph{KLIKI} IZ $k$ CHELOVEK. 
(kLIKA --- |TO GRUPPA LYUDEJ, V KOTOROJ VSE MEZHDU SOBOJ ZNAKOMY.) 
pREDPOLAGAETSYA, CHTO SLISHKOM BOLXSHIH KLIK NE BYVAET.

\ex[30] tRI MILLIONA CHELOVEK S RAZLICHNYMI IMENAMI BYLI ULOZHENY 
RYADOM NEPRERYVNOJ CEPOCHKOJ OT nXYU-jORKA DO kALIFORNII. kAZHDOMU IZ NIH 
DALI LISTOK BUMAGI, NA KOTOROM ON NAPISAL SVOE IMYA I IMYA SVOEGO 
BLIZHAJSHEGO ZAPADNOGO SOSEDA. chELOVEK, NAHODIVSHIJSYA V SAMOJ ZAPADNOJ 
TOCHKE CEPI, NE PONYAL, CHTO EMU DELATX, I VYKINUL SVOJ LISTOK. oSTALXNYE 
2999999 LISTKOV SOBRALI V BOLXSHUYU KORZINU I OTPRAVILI V nACIONALXNYJ 
ARHIV, V vASHINGTON, OKRUG kOLUMBIYA. tAM SODERZHIMOE KORZINY TSHCHATELXNO 
PERETASOVALI I ZAPISALI NA MAGNITNYE LENTY.

sPECIALIST PO TEORII INFORMACII OPREDELIL, CHTO IMEETSYA DOSTATOCHNO 
INFORMACII DLYA VOSSTANOVLENIYA SPISKA LYUDEJ V ISHODNOM PORYADKE. 
sPECIALIST PO PROGRAMMIROVANIYU NASHEL SPOSOB SDELATX |TO MENEE CHEM ZA 
1000 PROSMOTROV LENT S DANNYMI, ISPOLXZUYA LISHX POSLEDOVATELXNYJ DOSTUP K 
FAJLAM NA LENTAH I NEBOLXSHOE KOLICHESTVO PAMYATI S PROIZVOLXNYM DOSTUPOM. 
kAK EMU |TO UDALOSX?

[dRUGIMI SLOVAMI, KAK, IMEYA RASPOLOZHENNYE PROIZVOLXNYM OBRAZOM PARY 
$(x_i, x_{i+1})$, $1 \le i < N$, GDE VSE $x_i$ RAZLICHNY, POLUCHITX 
POSLEDOVATELXNOSTX $x_1$, $x_2$, \dots, $x_N$, PRIMENYAYA LISHX METODY 
POSLEDOVATELXNOJ OBRABOTKI DANNYH, PRIGODNYE DLYA RABOTY S MAGNITNYMI 
LENTAMI? eTO ZADACHA SORTIROVKI V SLUCHAE, KOGDA TRUDNO OPREDELITX, KAKOJ IZ 
DVUH KLYUCHEJ PREDSHESTVUET DRUGOMU; MY UZHE PODNIMALI |TOT VOPROS V UPR. 
2.2.3--25.]
%% 24

\subchap{* kombinatornye svojstva perestanovok}
pERESTANOVKOJ KONECHNOGO MNOZHESTVA NAZYVAETSYA NEKOTOROE RASPOLOZHENIE 
EGO |LEMENTOV V RYAD. pERESTANOVKI OSOBENNO VAZHNY PRI IZUCHENII ALGORITMOV 
SORTIROVKI, TAK KAK ONI SLUZHAT DLYA PREDSTAVLENIYA NEUPORYADOCHENNYH 
ISHODNYH DANNYH. chTOBY ISSLEDOVATX |FFEKTIVNOSTX RAZLICHNYH METODOV 
SORTIROVKI, NUZHNO UMETX PODSCHITYVATX CHISLO PERESTANOVOK, KOTORYE 
VYNUZHDAYUT POVTORYATX NEKOTORYJ SHAG ALGORITMA OPREDELENNOE CHISLO RAZ. 

mY, KONECHNO, UZHE NE RAZ VSTRECHALISX S PERESTANOVKAMI V GL. 1, 2 I~3. 
nAPRIMER, V P. 1.2.5 OBSUZHDALISX DVA OSNOVNYH TEORETICHESKIH METODA 
POSTROENIYA $n!$ PERESTANOVOK IZ $n$ OB�EKTOV;
V P. 1.3.3 PROANALIZIROVANY NEKOTORYE ALGORITMY, SVYAZANNYE S CIKLICHESKOJ 
STRUKTUROJ I MULXTIPLIKATIVNYMI SVOJSTVAMI PERESTANOVOK; V P. 3.3.2 
IZUCHENY IH OTREZKI MONOTONNOSTI. cELX NASTOYASHCHEGO PARAGRAFA---IZUCHITX 
NEKOTORYE DRUGIE SVOJSTVA PERESTANOVOK I RASSMOTRETX OBSHCHIJ SLUCHAJ, KOGDA 
DOPUSKAETSYA NALICHIE ODINAKOVYH |LEMENTOV. pOPUTNO MY UZNAEM MNOGOE O 
KOMBINATORNOJ MATEMATIKE.

sVOJSTVA PERESTANOVOK NASTOLXKO KRASIVY, CHTO PREDSTAVLYAYUT I 
SAMOSTOYATELXNYJ INTERES. uDOBNO BUDET DATX IH SISTEMATICHESKOE IZLOZHENIE V 
ODNOM MESTE, A NE RAZBRASYVATX MATERIAL PO VSEJ GLAVE. chITATELYAM, NE 
IMEYUSHCHIM SKLONNOSTI K MATEMATIKE, A TAKZHE TEM, KTO ZHAZHDET POSKOREE 
DOBRATXSYA DO SAMIH METODOV SORTIROVKI, REKOMENDUETSYA PEREJTI SRAZU K 
\S~5.2, POTOMU CHTO NASTOYASHCHIJ PARAGRAF \emph{NEPOSREDSTVENNOGO} 
OTNOSHENIYA K SORTIROVKE POCHTI NE IMEET.

\subsubchap{*iNVERSII}
pUSTX $a_1$ $a_2$ \dots\ $a_n$ ---PERESTANOVKA MNOZHESTVA 
$\{1, 2, \dots, n\}$. eSLI $i < j$, a $a_i>a_j$, TO PARA $(A_i, a_j)$ 
NAZYVAETSYA 
INVERSIEJ PERESTANOVKI; NAPRIMER, PERESTANOVKA 3 1 4 2 IMEET TRI INVERSII: 
$(3, 1)$, $(3, 2)$ I $(4, 2)$. kAZHDAYA INVERSIYA---|TO PARA |LEMENTOV, 
"NARUSHAYUSHCHIH PORYADOK"; SLEDOVATELXNO, EDINSTVENNAYA PERESTANOVKA, NE 
SODERZHASHCHAYA INVERSIJ,---|TO OTSORTIROVANNAYA PERESTANOVKA 1 2 \dots $n$. 
tAKAYA SVYAZX S SORTIROVKOJ I ESTX GLAVNAYA PRICHINA NASHEGO INTERESA K 
INVERSIYAM, HOTYA |TO PONYATIE UZHE ISPOLXZOVALOSX NAMI PRI ANALIZE ALGORITMA 
DINAMICHESKOGO RASPREDELENIYA PAMYATI (SM. UPR. 2.2.2--9).
%% 25

pONYATIE INVERSII VVEL g. kRAMER V 1750 G. [Intr. \`a 1'Analyse des Lignes 
Courbes alg\'ebriques (Geneva, 1750), 657--659; SR. S tOMAS mYUIR, thEOGU of 
Determinants, 1 (1906), 11--14] V SVYAZI SO SVOIM ZAMECHATELXNYM PRAVILOM 
RESHENIYA LINEJNYH URAVNENIJ. v SUSHCHNOSTI, ON OPREDELIL DETERMINANT 
$n\times n$-MATRICY SLEDUYUSHCHIM OBRAZOM:
$$
\det\pmatrix{
 x_{11} & x_{12} &\ldots & x_{1n} \cr
\vdots    & \vdots & & \vdots \cr
 x_{n1} & x_{n2} & \ldots & x_{nn} \cr
}=\sum (-1)^{I(a_1 a_2 \ldots a_n)}x_{1a_1}x_{2a_2}\ldots x_{na_n},
$$
GDE SUMMA BERETSYA PO VSEM  PERESTANOVKAM $a_1$ $a_2$ \dots\ $a_n$, A 
$I(a_1 a_2 \ldots a_n)$---CHISLO INVERSIJ V PERESTANOVKE.

\dfn{tABLICEJ INVERSIJ} PERESTANOVKI $a_1$ $a_2$ \dots\ $a_n$ 
NAZYVAETSYA POSLEDOVATELXNOSTX CHISEL $b_1$ $b_2$ \dots\ $b_n$, 
GDE $b_j$---CHISLO |LEMENTOV, 
\emph{B\'OLXSHIH} $j$ I RASPOLOZHENNYH \emph{LEVEE} $j$. 
(dRUGIMI SLOVAMI, $b_j$---CHISLO INVERSIJ, U KOTORYH VTOROJ |LEMENT 
RAVEN~$j$.) nAPRIMER, TABLICEJ INVERSIJ PERESTANOVKI
$$
5\;9\;1\;8\;2\;6\;4\;7\;3 \eqno                     (1)
$$
BUDET
$$
2\;3\;6\;4\;0\;2\;2\;1\;0,\eqno  (2)
$$
POSKOLXKU 5 I 9 RASPOLOZHENY LEVEE 1; 5, 9, 8---LEVEE 2 I T.D., VSEGO 20 
INVERSIJ. pO OPREDELENIYU
$$
0\le{} b_1\le{} n-1,  0\le{} b_2 \le{} n-2,\ldots ,0\le{} b_{n-1}\le{} 1, 
b_n=0.\eqno (3)
$$

pOZHALUJ, NAIBOLEE VAZHNYJ FAKT, KASAYUSHCHIJSYA PERESTANOVOK, I 
USTANOVLENNYJ mARSHALLOM hOLLOM, |TO TO, CHTO \emph{TABLICA INVERSIJ 
EDINSTVENNYM OBRAZOM OPREDELYAET SOOTVETSTVUYUSHCHUYU PERESTANOVKU.} [sM. 
Proc. Symp. Applied Math., {\bf 6} (American Math. Society, 1956), 203.] iZ 
LYUBOJ TABLICY INVERSIJ $b_1$ $b_2$ \dots\ $b_n$, UDOVLETVORYAYUSHCHEJ USLOVIYAM 
(3), MOZHNO ODNOZNACHNO VOSSTANOVITX PERESTANOVKU, KOTORAYA POROZHDAET 
DANNUYU TABLICU, PUTEM POSLEDOVATELXNOGO OPREDELENIYA OTNOSITELXNOGO 
RASPOLOZHENIYA |LEMENTOV $n$, $n-1$, \dots, $1$ (V |TOM PORYADKE). nAPRIMER, 
PERESTANOVKU, SOOTVETSTVUYUSHCHUYU (2), MOZHNO POSTROITX SLEDUYUSHCHIM OBRAZOM:
VYPISHEM CHISLO 9; TAK KAK $b_8=1$, TO 8 STOIT PRAVEE 9. pOSKOLXKU 
$b_7=2$, TO 7 STOIT PRAVEE 8 I~9. tAK KAK $b_6=2$, TO 6 STOIT PRAVEE DVUH 
UZHE VYPISANNYH NAMI CHISEL; TAKIM OBRAZOM, IMEEM
$$
9\; 8\; 6\; 7.
$$
%% 26
pRIPISHEM TEPERX 5 SLEVA, POTOMU CHTO $b_5=0$; POMESHCHAEM 4 VSLED ZA 
CHETYRXMYA IZ UZHE ZAPISANNYH CHISEL, 3---POSLE SHESTI VYPISANNYH CHISEL (T. E. 
V PRAVYJ KONEC) I POLUCHAEM
$$
5\;9\;8\;6\;4\;7\;3.
$$
vSTAVIV ANALOGICHNYM OBRAZOM 2 I 1, PRIDEM K (1).

tAKOE SOOTVETSTVIE VAZHNO, POTOMU CHTO CHASTO MOZHNO ZAMENITX ZADACHU, 
SFORMULIROVANNUYU V TERMINAH PERESTANOVOK, |KVIVALENTNOJ EJ ZADACHEJ, 
SFORMULIROVANNOJ V TERMINAH TABLIC INVERSIJ, KOTORAYA, VOZMOZHNO, RESHAETSYA 
PROSHCHE. rASSMOTRIM, NAPRIMER, SAMYJ PROSTOJ VOPROS: SKOLXKO SUSHCHESTVUET 
PERESTANOVOK MNOZHESTVA $\{1, 2, \ldots, n\}$? oTVET DOLZHEN BYTX RAVEN CHISLU 
VSEVOZMOZHNYH TABLIC INVERSIJ, A IH LEGKO PERESCHITATX, TAK KAK $b_1$ MOZHNO 
VYBRATX $n$ RAZLICHNYMI SPOSOBAMI, $b_2$ MOZHNO NEZAVISIMO OT $b-1$ 
VYBRATX $n-1$ SPOSOBAMI, \dots, $b_n$---ODNIM SPOSOBOM; ITOGO 
$P(P-1)\ldots 1=n!$ RAZLICHNYH TABLIC INVERSIJ. tABLICY INVERSIJ PERESCHITATX
LEGCHE, 
POTOMU CHTO $b$ NEZAVISIMY, V TO VREMYA KAK $A$ DOLZHNY BYTX VSE RAZLICHNY.

v P. 1:2.10 MY ISSLEDOVALI ZADACHU O CHISLE LOKALXNYH MAKSIMUMOV 
PERESTANOVKI, ESLI CHITATX EE SPRAVA NALEVO; INYMI SLOVAMI, TREBOVALOSX 
PODSCHITATX KOLICHESTVO |LEMENTOV, KAZHDYJ IZ KOTORYH BOLXSHE LYUBOGO IZ 
SLEDUYUSHCHIH POSLE NEGO. (nAPRIMER, PRAVOSTORONNIE MAKSIMUMY V (1)---|TO 9, 
8, 7 I 3.) oNO RAVNO KOLICHESTVU INDEKSOV $j$, TAKIH, CHTO $b_j=n-j$. tAK KAK 
$b_1$ PRINIMAET ZNACHENIE $n-1$ S VEROYATNOSTXYU $1/n$, $b_2$ (NEZAVISIMO) 
PRINIMAET ZNACHENIE $n-2$ S VEROYATNOSTXYU $1/(n-1)$ I T.D., TO IZ RASSMOTRENIYA 
INVERSIJ YASNO, CHTO SREDNEE CHISLO PRAVOSTORONNIH  MAKSIMUMOV RAVNO
$$
{1\over n}+{1\over n-1}+\cdots+1=H_n.    
$$
aNALOGICHNYM SPOSOBOM LEGKO POLUCHITX I SOOTVETSTVUYUSHCHUYU PROIZVODYASHCHUYU 
FUNKCIYU.

dRUGIE PRIMENENIYA TABLIC INVERSIJ VSTRETYATSYA DALEE V |TOJ GLAVE V SVYAZI 
S KONKRETNYMI ALGORITMAMI SORTIROVKI.

yaSNO, CHTO ESLI POMENYATX MESTAMI \emph{SOSEDNIE} |LEMENTY 
PERESTANOVKI, TO OBSHCHEE CHISLO INVERSIJ UVELICHITSYA ILI UMENXSHITSYA NA 
EDINICU. nA RIS. 1 POKAZANY 24 PERESTANOVKI MNOZHESTVA $\{1, 2, 3, 4\}$; 
LINIYAMI SOEDINENY PERESTANOVKI, OTLICHAYUSHCHIESYA DRUG OT DRUGA POLOZHENIEM 
DVUH SOSEDNIH |LEMENTOV; DVIGAYASX VDOLX LINII VNIZ, MY .UVELICHIVAEM CHISLO 
INVERSIJ NA EDINICU. sLEDOVATELXNO, CHISLO INVERSIJ V PERESTANOVKE $P$ 
RAVNO DLINE NISHODYASHCHEGO PUTI IZ 1 2 3 4 V $n$ NA RIS.~1; VSE TAKIE PUTI 
DOLZHNY IMETX ODINAKOVUYU DLINU.

zAMETIM, CHTO |TU DIAGRAMMU MOZHNO RASSMATRIVATX KAK TREHMERNOE TVERDOE 
TELO---"USECHENNYJ OKTA|DR", IMEYUSHCHIJ 8 SHESTIUGOLXNYH
%% 27
I 6 KVADRATNYH GRANEJ. eTO ODIN IZ RAVNOMERNYH MNOGOGRANNIKOV, KOTORYE 
OBSUZHDAL aRHIMED (SM. UPR.,10).

\picture{
rIS. 1. uSECHENNYJ OKTA|DR, NA KOTOROM POKAZANO IZMENENIE CHISLA 
INVERSIJ, KOGDA MENYAYUTSYA MESTAMI DVA SOSEDNIH |LEMENTA PERESTANOVKI;
}

nE SLEDUET PUTATX "INVERSII" PERESTANOVOK S OBRATNYMI PERESTANOVKAMI. 
vSPOMNIM, CHTO PERESTANOVKU MOZHNO ZAPISYVATX V VIDE DVUH STROK
$$
\pmatrix{
1 & 2 & 3 & \ldots & n \cr
a_1 & a_2 & a_3 & \ldots & a_n \cr
};\eqno (4)
$$
\dfn{OBRATNOJ} K |TOJ PERESTANOVKE NAZYVAETSYA PERESTANOVKA $a'_1$, $a'_2$, 
\dots\ $a'_n$, KOTORAYA POLUCHAETSYA, ESLI V (4) POMENYATX MESTAMI STROKI, A ZATEM 
UPORYADOCHITX STOLBCY V VOZRASTAYUSHCHEM PORYADKE PO VERHNIM |LEMENTAM: 
$$\pmatrix{
a_1 & a_2 & a_3 & \ldots & a_n \cr
1 & 2 & 3 & \ldots & n \cr
}=\pmatrix{
1 & 2 & 3 & \ldots & n \cr
a'_1 & a'_2 & a'_3 & \ldots & a'_n \cr
};
\eqno(5)
$$
nAPRIMER, OBRATNOJ K PERESTANOVKE 5 9 1 8 2 6 4 7 3 BUDET PERESTANOVKA
%% 28
3 5 9 7 1 6 8 4 2, TAK KAK
$$
\pmatrix{
5 & 9 &1 &8 &2 &6 &4 &7 &3\cr
1 & 2 & 3&4 &5 &6 &7 &8 &9\cr
}=\pmatrix{
1 &2 &3 &4 &5 &6 &7 &8 &9\cr
3 &5 &9 &7 &1 &6 &8 &4 &2\cr
}.
$$
   mOZHNO DATX DRUGOE OPREDELENIE OBRATNOJ PERESTANOVKI: $a'_j=k$ TOGDA I 
TOLXKO TOGDA, KOGDA $A_k=j$.

oBRATNUYU PERESTANOVKU VPERVYE VV�L X. a. rOTE [V k.F.~Hindenburg(ed.)., 
Sammlung combinatorisch-analytischer Abhandlungen, 2 (Leipzig, 1800), 
263--305]; ON ZAMETIL INTERESNUYU SVYAZX MEZHDU OBRATNYMI PERESTANOVKAMI I 
INVERSIYAMI: \emph{OBRATNAYA PERESTANOVKA SODERZHIT ROVNO STOLXKO ZHE 
INVERSIJ, SKOLXKO ISHODNAYA}. rOTE DAL NE SAMOE PROSTOE DOKAZATELXSTVO |TOGO 
FAKTA, NO ONO POUCHITELXNO I PRITOM DOVOLXNO KRASIVO. pOSTROIM TABLICU 
RAZMERA $n\times n$ I POSTAVIM TOCHKI V $j$-J KLETKE $i$-J STROKI, ESLI 
$a_i=j$. pOSLE |TOGO RASSTAVIM KRESTIKI VO VSEH KLETKAH, SNIZU OT KOTORYH (V 
TOM ZHE STOLBCE) I SPRAVA (V TOJ ZHE STROKE) ESTX TOCHKI. nAPRIMER, DLYA 5 9 1 8 2 
6 4 7 3 DIAGRAMMA BUDET TAKOJ:
$$
%%  picture
$$
kOLICHESTVO KRESTIKOV RAVNO CHISLU INVERSIJ, TAK KAK NETRUDNO VIDETX, CHTO 
$b_j$ RAVNO CHISLU KRESTIKOV V $j$-M STOLBCE. eSLI MY TEPERX TRANSPONIRUEM 
DIAGRAMMU (POMENYAV ROLYAMI STROKI I STOLBCY), TO POLUCHIM DIAGRAMMU DLYA 
OBRATNOJ PO OTNOSHENIYU K ISHODNOJ PERESTANOVKI; ZNACHIT, CHISLO KRESTIKOV 
(CHISLO INVERSIJ) ODINAKOVO V OBOIH SLUCHAYAH. rOTE ISPOLXZOVAL |TOT FAKT DLYA 
DOKAZATELXSTVA TOGO, CHTO DETERMINANT MATRICY NE MENYAETSYA PRI 
TRANSPONIROVANII.

dLYA ANALIZA NEKOTORYH ALGORITMOV SORTIROVKI NEOBHODIMO ZNATX CHISLO 
PERESTANOVOK $P$ |LEMENTOV, SODERZHASHCHIH ROVNO $k$ INVERSIJ. oBOZNACHIM |TO 
CHISLO CHEREZ $I_n(k)$; V TABL. 1 PRIVEDENY PERVYE NESKOLXKO ZNACHENIJ |TOJ 
FUNKCII.
%% 29


\htable{tABLICA 1}{pERESTANOVKI S $k$ INVERSIYAMI}%
{$#$\bskip\hfill&&\hfill\bskip$#$\bskip\hfill\cr
n & I_n(0) & I_n(1) & I_n(2) & I_n(3) & I_n(4) & I_n(5) & I_n(6) & I_n(7) & I_n(8) & 
I_n(9) & I_n(10) & I_n(11)\cr
1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\cr
2 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\cr
3 & 1 & 2 & 2 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\cr
4 & 1 & 3 & 5 & 6 & 5 & 3 & 1 & 0 & 0 & 0 & 0 & 0\cr
5 & 1 & 4 & 9 & 15 & 20 & 22 & 20 & 15 & 9 & 4 & 1 & 0\cr
6 & 1 & 5 & 14 & 29 & 49 & 71 & 90 & 101 & 101 & 90 & 71 & 49 \cr
}

iZ RASSMOTRENIYA TABLICY INVERSIJ $b_1$ $b_2$ \dots.$b_n$ YASNO, CHTO 
$I_k(0)=1$, $I_n(1)=n-1$  I CHTO VYPOLNYAETSYA SVOJSTVO SIMMETRII:
$$
I_n\left(\left({n \atop 2}\right)-k\right)=I_n(k)\eqno (6)
$$
dALEE, TAK KAK ZNACHENIYA $b$ MOZHNO VYBIRATX NEZAVISIMO DRUG OT DRUGA, TO 
NETRUDNO VIDETX, CHTO PROIZVODYASHCHAYA FUNKCIYA
$$
G_n(z)=I_n(0)+I_n(1)z+I_n(2)z^2+\cdots
\eqno (7)
$$
UDOVLETVORYAET SOOTNOSHENIYU $G_n(z) = (1 +z+ \cdots +z^{n-1})G_{n-1}(z)$;
SLEDOVATELXNO, ONA IMEET DOVOLXNO, PROSTOJ VID
$$
(1+z+\cdots+z^{n-1})\ldots(1+z)(1)=(1-z^n)\ldots(l-z^2)(l-z)/(l-z)^n.
\eqno(8)
$$
s POMOSHCHXYU |TOJ PROIZVODYASHCHEJ FUNKCII MOZHNO LEGKO PRODOLZHITX TABL. 1 I 
UBEDITXSYA, CHTO CHISLA, RASPOLOZHENNYE POD STUPENCHATOJ LINIEJ V TABLICE, 
UDOVLETVORYAYUT SOOTNOSHENIYU
$$
I_n(k)=I_n(k-1)+I_{n-1}(k) \rem{PRI $k<n$.}
\eqno(9)
$$
(dLYA CHISEL \emph{NAD} STUPENCHATOJ LINIEJ |TO SOOTNOSHENIE \emph{NE} 
VYPOLNYAETSYA.) bOLEE SLOZHNYE RASSUZHDENIYA (SM. UPR. 14) POKAZYVAYUT, CHTO NA 
SAMOM DELE IMEYUT MESTO FORMULY
$$
\eqalign{
I_n(2)&=\left({ n \atop 2}\right)-1, n \ge{} 2;\cr
I_n(3)&=\left({ n+1 \atop 3}\right) - \left({ n \atop 1}\right), n \ge{} 3;\cr
I_n(4)&=\left({n+2 \atop 4}\right)-\left({ n+1\atop 2}\right), n \ge{} 4;\cr
I_n(5)&=\left({n+3 \atop 5}\right)-\left({ n+2\atop3 }\right)+1, n \ge{} 5.\cr
}
$$
%% 30
oBSHCHAYA FORMULA DLYA $I_n(k)$ SODERZHIT OKOLO $1.6\sqrt k$ SLAGAEMYH:
$$
\eqalign{
I_n(k)=&\left({ n+k-2\atop k}\right)-\left({ n+k-3\atop k-2 }\right)+
\left({ n+k-6\atop k-5}\right)+\left({ n+k-8\atop k-7}\right)-\cdots\hfill\cr
&+(-1)^j\left(\left({ n+k-u_j-1\atop k-u_j}\right)+ \left({ n+k-u_j-j-1\atop k-u_j-j}\right) 
\right)+\cdots, \rem{$n\ge k$,}\quad\cr
}
\eqno (10)
$$
GDE $u_j=(3j^2-j)/2$ --- TAK NAZYVAEMOE "PYATIUGOLXNOE CHISLO".

rAZDELIV $G_n(z)$ NA $n!$, POLUCHIM PROIZVODYASHCHUYU FUNKCIYU $g_n(z)$ 
RASPREDELENIYA VEROYATNOSTEJ CHISLA INVERSIJ V SLUCHAJNOJ PERESTANOVKE $P$ 
|LEMENTOV. oNA RAVNA PROIZVEDENIYU
$$
g_n(z)=h_1(z)h_2(z)\ldots h_n(z),\eqno (11)
$$
GDE $h_k (z) = (1 + z + z^2 +\cdots + z^{k-1})/k$ --- PROIZVODYASHCHAYA FUNKCIYA 
RAVNOMERNOGO RASPREDELENIYA SLUCHAJNOJ VELICHINY, PRINIMAYUSHCHEJ CELYE 
NEOTRICATELXNYE ZNACHENIYA, MENXSHIE $k$. oTSYUDA
$$
\eqalignno{
\mean (g_n) &= \mean (h_1) + \mean (h_2) + \cdots + \mean (h_n) =\cr
&=0 +{1\over2}+\cdots+{n-1\over 2}={n(n-1)\over 4}; & (12)\cr 
\var (g_n)& = \var (h_1) + \var (h_2)+ \cdots + \var (h_n)=\cr
&=0 +{1\over 4}+\cdots+{n^2-1\over 12}={n(2n+5)(n-1)\over 72}&(13)\cr
}
$$
tAKIM OBRAZOM, SREDNEE CHISLO INVERSIJ DOVOLXNO VELIKO---OKOLO 
${1\over 4}n^2$; STANDARTNOE OTKLONENIE TAKZHE VESXMA VELIKO---OKOLO 
${1\over6}n^{3/2}$.

v KACHESTVE INTERESNOGO ZAVERSHENIYA IZUCHENIYA INVERSIJ RASSMOTRIM 
ODNO ZAMECHATELXNOE OTKRYTIE, PRINADLEZHASHCHEE 
p. a. mAK-mAGONU [{\sl Amer. J. Math.,\/} {\bf 35} (1913), 281--322]. 
oPREDELIM \dfn{INDEKS} PERESTANOVKI $a_1$ $a_2$ \dots $a_n$ KAK SUMMU 
VSEH $j$, TAKIH, CHTO $A_j>a_{j+1}$, $1 \le < n$. nAPRIMER, INDEKS 
PERESTANOVKI 5 9 1 8 2 6 4 7 3 RAVEN $2+4+6+8=20$. iNDEKS SLUCHAJNO SOVPAL 
S CHISLOM INVERSIJ. eSLI SOSTAVITX SPISOK VSEH 24 PERESTANOVOK MNOZHESTVA 
$\{1, 2, 3, 4\}$, A IMENNO
%% 31
{
\def|{\,\vrule}
\offinterlineskip
\ctable{
\strut\hfill$#$\bskip\hfill&&\hfill$#$\bskip\hfill\cr
\multispan{4}pERESTANOVKA &   iNDEKS & iNVERSII & \multispan{4}pERESTANOVKA&    iNDEKS &iNVERSII \cr
1 & 2 & 3 & 4 &    0  &    0   & 3| & 1 & 2 & 4 &  1  & 2 \cr
1 & 2 & 4|& 3 &    3  &    1   & 3| & 1 & 4|& 2 &  4  & 3 \cr
1 & 3|& 2 & 4 &    2  &    1   & 3| & 2|& 1 & 4 &  3  & 3 \cr
1 & 3 & 4|& 2 &    3  &    2   & 3| & 2 & 4|& 1 &  4  & 4 \cr
1 & 4|& 2 & 3 &    2  &    2   & 3  & 4|& 1 & 2 &  2  & 4 \cr
1 & 4|& 3|& 2 &    5  &    3   & 3  & 4|& 2|& 1 &  5  & 5 \cr
2|& 1 & z & 4 &    1  &    1   & 4| & 1 & 2 & 3 &  1  & 3 \cr
2|& 1 & 4|& 3 &    4  &    2   & 4| & 1 & 3|& 2 &  4  & 4 \cr
2 & 3|& 1 & 4 &    2  &    2   & 4| & 2|& 1 & 3 &  3  & 4 \cr
2 & 3 & 4|& 1 &    3  &    3   & 4| & 2 & 3|& 1 &  4  & 5 \cr
2 & 4|& 1 & 3 &    2  &    8   & 4| & 3|& 1 & 2 &  3  & 5 \cr
2 & 4|& 3|& 1 &    5  &    4   & 4| & 3|& 2|& 1 &  6  & 6 \cr
}
}
TO VIDNO, CHTO \emph{CHISLO PERESTANOVOK, IMEYUSHCHIH DANNYJ INDEKS $k$, 
RAVNO CHISLU PERESTANOVOK, IMEYUSHCHIH $k$ INVERSIJ.}

nA PERVYJ VZGLYAD |TOT FAKT MOZHET POKAZATXSYA POCHTI OCHEVIDNYM, ODNAKO 
POSLE NEKOTORYH RAZMYSHLENIJ ON NACHINAET KAZATXSYA CHUTX LI NE 
MISTICHESKIM, I NE VIDNO NIKAKOGO PROSTOGO PRYAMOGO EGO DOKAZATELXSTVA. 
mAK-mAGON NASHEL SLEDUYUSHCHEE OSTROUMNOE KOSVENNOE DOKAZATELXSTVO: PUSTX 
$J(A_1 A_2 \ldots a_n)$---INDEKS PERESTANOVKI $a_1$ $a_2$ \dots $a_n$, I 
SOOTVETSTVUYUSHCHAYA PROIZVODYASHCHAYA FUNKCIYA ESTX
$$
H_n(z)=\sum z^{J(a_1 a_2 \ldots a_n)}, \eqno (14)
$$
GDE SUMMA BERETSYA PO VSEM PERESTANOVKAM MNOZHESTVA $\{1, 2, \ldots., P\}$. 
mY HOTELI BY DOKAZATX, CHTO $H_n(z)=G_n(z)$. dLYA |TOGO OPREDELIM 
VZAIMNO ODNOZNACHNOE SOOTVETSTVIE MEZHDU $n$-KAMI 
$(q_1, q_2, \ldots, q_n)$ NEOTRICATELXNYH CELYH CHISEL, S ODNOJ STORONY, I 
UPORYADOCHENNYMI PARAMI $n$-OK
$$
((a_1, a_2, \ldots, a_n), (p_1, p_2, \ldots, p_n)),
$$
S DRUGOJ STORONY; ZDESX $A_1$ $A_2$ \dots\ $a_n$---PERESTANOVKA 
MNOZHESTVA $\{1, 2, \ldots, P\}$ I $p_1\ge p_2\ge \ldots \ge p_n \ge 0$.. eTO 
SOOTVETSTVIE BUDET UDOVLETVORYATX USLOVIYU
$$
q_1+q_2+\cdots+q_n=J(a_1 a_2 \ldots a_n)+(p_1+p_2+\cdots+p_n).
\eqno (15)
$$
pROIZVODYASHCHAYA FUNKCIYA $\sum z^{q_1+q_2+\cdots+q_n}$, GDE SUMMA BERETSYA 
PO VSEM $n$-KAM NEOTRICATELXNYH CELYH CHISEL $(q_1,  q_2, \ldots, q_n)$, 
RAVNA $Q_n (z) =1/(1-z)^z$; A PROIZVODYASHCHAYA FUNKCIYA $\sum 
z^{p_1+p_2+\cdots+p_n}$, GDE SUMMA BERETSYA PO VSEM $n$-KAM CELYH CHISEL 
$(R_1, R_2, \ldots p_n)$, TAKIH, CHTO $p_1\ge p_2\ge \ldots \ge p_n \ge 0$, RAVNA, 
KAK POKAZANO V UPR.~15,
$$
P_n(z)=1/(1-z)(1-z^2)\ldots(1-z^n).
\eqno(16)
$$
%% 32
sUSHCHESTVOVANIE VZAIMNO ODNOZNACHNOGO SOOTVETSTVIYA, KOTOROE UDOVLETVORYAET 
USLOVIYU (15) I KOTOROE MY SOBIRAEMSYA USTANOVITX, DOKAZYVAET RAVENSTVO 
$Q_n(z)=H_n(z) P_n(z)$, T.E.
$$
H_n(z)=Q_n(z)/P_n(z)=G_n(z).
$$

tREBUEMOE SOOTVETSTVIE OPREDELYAETSYA S POMOSHCHXYU ALGORITMA 
"SORTIROVKI". nACHAV S PUSTOGO SPISKA, PRI $k=1$, $2$, \dots, $n$ (V TAKOM 
PORYADKE) VSTAVLYAEM V |TOT SPISOK CHISLA $q_k$ SLEDUYUSHCHIM OBRAZOM: PUSTX 
POSLE $k-1$ SHAGOV V SPISKE SODERZHATSYA |LEMENTY
$p_1$, $p_2$, \dots, $p_{k-1}$, GDE $p_1\ge p_2\ge \ldots \ge p_{k-1}$, I 
OPREDELENA PERESTANOVKA $a_1$ $a_2$ \dots $a_n$ MNOZHESTVA 
$\{n, n-1, \ldots, n-k+2\}$. 
pUSTX $j$---EDINSTVENNOE CELOE CHISLO, TAKOE, CHTO 
$p_j>q_k\ge p_{j+1}$; ESLI $q_k\ge p_1$, TO POLAGAEM $j=0$, 
A ESLI $p_{k-1}>q_k$, TO 
POLAGAEM $j=k-1$. vSTAVIM TEPERX $q_k$  V SPISOK MEZHDU $p_j$ I $p_{j+1}$, 
A CELOE CHISLO $(n-k+1)$---V PERESTANOVKU MEZHDU $a_j$, I $a_{j+1}$. 
pRODELAV |TO DLYA VSEH $k$, POLUCHIM PERESTANOVKU $a_1$ $a_2$ \dots  $a_n$ 
MNOZHESTVA $\{1,2, \ldots, n\}$ I $n$-KU CHISEL 
$(p_1, p_2, \ldots, p_n)$, TAKIH, CHTO $p_1\ge p_2 \ge \ldots \ge p_n\ge 0$ I 
$$
p_j > p_{j+1}, \rem{ESLI $a_j>a_{j+1}$.}
$$
nAKONEC, DLYA $1 \le j < n$ VYCHTEM EDINICU IZ VSEH CHISEL $p_1$, \dots, $p_j$ 
PRI VSEH $j$, TAKIH, CHTO $a_j>a_{j+1}$. pOLUCHENNAYA PARA 
$((A_1, A_2, \ldots, A_n), (p_1, p_2, \ldots, p_n))$ UDOVLETVORYAET USLOVIYU (15).

pUSTX, NAPRIMER, $n=6$ I $(q_1, \ldots, q_6)=(3, 1, 4, 0, 0, 1).$ 
pOSTROENIE PROISHODIT SLEDUYUSHCHIM OBRAZOM:
{
\offinterlineskip
\ctable{
\strut\hfil$#$\bskip\hfil&&\hfil$#$\bskip\hfil\cr
k & \multispan{6} $p_1\ldots p_k$\hfill & \multispan{5} $a_1\ldots a_k$\hfill \cr
1 & 3 &   &   &   &   &   & 6 \cr
2 & 3 & 1 &   &   &   &   & 6 & 5 \cr
3 & 4 & 3 & 1 &   &   &   & 4 & 6 & 5 \cr
4 & 4 & 3 & 1 & 0 &   &   & 4 & 6 & 5 & 3 \cr
5 & 4 & 3 & 1 & 0 & 0 &   & 4 & 6 & 5 & 2 & 3 \cr
6 & 4 & 3 & 1 & 1 & 0 & 0 & 4 & 6 & 1 & 5 & 2 & 3 \cr
}
}
pOSLE ZAKLYUCHITELXNOJ KORREKTIROVKI POLUCHAEM 
$(p_1, \ldots, p_6)=(2, 1, 0, 0, 0,0)$.

nETRUDNO PROVERITX, CHTO |TOT PROCESS OBRATIM; TAKIM OBRAZOM, 
TREBUEMOE SOOTVETSTVIE USTANOVLENO I TEOREMA mAK-mAGONA DOKAZANA. 
aNALOGICHNOE VZAIMNO ODNOZNACHNOE SOOTVETSTVIE VSTRETITSYA NAM V P.~5.1.4.
\excercises
\ex[10] kAKOVA TABLICA INVERSIJ DLYA PERESTANOVKI 2 7 1 8 4 5 9 3 B? kAKOJ PERESTANOVKE 
SOOTVETSTVUET TABLICA INVERSIJ  5  0  1  2  1  2 0  0?

\ex[M15] rESHENIEM ZADACHI iOSIFA, SFORMULIROVANNOJ V UPR. 1.3.2--22, YAVLYAETSYA 
PERESTANOVKA MNOZHESTVA $\{1, 2, \ldots n\}$; RESHENIE DLYA PRIVEDENNOGO TAM PRIMERA 
$(n=8,m=4)$---PERESTANOVKA 5 4 6 1 3 8 7 2. sOOTVETSTVUYUSHCHAYA |TOJ PERESTANOVKE TABLICA 
INVERSIJ---3 6 3 1 0 0 1 0. nAJDITE PROSTOE REKURRENTNOE
%% 33
SOOTNOSHENIE DLYA |LEMENTOV $b_1$ $b_2$ \dots $b_n$ TABLICY 
INVERSIJ V OBSHCHEJ ZADACHE iOSIFA DLYA $n$ CHELOVEK, ESLI KAZNYAT KAZHDOGO $m$-GO 
CHELOVEKA.

\ex[18] pUSTX PERESTANOVKE $a_1$ $a_2$ \dots $a_n$ SOOTVETSTVUET TABLICA 
INVERSIJ $b_1$ $b_2$ \dots $b_n$; KAKOJ PERESTANOVKE $\bar a_1$ $\bar a_2$ 
\dots $\bar a_n$ SOOTVETSTVUET TABLICA INVERSIJ
$$
(n-1-b_1) (n-2-b_2) \ldots  (0-b_n)?
$$

\rex[20] pRIDUMAJTE ALGORITM, GODNYJ DLYA REALIZACII NA evm, KOTORYJ PO 
DANNOJ TABLICE INVERSIJ  $b_1$ $b_2$ \dots $b_n$, UDOVLETVORYAYUSHCHEJ USLOVIYAM 
(3), STROIL BY SOOTVETSTVUYUSHCHUYU PERESTANOVKU  $a_1$ $a_2$ \dots $a_n$. 
[{\sl uKAZANIE:\/} VSPOMNITE METODY RABOTY SO SVYAZANNOJ PAMYATXYU.]

\ex[35] dLYA VYPOLNENIYA NA TIPICHNOJ evm ALGORITM IZ UPR.~4 TREBUET VREMENI, 
PRIBLIZITELXNO PROPORCIONALXNOGO $n^2$; MOZHNO LI SOZDATX ALGORITM, VREMYA 
RABOTY KOTOROGO BYLO BY SUSHCHESTVENNO MENXSHE $n^2$?

\rex[26] pRIDUMAJTE ALGORITM VYCHISLENIYA TABLICY INVERSIJ $b_1$ $b_2$ \dots 
$b_n$, SOOTVETSTVUYUSHCHEJ DANNOJ PERESTANOVKE $a_1$ $a_2$ \dots $a_n$ 
MNOZHESTVA $\{1, 2, \ldots, P\}$,, VREMYA RABOTY KOTOROGO NA TIPICHNOJ evm 
BYLO BY PORYADKA $n\log n$.

\ex[20] pOMIMO TABLICY $b_1$ $b_2$ \dots $b_n$, OPREDELENNOJ V |TOM PUNKTE,
 MOZHNO  OPREDELITX NEKOTORYE DRUGIE TIPY TABLIC INVERSIJ, SOOTVETSTVUYUSHCHIH 
DANNOJ PERESTANOVKE $a_1$ $a_2$ \dots $a_n$ MNOZHESTVA 
$\{ 1, 2, \ldots, n\}$. v |TOM UPRAZHNENII MY RASSMOTRIM TRI DRUGIH TIPA TABLIC 
INVERSIJ, KOTORYE VOZNIKAYUT V PRILOZHENIYAH.

pUSTX $c_j$---CHISLO INVERSIJ, \emph{PERVAYA} KOMPONENTA KOTORYH RAVNA $j$, 
T.~E. CHISLO |LEMENTOV, MENXSHIH $j$ I RASPOLOZHENNYH \emph{PRAVEE} $j$. 
[pERESTANOVKE (1) SOOTVETSTVUET TABLICA $0$ $0$ $0$ $1$ $4$ $2$ $1$ $5$ 
$7$; YASNO, CHTO$ 0\le c_j<j$.] pUSTX $B_j=b_{a_j}$ I~$C_j=c_{a_j}$.

pOKAZHITE, CHTO PRI $1 \le j \le n$ SPRAVEDLIVY NERAVENSTVA $0\le B_j<j$ I 
$0\le C_j\le n-j$; POKAZHITE TAKZHE, CHTO PERESTANOVKU $a_1$ $a_2$ \dots 
$a_n$ MOZHNO ODNOZNACHNO OPREDELITX, ESLI ZADANA ILI TABLICA $c_1$ $c_2$ 
\dots $c_n$, ILI $B_1$ $B_2$ \dots $B_n$, ILI $C_1$ $C_2$ \dots $C_n$.

\ex[m24] sOHRANIM OBOZNACHENIYA UPR.~7; PUSTX $a'_1$ $a'_2$ \dots 
$a'_n$---PERESTANOVKA, OBRATNAYA K  $a_1$ $a_2$ \dots $a_n$ I PUSTX 
SOOTVETSTVUYUSHCHIE EJ TABLICY INVERSIJ--- $b'_1$ $b'_2$ \dots $b'_n$, $c'_1$ 
$c'_2$ \dots $c'_n$, $B'_1$ $B'_2$ \dots $B'_n$  I $C'_1$ $C'_2$ \dots 
$C'_n$. nAJDITE KAK MOZHNO BOLXSHE INTERESNYH SOOTNOSHENIJ MEZHDU $a_j$, $b_j$,
$c_j$, $B_j$, $C_j$, $a'_j$, $b'_j$, $c'_j$, $B'_j$, $C'_j$.

\rex[m21] dOKAZHITE, CHTO V OBOZNACHENIYAH UPR.~7 PERESTANOVKA $a_1$ $a_2$ 
\dots $a_n$ OBRATNA SAMOJ SEBE TOGDA I TOLXKO TOGDA, KOGDA $b_j=C_j$ PRI 
$1\le j\le n$.

\ex[vm20] rASSMOTRITE RIS.~1 KAK MNOGOGRANNIK V TREHMERNOM PROSTRANSTVE. 
chEMU RAVEN DIAMETR USECHENNOGO OKTA|DRA (RASSTOYANIE MEZHDU VERSHINAMI 1234 I 
4321), ESLI VSE REBRA IMEYUT EDINICHNUYU DLINU?

\ex[m25] (A) pUSTX $\pi=a_1\ a_2\ldots a_n$---PERESTANOVKA MNOZHESTVA $\{1, 2,
 \ldots, n\}$, $E(x)=\{(a_i, a_j)\vert i<j, a_i>a_j\}$---MNOZHESTVO EE 
INVERSIJ, a
$$
\overline{E}(\pi)=\{(a_i, a_j)\vert i>j, a_i>a_j\}
$$
---MNOZHESTVO EE '"NEINVERSIJ". dOKAZHITE, CHTO $E(\pi)$ I~$\overline{E}(\pi)$ 
TRANZITIVNY. [mNOZHESTVO $S$ UPORYADOCHENNYH PAR NAZYVAETSYA 
\dfn{TRANZITIVNYM}, ESLI DLYA LYUBYH $(a, b)$ I~$(b,c)$, PRINADLEZHASHCHIH $S$, 
PARA $(a, c)$ TAKZHE PRINADLEZHIT $S$.] (b) oBRATNO, PUSTX $E$---LYUBOE 
TRANZITIVNOE PODMNOZHESTVO MNOZHESTVA 
$T=\{(x, y)\vert 1\le  y < x\le n\}$, DOPOLNENIE KOTOROGO $T\backslash E$ 
TRANZITIVNO. dOKAZHITE, CHTO SUSHCHESTVUET PERESTANOVKA $\pi$, TAKAYA, CHTO $E(\pi)=E$.

\ex[m28] iSPOLXZUYA OBOZNACHENIYA PREDYDUSHCHEGO UPRAZHNENIYA, DOKAZHITE, CHTO ESLI 
$\pi_1$ I $\pi_2$---PERESTANOVKI, A $E$---MINIMALXNOE TRANZITIVNOE MNOZHESTVO,
 SODERZHASHCHEE $E(\pi_1)\cup E(\pi_2)$, TO $\overline{E}$---TOZHE TRANZITIVNOE 
MNOZHESTVO. [sLEDOVATELXNO, ESLI MY BUDEM GOVORITX, CHTO $\pi_1$ NAHODITSYA 
"NAD" $\pi_2$, KOGDA 
$E(\pi_1)\subseteq E(\pi_2)$, TO OPREDELENA RESHETKA PERESTANOVOK; 
SUSHCHESTVUET EDINSTVENNAYA "SAMAYA NIZKAYA" PERESTANOVKA, NAHODYASHCHAYASYA "NAD" 
DVUMYA DANNYMI PERESTANOVKAMI. dIAGRAMMA RESHETKI PRI  $n=4$ PREDSTAVLENA NA 
RIS. 1.]
%% 34

\bye
