\input style
KOTORAYA YAVLYAETSYA RAZNOVIDNOSTXYU SORTIROVKI S VYCHISLENIEM ADRESA.) 
dOPOLNITELXNOE PROSTRANSTVO BUDET, PO-VIDIMOMU, ISPOLXZOVATXSYA NAILUCHSHIM 
OBRAZOM, ESLI OTVESTI EGO POD POLYA SVYAZI, KAK V METODE VSTAVOK V SPISOK. k 
TOMU ZHE OTPADAET NEOBHODIMOSTX VYDELYATX OTDELXNYE OBLASTI DLYA VVODA I VYVODA;
VSE OPERACII MOZHNO VYPOLNITX V ODNOJ I TOJ ZHE OBLASTI PAMYATI.

oSNOVNAYA IDEYA---TAK OBOBSHCHITX METOD VSTAVOK V SPISOK, CHTOBY RASPOLAGATX NE 
ODNIM SPISKOM, A \emph{NESKOLXKIMI.} kAZHDYJ SPISOK SODERZHIT KLYUCHI IZ 
OPREDELENNOGO DIAPAZONA. mY DELAEM VAZHNOE PREDPOLOZHENIE O TOM, CHTO KLYUCHI 
RASPREDELENY DOVOLXNO RAVNOMERNO I NE "SKAPLIVAYUTSYA" HAOTICHESKI V 
KAKIH-TO DIAPAZONAH. mNOZHESTVO VSEH VOZMOZHNYH ZNACHENIJ KLYUCHEJ RAZBIVAETSYA 
NA $M$~OTREZKOV I PREDPOLAGAETSYA, CHTO DANNYJ KLYUCH POPADAET V DANNYJ 
OTREZOK S VEROYATNOSTXYU~$1/M$. oTVODIM DOPOLNITELXNUYU PAMYATX POD GOLOVY 
$M$~SPISKOV, A KAZHDYJ SPISOK STROIM, KAK PRI PROSTYH VSTAVKAH V SPISOK.

nET NEOBHODIMOSTI PRIVODITX ZDESX |TOT ALGORITM SO VSEMI PODROBNOSTYAMI. 
dOSTATOCHNO VNACHALE USTANOVITX VSE GOLOVY SPISKOV RAVNYMI~$\NULL$, A DLYA 
KAZHDOGO VNOVX POSTUPIVSHEGO |LEMENTA PREDVARITELXNO RESHITX, V KAKOJ IZ 
$M$~OTREZKOV ON POPADAET, POSLE CHEGO VSTAVITX EGO V SOOTVETSTVUYUSHCHIJ SPISOK,
KAK V ALGORITME~L.

chTOBY PROILLYUSTRIROVATX |TOT METOD V DEJSTVII, PREDPOLOZHIM, CHTO NASHI 
16~KLYUCHEJ RAZDELENY NA $M=4$~DIAPAZONA $0$--$249$, $250$--$499$, 
$500$--$749$, $750$--$999$. v PROCESSE SORTIROVKI POLUCHAYUTSYA SLEDUYUSHCHIE 
KONFIGURACII:
\ctable{
#\hfil\bskip&&\bskip#\hfil\bskip\cr
sPISKI & pRISHLO~4     & pRISHLO~8            & pRISHLO~12                  & kONECHNOE \cr
       & |LEMENTA     & |LEMENTOV           & |LEMENTOV                  & SOSTOYANIE\cr
1:     & $061$, $087$ & $061$, $087$, $170$ & $061$, $087$, $154$, $170$ & $061$, $087$, $154$, $170$\cr
2:     &              & $275$               & $275$, $426$               & $275$, $426$ \cr
3:     & $503$, $512$ & $503$, $512$        & $503$, $509$, $512$, $653$ & $503$, $509$, $512$, $612$\cr
       &              &                     &                            & $653$, $677$, $703$ \cr
4:     &              & $897$, $908$        & $897$, $908$               & $765$, $897$, $908$\cr
}
bLAGODARYA PRIMENENIYU SVYAZANNOJ PAMYATI NE VOZNIKAET PROBLEMY RASPREDELENIYA 
PAMYATI PRI ISPOLXZOVANII SPISKOV PEREMENNOJ DLINY.

