\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 k<M} x^{-k}\lim_{z\to-k}(z+k)\Gamma(z)=
\sum_{0\le k<M} x^{-k}{(-1)^k\over k!}.
$$
iNTEGRAL PO VERHNEJ CHASTI KONTURA ESTX 
$O\left(\int_{-\infty}^{1/2}\abs{\Gamma(t+iN)}x^{-t}\,dt\right)$,
I U NAS IMEETSYA IZVESTNAYA OCENKA
$$
\Gamma(t+iN)=O(N^{t-1/2} e^{-\pi N/2}) \rem{PRI $N\to\infty$.}
$$
[sVOJSTVA GAMMA-FUNKCIJ SM., NAPRIMER, V KNIGE A.~Erd\'elyi et al., Higher 
Transcendental Functions, 1 (New York: McGraw-Hill, 1953), GL.~1.] pO|TOMU 
INTEGRAL PO VERHNEMU OTREZKU
BESKONECHNO MAL: 
$O\left( e^{-\pi N/2}\int_{-\infty}^{1/2} (N/x)^t\,dt\right)$. 
iNTEGRAL PO NIZHNEMU
%% 162
OTREZKU VEDET SEBYA STOLX ZHE BEZOBIDNO. dLYA VYCHISLENIYA INTEGRALA PO 
LEVOMU OTREZKU KONTURA VOSPOLXZUEMSYA TEM FAKTOM, CHTO
$$
\eqalign{
\Gamma\left({1\over2}+it-M\right)&=
\Gamma\left({1\over2}+it\right)/\left(-M+{1\over2}+it\right)
  \ldots\left(-1+{1\over2}+it\right)=\cr
&=\Gamma\left({1\over2}+it\right) O(1/(M-1)!).\cr
}
$$
sLEDOVATELXNO, INTEGRAL PO LEVOJ STORONE ESTX 
$O(x^{M-1/2}/(M-1)!)\times
 \int_{-\infty}^\infty\abs{\Gamma\left({1\over2}+it\right)}\,dt$. 
pO|TOMU PRI $M$, $N$, $N'\to\infty$ UCELEET LISHX
INTEGRAL PO PRAVOJ STORONE; TEM SAMYM DOKAZANO TOZHDESTVO (42). v 
DEJSTVITELXNOSTI TOZHDESTVO (42) OSTAETSYA V SILE I V TOM SLUCHAE, ESLI 
ZAMENITX $1\over2$ LYUBYM POLOZHITELXNYM CHISLOM.

tEM ZHE SAMYM RASSUZHDENIEM MOZHNO VOSPOLXZOVATXSYA DLYA VYVODA DRUGIH 
POLEZNYH SOOTNOSHENIJ, SODERZHASHCHIH GAMMA-FUNKCII. vELICHINU $x^{-z}$ MOZHNO 
ZAMENITX DRUGIMI FUNKCIYAMI OT $z$; MOZHNO
TAKZHE ZAMENITX DRUGOJ VELICHINOJ KONSTANTU $1\over2$. nAPRIMER,
$$
{1\over2\pi i}\int_{-3/2-i\infty}^{-3/2+i\infty}\Gamma(z)x^{-z}\,dz
=e^{-x}-1+x,
\eqno(43)
$$
A |TO---KRITICHESKAYA VELICHINA V FORMULE (41) DLYA $T_n$:
$$
T_n=n\sum_{j\ge1}
{1\over2\pi i}\int_{-3/2-i\infty}^{-3/2+i\infty}\Gamma(z)(n/2^j)^{-1-z}\,dz.
\eqno(44)
$$

