\input style
\chapno=5\subchno=3\chapnotrue
\def\tape#1{{\hbox{\sl lENTA~#1\/}}\quad}
\subchap {vneshnyaya sortirovka} %5.4
pRISHLO VREMYA ZANYATXSYA INTERESNYMI ZADACHAMI, VOZNIKAYUSHCHIMI V TOM SLUCHAE,
KOGDA CHISLO SORTIRUEMYH ZAPISEJ PREVYSHAET OB®EM BYSTRODEJSTVUYUSHCHEGO
OPERATIVNOGO ZAPOMINAYUSHCHEGO USTROJSTVA. vNESHNYAYA SORTIROVKA V KORNE OTLICHNA
OT VNUTRENNEJ (HOTYA V OBOIH SLUCHAYAH NEOBHODIMO RASPOLOZHITX ZAPISI
DANNOGO FAJLA V NEUBYVAYUSHCHEM PORYADKE), I OB®YASNYAETSYA |TO TEM, CHTO VREMYA
DOSTUPA K FAJLAM NA VNESHNIH NOSITELYAH NAS ZHESTOCHAJSHIM OBRAZOM LIMITIRUET.
sTRUKTURA DANNYH DOLZHNA BYTX TAKOJ, CHTOBY SRAVNITELXNO MEDLENNYE
PERIFERIJNYE ZAPOMINAYUSHCHIE USTROJSTVA (LENTY, DISKI, BARABANY I T.~D.)
MOGLI SPRAVITXSYA S POTREBNOSTYAMI ALGORITMA SORTIROVKI. pO|TOMU
BOLXSHINSTVO IZUCHENNYH DO SIH POR METODOV VNUTRENNEJ SORTIROVKI (VSTAVKA,
 OBMEN, VYBOR) FAKTICHESKI BESPOLEZNO DLYA VNESHNEJ SORTIROVKI;
NEOBHODIMO RASSMOTRETX VSYU PROBLEMU ZANOVO.

pREDPOLOZHIM, NAPRIMER, CHTO PREDNAZNACHENNYJ DLYA SORTIROVKI FAJL SOSTOIT
IZ 5000~ZAPISEJ $R_1$ $R_2$~\dots{} $R_{5000}$ DLINOJ PO 20~SLOV (HOTYA
KLYUCHI~$K_i$ NE OBYAZATELXNO TAKOJ DLINY). kAK BYTX, ESLI VO VNUTRENNEJ
PAMYATI DANNOJ MASHINY POMESHCHAETSYA ODNOVREMENNO TOLXKO~1000 IZ |TIH ZAPISEJ?

sRAZU NAPRASHIVAETSYA TAKOE RESHENIE: NACHATX S SORTIROVKI KAZHDOGO IZ PYATI
PODFAJLOV~$R_1$~\dots{} $R_{1000}$, $R_{1001}$~\dots{} $R_{2000}$,~\dots,
$R_{4001}$~\dots{} $R_{5000}$ PO OTDELXNOSTI I ZATEM SLITX POLUCHENNYE
PODFAJLY. k SCHASTXYU, SLIYANIE OPERIRUET TOLXKO OCHENX PROSTYMI STRUKTURAMI
DANNYH, IMENNO LINEJNYMI SPISKAMI, PROJTI KOTORYE MOZHNO POSLEDOVATELXNYM
OBRAZOM, KAK STEKI ILI OCHEREDI. pO|TOMU DLYA SLIYANIYA GODYATSYA SAMYE DESHEVYE
VNESHNIE ZAPOMINAYUSHCHIE USTROJSTVA.

tOLXKO CHTO OPISANNYJ PROCESS---VNUTRENNYAYA SORTIROVKA S POSLEDUYUSHCHIM
"VNESHNIM SLIYANIEM"---VESXMA POPULYAREN, I NASHE IZUCHENIE VNESHNEJ SORTIROVKI
SVEDETSYA V OSNOVNOM K VARIACIYAM NA |TU TEMU.

vOZRASTAYUSHCHIE POSLEDOVATELXNOSTI ZAPISEJ, POLUCHAEMYE NA NACHALXNOJ FAZE
VNUTRENNEJ SORTIROVKI, V LITERATURE O SORTIROVKE CHASTO NAZYVAYUTSYA
\emph{CEPOCHKAMI;} |TA TERMINOLOGIYA DOVOLXNO SHIROKO RASPROSTRANENA, NO, K
SOZHALENIYU, ONA PROTIVORECHIT ESHCHE BOLEE RASPROSTRANENNOMU ISPOLXZOVANIYU
TERMINA "CEPOCHKA" V DRUGIH RAZDELAH VYCHISLITELXNOJ NAUKI, GDE ON OZNACHAET
\emph{PROIZVOLXNUYU} POSLEDOVATELXNOSTX SIMVOLOV. pRI IZUCHENII PERESTA-
%%296
NOVOK UZHE BYLO DANO VPOLNE PODHODYASHCHEE NAZVANIE DLYA UPORYADOCHENNYH
SEGMENTOV FAJLA, KOTORYE MY DOGOVORILISX NAZYVATX VOZRASTAYUSHCHIMI OTREZKAMI
ILI PROSTO \emph{OTREZKAMI.} v SOOTVETSTVII S |TIM BUDEM ISPOLXZOVATX
SLOVO "OTREZKI" DLYA OBOZNACHENIYA UPORYADOCHENNYH CHASTEJ FAJLA. tAKIM OBRAZOM,
ISPOLXZOVANIE PONYATIJ "CEPOCHKI OTREZKOV" I "OTREZKI CEPOCHEK" NE
PRIVEDET NI K KAKIM NEDORAZUMENIYAM.

rASSMOTRIM SNACHALA PROCESS VNESHNEJ SORTIROVKI, ISPOLXZUYUSHCHEJ V KACHESTVE
VSPOMOGATELXNOJ PAMYATI \emph{MAGNITNYE LENTY.} vEROYATNO, PROSTEJSHIM I
NAIBOLEE PRIVLEKATELXNYM SPOSOBOM SLIYANIYA S PRIMENENIEM LENT SLUZHIT
SBALANSIROVANNOE DVUHPUTEVOE SLIYANIE, V OSNOVE KOTOROGO LEZHIT IDEYA,
ISPOLXZOVAVSHAYASYA RANEE V ALGORITMAH~5.2.4N, S I~L. v PROCESSE SLIYANIYA
NAM POTREBUYUTSYA CHETYRE "RABOCHIE LENTY". nA PROTYAZHENII PERVOJ FAZY
VOZRASTAYUSHCHIE OTREZKI, POLUCHAEMYE PRI VNUTRENNEJ SORTIROVKE, POMESHCHAYUTSYA
POOCHEREDNO NA LENTY~1 I~2 DO TEH POR, POKA NE ISCHERPAYUTSYA ISHODNYE DANNYE.
zATEM LENTY~1 I~2 PEREMATYVAEM K NACHALU I SLIVAEM OTREZKI, NAHODYASHCHIESYA
NA |TIH LENTAH, POLUCHAYA NOVYE OTREZKI, VDVOE DLINNEE ISHODNYH. eTI NOVYE
OTREZKI ZAPISYVAYUTSYA PO MERE IH FORMIROVANIYA POPEREMENNO NA LENTY~3 I~4.
(eSLI NA LENTE~1 NA ODIN OTREZOK BOLXSHE, CHEM NA LENTE~2, TO PREDPOLAGAETSYA,
 CHTO LENTA~2 SODERZHIT DOPOLNITELXNYJ "FIKTIVNYJ" OTREZOK DLINY~0.) zATEM
VSE LENTY PEREMATYVAYUTSYA K NACHALU I SODERZHIMOE LENT~3 I~4 SLIVAETSYA V
UDVOENNYE PO DLINE OTREZKI, ZAPISYVAEMYE POOCHEREDNO NA LENTY~1 I~2.
pROCESS PRODOLZHAETSYA (PRI |TOM DLINA OTREZKOV KAZHDYJ RAZ UDVAIVAETSYA) DO
TEH POR, POKA NE OSTANETSYA ODIN OTREZOK (A IMENNO VESX UPORYADOCHENNYJ FAJL).
 eSLI POSLE VNUTRENNEJ SORTIROVKI BYLO POLUCHENO $S$~OTREZKOV,
PRICHEM~$2^{k-1}<S\le 2^k$, TO PROCEDURA SBALANSIROVANNOGO
DVUHPUTEVOGO SLIYANIYA PROIZVEDET ROVNO $k=\ceil{\log_2 S}$~PROHODOV PO VSEM
DANNYM.

nAPRIMER, V RASSMOTRENNOJ VYSHE SITUACII, KOGDA TREBUETSYA UPORYADOCHITX
5000~ZAPISEJ, A OB®EM VNUTRENNEJ PAMYATI SOSTAVLYAET 1000~ZAPISEJ, MY
IMEEM~$S=5$. nACHALXNAYA RASPREDELITELXNAYA FAZA PROCESSA SORTIROVKI
POMESTIT PYATX OTREZKOV NA LENTY SLEDUYUSHCHIM OBRAZOM:
$$
\eqalign{
\tape1 & R_1\ldots R_{1000}; R_{2001}\ldots R_{3000}; R_{4001}\ldots
R_{5000}. \cr
\tape2 & R_{1001}\ldots R_{2000};  R_{3001}\ldots R_{4000}.\cr
\tape3 & \hbox{(PUSTAYA)}\cr
\tape4 & \hbox{(PUSTAYA)}\cr
}
\eqno(1)
$$

pOSLE PERVOGO PROHODA SLIYANIYA NA LENTAH~3 I~4 POLUCHATSYA BOLEE DLINNYE
OTREZKI, CHEM NA LENTAH~1 I~2:
%%297
$$
\eqalign{
\tape3 & R_1 \ldots R_{2000}; R_{4001}\ldots R_{5000}.\cr
\tape4 & R_{2001} \ldots R_{4000}.\cr
}
\eqno(2)
$$

v KONEC LENTY~2 NEYAVNO DOBAVLYAETSYA FIKTIVNYJ OTREZOK, TAK CHTO
OTREZOK~$R_{4001}\ldots{}R_{5000}$ PROSTO KOPIRUETSYA NA LENTU~3. pOSLE
PEREMOTKI VSEH LENT K NACHALU SLEDUYUSHCHIJ PROHOD PO DANNYM PRIVEDET K TAKOMU
REZULXTATU:
$$
\eqalign{
\tape1& R_1 \ldots R_{4000}.\cr
\tape2& R_{4001}\ldots R_{5000}.\cr
}
\eqno(3)
$$
(oTREZOK~$R_{4001}\ldots{}R_{5000}$ SNOVA KOPIRUETSYA, NO ESLI BY MY NACHALI
S 8000~ZAPISEJ, TO V |TOT MOMENT LENTA~2 SODERZHALA
BY~$R_{4001}\ldots{}R_{8000}$.) nAKONEC, POSLE ESHCHE ODNOJ PEREMOTKI NA
LENTE~3 OKAZHETSYA OTREZOK~$R_1\ldots{}R_{5000}$, I SORTIROVKA ZAKONCHITSYA.

sBALANSIROVANNOE SLIYANIE LEGKO OBOBSHCHAETSYA NA SLUCHAJ~$T$ LENT DLYA
LYUBOGO~$T\ge3$. vYBEREM PROIZVOLXNOE CHISLO~$P$, TAKOE, CHTO~$1\le P < T$, I
RAZDELIM $T$~LENT NA DVA "BANKA": $P$~LENT V LEVOM BANKE I $T-P$~LENT V
PRAVOM BANKE. rASPREDELIM ISHODNYE OTREZKI KAK MOZHNO RAVNOMERNEE PO
$P$~LENTAM LEVOGO "BANKA", ZATEM VYPOLNIM $P\hbox{-PUTEVOE}$ SLIYANIE SLEVA
NAPRAVO, POSLE |TOGO---$(T-P)\hbox{-PUTEVOE}$~SLIYANIE SPRAVA NALEVO I~T.~D.,
 POKA SORTIROVKA NE ZAVERSHITSYA. oBYCHNO ZNACHENIE~$P$ LUCHSHE VSEGO VYBIRATX
RAVNYM~$\ceil{T/2}$ (SM.~UPR.~3, 4).

pRI~$T=4$, $P=2$ IMEEM CHASTNYJ SLUCHAJ---SBALANSIROVANNOE DVUHPUTEVOE SLIYANIE.
 vNOVX RASSMOTRIM PREDYDUSHCHIJ PRIMER, ISPOLXZUYA BOLXSHEE KOLICHESTVO LENT;
POLOZHIM~$T=6$ I~$P=3$. nACHALXNOE RASPREDELENIE TEPERX BUDET TAKIM:
$$
\eqalign{
\tape1 & R_1\ldots R_{1000}; R_{3001}\ldots R_{4000}.\cr
\tape2 & R_{1001} \ldots R_{2000}; R_{4001}\ldots R_{5000}.\cr
\tape3 & R_{2001} \ldots R_{3000}.\cr
}
\eqno(4)
$$
pERVYJ PROHOD SLIYANIYA PRIVEDET K
$$
\eqalign{
\tape4 & R_1 \ldots R_{3000}.\cr
\tape5 & R_{3001}\ldots R_{5000}.\cr
\tape6 & \hbox{(PUSTAYA)}\cr
}
\eqno(5)
$$
(pREDPOLAGAETSYA, CHTO NA LENTE~3 POMESHCHEN FIKTIVNYJ OTREZOK.) nA VTOROM
PROHODE SLIYANIYA RABOTA ZAVERSHAETSYA I
OTREZKI~$R_1\ldots R_{5000}$ POMESHCHAYUTSYA NA LENTU~1. eTOT CHASTNYJ
SLUCHAJ~$T=6$ |KVIVALENTEN~$T=5$, TAK KAK SHESTAYA LENTA ISPOLXZUETSYA LISHX
PRI~$S\ge7$.
%%298

