В.Б. Алексеев, А.А. Вороненко, С.А. Ложкин и др. - Задачи по курсу Основы кибернетики (2002) (1124121), страница 4
Текст из файла (страница 4)
1) I 2) DLQ KAVDOJ WER[INY, NE QWLQ@]EJSQ POL@SOM,POLU^IM KONTAKTNU@ SHEMU, W KOTOROJ CEPO^KI KONTAKTOW SOEDINQ@TTOLXKO POL@SA.3. w SLU^AE, ESLI KONTAKTNAQ SHEMA IMEET BOLEE DWUH POL@SOW, WYPOLNQEM TRANZITIWNOE ZAMYKANIE PO TOVDESTWU TIX .4. pOWTORQ@]IESQ CEPO^KI KONTAKTOW, SOEDINQ@]IE ODNU I TU VEPARU POL@SOW, UBIRAEM PO TOVDESTWU TV I .5. pO TOVDESTWU TI UBIRAEM IZOLIROWANNYE WER[INY.4.3. pRIWESTI K KANONI^ESKOMU WIDU SLEDU@]IE KONTAKTNYE SHEMY:x y z x11)2)11yzxzyyzzx22621+13)1xxxy2yy34.4. wYQSNITX, \KWIWALENTNY LI DANNYE KONTAKTNYE SHEMY, PRIWODQKAVDU@ IZ NIH K KANONI^ESKOMU WIDU:yx 1)12)2z1 zxxyy2y11 xxy2zzzy24.5.
1) pUSTX | KONTAKTNAQ SHEMA OT PEREMENNYH x1; : : : ; xn, =(a1; : : : ; an) | WEKTOR IZ 0 I 1. pUSTX | GRAF, POLU^AEMYJ IZ SHEMY, ESLI OSTAWITX TOLXKO WSE KONTAKTY WIDA x1 ; : : : ; xnn . pUSTX R( =nW + nR + nK(mod 2), GDE nW; nR; nK | ^ISLOWER[IN, REBER I SWQZNYHPKOMPONENT W GRAFE , I PUSTX R() = 2Bn R()(mod 2).dOKAZATX, ^TO ESLI KONTAKTNAQ SHEMA 0 OT PEREMENNYH x1; : : : ; xn;xn+1 POLU^ENA IZ KONTAKTNOJ SHEMY OT PEREMENNYH x1; : : : ; xn; xn+1W REZULXTATE PRIMENENIQ L@BOGO IZ TOVDESTW t1 t5, t6(m), m n, TOR() = R(0).2) oSNOWYWAQSX NA UTWERVDENII P. 1) DOKAZATX, ^TO KONTAKTNYE SHE1MYx1 xyz 21,xyz2(2)NELXZQ PREOBRAZOWATX DRUG W DRUGA PRI POMO]I TOVDESTW t1 t5; t(1)6 ; t6 .273) oSNOWYWAQSX NA UTWERVDENII P.
1) DOKAZATX, ^TO TOVDESTWO t6(m+1)(m)NE WYWODITSQ IZ TOVDESTW t1 t5; t(1)6 ; : : : ; t6 .4) dOKAZATX, ^TO IZ MNOVESTWA TOVDESTW t1 t5; t6(m) (m = 1; 2; : : :)NELXZQ WYDELITX KONE^NU@ POLNU@ SISTEMU TOVDESTW DLQ KONTAKTNYHSHEM.5) dOKAZATX, ^TO W KLASSE WSEH KONTAKTNYH SHEM NE SU]ESTWUET KONE^NOJ POLNOJ SISTEMY TOVDESTW.28~ASTXSISTEM4.nADEVNOSTX I KONTROLX UPRAWLQ@]IHdLQ UPRAWLQ@]EJ SISTEMY (SHEMY) BEZ PAMQTI, FUNKCIONIROWANIE KOTOROJ OPISYWAETSQ DISKRETNOJ FUNKCIEJ ILI, W OB]EM SLU^AE,WEKTOR-FUNKCIEJ, MOVET BYTX SFORMULIROWANA SLEDU@]AQ MODELX (SM.[12, 6]), W RAMKAH KOTOROJ OBY^NO RASSMATRIWA@TSQ WOPROSY EE NADEVNOSTI. pREDPOLAGAETSQ, ^TO IMEETSQ NEKOTORYJ \WNE[NIJ" ISTO^NIKNEISPRAWNOSTEJ (ISTO^NIK POMEH) i, POD DEJSTWIEM KOTOROGO L@BAQRASSMATRIWAEMAQ SHEMA MOVET PEREHODITX W ODNO IZ SWOIH \NEISPRAWNYH SOSTOQNIJ" (SHEM), OPREDELQEMYH \TIM ISTO^NIKOM.
pUSTX SHEME = (1), REALIZU@]EJ (WEKTOR-) FUNKCI@ F = F (1) = (f1(1); : : : ; fm(1))OT WHODNYH PEREMENNYH x = (x1; : : : ; xn), I ISTO^NIKU NEISPRAWNOSTEJi SOOTWETSTWU@T \NEISPRAWNYE" SOSTOQNIQ (SHEMY) (2); : : : ; (t), GDESHEMA (i), i = 2; : : :; t, REALIZUET FUNKCI@ F (i) = (f1(i); : : : ; fm(i)) OT PEREMENNYH x. pRI \TOM WSE SOSTOQNIQ (KAK ISPRAWNOE = (1), TAK INEISPRAWNYE (2); : : :; (t)) RAZBIWA@TSQ NA KLASSY (FUNKCIONALXNO) NEOTLI^IMYH SOSTOQNIJ, TO ESTX KLASSY \KWIWALENTNOSTI PO OTNO[ENI@RAWENSTWA REALIZUEMYH FUNKCIJ, I RASSMATRIWA@TSQ DALEE S TO^NOSTX@ DO NEOTLI^IMOSTI.
w DALXNEJ[EM, GOWORQ O NENADEVNOJ SHEME ,BUDEM IMETX W WIDU UKAZANNU@ WY[E MODELX M = (; i) I (ILI) SOOTWETSTWU@]EE EJ MNOVESTWO SHEM WMESTE S TEMI FUNKCIQMI, KOTORYEONI REALIZU@T.x 5. zADA^A KONTROLQ UPRAWLQ@]IH SISTEM. tESTY DLQ TAB-LICrASSMOTRIM MATEMATI^ESKU@ MODELX ZADA^I KONTROLQ UPRAWLQ@]IHSISTEM, SWQZANNU@ S PONQTIEM TESTA DLQ TABLICY.dLQ CELYH ^ISEL a I b, GDE a b, ^EREZ ba; be BUDEM OBOZNA^ATX MNOVESTWO CELYH ^ISEL OTREZKA [a; b], TO ESTX MNOVESTWO CELYH i TAKIH,^TO a i b. dLQ MNOVESTWA A I NATURALXNYH n; m ^EREZ An;m BUDEMOBOZNA^ATX MNOVESTWO MATRIC S n STROKAMI, m STOLBCAMI I \LEMENTAMI IZ A.
pRI \TOM BUDEM S^ITATX, ^TO Am, TO ESTX m-Q DEKARTOWASTEPENX MNOVESTWA A, SOWPADAET S A1;m. dLQ MATRICY M IZ MNOVESTWA An;m EE PODMATRICU, RASPOLOVENNU@ W STROKAH S NOMERAMI IZ MNOVESTWA I I W STOLBCAH S NOMERAMI IZ MNOVESTWA J , GDE I b1; ne IJ b1; me, BUDEM OBOZNA^ATX ^EREZ M < I; J >. pRI \TOM PODMAT29RICU WIDA M < I; b1; me > (M < b1; ne; J >) BUDEM OBOZNA^ATX ^EREZM < I > (SOOTWETSTWENNO M (J )). mATRICA M NAZYWAETSQ PRIWEDENNOJ,ESLI WSE EE STOLBCY RAZLI^NY.pUSTX M = (, i) | UKAZANNAQ WY[E MODELX NENADEVNOJ SHEMY S SOSTOQNIQMI = (1); (2); : : : ; (t) I FUNKCIQMI F =F (1); F (2); : : : ; F (t) OT PEREMENNYH x = (x1; : : : ; xn).
pUSTX, DALEE,FUNKCII F (1); F (2); : : : ; F (t) OPREDELENY NA MNOVESTWE NABOROW N =f1; : : : ; pg I PRINIMA@T ZNA^ENIQ IZ MNOVESTWA (NABOROW) A =f1; : : : ; ag.sOPOSTAWIM RASSMATRIWAEMOJ ZADA^E KONTROLQ MATRICU M , M 2p;tA , GDE M < s; j >= F (j)(s) DLQ WSEH s, s 2 b1; pe, I j , j 2 b1; te.
zAMETIM, ^TO ESLI M (i) = M (j ), TO SOSTOQNIQ S NOMERAMI i I j NEWOZMOVNOOTLI^ITX DRUG OT DRUGA NA OSNOWE DANNYH NABOROW. w TAKIH SLU^AQHWSE SOSTOQNIQ, KAK PRAWILO, RAZBIWA@TSQ NA KLASSY \KWIWALENTNOSTIPO OTNO[ENI@ NEOTLI^IMOSTI, A ZADA^A KONTROLQ STAWITSQ I RE[AETSQDLQ \TIH KLASSOW. zAMETIM TAKVE, ^TO KAVDOMU KLASSU NEOTLI^IMOSTISOSTOQNIJ SOOTWETSTWUET GRUPPA ODINAKOWYH STOLBCOW MATRICY M , AZADA^E KONTROLQ DLQ \TIH KLASSOW | PRIWEDENNAQ MATRICA M 0, MNOVESTWO STOLBCOW KOTOROJ SOWPADAET S MNOVESTWOM RAZLI^NYH STOLBCOWMATRICY M .pUSTX, DALEE, ZADANA CELX KONTROLQ, TO ESTX UKAZANO MNOVESTWO N ,SOSTOQ]EE IZ TEH NEUPORQDO^ENNYH PAR RAZLI^NYH ^ISEL OTREZKA b1; te,DLQ KOTORYH PARY SOSTOQNIJ (STOLBCOW MATRICY M ) S SOOTWETSTWU@]IMI NOMERAMI NEOBHODIMO OTLI^ATX DRUG OT DRUGA, SRAWNIWAQ ZNA^ENIQ, RASPOLOVENNYE W TEH ILI INYH STROKAH DANNOJ PARY STOLBCOW.w ^ASTNOSTI, ESLI N SOSTOIT IZ WSEH PAR UKAZANNOGO WIDA, TO CELX@KONTROLQ QWLQETSQ DIAGNOSTIKA SHEMY, A ESLI N = f(1; 2); : : :; (1; t)g,TO | PROWERKA ISPRAWNOSTI SHEMY.
mNOVESTWO T , T b1; pe, NAZYWAETSQ TESTOM DLQ MATRICY M OTNOSITELXNO MNOVESTWA N , ILI,INA^E, TESTOM DLQ (M; N ), ESLI DLQ L@BOJ PARY (i; j ) IZ N SU]ESTWUET s, s 2 T , TAKOE, ^TO M < s; i >=6 M < s; j >. mO]NOSTX TESTANAZYWAETSQ TAKVE EGO DLINOJ.zAMETIM, ^TO MNOVESTWO b1; pe WSEGDA OBRAZUET TEST. tEST, KOTORYJPERESTAET BYTX TESTOM PRI UDALENII L@BOGO SWOEGO \LEMENTA, NAZYWAETSQ TUPIKOWYM, A TEST, KOTORYJ IMEET MINIMALXNU@ MO]NOSTX, |MINIMALXNYM. w TOM SLU^AE, KOGDA CELX@ KONTROLQ QWLQETSQ DIAGNOSTIKA SHEMY (PROWERKA ISPRAWNOSTI SHEMY), TEST NAZYWAETSQ DIAGNOS30TI^ESKIM (SOOTWETSTWENNO PROWERQ@]IM).dLQ PRIWEDENNOJ MATRICY M , M 2 Ap;t, I CELI KONTROLQ NOPREDELIM BULEWU FUNKCI@ TESTA f (y1; : : : ; yp) SLEDU@]IM OBRAZOM:f (1; : : : ; p) = 1 TOGDA I TOLXKO TOGDA, KOGDA MNOVESTWO T , SOSTOQ]EE IZ TEH ^ISEL s, s 2 b1; pe, DLQ KOTORYH s = 1, OBRAZUET TEST DLQMATRICY M OTNOSITELXNO N .tEOREMA.
fUNKCIQ TESTA f (y1; : : : ; yp) DLQ MATRICY M , M 2 Ap;t, ICELI KONTROLQ N MOVET BYTX ZADANA knf^ _ys);(4:1)(f (y1; : : : ; yp) =(i;j )2N1spM < s; i >6=M < s; j >PRI^EM KAVDOE SLAGAEMOE WIDA ys : : : ysr SOKRA]ENNOJ dnf FUNKCIIf (y1; : : : ; yp) SOOTWETSTWUET TUPIKOWOMU TESTU T = fs1; : : : ; sr g IOBRATNO.nA DANNOJ TEOREME OSNOWAN SLEDU@]IJ UNIWERSALXNYJ ALGORITM POSTROENIQ WSEH TUPIKOWYH TESTOW DLQ MATRICY M OTNOSITELXNO CELIKONTROLQ N :1) WYPISYWAEM DLQ FUNKCII TESTA knf WIDA (4:1);2) RASKRYWAQ W NEJ SKOBKI, PRIWODQ \PODOBNYE" SLAGAEMYE (SM.
x 3)I PRIMENQQ PRAWILO POGLO]ENIQ x1 _ x1x2 = x1, POLU^AEM SOKRA]ENNU@dnf FUNKCII TESTA;3) SOPOSTAWLQEM KAVDOJ \LEMENTARNOJ KON_@NKCII SOKRA]ENNOJdnf TUPIKOWYJ TEST.1pRIMER.00B0pUSTX M = B@111 01 1101CC1 A.0dLQ POSTROENIQ WSEH TUPIKOWYH DIAGNOSTI^ESKIH TESTOW MATRICYM POSTROIM knf WIDA (4:1):(y1 _ y2 _ y3) (y2 _ y4) (y1 _ y3 _ y4):rASKRYWAQ W \TOJ knf SKOBKI, PRIWODQ PODOBNYE SLAGAEMYE I PRIMENQQ PRAWILO POGLO]ENIQ, POLU^IM SOKRA]ENNU@ dnf DLQ FUNKCIITESTA:y1y2 _ y1y4 _ y2y3 _ y2y4 _ y3y4:31tUPIKOWYMI DIAGNOSTI^ESKIMI TESTAMI MATRICY M QWLQ@TSQ MNOVESTWAf1; 2g; f1; 4g; f2; 3g; f2; 4g; f3; 4g:w DALXNEJ[EM PO UMOL^ANI@ BUDEM S^ITATX, ^TO MATRICA | \TOMATRICA IZ NULEJ I EDINIC, A TEST | DIAGNOSTI^ESKIJ TEST.
mNOVESTWO NOMEROW STROK MATRICY M , KOTOROE SOOTWETSTWUET PODMATRICE BEZNULEWYH STOLBCOW, NAZYWAETSQ EE POKRYTIEM. pOKRYTIE S^ITAETSQ TUPIKOWYM (KRAT^AJ[IM), ESLI UDALENIE IZ NEGO L@BOGO NOMERA STROKIPRIWODIT K MNOVESTWU NOMEROW STROK, NE QWLQ@]EMUSQ POKRYTIEM (SODERVIT MINIMALXNOE ^ISLO NOMEROW STROK). mO]NOSTX MINIMALXNOGOPOKRYTIQ NAZYWAETSQ GLUBINOJ MATRICY.5.1. nAJTI GLUBINU MATRICY M :00B01) M = B@1101 01 1110001CC1A0100 10 010010100001000CC0A110110 01101011010010100111011000 01 001100000110000011001B12) M = B@01BB 03) M = BB@ 1101BB 0B04) M = BBB 0@100110010CC0CC0CCA1100101011013201001110011110110101110CC0CC0A101BB 05) M = BB@ 01111001 1111000111000CC1CC1A100100 110010011000001101BB 16) M = BB@ 0010110101CC0CC0A15.2.
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 01 1 A ; TO0 1GRAFI^ESKOJ UPORQDO^ENNOSTX@.
nAPRIMER, ESLI M = @ 0000 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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
