\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_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\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 $ka_{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_ja_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