\prog M.(vSTAVKI V NESKOLXKO SPISKOV.) v |TOJ PROGRAMME DELAYUTSYA TE ZHE 
PREDPOLOZHENIYA, CHTO I V PROGRAMME~L, NO KLYUCHI DOLZHNY BYTX 
\emph{NEOTRICATELXNYMI;} TAK CHTO
$$
0\le|KEY|<(|BYTESIZE|)^3.
$$
eTOT DIAPAZON DELITSYA V PROGRAMME NA |M|~RAVNYH CHASTEJ PUTEM UMNOZHENIYA 
KAZHDOGO KLYUCHA NA PODHODYASHCHUYU KONSTANTU. gOLOVY SPISKOV HRANYATSYA V 
YACHEJKAH~$|HEAD|+1$,~\dots, $|HEAD|+|M|$.
%%125
\code
KEY   & EQU  & 1:3
LINK  & EQU  & 4:5
START & ENT2 & m            & 1
      & STZ  & HEAD,2       & M     & $|HEAD|[p]\asg\NULL$.
      & DEC2 & 1            & M
      & J2P  & *-2          & M     & $M\ge p \ge 1$.
      & ENT1 & N            & 1     & $j\asg N$.
2H    & LDA  & INPUT.l(KEY) & N
      & MUL  & =M(1:3)=     & N     & $|rA|\asg\floor{M\times K_j/|BYTESIZE|^3}$. 
      & STA  & *+1(1:2)     & N
      & ENT3 & 0            & N     & $q\asg |rA|$.
      & INC3 & HEAD+1-INPUT & N     & $q\asg |LOC|(|HEAD|[q])$.
      & LDA  & INPUT, 1     & N     & $K\asg K_j$.
      & JMP  & 4F           & N     & uSTANOVITX~$p$.
3H    & CMPA & INPUT,2(KEY) & B+N-A 
      & JLE  & 5F           & B+N-A & vSTAVITX, ESLI~$K\le K_p$.
      & ENT3 & 0,2          & B     & $q\asg p$.
4H    & LD2  & INPUT,3(LINK)& B+N   & $p\asg |LINK|(q)$.
      & J2P  & 3B           & B+N   & pEREHOD, ESLI NE KONEC SPISKA.
5n    & ST1  & INPUT,3(LINK)& N     & $|LINK|(q)\asg|LOC|(R_j)$.
      & ST2  & INPUT,1(LINK)& N     & $|LINK|(|LOC|(R_j))\asg p$.
6H    & DEC1 & 1            & N
      & J1P  & 2B           & N     & $N\ge j \ge 1$.
\endcode
\algend

eTA PROGRAMMA NAPISANA DLYA PROIZVOLXNOGO ZNACHENIYA~$M$, NO LUCHSHE 
ZAFIKSIROVATX~$M$, POLOZHIV EGO RAVNYM NEKOTOROMU UDOBNOMU ZNACHENIYU; 
MOZHNO, NAPRIMER, POLOZHITX~$M=|BYTESIZE|$, TOGDA GOLOVY SPISKOV MOZHNO 
OPUSTOSHITX ODNOJ-EDINSTVENNOJ KOMANDOJ~|MOVE|, A POSLEDOVATELXNOSTX 
KOMAND~08--11, REALIZUYUSHCHIH UMNOZHENIE, ZAMENITX KOMANDOJ~|LD3 INPUT,1(1:1)|. 
nAIBOLEE ZAMETNOE OTLICHIE PROGRAMMY~M OT PROGRAMMY~L SOSTOIT V 
TOM, CHTO V PROGRAMME~M NUZHNO RASSMATRIVATX SLUCHAJ PUSTOGO SPISKA, KOGDA NE 
NADO DELATX SRAVNENIJ.

