PDF-лекции (1121253), страница 6
Текст из файла (страница 6)
tAKIM OBRAZOM, DLQ RASPOZNAWANIQ SWOJSTWA"f 2 M ?" DOSTATO^NO ISPOLXZOWATX n 2n;1 BITOWYH OPERACIJ "x 6 y" IZATEM WZQTX KON_@NKCI@ POLU^ENNYH ZNA^ENIJ. oB]EE ^ISLO BITOWYHOPERACIJ BUDET n 2n;1 + n 2n;1 ; 1 = N log2 N ; 1.iZ UTWERVDENIJ 1-5 I TEOREMY pOSTA O POLNOTE POLU^AEM SLEDU@]EE UTWERVDENIE.tEOREMA. pRI WEKTORNOM PREDSTAWLENII FUNKCIJ DLQ RASPOZNAWNIQ POLNOTY SISTEMY FUNKCIJ SU]ESTWUET ALGORITM sf| SOSLOVNOSTX@ O(N log N ) GDE N DLINA WHODAzAME^ANIE.
wORONENKOa. a. [] NA[EL BOLEE BYSTRYJ ALGORITMpSO SLOVNOSTX@ O(N log N log log N ) DLQ RASPOZNAWANIQ SWOJSTWA MONOTONNOSTI (KLASS M ), OTKUDASLEDUET, ^TO I W TEOREME OCENKU O(N log N )pMOVNO PONIZITX DO O(N log N log log N ).-(,|29.)rASPOZNAWANIE SOHRANENIQ 2-H MESTNYHPREDIKATOW.pUSTX Ek = f0; 1; : : : ; k ; 1g. ~EREZ Pk BUDEM OBOZNA^ATX MNOVESTWO WSEH k-ZNA^NYH FUNKCIJ, TO ESTX FUNKCIJ, OTOBRAVA@]IH Ekn W EkPRI WSEH n.oPREDELENIE. pREDIKATOM (m-MESTNYM)mNA KONE^NOM MNOVESTWE D NAZYWAETSQ L@BAQ FUNKCIQ R(y1 : : : ym) : D ;! fISTINA, LOVXg:oPREDELENIE.
pUSTX f (x1 : : : xn) 2 Pk I R(y1; y2) | 2-MESTNYJPREDIKAT NA MNOVESTWE Ek . bUDEM GOWORITX, ^TO f (x1 : : : xn) SOHRANQETPREDIKAT R, ESLI DLQ L@BYH NABOROW ~ = (1 : : : n ) I ~ = (1 : : : n)WYPOLNQETSQ IMPLIKACIQ:(8jR(j ; j )) ! R(f (~); f (~)):oBOZNA^IM U (R) | KLASS WSEH FUNKCIJ,SOHRANQ@]IH PREDIKAT R.pUSTX ~ = (1; : : : ; n), ~ = (1; : : : ; n ) | NABORY S \LEMENTAMI IZD I R | 2-MESTNYJ PREDIKAT NA D. tOGDA OPREDELIM PREDIKAT Rn NADn SLEDU@]IM OBRAZOM:Rn(~; ~) 8jR(j ; j ):eSLI ~ = (1; : : : ; n;1 ), ~ = (1; : : : ; n;1 ), TO LEGKO WIDETX, ^TORn(~; ~) Rn;1(~ ; ~)&R(n; n):zADA^A. fIKSIRUEM Ek.
zADAN PREDIKAT R(y1; y2) NA Ek. tREBUETSQ POSTROITX ALGORITM (sf|) DLQ OTWETA NA WOPROS "f (x1 : : : xn ) 2U (R)?". pRI \TOM S^ITAETSQ, ^TO NABORY IZ Ekn UPORQDO^IWA@TSQ LEKSIKOGRAFI^ESKI I FUNKCIQ f ZADAETSQ WEKTOROM f = (0; 1; : : : ; kn;1)EE ZNA^ENIJ NA \TIH NABORAH; N = kn | DLINA WHODA.tRIWIALXNYJ ALGORITM DLQ \TOJ ZADA^I IMEET SLOVNOSTX O(N 2)(PROWERKA PAR). eSLI PREDIKAT R ISTINEN NA d PARAH, TO SU]ESTWUETALGORITM SO SLOVNOSTX@ O(dn) = O(N logk d).
oDNAKO WEREN SLEDU@]IJBOLEE SILXNYJ REZULXTAT.tEOREMA. dLQ L@BOGO PREDIKATA R(y1; y2) NA Ek SU]ESTWUET ALGORITM sf| RASPOZNA@]IJ "f (x1 : : : xn ) 2 U (R)?" SO SLOVNOSTX@O(N log N ) GDE N = kn DLINA WHODAdOKAZATELXSTWOf (x1 : : : xn) 2= U (R) () 9~ ; ~(Rn(~; ~)&R (f (); f ( ))) ()_() (Rn(~; ~)&R (f (~); f (~))) ()-(),,|..~ ;~30()__(Rn(~; ~)&(f (~) = c)&(f (~) = d)&R (c; d)) =c;d2Ek ~;~=__(c;d):R(c;d)(~;~)(Rn(~; ~)&(f (~) = c)&(f (~) = d)):pRI FIKSIROWANNYH c, d WY^ISLENIE LOGI^ESKIH PEREMENNYH x~ (f (~) = c) I y~ (f (~) = d) TREBUET O(N ) OPERACIJ.pUSTX L(N ) W= L0 (n) | MINIMALXNAQ BITOWAQ SLOVNOcTX WY^ISLENIQ WYRAVENIQ ~;~ Rn(~; ~)x~ y~ PRI ZADANNYH x~ ; y~: dOKAVEM, ^TOL(N ) = O(N log N ):pUSTX ~ = (~ ; n ); ~ = (~; n). tOGDA__Rn(~; ~)x~ y~ =Rn;1(~ ; ~)R(n; n )x~;ny~;n =~;~~=(~ ;n);~=(~;n )=_ _Rn;1(~ ; ~)R(n; n)x(~ ;n)y(~;n) =~;~ n;n_= Rn;1(~ ; ~)~;~=_~ ;~_n;nR(n; n)x(~ ;n)y(~;n) =_Rn;1(~ ; ~) x(~ ;n)n=_ __n :R(n;n)y(~;n) =( Rn;1 (~ ; ~)x(~ ;n)z(~;n));n ~;~GDE z(~;n) = n:R(n;n) y(~;n):oTS@DA L0(n) 6 kL0 (n ; 1)+ kn (k ; 1)+ k ; 1, POSKOLXKU ZADA^A DLQn SWODITSQ K k TAKIM VE ZADA^AM DLQ n ; 1, PRI \TOM DLQ WY^ISLENIQKAVDOJ IZ kn PEREMENNYH z TREBUETSQ NE BOLEE k ;1 DIZ_@NKCIJ I POSLERE[ENIQ WSEH k PODZADA^ TREBUETSQ k ; 1 DIZ_@NKCIJ DLQ WY^ISLENIQDIZ_@NKCII PO n .
pEREHODQ K L(N ), POLU^AEM L(N ) 6 kL( Nk ) + O(N ),OTKUDA, PO TEOREME O REKURRENTNOM NERAWENSTWE, L(N ) = O(N log N ).tEOREMA DOKAZANA.W31kLASSY F m.pUSTX TEPERX R(y1; : : : ; ym ) | m-MESTNYJ PREDIKAT NA MNOVESTWEEk = f0; 1; : : : ; k ; 1g: eSLI ~ j = (j1; j2; : : : ; jn); j = 1; 2; : : : ; m |NABORY S \LEMENTAMI IZ Ek , TO OPREDELIMRn(~1; ~2; : : : ; ~m ) 8iR(1i ; 2i ; : : : ; mi ):oPREDELENIE. bUDEM GOWORITX, ^TO FUNKCIQ f (x1; : : : ; xn) IZ PkSOHRANQET R, ESLI DLQ L@BYH m NABOROW ~1; ~2; : : : ; ~m WYPOLNQETSQIMPLIKACIQRn(~1; ~2; : : : ; ~m ) =) R(f (~1); f (~2); : : : ; f (~m )):rASSMOTRIM SLEDU@]IJ PREDIKAT F m NA E2 = f0; 1g:(Rm(y1; : : : ; ym ) = ISTINA () 9i(yi = 0);(10)LOVX () y~ = (1; : : : ; 1):kLASS WSEH FUNKCIJ ALGEBRY LOGIKI, SOHRANQ@]IH PREDIKAT Rm,OBOZNA^IM F m . kLASSY F m PRI m = 2; 3; 4; : : : OBRAZU@T ODNU IZ 8BESKONE^NYH CEPO^EK ZAMKNUTYH KLASSOW W ALGEBRE LOGIKI.
rASSMOTRIMSLEDU@]U@ ZADA^U.zADA^A. pUSTX m > 2 | FIKSIROWANNOE NATURALXNOE ^ISLO. tREBUETSQ POSTROITX ALGORITM DLQ OTWETA NA WOPROS "f (x1; : : : ; xn) 2 F m ?"PRI USLOWII, ^TO FUNKCIQ POSTUPAET NA WHOD W WIDE WEKTORA ZNA^ENIJf (x1; : : : ; xn) = (a0; a1; : : : ; a2n;1) DLINY N = 2n:zAMETIM, ^TO TRIWIALXNYJ ALGORITM, OSNOWANNYJ NA PROSMOTREWSEH WYBOROK PO m ZNA^ENIJ FUNKCII I PROWERKE IMPLIKACII ( )TREBUET PO PORQDKU NE MENEE N m OPERACIJ.tEOREMA. 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).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