sUMMIROVANIE MOZHNO VNESTI POD ZNAK INTEGRALA, TAK KAK SHODIMOSTX ZDESX 
DOSTATOCHNO HOROSHAYA; IMEEM
$$
\sum_{j\le 1}(n/2^j)^w=n^w\sum_{j\le1}(1/2^w)^j=n^w/(2^w-1),
\rem{ESLI $\Re(w)>0$,}
$$
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)<M$. pUSTX $M\to\infty$, $\Gamma(z)$ IMEET PROSTYE 
POLYUSY PRI $z=-1$ I~$z=0$, $n^{-1-z}$ NE IMEET POLYUSOV, a~$1/(2^{-1-z}-1)$ 
IMEET PROSTYE POLYUSY PRI $z=-1+2\pi i k/\ln2$.

nAIBOLXSHUYU TRUDNOSTX PREDSTAVLYAET DVOJNOJ POLYUS V TOCHKE~$z=-1$. eSLI 
$w=z+1$ MALO, TO MOZHNO VOSPOLXZOVATXSYA IZVESTNYM SOOTNOSHENIEM
$$
\Gamma(z+1)
=\exp(-\gamma z+\zeta(2)z^2/2-\zeta(3)z^3/3+\zeta(4)z^4/4-\ldots),
$$
GDE~$\zeta(s)=1^{-s}+2^{-s}+3^{-s}+\ldots=H_\infty^{(s)}$, DLYA VYVODA 
SLEDUYUSHCHIH RAZLOZHENIJ:
$$
\eqalign{
\Gamma(z)&={\Gamma(w+1)\over w(w-1)}=-w^{-1}+(\gamma-1)+O(w);\cr
n^{-1-z}&=1-(\ln n)w+O(w^2);\cr
1/(2^{-1-z}-1)&=-w^{-1}/\ln2-{1\over2}+O(w).\cr
}
$$
vYCHET V TOCHKE~$z=-1$ RAVEN KO|FFICIENTU PRI $w^{-1}$ V PROIZVEDENII |TIH 
TREH FORMUL, A IMENNO ${1\over2}-(\ln n+\gamma-1)/\ln2$. pRIBAVLYAYA 
OSTALXNYE VYCHETY, POLUCHAEM FORMULU
$$
T_n/n={\ln n+\gamma-1\over \ln 2}-{1\over2}+f(n)+{2\over n},
\eqno(46)
$$
GDE  $f(n)$---FUNKCIYA DOVOLXNO NEOBYCHNOGO VIDA:
$$
f(n)={2\over\ln 2}
\sum_{k\ge1} \Re(\Gamma(-1-2\pi ik/\ln2)\exp(2\pi i k\log_2n)).
\eqno(47)
$$
zAMETIM, CHTO $f(n)=f(2n)$. sREDNEE ZNACHENIE $f(n)$ RAVNO~0, TAK KAK 
SREDNEE ZNACHENIE KAZHDOGO SLAGAEMOGO RAVNO 0. (mOZHNO SCHITATX, CHTO 
VELICHINA $(\log_2 n) \bmod 1$ RASPREDELENA RAVNOMERNO, PRINIMAYA VO 
VNIMANIE REZULXTATY O CHISLAH S PLAVAYUSHCHEJ TOCHKOJ, POLUCHENNYE V P.~4.2.4.) 
kROME TOGO, POSKOLXKU 
$\abs{\Gamma(-1+it)}=\abs{\pi/(t(1+t^2)\sinh \pi t)}^{1/2}$, NETRUDNO 
POKAZATX, CHTO
$$
f(n)< 0.0000001725;
$$
TAKIM OBRAZOM, V PRAKTICHESKIH PRILOZHENIYAH $f(n)$ MOZHNO SPOKOJNO 
OTBROSITX. chTO KASAETSYA TEORII, TO BEZ~$f(n)$ MY NE MOZHEM
%%164
POLUCHITX ASIMPTOTICHESKOGO RYADA DLYA $U_n$; IMENNO PO|TOMU VELICHINA~$U_n$ 
SRAVNITELXNO TRUDNA DLYA ANALIZA. 
iTAK, MY DOKAZALI, CHTO
$$
U_n=n\log_2n+n\left({\gamma-1\over\ln2}-{1\over2}+f(n)\right)+O(1).
\eqno(48)
$$
dRUGIE PRIMERY PRIMENENIYA |TOGO METODA GAMMA-FUNKCIJ MOZHNO NAJTI V 
UPR.~51--53 I V \S~6.3.