tREHPUTEVOE SLIYANIE ZATRACHIVAET FAKTICHESKI NESKOLXKO BOLXSHE VREMENI
CENTRALXNOGO PROCESSORA, CHEM DVUHPUTEVOE, NO ONO OBYCHNO PRENEBREZHIMO MALO
PO SRAVNENIYU S VREMENEM, NEOBHODIMYM DLYA CHTENIYA, ZAPISI I PEREMOTKI
LENTY; MY DOVOLXNO HOROSHO OCENIM VREMYA VYPOLNENIYA SORTIROVKI, ESLI PRIMEM
VO VNIMANIE TOLXKO SUMMARNUYU VELICHINU PEREMESHCHENIJ LENT. v PREDYDUSHCHEM
PRIMERE ((4) I~(5)) TREBUYUTSYA TOLXKO DVA PROHODA PO DANNYM V SRAVNENII S
TREMYA PROHODAMI PRI~$T=4$. tAKIM OBRAZOM, SLIYANIE PRI~$T=6$ ZAJMET OKOLO
DVUH TRETEJ VREMENI PO OTNOSHENIYU K PREDYDUSHCHEMU SLUCHAYU.

sBALANSIROVANNOE SLIYANIE KAZHETSYA OCHENX PROSTYM I ESTESTVENNYM. nO ESLI
PRIGLYADETXSYA VNIMATELXNEE, TO SRAZU VIDNO, CHTO |TO NE NAILUCHSHIJ SPOSOB V
RAZOBRANNYH VYSHE CHASTNYH SLUCHAYAH. vMESTO TOGO CHTOBY PEREHODITX OT~(1)
K~(2) I PEREMATYVATX VSE LENTY, NAM SLEDOVALO OSTANOVITX PERVOE SLIYANIE,
 KOGDA LENTY~3 I~4 SODERZHALI SOOTVETSTVENNO~$R_1$~\dots $R_{2000}$ I
 $R_{2001}$~\dots $R_{4000}$, A LENTA~1 BYLA GOTOVA K
SCHITYVANIYU~$R_{4001}$~\dots $R_{5000}$. zATEM LENTY~2, 3, 4 MOGLI BYTX
PEREMOTANY K NACHALU, I SORTIROVKA ZAVERSHILASX BY TREHPUTEVYM SLIYANIEM NA
LENTU~2. oBSHCHEE CHISLO ZAPISEJ, PROCHITANNYH S LENTY V HODE |TOJ PROCEDURY,
 SOSTAVILO BY~$4000+5000=9000$ PROTIV~$5000+5000+5000=15000$ V
SBALANSIROVANNOJ SHEME. sOOBRAZITELXNAYA MASHINA MOGLA BY POSTICHX I |TO!

iMEYA PYATX OTREZKOV I CHETYRE LENTY, MOZHNO POSTUPITX ESHCHE LUCHSHE, RASPREDELIV
OTREZKI SLEDUYUSHCHIM OBRAZOM:
$$
\eqalign{
\tape1 & R_1 \ldots R_{1000}; R_{3001} \ldots  R_{4000}.\cr
\tape2 & R_{1001} \ldots R_{2000};  R_{4001} \ldots R_{5000}.\cr
\tape3 & R_{2001} \ldots R_{3000}.\cr
\tape4 & \hbox{(PUSTAYA)}.\cr
}
$$

tEPERX, VYPOLNIV TREHPUTEVOE SLIYANIE NA LENTU~4, ZATEM PEREMOTKU LENT~3
I~4 S POSLEDUYUSHCHIM TREHPUTEVYM SLIYANIEM NA LENTU~3, MOZHNO BYLO BY ZAVERSHITX
SORTIROVKU, PROCHITAV VSEGO $3000+5000=8000$~ZAPISEJ.

nAKONEC, ESLI BY MY IMELI SHESTX LENT, TO MOGLI BY, KONECHNO, ZAPISATX
ISHODNYE OTREZKI NA LENTY~1--5 I ZAKONCHITX SORTIROVKU ZA ODIN PROHOD,
VYPOLNIV PYATIPUTEVOE SLIYANIE NA LENTU~6. rASSMOTRENIE |TIH SLUCHAEV
POKAZYVAET, CHTO PROSTOE SBALANSIROVANNOE SLIYANIE NE YAVLYAETSYA NAILUCHSHIM, I
BYLO BY INTERESNO POISKATX ULUCHSHENNYE SHEMY SLIYANIYA.

v POSLEDUYUSHCHIH PUNKTAH |TOJ GLAVY VNESHNYAYA SORTIROVKA ISSLEDUETSYA BOLEE
GLUBOKO. v P.~5.4.1 RASSMATRIVAETSYA FAZA VNUTRENNEJ SORTIROVKI,
POROZHDAYUSHCHAYA NACHALXNYE OTREZKI; OSOBYJ INTERES PREDSTAVLYAET TEHNIKA "VYBORA
S ZAMESHCHENIEM", KOTORAYA ISPOLXZUET PORYADOK, PRISUTSTVUYUSHCHIJ V BOLXSHINSTVE
DANNYH,
%%299
CHTOBY PORODITX DLINNYE OTREZKI, ZNACHITELXNO PREVOSHODYASHCHIE EMKOSTX
VNUTRENNEJ PAMYATI. v P.~5.4.1 OBSUZHDAYUTSYA TAKZHE, STRUKTURY DANNYH, UDOBNYE
DLYA CELEJ MNOGOPUTEVOGO SLIYANIYA.

vAZHNEJSHIE SHEMY SLIYANIYA OBSUZHDAYUTSYA V P.~5.4.2---5.4.5. pOKA MY NE VSTUPIM V
EDINOBORSTVO S GRUBOJ DEJSTVITELXNOSTXYU NASTOYASHCHIH LENT I REALXNYH
SORTIRUEMYH DANNYH, DLYA NAS LUCHSHE, IZUCHAYA HARAKTERISTIKI |TIH SHEM, IMETX
VESXMA NAIVNOE PREDSTAVLENIE O LENTOCHNOJ SORTIROVKE. nAPRIMER, MOZHNO S
LEGKOJ DUSHOJ POLAGATX (KAK MY DELALI DO SIH POR), CHTO PERVONACHALXNYE
ISHODNYE ZAPISI POYAVLYAYUTSYA VOLSHEBNYM OBRAZOM V TECHENIE PERVOJ
RASPREDELITELXNOJ FAZY; NA SAMOM DELE ONI VEROYATNO, BUDUT ZANIMATX ODNU
IZ NASHIH LENT I, BYTX MOZHET, DAZHE CELIKOM ZAPOLNYAT NESKOLXKO BOBIN, TAK
KAK LENTA NE BESKONECHNA! lUCHSHE VSEGO PRENEBRECHX PODOBNYMI TEHNICHESKIMI
DETALYAMI DO TEH POR, POKA NE BUDET DOSTIGNUTO "AKADEMICHESKOE"
PONIMANIE KLASSICHESKIH SHEM SLIYANIYA. zATEM V P.~5.4.6 MY "VERNEMSYA
NA ZEMLYU", RASSMOTREV PRAKTICHESKIE OGRANICHENIYA, KOTORYE SILXNO  VLIYAYUT NA
VYBOR SHEMY SLIYANIYA. v P.~5.4.6 SRAVNIVAYUTSYA OSNOVNYE SHEMY SLIYANIYA IZ
P.~5.4.2---5.4.5 S ISPOLXZOVANIEM MNOZHESTVA RAZNOOBRAZNYH PREDPOLOZHENIJ,
KOTORYE VSTRECHAYUTSYA NA PRAKTIKE.

iNYE PODHODY K PROBLEME VNESHNEJ SORTIROVKI, NE OSNOVANNYE NA SLIYANII,
OBSUZHDAYUTSYA V P.~5.4.7 I~5.4.8. nASH OBZOR VNESHNEJ SORTIROVKI ZAKANCHIVAETSYA
V P.~5.4.9, GDE RASSMATRIVAETSYA VAZHNAYA PROBLEMA SORTIROVKI NA TAKOJ
PAMYATI, KAK DISKI I BARABANY.

\excercises
\ex[15] v TEKSTE VNESHNYAYA SORTIROVKA RASSMATRIVAETSYA POSLE
VNUTRENNEJ. pOCHEMU NELXZYA VOOBSHCHE POKONCHITX S FAZOJ VNUTRENNEJ SORTIROVKI,
PROSTO SLIVAYA ZAPISI VO VSE BOLEE I BOLEE DLINNYE OTREZKI PRYAMO S SAMOGO
NACHALA?

\ex[10] kAKIM BUDET SODERZHIMOE LENT (ANALOGICHNOE~(1)--(3)), ESLI
ZAPISI~$R_1$~\dots{} $R_{5000}$ SORTIRUYUTSYA S POMOSHCHXYU 3-LENTOCHNOGO
SBALANSIROVANNOGO METODA. PRI~$P=2$? sRAVNITE |TOT SLUCHAJ SO SLIYANIEM NA
4~LENTAH; SKOLXKO PROHODOV PO VSEM DANNYM BUDET SDELANO POSLE
PERVONACHALXNOGO RASPREDELENIYA OTREZKOV?

\ex[20] pOKAZHITE, CHTO SBALANSIROVANNOE $(P, T-P)\hbox{-PUTEVOE}$ SLIYANIE,
PRIMENENNOE K $S$~NACHALXNYM OTREZKAM, PROIZVODIT $2k$~PROHODOV,
ESLI~$P^k(T-P)^{k-1}<S\le  P^k(T-P)^k$,   I  PROIZVODIT  $2k+l$~ PROHODOV,
ESLI~$P^k(T-P)^k< S\le P^{k+1}(T-P)^k$.

dAJTE PROSTYE FORMULY DLYA VYCHISLENIYA (a)~TOCHNOGO CHISLA PROHODOV
KAK FUNKCII OT~$S$ PRI~$T=2P$, (b)~PRIBLIZHENNOGO CHISLA PROHODOV
PRI~$S\to\infty$ DLYA LYUBYH~$P$ I~$T$.

\ex[BM15] pRI KAKOM ZNACHENII~$P$, $1\le P < T$, ZNACHENIE~$P(T-P)$ MAKSIMALXNO?

%%300
\subsubchap{mNOGOPUTEVOE SLIYANIE I VYBOR S ZAMESHCHENIEM} % 5.4.1

v~P.~5.2.4 MY IZUCHALI METODY VNUTRENNEJ SORTIROVKI, OSNOVANNYE NA
DVUHPUTEVOM SLIYANII---PROCESSE OB®EDINENIYA DVUH
UPORYADOCHENNYH POSLEDOVATELXNOSTEJ V ODNU. nETRUDNO RASSHIRITX |TO DO
PONYATIYA $P\hbox{-PUTEVOGO}$ SLIYANIYA, KOGDA $P$~VHODNYH
OTREZKOV OB®EDINYAYUTSYA V ODIN VYHODNOJ.

pUSTX IMEETSYA $P$~VOZRASTAYUSHCHIH OTREZKOV, T.~E.~POSLEDOVATELXNOSTEJ
ZAPISEJ, KLYUCHI KOTORYH RASPOLOZHENY V NEUBYVAYUSHCHEM PORYADKE. oCHEVIDNYM
SPOSOBOM IH SLIYANIYA BUDET SLEDUYUSHCHIJ:
POSMOTRETX NA PERVYE ZAPISI KAZHDOGO OTREZKA I VYBRATX IZ NIH TU, KOTOROJ
SOOTVETSTVUET MINIMALXNYJ KLYUCH; |TA ZAPISX PEREDAETSYA NA VYHOD I
ISKLYUCHAETSYA IZ VHODNYH DANNYH, ZATEM PROCESS POVTORYAETSYA.

pOKA~$P$ NE SLISHKOM VELIKO, |TOT VYBOR UDOBNO OSUSHCHESTVLYATX,
PROSTO VYPOLNYAYA $P-1$~SRAVNENIJ DLYA NAHOZHDENIYA NAIMENXSHEGO IZ TEKUSHCHIH
KLYUCHEJ. nO ESLI, SKAZHEM, $P\ge8$, TO MOZHNO SOKRATITX RABOTU, ISPOLXZUYA
\emph{DEREVO VYBORA,} KAK OPISANO V P.~5.2.3;
TOGDA KAZHDYJ RAZ TREBUETSYA TOLXKO $\approx \log_2 P$~SRAVNENIJ
(POSLE NACHALXNOGO FORMIROVANIYA DEREVA). rASSMOTRIM, NAPRIMER,
CHETYREHPUTEVOE SLIYANIE S DVUHUROVNEVYM DEREVOM VYBORA:
{\def\tree#1#2#3#4#5#6{
\left\{ \matrix{
#1\left\{\matrix{#3\ \infty\hfill\cr #4\ \infty\hfill\cr}\right.\hfill\cr
#2\left\{\matrix{#5\ \infty\hfill\cr #6\ \infty\hfill\cr}\right.\hfill\cr
}\right.
}
$$
\matrix{
{\sl shAG~1.}&                             \hfill 087 &\tree{087}{154}{087\ 503} {170\ 908}{154\ 426\ 653}{612}\hfill\cr
{\sl shAG~2.}&                        \hfill 087\ 154 &\tree{170}{154}{503}{170\ 908}{154\ 426\ 653}{612}\hfill\cr
{\sl shAG~3.}&                   \hfill 087\ 154\ 170 &\tree{170}{426}{503}{170\ 908}{426\ 653}{612}\hfill\cr
\vdots\hfill    \cr
{\sl shAG~9.}& 087\ 154\ 170\ 426\ 503\ 612\ 653\ 908 &\tree{\infty}{\infty}{}{}{}{}\hfill\cr
}
$$}%
%%301
v |TOM PRIMERE V KONCE KAZHDOGO OTREZKA POMESHCHEN DOBAVOCHNYJ KLYUCH~$\infty$,
CHTOBY SLIYANIE ZAKANCHIVALOSX ESTESTVENNO. tAK KAK VNESHNEE SLIYANIE OBYCHNO
IMEET DELO S OCHENX DLINNYMI OTREZKAMI, TO |TA DOBAVOCHNAYA ZAPISX S KLYUCHOM~$\infty$
NE UVELICHIT SUSHCHESTVENNO DLINU DANNYH ILI OB®EM RABOTY PRI SLIYANII;
KROME TOGO; TAKAYA "KONCEVAYA" ZAPISX CHASTO SLUZHIT UDOBNYM SPOSOBOM
RAZDELENIYA ZAPISEJ FAJLA.