sKOLXKO ZHE VREMENI MY |KONOMIM, IMEYA $M$~SPISKOV VMESTO ODNOGO? oBSHCHEE 
VREMYA RABOTY PROGRAMMY~M RAVNO $7B+31N-3A+4M+2$~EDINIC, GDE~$M$---CHISLO 
SPISKOV, $N$---CHISLO SORTIRUEMYH ZAPISEJ, $A$ I~$B$ RAVNY SOOTVETSTVENNO 
CHISLU PRAVOSTORONNIH MAKSIMUMOV I CHISLU INVERSIJ SREDI KLYUCHEJ, 
PRINADLEZHASHCHIH KAZHDOMU SPISKU. (pRI ANALIZE |TOGO ALGORITMA V OTLICHIE OT 
VSEH DRUGIH ANALIZOV V DANNOM PUNKTE MY SCHITAEM KRAJNIJ PRAVYJ |LEMENT 
NEPUSTOJ PERESTANOVKI PRAVOSTORONNIM MAKSIMUMOM, A NE IGNORIRUEM EGO.) mY 
UZHE IZUCHILI VELICHINY~$A$ I~$B$ PRI~$M=1$, KOGDA IH SREDNIE ZNACHENIYA RAVNY 
SOOTVETSTVENNO~$H_N$ I~${1\over2}\perm{N}{2}$. sOGLASNO PREDPOLOZHENIYU O 
RASPREDELENII KLYUCHEJ, VEROYATNOSTX TOGO, CHTO DANNYJ SPISOK V KONCE 
SORTIROVKI BUDET SODERZHATX ROVNO $n$~|LEMENTOV, ESTX "BINOMIALXNAYA" VEROYATNOSTX
$$
\perm{N}{n}\left({1\over M}\right)^n\left(1-{1\over M}\right)^{N-n}.
\eqno(10)
$$
%%126
pO|TOMU SREDNIE ZNACHENIYA VELICHIN~$A$ I~$B$ V OBSHCHEM SLUCHAEV RAVNY
$$
\eqalignno{
A_{ave}&= M\sum_n\perm{N}{n}\left({1\over M}\right)^n
\left(1-{1\over M}\right)^{N-n}H_n; & (11) \cr
B_{ave}&= M\sum_n\perm{N}{n}\left({1\over M}\right)^n
\left(1-{1\over M}\right)^{N-n}\perm{n}{2}. & (12) \cr
}
$$
pO TEOREME~1.2.7A
$$
\sum_n\perm{N}{n}(M-1)^{-n}H_n=\left(1-{1\over M}\right)^{-N}(H_N-\ln M)+\varepsilon,
\qquad 
0<\varepsilon=\sum_{n>N}{1\over n}\left(1-{1\over M}\right)^{n-N}<{M-1\over N+1};
$$
SLEDOVATELXNO,
$$
A_{ave}=M(H_N-\ln M)+\delta, 
\qquad 
0<\delta<{M^2\over N+1}\left(1-{1\over M}\right)^{N+1}.
\eqno(13)
$$
(eTA FORMULA PRAKTICHESKI BESPOLEZNA, ESLI~$M\approx N$. bOLEE PODROBNO 
ASIMPTOTICHESKOE POVEDENIE VELICHINY~$A_{ave}$ PRI~$M=N/\alpha$  OBSUZHDAETSYA 
V UPR.~5.2.2-57.) sUMMU~(12) LEGKO VYCHISLITX S POMOSHCHXYU TOZHDESTVA
$$
\perm{N}{n}\perm{n}{2}=\perm{N}{2}\perm{N-2}{n-2},
$$
KOTOROE PREDSTAVLYAET SOBOJ CHASTNYJ SLUCHAJ TOZHDESTVA~(1.2.6-20); POLUCHAEM
$$
B_{ave}={1\over 2M}\perm{N}{2}.
\eqno(14)
$$
(sTANDARTNOE OTKLONENIE DLYA VELICHINY~$B$ SM.\ V UPR.~37.) sLEDOVATELXNO, 
OBSHCHEE VREMYA RABOTY PROGRAMMY~M PRI FIKSIROVANNOM~$M$ I~$N\to\infty$ RAVNO
$$
\eqalign{
\min\qquad& 31N+M+2,\cr
\ave\qquad& 1.75N^2/M+31N-3MH_N+3M\ln M+4M-3-1.75N/M+2,\cr 
\max\qquad& 3.50N^2+24.5N+4M+2.\cr
}
\eqno(15)
$$
zAMETIM, CHTO ESLI~$M$ NE SLISHKOM VELIKO, \emph{TO SREDNEE VREMYA RABOTY 
SOKRASHCHAETSYA V $M$~RAZ.} pRI~$M=10$ SORTIROVKA BUDET PRIMERNO V 10~RAZ 
BYSTREE, CHEM PRI~$M=1$! oDNAKO MAKSIMALXNOE VREMYA RABOTY GORAZDO BOLXSHE 
SREDNEGO. tAKIM OBRAZOM, PODTVERZHDAETSYA NEOBHODIMOSTX VYPOLNENIYA 
PREDPOLOZHENIYA O RAVNOMERNOSTI RASPREDELENIYA KLYUCHEJ, TAK KAK NAIHUDSHIJ 
SLUCHAJ IMEET MESTO, KOGDA VSE KLYUCHI POPADAYUT V ODIN SPISOK.