\excercises
\ex[m20] pUSTX $a_1$ \dots $a_n$---PERESTANOVKA MNOZHESTVA $\{1, \ldots, n\}$, 
I PUSTX $i$ I $j$ TAKOVY, CHTO $i<j$ I~$a_i>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[M21] pOSTROJTE ISHODNYJ FAJL, PRI KOTOROM PROGRAMMA Q RABOTALA BY 
ESHCHE MEDLENNEE, CHEM V UPR.~25. (pOPYTAJTESX NAJTI DEJSTVITELXNO PLOHOJ SLUCHAJ.)

%% 166
\ex[m23] kAKOJ ISHODNYJ FAJL BUDET \emph{NAILUCHSHIM} DLYA 
ALGORITMA~Q? nAJDITE PRIBLIZITELXNYE ZNACHENIYA VELICHIN~$A$, $B$, $C$, $D$, 
$E$, $X$ DLYA |TOGO SLUCHAYA.

\ex[M26] nAJDITE REKURRENTNOE SOOTNOSHENIE, ANALOGICHNOE~(20), 
KOTOROMU UDOVLETVORYAET SREDNEE CHISLO SRAVNENIJ V ALGORITME~Q, 
MODIFICIROVANNOM sINGLTONOM (T.~E.\ KOGDA V KACHESTVE~$s$ VYBIRAETSYA 
NE~$s=K_1$, A MEDIANA IZ~$\set{K_1, K_{\floor{(N+1)/2}}, K_N}$).

\ex[vm40] nAJDITE ASIMPTOTICHESKOE ZNACHENIE CHISLA SRAVNENIJ V ALGORITME 
sINGLTONA "MEDIANA IZ TREH" (SM.~UPR.~28).

\ex[25] (p.~shAKLETON.) pRI SORTIROVKE \emph{KLYUCHEJ DLINOJ V NESKOLXKO 
SLOV} MNOGIE ALGORITMY VSE BOLEE ZAMEDLYAYUTSYA PO MERE TOGO, KAK FAJL 
PRIBLIZHAETSYA K UPORYADOCHENNOMU SOSTOYANIYU, POSKOLXKU DLYA OPREDELENIYA 
PRAVILXNOGO LEKSIKOGRAFICHESKOGO PORYADKA RAVNYH ILI POCHTI RAVNYH KLYUCHEJ 
TREBUETSYA SRAVNITX NESKOLXKO PAR SLOV (SM.~UPR.~5-5). fAJLY, KOTORYE 
VSTRECHAYUTSYA NA PRAKTIKE, CHASTO SODERZHAT POCHTI RAVNYE KLYUCHI, I |TO 
YAVLENIE MOZHET ZAMETNO OTRAZITXSYA NA VREMENI SORTIROVKI.

tAKOE ZATRUDNENIE SUSHCHESTVENNO DLYA ALGORITMA~Q, NO NE DLYA ALGORITMA~R,
POSKOLXKU TAM KAZHDYJ RAZ PROVERYAETSYA TOLXKO ODIN BIT (HOTYA 
PRISUTSTVIE RAVNYH I POCHTI RAVNYH KLYUCHEJ MOZHET SILXNO UVELICHITX VREMYA 
RABOTY ALGORITMA~R PO DRUGIM PRICHINAM).

