В.Б. Алексеев, А.А. Вороненко, С.А. Ложкин, Д.С. Романов и др. - Задачи по курсу «Основы кибернетики» (2002) (1132782), страница 7
Текст из файла (страница 7)
nIVE UKAZANA sf| I RASPREDELENIQ REVIMOW RABOTY EE NENADEVNYH f|. nAJTI RASPREDELENIE REVIMOW RABOTY sf| , A ZATEMWY^ISLITX (), () I FUNKCI@ q.1) | sf| NA RIS. 22 A), GDE KON_@NKTOR RABOTAET ABSOL@TNO NADEVNO, A RASPREDELENIQ REVIMOW RABOTYu1 _ u2 I INWER u DIZ_@NKTORATORA u1 IME@T, SOOTWETSTWENNO, WID 1 _2 u2 u1 1 u2 I u31 u11 .334 42) | sf| NA RIS. 23 A), GDE DIZ_@NKTOR RABOTAET ABSOL@TNONADEVNOREVIMOW RABOTY KON_@NKTORA u1&u2 IMEET u ,&AuRASPREDELENIEWID 1 3 2 u11 .443) | sf| NA RIS.
24 A), GDE KON_@NKTOR RABOTAET ABSOL@TNONADEVNOREVIMOW RABOTY DIZ_@NKTORA u1 _ u2 IMEET u , _A uRASPREDELENIEWID 1 2 2 u1&1 u2 .337.3. 1) pUSTX W sf| NA RIS. 22 A) DIZ_@NKTOR RABOTAET ABSOL@TNO NADEVNO, A RASPREDELENIQ REVIMOW RABOTY KON_@NKTORA u1&u2 I46 u &u01?p p12 u 0 I 31 1 .INWERTORA u1 IME@T, SOOTWETSTWENNO, WID4 4iZWESTNO, ^TO WEROQTNOSTX TAKOGO FUNKCIONIROWANIQ SHEMY, PRI KOTOROM NA OBOIH WYHODAH SHEMY REALIZU@TSQ TOVDESTWENNYE NULI, RAWNA1 . nAJTI p.62) pUSTX RASPREDELENIQ REVIMOW RABOTY KON_@NKTORA u1&u2 I DIZ_&u2 1@NKTORA u1 _ u2 W sf| NA RIS. 23 A) IME@T WID u11?p p u _u x I 1 2, SOOTWETSTWENNO. iZWESTNO, ^TO WEROQTNOSTX TAKOGO2313FUNKCIONIROWANIQ SHEMY, PRI KOTOROM NA WYHODE REALIZUETSQ TOVDESTWENNAQ EDINICA, RAWNA 83 .
nAJTI p.7.4. pUSTX BAZIS b SOSTOIT IZ f|, REALIZU@]EGO FUNKCI@ GOLOSOWANIQ, KOTORYJ RABOTAET ABSOL@TNO NADEVNO, I KON_@NKTORA u &u 1 u1&u2,RASPREDELENIE REVIMOW RABOTY KOTOROGO IMEET WID 1 2 2 1 .331) dOSTATO^NO LI 40 FUNKCIONALXNYH \LEMENTOW, ^TOBY REALIZOWATXFUNKCI@ u1&u2 c NENADEVNOSTX@ NE BOLEE 0:1?2) dOSTATO^NO LI 400 FUNKCIONALXNYH \LEMENTOW, ^TOBY REALIZOWATX FUNKCI@ u1&u2 c NENADEVNOSTX@ NE BOLEE 0:002?7.5. nIVE PRIWEDENY RASPREDELENIQ REVIMOW RABOTY f| Ei, i =1; :::; b, NENADEVNOGO BAZISA b.
pOKAVITE, ^TO W DANNOM BAZISE WOZMOVNASKOLX UGODNO NADEVNAQPROIZWOLXNOJ FUNKCII. 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)v3(i)v1(i)v2(i)xx 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.x3 x2x3x3x1a xx4 xx3 xx2xx1 b14 32 1x3 x2 b2x2 x1rIS. 28.x3ax4x4x3x3x3x2x2x2x1x1bx3 x2rIS. 29.x3 x1x3 xx42ax3 x3 x1 b1 x1x4 x3 x2bx2 x 21ax2 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).aabbrIS. 33.rIS. 32.x2ax4x1x2x2x2x3bx4abx2 x3rIS. 34.rIS. 35.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)piZ (4) WYTEKAET NEWOZRASTANIE POSLEDOWATELXNOSTI n jQ(n)j. pOKAVEM, ^TO ONA OGRANI^ENA. eSLI Q NE PUSTO, TOpnpppn1 = 1 n jQ(n)j n jP2(n)j = 22n = 2:(5)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, TOpnpm2m ? 1)2?m < 2:limjQ(n)jjQ(m)j(2n!11.7. 2) wOSPOLXZOWATXSQ TEM, ^TO ^ISLO MONOTONNYH FUNKCIJ, ZAWIn )(SQ]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 MNOVESTWO?G 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 Gn?22RAWNO 2 . oTS@DA 2 jQ(n)j.wERHNQQ OCENKA jQ2r(?n)j. pRIFIKSIROWANNOJ FUNKCII l = xi : : : n?2xir IMEETSQ NE BOLEE 2 2 RAZLI^NYH FUNKCIJ f 2 Q(n). ~ISLOLINEJNYH FUNKCIJ, ZAWISQ]IHOT PEREMENNYH x1; : : :; xn, RAWNO 2n+1.n?pO\TOMU jQ(n)j 2n+122 . tAKIM OBRAZOM22n? jQ(n)j 2n+122n? :oTS@DApnjQ(n)j = 21=2:limn!1tEM SAMYM POSTROEN INWARIANTNYJ KLASS Q S HARAKTERISTIKOJ =1=2.1111111112k PARAGRAFU 22.7.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