v RASSMATRIVAEMOM PROCESSE KAZHDYJ SHAG, KROME PERVOGO, SOSTOIT IZ ZAMESHCHENIYA
NAIMENXSHEGO |LEMENTA SLEDUYUSHCHIM |LEMENTOM IZ |TOGO ZHE OTREZKA I IZMENENIYA
SOOTVETSTVUYUSHCHEGO PUTI V DEREVE VYBORA. tAK, NA SHAGE~2 IZMENYAETSYA 3~UZLA,
KOTORYE SODERZHALI~$087$ NA SHAGE~1; NA SHAGE~3 IZMENYAETSYA 3~UZLA,
SODERZHAVSHIE~$154$ NA SHAGE~2, I T.~D. pROCESS ZAMESHCHENIYA V DEREVE VYBORA
ODNOGO KLYUCHA DRUGIM NAZYVAETSYA \emph{VYBOROM S ZAMESHCHENIEM.}

mY MOZHEM PO-RAZNOMU RASSMATRIVATX PRIVEDENNOE CHETYREHPUTEVOE SLIYANIE. s
ODNOJ TOCHKI ZRENIYA ONO |KVIVALENTNO TREM DVUHPUTEVYM SLIYANIYAM, VYPOLNYAEMYM
SOVMESTNO, KAK SOPROGRAMMY; KAZHDYJ UZEL DEREVA VYBORA IZOBRAZHAET ODNU IZ
POSLEDOVATELXNOSTEJ, ISPOLXZUEMYH V PROCESSAH SLIYANIYA. dEREVO VYBORA, PO
SUSHCHESTVU, ISPOLXZUETSYA KAK PRIORITETNAYA OCHEREDX S DISCIPLINOJ "NAIMENXSHIJ
IZ VKLYUCHENNYH PERVYM ISKLYUCHAETSYA".
\picture{rIS.~62. tURNIR, PRI KOTOROM VYBIRAETSYA NAIMENXSHIJ KLYUCH;
ISPOLXZUETSYA POLNOE BINARNOE DEREVO, UZLY KOTOROGO ZANUMEROVANY NOMERAMI
OT~1 DO~23.}

tAK ZHE KAK V P.~5.2.3, MY MOGLI BY DLYA REALIZACII PRIORITETNOJ OCHEREDI
ISPOLXZOVATX NE DEREVO VYBORA, A PIRAMIDU. (pIRAMIDU, KONECHNO, NADO BYLO
BY ORGANIZOVATX TAKIM OBRAZOM, CHTOBY NA VERSHINE POYAVLYALSYA
\emph{NAIMENXSHIJ} |LEMENT, A NE NAIBOLXSHIJ,
%%302
OBRATIV DLYA |TOGO PORYADOK SOOTNOSHENIYA~(5.2.3-3).) tAK KAK PIRAMIDA
IMEET PEREMENNYJ RAZMER, MOZHNO IZBEZHATX ISPOLXZOVANIYA KLYUCHA~$\infty$;
SLIYANIE ZAKANCHIVAETSYA, KOGDA PIRAMIDA STANOVITSYA PUSTOJ. s DRUGOJ STORONY,
PRILOZHENIYA VNESHNEJ SORTIROVKI OBYCHNO IMEYUT DELO SO SRAVNITELXNO DLINNYMI
ZAPISYAMI I KLYUCHAMI, TAK CHTO V PIRAMIDU BUDUT ZAPISANY VMESTO SAMIH
KLYUCHEJ UKAZATELI NA NIH; MY UVIDIM NIZHE, CHTO DEREVXYA VYBORA MOGUT
NASTOLXKO UDOBNO IZOBRAZHATXSYA S POMOSHCHXYU UKAZATELEJ, CHTO ONI, VEROYATNO, V
DANNOJ SITUACII LUCHSHE PIRAMID.

\section dEREVO "PROIGRAVSHIH". nA RIS.~62 IZOBRAZHENO POLNOE
BINARNOE DEREVO S 12~VNESHNIMI (KVADRATNYMI) UZLAMI I
11~VNUTRENNIMI (KRUGLYMI); VO VNESHNIH UZLAH ZAPISANY KLYUCHI, VO
VNUTRENNIH--- "POBEDITELI", ESLI DEREVO RASSMATRIVATX KAK TURNIR DLYA VYBORA
\picture{rIS.~63.               tOT ZHE TURNIR, CHTO I NA RIS.~62, NO
POKAZANY PROIGRAVSHIE, A NE POBEDITELI; CHEMPION NAHODITSYA NA SAMOM VERHU.}
NAIMENXSHEGO KLYUCHA. chISLA MENXSHEGO RAZMERA NAD KAZHDYM UZLOM POKAZYVAYUT
TRADICIONNYJ SPOSOB RASPREDELENIYA POSLEDOVATELXNYH POZICIJ PAMYATI DLYA
POLNOGO BINARNOGO DEREVA.

chTOBY OPREDELITX NOVOE SOSTOYANIE DEREVA VYBORA, IZOBRAZHENNOGO NA RIS.~62,
 KOGDA NAIMENXSHIJ KLYUCH~$061$ BUDET ZAMENEN DRUGIM KLYUCHOM, NUZHNO
RASSMOTRETX TOLXKO KLYUCHI~$512$, $087$ I~$154$ I NIKAKIE DRUGIE. eSLI
INTERPRETIROVATX DEREVO KAK TURNIR, POSLEDNIE TRI KLYUCHA PREDSTAVLYAYUT
SOBOJ PROIGRAVSHIH V MATCHAH S IGROKOM~$061$. eTO NAVODIT NA MYSLX, CHTO MY V
DEJSTVITELXNOSTI DOLZHNY ZAPISATX VO VNUTRENNIE UZLY \emph{PROIGRAVSHEGO}
%%303
V KAZHDOM MATCHE, A NE POBEDITELYA, TOGDA INFORMACIYA, NEOBHODIMAYA DLYA
IZMENENIYA DEREVA, BUDET LEGKODOSTUPNOJ.

nA RIS.~63 IZOBRAZHENO TO ZHE DEREVO, CHTO I NA RIS.~62, NO VMESTO
POBEDITELEJ V NEM PREDSTAVLENY PROIGRAVSHIE. dOPOLNITELXNYJ UZEL S
NOMEROM~"0" DOBAVLEN NA VERSHINE DEREVA DLYA UKAZANIYA CHEMPIONA TURNIRA.
zAMETIM, CHTO KAZHDYJ KLYUCH, KROME CHEMPIONA, YAVLYAETSYA PROIGRAVSHIM ROVNO ODIN
RAZ (SM.~P.~5.3.3);
TAKIM OBRAZOM, KAZHDYJ KLYUCH POYAVLYAETSYA ODIN RAZ VO VNESHNEM UZLE I ODIN RAZ
VO VNUTRENNEM.

nA PRAKTIKE VNESHNIM UZLAM V NIZHNEJ CHASTI RIS.~63 BUDUT SOOTVETSTVOVATX
VESXMA DLINNYE ZAPISI, RASPOLOZHENNYE V PAMYATI evm, A VNUTRENNIM
UZLAM---UKAZATELI NA |TI ZAPISI. zAMETIM, CHTO $P\hbox{-PUTEVOE}$ SLIYANIE
TREBUET ROVNO $P$~VNESHNIH I $P$~VNUTRENNIH UZLOV PO ODNOMU V SOSEDNIH
GRUPPAH, CHTO NAVODIT NA MYSLX O RYADE |FFEKTIVNYH METODOV RASPREDELENIYA
PAMYATI. nETRUDNO VIDETX, KAKIM OBRAZOM MOZHNO ISPOLXZOVATX DEREVO
PROIGRAVSHIH DLYA VYBORA S ZAMESHCHENIEM. bOLEE DETALXNO MY OBSUDIM
|TOT ALGORITM V NASTOYASHCHEM PUNKTE CHUTX POZZHE.

\section pOLUCHENIE NACHALXNYH OTREZKOV POSREDSTVOM VYBORA S ZAMESHCHENIEM.
tEHNIKA VYBORA S ZAMESHCHENIEM MOZHET ISPOLXZOVATXSYA TAKZHE NA PERVOJ FAZE
VNESHNEJ SORTIROVKI, ESLI FAKTICHESKI VYPOLNITX $P\hbox{-PUTEVOE}$ SLIYANIE
VHODNYH DANNYH S SAMIMI SOBOJ. v |TOM SLUCHAE $P$~VYBIRAETSYA DOSTATOCHNO
BOLXSHIM, CHTOBY ZAPOLNITX, PO SUSHCHESTVU, VSYU VNUTRENNYUYU PAMYATX. kAZHDAYA
ZAPISX PRI VYVODE ZAMESHCHAETSYA OCHEREDNOJ ZAPISXYU IZ ISHODNYH DANNYH. eSLI U
|TOJ NOVOJ ZAPISI KLYUCH MENXSHE, CHEM U VYVEDENNOJ ZAPISI, TO MY NE VKLYUCHAEM
EE V TEKUSHCHIJ OTREZOK; V PROTIVNOM SLUCHAE MY OBYCHNYM OBRAZOM VKLYUCHAEM EE V
DEREVO VYBORA, TAK CHTO ONA OBRAZUET CHASTX OTREZKA, POROZHDAEMOGO V DANNYJ
MOMENT. tAKIM OBRAZOM, KAZHDYJ OTREZOK MOZHET SODERZHATX BOLXSHE $P$~ZAPISEJ,
HOTYA V LYUBOJ MOMENT V DEREVE VYBORA NAHODITSYA NE BOLEE
$P$~ZAPISEJ. tABLICA~1 ILLYUSTRIRUET |TOT PROCESS DLYA~$P=4$ (CHISLA,
ZAKLYUCHENNYE V SKOBKI, OZHIDAYUT VKLYUCHENIYA V SLEDUYUSHCHIJ OTREZOK).

eTOT VAZHNYJ METOD FORMIROVANIYA NACHALXNYH OTREZKOV BYL VPERVYE OPISAN
gAROLXDOM k.~sXYUVORDOM [Master's Thesis, Digital Computer Laboratory
Report R-232 (Mass.~Inst.~of~Technology, 1954), 29--30], KOTORYJ PRIVEL
SOOBRAZHENIYA V POLXZU TOGO, CHTO PRI PRIMENENII K SLUCHAJNYM DANNYM OTREZKI,
VIDIMO, BUDUT SODERZHATX BOLEE $1.5P$~ZAPISEJ. tU ZHE IDEYU PREDLOZHIL
PRIMERNO V 1950~G.\ a.~i.~dUMI V SVYAZI SO SPECIALXNYM USTROJSTVOM
DLYA SORTIROVKI, RAZRABATYVAEMYM Engineering Research Associates, NO NE
OPUBLIKOVAL EE. sAMO NAZVANIE "VYBOR S ZAMESHCHENIEM" (replacement
selecting) BYLO PRIDUMANO e.~X.~fR|NDOM
[{\sl JACM,\/} {\bf 3} (1956), 154], KOTORYJ ZAMETIL, CHTO "OZHIDAEMAYA DLINA
POROZHDAEMOJ POSLEDOVATELXNOSTI NE PODDAETSYA TOCHNOJ FORMULIROVKE, NO
%%304
\htable{tABLICA~1}%
{pRIMER CHETYREHPUTEVOGO VYBORA S ZAMESHCHENIEM}%
{
\strut\hfill$#$\bskip\hfill&\hfill\bskip$#$\bskip\hfill&\hfill\bskip$#$\bskip\hfill&\hfill\bskip$#$\bskip\hfill&\bskip$#$\bskip\hfill\cr
\multispan{4}\hfill sODERZHIMOE PAMYATI \hfill &  \hbox{vYVOD}\cr
\noalign{\hrule}
 503 & 087 & 512 & 061 & 061\cr
 603 & 087 & 512 & 908 & 087\cr
 503 & 170 & 512 & 908 & 170\cr
 503 & 897 & 512 & 908 & 503\cr
(275)& 897 & 512 & 908 & 512\cr
(275)& 897 & 653 & 908 & 653\cr
(275)& 897 &(426)& 908 & 897\cr
(275)&(154)&(426)& 908 & 908\cr
(275)&(154)&(426)&(509)& (\hbox{KONEC OTREZKA})\cr
 275 & 154 & 426 & 509 & 154\cr
 275 & 612 & 426 & 509 & 275\cr
\multispan{5}\hfill\hbox{I T.D.}\hfill\cr
\noalign{\hrule}
}
|KSPERIMENTY POZVOLYAYUT PREDPOLOZHITX, CHTO RAZUMNOJ OCENKOJ BUDET~$2P$".

e.~f.~mUR PREDLOZHIL IZYASHCHNYJ SPOSOB DOKAZATELXSTVA TOGO, CHTO OZHIDAEMAYA
DLINA OTREZKA RAVNA~$2P$, PROVEDYA ANALOGIYU SO
\picture{rIS.~64. vECHNYJ SNEGOOCHISTITELX V SVOEM NESKONCHAEMOM CIKLE.}
SNEGOOCHISTITELEM, DVIZHUSHCHIMSYA PO KRUGU [U.~S.~Patent~2983904 (1961),
cols.~3--4]. rASSMOTRIM SITUACIYU, IZOBRAZHENNUYU NA RIS.~64: NA KOLXCEVUYU
DOROGU RAVNOMERNO PADAYUT SNEZHINKI, A ODIN SNEGOOCHISTITELX NEPRERYVNO
UBIRAET SNEG. sNEG ISCHEZAET IZ SISTEMY,
%%304
KAK TOLXKO ON SBRASYVAETSYA ZA PREDELY DOROGI. tOCHKI DOROGI
OBOZNACHAYUTSYA VESHCHESTVENNYMI CHISLAMI~$x$, $0\le x < 1$; SNEZHINKA, PADAYUSHCHAYA
V TOCHKU~$x$, SOOTVETSTVUET VHODNOJ ZAPISI S KLYUCHOM~$x$, A SNEGOOCHISTITELX
PREDSTAVLYAET SOBOJ VYVOD PROCESSA VYBORA S ZAMESHCHENIEM.

sKOROSTX SNEGOOCHISTITELYA OBRATNO PROPORCIONALXNA VESU SNEGA, KOTORYJ
VSTRECHAETSYA NA EGO PUTI, I SITUACIYA VPOLNE URAVNOVESHENA, TAK CHTO OBSHCHEE
KOLICHESTVO SNEZHINOK NA DOROGE V TOCHNOSTI RAVNO~$P$. kAZHDYJ RAZ, KOGDA
SNEGOOCHISTITELX PROHODIT TOCHKU~0, NA VYHODE FORMIRUETSYA NOVYJ OTREZOK.
\picture{rIS.~65. pOPERECHNOE SECHENIE, POKAZYVAYUSHCHEE PEREMENNYJ VES SNEGA
PERED SNEGOOCHISTITELEM, KOGDA SISTEMA NAHODITSYA V USTANOVIVSHEMSYA REZHIME.}