%%127

eSLI POLOZHITX~$M=N$, TO SREDNEE VREMYA RABOTY BUDET PRIMERNO~$34.36N$, 
PRI~$M={1\over2}N$ ONO NESKOLXKO BOLXSHE, RAVNO PRIBLIZITELXNO~$34.52N$, 
A PRI~$M=N/10$ ONO RAVNO PRIBLIZITELXNO~$48.04N$. (zAMETIM, CHTO~$10N$ IZ 
|TIH EDINIC VREMENI MASHINY \MIX{} TRATYATSYA NA ODNU LISHX KOMANDU 
UMNOZHENIYA!) \emph{mY POLUCHILI METOD SORTIROVKI S VREMENEM RABOTY 
PORYADKA~$N$ PRI USLOVII, CHTO KLYUCHI DOVOLXNO RAVNOMERNO RASPREDELENY V 
OBLASTI IZMENENIYA.}

\excercises
\ex[10] yaVLYAETSYA LI ALGORITM~S ALGORITMOM "USTOJCHIVOJ" SORTIROVKI?

\ex[11] bUDET LI ALGORITM~S PRAVILXNO SORTIROVATX CHISLA, ESLI V SHAGE~S3 
OTNOSHENIE~"$K\ge K_i$" ZAMENITX NA~"$K>K_i$"?

\rex[30] yaVLYAETSYA LI PROGRAMMA~S SAMOJ KOROTKOJ PROGRAMMOJ SORTIROVKI 
DLYA MASHINY \MIX, ILI MOZHNO NAPISATX BOLEE KOROTKUYU PROGRAMMU, KOTORAYA BY 
DAVALA TOT ZHE REZULXTAT?

\rex[m20] nAJDITE MINIMALXNOE I MAKSIMALXNOE VREMYA RABOTY PROGRAMMY~S KAK 
FUNKCIYU OT~$N$.

\rex[m27] nAJDITE PROIZVODYASHCHUYU FUNKCIYU~$g_N(z)=\sum_{k\ge0} p_{Nk} z^k$ 
DLYA OBSHCHEGO VREMENI RABOTY PROGRAMMY~S, GDE~$p_{Nk}$---VEROYATNOSTX TOGO, CHTO 
NA VYPOLNENIE PROGRAMMY~S UJDET ROVNO $k$~EDINIC VREMENI PRI ZADANNOJ 
ISHODNOJ SLUCHAJNOJ PERESTANOVKE MNOZHESTVA~$\set{1, 2,~\ldots, N}$. 
vYCHISLITE TAKZHE STANDARTNOE OTKLONENIE VREMENI RABOTY DLYA DANNOGO ZNACHENIYA~$N$.

\ex[33] dLYA DVUHPUTEVYH VSTAVOK, PROILLYUSTRIROVANNYH V TABL.~2,
PO-VIDIMOMU, NEOBHODIMO, POMIMO OBLASTI VVODA, SODERZHASHCHEJ $N$~ZAPISEJ,
IMETX OBLASTX VYVODA, V KOTOROJ MOZHET HRANITXSYA $2N+1$~ZAPISEJ. pOKAZHITE,
CHTO MOZHNO VYPOLNYATX DVUHPUTEVYE VSTAVKI, IMEYA KAK DLYA VVODA, TAK I 
DLYA VYVODA PROSTRANSTVO, DOSTATOCHNOE DLYA HRANENIYA VSEGO $N+1$~ZAPISEJ.

\ex[m20] pUSTX~$a_1\,a_2\,\ldots\,a_n$---SLUCHAJNAYA PERESTANOVKA  
MNOZHESTVA~$\set{1, 2,~\ldots, n}$; KAKOVO SREDNEE ZNACHENIE 
VELICHINY~$\abs{a_1-1}+\abs{a_2-2}+\cdots+\abs{a_n-n}$? (oNO RAVNO 
PROIZVEDENIYU~$n$ NA SREDNEE CHISTOE RASSTOYANIE, NA KOTOROE PEREMESHCHAETSYA 
ZAPISX V PROCESSE SORTIROVKI.)

