%% 428 \input style \subsubchap{dISKI I BARABANY} dO SIH POR MY RASSMATRIVALI LENTY KAK EDINSTVENNOE SREDSTVO DLYA VNESHNEJ SORTIROVKI, ODNAKO NEREDKO V NASHEM RASPORYAZHENII OKAZYVAYUTSYA I DRUGIE TIPY USTROJSTV MASSOVOJ PAMYATI S BOLEE GIBKIMI VOZMOZHNOSTYAMI. hOTYA TAKIE ZAPOMINAYUSHCHIE .USTROJSTVA "BOLXSHOGO OB®EMA" ILI "ZAPOMINAYUSHCHIE USTROJSTVA S PRYAMYM DOSTUPOM" VESXMA MNOGOOBRAZNY, MOZHNO VYDELITX SLEDUYUSHCHIE OBSHCHIE SVOJSTVA: \medskip \item{i)} dLYA DOSTUPA K LYUBOJ OPREDELENNOJ CHASTI HRANIMOJ INFORMACII NE TREBUETSYA OCHENX MNOGO VREMENI. \item{ii)} bLOKI, SODERZHASHCHIE POSLEDOVATELXNYE SLOVA, MOGUT BYSTRO PEREDAVATXSYA MEZHDU VNUTRENNEJ (OPERATIVNOJ) I VNESHNEJ PAMYATXYU. \medskip \noindent mAGNITNAYA LENTA UDOVLETVORYAET (ii), NO NE (i), POSKOLXKU PEREHOD LENTY OT ODNOGO KONCA K DRUGOMU ZANIMAET MNOGO VREMENI. nEKOTORYE USTROJSTVA UDOVLETVORYAYUT (i), NO NE (ii); PRIMEROM MOZHET SLUZHITX PAMYATX BOLXSHOGO OB®EMA NA FERRITOVYH SERDECHNIKAH, \picture{rIS. 89. pAKET DISKOV} V KOTOROJ VREMYA DOSTUPA K KAZHDOMU SLOVU PRIMERNO V DESYATX RAZ PREVYSHAET VREMYA DOSTUPA K VNUTRENNEJ PAMYATI. kAZHDOE VNESHNEE ZAPOMINAYUSHCHEE USTROJSTVO IMEET SVOI HARAKTERNYE OSOBENNOSTI, KOTORYE SLEDUET TSHCHATELXNO IZUCHITX, PREZHDE CHEM PISATX DLYA NEGO BOLXSHIE PROGRAMMY; ODNAKO TEHNOLOGIYA MENYAETSYA TAK BYSTRO, CHTO ZDESX NE UDASTSYA SKOLXKO-NIBUDX PODROBNO OBSUDITX VSE SUSHCHESTVUYUSHCHIE RAZNOVIDNOSTI OBORUDOVANIYA. pO|TOMU MY RASSMOTRIM LISHX NEKOTORYE TIPICHNYE ZAPOMINAYUSHCHIE USTROJSTVA I NA .NIH PROILLYUSTRIRUEM PRODUKTIVNYE PODHODY K ZADACHE SORTIROVKI. oDNIM IZ NAIBOLEE RASPROSTRANENNYH TIPOV VNESHNIH ZAPOMINAYUSHCHIH USTROJSTV, UDOVLETVORYAYUSHCHIH (i) I (ii), YAVLYAETSYA DISKOVYJ %% 429 FAJL ILI MODULX S PAKETOM DISKOV (RIS. 89). dANNYE HRANYATSYA NA NESKOLXKIH BYSTRO VRASHCHAYUSHCHIHSYA KRUGLYH DISKAH, POKRYTYH MAGNITNYM MATERIALOM; DLYA ZAPISI ILI VYBORKI INFORMACII ISPOLXZUETSYA DERZHATELX GOLOVOK V VIDE GREBESHKA. SODERZHASHCHIJ ODNU ILI NESKOLXKO "GOLOVOK CHTENIYA/ZAPISI" DLYA KAZHDOJ POVERHNOSTI DISKA. kAZHDAYA POVERHNOSTX DELITSYA NA KONCENTRICHESKIE KOLXCA, NAZYVAEMYE \emph{DOROZHKAMI} ILI \emph{TREKAMI}, TAK CHTO ZA VREMYA ODNOGO OBOROTA DISKA POD GOLOVKAMI CHTENIYA/ZAPISI PROHODIT CELAYA DOROZHKA. dERZHATELX GOLOVOK MOZHET PEREMESHCHATXSYA V DVUH NAPRAVLENIYAH---VNUTRX ILI NARUZHU, PEREDVIGAYA GOLOVKI CHTENIYA/ZAPISI OT DOROZHKI K DOROZHKE, NO |TO DVIZHENIE TREBUET VREMENI. mNOZHESTVO DOROZHEK, KOTORYE MOGUT BYTX PROCHITANY ILI ZAPISANY BEZ PEREMESHCHENIYA DERZHATELYA GOLOVOK, NAZYVAETSYA \emph{CILINDROM}. nAPRIMER, NA RIS.~89 POKAZAN DISKOVYJ FAJL, KOTORYJ IMEET PO ODNOJ GOLOVKE CHTENIYA/ZAPISI NA KAZHDUYU POVERHNOSTX; PUNKTIRNYMI LINIYAMI OBOZNACHEN ODIN IZ CILINDROV, SOSTOYASHCHIJ IZ VSEH DOROZHEK, PROSMATRIVAEMYH V NASTOYASHCHIJ MOMENT GOLOVKAMI. chTOBY SDELATX NASHI RASSUZHDENIYA BOLEE KONKRETNYMI, RASSMOTRIM GIPOTETICHESKOE DISKOVOE USTROJSTVO |MIXTEC|, DLYA KOTOROGO $$ \eqalign{ \hbox{1 DOROZHKA}& =\hbox{5000 LITER,}\cr \hbox{1 CILINDR}& =\hbox{20 DOROZHEK,}\cr \hbox{1 DISKOVOE USTROJSTVO}&= \hbox{200 CILINDROV.}\cr } $$ tAKOE DISKOVOE USTROJSTVO SODERZHIT 20 MILLIONOV LITER, T. E. CHUTX MENXSHE TOGO OB®EMA DANNYH, KOTORYJ MOZHNO ZAPISATX NA ODNU MAGNITNUYU LENTU. nA NEKOTORYH MASHINAH DOROZHKI VBLIZI CENTRA SODERZHAT MENXSHE LITER, CHEM DOROZHKI BLIZHE K KRAYU. oT |TOGO PROGRAMMIROVANIE ZNACHITELXNO USLOZHNYAETSYA, NO |MIXTEC|, K SCHASTXYU, NE SOZDAET TAKIH PROBLEM. vREMYA, NEOBHODIMOE DLYA CHTENIYA ILI ZAPISI NA DISKOVYJ FAJL, PREDSTAVLYAET, PO SUSHCHESTVU, SUMMU TREH VELICHIN: \itemize \li vREMYA POISKA (VREMYA, ZATRACHIVAEMOE NA PEREMESHCHENIE DERZHATELYA GOLOVOK K NUZHNOMU CILINDRU). \li vREMYA OZHIDANIYA (ZADERZHKA, SVYAZANNAYA S VRASHCHENIEM DISKA, POKA GOLOVKA CHTENIYA/ZAPISI NE DOSTIGNET NUZHNOGO MESTA). \li vREMYA PEREDACHI (ZADERZHKA, SVYAZANNAYA S VRASHCHENIEM DISKA, POKA DANNYE PROHODYAT POD GOLOVKAMI). \itemend nA USTROJSTVAH |MIXTEC| VREMYA POISKA DLYA PEREHODA OT CILINDRA $i$ K CILINDRU $j$ RAVNO $25+{1\over2}\vert i-j \vert$ MS. eSLI $i$ I $j$---SLUCHAJNO VYBRANNYE CELYE CHISLA MEZHDU 1 I 200, TO SREDNEE ZNACHENIE %%430 $\vert i-j\vert$ RAVNO $2 \left( {201\atop 3}\right)/200^2\approx 66.7$, T. E. SREDNEE VREMYA POISKA SOSTAVLYAET PRIBLIZITELXNO 60~MS. dISKI |MIXTEC| SOVERSHAYUT ODIN OBOROT ZA 25 MS, TAK CHTO VREMYA OZHIDANIYA RAVNO V SREDNEM 12.5 MS. vREMYA PEREDACHI $n$ LITER ESTX $(n/5000)\times25\hbox{ MS}=5n\hbox{ MKS}$. (eTO PRIMERNO V $3{1\over3}$ RAZA BYSTREE, CHEM SKOROSTX PEREDACHI DLYA LENT |MIXT|, ISPOLXZOVANNYH V PRIMERAH P.~5.4.6.) tAKIM OBRAZOM, OSNOVNYE RAZLICHIYA MEZHDU DISKAMI |MIXTEC| I LENTAMI |MIXT|, KASAYUSHCHIESYA SORTIROVKI, SLEDUYUSHCHIE: \medskip \item{a)} nA LENTAH VOZMOZHEN TOLXKO POSLEDOVATELXNYJ DOSTUP K DANNYM. \item{b)} oTDELXNAYA OPERACIYA S DISKOM, KAK PRAVILO, SOPRYAZHENA SO ZNACHITELXNO BOLXSHIMI NAKLADNYMI RASHODAMI (VREMYA POISKA + VREMYA OZHIDANIYA V SRAVNENII SO STARTSTOPNYM VREMENEM). \item{c)} sKOROSTX PEREDACHI U DISKA BOLXSHE. \medskip iSPOLXZUYA DLYA LENT RAZUMNYE SHEMY SLIYANIYA, MY MOGLI DO NEKOTOROJ STEPENI SKOMPENSIROVATX NEDOSTATOK (a). tEPERX U NAS INAYA CELX---NAM NUZHNO NAJTI TAKIE RACIONALXNYE ALGORITMY SORTIROVKI NA DISKAH, V KOTORYH KOMPENSIRUETSYA NEDOSTATOK (b). \qsection kAK SOKRATITX VREMYA OZHIDANIYA? rASSMOTRIM .SNACHALA ZADACHU MINIMIZACII ZADERZHEK, VYZYVAEMYH TEM, CHTO V TOT MOMENT, KOGDA MY HOTIM NACHATX KOMANDU VVODA/VYVODA, DISK NE VSEGDA NAHODITSYA V PODHODYASHCHEJ POZICII. nELXZYA ZASTAVITX DISK VRASHCHATXSYA BYSTREE, NO VSE-TAKI MOZHNO PRIBEGNUTX K RAZNYM ULOVKAM, KOTORYE UMENXSHAT ILI DAZHE POLNOSTXYU USTRANYAT VREMYA OZHIDANIYA. nESOMNENNO, POMOZHET DOBAVLENIE ESHCHE NESKOLXKIH DERZHATELEJ GOLOVOK, NO |TO VESXMA DOROGOSTOYASHCHAYA MODIFIKACIYA OBORUDOVANIYA. vOT NESKOLXKO "PROGRAMMISTSKIH" IDEJ. \enumerate \li eSLI MY CHITAEM ILI ZAPISYVAEM ZA ODIN RAZ NESKOLXKO DOROZHEK ODNOGO CILINDRA, TO TEM SAMYM USTRANYAEM VREMYA OZHIDANIYA (I VREMYA POISKA) DLYA VSEH DOROZHEK, KROME PERVOJ. vOOBSHCHE ZACHASTUYU MOZHNO TAKIM OBRAZOM SINHRONIZOVATX VYCHISLENIYA S VRASHCHENIEM DISKA, CHTO PRI VYPOLNENII POSLEDOVATELXNOSTI KOMAND VVODA/VYVODA NE BUDET ZADERZHEK IZ-ZA OZHIDANIYA. \li rASSMOTRIM ZADACHU CHTENIYA POLOVINY DOROZHKI DANNYH (RIS.~90): ESLI KOMANDA CHTENIYA VYDAETSYA, KOGDA GOLOVKA NAHODITSYA V TOCHKE $A$, TO ZADERZHKA NA OZHIDANIE OTSUTSTVUET, I OBSHCHEE VREMYA CHTENIYA RAVNO VREMENI PEREDACHI, T.E. ${1\over2}\times25$ MS. eSLI KOMANDA NACHINAETSYA, KOGDA GOLOVKA NAHODITSYA V TOCHKE $B$, TO TREBUETSYA ${1\over 4}$ OBOROTA DLYA OZHIDANIYA I $1\over2$ DLYA PEREDACHI; V ITOGE IMEEM %%431 ${3\over4}\times25$ MS. nAIBOLEE INTERESEN SLUCHAJ, KOGDA GOLOVKA PERVONACHALXNO NAHODITSYA V TOCHKE $C$: IMEYA SOOTVETSTVUYUSHCHEE OBORUDOVANIE I PROGRAMMNOE OBESPECHENIE, NAM \emph{NE} PRIDETSYA TERYATX $3\over4$ OBOROTA NA OZHIDANIE. mOZHNO NEMEDLENNO NACHATX CHTENIE VO VTORUYU POLOVINU BUFERA VVODA, ZATEM POSLE PAUZY V ${1\over2}\times25$ MS .MOZHNO VOZOBNOVITX CHTENIE V PERVUYU POLOVINU BUFERA, TAK CHTO KOMANDA . BUDET ZAVERSHENA, KOGDA MY SNOVA POPADEM V TOCHKU $C$. pOSTUPAYA \picture{rIS. 90. aNALIZ VREMENI OZHIDANIYA PRI CHTENII POLOVINY DOROZHKI} TAKIM OBRAZOM, MOZHNO GARANTIROVATX, CHTO OBSHCHEE VREMYA NA OZHIDANIE+PEREDACHU NIKOGDA NE PREVZOJDET VREMENI ODNOGO OBOROTA NEZAVISIMO OT NACHALXNOGO POLOZHENIYA DISKA. sREDNEE VREMYA OZHIDANIYA UMENXSHAETSYA |TOJ SHEMOJ S POLOVINY OBOROTA DO ${1\over2}(1-x^2)$ OBOROTA, ESLI CHITAETSYA ILI ZAPISYVAETSYA DOLYA $x$ DOROZHKI ($0NECHETNOE CHISLO RAZ, NO V SLUCHAE ODNOGO BARABANA MOZHNO ISPOLXZOVATX BOLEE OBSHCHIE SHEMY SLIYANIYA. mY VIDELI V P.~5.4.4, CHTO SHEMY SLIYANIYA MOZHNO IZOBRAZHATX S POMOSHCHXYU DEREVXEV I CHTO VREMYA PEREDACHI, SOOTVETSTVUYUSHCHEE SHEME SLIYANIYA, PROPORCIONALXNO DLINE VNESHNEGO PUTI DEREVA. v KACHESTVE SHEM |FFEKTIVNOGO SLIYANIYA NA LENTAH MOZHNO ISPOLXZOVATX LISHX VPOLNE OPREDELENNYE DEREVXYA ("$T$-lifo" ILI "SILXNYE $T$-fifo"), POTOMU CHTO V PROCESSE SLIYANIYA NEKOTORYE OTREZKI OKAZYVAYUTSYA "SPRYATANNYMI" V SEREDINE LENTY. nO \emph{PRI ISPOLXZOVANII DISKOV ILI BARABANOV PRIGODNY LYUBYE DEREVXYA}, ESLI TOLXKO STEPENI IH VNUTRENNIH UZLOV NE SLISHKOM VELIKI (T. E. SOGLASUYUTSYA S NALICHNYM OB®EMOM VNUTRENNEJ PAMYATI). sLEDOVATELXNO, VREMYA PEREDACHI MOZHNO MINIMIZIROVATX, ESLI VYBRATX DEREVO S MINIMALXNOJ DLINOJ VNESHNEGO PUTI, TAKOE, KAK POLNOE $P$-ARNOE DEREVO, GDE $P$---SAMOE BOLXSHOE, KAKOE VOZMOZHNO. pO FORMULE (5.4.4--9) DLINA VNESHNEGO PUTI TAKOGO DEREVA %% 434 S $S$ VNESHNIMI UZLAMI (LISTXYAMI) RAVNA $$ qS-\lfloor(P^q-S)/(P-1)\rfloor, \qquad q=\lceil\log_P S\rceil. \eqno(1) $$ oSOBENNO PROSTO STROITSYA ALGORITM, KOTORYJ OSUSHCHESTVLYAET SLIYANIE V SOOTVETSTVII SO SHEMOJ POLNOGO $P$-ARNOGO DEREVA. (sM., NAPRIMER, RIS.~91, NA KOTOROM POKAZAN SLUCHAJ $P=3$, $S=6$.) sNACHALA MY DOBAVLYAEM, ESLI NEOBHODIMO, "FIKTIVNYE OTREZKI", CHTOBY SDELATX $S\equiv1 \pmod{P-1}$; ZATEM OB®EDINYAEM OTREZKI V SOOTVETSTVII S DISCIPLINOJ "PERVYM VKLYUCHAETSYA --- \picture{rIS. 92. pOLNOE TERNARNOE DEREVO S SHESTXYU LISTXYAMI...} PERVYM ISKLYUCHAETSYA", SLIVAYA NA KAZHDOM |TAPE $P$ SAMYH "STARYH" OTREZKOV V NACHALE OCHEREDI V ODIN OTREZOK, POMESHCHAEMYJ V KONEC. pOLNYE $P$-ARNYE DEREVXYA DAYUT OPTIMALXNUYU SHEMU, ESLI VSE OTREZKI IMEYUT RAVNUYU DLINU, NO CHASTO REZULXTAT MOZHET BYTX ESHCHE LUCHSHE, ESLI NEKOTORYE OTREZKI DLINNEE DRUGIH. oPTIMALXNUYU SHEMU DLYA |TOJ OBSHCHEJ SITUACII MOZHNO BEZ TRUDA POSTROITX S POMOSHCHXYU METODA hAFFM|NA (UPR. 2.3.4.5--10), KOTORYJ NA YAZYKE SLIYANIYA FORMULIRUETSYA TAK: "SNACHALA DOBAVXTE $(1-S)\bmod(P-1)$ FIKTIVNYH OTREZKOV DLINY 0, ZATEM MNOGOKRATNO SLIVAJTE $P$ \emph{KRATCHAJSHIH} IZ IMEYUSHCHIHSYA OTREZKOV, POKA NE OSTANETSYA ODIN OTREZOK". eSLI VSE NACHALXNYE OTREZKI IMEYUT ODINAKOVUYU DLINU, TO |TOT METOD SVODITSYA K OPISANNOJ VYSHE DISCIPLINE. v NASHEM PRIMERE SO 100000, ZAPISEJ MY MOZHEM VYPOLNYATX 9-PUTEVOE SLIYANIE, TAK KAK V PAMYATI POMESTYATSYA 18 BUFEROV VVODA I DVA BUFERA VYVODA, I V ALGORITME 5.4.6F BUDET DOSTIGNUTO POLNOE SOVMESHCHENIE VYCHISLENIJ. pOLNOE 9-ARNOE DEREVO S 60 LISTXYAMI SOOTVETSTVUET SHEME SLIYANIYA S $1{29\over30}$ PROHODA, ESLI. VSE NACHALXNYE OTREZKI IMEYUT ODINAKOVUYU DLINU. oBSHCHEE VREMYA SORTIROVKI S ODNIM BARABANOM I S ISPOLXZOVANIEM "KONTROLXNOGO CHTENIYA" POSLE KAZHDOJ ZAPISI STANOVITSYA, TAKIM OBRAZOM, RAVNYM 7.4 MIN. uVELICHIVAYA $P$, MOZHNO NEMNOGO UMENXSHITX |TO VREMYA, NO SITUACIYA VESXMA ZAPUTANNAYA, POSKOLXKU NE ISKLYUCHAETSYA ZADERZHKA CHTENIYA, TAK KAK BUFERY MOGUT OKAZATXSYA SLISHKOM POLNYMI ILI SLISHKOM PUSTYMI. %%435 \section vLIYANIE VREMENI POISKA. pREDYDUSHCHEE OBSUZHDENIE POKAZYVAET, CHTO DLYA BARABANOV OTNOSITELXNO LEGKO SKONSTRUIROVATX "OPTIMALXNUYU" SHEMU SLIYANIYA, POSKOLXKU VREMYA POISKA I VREMYA OZHIDANIYA MOZHNO SVESTI NA NET. nO ESLI ISPOLXZUYUTSYA DISKI, TO POISK INFORMACII ZANIMAET BOLXSHE VREMENI, CHEM EE CHTENIE. pO|TOMU VREMYA POISKA OKAZYVAET ZNACHITELXNOE VLIYANIE NA STRATEGIYU SORTIROVKI. uMENXSHENIE PORYADKA SLIYANIYA $P$ DAET VOZMOZHNOSTX . ISPOLXZOVATX BOLXSHIE PO RAZMERU BUFERY, TAK CHTO REZHE TREBUETSYA POISK; ZA SCHET |TOGO CHASTO KOMPENSIRUETSYA DOPOLNITELXNOE VREMYA PEREDACHI, KOTOROE RASTET S UMENXSHENIEM $P$. vREMYA POISKA ZAVISIT OT RASSTOYANIYA, PROHODIMOGO DERZHATELEM GOLOVOK, I MOZHNO POPYTATXSYA ORGANIZOVATX RABOTU TAKIM OBRAZOM, CHTOBY |TO RASSTOYANIE BYLO MINIMALXNYM. bYTX MOZHET, RAZUMNO SNACHALA SORTIROVATX ZAPISI VNUTRI CILINDROV. oDNAKO DOVOLXNO BOLXSHOE SLIYANIE TREBUET BOLXSHOGO KOLICHESTVA PEREHODOV. MEZHDU CILINDRAMI (SM., NAPRIMER, UPR.~2). kROME TOGO, REZHIM MULXTIPROGRAMMIROVANIYA V SOVREMENNYH OPERACIONNYH SISTEMAH OZNACHAET, CHTO POLXZOVATELX LISHX V REDKIH SLUCHAYAH MOZHET PO-NASTOYASHCHEMU KONTROLIROVATX POLOZHENIE DERZHATELYA GOLOVOK; BLESTYASHCHIE SHEMY, MINIMIZIRUYUSHCHIE POISK, OBYCHNO RABOTAYUT TOLXKO PO VYHODNYM DNYAM! tAKIM OBRAZOM, PREDPOLOZHENIE O TOM, CHTO KAZHDAYA KOMANDA DLYA DISKA TREBUET "SLUCHAJNOGO" POISKA, CHASTO VPOLNE OPRAVDANO. nASHA CELX V TOM I SOSTOIT, CHTOBY NAJTI TAKOE DEREVO (T. E. SHEMU SLIYANIYA), KOTOROE OBESPECHIVAET NAILUCHSHIJ BALANS MEZHDU VREMENEM POISKA I VREMENEM PEREDACHI; DLYA |TOJ CELI NAM NUZHEN NEKOTORYJ SPOSOB, POZVOLYAYUSHCHIJ OCENITX DOSTOINSTVA LYUBOGO KONKRETNOGO DEREVA PO OTNOSHENIYU K KONKRETNOJ KONFIGURACII OBORUDOVANIYA. rASSMOTRIM, NAPRIMER, DEREVO NA RIS.~92; MY HOTIM OCENITX, SKOLXKO VREMENI ZAJMET VYPOLNENIE'SOOTVETSTVUYUSHCHEGO SLIYANIYA, CHTOBY MOZHNO BYLO SRAVNITX |TO DEREVO S DRUGIMI. v POSLEDUYUSHCHIH RASSUZHDENIYAH MY SDELAEM NEKOTORYE PROSTYE PREDPOLOZHENIYA OTNOSITELXNO SLIYANIYA NA DISKAH, CHTOBY PROILLYUSTRIROVATX NEKOTORYE OBSHCHIE IDEI. pREDPOLOZHIM, CHTO (1) NA CHTENIE ILI ZAPISX $n$ LITER TREBUETSYA $72.5+0.005n$~MS; (2) POD RABOCHEE PROSTRANSTVO OTVODITSYA 100000 LITER VNUTRENNEJ PAMYATI; (3) DLYA PERESYLKI ODNOJ LITERY IZ BUFERA VVODA V BUFER VYVODA ZATRACHIVAETSYA V SREDNEM $0.004$~MS NA VYCHISLENIE; (4) \emph{NET SOVMESHCHENIYA} CHTENIYA, ZAPISI I VYCHISLENIJ; (5) RAZMER BUFERA, ISPOLXZUEMOGO DLYA VYVODA, NE OBYAZATELXNO DOLZHEN BYTX RAVEN RAZMERU BUFERA, ISPOLXZUEMOGO DLYA CHTENIYA DANNYH NA SLEDUYUSHCHEM PROHODE. aNALIZ ZADACHI SORTIROVKI PRI |TIH PROSTYH PREDPOLOZHENIYAH BUDET POLEZEN DLYA PONIMANIYA BOLEE SLOZHNYH SITUACIJ. eSLI VYPOLNYAETSYA $P$-PUTEVOE SLIYANIE, TO MY MOZHEM RAZDELITX %% 436 VNUTRENNYUYU RABOCHUYU PAMYATX NA $P+1$ BUFERNYH OBLASTEJ: $P$---DLYA VVODA I 1---DLYA VYVODA; V KAZHDOM BUFERE PO $B=100000/(P+1)$ LITER. pREDPOLOZHIM, CHTO PREDNAZNACHENNYE DLYA SLIYANIYA FAJLY SODERZHALI V SUMME $L$ LITER; TOGDA MY VYPOLNIM PRIBLIZITELXNO $L/B$ OPERACIJ VYVODA I PRIMERNO STOLXKO ZHE OPERACIJ VVODA; SLEDOVATELXNO, OBSHCHEE VREMYA SLIYANIYA PRI TAKIH PREDPOLOZHENIYAH BUDET RAVNO (V MILLISEKUNDAH) PRIBLIZITELXNO $$ 2\left(72.5{L\over B}+0.005L\right)+0.004L=(0.00145P+0.011545)L. \eqno(2) $$ iNYMI SLOVAMI, $P$-PUTEVOE SLIYANIE $L$ LITER ZANIMAET PRIMERNO $(\alpha P+\beta)L$ EDINIC VREMENI, GDE $\alpha$ I~$\beta$---NEKOTORYE KONSTANTY, ZAVISYASHCHIE OT VREMENI POISKA, VREMENI OZHIDANIYA, VREMENI VYCHISLENIJ I RAZMERA PAMYATI. eTA FORMULA PRIVODIT K INTERESNOMU SPOSOBU POSTROENIYA HOROSHIH SHEM SLIYANIYA DLYA \picture{rIS. 92. dEREVO S DLINOJ VNESHNEGO PUTI 16 ...} DISKOV. rASSMOTRIM, NAPRIMER, RIS.~92 I BUDEM SCHITATX, CHTO VSE NACHALXNYE .OTREZKI (IZOBRAZHENNYE KVADRATNYMI "LISTXYAMI") IMEYUT DLINU $L_0$.. tOGDA KAZHDOE SLIYANIE V UZLAH 9 I~10 ZANIMAET $(2\alpha+\beta)(2L_0)$ EDINIC VREMENI, SLIYANIE V UZLE 11 ZANIMAET $(3\alpha+\beta)(4L_0)$ EDINIC I OKONCHATELXNOE SLIYANIE V UZLE 12 ZANIMAET $(4\alpha+\beta)(8L_0)$ EDINIC. oBSHCHEE VREMYA SLIYANIYA, SLEDOVATELXNO, SOSTAVLYAET $(52\alpha + 16\beta)L_0$ EDINIC. kO|FFICIENT "16" NAM HOROSHO IZVESTEN: |TO PROSTO DLINA VNESHNEGO PUTI DEREVA. kO|FFICIENT "52" PRI $\alpha$ SOOTVETSTVUET NOVOMU PONYATIYU, KOTOROE MY MOZHEM NAZVATX \dfn{DLINOJ STEPENNOGO PUTI DEREVA}; ONA RAVNA SUMME, VZYATOJ PO VSEM LISTXYAM, STEPENEJ VNUTRENNIH UZLOV, LEZHASHCHIH NA PUTI OT LISTA K KORNYU. nAPRIMER, NA RIS.~92 DLINA STEPENNOGO PUTI RAVNA $(2+4)+(2+4)+(3+4)+(2+3+4)+(2+3+4)+(3+4)+(4)+(4)=52$. eSLI $\cJ$---LYUBOE DEREVO, TO PUSTX $D(\cJ)$, $E(\cJ)$ OBOZNACHAYUT SOOTVETSTVENNO DLINU STEPENNOGO PUTI I DLINU VNESHNEGO PUTI |TOGO DEREVA. aNALIZ SVODITSYA K SLEDUYUSHCHEJ TEOREME: %% 437 \proclaim tEOREMA H. eSLI VREMYA, TREBUEMOE DLYA VYPOLNENIYA $P$-PUTEVOGO SLIYANIYA $L$ LITER, IMEET VID $(\alpha P+\beta)L$ I ESLI TREBUETSYA SLITX $S$ OTREZKOV RAVNOJ DLINY, TO NAILUCHSHAYA SHEMA SLIYANIYA SOOTVETSTVUET DEREVU $\cJ$, DLYA KOTOROGO $\alpha D (\cJ)+\beta E(\cJ)$ MINIMALXNO SREDI VSEH DEREVXEV S $S$ LISTXYAMI. \noindent (eTA TEOREMA NEYAVNO SODERZHALASX V NEOPUBLIKOVANNOJ STATXE, KOTORUYU dZHORDZH a. hABB|RD PREDSTAVIL NA NACIONALXNUYU KONFERENCIYU ACM V 1963 G.) pUSTX $\alpha$ I $\beta$---FIKSIROVANNYE KONSTANTY; BUDEM GOVORITX, CHTO DEREVO \dfn{OPTIMALXNO}, ESLI ONO IMEET MINIMALXNOE ZNACHENIE $\alpha D(\cJ)+\beta E (\cJ)$ SREDI VSEH DEREVXEV $\cJ$ S TEM ZHE CHISLOM LISTXEV. nETRUDNO VIDETX, CHTO \emph{VSE PODDEREVXYA OPTIMALXNOGO DEREVA TAKZHE OPTIMALXNY}. pO|TOMU MY MOZHEM STROITX OPTIMALXNYE DEREVXYA S $n$ LISTXYAMI, OB®EDINYAYA OPTIMALXNYE DEREVXYA, U KOTORYH MENXSHE CHEM $n$ LISTXEV. \proclaim tEOREMA K. pUSTX POSLEDOVATELXNOSTX CHISEL $A_m(n)$ OPREDELENA PRI $1\le m\le n$ PRAVILAMI $$ \eqalignno{ A_1(1)&=0; & (3) \cr A_m(n)&=\min_{1\le k\le n/m} (A_1(k)+A_{m-1}(n-k) \rem{PRI $2\le m\le n$;} & (4) \cr A_1(n)&=\min_{2\le m\le n} ((\alpha mn+\beta n+A_m(n)) \rem{PRI $n\ge 2$.} & (5)\cr } $$ tOGDA $A_1(n)$ ESTX MINIMALXNOE ZNACHENIE $\alpha D (\cJ) +\beta E(\cJ)$ SREDI VSEH DEREVXEV $\cJ$ S $n$ LISTXYAMI. \proof iZ SOOTNOSHENIYA (4) SLEDUET, CHTO $A_m(n)$ ESTX MINIMALXNOE ZNACHENIE $A_1(n_1)+\cdots+A_1(n_m)$ PO VSEM POLOZHITELXNYM CHISLAM $n_1$, \dots, $n_m$, TAKIM, CHTO $n_1+\cdots+n_m=n$. tREBUEMYJ REZULXTAT POLUCHAETSYA TEPERX INDUKCIEJ PO~$n$. \proofend rEKURRENTNYE SOOTNOSHENIYA (3), (4), (5) MOZHNO ISPOLXZOVATX TAKZHE DLYA POSTROENIYA SAMIH OPTIMALXNYH DEREVXEV. pUSTX $k_m(n)$---ZNACHENIE, DLYA KOTOROGO DOSTIGAETSYA MINIMUM V OPREDELENII $A_m(P)$. tOGDA MOZHNO POSTROITX OPTIMALXNOE DEREVO S $n$ LISTXYAMI, OB®EDINYAYA $m=k_1(n)$ PODDEREVXEV V KORNE; PODDEREVXYA YAVLYAYUTSYA OPTIMALXNYMI DEREVXYAMI S $k_m(n)$, $k_{m-1}(n-k_m(n))$, $k_{m-2}(n-k_m(n)-k_{m-1}(n-k_m(n)))$, \dots LISTXYAMI SOOTVETSTVENNO. eTA KONSTRUKCIYA PRI $\alpha=\beta=1$ PROILLYUSTRIROVANA V KACHESTVE PRIMERA V TABL.~1. kOMPAKTNYE OPISANIYA SOOTVETSTVUYUSHCHIH OPTIMALXNYH DEREVXEV IMEYUTSYA V PRAVOJ CHASTI TABLICY; |LEMENT "4:9:9" DLYA $n=22$, NAPRIMER, OZNACHAET, CHTO OPTIMALXNOE DEREVO $\cJ_22$ S 22 LISTXYAMI MOZHNO POLUCHITX V REZULXTATE OB®EDINENIYA $\cJ_4$, $\cJ_9$ I~$\cJ_9$ (RIS.~93). oPTIMALXNYE DEREVXYA NE EDINSTVENNY; NAPRIMER, |LEMENT 5:8:9 BYL BY STOLX ZHE HOROSHIM, KAK I 4:9:9. %% 438 \bye