iNTUITIVNO YASNO, CHTO SISTEMA, PORABOTAV NEKOTOROE VREMYA, VYJDET NA
USTANOVIVSHIJSYA REZHIM, PRI KOTOROM SNEGOOCHISTITELX BUDET DVIGATXSYA S
POSTOYANNOJ SKOROSTXYU (V SILU KRUGOVOJ SIMMETRII DOROGI). eTO OZNACHAET,
CHTO V TOCHKE, GDE NAHODITSYA SNEGOOCHISTITELX, SNEG IMEET POSTOYANNYJ VES, A
VPEREDI SNEGOOCHISTITELYA |TOT VES LINEJNO UMENXSHAETSYA, KAK POKAZANO NA
RIS.~65. oTSYUDA SLEDUET, CHTO KOLICHESTVO SNEGA, UDALYAEMOGO ZA ODIN
OBOROT (A IMENNO DLINA OTREZKA), VDVOE PREVOSHODIT KOLICHESTVO SNEGA~$P$,
 PRISUTSTVUYUSHCHEGO V LYUBOJ MOMENT.

vO MNOGIH KOMMERCHESKIH PRILOZHENIYAH VHODNYE DANNYE \emph{NELXZYA} SCHITATX
POLNOSTXYU SLUCHAJNYMI---V NIH UZHE SUSHCHESTVUET OPREDELENNYJ PORYADOK;
SLEDOVATELXNO, OTREZKI, POROZHDAEMYE VYBOROM S ZAMESHCHENIEM, IMEYUT TENDENCIYU
SODERZHATX DAZHE BOLXSHE, CHEM $2P$~ZAPISEJ. v DALXNEJSHEM MY UVIDIM, CHTO VREMYA,
 NUZHNOE DLYA VNESHNEJ SORTIROVKI SLIYANIEM, V ZNACHITELXNOJ STEPENI ZAVISIT OT
KOLICHESTVA OTREZKOV, POROZHDAEMYH NACHALXNOJ RASPREDELITELXNOJ FAZOJ, TAK
CHTO VYBOR S ZAMESHCHENIEM STANOVITSYA OSOBENNO PRIVLEKATELXNYM; DRUGIE SPOSOBY
VNUTRENNEJ SORTIROVKI POROZHDALI BY PRIMERNO VDVOE BOLXSHE NACHALXNYH
OTREZKOV, POSKOLXKU RAZMERY PAMYATI OGRANICHENY.

tEPERX DETALXNO RASSMOTRIM PROCESS SOZDANIYA NACHALXNYH OTREZKOV VYBOROM S
ZAMESHCHENIEM. sLEDUYUSHCHIJ ALGORITM PRINADLEZHIT dZHONU~r.~uOLTERSU, dZHEJMSU
p|JNTERU I~mARTINU zALKU, KOTORYE ISPOLXZOVALI EGO V PROGRAMME
SORTIROVKI POSREDSTVOM SLIYANIYA, DLYA evm Philco~2000 V~1958~G. oN VKLYUCHAET
V SEBYA
%%306
PREKRASNYJ SPOSOB NACHALXNOGO FORMIROVANIYA DEREVA VYBORA I RAZDELENIYA
ZAPISEJ, PRINADLEZHASHCHIH RAZNYM OTREZKAM, A TAKZHE VYVODA POSLEDNEGO OTREZKA
PO EDINOOBRAZNOJ, SRAVNITELXNO PROSTOJ LOGIKE. (nADLEZHASHCHAYA OBRABOTKA
POSLEDNEGO OTREZKA, POROZHDENNOGO VYBOROM S ZAMESHCHENIEM, OKAZYVAETSYA
DOVOLXNO SLOZHNOJ;
BLOK, OSUSHCHESTVLYAYUSHCHIJ |TU OBRABOTKU, CHASTO BYVAET KAMNEM PRETKNOVENIYA DLYA
PROGRAMMISTA.) oSNOVNAYA IDEYA ZAKLYUCHAETSYA V TOM, CHTOBY RASSMATRIVATX KAZHDYJ
KLYUCH KAK PARU~$(S, K)$, GDE $K$---PERVONACHALXNYJ KLYUCH, A $S$---NOMER OTREZKA,
KOTOROMU PRINADLEZHIT DANNAYA ZAPISX. mY POLUCHIM VYHODNUYU
POSLEDOVATELXNOSTX, POROZHDENNUYU VYBOROM S ZAMESHCHENIEM, ESLI
LEKSIKOGRAFICHESKI UPORYADOCHIM |TI RASSHIRENNYE KLYUCHI ($S$ SCHITAETSYA STARSHE~$K$).

pRIVODIMYJ NIZHE ALGORITM ISPOLXZUET DLYA PREDSTAVLENIYA DEREVA VYBORA
STRUKTURU DANNYH, SOSTOYASHCHUYU IZ $P$~UZLOV; PREDPOLAGAETSYA, CHTO
$j\hbox{-J}$~UZEL~$X[j]$ SODERZHIT $c$~SLOV,
NACHINAYUSHCHIHSYA S~$|LOC|(X[j]])=L_0+cj$ PRI~$0\le j < P$, ON PREDSTAVLYAET KAK
VNUTRENNIJ UZEL S NOMEROM~$j$, TAK I VNESHNIJ UZEL S
NOMEROM~$P+j$ (RIS.~63). v KAZHDOM UZLE IMEETSYA NESKOLXKO POLEJ:

% !!! pRI SMENE STILYA ILI SHRIFTA POPLYVET
{\medskip\narrower
\item{|KEY|} = KLYUCH, NAHODYASHCHIJSYA V DANNOM VNESHNEM UZLE;

\item{|RECORD|} = ZAPISX, NAHODYASHCHAYASYA V DANNOM VNESHNEM UZLE
(VKLYUCHAYA |KEY| KAK PODPOLE);

\item{|LOSER|} = UKAZATELX NA "PROIGRAVSHEGO" V DANNOM VNUTRENNEM UZLE;

\item{|RN|} = NOMER OTREZKA, KUDA VKLYUCHENA ZAPISX, NA KOTORUYU UKAZYVAET~|LOSER|;

\item{|FE|} = UKAZATELX NA VNUTRENNIJ UZEL, RASPOLOZHENNYJ V DEREVE VYBORA VYSHE
DANNOGO VNESHNEGO UZLA;

\item{|FI|} = UKAZATELX NA VNUTRENNIJ UZEL, RASPOLOZHENNYJ V DEREVE VYBORA VYSHE
DANNOGO VNUTRENNEGO UZLA.
\medskip}

nAPRIMER, PRI~$P=12$ VNUTRENNIJ UZEL S NOMEROM~5 I VNESHNIJ UZEL S
NOMEROM~17 NA RIS.~63 OBA BUDUT PREDSTAVLENY UZLOM~$X[5]$ S
POLYAMI~$|KEY|=170$, $|LOSER|=L_0+9c$ (ADRES VNESHNEGO UZLA S NOMEROM~21),
$|FE|=L_0+8c$, $|FI|=L_0+2c$.

zNACHENIYA V POLYAH~|FE| I~|FI| YAVLYAYUTSYA KONSTANTAMI; TAKIM OBRAZOM, STROGO
GOVORYA, NET NEOBHODIMOSTI HRANITX IH V YAVNOM VIDE. oDNAKO INOGDA NA
NACHALXNOJ FAZE VNESHNEJ SORTIROVKI DLYA BYSTROJ RABOTY S USTROJSTVAMI
VVODA/VYVODA VYGODNEE HRANITX |TU IZBYTOCHNUYU INFORMACIYU, CHEM VYCHISLYATX
EE KAZHDYJ RAZ ZANOVO.

\alg R.(vYBOR S ZAMESHCHENIEM.) eTOT ALGORITM CHITAET ZAPISI POSLEDOVATELXNO
IZ VHODNOGO FAJLA I ZAPISYVAET IH POSLEDOVATELXNO V VYHODNOJ FAJL,
PROIZVODYA |RMAX|~OTREZKOV DLINY~$P$ ILI BOLXSHE (ZA ISKLYUCHENIEM POSLEDNEGO
OTREZKA). iMEETSYA $P\ge 2$~UZLOV $X[0],~\ldots, X[P-1]$ S POLYAMI, OPISANNYMI
VYSHE.

%%307
\picture{rIS.~66. pOLUCHENIE NACHALXNYH OTREZKOV POSREDSTVOM VYBORA S ZAMESHCHENIEM.}
\st[nACHALXNAYA USTANOVKA.] uSTANOVITX~$|RMAX|\asg0$, $|RC|\asg0$,
 $|LASTKEY|\asg\infty$, $|Q|\asg|LOC|(X[0])$ I~$|RQ|\asg0$. (|RC|---NOMER
TEKUSHCHEGO OTREZKA, a |LASTKEY|---KLYUCH POSLEDNEJ VYVEDENNOJ ZAPISI.
nACHALXNOE ZNACHENIE~|LASTKEY| DOLZHNO BYTX BOLXSHE LYUBOGO VOZMOZHNOGO KLYUCHA;
SR.~S~UPR.~8.) dLYA~$0\le j < P$ NACHALXNOE SODERZHIMOE~$X[j]$ USTANOVITX
SLEDUYUSHCHIM OBRAZOM (GDE~$|J|=|LOC|(X[j]))$:
$$
\displaylines{
|LOSER|(|J|)\asg J; |RN|(|J|)\asg0; \cr
|FE|(|J|)\asg|LOC|(X[\floor{(P+j)/2}]);   |FI|(|J|)\asg|LOC|(X[ \floor{j/2}]).\cr
}
$$
(uSTANOVKA~$|LOSER|(|J|)$ I~$|RN|(|J|)$ ESTX ISKUSSTVENNYJ
SPOSOB OBRAZOVATX NACHALXNOE DEREVO, RASSMATRIVAYA FIKTIVNYJ OTREZOK S
NOMEROM~0, KOTORYJ NIKOGDA NE VYVODITSYA. eTO--- NEKIJ TRYUK; SM.~UPR.~10.)

\st[kONEC OTREZKA?] eSLI~$|RQ|=|RC|$, TO PEREJTI K SHAGU~\stp{3}. (v
PROTIVNOM SLUCHAE~$|RQ|=|RC|+1$, I MY TOLXKO CHTO ZAKONCHILI OTREZOK S
NOMEROM~$|RC|$; V |TOM MESTE SLEDUET VYPOLNITX TE SPECIALXNYE DEJSTVIYA,
KOTORYE NUZHNY V SOOTVETSTVII SO SHEMOJ SLIYANIYA DLYA POSLEDUYUSHCHIH |TAPOV
SORTIROVKI.) eSLI~$|RQ|>|RMAX|$, TO ALGORITM ZAVERSHEN; V PROTIVNOM SLUCHAE
USTANOVITX~$|RC|\asg|RQ|$.

\st[vYVOD VERSHINY DEREVA.] (sEJCHAS |Q|~UKAZYVAET NA "CHEMPIONA",
 I~|RQ|---NOMER EGO OTREZKA.) eSLI~$|RQ|\ne 0$, TO VYVESTI~$|RECORD|(|Q|)$ I
USTANOVITX~$|LASTKEY|\asg|KEY|(|Q|)$.

\st[vVOD NOVOJ ZAPISI.] eSLI VHODNOJ FAJL ISCHERPAN,
USTANOVITX~$|RQ|\asg|RMAX|+1$ I PEREJTI K SHAGU~\stp{5}. v PROTIVNOM SLUCHAE
POMESTITX NOVUYU ZAPISX IZ VHODNOGO FAJLA
V~$|RECORD|(|Q|)$. eSLI~$|KEY|(|Q|)<|LASTKEY|$ (T.~E.~|TA ZAPISX NE
PRINADLEZHIT TEKUSHCHEMU OTREZKU), TO~$|RQ|\asg|RQ|+1$, I TEPERX,
ESLI~$|RQ|>|RMAX|$, USTANOVITX~$|RMAX|\asg|RQ|$.

%%308

\st[pODGOTOVKA K IZMENENIYU.] (sEJCHAS~|Q| UKAZYVAET NA NOVUYU ZAPISX S
NOMEROM OTREZKA~|RQ|.) uSTANOVITX~$|T|\asg|FE|(|Q|)$. (|T|---PEREMENNYJ
UKAZATELX, KOTORYJ BUDET DVIGATXSYA PO DEREVU.)

\st[uSTANOVKA NOVOGO PROIGRAVSHEGO.] eSLI~$|RN|(|T|)<|RQ|$
ILI ESLI~$|RN|(|T|)=|RQ|$ I~$|KEY|(|LOSER|(|T|))<|KEY|(|Q|)$. TO
POMENYATX MESTAMI $|LOSER|(|T|)\xchg |Q|$, $|RN|(|T|)\xchg |RQ|$. (v
PEREMENNYH~|Q| I~|RQ| ZAPOMINAETSYA TEKUSHCHIJ POBEDITELX I NOMER EGO OTREZKA.)

\st[sDVIG VVERH.] eSLI~$|T|=|LOC|(X[1])$, TO VERNUTXSYA K SHAGU~\stp{2}, V
PROTIVNOM SLUCHAE~$|T|\asg|FI|(|T|)$ I VERNUTXSYA K~\stp{6}.
\algend

v ALGORITME~R GOVORITSYA O VVODE I VYVODE ZAPISEJ PO ODNOJ, TOGDA KAK
PRAKTICHESKI OKAZYVAETSYA LUCHSHE CHITATX I ZAPISYVATX OTNOSITELXNO BOLXSHIE
BLOKI ZAPISEJ. sLEDOVATELXNO, NA SAMOM DELE ZA KULISAMI PRYACHUTSYA BUFERY
VVODA I VYVODA; IH PRISUTSTVIE V PAMYATI PRIVODIT K UMENXSHENIYU
ZNACHENIYA~$P$. eTO BUDET POYASNENO V P.~5.4.6.

