\input style \chapno=5\subchno=2\chapnotrue \subchap{optimal'naya sortirovka} % 5.3 tEPERX, KOGDA MY PROANALIZIROVALI TAKOE MNOZHESTVO METODOV VNUTRENNEJ SORTIROVKI, PRISHLO VREMYA OBRATITXSYA K BOLEE OBSHCHEMU VOPROSU: \emph{KAKOJ METOD VNUTRENNEJ SORTIROVKI NAILUCHSHIJ?} sUSHCHESTVUET LI TAKOJ VERHNIJ PREDEL SKOROSTI SORTIROVKI, KOTOROGO BY NE MOG DOSTICHX NI ODIN PROGRAMMIST, KAK BY ISKUSEN ON NI BYL? rAZUMEETSYA, NAILUCHSHEGO VOZMOZHNOGO SPOSOBA SORTIROVKI \emph{NET}; MY DOLZHNY TOCHNO OPREDELITX, CHTO PONIMATX POD SLOVOM "NAILUCHSHIJ", NO NE SUSHCHESTVUET NAILUCHSHEGO VOZMOZHNOGO SPOSOBA OPREDELITX SLOVO "NAILUCHSHIJ". aNALOGICHNYE VOPROSY OB OPTIMALXNOSTI ALGORITMOV MY OBSUZHDALI V P.~4.3.3, 4.6.3 I~4.6.4, GDE RASSMATRIVALOSX UMNOZHENIE S VYSOKOJ TOCHNOSTXYU I VYCHISLENIE POLINOMOV. v KAZHDOM SLUCHAE, DLYA TOGO CHTOBY VYPOLNYALISX USLOVIYA "DOSTATOCHNOSTI", T.~E.\ CHTOBY ZADACHA STALA RAZRESHIMOJ, NEOBHODIMO BYLO SFORMULIROVATX DOVOLXNO PROSTOE OPREDELENIE ALGORITMA, "NAILUCHSHEGO IZ VOZMOZHNYH". i V KAZHDOM SLUCHAE PERED NAMI VSTAVALI INTERESNEJSHIE ZADACHI, NASTOLXKO SLOZHNYE, CHTO ONI DO SIH POR POLNOSTXYU NE RESHENY. tAK ZHE OBSTOIT DELO I S SORTIROVKOJ: BYLI POLUCHENY NEKOTORYE INTERESNYE REZULXTATY, NO OSTALOSX ESHCHE MNOGO INTRIGUYUSHCHIH VOPROSOV, NA KOTORYE DO SIH POR NET OTVETOV. iZUCHENIE VNUTRENNEGO MEHANIZMA METODOV SORTIROVKI OBYCHNO BYLO NAPRAVLENO NA MINIMIZACIYU CHISLA SRAVNENIJ KLYUCHEJ PRI SORTIROVKE $n$~|LEMENTOV, ILI SLIYANII $m$~|LEMENTOV S $n$~|LEMENTAMI, ILI VYBORE $t\hbox{-Go}$~NAIBOLXSHEGO |LEMENTA IZ NEUPORYADOCHENNOGO NABORA $n$~|LEMENTOV. v P.~5.3.1, 5.3.2 I~5.3.3 |TI VOPROSY OBSUZHDAYUTSYA V OBSHCHEM SLUCHAE; V P.~5.3.4 RASSMATRIVAYUTSYA ANALOGICHNYE VOPROSY S INTERESNYM OGRANICHENIEM: POSLEDOVATELXNOSTX SRAVNENIJ DOLZHNA BYTX, PO SUSHCHESTVU, ZARANEE FIKSIROVANA. nEKOTORYE DRUGIE TIPY INTERESNYH TEORETICHESKIH VOPROSOV, SVYAZANNYH S OPTIMALXNOJ SORTIROVKOJ, MOZHNO NAJTI V UPRAZHNENIYAH K P.~5.3.4 I V OBSUZHDENII VNESHNEJ SORTIROVKI V P.~5.4.4. %% 219 \subsubchap{sORTIROVKA S MINIMALXNYM CHISLOM SRAVNENIJ} % 5.3.1 oCHEVIDNO, MINIMALXNOE CHISLO SRAVNENIJ KLYUCHEJ, NEOBHODIMOE DLYA SORTIROVKI $n$~|LEMENTOV, RAVNO~\emph{NULYU,} POSKOLXKU, KAK MY VIDELI, SUSHCHESTVUYUT METODY PORAZRYADNOJ SORTIROVKI, V KOTORYH VOOBSHCHE NE VYPOLNYAETSYA SRAVNENIJ. v SAMOM DELE, MOZHNO NAPISATX \MIX-PROGRAMMY, SPOSOBNYE SORTIROVATX I NE SODERZHASHCHIE TEM NE MENEE NI ODNOJ KOMANDY USLOVNOGO PEREHODA! (sM.~UPR.~5-6 V NACHALE |TOJ GLAVY.) mY TAKZHE VSTRECHALISX S NESKOLXKIMI METODAMI SORTIROVKI, KOTORYE, PO SUSHCHESTVU, BYLI OSNOVANY NA SRAVNENII KLYUCHEJ, NO VREMYA RABOTY KOTORYH NA DELE OPREDELYALOSX DRUGIMI FAKTORAMI, TAKIMI, KAK PEREMESHCHENIE DANNYH, VSPOMOGATELXNYE OPERACII I~T.~D. pO|TOMU YASNO, CHTO PODSCHET CHISLA SRAVNENIJ---NE EDINSTVENNYJ SPOSOB IZMERITX |FFEKTIVNOSTX METODA SORTIROVKI. oDNAKO V LYUBOM SLUCHAE NEBEZYNTERESNO PROVESTI TSHCHATELXNOE ISSLEDOVANIE CHISLA SRAVNENIJ, POSKOLXKU TEORETICHESKOE IZUCHENIE |TOGO VOPROSA POZVOLIT NAM S POLXZOJ DLYA DELA PRONIKNUTX VO VNUTRENNYUYU PRIRODU PROCESSOV SORTIROVKI, A TAKZHE POMOZHET OTTOCHITX MASTERSTVO DLYA RESHENIYA BOLEE PRAKTICHESKIH ZADACH, KOTORYE MOGUT VSTATX PERED NAMI V BUDUSHCHEM. chTOBY ISKLYUCHITX PORAZRYADNUYU SORTIROVKU, GDE SOVSEM NE VYPOLNYAETSYA SRAVNENIJ, OGRANICHIMSYA OBSUZHDENIEM METODOV SORTIROVKI, OSNOVANNYH TOLXKO NA ABSTRAKTNOM LINEJNOM OTNOSHENII PORYADKA "$<$" MEZHDU KLYUCHAMI, RASSMOTRENNOM V NACHALE |TOJ GLAVY. dLYA PROSTOTY MY TAKZHE OGRANICHIM SVOE OBSUZHDENIE SLUCHAEM \emph{RAZLICHNYH} KLYUCHEJ, A |TO ZNACHIT, CHTO PRI LYUBOM SRAVNENII KLYUCHEJ~$K_i$ I~$K_j$ VOZMOZHNY LISHX DVA ISHODA: LIBO~$K_iK_j$. (rASPROSTRANENIE |TOJ TEORII NA OBSHCHIJ SLUCHAJ, KOGDA DOPUSKAYUTSYA RAVNYE KLYUCHI, SM.~V UPR.~OT~3 DO~12.) zADACHU SORTIROVKI POSREDSTVOM SRAVNENIJ MOZHNO SFORMULIROVATX TAKZHE DRUGIMI |KVIVALENTNYMI SPOSOBAMI. eSLI ESTX $n$~GRUZOV I VESY S DVUMYA CHASHAMI, TO KAKOVO MINIMALXNOE CHISLO VZVESHIVANIJ, NEOBHODIMOE DLYA TOGO, CHTOBY RASPOLOZHITX GRUZY PO PORYADKU V SOOTVETSTVII S VESOM, ESLI V KAZHDOJ CHASHE VESOV POMESHCHAETSYA TOLXKO ODIN GRUZ? iLI ZHE, ESLI V NEKOTOROM TURNIRE UCHASTVUYUT $n$~IGROKOV, TO KAKOVO NAIMENXSHEE CHISLO IGR, DOSTATOCHNOE DLYA TOGO, CHTOBY RASPREDELITX MESTA MEZHDU SOREVNUYUSHCHIMISYA V PREDPOLOZHENII, CHTO SILY IGROKOV MOZHNO LINEJNO UPORYADOCHITX (NICHEJNYE REZULXTATY NE DOPUSKAYUTSYA). mETODY SORTIROVKI $n$~|LEMENTOV, UDOVLETVORYAYUSHCHIE UKAZANNYM OGRANICHENIYAM, MOZHNO PREDSTAVITX POSREDSTVOM STRUKTURY RASSHIRENNOGO BINARNOGO DEREVA, TAKOGO, KAK POKAZANO NA RIS.~34. kAZHDYJ \emph{VNUTRENNIJ UZEL} (IZOBRAZHENNYJ V VIDE KRUZHOCHKA) SODERZHIT %%220 DVA INDEKSA "$i:j$" I OZNACHAET SRAVNENIE KLYUCHEJ~$K_i$ I~$K_j$. lEVOE PODDEREVO |TOGO UZLA SOOTVETSTVUET POSLEDUYUSHCHIM SRAVNENIYAM, KOTORYE NEOBHODIMO VYPOLNITX, ESLI~$K_iK_j$. kAZHDYJ \emph{VNESHNIJ UZEL} DEREVA (IZOBRAZHENNYJ V VIDE PRYAMOUGOLXNIKA) SODERZHIT PERESTANOVKU $a_1$ $a_2$~\dots $a_n$ \picture{rIS.~34. dEREVO SRAVNENIJ DLYA SORTIROVKI TREH |LEMENTOV.} MNOZHESTVA~$\set{1, 2,~\ldots, n}$, OBOZNACHAYUSHCHUYU TOT FAKT, CHTO BYLO USTANOVLENO UPORYADOCHENIE $$ K_{a_1}K_2$, TO PRODOLZHATX (DVIGAYASX PO PRAVOMU PODDEREVU) SRAVNIVATX~$K_2$ S~$K_3$, A ZATEM, ESLI~$K_2K_3$, STANOVITSYA YASNO, CHTO~$K_2\ceil{n/2}$, VSTAVITX BINARNYMI VSTAVKAMI V GLAVNUYU CEPOCHKU OSTALXNYE |LEMENTY~$b$ V SLEDUYUSHCHEM PORYADKE: $$ b_3, b_2; b_5, b_4; b_{11}, b_{10},~\dots, b_6; b_{t_k}, b_{t_k-1},~\ldots, b_{t_{k-1}+1};~\ldots\,. \eqno(11) $$ nAM HOTELOSX BY OPREDELITX POSLEDOVATELXNOSTX~$(t_1, t_2, t_3, t_4,~\ldots)=(1, 3, 5, 11,~\ldots)$, UCHASTVUYUSHCHUYU V~(11), TAKIM OBRAZOM, CHTOBY KAZHDYJ IZ |LEMENTOV~$b_{t_k}$, $b_{t_k-1}$,~\dots, $b_{t_{k-1}+1}$ MOZHNO BYLO VSTAVITX V GLAVNUYU CEPOCHKU NE BOLEE, CHEM ZA $k$~SRAVNENIJ. oBOBSHCHAYA~(7), (8) I~(9), POLUCHIM DIAGRAMMU \picture{224.2} %%225 GDE GLAVNAYA CEPOCHKA DO~$a_{t_k-1}$~VKLYUCHITELXNO SODERZHIT $2t_{k-1}+(t_k-t_{k-1}-1)$~|LEMENTOV. eTO CHISLO DOLZHNO BYTX MENXSHE~$2^k$; DLYA NAS LUCHSHE VSEGO POLOZHITX EGO RAVNYM~$2^k-1$, I TOGDA $$ t_{k-1}+t_k=2^k. \eqno(12) $$ pOSKOLXKU~$t_1=1$, TO DLYA UDOBSTVA MOZHNO POLOZHITX~$t_0=1$; TOGDA, SUMMIRUYA GEOMETRICHESKUYU PROGRESSIYU, NAJDEM $$ \eqalignno{ t_k=2^k-t_{k-1}&=2^k-2^{k-1}+t_{k-2}=\ldots\cr \ldots&= 2^k-2^{k-1}+\cdots+(-1)^k2^0=(2^{k+1}+(-1)^k)/3. & (13)\cr } $$ (lYUBOPYTNO, CHTO TOCHNO TAKAYA ZHE POSLEDOVATELXNOSTX VOZNIKLA PRI IZUCHENII ALGORITMA VYCHISLENIYA NAIBOLXSHEGO OBSHCHEGO DELITELYA DVUH CELYH CHISEL; SR.~S~UPR.~4.5.2-27.) pUSTX $F(n)$---CHISLO SRAVNENIJ, NEOBHODIMYH DLYA SORTIROVKI P |LEMENTOV VSTAVKAMI I SLIYANIEM. yaSNO, CHTO $$ F(n)=\floor{n/2}+F(\floor{n/2})+G(\ceil{n/2}), \eqno(14) $$ GDE FUNKCIYA~$G$ OPISYVAET KOLICHESTVO RABOTY, VYPOLNYAEMOJ V SHAGE~(iii). eSLI~$t_{k-1}\le m \le t_k$, TO, SUMMIRUYA PO CHASTYAM, POLUCHAEM $$ \eqalignno{ G(m)&=\sum_{1\le j K_j$. yaSNO, CHTO $$ T(G)=T(G_1)+T(G_2). $$ eSLI~$T(G_1)\ge T(G_2)$, TO IMEEM $$ \eqalignno{ T(G)&\le 2T(G_1),\cr E(G_1)={n!\over 2^{k+1}T(G_1)} &={E(G)T(G)\over 2T(G_1)}\le E(G).&(23)\cr } $$ sLEDOVATELXNO, KAZHDOE SRAVNENIE PRIVODIT K GRAFU MENXSHEJ ILI RAVNOJ |FFEKTIVNOSTI; NELXZYA UVELICHITX |FFEKTIVNOSTX ZA SCHET DOPOLNITELXNYH SRAVNENIJ. zAMETIM, CHTO ESLI~$G$ SOVSEM NE SODERZHIT DUG, TO~$k=0$ I~$T(G)=n!$, T.~E.~NACHALXNAYA |FFEKTIVNOSTX RAVNA~1. eSLI ZHE GRAF~$G$ PREDSTAVLYAET OKONCHATELXNYJ REZULXTAT SORTIROVKI, TO $G$~VYGLYADIT KAK OTREZOK PRYAMOJ, I~$T(G)=1$. tAK, NAPRIMER, ESLI NAM NUZHNO POSTROITX PROCEDURU SORTIROVKI, KOTORAYA BY SORTIROVALA PYATX |LEMENTOV ZA SEMX ILI MENEE SRAVNENIJ, TO NEOBHODIMO POLUCHITX LINEJNYJ GRAF \picture{228.1} |FFEKTIVNOSTX KOTOROGO RAVNA~$5!/(2^7\times1)=120/128=15/16$. oTSYUDA SLEDUET, CHTO VSE GRAFY, VOZNIKAYUSHCHIE V PROCESSE SORTIROVKI, DOLZHNY IMETX |FFEKTIVNOSTX~$\ge{15\over16}$; ESLI BY POYAVILSYA KAKOJ-NIBUDX GRAF MENXSHEJ |FFEKTIVNOSTI, TO PO KRAJNEJ MERE ODIN IZ EGO POTOMKOV TOZHE IMEL BY MENXSHUYU |FFEKTIVNOSTX, I MY BY V KONCE KONCOV PRISHLI K LINEJNOMU GRAFU S |FFEKTIVNOSTXYU~$<{15\over16}$. v OBSHCHEM SLUCHAE |TO RASSUZHDENIE POKAZYVAET, CHTO VSE GRAFY, SOOTVETSTVUYUSHCHIE UZLAM DEREVA DLYA NEKOTOROJ PROCEDURY SORTIROVKI $n$~|LEMENTOV, DOLZHNY IMETX |FFEKTIVNOSTX~$\ge n!/2^l$, GDE $l+1$---CHISLO UROVNEJ V DEREVE. eTO ESHCHE ODIN SPOSOB DOKAZATELXSTVA NERAVENSTVA~$S(n)\ge \ceil{\log_2 n!}$, HOTYA TAKOE RASSUZHDENIE NA SAMOM DELE NE SILXNO OTLICHAETSYA OT PRIVEDENNOGO VYSHE. gRAF~(21) IMEET |FFEKTIVNOSTX~1, POSKOLXKU~$T(G)=15$ I GRAF~$G$ BYL POLUCHEN ZA TRI SRAVNENIYA. chTOBY VYYASNITX, KAKIE VERSHINY DOLZHNY UCHASTVOVATX V SLEDUYUSHCHEM SRAVNENII, MOZHNO %%229 POSTROITX \dfn{MATRICU SRAVNENIJ} $$ C(G)=\bordermatrix{ & a & b & c & d & e \cr a&0& 15 & 10 & 15 & 11 \cr b & 0 & 0 & 5 & 15 & 7 \cr c & 5 & 10 & 0 & 15 & 9 \cr d & 0 & 0 & 0 & 0 & 3 \cr e & 4 & 8 & 6 & 12 & 0 \cr }, \eqno(24) $$ GDE~$C_{ij}$ ESTX~$T(G_1)$ DLYA GRAFA~$G_1$, POLUCHENNOGO IZ~$G$ PUTEM DOBAVLENIYA DUGI~$i\to j$. eSLI MY, NAPRIMER, SRAVNIM~$K_c$ S~$K_e$, TO 15~PERESTANOVOK, SOGLASUYUSHCHIHSYA S~$G$, RASPADUTSYA NA DVE GRUPPY: $C_{ec}=6$, V KOTORYH $K_ey_2$. (v SILU SIMMETRII, PO SUSHCHESTVU, K TEM ZHE REZULXTATAM PRIVELI BY SRAVNENIYA~$x_3$ S~$y_2$, $x_5$ S~$y_3$ ILI~$x_7$ S~$y_3$.) eFFEKTIVNOSTX POLUCHENNOGO GRAFA DLYA~$x_129$. } ILI MENEE VERSHIN I OBLADALI |FFEKTIVNOSTXYU $\ge 12!/2^{29}\approx0.89221$. vSYAKIJ RAZ, KAK |TO OKAZYVAETSYA VOZMOZHNYM, MY VYBIRAEM GRAF S MENXSHEJ |FFEKTIVNOSTXYU I DOBAVLYAEM EGO K NASHEMU MNOZHESTVU, ESLI TOLXKO ON NE YAVLYAETSYA IZOMORFNYM ODNOMU IZ UZHE VKLYUCHENNYH V MNOZHESTVO GRAFOV (ILI DVOJSTVENNYM K NEMU, T.~E.~POLUCHAETSYA OBRASHCHENIEM OTNOSHENIYA PORYADKA). eSLI OBA POLUCHENNYH GRAFA IMEYUT ODINAKOVUYU |FFEKTIVNOSTX, TO PROIZVOLXNYM OBRAZOM VYBIRAETSYA ODIN IZ NIH. pERVYE 24~GRAFA, POLUCHENNYE TAKIM SPOSOBOM, IZOBRAZHENY NA RIS.~36, GDE PRIVEDENY TAKZHE IH |FFEKTIVNOSTI. pRI POMOSHCHI VYCHISLITELXNOJ MASHINY BYLO POSTROENO ROVNO 1594~GRAFA, PREZHDE CHEM |TOT PROCESS ZAVERSHILSYA. pOSKOLXKU GRAF %%233 NE BYL POLUCHEN, MOZHNO SDELATX VYVOD O TOM, CHTO~$S(12)>29$. vESXMA PRAVDOPODOBNO, CHTO I DLYA DOKAZATELXSTVA NERAVENSTVA~$S(22)>70$ MOZHNO PROIZVESTI ANALOGICHNYJ |KSPERIMENT ZA VPOLNE RAZUMNOE VREMYA, POSKOLXKU $22!/2^{70}\approx 0.952$---|TO CHREZVYCHAJNO VYSOKAYA |FFEKTIVNOSTX DLYA SORTIROVKI ZA 70~SHAGOV. (iZ 1594~NAJDENNYH GRAFOV S~12 ILI MENEE VERSHINAMI VSEGO 92~IMEYUT STOLX VYSOKUYU |FFEKTIVNOSTX.) pROMEZHUTOCHNYE REZULXTATY DAYUT VESKIE OSNOVANIYA PREDPOLOZHITX, CHTO~$S(13)=33$, I, SLEDOVATELXNO, SORTIROVKA VSTAVKAMI I SLIYANIEM NE OPTIMALXNA PRI~$n=13$. nO DO SIH POR NIKOMU NE UDALOSX OBNARUZHITX \emph{NI ODNOGO} TAKOGO ZNACHENIYA~$n$, CHTO~$S(n)0} \perm{n}{k} P_{n-k} \rem{PRI $n>0$.} $$ \ex[vm27] (o.~a.~gROSS.) nAJDITE PREDEL POSLEDOVATELXNOSTI CHISEL~$P_n$ IZ UPR.~3 PRI~$n\to\infty$. [\emph{vOZMOZHNOE UKAZANIE:} RASSMOTRITE CHASTICHNOE RAZLOZHENIE V DROBX~$\ctg z$.] \ex[16] eSLI DOPUSKAYUTSYA RAVNYE KLYUCHI, TO KAZHDOE SRAVNENIE MOZHET IMETX NE DVA, A TRI REZULXTATA: $K_iK_j$. v |TOJ OBSHCHEJ SITUACII ALGORITMY SORTIROVKI MOZHNO PREDSTAVLYATX V VIDE RASSHIRENNYH \emph{TERNARNYH} DEREVXEV, V KOTORYH KAZHDYJ VNUTRENNIJ UZEL~$i:j$ IMEET TRI PODDEREVA: LEVOE, SREDNEE I PRAVOE, SOOTVETSTVUYUSHCHIE TREM VOZMOZHNYM ISHODAM SRAVNENIYA. nARISUJTE RASSHIRENNOE TERNARNOE DEREVO, OPREDELYAYUSHCHEE ALGORITM SORTIROVKI DLYA~$n=3$, ESLI DOPUSKAYUTSYA RAVNYE KLYUCHI. v VASHEM DEREVE DOLZHNO BYTX 13~VNESHNIH UZLOV, SOOTVETSTVUYUSHCHIH 13~VOZMOZHNYM ISHODAM, PERECHISLENNYM V UPR.~3. \rex[m22] pUSTX~$S'(n)$---MINIMALXNOE CHISLO SRAVNENIJ, NEOBHODIMYH DLYA SORTIROVKI $n$~|LEMENTOV I VYYAVLENIYA VSEH RAVENSTV MEZHDU KLYUCHAMI, ESLI KAZHDOE SRAVNENIE IMEET TRI VOZMOZHNYH REZULXTATA, KAK V UPR.~5. nETRUDNO OBOBSHCHITX "TEORETIKO-INFORMACIONNOE" RASSUZHDENIE, PRIVEDENNOE V TEKSTE, %%236 I POKAZATX, CHTO~$S'(n)\ge \ceil{\log_3 P_n}$, GDE~$P_n$---FUNKCIYA, IZUCHENNAYA V UPR.~3 I~4; DOKAZHITE, CHTO NA SAMOM DELE~$S'(n)=S(n)$. \ex[20] nARISUJTE RASSHIRENNOE TERNARNOE DEREVO V SMYSLE UPR.~5 DLYA SORTIROVKI CHETYREH |LEMENTOV, ESLI IZVESTNO, CHTO VSE KLYUCHI RAVNY LIBO~0, LIBO~1. (tAK, NAPRIMER, ESLI~$K_1 \ceil{\log_2 n!}$. \ex[m20] dOKAZHITE TOZHDESTVO~(29). \ex[20] eSLI BY PROCEDURA, NACHALO KOTOROJ IZOBRAZHENO NA RIS.~36, PORODILA GRAF \picture{p.236} S |FFEKTIVNOSTXYU~$12!/2^{29}$, TO BYLO LI BY TEM SAMYM DOKAZANO, CHTO~$S(12) =29$? \ex[40] pROVEDITE |KSPERIMENTY SO SLEDUYUSHCHIM |VRISTICHESKIM PRAVILOM RESHENIYA OTNOSITELXNO TOGO, KAKUYU PARU KLYUCHEJ SRAVNIVATX SLEDUYUSHCHEJ PRI KONSTRUIROVANII DEREVA SRAVNENIJ. pUSTX NA KAZHDOJ STADII SORTIROVKI KLYUCHEJ~$\set{K_1,~\ldots, K_n}$ CHISLO KLYUCHEJ, O KOTORYH NA OSNOVANII VYPOLNENNYH DO SIH POR SRAVNENIJ IZVESTNO, CHTO ONI~$\le K_i$, OBOZNACHAETSYA CHEREZ~$u_i$, A CHISLO KLYUCHEJ, O KOTORYH IZVESTNO, CHTO ONI~$\ge K_i$, OBOZNACHAETSYA CHEREZ~$v_i$, $1\le i\le n$. %%237 pERENUMERUEM KLYUCHI TAK, CHTOBY POSLEDOVATELXNOSTX~$u_i/v_i$ STALA VOZRASTAYUSHCHEJ: $u1/v_1 \le u_2/v_2 \le \ldots \le u_n/v_n$. tEPERX SRAVNIM~$K_i:K_{i+1}$, GDE~$i$---INDEKS, MINIMIZIRUYUSHCHIJ VYRAZHENIE~$\abs{u_iv_{i+1}-u_{i+1}v_i}$. (hOTYA |TOT METOD ISPOLXZUET GORAZDO MENXSHE INFORMACII, CHEM SODERZHITSYA V POLNOJ MATRICE SRAVNENIJ, PODOBNOJ~(24), ON, KAK OKAZYVAETSYA, VO MNOGIH SLUCHAYAH DAET OPTIMALXNYE REZULXTATY.) \rex[m26] dOKAZHITE, CHTO RASSHIRENNOE BINARNOE DEREVO IMEET MINIMALXNUYU DLINU VNESHNEGO PUTI TOGDA I TOLXKO TOGDA, KOGDA SUSHCHESTVUET TAKOE CHISLO~$l$, CHTO VSE VNESHNIE UZLY NAHODYATSYA NA UROVNYAH~$l$ I~$l+1$ (ILI, BYTX MOZHET, TOLXKO NA UROVNE~$l$). \edef\exref{\the\excerno} \ex[m21] \dfn{vYSOTOJ} RASSHIRENNOGO BINARNOGO DEREVA NAZYVAETSYA MAKSIMALXNYJ NOMER UROVNYA, NA KOTOROM ESTX VNESHNIE UZLY. pUSTX~$x$---VNUTRENNIJ UZEL RASSHIRENNOGO BINARNOGO DEREVA; OBOZNACHIM CHEREZ~$t(x)$ CHISLO VNESHNIH UZLOV-POTOMKOV UZLA~$x$, A CHEREZ~$l(x)$ KORENX LEVOGO PODDEREVA UZLA~$x$. eSLI $x$---VNESHNIJ UZEL, TO POLOZHIM~$t(x)=1$. dOKAZHITE, CHTO RASSHIRENNOE BINARNOE DEREVO IMEET MINIMALXNUYU VYSOTU SREDI VSEH BINARNYH DEREVXEV S TEM ZHE CHISLOM UZLOV TOGDA I TOLXKO TOGDA, KOGDA DLYA VSEH EGO VNUTRENNIH UZLOV~$x$ VYPOLNYAETSYA NERAVENSTVO $$ \abs{t(x)-2t(l(x))}\le2^{\ceil{\log_2 t(x)}}-t(x). $$ \ex[m24] pRODOLZHENIE UPR.~\exref. dOKAZHITE, CHTO BINARNOE DEREVO IMEET MINIMALXNUYU DLINU VNESHNEGO PUTI SREDI VSEH BINARNYH DEREVXEV S TEM ZHE CHISLOM UZLOV TOGDA I TOLXKO TOGDA, KOGDA DLYA VSEH EGO VNUTRENNIH UZLOV~$x$ VYPOLNYAYUTSYA NERAVENSTVA $$ \abs{t(x)-2t(l(x))}\le 2^{\ceil{\log_2 t(x)}}-t(x) \hbox{ I } \abs{t(x)-2t(l(x))}\le t(x)-2^{\floor{\log_2 t(x)}}. $$ [tAK, NAPRIMER, ESLI~$t(x)=67$, TO DOLZHNO BYTX~$t(l(x))=32$, 33, 34 ILI~35. eSLI NUZHNO PROSTO MINIMIZIROVATX VYSOTU DEREVA, TO, SOGLASNO PREDYDUSHCHEMU UPRAZHNENIYU, DOSTATOCHNO, CHTOBY~$3\le t(l(x))\le 64$.] \ex[10] v TEKSTE DOKAZANO [SM.~FORMULU~(34)], CHTO SREDNEE CHISLO SRAVNENIJ, VYPOLNYAEMYH LYUBYM METODOM SORTIROVKI $n$~|LEMENTOV, NE MOZHET BYTX MENXSHE~$\ceil{\log_2 n!}\approx n\log_2 n$. oDNAKO PRI SORTIROVKE VSTAVKAMI V NESKOLXKO SPISKOV (ALGORITM~5.2.1m) ZATRACHIVAETSYA V SREDNEM VSEGO $O(n)$~EDINIC VREMENI. chEM |TO OB®YASNYAETSYA? \ex[27] (k. pIKAR.) pOSTROJTE TAKOE DEREVO SORTIROVKI DLYA SHESTI |LEMENTOV, CHTOBY VSE EGO VNESHNIE UZLY RASPOLAGALISX NA UROVNYAH~10 I~11. \ex[11] eSLI BY SUSHCHESTVOVALA PROCEDURA SORTIROVKI SEMI |LEMENTOV, NA KOTOROJ DOSTIGALSYA MINIMUM SREDNEGO CHISLA SRAVNENIJ, VYCHISLYAEMYJ PRI POMOSHCHI FORMULY~(34), TO SKOLXKO VNESHNIH UZLOV BYLO BY NA UROVNE~13 SOOTVETSTVUYUSHCHEGO DEREVA? \ex[m42] nAJDITE PROCEDURU SORTIROVKI DLYA SEMI |LEMENTOV, MINIMIZIRUYUSHCHUYU SREDNEE CHISLO VYPOLNYAEMYH SRAVNENIJ. \rex[20] pUSTX IZVESTNO, CHTO KONFIGURACII ($K_1K_j$, TO POMENYATX MESTAMI ZAPISI~$i$ I~$j$ I PRODVINUTXSYA PO PRAVOJ VETVI DEREVA" pO DOSTIZHENII VNESHNEGO UZLA DOLZHNY VYPOLNYATXSYA USLOVIYA~$K_1\le K_2\le \ldots\le K_n$. tAKIM OBRAZOM, DEREVO SRAVNENIJ-OBMENOV OTLICHAETSYA OT DEREVA SRAVNENIJ TEM, CHTO ONO OPISYVAET NE TOLXKO OPERACII SRAVNENIYA, NO I OPERACII PEREMESHCHENIYA DANNYH. oBOZNACHIM CHEREZ~$S_e(n)$ MINIMALXNOE CHISLO SRAVNENIJ-OBMENOV, NEOBHODIMYH V NAIHUDSHEM SLUCHAE DLYA SORTIROVKI |LEMENTOV PRI POMOSHCHI DEREVA SRAVNENIJ-OBMENOV. dOKAZHITE, CHTO~$S_e(n)\le S(n)+n-1$. \ex[m38] pRODOLZHENIE UPR.~30. dOKAZHITE, CHTO~$S_e(5)=8$. \ex[m42] pRODOLZHENIE UPR.~31. iSSLEDUJTE ZNACHENIYA FUNKCII~$S_e(n)$ PRI MALYH~$n>5$. \ex[M30] (t.~n.~hIBBARD.) \dfn{vESHCHESTVENNOZNACHNYM DEREVOM POISKA} PORYADKA~$x$ S RAZRESHENIEM~$\delta$ NAZYVAETSYA RASSHIRENNOE BINARNOE DEREVO, KAZHDYJ UZEL KOTOROGO SODERZHIT NEOTRICATELXNOE DEJSTVITELXNOE ZNACHENIE, TAKOE, CHTO (i)~ZNACHENIE V LYUBOM VNESHNEM UZLE~$\le \delta$; (ii)~ZNACHENIE V LYUBOM VNUTRENNEM UZLE~$\le $ SUMMY ZNACHENIJ DVUH EGO SYNOVEJ; (iii)~ZNACHENIE V KORNE RAVNO~$x$. \dfn{dLINA VZVESHENNOGO PUTI} TAKOGO DEREVA OPREDELYAETSYA KAK SUMMA PO VSEM VNESHNIM UZLAM NOMEROV UROVNEJ |TIH UZLOV, UMNOZHENNYH NA SODERZHASHCHIESYA V NIH ZNACHENIYA. dOKAZHITE, CHTO VESHCHESTVENNOZNACHNOE DEREVO POISKA PORYADKA~$x$ S RAZRESHENIEM~1 IMEET MINIMALXNUYU SREDI VSEH TAKIH DEREVXEV TOGO ZHE PORYADKA I S TEM ZHE RAZRESHENIEM DLINU VZVESHENNOGO PUTI TOGDA I TOLXKO TOGDA, KOGDA V~(ii) IMEET MESTO RAVENSTVO I DLYA VSEH PAR ZNACHENIJ~$x_0$ I~$x_1$, PRINADLEZHASHCHIH UZLAM-BRATXYAM, VYPOLNYAYUTSYA SLEDUYUSHCHIE USLOVIYA: (iv)~NE SUSHCHESTVUET CELOGO CHISLA~$k\ge 0$, TAKOGO, CHTO~$x_0<2^kB_j$, ESLI~$i\ge j$. sLIYANIE DOLZHNO ZAVERSHITXSYA %%240 KONFIGURACIEJ $$ B_1B_1$). \smallskip } \noindent pRAVYE OGRANICHENIYA OBOZNACHAYUTSYA SIMVOLAMI {\narrower \item{$\cdot$}~(NET OGRANICHENIYA SPRAVA), \item{$\backslash$}~(REZULXTATY VSEH SRAVNENIJ NE DOLZHNY PROTIVORECHITX USLOVIYU~$A_mB_n$). \medskip } \noindent sUSHCHESTVUET DEVYATX TIPOV DXYAVOLOV, OBOZNACHAEMYH SIMVOLAMI~$\nabla M\phi$, GDE~$\nabla$---LEVOE OGRANICHENIE, A~$\phi$---PRAVOE. nAPRIMER, DXYAVOL~"$\backslash M \backslash$" DOLZHEN GOVORITX, CHTO~$A_1B_q$, ESLI~$p>k$ I~$qk$ I~$q\ge l$. {\sl sTRATEGIYA~$B(k, l)$ DLYA~$i\le k \le m$ I~$1\le l < j$\/}. oTVETITX, CHTO~$A_iB_q$, ESLI~$p>k$ I~$q\le l$; ONI BUDUT UPRAVLYATXSYA DXYAVOLOM~$(k, l, \nabla, \backslash)$, ESLI~$p\le k$ I~$q\le l$, I DXYAVOLOM~$(m-k, n+1-l, /, \phi)$, ESLI~$p>k$ I~$q\le l$. {\sl sTRATEGIYA~$C(k, l)$ DLYA~$iB_j$, I POTREBOVATX, CHTOBY POSLEDUYUSHCHIE OPERACII OSUSHCHESTVLYALI SLIYANIYA~$\set{A_1,~\ldots, A_{k-1}}$ S~$\set{B_1,~\ldots, B_l}$ I~$\set{A_k,~\ldots, A_m}$ S~$\set{B_{l+1},~\ldots, B_n}$. (aNALOGICHNO STRATEGII~A.) {\sl sTRATEGIYA~$B'(k, l)$ DLYA~$1\le k \le i$ I~$jB_j$, I POTREBOVATX, CHTOBY POSLEDUYUSHCHIE OPERACII OSUSHCHESTVLYALI SLIYANIYA~$\set{A_1,~\ldots, A_{k-1}}$ S~$\set{B_1,~\ldots, B_l}$ I~$\set{A_k,~\ldots, A_m}$ S~$\set{B_l,~\ldots, B_n}$ PRI USLOVII~$A_{k-1}B_j$, I POTREBOVATX, CHTOBY POSLEDUYUSHCHIE OPERACII OSUSHCHESTVLYALI SLIYANIYA~$\set{A_1,~\ldots, A_k}$ S~$\set{B_1,~\ldots, B_l}$ I~$\set{A_k, ~\ldots, A_m}$ S~$\set{B_{l+1},~\ldots, B_n}$ PRI USLOVII~$B_lB_2$, TO NUZHNO ESHCHE $M(m, n-2)$~SRAVNENIJ, ESLI ZHE~$A_1i$, TO VOSPOLXZUEMSYA STRATEGIEJ~$A(i, i+1)$; PRIMENIV INDUKCIYU PO~$m$, POLUCHIM $$ .M.(m,m+d)\ge 1+.M.(i, i)+.M.(m-i, m+d-i)=2m+d-1. $$ \proofend % KONCEVOJ MARKER NE NA MESTE pERVYE DVA UTVERZHDENIYA TEOREMY~K POLUCHILI f.~hUAN I~sh.~lINX V~1969~G. eTO DOKAZATELXSTVO DAET OSNOVANIYA PREDPOLOZHITX, %%246 CHTO $M(m, m+d)=2m+d-1$ PRI VSEH DOSTATOCHNO BOLXSHIH~$m$, GDE~$d$ FIKSIROVANO. (sR.~S~UPR.~6.) \section vERHNIE OCENKI. rASSMOTRIM TEPERX \emph{VERHNIE} OCENKI FUNKCII~$M(m, n)$; HOROSHIE VERHNIE OCENKI SOOTVETSTVUYUT |FFEKTIVNYM ALGORITMAM SLIYANIYA. pRI~$m=1$ ZADACHA SLIYANIYA |KVIVALENTNA ZADACHE VSTAVKI, KOGDA IMEETSYA $n+1$~MEST MEZHDU |LEMENTAMI~$B_1$,~\dots,$B_n$, KUDA MOZHET POPASTX |LEMENT~$A_1$. v |TOM SLUCHAE NETRUDNO VIDETX, CHTO \emph{LYUBOE} RASSHIRENNOE BINARNOE DEREVO S $n+1$~VNESHNIMI UZLAMI ESTX DEREVO DLYA NEKOTOROGO METODA SLIYANIYA! (sM.~UPR.~2.) sLEDOVATELXNO, MOZHNO VYBRATX OPTIMALXNOE BINARNOE DEREVO, REALIZOVAV TEORETIKO-INFORMACIONNUYU NIZHNYUYU OCENKU $$ 1+\floor{\log_2 n}=M(1, n)=\ceil{\log_2(n+1)}. \eqno(15) $$ rAZUMEETSYA, BINARNYJ POISK~(P.~6.2.1)---PROSTEJSHIJ SPOSOB. POZVOLYAYUSHCHIJ DOSTICHX |TOGO ZNACHENIYA. sLUCHAJ~$m=2$ CHREZVYCHAJNO INTERESEN, NO ON GORAZDO SLOZHNEE. eGO POLNOSTXYU ISSLEDOVALI r.~l.~gR|HEM, f.~k.~hUAN I~sh.~lINX (SM.~UPR.~11, 12, 13); IMEEM $$ M(2, n)=\ceil{\log_2{7\over12}(n+1)}+\ceil{\log_2{14\over17}(n+1)}. \eqno(16) $$ mY VIDELI, CHTO PRI~$m=n$ OPTIMALXNA OBYCHNAYA PROCEDURA SLIYANIYA, A PRI~$m=1$ OPTIMALXNA DOVOLXNO SILXNO OTLICHAYUSHCHAYASYA OT NEE PROCEDURA BINARNOGO POISKA. nAM ZHE NUZHEN NEKOTORYJ PROMEZHUTOCHNYJ METOD, OB®EDINYAYUSHCHIJ V SEBE LUCHSHIE CHERTY ALGORITMOV OBYCHNOGO SLIYANIYA I BINARNOGO POISKA. fORMULA~(14) NAVODIT NA MYSLX O SLEDUYUSHCHEM ALGORITME, KOTORYM MY OBYAZANY f.~k.~hUANU I~sh.~lINYU [{\sl SIAM J.~Computing,\/} {\bf 1} (1972), 31--39]. \alg n.(bINARNOE SLIYANIE.) \st eSLI~$m$ ILI~$n$ RAVNO~0, TO OSTANOVITXSYA. eSLI~$m\le n$, TO USTANOVITX~$t\asg\floor{\log_2 (n/m)}$. eSLI~$m>n$, USTANOVITX~$t\asg\floor{\log_2 (m/n)}$ I PEREJTI K~\stp{4}. \st sRAVNITX~$A_m:B_{n+1-2^t}$. eSLI $A_m$~MENXSHE, TO USTANOVITX~$n\asg n-2^t$ I VOZVRATITXSYA K SHAGU~\stp{1}. \st vOSPOLXZOVAVSHISX METODOM BINARNOGO POISKA (KOTORYJ TREBUET ESHCHE ROVNO $t$~SRAVNENIJ), VSTAVITX~$A_m$ V SOOTVETSTVUYUSHCHEE MESTO SREDI~$\set{B_{n+1-2^t},~\ldots, B_n}$. eSLI~$k$---MAKSIMALXNYJ INDEKS, TAKOJ, CHTO~$B_k X_{n-j}. $$ [uSLOVIE~$\alpha< X_{i+1}$ ILI~$\beta>X_{n-j}$ TERYAET SMYSL, ESLI~$i\ge n$ ILI~$j\ge n$. pO|TOMU~$R_n(n,n)=M(2, n)$.] yaSNO, CHTO~$R_n(0, 0) = 0$. dOKAZHITE, CHTO $$ R_n(i,j)=1+\min\left(\min_{1\le k \le i} \max(R_n(k-1, j), R_{n-k}(i-k, j)), \min_{1\le k \le j} \max(R_n(i, k-1), R_{n-k}(i, j-k))\right) $$ PRI $0\le i \le n$, $0\le j \le n$, $i+j>0$. \ex[M42] (P.~l.~gR|HEM). pOKAZHITE, CHTO RESHENIE REKURRENTNOGO SOOTNOSHENIYA IZ UPR.~12 MOZHNO VYRAZITX SLEDUYUSHCHIM OBRAZOM. oPREDELIM FUNKCIYU~$G(x)$ PRI~$0{6\over7}2^{r-2}\hbox{ I } i-2^r\ge v \right)$,} \cr } $$ GDE~$u=2^pG(t/2^p)$ I~$v=2^{r-2}G(t/2^{r-2})$. %%250 (eTO, BYTX MOZHET, SAMOE SLOZHNOE REKURRENTNOE SOOTNOSHENIE IZ VSEH, KOTORYE KOGDA-LIBO BUDUT RESHENY!) \ex[46] (hUAN I~lINX.) pUSTX~$h_{3k}=2^k+2^{k-1}-1$, $h_{3k+1}=g_{2k}+g_{2k-3}+2^{k-2}$, $h_{3k+2}=2g_{2k}$ PRI~$k\ge 2$, ZA ISKLYUCHENIEM~$h_8=9$, I NACHALXNYE ZNACHENIYA PODOBRANY TAK, CHTO~$(h_0, h_1, h_2,~\ldots)=(1, 1, 2, 2, 3, 4, 5, 7, 9, 11, 14, 18, 23, 29, 38, 47, 59, 76,~\ldots)$. zDESX~$g_k$---FUNKCIYA, KOTORAYA BYLA OPREDELENA V UPR.~11. dOKAZHITE (ILI OPROVERGNITE), CHTO~$M(3, h_t)>t$, $M(3, h_t-1)\le t$ PRI VSEH~$t$. \ex[12] v SHAGE~H1 ALGORITMA BINARNOGO SLIYANIYA MOZHET POTREBOVATXSYA VYCHISLENIE ZNACHENIYA~$\floor{\log_2 (n/m)}$. kAK MOZHNO LEGKO VYCHISLITX |TO ZNACHENIE, NE PRIMENYAYA OPERACIJ DELENIYA I VZYATIYA LOGARIFMA? \picture{rIS.~38. fUNKCIYA gR|HEMA (SM.~UPR.~13).} \ex[18] pRI KAKIH~$m$ I~$n$, $1\le m \le n \le 10$, OPTIMALEN ALGORITM BINARNOGO SLIYANIYA hUANA I lINYA? \ex[m25] dOKAZHITE NERAVENSTVO~(21). [\emph{uKAZANIE:} |TO NERAVENSTVO NE OCHENX ZHESTKOE.] \ex[m40] iSSLEDUJTE \emph{SREDNEE} CHISLO SRAVNENIJ, VYPOLNYAEMYH ALGORITMOM BINARNOGO SLIYANIYA. \rex[23] dOKAZHITE, CHTO FUNKCIYA~$M$ UDOVLETVORYAET NERAVENSTVU~(22). \ex[20] pOKAZHITE, CHTO ESLI~$M(m, n+1) \le M(m+1, n)$ PRI VSEH~$m\le n$, TO~$M(m, n+1)\le 1+M(m, n)$ PRI VSEH~$m\le n$. \ex[m47] dOKAZHITE ILI OPROVERGNITE SOOTNOSHENIYA~(23), (24). \ex[m50] iSSLEDUJTE MINIMALXNOE \emph{SREDNEE} CHISLO SRAVNENIJ, NEOBHODIMYH DLYA SLIYANIYA $m$~|LEMENTOV S $n$~|LEMENTAMI. \ex[vm30] (e.~rEJNGOLXD.) pUSTX~$\set{A_1,~\ldots, A_n}$ I~$\set{B_1,~\ldots, B_n}$---MNOZHESTVA, SODERZHASHCHIE PO $n$~|LEMENTOV KAZHDOE. rASSMOTRITE ALGORITM, KOTORYJ PYTAETSYA PROVERITX NALICHIE RAVENSTVA MEZHDU MNOZHESTVAMI ISKLYUCHITELXNO PUTEM SRAVNENIJ NA RAVENSTVO |LEMENTOV |TIH MNOZHESTV. tAKIM OBRAZOM, ALGORITM ZADAET VOPROSY TIPA~"$A_i=B_j$?" PRI NEKOTORYH~$i$ I~$j$ I VYBIRAET DALXNEJSHIJ PUTX VYCHISLENIJ V ZAVISIMOSTI OT TOGO, BYL LI OTVET POLOZHITELXNYM ILI OTRICATELXNYM. oPREDELIV PODHODYASHCHEGO DXYAVOLA, DOKAZHITE, CHTO LYUBOJ TAKOJ ALGORITM V NAIHUDSHEM DLYA SEBYA SLUCHAE VYNUZHDEN VYPOLNITX NE MENEE ${1\over2}n (n+1)$~SRAVNENIJ. %%250 \subsubchap{* vYBOR S MINIMALXNYM CHISLOM SRAVNENIJ} % 5.3.3 pRI POISKE NAILUCHSHIH VOZMOZHNYH PROCEDUR DLYA VYBORA $t\hbox{-GO}$~|LEMENTA V PORYADKE UBYVANIYA IZ $n$~|LEMENTOV MY VSTRECHAEMSYA S KLASSOM ZADACH, PODOBNYH RASSMOTRENNYM V PREDYDUSHCHEM PUNKTE. iSTORIYA |TOGO VOPROSA VOSHODIT K ZANIMATELXNOMU (HOTYA I SERXEZNOMU) OCHERKU PREPODOBNOGO ch.~l.~dODZHSONA O TURNIRAH PO TENNISU, POYAVIVSHEMUSYA V St.~James's Gazette 1~AVGUSTA 1883~G. (STR.~5--6). dODZHSON, KOTORYJ, RAZUMEETSYA, BOLEE IZVESTEN KAK lXYUIS k|RROL, RASSMATRIVAL NESPRAVEDLIVYE PRAVILA, PO KOTORYM PRISUZHDALISX (I DO SIH POR PRISUZHDAYUTSYA) PRIZY V TURNIRAH PO TENNISU. rASSMOTRIM, NAPRIMER, RIS.~39, GDE POKAZAN TIPICHNYJ TURNIR "S VYBYVANIEM" MEZHDU 32~IGROKAMI, POMECHENNYMI $01$, $02$,~\dots, $32$. v FINALE IGROK~$01$ ODERZHIVAET POBEDU NAD IGROKOM~$05$, PO|TOMU YASNO, CHTO IGROK~$01$---CHEMPION I ZASLUZHIL PERVYJ PRIZ. nESPRAVEDLIVOSTX PROYAVLYAETSYA V TOM, CHTO IGROK~$05$ OBYCHNO POLUCHAET VTOROJ PRIZ, HOTYA ON MOZHET I NE BYTX VTORYM IGROKOM. vYIGRATX VTOROJ PRIZ MOZHNO, DAZHE ESLI IGRAESHX HUZHE POLOVINY IGROKOV TURNIRA. v SAMOM DELE, KAK ZAMETIL dODZHSON, VTOROJ IGROK VYIGRYVAET VTOROJ PRIZ V TOM I TOLXKO TOM SLUCHAE, ESLI PERVONACHALXNO ON I CHEMPION NAHODILISX V PROTIVOPOLOZHNYH POLOVINAH TURNIRA; DLYA $2^n$~IGROKOV |TO PROISHODIT S VEROYATNOSTXYU~$2^{n-1}/(2^n-1)$, TAK CHTO POCHTI V POLOVINE SLUCHAEV VTOROJ PRIZ POLUCHAET NE TOT IGROK! eSLI PROIGRAVSHIE V POLUFINALE (IGROKI~$25$ I~$17$ NA RIS.~39) SOREVNUYUTSYA ZA TRETIJ PRIZ, TO VESXMA MALOVEROYATNO, CHTO TRETIJ IGROK POLUCHIT TRETIJ PRIZ. pO|TOMU dODZHSON RESHIL NAJTI TAKOJ TURNIR, KOTORYJ PRAVILXNO OPREDELYAET VTOROGO I TRETXEGO IGROKOV V PREDPOLOZHENII TRANZITIVNOSTI. (iNACHE GOVORYA, ESLI IGROK~$A$ POBEZHDAET IGROKA~$B$, A~$B$ POBEZHDAET~$C$, TO MOZHNO SCHITATX, CHTO IGROK~$A$ POBEDIT~$C$). oN PRIDUMAL PROCEDURU, V KOTOROJ PROIGRAVSHIM DAYUT SYGRATX ESHCHE NESKOLXKO IGR, POKA NE STANET OPREDELENNO IZVESTNO, CHTO ONI HUZHE DRUGIH TREH IGROKOV. pRIMER SHEMY dODZHSONA PRIVODITSYA NA RIS.~40, IZOBRAZHAYUSHCHEM DOPOLNITELXNYJ TURNIR, KOTORYJ SLEDUET PROVESTI VMESTE S TURNIROM, POKAZANNYM NA RIS.~39. dELAETSYA POPYTKA ORGANIZOVATX VSTRECHI IGROKOV, U KOTORYH DO SIH POR BYLI RAVNYE REZULXTATY, I ISKLYUCHITX MATCHI MEZHDU IGROKAMI, POBEZHDENNYMI ODNIM I TEM ZHE CHELOVEKOM. nAPRIMER, IGROK~$16$ PROIGRYVAET~$11$, A IGROK~$13$ PROIGRYVAET~$12$ V PERVOM TURE; POSLE TOGO KAK IGROK~$16$ PROIGRYVAET~$13$ VO VTOROM TURE, $16$~ISKLYUCHAETSYA, TAK KAK TEPERX IZVESTNO, CHTO ON HUZHE, CHEM~$11$, $12$ I~$13$. v TRETXEM TURE MY NE POZVOLYAEM NOMERU~$19$ IGRATX S~$21$, TAK KAK ONI OBA BYLI POBEZHDENY %%252 \picture{rIS. 39. tURNIR 32~IGROKOV S VYBYVANIEM.} %%253 \picture{rIS. 40. tENNISNYJ TURNIR lXYUISA k|RROLA (V DOPOLNENIE K TURNIRU RIS.~39).} %% 254 IGROKOM~$18$ I MY NE MOGLI BY AVTOMATICHESKI ISKLYUCHITX PROIGRAVSHEGO VO VSTRECHE~$19$ S~$21$. bYLO BY PRIYATNO SOOBSHCHITX, CHTO TURNIR lXYUISA k|RROLA OKAZALSYA OPTIMALXNYM, NO, K SOZHALENIYU, |TO NE TAK. iZ ZAPISI V EGO DNEVNIKE OT 23~IYULYA 1883~G. YAVSTVUET, CHTO ON SOSTAVIL |TOT OCHERK PRIMERNO ZA SHESTX CHASOV, I CHUVSTVOVAL, CHTO, "POSKOLXKU TENNISNYJ SEZON PRIBLIZHAETSYA K KONCU, OCHERK SLEDUET NAPISATX POBYSTREE, NE SLISHKOM UVLEKAYASX KACHESTVOM". v EGO PROCEDURE DELAETSYA BOLXSHE SRAVNENIJ, CHEM NEOBHODIMO, I ONA NE SFORMULIROVANA DOSTATOCHNO CHETKO, CHTOBY KVALIFICIROVATX EE KAK ALGORITM. s DRUGOJ STORONY, V NEJ IMEYUTSYA NEKOTORYE OCHENX INTERESNYE ASPEKTY, ESLI SUDITX S TOCHKI ZRENIYA PARALLELXNYH VYCHISLENIJ. oNA TAKZHE PREDSTAVLYAETSYA OTLICHNYM RASPISANIEM TENNISNOGO TURNIRA, POSKOLXKU k|RROL VKLYUCHIL V NEE NESKOLXKO DRAMATICHESKIH |FFEKTOV; NAPRIMER, ON OPREDELIL, CHTO DVA FINALISTA DOLZHNY PROPUSTITX PYATYJ TUR I SYGRATX "DLINNYJ" MATCH V TURAH~6 I~7. oDNAKO ORGANIZATORY TURNIROV, PO-VIDIMOMU, SOCHLI |TO PREDLOZHENIE IZLISHNE LOGICHNYM, I POTOMU SISTEMA k|RROLA, SKOREE VSEGO, NIKOGDA NE ISPYTYVALASX. vMESTO |TOGO PRAKTIKUETSYA METOD "RASSEIVANIYA" BOLEE SILXNYH IGROKOV, CHTOBY ONI POPALI V RAZNYE CHASTI DEREVA. nA MATEMATICHESKOM SEMINARE V~1929--1930~G. gUGO shTEJNGAUZ POSTAVIL ZADACHU NAHOZHDENIYA MINIMALXNOGO CHISLA TENNISNYH MATCHEJ, TREBUEMYH DLYA OPREDELENIYA PERVOGO I VTOROGO IGROKOV V TURNIRE, ESLI IMEETSYA $n >2$~IGROKOV. yu.~shREJER [{\sl Mathesis Polska,\/} {\bf 7} (1932), 154--160] PRIVEL PROCEDURU, TREBUYUSHCHUYU SAMOE BOLXSHEE $n-2+\ceil{\log_2 n}$~MATCHEJ, ISPOLXZOVAV, PO SUSHCHESTVU, TOT ZHE METOD, CHTO I PERVYE DVE STADII PROCESSA, KOTORYJ MY NAZVALI SORTIROVKOJ POSREDSTVOM VYBORA IZ DEREVA (SM.~P.~5.2.3, RIS.~23), ODNAKO NE VYPOLNYAYA DOPOLNITELXNYH SRAVNENIJ, SODERZHASHCHIH~$-\infty$. shREJER TAKZHE UTVERZHDAL, CHTO $n-2+\ceil{\log_2 n}$---NAILUCHSHEE VOZMOZHNOE ZNACHENIE; NO EGO DOKAZATELXSTVO BYLO OSHIBOCHNYM, KAK I ESHCHE ODNA POPYTKA DOKAZATELXSTVA, PREDPRINYATAYA e.~sLUPECKI [{\sl Colloquium Mathematician,\/} {\bf 2} (1951), 286--290]. pROSHLO 32~GODA, PREZHDE CHEM s.~s.~kISLICYNYM BYLO OPUBLIKOVANO PRAVILXNOE, HOTYA I OCHENX SLOZHNOE DOKAZATELXSTVO [{\sl sIBIRSKIJ MATEMATICHESKIJ ZHURNAL,\/} {\bf 5} (1964), 557--564]. pUSTX~$V_t(n)$ DLYA~$1\le t \le n$ OBOZNACHAET MINIMALXNOE CHISLO SRAVNENIJ, TREBUEMYH DLYA OPREDELENIYA $t\hbox{-GO}$ V PORYADKE UBYVANIYA |LEMENTA IZ $n$~|LEMENTOV, I PUSTX $W_t(n)$~RAVNO NAIMENXSHEMU CHISLU SRAVNENIJ, NEOBHODIMYH DLYA OPREDELENIYA NAIBOLXSHEGO, VTOROGO,~\dots, $t\hbox{-GO}$ |LEMENTOV VSEH SRAZU. iZ SOOBRAZHENIJ SIMMETRII IMEEM $$ V_t(n)=V_{n+1-t}(n); \eqno(1) $$ %%255 OCHEVIDNO TAKZHE, CHTO $$ \eqalignno{ V_1(n)&=W_1(n), & (2) \cr V_t(n)&\le W_t(n), & (3) \cr W_n(n)&=W_{n-1}(n)=S(n). & (4) \cr } $$ v P.~5.2.3 MY VIDELI, CHTO $$ V_1(n)=n-1. \eqno(5) $$ eSTX UDIVITELXNO PROSTOE DOKAZATELXSTVO |TOGO FAKTA, POSKOLXKU KAZHDYJ UCHASTNIK TURNIRA, KROME CHEMPIONA, DOLZHEN PROIGRATX PO KRAJNEJ MERE ODNU IGRU! oBOBSHCHAYA |TU IDEYU I ISPOLXZUYA "DXYAVOLA", MY MOZHEM BEZ OSOBOGO TRUDA DOKAZATX TEOREMU shREJERA---kISLICYNA. \proclaim tEOREMA~S. pRI~$n\ge 2$ SPRAVEDLIVO RAVENSTVO~$V_2(n)=W_2(n)=n-2+\ceil{\log_2 n}$. \proof pREDPOLOZHIM, CHTO V TURNIRE, GDE S POMOSHCHXYU NEKOTOROJ DANNOJ PROCEDURY DOLZHEN OPREDELITXSYA VTOROJ IGROK, UCHASTVUYUT $n$~IGROKOV, I PUSTX~$a_j$---CHISLO IGROKOV, PROIGRAVSHIH~$j$ ILI BOLXSHE MATCHEJ. oBSHCHEE CHISLO SYGRANNYH MATCHEJ BUDET TOGDA RAVNO~$a_1+a_2+a_3+\ldots\,$. mY NE MOZHEM OPREDELITX VTOROGO IGROKA, NE VYYAVIV ZAODNO I CHEMPIONA (SM.~UPR.~2), PO|TOMU IZ PREDYDUSHCHIH RASSUZHDENIJ~$a_1=n-1$. dLYA ZAVERSHENIYA DOKAZATELXSTVA POKAZHEM, CHTO VSEGDA SUSHCHESTVUET POSLEDOVATELXNOSTX REZULXTATOV MATCHEJ, KOTORAYA PRIVODIT K~$a_2\ge \ceil{\log_2 n}-1$. pREDPOLOZHIM, CHTO K KONCU TURNIRA CHEMPION SYGRAL $p$~IGR I POBEDIL $p$~IGROKOV; ODNIM IZ NIH BYL VTOROJ IGROK, A OSTALXNYE DOLZHNY PROIGRATX PO KRAJNEJ MERE ESHCHE PO ODNOMU RAZU, PO|TOMU~$a_2\ge p-1$. iTAK, MY MOZHEM ZAKONCHITX DOKAZATELXSTVO, POSTROIV DXYAVOLA, PREDOPREDELYAYUSHCHEGO REZULXTATY IGR TAKIM OBRAZOM, CHTOBY CHEMPIONU PRISHLOSX SYGRATX PO KRAJNEJ MERE ESHCHE S~$\ceil{\log_2 n}$~DRUGIMI UCHASTNIKAMI TURNIRA. pUSTX DXYAVOL SCHITAET, CHTO IGROK~$A$ LUCHSHE, CHEM~$B$, ESLI~$A$ RANEE NE PROIGRYVAL, A~$B$ HOTYA BY ODNAZHDY PROIGRAL, ILI ESLI OBA NE PROIGRYVALI, NO $B$~VYIGRAL K |TOMU MOMENTU MENXSHE MATCHEJ, CHEM~$A$. pRI DRUGIH OBSTOYATELXSTVAH DXYAVOL MOZHET PRINIMATX PROIZVOLXNOE RESHENIE, NE PROTIVORECHASHCHEE NEKOTOROMU CHASTICHNOMU UPORYADOCHENIYU. rASSMOTRIM REZULXTATY ZAVERSHENNOGO TURNIRA, MATCHI KOTOROGO PREDOPREDELYALISX TAKIM DXYAVOLOM. mY SKAZHEM, CHTO "$A$ PREVOSHODIT $B$" TOGDA I TOLXKO TOGDA, KOGDA~$A=B$ ILI $A$~PREVOSHODIT IGROKA, KOTORYJ PERVYM POBEDIL~$B$. (tOLXKO PERVOE PORAZHENIE IGROKA SUSHCHESTVENNO V |TOM OTNOSHENII, POSLEDUYUSHCHIE EGO IGRY IGNORIRUYUTSYA. v SOOTVETSTVII S USTROJSTVOM DXYAVOLA LYUBOJ IGROK, \emph{PERVYM} POBEDIVSHIJ KAKOGO-TO, NI V ODNOJ IZ PREDYDUSHCHIH VSTRECH NE DOLZHEN IMETX PORAZHENIJ. oTSYUDA SLEDUET, CHTO %%256 IGROK, KOTORYJ VYIGRAL SVOI PERVYE $p$~MATCHEJ, PREVOSHODIT NA OSNOVANII |TIH $p$~IGR NE BOLEE $2^p$~IGROKOV. (eSLI~$p=0$, |TO OCHEVIDNO, ESLI ZHE $p>0$, TO $p\hbox{-J}$~MATCH BYL SYGRAN PROTIV IGROKA, KOTORYJ LIBO RANEE POTERPEL PORAZHENIE, LIBO PREVOSHODIT NE BOLEE~$2^{p-1}$~IGROKOV.) chEMPION PREVOSHODIT VSEH, PO|TOMU ON DOLZHEN BYL SYGRATX NE MENEE $\ceil{\log_2 n}$~MATCHEJ. \proofend tAKIM OBRAZOM, ZADACHA NAHOZHDENIYA VTOROGO V PORYADKE UBYVANIYA |LEMENTA POLNOSTXYU RESHENA V MINIMAKSNOM SMYSLE. v UPR.~6 POKAZANO, CHTO MOZHNO DATX PROSTUYU FORMULU DLYA MINIMALXNOGO CHISLA SRAVNENIJ, NEOBHODIMYH DLYA VYYAVLENIYA VTOROGO |LEMENTA MNOZHESTVA, ESLI IZVESTNO PROIZVOLXNOE CHASTICHNOE UPORYADOCHENIE |LEMENTOV. \qsection a ESLI $t>2$? v UPOMYANUTOJ STATXE kISLICYN POSHEL DALXSHE. oN RASSMOTREL BOLXSHIE ZNACHENIYA~$t$, DOKAZAV, CHTO $$ W_t(n)\le n-t+\sum_{n+1-tX_3$, $X_5X_7$, ZATEM SRAVNIM~$X_2:X_6$; V SILU SIMMETRII POLOZHIM~$X<2n+t-3+\sum_{0\le j\le t-2}\ceil{\log_2((n+2-t)/(t+j))}, \rem{$n\ge 2t-1$.} \eqno(12) $$ kIRKPATRIK TOCHNO USTANOVIL POVEDENIE FUNKCII~$V_t(n)$ PRI~$t=3$, DOKAZAV, CHTO~$V_3(n)=n+\ceil{\log_2 ((n-1)/2.5)}+\ceil{\log_2((n-1)/4)}$ PRI VSEH~$n\ge 50$ (SR.~S~UPR.~22). \section lINEJNYJ METOD. eSLI $n$~NECHETNO I~$t=\ceil{n/2}$, TO~$t\hbox{-J}$ V PORYADKE UBYVANIYA (I~$t\hbox{-J}$ V PORYADKE VOZRASTANIYA) |LEMENT NAZYVAETSYA MEDIANOJ. v SOOTVETSTVII S~(11) MY MOZHEM NAJTI MEDIANU~$n$ %%260 {\catcode`\!=\active\def!{\hbox to 0 pt{${}^*$\hss}} \htable{tABLICA 1}% {nAILUCHSHIE IZ IZVESTNYH VERHNIH OCENOK DLYA $V_t(n)$}% {\strut\bskip\hfill$#$\bskip&&\bskip\hfill$#$\bskip\cr n & V_1(n) & V_2(n) & V_3(n) & V_4(n) & V_5(n) & V_6(n) & V_7(n) & V_8(n) & V_9(n) & V_{10}(n)\cr \noalign{\hrule} 1 & 0 \cr 2 & 1 & 1 \cr 3 & 2 & 3 & 2 \cr 4 & 3 & 4 & 4 & 3 \cr 5 & 4 & 6 & 6 & 6 & 4 \cr 6 & 5 & 7 & 8 & 8 & 7 & 5 \cr 7 & 6 & 8 & 10 & 10!& 10 & 8 & 6\cr 8 & 7 & 9 & 11 & 12 & 12 & 11 & 9 & 7\cr 9 & 8 & 11 & 12 & 14 & 15!& 14 & 12 & 11 & 8\cr 10 & 9 & 12 & 14!& 15 & 17 & 17 & 15 & 14! & 12 & 9 \cr \noalign{\hrule} \multispan{11}\hbox{$*$)~v |TIH SLUCHAYAH UPR.~10--12 DAYUT POSTROENIYA, POZVOLYAYUSHCHIE ULUCHSHITX~(11).}\cr }}% |LEMENTOV ZA $\approx {1\over2}n\log_2 n$~SRAVNENIJ, NO |TO LISHX PRIBLIZITELXNO VDVOE BYSTREE SORTIROVKI, HOTYA NAM NUZHNA ZNACHITELXNO MENXSHAYA INFORMACIYA. v TECHENIE NESKOLXKIH LET OB®EDINENNYE USILIYA RYADA ISSLEDOVATELEJ BYLI NAPRAVLENY NA ULUCHSHENIE FORMULY~(11) DLYA BOLXSHIH ZNACHENIJ~$t$ I~$n$; NAKONEC, V 1971~G. mANU|LX bLUM OTKRYL METOD, TREBUYUSHCHIJ TOLXKO $O(n \log \log n)$~SHAGOV. pODHOD bLUMA K |TOJ ZADACHE DAL TOLCHOK K RAZVITIYU NOVOGO KLASSA METODOV, KOTORYJ PRIVEL K SLEDUYUSHCHEMU POSTROENIYU, PRINADLEZHASHCHEMU r.~rAJVESTU I~r.~tARXYANU. \proclaim tEOREMA~L. eSLI~$n>32$, TO~$V_t(n)\le 15n-163$ PRI~$1\le t\le n$. \proof kOGDA $n$~MALO, TEOREMA TRIVIALXNA, TAK KAK~$V_t(n)\le S(n)\le 10n\le 15n-163$ DLYA~$32r+1$, TO NAM NUZHNO NAJTI $(t-1-r)\hbox{-J}$~|LEMENT V PORYADKE UBYVANIYA IZ $n-1-r$~MENXSHIH |LEMENTOV. sUTX DELA V TOM, CHTO~$r$ I~$n-1-r$ OBA MENXSHE ILI RAVNY~$10q+3$ (RAZMER OBLASTEJ~a I~D PLYUS~v ILI~s). iNDUKCIEJ PO~$q$ VYVODIM, CHTO |TOT SHAG TREBUET NE BOLEE $15(10q+3)-163$~SRAVNENIJ. \medskip oBSHCHEE CHISLO SRAVNENIJ OKAZYVAETSYA NE BOLXSHE $$ 13(2q+1)+30q-148+4q+15(10q+3)-163=15(14q-6)-163. $$ tAK KAK MY NACHALI S NE MENEE $14q-6$~|LEMENTOV, DOKAZATELXSTVO ZAVERSHENO. \proofend mETOD, ISPOLXZOVANNYJ V |TOM DOKAZATELXSTVE, NE VPOLNE SOVERSHENNYJ, POSKOLXKU NA SHAGE~4 TERYAETSYA ZNACHITELXNAYA INFORMACIYA. tSHCHATELXNYE ULUCHSHENIYA, PRODELANNYE v.~pRATTOM, %%262 r.~rAJVESTOM I~r.~tARXYANOM, POKAZYVAYUT, CHTO KONSTANTU~15 MOZHNO UMENXSHITX DO~$5.43$. \section sREDNEE CHISLO. vMESTO MINIMIZACII \emph{MAKSIMALXNOGO} CHISLA SRAVNENIJ MOZHNO ISKATX ALGORITM, KOTORYJ MINIMIZIRUET \emph{SREDNEE} CHISLO SRAVNENIJ, PREDPOLAGAYA, CHTO PORYADOK SLUCHAEN. kAK OBYCHNO, |TA ZADACHA ZNACHITELXNO TRUDNEE, I ONA VSE ESHCHE NE RESHENA DAZHE V SLUCHAE~$t=2$. kLOD pIKAR UPOMYANUL |TU ZADACHU V SVOEJ \picture{ rIS.~42. pROCEDURA, KOTORAYA VYBIRAET VTOROJ |LEMENT IZ~$\set{X_1, X_2, X_3, X_4, X_5, X_6}$, ISPOLXZUYA V SREDNEM $6{1\over2}$~SRAVNENIJ. kAZHDAYA "SIMMETRICHNAYA" VETVX IDENTICHNA SVOEMU BRATU, ODNAKO IMENA PERESTAVLENY SOOTVETSTVUYUSHCHIM OBRAZOM. vO VNESHNIH UZLAH ZAPISANO~$j\ k$, ESLI IZVESTNO, CHTO $X_j$---VTOROJ, a $X_k$---NAIBOLXSHIJ |LEMENT; CHISLO PERESTANOVOK, PRIVODYASHCHIH K |TOMU UZLU, ZAPISANO NEPOSREDSTVENNO POD NIM. } KNIGE Th\'eorie des Questionnaires (1965), SHIROKOE ISSLEDOVANIE BYLO PREDPRINYATO mILTONOM sOBELEM [Univ.~of Minnesota, Dept.~of Statistics, report~113 (November, 1968)]. sOBELX POSTROIL PROCEDURU, IZOBRAZHENNUYU NA RIS.~42, KOTORAYA NAHODIT VTOROJ V PORYADKE UBYVANIYA |LEMENT IZ SHESTI |LEMENTOV, V SREDNEM ISPOLXZUYA TOLXKO $6{1\over2}$~SRAVNENIJ. v HUDSHEM %%263 SLUCHAE TREBUETSYA 8~SRAVNENIJ, I |TO HUZHE, CHEM~$V_2(6)=7$; NO VSE IZVESTNYE PROCEDURY DLYA |TOJ ZADACHI, TREBUYUSHCHIE NE BOLEE 7~SRAVNENIJ, ISPOLXZUYUT V SREDNEM PO KRAJNEJ MERE $6{2\over3}$~SRAVNENIJ. tAKIM OBRAZOM, VEROYATNO, NIKAKAYA PROCEDURA NAHOZHDENIYA VTOROGO IZ SHESTI |LEMENTOV NE BUDET OPTIMALXNOJ ODNOVREMENNO I KAK MINIMAKSNAYA, I KAK MINIMIZIRUYUSHCHAYA SREDNEE CHISLO SRAVNENIJ. pUSTX $\bar V(n)$~OBOZNACHAET MINIMALXNOE SREDNEE CHISLO SRAVNENIJ, NEOBHODIMYH DLYA OPREDELENIYA $t\hbox{-GO}$~|LEMENTA V PORYADKE UBYVANIYA IZ $n$~|LEMENTOV. v SLEDUYUSHCHEJ TABLICE POKAZANY NAILUCHSHIE IZVESTNYE VERHNIE OCENKI DLYA~$\bar V_2(n)$, VYCHISLENNYE sOBELEM: {\catcode`\!=\active\def!#1,#2/#3.{#1{#2\over#2}} $$ \vbox{ \halign{ \hfill$#$\bskip&&\bskip$#$\hfill\bskip\cr n=2& 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \cr \bar V_2(n)\le 1& !2,2/3. & 4 & !5,4/15. & !6,1/2. & !7,17/21. & 9 & !10, 1/15. & !11,4/135.\cr }} \eqno(13) $$ } sOBELX PREDPOLOZHIL, CHTO $$ \bar V_2(n)\ge n-2+\floor{2\log_2 n}/2. \eqno(14) $$ r.~u.~fLOJD V 1970~G.\ OBNARUZHIL, CHTO MEDIANA $n$~|LEMENTOV V SREDNEM MOZHET BYTX NAJDENA VSEGO ZA ${3\over2}n+O\left(n^{2\over3}\log n\right)$~SRAVNENIJ. (sM.~UPR.~13.) fAKTICHESKI ON DOKAZAL, CHTO $$ \bar V_t(n)\le n+t+f(n), \rem{GDE $\lim_{n\to\infty} f(n)/n=0$.} \eqno(15) $$ pREDPOLAGAETSYA, CHTO |TOT REZULXTAT YAVLYAETSYA NAILUCHSHEJ ASIMPTOTICHESKOJ FORMULOJ, ODNAKO NIKAKOJ UDOVLETVORITELXNOJ NIZHNEJ OCENKI VSE ESHCHE NE NAJDENO. \excercises \ex[15] pOCHEMU V TURNIRE lXYUISA k|RROLA (RIS.~39 I~40) IGROK~$13$ VYBYVAET, NESMOTRYA NA TO CHTO ON VYIGRAL SVOJ MATCH V TRETXEM TURE? \rex[m25] dOKAZHITE, CHTO POSLE TOGO, KAK MY NASHLI S POMOSHCHXYU POSLEDOVATELXNOSTI SRAVNENIJ $t\hbox{-J}$ |LEMENT V PORYADKE UBYVANIYA IZ $n$~|LEMENTOV, MY TAKZHE ZNAEM, KAKIE $t-1$~|LEMENTOV BOLXSHE NEGO I KAKIE $n-t$~|LEMENTOV MENXSHE. \ex[M21] dOKAZHITE, CHTO~$V_t(n)\ge V_t(n-1)+1$ PRI~$1\le t \le n$. \ex[m20] dOKAZHITE, CHTO~$W_t(n)\ge\ceil{\log_2 n^{t\atop -}}$, GDE~$n^{t\atop -}=n(n-1) \ldots (n+1-t)$. \ex[10] dOKAZHITE, CHTO~$W_3(n)\le V_3(n)+1$. \rex[m26] (r.~u.~fLOJD.) dANO $n$~RAZLICHNYH |LEMENTOV~$\set{X_1,~\ldots, X_n}$ I OTNOSHENIYA~$X_iK_j$, ODNAKO~$i$ I~$j$ MENYAYUTSYA ROLYAMI. nA RIS.~43(A) IZOBRAZHENO DEREVO SRAVNENIJ, V KOTOROM |TO USLOVIE VYPOLNENO. (zAMETIM, CHTO NA KAZHDOM UROVNE PROIZVODITSYA ODINAKOVOE CHISLO SRAVNENIJ, PO|TOMU POSLE $m$~SRAVNENIJ IMEETSYA $2^m$~REZULXTATOV; TAK KAK~$n!$ NE YAVLYAETSYA STEPENXYU~2, TO NEKOTORYE SRAVNENIYA BUDUT IZLISHNIMI V TOM SMYSLE, CHTO ODNO IZ IH PODDEREVXEV NIKOGDA NE VSTRECHAETSYA NA PRAKTIKE. iNYMI SLOVAMI, NA NEKOTORYH VETVYAH DEREVA PRIHODITSYA VYPOLNYATX BOLXSHE SRAVNENIJ, CHEM NEOBHODIMO, CHTOBY SORTIROVKA BYLA PRAVILXNOJ NA VSEH SOOTVETSTVUYUSHCHIH VETVYAH.) tAK KAK KAZHDYJ PUTX TAKOGO DEREVA SVERHU DONIZU OPREDELYAET VSE DEREVO, TO PODOBNUYU SHEMU SORTIROVKI PROSHCHE IZOBRAZHATX V VIDE \dfn{SETI,} KAK NA RIS.~43(b). pRYAMOUGOLXNIKI V TAKOJ SETI PREDSTAVLYAYUT "KOMPARATORNYE MODULI", IMEYUSHCHIE DVA VHODA (IZOBRAZHENNYE LINIYAMI, VHODYASHCHIMI V MODULX SVERHU) %%266 \picture{rIS. 43. dEREVO SRAVNENIJ, V KOTOROM NE UCHITYVAETSYA PREDYSTORIYA, (a) I SOOTVETSTVUYUSHCHAYA SETX~(b).} %%267 I DVA VYHODA (IZOBRAZHENNYE LINIYAMI, VYHODYASHCHIMI VNIZ); LEVYJ VYHOD ESTX MENXSHIJ IZ DVUH VHODOV, A PRAVYJ VYHOD---BOLXSHIJ IZ NIH. eLEMENT~$K'_1$ V NIZHNEJ CHASTI SETI ESTX NAIMENXSHIJ IZ~$\set{K_1, K_2, K_3, K_4}$, $K'_2$---VTOROJ V PORYADKE VOZRASTANIYA I~T.~D. nETRUDNO DOKAZATX, CHTO LYUBAYA SETX SORTIROVKI SOOTVETSTVUET DEREVU SRAVNENIJ, OBLADAYUSHCHEMU SVOJSTVOM NEZAVISIMOSTI OT PREDYSTORII (V UKAZANNOM VYSHE SMYSLE), I CHTO LYUBOE TAKOE DEREVO SOOTVETSTVUET SETI KOMPARATORNYH MODULEJ. mEZHDU PROCHIM ZAMETIM, CHTO S INZHENERNOJ TOCHKI ZRENIYA KOMPARATORNYJ MODULX DOVOLXNO LEGKO IZGOTOVITX. pREDPOLOZHIM, NAPRIMER, CHTO PO LINIYAM SVYAZI V MODULX POSTUPAYUT DVOICHNYE CHISLA PO ODNOMU BITU V EDINICU VREMENI, NACHINAYA SO STARSHEGO. kAZHDYJ KOMPARATORNYJ MODULX IMEET TRI SOSTOYANIYA I FUNKCIONIRUET SLEDUYUSHCHIM OBRAZOM: $$ \matrix{ \multispan{3}\hfill\hbox{mOMENT $t$}\hfill &\multispan{3}\hfill \hbox{mOMENT $(t+1)$}\hfill\cr \hbox{sOSTOYANIE} & \hbox{vHODY}\hfill\span & \hbox{sOSTOYANIE} &\hbox{vYHODY}\hfill\span\cr 0 & 0 & 0 & 0 & 0 & 0\cr 0 & 0 & 1 & 1 & 0 & 1\cr 0 & 1 & 0 & 2 & 0 & 1\cr 0 & 1 & 1 & 0 & 1 & 1\cr 1 & x & y & 1 & x & y\cr 2 & x & y & 2 & y & x\cr } $$ pERVONACHALXNO VSE MODULI NAHODYATSYA V SOSTOYANII~0 I VYDAYUT~$00$. mODULX PEREHODIT V SOSTOYANIE~1 ILI~2, KAK TOLXKO EGO VHODY STANUT RAZLICHNYMI. chISLA, KOTORYE V MOMENT VREMENI~$t$ NACHALI POSTUPATX SVERHU V SETX, SOOTVETSTVUYUSHCHUYU RIS.~43(b), NACHNUT V MOMENT~$t+3$ VYVODITXSYA SNIZU V OTSORTIROVANNOM \picture{rIS.~44. eSHCHE ODIN SPOSOB PREDSTAVLENIYA SORTIROVKI POSLEDOVATELXNOSTI $\langle 4, 1, 3, 2\rangle$ POSREDSTVOM SETI, IZOBRAZHENNOJ NA RIS.~43.} PORYADKE, ESLI VKLYUCHITX SOOTVETSTVUYUSHCHIJ ZADERZHIVAYUSHCHIJ |LEMENT V LINIYAH~$K'_1$ I~$K'_4$. dLYA RAZRABOTKI TEORII SETEJ SORTIROVKI UDOBNO IZOBRAZHATX IH NESKOLXKO INYM SPOSOBOM (RIS.~44). nA |TOM RISUNKE CHISLA POSTUPAYUT SLEVA, A KOMPARATORNYE MODULI IZOBRAZHENY VERTIKALXNYMI SOEDINENIYAMI MEZHDU DVUMYA PRYAMYMI; KAZHDYJ %%268 KOMPARATOR VYZYVAET, ESLI NEOBHODIMO, PERESTANOVKU SVOIH VHODOV TAKIM OBRAZOM, CHTO POSLE PROHOZHDENIYA KOMPARATORA BOLXSHEE CHISLO OKAZYVAETSYA NA NIZHNEJ LINII. v PRAVOJ CHASTI DIAGRAMMY VSE CHISLA UPORYADOCHENY SVERHU VNIZ. rANEE, IZUCHAYA OPTIMALXNUYU SORTIROVKU, MY UDELYALI OSNOVNOE VNIMANIE MINIMIZACII CHISLA SRAVNENIJ, POCHTI (ILI SOVSEM) \picture{rIS.~45. pOLUCHENIE $(n+1)$-|LEMENTNOGO SORTIROVSHCHIKA IZ $n$-|LEMENTNOGO: (a)---VSTAVKA; (b)---VYBOR.} NE UCHITYVAYA PEREMESHCHENIE DANNYH ILI SLOZHNOSTX STRUKTURY RESHENIJ METODA SORTIROVKI. v |TOM OTNOSHENII SETI SORTIROVKI IMEYUT NEKOTOROE PREIMUSHCHESTVO, TAK KAK DANNYE MOGUT HRANITXSYA V $n$~YACHEJKAH, A STRUKTURA RESHENIJ "PRYAMOLINEJNA"; NET NEOBHODIMOSTI ZAPOMINATX REZULXTATY PREDYDUSHCHIH SRAVNENIJ---PLAN NEIZMENEN I FIKSIROVAN ZARANEE. eSHCHE ODNIM VAZHNYM \picture{rIS.~46. sETEVYE ANALOGI |LEMENTARNYH SHEM VNUTRENNEJ SORTIROVKI, POLUCHENNYE MNOGOKRATNYM PRIMENENIEM OPERACII, PREDSTAVLENNOJ NA RIS.~45: (a)---PROSTAYA VSTAVKA; (b)---METOD PUZYRXKA.} PREIMUSHCHESTVOM SETEJ SORTIROVKI YAVLYAETSYA TO, CHTO CHASTX OPERACIJ MOZHNO SOVMESTITX, ESLI VYPOLNYATX IH ODNOVREMENNO (NA PODHODYASHCHEJ MASHINE). nAPRIMER, PYATX SHAGOV NA RIS.~43 I~44 SOKRASHCHAYUTSYA DO TREH, ESLI DOPUSTITX ODNOVREMENNYE NEPEREKRYVAYUSHCHIESYA SRAVNENIYA, TAK KAK MOZHNO OB®EDINITX PERVYE DVA I SLEDUYUSHCHIE DVA SHAGA; POZDNEE V DANNOM PUNKTE MY ISPOLXZUEM %%269 |TO SVOJSTVO SETEJ SORTIROVKI. tAKIM OBRAZOM, SETI SORTIROVKI MOGUT BYTX OCHENX POLEZNY, HOTYA VOZMOZHNOSTX POSTROENIYA |FFEKTIVNOJ SETI SORTIROVKI $n$~|LEMENTOV PRI BOLXSHIH~$n$ VOVSE NE OCHEVIDNA; VOZMOZHNO, MY OBNARUZHIM, CHTO DLYA PODDERZHANIYA ODNORODNOJ STRUKTURY RESHENIJ TREBUETSYA MNOGO DOPOLNITELXNYH SRAVNENIJ. iMEETSYA DVA PROSTYH SPOSOBA POSTROENIYA SETI SORTIROVKI. DLYA $n+1$~|LEMENTOV, ESLI DANA SETX DLYA $n$~|LEMENTOV: S ISPOLXZOVANIEM LIBO PRINCIPA \emph{VSTAVKI,} LIBO PRINCIPA \emph{VYBORA.} nA \picture{rIS.~47. pRI PARALLELXNOM VYPOLNENII OPERACIJ PROSTAYA VSTAVKA SOVPADAET S METODOM PUZYRXKA!} RIS.~45(a) POKAZANO, KAK $(n+1)\hbox{-J}$~|LEMENT MOZHET BYTX VSTAVLEN NA NUZHNOE MESTO POSLE TOGO, KAK PERVYE $n$~|LEMENTOV OTSORTIROVANY, A NA RIS.~45(b) POKAZANO, KAK MOZHNO VYBRATX NAIBOLXSHIJ |LEMENT, PREZHDE CHEM PEREJTI K SORTIROVKE OSTALXNYH. mNOGOKRATNOE PRIMENENIE RIS.~45(a) DAET SETEVOJ ANALOG PROSTYH VSTAVOK (ALGORITM~5.2.1S), A MNOGOKRATNOE PRIMENENIE RIS.~45(b) PRIVODIT K SETEVOMU ANALOGU METODA PUZYRXKA (ALGORITM~5.2.2B). nA RIS.~46 IZOBRAZHENY SOOTVETSTVUYUSHCHIE SETI DLYA SHESTI |LEMENTOV. iNTERESNO ZAMETITX, CHTO ESLI SZHATX KAZHDUYU SETX, CHTOBY OBESPECHITX ODNOVREMENNYE OPERACII, TO OBA METODA SVEDUTSYA K ODNOJ I TOJ ZHE "TREUGOLXNOJ" PROCEDURE S $(2n-3)$~STADIYAMI (RIS.~47). lEGKO DOKAZATX, CHTO SETI, PREDSTAVLENNYE NA RIS.~43 I~44, BUDUT SORTIROVATX LYUBOE MNOZHESTVO IZ CHETYREH CHISEL, POSKOLXKU PERVYE CHETYRE KOMPARATORA NAPRAVLYAYUT NAIMENXSHIJ I NAIBOLXSHIJ |LEMENTY NA POLOZHENNYE IM MESTA, A POSLEDNIJ KOMPARATOR RASPOLAGAET V TREBUEMOM PORYADKE OSTALXNYE DVA |LEMENTA. oDNAKO NE VSEGDA TAK LEGKO SKAZATX, BUDET LI DANNAYA SETX SORTIROVATX VSE VOZMOZHNYE VHODNYE POSLEDOVATELXNOSTI; NAPRIMER, SETI \picture{p.269} YAVLYAYUTSYA PRAVILXNYMI CHETYREH|LEMENTIYMI SETYAMI SORTIROVKI, NO DOKAZATELXSTVO IH PRAVILXNOSTI NETRIVIALXNO. bYLO BY %%270 DOSTATOCHNO PROVERITX KAZHDUYU $n$-|LEMENTNUYU SETX NA VSEH $n!$~PERESTANOVKAH $n$~RAZLICHNYH CHISEL, NO FAKTICHESKI MY MOZHEM OBOJTISX ZNACHITELXNO MENXSHIM KOLICHESTVOM PROVEROK. \proclaim tEOREMA~Z. (pRINCIP NULEJ I EDINIC.) eSLI SETX S $n$~VHODAMI SORTIRUET V NEUBYVAYUSHCHEM PORYADKE VSE $2^n$~POSLEDOVATELXNOSTEJ IZ~0 I~1, TO ONA BUDET SORTIROVATX V NEUBYVAYUSHCHEM PORYADKE LYUBUYU POSLEDOVATELXNOSTX $n$~CHISEL. \proof (eTO CHASTNYJ SLUCHAJ TEOREMY bURISIUSA, UPR.~5.3.1-12.) eSLI~$f(x)$---LYUBAYA MONOTONNAYA FUNKCIYA, DLYA KOTOROJ~$f(x)\le f(y)$ PRI~$x\le y$, I ESLI DANNAYA SETX PREOBRAZUET~$\< x_1,~\ldots, x_n>$ V~$\$, TO, KAK NETRUDNO VIDETX, |TA SETX PREOBRAZUET~$\$ V~$\$. eSLI~$y_i>y_{i+1}$ PRI NEKOTOROM~$i$, TO RASSMOTRIM MONOTONNUYU FUNKCIYU~$f$, KOTORAYA DLYA VSEH CHISEL $$, KOTORAYA NE SORTIRUETSYA DANNOJ SETXYU. sLEDOVATELXNO, ESLI VSE POSLEDOVATELXNOSTI~0 I~1 PODDAYUTSYA SORTIROVKE, TO BUDEM IMETX~$y_i\le y_{i+1}$ DLYA VSEH~$1\le i < n$. \proofend pRINCIP NULEJ I EDINIC DOVOLXNO POLEZEN DLYA POSTROENIYA SETEJ SORTIROVKI. v KACHESTVE NETRIVIALXNOGO PRIMERA POLUCHIM OBOBSHCHENNYJ VARIANT "OBMENNOJ SORTIROVKI SO SLIYANIEM" b|TCHERA (ALGORITM~5.2.2m). iDEYA SOSTOIT V TOM, CHTOBY SORTIROVATX $m+n$~|LEMENTOV, "SORTIRUYA PERVYE~$m$ I POSLEDNIE~$n$ |LEMENTOV NEZAVISIMO I ZATEM PRIMENYAYA K REZULXTATU \dfn{$(m, n)$-SETX SLIYANIYA.} pOSTROITX $(m, n)$-SETX SLIYANIYA MOZHNO PO INDUKCII: {\medskip\narrower \item{a)}~eSLI~$m=0$ ILI~$n=0$, TO SETX PUSTAYA. eSLI~$m=n=1$, TO SETX SOSTOIT IZ EDINSTVENNOGO KOMPARATORNOGO MODULYA. \item{b)}~eSLI~$mn>1$, TO OBOZNACHIM SLIVAEMYE POSLEDOVATELXNOSTI $\$ I~$\$. sOLXEM "NECHETNYE POSLEDOVATELXNOSTI"~$\$ I~$\$ I POLUCHIM OTSORTIROVANNYJ REZULXTAT~$\$; SOLXEM "CHETNYE POSLEDOVATELXNOSTI"~$\$ I~$\$ I POLUCHIM OTSORTIROVANNYJ REZULXTAT~$\$. i NAKONEC, PRIMENIM OPERACII SRAVNENIYA-OBMENA $$ w_1:v_2, w_2:v_3, w_3:v_4, w_{\floor{m/2}+\floor{n/2}}:v^* \eqno(1) $$ K POSLEDOVATELXNOSTI $$ \; \eqno(2) $$ REZULXTAT BUDET OTSORTIROVAN. (!) (zDESX~$v^*=v_{\floor{m/2}+\floor{n/2}+1}$ NE SUSHCHESTVUET, ESLI~$m$ I~$n$ OBA CHETNYE, I~$v^{**}=v_{\floor{m/2}+\floor{n/2}+2}$ %% 271 SUSHCHESTVUET, LISHX ESLI~$m$ I~$n$ OBA NECHETNYE; OBSHCHEE CHISLO KOMPARATORNYH MODULEJ, UKAZANNYH V~(1), RAVNO~$\floor{(m+n)-1)/2}$.) \medskip} \noindent nAZOVEM $(m, n)$-SETX SLIYANIYA b|TCHERA \dfn{CHETNO-NECHETNYM SLIYANIEM.} pOSTROENNOE V SOOTVETSTVII S |TIMI PRINCIPAMI $(4, 7)$-SLIYANIE POKAZANO NA RIS.~48. \picture{rIS. 48. chETNO-NECHETNOE SLIYANIE DLYA~$m=4$ I~$n=7$.} chTOBY DOKAZATX, CHTO |TA OCHENX STRANNAYA PROCEDURA DEJSTVITELXNO RABOTAET PRI~$mn>1$, VOSPOLXZUEMSYA PRINCIPOM NULEJ I EDINIC I PROVERIM EE NA VSEH POSLEDOVATELXNOSTYAH~0 I~1. pOSLE NACHALXNYH $m$-SORTIROVKI I $n$-SORTIROVKI POSLEDOVATELXNOSTX~$\$ BUDET SOSTOYATX IZ $k$~NULEJ, ZA KOTORYMI SLEDUYUT $m-k$~EDINIC, A POSLEDOVATELXNOSTX~$\$---IZ $l$~NULEJ S POSLEDUYUSHCHIMI $n-l$~EDINICAMI PRI NEKOTORYH~$k$ I~$l$. sLEDOVATELXNO, POSLEDOVATELXNOSTX~$\$ BUDET SOSTOYATX IZ~$\ceil{k/2}+\ceil{l/2}$~NULEJ S POSLEDUYUSHCHIMI EDINICAMI, A $\$---IZ $\floor{k/2}+\floor{l/2}$~NULEJ S POSLEDUYUSHCHIMI EDINICAMI. rESHAYUSHCHIM MOMENTOM DOKAZATELXSTVA YAVLYAETSYA TO, CHTO $$ (\ceil{k/2}+\ceil{l/2})-(\floor{k/2}+\floor{l/2})=0, 1 \hbox{ ILI } 2. \eqno(3) $$ eSLI |TA RAZNOSTX RAVNA~0 ILI~1, TO POSLEDOVATELXNOSTX~(2) UZHE UPORYADOCHENA, A ESLI ONA RAVNA~2, TO ODNA IZ OPERACIJ SRAVNENIYA-OBMENA V~(1) STAVIT VSE NA SVOI MESTA. dOKAZATELXSTVO ZAVERSHENO. (zAMETIM, CHTO PRINCIP NULEJ I EDINIC SVODIT $\perm{m+n}{m}$~SLUCHAEV V ZADACHE SLIYANIYA VSEGO LISHX K~$(m+1)(n+1)$, KAZHDYJ IZ KOTORYH IZOBRAZHAETSYA DVUMYA PARAMETRAMI~$k$ I~$l$.) pUSTX~$C(m, n)$---CHISLO KOMPARATORNYH MODULEJ, ISPOLXZUEMYH PRI CHETNO-NECHETNOM SLIYANII $m$ I $n$~|LEMENTOV, NE SCHITAYA %%272 NACHALXNYH $m$- I~$n$-SORTIROVOK; IMEEM $$ C(m,n)=\cases{ mn, & ESLI $mn\le 1$;\cr C(\ceil{m/2}, \ceil{n/2})+C(\floor{m/2}, \floor{n/2})+ \floor{(m+n-1)/2}, & ESLI $mn>1$.\cr } \eqno(4) $$ v OBSHCHEM SLUCHAE |TO NE SLISHKOM PROSTAYA FUNKCIYA OT~$m$ I~$n$, ODNAKO, ZAMETIV, CHTO~$C(1, n)=n$ I CHTO $$ C(m+1, n+1)-C(m,n)= =1+C(\floor{m/2}+1, \floor{n/2}+1)-C(\floor{m/2}, \floor{n/2}), \rem{ESLI $mn\ge 1$}, $$ MY MOZHEM VYVESTI SOOTNOSHENIE $$ C(m+1, n+1)-C(m,n)=t+2+\floor{n/2^{t+1}}, \rem{ESLI~$n\ge m \ge 1$ I~$t=\floor{\log_2 m}$.} \eqno(5) $$ sLEDOVATELXNO, $$ C(m, m+r)=B(m)+m+R_m(r) \rem{PRI $m\ge0$, $r\ge0$,} \eqno (6) $$ GDE $B(m)$~ESTX FUNKCIYA "BINARNOJ VSTAVKI"~$\sum_{1\le k\le m}\ceil{\log_2 k}$ IZ SOOTNOSHENIYA~(5.3.1-3), A $R_m(r)$~OBOZNACHAET SUMMU PERVYH OT CHLENOV RYADA $$ \floor{{r+0\over1}}+\floor{{r+1\over2}}+\floor{{r+2\over4}}+ \floor{{r+3\over4}}+\floor{{r+4\over8}}+\cdots+ \floor{{r+j\over2^{\floor{\log_2 j}+1}}}+\ldots\,. \eqno(7) $$ eSLI ZHE~$r=0$, POLUCHAEM VAZHNYJ CHASTNYJ SLUCHAJ $$ C(m,m)=B(m)+m. \eqno(8) $$ kROME TOGO, ESLI~$t=\ceil{\log_2 m}$, TO $$ \eqalign{ R_m(r+2^t) &= R_m(r)+1\cdot 2^{t-1}+2\cdot 2^{t-2}+\cdots+2^{t-1}\cdot2^0+m=\cr &= R_m(r)+m+t\cdot 2^{t-1}. } $$ sLEDOVATELXNO, $C(m, n+2^t)-C(m, n)$~IMEET PROSTOJ VID I $$ C(m, n)=\left({t\over2}+{m\over 2^t}\right) n+O(1)\rem{ PRI FIKSIROVANNOM~$m$, $n\to\infty$, $t=\ceil{\log_2 m}$;} \eqno (9) $$ CHLEN~$O(1)$ STANOVITSYA V KONCE KONCOV PERIODICHESKOJ FUNKCIEJ OT~$n$ S DLINOJ PERIODA~$2^t$. aSIMPTOTICHESKI PRI~$n\to\infty$ VELICHINA~$C(n, n)$ RAVNA~$n \log_2 n$ IZ~(8) I UPR.~5.3.1-15. \section sETI S MINIMALXNYM CHISLOM SRAVNENIJ. pUSTX~$\hat S(n)$---MINIMALXNOE CHISLO SRAVNENIJ, TREBUEMYH V SETI SORTIROVKI DLYA $n$~|LEMENTOV; YASNO, CHTO~$\hat S(n)\ge S(n)$, GDE~$S(n)$---MINIMALXNOE CHISLO SRAVNENIJ, %%273 NEOBHODIMOE DLYA SORTIROVKI BEZ VSYAKIH OGRANICHENIJ (SM.~P.~5.3.1). mY VIDELI, CHTO~$\hat S(4)=5=S(4)$, PO|TOMU NOVOE OGRANICHENIE NE VYZYVAET POTERI |FFEKTIVNOSTI PRI~$n=4$; NO UZHE PRI~$n=5$ OKAZYVAETSYA, CHTO~$\hat S(5)=9$, V TO VREMYA KAK~$S(5)=7$. zADACHA OPREDELENIYA~$\hat S(n)$ KAZHETSYA ESHCHE BOLEE TRUDNOJ, CHEM ZADACHA OPREDELENIYA~$S(n)$; DO SIH POR NEIZVESTNO DAZHE ASIMPTOTICHESKOE POVEDENIE~$\hat S(n)$. iNTERESNO PROSLEDITX ISTORIYU |TOJ ZADACHI, TAK KAK NA KAZHDYJ NOVYJ SHAG PRIHODILOSX ZATRACHIVATX OPREDELENNYE USILIYA. sETI SORTIROVKI BYLI VPERVYE ISSLEDOVANY p.~n.~aRMSTRONGOM, r.~dZH.~nELXSONOM I d.~dZH.~o'kONNOROM OKOLO 1954~G. [SM.~U.~S.~Patent 3029413]; ONI POKAZALI, CHTO~$\hat S(n+1)\le \hat S(n)+n$. kAK SKAZANO V IH PATENTNOJ ZAYAVKE, "PRILOZHIV STARANIYA, MOZHNO SKONSTRUIROVATX |KONOMICHNYE $n$-VHODNYE SORTIRUYUSHCHIE PEREKLYUCHATELI, ISPOLXZUYA UMENXSHENNOE CHISLO DVUHVHODNYH SORTIRUYUSHCHIH PEREKLYUCHATELEJ"; ONI PRIVELI PRIMERY KONSTRUKCIJ DLYA~$4\le n \le 8$, ISPOLXZOVAV SOOTVETSTVENNO 5, 9, 12, 18 I 19~KOMPARATOROV. rABOTAYA DALEE NAD |TOJ ZADACHEJ, nELXSON SOVMESTNO S r.~ch.~bOZE ESHCHE DO~1960~G. RAZRABOTALI OBSHCHUYU PROCEDURU DLYA POSTROENIYA SETEJ SORTIROVKI, POKAZYVAYUSHCHUYU, CHTO~$\hat S(2^n)\le3^n-2^n$ PRI VSEH~$n$, PO|TOMU~$\hat S(n)=O(n^{\log_2 3})=O(n^{1.585})$. bOZE I~nELXSON OPUBLIKOVALI SVOJ INTERESNYJ METOD V {\sl JACM,\/} {\bf 9} (1962), 282--296, VYSKAZAV PREDPOLOZHENIE, CHTO |TO NAILUCHSHIJ VOZMOZHNYJ REZULXTAT; t.~n.~hIBBARD [{\sl JACM,\/} {\bf 10} (1963), 142--150] NASHEL ANALOGICHNYJ, NO NESKOLXKO BOLEE PROSTOJ METOD, V KOTOROM ISPOLXZUETSYA TAKOE ZHE CHISLO SRAVNENIJ, PODKREPIV TEM SAMYM |TO PREDPOLOZHENIE. v 1964~G.\ r.~u.~fLOJD I~d.~e.~kNUT ISPOLXZOVALI NOVYJ PODHOD K |TOJ ZADACHE, PRIVEDSHIJ IH K ASIMPTOTICHESKOJ OCENKE VIDA~$\hat S(n)=O(n^{1+c/\sqrt{\log n}})$. rABOTAYA NEZAVISIMO, k.~e.~b|TCHER OTKRYL OPISANNUYU VYSHE OBSHCHUYU STRATEGIYU SLIYANIYA; ISPOLXZUYA CHISLO KOMPARATOROV, OPREDELYAEMOE KAK $$ c(1)=0, c(n)=c(\ceil{n/2})+c(\floor{n/2})+C(\ceil{n/2}, \floor{n/2}) \rem{PRI $n\ge2$,} \eqno (10) $$ ON DOKAZAL, CHTO (SM.~UPR.~5.2.2-14) $$ c(2^t)=(t^2-t+4)2^{t-2}-1, $$ I OTSYUDA VYVEL, CHTO~$\hat S(n)=O(n(\log n)^2)$. kAK b|TCHER, TAK I fLOJD S kNUTOM OPUBLIKOVALI SVOI KONSTRUKCII LISHX CHEREZ NEKOTOROE VREMYA [{\sl Notices of the Amer.\ Math.\ Soc.,\/} {\bf 14} (1967), 283; Proc.\ AFIPS Spring Joint Computer Conference, {\bf 32} (1968), 307--314]. %%274 kOE-KOMU UDALOSX SOKRATITX CHISLO KOMPARATOROV, ISPOLXZUEMYH V KONSTRUKCII SLIYANIYA S OBMENAMI, PREDLOZHENNOJ b|TCHEROM; V SLEDUYUSHCHEJ TABLICE POKAZANY DAILUCHSHIE IZ IZVESTNYH V NASTOYASHCHEE VREMYA VERHNIH OCENOK DLYA~$\hat S(n)$: $$ \matrix{ \hfill n=1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 \cr \hfill c(n)=0 & 1 & 3 & 5 & 9 & 12 & 16 & 19 & 26 & 31 & 37 & 41 & 48 & 53 & 59 & 63 \cr \hfill \hat S(n)\le 0 & 1 & 3 & 5 & 9 & 12 & 16 & 19 & 25 & 29 & 35 & 39 & 46 & 51 & 56 & 60\cr } \eqno(11) $$ tAK KAK~$\hat S(n)8$. eSLI~$n\le 8$, TO TAKAYA SORTIROVKA |KVIVALENTNA PO KOLICHESTVU KOMPARATOROV KONSTRUKCII bOZE I~nELXSONA. fLOJD I~kNUT DOKAZALI V 1964--1966~GG., CHTO UKAZANNYE ZNACHENIYA~$\hat S(n)$ \emph{TOCHNY} PRI~$n<8$ [SM.\ A Survey of Combinatorial Theory (North-Holland, 1973), 163--172]; ZNACHENIYA~$\hat S(n)$ PRI~$n>8$ DO SIH POR NEIZVESTNY. kONSTRUKCII, PRIVODYASHCHIE K UKAZANNYM VYSHE ZNACHENIYAM DLYA~$\hat S(n)$, IZOBRAZHENY NA RIS.~49. sETX PRI~$n=9$, OSNOVANNAYA NA INTERESNOM TREHPUTEVOM SLIYANII, BYLA NAJDENA r.~u.~fLOJDOM V 1964~G.; USTANOVITX EE SPRAVEDLIVOSTX MOZHNO PRI POMOSHCHI OBSHCHEGO PRINCIPA, OPISANNOGO V UPR.~27. sETX PRI~$n=10$ V~1969~G.\ POSTROIL a.~vAKSMAN; ON RASSMATRIVAL VHODY KAK PERESTANOVKI MNOZHESTVA~$\set{1, 2,~\ldots, 10}$ I PYTALSYA, SOHRANYAYA NEKOTORUYU SIMMETRIYU, NASKOLXKO VOZMOZHNO UMENXSHITX CHISLO ZNACHENIJ, KOTORYE MOGUT POYAVLYATXSYA V KAZHDOJ STROKE NA DANNOJ STADII. v 1969~G. g.~shAPIRO NASHEL SETX SORTIROVKI 16~|LEMENTOV S 62~KOMPARATORAMI, I |TO BYLO VESXMA NEOZHIDANNO, POSKOLXKU METOD b|TCHERA (63~SRAVNENIYA), KAZALOSX, ISPOLXZUET VSE VOZMOZHNOSTI, ESLI $n$~YAVLYAETSYA STEPENXYU~2. m.~u.~gRIN VSKORE POSLE TOGO, KAK ON OZNAKOMILSYA S KONSTRUKCIEJ shAPIRO, POVERG VSEH V ESHCHE BOLXSHEE IZUMLENIE, NAJDYA SORTIROVKU S 60~SRAVNENIYAMI, POKAZANNUYU NA RIS.~49. pERVAYA CHASTX KONSTRUKCII gRINA DOVOLXNO PROSTA DLYA PONIMANIYA; POSLE TOGO KAK VYPOLNENY 32~OPERACII SRAVNENIYA-OBMENA SLEVA OT PUNKTIRNOJ LINII, VSE PRYAMYE MOZHNO TAK POMETITX 16~PODMNOZHESTVAMI~$\set{a, b, c, d}$, CHTOBY PRO PRYAMUYU, POMECHENNUYU~$s$, BYLO IZVESTNO, CHTO ONA SODERZHIT CHISLA, MENXSHIE ILI RAVNYE SODERZHIMOMU PRYAMOJ, POMECHENNOJ~$t$, VSYAKIJ RAZ, KOGDA $s$~ESTX PODMNOZHESTVO~$t$. sOSTOYANIE SORTIROVKI V |TOT MOMENT OBSUZHDAETSYA BOLEE PODROBNO V UPR.~32. oDNAKO SRAVNENIYA, VYPOLNYAEMYE NA POSLEDUYUSHCHIH UROVNYAH, STANOVYATSYA SOVERSHENNO ZAGADOCHNYMI, I DO SIH POR NIKTO NE ZNAET, KAK OBOBSHCHITX |TU KONSTRUKCIYU, CHTOBY POLUCHITX STOLX ZHE |FFEKTIVNYE SETI DLYA BOLXSHIH ZNACHENIJ~$n$. %%275 shAPIRO I gRIN OTKRYLI TAKZHE IZOBRAZHENNUYU NA RIS.~49 SETX DLYA~$n=12$. hOROSHIE SETI DLYA~$n=11$, 13, 14 I~15 MOZHNO POLUCHITX, UDALIV NIZHNYUYU PRYAMUYU SETI DLYA~$n+1$ VMESTE SO VSEMI KOMPARATORAMI, PODSOEDINENNYMI K |TOJ LINII. \picture{rIS. 49. eFFEKTIVNYE SETI SORTIROVKI.} nAILUCHSHIE IZVESTNYE K NASTOYASHCHEMU MOMENTU SETI DLYA~$n\to\infty$ SM.~V DOKTORSKOJ DISSERTACII d.~vAN~vORISA (Stanford University, 1971); EGO SETI TREBUYUT ASIMPTOTICHESKI %% 276 ${1\over 4}n(\log_2 n)^2-\alpha n \log_2 n$~KOMPARATOROV, GDE~$\alpha={1\over4}+{1\over6}\sum_{k\ge0}2^{-2^k-k}\approx0.356~852$. \section sETI S MINIMALXNYM VREMENEM. v FIZICHESKIH REALIZACIYAH SETEJ SORTIROVKI I NA PARALLELXNYH evm MOZHNO VYPOLNYATX NEPERESEKAYUSHCHIESYA OPERACII SRAVNENIYA-OBMENA ODNOVREMENNO, PO|TOMU KAZHETSYA ESTESTVENNYM POPYTATXSYA MINIMIZIROVATX VREMYA ZADERZHKI. pO NEKOTOROM RAZMYSHLENII ZAKLYUCHAEM, CHTO VREMYA ZADERZHKI SETI SORTIROVKI RAVNO MAKSIMALXNOMU CHISLU KOMPARATOROV, PRILEGAYUSHCHIH K KAKOMU-LIBO "PUTI" CHEREZ SETX, ESLI OPREDELITX PUTX KAK TRAEKTORIYU LYUBOGO DVIZHENIYA SLEVA NAPRAVO, \picture{rIS.~50. vYPOLNENIE KAZHDOGO SRAVNENIYA V NAIBOLEE RANNIJ IZ VOZMOZHNYH MOMENTOV.} VOZMOZHNO, S PEREHODOM S ODNOJ PRYAMOJ NA DRUGUYU CHEREZ KOMPARATORY. u KAZHDOGO KOMPARATORA MY MOZHEM POSTAVITX PORYADKOVYJ NOMER, UKAZYVAYUSHCHIJ SAMYJ RANNIJ MOMENT, KOGDA MOZHET BYTX VYPOLNENO SRAVNENIE; |TOT NOMER NA EDINICU BOLXSHE, CHEM MAKSIMALXNYJ NOMER U KOMPARATOROV, PREDSHESTVUYUSHCHIH DANNOMU. (sM.~RIS.~50(a); V CHASTI~(b) |TOGO RISUNKA POKAZANA TA ZHE SETX, PERERISOVANNAYA TAK, CHTOBY KAZHDOE SRAVNENIE VYPOLNYALOSX V NAIBOLEE RANNIJ VOZMOZHNYJ MOMENT.) v OPISANNOJ VYSHE SETI b|TCHERA DLYA CHETNO-NECHETNOGO SLIYANIYA ZATRACHIVAETSYA $T_b(m,n)$~EDINIC VREMENI, GDE~$T_b(m,0)=T_b(0, n)=0$, $T_B(1,1)=1$ I $$ T_B(m, n)=1+\max(T_B(\floor{m/2}, \floor{n/2}), T_B(\ceil{m/2}, \ceil{n/2})) \rem{DLYA~$mn\ge 2$.} $$ iSPOLXZUYA |TI SOOTNOSHENIYA, MOZHNO DOKAZATX PO INDUKCII, CHTO~$T_B(m, n+1)\ge T_B(m,n)$; SLEDOVATELXNO, $T_B(m, n)=1+T_B(\ceil{m/2}, \ceil{n/2})$ DLYA~$mn\ge2$, A OTSYUDA ZAKLYUCHAEM, CHTO $$ T_B(m,n)=1+\ceil{\log_2 \max (m,n)} \rem{DLYA $mn\ge1$.} \eqno (12) $$ tAKIM OBRAZOM, KAK POKAZANO V UPR.~5, METOD SORTIROVKI b|TCHERA IMEET VREMYA ZADERZHKI $$ \perm{1+\ceil{\log_2 n}}{2}. \eqno(13) $$ %%277 pUSTX $\hat T(n)$---MINIMALXNOE VREMYA ZADERZHKI, DOSTIZHIMOE V LYUBOJ SETI SORTIROVKI $n$~|LEMENTOV. nEKOTORYE IZ OPISANNYH VYSHE SETEJ MOZHNO ULUCHSHITX, NE ISPOLXZOVAV DOPOLNITELXNYH KOMPARATOROV, TAK, CHTOBY ONI IMELI MENXSHEE VREMYA ZADERZHKI, KAK \picture{rIS.~51. sETI SORTIROVKI, KOTORYE NEOBYKNOVENNO BYSTRY, ESLI SRAVNENIYA VYPOLNYAYUTSYA PARALLELXNO.} POKAZANO NA RIS.~51 DLYA~$n=6$ I~$n=9$, A V UPR.~7---DLYA~$n=10$. mOZHNO POLUCHITX ESHCHE MENXSHEE VREMYA ZADERZHKI, ESLI DOBAVITX ODIN ILI DVA DOPOLNITELXNYH MODULYA, KAK POKAZYVAYUT SETI DLYA~$n=10$, 12 I~16 NA RIS.~51. eTI POSTROENIYA PRIVODYAT K SLEDUYU- %%378 SHCHIM VERHNIM OCENKAM DLYA~$T(n)$ PRI UMERENNYH ZNACHENIYAH~$n$: $$ \matrix{ \hfill n=1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16\cr \hfill \hat T(n)\le 0 & 1 & 3 & 3 & 5 & 5 & 6 & 6 & 7 & 7 & 8 & 8 & 9 & 9 & 9 & 9\cr } \eqno(14) $$ iZVESTNO, CHTO PRIVEDENNYE ZDESX ZNACHENIYA TOCHNY PRI~$n\le 8$ (SM.~UPR.~4). sETI NA RIS.~51 ZASLUZHIVAYUT TSHCHATELXNOGO IZUCHENIYA, POSKOLXKU VOVSE NE OCHEVIDNO, CHTO ONI GODYATSYA DLYA SORTIROVKI; |TI SETI BYLI OTKRYTY V~1969--1971~GG. g.~shAPIRO ($n=6$, 9, 12) I~d.~vAN~vORISOM ($n=10$, 16). \section sETI SLIYANIYA. pUSTX $\hat M(m, n)$~OBOZNACHAET MINIMALXNOE CHISLO KOMPARATOROV, NEOBHODIMYH DLYA SETI, KOTORAYA SLIVAET $m$~|LEMENTOV~$x_1~\le~\ldots \le x_m$ S~$n$~|LEMENTAMI~$y_1\le\ldots \le y_n$, OBRAZUYA OTSORTIROVANNUYU POSLEDOVATELXNOSTX~$z_1\le \ldots \le z_{m+n}$. k NASTOYASHCHEMU VREMENI NE OTKRYTO NI ODNOJ SETI SLIYANIYA, KOTORAYA BYLA BY LUCHSHE CHETNO-NECHETNOGO SLIYANIYA, OPISANNOGO VYSHE; SLEDOVATELXNO, FUNKCIYA~$C(m, n)$ V~(6) PREDSTAVLYAET NAILUCHSHUYU IZVESTNUYU VERHNYUYU OCENKU DLYA~$\hat M(m, n)$. r.~u.~fLOJD OBNARUZHIL INTERESNYJ SPOSOB, POZVOLYAYUSHCHIJ OPREDELITX \emph{NIZHNIE} OCENKI V |TOJ ZADACHE SLIYANIYA. \proclaim tEOREMA~F. pRI VSEH~$n\ge 1$ SPRAVEDLIVO NERAVENSTVO~$\hat M (2n, 2n)\ge 2\hat M(n, n)+n$. \proof rASSMOTRIM SETX S~$\hat M(2n, 2n)$~KOMPARATORNYMI MODULYAMI, SPOSOBNUYU SORTIROVATX VSE VHODNYE POSLEDOVATELXNOSTI~$\$, TAKIE, CHTO~$z_1\le z_3\le\ldots \le z_{4n-1}$ I~$z_2\le z_4\le\ldots\le z_{4n}$. mY MOZHEM SCHITATX, CHTO KAZHDYJ MODULX ZAMENYAET~$(z_i, z_j)$ NA~$(\min(z_i, z_j, \max(z_i, z_j))$ PRI NEKOTORYH~$i2n$ I~$j>2n$; \item{c)}~$i\le 2n$ I~$j>2n$. \medskip} kLASS~(a) DOLZHEN SODERZHATX PO KRAJNEJ MERE $\hat M(n, n)$~KOMPARATOROV, TAK KAK $z_{2n+1}$, $z_{2n+2}$,~\dots, $z_{4n}$ MOGUT UZHE NAHODITXSYA NA SVOIH MESTAH, KOGDA SLIYANIE NACHINAETSYA; ANALOGICHNO V KLASSE~(b) DOLZHNO BYTX PO KRAJNEJ MERE $\hat M(n, n)$~KOMPARATOROV. kROME TOGO, KAK POKAZYVAET VHODNAYA POSLEDOVATELXNOSTX~$\<0, 1, 0, 1,~\ldots, 0, 1>$, KLASS~(c) SODERZHIT NE MENEE $n$~KOMPARATOROV, TAK KAK $n$~NULEJ DOLZHNY PEREMESTITXSYA IZ~$\set{z_{2n+1},~\ldots, z_{4n}}$ V~$\set{z_1,~\ldots, z_{2n}}$. \proofend mNOGOKRATNOE PRIMENENIE TEOREMY~F DOKAZYVAET, CHTO~$\hat M(2^m, 2^m)\ge{1\over2}(m+2) 2^m$; SLEDOVATELXNO, $\hat M(n, n) \ge {1\over2}n \log_2 n+O(n)$. %%279 sLIYANIE \emph{BEZ} SETEVOGO OGRANICHENIYA TREBUET LISHX $M(n,n)=2n-1$~SRAVNENIJ; TAKIM OBRAZOM, MY DOKAZALI, CHTO SETEVOE SLIYANIE SLOZHNEE PO SUSHCHESTVU, CHEM SLIYANIE VOOBSHCHE. chETNO-NECHETNOE SLIYANIE POKAZYVAET, CHTO~$\hat M(n,n)\le C(n, n)= n\log_2 n+O(n)$, PO|TOMU ASIMPTOTICHESKOE POVEDENIE~$\hat M(n, n)$ IZVESTNO S TOCHNOSTXYU DO MNOZHITELYA~2. (tOCHNYE ZNACHENIYA~$\hat M(n, n)$ IZVESTNY DLYA~$n\le 5$; SM.~UPR.~9.) a.~k.~yaO I~f.~f.~yaO DOKAZALI, CHTO~$\hat M(2,n)=C(2, n)=\ceil{{3\over2}n}$ I~$\hat M(m, n)\ge{1\over2}n\log_2(m+1)$ PRI~$m$ IZ $p$~CHISEL BUDEM NAZYVATX \dfn{BITONNOJ,} ESLI~$z_1\ge\ldots\ge z_k\le\ldots\le z_p$ DLYA NEKOTOROGO~$k$, $1\le k \le p$ (SRAVNITE |TO S OBYCHNYM OPREDELENIEM "MONOTONNYH" POSLEDOVATELXNOSTEJ). bITONNYJ SORTIROVSHCHIK PORYADKA~$p$---|TO KOMPARATORNAYA SETX, SPOSOBNAYA SORTIROVATX V NEUBYVAYUSHCHEM PORYADKE LYUBUYU BITONNUYU POSLEDOVATELXNOSTX DLINY~$p$. zADACHA SLIYANIYA~$x_1\le\ldots\le x_m$ S~$y_1\le\ldots\le y_n$ YAVLYAETSYA CHASTNYM SLUCHAEM ZADACHI BITONNOJ SORTIROVKI, TAK KAK SLIYANIE MOZHNO OSUSHCHESTVITX, PRIMENIV K POSLEDOVATELXNOSTI~$\$ BITONNYJ SORTIROVSHCHIK PORYADKA~$m+n$. zAMETIM, CHTO ESLI POSLEDOVATELXNOSTX~$\$ BITONNAYA, TO TAKOVYMI ZHE YAVLYAYUTSYA I VSE EE PODPOSLEDOVATELXNOSTI. vSKORE POSLE TOGO, KAK b|TCHER OTKRYL SETI CHETNO-NECHETNOGO SLIYANIYA, ON OBNARUZHIL, CHTO ANALOGICHNYM OBRAZOM MOZHNO POSTROITX BITONNYJ SORTIROVSHCHIK PORYADKA~$p$, SNACHALA NEZAVISIMO SORTIRUYA BITONNYE PODPOSLEDOVATELXNOSTI~$\$ I~$\$, A ZATEM VYPOLNYAYA SRAVNENIYA-OBMENY~$z_1:z_2$, $z_3:z_4$,~$\ldots\,$. (dOKAZATELXSTVO SM.~V~UPR.~10.) eSLI SOOTVETSTVUYUSHCHEE CHISLO KOMPARATORNYH MODULEJ OBOZNACHITX CHEREZ~$C'(p)$, TO BUDEM IMETX $$ C'(p)=C'(\ceil{p/2})+C'(\floor{p/2})+\floor{p/2} \rem{PRI $p\ge2$.} \eqno (15) $$ A VREMYA ZADERZHKI, OCHEVIDNO, RAVNO~$\ceil{\log_2 p}$. nA~RIS.~52 POKAZAN BITONNYJ SORTIROVSHCHIK PORYADKA~7, POSTROENNYJ |TIM SPOSOBOM; ON MOZHET BYTX ISPOLXZOVAN I KAK~$(3, 4)$, I KAK $(2, 5)\hbox{-SETX}$ SLIYANIYA S ZADERZHKOJ V TRI EDINICY; CHETNO-NECHETNOE SLIYANIE DLYA~$m=2$ I~$n=5$ IMEET NA ODIN KOMPARATOR MENXSHE, NO NA ODIN UROVENX ZADERZHKI BOLXSHE. %%280 bITONNYJ SORTIROVSHCHIK b|TCHERA PORYADKA~$2^k$ OSOBENNO INTERESEN; ON SOSTOIT IZ $k$~UROVNEJ PO $2^{k-1}$~KOMPARATOROV V KAZHDOM. zANUMERUEM VHODNYE PRYAMYE~$z_0$, $z_1$,~\dots, $z_{2^k-1}$; PRI |TOM |LEMENT~2, SRAVNIVAETSYA S~$z_j$ NA UROVNE~$l$ TOGDA I TOLXKO TOGDA, KOGDA DVOICHNYE PREDSTAVLENIYA~$i$ I~$j$ RAZLICHAYUTSYA TOLXKO V $l\hbox{-M}$~BITE SLEVA. eTA PROSTAYA STRUKTURA PRIVODIT K PARALLELXNOJ SETI SORTIROVKI, KOTORAYA TAK ZHE BYSTRA, KAK OBMENNAYA SORTIROVKA \picture{rIS.~52. bITONNYJ SORTIROVSHCHIK b|TCHERA PORYADKA~7.} SO SLIYANIEM (ALGORITM~5.2.2M), NO ZNACHITELXNO PROSHCHE DLYA REALIZACII. (sM.~UPR.~11 I~13.) eSLI~$m=n$, TO NETRUDNO VIDETX, CHTO I CHETNO-NECHETNOE SLIYANIE, I BITONNYJ SORTIROVSHCHIK b|TCHERA OBESPECHIVAYUT ABSOLYUTNYJ MINIMUM VREMENI ZADERZHKI, DOSTIZHIMOGO V LYUBOJ SETI SLIYANIYA. \picture{rIS.~53. oDIN |LEMENT SLIVAETSYA S SHESTXYU DRUGIMI S RAZVETVLENIEM, CHTOBY DOSTICHX MINIMALXNO VOZMOZHNOGO VREMENI ZADERZHKI.} v $(n, n)$-SETI SLIYANIYA $n\hbox{-J}$ PO VELICHINE VYHOD (SCHITAYA OT NAIMENXSHEGO) DOLZHEN ZAVISETX OT VSEH $2n$~VHODOV, I ESLI EGO MOZHNO VYCHISLITX ZA $l$~SHAGOV, TO ON BUDET ZAVISETX NE BOLEE, CHEM OT $2^l$~VHODOV; PO|TOMU~$2^l\ge 2n$, $l\ge \ceil{\log_2 (2n)}$. eSLI~$m$ I MY HOTIM VYBRATX $t$~NAIBOLXSHIH; v.~e.~aLEKSEEV [{\sl kIBERNETIKA,\/} {\bf 5}, 5 (1969), 99--103] ZAMETIL, CHTO |TO MOZHET BYTX VYPOLNENO, ESLI SNACHALA OTSORTIROVATX~$\$ I~$\$, A ZATEM SRAVNITX I POMENYATX MESTAMI $$ x_1:x_{2t}, x_2:x_{2t-1},~\ldots, x_t:x_{t+1}. \eqno(17) $$ tAK KAK NI V ODNOJ IZ |TIH PAR NE MOZHET SODERZHATXSYA BOLEE ODNOGO IZ NAIBOLXSHIH $t$~|LEMENTOV (POCHEMU?), TO PROCEDURA aLEKSEEVA DOLZHNA VYBRATX $t$~NAIBOLXSHIH |LEMENTOV. eSLI NAM NUZHNO VYBRATX $t$~NAIBOLXSHIH IZ $nt$~|LEMENTOV, TO MY MOZHEM PRIMENITX |TU PROCEDURU $n-1$~RAZ (ISKLYUCHAYA KAZHDYJ RAZ $t$~|LEMENTOV); SLEDOVATELXNO, $$ \hat U_t(nt)\le (n-1)(2\hat S(t)+t). \eqno(18) $$ aLEKSEEV TAKZHE POLUCHIL INTERESNUYU \emph{NIZHNYUYU} OCENKU DLYA ZADACHI VYBORA. %%282 \proclaim tEOREMA~A. $\hat U_t (n) \ge (n-t)\ceil{\log_2 (t+1)}$. \proof uDOBNEE RASSMATRIVATX |KVIVALENTNUYU ZADACHU VYBORA \emph{NAIMENXSHIH} $t$~|LEMENTOV. oKOLO KAZHDOJ PRYAMOJ KOMPARATORNOJ SETI MOZHNO VYPISATX CHISLA~$(l, u)$, KAK POKAZANO NA RIS.~54, GDE~$l$ I~$u$ OBOZNACHAYUT SOOTVETSTVENNO MINIMALXNOE I \picture{rIS.~54. oTDELENIE CHETYREH NAIBOLXSHIH OT CHETYREH NAIMENXSHIH. (chISLA NAD PRYAMYMI ISPOLXZUYUTSYA V DOKAZATELXSTVE TEOREMY~A.)} MAKSIMALXNOE ZNACHENIYA, KOTORYE MOGUT POYAVITXSYA V |TOM MESTE, ESLI VHODOM SLUZHIT PERESTANOVKA~$\set{1, 2,~\ldots, n}$. pUSTX~$l_i$ I~$l_j$---NIZHNIE OCENKI NA PRYAMYH~$i$ I~$j$ PERED SRAVNENIEM~$x_i:x_j$, I PUSTX~$l'_i$ I~$l'_j$---SOOTVETSTVUYUSHCHIE NIZHNIE OCENKI POSLE |TOGO \picture{rIS.~55. iNAYA INTERPRETACIYA SETI, IZOBRAZHENNOJ NA RIS.~54.} SRAVNENIYA. oCHEVIDNO, CHTO~$l'_i=\min(l_i, l_j)$, A V UPR.~24 DOKAZYVAETSYA (NEOCHEVIDNOE) SOOTNOSHENIE $$ l'_j\le l_i+l_j. \eqno (19) $$ tEPERX DADIM DRUGUYU INTERPRETACIYU DEJSTVIYA SETI (RIS.~55); PREDPOLOZHIM, CHTO NA VSEH VHODNYH PRYAMYH SODERZHITSYA NULX, %%283 A KAZHDYJ "KOMPARATOR" POMESHCHAET TEPERX NA VERHNYUYU PRYAMUYU MENXSHIJ IZ EGO VHODOV, A NA NIZHNYUYU PRYAMUYU---BOLXSHIJ VHOD \emph{PLYUS ODIN.} pOLUCHAYUSHCHIESYA CHISLA~$\$ OBLADAYUT SVOJSTVOM $$ 2^{m_i}\ge l_i \eqno(20) $$ V LYUBOM MESTE SETI, TAK KAK |TO SVOJSTVO PERVONACHALXNO SPRAVEDLIVO I SOHRANYAETSYA KAZHDYM KOMPARATOROM V SILU~(19). kROME TOGO, OKONCHATELXNOE ZNACHENIE $$ m_1+m_2+\cdots+m_n $$ RAVNO OBSHCHEMU CHISLU KOMPARATOROV V SETI, TAK KAK KAZHDYJ KOMPARATOR DOBAVLYAET K |TOJ SUMME EDINICU. eSLI SETX VYBIRAET NAIMENXSHIE $t$~CHISEL, TO~$n-t$ IZ CHISEL~$l_i$ BOLXSHE ILI RAVNY~$t+1$; SLEDOVATELXNO, $n-t$ IZ CHISEL~$m_i$ DOLZHNY BYTX~$\ge \ceil{\log_2 (t+1)}$. \proofend nIZHNYAYA OCENKA V TEOREME~A OKAZYVAETSYA TOCHNOJ, ESLI~$t=1$ ILI~$t=2$ (SM.~UPR.~19). v TABL.~1 DANY ZNACHENIYA~$\hat U_t(n)$, $\hat V_t(n)$ I~$\hat W_t(n)$ DLYA NEBOLXSHIH~$t$ I~$n$. \htable{tABLICA~1}% {sRAVNENIYA, NEOBHODIMYE DLYA SETEJ VYBORA ($\hat U_t(n)$, $\hat V_t(n)$, $\hat W_t(n)$)}% {\strut\hfill$#$\hfill&&\bskip\hfill$#$\hfill\bskip\cr & t=1 & t=2 & t=3 & t=4 & t=5 & t=6 \cr \noalign{\hrule} n=1 & (0,0,0)\cr n=2 & (1,1,1)& (0,1,1)\cr n=3 & (2,2,2)& (2,3,3)& (0,2,3) \cr n=4 & (3,3,3)& (4,5,5)& (3,5,5) & (0,3,5) \cr n=5 & (4,4,4)& (6,7,7)& (6,7,8) & (4,7,9) & (0,4,9) \cr n=6 & (5,5,5)& (8,9,9)& (8,10,10)& (8,10,12) & (5,9,12) & (0,5,12) \cr \noalign{\hrule} } \excercises (pervaya chast') dALEE V NESKOLXKIH UPRAZHNENIYAH DANO BOLEE GLUBOKOE RAZVITIE TEORII SETEJ SORTIROVKI, PO|TOMU BUDET UDOBNO VVESTI NEKOTORYE OBOZNACHENIYA. vMESTO MODULYA SRAVNENIYA-OBMENA BUDEM PISATX~$[i:j]$. sETX S $n$~VHODAMI I $r$~KOMPARATORNYMI MODULYAMI ZAPISHEM KAK~$[i_1:j_1]\,[i_2:j_2]\ldots[i_r:j_r]$, GDE VSE~$i$ I~$j$ MENXSHE ILI RAVNY~$n$; DLYA KRATKOSTI BUDEM NAZYVATX EE $n\hbox{-SETXYU}$. sETX NAZYVAETSYA \dfn{STANDARTNOJ,} ESLI~$i_q$ ESTX $n\hbox{-VEKTOR}$, A $\alpha$~ESTX $n\hbox{-SETX}$, TO ISPOLXZUEM OBOZNACHENIE~$x\alpha$ DLYA VEKTORA CHISEL~$\<(x\alpha)_1,~\ldots, (x\alpha)_n>$, POROZHDENNYH SETXYU. pOLOZHIM TAKZHE DLYA KRATKOSTI~$a\lor b=\max(a, b)$, %%284 $a\land b=\min(a, b)$, $\bar a=1-a$; TOGDA~$(x[i:j])_i=x_i\land x_j$, $(x[i:j])_j=x_i\lor x_j$ I~$(x[i:j])_k=x_k$ DLYA~$i\ne k \ne j$. bUDEM GOVORITX, CHTO $\alpha$~YAVLYAETSYA \emph{SETXYU SORTIROVKI,} TOGDA I TOLXKO TOGDA, KOGDA~$(x\alpha)_i\le(x\alpha)_{i+1}$ DLYA~$1\le i < n$ I VSEH~$x$. sIMVOL~$e^{(i)}$ OBOZNACHAET VEKTOR, U KOTOROGO V POZICII~$i$ NAHODITSYA~1, A V OSTALXNYH MESTAH~0; TAKIM OBRAZOM, $(e^{(i)})_j=\delta_{ij}$. sIMVOL~$D_n$ OBOZNACHAET MNOZHESTVO VSEH $2^n$~$n\hbox{-MESTNYH}$ VEKTOROV IZ~0 I~1, A $P_n$~OBOZNACHAET MNOZHESTVO VSEH $n!$~VEKTOROV, YAVLYAYUSHCHIHSYA PERESTANOVKAMI~$\set{1, 2,~\ldots, n}$. mY BUDEM ISPOLXZOVATX OBOZNACHENIYA~$x\land y$ I~$x\lor y$ DLYA VEKTOROV~$\$ I~$\$ I BUDEM PISATX~$x\le y$, ESLI~$x_i\le y_i$ PRI VSEH~$i$. tAKIM OBRAZOM, $x\le y$~TOGDA I TOLXKO TOGDA, KOGDA~$x\lor y= y$, I TOGDA I TOLXKO TOGDA, KOGDA \picture{rIS.~56. nESTANDARTNAYA SETX, OSNOVANNAYA NA BITONNOJ SORTIROVKE.} $x\land y=x$. eSLI~$x$ I~$y$ LEZHAT V~$D_n$, TO BUDEM GOVORITX, CHTO \dfn{$x$~POKRYVAET~$y$,} ESLI~$x=y\lor e^{(i)}\ne y$ PRI NEKOTOROM~$i$. nAKONEC, DLYA VSEH~$x$ V~$D_n$ PUSTX~$\nu(x)$ BUDET CHISLOM EDINIC V $x$, a~$\zeta(x)$---CHISLOM NULEJ; TAKIM OBRAZOM, $\nu(x)+\zeta(x)=n$. \ex[20] nARISUJTE SETX CHETNO-NECHETNOGO SLIYANIYA DLYA~$m=3$ I~$n=5$. \ex[22] pOKAZHITE, CHTO ALGORITMU SORTIROVKI v.~pRATTA (SM.~UPR.~5.2.1-30) SOOTVETSTVUET SETX SORTIROVKI $n$~|LEMENTOV, IMEYUSHCHAYA PRIBLIZITELXNO $(\log_2 n) \times (\log_3 n)$~UROVNEJ ZADERZHKI. nARISUJTE TAKUYU SETX DLYA~$n=12$. \ex[M20] (k.~e.~b|TCHER.) nAJDITE PROSTOE SOOTNOSHENIE MEZHDU~$C(m, m-1)$ I~$C(m,m)$. \rex[m23] dOKAZHITE, CHTO~$\hat T(6) =5$. \ex[m21] dOKAZHITE, CHTO VYRAZHENIE~(13) DEJSTVITELXNO OPREDELYAET VREMYA ZADERZHKI DLYA SETI SORTIROVKI, OPISANNOJ SOOTNOSHENIYAMI~(10). \ex[28] pUSTX~$T(n)$ BUDET MINIMALXNYM CHISLOM STADIJ, TREBUEMYH DLYA SORTIROVKI S \emph{ODNOVREMENNYM VYPOLNENIEM NEPERESEKAYUSHCHIHSYA SRAVNENIJ} (BEZ SETEVOGO OGRANICHENIYA); KAZHDOE TAKOE MNOZHESTVO SRAVNENIJ MOZHET BYTX PREDSTAVLENO UZLOM, SODERZHASHCHIM MNOZHESTVO PAR~$i_1:j_1$, $i_2:j_2$,~\dots, $i_r:j_r$, GDE VSE~$i_1$, $j_1$, $i_2$, $j_2$,~\dots, $i_r$, $j_r$ RAZLICHNY; OT |TOGO UZLA OTHODIT VNIZ $2^r$~VETVEJ, %%285 SOOTVETSTVUYUSHCHIH SLUCHAYAM $$ \eqalign{ &\<{K_{i_1};\cr &\<{K_{i_1}>K_{j_1}, K_{i_2} \hbox{I~T.~D.}\cr } $$ dOKAZHITE, CHTO~$T(5) =T (6) = 5$. \ex[25] pOKAZHITE, CHTO ESLI POSLEDNIJ KOMPARATOR SETI DLYA~$n=10$ NA~RIS.~49 POMESTITX NEPOSREDSTVENNO PERED VTORYM I TRETXIM S KONCA KOMPARATORAMI, TO SETX PO-PREZHNEMU BUDET SORTIROVATX. \ex[m20] dOKAZHITE, CHTO~$\hat M(m_1+m_2, n_1+n_2)\ge \hat M(m_1, n_1)+ \hat M(m_2, n_2)+\min(m_1, n_2)$ PRI~$m_1, m_2, n_1, n2\ge 0$. \ex[m25] (r.~u.~fLOJD.) dOKAZHITE, CHTO~$\hat M(3,3)=6$, $\hat M(4,4)=9$, $\hat M(5,5)=13$. \ex[m22] dOKAZHITE, CHTO BITONNYJ SORTIROVSHCHIK b|TCHERA, KAK ON OPREDELEN V TEKSTE PERED~(15), DEJSTVITELXNO RABOTAET. [\emph{uKAZANIE.} dOSTATOCHNO DOKAZATX, CHTO BUDUT SORTIROVATXSYA VSE POSLEDOVATELXNOSTI, SOSTOYASHCHIE IZ $k$~EDINIC, ZA KOTORYMI SLEDUYUT $l$~NULEJ, ZA KOTORYMI SLEDUYUT $n-k-l$~EDINIC.] \ex[m23] dOKAZHITE, CHTO BITONNYJ SORTIROVSHCHIK b|TCHERA PORYADKA~$2^p$ BUDET SORTIROVATX NE TOLXKO POSLEDOVATELXNOSTI~$\$, DLYA KOTORYH $z_0 \ge \ldots\ge z_k \le \ldots\le z_{2^p-1}$, NO TAKZHE I VSE POSLEDOVATELXNOSTI, DLYA KOTORYH $z_0\le \ldots \le z_k \ge \ldots \ge z_{2^p-1}$. [kAK SLEDSTVIE |TOGO, SETX NA RIS.~56 BUDET SORTIROVATX 16~|LEMENTOV, TAK KAK KAZHDAYA STADIYA SOSTOIT IZ BITONNYH SORTIROVSHCHIKOV ILI OBRASHCHENNYH BITONNYH SORTIROVSHCHIKOV, PRIMENYAEMYH K POSLEDOVATELXNOSTYAM, KOTORYE BYLI OTSORTIROVANY V PROTIVOPOLOZHNYH NAPRAVLENIYAH.] \ex[m20] dOKAZHITE ILI OPROVERGNITE SLEDUYUSHCHEE UTVERZHDENIE: ESLI~$x$ I~$y$---BITONNYE POSLEDOVATELXNOSTI RAVNOJ DLINY, TO POSLEDOVATELXNOSTI~$x\lor y$ I~$x\land y$ TAKZHE BITONNYE. \rex[24] (X.~s.~sTOUN). pOKAZHITE, CHTO SETX SORTIROVKI DLYA $2^t$~|LEMENTOV MOZHNO POSTROITX PO SHEME, PROILLYUSTRIROVANNOJ DLYA~$t=4$ NA RIS.~57. kAZHDYJ IZ $t^2$~SHAGOV |TOJ SHEMY SOSTOIT IZ "IDEALXNOGO TASOVANIYA" PERVYH $2^{t-1}$~|LEMENTOV S POSLEDNIMI~$2^{t-1}$, ZA KOTORYM SLEDUYUT OPERACII, VYPOLNYAEMYE ODNOVREMENNO NAD $2^{t-1}$~PARAMI SOSEDNIH |LEMENTOV. kAZHDAYA IZ |TIH OPERACIJ OBOZNACHENA LIBO~"$0$" (NET OPERACII), LIBO~"$+$" (STANDARTNYJ KOMPARATORNYJ MODULX), LIBO~"$-$" (OBRASHCHENNYJ KOMPARATORNYJ MODULX). sORTIROVKA PROTEKAET V $t$~STADIJ PO $t$~SHAGOV KAZHDAYA; NA POSLEDNEJ STADII VSE OPERACII SUTX~"$+$". v TECHENIE STADII~$s$ PRI~$sj_q$. eSLI TAKIH INDEKSOV NET, TO OSTANOVITXSYA. \item{T2.}~zAMENITX VSE VHOZHDENIYA~$i_q$ NA~$j_q$ I VSE VHOZHDENIYA~$j_q$ NA~$i_q$ VO VSEH KOMPARATORAH~$[i_s:j_s]$ DLYA~$q\le s \le r$. vERNUTXSYA K SHAGU~T1.\endmark \medskip} \noindent nAPRIMER, SETX~$[4:1]\,[3:2]\,[1:3]\,[2:4]\,[1:2]\,[3:4]$ PREOBRAZUETSYA SNACHALA V~$[1:4]\,[3:2]\,[4:3]\,[2:1]\,[4:2]\,[3:1]$, ZATEM V~$[1:4]\,[2:3]\,[4:2]\,[3:1]\,[4:3]\,[2:1]$, ZATEM %%286 \picture{rIS.~57.~sORTIROVKA 16 |LEMENTOV S "IDEALXNYM TASOVANIEM".} %%287 V~$[1:4]\,[2:3]\,[2:4]\,[3:1]\,[2:3]\,[4:1]$ I~T.~D., POKA NE POLUCHITSYA STANDARTNAYA SETX~$[1:4]\,[2:3]\,[2:4]\,[1:3]\,[1:2]\,[3:4]$. \ex[m25] pUSTX~$D_{tn}$ BUDET MNOZHESTVOM VSEH $\perm{n}{t}$~POSLEDOVATELXNOSTEJ $\$ IZ NULEJ I EDINIC, IMEYUSHCHIH ROVNO $t$~EDINIC. dOKAZHITE, CHTO $\hat U_t(n)$~RAVNO MINIMALXNOMU CHISLU KOMPARATOROV, KOTORYE NEOBHODIMY V SETI, SORTIRUYUSHCHEJ VSE |LEMENTY~$D_{tn}$; CHTO $\hat V_t (n)$~RAVNO MINIMALXNOMU CHISLU KOMPARATOROV, NUZHNYH DLYA SORTIROVKI~$D_{tn}\cup D_{(t-1)n}$; I CHTO $\hat W_t(n)$~RAVNO MINIMALXNOMU CHISLU KOMPARATOROV, NUZHNYH DLYA SORTIROVKI~$\bigcup_{0\le k \le t} D_{kn}$. \rex[m20] dOKAZHITE, CHTO SETX, KOTORAYA OPREDELYAET MEDIANU $2t-1$~|LEMENTOV, TREBUET NE MENEE~$(t-1)\ceil{\log_2(t+1)}+\ceil{\log_2 t}$ KOMPARATORNYH MODULEJ. [\emph{uKAZANIE:} SM. DOKAZATELXSTVO TEOREMY~A.] \ex[m22] dOKAZHITE, CHTO~$\hat U_2(n)=2n-4$ I~$\hat V_2(n)=2n-3$ DLYA VSEH~$n\ge2$. \ex[24] dOKAZHITE, CHTO~$\hat V_3(5)=7$. \ex[M15] pUSTX~$\alpha$---LYUBAYA $n\hbox{-SETX}$, A~$x$ I~$y$---DVA $n\hbox{-VEKTORA}$. dOKAZHITE, CHTO IZ~$x\le y$ SLEDUET~$x\alpha \le y\alpha$. \ex[m15] dOKAZHITE, CHTO ESLI~$x$ I~$y$ SUTX $n\hbox{-VEKTORY}$ DEJSTVITELXNYH CHISEL, TO~$x\cdots y \le (x\alpha)\cdot(y\alpha)$. (zDESX~$x\cdot y$---SKALYARNOE PROIZVEDENIE $x_1y_1+\cdots+x_ny_n$.) \ex[m17]. pUSTX~$\alpha$ ESTX~$n\hbox{-SETX}$. dOKAZHITE, CHTO SUSHCHESTVUET PERESTANOVKA~$p\in P_n$, TAKAYA, CHTO $(p\alpha)_i=j$ TOGDA I TOLXKO TOGDA, KOGDA V~$D_n$~NAJDUTSYA VEKTORY~$x$, $y$, TAKIE, CHTO~$x$ POKRYVAET~$y$, $(x\alpha)_i=1$, $(y\alpha)_i=0$ I~$\zeta(y)=j$. \rex[M21] (v.~e.~aLEKSEEV.) pUSTX~$\alpha$ ESTX~$n\hbox{-SETX}$; VVEDEM OBOZNACHENIYA $l_k=\min\set{ (p\alpha)_k \mid p\in P_n}$, $u_k=\max\set{(p\alpha)_k\mid p\in P_n}$ PRI~$1\le k \le n$ DLYA NIZHNEJ I VERHNEJ GRANIC DIAPAZONA ZNACHENIJ, KOTORYE MOGUT POYAVLYATXSYA NA PRYAMOJ~$k$ VYHODA. pUSTX~$l'_k$ I~$u'_k$---ANALOGICHNO OPREDELENNYE VELICHINY DLYA SETI~$\alpha'=\alpha[i:j]$. dOKAZHITE, CHTO~$l'_i=l_i\land l_j$, $l'_j\le l_i+l_j$, $u'_i\ge u_+u_j-(n+1)$, $u'_j=u_i\lor u_j$. [\emph{uKAZANIE:} DLYA DANNYH VEKTOROV~$x$ I~$y$ IZ~$D_n$, TAKIH, CHTO~$(x\alpha)_i=(y\alpha)_j=0$, $\zeta(x)=l_i$, $\zeta(y)=l_j$, NAJDITE VEKTOR~$z$ IZ~$D_n$, TAKOJ, CHTO~$(z\alpha')_j=0$, $\zeta(z)\le l_i+l_j$.] \ex[M30] pUSTX~$l_k$ I~$u_k$ OPREDELENY, KAK V UPR.~24. dOKAZHITE, CHTO MNOZHESTVO~$\set{(p\alpha)_k \mid p\in P_n}$ SODERZHIT VSE CELYE CHISLA MEZHDU~$l_k$ I~$u_k$ VKLYUCHITELXNO. \ex[M24] (r.~u.~fLOJD.) pUSTX~$\alpha$ ESTX $n\hbox{-SETX}$. dOKAZHITE, CHTO MNOZHESTVO~$D_n\alpha=\set{x\alpha \mid x\in D_n}$ MOZHET BYTX OPREDELENO, IZ MNOZHESTVA~$P_n\alpha=\set{p\alpha \mid p\in P_n}$ I, OBRATNO, $P_n\alpha$~MOZHET BYTX OPREDELENO IZ~$D_n\alpha$. \rex[M20] pUSTX~$x$ I~$y$---VEKTORY, I PUSTX~$x\alpha$ I~$y\alpha$---OTSORTIROVANNYE VEKTORY. dOKAZHITE, CHTO~$(x\alpha)_i\le (y\alpha)_j$ TOGDA I TOLXKO TOGDA, KOGDA DLYA LYUBOJ SOVOKUPNOSTI $j$~|LEMENTOV IZ~$y$ MOZHNO NAJTI SOVOKUPNOSTX $i$~|LEMENTOV IZ~$x$, TAKUYU, CHTO LYUBOJ |LEMENT, VZYATYJ IZ~$x$, MENXSHE NEKOTOROGO |LEMENTA, VZYATOGO IZ~$y$, ILI RAVEN EMU. iSPOLXZUJTE |TOT PRINCIP DLYA DOKAZATELXSTVA TOGO, CHTO \emph{ESLI OTSORTIROVATX STROKI LYUBOJ MATRICY, A ZATEM OTSORTIROVATX STOLBCY, TO STROKI OSTANUTSYA UPORYADOCHENNYMI.} \rex[m20] sLEDUYUSHCHAYA DIAGRAMMA POKAZYVAET, KAK ZAPISATX FORMULY DLYA SODERZHIMOGO VSEH LINIJ SETI SORTIROVKI CHEREZ EE VHODY: \picture{p.287} iSPOLXZUYA ZAKONY KOMMUTATIVNOSTI~$x\land y =y \land x$, $x\lor y = y \lor x$, ZAKONY ASSOCIATIVNOSTI~$x\land (y\land z)=(x\land y) \land z$, $x \lor (y \lor z) = (x \lor y) \lor z$, ZAKONY DISTRIBUTIVNOSTI $x\land (y\lor z)=(x\land y)\lor (x\land z)$, $x\lor(y\land z)=(x\lor y)\land (x\lor z)$, ZAKONY POGLOSHCHENIYA $x\land (x\lor y)=x\lor(x\land y)=x$ I ZAKONY IDEMPOTENTNOSTI $x\land x=x\lor x = x$, MY MOZHEM SVESTI FORMULY V PRAVOJ CHASTI |TOJ SETI SOOTVETSTVENNO K~$(a \land b \land c \land d)$, $(a\land b \land c) \lor (a\land b \land d) \lor (a\land c\land d) \lor (b \land c \land d)$, $(a\land b) \lor (a \land c) \lor (a \land d) \lor (b \land c) \lor (b \land d) \lor (c \land d)$, $a \lor b \lor c \lor d$. dOKAZHITE, %%288 CHTO V OBSHCHEM SLUCHAE $t\hbox{-J}$ V PORYADKE UBYVANIYA |LEMENT IZ~$\set{x_1,~\ldots, x_n}$ DAETSYA "|LEMENTARNOJ SIMMETRICHESKOJ FUNKCIEJ" $$ \sigma_t(x_1,~\ldots, x_n)= \bigvee \set{x_{i_1}\land x_{i_2}\land\ldots\land x_{i_t} \mid 1\le i_1 < i_2 < \ldots < i_t \le n}. $$ [zDESX $\perm{n}{t}$~CHLENOV OB®EDINYAYUTSYA OPERACIEJ~$\vee$ VMESTE. tAKIM OBRAZOM, ZADACHA NAHOZHDENIYA SETI SORTIROVKI MINIMALXNOJ STOIMOSTI |KVIVALENTNA ZADACHE VYCHISLENIYA |LEMENTARNYH SIMMETRICHESKIH FUNKCIJ S MINIMALXNYM CHISLOM SHEM "I/ILI", GDE NA KAZHDOM SHAGE DVE VELICHINY~$\phi$ I~$\psi$ ZAMENYAYUTSYA NA~$\phi\land\psi$ I~$\phi\lor\psi$.] \ex[M20] dANO, CHTO~$x_1\le x_2 \le x_3$ I~$y_1\le y_2 \le y_3 \le y_4 \le y_5$ I CHTO~$z_1\le z_2 \le \ldots \le z_8$---REZULXTAT SLIYANIYA~$x$ S~$y$. nAJDITE VYRAZHENIYA DLYA KAZHDOGO~$z$ CHEREZ~$x$ I~$y$, ISPOLXZUYA OPERATORY~$\land$ I~$\lor$. \ex[vm24] dOKAZHITE, CHTO LYUBAYA FORMULA, SODERZHASHCHAYA~$\land$, $\lor$ I NEZAVISIMYE PEREMENNYE~$\set{x_1,~\ldots, x_n}$, MOZHET BYTX PRIVEDENA S ISPOLXZOVANIEM TOZHDESTV IZ UPR.~28 K "KANONICHESKOJ" FORME~$\tau_1\lor\tau_2\lor\ldots\lor\tau_k$, ZDESX~$k\ge1$ I KAZHDYJ~$\tau_i$ IMEET VID~$\land \set{x_j \mid j \in S_i}$, GDE~$S_i$---PODMNOZHESTVO~$\set{1,2,~\ldots, n}$ I NIKAKOE MNOZHESTVO~$S_i$ NE VKLYUCHAETSYA V~$S_j$, ESLI~$i\ne j$. dOKAZHITE TAKZHE, CHTO DVE TAKIE KANONICHESKIE FORMY RAVNY DLYA VSEH~$x_1$,~\dots, $x_n$ TOGDA I TOLXKO TOGDA, KOGDA ONI IDENTICHNY (S TOCHNOSTXYU DO PORYADKA). \ex[m24] (r.~dEDEKIND, 1897.) pUSTX~$\delta_n$---CHISLO RAZLICHNYH KANONICHESKIH FORM OT~$x_1$,~\dots, $x_n$ V SMYSLE UPR.~30 tAK, $\delta_1=l$, $\delta_2=4$ I~$\delta_3=18$. chEMU RAVNO~$\delta_4$? \ex[m28] (m.~u.~gRIN.) pUSTX~$G_1=\set{00, 01, 11}$; OPREDELIM~$G_{n+1}$ KAK MNOZHESTVO VSEH CEPOCHEK~$\theta\phi\psi\omega$, TAKIH, CHTO~$\theta$, $\phi$, $\psi$, $\omega$ IMEYUT DLINU~$2^{n+1}$ I~$\theta\phi$, $\psi\omega$, $\theta\psi$ I~$\phi\omega$ PRINADLEZHAT~$G_n$. pUSTX~$\alpha$---SETX, SOSTOYASHCHAYA IZ CHETYREH PERVYH UROVNEJ 16-SORTIROVSHCHIKA, IZOBRAZHENNOGO NA RIS.~48. pOKAZHITE, CHTO~$D_{16}\alpha=G_4$, I DOKAZHITE, CHTO |TO MNOZHESTVO IMEET V TOCHNOSTI $\delta_4+2$~|LEMENTOV. (sM.~UPR.~31.) \rex[m22] nE VSE $\delta_n$~FUNKCIJ OT~$\$ IZ UPR.~31 MOGUT VSTRETITXSYA V KOMPARATORNYH SETYAH. a IMENNO DOKAZHITE, CHTO FUNKCIYA~$(x_1\land x_2) \lor (x_2\land x_3) \lor (x_3\land x_4)$ NE MOZHET BYTX REZULXTATOM NIKAKOJ KOMPARATORNOJ SETI OT~$\$. \ex[23] yaVLYAETSYA LI SLEDUYUSHCHAYA SETX SETXYU SORTIROVKI? \picture{p.288} \ex[20] dOKAZHITE, CHTO V LYUBOJ \emph{STANDARTNOJ SETI} SORTIROVKI DOLZHEN PO KRAJNEJ MERE ODIN RAZ VSTRETITXSYA KAZHDYJ IZ KOMPARATOROV~$[i:i+1]$ PRI~$1\le i < n$. \rex[22] sETX NA RIS.~47 SODERZHIT TOLXKO \emph{KRATCHAJSHIE} SRAVNENIYA~$[i:i+1]$; BUDEM NAZYVATX TAKIE SETI \dfn{PRIMITIVNYMI,} (a)~dOKAZHITE, CHTO PRIMITIVAAYA SETX SORTIROVKI DLYA $n$~|LEMENTOV DOLZHNA IMETX NE MENEE $\perm{n}{2}$~KOMPARATOROV. [\emph{uKAZANIE:} RASSMOTRITE INVERSII PERESTANOVKI.] (b)~(r.~u.~fLOJD, 1964.) pUSTX~$\alpha$---PRIMITIVNAYA SETX DLYA $n$~|LEMENTOV, A~$x$---VEKTOR, TAKOJ, CHTO~$(x\alpha)_i >(x\alpha)_j$ PRI NEKOTORYH~$i(y\alpha)_j$, GDE~$y$---VEKTOR~$\$. (S)~v KACHESTVE SLEDSTVIYA~(b) DOKAZHITE, CHTO PRIMITIVNAYA %%288 SETX YAVLYAETSYA SETXYU SORTIROVKI TOGDA I TOLXKO TOGDA, KOGDA ONA SORTIRUET EDINSTVENNYJ VEKTOR~$\$! \ex[m22] \dfn{chETNO-NECHETNAYA SORTIROVKA S TRANSPOZICIYAMI} DLYA $n$~CHISEL, $n\ge 3$, |TO $n\hbox{-UROVNEVAYA}$ SETX S ${1\over2}n(n-1)$~KOMPARATORAMI, NAPOMINAYUSHCHAYA KIRPICHNUYU KLADKU (RIS.~58). (eSLI $n$~CHETNO, IMEYUTSYA DVE VOZMOZHNOSTI.) tAKUYU SORTIROVKU OSOBENNO LEGKO REALIZOVATX APPARATURNO, TAK KAK POPEREMENNO VYPOLNYAYUTSYA TOLXKO DVA VIDA DEJSTVIJ. dOKAZHITE, CHTO TAKAYA SETX DEJSTVITELXNO BUDET PRAVILXNOJ SETXYU SORTIROVKI. [\emph{uKAZANIE:} SM.~UPR.~36.] \picture{rIS.~58. chETNO-NECHETNAYA SORTIROVKA S TRANSPOZICIYAMI.} \ex[29] mOZHNO DATX DRUGUYU INTERPRETACIYU SETYAM SORTIROVKI, SCHITAYA, CHTO NA KAZHDOJ LINII NAHODITSYA MULXTIMNOZHESTVO IZ $m$~CHISEL, A NE ODNO CHISLO; PRI |TOJ INTERPRETACII OPERACIYA~$[i:j]$ ZAMENYAET~$x_i$ I~$x_j$ SOOTVETSTVENNO NA~$x_i \upup x_j$ I~$x_i\dndn x_j$---NAIMENXSHIE~$m$ I NAIBOLXSHIE~$m$ IZ~$2m$ CHISEL~$x_i\uplus x_j$. (rIS.~59 ILLYUSTRIRUET |TO PRI~$m=2$.) eSLI~$a$ I~$b$ SUTX MULXTIMNOZHESTVA, SODERZHASHCHIE $m$~CHISEL KAZHDOE, TO BUDEM GOVORITE, CHTO~$a \lflf b$ TOGDA \picture{rIS.~59. dRUGAYA INTERPRETACIYA SETI SORTIROVKI, PREDSTAVLENNOJ NA RIS.~44: KAZHDYJ KOMPARATORNYJ MODULX VYPOLNYAET OPERACIYU SLIYANIYA.} I TOLXKO TOGDA, KOGDA~$a \upup b=a$ (ILI, |KVIVALENTNO, $a \dndn b=b$; NAIBOLXSHIJ |LEMENT~$a$ MENXSHE ILI RAVEN NAIMENXSHEMU |LEMENTU~$b$). tAKIM OBRAZOM, $a \upup b \lflf a \dndn b$. pUSTX~$\alpha$ ESTX $n\hbox{-SETX}$, a~$x=\$---VEKTOR, V KOTOROM KAZHDAYA KOMPONENTA~$x_i$---MULXTIMNOZHESTVO IZ $m$~|LEMENTOV. dOKAZHITE, CHTO ESLI~$(x\alpha)_i$ NE $\lflf (x\alpha)_j$ V OPISANNOJ INTERPRETACII, TO V~$D_n$ NAJDETSYA VEKTOR~$y$, TAKOJ, CHTO $(y\alpha)_i=1$ I~$(y\alpha)_j=0$. [sLEDOVATELXNO, SETX SORTIROVKI $n$~|LEMENTOV PREVRASHCHAETSYA V SETX SORTIROVKI $mn$~|LEMENTOV, ESLI ZAMENITX SRAVNENIYA $m$-PUTEVYMI SLIYANIYAMI. nA RIS.~60 IZOBRAZHEN VOSXMI|LEMENTNYJ SORTIROVSHCHIK, POSTROENNYJ IZ CHETYREH|LEMENTNOGO S ISPOLXZOVANIEM |TOGO NABLYUDENIYA.] \rex[m23] pOKAZHITE, CHTO V OBOZNACHENIYAH UPR.~38 $(x\upup y)\upup z=x\upup (y\upup z)$ I~$(x\dndn y)\dndn z=x\dndn(y\dndn z)$, ODNAKO $(x\dndn y)\upup z)$ \emph{NE} VSEGDA RAVNO~$(x\upup z)\dndn (y\upup z)$ I~$(x\upup y)\dndn (x\upup z)\dndn (y\upup z)$ \emph{NE} VSEGDA RAVNO SREDNIM $m$~|LEMENTAM~$x\uplus y \uplus z$. nAJDITE PRAVILXNUYU FORMULU DLYA |TIH SREDNIH |LEMENTOV, ISPOLXZOVAV V NEJ $x$, $y$, $z$, A TAKZHE OPERACII~$\upup$ I~$\dndn$. %%290 \ex[M25] (r.~l.~gR|HEM.) kOMPARATOR~$[i:j]$ NAZYVAETSYA IZBYTOCHNYM V SETI~$\alpha_1[i:j]\alpha_2$, ESLI LIBO~$(x\alpha_1)_i \le (x\alpha_1)_j$ DLYA VSEH VEKTOROV~$x$, LIBO~$(x\alpha_1)_i\ge (x\alpha_1)_j$ DLYA VSEH VEKTOROV~$x$. dOKAZHITE, CHTO ESLI $\alpha$~YAVLYAETSYA SETXYU S $r$~NEIZBYTOCHNYMI KOMPARATORAMI, TO NAJDUTSYA PO KRAJNEJ MERE $r$~RAZLICHNYH UPORYADOCHENNYH \picture{rIS.~60. 8-SORTIROVSHCHIK, POSTROENNYJ IZ 4-SORTIROVSHCHIKA S ISPOLXZOVANIEM SLIYANIYA.} PAR~$(i, j)$ RAZLICHNYH INDEKSOV, TAKIH, CHTO~$(x\alpha)_i\le (x\alpha)_j$ DLYA VSEH VEKTOROV~$x$. (sLEDOVATELXNO, SETX BEZ IZBYTOCHNYH KOMPARATOROV SODERZHIT NE BOLEE $\perm{n}{2}$~MODULEJ.) \rex[M27] (v.~e.~aLEKSEEV.) pUSTX~$\alpha=[i_1:j_1]\ldots[i_r:j_r]$ ESTX~$n\hbox{-SETX}$; DLYA~$1\le s \le r$ OPREDELIM~$\alpha^s=[i'_1:j'_1]\ldots[i'_{s-1}:j'_{s-1}]\, [i_s:j_s]\ldots[i_r:j_r]$, GDE~$i'_k$ I~$j'_k$ POLUCHENY IZ~$i_k$ I~$j_k$ ZAMENOJ~$i_s$ NA~$j_s$ I~$j_s$ NA~$i_s$ VEZDE, GDE ONI VSTRECHAYUTSYA. nAPRIMER, ESLI~$\alpha=[1:2]\,[3:4]\,[1:3]\,[2:4]\,[2:3]$, TO~$\alpha^4=[1:4]\, [3:2]\,[1:3]\,[2:4]\,[2:3]$. {\medskip\narrower \item{a)}~dOKAZHITE, CHTO~$D_n\alpha=D_n(\alpha^s)$. \item{b)}~dOKAZHITE, CHTO~$(\alpha^s)^t=(\alpha^t)^s$. \item{c)}~\dfn{sOPRYAZHENIEM~$\alpha$} YAVLYAETSYA LYUBAYA SETX VIDA~$(\ldots((\alpha^{s_1})^{s_2})\ldots)^{s_k}$. dOKAZHITE, CHTO $\alpha$~IMEET NE BOLEE $2^{r-1}$~SOPRYAZHENIJ. \item{d)}~pUSTX~$g_\alpha(x)=1$, ESLI~$x\in D_n\alpha$, I~$g_\alpha(x)=0$, ESLI~$x\notin D_n\alpha$, I PUSTX $$ f_\alpha(x)=(\bar x_{i_1}\lor x_{j_1})\land\ldots\land(\bar x_{i_r}\lor x_{j_r}). $$ dOKAZHITE, CHTO~$g_\alpha(x)=\bigvee\set{f_{\alpha'}(x)\mid \hbox{$\alpha'$ ESTX SOPRYAZHENIE~$\alpha$}}$. \item{e)}~pUSTX~$G_\alpha$---NAPRAVLENNYJ GRAF S VERSHINAMI~$\set{1,~\ldots, n}$ I DUGAMI~$i_s\to j_s$ DLYA~$1\le s \le r$. dOKAZHITE, CHTO A YAVLYAETSYA SETXYU SORTIROVKI TOGDA I TOLXKO TOGDA, KOGDA DLYA VSEH EE SOPRYAZHENIJ~$\alpha'$ V~$G_{\alpha'}$ IMEETSYA ORIENTIROVANNYJ PUTX OT~$i$ DO~$i+1$ DLYA~$1\le i < n$. [eTO DOVOLXNO INTERESNOE USLOVIE, POSKOLXKU~$G_\alpha$ NE ZAVISIT OT PORYADKA KOMPARATOROV V~$\alpha$.] \medskip} \rex[25] (d.~vAN vORIS.) dOKAZHITE, CHTO~$\hat S(n)\ge \hat S(n-1)+\ceil{\log_2 n}$. \ex[23] \dfn{pERESTANOVOCHNOJ SETXYU} NAZYVAETSYA POSLEDOVATELXNOSTX MODULEJ~$[i_1:j_1]\ldots[i_r:j_r]$, GDE KAZHDYJ MODULX~$[i:j]$ MOZHET USTANAVLIVATXSYA IZVNE V ODNO IZ DVUH SOSTOYANIJ: LIBO ON PEREDAET SVOI VHODY BEZ IZMENENIJ, LIBO MENYAET MESTAMI~$x_i$ I~$x_j$ (NEZAVISIMO OT ZNACHENIJ~$x_i$ I~$x_j$), I POSLEDOVATELXNOSTX MODULEJ DOLZHNA BYTX TAKOJ, CHTO NA VYHODE MOZHNO POLUCHITX LYUBUYU PERESTANOVKU VHODOV PRI SOOTVETSTVUYUSHCHEJ USTANOVKE MODULEJ. lYUBAYA SETX SORTIROVKI YAVLYAETSYA, OCHEVIDNO, PERESTANOVOCHNOJ SETXYU, NO OBRATNOE NEVERNO. nAJDITE PERESTANOVOCHNUYU SETX DLYA PYATI |LEMENTOV, IMEYUSHCHUYU TOLXKO VOSEMX MODULEJ. %%291 \ex[46] iZUCHITE SVOJSTVA SETEJ SORTIROVKI, POSTROENNYH IZ $m$-SORTIROVSHCHIKOV VMESTO 2-SORTIROVSHCHIKOV. (nAPRIMER, g.~shAPIRO POSTROIL SETX DLYA SORTIROVKI 16~|LEMENTOV, ISPOLXZOVAV CHETYRNADCATX 4-SORTIROVSHCHIKOV. nAILUCHSHEE LI |TO RESHENIE? sUSHCHESTVUET LI DLYA VSEH $m$~|FFEKTIVNYJ SPOSOB SORTIROVKI $m^2$~|LEMENTOV S POMOSHCHXYU MODULEJ, VYPOLNYAYUSHCHIH $m$-SORTIROVKU?) \ex[48] nAJDITE, $(m, n)\hbox{-SETX}$ SLIYANIYA S CHISLOM KOMPARATOROV, MENXSHIM~$C(m,n)$, ILI DOKAZHITE, CHTO TAKOJ SETI NE SUSHCHESTVUET. \ex[48] nAJDITE $(m, n)\hbox{-SETX}$ SLIYANIYA MENXSHE, CHEM S $\ceil{\log_2 (m+n)}$~UROVNYAMI ZADERZHKI, ILI DOKAZHITE, CHTO EE NE SUSHCHESTVUET. \ex[48] iZUCHITE KLASS SHEM SORTIROVKI, KOTORYE MOGUT BYTX REALIZOVANY V VIDE SHEM S IDEALXNYM TASOVANIEM, KAK NA RIS.~57, NO S DRUGIM RASPOLOZHENIEM OPERACIJ~"$0$", "$+$" I~"$-$". \ex[vm49] iSSLEDUJTE SVOJSTVA OPERACIJ~$\upup$ I~$\dndn$, OPREDELENNYH V UPR.~38. mOZHNO LI OHARAKTERIZOVATX VSE TOZHDESTVA V |TOJ ALGEBRE KAKIM-LIBO IZYASHCHNYM SPOSOBOM ILI VYVESTI VSE IH IZ KONECHNOGO NABORA TOZHDESTV? v |TOM OTNOSHENII TAKIE TOZHDESTVA, KAK $$ x\upup x \upup x = x \upup x \hbox{ ILI } x\upup (x\dndn (x\upup (x\dndn y)))=x\upup(x\dndn y), $$ KOTORYE IMEYUT MESTO TOLXKO DLYA~$m\le 2$, PREDSTAVLYAYUT OTNOSITELXNO NEBOLXSHOJ INTERES; RASSMATRIVAJTE LISHX TOZHDESTVA, SPRAVEDLIVYE PRI \emph{VSEH}~$m$. \ex[M49] kAKOVO ASIMPTOTICHESKOE POVEDENIE FUNKCII~$T(n)$, OPREDELENNOJ V UPR.~B? mOZHET LI BYTX $T(n)<\hat T(n)$ PRI KAKOM-NIBUDX~$n$? \ex[50] nAJDITE TOCHNOE ZNACHENIE~$\hat S(n)$ DLYA KAKOGO-LIBO~$n>8$. \ex[m50] dOKAZHITE, CHTO ASIMPTOTICHESKOE ZNACHENIE~$\hat S(n)$ NE ESTX~$O(n\log n)$. \centerline{{\bf uprazhneniya, (vtoraya chast')}} sLEDUYUSHCHIE UPRAZHNENIYA IMEYUT DELO S RAZLICHNYMI TIPAMI OPTIMALXNYH ZADACH, KASAYUSHCHIHSYA SORTIROVKI. pERVYE NESKOLXKO ZADACH OSNOVANY NA "INTERESNOM "MNOGOGOLOVOCHNOM" OBOBSHCHENII METODA PUZYRXKA, PREDLOZHENNOM f.~n.~aRMSTRONGOM I~r.~dZH.~nELXSONOM ESHCHE V~1954~G. [sM.~U.~S.~Patents 3029413, 3034102.] pUSTX~$1=h_1N$, TO ZAPISX~$R_{j+h[k]}$ NE RASSMATRIVAETSYA, INACHE GOVORYA, %%292 KLYUCHI~$K_0$, $K_{-1}$, $K_{-2}$,~\dots{} SCHITAYUTSYA RAVNYMI~$-\infty$, a~$K_{N+1}$, $K_{N+2}$,~\dots{}---RAVNYMI~$+\infty$. pO|TOMU PRI~$j\le -h[m-1]$ ILI~$j>N-h[2]$ SHAG~$j$ TRIVIALEN.) nAPRIMER, V SLEDUYUSHCHEJ TABLICE POKAZAN ODIN PROHOD SORTIROVKI PRI~$m=3$, $N=9$ I~$h_1=1$, $h_2=2$, $h_3=4$: {\def\ul#1{\underline{#1}}\def\emp{\phantom{0}} \ctable{ $#$\hfill && \bskip\hfill$#$\hfill\bskip\cr & K_{-2} & K_{-1} & K_0 & K_1 & K_2 & K_3 & K_4 & K_5 & K_6 & K_7 & K_8 & K_9 & K_{10} & K_{11} & K_{12}\cr j=-3 & \ul{\emp} & \ul{\emp} & & \ul{3} & 1 & 4 & 5 & 9 & 2 & 6 & 8 & 7 \cr j=-2 & & \ul{\emp}& \ul{\emp}& 3 & \ul{1} & 4 & 5 & 9 & 2 & 6 & 8 & 7 \cr j=-1 & & & \ul{\emp}&\ul{3} & 1 & \ul{4} & 5 & 9 & 2 & 6 & 8 & 7\cr j=0 & & & &\ul{1} & \ul{3} & 4 & \ul{5} & 9 & 2 & 6 & 8 & 7 \cr j=1 & & & & 1 & \ul{3} & \ul{4} & 5 & \ul{9} & 2 & 6 & 8 & 7 \cr j=2 & & & & 1 & 3 & \ul{2} & \ul{4} & 9 & \ul{5} & 6 & 8 & 7 \cr j=3 & & & & 1 & 3 & 2 & \ul{4} & \ul{6} & 5 &\ul{9} & 8 & 7 \cr j=4 & & & & 1 & 3 & 2 & 4 & \ul{5} & \ul{6} & 9 & \ul{8} & 7 \cr j=5 & & & & 1 & 3 & 2 & 4 & 5 & \ul{6} & \ul{7} & 8 & \ul{9}\cr j=6 & & & & 1 & 3 & 2 & 4 & 5 & 6 & \ul{7} & \ul{8} & 9 & \ul{\emp} \cr j=7 & & & & 1 & 3 & 2 & 4 & 5 & 6 & 7 & \ul{8} & \ul{9} & & \ul{\emp}\cr j=8 & & & & 1 & 3 & 2 & 4 & 5 & 6 & 7 & 8 & \ul{9} & \ul{\emp}& & \ul{\emp} \cr } } zAMETIM, CHTO, ESLI~$m=2$, $h_1=1$ I~$h_2=2$, |TOT "MNOGOGOLOVOCHNYJ" METOD SVODITSYA K METODU PUZYRXKA (ALGORITM~5.2.2B). \ex[21] (dZHEJMS dUGUNDI.) dOKAZHITE, CHTO ESLI~$h[k+1]=h[k]+1$ PRI NEKOTOROM~$k$, $1\le k < m$, TO MNOGOGOLOVOCHNYJ SORTIROVSHCHIK, OPREDELENNYJ VYSHE, OTSORTIRUET LYUBOJ VHODNOJ FAJL ZA KONECHNOE CHISLO PROHODOV. nO ESLI~$h[k+1]\ge h[k]+2$ PRI~$1\le k < m$, TO MOZHET SLUCHITXSYA, CHTO VHODNAYA POSLEDOVATELXNOSTX \emph{NIKOGDA} NE STANET UPORYADOCHENNOJ. \edef\exref{\the\excerno} \rex[50] (aRMSTRONG I~nELXSON.) pUSTX~$h[k+1]\le h[k]+k$ PRI~$1\le k\le m$ I~$N\ge n-1$. dOKAZHITE, CHTO V TECHENIE PERVOGO PROHODA NAIBOLXSHIE $n-1$~|LEMENTOV VSEGDA ZAJMUT SVOI OKONCHATELXNYE MESTA. [\emph{uKAZANIE:} ISPOLXZUJTE PRINCIP NULEJ I EDINIC; DOKAZHITE, CHTO ESLI SORTIRUETSYA POSLEDOVATELXNOSTX IZ NULEJ I EDINIC, PRICHEM EDINIC MENXSHE~$n$, TO VSE GOLOVKI MOGUT CHITATX~1 LISHX V TOM SLUCHAE, KOGDA VSE NULI LEZHAT SLEVA OT GOLOVOK.] dOKAZHITE, CHTO ESLI GOLOVKI UDOVLETVORYAYUT SFORMULIROVANNYM USLOVIYAM, TO SORTIROVKA BUDET ZAKONCHENA NE BOLEE, CHEM ZA $\ceil{(N-1)/(n-1)}$~PROHODOV. sUSHCHESTVUET LI VHODNOJ FAJL, DLYA KOTOROGO NEOBHODIMO ROVNO STOLXKO PROHODOV? \ex[26] dOKAZHITE, CHTO PRI~$n=N$ PERVYJ PROHOD POMESTIT NAIMENXSHIJ KLYUCH V POZICIYU~$R_1$ TOGDA I TOLXKO TOGDA, KOGDA~$h[k+1]\le 2h[k]$, $1\le k=\<1, 2, 4, 7,~\ldots, 1+\perm{m}{2}>. $$ OBRAZUET SOVERSHENNYJ SORTIROVSHCHIK DLYA $N=\perm{m}{2}$~|LEMENTOV, ISPOLXZUYA $m=(\sqrt{8N-7}+l)/2$~GOLOVOK. nAPRIMER, POSLEDOVATELXNOSTX GOLOVOK~$\<1, 2, 4, 7, 11, 16, 22>$ YAVLYAETSYA SOVERSHENNYM SORTIROVSHCHIKOM DLYA 22~|LEMENTOV. dOKAZHITE, CHTO POSLEDOVATELXNOSTX GOLOVOK~$\<1, 2, 4, 7, 11, 16, 23>$ NA SAMOM DELE BUDET SOVERSHENNYM SORTIROVSHCHIKOM DLYA 23~|LEMENTOV. \ex[49] oPREDELITE PRI ZADANNOM~$m$ NAIBOLXSHEE~$N$, DLYA KOTOROGO SUSHCHESTVUET SOVERSHENNYJ SORTIROVSHCHIK S $m$~GOLOVKAMI. vERNO LI, CHTO~$N=O(m^2)$? %%293 \ex[23] (v.~pRATT.) eSLI KAZHDAYA GOLOVKA~$h_k$ NAHODITSYA V POLOZHENII~$2^{k-1}$ DLYA~$1\le k \le m$, TO SKOLXKO PROHODOV POTREBUETSYA DLYA SORTIROVKI POSLEDOVATELXNOSTI NULEJ I EDINIC~$z_1$ $z_2$~\dots{} $z_{2^{m-1}}$, GDE $z_j=0$ TOGDA I TOLXKO TOGDA, KOGDA $j$~YAVLYAETSYA STEPENXYU~2? \ex[24] (oDNORODNAYA SORTIROVKA.) v DEREVE NA RIS.~34 V P.~5.3.1 SRAVNENIE~$2:3$ VYPOLNYAETSYA V OBOIH VETVYAH UROVNYA~1; A V KAZHDOJ VETVI UROVNYA~2 VYPOLNYAETSYA SRAVNENIE~$1:3$, ESLI TOLXKO ONO NE YAVLYAETSYA IZBYTOCHNYM. v OBSHCHEM SLUCHAE MY MOZHEM RASSMOTRETX KLASS ALGORITMOV SORTIROVKI, ODNORODNYH IMENNO V |TOM SMYSLE, PREDPOLAGAYA, CHTO~$M=\perm{N}{2}$ PAR~$\set{(a,b) \mid 1\le aK_{b_i}$, TO DOBAVITX DUGU~$b_i\to a_i$. \medskip nAS INTERESUET GLAVNYM OBRAZOM CHISLO SRAVNENIJ KLYUCHEJ, VYPOLNYAEMYH ALGORITMOM ODNORODNOJ SORTIROVKI, A NE MEHANIZM, S POMOSHCHXYU KOTOROGO DEJSTVITELXNO USTRANYAYUTSYA IZBYTOCHNYE SRAVNENIYA; GRAF~$G$ NE OBYAZATELXNO STROITX V YAVNOM VIDE---ZDESX ON ISPOLXZUETSYA TOLXKO DLYA OPREDELENIYA ODNORODNOJ SORTIROVKI. bUDEM TAKZHE RASSMATRIVATX \dfn{OGRANICHENNUYU ODNORODNUYU SORTIROVKU,} PRI KOTOROJ V UKAZANNYH VYSHE SLUCHAYAH 1--3 UCHITYVAYUTSYA TOLXKO PUTI DLINY~2. (aLGORITM OGRANICHENNOJ SORTIROVKI MOZHET VYPOLNYATX NEKOTORYE IZBYTOCHNYE SRAVNENIYA, NO, KAK POKAZYVAET UPR.~59, ANALIZ OGRANICHENNOGO SLUCHAYA NESKOLXKO PROSHCHE.) dOKAZHITE, CHTO ALGORITM OGRANICHENNOJ ODNORODNOJ SORTIROVKI SOVPADAET S ALGORITMOM ODNORODNOJ SORTIROVKI, KOGDA POSLEDOVATELXNOSTX PAR LEKSIKOGRAFICHESKI UPORYADOCHENA: $$ (1, 2)\, (1, 3)\, (1, 4)\ldots(1, N)\, (2, 3)\, (2, 4)\ldots(2, N)\ldots (N-1, N). $$ pOKAZHITE, CHTO NA SAMOM DELE OBA ALGORITMA |KVIVALENTNY "BYSTROJ SORTIROVKE" (ALGORITM~5.2.2Q), ESLI VSE KLYUCHI RAZLICHNY I IZBYTOCHNYE SRAVNENIYA BYSTROJ SORTIROVKI USTRANENY, KAK V UPR.~5.2.2-24. (nE OBRASHCHAJTE VNIMANIYA NA PORYADOK, V KOTOROM DEJSTVITELXNO VYPOLNYAYUTSYA SRAVNENIYA V BYSTROJ SORTIROVKE; UCHITYVAJTE TOLXKO, KAKIE PARY KLYUCHEJ SRAVNIVAYUTSYA.) \ex[m38] dLYA ZADANNOJ, KAK V UPR.~58, POSLEDOVATELXNOSTI PAR~$(a_1, b_1)$~\dots{}$(a_M, b_M)$ PUSTX~$c_i$ BUDET CHISLOM PAR~$(j, k)$, TAKIH, CHTO~$jR_i$, DOSTIGAETSYA MINIMALXNOE CHISLO PROHODOV. %% 295 \bye