В.Б. Алекссев - Сложные алгоритмы (1132790), страница 6
Текст из файла (страница 6)
pRI WEKTORNOM PREDSTAWLENII FUNKCIJ DLQRASPOZNAWNIQ SWOJSTWA "f (x1; : : : ; xn) 2 S ?" SU]ESTWUET ALGORITMsf| SO SLOVNOSTX@ O(N ) GDE N = 2n DLINA WHODAdOKAZATELXSTWO pO OPREDELENI@ SAMODWOJSTWENNYH FUNKCIJf (x1; : : : ; xn) 2 S TOGDA I TOLXKO TOGDA, KOGDA DLQ L@BOGO ~ =(1; : : : ; n ) WYPOLNQETSQ f (1; : : : ; n) = f (1; : : : ; n ), TO ESTX KOGDADLQ WSEH i = 0; 1; : : : ; 2n;1 ; 1 WYPOLNQETSQ ai = ai+2n;1 . tAKIM OBRAZOM,()1.()0.(),|.27.DLQ RASPOZNAWANIQ SWOJSTWA "f 2 S ?" DOSTATO^NO ISPOLXZOWATX 2n;1BULEWYH OPERACIJ ai ai+2n;1 I ZATEM WZQTX KON_@NKCI@ POLU^ENNYHZNA^ENIJ.
oB]EE ^ISLO BITOWYH OPERACIJ BUDET 2n;1 +2n;1 ; 1 = N ; 1.uTWERVDENIE 4. pRI WEKTORNOM PREDSTAWLENII FUNKCIJ DLQRASPOZNAWANIQ SWOJSTWA "f (x1; : : : ; xn) 2 L?" SU]ESTWUET ALGORITMsf| SO SLOVNOSTX@ O(N ) GDE N = 2n DLINA WHODA()lEMMA.,|.(f (x1; : : : ; xn) 2 L () f (0; x2; : : : ; xn ) 2 L;f (1; x2; : : : ; xn ) f (0; x2 ; : : : ; xn ) c; c 2 f0; 1g:dOKAZATELXSTWO eSLI f (x1; : : : ; xn ) = a1x1 a2x2 : : : anxn + a0;TO, O^EWIDNO, f (0; x2; : : : ; xn ) 2 L I f (1; x2; : : : ; xn) f (0; x2 ; : : : ; xn) a1: dLQ DOKAZATELXSTWA OBRATNOGO PEREHODA ZAMETIM, ^TO DLQ L@BOJBULEWOJ FUNKCII SPRAWEDLIWO PREDSTAWLENIEf (x1 ; : : : ; xn ) = x1 f (0; x2; : : : ; xn) x1 f (1; x2; : : : ; xn ) =(x1 1) f (0; x2 ; : : : ; xn) f (1; x2 ; : : : ; xn) = x1 (f (0; x2; : : : ; xn ) f (1; x2; : : : ; xn )) f (0; x2; : : : ; xn ).
pO\TOMU, ESLI f (1; x2; : : : ; xn ) f (0; x2; : : : ; xn ) c, TO ESTX f (0; x2; : : : ; xn) f (1; x2; : : : ; xn ) c, If (0; x2; : : : ; xn ) 2 L, TO I f (x1; x2; : : : ; xn) 2 L:lEMMA DOKAZANA.bUDEM STROITX ALGORITM (sf|) DLQ RASPOZNAWANIQ SWOJSTWA"f (x1; : : : ; xn) 2 L?" REKURSIWNO W SOOTWETSTWII S LEMMOJ. dLQ PROWERKI USLOWIQ f (1; x2 ; : : : ; xn) f (0; x2 ; : : : ; xn ) DOSTATO^NO 2n ; 1 BINARNYH BITOWYH OPERACIJ (2n;1 SRAWNENIJ i = i+2n;1 I 2n;1 ; 1 KON_@NKCIJ POLU^ENNYH ZNA^ENIJ). aNALOGI^NO 2n ; 1 BINARNYH OPERACIJDOSTATO^NO DLQ PROWERKI USLOWIQ f (1; x2; : : : ; xn ) f (0; x2 ; : : : ; xn) 1:dLQ PROWERKI USLOWIQ f (1; x2; : : : ; xn ) = f (0; x2 ; : : : ; xn) c DOSTATO^NOWZQTX DIZ_@NKCI@ DWUH POLU^ENNYH REZULXTATOW SRAWNENIJ.
pRI \TOMOB]EE ^ISLO BITOWYH OPERACIJ 2(2n ; 1) < 2n+1 . pUSTX L(n) | MINIMALXNOE ^ISLO BITOWYH OPERACIJ DLQ OTWETA NA WOPROS "f (x1; : : : ; xn) 2L?" tOGDA L(1) = 1 (T.K. WYHOD z 1) I W SOOTWETSTWII S LEMMOJL(n) < L(n ; 1)+2n+1 < L(n ; 2)+2n +2n+1 < L(n ; 3)+2n;1 +2n +2n+1 <: : : < L(1) + 23 + 24 + : : : + 2n+1 < 2n+2 = 4N . tEOREMA DOKAZANA.uTWERVDENIE 5. pRI WEKTORNOM PREDSTAWLENII FUNKCIJ DLQRASPOZNAWNIQ SWOJSTWA "f (x1; : : : ; xn) 2 M ?" SU]ESTWUET ALGORITMsf| SO SLOVNOSTX@ O(N log N ) GDE N = 2n DLINA WHODAdOKAZATELXSTWO iZWESTNO, ^TO f (x1; : : : ; xn ) 2 M TOGDA I TOLXKO TOGDA, KOGDA DLQ L@BYH DWUH NABOROW ~ I ~ TAKIH, ^TO ~ =(1; : : : ; i;1 ; 0; i+1 ; : : : ; n ) I ~ = (1; : : : ; i;1 ; 0; i+1 ; : : : ; n ) (GDE.(),.28|.i | L@BOE), WYPOLNQETSQ f (~) 6 f (~): ~ISLO UKAZANNYH PAR NABOROW (~; ~) RAWNO n 2n;1 .
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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
