В.Б. Алекссев - Сложные алгоритмы (1132790), страница 5
Текст из файла (страница 5)
rAZREVEMKAVDU@ IZ MATRIC A I B , A TAKVE ISKOMU@ MATRICU C = A B , NA 4KWADRATNYH BLOKA RAZMERA n2 n2 :. B C11 A12 11 B12 11 C12 ;B = ;C = :A= AA21 A22B21 B22C21 C22 iZ ALGEBRY IZWESTNO, ^TO W \TOM SLU^AEC11 = A11B11 + A12B21; C12 = A11B12 + A12B22;C21 = A21B11 + A22B21; C22 = A21B12 + A22B22:tAKIM OBRAZOM, WY^ISLENIE MATRICY C SWODITSQ K 8 UMNOVENIQMMATRIC PORQDKA n2 (I NESKOLXKIM SLOVENIQM). iDEQ {TRASSENA SOSTOITW ZAMENE 8 UMNOVENIJ NA 7 (SRAWNITE S ALGORITMOM kARACUBY). rAS-22SMOTRIM SLEDU@]IE 7 PROIZWEDENIJ:D1 = (A11 + A22)(B11 + B22); D5 = (A11 + A12)B22;D2 = (;A11 + A21)(B11 + B12); D6 = A22(;B11 + B21);D3 = (A12 ; A22)(B21 + B22); D7 = (A21 + A22)B11:D4 = A11(B12 ; B22);rASKRYWAQ SKOBKI I PRIWODQ PODOBNYE ^LENY, MOVNO PROWERITX, ^TOC11 = D1 + D3 ; D5 + D6; C12 = D4 + D5;C21 = D6 + D7;C22 = D1 + D2 + D4 ; D7:tAKIM OBRAZOM, UMNOVENIE MATRIC PORQDKA n SWODITSQ K 7 UMNOVENIQMMATRIC PORQDKA n2 I NESKOLXKIM SLOVENIQM MATRIC PORQDKA n2 : eSLIn = 2k ; TO \TOT PROCESS MOVNO PRODOLVITX REKURSIWNO.
eSLI VE n = 1;TO DLQ UMNOVENIQ MATRIC PORQDKA 1 TREBUETSQ WSEGO 1 UMNOVENIE\LEMENTOW. pUSTX L(n) | ^ISLO ARIFMETI^ESKIH OPERACIJ W OPISANNOMALGORITME. tAK KAK SLOVENIE DWUH MATRIC PORQDKA n2 TREBUET O(n2)OPERACIJ, TO DLQ n = 2k (k = 1; 2; 3; : : : ) POLU^AEM REKURRENTNOE NERAWENSTWOL(n) 6 7L( n2 ) + O(n2):pO TEOREME O REKURRENTNOM NERAWENSTWE OTS@DA POLU^AEM L(n) =O(nlog2 7): tEOREMA DOKAZANA.zAME^ANIE. 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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
