\input style %% 161 pRIVEDENNOE NIZHE RASSUZHDENIE POKAZHET, CHTO |TA POSLEDNYAYA SUMMA ESTX $O(1)$; SLEDOVATELXNO, $U_n-T_n=O(1)$. (sM. UPR.~47.) dO SIH POR MY ESHCHE NE ISPOLXZOVALI NIKAKIH METODOV, KOTORYE BY DEJSTVITELXNO OTLICHALISX OT PRIMENYAVSHIHSYA RANEE, NO \picture{rIS. 20. kONTURY INTEGRIROVANIYA DLYA TOZHDESTV S GAMMA-FUNKCIYAMI.} DLYA IZUCHENIYA RYADA~$T_n$ POTREBUETSYA NOVAYA IDEYA, OSNOVANNAYA NA PROSTYH PRINCIPAH TEORII FUNKCIJ KOMPLEKSNOGO PEREMENNOGO. eSLI $x$---PROIZVOLXNOE POLOZHITELXNOE CHISLO, TO $$ e^{-x}={1\over 2\pi i}\int_{1/2-i\infty}^{1/2+i\infty} \Gamma(z)x^{-z}\,dz= {1\over 2\pi}\int_{-\infty}^\infty\Gamma\left({1\over2}+it\right)x^{-(1/2+it)}\,dt. \eqno(42) $$ dLYA DOKAZATELXSTVA |TOGO TOZHDESTVA RASSMOTRIM PUTX INTEGRIROVANIYA, POKAZANNYJ NA RIS.~20(a), GDE $N$, $N'$ I $M$ VELIKI. zNACHENIE INTEGRALA VDOLX |TOGO KONTURA RAVNO SUMME VYCHETOV VNUTRI KONTURA, A IMENNO $$ \sum_{0\le k0$,} $$ TAK KAK $\abs{2^w} = 2^{\Re(w)} > 1$. pO|TOMU $$ T_n={n\over2\pi i} \int_{-3/2-i\infty}^{-3/2+i\infty} {\Gamma(z)n^{-1-z}\over 2^{-1-z}-1}\, dz, \eqno(45) $$ I OSTAETSYA OCENITX POSLEDNIJ INTEGRAL. nA |TOT RAZ INTEGRIROVANIE PROIZVODITSYA PO KONTURU, KOTORYJ BOLXSHE VYTYANUT VPRAVO, KAK IZOBRAZHENO NA RIS. 20(b). %% 163 iNTEGRAL PO VERHNEMU OTREZKU ESTX $O\left(n^{1/2}e^{-\pi M/2} \int_{-3/2}^M N^t\,dt\right)$, ESLI $2^{iN}\ne1$, A INTEGRAL PO NIZHNEMU OTREZKU TAKZHE PRENEBREZHIMO MAL. iNTEGRAL PO PRAVOMU OTREZKU RAVEN $O\left( n^{-1-M} \int_{-\infty}^\infty \abs{\Gamma(M+it)}\,dt\right)$. fIKSIRUYA $M$ I USTREMLYAYA $N$, $N'$ K~$\infty$, MOZHNO POKAZATX, CHTO $-T_n/n$ ESTX $O(n^{-1-M})$ PLYUS SUMMA VYCHETOV V OBLASTI $-3/2 < \Re(z)a_j$. pUSTX $a'_1$ \dots $a'_n$---PERESTANOVKA, KOTORAYA POLUCHAETSYA IZ $a_1$ \dots $a_n$, ESLI POMENYATX MESTAMI $a_i$ I $a_j$. mOZHET LI V $a'_1$ \dots $a'_n$ BYTX BOLXSHE INVERSIJ, CHEM V $a_1$ \dots $a_n$? \rex[m25] (a) kAKOVO MINIMALXNOE CHISLO OBMENOV, NEOBHODIMOE DLYA TOGO, CHTOBY OTSORTIROVATX PERESTANOVKU 3\ 7\ 6\ 9\ 8\ 1\ 4\ 5? (b) vOOBSHCHE PUSTX DANA PERESTANOVKA $\pi=a_1\ \ldots\ a_n$ MNOZHESTVA $\{1, \ldots, n\}$, I PUSTX $\mathop{\rm xch}\nolimits (\pi)$---MINIMALXNOE CHISLO OBMENOV, V REZULXTATE KOTORYH PERESTANOVKA $\pi$ BUDET OTSORTIROVANA V VOZRASTAYUSHCHEM PORYADKE. vYRAZITE $\mathop{\rm xch}\nolimits (\pi)$, CHEREZ "BOLEE PROSTYE" HARAKTERISTIKI PERESTANOVKI~$\pi$. (sR. S UPR. 5 2.1--39.) \ex[10] yaVLYAETSYA LI USTOJCHIVOJ SORTIROVKA METODOM PUZYRXKA (ALGORITM B)? \ex[m23] eSLI V SHAGE B4 POLUCHITSYA $t=1$, TO NA SAMOM DELE RABOTU ALGORITMA~B MOZHNO SRAZU ZHE ZAKANCHIVATX, POTOMU CHTO V SLEDUYUSHCHEM SHAGE B2 NE VYPOLNITSYA NIKAKIH POLEZNYH DEJSTVIJ. kAKOVA VEROYATNOSTX TOGO, CHTO PRI SORTIROVKE SLUCHAJNOJ PERESTANOVKI V SHAGE B4 OKAZHETSYA $t=1$? \ex[m25] pUSTX $b_1$ $b_2$ \dots $b_n$---TABLICA INVERSIJ PERESTANOVKI $a_1$ $a_2$ \dots $a_n$. pOKAZHITE, CHTO POSLE $r$ PROSMOTROV SORTIROVKI METODOM PUZYRXKA ZNACHENIE PEREMENNOJ |BOUND| RAVNO $\max \{b_i+i \mid b_i\ge r\}-r$, GDE $0\le r\le \max(b_1, \ldots, b_n)$. \ex[m22] pUSTX $a_1$ \dots{} $a_n$---PERESTANOVKA MNOZHESTVA $\{1, \dots, n\}$, I PUSTX $a'_1$ \dots{} $a'_n$---OBRATNAYA K NEJ PERESTANOVKA. pOKAZHITE, CHTO CHISLO PROSMOTROV, NEOBHODIMYH DLYA TOGO, CHTOBY OTSORTIROVATX $a_1$ \dots{} $a_n$" METODOM PUZYRXKA. RAVNO $1+\max(a'_1-1, a'_2-2, \ldots, a'_n-n)$. \ex[m28] vYCHISLITE STANDARTNOE OTKLONENIE CHISLA PROSMOTROV SORTIROVKI METODOM PUZYRXKA I VYRAZITE EGO CHEREZ $n$ I FUNKCIYU $P(n)$. [sR. S FORMULAMI (6) I (7).] \ex[m24] vYVEDITE FORMULU (8). \ex[m48] pROANALIZIRUJTE CHISLO PROSMOTROV I CHISLO SRAVNENIJ V ALGORITME SHEJKER-SORTIROVKI. (\emph{zAMECHANIE:} CHASTICHNAYA INFORMACIYA SODERZHITSYA V UPR. 5.4.8--9.) \ex[m26] pUSTX $a_1$ $a_2$ \dots{} $a_n$---2-UPORYADOCHENNAYA PERESTANOVKA MNOZHESTVA $\{1, 2, \ldots, n\}$. (a) kAKOVY KOORDINATY KONECHNYH TOCHEK $a_i\hbox{-GO}$ SHAGA SOOTVETSTVUYUSHCHEGO RESHETOCHNOGO PUTI (SR. S RIS.~11)? (b) dOKAZHITE, CHTO SRAVNENIE/OBMEN |LEMENTOV $a_1$: $a_2$, $a_3$, $a_4$, \dots SOOTVETSTVUET PEREGIBANIYU PUTI OTNOSITELXNO DIAGONALI, KAK NA RIS.~18(b). (S) dOKAZHITE, CHTO SRAVNENIE/OBMEN |LEMENTOV $a_2$: $a_{2+d}$, $a_4$:$a_{4+d}$, \dots{} SOOTVETSTVUET PEREGIBANIYU PUTI OTNOSITELXNO LINII, RASPOLOZHENNOJ NA $m$ EDINIC NIZHE DIAGONALI, KAK NA RIS. 18(S), (d) I (e), ESLI $d=2m-l$. \rex[m25] nA KAKOJ PERESTANOVKE MNOZHESTVA $\{1, 2, \ldots, 16\}$ DOSTIGAETSYA MAKSIMUM CHISLA OBMENOV V ALGORITME b|TCHERA? \ex[24] nAPISHITE \MIX-PROGRAMMU DLYA ALGORITMA M, PREDPOLAGAYA, CHTO \MIX---DVOICHNAYA VYCHISLITELXNAYA MASHINA S OPERACIYAMI |AND| I |SRB|. sKOLXKO VREMENI POTREBUETSYA VASHEJ PROGRAMME, CHTOBY OTSORTIROVATX SHESTNADCATX ZAPISEJ IZ TABL.~1? %%165 \ex [10] uSTOJCHIVA LI SORTIROVKA b|TCHERA? \ex [m21] pUSTX $c(N)$---CHISLO SRAVNENIJ KLYUCHEJ, PROIZVODIMYH PRI SORTIROVKE $N$ |LEMENTOV METODOM b|TCHERA; |TO RAVNO CHISLU VYPOLNENII SHAGA M4. (a) pOKAZHITE, CHTO PRI $t\ge 1$ $c(2^t)=2c(2^{t-1}+(t-1)2^{t-1}+1.$ (b) nAJDITE PROSTOE VYRAZHENIE DLYA $c(2^t)$ KAK FUNKCIYU OT~$t$. (\emph{uKAZANIE:} RASSMOTRITE POSLEDOVATELXNOSTX $x_t=c(2^t)/2^t)$. \ex[m38] sODERZHANIE |TOGO UPRAZHNENIYA---ANALIZ FUNKCII $c(N)$ IZ UPR.~14 I NAHOZHDENIE FORMULY DLYA $c(N)$, ESLI $N=2^{e_1}+2^{e_2}+\cdots+2^{e_r}$, $e_1>e_2>\ldots>e_r\ge0$. (a) pUSTX $a(N)=c(N+1)-c(N)$. dOKAZHITE, CHTO $a(2n)=a(n)+\floor{\log_2(2n)}$, $a(2n+1)=a(n)+1$; OTSYUDA $$ a(N)=\perm{e_1+1}{2}-r(e_1-1)+(e_1+e_2+\cdots+e_r). $$ (b) pUSTX $x(n)=a(n)-a(\floor{n/2})$, I TOGDA $a(n)=x(n)+x(\floor{n/2})+x(\floor{n/4})+\cdots$. pUSTX $y(n)=x(1)+x(2)+\cdots+x(n)$, I PUSTX~$z(2n)=y(2n)-a(n)$, $z(2n+1)=y(2n+1)$. dOKAZHITE, CHTO $c(N+1)=z(N)+2z(\floor{N/2})+4z(\floor{N/4})+\cdots$. (c) dOKAZHITE,CHTO $y(N)=N+(\floor{N/2}+1)\times(e_1-1)-2^{e_1}+2$. (d) tEPERX SOBERITE VSE VMESTE I NAJDITE VYRAZHENIE $c(N)$ CHEREZ POKAZATELI $e_j$ PRI FIKSIROVANNOM ZNACHENII $r$. \ex[vm46] nAJDITE ASIMPTOTICHESKOE ZNACHENIE SREDNEGO CHISLA OBMENOV V SLUCHAE, KOGDA ALGORITM b|TCHERA PRIMENYAETSYA K $N=2^t$ RAZLICHNYM |LEMENTAM, RASPOLOZHENNYM V SLUCHAJNOM PORYADKE. \rex[20] gDE V ALGORITME Q ISPOLXZUETSYA TO, CHTO $K_0$ I~$K_{N+1}$ OBLADAYUT ZNACHENIYAMI, POSTULIROVANNYMI NERAVENSTVAMI (13)? \rex[20] oB®YASNITE, KAK RABOTAET ALGORITM Q V SLUCHAE, KOGDA VSE KLYUCHI V ISHODNOM FAJLE RAVNY. chTO PROIZOJDET, ESLI V SHAGAH Q3 I Q5 ZAMENITX ZNAKI "$<$" NA "$\le$"? \ex[15] bUDET LI ALGORITM Q PO-PREZHNEMU RABOTATX PRAVILXNO, ESLI VMESTO STEKA (POSLEDNIM VKLYUCHAETSYA---PERVYM ISKLYUCHAETSYA) VOSPOLXZOVATXSYA OCHEREDXYU (PERVYM VKLYUCHAETSYA---PERVYM ISKLYUCHAETSYA)? \ex[m20] vYRAZITE NAIBOLXSHEE CHISLO |LEMENTOV, KOTORYE MOGUT ODNOVREMENNO OKAZATXSYA V STEKE VO VREMYA RABOTY ALGORITMA Q, V VIDE FUNKCII OT~M I~$N$. \ex[20] oB®YASNITE, POCHEMU FAZA RAZDELENIYA V ALGORITME Q TREBUET KAK RAZ TAKOGO CHISLA SRAVNENIJ, PERESYLOK I T. D., KAK |TO OPISANO V (17). \ex[m25] pUSTX $p_kN$---VEROYATNOSTX TOGO, CHTO VELICHINA~$A$ V (14) BUDET RAVNA~$k$, ESLI ALGORITM Q PRIMENYAETSYA K SLUCHAJNOJ PERESTANOVKE MNOZHESTVA $\{1, 2, \ldots, N\}$, I PUSTX~$A_N(z)=\sum_k p_kN^{z^k}$---SOOTVETSTVUYUSHCHAYA PROIZVODYASHCHAYA FUNKCIYA. dOKAZHITE, CHTO~$A_N(z)=1$ PRI~$N\le M$, I~$A_N(z)= z(\sum_{1\le s\le N} A_{s-1}(z)A_{N-s}(z))/N$ PRI~$N>M$. nAJDITE ANALOGICHNYE REKURRENTNYE SOOTNOSHENIYA, OPREDELYAYUSHCHIE DRUGIE RASPREDELENIYA VEROYATNOSTEJ $B_N(z)$, $C_N(z)$, $D_N(z)$, $E_N(z)$, $L_N(z)$, $X_N(z)$. \ex[m24] pUSTX $A_N$, $B_N$, $D_N$, $E_N$, $L_N$, $X_N$---SREDNIE ZNACHENIYA SOOTVETSTVUYUSHCHIH VELICHIN V (14) PRI SORTIROVKE SLUCHAJNOJ PERESTANOVKI-MNOZHESTVA $\{1, 2, \ldots, N\}$. nAJDITE DLYA |TIH VELICHIN REKURRENTNYE SOOTNOSHENIYA, ANALOGICHNYE (18), ZATEM RAZRESHITE |TI SOOTNOSHENIYA I POLUCHITE FORMULY (25). \ex[m21] oCHEVIDNO, V ALGORITME Q PROIZVODITSYA NESKOLXKO BOLXSHE SRAVNENIJ, CHEM |TO NEOBHODIMO, POTOMU CHTO V SHAGAH Q3 I Q5 MOZHET OKAZATXSYA, CHTO $i=j$ ILI DAZHE $i>j$. sKOLXKO SRAVNENIJ $G_N$ PROIZVODILOSX BY V SREDNEM, ESLI BY ISKLYUCHALISX VSE SRAVNENIYA PRI $i\ge j$? \ex[m20] chEMU RAVNY TOCHNYE ZNACHENIYA VELICHIN $A$, $B$, $C$, $D$, $E$, $L$, $X$ DLYA PROGRAMMY Q V SLUCHAE, KOGDA ISHODNYE KLYUCHI PREDSTAVLYAYUT SOBOJ UPORYADOCHENNYJ NABOR CHISEL $1$, $2$, \dots, $N$ V PREDPOLOZHENII, CHTO $N>M$? \rex[M2I] pOSTROJTE ISHODNYJ FAJL, PRI KOTOROM PROGRAMMA Q .RABOTALA BY ESHCHE MEDLENNEE, CHEM V UPR.~25. (pOPYTAJTESX NAJTI DEJSTVITELXNO PLOHOJ SLUCHAJ.) %% 166 \bye