\input style
\chapno=5\subchno=4\subsubchno=3\chapnotrue
kASKADNOE SLIYANIE, PODOBNO MNOGOFAZNOMU, NACHINAETSYA S
"TOCHNOGO RASPREDELENIYA" OTREZKOV PO LENTAM, HOTYA PRAVILA TOCHNOGO
RASPREDELENIYA OTLICHNY OT PRAVIL P.~5.4.2. kAZHDAYA STROKA
TABLICY PREDSTAVLYAET POLNYJ PROHOD PO \emph{VSEM} DANNYM. pROHOD~2,
NAPRIMER, POLUCHAETSYA POSREDSTVOM VYPOLNENIYA PYATIPUTEVOGO SLIYANIYA S~T1,
T2, T3, T4, T5 NA~T6, POKA~T5 NE STANET PUSTOJ (PRI |TOM NA~T6 POMESHCHAYUTSYA
15~OTREZKOV OTNOSITELXNOJ DLINY~5), ZATEM CHETYREHPUTEVOGO SLIYANIYA S~T1, T2,
T3, T4 NA~T5, ZATEM TREHPUTEVOGO SLIYANIYA NA~T4, DVUHPUTEVOGO SLIYANIYA
NA~T3 I, NAKONEC, ODNOPUTEVOGO SLIYANIYA (OPERACII KOPIROVANIYA) S~T1
NA~T2. pROHOD~3 POLUCHAETSYA TAKIM ZHE OBRAZOM PUTEM VYPOLNENIYA SNACHALA
PYATIPUTEVOGO SLIYANIYA, POKA ODNA LENTA NE STANET PUSTOJ, ZATEM
CHETYREHPUTEVOGO I~T.~D. (pOHOZHE, CHTO |TOMU PUNKTU KNIGI SLEDOVALO BY
PRISVOITX NOMER~5.4.3.2.1, A NE~5.4.3!)
yaSNO, CHTO OPERACII KOPIROVANIYA IZLISHNI, I IH MOZHNO BYLO BY OPUSTITX.
fAKTICHESKI, ODNAKO, V SLUCHAE SHESTI LENT |TO KOPIROVANIE ZANIMAET TOLXKO
NEBOLXSHOJ PROCENT VSEGO VREMENI. eLEMENTY, KOTORYE POLUCHAYUTSYA PROSTYM
KOPIROVANIEM, OTMECHENY V PRIVEDENNOJ TABLICE ZVEZDOCHKOJ. tOLXKO~25 IZ~950
OBRABATYVAEMYH OTREZKOV PRINADLEZHAT |TOMU KLASSU. bOLXSHAYA CHASTX
VREMENI OTVODITSYA PYATIPUTEVOMU I CHETYREHPUTEVOMU SLIYANIYAM.
nA PERVYJ VZGLYAD MOZHET POKAZATXSYA, CHTO KASKADNAYA SHEMA---DOVOLXNO PLOHOJ
VARIANT V SRAVNENII S MNOGOFAZNOJ, TAK KAK STANDARTNAYA MNOGOFAZNAYA SHEMA
ISPOLXZUET VSE VREMYA $(T-1)\hbox{-PUTEVOE}$ SLIYANIE, V TO VREMYA KAK
KASKADNAYA ISPOLXZUET $(T-1)\hbox{-PUTEVOE}$, $(T-2)\hbox{-PUTEVOE}$,
$(T-3)\hbox{-PUTEVOE}$ I~T.~D., NO V DEJSTVITELXNOSTI ONA ASIMPTOTICHESKI
\emph{LUCHSHE,} CHEM MNOGOFAZNAYA, DLYA SHESTI I BOLEE LENT! kAK MY VIDELI V
P.~5.4.2, VYSOKIJ PORYADOK SLIYANIYA NE YAVLYAETSYA GARANTIEJ |FFEKTIVNOSTI. v
TABL.~1 POKAZANY HARAKTERISTIKI VYPOLNENIYA KASKADNOGO SLIYANIYA PO
ANALOGII S PODOBNOJ TABLICEJ P.~5.4.2.
nETRUDNO VYVESTI "TOCHNYE RASPREDELENIYA" DLYA KASKADNOGO SLIYANIYA. dLYA SHESTI
LENT IMEEM
$$
\matrix{
\hbox{uROVENX} & T1 & T2 & T3 & T4 & T5 \cr
0 & 1 & 0 & 0 & 0 & 0 \cr
1 & 1 & 1 & 1 & 1 & 1 \cr
2 & 5 & 4 & 3 & 2 & 1 \cr
3 & 15 & 14 & 12 & 9 & 6 \cr
4 & 55 & 50 & 41 & 29 & 15 \cr
5 & 190 & 175 & 146 & 105 & 55 \cr
\multispan{6}\dotfill\cr
n & a_n & b_n & c_n & d_n & e_n \cr
n+1 & a_n+b_n+c_n+d_n+e_n & a_n+b_n+c_n+d_n & a_n+b_n+c_n & a_n+b_n & a_n \cr
}
\eqno(1)
$$
%%344
\htable{tABLICA 1}%
{hARAKTER POVEDENIYA KASKADNOGO SLIYANIYA}%
{\strut\hfill # && \bskip\hfill$#$\hfill\bskip\cr
lENTY & \hbox{pROHODY} & \hbox{pROHODY} & \hbox{oTNOSHENIE}\cr
& \hbox{(S KOPIROVANIEM)} & \hbox{(BEZ KOPIROVANIYA)} &\hbox{ROSTA}\cr
\noalign{\hrule}
3 & 2.078\ln S+0.672 & 1.504\ln S+0.992 & 1.6180340\cr
4 & 1.235\ln S+0.754 & 1.102\ln S+0.820 & 2.2469796\cr
5 & 0.946\ln S+0.796 & 0.897\ln S+0.800 & 2.8793852\cr
6 & 0.796\ln S+0.821 & 0.773\ln S+0.808 & 3.5133371\cr
7 & 0.703\ln S+0.839 & 0.691\ln S+0.822 & 4.1481149\cr
8 & 0.639\ln S+0.852 & 0.632\ln S+0.834 & 4.7833861\cr
9 & 0.592\ln S+0.861 & 0.587\ln S+0.845 & 5.4189757\cr
10 & 0.555\ln S+0.869 & 0.552\ln S+0.854 & 6.0547828\cr
20 & 0.397\ln S+0.905 & 0.397\ln S+0.901 & 12.4174426\cr
\noalign{\hrule}
}
oTMETIM INTERESNOE SVOJSTVO |TIH CHISEL---IH OTNOSITELXNYE VELICHINY YAVLYAYUTSYA
TAKZHE I DLINAMI DIAGONALEJ PRAVILXNOGO $(2T-1)\hbox{-UGOLXNIKA}$. nAPRIMER,
PYATX DIAGONALEJ ODINNADCATIUGOLXNIKA NA RIS.~73 IMEYUT OTNOSITELXNYE DLINY,
OCHENX BLIZKIE K~190, 175, 146, 105 I~55! mY DOKAZHEM |TOT ZAMECHATELXNYJ FAKT
\picture{rIS.~73. gEOMETRICHESKAYA INTERPRETACIYA KASKADNYH CHISEL.}
POZDNEE V |TOM PUNKTE, A TAKZHE UVIDIM, CHTO OTNOSITELXNYE VREMENA,
ZATRACHIVAEMYE NA $(T-1)\hbox{-PUTEVOE}$ SLIYANIE, $(T-2)\hbox{-PUTEVOE}$
SLIYANIE,~\dots, ODNOPUTEVOE SLIYANIE, PRIBLIZITELXNO PROPORCIONALXNY
\emph{KVADRATAM} DLIN |TIH DIAGONALEJ.
\section *nACHALXNOE RASPREDELENIE OTREZKOV. eSLI CHISLO NACHALXNYH
OTREZKOV V DEJSTVITELXNOSTI NE ESTX CHISLO fIBONACHCHI, MY MOZHEM,
KAK OBYCHNO, VSTAVITX FIKTIVNYE OTREZKI. pOVERHNOSTNYJ ANALIZ SITUACII
POKAZYVAET, CHTO METOD PRIPISYVANIYA FIKTIVNYH OTREZKOV NESUSHCHESTVEN, TAK
KAK KASKADNOE SLIYANIE VSEGDA OSUSHCHESTVLYAET
%%345
POLNYE PROHODY; ESLI IMEETSYA 190~NACHALXNYH OTREZKOV, TO KAZHDAYA ZAPISX
OBRABATYVAETSYA PYATX RAZ, KAK V PRIVEDENNOM VYSHE PRIMERE, NO ESLI IMEETSYA
191~OTREZOK, TO, OCHEVIDNO, SLEDUET UVELICHITX UROVENX, I TEPERX KAZHDAYA
ZAPISX BUDET OBRABATYVATXSYA SHESTX RAZ. k SCHASTXYU, V DEJSTVITELXNOSTI MOZHNO
IZBEZHATX TAKOGO REZKOGO SKACHKA. d|VID~e.~fERGYUSON NASHEL SPOSOB TAK
RASPREDELITX NACHALXNYE OTREZKI, CHTO MNOGIE OPERACII VO VREMYA PERVOJ
\picture{
rIS.~74. eFFEKTIVNOSTX KASKADNOGO SLIYANIYA S RASPREDELENIEM
PO ALGORITMU~D.
}
FAZY SLIYANIYA SVODYATSYA K KOPIROVANIYU SODERZHIMOGO LENTY. eSLI OBOJTI TAKIE
KOPIROVANIYA (PROSTO IZMENIV "LOGICHESKIE" NOMERA LENTOCHNYH USTROJSTV PO
OTNOSHENIYU K "FIZICHESKIM" NOMERAM, KAK V ALGORITME~5.4.2D), TO POLUCHIM
OTNOSITELXNO PLAVNYJ PEREHOD S UROVNYA NA UROVENX, KAK IZOBRAZHENO NA RIS.~74.
pREDPOLOZHIM, CHTO $(a, b, c, d, e)$, GDE~$a\ge b \ge c \ge d \ge e$---TOCHNOE
RASPREDELENIE. pEREOPREDELIV SOOTVETSTVIE MEZHDU LOGICHESKIMI
I FIZICHESKIMI LENTOCHNYMI USTROJSTVAMI, MY MOZHEM PREDSTAVITX, CHTO REALXNOE
RASPREDELENIE---|TO~$(e, d, c, b, a)$,
%%346
T.~E.~$a$~OTREZKOV NA~T5, $b$~NA~t4 I~T.~D. sLEDUYUSHCHEE TOCHNOE
RASPREDELENIE---|TO $(a+b+c+d+e, a+b+c+d, a+b+c, a+b, a)$;
I ESLI VVOD ISCHERPYVAETSYA PREZHDE, CHEM MY DOSTIGAEM |TOGO SLEDUYUSHCHEGO
UROVNYA, TO BUDEM SCHITATX, CHTO LENTY SODERZHAT
SOOTVETSTVENNO~$(D_1, D_2, D_3, D_4, D_5)$ FIKTIVNYH OTREZKOV, GDE
$$
\displaynarrow{
D_1 \le a+b+c+d,\quad D_1 \le a+b+c,\quad D_3\le a+b,\cr
D_4 \le a,\quad D_5=0;\qquad D_1\ge D_2 \ge D_3 \ge D_4 \ge D_5.\cr
}
\eqno(2)
$$
mY VOLXNY PREDSTAVLYATX SEBE, CHTO |TI FIKTIVNYE OTREZKI POYAVLYAYUTSYA NA
LENTAH V LYUBOM UDOBNOM MESTE. pREDPOLAGAETSYA, CHTO PERVYJ PROHOD SLIYANIYA
DAST $a$~OTREZKOV POSREDSTVOM PYATIPUTEVOGO SLIYANIYA, ZATEM $b$~OTREZKOV
POSREDSTVOM CHETYREHPUTEVOGO I~T.~D. nASHA CELX SOSTOIT V RASPOLOZHENII
FIKTIVNYH OTREZKOV TAKIM OBRAZOM, CHTOBY ZAMENITX SLIYANIE KOPIROVANIEM.
uDOBNO VYPOLNYATX PERVYJ PROHOD SLIYANIYA SLEDUYUSHCHIM OBRAZOM:
1.~eSLI~$D_4=a$, TO VYCHESTX~$a$ IZ VSEH~$D_1$, $D_2$, $D_3$, $D_4$ I
ZAYAVITX, CHTO~T5---REZULXTAT SLIYANIYA. eSLI~$D_4<a$, TO SLITX $a$~OTREZKOV S
LENT~T1 PO~T5, ISPOLXZUYA MINIMALXNO VOZMOZHNOE CHISLO FIKTIVNYH OTREZKOV
NA LENTAH~T1--T5 TAK, CHTOBY NOVYE ZNACHENIYA~$D_1$, $D_2$, $D_3$, $D_4$
UDOVLETVORYALI SOOTNOSHENIYAM
$$
\displaynarrow{
D_1\le b+c+d,\quad D_2\le b+c,\quad D_3\le b,\cr
D_4=0;\qquad D_1\ge D_2\ge D_3\ge D_4.\cr
}
\eqno(3)
$$
tAKIM OBRAZOM, ESLI~$D_2$ BYLO PERVONACHALXNO~$\le b+c$, TO MY
NE ISPOLXZUEM NI ODNOGO FIKTIVNOGO OTREZKA S |TOJ LENTY NA DANNOM SHAGE; V
TO ZHE VREMYA, ESLI~$b+c<D_2\le a+b+c$, MY ISPOLXZUEM ROVNO~$D_2-b-c$
FIKTIVNYH OTREZKOV.
2.~(eTOT SHAG ANALOGICHEN SHAGU~1, NO S NEKOTORYM "SDVIGOM".) eSLI~$D_3=b$,
TO VYCHESTX~$b$ IZ VSEH~$D_1$, $D_2$, $D_3$ I ZAYAVITX, CHTO~T4---REZULXTAT
SLIYANIYA. eSLI~$D_3<b$, TO SLITX $b$~OTREZKOV S LENT~T1--T4, UMENXSHAYA, ESLI
NEOBHODIMO, CHISLO FIKTIVNYH OTREZKOV, CHTOBY DOSTICHX
$$
D_1\le b+c,\quad D_2\le b,\quad D_3=0;\qquad D_1\ge D_2\ge D_3.
$$
3.~i TAK DALEE.
mETOD fERGYUSONA RASPREDELENIYA OTREZKOV PO LENTAM MOZHNO PROILLYUSTRIROVATX,
RASSMOTREV PROCESS PEREHODA S UROVNYA~3 NA UROVENX~4 V~(1). dOPUSTIM, CHTO
"LOGICHESKIE" LENTY (T1,~\dots, T5) SODERZHALI SOOTVETSTVENNO
$(5, 9, 12, 14, 15)$~OTREZKOV I CHTO MY HOTIM DOVESTI |TO V KONECHNOM ITOGE
DO~$(55, 50, 41, 29, 15)$. eTA PROCEDURA MOZHET BYTX KRATKO ZAPISANA TAK:
%%347
\ctable{
$#$\hfill&&\hfill\bskip$#$\bskip\hfill\cr
& \hbox{dOBAVITX} &\hbox{dOBAVITX} &\hbox{dOBAVITX} &\hbox{dOBAVITX} &\hbox{dOBAVITX} &\hbox{s|KONOMLENNAYA}\cr
\hbox{shAG} &\hbox{K T1} &\hbox{K T2} &\hbox{K T3} &\hbox{K T4} &\hbox{K T5} &\hbox{VELICHINA}\cr
(1, 1)& 9 & 0 & 0 & 0 & 0 & 15+14+12+5\cr
(2, 2)& 3 & 12 & 0 & 0 & 0 & 15+14+9+5\cr
(2, 1)& 9 & 0 & 0 & 0 & 0 & 15+14+5\cr
(3, 3)& 2 & 2 & 14 & 0 & 0 & 15+12+5\cr
(3, 2)& 3 & 12 & 0 & 0 & 0 & 15+9+5\cr
(3, 1)& 9 & 0 & 0 & 0 & 0 & 15+5\cr
(4, 4)& 1 & 1 & 1 & 15 & 0 & 14+5\cr
(4, 3)& 2 & 2 & 14 & 0 & 0 & 12+5\cr
(4, 2)& 3 & 12 & 0 & 0 & 0 & 9+5\cr
(4, 1)& 9 & 0 & 0 & 0 & 0 & 5\cr
}
sNACHALA POMESHCHAEM DEVYATX OTREZKOV NA~T1, ZATEM $(3, 12)$---NA~T1 I~T2 I~T.~D.
eSLI VVOD ISCHERPAETSYA, SKAZHEM, VO VREMYA SHAGA~$(3, 2)$, TO "S|KONOMLENNAYA
VELICHINA" SOSTAVLYAET~$15+9+5$. eTO OZNACHAET, CHTO MY IZBEGAEM PYATIPUTEVOGO
SLIYANIYA 15~OTREZKOV, DVUHPUTEVOGO SLIYANIYA 9~OTREZKOV I ODNOPUTEVOGO
SLIYANIYA 5~OTREZKOV POSREDSTVOM PRISVOENIYA FIKTIVNYH OTREZKOV.
dRUGIMI SLOVAMI, $15+9+5$ OTREZKOV, PRISUTSTVUYUSHCHIH NA UROVNE~3,
NE OBRABATYVAYUTSYA V TECHENIE PERVOJ FAZY SLIYANIYA.
sLEDUYUSHCHIJ ALGORITM DETALXNO OPISYVAET |TOT PROCESS.
\alg C.(sORTIROVKA KASKADNYM SLIYANIEM SO SPECIALXNYM RASPREDELENIEM.) eTOT
ALGORITM RASPREDELYAET NACHALXNYE OTREZKI PO LENTAM OTREZOK ZA OTREZKOM,
POKA ZAPAS NACHALXNYH OTREZKOV NE ISCHERPAETSYA. zATEM ON OPREDELYAET, KAK
SLEDUET SLIVATX LENTY, PREDPOLAGAYA, CHTO IMEETSYA $T\ge 3$~LENTOPROTYAZHNYH
USTROJSTV, PRI |TOM ISPOLXZUETSYA SAMOE BOLXSHEE
$(T-1)\hbox{-PUTEVOE}$~SLIYANIE I
NENUZHNYE ODNOPUTEVYE SLIYANIYA USTRANYAYUTSYA. lENTA~$T$ MOZHET
BYTX ISPOLXZOVANA DLYA HRANENIYA VVODA, TAK KAK NA NEE NE POPADAET NI ODIN
NACHALXNYJ OTREZOK. aLGORITM RABOTAET SO SLEDUYUSHCHIMI MASSIVAMI:
{\let\mypar=\par\ctable{
$#$,\bskip\hfill&$#$:\bskip\hfill&
\vtop{\parindent=0pt \hsize=13cm #\mypar}\cr
|A|[j] & 1 \le j \le T &
pOSLEDNEE TOCHNOE KASKADNOE RASPREDELENIE, KOTOROE BYLO DOSTIGNUTO. \cr
|AA|[j] & 1 \le j \le T &
tOCHNOE KASKADNOE RASPREDELENIE, K KOTOROMU MY STREMIMSYA. \cr
|D|[j] & 1 \le j \le T &
chISLO FIKTIVNYH OTREZKOV, PREDPOLAGAEMYH PRISUTSTVUYUSHCHIMI NA LOGICHESKOM
LENTOPROTYAZHNOM USTROJSTVE S NOMEROM~$j$. \cr
|M|[j] & 1 \le j \le T &
mAKSIMALXNOE CHISLO FIKTIVNYH OTREZKOV, KOTOROE ZHELATELXNO IMETX NA
LOGICHESKOM LENTOPROTYAZHNOM USTROJSTVE S NOMEROM~$j$. \cr
|TAPE|[j] & 1 \le j \le T &
nOMER FIZICHESKOGO LENTOPROTYAZHNOGO USTROJSTVA, SOOTVETSTVUYUSHCHEGO
LOGICHESKOMU LENTOPROTYAZHNOMU USTROJSTVU S NOMEROM~$j$.\cr
}}
%%348
\st[nACHALXNAYA USTANOVKA.] uSTANOVITX $|A|[k]\asg |AA|[k]\asg |D|[k]\asg 0$
PRI~$2\le k \le T$; USTANOVITX $|A|[1]\asg 0$, $|AA|[1]\asg 1$,
$|D|[1]\asg 1$; USTANOVITX~$|TAPE|[k]\asg k$ PRI~$1\le k \le T$. nAKONEC,
USTANOVITX~$i\asg T-2$, $j\asg 1$, $k\asg 1$, $l\asg 0$, $m\asg 1$ I
PEREJTI K SHAGU~\stp{5} (|TI MANEVRY YAVLYAYUTSYA ODNIM IZ SPOSOBOV NACHATX
RABOTU NEPOSREDSTVENNO VO VNUTRENNEM CIKLE S SOOTVETSTVUYUSHCHEJ USTANOVKOJ
UPRAVLYAYUSHCHIH PEREMENNYH).
\st[nACHATX NOVYJ UROVENX.] (mY TOLXKO CHTO POLUCHILI TOCHNOE RASPREDELENIE.
nO TAK KAK ESHCHE IMEYUTSYA ISHODNYE DANNYE, TO NEOBHODIMO PODGOTOVITXSYA K
SLEDUYUSHCHEMU UROVNYU.) uVELICHITX~$l$ NA~1. uSTANOVITX~$|A|[k]\asg |AA|[k]$
PRI~$1\le k \le T$, ZATEM USTANOVITX~$|AA|[T-k]\asg |AA|[T-k+1]+|A|[k]$
PRI~$k=1$, 2,~\dots, $T-1$ (V TAKOM PORYADKE). uSTANOVITX $(|TAPE|[1],
|TAPE|[2],~\ldots, |TAPE|[T-1])\asg (|TAPE|[T-1],~\ldots, |TAPE|[2],
|TAPE|[1])$ I USTANOVITX~$|D|[k]\asg |AA|[k+1]$ PRI~$1\le k < T$.
nAKONEC, USTANOVITX~$i\asg 1$.
\st[nACHATX PODUROVENX~$i$.] uSTANOVITX~$j\asg i$. (pEREMENNYE~$i$
I~$j$ PREDSTAVLYAYUT "SHAG~$(i,j)$" V TABLICE, ILLYUSTRIRUYUSHCHEJ METOD fERGYUSONA.)
\st[nACHATX SHAG~$(i, j)$.] uSTANOVITX~$k\asg j$ I~$m\asg
|A|[T-j-1]$. eSLI~$m=0$ I~$i=j$, TO USTANOVITX~$i\asg T-2$ I
VERNUTXSYA K~\stp{3}; ESLI~$m=0$ I~$i\ne j$, VERNUTXSYA K~\stp{2}.
(pEREMENNAYA~$m$ PREDSTAVLYAET SOBOJ CHISLO OTREZKOV, KOTOROE DOLZHNO
BYTX ZAPISANO NA LENTU~$|TAPE|[k]$; $m$~BYVAET RAVNO~0, TOLXKO ESLI~$l=1$.)
\st[vVESTI NA LENTU~$|TAPE|[k]$.] zAPISATX ODIN OTREZOK NA
LENTU NOMER~$|TAPE|[k]$ I UMENXSHITX~$|D|[k]$ NA~1. zATEM, ESLI
VVOD ISCHERPAN, PEREMOTATX VSE LENTY I PEREJTI K SHAGU~\stp{7}.
\st[pRODVIZHENIE.] uMENXSHITX~$m$ NA~1. eSLI~$m>0$, VERNUTXSYA K SHAGU~\stp{5}.
v PROTIVNOM SLUCHAE UMENXSHITX~$k$ NA~1; ESLI~$k>0$, USTANOVITX~$m\asg
|A|[T-j-1]-|A|[T-j]$ I VERNUTXSYA K~\stp{5}, ESLI~$m>0$. v PROTIVNOM SLUCHAE
UMENXSHITX~$j$ NA~1;
ESLI~$j>0$, PEREJTI K SHAGU~\stp{4}. v PROTIVNOM SLUCHAE UVELICHITX~$i$
NA~1; ESLI~$i<T<1$, VERNUTXSYA K SHAGU~\stp{3}. v PROTIVNOM SLUCHAE PEREJTI
K~\stp{2}.
\st[pODGOTOVKA K SLIYANIYU.] (k |TOMU MOMENTU NACHALXNOE RASPREDELENIE
ZAVERSHENO, I TABLICY~|A|, |AA|, |D| I~|TAPE| OPISYVAYUT SOSTOYANIE VSEH
LENT V DANNYJ MOMENT.) uSTANOVITX~$|M|[k]\asg|AA|[k+1]$ PRI~$1\le k < T$ I
USTANOVITX~$|FIRST|\asg 1$. (pEREMENNAYA~|FIRST| PRINIMAET NENULEVOE
ZNACHENIE TOLXKO VO VREMYA PERVOGO PROHODA SLIYANIYA.)
\st[kASKAD.] eSLI~$l=0$, OSTANOVITXSYA; SORTIROVKA ZAVERSHENA, VYVOD
NAHODITSYA NA~$|TAPE|[1]$. v PROTIVNOM SLUCHAE PRI~$p=T-1$, $T-2$,~\dots, 1
(V TAKOM PORYADKE) VYPOLNYATX $p\hbox{-PUTEVOE}$ SLIYANIE S
LENT~$|TAPE|[1]$,~\dots, $|TAPE|[p]$ NA~$|TAPE|[p+1]$ SLEDUYUSHCHIM OBRAZOM:
%% 349
eSLI~$p=1$, TO MODELIROVATX ODNOPUTEVOE SLIYANIE
OBYCHNOJ PEREMOTKOJ~$|TAPE|[2]$ I ZAMENOJ~$|TAPE|[1]\xchg |TAPE|[2]$. v
PROTIVNOM SLUCHAE, ESLI~$|FIRST|=1$ I~$|D|[p-1]=|M|[p-1]$, TO MODELIROVATX
$p\hbox{-PUTEVOE}$ SLIYANIE, PROSTO POMENYAV $|TAPE|[p]\xchg |TAPE|[p+1]$,
PEREMOTAV~$|TAPE|[p]$ I VYCHTYA~$M[p-1]$ IZ KAZHDOGO~$|D|[1]$,~\dots,
$|D|[p-1]$, $|M|[1]$,~\dots, $|M|[p-1]$. v PROTIVNOM SLUCHAE
VYCHESTX~$|M|[p-1]$ IZ VSEH~$|M|[1]$,~\dots, $|M|[p-1]$. zATEM SLITX PO
ODNOMU OTREZKU S KAZHDOJ~$|TAPE|[j]$, TAKOJ, CHTO~$1\le j \le p$
I~$|D|[j]\le |M|[j]$; VYCHESTX EDINICU IZ KAZHDOGO~$|D|[j]$, TAKOGO,
CHTO~$1\le j \le p$ I~$|D|[j]>|M|[j]$, I POMESTITX VYVODNOJ OTREZOK
NA~$|TAPE|[p+1]$. pRODOLZHATX RABOTU, POKA $|TAPE|[p]$ NE STANET PUSTOJ.
zATEM PEREMOTATX~$|TAPE|[p]$ I~$|TAPE|[p+1]$.
\st[oPUSTITXSYA NA ODIN UROVENX.] uMENXSHITX~$l$ NA~1,
USTANOVITX~$|FIRST|\asg 0$, USTANOVITX
$(|TAPE|[1],~\ldots, |TAPE|[T])\asg (|TAPE|[T],~\ldots, |TAPE|[1])$. (k
|TOMU MOMENTU VSE~|D| I~|M|---NULI I TAKOVYMI OSTANUTSYA.) vERNUTXSYA K~\stp{8}.
\algend
shAGI~C1--C6 |TOGO ALGORITMA VYPOLNYAYUT RASPREDELENIE, SHAGI~C7--C9 VYPOLNYAYUT
SLIYANIE; |TI DVE CHASTI SOVERSHENNO NEZAVISIMY ODNA OT DRUGOJ, I MOZHNO BYLO
BY HRANITX~$|M|[k]$ I~$|AA|[k+1]$ V ODNIH I TEH ZHE YACHEJKAH PAMYATI.
\picture{rIS.~75. kASKADNOE SLIYANIE SO SPECIALXNYM RASPREDELENIEM.}
\section *aNALIZ KASKADNOGO SLIYANIYA. kASKADNOE SLIYANIE PODDAETSYA ANALIZU
S BOLXSHIM TRUDOM, CHEM MNOGOFAZNOE. nO |TOT ANALIZ OSOBENNO INTERESEN,
POSKOLXKU SODERZHIT MNOGO ZAMECHATELXNYH FORMUL. nASTOYATELXNO REKOMENDUEM
CHITATELYAM, INTERESUYUSHCHIMSYA DISKRETNOJ MATEMATIKOJ, SAMOSTOYATELXNO
PROANALIZIROVATX KASKADNOE RASPREDELENIE, PREZHDE CHEM CHITATX DALXSHE, VEDX CHISLA
%%350
IMEYUT TAK MNOGO NEOBYCHNYH SVOJSTV, OTKRYVATX KOTORYE---ODNO UDOVOLXSTVIE! mY
OBSUDIM ZDESX LISHX ODIN IZ MNOGIH PODHODOV, OBRASHCHAYA OSOBOE VNIMANIE NA
METODY POLUCHENIYA REZULXTATOV.
dLYA UDOBSTVA RASSMOTRIM SLUCHAJ SHESTI LENT. pRI |TOM BUDEM STARATXSYA
POLUCHITX FORMULY, KOTORYE OBOBSHCHAYUTSYA NA SLUCHAJ LYUBOGO~$T$. sOOTNOSHENIYA~(1)
PRIVODYAT K PERVOJ OSNOVNOJ SISTEME:
$$
\eqalignter{
a_n &= a_n &=\perm{0}{0}a_n,\cr
b_n &= a_n-e_{n-1}=a_n-a_{n-2} &=\perm{1}{0}a_n-\perm{2}{2}a_{n-2},\cr
c_n &= b_n-d_{n-1}=b_n-a_{n-2}-b_{n-2} &=\perm{2}{0}a_n-\perm{3}{2}a_{n-2}+\perm{4}{4}a_{n-4},\cr
d_n &= c_n-c_{n-1}=c_n-a_{n-2}-b_{n-2}-c_{n-2} &=\perm{3}{0}a_n-\perm{4}{2}a_{n-2}+\perm{5}{4}a_{n-4}-\perm{6}{6}a_{n-6},\cr
e_n &= d_n-b_{n-1}=d_n-a_{n-2}-b_{n-2}-c_{n-2}-d_{n-2} &=\perm{4}{0}a_n-\perm{5}{2}a_{n-2}+\perm{6}{4}a_{n-4}-\perm{7}{6}a_{n-6}+\perm{8}{8}a_{n-8}.\cr
}
\eqno(4)
$$
oBOZNACHIM~$A(z)=\sum_{n\ge0} a_n z^n$,~\dots, $E(z)=\sum_{n\ge0}e_n z^n$ I
OPREDELIM MNOGOCHLENY
$$
\eqalignno{
q_m(z)&=\perm{m}{0}-\perm{m+1}{2}z^2+\perm{m+2}{4}z^4-\cdots=\cr
&=\sum_{k\ge 0}\perm{m+k}{2k}(-1)^k z^{2k}
= \sum_{0\le k \le m}\perm{2m-k}{k}(-1)^{m-k} z^{2m-2k}. & (5)\cr
}
$$
rEZULXTAT~(4) KRATKO MOZHNO ISTOLKOVATX TAK,
CHTO~$B(z)-q_1(z)\times A(z)$,~\dots, $E(z)-q_4(z)A(z)$ SVODYATSYA K
KONECHNYM SUMMAM, SOOTVETSTVUYUSHCHIM
GRANICHNYM USLOVIYAM, A IMENNO ZNACHENIYAM~$a_{-1}$, $a_{-2}$, $a_{-3}$,~\dots,
KOTORYE POYAVLYAYUTSYA V~(4) (PRI NEBOLXSHIH~$n$), NO NE V~$A(z)$. chTOBY
POLUCHITX PODHODYASHCHIE GRANICHNYE USLOVIYA, PRIMENIM REKURRENTNOE SOOTNOSHENIE
V OBRATNUYU STORONU DLYA OTRICATELXNYH UROVNEJ DO UROVNYA~$-8$:
\ctable{
\hfill$#$\bskip&&\hfill\bskip$#$\bskip\cr
\hfill n & \hfill a_n & \hfill b_n & \hfill c_n & \hfill d_n & \hfill e_n \cr
0 & 1 & 0 & 0 & 0 & 0\cr
-1 & 0 & 0 & 0 & 0 & 1\cr
-2 & 1 & -1 & 0 & 0 & 0\cr
-3 & 0 & 0 & 0 & -1 & 2\cr
-4 & 2 & -3 & 1 & 0 & 0\cr
-5 & 0 & 0 & 1 & -4 & 5\cr
-6 & 5 & -9 & 5 & -1 & 0\cr
-7 & 0 & -1 & 6 & -14 & 14\cr
-8 & 14 & -28 & 20 & -7 & 1\cr
}
(dLYA SEMI LENT TABLICA BYLA BY ANALOGICHNOJ, ODNAKO STROKI S NECHETNYMI~$n$
BYLI BY SDVINUTY VPRAVO NA ODIN |LEMENT.) tAJNA
POSLEDOVATELXNOSTI~$a_0$, $a_{-2}$, $a_{-4},~\ldots=1, 1, 2, 5, 14,~\ldots$
MGNOVENNO RASKRYVAETSYA SPECIALISTOM PO INFORMATIKE, TAK KAK
%%351
|TA POSLEDOVATELXNOSTX VSTRECHAETSYA V SVYAZI S OCHENX MNOGIMI REKURRENTNYMI
ALGORITMAMI (NAPRIMER, V UPR.~2.2.1-4 I FORMULE~2.3.4.4-13)). iTAK, MY
PREDPOLAGAEM, CHTO V SLUCHAE $T$~LENT
$$
\eqalignrem{
a_{-2n}&=\perm{2n}{n}{1\over n+1} & PRI $0\le n \le T-2$; \cr
a_{-2n-1}&=0 & PRI $0\le n \le T-3$.\cr
}
\eqno(6)
$$
chTOBY PROVERITX PRAVILXNOSTX |TOGO PREDPOLOZHENIYA, DOSTATOCHNO POKAZATX,
CHTO~(6) I~(4) PRIVODYAT K PRAVILXNYM REZULXTATAM DLYA UROVNEJ~0 I~1. dLYA
UROVNYA~1 |TO OCHEVIDNO, A DLYA UROVNYA~0 NAM NADO PROVERITX, CHTO
$$
\perm{m}{0}a_0-\perm{m+1}{2}a_{-2}+\perm{m+2}{4}a_{-4}-\perm{m+3}{6}a_{-6}+\cdots
=\sum_{k\ge0}\perm{m+k}{2k}\perm{2k}{k}{(-1)^k\over k+1}
=\delta_{m0}
\eqno(7)
$$
DLYA~$0\le m \le T-2$. k SCHASTXYU, |TU SUMMU MOZHNO VYCHISLITX STANDARTNYMI
METODAMI (|TO "ZADACHA~2", ODIN IZ OSNOVNYH PRIMEROV V TEKSTE P.~4.2.6).
tEPERX MOZHNO VYCHISLITX KO|FFICIENTY~$B(z)-q_1(z)A(z)$ I~T.~D. rASSMOTRIM,
NAPRIMER, KO|FFICIENT PRI~$z^{2m}$ V~$D(z)-q_3(z)A(z)$. oN RAVEN
$$
\eqalign{
\sum_{k\ge0}\perm{3+m+k}{2m+2k}(-1)^{m+k}a_{-2k}
&=\sum_{k\ge0}\perm{3+m+k}{2m+2k}\perm{2k}{k}{(-1)^{m+k}\over k+1}=\cr
&=(-1)^m\left(\perm{2+m}{2m-1}-\perm{3+m}{2m}\right)=\cr
&=(-1)^{m+1}\perm{2+m}{2m}\cr
}
$$
IZ REZULXTATA "ZADACHI~3" V~P.~1.2.6. tAKIM OBRAZOM, MY VYVELI FORMULY
$$
\eqalign{
A(z) &=q_0(z)A(z);\cr
B(z) &=q_1(z)A(z)-q_0(z);\cr
C(z) &=q_2(z)A(z)-q_1(z);\cr
D(z) &=q_3(z)A(z)-q_2(z);\cr
E(z) &=q_4(z)A(z)-q_3(z).\cr
}
\eqno (8)
$$
kROME TOGO, IMEEM~$e_{n+1}=a_n$; SLEDOVATELXNO, $zA(z)=E(z)$ I
$$
A(z)=q_3(z)/(q_4(z)-z).
\eqno (9)
$$
pROIZVODYASHCHIE FUNKCII BYLI VYRAZHENY PRI POMOSHCHI $q\hbox{-MNOGOCHLENOV}$,
PO|TOMU MY HOTIM LUCHSHE IZUCHITX~$q$. v |TOM OTNOSHENII POLEZNO UPR.~1.2.9-15,
TAK KAK ONO DAET VYRAZHENIE V ZAMKNUTOM
%%352
VIDE, KOTOROE MOZHET BYTX ZAPISANO KAK
$$
q_m(z)={((\sqrt{4-z^2}+iz)/2)^{2m+1}+((\sqrt{4-z^2}-iz)/2)^{2m+1}
\over \sqrt{4-z^2}}
\eqno(10) $$
vSE UPROSHCHAETSYA, ESLI TEPERX POLOZHITX~$z=2 \sin\theta$:
$$
\eqalignno{
q_m(2\sin\theta)=&
{(\cos\theta+i\sin\theta)^{2m+1}+(\cos\theta-i\sin\theta)^{2m+1}\over 2\cos\theta}=\cr
&={\cos(2m+1)\theta\over \cos\theta}. & (11)\cr
}
$$
(eTO SOVPADENIE ZASTAVLYAET DUMATX, CHTO MNOGOCHLENY~$q_m(z)$ HOROSHO
IZVESTNY V MATEMATIKE; I DEJSTVITELXNO, VZGLYANUV V SOOTVETSTVUYUSHCHIE
TABLICY, VIDIM, CHTO~$q_m(z)$, PO SUSHCHESTVU, MNOGOCHLEN chEBYSH¸VA VTOROGO RODA,
A IMENNO~$(-1)^m U_{2m}(z/2)$ V OBYCHNYH OBOZNACHENIYAH.)
tEPERX MOZHNO OPREDELITX KORNI ZNAMENATELYA V~(9):
$q_4(2\sin\theta)=2\sin\theta$ SVODITSYA K
$$
\cos 9\theta = 2 \sin \theta \cos \theta = \sin 2\theta.
$$
rESHENIYA |TOGO SOOTNOSHENIYA POLUCHAEM, ESLI
TOLXKO~$\pm9\theta=2\theta+\left(2n-{1\over2}\right)\pi$; VSE
TAKIE~$\theta$ DAYUT KORNI ZNAMENATELYA V~(9) PRI USLOVII,
CHTO~$\cos\theta\ne 0$. (eSLI~$\cos\theta=0$, TO~$q_m(\pm2)=\pm(2m+1)$,
NIKOGDA NE RAVNO~$\pm2$.) sLEDOVATELXNO, POLUCHAEM 8~RAZLICHNYH KORNEJ:
$$
\displaylines{
q_4(z)-z=0 \qquad \hbox{ PRI } z=2\sin{-5\over 14}\pi,\quad
2\sin{-1 \over 14}\pi,\quad 2\sin{3 \over 14}\pi, \cr
2\sin{-7 \over 22}\pi,\quad 2\sin{-3 \over 22}\pi,\quad
2\sin{1 \over 22}\pi, \quad 2\sin{5 \over 22}\pi,\quad 2\sin{9 \over 22}\pi.\cr
}
$$
tAK KAK~$q_4(z)$---MNOGOCHLEN STEPENI~8, MY UCHLI VSE KORNI. pERVYE TRI IZ
|TIH ZNACHENIJ DAYUT~$q_3(z)=0$, TAK CHTO~$q_3(z)$ I~$q_4(z)-z$ IMEYUT OBSHCHIM
DELITELEM MNOGOCHLEN TRETXEJ STEPENI. oSTALXNYE PYATX KORNEJ UPRAVLYAYUT
ASIMPTOTICHESKIM POVEDENIEM KO|FFICIENTOV~$A(z)$, ESLI RAZLOZHITX~(9) V
|LEMENTARNYE DROBI.
pEREJDYA K RASSMOTRENIYU OBSHCHEGO SLUCHAYA $T$~LENT,
POLOZHIM~$\theta_k=(4k+1)\pi/(4T-2)$. pROIZVODYASHCHAYA FUNKCIYA~$A(z)$ DLYA
$T\hbox{-LENTOCHNYH}$ KASKADNYH CHISEL PRINIMAET VID
$$
{4\over 2T-1}\sum_{-T/2<k<\floor{T/2}}{\cos^2\theta_k\over 1-z/(2\sin\theta_k)}
\eqno(12)
$$
(SM.~UPR.~8); SLEDOVATELXNO,
$$
a_n={4\over 2T-1}\sum_{-T/2<k<\floor{T/2}}\cos^2\theta_k \left({1\over 2\sin\theta_k}\right)^n.
\eqno(13)
$$
%% 353
sOOTNOSHENIYA~(8) PRIVODYAT TEPERX K ANALOGICHNYM FORMULAM:
$$
\eqalign{
b_n&={4\over 2T-1}\sum_{-T/2<k<\floor{T/2}}\cos\theta_k\cos3\theta_k\left({1\over 2\sin\theta_k}\right)^n;\cr
c_n&={4\over 2T-1}\sum_{-T/2<k<\floor{T/2}}\cos\theta_k\cos5\theta_k\left({1\over 2\sin\theta_k}\right)^n;\cr
d_n&={4\over 2T-1}\sum_{-T/2<k<\floor{T/2}}\cos\theta_k\cos7\theta_k\left({1\over 2\sin\theta_k}\right)^n\cr
}
\eqno(14)
$$
I~T.~D. v UPR.~9 POKAZANO, CHTO |TI URAVNENIYA SPRAVEDLIVY DLYA VSEH~$n\ge0$,
A NE TOLXKO DLYA BOLXSHIH~$n$. v KAZHDOJ SUMME CHLEN S~$k=0$ ZNACHITELXNO
PREVOSHODIT VSE OSTALXNYE, OSOBENNO ESLI~$n$ DOSTATOCHNO VELIKO;
SLEDOVATELXNO, "OTNOSHENIE ROSTA" ESTX
$$
{1\over 2\sin\theta_0}={2\over\pi}T-{1\over\pi}+{\pi\over 48T}+O(T^{-2}).
\eqno(15)
$$
kASKADNAYA SORTIROVKA VPERVYE BYLA ISSLEDOVANA u.~k.~kARTEROM
[Proc.\ IFIP Congress (1962), 62--66], KOTORYJ POLUCHIL CHISLENNYE REZULXTATY
DLYA NEBOLXSHIH ZNACHENIJ~$T$, I d|VIDOM fERGYUSONOM
[{\sl CACM,\/} {\bf 7} (1964), 297], KOTORYJ OTKRYL PERVYE DVA CHLENA V
ASIMPTOTICHESKOM POVEDENII~(15) OTNOSHENIYA ROSTA.
lETOM 1964~G.\ r.~u.~fLOJD POLUCHIL YAVNYJ VID~$1/(2\sin\theta_0)$
DLYA OTNOSHENIYA ROSTA, TAK CHTO TOCHNYE FORMULY
MOGLI BYTX ISPOLXZOVANY DLYA VSEH~$T$. gLUBOKIJ ANALIZ KASKADNYH CHISEL BYL
NEZAVISIMO VYPOLNEN dZH.~n.~r|JNI
[{\sl Canadian J.~Math.,\/} {\bf 18} (1966), 332--349],
KOTORYJ NATKNULSYA NA NIH SOVERSHENNO DRUGIM PUTEM,
NE IMEYA DELA S SORTIROVKOJ. r|JNI PODMETIL ANALOGIYU S DIAGONALYAMI
(RIS.~73) I VYVEL MNOGO DRUGIH INTERESNYH SVOJSTV |TIH CHISEL. fLOJD
I~r|JNI V SVOIH DOKAZATELXSTVAH OPERIROVALI S MATRICAMI (SM.~UPR.~6).
\section mODIFIKACIYA KASKADNOJ SORTIROVKI. eSLI DOBAVLENA ESHCHE ODNA LENTA,
TO POCHTI VSE VREMYA PEREMOTKI V TECHENIE KASKADNOJ SORTIROVKI MOZHNO
SOVMESTITX. nAPRIMER, MY MOZHEM SLIVATX~T1--T5 NA~T7, ZATEM~T1--T4 NA~T6,
ZATEM~T1--T3 NA~T5 (KOTORAYA K |TOMU MOMENTU UZHE PEREMOTANA), ZATEM~T1--T2
NA~T4 I NACHATX SLEDUYUSHCHIJ PROHOD, KOGDA NA~T4 BUDET PEREMOTANO
SRAVNITELXNO NEMNOGO DANNYH. eFFEKTIVNOSTX |TOGO PROCESSA MOZHNO
PREDSKAZATX NA OSNOVANII IZLOZHENNOGO VYSHE ANALIZA KASKADNOGO
METODA (DALXNEJSHIE PODROBNOSTI SM.~V~P.~5.4.6).
sHEMA "KOMPROMISSNOGO SLIYANIYA", KOTORAYA VKLYUCHAET MNOGOFAZNUYU I KASKADNUYU
SHEMY KAK CHASTNYE SLUCHAI, BYLA PREDLOZHENA d.~e.~kNUTOM V [{\sl CACM,\/}
{\bf 6} (1963), 585--587]. kAZHDAYA FAZA SOSTOIT IZ~$(T-1)\hbox{-PUTEVOGO}$,
$(T-2)\hbox{-PUTEVOGO}$,~\dots, $P\hbox{-PUTEVOGO}$ SLIYANIJ, GDE $P$---LYUBOE
FIKSIROVANNOE CHISLO MEZHDU~1 I~$T-1$. eSLI~$P=T-1$, TO |TO---MNOGOFAZNYJ
METOD; ESLI~$P=1$, |TO---CHISTYJ
%%354
KASKADNYJ METOD; ESLI~$P=2$, |TO---KASKADNYJ METOD BEZ FAZ
KOPIROVANIYA. aNALIZ TAKOJ SHEMY BYL PRODELAN ch.~rADKE
[{\sl IBM Systems J.,\/} {\bf 5} (1966), 226--247] I~u.~h.~bURZHEM
[Proc. IFIP Congress, {\bf 1} (1971), 454---459]. bURZH NASHEL
PROIZVODYASHCHUYU FUNKCIYU~$\sum T_n(x) z^n$ DLYA
KAZHDOGO~$(P, T)\hbox{-KOMPROMISSNOGO}$ SLIYANIYA,
OBOBSHCHAYUSHCHUYU SOOTNOSHENIE~(5.4.2-16); ON
POKAZAL, CHTO NAILUCHSHEE ZNACHENIE~$P$ (S TOCHKI ZRENIYA NAIMENXSHEGO CHISLA
OBRABATYVAEMYH NACHALXNYH OTREZKOV), KAK FUNKCII OT~$S$
PRI~$S\to\infty$ (ESLI NEPOSREDSTVENNO ISPOLXZOVATX SHEMU RASPREDELENIYA
I PRENEBRECHX VREMENEM PEREMOTKI), ESTX SOOTVETSTVENNO
$(2, 3, 3, 4, 4, 4, 3, 3, 4)$ PRI~$T=(3, 4, 5, 6, 7, 8, 9, 10, 11)$.
eTI ZNACHENIYA~$P$ S
ROSTOM~$T$ SILXNEE OTKLONYAYUTSYA V STORONU KASKADNOGO, A NE MNOGOFAZNOGO
METODA, I OKAZYVAETSYA, CHTO KOMPROMISSNOE SLIYANIE NIKOGDA NE STANET
SUSHCHESTVENNO LUCHSHE KASKADNOGO. s DRUGOJ STORONY, PRI OPTIMALXNOM VYBORE
UROVNEJ I RASPREDELENII FIKTIVNYH OTREZKOV, KAK OPISANO V P.~5.4.2, CHISTYJ
MNOGOFAZNYJ METOD KAZHETSYA NAILUCHSHIM SREDI VSEH KOMPROMISSNYH SLIYANIJ.
k SOZHALENIYU, OPTIMALXNOE RASPREDELENIE SRAVNITELXNO TRUDNO REALIZOVATX.
t.~l.~jONSEN [{\sl BIT,\/} {\bf 6} (1966), 129--143] ISSLEDOVAL
SOCHETANIYA SBALANSIROVANNOGO I MNOGOFAZNOGO SLIYANIJ; MODIFIKACIYA
SBALANSIROVANNOGO SLIYANIYA S SOVMESHCHENIEM PEREMOTOK BYLA PREDLOZHENA
m.~gOTCEM [Digital Computer User's Handbook, ed.~by.~M.~Klerer
and~G.~A.~Korn (New York: McGraw-Hill, 1967), 1.311--1.312]; MOZHNO
PREDSTAVITX SEBE I MNOGIE DRUGIE GIBRIDNYE SHEMY.
\excercises
\ex[10] iSPOLXZUYA TABL.~1, SRAVNITE KASKADNOE SLIYANIE S OPISANNOJ
V P.~5.4.2 VERSIEJ MNOGOFAZNOGO SLIYANIYA S "RASSHCHEPLENIEM LENT". kAKOJ
METOD LUCHSHE? (vREMENEM PEREMOTKI PRENEBRECHX.)
\rex[22] sRAVNITE KASKADNUYU SORTIROVKU S TREMYA LENTAMI,
ISPOLXZUYUSHCHUYU ALGORITM~C, I MNOGOFAZNUYU SORTIROVKU S TREMYA LENTAMI,
ISPOLXZUYUSHCHUYU ALGORITM~5.4.2D kAKIE SHODSTVA I RAZLICHIYA VY ZaMeTITe?
\ex[20] sOSTAVXTE TABLICU, POKAZYVAYUSHCHUYU, CHTO PROISHODIT PRI SORTIROVKE NA
SHESTI LENTAH 100~NACHALXNYH OTREZKOV PRI POMOSHCHI ALGORITMA~C.
\ex[m20] (dZH.~n.~r|JNI.) "kASKADNOE RASPREDELENIE $n\hbox{-GO}$ UROVNYA"
ESTX MULXTIMNOZHESTVO, OPREDELENNOE SLEDUYUSHCHIM OBRAZOM (V SLUCHAE SHESTI LENT):
$\set{1, 0, 0, 0, 0}$ ESTX KASKADNOE RASPREDELENIE NULEVOGO UROVNYA;
ESLI~$\set{a, b, c, d, e}$---KASKADNOE RASPREDELENIE $n\hbox{-GO}$~UROVNYA,
TO~$\set{a+b+c+d+e, a+b+c+d, a+b+c, a+b, a}$ BUDET KASKADNYM
RASPREDELENIEM $(n+1)\hbox{-GO}$ UROVNYA (tAK KAK MULXTIMNOZHESTVO NE
UPORYADOCHENO, TO IZ EDINSTVENNOGO RASPREDELENIYA $n\hbox{-GO}$~UROVNYA MOZHNO
OBRAZOVATX DO~5 RAZLICHNYH RASPREDELENIJ $(n+1)\hbox{-GO}$~UROVNYA.)
(a)~dOKAZHITE, CHTO \emph{LYUBOE}
MULXTIMNOZHESTVO~$\set{a, b, c, d, e}$ IZ VZAIMNO PROSTYH CHISEL YAVLYAETSYA
KASKADNYM RASPREDELENIEM $n\hbox{-GO}$~UROVNYA PRI NEKOTOROM~$n$.
(b)~dOKAZHITE, CHTO RASPREDELENIE, ISPOLXZUEMOE V KASKADNOJ SORTIROVKE,
\emph{OPTIMALXNO} V TOM SMYSLE, CHTO ESLI~$\set{a, b, c, d, e}$---LYUBOE
RASPREDELENIE $n\hbox{-GO}$~UROVNYA, PRICHEM~$a\ge b \ge c \ge d \ge e$, TO
BUDEM IMETX~$a\le a_n$, $b\le b_n$, $c\le c_n$, $d\le d_n$, $e\le e_n$,
GDE~$\set{a_n, b_n, c_n, d_n, e_n}$---RASPREDELENIE, OPREDELENNOE V~(1).
\rex[20] dOKAZHITE, CHTO KASKADNYE CHISLA, OPREDELENNYE V~(1), UDOVLETVORYAYUT
%%355
ZAKONU
$$
a_k a_{n-k}+b_k b_{n-k}+c_k c_{n-k}+d_k d_{n-k}+e_k e_{n-k}=a_n
\rem{PRI~$ 0\le k \le n$.}
$$
[\emph{uKAZANIE:} DLYA LUCHSHEGO PONIMANIYA |TOGO SOOTNOSHENIYA RASSMOTRITE,
SKOLXKO OTREZKOV RAZLICHNOJ DLINY VYVODITSYA V TECHENIE $k\hbox{-GO}$~PROHODA
POLNOJ KASKADNOJ SORTIROVKI.]
\ex[m20] nAJDITE $5\times5$-MATRICU~$Q$, TAKUYU, CHTO PERVAYA STROKA~$Q^n$
SODERZHIT KASKADNYE CHISLA DLYA SHESTI LENT~$a_n b_n c_n d_n e_n$ PRI
VSEH~$n\ge 0$.
\ex[m20] pRI USLOVII CHTO KASKADNOE SLIYANIE PRIMENYAETSYA K
TOCHNOMU RASPREDELENIYU $a_n$~NACHALXNYH OTREZKOV, NAJDITE FORMULU DLYA
VELICHINY S|KONOMLENNOJ RABOTY, KOGDA ISKLYUCHAETSYA ODNOPUTEVOE SLIYANIE.
\ex[vm23] vYVEDITE FORMULU~(12).
\ex[vm26] vYVEDITE FORMULU~(14).
\rex[m28] vMESTO SISTEMY~(4) DLYA IZUCHENIYA KASKADNYH CHISEL VOSPOLXZUJTESX
V KACHESTVE ISHODNYH TOZHDESTVAMI
$$
\eqalignter{
e_n&=a_{n-1} &= \perm{1}{1}a_{n-1};\cr
d_n&=2a_{n-1}-e_{n-2} &=\perm{2}{1}a_{n-1}-\perm{3}{3}a_{n-3};\cr
c_n&=3a_{n-1}-d_{n-2}-2e_{n-2} &=\perm{3}{1}a_{n-1}-\perm{4}{3}a_{n-3}+\perm{5}{5}a_{n-5}\cr
}
$$
I~T.~D. pOLAGAYA
$$
r_m(z)=\perm{m}{1}z-\perm{m+1}{3}z^3+\perm{m+2}{5}z^5-\ldots,
$$
VYRAZITE~$A(z)$, $B(z)$ I~T.~D.\ CHEREZ |TI $r\hbox{-MNOGOCHLENY}$.
\ex[m38] pUSTX
$$
f_m(z)=\sum_{0\le k \le m} \perm{\floor{(m+k)/2}}{k}(-1)^{\ceil{k/2}}z^k.
$$
dOKAZHITE, CHTO PROIZVODYASHCHAYA FUNKCIYA~$A(z)$ DLYA $T\hbox{-LENTOCHNYH}$
KASKADNYH CHISEL RAVNA~$f_{T-3}(z)/f_{T-1}(z)$, PRICHEM CHISLITELX I
ZNAMENATELX |TOGO VYRAZHENIYA NE IMEYUT OBSHCHIH DELITELEJ.
\ex[m40] dOKAZHITE, CHTO SHEMA RASPREDELENIYA fERGYUSONA OPTIMALXNA V TOM
SMYSLE, CHTO PRI LYUBOM DRUGOM METODE RAZMESHCHENIYA FIKTIVNYH OTREZKOV,
UDOVLETVORYAYUSHCHEM~(2), VO VREMYA PERVOGO PROHODA BUDET OBRABATYVATXSYA
NE MENXSHE NACHALXNYH OTREZKOV, \emph{PRI USLOVII} CHTO VO VREMYA |TOGO
PROHODA ISPOLXZUETSYA STRATEGIYA SHAGOV~C7--C9.
\ex[40] v TEKSTE PREDLAGAETSYA BOLXSHUYU CHASTX VREMENI PEREMOTKI SOVMESHCHATX
PUTEM DOBAVLENIYA DOPOLNITELXNOJ LENTY. rAZRABOTAJTE |TU IDEYU. (nAPRIMER,
SHEMA, IZLOZHENNAYA V TEKSTE, VKLYUCHAET OZHIDANIE PEREMOTKI LENTY~T4;
NE BUDET LI LUCHSHE ISKLYUCHITX~T4 IZ PERVOJ FAZY SLIYANIYA SLEDUYUSHCHEGO PROHODA?)
\subsubchap{chTENIE LENTY V OBRATNOM NAPRAVLENII} %% 5.4.4
mNOGIE LENTOPROTYAZHNYE USTROJSTVA POZVOLYAYUT CHITATX LENTU V NAPRAVLENII,
PROTIVOPOLOZHNOM TOMU, V KOTOROM SHLA ZAPISX NA NEE. sHEMY SLIYANIYA, S
KOTORYMI MY VSTRECHALISX DO SIH POR, VSEGDA ZAPISYVAYUT INFORMACIYU NA LENTU
V PRYAMOM NAPRAVLENII,
%% 356
ZATEM PEREMATYVAYUT LENTU, CHITAYUT EE V PRYAMOM NAPRAVLENII I VNOVX
PEREMATYVAYUT. (fAJLY NA LENTE, SLEDOVATELXNO, VEDUT SEBYA KAK OCHEREDI
"PERVYM VKLYUCHAETSYA---PERVYM ISKLYUCHAETSYA".) oBRATNOE CHTENIE POZVOLYAET
OBOJTISX BEZ OBEIH OPERACIJ PEREMOTKI:
MY ZAPISYVAEM NA LENTU V PRYAMOM NAPRAVLENII I CHITAEM EE V OBRATNOM. (v
|TOM SLUCHAE FAJLY VEDUT SEBYA KAK STEKI, POSKOLXKU ZDESX DEJSTVUET PRAVILO
"POSLEDNIM VKLYUCHAETSYA---PERVYM ISKLYUCHAETSYA".)
sHEMY SBALANSIROVANNOGO, MNOGOFAZNOGO I KASKADNOGO SLIYANIJ MOZHNO
PRISPOSOBITX DLYA OBRATNOGO CHTENIYA. oSNOVNOE OTLICHIE SOSTOIT V TOM, CHTO
\emph{SLIYANIE IZMENYAET PORYADOK OTREZKOV,} ESLI MY CHITAEM V PRYAMOM
NAPRAVLENII I ZAPISYVAEM V OBRATNOM. eSLI DVA OTREZKA NAHODYATSYA NA LENTE V
VOZRASTAYUSHCHEM PORYADKE, TO IH MOZHNO SLITX, CHITAYA V OBRATNOM NAPRAVLENII, NO
PRI |TOM PORYADOK STANET UBYVAYUSHCHIM. pOLUCHENNYE TAKIM PUTEM
UBYVAYUSHCHIE OTREZKI STANUT VOZRASTAYUSHCHIMI NA SLEDUYUSHCHEM PROHODE; TAKIM OBRAZOM,
ALGORITM SLIYANIYA DOLZHEN UMETX RABOTATX S OTREZKAMI OBOIH NAPRAVLENIJ.
pROGRAMMISTU, VPERVYE STOLKNUVSHEMUSYA S OBRATNYM CHTENIEM, MOZHET POKAZATXSYA,
CHTO ON STOIT NA GOLOVE!
v KACHESTVE PRIMERA OBRATNOGO CHTENIYA RASSMOTRIM PROCESS SLIYANIYA 8~NACHALXNYH
OTREZKOV S ISPOLXZOVANIEM \emph{SBALANSIROVANNOGO} SLIYANIYA NA 4~LENTAH.
mOZHNO SLEDUYUSHCHIM OBRAZOM ZAPISATX NASHI DEJSTVIYA:
\ctable{
# \hfil & \bskip\hfil$#$\hfil\bskip & \bskip\hfil$#$\hfil\bskip &
\bskip\hfil$#$\hfil\bskip & \bskip\hfil$#$\hfil\bskip & # \hfil \cr
& T1 & T2 & T3 & T4 \cr
pROHOD~1. & A_1 A_1 A_1 A_1 & A_1 A_1 A_1 A_1 & - & - & nACHALXNOE RASPREDELENIE \cr
pROHOD~2. & - & - & D_2 D_2 & D_2 D_2 & sLIYANIE NA~$T3$ I~$T4$\cr
pROHOD~3. & A_4 & A_4 & - & - & sLIYANIE NA~$T1$ I~$T2$\cr
pROHOD~4. & - & - & D_8 & - & oKONCHATELXNOE SLIYANIE NA~$T3$\cr
}
zDESX $A_r$~OBOZNACHAET OTREZOK, IMEYUSHCHIJ OTNOSITELXNUYU DLINU~$r$ I
RASPOLOZHENNYJ V VOZRASTAYUSHCHEM PORYADKE, ESLI LENTA CHITAETSYA V PRYAMOM
NAPRAVLENII, KAK V PREDYDUSHCHIH NASHIH PRIMERAH; $D_r$---ANALOGICHNOE
OBOZNACHENIE DLYA UBYVAYUSHCHEGO OTREZKA DLINY~$r$. vO VREMYA 2-GO~PROHODA
VOZRASTAYUSHCHIE OTREZKI STANOVYATSYA UBYVAYUSHCHIMI: ONI OKAZYVAYUTSYA UBYVAYUSHCHIMI
PRI VVODE, TAK KAK MY CHITAEM V OBRATNOM NAPRAVLENII. oNI VNOVX IZMENYAYUT
ORIENTACIYU NA 3-M~PROHODE.
zAMETIM, CHTO OPISANNYJ PROCESS ZAVERSHAETSYA REZULXTATOM NA LENTE~$T3$ V
\emph{UBYVAYUSHCHEM} PORYADKE. eSLI |TO PLOHO (CHTO ZAVISIT OT TOGO, DOLZHEN LI
REZULXTAT CHITATXSYA V OBRATNOM NAPRAVLENII, ILI ZHE LENTA, SODERZHASHCHAYA EGO,
DOLZHNA BYTX SNYATA I OTLOZHENA DLYA BUDUSHCHEGO ISPOLXZOVANIYA), MY MOZHEM
SKOPIROVATX EGO NA DRUGUYU LENTU, OBRATIV NAPRAVLENIE. bOLEE BYSTRYM
SPOSOBOM BYLA BY
%%357
PEREMOTKA~$T1$ I~$T2$ POSLE 3-GO~PROHODA, PRI |TOM VO VREMYA 4-GO~PROHODA
POLUCHAETSYA~$A_8$. eSHCHE BYSTREE BYLO BY NACHATX S VOSXMI \emph{UBYVAYUSHCHIH}
OTREZKOV NA 1-M~PROHODE, TAK KAK |TO POMENYAET MESTAMI VSE~$A$ I~$D$.
oDNAKO DLYA SBALANSIROVANNOGO SLIYANIYA 16~NACHALXNYH OTREZKOV POTREBOVALOSX
BY, CHTOBY NACHALXNYE OTREZKI BYLI VOZRASTAYUSHCHIMI, A TAK KAK MY OBYCHNO NE
ZNAEM ZARANEE, SKOLXKO NACHALXNYH OTREZKOV BUDET OBRAZOVANO, TO NEOBHODIMO
VYBRATX ODNO POSTOYANNOE NAPRAVLENIE. sLEDOVATELXNO, IDEYA PEREMOTKI POSLE
3-GO~PROHODA, VEROYATNO, NAILUCHSHAYA.
\emph{kASKADNOE} SLIYANIE PREOBRAZUETSYA TAKIM ZHE SPOSOBOM. rASSMOTRIM,
NAPRIMER, SORTIROVKU 14~NACHALXNYH OTREZKOV NA CHETYREH LENTAH:
\ctable{
# \hfil & \bskip\hfil$#$\hfil\bskip & \bskip\hfil$#$\hfil\bskip &
\bskip\hfil$#$\hfil\bskip & \bskip\hfil$#$\hfil\bskip & # \hfil \cr
& T1 & T2 & T3 & T4 \cr
pROHOD~1. & A_1 A_1 A_1 A_1 A_1 A_1 & A_1 A_1 A_1 A_1 A_1 & A_1 A_1 A_1 & - \cr
pROHOD~2. & - & D_1 & D_2 D_2 & D_3 D_3 D_3 \cr
pROHOD~3. & A_6 & A_5 & A_3 & - \cr
pROHOD~4. & - & - & - & D_{14} \cr
\noalign{\noindent
sNOVA VMESTO~$D_{14}$ MOZHNO POLUCHITX~$A_{14}$, ESLI PEREMOTATX~$T1$, $T2$,
$T3$ NEPOSREDSTVENNO PERED POSLEDNIM PROHODOM. zAMETIM, CHTO |TO "CHISTOE"
KASKADNOE SLIYANIE V TOM SMYSLE, CHTO VSE ODNOPUTEVYE SLIYANIYA VYPOLNENY
YAVNYM OBRAZOM. eSLI BY MY ZAPRETILI OPERACII KOPIROVANIYA, KAK V
ALGORITME~5.4.3D, TO POSLE 2-GO~PROHODA STOLKNULISX BY S SITUACIEJ
}
& A_1 & - & D_2D_2 & D_3D_3D_3 \cr
}
I BYLO BY NEVOZMOZHNO PRODOLZHATX RABOTU, ISPOLXZUYA TREHPUTEVOE SLIYANIE, TAK
KAK MY NE MOZHEM SLIVATX OTREZKI PROTIVOPOLOZHNYH NAPRAVLENIJ! mOZHNO BYLO
BY IZBEZHATX OPERACII KOPIROVANIYA~$T1$ NA~$T2$, ESLI PEREMOTATX~$T1$ I
NACHATX CHITATX EE V PRYAMOM NAPRAVLENII VO VREMYA SLEDUYUSHCHEJ FAZY SLIYANIYA (V
TO VREMYA KAK~$T3$ I~$T4$ CHITAYUTSYA V OBRATNOM NAPRAVLENII). nO TOGDA
PRISHLOSX BY VNOVX PEREMOTATX~$T1$ POSLE SLIYANIYA, TAK CHTO |TOT
PRIEM ZAMENYAET ODNO KOPIROVANIE NA DVE PEREMOTKI.
tAKIM OBRAZOM, METOD RASPREDELENIYA ALGORITMA~5.4.3C RABOTAET DLYA
OBRATNOGO CHTENIYA NE STOLX |FFEKTIVNO, KAK DLYA PRYAMOGO CHTENIYA; VREMENNYE
ZATRATY REZKO VOZRASTAYUT KAZHDYJ RAZ, KOGDA CHISLO NACHALXNYH OTREZKOV
PROHODIT CHEREZ "TOCHNOE" KASKADNOE RASPREDELENIE. chTOBY POLUCHITX BOLEE
GLADKIJ PROHOD MEZHDU TOCHNYMI KASKADNYMI RASPREDELENIYAMI, MOZHNO
ISPOLXZOVATX INOJ METOD RASPREDELENIYA (SM.~UPR.~17).
\section oBRATNOE CHTENIE V MNOGOFAZNOM SLIYANII. nA PERVYJ VZGLYAD (I
DAZHE NA VTOROJ I TRETIJ!) SHEMA MNOGOFAZNOGO SLIYANIYA KAZHETSYA SOVERSHENNO
NEPODHODYASHCHEJ DLYA OBRATNOGO CHTENIYA. pREDPOLOZHIM, NAPRIMER, CHTO IMEYUTSYA
13~NACHALXNYH OTREZKOV I TRI LENTY.
%%358
\ctable{
# \hfil & \bskip\hfil$#$\hfil\bskip & \bskip\hfil$#$\hfil\bskip &
\bskip\hfil$#$\hfil\bskip \cr
& T1 & T2 & T3 \cr
fAZA~1.& A_1 A_1 A_1 A_1 A_1 & A_1 A_1 A_1 A_1 A_1 A_1 A_1 A_1 & - \cr
fAZA~2.& - & A_1 A_1 A_1 & D_2 D_2 D_2 D_2 D_2\cr
}
zDESX MY VSTAEM V TUPIK; MOZHNO BYLO BY PEREMOTATX~$T2$ ILI~$T3$ I ZATEM
CHITATX IH V PRYAMOM NAPRAVLENII, V TO VREMYA KAK OSTALXNYE LENTY---V
OBRATNOM. nO |TO SILXNO ZAPUTALO BY DELO, I VYGODA OT OBRATNOGO CHTENIYA
BYLA BY OTNOSITELXNO MALA.
oSTROUMNAYA IDEYA, SPASAYUSHCHAYA POLOZHENIE, SOSTOIT V TOM,
CHTOBY \emph{CHEREDOVATX NAPRAVLENIYA OTREZKOV NA KAZHDOJ LENTE.} tOGDA
SLIYANIE MOZHET PROISHODITX VPOLNE SOGLASOVANNO:
\ctable{
# \hfil & \bskip\hfil$#$\hfil\bskip & \bskip\hfil$#$\hfil\bskip & \bskip\hfil$#$\hfil\bskip \cr
fAZA~1. & A_1 D_1 A_1 D_1 A_1 & D_1 A_1 D_1 A_1 D_1 A_1 D_1 A_1 & - \cr
fAZA~2. & - & D_1 A_1 D_1 & D_2 A_2 D_2 A_2 D_2 \cr
fAZA~3. & A_3 D_3 A_3 & - & D_2 A_2 \cr
fAZA~4. & A_3 & D_5 A_5 & - \cr
fAZA~5. & - & D_5 & D_8 \cr
fAZA~6. & A_{13} & - & - \cr
}
eTOT PRINCIP BYL KRATKO UPOMYANUT r.~l.~gILST|DOM V EGO RANNEJ STATXE O
MNOGOFAZNOM SLIYANII, BOLEE POLNO ON OPISAL EGO
V~{\sl CACM,\/} {\bf 6} (1963), 220--223.
eTOT $ADA\hbox{-METOD}$ CHETKO RABOTAET DLYA MNOGOFAZNOGO SLIYANIYA S
\emph{LYUBYM} CHISLOM LENT; MOZHNO POKAZATX, CHTO~$A$ I~$D$
SOGLASUYUTSYA SOOTVETSTVUYUSHCHIM OBRAZOM NA KAZHDOJ FAZE, PRI TOM TOLXKO
USLOVII, CHTO PROHOD NACHALXNOGO RASPREDELENIYA POROZHDAET CHEREDUYUSHCHIESYA
OTREZKI~$A$ I~$D$ NA KAZHDOJ LENTE I CHTO KAZHDAYA LENTA KONCHAETSYA
OTREZKOM~$A$ (ILI KAZHDAYA LENTA KONCHAETSYA OTREZKOM~$D$). tAK KAK POSLEDNIJ
OTREZOK, ZAPISYVAEMYJ V FAJL VYVODA VO VREMYA ODNOJ FAZY, IMEET NAPRAVLENIE,
PROTIVOPOLOZHNOE NAPRAVLENIYU POSLEDNEGO ISPOLXZOVANNOGO OTREZKA IZ FAJLA
VVODA, TO SLEDUYUSHCHAYA FAZA VSEGDA NAHODIT SVOI OTREZKI S NADLEZHASHCHEJ
ORIENTACIEJ. dALEE, MY VIDELI V UPR.~5.4.2-13, CHTO BOLXSHINSTVO TOCHNYH
FIBONACHCHIEVYH RASPREDELENIJ TREBUET \emph{NECHETNOGO} CHISLA OTREZKOV NA
ODNOJ LENTE (OKONCHATELXNOJ VYVODNOJ LENTE) I CHETNOGO CHISLA OTREZKOV NA
VSEH OSTALXNYH LENTAH. eSLI~$T1$ PREDNAZNACHENA DLYA KONECHNOGO VYVODA, TO
MY MOZHEM, SLEDOVATELXNO, GARANTIROVATX, CHTO VSE LENTY BUDUT KONCHATXSYA
OTREZKOM~$A$, ESLI LENTU~$T1$ NACHNEM S~$A$, A VSE OSTALXNYE LENTY---S~$D$.
mOZHNO ISPOLXZOVATX METOD RASPREDELENIYA, ANALOGICHNYJ ALGORITMU~5.4.2D,
IZMENIV EGO TAKIM OBRAZOM, CHTOBY RASPREDELENIE NA KAZHDOM UROVNE IMELO V
KACHESTVE VYVODNOJ LENTY~$T1$.
(mY PROPUSKAEM UROVNI~$1$, $T+1$, $2T+1$,~\dots, TAK KAK |TO TE UROVNI,
NA KOTORYH KONECHNOJ VYVODNOJ LENTOJ YAVLYAETSYA PERVONACHALXNO PUSTAYA LENTA.)
nAPRIMER, V SLUCHAE SHESTI LENT MOZHNO ISPOLXZOVATX
%% 358
VMESTO~(5.4.2-1) SLEDUYUSHCHEE RASPREDELENIE OTREZKOV:
$$
\vcenter{\halign{
\hfil$#$\hfil&\bskip\hfil$#$\bskip&\bskip\hfil$#$\bskip&\bskip\hfil$#$\bskip&\bskip\hfil$#$\bskip&\bskip\hfil$#$\bskip&\bskip\hfil$#$\bskip&\bskip\hfil$#$\bskip&\hfil$#$\hfil\cr
& & & & & & & \hbox{oKONCHATELXNYJ} \cr
\hbox{uROVENX} & T1 & T2 & T3 & T4 & T5 & \hbox{sUMMA} & \hbox{VYVOD NA LENTE}\cr
0 & 1 & 0 & 0 & 0 & 0 & 1 & T1 \cr
2 & 1 & 2 & 2 & 2 & 2 & 9 & T1 \cr
3 & 3 & 4 & 4 & 4 & 2 & 17 & T1 \cr
4 & 7 & 8 & 8 & 6 & 4 & 33 & T1 \cr
5 & 15 & 16 & 14 & 12 & 8 & 65 & T1 \cr
6 & 31 & 30 & 28 & 24 & 16 & 129 & T1 \cr
8 & 61 & 120 & 116 & 108 & 92 & 497 & T1 \cr
}}
\eqno(1)
$$
tAKIM OBRAZOM, NA~$T1$ VSEGDA POMESHCHAETSYA NECHETNOE CHISLO OTREZKOV, TOGDA
KAK NA LENTY S~$T2$ PO~$T5$---CHETNYE CHISLA (V UBYVAYUSHCHEM PORYADKE DLYA
UPROSHCHENIYA PRISVOENIYA FIKTIVNYH OTREZKOV). tAKOE RASPREDELENIE IMEET TO
PREIMUSHCHESTVO, CHTO KONECHNAYA VYVODNAYA LENTA IZVESTNA ZARANEE NEZAVISIMO OT
CHISLA NACHALXNYH OTREZKOV, KOTORYE PRIDETSYA OBRABATYVATX. oKAZYVAETSYA
(SM.~UPR.~3), CHTO ESLI ISPOLXZUETSYA |TA SHEMA, TO REZULXTAT VSEGDA BUDET
NA~$T1$ V VOZRASTAYUSHCHEM PORYADKE.
dRUGOJ SPOSOB OSUSHCHESTVITX RASPREDELENIE DLYA MNOGOFAZNOJ SHEMY S OBRATNYM
CHTENIEM BYL PREDLOZHEN d.~t.~gUDVINOM I~dZH.~l.~vENNOM
[{\sl CACM,\/} {\bf 7} (1964), 315]. mY MOZHEM RASPREDELYATX OTREZKI, POCHTI KAK
V ALGORITME~5.4.2D, NACHINAYA S $D\hbox{-OTREZKA}$ NA KAZHDOJ LENTE. kOGDA VVOD
ISCHERPAN, MY PREDSTAVLYAEM SEBE FIKTIVNYJ $A\hbox{-OTREZOK}$
RASPOLOZHENNYM V NACHALE EDINSTVENNOJ "NECHETNOJ" LENTY, ESLI TOLXKO NE
DOSTIGNUTO RASPREDELENIE SO VSEMI NECHETNYMI CHISLAMI. oSTALXNYE FIKTIVNYE
OTREZKI MY PREDSTAVLYAEM SEBE RASPOLOZHENNYMI V KONCE LENT ILI
SGRUPPIROVANNYMI V PARY V SEREDINE. vOPROS OB OPTIMALXNOM RAZMESHCHENII
FIKTIVNYH OTREZKOV ANALIZIRUETSYA NIZHE V UPR.~5.
\section oPTIMALXNYE SHEMY SLIYANIYA. dO SIH POR MY OBSUZHDALI RAZLICHNYE
SHEMY SLIYANIYA S LENTAMI, NE PYTAYASX NAJTI METOD, "NAILUCHSHIJ IZ VOZMOZHNYH".
oPREDELENIE OPTIMALXNOJ SHEMY KAZHETSYA OSOBENNO SLOZHNYM V SLUCHAE PRYAMOGO
CHTENIYA, GDE VZAIMODEJSTVIE VREMENI PEREMOTKI I VREMENI SLIYANIYA S TRUDOM
PODDAETSYA ANALIZU. s DRUGOJ STORONY, ESLI SLIYANIE
OSUSHCHESTVLYAETSYA POSREDSTVOM OBRATNOGO CHTENIYA I PRYAMOJ ZAPISI, TO, PO
SUSHCHESTVU, VSE PEREMOTKI USTRANYAYUTSYA I OKAZYVAETSYA VOZMOZHNYM
DATX DOVOLXNO HOROSHUYU HARAKTERISTIKU OPTIMALXNYM SHEMAM SLIYANIYA.
rICHARD~m.~kARP PREDLOZHIL NESKOLXKO INTERESNYH PODHODOV K |TOJ ZADACHE, I
MY ZAVERSHAEM |TOT PUNKT OBSUZHDENIEM RAZVITOJ IM TEORII.
vO-PERVYH, NAM NEOBHODIM BOLEE UDOBNYJ SPOSOB OPISANIYA SHEM SLIYANIYA VMESTO
DOVOLXNO TAINSTVENNYH TABLIC "SODERZHIMOGO LENT", KOTORYE ISPOLXZOVALISX
VYSHE. kARP PREDLOZHIL DVA
%%360
TAKIH SPOSOBA---\emph{VEKTORNOE PREDSTAVLENIE SHEMY SLIYANIYA} I
\emph{PREDSTAVLENIE V VIDE DEREVA.} oBA PREDSTAVLENIYA POLEZNY NA PRAKTIKE,
I MY OPISHEM IH PO OCHEREDI.
vEKTORNOE PREDSTAVLENIE SHEMY SLIYANIYA SOSTOIT IZ POSLEDOVATELXNOSTI
"VEKTOROV SLIYANIYA" $y^m\ldots{}y^1 y^0$, KAZHDYJ IZ KOTORYH IMEET
$T$~KOMPONENT; $y^{(i)}$ SLEDUYUSHCHIM OBRAZOM IZOBRAZHAET $i\hbox{-J}$ S KONCA
SHAG SLIYANIYA:
$$
y^{(i)}_j=\cases{
+1, & ESLI LENTA S NOMEROM~$j$ YAVLYAETSYA VVODNOJ DLYA DANNOGO SLIYANIYA; \cr
\phantom{-}0, & ESLI LENTA S NOMEROM~$j$ NE ISPOLXZUETSYA V DANNOM SLIYANII;\cr
-1, & ESLI NA LENTU S NOMEROM~$j$ VYVODITSYA REZULXTAT DANNOGO SLIYANIYA.\cr
}
\eqno(2)
$$
tAKIM OBRAZOM, ROVNO ODNA KOMPONENTA~$y^{(i)}$ RAVNA~$-1$,
OSTALXNYE KOMPONENTY RAVNY~0 I~1. iTOGOVYJ VEKTOR~$y^{(0)}$ OSOBYJ; |TO
EDINICHNYJ VEKTOR, IMEYUSHCHIJ~1 V POZICII~$j$, ESLI
OKONCHATELXNYJ OTSORTIROVANNYJ REZULXTAT OKAZYVAETSYA NA USTROJSTVE~$j$, I~0
V OSTALXNYH MESTAH. iZ |TOGO OPREDELENIYA SLEDUET, CHTO VEKTORNAYA SUMMA
$$
v^{(i)}=y^{(i)}+y^{(i-1)}+\cdots+y^{(0)}
\eqno(3)
$$
PREDSTAVLYAET SOBOJ RASPREDELENIE OTREZKOV NA LENTAH NEPOSREDSTVENNO
PERED $i\hbox{-M}$ S KONCA SHAGOM SLIYANIYA, PRICHEM NA LENTE~$j$ NAHODITSYA
$v^{(i)}_j$~OTREZKOV. v CHASTNOSTI, PO~$v^{(m)}$ MOZHNO SUDITX, SKOLXKO
OTREZKOV POMESHCHAET NA KAZHDUYU LENTU NACHALXNYJ PROHOD RASPREDELENIYA.
tRI SHEMY SLIYANIYA, OPISANNYE RANEE V |TOM PUNKTE V TABLICHNOJ FORME,
IMEYUT SLEDUYUSHCHIE VEKTORNYE PREDSTAVLENIYA:
{\def\!{\phantom{+}}\def\y#1{y^{(#1)}}\ctable{
$#$&$\hbox{}# \quad$ & $#$&$\hbox{}#\quad $ & $#$&$\hbox{}#$ \cr
\omit \hfil sBALANSIROVANNAYA \hfil \span & \omit \hfil kASKADNAYA \hfil \span & \omit \hfil mNOGOFAZNAYA \hfil \span \cr
\omit \hfil ($T=4$, $S=8$) \hfil \span & \omit \hfil ($T=4$, $S=14$) \hfil \span & \omit \hfil ($T=3$, $S=13$) \hfil\span\cr
v^{(7)} &=(\!4,\!4,\!0,\!0) & v^{(10)} &= (\!6,\!5,\!3,\!0) & v^{(12)} &=(\!5,\!8,\!0)\cr
\y{7} &= (+1, +1, -1,\!0) & \y{10}&= (+1, +1, +1, -1) & \y{12} &= ( +1, +1, -1)\cr
\y{6} &= (+1, +1,\!0, -1) & \y{9} &= (+1, +1, +1, -1) & \y{11} &= (+1, +1, -1)\cr
\y{5} &= (+1, +1, -1,\!0) & \y{8} &= (+1, +1, +1, -1) & \y{10} &=(+1, +1, -1)\cr
\y{4} &= (+1, +1,\!0, -1) & \y{7} &= (+1, +1, -1,\!0) & \y{9} &= (+1, +1, -1)\cr
\y{3} &= (-1,\!0, +1, +1) & \y{6} &= (+1, +1, -1,\!0) & \y{8} &= (+1, +1, -1)\cr
\y{2} &=(\!0, -1, +1, +1) & \y{5} &= (+1, -1,\!0,\!0) & \y{7} &= (-1, +1, +1)\cr
\y{1} &= (+1, +1, -1,\!0) & \y{4} &= (-1, +1, +1, +1) & \y{6} &= (-1, +1, +1)\cr
\y{0} &=(\!0,\!0,\!1,\!0) & \y{3} &=(\!0, -1, +1, +1) & \y{5} &= (-1, +1, +1)\cr
\omit & \omit & \y{2} &=(\!0,\!0, -1, +1) & \y{4} &= (+1, -1, +1)\cr
\omit & \omit & \y{1} &= (+1, +1, +1, -1) & \y{3} &= (+1, -1, +1)\cr
\omit & \omit & \y{0} &=(\!0,\!0,\!0,\!1) & \y{2} &= (+1, +1, -1)\cr
\omit & \omit & \omit & \omit & \y{1} &= (-1, +1, +1)\cr
\omit & \omit & \omit & \omit & \y{0} &= (\!1,\!0,\!0)\cr
}}
%%361
mOZHET POKAZATXSYA NEUDOBNYM NUMEROVATX |TI VEKTORY S KONCA TAK, CHTOBY
$y^{(m)}$~POYAVLYALSYA PERVYM, A $y^{(0)}$---POSLEDNIM, NO |TA OSOBAYA TOCHKA
ZRENIYA OKAZYVAETSYA PREDPOCHTITELXNOJ PRI RAZRABOTKE TEORII. dLYA POISKA
OPTIMALXNOGO METODA NEPLOHO NACHATX S OTSORTIROVANNOGO VYVODA I PREDSTAVITX
SEBE, KAK EGO MOZHNO "RAZLITX" NA RAZLICHNYE LENTY, ZATEM "RAZLITX" IH
I~T.~D., RASSMATRIVAYA POSLEDOVATELXNYE RASPREDELENIYA~$v^{(0)}$,
$v^{(1)}$, $v^{(2)}$,~\dots V PORYADKE, OBRATNOM TOMU, V KOTOROM ONI V
DEJSTVITELXNOSTI POYAVLYAYUTSYA V PROCESSE SORTIROVKI. fAKTICHESKI IMENNO |TOT
PODHOD BYL UZHE ISPOLXZOVAN NAMI PRI ANALIZE MNOGOFAZNOGO I KASKADNOGO SLIYANIYA.
kAZHDAYA SHEMA SLIYANIYA, OCHEVIDNO, IMEET VEKTORNOE PREDSTAVLENIE. i OBRATNO,
KAK LEGKO VIDETX, POSLEDOVATELXNOSTX
VEKTOROV~$y^{(m)}\ldots{}y^{(1)}y^{(0)}$ SOOTVETSTVUET REALXNOJ SHEME
SLIYANIYA TOGDA I TOLXKO TOGDA, KOGDA VYPOLNYAYUTSYA SLEDUYUSHCHIE TRI USLOVIYA:
{\medskip\narrower
\item{i)}~VEKTOR~$y^{(0)}$ YAVLYAETSYA EDINICHNYM;
\item{ii)}~ROVNO ODNA KOMPONENTA VEKTORA~$y^{(i)}$ RAVNA~$-1$, VSE
OSTALXNYE KOMPONENTY RAVNY~$0$ ILI~$+1$, $m\ge i \ge 1$;
\item{iii)}~VSE KOMPONENTY VEKTORA~$y^{(i)}+\ldots+y^{(1)}+y^{(0)}$
NEOTRICATELXNY, $m\ge i \ge 1$.
\medskip
}
pREDSTAVLENIE SHEMY SLIYANIYA V VIDE DEREVA DAET DRUGOE IZOBRAZHENIE TOJ ZHE
INFORMACII. mY STROIM DEREVO S ODNIM VNESHNIM "LISTOVYM" UZLOM DLYA KAZHDOGO
NACHALXNOGO OTREZKA I S ODNIM VNUTRENNIM UZLOM DLYA KAZHDOGO OTREZKA,
POLUCHENNOGO V REZULXTATE SLIYANIYA, TAKIM OBRAZOM, CHTO POTOMKAMI
LYUBOGO VNUTRENNEGO UZLA YAVLYAYUTSYA OTREZKI, IZ KOTORYH ON BYL SFORMIROVAN.
kAZHDYJ VNUTRENNIJ UZEL POMECHAETSYA NOMEROM SHAGA, NA KOTOROM BYL OBRAZOVAN
SOOTVETSTVUYUSHCHIJ OTREZOK, PRI |TOM SHAGI NUMERUYUTSYA V OBRATNOM PORYADKE, KAK
V VEKTORNOM PREDSTAVLENII;
KROME TOGO, REBRA NEPOSREDSTVENNO NAD KAZHDYM UZLOM POMECHAYUTSYA IMENEM
LENTY, NA KOTOROJ OKAZYVAETSYA |TOT OTREZOK. nAPRIMER, TRI PRIVEDENNYE VYSHE
SHEMY IMEYUT PREDSTAVLENIYA V VIDE DEREVA, IZOBRAZHENNYE NA RIS.~76, ESLI MY
NAZOVEM LENTY~$A$, $B$, $C$, $D$, A NE~$T1$, $T2$, $T3$, $T4$.
eTO UDOBNOE I NAGLYADNOE PREDSTAVLENIE MNOGIH SUSHCHESTVENNYH SVOJSTV SHEMY
SLIYANIYA; NAPRIMER, ESLI OTREZOK NA UROVNE~$0$ DEREVA (KORENX) DOLZHEN BYTX
VOZRASTAYUSHCHIM, TO OTREZKI NA UROVNE~$1$ DOLZHNY BYTX UBYVAYUSHCHIMI, OTREZKI NA
UROVNE~$2$---VOZRASTAYUSHCHIMI I~T.~D.; NEKOTORYJ NACHALXNYJ OTREZOK
YAVLYAETSYA VOZRASTAYUSHCHIM TOGDA I TOLXKO TOGDA, KOGDA SOOTVETSTVUYUSHCHIJ VNESHNIJ
UZEL NAHODITSYA NA UROVNE S CHETNYM NOMEROM. dALEE, SUMMARNOE KOLICHESTVO
NACHALXNYH OTREZKOV, OBRABATYVAEMYH PRI SLIYANII (NE VKLYUCHAYA NACHALXNOE
RASPREDELENIE), V TOCHNOSTI RAVNO \emph{DLINE VNESHNEGO PUTI} DEREVA, TAK
KAK KAZHDYJ NACHALXNYJ OTREZOK NA UROVNE~$k$ OBRABATYVAETSYA ROVNO $k$~RAZ.
%%362
\picture{rIS.~76. pREDSTAVLENIYA TREH SHEM SLIYANIYA V VIDE DEREVA.}
lYUBAYA SHEMA SLIYANIYA IMEET PREDSTAVLENIE V VIDE DEREVA, NO NE KAZHDOE DEREVO
OPREDELYAET SHEMU SLIYANIYA. dEREVO, VNUTRENNIE UZLY KOTOROGO POMECHENY
CHISLAMI OT~$1$ DO~$m$ I REBRA KOTOROGO POMECHENY IMENAMI LENT, IZOBRAZHAET
PRAVILXNUYU SHEMU SLIYANIYA S OBRATNYM CHTENIEM TOGDA I TOLXKO TOGDA, KOGDA
a)~NIKAKIE DVA REBRA, SMEZHNYE S ODNIM VNUTRENNIM UZLOM, NE IMEYUT
ODINAKOVOGO IMENI LENTY;
b)~ESLI~$i>j$ I ESLI $A$~ESTX IMYA LENTY, TO DEREVO NE SODERZHIT KONFIGURACII
\picture{p.362}
%%363
c)~ESLI~$i<j<k<l$ I ESLI~$A$---IMYA LENTY, TO DEREVO NE SODERZHIT TAKIH PAR:
\picture{p.363.1}
uSLOVIE~(a) OCHEVIDNO, TAK KAK VVODNYE I VYVODNAYA LENTY SLIYANIYA DOLZHNY
BYTX RAZLICHNY; USLOVIE~(b) TAKZHE OCHEVIDNO. uSLOVIE "NEPERESECHENIYA"~(c)
OTRAZHAET HARAKTERNOE DLYA OPERACIJ OBRATNOGO CHTENIYA LENTY OGRANICHENIE
"POSLEDNIM VKLYUCHAETSYA --- PERVYM ISKLYUCHAETSYA". oTREZOK, OBRAZOVANNYJ NA
SHAGE~$k$, DOLZHEN BYTX UDALEN PREZHDE OTREZKA, SFORMIROVANNOGO RANEE
NA TOJ ZHE LENTE; SLEDOVATELXNO, KONFIGURACII~(4) NEVOZMOZHNY. nETRUDNO
PROVERITX, CHTO LYUBOE POMECHENNOE DEREVO, UDOVLETVORYAYUSHCHEE USLOVIYAM~(a),
(b), (c), DEJSTVITELXNO SOOTVETSTVUET NEKOTOROJ SHEME SLIYANIYA S OBRATNYM
CHTENIEM.
eSLI IMEETSYA $T$~LENTOCHNYH USTROJSTV, TO IZ USLOVIYA~(a) SLEDUET, CHTO
STEPENX KAZHDOGO VNUTRENNEGO UZLA RAVNA~$T-1$ ILI MENXSHE. pRIPISYVANIE
PODHODYASHCHIH METOK VSEM TAKIM DEREVXYAM NE VSEGDA VOZMOZHNO; NAPRIMER,
ESLI~$T=3$, TO NE SUSHCHESTVUET SHEMY SLIYANIYA S DEREVOM VIDA
\picture{p.363.2}
tAKAYA FORMA DEREVA PRIVELA BY K OPTIMALXNOJ SHEME SLIYANIYA, ESLI BY MY
SMOGLI SOOTVETSTVUYUSHCHIM OBRAZOM PRIPISATX NOMERA SHAGOV I NOMERA LENT,
POSKOLXKU |TO EDINSTVENNOE DEREVO S MINIMALXNOJ DLINOJ VNESHNEGO PUTI
SREDI DEREVXEV, IMEYUSHCHIH CHETYRE VNESHNIH UZLA. nO V SILU SIMMETRII |TOJ
DIAGRAMMY IMEETSYA, PO SUSHCHESTVU, TOLXKO ODIN SPOSOB POMETITX EE, SOBLYUDAYA
USLOVIYA~(a) I~(b):
\picture{p.363.3}
%%364
oDNAKO PRI |TOM NARUSHAETSYA USLOVIE~(c). dEREVO, KOTOROE MOZHET BYTX
POMECHENO V SOOTVETSTVII S UPOMYANUTYMI USLOVIYAMI S ISPOLXZOVANIEM~$T$ ILI
MENXSHE IMEN LENT, NAZYVAETSYA $T\hbox{-lifo}$\note{1}%
{"Lifo"---ABBREVIATURA DLYA "last in---first out" (POSLEDNIM VKLYUCHAETSYA---
PERVYM ISKLYUCHAETSYA).---{\it pRIM. PEREV.\/}} DEREVOM.
dRUGOJ SPOSOB HARAKTERIZOVATX VSE POMECHENNYE DEREVXYA, KOTORYE MOGUT
VOZNIKNUTX IZ SHEMY SLIYANIYA, SOSTOIT V TOM, CHTOBY RASSMOTRETX, KAK VSE
PODOBNYE DEREVXYA MOGUT BYTX "VYRASHCHENY". nACHNEM S NEKOTOROGO IMENI LENTY,
SKAZHEM~$A$, I S ROSTKA DEREVA
\picture{p.364.1}
shAG~$i$ ROSTA DEREVA SOSTOIT V VYBORE RAZLICHNYH IMEN LENT~$B$, $B_1$,
$B_2$,~\dots, $B_k$ I ZAMENE \emph{POZZHE VSEGO OBRAZOVANNOGO} UZLA,
SOOTVETSTVUYUSHCHEGO~$B$,
\picture{p.364.2}
eTO PRAVILO "POSLEDNIM OBRAZOVAN---PERVYM RASTET" V TOCHNOSTI OPISYVAET
SPOSOB POSTROENIYA PREDSTAVLENIYA V VIDE DEREVA NEPOSREDSTVENNO IZ
VEKTORNOGO PREDSTAVLENIYA.
oPREDELENIE STROGO OPTIMALXNOJ $T\hbox{-LENTOCHNOJ}$ SHEMY SLIYANIYA,
T.~E.~DEREVA, IMEYUSHCHEGO MINIMALXNUYU DLINU PUTI SREDI
VSEH $T\hbox{-lifo}$~DEREVXEV S DANNYM CHISLOM VNESHNIH UZLOV, KAZHETSYA
VESXMA TRUDNOJ ZADACHEJ. sLEDUYUSHCHAYA NEOCHEVIDNAYA SHEMA, NAPRIMER,
OKAZYVAETSYA NAILUCHSHIM SPOSOBOM SLITX SEMX NACHALXNYH OTREZKOV, IMEYA
CHETYRE LENTY I CHITAYA V OBRATNOM NAPRAVLENII:
%%365
oDNOPUTEVOE SLIYANIE NEOBHODIMO PO SUSHCHESTVU DLYA DOSTIZHENIYA OPTIMUMA!
(sM.~UPR.~8.) s DRUGOJ STORONY, NE TAK TRUDNO DATX KONSTRUKCII,
\emph{ASIMPTOTICHESKI} OPTIMALXNYE DLYA LYUBOGO FIKSIROVANNOGO~$T$.
pUSTX~$K_T(n)$---MINIMALXNAYA DLINA VNESHNEGO PUTI, DOSTIZHIMAYA V
$T\hbox{-lifo}$~DEREVE S $n$~VNESHNIMI UZLAMI. iSPOLXZUYA TEORIYU, RAZVITUYU V
P.~2.3.4.5, NETRUDNO DOKAZATX, CHTO
$$
K_T(n)\ge nq - \floor{((T-1)^q-n)/(T-2)}, \quad
q=\ceil{\log_{T-1} n},
\eqno(9)
$$
TAK KAK |TO MINIMALXNAYA DLINA VNESHNEGO PUTI LYUBOGO DEREVA S $n$~VNESHNIMI
UZLAMI I STEPENXYU LYUBOGO UZLA~$<T$. k NASTOYASHCHEMU MOMENTU IZVESTNY
OTNOSITELXNO NEMNOGIE TOCHNYE ZNACHENIYA~$K_T(n)$. zDESX PRIVEDENY NEKOTORYE
VERHNIE OCENKI, KOTORYE, VEROYATNO, TOCHNY:
$$
\vbox{\halign{
\hfil$#$ &&\bskip \hfil$#$ \cr
n = 1 & 2 & 3 & 4 & 5& 6& 7& 8& 9& 10& 11& 12& 13& 14& 15\cr
K_3(n) \le 0 & 2 & 5 & 9 & 12& 16& 21& 25& 30& 34& 39& 45& 50& 56& 61\cr
K_4(n) \le 0 & 2 & 3 & 6 & 8& 11& 14& 17& 20& 24& 27& 31& 33& 37& 40\cr
}}
\eqno (10)
$$
kARP OBNARUZHIL, CHTO LYUBOE DEREVO S VNUTRENNIMI UZLAMI STEPENI~$< T$
YAVLYAETSYA \emph{POCHTI} $T\hbox{-lifo}$~DEREVOM V TOM SMYSLE, CHTO ONO MOZHET
BYTX SDELANO $T\hbox{-lifo}$ S POMOSHCHXYU ZAMENY NEKOTORYH VNESHNIH UZLOV NA
ODNOPUTEVYE SLIYANIYA. fAKTICHESKI POSTROENIE PODHODYASHCHEJ RASSTANOVKI METOK
VYPOLNYAETSYA, DOVOLXNO PROSTO. pUSTX~$A$---KONKRETNOE IMYA LENTY. bUDEM
DEJSTVOVATX SLEDUYUSHCHIM OBRAZOM:
\medskip
{\sl shAG~1.\/} pRIPISATX IMENA LENT REBRAM DIAGRAMMY DEREVA LYUBYM SPOSOBOM,
SOVMESTIMYM S USLOVIEM~(a), UKAZANNYM VYSHE, ODNAKO TAK, CHTOBY SPECIALXNOE
IMYA~$A$ ISPOLXZOVALOSX TOLXKO V SAMOM LEVOM REBRE VETVI.
\smallskip
{\sl shAG~2.\/} zAMENITX KAZHDYJ VNESHNIJ UZEL VIDA
\picture{p.365}
ESLI TOLXKO~$B\ne A$.
\smallskip
{\sl shAG~3.\/} zANUMEROVATX VNUTRENNIE UZLY V PRYAMOM PORYADKE\note{1}%
{sM.~P.~2.3.1.---{\sl pRIM. PEREV.\/}}.
rEZULXTATOM BUDET RASSTANOVKA METOK, UDOVLETVORYAYUSHCHAYA USLOVIYAM~(a), (b), (c).
\medskip
%%366
nAPRIMER, ESLI MY NACHNEM S DEREVA
\picture{p.366.1}
I TREH LENT, TO |TA PROCEDURA MOGLA BY PRIPISATX METKI TAKIM OBRAZOM:
\picture{p.366.2}
nETRUDNO PROVERITX, CHTO KONSTRUKCIYA kARPA UDOVLETVORYAET DISCIPLINE
"POSLEDNIM OBRAZOVAN---PERVYM RASTET" V SILU SVOJSTV PRYAMOGO PORYADKA (SM.~UPR.~12).
zAMETIM, CHTO REZULXTATOM |TOGO POSTROENIYA YAVLYAETSYA SHEMA SLIYANIYA, V
KOTOROJ VSE NACHALXNYE OTREZKI POYAVLYAYUTSYA NA LENTE~$A$. eTO PREDPOLAGAET
SLEDUYUSHCHUYU SHEMU RASPREDELENIYA I SORTIROVKI, KOTORUYU MOZHNO NAZVATX
SLIYANIEM V \emph{PRYAMOM PORYADKE.}
%% !!! OPREDELITX STILX, SVYAZANNYJ S ALGORITMOM
{\medskip\narrower
\item{\bf P1.}~rASPREDELYATX NACHALXNYE OTREZKI NA LENTU~$A$, POKA VVOD NE
BUDET ISCHERPAN. pUSTX~$S$---CHISLO VSEH NACHALXNYH OTREZKOV.
\item{\bf P2.}~vYPOLNYATX PRIVEDENNOE VYSHE POSTROENIE, ISPOLXZUYA
$(T-1)\hbox{-ARNOE}$ DEREVO S $S$~VNESHNIMI UZLAMI S MINIMALXNOJ DLINOJ
PUTI, POLUCHAYA $T\hbox{-lifo}$~DEREVO, DLINA VNESHNEGO PUTI KOTOROGO
PREVYSHAET NIZHNYUYU GRANICU~(9) NE BOLEE, CHEM NA~$S$.
\item{\bf P3.}~sLIVATX OTREZKI V SOOTVETSTVII S |TOJ SHEMOJ.
\endmark
\medskip}
rEZULXTAT V UKAZANNOJ SHEME POLUCHAETSYA NA KAKOJ UGODNO LENTE. nO
\emph{|TA SHEMA IMEET ODIN SERXEZNYJ IZ®YAN.}
(vIDIT LI CHITATELX, CHTO IMENNO ZDESX BUDET NEPRAVILXNO RABOTATX?) dELO
%%367
V TOM, CHTO SHEMA TREBUET, CHTOBY PERVONACHALXNO NEKOTORYE IZ OTREZKOV NA~$A$
BYLI VOZRASTAYUSHCHIMI, A NEKOTORYE---UBYVAYUSHCHIMI V ZAVISIMOSTI OT TOGO,
POYAVLYAETSYA LI SOOTVETSTVUYUSHCHIJ VNESHNIJ UZEL NA NECHETNOM ILI CHETNOM UROVNE.
eTU PROBLEMU MOZHNO RAZRESHITX, NE ZNAYA~$S$ ZARANEE, PUTEM KOPIROVANIYA
OTREZKOV, KOTORYE DOLZHNY BYTX UBYVAYUSHCHIMI, NA VSPOMOGATELXNUYU LENTU (ILI
LENTY) NEPOSREDSTVENNO PERED TEM, KAK ONI TREBUYUTSYA. tOGDA SUMMARNOE
KOLICHESTVO OPERACIJ, IZMERYAEMOE V DLINAH NACHALXNYH OTREZKOV, OKAZHETSYA RAVNYM
$$
S \log_{T-1} S+O(S).
\eqno(13)
$$
tAKIM OBRAZOM, SLIYANIE V PRYAMOM PORYADKE OPREDELENNO LUCHSHE MNOGOFAZNOGO ILI
KASKADNOGO PRI~$S\to\infty$; V DEJSTVITELXNOSTI ONO ASIMPTOTICHESKI
\emph{OPTIMALXNO,} TAK KAK~(9) POKAZYVAET, CHTO~$S\log_{T-1} S+O(S)$---|TO
NAILUCHSHEE, CHTO MY VOOBSHCHE MOZHEM NADEYATXSYA POLUCHITX S $T$~LENTAMI. s DRUGOJ
STORONY, DLYA SRAVNITELXNO NEBOLXSHIH ZNACHENIJ~$S$, OBYCHNO VSTRECHAYUSHCHIHSYA
NA PRAKTIKE, SLIYANIE V PRYAMOM PORYADKE VESXMA NE|FFEKTIVNO;
MNOGOFAZNYJ ILI KASKADNYJ METODY PROSHCHE I BYSTREE, ESLI $S$~OTNOSITELXNO
MALO. vOZMOZHNO, UDASTSYA IZOBRESTI PROSTUYU SHEMU RASPREDELENIYA I SLIYANIYA,
KOTORAYA SRAVNIMA S MNOGOFAZNOJ I KASKADNOJ DLYA NEBOLXSHIH~$S$ I
ASIMPTOTICHESKI OPTIMALXNA PRI BOLXSHIH~$S$.
nIZHE V UPRAZHNENIYAH VTOROJ CHASTI DEMONSTRIRUETSYA, KAK kARP ANALOGICHNYM
OBRAZOM POSTAVIL VOPROS DLYA SLIYANIYA S \emph{PRYAMYM CHTENIEM.} tEORIYA
OKAZYVAETSYA V |TOM SLUCHAE ZNACHITELXNO- BOLEE SLOZHNOJ, HOTYA BYLI POLUCHENY
NEKOTORYE VESXMA INTERESNYE REZULXTATY.
\excercises (pervaya chast')
\ex[17] pRI SLIYANII S PRYAMYM CHTENIEM CHASTO UDOBNO OTMECHATX KONEC KAZHDOGO
OTREZKA NA LENTE PUTEM DOBAVLENIYA ISKUSSTVENNOJ "KONCEVOJ" ZAPISI S
KLYUCHOM~$+\infty$. kAK SLEDUET VIDOIZMENITX |TOT METOD PRI OBRATNOM CHTENII?
\ex[20] bUDUT LI STOLBCY TABLICY, ANALOGICHNOJ~(1), VSEGDA NEUBYVAYUSHCHIMI,
ILI BYVAYUT SLUCHAI, KOGDA NAM PRIDETSYA "VYCHITATX" OTREZKI S NEKOTOROJ
LENTY PRI PEREHODE OT ODNOGO UROVNYA K SLEDUYUSHCHEMU?
\rex[20] dOKAZHITE, CHTO METOD MNOGOFAZNOGO RASPREDELENIYA, OPISANNYJ V SVYAZI
S~(1), DAET POSLE ZAVERSHENIYA SORTIROVKI NA LENTE~T1, VSEGDA OTREZOK~$A$,
ESLI PERVONACHALXNO NA~T1 BYLO~$ADA\ldots$, A NA~T2--T5 BYLO~$DAD\ldots\,$.
\ex[22] kAK VY OCENIVAETE IDEYU VYPOLNYATX MNOGOFAZNOE SLIYANIE S OBRATNYM
CHTENIEM, RASPREDELIV VSE OTREZKI V \emph{VOZRASTAYUSHCHEM} PORYADKE I SCHITAYA,
CHTO VSE POZICII~"$D$" PERVONACHALXNO ZAPOLNENY FIKTIVNYMI OTREZKAMI?
\rex[23] kAKIE FORMULY DLYA STROK CHISEL SLIYANIYA VMESTO~(8), (9), (10)
I~(11) IZ~5.4.2 BUDUT SPRAVEDLIVY DLYA MNOGOFAZNOGO SLIYANIYA S OBRATNYM
CHTENIEM? iZOBRAZITE CHISLA SLIYANIYA DLYA RASPREDELENIYA PYATOGO UROVNYA NA
SHESTI LENTAH, NARISOVAV DIAGRAMMU, ANALOGICHNUYU RIS.~71(a).
\ex[07] kAKOVO VEKTORNOE PREDSTAVLENIE SHEMY SLIYANIYA,
PREDSTAVLENIEM KOTOROJ V VIDE DEREVA YAVLYAETSYA~(8)?
%%368
\ex[16] nARISUJTE PREDSTAVLENIE V VIDE DEREVA SHEMY SLIYANIYA S OBRATNYM
CHTENIEM, OPREDELENNOJ SLEDUYUSHCHEJ POSLEDOVATELXNOSTXYU VEKTOROV:
{\def\!{\phantom{+}}\def\y#1{y^{(#1)}}\ctable{
$#$&$\hbox{}#$ \bskip & $#$&$\hbox{}#$ \bskip& $#$&$\hbox{}#$ \cr
v^{(33)} &= (\!20,\!9,\!5) & \y{22} &= (+1, -1, +1) & \y{10} &= (+1, +1, -1)\cr
\y{33} &= (+1, -1, +1) & \y{21} &= (-1, +1, +1) & \y{9} &= (+1, -1, +1) \cr
\y{32} &= (+1, +1, -1) & \y{20} &= (+1, +1, -1) & \y{8} &= (+1, +1, -1) \cr
\y{31} &= (+1, +1, -1) & \y{19} &= (-1, +1, +1) & \y{7} &= (+1, +1, -1) \cr
\y{30} &= (+1, +1, -1) & \y{18} &= (+1, +1, -1) & \y{6} &= (+1, +1, -1) \cr
\y{29} &= (+1, -1, +1) & \y{17} &= (+1, +1, -1) & \y{5} &= (-1, +1, +1) \cr
\y{28} &= (-1, +1, +1) & \y{16} &= (+1, +1, -1) & \y{4} &= (+1, -1, +1) \cr
\y{27} &= (+1, -1, +1) & \y{15} &= (+1, +1, -1) & \y{3} &= (-1, +1, +1) \cr
\y{26} &= (+1, -1, +1) & \y{14} &= (+1, -1, +1) & \y{2} &= (+1, -1, +1) \cr
\y{25} &= (+1, +1, -1) & \y{13} &= (+1, -1, +1) & \y{1} &= (-1, +1, +1) \cr
\y{24} &= (+1, -1, +1) & \y{12} &= (-1, +1, +1) & \y{0} &=(\!1,\!0,\!0) \cr
\y{23} &= (+1, -1, +1) & \y{11} &= (+1, +1, -1)\cr
}}
\ex[23] dOKAZHITE, CHTO~(8)---OPTIMALXNYJ SPOSOB SLIYANIYA S OBRATNYM CHTENIEM
PRI~$S=7$ I~$T=4$ I CHTO VSE METODY, IZBEGAYUSHCHIE ODNOPUTEVOGO SLIYANIYA, HUZHE.
\ex[m22] dOKAZHITE NIZHNYUYU OCENKU~(9).
\ex[41] pRI POMOSHCHI evm SOSTAVXTE TABLICU TOCHNYH ZNACHENIJ~$K_T(n)$.
\rex[20] vERNO LI UTVERZHDENIE, CHTO DLYA LYUBOJ SHEMY SLIYANIYA S OBRATNYM
CHTENIEM, NE ISPOLXZUYUSHCHEJ NICHEGO, KROME $(T-1)\hbox{-PUTEVOGO}$ SLIYANIYA,
NEOBHODIMO, CHTOBY OTREZKI NA KAZHDOJ LENTE CHEREDOVALISX: $ADAD\ldots$,
T.~E.\ ONA NE BUDET RABOTATX, ESLI DVA SOSEDNIH OTREZKA OKAZHUTSYA ODINAKOVO UPORYADOCHENNYMI?
\ex[22] dOKAZHITE, CHTO KONSTRUKCIYA S PRYAMYM PORYADKOM kARPA VSEGDA POROZHDAET
POMECHENNOE DEREVO, UDOVLETVORYAYUSHCHEE USLOVIYAM~(a), (b), (c).
\ex[1B] sDELAJTE~(12) BOLEE |FFEKTIVNYM, UDALIV KAK MOZHNO
BOLXSHE ODNOPUTEVYH SLIYANIJ, ODNAKO TAK, CHTOBY PRYAMOJ PORYADOK VSE ESHCHE DAVAL
PRAVILXNUYU RASSTANOVKU METOK U VNUTRENNIH UZLOV.
\ex[40] pRIDUMAJTE ALGORITM, KOTORYJ VYPOLNYAET SLIYANIE V PRYAMOM
PORYADKE BEZ YAVNOGO POSTROENIYA DEREVA V SHAGAH~P2 I~Pz, ISPOLXZUYA TOLXKO
$O(\log S)$~SLOV PAMYATI DLYA UPRAVLENIYA SLIYANIEM.
\ex[m39] kONSTRUKCIYA kARPA S PRYAMYM PORYADKOM POROZHDAET DEREVXYA S
ODNOPUTEVYM SLIYANIEM V NEKOTORYH TERMINALXNYH UZLAH. dOKAZHITE,
CHTO ESLI~$T=3$, TO MOZHNO POSTROITX ASIMPTOTICHESKIE OPTIMALXNYE
$3\hbox{-lifo}$~DEREVXYA, V KOTORYH ISPOLXZUETSYA TOLXKO DVUHPUTEVOE SLIYANIE
dRUGIMI SLOVAMI, PUSTX $\hat K_T(n)$~BUDET MINIMALXNOJ DLINOJ VNESHNEGO
PUTI SREDI VSEH $T\hbox{-lifo}$~DEREVXEV S $n$~VNESHNIMI UZLAMI, TAKIH, CHTO
KAZHDYJ VNUTRENNIJ UZEL IMEET STEPENX~$T-1$. dOKAZHITE,
CHTO~$\hat K_3(n)=n\log_2 n+O(n)$.
\ex[m46] (sOHRANYAYUTSYA OBOZNACHENIYA UPR.~15) vERNO LI,
CHTO~$\hat K_T(n)=n\log_{T-1}(n)+O(n)$ DLYA \emph{VSEH}~$T\ge 3$,
ESLI~$n \equiv 1 \pmod{T-1}$?
\rex[28] (rICHARD~d.~pRATT.) chTOBY POLUCHITX VOZRASTAYUSHCHIJ PORYADOK V
KASKADNOM SLIYANII S OBRATNYM CHTENIEM, MY MOGLI BY POTREBOVATX
\emph{CHETNOGO} CHISLA PROHODOV SLIYANIYA; |TO PREDPOLAGAET, CHTO METOD
NACHALXNOGO RASPREDELENIYA NESKOLXKO OTLICHEN OT ALGORITMA~5.4.3C.
(a)~iZMENITE~(5.4.3-1) TAK, CHTOBY BYLI PREDSTAVLENY TOLXKO TOCHNYE
RASPREDELENIYA, KOTORYE TREBUYUT CHETNOGO CHISLA PROHODOV SLIYANIYA. (b)
sKONSTRUIRUJTE SHEMU NACHALXNOGO RASPREDELENIYA,
%% 369
OSUSHCHESTVLYAYUSHCHUYU INTERPOLYACIYU MEZHDU |TIMI TOCHNYMI
RASPREDELENIYAMI. [iNACHE GOVORYA, ESLI CHISLO NACHALXNYH OTREZKOV POPADAET
MEZHDU TOCHNYMI RASPREDELENIYAMI, TO ZHELATELXNO SLITX NEKOTORYE (NO NE VSE)
OTREZKI DVAZHDY, CHTOBY DOSTIGNUTX TOCHNOGO RASPREDELENIYA.]
\ex[46] pREDPOLOZHIM, CHTO IMEETSYA $T$~LENTOCHNYH USTROJSTV DLYA
NEKOTOROGO~$T\ge3$ I CHTO $T1$~SODERZHIT $N$~ZAPISEJ, V TO VREMYA KAK
OSTALXNYE LENTY PUSTY. vOZMOZHNO LI OBRATITX PORYADOK ZAPISEJ NA~$T1$ ZA
CHISLO SHAGOV, MENXSHEE~$O(N\log N)$, BEZ OBRATNOGO CHTENIYA? (eTA OPERACIYA
YAVLYAETSYA, KONECHNO, TRIVIALXNOJ, ESLI DOPUSKAETSYA OBRATNOE CHTENIE.)
sM.~V~UPR.~5.2.5-14 KLASS TAKIH ALGORITMOV, KOTORYE, ODNAKO, TRATYAT
PORYADKA $N \log N$~SHAGOV.
uprazhneniya. (vtoraya chast')
sLEDUYUSHCHIE UPRAZHNENIYA RAZVIVAYUT TEORIYU LENTOCHNOGO SLIYANIYA S PRYAMYM CHTENIEM.
v |TOM SLUCHAE KAZHDAYA LENTA DEJSTVUET KAK OCHEREDX, A NE KAK STEK. sHEMU
SLIYANIYA MOZHNO PREDSTAVITX POSLEDOVATELXNOSTXYU
VEKTOROV~$y^{(n)}\ldots{}y^{(1)}y^{(0)}$ TOCHNO TAK ZHE, KAK V TEKSTE, NO
KOGDA MY PREOBRAZUEM VEKTORNOE PREDSTAVLENIE V PREDSTAVLENIE V VIDE DEREVA,
TO MY ZAMENYAEM PRAVILO "POSLEDNIM OBRAZOVAN---PERVYM RASTET" NA "PERVYM
OBRAZOVAN---PERVYM RASTET". tAKIM OBRAZOM, NEDOPUSTIMAYA KONFIGURACIYA~(4)
DOLZHNA BYTX ZAMENENA NA
\picture{p.369}
dEREVO, KOTOROE MOZHET BYTX POMECHENO TAK, CHTOBY IZOBRAZHATX SLIYANIE S
PRYAMYM CHTENIEM NA $T$~LENTAH, NAZYVAETSYA~$T\hbox{-fifo}$%
\note{1}%
{"Fifo"---ABBREVIATURA OT "first in first out" (PERVYM VKLYUCHAETSYA---PERVYM
ISKLYUCHAETSYA).---{\sl pRIM. PEREV.\/}}
PO ANALOGII S TERMINOM~$T\hbox{-lifo}$ V SLUCHAE OBRATNOGO CHTENIYA.
eSLI LENTY MOZHNO PROCHITATX V OBRATNOM NAPRAVLENII, ONI OBRAZUYUT OCHENX
HOROSHIE STEKI. nO, K SOZHALENIYU, ONI NE MOGUT OBRAZOVATX OCHENX HOROSHIE
UNIVERSALXNYE OCHEREDI. eSLI MY V PROIZVOLXNOM PORYADKE ZAPISYVAEM I CHITAEM
PO PRAVILU "PERVYM VKLYUCHAETSYA---PERVYM ISKLYUCHAETSYA", TO PRIHODITSYA TRATITX
MNOGO VREMENI NA PEREMOTKU OT ODNOJ CHASTI LENTY K DRUGOJ. hUZHE TOGO---MY
VSKORE PROSKOCHIM KONEC LENTY! mY STALKIVAEMSYA S TOJ ZHE PROBLEMOJ, CHTO I
PROBLEMA VYHODA OCHEREDI ZA GRANICU PAMYATI [SM.\ SOOTNOSHENIYA~(2.2.2-4)
I~(2.2.2-5)], NO RESHENIE V VIDE~(2.2.2-6) I~(2.2.2-7) NE PRIMENIMO K
LENTAM, TAK KAK ONI NE YAVLYAYUTSYA KOLXCEVYMI. pO|TOMU DEREVO BUDEM NAZYVATX
\emph{SILXNYM} $T\hbox{-fifo}$~DEREVOM, ESLI ONO MOZHET BYTX POMECHENO TAK,
CHTOBY SOOTVETSTVUYUSHCHAYA SHEMA SLIYANIYA ISPOLXZOVALA LENTY, PODCHINYAYASX
OSOBOJ DISCIPLINE: "ZAPISATX, PEREMOTATX, PROCHITATX VSE, PEREMOTATX;
ZAPISATX, PEREMOTATX, PROCHITATX VSE, PEREMOTATX; I T.~D.".
\ex[22] (r.~m.~kARP.) nAJDITE BINARNOE DEREVO, KOTOROE NE
YAVLYAETSYA~$3\hbox{-fifo}$.
\rex[22] sFORMULIRUJTE USLOVIE "SILXNOGO $T\hbox{-fifo}$" DEREVA V
TERMINAH DOSTATOCHNO PROSTOGO PRAVILA OTNOSITELXNO NEDOPUSTIMYH
KONFIGURACIJ METOK LENT, ANALOGICHNOGO ($4'$).
\ex[18] nARISUJTE PREDSTAVLENIE V VIDE DEREVA SHEMY SLIYANIYA S PRYAMYM
CHTENIEM; OPREDELENNOJ POSREDSTVOM VEKTOROV V UPR.~7. yaVLYAETSYA LI
|TO DEREVO SILXNYM~$3\hbox{-fifo}$?
\ex[28] (r.~m.~kARP.) dOKAZHITE, CHTO PREDSTAVLENIYA V VIDE DEREVA
MNOGOFAZNOGO I KASKADNOGO SLIYANIYA S TOCHNYM RASPREDELENIEM POLNOSTXYU ODINAKOVY
%% 370
KAK V SLUCHAE OBRATNOGO CHTENIYA, TAK I V SLUCHAE PRYAMOGO CHTENIYA, ZA
ISKLYUCHENIEM NOMEROV, KOTORYMI POMECHENY VNUTRENNIE UZLY. nAJDITE BOLEE
SHIROKIJ KLASS VEKTORNYH, PREDSTAVLENIJ SHEM SLIYANIYA, DLYA KOTORYH |TO VERNO.
\ex[24] (r.~m.~kARP.) bUDEM GOVORITX, CHTO OTREZOK~$y^{(q)}\ldots{}y^{(r)}$
SHEMY SLIYANIYA YAVLYAETSYA \dfn{STADIEJ,} ESLI NIKAKAYA VYVODNAYA LENTA NE
ISPOLXZUETSYA V DALXNEJSHEM KAK VVODNAYA, T.~E.\ ESLI NE SUSHCHESTVUET~$i$, $j$,
$k$, TAKIH, CHTO~$q\ge i> k \ge r$ I~$y^{(i)}_j=-1$, $y^{(k)}_j=+1$. cELX
|TOGO UPRAZHNENIYA---DOKAZATX, CHTO \emph{KASKADNOE SLIYANIE MINIMIZIRUET CHISLO
STADIJ} SREDI VSEH SHEM SLIYANIYA S TEM ZHE CHISLOM LENT I NACHALXNYH OTREZKOV.
uDOBNO VVESTI NEKOTORYE OBOZNACHENIYA. bUDEM PISATX~$v\to w$, ESLI~$v$
I~$w$---TAKIE $T\hbox{-VEKTORY}$, CHTO SUSHCHESTVUET SHEMA SLIYANIYA, KOTORAYA V
SVOEJ PERVOJ STADII PEREVODIT~$w$ V~$v$ (T.~E.\ SUSHCHESTVUET SHEMA
SLIYANIYA~$y^{(m)}\ldots{}y^{(0)}$, TAKAYA, CHTO
$y^{(m)}\ldots{}y^{(l+1)}$~YAVLYAETSYA STADIEJ, $w=y^{(m)}+\cdots+y^{(0)}$
I~$v=y^{(l)}+\cdots+y^{(0)}$). bUDEM PISATX~$v\preceq w$, ESLI~$v$
I~$w$---$T\hbox{-VEKTORY}$, TAKIE, CHTO SUMMA NAIBOLXSHIH $k$~|LEMENTOV
VEKTORA~$v$ NE PREVYSHAET SUMMY NAIBOLXSHIH $k$~|LEMENTOV VEKTORA~$w$
PRI~$1\le k \le T$. tAK, NAPRIMER,
$(2, 1, 2, 2, 2, 1) \preceq (1, 2, 3, 0, 3, 1)$,
TAK KAK $2\le 3$, $2+2\le 3+3$,~\dots, $2+2+2+2+ 1+1\le 3+3+2+1+1 +0$.
nAKONEC, ESLI~$v=(v_1,~\ldots, v_T)$,
TO PUSTX~$C(v)=(s_T, s_{T-2}, s_{T-3},~\ldots, s_1, 0)$, GDE $s_k$~ESTX
SUMMA NAIBOLXSHIH $k$~|LEMENTOV VEKTORA~$v$.
%% !!! SSYLKA NA UPRAZHNENIE
(a)~dOKAZHITE, CHTO~$v\to C(v)$. (b)~dOKAZHITE, CHTO~$v\preceq w$
VLECHET~$C(v)\preceq C(w)$. (c)~sCHITAYA IZVESTNYM REZULXTAT UPR.~24,
DOKAZHITE, CHTO KASKADNOE SLIYANIE MINIMIZIRUET CHISLO STADIJ.
%% !!! SSYLKA NA UPRAZHNENIE
\ex[m35] iSPOLXZUYA OBOZNACHENIYA UPR.~23, DOKAZHITE, CHTO~$v\to w$
VLECHET~$w\preceq C(v)$.
%% !!! SSYLKA NA UPRAZHNENIE
\ex[m36] (r.~m.~kARP.) bUDEM GOVORITX, CHTO
SEGMENT~$y^{(q)}\ldots{}y^{(r)}$ SHEMY SLIYANIYA YAVLYAETSYA \dfn{FAZOJ,} ESLI
NI ODNA IZ LENT NE ISPOLXZUETSYA I DLYA VVODA, I DLYA VYVODA, T.~E.\ ESLI NE
SUSHCHESTVUET~$i$, $j$, $k$, TAKIH, CHTO~$q\ge i$, $k\ge r$ I~$y^{(i)}_j=+1$,
$y^{(k)}_j=-1$. cELX |TOGO UPRAZHNENIYA---ISSLEDOVATX SHEMU SLIYANIYA, KOTORAYA
MINIMIZIRUET CHISLO FAZ. mY BUDEM PISATX~$v \To w$, ESLI~$w$ MOZHET BYTX
PREOBRAZOVANO V~$v$ ZA ODNU FAZU (SR.~S~PODOBNYM OBOZNACHENIEM,
VVEDENNYM V UPR.~23), I PUSTX~$D_k(v)=(s_k+t_{k+1}, s_k+t_{k+2},~\ldots,
s_k+t_T, 0,~\ldots, 0)$, GDE~$t_j$ OBOZNACHAET~$j\hbox{-J}$ V PORYADKE
UBYVANIYA |LEMENT~$v$ I~$s_k=t_1+\cdots+t_k$. (a)~dOKAZHITE, CHTO~$v\To
D_k(v)$ PRI~$1\le k < T$. (b)~dOKAZHITE, CHTO IZ~$v\preceq w$
SLEDUET~$D_k(v)\preceq D_k(w)$ PRI~$1\le k < T$. (c)~dOKAZHITE, CHTO
IZ~$v\To w$ SLEDUET~$w\preceq D_k(v)$ DLYA NEKOTOROGO~$k$, $1\le k < T$.
(d)~sLEDOVATELXNO, SHEMA SLIYANIYA, SORTIRUYUSHCHAYA MAKSIMALXNOE CHISLO NACHALXNYH
OTREZKOV NA $T$~LENTAH ZA $q$~FAZ, MOZHET BYTX IZOBRAZHENA
POSLEDOVATELXNOSTXYU .CELYH CHISEL~$k_1 k_2~\ldots k_q$, TAKOJ,
CHTO NACHALXNOE RASPREDELENIE ESTX~$D_{k_q}(\ldots D_{k_2}(D_{k_1}(u))\ldots)$,
%!!! SSYLKA NA UPRAZHNENIE
GDE~$u=(1, 0,~\ldots, 0)$. eTA STRATEGIYA MINIMUMA FAZ, IMEET SILXNOE
$T\hbox{-fifo}$~PREDSTAVLENIE, I ONA TAKZHE VHODIT V KLASS SHEM UPR.~22.
kOGDA~$T=3$, |TO \emph{MNOGOFAZNAYA} SHEMA, A PRI~$T=4$, 5, 6, 7 |TO
VARIACIYA \emph{SBALANSIROVANNOJ} SHEMY.
%!!! SSYLKA NA UPRAZHNENIE
\ex[m46] (r.~m.~kARP). vERNO LI, CHTO OPTIMALXNAYA POSLEDOVATELXNOSTX~$k_1
k_2~\ldots k_q$, UPOMYANUTAYA V UPR.~25, VSEGDA
RAVNA~$1\ceil{T/2}\floor{T/2}\ceil{T/2}\floor{T/2}~\ldots$ DLYA VSEH~$T\ge
4$ I VSEH DOSTATOCHNO BOLXSHIH~$q$?
\subsubchap{oSCILLIRUYUSHCHAYA SORTIROVKA}%5.4.5
eSHCHE ODIN PODHOD K SORTIROVKE SLIYANIEM BYL PREDLOZHEN shELDONOM sOBELEM V
[{\sl JACM,\/} {\bf 9} (1962), 372--375]. vMESTO TOGO CHTOBY NACHINATX S
PROHODA RASPREDELENIYA, KOGDA VSE NACHALXNYE OTREZKI RASPREDELYAYUTSYA PO
LENTAM, ON PREDLOZHIL ALGORITM, KOTORYJ PEREKLYUCHAETSYA TO NA RASPREDELENIE,
TO NA SLIYANIE, TAK CHTO BOLXSHAYA CHASTX SORTIROVKI PROISHODIT ESHCHE DO TOGO,
KAK VSYA ISHODNAYA INFORMACIYA BUDET POLNOSTXYU PROSMOTRENA.
%%371
pREDPOLOZHIM, NAPRIMER, CHTO DLYA SLIYANIYA ISPOLXZUETSYA PYATX LENT. pO METODU
sOBELYA 16~NACHALXNYH OTREZKOV BUDUT SORTIROVATXSYA SLEDUYUSHCHIM OBRAZOM:
\ctable{
#\hfil\bskip&#\hfil\bskip&\hfil$#$\hfil\bskip&\hfil$#$\hfil\bskip
&\hfil$#$\hfil\bskip&\hfil$#$\hfil\bskip&\hfil$#$\hfil\bskip
&#\hfil\cr
& \hfil oPERACIYA& T1 & T2 & T3 & T4 & T5 & \hbox{sTOIMOSTX} \cr
fAZA~1.& rASPREDELENIE & A_1 & A_1 & A_1 & A_1 & - & 4\cr
fAZA~2.& sLIYANIE & - & - & - & - & D_4 & 4\cr
fAZA~3.& rASPREDELENIE & - & A_1 & A_1 & A_1 & D_4A_1& 4\cr
fAZA~4.& sLIYANIE & D_4 & - & - & - & D_4 & 4\cr
fAZA~5.& rASPREDELENIE & D_4A_1& - & A_1 & A_1 & D_4A_1& 4\cr
fAZA~6.& sLIYANIE & D_4 & D_4 & - & - & D_4 & 4\cr
fAZA~7.& rASPREDELENIE & D_4A_1& D_4A_1& - & A_1 & D_4A_1& 4\cr
fAZA~8.& sLIYANIE & D_4 & D_4 & D_4 & - & D_4 & 4\cr
fAZA~9.& sLIYANIE & - & - & - & A_{16} & - & 16\cr
}
zDESX, KAK I V P.~5.4.4, MY ISPOLXZUEM~$A_r$ I~$D_r$ DLYA OBOZNACHENIYA
SOOTVETSTVENNO VOZRASTAYUSHCHIH I UBYVAYUSHCHIH OTREZKOV OTNOSITELXNOJ DLINY~$r$.
rASSMATRIVAEMYJ METOD NACHINAET S ZAPISI PO ODNOMU NACHALXNOMU OTREZKU NA
KAZHDUYU IZ CHETYREH LENT I SLIVAET IH (CHITAYA V OBRATNOM NAPRAVLENII) NA
PYATUYU LENTU. oPYATX VOZOBNOVLYAETSYA RASPREDELENIE, NA |TOT RAZ
CIKLICHESKI SDVINUTOE NA~1 VPRAVO PO OTNOSHENIYU K LENTAM, I VTOROE SLIYANIE
DAET ESHCHE ODIN OTREZOK~$D_4$. kOGDA |TIM SPOSOBOM SFORMIROVANY CHETYRE
OTREZKA~$D_4$, DOPOLNITELXNOE SLIYANIE SOZDAET~$A_{16}$. pROCESS MOZHNO
PRODOLZHATX, SOZDAVAYA ESHCHE TRI~$A_{16}$, SLIVAYA IH V~$D_{64}$ I~T.~D.\ DO
TEH POR, POKA NE ISCHERPAYUTSYA ISHODNYE DANNYE. nE NUZHNO ZNATX ZARANEE
DLINU ISHODNYH DANNYH.
eSLI CHISLO NACHALXNYH OTREZKOV~$S$ ESTX~$4^m$, TO NETRUDNO VIDETX, CHTO |TOT
METOD OBRABATYVAET KAZHDUYU ZAPISX ROVNO $m+1$~RAZ (ODIN RAZ VO VREMYA
RASPREDELENIYA I $m$~RAZ VO VREMYA SLIYANIYA). eSLI~$S$ LEZHIT MEZHDU~$4^{m-1}$
I~$4^m$, TO MOZHNO S POMOSHCHXYU FIKTIVNYH OTREZKOV UVELICHITX~$S$ DO~$4^m$;
SLEDOVATELXNO, OBSHCHEE VREMYA SORTIROVKI BUDET OPREDELYATXSYA
$\ceil{\log_4 S}+1$~PROHODAMI PO VSEM DANNYM. eTO KAK RAZ TO, CHTO DOSTIGAETSYA
PRI SBALANSIROVANNOJ SORTIROVKE NA \emph{VOSXMI} LENTAH; V OBSHCHEM SLUCHAE
OSCILLIRUYUSHCHAYA SORTIROVKA S $T$~RABOCHIMI LENTAMI
|KVIVALENTNA SBALANSIROVANNOMU SLIYANIYU S $2(T-1)$~LENTAMI, TAK KAK
ONA DELAET $\ceil{\log_{T-1} S}+1$~PROHODOV PO DANNYM. eSLI
$S$~OKAZYVAETSYA STEPENXYU~$T-1$, TO |TO SAMOE LUCHSHEE, CHTO MOZHNO POLUCHITX
PRI \emph{LYUBOM} METODE S $T$~LENTAMI, TAK KAK ZDESX DOSTIGAETSYA
NIZHNYAYA OCENKA IZ SOOTNOSHENIYA~(5.4.4-9). s DRUGOJ STORONY,
ESLI~$S$ RAVNO~$(T-1)^{m-1}+1$, T.~E.\ ROVNO NA EDINICU BOLXSHE
STEPENI~$T-1$, TO |TOT METOD TERYAET POCHTI CELYJ PROHOD.
v UPR.~2 POKAZANO, KAK USTRANITX CHASTX |TOJ LISHNEJ RABOTY, ISPOLXZUYA
SPECIALXNUYU PROGRAMMU OKONCHANIYA. eSHCHE ODNO USOVERSHENSTVOVANIE BYLO
PREDLOZHENO V 1966~G. dENISOM~l.~b|NCHEROM,
%% 372
KOTORYJ NAZVAL SVOYU PROCEDURU PEREKRESTNYM SLIYANIEM.
[sM.~H.~Wedekind, Datenorganisation (Berlin W. de Gruyter, 1970). 164--166,
I~U.~S.~Patent~3540000 (10~NOYABRYA 1970).] oSNOVNAYA IDEYA SOSTOIT V TOM,
CHTOBY OTLOZHITX SLIYANIE DO TEH POR, POKA NE BUDET NAKOPLENO BOLXSHE SVEDENIJ
OB~$S$. mY OBSUDIM NESKOLXKO IZMENENNUYU FORMU PERVONACHALXNOJ SHEMY b|NCHERA.
eTA ULUCHSHENNAYA OSCILLIRUYUSHCHAYA SORTIROVKA DEJSTVUET SLEDUYUSHCHIM OBRAZOM:
\ctable{
#\hfil\bskip&#\hfil\bskip&\hfil$#$\hfil\bskip&\hfil$#$\hfil\bskip
&\hfil$#$\hfil\bskip&\hfil$#$\hfil\bskip&\hfil$#$\hfil\bskip
&#\hfil\cr
& oPERACIYA & T1 & T2 & T3 & T4 & t5 &
\hbox{sTOIMOSTX} \cr
fAZA~1.& rASPREDELENIE& - & A_1 & A_1 & A_1 & A_1 & 4\cr
fAZA~2.& rASPREDELENIE& - & A_1 & A_1A_1& A_1A_1& A_1A_1& 3\cr
fAZA~3.& sLIYANIE & D_4 & - & A_1 & A_1 & A_1 & 4\cr
fAZA~4.& rASPREDELENIE& D_4A_1& - & A_1 & A_1A_1& A_1A_1& 3\cr
fAZA~5.& sLIYANIE & D_4 & D_4 & - & A_1 & A_1 & 4\cr
fAZA~6.& rASPREDELENIE& D_4A_1& D_4A_1& - & A_1 & A_1A_1& 3\cr
fAZA~7.& sLIYANIE & D_4 & D_4 & D_4 & - & A_1 & 4\cr
fAZA~8.& rASPREDELENIE& D_4A_1& D_4A_1& D_4A_1& - & A_1 & 3\cr
fAZA~9.& sLIYANIE & D_4 & D_4 & D_4 & D_4 & - & 4\cr
\noalign{\smallskip
\noindent
v |TOT MOMENT MY NE SLIVAEM VSE~$D_4$ V~$A_{16}$, (ESLI TOLXKO NE
OKAZHETSYA, CHTO ISHODNYE DANNYE ISCHERPANY); LISHX POSLE TOGO, KAK ZAKONCHITSYA
\smallskip}
fAZA~15.& sLIYANIE & D_4 D_4 & D_4 D_4 & D_4 D_4 & D_4 & - & 4 \cr
\noalign {\smallskip
\noindent BUDET POLUCHEN PERVYJ OTREZOK~$A_{16}$:
\smallskip}
fAZA~16. & sLIYANIE & D_4 & D_4 & D_4 - & A_{16} & 16 \cr
\noalign{\smallskip
\noindent vTOROJ OTREZOK~$A_{16}$ POYAVITSYA POSLE SOZDANIYA ESHCHE TREH~$D_4$:
\smallskip}
fAZA~22. & sLIYANIE & D_4 D_4 & D_4 D_4 & D_4 & - & A_{16}D_4 & 4\cr
fAZA~23. & sLIYANIE & D_4 & D_4 & - & A_{16} & A_{16} & 16 \cr
}
I~T.~D.\ (SR.~S~FAZAMI~1--5). pREIMUSHCHESTVA SHEMY b|NCHERA MOZHNO VIDETX,
ESLI IMEETSYA, NAPRIMER, TOLXKO PYATX NACHALXNYH OTREZKOV: OSCILLIRUYUSHCHAYA
SORTIROVKA (EE MODIFIKACIYA IZ UPR.~2) VYPOLNYALA BY CHETYREHPUTEVOE SLIYANIE
(NA FAZE~2), ZA KOTORYM SLEDOVALO BY DVUHPUTEVOE SLIYANIE S OBSHCHEJ
STOIMOSTXYU~$4+4+4+1+5= 14$, TOGDA KAK SHEMA b|NCHERA VYPOLNYALA BY
DVUHPUTEVOE SLIYANIE (NA FAZE~3), ZA KOTORYM SLEDOVALO BY CHETYREHPUTEVOE
SLIYANIE S OBSHCHEJ STOIMOSTXYU~$4+1+2+5=12$. (oBA METODA TAKZHE TREBUYUT
NEBOLXSHIH DOPOLNITELXNYH ZATRAT, IMENNO ODNOKRATNOJ PEREMOTKI PERED
OKONCHATELXNYM SLIYANIEM.)
%%373
tOCHNOE OPISANIE METODA b|NCHERA SODERZHITSYA NIZHE V ALGORITME~B. k
SOZHALENIYU, SOOTVETSTVUYUSHCHUYU PROCEDURU, PO-VIDIMOMU, TRUDNEJ PONYATX, CHEM
ZAPROGRAMMIROVATX; LEGCHE OB®YASNITX |TOT METOD evm, CHEM PROGRAMMISTU!
chASTICHNO |TO PROISHODIT PO TOJ PRICHINE, CHTO REKURSIVNYJ METOD VYRAZHEN V
ITERATIVNOM VIDE I ZATEM PODVERGNUT NEKOTOROJ OPTIMIZACII; CHITATELX,
VOZMOZHNO, OBNARUZHIT, CHTO NEOBHODIMO NESKOLXKO RAZ PROSLEDITX ZA RABOTOJ
ALGORITMA, CHTOBY DEJSTVITELXNO OSOZNATX, CHTO ZHE PROISHODIT.
\alg B.(oSCILLIRUYUSHCHAYA SORTIROVKA S PEREKRESTNYM RASPREDELENIEM.) eTOT
ALGORITM BERET PERVONACHALXNYE OTREZKI I RASPREDELYAET IH NO LENTAM, VREMYA
OT VREMENI PRERYVAYA PROCESS RASPREDELENIYA, CHTOBY SLITX SODERZHIMOE
NEKOTORYH LENT.
\picture{rIS.~77. oSCILLIRUYUSHCHAYA SORTIROVKA S PEREKRESTNYM RASPREDELENIEM.}
v ALGORITME ISPOLXZUETSYA $P\hbox{-PUTEVOE}$ SLIYANIE I PREDPOLAGAETSYA,
CHTO ESTX $T=P+1\ge 3$~LENTOCHNYH USTROJSTV (NE SCHITAYA USTROJSTVA, KOTOROE
MOZHET BYTX NEOBHODIMO DLYA HRANENIYA ISHODNYH DANNYH). lENTOCHNYE USTROJSTVA
DOLZHNY DOPUSKATX CHTENIE KAK V PRYAMOM, TAK I V OBRATNOM NAPRAVLENII; ONI
OBOZNACHENY CHISLAMI~0, 1,~\dots, $P$. iSPOLXZUYUTSYA SLEDUYUSHCHIE MASSIVY:
{\medskip\narrower
\item{$|D|[j]$,} $0\le j \le P$---CHISLO FIKTIVNYH OTREZKOV, NALICHIE KOTORYH
PREDPOLAGAETSYA V KONCE LENTY~$j$.
\item{$|A|[l, j]$,} $0\le l \le L$, $0\le j \le P$. zDESX~$L$---DOSTATOCHNO
BOLXSHOE CHISLO, TAKOE, CHTO BUDET VVEDENO NE BOLEE~$P^{L+1}$ NACHALXNYH
OTREZKOV. eSLI~$|A|[l, j]=k \ge 0$, TO NA LENTE~$j$ IMEETSYA OTREZOK
NOMINALXNOJ DLINY~$P^k$, SOOTVETSTVUYUSHCHIJ "UROVNYU~$l$" RABOTY ALGORITMA.
eTOT OTREZOK VOZRASTAYUSHCHIJ, ESLI $k$~CHETNO, I UBYVAYUSHCHIJ, ESLI $k$~NECHETNO.
$|A|[l, j]=-1$~OZNACHAET, CHTO NA UROVNE~$l$ LENTA~$j$ NE ISPOLXZUETSYA.
\medskip}
\noindent iNSTRUKCIYA "ZAPISATX NACHALXNYJ OTREZOK NA LENTU~$j$"
YAVLYAETSYA SOKRASHCHENNYM OBOZNACHENIEM SLEDUYUSHCHIH DEJSTVIJ:
%%374
{\medskip\narrower
\noindent uSTANOVITX~$|A|[l, j]\asg 0$. eSLI ISHODNYE DANNYE ISCHERPANY, TO
UVELICHITX~$|D|[j]$ NA~1; V PROTIVNOM SLUCHAE ZAPISATX OTREZOK NA
LENTU~$j$ (V VOZRASTAYUSHCHEM PORYADKE).
\medskip}
\noindent iNSTRUKCIYA "SLITX NA LENTU~$j$" ISPOLXZUETSYA KAK KRATKOE
OBOZNACHENIE SLEDUYUSHCHIH DEJSTVIJ:
{\medskip\narrower
\noindent eSLI~$|D|[i]>0$ DLYA VSEH~$i\ne j$, TO UMENXSHITX~$|D|[i]$ NA~1
PRI VSEH~$i\ne j$ I UVELICHITX~$|D|[j]$ NA~1. v PROTIVNOM SLUCHAE SLITX ODIN
OTREZOK NA LENTU~$j$ SO VSEH LENT~$i\ne j$, TAKIH, CHTO~$|D|[i]=0$, I
UMENXSHITX~$|D|[i]$ NA~1 DLYA VSEH OSTALXNYH~$i\ne j$.
\medskip}
\st[nACHALXNAYA USTANOVKA.] uSTANOVITX~$|D|[j]\asg 0$ PRI~$0\le j \le P$.
zATEM ZAPISATX NACHALXNYJ OTREZOK NA LENTU~$j$ PRI~$1 \le j \le P$.
uSTANOVITX~$|A|[0,0]\asg -1$, $l\asg 0$, $q\asg 0$.
\st[vVOD ZAVERSHEN?] (v |TOT MOMENT LENTA~$q$ PUSTA I VSYAKAYA DRUGAYA LENTA
SODERZHIT SAMOE BOLXSHEE ODIN OTREZOK.) eSLI ESHCHE ESTX ISHODNYE DANNYE,
PEREJTI K SHAGU~\stp{3}. oDNAKO ESLI VVOD ISCHERPAN, TO PEREMOTATX VSE
LENTY~$j\ne q$, TAKIE, CHTO $|A|[0, j]$~CHETNO; ZATEM SLITX NA LENTU~$q$,
CHITAYA VSE TOLXKO CHTO PEREMOTANNYE LENTY V PRYAMOM NAPRAVLENII, A
OSTALXNYE LENTY---V OBRATNOM. eTIM ZAVERSHAETSYA SORTIROVKA; REZULXTAT
NAHODITSYA NA LENTE~$q$ V VOZRASTAYUSHCHEM PORYADKE.
\st[nACHATX NOVYJ UROVENX.] uSTANOVITX~$l \asg l+1$, $r \asg q$, $s \asg 0$
I~$q\asg (q+1) \bmod T$. zAPISATX NACHALXNYJ OTREZOK NA LENTU~$(q+j) \bmod T$
PRI~$1 \le j \le T-2$. (tAKIM OBRAZOM, NACHALXNYE OTREZKI ZAPISYVAYUTSYA NA
VSE LENTY, KROME LENT~$q$ I~$r$.) uSTANOVITX~$|A|[l, q]\asg -1$
I~$|A|[l, r] \asg -1$.
\st[mOZHNO LI SLIVATX?] eSLI~$|A|[l-1, q]\ne s$, VERNUTXSYA K SHAGU~\stp{3}.
\st[sLIYANIE.] (v |TOT MOMENT $|A|[l-1, q]=|A|[l, j]=s$ PRI
VSEH~$j\ne q$, $j \ne r$.) sLITX NA LENTU~$r$. (sM.\ VYSHE OPREDELENIE |TOJ
OPERACII.) zATEM USTANOVITX~$s \asg s+1$, $l \asg l-1$,
$|A|[l, r]\asg s$ I~$|A|[l, q] \asg -1$. uSTANOVITX~$r \asg (2q-r)\bmod T$.
(v OBSHCHEM SLUCHAE MY IMEEM~$r=(q-1)\bmod T$, ESLI $s$~CHETNO,
I~$r=(q+1) \bmod T$, ESLI $s$~NECHETNO.)
\st[zAKONCHEN LI UROVENX?] eSLI~$l=0$, PEREJTI K~\stp{2}. v PROTIVNOM
SLUCHAE, ESLI~$|A|[l, j]=s$ DLYA VSEH~$j\ne q$ I~$j\ne r$, TO PEREJTI
K~\stp{4}. v PROTIVNOM SLUCHAE VERNUTXSYA K~\stp{3}.
\algend
chTOBY POKAZATX PRAVILXNOSTX |TOGO ALGORITMA, MY MOZHEM ISPOLXZOVATX
DOKAZATELXSTVO TIPA "REKURSIVNOJ INDUKCII", TAK ZHE KAK MY DELALI DLYA
ALGORITMA~2.3.1T. pREDPOLOZHIM, CHTO MY NACHINAEM S SHAGA~B3 S~$l=l_0$,
$q=q_0$, $s_+=|A|[l_0, (q_0+1)\bmod T]$ I~$s_-=|A|[l_0, (q_0-1)\bmod T]$,
I DOPUSTIM, KROME TOGO, CHTO LIBO~$s_+=0$, LIBO~$s_-=1$, LIBO~$s_+=2$,
LIBO~$s_-=3$, LIBO~$\ldots\,$. mOZHNO PROVERITX PO INDUKCII, CHTO ALGORITM V
KONCE KONCOV PRIDET K SHAGU~B5, NE IZMENIV S NULEVOJ PO~$l\hbox{-YU}$
STROKI~|A| I SO ZNACHENIYAMI
%%375
PEREMENNYH~$l=l_0+1$, $q=q_0\pm 1$, $r=q_0$
I~$s=s_+ \ror s_-$, PRICHEM MY VYBIRAEM ZNAK~$+$,
ESLI~$s_+=0 \ror (s_+=2 \rand s_-\ne 1) \ror (s_+=4 \rand s_-\ne 1, 3)
\ror \ldots$, I MY VYBIRAEM ZNAK~$-$,
ESLI~$(s_-=1 \rand s_+=0) \ror (s_-=3 \rand s_+\ne 0, 2)\ror \ldots\,$.
pRIVEDENNYJ ZDESX NABROSOK DOKAZATELXSTVA NE OCHENX |LEGANTEN, NO I
SAM ALGORITM SFORMULIROVAN V VIDE, KOTORYJ BOLXSHE GODITSYA DLYA REALIZACII,
CHEM DLYA PROVERKI PRAVILXNOSTI.
\picture{rIS.~78 eFFEKTIVNOSTX OSCILLIRUYUSHCHEJ SORTIROVKI, ISPOLXZUYUSHCHEJ
METOD ALGORITMA~B I~UPR.~3.}
nA RIS.~78 POKAZANA |FFEKTIVNOSTX ALGORITMA~B, VYRAZHENNAYA SREDNIM CHISLOM
SLIYANIJ KAZHDOJ ZAPISI V ZAVISIMOSTI OT~$S$---CHISLA NACHALXNYH OTREZKOV,
PRICHEM PREDPOLAGAETSYA, CHTO NACHALXNYE OTREZKI PRIBLIZITELXNO RAVNY PO
DLINE. (sOOTVETSTVUYUSHCHIE GRAFIKI DLYA MNOGOFAZNOJ I KASKADNOJ SORTIROVKI
PRIVEDENY NA RIS.~70 I~74.) pRI PODGOTOVKE RIS.~78 UCHTENO NEBOLXSHOE
USOVERSHENSTVOVANIE, UPOMYANUTOE V UPR.~3.
%%376
\section pRYAMOE CHTENIE. sHEMA OSCILLIRUYUSHCHEJ SORTIROVKI, PO-VIDIMOMU,
TREBUET VOZMOZHNOSTI OBRATNOGO CHTENIYA, POSKOLXKU PRIHODITSYA GDE-TO
NAKAPLIVATX DLINNYE OTREZKI PO MERE TOGO, KAK MY SLIVAEM VNOVX VVEDENNYE
KOROTKIE OTREZKI. tEM NE MENEE m.~a.~gOTC
[Proc. AFIPS Spring Jt. sOTR. Conf.; {\bf 25} (1964), 599--607] NASHEL
SPOSOB VYPOLNITX OSCILLIRUYUSHCHUYU SORTIROVKU, ISPOLXZUYA TOLXKO PRYAMOE CHTENIE
I PROSTUYU PEREMOTKU. eGO METOD V KORNE OTLICHAETSYA OT OSTALXNYH SHEM,
KOTORYE MY VIDELI V |TOJ GLAVE, POSKOLXKU
a)~DANNYE INOGDA ZAPISYVAYUTSYA V NACHALO LENTY, PRICHEM PREDPOLAGAETSYA, CHTO
DANNYE, NAHODYASHCHIESYA V \emph{SEREDINE} |TOJ LENTY, NE RAZRUSHAYUTSYA;
b)~VSE NACHALXNYE STROKI IMEYUT FIKSIROVANNUYU MAKSIMALXNUYU DLINU.
uSLOVIE~(a) NARUSHAET SVOJSTVO "PERVYM VKLYUCHAETSYA---PERVYM ISKLYUCHAETSYA",
KOTOROE, KAK MY PREDPOLOZHILI, YAVLYAETSYA HARAKTERISTIKOJ PRYAMOGO CHTENIYA,
ODNAKO ONO MOZHET BYTX NADEZHNO REALIZOVANO, ESLI MEZHDU OTREZKAMI
OSTAVLYATX DOSTATOCHNOE KOLICHESTVO CHISTOJ LENTY I ESLI V NUZHNYE MOMENTY
PRENEBRECHX "OSHIBKAMI CHETNOSTI". uSLOVIE~(b) OKAZYVAETSYA DO
NEKOTOROJ STEPENI PROTIVORECHASHCHIM |FFEKTIVNOMU ISPOLXZOVANIYU VYBORA S ZAMESHCHENIEM.
oSCILLIRUYUSHCHAYA SORTIROVKA gOTCA S PRYAMYM CHTENIEM IMEET ODNO TEMNOE
PYATNO---|TO ODIN IZ PERVYH ALGORITMOV, KOTORYJ BYL ZAPATENTOVAN KAK ALGORITM,
A NE KAK FIZICHESKOE USTROJSTVO [U.~S.~Patent~3380029 (23~APRELYA 1968)].
eSLI POLOZHENIE NE IZMENITSYA, TO |TO OZNACHAET, CHTO ALGORITM NELXZYA
ISPOLXZOVATX V PROGRAMME BEZ RAZRESHENIYA VLADELXCA PATENTA. mETOD
b|NCHERA (OSCILLIRUYUSHCHAYA SORTIROVKA S OBRATNYM CHTENIEM) BYL ZAPATENTOVAN
IBM NESKOLXKIMI GODAMI POZZHE. [tAKIM OBRAZOM, NASTUPIL KONEC |RY, KOGDA
UDOVOLXSTVIE OT OTKRYTIYA NOVOGO ALGORITMA SCHITALOSX DOSTATOCHNYM
VOZNAGRAZHDENIEM! tAK KAK PROGRAMMIROVANIE NEOTDELIMO OT SOZDANIYA MASHINY,
A PROGRAMMY DLYA evm TEPERX STOYAT DENEG, TO PATENTOVANIE ALGORITMOV
YAVLYAETSYA NEIZBEZHNYM. kONECHNO, DEJSTVIYA NEDALXNOVIDNYH LYUDEJ,
SOHRANYAYUSHCHIH NOVYE ALGORITMY V STROGOM SEKRETE, ZNACHITELXNO HUZHE,
CHEM SHIROKAYA DOSTUPNOSTX ALGORITMOV, KOTORYE YAVLYAYUTSYA SOBSTVENNOSTXYU V
TECHENIE LISHX OGRANICHENNOGO VREMENI.]
cENTRALXNAYA IDEYA V METODE gOTCA SOSTOIT V TAKOM ISPOLXZOVANII LENT,
CHTOBY KAZHDAYA LENTA NACHINALASX S OTREZKA OTNOSITELXNOJ DLINY~1, ZA
KOTORYM SLEDOVAL BY OTREZOK OTNOSITELXNOJ DLINY~$P$, ZATEM~$P^2$ I~T.~D.
nAPRIMER, ESLI~$T=5$, TO SORTIROVKA NACHINAETSYA SLEDUYUSHCHIM OBRAZOM
("."~UKAZYVAET TEKUSHCHEE POLOZHENIE GOLOVKI CHTENIYA-ZAPISI NA KAZHDOJ LENTE):
%%377
\ctable{
#\hfil\bskip&#\hfil\bskip&\hfil$#$\hfil\bskip&\hfil$#$\hfil\bskip
&\hfil$#$\hfil\bskip&\hfil$#$\hfil\bskip&\hfil$#$\hfil\bskip
&\hfil$#$\hfil\bskip&#\hfil\cr
& oPERACIYA & T1 & T2 & T3 & T4 & T5 &
\hbox{sTOIMOSTX} & pRIMECHANIYA \cr
fAZA~1. & rASPREDELENIE& A_1 & .A_1 & .A_1 & .A_1 & A_1.
& 5& [T5 NE PEREMATYVAETSYA]\cr
fAZA~2. & sLIYANIE & A_1. & A_1. & A_1. & A_1. &
A_1A_4. & 4& [pEREMOTKA VSEH LET]\cr
fAZA~3. & rASPREDELENIE& A_1 & .A_1 & .A_1 & A_1. &
.A_1A_4 & 4& [T4 NE PEREMATYVAETSYA]\cr
fAZA~4. & sLIYANIE & A_1. & A_1. & A_1. & A_1A_4.&
A_1.A_4 & 4& [pEREMOTKA VSEH LENT]\cr
fV|A~5. & rASPREDELENIE& A_1 & .A_1 & A_1. & .A_1A_4&
.A_1A_4 & 4& [T3 NE PEREMATYVAETSYA]\cr
fAZA~6. & sLIYANIE & A_1. & A_1. & A_1A_4.& A_1.A_4&
A_1.A_4 & 4& [pEREMOTKA VSEH LENT]\cr
fAZA~7. & rASPREDELENIE& A_1 & A_1. & .A_1A_4& .A_1A_4&
.A_1A_4 & 4& [T2 NE PEREMATYVAETSYA]\cr
fAZA~8. & sLIYANIE & A_1. & A_1A_4. & A_1.A_4& A_1.A_4&
A_1.A_4 & 4& [pEREMOTKA VSEH LENT]\cr
FAZA~9. & rASPREDELENIE& A_1. & .A_1A_4 & .A_1A_4& .A_1A_4&
.A_1A_4 & 4& [T1 NE PEREMATYVAETSYA]\cr
fAZA~10.& sLIYANIE & A_1A_4. & A_1.A_4 & A_1.A_4& A_1.A_4&
A_1.A_4 & 4& [nET PEREMOTKI]\cr
fAZA~11.& sLIYANIE & A_1A_4A_{16}. & A_1A_4. & A_1A_4.& A_1A_4.&
A_1A_4. & 16& [pEREMOTKA VSEH LENT]\cr
}
i TAK DALEE. vO VREMYA FAZY~1 LENTA~T1 PEREMATYVAETSYA I ODNOVREMENNO
NA~T2 ZAPISYVAYUTSYA ISHODNYE DANNYE, ZATEM PEREMATYVAETSYA~T2 I
ODNOVREMENNO NA~T3 ZAPISYVAYUTSYA ISHODNYE DANNYE I~T.~D. v KONCE KONCOV,
KOGDA ISHODNYE DANNYE ISCHERPANY, NACHINAYUT POYAVLYATXSYA FIKTIVNYE OTREZKI, I
INOGDA NEOBHODIMO VOOBRAZITX, CHTO ONI ZAPISANY YAVNO NA LENTE POLNOJ
DLINY. nAPRIMER, ESLI~$S=18$, TO OTREZKI~$A_1$ NA~T4 I~T5 BUDUT
FIKTIVNYMI VO VREMYA FAZY~9; NAM PRIDETSYA PRODVINUTXSYA VPERED PO~T4 I~T5
PRI SLIYANII S~T2 I~T3 NA~T1 VO VREMYA FAZY~10, TAK KAK NAM NADO DOBRATXSYA
DO OTREZKOV~$A_4$ NA~T4 I~T5 DLYA PODGOTOVKI K FAZE~11. s DRUGOJ STORONY,
FIKTIVNYJ OTREZOK~$A_1$ NA~T1 NE OBYAZATELXNO DOLZHEN SUSHCHESTVOVATX YAVNO.
tAKIM OBRAZOM, "KONEC IGRY" NESKOLXKO ZAMYSLOVAT. eSHCHE S ODNIM
PRIMEROM PRIMENENIYA |TOGO METODA MY VSTRETIMSYA V SLEDUYUSHCHEM PUNKTE.
\excercises
\ex[22] v TEKSTE IMEETSYA ILLYUSTRACIYA OSCILLIRUYUSHCHEJ SORTIROVKI sOBELYA V EE
PERVOZDANNOM VIDE DLYA~$T=5$ I~$S=16$. dAJTE TOCHNOE OPREDELENIE ALGORITMA,
V KOTOROM |TA PROCEDURA OBOBSHCHAETSYA I SORTIRUYUTSYA $S=P^L$~NACHALXNYH
OTREZKOV NA $T=P+1\ge 3$~LENTAH. pOSTARAJTESX NAJTI ALGORITM,
KOTORYJ MOZHET BYTX OCHENX PROSTO OPISAN.
\ex[24] eSLI V IZNACHALXNOM METODE sOBELYA $S=6$, TO MY MOGLI BY ZAYAVITX,
CHTO~$S=16$ I CHTO IMEETSYA 10~FIKTIVNYH OTREZKOV. tOGDA FAZA~3 V PRIMERE V
TEKSTE POMESTILA BY FIKTIVNYE OTREZKI~$A_0$ NA~T4 I~T5; FAZA~4 SLILA
BY OTREZKI~$A_1$ NA~T2 I~T3 V~$D_2$ NA~T1; FAZY~5--8 NE DELALI BY NICHEGO;
FAZA~9 PORODILA BY~$A_6$ NA~T4. lUCHSHE BY PEREMOTATX~T2 I~T3 SRAZU POSLE
FAZY~3 I ZATEM NEMEDLENNO POLUCHATX~$A_6$ NA~T4 S POMOSHCHXYU TREHPUTEVOGO SLIYANIYA.
pOKAZHITE, KAK, OSNOVYVAYASX NA |TOJ IDEE, ULUCHSHITX OKONCHANIE ALGORITMA IZ
UPR.~1, ESLI~$S$ NE YAVLYAETSYA TOCHNOJ STEPENXYU~$P$.
\rex[24] sOSTAVXTE TABLICU, POKAZYVAYUSHCHUYU POVEDENIE ALGORITMA~B, ESLI~$T=3$,
PREDPOLAGAYA, CHTO IMEETSYA 9~NACHALXNYH OTREZKOV. pOKAZHITE, CHTO
|TA PROCEDURA OCHEVIDNO NE|FFEKTIVNA V ODNOM MESTE, I PREDLOZHITE
IZMENENIYA V ALGORITME~B, KOTORYE ISPRAVLYAYUT POLOZHENIE.
\ex[21] nA SHAGE~B3 IMEETSYA USTANOVKA KAK~$|A|[l, q]$, TAK I~$|A|[l, r]$
V~$-1$. pOKAZHITE, CHTO ODNA IZ |TIH OPERACIJ VSEGDA LISHNYAYA, TAK KAK
SOOTVETSTVUYUSHCHIJ |LEMENT MASSIVA~|A| NIKOGDA NE RASSMATRIVAETSYA.
\ex[m25] pUSTX~$S$---CHISLO NACHALXNYH OTREZKOV V IMEYUSHCHIHSYA ISHODNYH DANNYH
DLYA ALGORITMA~B. pRI KAKIH ZNACHENIYAH~$S$ NE TREBUETSYA \emph{NI ODNOJ
PEREMOTKI} NA SHAGE~B2?
%%378
\bye\input style
\chapno=5\subchno=4\subsubchno=3\chapnotrue
kASKADNOE SLIYANIE, PODOBNO MNOGOFAZNOMU, NACHINAETSYA S
"TOCHNOGO RASPREDELENIYA" OTREZKOV PO LENTAM, HOTYA PRAVILA TOCHNOGO
RASPREDELENIYA OTLICHNY OT PRAVIL P.~5.4.2. kAZHDAYA STROKA
TABLICY PREDSTAVLYAET POLNYJ PROHOD PO \emph{VSEM} DANNYM. pROHOD~2,
NAPRIMER, POLUCHAETSYA POSREDSTVOM VYPOLNENIYA PYATIPUTEVOGO SLIYANIYA S~T1,
T2, T3, T4, T5 NA~T6, POKA~T5 NE STANET PUSTOJ (PRI |TOM NA~T6 POMESHCHAYUTSYA
15~OTREZKOV OTNOSITELXNOJ DLINY~5), ZATEM CHETYREHPUTEVOGO SLIYANIYA S~T1, T2,
T3, T4 NA~T5, ZATEM TREHPUTEVOGO SLIYANIYA NA~T4, DVUHPUTEVOGO SLIYANIYA
NA~T3 I, NAKONEC, ODNOPUTEVOGO SLIYANIYA (OPERACII KOPIROVANIYA) S~T1
NA~T2. pROHOD~3 POLUCHAETSYA TAKIM ZHE OBRAZOM PUTEM VYPOLNENIYA SNACHALA
PYATIPUTEVOGO SLIYANIYA, POKA ODNA LENTA NE STANET PUSTOJ, ZATEM
CHETYREHPUTEVOGO I~T.~D. (pOHOZHE, CHTO |TOMU PUNKTU KNIGI SLEDOVALO BY
PRISVOITX NOMER~5.4.3.2.1, A NE~5.4.3!)
yaSNO, CHTO OPERACII KOPIROVANIYA IZLISHNI, I IH MOZHNO BYLO BY OPUSTITX.
fAKTICHESKI, ODNAKO, V SLUCHAE SHESTI LENT |TO KOPIROVANIE ZANIMAET TOLXKO
NEBOLXSHOJ PROCENT VSEGO VREMENI. eLEMENTY, KOTORYE POLUCHAYUTSYA PROSTYM
KOPIROVANIEM, OTMECHENY V PRIVEDENNOJ TABLICE ZVEZDOCHKOJ. tOLXKO~25 IZ~950
OBRABATYVAEMYH OTREZKOV PRINADLEZHAT |TOMU KLASSU. bOLXSHAYA CHASTX
VREMENI OTVODITSYA PYATIPUTEVOMU I CHETYREHPUTEVOMU SLIYANIYAM.
nA PERVYJ VZGLYAD MOZHET POKAZATXSYA, CHTO KASKADNAYA SHEMA---DOVOLXNO PLOHOJ
VARIANT V SRAVNENII S MNOGOFAZNOJ, TAK KAK STANDARTNAYA MNOGOFAZNAYA SHEMA
ISPOLXZUET VSE VREMYA $(T-1)\hbox{-PUTEVOE}$ SLIYANIE, V TO VREMYA KAK
KASKADNAYA ISPOLXZUET $(T-1)\hbox{-PUTEVOE}$, $(T-2)\hbox{-PUTEVOE}$,
$(T-3)\hbox{-PUTEVOE}$ I~T.~D., NO V DEJSTVITELXNOSTI ONA ASIMPTOTICHESKI
\emph{LUCHSHE,} CHEM MNOGOFAZNAYA, DLYA SHESTI I BOLEE LENT! kAK MY VIDELI V
P.~5.4.2, VYSOKIJ PORYADOK SLIYANIYA NE YAVLYAETSYA GARANTIEJ |FFEKTIVNOSTI. v
TABL.~1 POKAZANY HARAKTERISTIKI VYPOLNENIYA KASKADNOGO SLIYANIYA PO
ANALOGII S PODOBNOJ TABLICEJ P.~5.4.2.
nETRUDNO VYVESTI "TOCHNYE RASPREDELENIYA" DLYA KASKADNOGO SLIYANIYA. dLYA SHESTI
LENT IMEEM
$$
\matrix{
\hbox{uROVENX} & T1 & T2 & T3 & T4 & T5 \cr
0 & 1 & 0 & 0 & 0 & 0 \cr
1 & 1 & 1 & 1 & 1 & 1 \cr
2 & 5 & 4 & 3 & 2 & 1 \cr
3 & 15 & 14 & 12 & 9 & 6 \cr
4 & 55 & 50 & 41 & 29 & 15 \cr
5 & 190 & 175 & 146 & 105 & 55 \cr
\multispan{6}\dotfill\cr
n & a_n & b_n & c_n & d_n & e_n \cr
n+1 & a_n+b_n+c_n+d_n+e_n & a_n+b_n+c_n+d_n & a_n+b_n+c_n & a_n+b_n & a_n \cr
}
\eqno(1)
$$
%%344
\htable{tABLICA 1}%
{hARAKTER POVEDENIYA KASKADNOGO SLIYANIYA}%
{\strut\hfill # && \bskip\hfill$#$\hfill\bskip\cr
lENTY & \hbox{pROHODY} & \hbox{pROHODY} & \hbox{oTNOSHENIE}\cr
& \hbox{(S KOPIROVANIEM)} & \hbox{(BEZ KOPIROVANIYA)} &\hbox{ROSTA}\cr
\noalign{\hrule}
3 & 2.078\ln S+0.672 & 1.504\ln S+0.992 & 1.6180340\cr
4 & 1.235\ln S+0.754 & 1.102\ln S+0.820 & 2.2469796\cr
5 & 0.946\ln S+0.796 & 0.897\ln S+0.800 & 2.8793852\cr
6 & 0.796\ln S+0.821 & 0.773\ln S+0.808 & 3.5133371\cr
7 & 0.703\ln S+0.839 & 0.691\ln S+0.822 & 4.1481149\cr
8 & 0.639\ln S+0.852 & 0.632\ln S+0.834 & 4.7833861\cr
9 & 0.592\ln S+0.861 & 0.587\ln S+0.845 & 5.4189757\cr
10 & 0.555\ln S+0.869 & 0.552\ln S+0.854 & 6.0547828\cr
20 & 0.397\ln S+0.905 & 0.397\ln S+0.901 & 12.4174426\cr
\noalign{\hrule}
}
oTMETIM INTERESNOE SVOJSTVO |TIH CHISEL---IH OTNOSITELXNYE VELICHINY YAVLYAYUTSYA
TAKZHE I DLINAMI DIAGONALEJ PRAVILXNOGO $(2T-1)\hbox{-UGOLXNIKA}$. nAPRIMER,
PYATX DIAGONALEJ ODINNADCATIUGOLXNIKA NA RIS.~73 IMEYUT OTNOSITELXNYE DLINY,
OCHENX BLIZKIE K~190, 175, 146, 105 I~55! mY DOKAZHEM |TOT ZAMECHATELXNYJ FAKT
\picture{rIS.~73. gEOMETRICHESKAYA INTERPRETACIYA KASKADNYH CHISEL.}
POZDNEE V |TOM PUNKTE, A TAKZHE UVIDIM, CHTO OTNOSITELXNYE VREMENA,
ZATRACHIVAEMYE NA $(T-1)\hbox{-PUTEVOE}$ SLIYANIE, $(T-2)\hbox{-PUTEVOE}$
SLIYANIE,~\dots, ODNOPUTEVOE SLIYANIE, PRIBLIZITELXNO PROPORCIONALXNY
\emph{KVADRATAM} DLIN |TIH DIAGONALEJ.
\section *nACHALXNOE RASPREDELENIE OTREZKOV. eSLI CHISLO NACHALXNYH
OTREZKOV V DEJSTVITELXNOSTI NE ESTX CHISLO fIBONACHCHI, MY MOZHEM,
KAK OBYCHNO, VSTAVITX FIKTIVNYE OTREZKI. pOVERHNOSTNYJ ANALIZ SITUACII
POKAZYVAET, CHTO METOD PRIPISYVANIYA FIKTIVNYH OTREZKOV NESUSHCHESTVEN, TAK
KAK KASKADNOE SLIYANIE VSEGDA OSUSHCHESTVLYAET
%%345
POLNYE PROHODY; ESLI IMEETSYA 190~NACHALXNYH OTREZKOV, TO KAZHDAYA ZAPISX
OBRABATYVAETSYA PYATX RAZ, KAK V PRIVEDENNOM VYSHE PRIMERE, NO ESLI IMEETSYA
191~OTREZOK, TO, OCHEVIDNO, SLEDUET UVELICHITX UROVENX, I TEPERX KAZHDAYA
ZAPISX BUDET OBRABATYVATXSYA SHESTX RAZ. k SCHASTXYU, V DEJSTVITELXNOSTI MOZHNO
IZBEZHATX TAKOGO REZKOGO SKACHKA. d|VID~e.~fERGYUSON NASHEL SPOSOB TAK
RASPREDELITX NACHALXNYE OTREZKI, CHTO MNOGIE OPERACII VO VREMYA PERVOJ
\picture{
rIS.~74. eFFEKTIVNOSTX KASKADNOGO SLIYANIYA S RASPREDELENIEM
PO ALGORITMU~D.
}
FAZY SLIYANIYA SVODYATSYA K KOPIROVANIYU SODERZHIMOGO LENTY. eSLI OBOJTI TAKIE
KOPIROVANIYA (PROSTO IZMENIV "LOGICHESKIE" NOMERA LENTOCHNYH USTROJSTV PO
OTNOSHENIYU K "FIZICHESKIM" NOMERAM, KAK V ALGORITME~5.4.2D), TO POLUCHIM
OTNOSITELXNO PLAVNYJ PEREHOD S UROVNYA NA UROVENX, KAK IZOBRAZHENO NA RIS.~74.
pREDPOLOZHIM, CHTO $(a, b, c, d, e)$, GDE~$a\ge b \ge c \ge d \ge e$---TOCHNOE
RASPREDELENIE. pEREOPREDELIV SOOTVETSTVIE MEZHDU LOGICHESKIMI
I FIZICHESKIMI LENTOCHNYMI USTROJSTVAMI, MY MOZHEM PREDSTAVITX, CHTO REALXNOE
RASPREDELENIE---|TO~$(e, d, c, b, a)$,
%%346
T.~E.~$a$~OTREZKOV NA~T5, $b$~NA~t4 I~T.~D. sLEDUYUSHCHEE TOCHNOE
RASPREDELENIE---|TO $(a+b+c+d+e, a+b+c+d, a+b+c, a+b, a)$;
I ESLI VVOD ISCHERPYVAETSYA PREZHDE, CHEM MY DOSTIGAEM |TOGO SLEDUYUSHCHEGO
UROVNYA, TO BUDEM SCHITATX, CHTO LENTY SODERZHAT
SOOTVETSTVENNO~$(D_1, D_2, D_3, D_4, D_5)$ FIKTIVNYH OTREZKOV, GDE
$$
\displaynarrow{
D_1 \le a+b+c+d,\quad D_1 \le a+b+c,\quad D_3\le a+b,\cr
D_4 \le a,\quad D_5=0;\qquad D_1\ge D_2 \ge D_3 \ge D_4 \ge D_5.\cr
}
\eqno(2)
$$
mY VOLXNY PREDSTAVLYATX SEBE, CHTO |TI FIKTIVNYE OTREZKI POYAVLYAYUTSYA NA
LENTAH V LYUBOM UDOBNOM MESTE. pREDPOLAGAETSYA, CHTO PERVYJ PROHOD SLIYANIYA
DAST $a$~OTREZKOV POSREDSTVOM PYATIPUTEVOGO SLIYANIYA, ZATEM $b$~OTREZKOV
POSREDSTVOM CHETYREHPUTEVOGO I~T.~D. nASHA CELX SOSTOIT V RASPOLOZHENII
FIKTIVNYH OTREZKOV TAKIM OBRAZOM, CHTOBY ZAMENITX SLIYANIE KOPIROVANIEM.
uDOBNO VYPOLNYATX PERVYJ PROHOD SLIYANIYA SLEDUYUSHCHIM OBRAZOM:
1.~eSLI~$D_4=a$, TO VYCHESTX~$a$ IZ VSEH~$D_1$, $D_2$, $D_3$, $D_4$ I
ZAYAVITX, CHTO~T5---REZULXTAT SLIYANIYA. eSLI~$D_4<a$, TO SLITX $a$~OTREZKOV S
LENT~T1 PO~T5, ISPOLXZUYA MINIMALXNO VOZMOZHNOE CHISLO FIKTIVNYH OTREZKOV
NA LENTAH~T1--T5 TAK, CHTOBY NOVYE ZNACHENIYA~$D_1$, $D_2$, $D_3$, $D_4$
UDOVLETVORYALI SOOTNOSHENIYAM
$$
\displaynarrow{
D_1\le b+c+d,\quad D_2\le b+c,\quad D_3\le b,\cr
D_4=0;\qquad D_1\ge D_2\ge D_3\ge D_4.\cr
}
\eqno(3)
$$
tAKIM OBRAZOM, ESLI~$D_2$ BYLO PERVONACHALXNO~$\le b+c$, TO MY
NE ISPOLXZUEM NI ODNOGO FIKTIVNOGO OTREZKA S |TOJ LENTY NA DANNOM SHAGE; V
TO ZHE VREMYA, ESLI~$b+c<D_2\le a+b+c$, MY ISPOLXZUEM ROVNO~$D_2-b-c$
FIKTIVNYH OTREZKOV.
2.~(eTOT SHAG ANALOGICHEN SHAGU~1, NO S NEKOTORYM "SDVIGOM".) eSLI~$D_3=b$,
TO VYCHESTX~$b$ IZ VSEH~$D_1$, $D_2$, $D_3$ I ZAYAVITX, CHTO~T4---REZULXTAT
SLIYANIYA. eSLI~$D_3<b$, TO SLITX $b$~OTREZKOV S LENT~T1--T4, UMENXSHAYA, ESLI
NEOBHODIMO, CHISLO FIKTIVNYH OTREZKOV, CHTOBY DOSTICHX
$$
D_1\le b+c,\quad D_2\le b,\quad D_3=0;\qquad D_1\ge D_2\ge D_3.
$$
3.~i TAK DALEE.
mETOD fERGYUSONA RASPREDELENIYA OTREZKOV PO LENTAM MOZHNO PROILLYUSTRIROVATX,
RASSMOTREV PROCESS PEREHODA S UROVNYA~3 NA UROVENX~4 V~(1). dOPUSTIM, CHTO
"LOGICHESKIE" LENTY (T1,~\dots, T5) SODERZHALI SOOTVETSTVENNO
$(5, 9, 12, 14, 15)$~OTREZKOV I CHTO MY HOTIM DOVESTI |TO V KONECHNOM ITOGE
DO~$(55, 50, 41, 29, 15)$. eTA PROCEDURA MOZHET BYTX KRATKO ZAPISANA TAK:
%%347
\ctable{
$#$\hfill&&\hfill\bskip$#$\bskip\hfill\cr
& \hbox{dOBAVITX} &\hbox{dOBAVITX} &\hbox{dOBAVITX} &\hbox{dOBAVITX} &\hbox{dOBAVITX} &\hbox{s|KONOMLENNAYA}\cr
\hbox{shAG} &\hbox{K T1} &\hbox{K T2} &\hbox{K T3} &\hbox{K T4} &\hbox{K T5} &\hbox{VELICHINA}\cr
(1, 1)& 9 & 0 & 0 & 0 & 0 & 15+14+12+5\cr
(2, 2)& 3 & 12 & 0 & 0 & 0 & 15+14+9+5\cr
(2, 1)& 9 & 0 & 0 & 0 & 0 & 15+14+5\cr
(3, 3)& 2 & 2 & 14 & 0 & 0 & 15+12+5\cr
(3, 2)& 3 & 12 & 0 & 0 & 0 & 15+9+5\cr
(3, 1)& 9 & 0 & 0 & 0 & 0 & 15+5\cr
(4, 4)& 1 & 1 & 1 & 15 & 0 & 14+5\cr
(4, 3)& 2 & 2 & 14 & 0 & 0 & 12+5\cr
(4, 2)& 3 & 12 & 0 & 0 & 0 & 9+5\cr
(4, 1)& 9 & 0 & 0 & 0 & 0 & 5\cr
}
sNACHALA POMESHCHAEM DEVYATX OTREZKOV NA~T1, ZATEM $(3, 12)$---NA~T1 I~T2 I~T.~D.
eSLI VVOD ISCHERPAETSYA, SKAZHEM, VO VREMYA SHAGA~$(3, 2)$, TO "S|KONOMLENNAYA
VELICHINA" SOSTAVLYAET~$15+9+5$. eTO OZNACHAET, CHTO MY IZBEGAEM PYATIPUTEVOGO
SLIYANIYA 15~OTREZKOV, DVUHPUTEVOGO SLIYANIYA 9~OTREZKOV I ODNOPUTEVOGO
SLIYANIYA 5~OTREZKOV POSREDSTVOM PRISVOENIYA FIKTIVNYH OTREZKOV.
dRUGIMI SLOVAMI, $15+9+5$ OTREZKOV, PRISUTSTVUYUSHCHIH NA UROVNE~3,
NE OBRABATYVAYUTSYA V TECHENIE PERVOJ FAZY SLIYANIYA.
sLEDUYUSHCHIJ ALGORITM DETALXNO OPISYVAET |TOT PROCESS.
\alg C.(sORTIROVKA KASKADNYM SLIYANIEM SO SPECIALXNYM RASPREDELENIEM.) eTOT
ALGORITM RASPREDELYAET NACHALXNYE OTREZKI PO LENTAM OTREZOK ZA OTREZKOM,
POKA ZAPAS NACHALXNYH OTREZKOV NE ISCHERPAETSYA. zATEM ON OPREDELYAET, KAK
SLEDUET SLIVATX LENTY, PREDPOLAGAYA, CHTO IMEETSYA $T\ge 3$~LENTOPROTYAZHNYH
USTROJSTV, PRI |TOM ISPOLXZUETSYA SAMOE BOLXSHEE
$(T-1)\hbox{-PUTEVOE}$~SLIYANIE I
NENUZHNYE ODNOPUTEVYE SLIYANIYA USTRANYAYUTSYA. lENTA~$T$ MOZHET
BYTX ISPOLXZOVANA DLYA HRANENIYA VVODA, TAK KAK NA NEE NE POPADAET NI ODIN
NACHALXNYJ OTREZOK. aLGORITM RABOTAET SO SLEDUYUSHCHIMI MASSIVAMI:
{\let\mypar=\par\ctable{
$#$,\bskip\hfill&$#$:\bskip\hfill&
\vtop{\parindent=0pt \hsize=13cm #\mypar}\cr
|A|[j] & 1 \le j \le T &
pOSLEDNEE TOCHNOE KASKADNOE RASPREDELENIE, KOTOROE BYLO DOSTIGNUTO. \cr
|AA|[j] & 1 \le j \le T &
tOCHNOE KASKADNOE RASPREDELENIE, K KOTOROMU MY STREMIMSYA. \cr
|D|[j] & 1 \le j \le T &
chISLO FIKTIVNYH OTREZKOV, PREDPOLAGAEMYH PRISUTSTVUYUSHCHIMI NA LOGICHESKOM
LENTOPROTYAZHNOM USTROJSTVE S NOMEROM~$j$. \cr
|M|[j] & 1 \le j \le T &
mAKSIMALXNOE CHISLO FIKTIVNYH OTREZKOV, KOTOROE ZHELATELXNO IMETX NA
LOGICHESKOM LENTOPROTYAZHNOM USTROJSTVE S NOMEROM~$j$. \cr
|TAPE|[j] & 1 \le j \le T &
nOMER FIZICHESKOGO LENTOPROTYAZHNOGO USTROJSTVA, SOOTVETSTVUYUSHCHEGO
LOGICHESKOMU LENTOPROTYAZHNOMU USTROJSTVU S NOMEROM~$j$.\cr
}}
%%348
\st[nACHALXNAYA USTANOVKA.] uSTANOVITX $|A|[k]\asg |AA|[k]\asg |D|[k]\asg 0$
PRI~$2\le k \le T$; USTANOVITX $|A|[1]\asg 0$, $|AA|[1]\asg 1$,
$|D|[1]\asg 1$; USTANOVITX~$|TAPE|[k]\asg k$ PRI~$1\le k \le T$. nAKONEC,
USTANOVITX~$i\asg T-2$, $j\asg 1$, $k\asg 1$, $l\asg 0$, $m\asg 1$ I
PEREJTI K SHAGU~\stp{5} (|TI MANEVRY YAVLYAYUTSYA ODNIM IZ SPOSOBOV NACHATX
RABOTU NEPOSREDSTVENNO VO VNUTRENNEM CIKLE S SOOTVETSTVUYUSHCHEJ USTANOVKOJ
UPRAVLYAYUSHCHIH PEREMENNYH).
\st[nACHATX NOVYJ UROVENX.] (mY TOLXKO CHTO POLUCHILI TOCHNOE RASPREDELENIE.
nO TAK KAK ESHCHE IMEYUTSYA ISHODNYE DANNYE, TO NEOBHODIMO PODGOTOVITXSYA K
SLEDUYUSHCHEMU UROVNYU.) uVELICHITX~$l$ NA~1. uSTANOVITX~$|A|[k]\asg |AA|[k]$
PRI~$1\le k \le T$, ZATEM USTANOVITX~$|AA|[T-k]\asg |AA|[T-k+1]+|A|[k]$
PRI~$k=1$, 2,~\dots, $T-1$ (V TAKOM PORYADKE). uSTANOVITX $(|TAPE|[1],
|TAPE|[2],~\ldots, |TAPE|[T-1])\asg (|TAPE|[T-1],~\ldots, |TAPE|[2],
|TAPE|[1])$ I USTANOVITX~$|D|[k]\asg |AA|[k+1]$ PRI~$1\le k < T$.
nAKONEC, USTANOVITX~$i\asg 1$.
\st[nACHATX PODUROVENX~$i$.] uSTANOVITX~$j\asg i$. (pEREMENNYE~$i$
I~$j$ PREDSTAVLYAYUT "SHAG~$(i,j)$" V TABLICE, ILLYUSTRIRUYUSHCHEJ METOD fERGYUSONA.)
\st[nACHATX SHAG~$(i, j)$.] uSTANOVITX~$k\asg j$ I~$m\asg
|A|[T-j-1]$. eSLI~$m=0$ I~$i=j$, TO USTANOVITX~$i\asg T-2$ I
VERNUTXSYA K~\stp{3}; ESLI~$m=0$ I~$i\ne j$, VERNUTXSYA K~\stp{2}.
(pEREMENNAYA~$m$ PREDSTAVLYAET SOBOJ CHISLO OTREZKOV, KOTOROE DOLZHNO
BYTX ZAPISANO NA LENTU~$|TAPE|[k]$; $m$~BYVAET RAVNO~0, TOLXKO ESLI~$l=1$.)
\st[vVESTI NA LENTU~$|TAPE|[k]$.] zAPISATX ODIN OTREZOK NA
LENTU NOMER~$|TAPE|[k]$ I UMENXSHITX~$|D|[k]$ NA~1. zATEM, ESLI
VVOD ISCHERPAN, PEREMOTATX VSE LENTY I PEREJTI K SHAGU~\stp{7}.
\st[pRODVIZHENIE.] uMENXSHITX~$m$ NA~1. eSLI~$m>0$, VERNUTXSYA K SHAGU~\stp{5}.
v PROTIVNOM SLUCHAE UMENXSHITX~$k$ NA~1; ESLI~$k>0$, USTANOVITX~$m\asg
|A|[T-j-1]-|A|[T-j]$ I VERNUTXSYA K~\stp{5}, ESLI~$m>0$. v PROTIVNOM SLUCHAE
UMENXSHITX~$j$ NA~1;
ESLI~$j>0$, PEREJTI K SHAGU~\stp{4}. v PROTIVNOM SLUCHAE UVELICHITX~$i$
NA~1; ESLI~$i<T<1$, VERNUTXSYA K SHAGU~\stp{3}. v PROTIVNOM SLUCHAE PEREJTI
K~\stp{2}.
\st[pODGOTOVKA K SLIYANIYU.] (k |TOMU MOMENTU NACHALXNOE RASPREDELENIE
ZAVERSHENO, I TABLICY~|A|, |AA|, |D| I~|TAPE| OPISYVAYUT SOSTOYANIE VSEH
LENT V DANNYJ MOMENT.) uSTANOVITX~$|M|[k]\asg|AA|[k+1]$ PRI~$1\le k < T$ I
USTANOVITX~$|FIRST|\asg 1$. (pEREMENNAYA~|FIRST| PRINIMAET NENULEVOE
ZNACHENIE TOLXKO VO VREMYA PERVOGO PROHODA SLIYANIYA.)
\st[kASKAD.] eSLI~$l=0$, OSTANOVITXSYA; SORTIROVKA ZAVERSHENA, VYVOD
NAHODITSYA NA~$|TAPE|[1]$. v PROTIVNOM SLUCHAE PRI~$p=T-1$, $T-2$,~\dots, 1
(V TAKOM PORYADKE) VYPOLNYATX $p\hbox{-PUTEVOE}$ SLIYANIE S
LENT~$|TAPE|[1]$,~\dots, $|TAPE|[p]$ NA~$|TAPE|[p+1]$ SLEDUYUSHCHIM OBRAZOM:
%% 349
eSLI~$p=1$, TO MODELIROVATX ODNOPUTEVOE SLIYANIE
OBYCHNOJ PEREMOTKOJ~$|TAPE|[2]$ I ZAMENOJ~$|TAPE|[1]\xchg |TAPE|[2]$. v
PROTIVNOM SLUCHAE, ESLI~$|FIRST|=1$ I~$|D|[p-1]=|M|[p-1]$, TO MODELIROVATX
$p\hbox{-PUTEVOE}$ SLIYANIE, PROSTO POMENYAV $|TAPE|[p]\xchg |TAPE|[p+1]$,
PEREMOTAV~$|TAPE|[p]$ I VYCHTYA~$M[p-1]$ IZ KAZHDOGO~$|D|[1]$,~\dots,
$|D|[p-1]$, $|M|[1]$,~\dots, $|M|[p-1]$. v PROTIVNOM SLUCHAE
VYCHESTX~$|M|[p-1]$ IZ VSEH~$|M|[1]$,~\dots, $|M|[p-1]$. zATEM SLITX PO
ODNOMU OTREZKU S KAZHDOJ~$|TAPE|[j]$, TAKOJ, CHTO~$1\le j \le p$
I~$|D|[j]\le |M|[j]$; VYCHESTX EDINICU IZ KAZHDOGO~$|D|[j]$, TAKOGO,
CHTO~$1\le j \le p$ I~$|D|[j]>|M|[j]$, I POMESTITX VYVODNOJ OTREZOK
NA~$|TAPE|[p+1]$. pRODOLZHATX RABOTU, POKA $|TAPE|[p]$ NE STANET PUSTOJ.
zATEM PEREMOTATX~$|TAPE|[p]$ I~$|TAPE|[p+1]$.
\st[oPUSTITXSYA NA ODIN UROVENX.] uMENXSHITX~$l$ NA~1,
USTANOVITX~$|FIRST|\asg 0$, USTANOVITX
$(|TAPE|[1],~\ldots, |TAPE|[T])\asg (|TAPE|[T],~\ldots, |TAPE|[1])$. (k
|TOMU MOMENTU VSE~|D| I~|M|---NULI I TAKOVYMI OSTANUTSYA.) vERNUTXSYA K~\stp{8}.
\algend
shAGI~C1--C6 |TOGO ALGORITMA VYPOLNYAYUT RASPREDELENIE, SHAGI~C7--C9 VYPOLNYAYUT
SLIYANIE; |TI DVE CHASTI SOVERSHENNO NEZAVISIMY ODNA OT DRUGOJ, I MOZHNO BYLO
BY HRANITX~$|M|[k]$ I~$|AA|[k+1]$ V ODNIH I TEH ZHE YACHEJKAH PAMYATI.
\picture{rIS.~75. kASKADNOE SLIYANIE SO SPECIALXNYM RASPREDELENIEM.}
\section *aNALIZ KASKADNOGO SLIYANIYA. kASKADNOE SLIYANIE PODDAETSYA ANALIZU
S BOLXSHIM TRUDOM, CHEM MNOGOFAZNOE. nO |TOT ANALIZ OSOBENNO INTERESEN,
POSKOLXKU SODERZHIT MNOGO ZAMECHATELXNYH FORMUL. nASTOYATELXNO REKOMENDUEM
CHITATELYAM, INTERESUYUSHCHIMSYA DISKRETNOJ MATEMATIKOJ, SAMOSTOYATELXNO
PROANALIZIROVATX KASKADNOE RASPREDELENIE, PREZHDE CHEM CHITATX DALXSHE, VEDX CHISLA
%%350
IMEYUT TAK MNOGO NEOBYCHNYH SVOJSTV, OTKRYVATX KOTORYE---ODNO UDOVOLXSTVIE! mY
OBSUDIM ZDESX LISHX ODIN IZ MNOGIH PODHODOV, OBRASHCHAYA OSOBOE VNIMANIE NA
METODY POLUCHENIYA REZULXTATOV.
dLYA UDOBSTVA RASSMOTRIM SLUCHAJ SHESTI LENT. pRI |TOM BUDEM STARATXSYA
POLUCHITX FORMULY, KOTORYE OBOBSHCHAYUTSYA NA SLUCHAJ LYUBOGO~$T$. sOOTNOSHENIYA~(1)
PRIVODYAT K PERVOJ OSNOVNOJ SISTEME:
$$
\eqalignter{
a_n &= a_n &=\perm{0}{0}a_n,\cr
b_n &= a_n-e_{n-1}=a_n-a_{n-2} &=\perm{1}{0}a_n-\perm{2}{2}a_{n-2},\cr
c_n &= b_n-d_{n-1}=b_n-a_{n-2}-b_{n-2} &=\perm{2}{0}a_n-\perm{3}{2}a_{n-2}+\perm{4}{4}a_{n-4},\cr
d_n &= c_n-c_{n-1}=c_n-a_{n-2}-b_{n-2}-c_{n-2} &=\perm{3}{0}a_n-\perm{4}{2}a_{n-2}+\perm{5}{4}a_{n-4}-\perm{6}{6}a_{n-6},\cr
e_n &= d_n-b_{n-1}=d_n-a_{n-2}-b_{n-2}-c_{n-2}-d_{n-2} &=\perm{4}{0}a_n-\perm{5}{2}a_{n-2}+\perm{6}{4}a_{n-4}-\perm{7}{6}a_{n-6}+\perm{8}{8}a_{n-8}.\cr
}
\eqno(4)
$$
oBOZNACHIM~$A(z)=\sum_{n\ge0} a_n z^n$,~\dots, $E(z)=\sum_{n\ge0}e_n z^n$ I
OPREDELIM MNOGOCHLENY
$$
\eqalignno{
q_m(z)&=\perm{m}{0}-\perm{m+1}{2}z^2+\perm{m+2}{4}z^4-\cdots=\cr
&=\sum_{k\ge 0}\perm{m+k}{2k}(-1)^k z^{2k}
= \sum_{0\le k \le m}\perm{2m-k}{k}(-1)^{m-k} z^{2m-2k}. & (5)\cr
}
$$
rEZULXTAT~(4) KRATKO MOZHNO ISTOLKOVATX TAK,
CHTO~$B(z)-q_1(z)\times A(z)$,~\dots, $E(z)-q_4(z)A(z)$ SVODYATSYA K
KONECHNYM SUMMAM, SOOTVETSTVUYUSHCHIM
GRANICHNYM USLOVIYAM, A IMENNO ZNACHENIYAM~$a_{-1}$, $a_{-2}$, $a_{-3}$,~\dots,
KOTORYE POYAVLYAYUTSYA V~(4) (PRI NEBOLXSHIH~$n$), NO NE V~$A(z)$. chTOBY
POLUCHITX PODHODYASHCHIE GRANICHNYE USLOVIYA, PRIMENIM REKURRENTNOE SOOTNOSHENIE
V OBRATNUYU STORONU DLYA OTRICATELXNYH UROVNEJ DO UROVNYA~$-8$:
\ctable{
\hfill$#$\bskip&&\hfill\bskip$#$\bskip\cr
\hfill n & \hfill a_n & \hfill b_n & \hfill c_n & \hfill d_n & \hfill e_n \cr
0 & 1 & 0 & 0 & 0 & 0\cr
-1 & 0 & 0 & 0 & 0 & 1\cr
-2 & 1 & -1 & 0 & 0 & 0\cr
-3 & 0 & 0 & 0 & -1 & 2\cr
-4 & 2 & -3 & 1 & 0 & 0\cr
-5 & 0 & 0 & 1 & -4 & 5\cr
-6 & 5 & -9 & 5 & -1 & 0\cr
-7 & 0 & -1 & 6 & -14 & 14\cr
-8 & 14 & -28 & 20 & -7 & 1\cr
}
(dLYA SEMI LENT TABLICA BYLA BY ANALOGICHNOJ, ODNAKO STROKI S NECHETNYMI~$n$
BYLI BY SDVINUTY VPRAVO NA ODIN |LEMENT.) tAJNA
POSLEDOVATELXNOSTI~$a_0$, $a_{-2}$, $a_{-4},~\ldots=1, 1, 2, 5, 14,~\ldots$
MGNOVENNO RASKRYVAETSYA SPECIALISTOM PO INFORMATIKE, TAK KAK
%%351
|TA POSLEDOVATELXNOSTX VSTRECHAETSYA V SVYAZI S OCHENX MNOGIMI REKURRENTNYMI
ALGORITMAMI (NAPRIMER, V UPR.~2.2.1-4 I FORMULE~2.3.4.4-13)). iTAK, MY
PREDPOLAGAEM, CHTO V SLUCHAE $T$~LENT
$$
\eqalignrem{
a_{-2n}&=\perm{2n}{n}{1\over n+1} & PRI $0\le n \le T-2$; \cr
a_{-2n-1}&=0 & PRI $0\le n \le T-3$.\cr
}
\eqno(6)
$$
chTOBY PROVERITX PRAVILXNOSTX |TOGO PREDPOLOZHENIYA, DOSTATOCHNO POKAZATX,
CHTO~(6) I~(4) PRIVODYAT K PRAVILXNYM REZULXTATAM DLYA UROVNEJ~0 I~1. dLYA
UROVNYA~1 |TO OCHEVIDNO, A DLYA UROVNYA~0 NAM NADO PROVERITX, CHTO
$$
\perm{m}{0}a_0-\perm{m+1}{2}a_{-2}+\perm{m+2}{4}a_{-4}-\perm{m+3}{6}a_{-6}+\cdots
=\sum_{k\ge0}\perm{m+k}{2k}\perm{2k}{k}{(-1)^k\over k+1}
=\delta_{m0}
\eqno(7)
$$
DLYA~$0\le m \le T-2$. k SCHASTXYU, |TU SUMMU MOZHNO VYCHISLITX STANDARTNYMI
METODAMI (|TO "ZADACHA~2", ODIN IZ OSNOVNYH PRIMEROV V TEKSTE P.~4.2.6).
tEPERX MOZHNO VYCHISLITX KO|FFICIENTY~$B(z)-q_1(z)A(z)$ I~T.~D. rASSMOTRIM,
NAPRIMER, KO|FFICIENT PRI~$z^{2m}$ V~$D(z)-q_3(z)A(z)$. oN RAVEN
$$
\eqalign{
\sum_{k\ge0}\perm{3+m+k}{2m+2k}(-1)^{m+k}a_{-2k}
&=\sum_{k\ge0}\perm{3+m+k}{2m+2k}\perm{2k}{k}{(-1)^{m+k}\over k+1}=\cr
&=(-1)^m\left(\perm{2+m}{2m-1}-\perm{3+m}{2m}\right)=\cr
&=(-1)^{m+1}\perm{2+m}{2m}\cr
}
$$
IZ REZULXTATA "ZADACHI~3" V~P.~1.2.6. tAKIM OBRAZOM, MY VYVELI FORMULY
$$
\eqalign{
A(z) &=q_0(z)A(z);\cr
B(z) &=q_1(z)A(z)-q_0(z);\cr
C(z) &=q_2(z)A(z)-q_1(z);\cr
D(z) &=q_3(z)A(z)-q_2(z);\cr
E(z) &=q_4(z)A(z)-q_3(z).\cr
}
\eqno (8)
$$
kROME TOGO, IMEEM~$e_{n+1}=a_n$; SLEDOVATELXNO, $zA(z)=E(z)$ I
$$
A(z)=q_3(z)/(q_4(z)-z).
\eqno (9)
$$
pROIZVODYASHCHIE FUNKCII BYLI VYRAZHENY PRI POMOSHCHI $q\hbox{-MNOGOCHLENOV}$,
PO|TOMU MY HOTIM LUCHSHE IZUCHITX~$q$. v |TOM OTNOSHENII POLEZNO UPR.~1.2.9-15,
TAK KAK ONO DAET VYRAZHENIE V ZAMKNUTOM
%%352
VIDE, KOTOROE MOZHET BYTX ZAPISANO KAK
$$
q_m(z)={((\sqrt{4-z^2}+iz)/2)^{2m+1}+((\sqrt{4-z^2}-iz)/2)^{2m+1}
\over \sqrt{4-z^2}}
\eqno(10) $$
vSE UPROSHCHAETSYA, ESLI TEPERX POLOZHITX~$z=2 \sin\theta$:
$$
\eqalignno{
q_m(2\sin\theta)=&
{(\cos\theta+i\sin\theta)^{2m+1}+(\cos\theta-i\sin\theta)^{2m+1}\over 2\cos\theta}=\cr
&={\cos(2m+1)\theta\over \cos\theta}. & (11)\cr
}
$$
(eTO SOVPADENIE ZASTAVLYAET DUMATX, CHTO MNOGOCHLENY~$q_m(z)$ HOROSHO
IZVESTNY V MATEMATIKE; I DEJSTVITELXNO, VZGLYANUV V SOOTVETSTVUYUSHCHIE
TABLICY, VIDIM, CHTO~$q_m(z)$, PO SUSHCHESTVU, MNOGOCHLEN chEBYSH¸VA VTOROGO RODA,
A IMENNO~$(-1)^m U_{2m}(z/2)$ V OBYCHNYH OBOZNACHENIYAH.)
tEPERX MOZHNO OPREDELITX KORNI ZNAMENATELYA V~(9):
$q_4(2\sin\theta)=2\sin\theta$ SVODITSYA K
$$
\cos 9\theta = 2 \sin \theta \cos \theta = \sin 2\theta.
$$
rESHENIYA |TOGO SOOTNOSHENIYA POLUCHAEM, ESLI
TOLXKO~$\pm9\theta=2\theta+\left(2n-{1\over2}\right)\pi$; VSE
TAKIE~$\theta$ DAYUT KORNI ZNAMENATELYA V~(9) PRI USLOVII,
CHTO~$\cos\theta\ne 0$. (eSLI~$\cos\theta=0$, TO~$q_m(\pm2)=\pm(2m+1)$,
NIKOGDA NE RAVNO~$\pm2$.) sLEDOVATELXNO, POLUCHAEM 8~RAZLICHNYH KORNEJ:
$$
\displaylines{
q_4(z)-z=0 \qquad \hbox{ PRI } z=2\sin{-5\over 14}\pi,\quad
2\sin{-1 \over 14}\pi,\quad 2\sin{3 \over 14}\pi, \cr
2\sin{-7 \over 22}\pi,\quad 2\sin{-3 \over 22}\pi,\quad
2\sin{1 \over 22}\pi, \quad 2\sin{5 \over 22}\pi,\quad 2\sin{9 \over 22}\pi.\cr
}
$$
tAK KAK~$q_4(z)$---MNOGOCHLEN STEPENI~8, MY UCHLI VSE KORNI. pERVYE TRI IZ
|TIH ZNACHENIJ DAYUT~$q_3(z)=0$, TAK CHTO~$q_3(z)$ I~$q_4(z)-z$ IMEYUT OBSHCHIM
DELITELEM MNOGOCHLEN TRETXEJ STEPENI. oSTALXNYE PYATX KORNEJ UPRAVLYAYUT
ASIMPTOTICHESKIM POVEDENIEM KO|FFICIENTOV~$A(z)$, ESLI RAZLOZHITX~(9) V
|LEMENTARNYE DROBI.
pEREJDYA K RASSMOTRENIYU OBSHCHEGO SLUCHAYA $T$~LENT,
POLOZHIM~$\theta_k=(4k+1)\pi/(4T-2)$. pROIZVODYASHCHAYA FUNKCIYA~$A(z)$ DLYA
$T\hbox{-LENTOCHNYH}$ KASKADNYH CHISEL PRINIMAET VID
$$
{4\over 2T-1}\sum_{-T/2<k<\floor{T/2}}{\cos^2\theta_k\over 1-z/(2\sin\theta_k)}
\eqno(12)
$$
(SM.~UPR.~8); SLEDOVATELXNO,
$$
a_n={4\over 2T-1}\sum_{-T/2<k<\floor{T/2}}\cos^2\theta_k \left({1\over 2\sin\theta_k}\right)^n.
\eqno(13)
$$
%% 353
sOOTNOSHENIYA~(8) PRIVODYAT TEPERX K ANALOGICHNYM FORMULAM:
$$
\eqalign{
b_n&={4\over 2T-1}\sum_{-T/2<k<\floor{T/2}}\cos\theta_k\cos3\theta_k\left({1\over 2\sin\theta_k}\right)^n;\cr
c_n&={4\over 2T-1}\sum_{-T/2<k<\floor{T/2}}\cos\theta_k\cos5\theta_k\left({1\over 2\sin\theta_k}\right)^n;\cr
d_n&={4\over 2T-1}\sum_{-T/2<k<\floor{T/2}}\cos\theta_k\cos7\theta_k\left({1\over 2\sin\theta_k}\right)^n\cr
}
\eqno(14)
$$
I~T.~D. v UPR.~9 POKAZANO, CHTO |TI URAVNENIYA SPRAVEDLIVY DLYA VSEH~$n\ge0$,
A NE TOLXKO DLYA BOLXSHIH~$n$. v KAZHDOJ SUMME CHLEN S~$k=0$ ZNACHITELXNO
PREVOSHODIT VSE OSTALXNYE, OSOBENNO ESLI~$n$ DOSTATOCHNO VELIKO;
SLEDOVATELXNO, "OTNOSHENIE ROSTA" ESTX
$$
{1\over 2\sin\theta_0}={2\over\pi}T-{1\over\pi}+{\pi\over 48T}+O(T^{-2}).
\eqno(15)
$$
kASKADNAYA SORTIROVKA VPERVYE BYLA ISSLEDOVANA u.~k.~kARTEROM
[Proc.\ IFIP Congress (1962), 62--66], KOTORYJ POLUCHIL CHISLENNYE REZULXTATY
DLYA NEBOLXSHIH ZNACHENIJ~$T$, I d|VIDOM fERGYUSONOM
[{\sl CACM,\/} {\bf 7} (1964), 297], KOTORYJ OTKRYL PERVYE DVA CHLENA V
ASIMPTOTICHESKOM POVEDENII~(15) OTNOSHENIYA ROSTA.
lETOM 1964~G.\ r.~u.~fLOJD POLUCHIL YAVNYJ VID~$1/(2\sin\theta_0)$
DLYA OTNOSHENIYA ROSTA, TAK CHTO TOCHNYE FORMULY
MOGLI BYTX ISPOLXZOVANY DLYA VSEH~$T$. gLUBOKIJ ANALIZ KASKADNYH CHISEL BYL
NEZAVISIMO VYPOLNEN dZH.~n.~r|JNI
[{\sl Canadian J.~Math.,\/} {\bf 18} (1966), 332--349],
KOTORYJ NATKNULSYA NA NIH SOVERSHENNO DRUGIM PUTEM,
NE IMEYA DELA S SORTIROVKOJ. r|JNI PODMETIL ANALOGIYU S DIAGONALYAMI
(RIS.~73) I VYVEL MNOGO DRUGIH INTERESNYH SVOJSTV |TIH CHISEL. fLOJD
I~r|JNI V SVOIH DOKAZATELXSTVAH OPERIROVALI S MATRICAMI (SM.~UPR.~6).
\section mODIFIKACIYA KASKADNOJ SORTIROVKI. eSLI DOBAVLENA ESHCHE ODNA LENTA,
TO POCHTI VSE VREMYA PEREMOTKI V TECHENIE KASKADNOJ SORTIROVKI MOZHNO
SOVMESTITX. nAPRIMER, MY MOZHEM SLIVATX~T1--T5 NA~T7, ZATEM~T1--T4 NA~T6,
ZATEM~T1--T3 NA~T5 (KOTORAYA K |TOMU MOMENTU UZHE PEREMOTANA), ZATEM~T1--T2
NA~T4 I NACHATX SLEDUYUSHCHIJ PROHOD, KOGDA NA~T4 BUDET PEREMOTANO
SRAVNITELXNO NEMNOGO DANNYH. eFFEKTIVNOSTX |TOGO PROCESSA MOZHNO
PREDSKAZATX NA OSNOVANII IZLOZHENNOGO VYSHE ANALIZA KASKADNOGO
METODA (DALXNEJSHIE PODROBNOSTI SM.~V~P.~5.4.6).
sHEMA "KOMPROMISSNOGO SLIYANIYA", KOTORAYA VKLYUCHAET MNOGOFAZNUYU I KASKADNUYU
SHEMY KAK CHASTNYE SLUCHAI, BYLA PREDLOZHENA d.~e.~kNUTOM V [{\sl CACM,\/}
{\bf 6} (1963), 585--587]. kAZHDAYA FAZA SOSTOIT IZ~$(T-1)\hbox{-PUTEVOGO}$,
$(T-2)\hbox{-PUTEVOGO}$,~\dots, $P\hbox{-PUTEVOGO}$ SLIYANIJ, GDE $P$---LYUBOE
FIKSIROVANNOE CHISLO MEZHDU~1 I~$T-1$. eSLI~$P=T-1$, TO |TO---MNOGOFAZNYJ
METOD; ESLI~$P=1$, |TO---CHISTYJ
%%354
KASKADNYJ METOD; ESLI~$P=2$, |TO---KASKADNYJ METOD BEZ FAZ
KOPIROVANIYA. aNALIZ TAKOJ SHEMY BYL PRODELAN ch.~rADKE
[{\sl IBM Systems J.,\/} {\bf 5} (1966), 226--247] I~u.~h.~bURZHEM
[Proc. IFIP Congress, {\bf 1} (1971), 454---459]. bURZH NASHEL
PROIZVODYASHCHUYU FUNKCIYU~$\sum T_n(x) z^n$ DLYA
KAZHDOGO~$(P, T)\hbox{-KOMPROMISSNOGO}$ SLIYANIYA,
OBOBSHCHAYUSHCHUYU SOOTNOSHENIE~(5.4.2-16); ON
POKAZAL, CHTO NAILUCHSHEE ZNACHENIE~$P$ (S TOCHKI ZRENIYA NAIMENXSHEGO CHISLA
OBRABATYVAEMYH NACHALXNYH OTREZKOV), KAK FUNKCII OT~$S$
PRI~$S\to\infty$ (ESLI NEPOSREDSTVENNO ISPOLXZOVATX SHEMU RASPREDELENIYA
I PRENEBRECHX VREMENEM PEREMOTKI), ESTX SOOTVETSTVENNO
$(2, 3, 3, 4, 4, 4, 3, 3, 4)$ PRI~$T=(3, 4, 5, 6, 7, 8, 9, 10, 11)$.
eTI ZNACHENIYA~$P$ S
ROSTOM~$T$ SILXNEE OTKLONYAYUTSYA V STORONU KASKADNOGO, A NE MNOGOFAZNOGO
METODA, I OKAZYVAETSYA, CHTO KOMPROMISSNOE SLIYANIE NIKOGDA NE STANET
SUSHCHESTVENNO LUCHSHE KASKADNOGO. s DRUGOJ STORONY, PRI OPTIMALXNOM VYBORE
UROVNEJ I RASPREDELENII FIKTIVNYH OTREZKOV, KAK OPISANO V P.~5.4.2, CHISTYJ
MNOGOFAZNYJ METOD KAZHETSYA NAILUCHSHIM SREDI VSEH KOMPROMISSNYH SLIYANIJ.
k SOZHALENIYU, OPTIMALXNOE RASPREDELENIE SRAVNITELXNO TRUDNO REALIZOVATX.
t.~l.~jONSEN [{\sl BIT,\/} {\bf 6} (1966), 129--143] ISSLEDOVAL
SOCHETANIYA SBALANSIROVANNOGO I MNOGOFAZNOGO SLIYANIJ; MODIFIKACIYA
SBALANSIROVANNOGO SLIYANIYA S SOVMESHCHENIEM PEREMOTOK BYLA PREDLOZHENA
m.~gOTCEM [Digital Computer User's Handbook, ed.~by.~M.~Klerer
and~G.~A.~Korn (New York: McGraw-Hill, 1967), 1.311--1.312]; MOZHNO
PREDSTAVITX SEBE I MNOGIE DRUGIE GIBRIDNYE SHEMY.
\excercises
\ex[10] iSPOLXZUYA TABL.~1, SRAVNITE KASKADNOE SLIYANIE S OPISANNOJ
V P.~5.4.2 VERSIEJ MNOGOFAZNOGO SLIYANIYA S "RASSHCHEPLENIEM LENT". kAKOJ
METOD LUCHSHE? (vREMENEM PEREMOTKI PRENEBRECHX.)
\rex[22] sRAVNITE KASKADNUYU SORTIROVKU S TREMYA LENTAMI,
ISPOLXZUYUSHCHUYU ALGORITM~C, I MNOGOFAZNUYU SORTIROVKU S TREMYA LENTAMI,
ISPOLXZUYUSHCHUYU ALGORITM~5.4.2D kAKIE SHODSTVA I RAZLICHIYA VY ZaMeTITe?
\ex[20] sOSTAVXTE TABLICU, POKAZYVAYUSHCHUYU, CHTO PROISHODIT PRI SORTIROVKE NA
SHESTI LENTAH 100~NACHALXNYH OTREZKOV PRI POMOSHCHI ALGORITMA~C.
\ex[m20] (dZH.~n.~r|JNI.) "kASKADNOE RASPREDELENIE $n\hbox{-GO}$ UROVNYA"
ESTX MULXTIMNOZHESTVO, OPREDELENNOE SLEDUYUSHCHIM OBRAZOM (V SLUCHAE SHESTI LENT):
$\set{1, 0, 0, 0, 0}$ ESTX KASKADNOE RASPREDELENIE NULEVOGO UROVNYA;
ESLI~$\set{a, b, c, d, e}$---KASKADNOE RASPREDELENIE $n\hbox{-GO}$~UROVNYA,
TO~$\set{a+b+c+d+e, a+b+c+d, a+b+c, a+b, a}$ BUDET KASKADNYM
RASPREDELENIEM $(n+1)\hbox{-GO}$ UROVNYA (tAK KAK MULXTIMNOZHESTVO NE
UPORYADOCHENO, TO IZ EDINSTVENNOGO RASPREDELENIYA $n\hbox{-GO}$~UROVNYA MOZHNO
OBRAZOVATX DO~5 RAZLICHNYH RASPREDELENIJ $(n+1)\hbox{-GO}$~UROVNYA.)
(a)~dOKAZHITE, CHTO \emph{LYUBOE}
MULXTIMNOZHESTVO~$\set{a, b, c, d, e}$ IZ VZAIMNO PROSTYH CHISEL YAVLYAETSYA
KASKADNYM RASPREDELENIEM $n\hbox{-GO}$~UROVNYA PRI NEKOTOROM~$n$.
(b)~dOKAZHITE, CHTO RASPREDELENIE, ISPOLXZUEMOE V KASKADNOJ SORTIROVKE,
\emph{OPTIMALXNO} V TOM SMYSLE, CHTO ESLI~$\set{a, b, c, d, e}$---LYUBOE
RASPREDELENIE $n\hbox{-GO}$~UROVNYA, PRICHEM~$a\ge b \ge c \ge d \ge e$, TO
BUDEM IMETX~$a\le a_n$, $b\le b_n$, $c\le c_n$, $d\le d_n$, $e\le e_n$,
GDE~$\set{a_n, b_n, c_n, d_n, e_n}$---RASPREDELENIE, OPREDELENNOE V~(1).
\rex[20] dOKAZHITE, CHTO KASKADNYE CHISLA, OPREDELENNYE V~(1), UDOVLETVORYAYUT
%%355
ZAKONU
$$
a_k a_{n-k}+b_k b_{n-k}+c_k c_{n-k}+d_k d_{n-k}+e_k e_{n-k}=a_n
\rem{PRI~$ 0\le k \le n$.}
$$
[\emph{uKAZANIE:} DLYA LUCHSHEGO PONIMANIYA |TOGO SOOTNOSHENIYA RASSMOTRITE,
SKOLXKO OTREZKOV RAZLICHNOJ DLINY VYVODITSYA V TECHENIE $k\hbox{-GO}$~PROHODA
POLNOJ KASKADNOJ SORTIROVKI.]
\ex[m20] nAJDITE $5\times5$-MATRICU~$Q$, TAKUYU, CHTO PERVAYA STROKA~$Q^n$
SODERZHIT KASKADNYE CHISLA DLYA SHESTI LENT~$a_n b_n c_n d_n e_n$ PRI
VSEH~$n\ge 0$.
\ex[m20] pRI USLOVII CHTO KASKADNOE SLIYANIE PRIMENYAETSYA K
TOCHNOMU RASPREDELENIYU $a_n$~NACHALXNYH OTREZKOV, NAJDITE FORMULU DLYA
VELICHINY S|KONOMLENNOJ RABOTY, KOGDA ISKLYUCHAETSYA ODNOPUTEVOE SLIYANIE.
\ex[vm23] vYVEDITE FORMULU~(12).
\ex[vm26] vYVEDITE FORMULU~(14).
\rex[m28] vMESTO SISTEMY~(4) DLYA IZUCHENIYA KASKADNYH CHISEL VOSPOLXZUJTESX
V KACHESTVE ISHODNYH TOZHDESTVAMI
$$
\eqalignter{
e_n&=a_{n-1} &= \perm{1}{1}a_{n-1};\cr
d_n&=2a_{n-1}-e_{n-2} &=\perm{2}{1}a_{n-1}-\perm{3}{3}a_{n-3};\cr
c_n&=3a_{n-1}-d_{n-2}-2e_{n-2} &=\perm{3}{1}a_{n-1}-\perm{4}{3}a_{n-3}+\perm{5}{5}a_{n-5}\cr
}
$$
I~T.~D. pOLAGAYA
$$
r_m(z)=\perm{m}{1}z-\perm{m+1}{3}z^3+\perm{m+2}{5}z^5-\ldots,
$$
VYRAZITE~$A(z)$, $B(z)$ I~T.~D.\ CHEREZ |TI $r\hbox{-MNOGOCHLENY}$.
\ex[m38] pUSTX
$$
f_m(z)=\sum_{0\le k \le m} \perm{\floor{(m+k)/2}}{k}(-1)^{\ceil{k/2}}z^k.
$$
dOKAZHITE, CHTO PROIZVODYASHCHAYA FUNKCIYA~$A(z)$ DLYA $T\hbox{-LENTOCHNYH}$
KASKADNYH CHISEL RAVNA~$f_{T-3}(z)/f_{T-1}(z)$, PRICHEM CHISLITELX I
ZNAMENATELX |TOGO VYRAZHENIYA NE IMEYUT OBSHCHIH DELITELEJ.
\ex[m40] dOKAZHITE, CHTO SHEMA RASPREDELENIYA fERGYUSONA OPTIMALXNA V TOM
SMYSLE, CHTO PRI LYUBOM DRUGOM METODE RAZMESHCHENIYA FIKTIVNYH OTREZKOV,
UDOVLETVORYAYUSHCHEM~(2), VO VREMYA PERVOGO PROHODA BUDET OBRABATYVATXSYA
NE MENXSHE NACHALXNYH OTREZKOV, \emph{PRI USLOVII} CHTO VO VREMYA |TOGO
PROHODA ISPOLXZUETSYA STRATEGIYA SHAGOV~C7--C9.
\ex[40] v TEKSTE PREDLAGAETSYA BOLXSHUYU CHASTX VREMENI PEREMOTKI SOVMESHCHATX
PUTEM DOBAVLENIYA DOPOLNITELXNOJ LENTY. rAZRABOTAJTE |TU IDEYU. (nAPRIMER,
SHEMA, IZLOZHENNAYA V TEKSTE, VKLYUCHAET OZHIDANIE PEREMOTKI LENTY~T4;
NE BUDET LI LUCHSHE ISKLYUCHITX~T4 IZ PERVOJ FAZY SLIYANIYA SLEDUYUSHCHEGO PROHODA?)
\subsubchap{chTENIE LENTY V OBRATNOM NAPRAVLENII} %% 5.4.4
mNOGIE LENTOPROTYAZHNYE USTROJSTVA POZVOLYAYUT CHITATX LENTU V NAPRAVLENII,
PROTIVOPOLOZHNOM TOMU, V KOTOROM SHLA ZAPISX NA NEE. sHEMY SLIYANIYA, S
KOTORYMI MY VSTRECHALISX DO SIH POR, VSEGDA ZAPISYVAYUT INFORMACIYU NA LENTU
V PRYAMOM NAPRAVLENII,
%% 356
\bye