\ex[10] yaVLYAETSYA LYA ALGORITM~D ALGORITMOM "USTOJCHIVOJ" SORTIROVKI?

\ex[20] kAKIE ZNACHENIYA~$A$ I~$B$ I KAKOE OBSHCHEE VREMYA RABOTY 
PROGRAMMY~D SOOTVETSTVUYUT TABL.~3 I~4? pROANALIZIRUJTE DOSTOINSTVA METODA 
shELLA PO SRAVNENIYU S PROSTYMI VSTAVKAMI V |TOM SLUCHAE.

\rex[22] v SLUCHAE, KOGDA~$K_j\ge K_{j-h}$, V SHAGE~D3 ALGORITM~D 
PREDPISYVAET VYPOLNENIE MNOZHESTVA NENUZHNYH DEJSTVIJ. pOKAZHITE, KAK MOZHNO 
IZMENITX PROGRAMMU~D, CHTOBY IZBEZHATX |TIH IZBYTOCHNYH VYCHISLENIJ, I 
OBSUDITE PREIMUSHCHESTVA TAKOGO IZMENENIYA.

\ex[m10] kAKOJ PUTX NA RESHETKE (ANALOGICHNOJ PREDSTAVLENNOJ NA RIS.~11) 
SOOTVETSTVUET PERESTANOVKE $1\,2\,5\,3\,7\,4\,8\,6\,9\,11\,10\,12$?

\ex[m20] dOKAZHITE, CHTO SUMMA VERTIKALXNYH VESOV PUTI NA RESHETKE RAVNA 
CHISLU INVERSIJ SOOTVETSTVUYUSHCHEJ 2-UPORYADOCHENNOJ PERESTANOVKI.

\rex[m22] pOYASNITE, KAK NUZHNO PRIPISATX VESA \emph{GORIZONTALXNYM} 
OTREZKAM VMESTO VERTIKALXNYH, CHTOBY SUMMA GORIZONTALXNYH VESOV PUTI NA 
RESHETKE RAVNYALASX CHISLU INVERSIJ V SOOTVETSTVUYUSHCHEJ 2-UPORYADOCHENNOJ PERESTANOVKE.

\ex[m24] (a)~pOKAZHITE, CHTO DLYA SUMM, OPREDELYAEMYH RAVENSTVOM~(2),
$A_{2n+1}=2A_{2n}$. (b)~eSLI POLOZHITX~$r=-s-1$, $t=1$, TO OBSHCHEE TOZHDESTVO 
IZ UPR.~1.2.6-26 UPROSHCHAETSYA DO
$$
\sum_k\perm{2k+s}{k}z^k={1\over\sqrt{1-4z}}\left({1-\sqrt{1-4z}\over 2z}\right)^s.
$$
%%128
rASSMOTREV SUMMU~$\sum_n A_{2n} z^n$ POKAZHITE, CHTO
$$
A_{2n}=n\cdot 4^{n-1}.
$$

\rex[vm33] pUSTX~$g_n(z)$, $\bar g_n(z)$, $h(z)$, $\bar h_n(z)$ 
RAVNY~$\sum z^{\hbox{OBSHCHIJ VES PUTI}}$, GDE SUMMA BERETSYA PO VSEM PUTYAM 
DLINY~$2n$ NA RESHETKE IZ~$(0, 0)$ V~$(n, n)$, UDOVLETVORYAYUSHCHIM NEKOTORYM 
OGRANICHENIYAM NA VERSHINY, CHEREZ KOTORYE |TI PUTI PROHODYAT: DLYA~$h_n(z)$ NET 
OGRANICHENIJ, DLYA~$g_n(z)$ PUTI NE DOLZHNY PROHODITX CHEREZ VERSHINY~$(i, j)$, 
TAKIE, CHTO~$i>j$; $\bar h_n(z)$ I~$\bar g_n(z)$ OPREDELYAYUTSYA ANALOGICHNO, 
NO NE DOPUSKAYUTSYA TAKZHE I VERSHINY~$(i, i)$ PRI~$0<i < n$. tAKIM OBRAZOM,
$$
\displaylines{
g_0(z)=1, \quad g_1(z)=z, \quad g_2(z)=z^3+z^2; \quad \bar g_1(z)=z, \quad \bar g_2(z)=z^3;\cr
h_0(z)=1,\quad   h_1(z)=z+1, \quad h_2(z)=z^3+z^2+3z+1;\cr
\bar h_1(z)=z+1, \quad \bar h_2(z)=z^3+z.\cr
}
$$
nAJDITE REKURRENTNYE SOOTNOSHENIYA, OPREDELYAYUSHCHIE |TI FUNKCII, I 
VOSPOLXZUJTESX |TIMI REKURRENTNYMI SOOTNOSHENIYAMI DLYA DOKAZATELXSTVA RAVENSTVA
$$
h''_n(1)+h'_n(1)={7n^3+4n^2+4n\over 30}\perm{2n}{n}.
$$
(oTSYUDA LEGKO NAHODITSYA TOCHNAYA FORMULA DISPERSII CHISLA INVERSIJ V 
SLUCHAJNOJ 2-UPORYADOCHENNOJ PERESTANOVKE MNOZHESTVA~$\set{1, 2,~\ldots, 2n}$; 
ONA ASIMPTOTICHESKI PRIBLIZHAETSYA K~$\left({7\over 30}-{\pi\over 16}\right) n^3$.)

