В.Б. Алексеев, А.А. Вороненко, С.А. Ложкин, Д.С. Романов и др. - Задачи по курсу «Основы кибернетики» (2002) (1132782), страница 4
Текст из файла (страница 4)
tOGDA KONTAKTOM S POMETKOJ IjBUDEM OBOZNA^ATX CEPO^KU IZ n POSLEDOWATELXNO SOEDINENNYH KONTAKTOW x1 ; x2 ; : : : ; xnn .rASSMOTRIM SISTEMU OBOB]ENNYH TOVDESTW:TI :! ?12ITII :I~!1212(ZDESX I~ | CEPO^KA, POLU^ENNAQ IZ CEPO^KI I PROIZWOLXNOJ PERESTANOWKOJ KONTAKTOW)TIII :I0 I1 I2n?1!2 : : : 2n:::122n1(ZDESX DOPUSKAETSQ SOWPADENIE POL@SOW I OTSUTSTWIE NEKOTORYH IZ NIH)TIV :1x2!x1 x24I0I2n?1.. I12ITV : 1TV I :TV II :3I 2I112II!2ITV III : p I 1 II :::p?1TIX : 1I33I 2I! 1 I!13I21!! 1 I2I2I I I1p3I:: :p?13I 24.2. wYWESTI IZ OSNOWNOJ SISTEMY TOVDESTW OBOB]ENNYE TOVDESTWATI { TIX .kANONI^ESKOJ KONTAKTNOJ SHEMOJ DLQ BULEWOJ FUNKCII f (x1; : : : ;xn), OTLI^NOJ OT KONSTANTY 0, NAZOWEM DWUHPOL@SNU@ KONTAKTNU@ SHEMU, SOSTOQ]U@ IZ CEPO^EK, SOEDINQ@]IH POL@SA I NE IME@]IH OB]IHWER[IN, KROME POL@SOW, I SOOTWETSTWU@]IH WSEM KON_@NKCIQM SOWER[ENNOJ DIZ_@NKTIWNOJ NORMALXNOJ FORMY FUNKCII f .
dLQ KONSTANTY0 KANONI^ESKOJ KONTAKTNOJ SHEMOJ NAZOWEM KONTAKTNU@ SHEMU, SOSTOQ]U@ IZ DWUH IZOLIROWANNYH POL@SOW. kANONI^ESKOJ MNOGOPOL@SNOJKONTAKTNOJ SHEMOJ NAZOWEM OB_EDINENIE NEPERESEKA@]IHSQ PO WNUTRENNIM WER[INAM DWUHPOL@SNYH KANONI^ESKIH KONTAKTNYH SHEM, POSTROENNYH DLQ KAVDOJ PARY POL@SOW.25pRIWESTI KONTAKTNU@ SHEMU, W KOTOROJ IME@TSQ TOLXKO PEREMENNYEx1; : : : ; xn, K KANONI^ESKOMU WIDU MOVNO PRI POMO]I SLEDU@]EGO ALGORITMA ([16]).1.
kAVDYJ KONTAKT S POMETKOJ xi ISHODNOJ KONTAKTNOJ SHEMY ZAMENQEM NA DWUHPOL@SNU@ PODSHEMU W SOOTWETSTWII S TOVDESTWOMTIV , W?iiKOTOROM Ij | CEPO^KI KONTAKTOW WIDA x1 ; : : : ; xi?1 ; xi+1 ; : : : ; xnn .2. pUSTX a | PROIZWOLXNAQ WER[INA ISHODNOJ KONTAKTNOJ SHEMY, NEQWLQ@]AQSQ POL@SOM I IZOLIROWANNOJ WER[INOJ.1) pRIMENQQ TOVDESTWO TV III DLQ KAVDOJ ZWEZDY S CENTROM W WER[INE a DOBIWAEMSQ TOGO, ^TOBY IZ WER[INY a ISHODILI TOLXKO RAZLI^NYECEPO^KI KONTAKTOW.2) pO TOVDESTWU TIII WER[INU a WMESTE SO WSEMI CEPO^KAMI KONTAKTOW, ISHODQ]IMI IZ NEE, UDALQEM.pOWTORQQ PP.
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( =WER[IN, REBER I SWQZNYHnW + nR + nK(mod 2), GDE nW; nR; nK | ^ISLOPKOMPONENT 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, t(6m), 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^ _f (y1; : : : ; yp) =(ys);(4:1)(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@111001 1110001CC1A0100 10 010010100001000CC0A110110 01101011010010100111011000 01 001100000110000011001B12) M = B@01B0BB3) M = B 1@101B0BB04) M = BB0B@100110010CC0CC0CC1A100101011013201001110011110110101110CC0CC0A101B0B5) M = B0B@1111001 1111000111000CC1CC1A100100 110010011000001101B1BB6) M = B 0@010110101CC0CC0A15.2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
