В.Б. Алексеев, А.А. Вороненко, С.А. Ложкин и др. - Задачи по курсу Основы кибернетики (2002) (1124121), страница 7
Текст из файла (страница 7)
u uREALIZACIQ1) b = 1, E1 : 11 p 2 u1 _p u2 ; u _ u 1 u u 1 u &u 2) b = 3, E1 : 11 p2 p , E2 : 11 p 2 p , E3 : 1 1 2 .dRUGOJ (TAK NAZYWAEMYJ LOGIKO-KOMBINATORNYJ [12]) PODHOD K OPREDELENI@ UROWNQ NADEVNOSTI SHEMY SWQZAN S PONQTIEM SAMOKORREKTIRUEMOSTI. sHEMA NAZYWAETSQ SAMOKORREKTIRU@]EJSQ OTNOSITELXNO ISTO^NIKA NEISPRAWNOSTEJ i, ESLI W MODELI (; i) WSE SOSTOQNIQ\KWIWALENTNY. eSTESTWENNO S^ITATX, ^TO ^EM BOLX[E NEISPRAWNOSTEJKORREKTIRUET SHEMA , TEM WY[E UROWENX EE NADEVNOSTI.
zADA^A SINTEZA SAMOKORREKTIRU@]IHSQ SHEM QWLQETSQ WAVNYM ^ASTNYM SLU^AEMOB]EJ ZADA^I SINTEZA.rASSMOTRIM ZADA^U SINTEZA KONTAKTNYH SHEM, KOTORYE QWLQ@TSQ SA47MOKORREKTIRU@]IMISQ OTNOSITELXNO ISTO^NIKA NEISPRAWNOSTEJ ir;s(SM. x 6). pROSTEJ[IJ SPOSOB RE[ENIQ \TOJ ZADA^I SWQZAN S POSLEDOWATELXNYM I (ILI) PARALLELXNYM DUBLIROWANIEM DWUHPOL@SNOJ ks.lEGKO WIDETX, ^TO ESLI PRI \TOM WZQTX l \KZEMPLQROW SAMOKORREKTIRU@]EJSQ OTNOSITELXNO ir;s ks I SOEDINITX IH POSLEDOWATELXNO(PARALLELXNO), TO POLU^IM \KWIWALENTNU@ ks 0, KOTORAQ QWLQETSQSAMOKORREKTIRU@]EJSQ OTNOSITELXNO iR;S , GDE R = r, S = (s +1) l 1(SOOTWETSTWENNO R = (r + 1) l 1, S = s). aNALOGI^NYJ REZULXTATDAET UKAZANNOE WY[E DUBLIROWANIE, ESLI EGO PRIMENQTX K KAVDOMUKONTAKTU SHEMY (\TOT SPOSOBOM MOVNO STROITX MNOGOPOL@SNYE SAMOKORREKTIRU@]IESQ ks).dRUGOJ SPOSOB PEREHODA OT (MNOGOPOL@SNOJ) ks K \KWIWALENTNOJ EJ ks 0, KOTORAQ QWLQETSQ SAMOKORREKTIRU@]EJSQ OTNOSITELXNOi;1 , GDE 2 f0; 1g, ZAKL@^AETSQ W SLEDU@]EM.
rAZOBXEM ks NA NEPERESEKA@]IESQ SWQZNYE (MNOGOPOL@SNYE) PODSHEMY 1; : : : ; l, KAVDAQIZ KOTORYH SOSTOIT IZ KONTAKTOW ODNOGO TIPA, A ZATEM ZAMENIM ks i,i = 1; : : : ; l, NA ks 0i, SOSTOQ]U@ IZ KONTAKTOW TOGO VE TIPA, KOTORAQPREDSTAWLQET SOBOJ CIKL, PROHODQ]IJ ^EREZ WSE WER[INY v1(i); : : : ; va(ii)ks i, ESLI = 1 (SM. RIS. 27 A)) I ZWEZDU S CENTROM W NOWOJ WER[INE,SOEDINENNOJ SO WSEMI WER[INAMI v1(i); : : : ; va(ii) ks i, ESLI = 0 (SM.RIS.
27 B)).v1(i)xv2(i)xva(ii)x:: :A)v1(i)v3(i)v2(i)x x x v3(i)x : : :va(ii)rIS. 27B)7.6. 1) dOKAZATX, ^TO ESLI FUNKCIQ xi , GDE 1 i n I 2 f0; 1gMOVET BYTX POLU^ENA IZ FUNKCII f (x1; :::; xn) W REZULXTATE NEKOTOROJPODSTANOWKI KONSTANT WMESTO bp x1; :::; xi 1; xi+1; :::; xn, TO W L@BOJ ks,REALIZU@]IJ f I KORREKTIRU@]EJ r OBRYWOW (r ZAMYKANIJ), SODERVITSQ NE MENEE (r + 1) KONTAKTOW xi .2) pOSTROITX DLQ FUNKCII x1 x2 MINIMALXNU@ ks, KORREKTIRU@]U@48A) ODNO RAZMYKANIE,B) ODNO ZAMYKANIE.7.7.
pOSTROITX PO ks \KWIWALENTNU@ EJ ks 0, KORREKTIRU@]U@1) ODNO RAZMYKANIE2) ODNO ZAMYKANIEI TAKU@, ^TOA) L(0) 30, ESLI | ks NA RIS. 28,B) L(0) 25, ESLI | ks NA RIS. 29,W) L(0) 28, ESLI | ks NA RIS. 30. x2x3x3x1x3 a xx4 xx3 xx2xx1 b14 32 1x3 x2 b2x2 x1rIS. 28.x3ax4x4x3x3x3x2x2x2x1x1bx3 x2rIS. 29.x3 x1x3 xx42ax3 x3 x1 b1 x1x4 x3 x2x2 x b21ax2 x4x1 x3x2 x bx2 4rIS. 30.rIS. 31.7.8. rASSMATRIWAETSQ ks NA RIS. 31.1) pOSTROITX PO \TOJ SHEME ks NE BOLEE ^EM IZ 13 KONTAKTOW, KORREKTIRU@]U@A) ODNO RAZMYKANIE,B) ODNO ZAMYKANIE.2) pOSTROITX DLQ FUNKCII, REALIZUEMOJ \TOJ SHEMOJ, MINIMALXNU@ks, KORREKTIRU@]U@49A) ODNO RAZMYKANIE,B) ODNO ZAMYKANIE.7.9.
dLQ FUNKCII m(x1; x2; x3) = x1x2 _ x1x3 _ x2x3 POSTROITX ksSLOVNOSTI 8, KORREKTIRU@]U@A) ODNO RAZMYKANIE,B) ODNO ZAMYKANIE.uKAZANIE. kARKASY \TIH SHEM PREDSTAWLENY NA RIS. 32 I 33 (SOOTWETSTWENNO).ababrIS. 32.x2ax4x1x2x2x2rIS. 33.x3bx4abx2 x3rIS. 35.rIS. 34.7.10. dOKAZATX, ^TO MINIMALXNAQ KORREKTIRU@]AQ ODNO RAZMYKANIEks DLQ LINEJNOJ BULEWOJ FUNKCII, SU]ESTWENNO ZAWISQ]EJ OT WSEH SWOIH n PEREMENNYH, IMEET SLOVNOSTX 4n (ks, REALIZU@]AQ \TU FUNKCI@,PREDSTAWLENA NA RIS. 21).7.11. rASSMATRIWAETSQ ks NA RIS. 34. pOSTROITX PO \TOJ SHEME ks,KORREKTIRU@]U@ ODNO RAZMYKANIE I IME@]U@ SLOVNOSTXA) NE BOLEE 18,B) NE BOLEE 17.7.12. dLQ \LEMENTARNOJ SIMMETRI^ESKOJ FUNKCII TREH PEREMENNYHS RABO^IM ^ISLOM DWA S32(x1; x2; x3) = x1x2x3 _ x1x2x3 _ x1x2x3 POSTROITX MINIMALXNU@ KORREKTIRU@]U@ ODNO RAZMYKANIE ks. uKAZANIE.kARKAS \TOJ SHEMY PREDSTAWLEN NA RIS.
35.x1507.13. oBOZNA^IM ^EREZ Lp(f ), p 0, SLOVNOSTX MINIMALXNOJ ks,REALIZU@]EJ FUNKCI@ f I KORREKTIRU@]EJ p OBRYWOW (p ZAMYKANIJ)KONTAKTOW. dOKAVITE, ^TO ESLI DLQ NATURALXNOGO s I CELYH NEOTRICATELXNYH k; k1; : : :; ks IMEET MESTO RAWENSTWO k1 + + ks + s = k + 1, TOLk (f ) Lk (f ) + + Lks (f ).7.14. pOKAVITE, ^TO W SLU^AE RAZMYKANIQ DLQ WELI^IN, WWEDENNYHW ZADA^E 7.13, SPRAWEDLIWY NERAWENSTWA:A) 6(p + 1) Lp(x1 x2 x3) 6(p + 1) + 2((p + 1) mod 2),B) 6(p + 1) Lp(S32(x1; x2; x3)) 6(p + 1) + ((p + 1) mod 2), GDES32(x1; x2; x3) = x1x2x3 _ x1x2x3 _ x1x2x3.7.15. pUSTX | KORREKTIRU@]AQ ODIN OBRYW ks, W KOTOROJ MOVNOWYDELITX s PAR WER[IN (WSE WER[INY RAZLI^NY) TAKIH, ^TO PO ANALIZU PROWODIMOSTEJ MEVDU \TIMI PARAMI WER[IN MOVNO OBNARUVITXL@BOJ EDINI^NYJ OBRYW KONTAKTA.
pOKAZATX, ^TO SHEMU MOVNO PREOBRAZOWATX W KORREKTIRU@]U@ ODIN OBRYW ks 0 TAKU@, ^TO L@BOJEDINI^NYJ OBRYW KONTAKTA W NEJ MOVET BYTX OBNARUVEN PO ANALIZUPROWODIMOSTEJ MEVDU DWUMQ WER[INAMI SHEMY.151oTWETY, UKAZANIQ I RE[ENIQk PARAGRAFU 11.1. 1) dA; 2) DA; 3) NET; 4) NET.1.2. 1) nET. pRIMER: fxg. 2) nET. pRIMER: f0; 1; xg.1.3. dA.1.4. 6) nET, TAK KAK, NAPRIMER, FUNKCIQ f (x; y) = x _ y QWLQETSQSIMMETRI^ESKOJ, NO PRI DOBAWLENII W NEE FIKTIWNOJ PEREMENNOJ z POLU^AETSQ NESIMMETRI^ESKAQ FUNKCIQ g(x; y; z) = x _ y.7) dA.1.5. pUSTX n 0 I f (x1; : : : ; xn; xn+1) | PROIZWOLXNAQ FUNKCIQ IZQ(n + 1). iZ RAZLOVENIQf (x1; : : : ; xn; xn+1) = xn+1f (x1; : : : ; xn; 1) _ xn+1f (x1; : : : ; xn; 0)SLEDUET, ^TO FUNKCIQ f POLNOSTX@ OPREDELQETSQ PAROJ SWOIH PODFUNKCIJ f (x1; : : : ; xn; 1) I f (x1; : : : ; xn; 0).
pOSKOLXKU POSLEDNIE TAKVE PRINADLEVAT KLASSU Q, IMEEMjQ(n + 1)j jQ(n)j2:oTS@DApnpjQ(n + 1)j n jQ(n)j:(4)pniZ (4) WYTEKAET NEWOZRASTANIE POSLEDOWATELXNOSTI jQ(n)j. pOKAVEM, ^TO ONA OGRANI^ENA. eSLI Q NE PUSTO, TOpn 2npnpnpn(5)1 = 1 jQ(n)j jP2(n)j = 2 = 2:psLEDOWATELXNO, PREDEL POSLEDOWATELXNOSTI n jQ(n)j SU]ESTWUET I ZAKL@^EN W SEGMENTE [1; 2].1.6. w SAMOM DELE, PRI NEKOTOROM FIKSIROWANNOM m SU]ESTWUETpFUNKCIQ g(x1; : : : ; xm) 2= Q. tAK KAK POSLEDOWATELXNOSTX n jQ(n)j NEWOZRASTAET, TOppnm2m 1)2 m < 2:jQ(n)jjQ(m)j(2limn!11.7. 2) wOSPOLXZOWATXSQ TEM, ^TO ^ISLO MONOTONNYH FUNKCIJ, ZAWInSQ]IH OT PEREMENNYH x1; x2; : : : ; xn, NE PREWOSHODIT n(dn= e).3) 1/2. nIVNQQ OCENKA jQ(n)j.
wYBEREM LINEJNU@ FUNKCI@ l W (3)RAWNOJ x1: : :xn. pUSTX B n;1 | MNOVESTWO DWOI^NYH NABOROW DLINY n2 +12222222222252S NE^ETNYM ^ISLOM KOORDINAT, RAWNYH 1. ~EREZ Nf OBOZNA^IM MNOVESTWO NABOROW, OBRA]A@]IH FUNKCI@ f W EDINICU. qSNO, ^TO Nl = B n;1I jB n;1jn= 2n 1. sREDI FUNKCIJ g(x1; : : : ; xn) 2 P2 NAJDETSQ MNOVESTWOG IZ 22 FUNKCIJ, POPARNO OTLI^A@]IHSQ DRUG OT DRUGA NA MNOVESTWE B n;1.n qSNO, ^TO ^ISLOFUNKCIJ WIDA (3) S l = x1 : : : xn I g 2 Gn22RAWNO 2 .
oTS@DA 2 jQ(n)j.wERHNQQ OCENKA jQ2r(n)j. pRIFIKSIROWANNOJ FUNKCII l = xi : : : n2xir IMEETSQ NE BOLEE 2 2 RAZLI^NYH FUNKCIJ f 2 Q(n). ~ISLOn+1.LINEJNYH FUNKCIJ, ZAWISQ]IHOTPEREMENNYHx;:::;x,RAWNO21npO\TOMU jQ(n)j 2n+122n . tAKIM OBRAZOM22n jQ(n)j 2n+122n :oTS@DApn1=2:limjQ(n)j=2n!1tEM SAMYM POSTROEN INWARIANTNYJ KLASS Q S HARAKTERISTIKOJ =1=2.1111111112k PARAGRAFU 22.7. uKAZANIE. wOSPOLXZOWATXSQ TOVDESTWAMI: (x_y)(x_z) = (x_yz);ESLI FORMULY Y I Z NEVZAWISQTOT x, TO (x _ Y )(x _ Z ) RAWNO Y _ Z ;Vy1y2 : : : yk _ z1z2 : : : zl = 1ik 1jl(yi _ zj ).2.8. sM.
[7]2.9. wOSPOLXZUJTESX SWODIMOSTQMI ZADA^I 2.8.2.10. 1) dOKAVITE, ^TO ZADA^A wyp POLINOMIALXNO SWODITSQ K RAS-SMATRIWAEMOJ ZADA^E;2) DOKAVITE, ^TO ZADA^A 3-wyp POLINOMIALXNO SWODITSQ K RASSMATRIWAEMOJ ZADA^E.2.11. 1), 3) zADA^I PRINADLEVAT KLASSU P;2) NP-POLNAQ ZADA^A. uKAZANIE. pUSTX D | NEKOTORAQ dnf OT PEREMENNYH x1; : : : ; xn. pREOBRAZUEM EE W dnf D0, D0, REALIZU@]U@ FUNKCI@ t D1 _ x1 y1 _ : : : _ xn yn, GDE PEREMENNAQ t NE WSTRE^AETSQ W dnfD, A dnf D1 POLU^ENA IZ dnf D ZAMENOJ KAVDOJ BUKWY WIDA xi NAPEREMENNU@ yi. tOGDA dnf D OBRA]AETSQ W NOLX NA NEKOTOROM NABORETOGDA I TOGDA, KOGDA SU]ESTWU@T DWA PROTIWOPOLOVNYH NABORA, NA KOTORYH dnf D0 OBRA]AETSQ W NOLX. kROME TOGO, POSTROITX dnf D0 POdnf D NA DETERMINIROWANNOJ mt MOVNO ZA POLINOMIALXNOE WREMQ.53tAKIM OBRAZOM, NP-POLNAQ ZADA^A O SU]ESTWOWANII NABORA, OBRA]A@]EGO dnf W NOLX (SM.
ZADA^U 2.10 P. 1)) POLINOMIALXNO SWODITSQ KRASSMATRIWAEMOJ ZADA^E.4) NP-POLNAQ ZADA^A. uKAZANIE. sWEDITE K NEJ ZADA^U 3-wyp.5) zADA^A PRINADLEVIT KLASSU P. uKAZANIE. wOSPOLXZUJTESX KRITERIEM SU]ESTWOWANIQ \JLEROWA CIKLA W GRAFE. (tEOREMA |JLERA. wSWQZNOM GRAFE SU]ESTWUET CIKL, PROHODQ]IJ PO WSEM REBRAM, PRI^EMPO KAVDOMU W TO^NOSTI ODIN RAZ, TOGDA I TOLXKO TOGDA, KOGDA STEPENXKAVDOJ EGO WER[INY ^ETNA.)6) NP-POLNAQ ZADA^A.7) zADA^A PRINADLEVIT KLASSU P.
uKAZANIE. wOSPOLXZUJTESX KRITERIEM 2-RASKRA[IWAEMOGO GRAFA. (tEOREMA. gRAF MOVNO RASKRASITX WDWA CWETA TOGDA I TOLXKO TOGDA, KOGDA ON NE SODERVIT CIKLOW NE^ETNOJDLINY.)8) NP-POLNAQ ZADA^A. uKAZANIE. pUSTX D, D = K1 _ : : : Kl , | NEKOTORQ dnf BEZ OTRICANIJ PEREMENNYH. sOPOSTAWIM EJ GIPERGRAFG =< V; E >, GDE MNOVESTWO WER[IN V ESTX MNOVESTWO PEREMENNYH,WSTRE^A@]IHSQ W dnf D, MNOVESTWO REBER E ESTX fE1 : : : El g, PRI^EMREBRO Ei SOSTOIT IZ PEREMENNYH, SODERVA]IHSQ W \LEMENTARNOJ KON_@NKCII Ki, i = 1; : : : ; l.
tOGDA dnf D OBRA]AETSQ W NOLX NA NEKOTORYHDWUH PROTIWOPOLOVNYH NABORAH TOGDA I TOLXKO TOGDA, KOGDA GIPERGRAF G MOVNO RASKRASITX W DWA CWETA. pOSTROITX GIPERGRAF G PO ISHODNOJ dnf D NA DETERMINIROWANNOJ mt MOVNO ZA POLINOMIALXNOEWREMQ. tAKIM OBRAZOM, NP-POLNAQ ZADA^A OB OBRA]ENII W NOLX NA DWUHPROTIWOPOLOVNYH NABORAH dnf BEZ OTRICANIJ (SM. P. 2)) SWODITSQ KRASSMATRIWAEMOJ ZADA^E.2.12. 1) A), G) zADA^I PRINADLEVAT KLASSU P. uKAZANIE.
wOSPOLXZUJTESX TEM FAKTOM, ^TO LINEJNAQ FUNKCIQ RAWNA EDINICE NA NABORAHLIBO TOLXKO S NE^ETNYM, LIBO TOLXKO S ^ETNYM ^ISLOM EDINIC.1) B), W) NP-POLNYE ZADA^I. uKAZANIE. sWEDITE K RASSMATRIWAEMYMZADA^AM NP-POLNU@ ZADA^U OB OBRA]ENII dnf W NOLX (SM. ZADA^U 2.10P. 1)). pUSTX D | NEKOTORAQ NE RAWNAQ TOVDESTWENNO NUL@ dnf, A dnfD0 REALIZUET FUNKCI@ D t, GDE t | PEREMENNAQ, NE WSTRE^A@]AQSQ Wdnf D. tOGDA dnf D NA NEKOTOROM NABORE OBRA]AETSQ W NOLX TOGDAI TOLXKO TOGDA, KOGDA dnf D0 REALIZUET NELINEJNU@ FUNKCI@.2) A) zADA^A PRINADLEVIT KLASSU P.
uKAZANIE. mOVNO WOSPOLXZOWATXSQ OPREDELENIEM MONOTONNOJ FUNKCII.542) B) NP-POLNAQ ZADA^A. uKAZANIE. sWEDITE K RASSMATRIWAEMYM ZADA^AM NP-POLNU@ ZADA^U OB OBRA]ENII dnf W NOLX (SM. ZADA^U 2.10 P.1)). pUSTX D | NEKOTORAQ NE RAWNAQ TOVDESTWENNO NUL@ dnf, A dnfD0 REALIZUET FUNKCI@ D _ t, GDE t | PEREMENNAQ, NE WSTRE^A@]AQSQ Wdnf D. tOGDA dnf D NA NEKOTOROM NABORE OBRA]AETSQ W NOLX TOGDAI TOLXKO TOGDA, KOGDA dnf D0 REALIZUET NEMONOTONNU@ FUNKCI@.2) W) zADA^A PRINADLEVIT KLASSU P.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