\ex[m24] nAJDITE FORMULU MAKSIMALXNOGO CHISLA INVERSIJ V $h$-UPORYADOCHENNOJ 
PERESTANOVKE MNOZHESTVA~$\set{1, 2,~\ldots, n}$. kAKOVO MAKSIMALXNO 
VOZMOZHNOE CHISLO PEREMESHCHENIJ, VYPOLNYAEMYH ALGORITMOM~D, ESLI SHAGI 
SORTIROVKI UDOVLETVORYAYUT USLOVIYU DELIMOSTI~(5)?

\ex[M21] pOKAZHITE, CHTO ESLI~$N=2^t$ I~$h_s=2^{s-1}$ PRI~$t\ge s\ge 1$, 
TO SUSHCHESTVUET EDINSTVENNAYA PERESTANOVKA MNOZHESTVA~$\set{1, 2,~\ldots, N}$, 
MAKSIMIZIRUYUSHCHAYA CHISLO PEREMESHCHENIJ, VYPOLNYAEMYH ALGORITMOM~D. nAJDITE 
PROSTOJ SPOSOB OPISANIYA |TOJ PERESTANOVKI.

\ex[vm24] pRI BOLXSHIH ZNACHENIYAH~$N$ SUMMU~(6) MOZHNO OCENITX VELICHINOJ
$$
{1\over 4}{N^2\over h_t}+{\sqrt{\pi}\over 8}
\left({N^{3/2}h_t^{1/2}\over h_{t-1}}+\cdots+{N^{3/2}h_2^{1/2}\over h_1}\right).
$$
kAKOVY DEJSTVITELXNYE CHISLA~$h_t$,~\dots, $h_1$, MINIMIZIRUYUSHCHIE |TO 
VYRAZHENIE, ESLI~$N$ I~$t$ FIKSIROVANY, a~$h_1=1$?

\rex[m25] kAKOVO SREDNEE ZNACHENIE VELICHINY~$A$ V ANALIZE VREMENI RABOTY
PROGRAMMY~D, ESLI SHAGI SORTIROVKI UDOVLETVORYAYUT USLOVIYU DELIMOSTI~(5)?

\ex[m20] pOKAZHITE, CHTO TEOREMA~K SLEDUET IZ LEMMY~L.

\ex[m25] pUSTX~$h$ I~$k$---VZAIMNO PROSTYE CELYE POLOZHITELXNYE 
CHISLA. pOKAZHITE, CHTO NAIBOLXSHEE CELOE CHISLO, KOTOROE NELXZYA PREDSTAVITX V 
VIDE~$ah+bk$, GDE~$a$ I~$b$---\emph{NEOTRICATELXNYE} CELYE CHISLA, 
RAVNO~$hk-h-k$. sLEDOVATELXNO, ESLI FAJL YAVLYAETSYA ODNOVREMENNO 
$h$-UPORYADOCHENNYM I~$k$-UPORYADOCHENNYM, TO~$K_i\le K_j$ PRI~$j-i\ge(h-1)(k-1)$.

