В.Б. Алексеев, А.А. Вороненко, С.А. Ложкин, Д.С. Романов и др. - Задачи по курсу «Основы кибернетики» (2002) (1132782), страница 5
Текст из файла (страница 5)
nAJTI DLINU MINIMALXNOGO TESTA DLQ MATRICY M , MNOVESTWOSTOLBCOW KOTOROJ ESTX11) B n;2) BknS, k > 0;3)B2nk ;0kSn=24) Bkn Bkn+1, k 0.5.3. ~EREZ M (2) BUDEM OBOZNA^ATX MATRICU, SOSTAWLENNU@ IZ SUMMPO MODUL@ 2 WSEWOZMOVNYH PAR STOLBCOW MATRICY M , WYPISANNYH WPORQDKE WOZRASTANIQ NOMEROW \TIH PAR W SOOTWETSTWII0 S IH LEKSIKO1 1 1 0GRAFI^ESKOJ UPORQDO^ENNOSTX@. nAPRIMER, ESLI M = @ 0 1 1 A ; TO0 0 100 1 11M (2) = @ 1 1 0 A :0 1 1dOKAZATX, ^TO MNOVESTWO NOMEROW STROK MATRICY M QWLQETSQ TESTOM(MINIMALXNYM, TUPIKOWYM TESTOM) TOGDA I TOLXKO TOGDA, KOGDA ONOQWLQETSQ POKRYTIEM (KRAT^AJ[IM, TUPIKOWYM POKRYTIEM) MATRICYM (2).5.4. oBOB]ITX REZULXTAT ZADA^I 5.3 NA SLU^AJ PROIZWOLXNOJ CELIKONTROLQ N .5.5.
dWE MATRICY M I L S ODINAKOWYM ^ISLOM STROK NAZYWA@TSQ T \KWIWALENTNYMI, ESLI MNOVESTWO NOMEROW STROK MATRICY M QWLQETSQ~EREZ Bkn , GDE 0 k]IH ROWNO k EDINIC.1 n, OBOZNA^AETSQ MNOVESTWO WSEH NABOROW KUBA B n, SODERVA33TESTOM TOGDA I TOLXKO TOGDA, KOGDA ONO QWLQETSQ TESTOM MATRICY L.wYQSNITX, QWLQ@TSQ LI T -\KWIWALENTNYMI MATRICY M I L, ESLI1) M POLU^ENA IZ L PERESTANOWKOJ STOLBCOW;2) M POLU^ENA IZ L PERESTANOWKOJ STROK;3) M POLU^ENA IZ L UDALENIEM WSEH STOLBCOW, SPLO[X SOSTOQ]IH IZ0 (1);4) M POLU^ENA IZ L WY^ERKIWANIEM k ? 1 STOLBCOW IZ k ODINAKOWYH;5) M POLU^ENA SLOVENIEM PO MODUL@ 2 KAVDOGO STOLBCA MATRICY LS ZADANNYM STOLBCOM ~;6) M POLU^ENA IZ L SLOVENIEM PO MODUL@ 2 KAVDOJ STROKI MATRICYL S ZADANNOJ STROKOJ ~;7) M POLU^ENA IZ L ZAMENOJ WSEH 0 NA 1 I WSEH 1 NA 0;8) M SOSTOIT IZ WSEH LINEJNYH KOMBINACIJ STOLBCOW MATRICY L;9) M = L(2) (OPREDELENIE SM.
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 xxxabayybyyy 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. 13.rIS. 14.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.
xzxazyyzxxzb 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 x2x2x3.. xrxr xr+1x2x2 x3x3x4..
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
