В.Б. Алексеев - Электронный коспект лекций, страница 6
Описание файла
PDF-файл из архива "В.Б. Алексеев - Электронный коспект лекций", который расположен в категории "". Всё это находится в предмете "сложность алгоритмов" из 7 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 6 страницы из PDF
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.
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.