e.~X.~fR|ND [{\sl JACM,\/} {bf 3} (1956), 154] PREDLOZHIL
SLEDUYUSHCHEE OBOBSHCHENIE METODA VYBORA S ZAMESHCHENIEM. v TEH SLUCHAYAH,
KOGDA VVODIMYJ KLYUCH MENXSHE, CHEM~|LASTKEY| (TAK CHTO ON NE POPADET V TEKUSHCHIJ
OTREZOK), NO BOLXSHE ILI RAVEN POSLEDNEMU KLYUCHU, DEJSTVITELXNO
ZAPISANNOMU NA LENTU (TAK CHTO EGO FAKTICHESKI MOZHNO BYLO BY POMESTITX V
TEKUSHCHIJ OTREZOK), VSTAVLYATX |TOT KLYUCH VNUTRX BUFERA VYVODA. kROME TOGO,
NEKOTORYE evm UMEYUT VYPOLNYATX "CHTENIE VRAZBROS" I "ZAPISX SO SBORKOJ",
T.~E.~VVODITX INFORMACIYU VO VNUTRENNYUYU PAMYATX NE OBYAZATELXNO V
POSLEDOVATELXNYE YACHEJKI, A "VRAZBROS" I VYVODITX EE, SOBIRAYA IZ
RAZNYH MEST. eTO POZVOLYAET SOVMESHCHATX PAMYATX DLYA BUFEROV S PAMYATXYU DLYA
DEREVA VYBORA.

\section *pREOBRAZOVANIE OTREZKOV S ZADERZHKOJ. r.~dZH.~dINSMOR
[{\sl CACM,\/} {\bf 8} (1965), 48] PREDLOZHIL INTERESNOE USOVERSHENSTVOVANIE
VYBORA S ZAMESHCHENIEM, ISPOLXZUYUSHCHEE PONYATIE, KOTOROE BUDEM
NAZYVATX \dfn{STEPENXYU SVOBODY.} kAK MY VIDELI, KAZHDYJ BLOK ZAPISEJ,
NAHODYASHCHIJSYA NA LENTE V SOSTAVE OTREZKA, SODERZHIT ZAPISI V NEUBYVAYUSHCHEM
PORYADKE, TAK CHTO PERVYJ |LEMENT NAIMENXSHIJ, A POSLEDNIJ NAIBOLXSHIJ. v
OBYCHNOM PROCESSE VYBORA S ZAMESHCHENIEM NAIMENXSHIJ |LEMENT KAZHDOGO BLOKA V
NEKOTOROM OTREZKE VSEGDA NE MENXSHE, CHEM NAIBOLXSHIJ |LEMENT V PREDYDUSHCHEM
BLOKE |TOGO OTREZKA; |TO SOOTVETSTVUET "1~STEPENI SVOBODY". dINSMOR
PREDLOZHIL OSLABITX |TO USLOVIE DO "$m$~STEPENEJ SVOBODY"; NOVOE USLOVIE
NE TREBUET, CHTOBY NAIMENXSHIJ |LEMENT KAZHDOGO BLOKA BYL NE MENXSHE, CHEM
NAIBOLXSHIJ |LEMENT PREDYDUSHCHEGO BLOKA, NO ON \emph{NE DOLZHEN BYTX MENXSHE,
CHEM NAIBOLXSHIE |LEMENTY KAKIH-TO $m$~PREDYDUSHCHIH BLOKOV TOGO ZHE OTREZKA.}
zAPISI V OTDELXNOM BLOKE UPORYADOCHENY, KAK I RANEE, NO SOSEDNIE BLOKI NE
OBYAZANY BYTX VZAIMNO UPORYADOCHENNYMI.

%%309

pREDPOLOZHIM, NAPRIMER, CHTO BLOKI SODERZHAT TOLXKO PO DVE ZAPISI; SLEDUYUSHCHAYA
POSLEDOVATELXNOSTX BLOKOV YAVLYAETSYA OTREZKOM S TREMYA STEPENYAMI SVOBODY:
$$
\vert 08\ 50 \vert 06\ 90 \vert 17\ 27 \vert 42\ 67 \vert 51\ 89 \vert
\eqno (1)
$$

sLEDUYUSHCHIJ BLOK, KOTORYJ MOZHET BYTX CHASTXYU |TOGO OTREZKA, DOLZHEN NACHINATXSYA
S |LEMENTA, NE MENXSHEGO, CHEM TRETIJ PO PORYADKU |LEMENT
MNOZHESTVA~$\set{50, 90, 27, 67, 89}$, SCHITAYA OT NAIBOLXSHEGO, T.~E.\ NE
MENXSHE~67. pOSLEDOVATELXNOSTX~(1) NE YAVLYAETSYA OTREZKOM S DVUMYA STEPENYAMI
SVOBODY, TAK KAK 17~MENXSHE, CHEM~50 I~90.

oTREZOK S $m$~STEPENYAMI SVOBODY V PROCESSE CHTENIYA V SLEDUYUSHCHEJ FAZE
SORTIROVKI MOZHET BYTX PREOBRAZOVAN TAKIM OBRAZOM, CHTO DLYA VSEH
PRAKTICHESKIH CELEJ ON BUDET OTREZKOM V OBYCHNOM SMYSLE. nACHNEM S CHTENIYA
PERVYH $m$~BLOKOV V $m$~BUFEROV I BUDEM PROIZVODITX $m\hbox{-PUTEVOE}$
SLIYANIE IH; KOGDA ODIN IZ BUFEROV ISCHERPAETSYA, POMESTIM V NEGO
$(m+1)\hbox{-J}$~BLOK I~T.~D. tAKIM OBRAZOM, MY MOZHEM VOSSTANOVITX
OTREZOK V VIDE ODNOJ UPORYADOCHENNOJ POSLEDOVATELXNOSTI, TAK KAK PERVOE
SLOVO KAZHDOGO VNOVX SCHITYVAEMOGO BLOKA DOLZHNO BYTX BOLXSHE ILI RAVNO
POSLEDNEMU SLOVU TOLXKO CHTO ISCHERPANNOGO BLOKA (ESLI ONO NE BYLO MENXSHE,
CHEM NAIBOLXSHIE |LEMENTY KAKIH-LIBO $m$~BLOKOV, PREDSHESTVUYUSHCHIH EMU). eTOT
METOD PREOBRAZOVANIYA OTREZKA, V SUSHCHNOSTI, YAVLYAETSYA $m\hbox{-PUTEVYM}$
SLIYANIEM, ISPOLXZUYUSHCHIM TOLXKO ODNO LENTOCHNOE USTROJSTVO DLYA VSEH VHODNYH
BLOKOV!

pROCEDURA PREOBRAZOVANIYA DEJSTVUET KAK SOPROGRAMMA, K KOTOROJ OBRASHCHAYUTSYA
KAZHDYJ RAZ, KOGDA NUZHNO POLUCHITX ODNU OCHEREDNUYU ZAPISX OTREZKA. mY MOZHEM
PREOBRAZOVYVATX RAZLICHNYE OTREZKI S RAZLICHNYH LENTOCHNYH USTROJSTV I S
RAZLICHNYMI STEPENYAMI SVOBODY I SLIVATX POLUCHAYUSHCHIESYA OTREZKI---VSE V ODNO I
TO ZHE VREMYA. eTO, PO SUSHCHESTVU, PODOBNO TOMU, KAK ESLI BY MY CHETYREHPUTEVOE
SLIYANIE, RASSMOTRENNOE V NACHALE |TOGO PUNKTA, PREDSTAVILI SEBE KAK
NESKOLXKO DVUHPUTEVYH SLIYANIJ, PROISHODYASHCHIH ODNOVREMENNO.

eTA OSTROUMNAYA IDEYA DO SIH POR NE PROANALIZIROVANA DO KONCA. iMEYUTSYA
NEKOTORYE PREDVARITELXNYE REZULXTATY, POKAZYVAYUSHCHIE, CHTO, KOGDA
$P$~VELIKO PO SRAVNENIYU S RAZMEROM BLOKA, DLINA OTREZKA PRI~$m=2$
PRIBLIZITELXNO RAVNA~$2.1P$, ONA RAVNA~$2.3P$ PRI~$m=4$ I~$2.5P$ PRI~$m=8$.
tAKOE UVELICHENIE, BYTX MOZHET, NEDOSTATOCHNO, CHTOBY OPRAVDATX USLOZHNENIE
ALGORITMA. s DRUGOJ STORONY, METOD MOZHET OKAZATXSYA VYGODNYM, ESLI NA.
PROTYAZHENII VTOROGO |TAPA SORTIROVKI ESTX MESTO DLYA DOVOLXNO BOLXSHOGO CHISLA
BUFEROV.

%%310

\section *nATURALXNYJ VYBOR. dRUGOJ PUTX UVELICHENIYA DLINY OTREZKOV,
 POROZHDAEMYH VYBOROM S ZAMESHCHENIEM, BYL ISSLEDOVAN u.~d.~fR|JZEROM
I~ch.~k.~uONOM. iH IDEYA SOSTOIT V TOM, CHTOBY SLEDOVATX ALGORITMU~R, NO,
KOGDA NA SHAGE~R4 $|KEY|(|Q|)<|LASTKEY|$, NOVAYA ZAPISX~$|RECORD|(|Q|)$ NE
OSTAETSYA V DEREVE,, A VYVODITSYA V NEKOTORYJ VNESHNIJ \emph{REZERVUAR} I
CHITAETSYA NOVAYA ZAPISX. eTOT PROCESS PRODOLZHAETSYA DO TEH POR, POKA V
REZERVUARE NE OKAZHETSYA OPREDELENNOE KOLICHESTVO ZAPISEJ~$P'$; TOGDA
OSTATOK TEKUSHCHEGO OTREZKA VYVODITSYA IZ DEREVA, I |LEMENTY REZERVUARA
ISPOLXZUYUTSYA V KACHESTVE ISHODNYH DANNYH DLYA SLEDUYUSHCHEGO OTREZKA.

eTOT METOD DOLZHEN POROZHDATX BOLEE DLINNYE OTREZKI, CHEM VYBOR S ZAMESHCHENIEM,
POSKOLXKU ON "OBHODIT" VNOVX POSTUPAYUSHCHIE "MERTVYE" ZAPISI, VMESTO TOGO
CHTOBY POZVOLYATX IM ZAPOLNYATX DEREVO; NO EMU TREBUETSYA DOPOLNITELXNOE VREMYA
NA OBMEN S REZERVUAROM. kOGDA~$P'>P$, NEKOTORYE ZAPISI MOGUT
OKAZYVATXSYA V REZERVUARE DVAZHDY, NO PRI~$P'\le P$ TAKOGO SLUCHITXSYA NE MOZHET.

fR|JZER I~uON, PROVEDYA OBSHIRNYE |MPIRICHESKIE ISPYTANIYA SVOEGO METODA,
ZAMETILI, CHTO, KOGDA~$P$ DOSTATOCHNO VELIKO (SKAZHEM, $P\ge 32$) I~$P'=P$,
SREDNYAYA DLINA OTREZKA DLYA SLUCHAJNYH DANNYH OKAZYVAETSYA RAVNOJ~$eP$,
GDE~$e\approx 2.718$---OSNOVANIE NATURALXNYH LOGARIFMOV. eTO YAVLENIE, A
TAKZHE TOT FAKT, CHTO METOD BYL POLUCHEN KAK |VOLYUCIONNOE RAZVITIE PROSTOGO
VYBORA S ZAMESHCHENIEM, POSLUZHILI DLYA NIH NEPOSREDSTVENNYM
OSNOVANIEM NAZVATX SVOJ METOD \dfn{NATURALXNYM VYBOROM.}

mOZHNO DOKAZATX "NATURALXNYJ" ZAKON DLYA DLINY OTREZKA, VNOVX
VOSPOLXZOVAVSHISX ANALOGIEJ SO SNEGOOCHISTITELEM NA RIS.~64 I PRIMENIV
|LEMENTARNYJ MATEMATICHESKIJ ANALIZ. pUSTX~$L$ OBOZNACHAET DLINU PUTI,
a~$x(t)$---POLOZHENIE SNEGOOCHISTITELYA V MOMENT~$t$ PRI~$0 \le t \le T$.
pREDPOLOZHIM, CHTO V MOMENT~$T$ REZERVUAR ZAPOLNYAETSYA; V |TOT MOMENT PADENIE
SNEGA VREMENNO PREKRASHCHAETSYA, POKA SNEGOOCHISTITELX VOZVRASHCHAETSYA V ISHODNOE
POLOZHENIE (SCHISHCHAYA $P$~SNEZHINOK, OSTAVSHIHSYA NA EGO PUTI). sITUACIYA TAKAYA
ZHE, KAK I RANEE, TOLXKO "USLOVIYA RAVNOVESIYA" DRUGIE---VMESTO $P$~SNEZHINOK NA
VSEJ DOROGE V LYUBOJ MOMENT VREMENI MY IMEEM $P$~SNEZHINOK PERED
SNEGOOCHISTITELEM I REZERVUAR (ZA SNEGOOCHISTITELEM), ZAPOLNYAYUSHCHIJSYA DO
UROVNYA V $P$~SNEZHINOK. v TECHENIE INTERVALA VREMENI~$dt$ SNEGOOCHISTITELX
PRODVIGAETSYA NA~$dx$, ESLI VYVODYATSYA $h(x, t)dx$~ZAPISEJ, GDE~$h(x,
t)$---TOLSHCHINA SLOYA SNEGA V MOMENT VREMENI~$t$ V TOCHKE~$x=x(t)$, IZMERYAEMAYA V
SOOTVETSTVUYUSHCHIH EDINICAH; SLEDOVATELXNO, $h(x, t)=h(x, 0)+Kt$ DLYA VSEH~$x$.
 tAK KAK CHISLO ZAPISEJ V PAMYATI OSTAETSYA POSTOYANNYM, TO $h(x, t)dx$~ESTX
TAKZHE CHISLO ZAPISEJ, VVODIMYH \emph{PERED} SNEGOOCHISTITELEM, A
IMENNO~$Kdt(L-x)$, GDE~$K$---SKOROSTX PADENIYA SNEGA (RIS.~67). tAKIM OBRAZOM,
$$
{dx\over dt}={K(L-x)\over h(x,t)}.
\eqno(2)
$$
%%311