\ex[M30] dOKAZHITE, CHTO LYUBOE CELOE CHISLO~$\ge 2^h(2^h-1)$ MOZHNO 
PREDSTAVITX V VIDE~$a_0(2^h-1)+a_1(2^{h+1}-1)+a_2(2^{h+2}-1)+\ldots$, 
GDE~$a_j$---NEOTRICATELXNYE CELYE CHISLA; NO CHISLO~$2^h(2^h-1)-1$ NELXZYA 
PREDSTAVITX V TAKOM VIDE. bOLEE TOGO, SUSHCHESTVUET ROVNO $2^{h-1}(2^h+h-3)$ 
CELYH POLOZHITELXNYH CHISEL, KOTORYE NELXZYA PREDSTAVITX V TAKOM VIDE.

nAJDITE ANALOGICHNYE FORMULY DLYA SLUCHAYA, KOGDA V |TOM 
PREDSTAVLENII VYRAZHENIE~$2^k-1$ ZAMENENO NA~$2^k+1$.

\rex[m22] dOKAZHITE, CHTO ESLI~$h_{s+2}$ I~$h_{s+1}$ VZAIMNO PROSTY, TO 
CHISLO PEREMESHCHENIJ, VYPOLNYAEMYH ALGORITMOM~D PRI PROSMOTRE S SHAGOM~$h_s$, 
ESTX~$O(Nh_{s+2}h_{s+1}/h_s)$. (\emph{uKAZANIE:} SM.~UPR.~21.)
%% 129

\ex[m42] dOKAZHITE, CHTO TEOREMA~P---NAILUCHSHAYA IZ VOZMOZHNYH TEOREM V TOM 
SMYSLE, CHTO POKAZATELX~$3/2$ NELXZYA UMENXSHITX.

\rex[M22] sKOLXKO SUSHCHESTVUET PERESTANOVOK MNOZHESTVA~$\set{1, 2,~\ldots, n}$, 
YAVLYAYUSHCHIHSYA ODNOVREMENNO 3-UPORYADOCHENNYMI I 2-UPORYADOCHENNYMI? 
kAKOVO MAKSIMALXNOE CHISLO INVERSIJ V TAKOJ PERESTANOVKE? chEMU RAVNO 
SUMMARNOE CHISLO INVERSIJ VO VSEH TAKIH PERESTANOVKAH?

\ex[m35] mOZHET LI 3-, 5- I 7-UPORYADOCHENNYJ FAJL IZ $N$~|LEMENTOV SODERZHATX 
BOLEE $N$~INVERSIJ?

\ex[m50] pREDLOZHITE |FFEKTIVNYJ ALGORITM POSTROENIYA PERESTANOVOK, KOTORYE 
TREBUYUT MAKSIMALXNOGO CHISLA OPERACIJ PEREMESHCHENIYA V ALGORITME~D PRI 
ZADANNYH~$N$, $h_t$, $h_{t-1}$,~\dots, $h_1$.

\ex[15] kAKAYA IZ POSLEDOVATELXNOSTEJ SHAGOV, UKAZANNYH V TABL.~6, NAILUCHSHAYA 
DLYA PROGRAMMY~D S TOCHKI ZRENIYA SUMMARNOGO VREMENI RABOTY?

\ex[m42] nAJDITE DLYA~$N=1000$ I RAZLICHNYH ZNACHENIJ~$t$ 
|MPIRICHESKIE ZNACHENIYA~$h_t$,~\dots, $h_1$, KOTORYE, BYTX MOZHET, 
MINIMIZIRUYUT SREDNEE CHISLO OPERACIJ PEREMESHCHENIYA V ALGORITME~D V TOM 
SMYSLE, CHTO ESLI IZMENITX ODNU IZ VELICHIN~$h$, NE MENYAYA OSTALXNYH, TO 
SREDNEE CHISLO PEREMESHCHENIJ VOZRASTET.

\ex[m23] (v.~pRATT.) pOKAZHITE, CHTO ESLI MNOZHESTVO SHAGOV 
ESTX~$\set{2^p3^q \mid 2^p3^q<N}$, TO CHISLO PROSMOTROV RAVNO 
PRIMERNO~${1\over2}(\log_2 N)(\log_3 N)$ I NA KAZHDYJ PROSMOTR PRIHODITSYA 
NE BOLEE $N/2$~OPERACIJ PEREMESHCHENIYA. v DEJSTVITELXNOSTI PRI LYUBOM 
PROSMOTRE, ESLI~$K_{j-h}>K_j$, TO VSEGDA~$K_{j-3h}$, 
$K_{j-2h}>\le K_j<K_{j-h}\le K_{j+h}$, $K_{j+2h}$, TAK CHTO MOZHNO PROSTO 
POMENYATX MESTAMI~$K_{j-h}$ I~$K_j$ I UVELICHITX~$j$ NA~$2h$, S|KONOMIV V 
ALGORITME~D 2~SRAVNENIYA. (\emph{uKAZANIE:} cM.~UPR.~25.)