oB®YASNITE, KAK MOZHNO USOVERSHENSTVOVATX ALGORITM~Q, CHTOBY IZBEZHATX |TOGO 
ZATRUDNENIYA; V PODFAJLE, O KOTOROM IZVESTNO, CHTO STARSHIE $k$~SLOV VO VSEH 
KLYUCHAH SODERZHAT POSTOYANNYE ZNACHENIYA, SLEDUET PROVERYATX LISHX 
$(k+1)\hbox{-E}$~SLOVA KLYUCHEJ.

\rex[20] (ch.~e.~r.~hOAR) pREDPOLOZHIM, CHTO NAM NUZHNO NE OTSORTIROVATX FAJL, A 
LISHX OPREDELITX $m\hbox{-J}$ NAIMENXSHIJ PO VELICHINE |LEMENT IZ 
ZADANNOGO MNOZHESTVA $n$~|LEMENTOV. pOKAZHITE, CHTO "BYSTRUYU SORTIROVKU" 
MOZHNO PRISPOSOBITX DLYA |TOJ CELI, IZBEZHAV ZNACHITELXNOJ CHASTI VYCHISLENIJ, 
NEOBHODIMYH DLYA POLNOJ SORTIROVKI.

\ex[m40] nAJDITE PROSTOE VYRAZHENIE "V ZAMKNUTOM VIDE" 
DLYA~$C_{nm}$---SREDNEGO CHISLA SRAVNENIJ KLYUCHEJ, NEOBHODIMYH DLYA OTYSKANIYA 
$m\hbox{-GO}$~NAIMENXSHEGO IZ $n$~|LEMENTOV PO METODU UPR.~31. (dLYA 
PROSTOTY MOZHNO PROPUSKATX VSE SRAVNENIYA S~$i\ge j$, KAK V UPR.~24.) kAKOVO 
ASIMPTOTICHESKOE POVEDENIE VELICHINY~$C_{(2m-1)m}$---SREDNEGO CHISLA SRAVNENIJ, 
NEOBHODIMYH DLYA NAHOZHDENIYA MEDIANY IZ $2m-1$~|LEMENTOV METODOM hOARA?

\rex[20] rAZRABOTAJTE ALGORITM PERERAZMESHCHENIYA CHISEL V NEKOTOROJ ZADANNOJ 
TABLICE TAKIM OBRAZOM, CHTOBY VSE OTRICATELXNYE ZNACHENIYA PREDSHESTVOVALI 
POLOZHITELXNYM. eLEMENTY NE NUZHNO POLNOSTXYU SORTIROVATX:
DOSTATOCHNO PROSTO OTDELITX OTRICATELXNYE CHISLA OT POLOZHITELXNYH. 
vASH ALGORITM DOLZHEN PROIZVODITX MINIMALXNO VOZMOZHNOE CHISLO OBMENOV.

\ex[20] kAK MOZHNO USKORITX CIKLY PROVERKI BITOV V OBMENNOJ PORAZRYADNOJ 
SORTIROVKE (SHAGI OT~R3 DO~R6)?

\ex[m23] pROANALIZIRUJTE STATISTICHESKIE HARAKTERISTIKI~$A$, $B$, $C$, $G$,
$K$, $L$, $R$, $S$ I~$X$, KOTORYE POLUCHAYUTSYA PRI OBMENNOJ PORAZRYADNOJ 
SORTIROVKE DLYA "ISHODNYH DANNYH TIPA~(i)".