k SCHASTXYU, OKAZYVAETSYA, CHTO~$h(x,t)$---KONSTANTA, I ONA RAVNA~$KT$ PRI
VSEH~$x=x(t)$ I~$0\le t \le T$, TAK KAK SNEG PADAET RAVNOMERNO V
TOCHKU~$x(t)$ V TECHENIE $T-t$~EDINIC VREMENI POSLE TOGO, KAK
SNEGOOCHISTITELX PROHODIT |TU TOCHKU, PLYUS $t$~EDINIC VREMENI PERED TEM, KAK
ON VERNETSYA. iNYMI SLOVAMI, SNEGOOCHISTITELX VIDIT PERED SOBOJ VSE VREMYA
ODINAKOVYJ SLOJ SNEGA NA PROTYAZHENII VSEGO PUTI, ESLI DOPUSTITX, CHTO
DOSTIGNUT USTANOVIVSHIJSYA REZHIM, KOGDA |TOT PUTX VSE VREMYA ODIN I TOT ZHE.
sLEDOVATELXNO, OBSHCHEE KOLICHESTVO SCHISHCHAEMOGO SNEGA (DLINA OTREZKA)
ESTX~$KTL$,
\picture{rIS.~67. vVODITSYA I VYVODITSYA RAVNOE KOLICHESTVO SNEGA; ZA
VREMYA~$dt$ SNEGOOCHISTITELX PEREMESHCHAETSYA NA~$dx$.}
A KOLICHESTVO SNEGA V PAMYATI ESTX KOLICHESTVO SNEGA, SCHISHCHAEMOGO POSLE
MOMENTA~$T$, A IMENNO~$KT(L-x(T))$.

rESHENIEM URAVNENIYA~(2) PRI USLOVII, CHTO~$x(0)=0$, BUDET
$$
x(t)=L(1-e^{-t/T}).
\eqno(3)
$$
sLEDOVATELXNO, $P=KTLe^{-1}=\hbox{(DLINA OTREZKA)}/e$---|TO KAK RAZ TO, CHTO
MY I HOTELI DOKAZATX.

v UPR.~21--23 POKAZANO, CHTO |TOT ANALIZ MOZHNO RASPROSTRANITX NA SLUCHAJ
PROIZVOLXNOGO~$P'$; NAPRIMER, KOGDA~$P'=2P$, SREDNYAYA DLINA OTREZKA
OKAZYVAETSYA RAVNOJ~$e^\theta(e-\theta)P$,
GDE~$\theta={1\over2}(e-\sqrt{e^2-4})$,---REZULXTAT, KOTORYJ VRYAD LI MOZHNO BYLO
PREDPOLOZHITX ZARANEE! v TABL.~2 PRIVODITSYA ZAVISIMOSTX MEZHDU DLINOJ
OTREZKA I RAZMEROM REZERVUARA; S POMOSHCHXYU |TOJ TABLICY MOZHNO OCENITX
POLEZNOSTX NATURALXNOGO VYBORA DLYA KONKRETNOJ MASHINY V TOJ ILI INOJ SITUACII.

\section *aNALIZ VYBORA S ZAMESHCHENIEM. vERNEMSYA TEPERX K SLUCHAYU VYBORA S
ZAMESHCHENIEM BEZ VSPOMOGATELXNOGO REZERVUARA. aNALOGIYA SO SNEGOOCHISTITELEM
DAET DOVOLXNO HOROSHUYU OCENKU SREDNEJ DLINY OTREZKOV, POLUCHAEMYH PRI VYBORE
S ZAMESHCHENIEM "V PREDELE", TEM NE MENEE MOZHNO POLUCHITX ZNACHITELXNO BOLEE
TOCHNUYU INFORMACIYU OB ALGORITME~R, PRIMENYAYA FAKTY OB OTREZKAH V
PERESTANOVKAH, IZUCHENNYH NAMI V P.~5.1.3. dLYA UDOBSTVA BUDEM SCHITATX, CHTO
VHODNOJ FAJL YAVLYAETSYA POSLEDOVATELXNOSTXYU  (PROIZVOLXNOJ DLINY)
NEZAVISIMYH SLUCHAJNYH DEJSTVITELXNYH CHISEL, RASPOLOZHENNYH MEZHDU~0 I~1.

%%312
\htable{tABLICA 2}%
{dLINA OTREZKOV PRI NATURALXNOM VYBORE}%
{\strut\hfill$#$\bskip&\bskip\hfill$#$\bskip&\bskip\hfill$#$\bskip&
 \hfill$\qquad#$\bskip&\bskip\hfill$#$\bskip&\bskip\hfill$#$\cr
\omit\hfill rAZMER \hfill & \omit\hfill dLINA\hfill & & \omit\hfill rAZMER
\hfill & dLINA \hfill\cr
\omit\hfill REZERVUARA \hfill  & \omit\hfill OTREZKA\hfill &\omit\hfill
pARAMETR\hfill &\omit\hfill REZERVUARA \hfill & \omit\hfill OTREZKA\hfill
& \omit\hfill pARAMETR\hfill \cr
\noalign{\hrule}
1.00000P & 2.71828P & 1.00000 &  0.38629P &  2.00000P & 0.69315\cr
2.00000P & 3.53487P & 1.43867 &  1.30432P &  3.oooooP & 1.15881\cr
3.00000P & 4.16220P & 1.74773 &  2.72294P &  4.00000P & 1.66862\cr
4.00000P & 4.69445P & 2.01212 &  4.63853P &  5.00000P & 2.16714\cr
5.00000P & 5.16369P & 2.24038 & 21.72222P & 10.00000P & 4.66667\cr
10.00000P& 7.00877P & 3.17122 &  5.29143P &  5.29143P & 2.31329\cr
\noalign{\hrule}
\noalign{\hbox{\strut "pARAMETR"~$k+\theta$ OPREDELEN V UPR.~22}}
}

pUSTX
$$
g_P(z_1, z_2,~\ldots, z_k)=\sum_{l_1, l_2,~\ldots, l_k\ge 0}
a_P(l_1, l_2,~\ldots, l_k)z_1^{l_1} z_2^{l_2}\ldots z_k^{l_k}
$$
---PROIZVODYASHCHAYA FUNKCIYA DLYA DLINY OTREZKA, POLUCHENNOGO
PRI $P\hbox{-PUTEVOM}$~VYBORE S ZAMESHCHENIEM, PRIMENENNOM K. TAKOMU FAJLU,
 GDE $a_P(l_1, l_2,~\ldots, l_k)$~ESTX VEROYATNOSTX TOGO, CHTO PERVYJ
OTREZOK IMEET DLINU~$l_1$, VTOROJ---DLINU~$l_2$,~\dots, $k\hbox{-J}$ IMEET
DLINU~$l_k$. bUDEM OSNOVYVATXSYA NA SLEDUYUSHCHEJ "TEOREME NEZAVISIMOSTI", tAK
KAK ONA SVODIT NASH ANALIZ K SLUCHAYU~$P=1$.

\proclaim tEOREMA~K.
$g_P(z_1, z_2,~\ldots, z_k)=g_1(z_1, z_2,~\ldots, z_k)^P$.

\proof pUSTX ISHODNYE KLYUCHI SUTX~$X_1$, $X_2$, $X_3$,~$\ldots\,
$. aLGORITM~R RAZDELYAET IH NA $P$~PODPOSLEDOVATELXNOSTEJ V SOOTVETSTVII
S TEM, V KAKOJ VNESHNIJ UZEL DEREVA ONI POPADAYUT;
PODPOSLEDOVATELXNOSTX, SODERZHASHCHAYA~$X_n$, OPREDELYAETSYA ZNACHENIYAMI~$X_1$,
~\dots, $X_{n-1}$. tAKIM OBRAZOM, |TI PODPOSLEDOVATELXNOSTI  YAVLYAYUTSYA
NEZAVISIMYMI POSLEDOVATELXNOSTYAMI NEZAVISIMYH SLUCHAJNYH CHISEL,
RASPOLOZHENNYH MEZHDU~0 I~1. kROME TOGO, VYHOD VYBORA S ZAMESHCHENIEM V
TOCHNOSTI SOVPADAET S REZULXTATOM $P\hbox{-PUTEVOGO}$ SLIYANIYA, ESLI EGO
PROIZVESTI NAD |TIMI PODPOSLEDOVATELXNOSTYAMI; NEKOTORYJ |LEMENT
PRINADLEZHIT $j\hbox{-MU}$~OTREZKU PODPOSLEDOVATELXNOSTI TOGDA I TOLXKO
TOGDA, KOGDA ON PRINADLEZHIT $j\hbox{-MU}$~OTREZKU, POLUCHENNOMU PRI
VYBORE S ZAMESHCHENIEM (TAK KAK NA SHAGE~R4 KLYUCHI~|LASTKEY| I~$|KEY|(|Q|)$
PRINADLEZHAT ODNOJ PODPOSLEDOVATELXNOSTI).

iNACHE GOVORYA, MOZHNO SCHITATX, CHTO ALGORITM~R PRIMENYAETSYA K $P$~SLUCHAJNYM
NEZAVISIMYM ISHODNYM FAJLAM I CHTO SHAG~R4 CHITAET SLEDUYUSHCHUYU ZAPISX IZ
FAJLA, SOOTVETSTVUYUSHCHEGO VNESHNEMU UZLU~|Q|; V |TOM SMYSLE RASSMATRIVAEMYJ
ALGORITM |KVIVALENTEN  $P\hbox{-PUTEVOMU}$ SLIYANIYU, GDE KONCY OTREZKOV
OTMECHAYUTSYA UBYVANIEM |LEMENTOV.

tAKIM OBRAZOM, NA VYHODE BUDUT OTREZKI DLIN~$(l_1,~\ldots, l_k)$ TOGDA I
TOLXKO TOGDA, KOGDA PODPOSLEDOVATELXNOSTI SOSTOYAT IZ
%% 313
OTREZKOV DLIN~$(l_{11},~\ldots, l_{1k})$,~\dots, $(l_{P1},~\ldots,
l_{Pk})$ SOOTVETSTVENNO; GDE~$l_{ij}$---NEKOTORYE NEOTRICATELXNYE CELYE
CHISLA, UDOVLETVORYAYUSHCHIE SOOTNOSHENIYU~$\sum_{1\le i \le P} l_{ij}=l_j$
PRI~$1\le j \le k$. oTSYUDA SLEDUET, CHTO
$$
a_P(l_1,~\ldots, l_k)=\sum_{
{\scriptstyle l_{11}+\cdots+l_{P1}=l_1 \atop
\scriptstyle \vdots} \atop
\scriptstyle l_{1k}+\cdots+l_{Pk}=l_k
}a_1(l_{11},~\ldots, l_{1k})\ldots a_1(l_{P1},~\ldots, l_{Pk}),
$$
CHTO |KVIVALENTNO ISKOMOMU REZULXTATU.
\proofend

v P.~5.1.3 MY IZUCHILI SREDNEE ZNACHENIE~$L_k$---DLINY $k\hbox{-GO}$~OTREZKA
PRI~$P=1$ (|TI ZNACHENIYA PRIVEDENY V TABL.~5.1.3-2). iZ TEOREMY~K SLEDUET,
CHTO SREDNYAYA DLINA $k\hbox{-GO}$~OTREZKA PRI LYUBOM~$P$ V $P$~RAZ BOLXSHE
SREDNEJ DLINY PRI~$P=1$, ONA RAVNA~$L_kP$;
DISPERSIYA TAKZHE V $P$~RAZ BOLXSHE, TAK CHTO STANDARTNOE OTKLONENIE DLINY
OTREZKA PROPORCIONALXNO~$\sqrt{P}$. eTI REZULXTATY BYLI VPERVYE POLUCHENY
b.~dZH.~g|SSNER OKOLO 1958~G.

tAKIM OBRAZOM, PERVYJ OTREZOK, POLUCHENNYJ DLYA SLUCHAJNYH DANNYH
ALGORITMOM~R, BUDET IMETX DLINU, PRIBLIZHENNO RAVNUYU
$(e-1)P\approx 1.718P$~ZAPISEJ,
VTOROJ---PRIBLIZHENNO~$(e^2-2e)P\approx 1.952P$, TRETIJ---$1.996P$; DLINA
SLEDUYUSHCHIH OTREZKOV BUDET OCHENX BLIZKA K~$2P$, POKA MY NE DOJDEM DO
POSLEDNIH DVUH OTREZKOV (SM. UPR.~14). sTANDARTNOE OTKLONENIE DLINY
BOLXSHINSTVA |TIH OTREZKOV PRIBLIZHENNO
RAVNO~$\sqrt{(4e-10)P}\approx 0.934 \sqrt{P}$
[{\sl CACM,\/} {\bf 6} (1963), 685--687].

kROME |TOGO, SOGLASNO UPR.~5.1.3-10, \emph{SUMMARNAYA} DLINA PERVYH
$k$~OTREZKOV BUDET DOVOLXNO BLIZKA K~$\left(2k-{1\over3}\right)P$ SO
STANDARTNYM
OTKLONENIEM~$\left(\left({2\over3}k+{2\over9}\right)P\right)^{1/2}$.
pROIZVODYASHCHIE FUNKCII~$g_1(z, z,~\ldots, z)$ I~$g_1(1,~\ldots, 1, z)$
VYVODYATSYA V UPR.~5.1.3-9 I~11.

v PRIVEDENNOM VYSHE ANALIZE PREDPOLAGALOSX, CHTO ISHODNYJ FAJL BESKONECHNO
DLINNYJ, NO DOKAZATELXSTVO TEOREMY~K POKAZYVAET, CHTO TOCHNO TAKAYA ZHE
VEROYATNOSTX~$a_P(l_1,~\ldots, l_k)$ POLUCHILASX BY V SLUCHAE LYUBOJ SLUCHAJNOJ
ISHODNOJ POSLEDOVATELXNOSTI, SODERZHASHCHEJ PO KRAJNEJ MERE
$l_1+\cdots+l_k+P$~|LEMENTOV. sLEDOVATELXNO, POLUCHENNYE REZULXTATY
PRIMENIMY DLYA FAJLA RAZMERA, SKAZHEM, $N > (2K+1)P$ V SILU MALOJ VELICHINY
STANDARTNOGO OTKLONENIYA.