\rex[25] nAPISHITE \MIX-PROGRAMMU DLYA ALGORITMA SORTIROVKI, PREDLOZHENNOGO 
v.~pRATTOM (UPR.~30). vYRAZITE EE VREMYA RABOTY CHEREZ VELICHINY~$A$, $B$, 
$S$, $T$, $N$, ANALOGICHNYE SOOTVETSTVUYUSHCHIM VELICHINAM V PROGRAMME~D.

\ex[10] kAKOVO BUDET OKONCHATELXNOE SODERZHIMOE 
SVYAZEJ~$L_0L_1\ldots{}L_{16}$, ESLI PROVESTI DO KONCA SORTIROVKU SPISKA 
VSTAVKAMI V TABL.~8?

\rex[25] nAJDITE SPOSOB USOVERSHENSTVOVATX PROGRAMMU~L, CHTOBY EE 
VREMYA RABOTY OPREDELYALOSX VELICHINOJ~$5B$, A NE~$7B$, GDE~$B$---CHISLO INVERSIJ.

\ex[m10] pROVERXTE FORMULU~(10).

\ex[18] pREDPOLOZHIM, CHTO RAZMER BAJTA MASHINY~\MIX{} RAVEN~100 I 
SHESTNADCATX KLYUCHEJ V TABL.~8 RAVNY NA SAMOM DELE~$503\,000$, $087\,000$, 
$512\,000$,~\dots, $703\,000$. oPREDELITE VREMYA RABOTY PROGRAMM~M I~L S 
|TIMI DANNYMI PRI~$M=4$.

\ex[vm16] eSLI PROGRAMMA VYPOLNYAETSYA PRIBLIZITELXNO ZA $A/M+B$~EDINIC 
VREMENI I ISPOLXZUET $C+M$~YACHEEK PAMYATI, TO PRI KAKOM 
VYBORE~$M$ DOSTIGAETSYA OPTIMALXNOE ZNACHENIE PROIZVEDENIYA PROSTRANSTVA NA VREMYA?

\ex[m25] pUSTX~$g_n(z)$---PROIZVODYASHCHAYA FUNKCIYA DLYA CHISLA INVERSIJ V 
SLUCHAJNOJ PERESTANOVKE $n$~|LEMENTOV (SR.\ S FORMULOJ~(5.1.1-11)). 
pUSTX~$g_{NM}(z)$---SOOTVETSTVUYUSHCHAYA PROIZVODYASHCHAYA FUNKCIYA DLYA VELICHINY~$B$ V 
PROGRAMME~$M$. pOKAZHITE, CHTO
$$
\sum_{N\ge0} g_{NM}(z) M^N w^N/N!=\left(\sum_{n\ge0} g_n(z)w^n/n!\right)^M,
$$
I VOSPOLXZUJTESX |TOJ FORMULOJ DLYA VYVODA DISPERSII VELICHINY~$B$.

\ex[vm23] (r.~m.~kARP.) pUSTX~$F(x)$---NEKOTORAYA FUNKCIYA 
RASPREDELENIYA VEROYATNOSTEJ, PRICHEM~$F(0)=0$ I~$F(1)=1$. dOKAZHITE, CHTO ESLI 
KLYUCHI~$K_1$, $K_2$,~\dots, $K_N$ NEZAVISIMO VYBIRAYUTSYA SLUCHAJNYM OBRAZOM 
IZ |TOGO RASPREDELENIYA I~$M=cN$, GDE~$c$---KONSTANTA, A~$N\to\infty$, TO 
VREMYA RABOTY PROGRAMMY~M ESTX~$O(N)$, ESLI TOLXKO~$F$---DOSTATOCHNO GLADKAYA 
FUNKCIYA. (kLYUCH~$K$ VSTAVLYAETSYA V SPISOK~$j$, ESLI~$\floor{MK}=j-1$; |TO 
SLUCHAETSYA S VEROYATNOSTXYU~$F(j/M)-F((j-1)/M)$. v TEKSTE RASSMATRIVALSYA LISHX 
SLUCHAJ~$F(x)=x$, $0\le x \le 1$.)

%%130
\bye