В.Б. Алексеев, А.А. Вороненко, С.А. Ложкин, Д.С. Романов и др. - Задачи по курсу «Основы кибернетики» (2002) (1132782), страница 9
Текст из файла (страница 9)
f(100); (111)g, f(001); (010); (111)g, f(001); (010); (100)g.6.7. A) f(000); (011)g, f(000); (111)g; B) f(000); (011); (101)g, f(000);(101); (111)g.6.8. A) f(010); (101)g, f(100); (110)g, f(010); (100); (111)g; B) f(010);(100); (101)g, f(010); (100); (110)g, f(010); (100); (111)g, f(010); (101);(110)g, f(100); (101); (110)g.6.9. uKAZANIE.
dOKAZATELXSTWA PROWODQTSQ OT PROTIWNOGO.6.10. 1) uKAZANIE. nAJDITE r GRUPP PO (n ? r) KONTAKTOW W KAVDOJ,EDINI^NYE OBRYWY KOTORYH DA@T MATRICU, UDOWLETWORQ@]U@ (POSLEINWERTIROWANIQ) USLOWIQM ZADA^I 5.12; 2) (r. n. tONOQN [21]). rASSMOTRITE PRI n 2r MNOVESTWO NABOROW, POROVDAEMYH SLEDU@]IMI SLOWAMI DLINY n W ALFAWITE f0; 1g: 0s 1r 0n?s ?r , 1s 0n1r?s , 1s [01]r?s 0n?2r+s ,0s [01]s 0n?2r?s , 0n?2r+s [01]r?s 1s (s1 = 0; n ? r, s2 = 1; r ? 1, s3 =0; r ? 1, s4 = 1; n ? 2r, s5 = 1; r ? 2).6.11.
n + 1.6.12. 1) 2. 2) uKAZANIE. iSPOLXZUJTE METOD DIHOTOMII, T. E. DELENIQSHEMY NA DWE ^ASTI.6.13. A) 2n?1, B) 2n?1, W) 2n.1444551558223336.14. uKAZANIE. rASSMOTRITE NABORY EDINI^NOJ SFERY I EE CENTR.dOSTIVIMOSTX OCENKI PROILL@STRIRUJTE NA SHEME, POSTROENNOJ PO METODU KASKADOW.6.15. (h. a. mADATQN [15]). uKAZANIE. dOKAVITE, ^TO SREDI NEISPRAWNYH SHEM NAJDUTSQ SHEMY, REALIZU@]IE OBE KONSTANTY, A TAKVESHEMY, REALIZU@]IE ILI x1 x2 xnn , ILI x1 _x2 _ _xnn DLQ L@BOGONABORA (1; 2; : : : ; n).6.16.
1) uKAZANIE. rASSMOTRITE IZOLIROWANNYJ BLOK \TOJ SHEMY. 2)A) 2 PRI ^ETNYH n, 3 PRI NE^ETNYH n; B) 4; W) 6 PRI ^ETNYH n, 7 PRINE^ETNYH n. 3) (r. n. tONOQN [20]). uKAZANIE. iSPOLXZUJTE METOD DIHOTOMII. dLINA TESTA NE BOLEE, ^EM NA KONSTANTU, OTLI^AETSQ OT log2 n.4) A) (r. n. tONOQN [20]). uKAZANIE. iSPOLXZUJTE METOD DIHOTOMII. B)uKAZANIE.
iSPOLXZUJTE METOD DELENIQ SHEMY NA 4 ^ASTI.6.17. (n. p. rEDXKIN [6]). uKAZANIE. rASSMOTRITE ks, REALIZU@]U@FUNKCI@ f (x1; : : : ; xn) I POSTROENNU@ PO FORMULE (Kf (x1 _ x1)) (Df (x1 _x1)), GDE Kf I Df | KON_@NKTIWNAQ I DIZ_@NKTIWNAQ SOWER[ENNYENORMALXNYE FORMY FUNKCII f .6.18. 1) A) f(00); (01); (11)g, ^ISLO TESTOW | 2; B) f(001); (010); (011);(110); (111)g (PORQDOK PEREMENNYH | x; y; q0), ^ISLO TESTOW | 12. 2)f(001); (011); (110)g (PORQDOK PEREMENNYH | x; y; q0). 3) f(1000); (0001);(0110)g (PORQDOK PEREMENNYH | a; b; x; y).
4) f(0000); (0111); (1111)g.6.19. 2) uKAZANIE. rASSMOTRITE SHEMU NA RIS. 25 I ZAMETXTE, ^TONEISPRAWNOSTX TIPA 0 NA WYHODE TRETXEGO SLEWA INWERTORA W NIVNEMRQDU INWERTOROW OBNARUVIWAETSQ LI[X NA NABORE (0001), NE WHODQ]EMW TEST IZ ZADA^I 6.18.4.6.20. (n. p. rEDXKIN [6]). uKAZANIE. iSKOMAQ SHEMA STROITSQ PO INDUKCII IZ BLOKOW, KAVDYJ BLOK PODOBEN SHEME NA RIS. 22 A) BEZ WYHODAz1. tEST IZ ^ETYREH NABOROW: (0; 0; 0; : : :; 0), (1; 0; 0; : : :; 0), (0; 1; 1; : : :; 1),(1; 1; 1; : : :; 1).6.21. 1) wWEDEM OBOZNA^ENIE:10 01B11BM =B11B@ 011111010000 011101000111211010001111120 10011B01 C11 CCBCBC11 C;N=11:CBC@ 01 A11 A0100mATRICA TESTA T RAZMEROM 5 2n PRI \TOM BUDET IMETX WID T =59(M 0MM : : : MN ), GDE MATRICA M 0 POLU^AETSQ IZ MATRICY M WYBRASYWANIEM NUVNOGO KOLI^ESTWA PERWYH STOLBCOW (PORQDOK PEREMENNYH |x1; y1; x2; y2; : : : ; xn; yn).
uKAZANIE. dLQ POSTROENIQ TESTA ISPOLXZU@TSQ TABLICY NEISPRAWNOSTEJ IZ ZADA^I 6.18.1. pRI \TOM SU]ESTWENNYSLEDU@]IE FAKTY. l@BAQ NEISPRAWNOSTX BLOKA S NOMEROM n WIDA 1SHEMY n OBNARUVIWAETSQ PO ANALIZU FUNKCII NEISPRAWNOSTI NA EGOWTOROM WYHODE (T. E. NA WYHODE SHEMY zn). eSLI NEISPRAWNOSTX W BLOKE SNOMEROM i, 1 < i < n, NE OBNARUVIWAETSQ NA EGO WTOROM WYHODE (T. E.
NAWYHODE SHEMY zi), TO NA NABORAH TESTA FUNKCIQ NEISPRAWNOSTI, REALIZUEMAQ NA WYHODE SHEMY zi?1, OTLI^IMA OT WSEH FUNKCIJ NEISPRAWNOSTI, WOZNIKA@]IH NA \TOM WYHODE PRI WSEWOZMOVNYH NEISPRAWNOSTQH WBLOKE S NOMEROM i ? 1. wSE NEISPRAWNOSTI W i-M BLOKE (1 i n), NEOTLI^IMYE PO ANALIZU FUNKCII NEISPRAWNOSTI NA EGO WTOROM WYHODE(T. E. NA WYHODE SHEMY zi), OTLI^A@TSQ NA NABORAH TESTA PO ANALIZUFUNKCII NEISPRAWNOSTI NA WYHODE SHEMY zi?1. nIVNQQ OCENKA DLINYTESTA SLEDUET IZ ZADA^I 6.18.1 DLQ BLOKA, WY^ISLQ@]EGO DWA STAR[IHRAZRQDA SUMMY.2) nABORY TESTA POROVDA@TSQ SLOWAMI DLINY 2n SLEDU@]EGO WIDA: [00]i?111[01]n?i, [11]i?100[01]n?i (i = 1; n), PORQDOK PEREMENNYH |xn; yn; : : : ; x2; y2; x1; y1. uKAZANIE.
dLQ POSTROENIQ TESTA ISPOLXZUETSQTABLICA NEISPRAWNOSTEJ IZ ZADA^I 6.18.2. nIVNQQ OCENKA SLEDUET IZKONSTRUKTIWNYH SOOBRAVENIJ.3) nABORY TESTA POROVDA@TSQ SLOWAMI DLINY 2n SLEDU@]EGOWIDA: [01]n, 10[01]n?1, 00[10]n?1, 01[10]n?1, PORQDOK PEREMENNYH |an; bn; xn?1; yn?1; xn?2; yn?2; : : : ; x2; y2; x1; y1. uKAZANIE. dLQ POSTROENIQTESTA ISPOLXZUETSQ TABLICA NEISPRAWNOSTEJ IZ ZADA^I 6.18.3.6.22. (S.
M. Reddy [23]). uKAZANIE. rASSMOTRITE RAZLOVENIE BULEWOJ FUNKCII f (x1; : : : ; xn) W POLINOM vEGALKINA, REALIZUQ CEPO^KAMI FUNKCIONALXNYH \LEMENTOW KAK MONOTONNYE KON_@NKCII,TAK I SUMMU PO MODUL@ DWA. pRI \TOM NA ODIN IZ WHODOW \LEMENTA SUMMY PO MODUL@ DWA, NAIBOLEE UDALENNOGO OT WYHODA SHEMY, PODAETSQ WYHOD CEPO^KI, REALIZU@]EJ OTLI^NU@ OT KONSTANTYMONOTONNU@ KON_@NKCI@ NAIMENX[EJ DLINY (PUSTX \TA KON_@NKCIQ IMEET WID xi : : : xis ).
tOGDA MNOVESTWO NABOROW f(0; : : : ; 0);(1; : : :; 1); (0; 1; : : :; 1); f(1; 0; 1; : : :; 1); : : :; (1; : : :; 1; 0); (0; 1; : : :; 1);(0; : : :; 0; 1; 0; : : :; 0; 1; 0; : : :; 0) (W POSLEDNEM NABORE ROWNO s EDINIC, STOQ]IH NA MESTAH PEREMENNYH xi ; : : : ; xis ) MO]NOSTI (n + 3) OBRAZUET1160EDINI^NYJ PROWERQ@]IJ TEST DLQ \TOJ SHEMY.6.23. (w. n. nOSKOW [17]). uKAZANIE. wERHNQQ OCENKA O^EWIDNA. dLQDOKAZATELXSTWA NIVNEJ RASSMOTRITE FUNKCI@ x1x2 : : : xn _ x1x2 : : : xn.6.24. (i. a.
~EGIS, s. w. qBLONSKIJ [22]). uKAZANIE. iSPOLXZUJTEASIMPTOTI^ESKI NAILU^[IJ METOD SINTEZA SHEM.6.25. uKAZANIE. dOKAZATELXSTWA PROWODQTSQ OT PROTIWNOGO.7.1. 1) sLEDUET IZ (6.1){(6.3). 2) dOSTATO^NO ISPOLXZOWATX (6.5). 3)dOSTATO^NO WYRAZITX () ^EREZ WEROQTNOSTI (Ei; ).7.2. 1)5 (M) = (M) = 41 : 2) (M) = (M) = 167 : 3) (M) =(M) = 9 :7.3. 1) p = 13 : 2) p = 14 :7.4. 1) dA. 2) dA.7.5. uKAZANIQ.
1) rEALIZUJTE SKOLX UGODNO NADEVNO FUNKCI@ xjy. 2)rEALIZUJTE SKOLX UGODNO NADEVNO FUNKCII x y I 1.k PARAGRAFU 77.6. 1) dOKAZATELXSTWO PROWODITSQ OT PROTIWNOGO. 2) iSPOLXZUJTEks, POSTROENNU@ PO SOWER[ENNOJ dnf FUNKCII x1 x2, A TAKVE REZULXTAT ZADA^I 7.6.1.7.7. uKAZANIE. iSPOLXZUJTE OPISANNOE W PREDISLOWII \KWIWALENTNOEPREOBRAZOWANIE SWQZNYH MNOGOPOL@SNYH PODSHEM, SOSTOQ]IH IZ KONTAKTOW ODNOGO WIDA.7.8. 1) uKAZANIE. aNALOGI^NO 7.7. 2) wOSPOLXZUJTESX TEM, ^TO SHEMAREALIZUET FUNKCI@ x1(x4 _ x3) _ x2, A TAKVE REZULXTATOM ZADA^I 7.6.1.7.9.
sHEMY PREDSTAWLENY NA RIS. 36 I 37 SOOTWETSTWENNO.7.10. (w. m. rABINOWI^ [18]). uKAZANIE. k SHEME NA RIS. 21 NADODOBAWITX 4 KONTAKTA x1, x1, xn, xn TAK, ^TOBY PERWYE DWA BYLI BYINCIDENTNY POL@SU b (NO NE POL@SU a), WTORYE DWA | POL@SU a (NONE POL@SU b) SHEMY, I PRI \TOM KAVDYJ IZ NOWYH KONTAKTOW DOLVENBYTX SMEVEN S IME@]IMSQ W SHEME PROTIWOPOLOVNYM KONTAKTOM TOJVE PEREMENNOJ.7.11. A) uKAZANIE. iSPOLXZUJTE REZULXTAT ZADA^I 7.10.
B) w PODSHEME LINEJNOJ FUNKCII POMENQJTE MESTAMI PEREMENNYE x1 I x2, A DALEEUSOWER[ENSTWUJTE RE[ENIE IZ PUNKTA A) TEHNIKOJ, UPOMQNUTOJ W UKAZANII K ZADA^E 7.7.61x1ax2x3x3x2x2x3x1x1b a x3x2 x2x3x2x1 x2 x3 ax3 x1 xx2x 3b2 bx3 x1 x3x1 x1x2rIS. 36.rIS. 37.rIS. 38.7.12.
sHEMA PREDSTAWLENA NA RIS. 38. uKAZANIE. nIVNQQ OCENKA SLOVNOSTI SLEDUET IZ ZADA^I 7.6.1.7.13. uKAZANIE. iSPOLXZUJTE PARALLELXNOE (POSLEDOWATELXNOE) SOEDINENIE SHEM, NA KOTORYH DOSTIGA@TSQ Lk (f ); : : :; Lks (f ).7.14. (e. w. wALENTINOW [13]). uKAZANIE. A) wERHNQQ OCENKA. iSPOLXZUJTE PRI n = 3 SHEMY NA RIS. 21 I IZ RE[ENIQ ZADA^I 7.10, DALEEWOSPOLXZUJTESX REZULXTATOM ZADA^I 7.13.
B) wERHNQQ OCENKA. iSPOLXZUJTE SHEMU NA RIS. 17 (PRI n = 3 I r = 2) I SHEMU NA RIS. 36, DALEEWOSPOLXZUJTESX REZULXTATOM ZADA^I 7.13. nIVNIE OCENKI SLEDU@T IZZADA^I 7.6.1.7.15. (a. i. rYBKO [19]). uKAZANIE. pUSTX (a1; b1), (a2; b2); : : :, (as; bs)| UKAZANNYE W USLOWII ZADA^I s PAR WER[IN. dOSTROJTE K SHEME DWA IZOMORFNYH KONTAKTNYH DEREWA TAK, ^TO LISTXQMI PERWOGO DEREWA QWLQ@TSQ WER[INY a1; a2; : : : ; as, LISTXQMI WTOROGO | WER[INYb1; b2; : : : ; bs, WSE WNUTRENNIE WER[INY DEREWXEW QWLQ@TSQ NOWYMI, I DLQL@BOGO i, i 2 f1; 2; : : :; sg, PROWODIMOSTX MEVDU KORNEM PERWOGO DEREWAI ai RAWNA PROWODIMOSTI MEVDU KORNEM WTOROGO DEREWA I bi.162sPISOK LITERATURY[1] aHO a., hOPKROFT d., uLXMAN d., pOSTROENIE I ANALIZ WY^ISLITELXNYH ALGORITMOW, m.: mIR, 1979, 536 S.[2] gAWRILOW g.
p., sAPOVENKO a. a., zADA^I I UPRAVNENIQ PO KURSUDISKRETNOJ MATEMATIKI, m.: nAUKA, 1992, 408 S.[3] g\RI m., dVONSON d., wY^ISLITELXNYE MA[INY I TRUDNORE[AEMYE ZADA^I, m.: mIR, 1982, 416 S.[4] kIBERNETI^ESKIJ SBORNIK (nOWAQ SERIQ), N 12, m.: mIR, 1975, S. 510.[5] lUPANOW o.
b., aSIMPTOTI^ESKIE OCENKI SLOVNOSTI UPRAWLQ@]IHSISTEM, m.: iZD-WO mgu, 1984, 137 S.[6] rEDXKIN n. p., nADEVNOSTX I DIAGNOSTIKA SHEM, m.: iZD-WO mgu,1992, 192 S.[7] sAPOVENKO a. a., nEKOTORYE WOPROSY SLOVNOSTI ALGORITMOW, m.:maks pRESS, 2001, 46 S.[8] qBLONSKIJ s. w., o NEWOZMOVNOSTI \LIMINACII PEREBORA WSEHFUNKCIJ IZ P2 PRI RE[ENII NEKOTORYH ZADA^ TEORII SHEM // dansssr, 124, 1, 1959, S.
44-47.[9] qBLONSKIJ s. w., oB ALGORITMI^ESKIH TRUDNOSTQH SINTEZA MINIMALXNYH KONTAKTNYH SHEM // pROBLEMY KIBERNETIKI, m.: nAUKA,wYP. 2, 1959, S. 75-121.[10] qBLONSKIJ s. w., wWEDENIE W DISKRETNU@ MATEMATIKU, m.: nAUKA,1986, 384 S.[11] qBLONSKIJ s. w., |KWIWALENTNYE PREOBRAZOWANIQ UPRAWLQ@]IHSISTEM. mETODI^ESKAQ RAZRABOTKA PO KURSU \|LEMENTY KIBERNETIKI", m.: iZD-WO mgu, 1986, 40 S.[12] qBLONSKIJ s.
w., nADEVNOSTX UPRAWLQ@]IH SISTEM. mETODI^ESKAQ RAZRABOTKA PO KURSU \oSNOWY KIBERNETIKI", m.: iZD-WO mgu,1991, 40 S.63dOPOLNITELXNAQ LITERATURA[13] wALENTINOW e. w., o SLOVNOSTI BULEWYH FUNKCIJ, OT TREH PEREMENNYH W KLASSE KONTAKTNYH SHEM, KORREKTIRU@]IH OBRYWY //tRUDY II mEVDUNARODNOJ KONFERENCII \dISKRETNYE MODELI W TEORII UPRAWLQ@]IH SISTEM" (kRASNOWIDOWO, 13-18 I@NQ 1997 G.),m.: dIALOG mgu, 1997, S. 10.[14] lINDON r.
k., tOVDESTWA W KONE^NYH ALGEBRAH // kIBERNETI^ESKIJSBORNIK, WYP. 1, 1960, S. 246-248.[15] mADATQN h. a., pOLNYJ TEST DLQ BESPOWTORNYH KONTAKTNYHSHEM // pROBLEMY KIBERNETIKI, WYP. 23, m.: nAUKA, 1970, S. 103118.[16] mURSKIJ w. l., oB \KWIWALENTNYH PREOBRAZOWANIQH KONTAKTNYHSHEM // sB. \pROBLEMY KIBERNETIKI", WYP. 5, m.: fIZMATGIZ, 1961,S. 61-76.[17] nOSKOW w. n., o DLINAH MINIMALXNYH EDINI^NYH DIAGNOSTI^ESKIHTESTOW, KONTROLIRU@]IH RABOTU WHODOW LOGI^ESKIH SHEM // dISKRETNYJ ANALIZ, WYP. 32, nOWOSIBIRSK: iZD-WO im so an sssr,1978, S. 40-52.[18] rABINOWI^ w. m., o SAMOKORREKTIRU@]IHSQ KONTAKTNYH SHEMAHDLQ S^ET^IKA ^ETNOSTI // pROBLEMY KIBERNETIKI, WYP. 17, m.:nAUKA, 1966, S.
227-231.[19] rYBKO a. i., o SLOVNOSTI SAMOKORREKTIRU@]IHSQ KONTAKTNYH SHEM, DOPUSKA@]IH TESTIROWANIE // pROBLEMY KIBERNETIKI,wYP. 37, m.: nAUKA, 1980, S. 139-153.[20] tONOQN r. n., o EDINI^NYH TESTAH DLQ KONTAKTNYH SHEM, REALIZU@]IH LINEJNYE FUNKCII // iZW. an aRM. ssr, T. VI, N 1, 1971,S. 61-66.[21] tONOQN r.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