\ex[m27] dLYA LYUBOJ DANNOJ POSLEDOVATELXNOSTI CHISEL~$\< a_n >=a_0$, $a_1$,
$a_2$,~\dots{} OPREDELIM EE \dfn{BINOMIALXNOE-PREOBRAZOVANIE} 
$\<\hat a>_n=\hat a_0$, $\hat a_1$, $\hat a_2$,~\dots{} PRAVILOM
$$
\hat a_n = \sum_k \perm{n}{k} (-1)^k a_k.
$$
(a)~dOKAZHITE, CHTO~$\<\hat {\hat a}_n>=\< a_n>$. (b)~nAJDITE BINOMIALXNYE 
PREOBRAZOVANIYA POSLEDOVATELXNOSTEJ~$\<1>$; $\<n>$; $\<\perm{n}{m}>$ PRI 
FIKSIROVANNOM~$m$; $\<a^n>$ PRI FIKSIROVANNOM~$a$; $\<\perm{n}{m}a^n>$ PRI 
FIKSIROVANNYH~$a$ I~$m$. (c)~pRI USLOVII, CHTO
%% 167
POSLEDOVATELXNOSTX~$\<x_n>$ UDOVLETVORYAET SOOTNOSHENIYU
$$
x_n=a_n+2^{1-n}\sum_{k\ge 2} \perm{n}{k}x_k 
\rem{PRI~$n\ge 2$, $x_0=x_1=a_0=a_1=0$,}
$$
DOKAZHITE, CHTO
$$
x_n=\sum_{k\ge 2}\perm{n}{k}(-1)^k{2^{k-1}\hat a_k \over 2^{k-1}-1}=
a_n+\sum_{k\ge 2}\perm{n}{k}(-1)^k{\hat a_k \over 2^{k-1}-1}.
$$

\ex[M28] oPREDELITE VSE TAKIE POSLEDOVATELXNOSTI~$\< a_n>$, 
CHTO~$\<\hat a_n>=\<a_n>$ V SMYSLE UPR.~36.

\rex[M30] nAJDITE~$A_N$, $B_N$, $C_N$, $G_N$, $K_N$, $L_N$, $R_N$, 
I~$X_N$---SREDNIE ZNACHENIYA VELICHIN~(29)---V SLUCHAE, KOGDA PORAZRYADNOJ 
SORTIROVKE PODVERGAYUTSYA "ISHODNYE DANNYE TIPA~(ii)". vYRAZITE VASHI OTVETY 
CHEREZ~$N$ I FUNKCII
$$
U_n=\sum_{k\ge 2}\perm{n}{k}{(-1)^k \over 2^{k-1}-1},\qquad
V_n=\sum_{k\ge 2}\perm{n}{k}{(-1)^k k \over 2^{k-1}-1}=n(U_n-U_{n-1}).
$$
[\emph{uKAZANIE:} SM.~UPR.~36.]

\ex[20] rEZULXTATY~(30) POKAZYVAYUT, CHTO PORAZRYADNAYA OBMENNAYA SORTIROVKA, 
PRIMENENNAYA K SLUCHAJNYM VHODNYM DANNYM, TREBUET OKOLO $1.44$~STADIJ. 
dOKAZHITE, CHTO BYSTRAYA SORTIROVKA NIKOGDA NE TREBUET BOLEE $N$~STADIJ, I 
OB®YASNITE, POCHEMU PRI OBMENNOJ PORAZRYADNOJ SORTIROVKE CHASTO 
BYVAET NEOBHODIMO BOLEE $N$~STADIJ.

\ex[21] oB®YASNITE, KAK NUZHNO IZMENITX ALGORITM~R, CHTOBY ON 
RABOTAL DOSTATOCHNO |FFEKTIVNO I TOGDA, KOGDA SORTIRUEMYE FAJLY SODERZHAT 
MNOGO RAVNYH KLYUCHEJ.

\ex[23] dAJTE TOCHNOE OPISANIE ALGORITMA "INTERVALXNOJ OBMENNOJ 
SORTIROVKI" vAN eMDENA.

\ex[m43] pROANALIZIRUJTE ALGORITM INTERVALXNOJ OBMENNOJ SORTIROVKI IZ UPR.~41.

\ex[vm21] dOKAZHITE, 
CHTO~$\int_0^1 y^{-1}(e^{-y}-1)\,dy +\int_1^\infty y^{-1}e^{-y}\,dy=-\gamma$. 
[\emph{uKAZANIE:} RASSMOTRITE~$\lim_{a\to 0+} y^{a-1}$.]