mY POZNAKOMIMSYA S RYADOM PRIMENENIJ, V KOTORYH SHEMA SLIYANIYA TREBUET,
CHTOBY NEKOTORYE OTREZKI BYLI VOZRASTAYUSHCHIMI, A NEKOTORYE---UBYVAYUSHCHIMI.
pOSKOLXKU OSTATOK, NAKAPLIVAYUSHCHIJSYA V PAMYATI U KONCA VOZRASTAYUSHCHEGO OTREZKA,
IMEET TENDENCIYU SODERZHATX CHISLA, V SREDNEM MENXSHIE, CHEM SLUCHAJNYE DANNYE,
TO IZMENENIE NAPRAVLENIYA UPORYADOCHENIYA UMENXSHAET SREDNYUYU DLINU OTREZKOV.
rASSMOTRIM, NAPRIMER, SNEGOOCHISTITELX, KOTORYJ DOLZHEN
%%314
VYPOLNYATX RAZVOROT KAZHDYJ RAZ, KAK ON DOSTIGAET KONCA PRYAMOJ DOROGI;
ON BUDET OCHENX BYSTRO PEREDVIGATXSYA PO TOLXKO CHTO OCHISHCHENNOMU UCHASTKU. v
SLUCHAE IZMENYAEMOGO NAPRAVLENIYA DLINA OTREZKOV DLYA SLUCHAJNYH DANNYH
IZMENYAETSYA MEZHDU~$1.5P$ I~$2P$ (SM.~UPR.~24).

\excercises
\ex[10] kAKIM BUDET SHAG 4 V PRIMERE CHETYREH PUTEVOGO SLIYANIYA V NACHALE
|TOGO PUNKTA?

\ex[12] kAKIE IZMENENIYA PROIZOSHLI BY V DEREVE RIS.~63, ESLI BY KLYUCH~$061$
BYL ZAMENEN KLYUCHOM~$612$?

\ex[16] (e.~f.~mUR.) chTO POLUCHITSYA V REZULXTATE PRIMENENIYA
CHETYREHPUTEVOGO VYBORA S ZAMESHCHENIEM K POSLEDOVATELXNYM SLOVAM SLEDUYUSHCHEGO
PREDLOZHENIYA\note{1}%
{vOSEMXDESYAT SEMX LET TOMU NAZAD NASHI PREDKI OSNOVALI NA |TOM KONTINENTE
NOVUYU NACIYU, POSVYATIVSHUYU SEBYA DELU SVOBODY I UBEZHDENNUYU V TOM, CHTO VSE
LYUDI SOZDANY RAVNYMI.---{\sl pRIM. PEREV.\/}}
{\medskip\narrower\tt\noindent
fourscore and seven years ago our fathers brought forth on this continent
a new nation conceived in liberty and dedicated to the proposition that
all men are created equal.
\medskip\noindent}
(iSPOLXZUJTE OBYCHNYJ ALFAVITNYJ PORYADOK, RASSMATRIVAYA KAZHDOE SLOVO
KAK ODIN KLYUCH.)

\ex[16] pRIMENITE CHETYREHPUTEVOJ \emph{NATURALXNYJ} VYBOR K PREDLOZHENIYU
IZ UPR.~3, ISPOLXZUYA REZERVUAR EMKOSTI~4.

\ex[00] vERNO LI, CHTO VYBOR S ZAMESHCHENIEM, ISPOLXZUYUSHCHIJ DEREVO, RABOTAET,
TOLXKO ESLI $P$~ESTX STEPENX DVOJKI ILI SUMMA DVUH STEPENEJ DVOJKI?

\ex[15] v ALGORITME~R UKAZYVAETSYA, CHTO $P$~DOLZHNO BYTX~$\ge2$;
KAKIE OTNOSITELXNO NEBOLXSHIE IZMENENIYA NADO SDELATX V |TOM ALGORITME,
CHTOBY ON PRAVILXNO RABOTAL DLYA VSEH~$P\ge 1$?

\ex[17] chTO DELAET ALGORITM~R V SLUCHAE OTSUTSTVIYA ISHODNOJ INFORMACII?

\ex[20] aLGORITM~R ISPOLXZUET ISKUSSTVENNYJ KLYUCH~"$\infty$", KOTORYJ
DOLZHEN BYTX BOLXSHE LYUBOGO VOZMOZHNOGO KLYUCHA. pOKAZHITE, CHTO ESLI BY
KAKOJ-NIBUDX REALXNYJ KLYUCH OKAZALSYA RAVNYM~$\infty$, TO ALGORITM MOG BY
OSHIBITXSYA, I OB®YASNITE, KAK IZMENITX ALGORITM V SLUCHAE, KOGDA REALIZACIYA
"NASTOYASHCHEJ" BESKONECHNOSTI NEUDOBNA.

\rex[23] kAK VY IZMENILI BY ALGORITM~R, CHTOBY ON VYVODIL
NEKOTORYE ZADANNYE OTREZKI (OPREDELYAEMYE~|RC|) V VOZRASTAYUSHCHEM PORYADKE, A
DRUGIE V UBYVAYUSHCHEM?

\ex[26] nACHALXNAYA USTANOVKA UKAZATELEJ~|LOSER| NA SHAGE~R1 OBYCHNO
NE SOOTVETSTVUET NIKAKOMU DEJSTVITELXNOMU TURNIRU, TAK KAK VNESHNIJ
UZEL~$P+j$ MOZHET NE LEZHATX V PODDEREVE S VERSHINOJ VO VNUTRENNEM
UZLE~$j$. oB®YASNITE, POCHEMU ALGORITM~R VSE RAVNO RABOTAET.
[\emph{uKAZANIE.} bUDET LI RABOTATX ALGORITM~R, ESLI
MNOZHESTVU~$\set{|LOSER|(|LOC| (X[0])),~\ldots,
|LOSER|(|LOC| (X[P-1]))}$ PRISVAIVAETSYA NA SHAGE~R1 \emph{PROIZVOLXNAYA}
PERESTANOVKA MNOZHESTVA~$\set{|LOC|(X[0]),~\ldots, |LOC|(X[P-1])}$?]

\ex[m25] vERNO LI, CHTO DLYA SLUCHAJNYH ISHODNYH DANNYH VEROYATNOSTX TOGO,
CHTO~$|KEY|(|Q|)<|LASTKEY|$ NA SHAGE~R4, PRIBLIZHENNO RAVNA~1/2?

\ex[M46] pROVEDITE DETALXNOE ISSLEDOVANIE TOGO, SKOLXKO RAZ VYPOLNYAETSYA
KAZHDAYA CHASTX ALGORITMA~R; NAPRIMER, KAK CHASTO VYPOLNYAETSYA PERESTANOVKA
NA SHAGE~R6?

%%315
\ex[13] pOCHEMU VTOROJ OTREZOK, POLUCHENNYJ PRI VYBORE S ZAMESHCHENIEM, OBYCHNO
DLINNEE PERVOGO?

\rex[vm25] iSPOLXZUJTE ANALOGIYU SO SNEGOOCHISTITELEM, CHTOBY OCENITX SREDNYUYU
DLINU DVUH \emph{POSLEDNIH} OTREZKOV, POLUCHENNYH PRI VYBORE S ZAMESHCHENIEM,
 PRIMENENNOM K DLINNOJ POSLEDOVATELXNOSTI ISHODNYH DANNYH.

\ex[20] vERNO LI, CHTO POSLEDNIJ OTREZOK, POLUCHENNYJ PRI VYBORE S
ZAMESHCHENIEM, NIKOGDA NE SODERZHIT BOLEE $P$~ZAPISEJ? oBSUDITE VASH OTVET.

\ex[m26] nAJDITE "PROSTOE" NEOBHODIMOE I DOSTATOCHNOE USLOVIE TOGO, CHTO
FAJL~$R_1$~$R_2$~\dots{} $R_N$ BUDET POLNOSTXYU UPORYADOCHEN ZA ODIN PROHOD
$P\hbox{-PUTEVOGO}$ VYBORA S ZAMESHCHENIEM. kAKOVA VEROYATNOSTX |TOGO SOBYTIYA
KAK FUNKCIYA~$P$ I~$N$, ESLI ISHODNYMI DANNYMI SLUZHIT SLUCHAJNAYA
PERESTANOVKA MNOZHESTVA~$\set{1, 2,~\ldots, N}$?

\ex[20] chTO POLUCHAETSYA V REZULXTATE RABOTY ALGORITMA~R, KOGDA ISHODNYE
KLYUCHI PREDSTAVLYAYUT SOBOJ NEVOZRASTAYUSHCHUYU
POSLEDOVATELXNOSTX~$K_1\ge K_2\ge\ldots\ge K_N$?

\rex[22] chTO PROIZOJDET, ESLI VNOVX PRIMENITX ALGORITM~R K FAJLU,
POLUCHENNOMU V REZULXTATE RABOTY ALGORITMA~R?

\ex[vm22] iSPOLXZUJTE ANALOGIYU SO SNEGOOCHISTITELEM, CHTOBY DOKAZATX, CHTO
PERVYJ OTREZOK, POLUCHENNYJ PRI VYBORE S ZAMESHCHENIEM, IMEET DLINU PRIMERNO
$(e-1)P$~ZAPISEJ.

\ex[vm24] kAKUYU PRIMERNO DLINU IMEET PERVYJ OTREZOK, POLUCHENNYJ PRI
NATURALXNOM VYBORE, KOGDA~$P=P'$?

\rex[vm23] oPREDELITE PRIBLIZITELXNUYU DLINU OTREZKOV,
POLUCHENNYH POSREDSTVOM NATURALXNOGO VYBORA PRI~$P'<P$.

\ex[vm40] cELXYU |TOGO UPRAZHNENIYA YAVLYAETSYA OPREDELENIE SREDNEJ DLINY
OTREZKOV, POLUCHAEMYH PRI NATURALXNOM VYBORE PRI~$P'>P$.
pUSTX~$\kappa=k+\theta$---DEJSTVITELXNOE CHISLO~$\ge 1$,
GDE~$k=\floor{\kappa}$, A~$\theta=\kappa \bmod 1$, I RASSMOTRIM
FUNKCIYU~$F(\kappa)=F_k(\theta)$, GDE~$F_k(\theta)$---POLINOMY, OPREDELYAEMYE
PROIZVODYASHCHEJ FUNKCIEJ
$$
\sum_{k\ge0} F_k(\theta)z^k=e^{-\theta z}/(1-z e^{1-z}).
$$
tAKIM OBRAZOM, $F_0(\theta)=1$, $F_1(\theta)=e-\theta$,
$F_2(\theta)=e^2-e-e\theta+{1\over2}\theta^2$ I~T.~D.

pREDPOLOZHIM, CHTO V MOMENT~$t=0$ SNEGOOCHISTITELX NACHINAET
MODELIROVATX PROCESS NATURALXNOGO VYBORA, I DOPUSTIM, CHTO ZA $T$~EDINIC
VREMENI POZADI NEGO UPADUT ROVNO $P$~SNEZHINOK. v |TOT MOMENT VTOROJ
SNEGOOCHISTITELX NACHINAET TOT ZHE PUTX, ZANIMAYA V MOMENT VREMENI~$t+T$ TO
ZHE POLOZHENIE, CHTO ZANIMAL PERVYJ SNEGOOCHISTITELX V MOMENT~$t$. v KONCE
KONCOV, K MOMENTU~$\kappa T$ POZADI PERVOGO SNEGOOCHISTITELYA UPADUT ROVNO
$P'$~SNEZHINOK; ON MGNOVENNO OCHISHCHAET OSTATOK DOROGI I ISCHEZAET.

iSPOLXZUYA |TU MODELX DLYA INTERPRETACII NATURALXNOGO VYBORA, POKAZHITE, CHTO
DLINA OTREZKA~$e^\theta F(\kappa) P$ POLUCHAETSYA PRI
$$
P'/P=k+1+e^\theta\left(\kappa F(\kappa)-\sum_{0\le j \le \kappa}F(\kappa-j)\right).
$$

\ex[vm35] pREDYDUSHCHEE UPRAZHNENIE ANALIZIRUET NATURALXNYJ VYBOR V TOM SLUCHAE,
 KOGDA ZAPISI IZ REZERVUARA VSEGDA CHITAYUTSYA V TOM ZHE PORYADKE, V KOTOROM
ONI ZAPISYVALISX: "PERVYM VKLYUCHAETSYA---PERVYM ISKLYUCHAETSYA". oCENITE DLINU
OTREZKOV, KOTORAYA POLUCHILASX BY, ESLI BY SODERZHIMOE REZERVUARA, OSTAVSHEESYA
OT PREDYDUSHCHEGO OTREZKA, CHITALOSX V SOVERSHENNO \emph{SLUCHAJNOM} PORYADKE,
KAK ESLI BY ZAPISI V REZERVUARE TSHCHATELXNO PEREMESHIVALISX MEZHDU OTREZKAMI.

\ex[vm39] cELX |TOGO UPRAZHNENIYA---ANALIZ POSLEDSTVIJ, VYZVANNYH SLUCHAJNYM
IZMENENIEM NAPRAVLENIYA UPORYADOCHENIYA OTREZKOV V VYBORE S ZAMESHCHENIEM.
%%316
\medskip
\item{a)}~pUSTX~$g_P(z_1, z_2,~\ldots, z_k)$---TA ZHE PROIZVODYASHCHAYA FUNKCIYA,
CHTO I V TEOREME~K, NO DLYA KAZHDOGO IZ $k$~OTREZKOV OPREDELENO, YAVLYAETSYA LI
ON VOZRASTAYUSHCHIM ILI UBYVAYUSHCHIM. nAPRIMER, MY MOZHEM SCHITATX, CHTO VSE
OTREZKI S NECHETNYMI NOMERAMI VOZRASTAYUSHCHIE, A S CHETNYMI UBYVAYUSHCHIE pOKAZHITE,
 CHTO TEOREMA~K SPRAVEDLIVA DLYA KAZHDOJ IZ $2^k$~PROIZVODYASHCHIH FUNKCIJ
TAKOGO VIDA.

\item{b)}~v SILU~(a) MOZHNO SCHITATX~$P=1$. mOZHNO TAKZHE PREDPOLOZHITX,
CHTO ISHODNOJ YAVLYAETSYA RAVNOMERNO RASPREDELENNAYA POSLEDOVATELXNOSTX
NEZAVISIMYH SLUCHAJNYH VELICHIN, ZAKLYUCHENNYH MEZHDU~0 I~1 pUSTX
$$
a(x,y)=\cases{
e^{1-x}-e^{y-x}, & ESLI~$x\le y$;\cr
e^{1-x},               & ESLI~$x>y$.\cr
}
$$
pUSTX~$f(x)\,dx$---VEROYATNOSTX TOGO, CHTO OPREDELENNYJ VOZRASTAYUSHCHIJ OTREZOK
NACHINAETSYA S~$x$. dOKAZHITE, CHTO~$\left(\int_0^1a(x,y) f(x)\,dx\right)\,dy$
ESTX VEROYATNOSTX TOGO, CHTO SLEDUYUSHCHIJ OTREZOK NACHINAETSYA S~$y$.
[\emph{uKAZANIE:} RASSMOTRITE DLYA KAZHDOGO~$n\ge0$ VEROYATNOSTX TOGO,
CHTO~$x\le X_1\le\ldots\le X_n >y$ PRI DANNYH~$x$ I~$y$.]

