В.Б. Алексеев - Электронный коспект лекций (1158874), страница 5
Текст из файла (страница 5)
oVIDAETSQ, ^TO DLQ UMNOVENIQ MATRIC PORQDKA nSU]ESTWUET ALGORITM S ^ISLOM ARIFMETI^ESKIH OPERACIJ O(n2+") DLQL@BOGO FIKSIROWANNOGO " > 0 (SRAWNITE S ALGORITMOM tOOMA), ODNAKOPOKA (SEREDINA 2001 GODA) NAILU^[EJ OCENKOJ QWLQETSQ O(n2:38) [ ].23aLGORITMY UMNOVENIQ 0-1-MATRICpUSTX MATRICY A I B SOSTOQT TOLXKO IZ 0 I 1 I TREBUETSQWY^ISLITX C = A B; GDE WSE \LEMENTY crs DOLVNY BYTX PREDSTAWLENYW DWOI^NOJ SISTEME. w KA^ESTWE OPERACIJ RAZRE[IM TOLXKO L@BYEBITOWYE OPERACII NAD DWUMQ PEREMENNYMI.tEOREMA. dLQ WY^ISLENIQ OBY^NOGO PROIZWEDENIQ DWUHMATRIC PORQDKA n SU]ESTWUET ALGORITM S ^ISLOM BITOWYH OPERACIJ O(nlog2 7 log2 n):lEMMA.
eSLI W ISHODNYH MATRICAH A I B PORQDKA n WSE \LEMENTY IME@T DWOI^NU@ DLINU NE BOLEE k WKL@^AQ ZNAK TO W ALGORITME {TRASSENA DLQ WY^ISLENIQ AB WSE WOZNIKA@]IE ^ISLA IME@TDWOI^NU@ DLINU NE BOLEE 2k + 4dlog2 ne:dOKAZATELXSTWO LEMMY pRI FORMIROWANII PODZADA^ WY^ISLENIQ D1 ; D7 W ALGORITME {TRASSENA PROISHODIT SLOVENIE (ILI WY^ITANIE) NE BOLEE ^EM DWUH MATRIC. pO\TOMU MODULI WSEH ^ISEL NEBOLEE ^EM UDWAIWA@TSQ, TO ESTX DOBAWLQETSQ NE BOLEE ODNOGO RAZRQDA.pRI PEREHODE OT RAZMERNOSTI n K RAZMERNOSTI 1 PODZADA^I FORMIRU@TSQ dlog2 ne RAZ. sLEDOWATELXNO, W PODZADA^AH RAZMERNOSTI 1 WSE^ISLA IME@T DLINU NE BOLEE k + dlog2 ne: dLQ PODZADA^ RAZMERNOSTI 1ALGORITM {TRASSENA PROIZWODIT OBY^NOE UMNOVENIE.
pRI \TOM DLINAPOLU^A@]IHSQ ^ISEL NE PREWOSHODIT 2k +2dlog2 ne: pRI WY^ISLENII CrsPO REZULXTATAM PODZADA^ D1 ; D7 SKLADYWA@TSQ (WY^ITA@TSQ) NE BOLEE^EM PO 4 MATRICY. pRI \TOM MAKSIMALXNYE MODULI ^ISEL WOZRASTA@TNE BOLEE ^EM W 4 RAZA, TO ESTX DOBAWLQETSQ NE BOLEE ^EM PO 2 RAZRQDA.pOSKOLXKU OBRATNYH [AGOW TAKVE dlog2 ne; TO WSE POLU^AEMYE ^ISLAIME@T DLINU NE BOLEE 2k + 2dlog2 ne + 2dlog2 ne = 2k + 4dlog2 ne: lEMMADOKAZANA.dOKAZATELXSTWO TEOREMY pRIMENIM DLQ WY^ISLENIQ AB ALGORITM {TRASSENA.
pO USLOWI@ W ISHODNYH MATRICAH A I B WSE \LEMENTYIME@T DLINU 2 (WKL@^AQ ZNAK). tOGDA PO LEMME WSE WOZNIKA@]IE WALGORITME ^ISLA BUDUT IMETX DLINU NE BOLEE 4 + 4dlog2 ne = O(log n):tAK KAK W ALGORITME {TRASSENA ISPOLXZU@TSQ TOLXKO SLOVENIE, WY^ITANIE I UMNOVENIE, TO L@BAQ ARIFMETI^ESKAQ OPERACIQ W ALGORITME{TRASSENA TREBUET O(log2 n) BITOWYH OPERACIJ.
pOSKOLXKU ALGORITM{TRASSENA ISPOLXZUET O(nlog2 7) ARIFMETI^ESKIH OPERACIJ, TO WSE ONIPOTREBU@T O(nlog2 7 log2 n) BITOWYH OPERACIJ. tEOREMA DOKAZANA.zAME^ANIE 1. oCENKU MOVNO ULU^[ITX, ESLI ISPOLXZOWATX BYSTRYE ALGORITMY DLQ UMNOVENIQ ^ISEL.zAME^ANIE 2. w \TOJ TEOREME MOVNO POLU^ITX OCENKU O(n2:38);()0-1---(..24),-ESLI ISPOLXZOWATX IZWESTNYJ BOLEE BYSTRYJ ALGORITM UMNOVENIQ MATRIC.rASSMOTRIM TEPERX OPERACI@ BULEWSKOGO UMNOVENIQ 0-1-MATRIC.oPREDELENIE. pUSTX A = kaij k I B = kbklk DWE MATRICYPORQDKA n: bULEWSKIM PROIZWEDENIEM A B NAZYWAETSQ MATRICA D =kdrsk TAKAQ ^TOn_drs = arp bps|0-1-,p=1DLQ WSEH r I sdLQ BULEWSKOGO UMNOVENIQ MATRIC NELXZQ NEPOSREDSTWENNO PRIMENITX IDE@ {TRASSENA, TAK KAK W ALGORITME {TRASSENA ESTX WY^ITANIE, A U DIZ_@NKCII NET OBRATNOJ OPERACII. nESMOTRQ NA \TO,SPRAWEDLIWA SLEDU@]AQ TEOREMA.tEOREMA. bULEWSKOE PROIZWEDENIE D = A B DWUH MATRICA I B PORQDKA n MOVNO WY^ISLITX S ^ISLOM BITOWYH OPERACIJO(nlog2 7 log2 n)dOKAZATELXSTWO mY OPI[EM SOOTWETSTWU@]IJ ALGORITM, KOTORYJ OSNOWAN NA IDEE "RAS[IRENIQ MODELI" (SM.
ALGORITM tOOMA).wMESTO WY^ISLENIQ D = A B MY WY^ISLIM SNA^ALA OBY^NOE PROIZWEDENIE C = AB . pRI \TOM OTMETIM SLEDU@]U@ SWQZX MEVDU D IC:drs = 1 () crs > 0:pO PREDYDU]EJ TEOREME DLQ WY^ISLENIQ C = kcrs k SU]ESTWUET ALGORITM S ^ISLOM BITOWYH OPERACIJ O(nlog2 7 log2 n): pOSLE \TOGO W KAVDOM crs DOSTATO^NO WZQTX DIZ_@NKCI@ WSEH RAZRQDOW (ISKL@^AQ ZNAK),^TOBY WY^ISLITX drs: pOSKOLXKU 0 6 crs 6 n, TO DLINA KAVDOGO crsNE PREWOSHODIT O(log n) I NA WY^ISLENIE WSEH drs IZ crs POTREBUETSQO(n2 log n) BITOWYH OPERACIJ. oB]EE ^ISLO BITOWYH OPERACIJ BUDETO(nlog2 7 log2 n) + O(n2 log n) = O(nlog2 7 log2 n): tEOREMA DOKAZANA.zAME^ANIE.
sM. ZAME^ANIQ K PREDYDU]EJ TEOREME..0-1-..25tRANZITIWNOE ZAMYKANIE GRAFOWdANO: ORIENTIROWANNYJ GRAF G W WIDE MATRICY A = kaij k, GDEaij = 1, ESLI W G ESTX DUGA IZ vi W vj , I aij = 0, ESLI TAKOJ DUGI NET(aii = 0 DLQ WSEH i).tREBUETSQ: POSTROITX MATRICU B = kbij k, TAKU@, ^TO bij = 1, ESLIESTX ORIENTIROWANNYJ PUTX IZ vi W vj , I bij = 0, ESLI TAKOGO PUTI NET(W ^ASTNOSTI, bii = 1 DLQ WSEH i).oPREDELENIE. oRIENTIROWANNYJ GRAF S MATRICEJ SMEVNOSTIB NAZYWAETSQ TRANZITIWNYM ZAMYKANIEM GRAFA GtEOREMA. tRANZITIWNOE ZAMYKANIE ORIENTIROWANNOGOGRAFA S3log7n WER[INAMI MOVNO POSTROITX ISPOLXZUQ O(n 2 log n) BITOWYHOPERACIJdOKAZATELXSTWO pUSTX A | MATRICA SMEVNOSTI ORGRAFA GI MATRICA A = kaij k POLU^AETSQ IZ A ZAMENOJ WSEH DIAGONALXNYH\LEMENTOW NA 1.
tOGDA aij = 1 W TOM I TOLXKO W TOM SLU^AE, ESLI IZvi W vj SU]ESTWUET ORIENTIROWANNYJ PUTX DLINY (T.E. S ^ISLOM DUG) NEBOLEE 1. pUSTX Ak = A A : : : A; GDE ^ISLO SOMNOVITELEJ RAWNO k IUMNOVENIE MATRIC BULEWSKOE.lEMMA. eSLI Ak = kakij k; TO akij = 1 W TOM I TOLXKO W TOMSLU^AE ESLI W G SU]ESTWUET ORIENTIROWANNYJ PUTX IZ vi W vj DLINYNE BOLEE kdOKAZATELXSTWO (INDUKCIEJ PO k). pRI k = 1 UTWERVDENIE WERNO.pUSTX ONO WERNO PRI k = p, TO ESTX apij = 1 TOGDA I TOLXKO TOGDA, KOGDASU]ESTWUET PUTX IZ vi W vj WDLINY NE BOLEE p.
pO OPREDELENI@ POLU^AEMpp+1A(p+1) = Ap A I ap+1ij = q aiq aqj . oTS@DA aij = 1 TOGDA I TOLXKOTOGDA, KOGDA SU]ESTWUET WER[INA vq TAKAQ, ^TO IZ vi W vq SU]ESTWUETPUTX DLINY NE BOLEE p, I IZ vq W vj SU]ESTWUET PUTX DLINY NE BOLEE1. nO \TO USLOWIE RAWNOSILXNO TOMU, ^TO IZ vi W vj SU]ESTWUET PUTXDLINY NE BOLEE p + 1. tAKIM OBRAZOM, UTWERVDENIE LEMMY WERNO I PRIk = p + 1. lEMMA DOKAZANA.eSLI W ORGRAFE G IZ vi W vj SU]ESTWUET HOTQ BY ODIN ORIENTIROWANNYJ PUTX, TO SU]ESTWUET TAKOJ PUTX BEZ POWTORENIQ WER[IN I, SLEDOWATELXNO, DLINY NE BOLEE n ; 1, GDE n | ^ISLO WER[IN W G. pO\TOMUIZ LEMMY SLEDUET, ^TO Ak = B PRI L@BOMk > n ; 1. bUDEM WY^ISLQTXm2482POSLEDOWATELXNO A; A ;mA ; A ; : : : A ; GDE m = dlog2(n ; 1)e.
tAKKAK 2m > n ; 1, TO A2 = B . pO TEOREME SU]ESTWUET ALGORITM DLQWY^ISLENIQ WSEH \TIH MATRIC I, W ^ASTNOSTI B , S ^ISLOM BITOWYHOPERACIJ m O(nlog2 7 log2 n) = O(nlog2 7 log3 n): tEOREMA DOKAZANA.zAME^ANIE. sM. ZAME^ANIQ K TEOREME..,..,.26rASPOZNAWANIE PRINADLEVNOSTI BULEWYH FUNKCIJPREDPOLNYM KLASSAM pOSTArASSMOTRIM ZADA^U RASPOZNAWANIQ SWOJSTW BULEWYH FUNKCIJ,PRI^EM SEJ^AS BUDEM S^ITATX, ^TO BULEWY FUNKCII POSTUPA@T NA WHODALGORITMA W WEKTORNOM PREDSTAWLENII.
a IMENNO, PUSTX WSE NABORYDLINY n IZ 0 I 1 UPORQDO^ENY ESTESTWENNYM OBRAZOM (KAK SOOTWETSTWU@]IE IM DWOI^NYE ^ISLA). tOGDA BULEWSKU@ FUNKCI@ f (x1; : : : ; xn) OTn PEREMENNYH MOVNO ZADATX WEKTOROM (a0; a1; : : : ; a2n;1) EE ZNA^ENIJ NAWSEH 2n NABORAH. w KA^ESTWE ALGORITMOW MY RASSMOTRIM ALGORITMY SBITOWYMI OPERACIQMI. l@BOJ TAKOJ ALGORITM MOVNO RASSMATRIWATXKAK SHEMU IZ FUNKCIONALXNYH \LEMENTOW (sf|), \LEMENTAMI W KOTOROJMOGUT BYTX L@BYE FUNKCII OT 2 PEREMENNYH (ILI 1). eSLI OTWET WZADA^E DLQ DANNOGO WHODA "DA", TO NA WYHODE DOLVNA BYTX 1, INA^E 0.pOD SLOVNOSTX@ ALGORITMA BUDEM PONIMATX ^ISLO BITOWYH OPERACIJ(^ISLO \LEMENTOW W sf|).tEOREMA pOSTA O POLNOTE SISTEMY BULEWYH FUNKCIJ SWODIT WOPROS O POLNOTE K WOPROSU O PRINADLEVNOSTI FUNKCIJ 5 PREDPOLNYMKLASSAM T0; T1; S; L; M (SM.[ ]). mY RASSMOTRIM WOPROS O SLOVNOSTIRASPOZNAWANIQ \TIH SWOJSTW.
nAPOMNIM, ^TOf 2 T0 () f (0; : : : ; 0) = 0; f 2 T1 () f (1; : : : ; 1) = 1,f 2 S () f (x1; : : : ; xn) = f(x1; : : : ; xn),f 2 L () f (x1; : : : ; xn ) = a0 a1x1 : : : anxn,f 2 M () DLQ WSEH ~ = (1; : : : ; n) I ~ = (1; : : : ; n)TAKIH, ^TO 8i(i 6 i ); WYPOLNQETSQ f (~) 6 f (~).uTWERVDENIE 1. pRI WEKTORNOM PREDSTAWLENII FUNKCIJ DLQRASPOZNAWNIQ SWOJSTWA "f (x1 ; : : : ; xn ) 2 T0?" SU]ESTWUET ALGORITMsf| SO SLOVNOSTX@w \TOM SLU^AE WYHOD z ZADAETSQ FORMULOJ z = 0.uTWERVDENIE 2. pRI WEKTORNOM PREDSTAWLENII FUNKCIJ DLQRASPOZNAWNIQ SWOJSTWA "f (x1 ; : : : ; xn ) 2 T1?" SU]ESTWUET ALGORITMsf| SO SLOVNOSTX@w \TOM SLU^AE WYHOD z ZADAETSQ FORMULOJ z = 2n;1.uTWERVDENIE 3.
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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