\ex[vm24] vYVEDITE FORMULU~(37), KAK |TO PREDLOZHENO V TEKSTE NASTOYASHCHEGO PUNKTA.

\ex[vm20] oB®YASNITE, POCHEMU PRI~$x>0$ SPRAVEDLIVO RAVENSTVO~(43).

\ex[vm20] kAKOVO ZNACHENIE 
VYRAZHENIYA~$(1/2\pi i) \int_{a-i\infty}^{a+i\infty}\Gamma(z) n^{s-z}\,dz/(2^{s-z}-1)$
PRI USLOVII, CHTO~$s$---CELOE POLOZHITELXNOE CHISLO I~$0<a<s$?

\ex[vm21] dOKAZHITE, CHTO~$\sum_{j\ge1} (n/2^j) e^{-n/2^j}$---OGRANICHENNAYA 
FUNKCIYA OT~$n$.

\ex[vm24] nAJDITE ASIMPTOTICHESKOE ZNACHENIE VELICHINY~$V_n$, OPREDELENNOJ 
V UPR.~38, PRI POMOSHCHI METODOV, ANALOGICHNYH TEM, KOTORYMI V 
TEKSTE NASTOYASHCHEGO PUNKTA ISSLEDOVALASX VELICHINA~$U_n$, I POLUCHITE CHLENY DO~$O(1)$.

\ex[vm24] pRODOLZHITE ASIMPTOTICHESKUYU FORMULU~(47) DLYA~$U_n$ DO CHLENOV PORYADKA~$O(n^{-1})$.

\ex[vm24] nAJDITE ASIMPTOTICHESKOE ZNACHENIE FUNKCII
$$
U_{mn}=\sum_{k\ge 2}\perm{n}{k}(-1)^k{1\over m^{k-1}-1},
$$
GDE~$m$---PROIZVOLXNOE FIKSIROVANNOE CHISLO, BOLXSHEE~1. (eTA VELICHINA 
PRI~$m$~CELOM BOLXSHEM~$2$ POTREBUETSYA PRI ISSLEDOVANII OBOBSHCHENIJ OBMENNOJ
PORAZRYADNOJ
%%168
SORTIROVKI, A TAKZHE PRI IZUCHENII ALGORITMOV POISKA V 
"BOROVOJ PAMYATI" V \S~6.3.)

\rex[vm28] pOKAZHITE, CHTO DLYA VYVODA ASIMPTOTICHESKOGO RAZLOZHENIYA~$r_k(m)$ 
MOZHNO VOSPOLXZOVATXSYA METODOM ISSLEDOVANIYA ASIMPTOTICHESKIH ZADACH PRI 
POMOSHCHI GAMMA-FUNKCIJ VMESTO FORMULY SUMMIROVANIYA eJLERA (SR.~S~(35)). eTO 
DAET NAM EDINOOBRAZNYJ SPOSOB IZUCHENIYA~$r_k(m)$ PRI VSEH~$k$, NE 
POLAGAYASX NA TAKIE "TRYUKI", KAK VVEDENIE FUNKCII~$g_{-1}(x)=(e^{-x^2}-1)/x$.

\ex[vm35] (n.~g.~DE~bREJN.) kAKOVO ASIMPTOTICHESKOE POVEDENIE SUMMY
$$
S_n=\sum_{t\ge 1} \left({2n \over n+t}\right) d(t),
$$
GDE~$d(t)$---KOLICHESTVO DELITELEJ CHISLA~$t$? (tAK, $d(1)=1$, $d(2)=d(3)=2$,
 $d(4)=3$, $d(5)=2$ I~T.~D. eTOT VOPROS VOZNIKAET V SVYAZI S ANALIZOM 
ALGORITMA PROHOZHDENIYA DEREVA; UPR.~2.3.1-11.) nAJDITE ZNACHENIE 
VELICHINY~$S_n/\perm{2n}{n}$ DO CHLENOV PORYADKA~$O(n^{-1})$.