\item{c)}~rASSMOTRITE OTREZKI, MENYAYUSHCHIE NAPRAVLENIE UPORYADOCHENIYA S
VEROYATNOSTXYU~$p$, DRUGIMI SLOVAMI, NAPRAVLENIE KAZHDOGO OTREZKA, KROME
PERVOGO, SOVPADAET S NAPRAVLENIEM PREDYDUSHCHEGO OTREZKA S
VEROYATNOSTXYU~$q=1-p$ I PROTIVOPOLOZHNO EMU S VEROYATNOSTXYU~$p$. (tAKIM
OBRAZOM, ESLI~$p=0$, TO VSE OTREZKI IMEYUT ODINAKOVOE NAPRAVLENIE;
ESLI~$p=1$, NAPRAVLENIE OTREZKOV CHEREDUETSYA, A PRI~$p=1/2$ OTREZKI
SLUCHAJNYE I NEZAVISIMYE) pUSTX
$$
f_1(x)=1,\quad
f_{n+1}(y)=p\int_0^1a(x,y)f_n(1-x)\,dx+q\int_0^1a(x,y)f_n(x)\,dx.
$$
pOKAZHITE, CHTO VEROYATNOSTX TOGO, CHTO $n\hbox{-J}$~OTREZOK NACHINAETSYA S~$x$,
ESTX~$f_n(x)\,dx$, ESLI $(n-1)\hbox{-J}$~OTREZOK VOZRASTAYUSHCHIJ,
I~$f_n(1-x)\,dx$, ESLI $(n-1)\hbox{-J}$~OTREZOK UBYVAYUSHCHIJ.

\item{d)}~nAJDITE RESHENIE~$f$ DLYA URAVNENIYA "USTANOVIVSHEGOSYA REZHIMA"
$$
f(y)=p\int_0^1a(x,y)f(1-x)\,dx+q\int_0^1a(x,y)f(x)\,dx,\quad \int_0^1f(x)\,dx=1.
$$
[\emph{uKAZANIE:} POKAZHITE, CHTO~$f''(x)$ NE ZAVISIT OT~$x$.]

\item{e)}~pOKAZHITE, CHTO POSLEDOVATELXNOSTX~$f''(x)$ CHASTI~(c) VESXMA
BYSTRO SHODITSYA K FUNKCII~$f(x)$ CHASTI~(d).

\item{f)}~pOKAZHITE, CHTO SREDNYAYA DLINA VOZRASTAYUSHCHEGO OTREZKA,
NACHINAYUSHCHEGOSYA S~$x$, RAVNA~$e^{1-x}$.

\item{g)}~nAKONEC, OB®EDINITE VSE PREDYDUSHCHIE REZULXTATY I DOKAZHITE
SLEDUYUSHCHUYU TEOREMU. \dfn{eSLI NAPRAVLENIYA POSLEDOVATELXNYH OTREZKOV PRI
VYBORE S ZAMESHCHENIEM NEZAVISIMO IZMENYAYUTSYA NA PROTIVOPOLOZHNYE S
VEROYATNOSTXYU~$p$, TO SREDNYAYA DLINA OTREZKA STREMITSYA K~$(6/(3+p))P$.} (eTA
TEOREMA PRI~$p=1$  VPERVYE BYLA DOKAZANA kNUTOM [{\sl CACM,\/} {\bf 6}
(1963), 685--688]; PRI~$p=1/2$ EE DOKAZAL e.~g.~kONHEJM V~1978~G.)

\ex[vm40]rASSMOTRITE SLEDUYUSHCHUYU PROCEDURU.
{\medskip\narrower
%!!! OPREDELITX STILX, SVYAZANNYJ S ALGORITMOM
\item{N1.}~pROCHITATX ZAPISX, POMESTIV EE V REZERVUAR EMKOSTXYU V ODNO SLOVO.
 zATEM PROCHITATX SLEDUYUSHCHUYU ZAPISX~|R|, I PUSTX~|K| BUDET EE KLYUCHOM.
%
\item{N2.} vYVESTI SODERZHIMOE REZERVUARA, USTANOVITX~|LASTKEY| RAVNYM EGO
KLYUCHU I OPUSTOSHITX REZERVUAR.
%
\item{N3.}~eSLI~$|K|<|LASTKEY|$, TO VYVESTI~|R|,
USTANOVITX~$|LASTKEY|\asg |K|$ I PEREJTI K~N5.
%%317
\item{N4.}~eSLI REZERVUAR NE PUST, VERNUTXSYA K~N2; V PROTIVNOM SLUCHAE
POMESTITX~|R|
V REZERVUAR.
%
\item{N5.}~pROCHITATX NOVUYU ZAPISX~|R| I USTANOVITX~|K| RAVNYM EE KLYUCHU. pEREJTI
K~N3.
\endmark\medskip}

eTA PROCEDURA, V SUSHCHNOSTI, |KVIVALENTNA NATURALXNOMU VYBORU
S~$P=1$ I~$P'=1$ ILI~$P'=2$ (V ZAVISIMOSTI OT TOGO, V KAKOJ MOMENT MY
OPUSTOSHAEM REZERVUAR---KAK TOLXKO ON ZAPOLNITSYA ILI KOGDA NAM NADO BUDET
ZAPISATX. V ZAPOLNENNYJ REZERVUAR NOVYJ |LEMENT, PEREPOLNYAYUSHCHIJ EGO), ZA
ISKLYUCHENIEM TOGO, CHTO |TA PROCEDURA POROZHDAET \emph{UBYVAYUSHCHIE} OTREZKI I
NIKOGDA NE OSTANAVLIVAETSYA. eTI OTKLONENIYA NE PRINOSYAT VREDA, ONI UDOBNY
DLYA NASHEJ CELI.

dEJSTVUYA, KAK V UPR.~24, OBOZNACHIM CHEREZ~$f_n(x, y)\,dy\,dx$ VEROYATNOSTX
TOGO, CHTO $(x, y)$~SUTX ZNACHENIYA~$(|LASTKEY|,|K|)$ SOOTVETSTVENNO SRAZU ZHE
POSLE $n\hbox{-GO}$~VYPOLNENIYA SHAGA~N2. dOKAZHITE, CHTO SUSHCHESTVUET
FUNKCIYA~$g_n(x)$ OT ODNOJ PEREMENNOJ, TAKAYA, CHTO~$f_n(x, y)=g_n(x)$,
ESLI~$x<y$, I~$f_n(x, y)=g_n(x)-e^{-y}(g_n(x)-g_n(y))$, ESLI~$x>y$.
fUNKCIYA~$g_n(x)$ OPREDELYAETSYA SOOTNOSHENIYAMI~$g_1(x)=1$,
$$
g_{n+1}(x)=\int_0^x e^ug_n(u)\,du+\int_0^x dv\,(v+1)
\int_v^1du\, ((e^v-1)g_n(u)+g_n(v))+
+x\int_x^1dv\,\int_v^1 du\,((e^v-1)g_n(u)+g_n(v)).
$$
pOKAZHITE DALEE, CHTO OZHIDAEMAYA DLINA $n\hbox{-GO}$~OTREZKA RAVNA
$$
\int_0^1\,dx\int_0^x\,dy(g_n(x)(e^y-1)+g_n(y))\left(2-{1\over2}y^2\right)
+\int_0^1dx\,(1-x)g_n(x)e^x.
$$
[\emph{zAMECHANIE.} rESHENIE |TOGO URAVNENIYA V USTANOVIVSHEMSYA REZHIME
OKAZYVAETSYA OCHENX SLOZHNYM; ONO BYLO CHISLENNO NAJDENO dZH.~mAK-kENNOJ. oN
POKAZAL, CHTO DLINA OTREZKA STREMITSYA K PREDELXNOMU ZNACHENIYU~2.61307209.
tEOREMA~K NE PRIMENIMA K NATURALXNOMU VYBORU, TAK CHTO SLUCHAJ~$P=1$ NELXZYA
RASPROSTRANITX NA DRUGIE~$P$.]

\ex[m33] rASSMATRIVAYA ALGORITM UPR.~25 KAK OPREDELENIE NATURALXNOGO VYBORA
DLYA~$P'=1$, NAJDITE SREDNYUYU DLINU \emph{PERVOGO} OTREZKA DLYA~$P'=r$
PRI LYUBOM~$r\ge0$ PO SLEDUYUSHCHEJ SHEME:
\medskip
\item{a)}~pOKAZHITE, CHTO PERVYJ OTREZOK IMEET DLINU~$n$ S VEROYATNOSTXYU
$$
(n+r)\stir{n+r}{n}\Big/(n+r+1)!.
$$

\item{b)}~oPREDELIM "CHISLA sTIRLINGA VTOROGO PORYADKA"~$\Stir{n}{m}$ PRAVILAMI
$$
\Stir{0}{m}=\delta_{m0},\quad
\Stir{n}{m}=(n+m-1)\left(\Stir{n-1}{m}+\Stir{n-1}{m-1}\right)\rem{PRI $n>0$.}
$$
dOKAZHITE, CHTO
$$
\stir{n+r}{n}=\sum_{0\le k \le r}\perm{n+r}{k+r}\Stir{r}{k}.
$$
%%318
\item{c)}~dOKAZHITE, CHTO SREDNYAYA DLINA PERVOGO OTREZKA BUDET, SLEDOVATELXNO,
 $c_re-r-1$, GDE
$$
c_r=\sum_{0\le k \le r}\left[\left[{r\atop k}\right]\right] (r+k+1)/(r+k)!.
$$

\ex[25] v TEKSTE RASSMATRIVAETSYA TOLXKO SLUCHAJ SORTIROVKI
ZAPISEJ FIKSIROVANNOGO RAZMERA. kAK RAZUMNYM OBRAZOM PRISPOSOBITX VYBOR S
ZAMESHCHENIEM K ZAPISYAM \emph{PEREMENNOJ DLINY?}

\subsubchap{mNOGOFAZNOE SLIYANIE} %5.4.2
tEPERX, POSLE TOGO KAK MY VYYASNILI, KAK MOZHNO OBRAZOVATX NACHALXNYE OTREZKI,
 RASSMOTRIM RAZLICHNYE METODY RASPREDELENIYA  OTREZKOV PO LENTAM I SLIYANIYA
IH DO TEH POR, POKA NE POLUCHITSYA EDINSTVENNYJ OTREZOK.

pREDPOLOZHIM SNACHALA, CHTO V NASHEM RASPORYAZHENII IMEYUTSYA TRI LENTOCHNYH
USTROJSTVA: $T1$, $T2$ I~$T3$; MOZHNO VOSPOLXZOVATXSYA SBALANSIROVANNYM
SLIYANIEM, OPISANNYM V NACHALE~\S~5.4, DLYA~$P=2$ I~$T=3$. oNO PRINIMAET
SLEDUYUSHCHIJ VID:
%% !!! OPREDELITX STILX, SVYAZANNYJ S ALGORITMOM
{\medskip\narrower
\item{B1.}~rASPREDELITX NACHALXNYE OTREZKI POPEREMENNO NA LENTY~$T1$ I~$T2$.

\item{B2.}~sLITX OTREZKI S LENT~$T1$ I~$T2$ NA~$T3$; ZATEM OSTANOVITXSYA,
 ESLI~$T3$ SODERZHIT TOLXKO ODIN OTREZOK.

\item{B3.}~sKOPIROVATX OTREZKI S~$T3$ POPEREMENNO NA~$T1$ I~$T2$,
ZATEM VERNUTXSYA K SHAGU~B2.\endmark
\medskip\noindent}
eSLI NACHALXNOE RASPREDELENIE DALO 5~OTREZKOV, TO PERVYJ PROHOD SLIYANIYA
PRIVEDET K $\ceil{S/2}$~OTREZKAM NA~$T3$, VTOROJ---K~$\ceil{S/4}$ I~T.~D.
tAKIM OBRAZOM, ESLI, SKAZHEM, $17\le S \le 32$, TO PROIZOJDET 1~PROHOD
RASPREDELENIYA, 5~PROHODOV SLIYANIYA I 4~PROHODA KOPIROVANIYA; V OBSHCHEM
SLUCHAE PRI~$S>1$ CHISLO PROHODOV PO VSEM DANNYM BUDET RAVNO~$2
\ceil{\log_2 S}$.

pROHODY KOPIROVANIYA V |TOJ PROCEDURE NEZHELATELXNY, TAK KAK ONI NE
UMENXSHAYUT CHISLA OTREZKOV. mOZHNO OBOJTISX POLOVINOJ KOPIROVANIJ, ESLI
ISPOLXZOVATX \emph{DVUHFAZNUYU} PROCEDURU:
%% !!! OPREDELITX STILX, SVYAZANNYJ S ALGORITMOM
{\medskip\narrower
\item{A1.}~rASPREDELITX NACHALXNYE OTREZKI POPEREMENNO NA LENTY~$T1$  I~$T2$.

\item{A2.}~sLITX OTREZKI S LENT~$T1$ I~$T2$ NA~$T3$; OSTANOVITXSYA, ESLI
$T3$~SODERZHIT TOLXKO ODIN OTREZOK.

\item{A3.}~sKOPIROVATX \emph{POLOVINU} OTREZKOV S~$T3$ NA~$T1$.

\item{A4.}~sLITX OTREZKI S LENT~$T1$ I~$T3$ NA~$T2$; OSTANOVITXSYA, ESLI
$T2$~SODERZHIT TOLXKO ODIN OTREZOK.

\item{A5.}~sKOPIROVATX \emph{POLOVINU} OTREZKOV S~$T2$ NA~$T1$. vERNUTXSYA
K SHAGU~A2. \endmark
\medskip\noindent}
chISLO PROHODOV PO VSEM DANNYM SOKRATILOSX
DO~${3\over2}\ceil{\log_2 S}+{1\over2}$,
%%319
\bye