В.Б. Алексеев, А.А. Вороненко, С.А. Ложкин и др. - Задачи по курсу Основы кибернетики (2002) (1124121), страница 5
Текст из файла (страница 5)
W ZADA^E 5.3).5.6. dOKAZATX, ^TO ^ISLOTUPIKOWYH TESTOW MATRICY M S m STROKAm2MI NE PREWOSHODIT b m c .5.7. dOKAZATX, ^TO ^ISLO PRIWEDENNYH MATRIC IZ Bm;n, U KOTORYHFIKSIROWANNOE MNOVESTWO NOMEROW STROK MO]NOSTI k QWLQETSQ TESTOM,RAWNO 2k (2k 1) : : : (2k n + 1)2n(m k).5.8. pOLXZUQSX UNIWERSALXNYM ALGORITMOM, POSTROITX WSE TUPIKOWYE TESTY DLQ MATRIC 1), 2), 5), 6) ZADA^I 5.1.5.9. dOKAZATX, ^TO DLINA TUPIKOWOGO TESTA DLQ PRIWEDENNOJ MATRICY S n STOLBCAMI LEVIT W PREDELAH OT dlog2 ne DO (n 1) I ^TO OBEUKAZANNYE GRANICY DOSTIGA@TSQ.25.10. mOGUT LI STROKI NEKOTOROGO TUPIKOWOGO TESTA DLQ MATRICYM BYTX LINEJNO ZAWISIMY?5.11.
pUSTX MATRICA M IZ Bm;n IMEET W KAVDOJ SWOEJ STROKE NEBOLEE p, p > 0, EDINIC. dOKAZATX, ^TO DLINA MINIMALXNOGO TESTA DLQMATRICY M NE MENEE d 2np e.5.12. pUSTX PERWYJ STOLBEC PRIWEDENNOJ MATRICY M , M 2 Bm;n+1,SOSTOIT IZ ODNIH NULEJ (W SOOTWETSTWII S ZADA^EJ 5.5.5 L@BAQ MATRICAT -\KWIWALENTNA MATRICE S TAKIM VE ^ISLOM STOLBCOW, U KOTOROJ PERWYJ STOLBEC SOSTOIT TOLXKO IZ NULEJ), A EE OSTALXNYE STOLBCY MOVNORAZBITX NA s GRUPP TAK, ^TO PODMATRICA MATRICY M , POROVDAEMAQ~EREZ dae (SOOTWETSTWENNO bac) OBOZNA^AETSQ BLIVAJ[EE K a SWERHU (SOOTWETSTWENNO, SNIZU) CELOE ^ISLO.234L@BOJ IZ \TIH GRUPP, IMEET W KAVDOJ SWOEJ STROKE NE BOLEE ODNOJ EDINICY.
pOKAZATX, ^TO DLINA TESTA MATRICY M NE MENX[E, ^EM 2n=(s+1).x 6. tESTY DLQ KONTAKTNYH SHEM I SHEM IZ FUNKCIONALXNYH\LEMENTOWrASSMOTRIM OB]U@ MODELX NENADEVNYH SHEM PRIMENITELXNO K KONTAKTNYM SHEMAM (ks) I SHEMAM IZ FUNKCIONALXNYH \LEMENTOW (sf|).bUDEM S^ITATX, ^TO L@BOE NEISPRAWNOE SOSTOQNIE ks SWQZANO S RAZMYKANIEM (OBRYWOM) ODNOJ ^ASTI I ZAMYKANIEM DRUGOJ ^ASTI KONTAKTOW ks. pRI \TOM PREDPOLAGAETSQ, ^TO FUNKCIQ PROWODIMOSTI ZAMKNUTOGO (RAZOMKNUTOGO) KONTAKTA TOVDESTWENNO RAWNA EDINICE (SOOTWETSTWENNO NUL@).
w ^ASTNOSTI, ^EREZ ir;s, GDE r I s | CELYE NEOTRICATELXNYE ^ISLA, BUDEM OBOZNA^ATX ISTO^NIK NEISPRAWNOSTEJ, DOPUSKA@]IJ NE BOLEE, ^EM r, OBRYWOW I NE BOLEE, ^EM s, ZAMYKANIJ KONTAKTOWks ODNOWREMENNO. tEST DLQ ISTO^NIKA NEISPRAWNOSTEJ i0;1 (i1;0) NAZYWA@T EDINI^NYM TESTOM ZAMYKANIQ (SOOTWETSTWENNO, RAZMYKANIQ).pRI IZU^ENII NENADEVNOSTI sf|, W SWO@ O^EREDX, BUDEM S^ITATX,^TO KAVDOE IH NEISPRAWNOE SOSTOQNIE SWQZANO S WOZMOVNYM IZMENENIEMFUNKCIONIROWANIQ FUNKCIONALXNYH \LEMENTOW (f|) ILI WHODOW SHEMYPRI SOHRANENIII MESTNOSTI REALIZUEMYH IMI BULEWYH FUNKCIJ. pREDPOLAGAETSQ TAKVE, ^TO WSE SOEDINENIQ MEVDU WHODAMI, f| I WYHODAMIsf| NE NARU[A@TSQ I PEREDA@T INFORMACI@ BEZ ISKAVENIJ. pUSTX,W ^ASTNOSTI, sf| 0 QWLQETSQ NEISPRAWNYM SOSTOQNIEM sf| , xi |WHOD SHEMY , A E | EE f|, REALIZU@]IJ BULEWU FUNKCI@ '(u1; : : : ; uk ).bUDEM GOWORITX, ^TO W SOSTOQNII 0 NA WHODE xi IMEET MESTO KONSTANTNAQ NEISPRAWNOSTX TIPA , 2 f0; 1g, ESLI W SOOTWETSTWU@]EJxi WHODNOJ WER[INE 0 REALIZUETSQ BULEWA FUNKCIQ .
bUDEM GOWORITXTAKVE, ^TO W SOSTOQNII 0 NA j -M WHODE, 1 j k, (WYHODE) f| E SHEMY IMEET MESTO KONSTANTNAQ NEISPRAWNOSTX TIPA , 2 f0; 1g, ESLIf| E REALIZUET W 0 BULEWU FUNKCI@ '(u1; : : : ; uj 1; ; uj+1; : : : ; uk ) (SOOTWETSTWENNO ). mOVNO RASSMATRIWATX KONSTANTNYE NEISPRAWNOSTIRAZLI^NYH TIPOW, A TAKVE KONSTANTNYE NEISPRAWNOSTI KAK NA WHODAH,TAK I NA WYHODAH f|.pRI OPISANII ISTO^NIKA NEISPRAWNOSTEJ W ks ILI sf| ^ASTOWYDELQETSQ MNOVESTWO TEH \LEMENTOW ILI \UZLOW" , KOTORYE MOGUTWYHODITX IZ STROQ, I UKAZYWA@TSQ WOZMOVNYE NEISPRAWNYE SOSTOQNIQKAVDOGO IZ NIH.
pRI \TOM ISTO^NIK, DOPUSKA@]IJ L@BU@ KOMBINA35CI@ L@BYH NEISPRAWNYH SOSTOQNIJ DLQ L@BOGO PODMNOVESTWA (PODMNOVESTWA MO]NOSTI 1) \LEMENTOW MNOVESTWA , NAZYWAETSQ POLNYM(SOOTWETSTWENNO, EDINI^NYM) ISTO^NIKOM DLQ MNOVESTWA I ZADANNYH NEISPRAWNYH SOSTOQNIJ EGO \LEMENTOW, A SWQZANNYJ S NIM TEST |POLNYM (SOOTWETSTWENNO, EDINI^NYM) TESTOM. pO UMOL^ANI@ S^ITAETSQ, ^TO = .pRI POSTROENIII TESTOW DLQ ks I sf| MOVNO PRIMENQTX OB]IE METODY I ALGORITMY POSTROENIQ TESTOW DLQ TABLIC (SM. x 5). wO MNOGIHSLU^AQH PRI POSTROENII TESTOW DLQ DWUHPOL@SNOJ ks OT PEREMENNYH x1; : : : ; xn, REALIZU@]EJ BULEWU FUNKCI@ f , POLEZNO PRIMENQTX SOOTWETSTWIE MEVDU NABOROM , 2 B n, IZ Nf (Nf) I PROSTYMI CEPQMI(SOOTWETSTWENNO TUPIKOWYMI SE^ENIQMI), KOTORYE SOSTOQT IZ ZAMKNUTYH (SOOTWETSTWENNO RAZOMKNUTYH) NA NABORE KONTAKTOW I SOEDINQ@T(SOOTWETSTWENNO OTDELQ@T) POL@SA SHEMY (SM. ZADA^U 6.9).6.1.
tESTY DLQ KONTAKTNYH SHEM6.1. pOSTROITX WSE TUPIKOWYE TESTY DLQ ks NA RIS. 10 I ISTO^NIKANEISPRAWNOSTEJ, DOPUSKA@]EGO OBRYW ODNOGO IZ KONTAKTOW WIDA x.z xz xxxyyyyababy z yx z xrIS. 10.rIS. 11.6.2. pOSTROITX WSE TUPIKOWYEA) PROWERQ@]IEB) DIAGNOSTI^ESKIETESTY DLQ ks NA RIS. 11 I ISTO^NIKA NEISPRAWNOSTEJ, DOPUSKA@]EGORAZMYKANIE KONTAKTOW WIDA z, z, A TAKVE ZAMYKANIE KONTAKTA WIDA y,PRI^EM OB]EE ^ISLO NEISPRAWNYH KONTAKTOW NE MOVET BYTX BOLX[E 1.6.3.
pOSTROITX WSE TUPIKOWYEA) PROWERQ@]IEB) DIAGNOSTI^ESKIETESTY DLQ ks NA RIS. 12 I ISTO^NIKA NEISPRAWNOSTEJ, DOPUSKA@]EGOOBRYW ODNOGO KONTAKTA PEREMENNYH x; z.36axyyyzb azyzyxb azxyx zxybz y xy zrIS. 12.rIS. 14.rIS. 13.6.4. pOSTROITX WSE TUPIKOWYEA) PROWERQ@]IEB) DIAGNOSTI^ESKIETESTY DLQ ks NA RIS. 13 I ISTO^NIKA NEISPRAWNOSTEJ, DOPUSKA@]EGOODNU IZ SLEDU@]IH NEISPRAWNOSTEJ: OBRYW KONTAKTA z, OBRYW WYDELENNOGO KONTAKTA z I ZAMYKANIE WYDELENNOGO KONTAKTA y.6.5. pOSTROITX WSE TUPIKOWYEA) PROWERQ@]IEB) DIAGNOSTI^ESKIETESTY DLQ ks NA RIS. 14 S EDINI^NYM ISTO^NIKOM NEISPRAWNOSTEJ,DOPUSKA@]IM OBRYW KONTAKTOW WIDA z, z ILI ZAMYKANIE KONTAKTA WIDAy.6.6.
pOSTROITX WSE TUPIKOWYE TESTY DLQ ks NA RIS. 15 I ISTO^NIKANEISPRAWNOSTEJ, DOPUSKA@]EGO ZAMYKANIE ODNOGO IZ KONTAKTOW WIDAx; y; y. xzxazyyxzxzb azrIS. 15.xxyxzb ayrIS. 16.6.7. pOSTROITX WSE TUPIKOWYEzxxyzxbyrIS. 17.A) PROWERQ@]IEB) DIAGNOSTI^ESKIETESTY DLQ ks NA RIS. 16 I ISTO^NIKA NEISPRAWNOSTEJ, DOPUSKA@]EGOZAMYKANIE ODNOGO KONTAKTA PEREMENNYH y; z.6.8. pOSTROITX WSE TUPIKOWYEA) PROWERQ@]IE37B) DIAGNOSTI^ESKIETESTY DLQ ks NA RIS.
17 I ISTO^NIKA NEISPRAWNOSTEJ, DOPUSKA@]EGORAZMYKANIE ODNOGO KONTAKTA WIDA x, y ILI z.6.9. pUSTX W DWUHPOL@SNOJ ks OT PEREMENNYH x1; : : : ; xn DLQ L@BOGO NABORA = (1; : : :; n) IZ Nf NAJDETSQ EDINSTWENNAQ NE SODERVA]AQ KONTAKTOW WIDA x1 ; : : : ; xnn CEPX C, SOEDINQ@]AQ POL@SA. pUSTXISTO^NIK NEISPRAWNOSTEJ i DOPUSKAET OBRYW NE BOLEE, ^EM ODNOGO IZKONTAKTOW k1; : : :; ks 1 ks I POROVDAET PRI \TOM s OTLI^IMYH SOSTOQNIJ.1) dOKAZATX, ^TO MNOVESTWO NABOROW T , T B n, OBRAZUET PROWERQ@]IJ TEST DLQ (, i) TOGDA I TOLXKO TOGDA, KOGDA DLQ KAVDOGO KONTAKTAki, i = 1; : : :; (s 1), NAJDETSQ CEPX C, 2 T , PROHODQ]AQ ^EREZ NEGO.2) dOKAZATX, ^TO MNOVESTWO NABOROW T , T B n, OBRAZUET DIAGNOSTI^ESKIJ TEST DLQ (, i) TOGDA I TOLXKO TOGDA, KOGDA ONO OBRAZUET PROWERQ@]IJ TEST I DLQ L@BYH DWUH KONTAKTOW ki I kj , GDE 1 i < j (s 1),NAJDETSQ TAKOJ NABOR , 2 T , ^TO CEPX C PROHODIT ^EREZ ODIN IZ\TIH KONTAKTOW I NE PROHODIT ^EREZ DRUGOJ.6.10.
rASSMATRIWAETSQ POSTROENNAQ PO METODU KASKADOW ks Snr (SM.RIS. 18), REALIZU@]AQ \LEMENTARNU@ SIMMETRI^ESKU@ FUNKCI@ OT nPEREMENNYH S RABO^IM ^ISLOM r (T. E. FUNKCI@, PRINIMA@]U@ ZNA^ENIE 1 NA WSEH NABORAH IZ Brn I TOLXKO NA NIH).1) iSPOLXZUQ REZULXTAT ZADA^I 5.12, POLU^ITX NIVN@@ OCENKU WIDA2r(n r) DLQ DLINY EDINI^NOGO TESTA RAZMYKANIQ DANNOJ SHEMY.r+12) pOKAZATX, ^TO DLQ Snr SU]ESTWUET EDINI^NYJ DIAGNOSTI^ESKIJTEST RAZMYKANIQ DLINY, NE PREWOSHODQ]EJ 2n 2.6.11. nAJTI DLINU MINIMALXNOGO EDINI^NOGO PROWERQ@]EGO TESTADLQ RAZMYKANIQ KONTAKTOW W ks NA RIS.
19.6.12. rASSMATIWAETSQ ks NA RIS. 20.1) nAJTI DLINU MINIMALXNOGO EDINI^NOGO PROWERQ@]EGO TESTA DLQRAZMYKANIQ.2) pOSTROITX TAKOJ EDINI^NYJ TEST RAZMYKANIQ DLQ KONTAKTOWWIDA x1; : : : ; xn, x1; : : : ; xn, DLINA KOTOROGO NE PREWOSHODIT WELI^INYdlog2 ne + 2.138a x x11 x2x2 x3.. xrxr xr+1x2x2 x3x3 x4..
xr+1xr+1 xr+2xn r 1 xn r xn r 1 xn r xn r+1 xn r xn r+1 xn r xn r+1 xn r+2 xn r+1 xn r+2 ...... xn 2 xn 1 xn 2 xn 1 xn xn 1 xnb::: x x 2in 1x1xnabx2 x3xixi+1xn 1 xnx1 x2 : : : xi : : : xn 1 xnrIS. 19. x ::: x ::: xn 1i2x1xnax2n 2x2n 1 bxn+i 1 xn+ixn+1 xn+2x1 x2 : : : xi : : : xn 1 xnrIS. 20.::: ::: xn 1 xnxxi2x1xn 1 baxxxxxx1 2 x2 2 : : : i xi i : : : xn 1 n 1 xnrIS. 21.6.13.
nA OSNOWE KONTAKTNOGO DEREWA POSTROENA ks DLQ FUNKCIIf (x1; : : : ; xn) = x1 x2 : : : xn. dLQ \TOJ SHEMY NAJTI DLINU MINIMALXNOGO EDINI^NOGO TESTAA) RAZMYKANIQ,B) ZAMYKANIQ,W) KAK RAZMYKANIQ, TAK I ZAMYKANIQ.6.14. eDINI^NOJ SFEROJ S CENTROM W TO^KE , 2 Bn, NAZYWAETSQMNOVESTWO WSEH NABOROW KUBA B n, OTLI^A@]IHSQ OT NABORA TOLXKO WODNOJ KOORDINATE.dOKAZATX, ^TO DLINA MINIMALXNOGO EDINI^NOGO TESTA RAZMYKANIQDLQ PROIZWOLXNOJ ks, REALIZU@]EJ HARAKTERISTI^ESKU@ FUNKCI@EDINI^NOJ SFERY KUBA B n, NE MENX[E n.
pOKAVITE, ^TO UKAZANNAQ OCENKA DOSTIVIMA.x3 : : :x3x4x4 :::x4x5x5 :::.... . . . xr+2 : : :xr+2xr+3 xr+3 : : :: : : rISx. 18. 396.15. dOKAZATX, ^TO DLQ FUNKCII f (x1; : : : ; xn) = x1 x2 : : : xn NESU]ESTWUET ks OT n PEREMENNYH, IME@]EJ POLNYJ TEST DLINY MENX[E, ^EM 2n.6.16.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