\ex[vm42] pROANALIZIRUJTE CHISLO PROVEROK BITOV I CHISLO OBMENOV,
VYPOLNYAEMYH PRI OBMENNOJ PORAZRYADNOJ SORTIROVKE, ESLI ISHODNYMI 
DANNYMI SLUZHAT DVOICHNYE CHISLA S BESKONECHNOJ TOCHNOSTXYU IZ PROMEZHUTKA~$[0,1)$,
KAZHDYJ BIT KOTORYH NEZAVISIMO PRINIMAET ZNACHENIE~$1$ S 
VEROYATNOSTXYU~$p$. (v OSNOVNOM TEKSTE PUNKTA OBSUZHDALSYA LISHX 
SLUCHAJ~$p={1\over 2}$; PRIMENYAVSHIESYA METODY MOZHNO OBOBSHCHITX NA SLUCHAJ 
PROIZVOLXNOGO~$p$.) rASSMOTRITE OSOBO SLUCHAJ~$p=1/\phi=.61803\ldots\,$.

\ex[vm24] (s.~o.~rAJE.) pOKAZHITE, CHTO~$U_n$ MOZHNO ZAPISATX V VIDE
$$
U_n=(-1)^n {n!\over 2\pi i} \oint_C {dz \over z(z-1)\ldots(z-n)}{1\over 
2^{z-1}-1},
$$
GDE~$C$---ZAMKNUTAYA KRIVAYA, OHVATYVAYUSHCHAYA OBLASTX OKOLO TOCHEK~$2$, $3$,~\dots,
$n$. v REZULXTATE ZAMENY~$C$ NA PROIZVOLXNO BOLXSHUYU OKRUZHNOSTX S 
CENTROM V NACHALE KOORDINAT POLUCHAEM SHODYASHCHIJSYA RYAD
$$
U_n=n(H_{n-1}-1)/(\ln 2)-{1\over 2}n +2+{2\over \ln 2}\sum_{m\ge 1}\Re(B(n+1, -1+ibm)),
$$
GDE~$b=2\pi/(\ln 2)$ 
I~$B(n+1, -1+ibm)=\Gamma(n+1)\Gamma(-1+ibm)/\Gamma(n+ibm)=n!/\prod_{0\le k \le n}(k-1+ibm)$.

\rex[22] pOKAZHITE, KAK NUZHNO IZMENITX PROGRAMMU~Q, CHTOBY V KACHESTVE
RAZDELYAYUSHCHEGO |LEMENTA VYBIRALASX MEDIANA IZ TREH KLYUCHEJ~(28).

\ex[m44] pROANALIZIRUJTE V SREDNEM POVEDENIE VELICHIN, OT KOTORYH ZAVISIT 
VREMYA RABOTY PROGRAMMY~Q, ESLI PROGRAMMA IZMENENA TAK, CHTO ONA VYBIRAET 
MEDIANU IZ TREH |LEMENTOV, KAK V UPR.~55. [(sR.~UPR.~29.)]

\rex[vm24] nAJDITE ASIMPTOTICHESKOE ZNACHENIE CHISLA 
PRAVOSTORONNIH MAKSIMUMOV, VSTRECHAYUSHCHIHSYA PRI SORTIROVKE VSTAVKAMI V 
NESKOLXKO SPISKOV (FORMULA~(5.2.1-11)), ESLI~$M=N/\alpha$ PRI 
FIKSIROVANNOM~$\alpha$ I~$N\to\infty$. 
vYPOLNITE RAZLOZHENIE DO CHLENOV PORYADKA~$O(N^{-1})$ I VYRAZITE VASH OTVET 
CHEREZ INTEGRALXNUYU POKAZATELXNUYU FUNKCIYU~$E_1(z)=\int_z^\infty e^{-t}\,dt/t$.

%% 169

\bye