В.Б. Алексеев, А.А. Вороненко, С.А. Ложкин и др. - Задачи по курсу Основы кибернетики (2002) (1124121), страница 6
Текст из файла (страница 6)
rASSMATRIWAETSQ POSTROENNAQ PO METODU KASKADOW ks n, REALIZU@]AQ LINEJNU@ FUNKCI@ x1 x2 xn 1 PRI n 3 (SM.RIS. 21).1) dOKAZATX \KWIWALENTNOSTX EDINI^NYH ZAMYKANIJ ODNOIMENNYHKONTAKTOW.2) nAJTI DLINU MINIMALXNOGO EDINI^NOGO PROWERQ@]EGO TESTAA) ZAMYKANIQ,B) RAZMYKANIQ,W) KAK RAZMYKANIQ, TAK I ZAMYKANIQ.3) pOSTROITX ASIMPTOTI^ESKI MINIMALXNYJ EDINI^NYJ TEST ZAMYKANIQ.4) pOSTROITX EDINI^NYJ TEST RAZMYKANIQ, DLINA KOTOROGO NE PREWOSHODITA) 2 log2 n + 7,B) 23 log2 n + 10.6.17. dOKAZATX, ^TO L@BU@ BULEWU FUNKCI@ MOVNO REALIZOWATX ks,DOPUSKA@]EJ EDINSTWENNYJ POLNYJ PROWERQ@]IJ TEST, SOSTOQ]IJ IZWSEH NABOROW.6.2.
tESTY DLQ SHEM IZ FUNKCIONALXNYH \LEMENTOW6.18. 1) pOSTROITX MINIMALXNYJ EDINI^NYJ DIAGNOSTI^ESKIJ TESTOTNOSITELXNO KONSTANTNYH NEISPRAWNOSTEJ NA WYHODAH f| SHEMY NARIS. 22 A), B)3 I UKAZATX ^ISLO TAKIH TESTOW.2) pOSTROITX MINIMALXNYJ EDINI^NYJ PROWERQ@]IJ TEST OTNOSITELXNO KONSTANTNYH NEISPRAWNOSTEJ NA WYHODAH f| SHEMY NARIS. 23 A).3) pOSTROITX MINIMALXNYJ EDINI^NYJ PROWERQ@]IJ TEST OTNOSITELXNO KONSTANTNYH NEISPRAWNOSTEJ NA WYHODAH f| SHEMY NARIS. 24 A).pRI IZOBRAVENII SHEM IZ FUNKCIONALXNYH \LEMENTOW W NASTOQ]EM POSOBII DEJSTWU@T PRAWILA:1) OB]IMI TO^KAMI PROWODNIKOW MOGUT QWLQTXSQ LI[X TO^KI WYHODOW FUNKCIONALXNYH \LEMENTOW,2) WHODY KAVDOGO FUNKCIONALXNOGO \LEMENTA UPORQDO^ENY SLEWA NAPRAWO.3404) pOSTROITX MINIMALXNYJ PROWERQ@]IJ TEST OTNOSITELXNO KONSTANTNYH NEISPRAWNOSTEJ NA WYHODAH TEH f| SHEMY NA RIS.
25, KOTORYE SODERVAT WHODY SHEMY.6.19. 1) pOKAZATX, ^TO TEST, PROWERQ@]IJ KONSTANTNYE NEISPRAWNOSTI NA WYHODAH f|, SREDI WHODOW KOTORYH ESTX LIBO WHODY SHEMY,LIBO WETWQ]IESQ WYHODY FUNKCIONALXNYH \LEMENTOW, QWLQETSQ PROWE-RQ@]IM TESTOM DLQ KONSTANTNYH NEISPRAWNOSTEJ NA WYHODAH WSEH f|SHEMY (PRI \TOM PREDPOLAGAETSQ, ^TO BAZIS NE SODERVIT f|, REALIZU@]IH KONSTANTY).x yQQ AQQAAx yq0&_q1 :qqA A AA@@1 A A@@ A&A?2z0 :q11q12A_ A?1zA)zB)x1 y1x2: : :xn y2: : :ynn : 0n 1z?0 z?1 z10 z?2 : : : : : z?nW)rIS. 22.
sHEMA SUMMATORA n0x yqQ qq^ 0 :qqqqqq Q A QQAA A_A&AAAAA&AAAAA_ A 00?qA)qsHEMA ^ n :x1 y1x2: : :xn y2: : :ynq?qq^ 0z0rIS. 23.41q^ nB)qq1z?2abxq~ 2 :qyqqA_ AA&AA_ AA&A0 ? ?0A)a bsHEMA ~ n :anbnxn y1n 1 xn 2x1yn 2y1qqqqq~ 2rIS. 24.B):::qq:::q~ n 1?a1 ?b12) pOKAZATX, ^TO sf| NA RIS. 25 QWLQETSQ PRIMEROM SHEMY, DLQ KOTOROJ EDINI^NYJ TEST, PROWERQ@]IJ KONSTANTNYE NEISPRAWNOSTI NAWYHODAH LI[X TEH f|, SREDI WHODOW KOTORYH ESTX WHODY SHEMY, NEQWLQETSQ EDINI^NYM PROWERQ@]IM TESTOM DLQ KONSTANTNYH NEISPRAWNOSTEJ NA WYHODAH WSEH f| SHEMY.6.20. rEALIZOWATX LINEJNU@ FUNKCI@x1 x2 x3 x4x1 x2 : : :xn sf| W STANDARTNOM BAZISE,A A A A qqqqDOPUSKA@]EJ EDINI^NYJ TEST IZ ^ETYREHNABOROW, PROWERQ@]IJ KONSTANTNYE NEISPRAWNOSTI NA WYHODAH f| SHEMY.A A A 6.21. 1) dOKAZATX, ^TO DLINA MINIMALXAAASSNOGO EDINI^NOGO TESTA, DIAGNOSTIRU@]E SSA_ A_ A_ A_ AAAAGO KONSTANTNYE NEISPRAWNOSTI NA WYHODAH f| SHEMY SUMMATORA n PRI n 3A A A A AAAAHH C(RIS.
22 W)), RAWNA 5. HHC2) sHEMA ^ n NA RIS. 23 B) IMEET SLOVA_ A_ AANOSTX 4n 3 I WY^ISLQET STAR[IJ RAZSS _A RQD z0 SUMMY z0z1 : : : zn DWOI^NYH ^ISELA?zx1 : : : xn I y1 : : : yn (SHEMA ^ 1 PREDSTAWLQETrIS. 25.SOBOJ KON_@NKTOR). dOKAZATX, ^TO DLINAMINIMALXNOGO EDINI^NOGO TESTA, PROWERQ@]EGO KONSTANTNYE NEISPRAWNOSTI NA WYHODAH f| SHEMY ^ n, RAWNA2n.3) pOSTROITX EDINI^NYJ TEST, PROWERQ@]IJ KONSTANTNYE NEISPRAWNOSTI NA WYHODAH f| SHEMY ~ n NA RIS. 24 B), IME@]IJ DLINU NE BOLEE 4.6.22. pOKAZATX SU]ESTWOWANIE TAKOGO BAZISA IZ f|, W KOTOROM DLQL@BOJ BULEWOJ FUNKCII n PEREMENNYH SU]ESTWUET SHEMA, DOPUSKA@]AQEDINI^NYJ PROWERQ@]IJ KONSTANTNYE NEISPRAWNOSTI NA WYHODAH f|AXX XAAPAXPXXSSP XPS S PA_ A_ A_ AAA42TEST DLINY, NE PREWOSHODQ]EJ n + 3.6.23. dOKAZATX, ^TO DLINA POLNOGO PROWERQ@]EGO TESTA DLQ WHODOWn-WHODOWOJ SHEMY NE PREWOSHODIT 2n.
pOKAZATX NEULU^[AEMOSTX PREDYDU]EJ OCENKI DLQ NEKOTOROJ FUNKCII.6.24. pOKAZATX, ^TO, NA^INAQ S NEKOTOROGO n, L@BAQ BULEWA FUNKCIQ nPEREMENNYH OBLADAET SHEMOJ, DOPUSKA@]EJ NETRIWIALXNYJ EDINI^NYJTEST, DIAGNOSTIRU@]IJ KONSTANTNYE NEISPRAWNOSTI NA WYHODAH f|.6.25. pOKAVITE, ^TO MINIMALXNYJ PROWERQ@]IJ EDINI^NYE KONSTANTNYE NEISPRAWNOSTI NA WYHODAH f| TEST DLQ PROIZWOLXNOGO DE[IFRATORA (DLQ PROIZWOLXNOGO UNIWERSALXNOGO MNOGOPOL@SNIKA) SOSTOIT IZ WSEH NABOROW.43x 7. oCENKA NADEVNOSTI SHEM. sAMOKORREKTIRU@]IESQ SHE-MY.dLQ OPREDELENIQ UROWNQ NADEVNOSTI SHEMY ^ASTO PRIMENQETSQ WEROQTNOSTNYJ PODHOD (SM., NAPRIMER, [12, 6]).
pUSTX M = (; i) |MODELX NENADEVNOJ SHEMY OT PEREMENNYH x1; : : : ; xn, IME@]EJ SOSTOQNIQ = (1); (2); : : : ; (t), W KOTORYH REALIZU@TSQ FUNKCII F =F (1); F (2); : : : ; F (t) SOOTWETSTWENNO, OPREDELENNYE NA MNOVESTWE NABOROWN = f1; : : : ; pg. pUSTX, DALEE, IZWESTNA I RAWNA i, i = 1; : : : ; t, WEROQTNOSTX TOGO, ^TO SHEMA NAHODITSQ W SOSTOQNII (i), GDE 0 i 1 IPt = 1.
wWEDEM SLEDU@]IE WELI^INY, HARAKTERIZU@]IE NENADEVi=1 iNOSTX SHEMY W MODELI M:Xj ;(6:1) (M) =F (j) 6= Fjt2 (M; ) =XF (j) ( ) 6= F ( )2j tj ;GDE 2 N , A ZATEM POLOVIM(M) = max (M; ); 2N(6:2)(6:3)qM(x1; : : : ; xn) = (M; (x1; : : : ; xn)):(6:4)zAMETIM, ^TO WELI^INA (M) ( (M; )) ZADAET WEROQTNOSTX TOGO, ^TOSHEMA REALIZUET FUNKCI@, NE RAWNU@ F (SOOTWETSTWENNO NE RAWNU@F NA NABORE ), I PO\TOMU(M) (M) p(M);(6:5)OTKUDA SLEDUET, W ^ASTNOSTI, ^TO (M) = 0 TOGDA I TOLXKO TOGDA, KOGDA (M) = 0.
sHEMA S^ITAETSQ ABSOL@TNO NADEVNOJ W MODELI M,ESLI (M) = 0 (ILI (M) = 0). |TO OZNA^AET, ^TO WSE SOSTOQNIQ SHEMY, IME@]IE POLOVITELXNU@ WEROQTNOSTX, \KWIWALENTNY . fUNKCIQqM(x1; : : : ; xn) NAZYWAETSQ FUNKCIEJ WEROQTNOSTI NEPRAWILXNOGO SRABATYWANIQ SHEMY . w DALXNEJ[EM, PRI ZAPISI WWEDENNYH WELI^INWMESTO PARY M = (; i) BUDEM PISATX PROSTO , ESLI IZ KONTEKSTAQSNO, KAKOJ ISTO^NIK NEISPRAWNOSTEJ IMEETSQ W WIDU.rASSMOTRIM WEROQTNOSTNYJ PODHOD NA PRIMERE NENADEVNYH sf|NAD BAZISOM b = fEigbi=1, GDE f| Ei REALIZUET BULEWU FUNKCI@44'i(u1; : : : ; uki ).
pUSTX DLQ KAVDOGO i, i = 1; : : : ; b, IZWESTNO RASPREDEk LENIE REVIMOW RABOTY f| Ei, TO ESTX DLQ KAVDOGO j , j = 1; : : : ; 22 i ,IZWESTNA I RAWNA i;j WEROQTNOSTX TOGO, ^TO f| Ei REALIZUET j -@ BULEWUFUNKCI@ OT BULEWYH PEREMENNYH u1; : : : ; uki (ESLI S^ITATX, ^TO WSE BULEWY FUNKCII OT PEREMENNYH u1; : : : ; uki UPORQDO^ENY W SOOTWETSTWII SNOMERAMI IH STOLBCOW ZNA^ENIJ).
pRI NAHOVDENII NENADEVNOSTI SHEMY NAD BAZISOM b BUDEM S^ITATX, ^TO WSE EE f| PEREHODQT W SWOISOSTOQNIQ NEZAWISIMO DRUG OT DRUGA I ^TO L@BOE SOSTOQNIE sf| OPREDELQETSQ SOSTOQNIQMI f| (SM. x 6). w SOOTWETSTWII S \TIM NAOSNOWE WWEDENNYH WY[E SOOTNO[ENIJ (6:1)-(6:4) MOVNO NAJTI ZNA^ENIQNENADEVNOSTI () I () DLQ sf| , A TAKVE RASPREDELENIE REVIMOWEE RABOTY I FUNKCI@ q(x1; : : : ; xn).s^ITAETSQ, ^TO FUNKCIQ f (x1; : : : ; xn) DOPUSKAET SKOLX UGODNO NADEVNU@ REALIZACI@ W BAZISE b, ESLI DLQ L@BOGO ", " > 0, SU]ESTWUET sf| NAD b, KOTORAQ REALIZUET f I DLQ KOTOROJ () < ".
pOWY[ENIE NADEVNOSTI PRI REALIZACII fal f (x1; : : : ; xn) WOZMOVNO, ESLI W BAZISEb IMEETSQ ABSOL@TNO NADEVNYJ f| Ei, REALIZU@]IJ FUNKCI@ GOLOSOWANIQ m(x1; x2; x3) = x1x2 _ x1x3 _ x2x3 (SM. [12]). dEJSTWITELXNO, ESLIsf| REALIZUET f I () = ", TO DLQ NENADEVNOSTI sf| (1), POKAZANNOJ NA RIS. 26 A), KOTORAQ TOVE REALIZUET f , IMEET MESTO RAWENSTWO((1)) = H (") = 3"2 2"3(GRAFIK FUNKCII = H (") POKAZAN NA RIS. 26 B)).xx1qXqqq nXqXXXXXXXXXXXX XXQQQQQQ@@ i@E1120?12B)A)"1rIS.
26.zAMETIM, ^TO H (0) = 0, H 21 = 12 , ^TO PERWYE DWE PROIZWOD45 NYE FUNKCIIH (") NA OTREZKE 0; 21 NEOTRICATELXNY, PRI^EM H 0(0) =H 00 12 = 0 I H 0 21 > 0, H 00(0) > 0, I ^TO ((1)) < ", ESLI " < 12 . pO\TOMU, REKURSIWNO PRIMENQQ UKAZANNU@ PROCEDURU POWY[ENIQ NADEVNOSTI K sf| (k), REZULXTATOM KOTOROJ QWLQETSQ sf| (k+1), k = 1; 2; :::,POSTROIM POSLEDOWATELXNOSTX sf| (1), (2); :::, (k); :::, REALIZU@]IHf , DLQ KOTOROJ((k)) = H (((k 1))) k!0:!1(k) SODERVIT 3k PODSHEM WIDA I 1 + 3 +zAMETIM TAKVE,^TOsf| + 3k 1 = 3k2 1 f| Ei.aNALOGI^NYE POSTROENIQ I OCENKI PRIMENIMY I DLQ POWY[ENIQ NENADEVNOSTI sf|.7.1. 1) dOKAZATX, ^TO (M) = (M) TOGDA I TOLXKO TOGDA, KOGDA DLQM SU]ESTWUET PROWERQ@]IJ TEST DLINY 1.2) dOKAZATX, ^TO FUNKCIQ f DOPUSKAET SKOLX UGODNO NADEVNU@ REALIZACI@ W BAZISE b TOGDA I TOLXKO TOGDA, KOGDA DLQ L@BOGO ", " > 0,SU]ESTWUET sf| NAD b, KOTORAQ REALIZUET f I DLQ KOTOROJ () < ".3) dOKAZATX, ^TO DLQ WY^ISLENIQ NENADEVNOSTI () W SOOTWETSTWIIS (6:3) DLQ sf| NAD BAZISOM b DOSTATO^NO ZNATX NENADEVNOSTI WIDA (Ei; ) DLQ WSEH f| Ei BAZISA b I WSEH NABOROW IZ B ki , i = 1; : : : ; b.7.2.
nIVE UKAZANA sf| I RASPREDELENIQ REVIMOW RABOTY EE NENADEVNYH f|. nAJTI RASPREDELENIE REVIMOW RABOTY sf| , A ZATEMWY^ISLITX (), () I FUNKCI@ q.1) | sf| NA RIS. 22 A), GDE KON_@NKTOR RABOTAET ABSOL@TNO NADEVNO, A RASPREDELENIQ REVIMOW RABOTYu1 _ u2 I INWER u DIZ_@NKTORATORA u1 IME@T, SOOTWETSTWENNO, WID 1 _2 u2 u1 1 u2 I u31 u11 .334 42) | sf| NA RIS. 23 A), GDE DIZ_@NKTOR RABOTAET ABSOL@TNONADEVNOREVIMOW RABOTY KON_@NKTORA u1&u2 IMEET u ,&AuRASPREDELENIEWID 1 3 2 u11 .443) | sf| NA RIS. 24 A), GDE KON_@NKTOR RABOTAET ABSOL@TNONADEVNOREVIMOW RABOTY DIZ_@NKTORA u1 _ u2 IMEET u , _A uRASPREDELENIEWID 1 2 2 u1&1 u2 .337.3.
1) pUSTX W sf| NA RIS. 22 A) DIZ_@NKTOR RABOTAET ABSOL@TNO NADEVNO, A RASPREDELENIQ REVIMOW RABOTY KON_@NKTORA u1&u2 I46 u &u01 p p12 u 0 I 31 1 .INWERTORA u1 IME@T, SOOTWETSTWENNO, WID4 4iZWESTNO, ^TO WEROQTNOSTX TAKOGO FUNKCIONIROWANIQ SHEMY, PRI KOTOROM NA OBOIH WYHODAH SHEMY REALIZU@TSQ TOVDESTWENNYE NULI, RAWNA16 . nAJTI p.2) pUSTX RASPREDELENIQ REVIMOW RABOTY KON_@NKTORA u1&u2 I DIZ_@NKTORA u1 _ u2 W sf| NA RIS.
23 A) IME@T WID u11&up2 1p u _u x I 1 2, SOOTWETSTWENNO. iZWESTNO, ^TO WEROQTNOSTX TAKOGO2313FUNKCIONIROWANIQ SHEMY, PRI KOTOROM NA WYHODE REALIZUETSQ TOVDESTWENNAQ EDINICA, RAWNA 38 . nAJTI p.7.4. pUSTX BAZIS b SOSTOIT IZ f|, REALIZU@]EGO FUNKCI@ GOLOSOWANIQ, KOTORYJ RABOTAET ABSOL@TNO NADEVNO, I KON_@NKTORA u &u 1 u1&u2,RASPREDELENIE REVIMOW RABOTY KOTOROGO IMEET WID 1 2 2 1 .331) dOSTATO^NO LI 40 FUNKCIONALXNYH \LEMENTOW, ^TOBY REALIZOWATXFUNKCI@ u1&u2 c NENADEVNOSTX@ NE BOLEE 0:1?2) dOSTATO^NO LI 400 FUNKCIONALXNYH \LEMENTOW, ^TOBY REALIZOWATX FUNKCI@ u1&u2 c NENADEVNOSTX@ NE BOLEE 0:002?7.5. nIVE PRIWEDENY RASPREDELENIQ REVIMOW RABOTY f| Ei, i =1; :::; b, NENADEVNOGO BAZISA b. pOKAVITE, ^TO W DANNOM BAZISE WOZMOVNASKOLX UGODNO NADEVNAQPROIZWOLXNOJ FUNKCII.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
