Алексеев - Сложность алгоритмов (1123759), страница 6
Текст из файла (страница 6)
dLQ L@BOGO FIKSIROWANNOGO m > 2 SU]ESTWUET ALGORITM DLQ OTWETA NA WOPROS "f (x1 : : : xn ) 2 U (Rm)?" S BITOWOJSLOVNOSTX@ O(N log3 N ):zAME^ANIE. kONSTANTA ZAWISIT OT m (RASTET S ROSTOM m).dOKAZATELXSTWO pUSTX ~1; ~2; : : : ; ~m | PROIZWOLXNYE NABORY,GDE ~j = (j1; j2 ; : : : ; jn ): tOGDA PO OPREDELENI@f (x1; : : : ; xm ) 2= Fm ()() 9~1 ; : : : ; ~m (Rnm(~1; : : : ; ~m )&(f (~1) = 1)& : : : &(f (~m) = 1)) ()_()Rnm(~1; : : : ; ~m )x~1 : : : x~m =-.~ 1;:::;~m32=_~1 ;:::;~mRm(11 : : : m1 ) Rm(12 : : : m2 ) : : : Rm(1n : : : mn )x~1 : : : x~m ;GDE x~ (f (~) = 1), T.E. x~ | SOOTWETSWU@]AQ KOORDINATA W WEKTOREFUNKCII. oPREDELIM FUNKCI@ tm (1; : : : ; m ), GDE j 2 f0; 1g, SLEDU@]IM OBRAZOM:(tm(1; : : : ; m ) = 0; ESLI Rm(1; : : : ; m);(11)1; ESLI Rm(1; : : : ; m):lEGKO WIDETX, ^TO_Rm(11; : : : ; m1 ) : : : Rm(1n; : : : ; mn )x~1 : : : x~m = i ()~ 1;:::;~mTn =X~ 1;:::;~mtm(11 ; : : : ; m1 ) : : : tm(1n; : : : ; mn )x~1 : : : x~m > 0:pUSTX L0ap(n) = Lap(N ) |NAIMENX[EE ^ISLO ARIFMETI^ESKIH OPERACIJ, NEOBHODIMYH DLQ WY^ISLENIQ Tn.
oBOZNA^IM ~j =(j1; j2; : : : ; jn;1); j = jn. tOGDAXXTn =tm (11; : : : ; m1 ) : : : tm(1n; : : : ; mn ) x~1 ;1 : : : x~m ;m =~1 ;:::;~m 1 ;:::;m=X~1 ;:::;~m==X~1 ;:::;~mtnm;1(~1; : : : ; ~m )XX(1;:::;m )2E2mtnm;1(~1; : : : ; ~m)~1 ;:::;~mtnm;1 (~1; : : :GDEX(1 ;:::;m )6=(1;:::;1)x~1;1 : : : x~m ;m =; ~m )((x~1;0 + x~1;1)(x~2;0 + x~2;1) : : : (x~m ;0 + x~m ;1);;x~1 ;1x~2;1 : : : x~m ;1) =;tm (1; : : : ; m )x~1;1 : : : x~m ;m =XX~1 ;:::;~mtnm;1(~1; : : : ; ~m )y~1 y~2 : : : y~m ;tnm;1(~1; : : : ; ~m)z~1 z~2 : : : z~m ;~1 ;:::;~my~ = x~;0 + x;1~ ; A z~ = x~;1sWELI ZADA^U S PARAMETROM n K 2 PODZADA^AM S PARAMETROM n ; 1.oTS@DA L0AR(n) 6 2L0AR(n ; 1) + 2n;1 + 1, POSKOLXKU DLQ WY^ISLENIQWSEH y~ DOSTATO^NO 2n;1 SLOVENIJ I ODNOGO WY^ITANIQ DOSTATO^NO DLQWY^ISLENIQ Tn POSLE RE[ENIQ DWUH PODZADA^.
pEREHODQ K N , IMEEML0ap(N ) = 2Lap( N2 )+ O(N ). oTS@DA PO TEOREME O REKURRENTNOM NERAWENSTWE POLU^AEM Lap(N ) = O(N log N ) (W \TOJ TEOREME IMEEM a = 2; c =332; = 1). oTMETIM, ^TO ISHODNAQ ZADA^A BYLA DLQ x~ 2 f0; 1g. oDNAKOW PODZADA^AH PEREMENNYE MOGUT BYTX PROIZWOLXNYMI NATURALXNYMI^ISLAMI. pEREHOD K PODZADA^AM DELAETSQ n ; 1 RAZ. pRI KAVDOM PEREHODE RAZRQDNOSTX PEREMENNYH UWELI^IWAETSQ NE BOLEE, ^EM NA 1, PO\TOMUW PODZADA^AH WSE ^ISLA IME@T DLINU NE BOLEE n + 1. pRI n = 0 POLU^A@TSQ PODZADA^I WY^ISLENIQ T0 WIDA T0 = z z z z : : : z = z m , W KOTORYHOBRAZU@TSQ ^ISLA DLINY 6 m(n +1). pRI PEREHODE K ZADA^E IZ PODZADA^DLINA ^ISEL UWELI^IWAETSQ NE BOLEE, ^EM NA 1, PO\TOMU WSE ^ISLA WALGORITME IME@T DLINU NE BOLEE m(n+1)+n 6 constn: sLEDOWATELXNO,KAVDAQ ARIFMETI^ESKAQ OPERACIQ TREBUET O(n2) = O(log2 N ) BITOWYHOPERACIJ, OTKUDA L(N ) = Lap(N ) O(log2 N ) = O(N log3 N ), ^.T.D.34mA[INY tX@RINGAw RASSMOTRENNYH WY[E PRIMERAH KLASS ALGORITMOW BYL OGRANI^EN.
tAK, W ZADA^AH SORTIROWKI I POISKA MY NE OBSUVDALI SPOSOBPREDSTAWLENIQ \LEMENTOW ai I NE RAZRE[ALI IZU^ATX I PREOBRAZOWYWATX OTDELXNYE ^ASTI \TIH PREDSTAWLENIJ. eSLI MY HOTIM POLU^ATXUTWERVDENIQ TIPA "DLQ L@BYH ALGORITMOW" WOOB]E, TO MY DOLVNYPRINQTX KAKU@-NIBUDX UNIWERSALXNU@ MODELX ALGORITMOW. oDNOJ IZTAKIH MODELEJ QWLQETSQ MA[INA tX@RINGAmA[INA tX@RINGA M IMEET POTENCIALXNO BESKONE^NU@ LENTU,RAZDELENNU@ NA Q^EJKI, I GOLOWKU, KOTORAQ W KAVDYJ (DISKRETNYJ)MOMENT WREMENI t = 0; 1; 2; : : : OBOZREWAET ROWNO ODNU Q^EJKU.
zADANONEKOTOROE KONE^NOE MNOVESTWO SOSTOQNIJ Q = fq0; q1; : : : ; ql g, I MA[INAW KAVDYJ MOMENT WREMENI NAHODITSQ ROWNO W 1 IZ \TIH SOSTOQNIJ.zADAN KONE^NYJ LENTO^NYJ (RABO^IJ) ALFAWIT C = fc0; c1; : : : ; cm g, GDEc0 = | PUSTOJ SIMWOL, I W KAVDYJ MOMENT WREMENI W KAVDOJ Q^EJKENAHODITSQ ROWNO 1 SIMWOL IZ ALFAWITA C , PRI^EM BUDEM S^ITATX, ^TOSIMWOLY, OTLI^NYE OT , NAHODQTSQ LI[X W KONE^NOM ^ISLE Q^EEK. mA[INA M HARAKTERIZUETSQ EE PROGRAMMOJ, KOTORAQ PREDSTAWLQET SOBOJKONE^NYJ NABOR KOMAND WIDA: ciqj ! ck qr T , GDE ci 2 C , ck 2 C , qj 2 Q,qr 2 Q, T 2 L; R; S .
nA KAVDOM TAKTE MA[INA M RABOTAET SLEDU@]IMOBRAZOM. eSLI GOLOWKA OBOZREWAET Q^EJKU, W KOTOROJ NAHODITSQ SIMWOLcj , M NAHODITSQ W SOSTOQNII qj I W PROGRAMME MA[INY M ESTX KOMANDAciqj ! ck qr T , TO SIMWOL W OBOZREWAEMOJ Q^EJKE ZAMENQETSQ NA ck ,MA[INA PEREHODIT W SOSTOQNIE qr I GOLOWKA OSTAETSQ NA MESTE, ESLIT = S , ILI SDWIGAETSQ NA 1 Q^EJKU WPRAWO ILI WLEWO, ESLI T = R ILIT = L. dALEE MA[INA PEREHODIT K SLEDU@]EMU TAKTU I POWTORQET \TOTPROCESS. eSLI VE W PROGRAMME MA[INY NET KOMANDY, W LEWOJ ^ASTIKOTOROJ STOIT PARA ciqj , TO MA[INA OSTANAWLIWAETSQ.mY BUDEM RASSMATRIWATX TOLXKO DETERMINIROWANNYE MA[INYtX@RINGA, TO ESTX TAKIE, U KOTORYH W PROGRAMME KAVDAQ PARA ci qjWSTRE^AETSQ W LEWYH ^ASTQH KOMAND NE BOLEE ODNOGO RAZA. w \TOM SLU^AEKAVDYJ [AG MA[INY OPREDELQETSQ ODNOZNA^NO.oPREDELENIE.
eSLI A - ALFAWIT, TO ^EREZ A BUDEM OBOZNA^ATXMNOVESTWO WSEH (KONE^NYH) SLOW W ALFAWITE A. pUSTX C - LENTO^NYJALFAWIT MA[INY M , C0 = C n fg I PUSTX ZADAN NEKOTORYJ WHODNOJ ALFAWIT A, TAKOJ, ^TO A C0. tOGDA MY BUDEM S^ITATX, ^TOMA[INA M OSU]ESTWLQET PREOBRAZOWANIE 'M : A ! C0 [ fg, KOTOROE OPREDELQETSQ SLEDU@]IM OBRAZOM (ZDESX W fg TRAKTUETSQ KAKNEOPREDELENNOSTX). pUSTX ZADANO NEKOTOROE SLOWO a = a1a2 : : : an 2 A..35rAZMESTIM SIMWOLY \TOGO SLOWA W POSLEDOWATELXNYE Q^EJKI LENTY, A WOSTALXNYE Q^EJKI POMESTIM , POMESTIM GOLOWKU NA Q^EJKU, W KOTOROJSTOIT a1, USTANOWIM MA[INU W NA^ALXNOE SOSTOQNIE q1 I NA^NEM RABOTUMA[INY. eSLI POSLE \TOGO MA[INA M BUDET RABOTATX BESKONE^NO DOLGO, TO S^ITAEM, ^TO 'M (a1a2 : : : an) = . eSLI MA[INA M OSTANOWITSQI GOLOWKA BUDET OBOZREWATX , TO TAKVE S^ITAEM, ^TO 'M (a) = .eSLI VE M OSTANOWITSQ I OBOZREWAEMYJ SIMWOL OTLI^EN OT , TORASSMOTRIM MAKSIMALXNU@ SWQZNU@ (SOSTOQ]U@ IZ POSLEDOWATELXNYHQ^EEK) OBLASTX LENTY, KOTORAQ SODERVIT OBOZREWAEMU@ Q^EJKU I NESODERVIT .
pUSTX W Q^EJKAH \TOJ OBLASTI ZAPISANO SLOWO b = b1b2 : : : bk(\TA OBLASTX, O^EWIDNO, KONE^NA). tOGDA S^ITAEM, ^TO 'M (a) = b.tEZIStX@RINGA. dLQ L@BOGO ALGORITMI^ESKOGO PREOBRAZOWANIQ ' : A ! C0 [ fg SU]ESTWUET MA[INA tX@RINGA M OSU]ESTWLQ@]AQ PREOBRAZOWANIE 'rASPOZNAWANIE SIMMETRIIpUSTX A = f0; 1g I SLOWO a = a1a2 : : : an 2 A.
bUDEM GOWORITX,^TO SLOWO a SIMMETRI^NO, ESLI a1 = an; a2 = an;1 I T.D. pUSTX MA[INAtX@RINGA M IMEET LENTO^NYJ ALFAWIT C I MNOVESTWO SOSTOQNIJ Q,PRI^EM A C I q0 2 Q, q00 2 Q. bUDEM GOWORITX, ^TO M RASPOZNAETSIMMETRI@, ESLI DLQ L@BOGO WHODNOGO SLOWA a 2 A MA[INA M WSEGDAOSTANAWLIWAETSQ I PRI \TOM NAHODITSQ W SOSTOQNII q0 , ESLI a SIMMETRI^NO, ILI q00, ESLI a NE SIMMETRI^NO.uTWERVDENIE. sU]ESTWUET MA[INA tX@RINGA M KOTORAQRASPOZNAET SIMMETRI@ I DELAET PRI L@BOM WHODNOM SLOWE DLINY nNE BOLEE cn2 [AGOW GDE c NEKOTORAQ KONSTANTAdOKAZATELXSTWO dOSTATO^NO POSTROITX MA[INU M , KOTORAQ ZAPOMINAET I STIRAET PERWYJ SIMWOL, PEREGONQET GOLOWKU W KONEC SLOWAI SRAWNIWAET SIMWOL W PAMQTI S POSLEDNIM SIMWOLOM SLOWA.
eSLIONI NE SOWPADA@T, TO M PEREHODIT W SOSTOQNIE q00 I OSTANAWLIWAETSQ.eSLI SOWPADA@T, TO ONA STIRAET POSLEDNIJ SIMWOL, WOZWRA]AETSQ WNA^ALO SLOWA I POWTORQET PROCESS. eSLI SLOWO POLNOSTX@ STERTO, TOM PEREHODIT W SOSTOQNIE q0 I OSTANAWLIWAETSQ. pRI \TOM GOLOWKA NEBOLEE n RAZ PROBEGAET PO SLOWU DLINY NE BOLEE n.
pO\TOMU OB]EE ^ISLO[AGOW ESTX O(n2).-,-.,,-..36oB]IE UTWERVDENIQ O SLOVNOSTI ZADA^rASSMOTRIM WSE MA[INY tX@RINGA, IME@]IE W LENTO^NOM ALFAWITE SIMWOLY I j. pUSTX Z + = f0g[ N , GDE N - MNOVESTWO NATURALXNYH ^ISEL. bUDEM PREDSTAWLQTX ^ISLO k 2 Z + NA LENTE MA[INY W WIDEKODA jj : : : j , GDE KOLI^ESTWO j RAWNO k + 1 (OSTALXNYE SIMWOLYNA LENTE ). nABOR (k1; k2; : : : ; kn ) BUDEM PREDSTAWLQTX W WIDE KODA jj : : : j jj : : : j : : : jj : : : j ,GDE W PERWOM MASSIWE k1 +1 SIMWOLOW j,WO WTOROM k2 + 1 I T.D. pRIMENQQ MA[INU M K KODU ^ISLA ILI NABORA,BUDEM POME]ATX GOLOWKU NA SAMYJ PERWYJ SIMWOL j I USTANAWLIWATXMA[INU M W EE NA^ALXNOE SOSTOQNIE q1.oPREDELENIE.
dLQ L@BOJ MA[INY tX@RINGA M I L@BOGO NATURALXNOGO ^ISLA n BUDEM S^ITATX, ^TO MA[INA M WY^ISLQET FUNKCI@f (x1; x2; : : : ; xn) : (Z + )n ! Z + [ fg KOTORAQ OPREDELQETSQ SLEDU@]IMOBRAZOM. pRIMENIM MA[INU M K KODU NABORA (a1; a2; : : : ; an). eSLI MOSTANOWITSQ I POSLE OSTANOWKI NA LENTE BUDET TOLXKO KOD NEKOTOROGO^ISLA b 2 Z + , TO f (a1; a2; : : : ; an) = b. wO WSEH OSTALXNYH SLU^AQHf (a1; a2; : : : ; an) = (NEOPREDELENNOSTX).oPREDELENIE.
fUNKCIQ f (x1; x2; : : : ; xn) : (Z +)n ! Z + [ fg NAZYWAETSQ WY^ISLIMOJ, ESLI SU]ESTWUET MA[INA tX@RINGA M , KOTORAQEE WY^ISLQET.oPREDELENIE. gOWORQT, ^TO MA[INA M PRAWILXNO WY^ISLQET FUNKCI@ f (x1; x2; : : : ; xn), ESLI NA^INAQ RABOTU S KODA NABORA(a1; : : : ; an) MA[INA M W TOM SLU^AE, KOGDA f (a1; a2; : : : ; an) NE OPREDELENO, OBQZATELXNO RABOTAET BESKONE^NO DOLGO, A W TOM SLU^AE, KOGDAf (a1; a2; : : : ; an) = b, MA[INA OSTANAWLIWAETSQ, NA LENTE OSTAETSQ KOD bI GOLOWKA MA[INY OBOZREWAET SAMYJ LEWYJ SIMWOL j.uTWERVDENIE. eSLI f (x1; x2; : : : ; xn) WY^ISLIMA TO SU]ESTWUET MA[INA tX@RINGA M KOTORAQ EE WY^ISLQET PRAWILXNOdOKAZATELXSTWO SM., NAPRIMER, W [ ].oPREDELENIE. wS@DU OPREDELENNYE WY^ISLIMYE FUNKCII MYBUDEM NAZYWATX OB]EREKURSIWNYMI FUNKCIQMI.
(oBY^NO OB]EREKURSIWNYE FUNKCII OPREDELQ@T INA^E, NO DANNOE OPREDELENIE \KWIWALENTNO OBY^NOMU; SM., NAPRIMER, [ ]).fUNKCIQ, WY^ISLQEMAQ MA[INOJ M , NE IZMENITSQ, ESLI PROIZWOLXNO PEREIMENOWATX WSE SIMWOLY LENTO^NOGO ALFAWITA, KROME Ij, I WSE SOSTOQNIQ, OSTAWLQQ NA^ALXNOE SOSTOQNIE NA^ALXNYM (KONE^NO, RAZNYE SIMWOLY DOLVNY PEREIMENOWYWATXSQ W RAZNYE).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
