В.Б. Алексеев, А.А. Вороненко, С.А. Ложкин, Д.С. Романов и др. - Задачи по курсу «Основы кибернетики» (2002) (1132782), страница 6
Текст из файла (страница 6)
xr+1xr+1 xr+2xn?r?1 xn?r xn?r?1 xn?r xn?r+1 xn?r xn?r+1 xn?r xn?r+1 xn?r+2xn?r+1 xn?r+2 ...... xn?2 xn?1 xn?2 xn?1 xn xn?1 xnb::: x x 2in?1x1xnax2 x3xixi+1xn?1 xnbx1 x2 : : : xi : : : xn?1 xnrIS. 19. x ::: x ::: x2in?1x1xnaxn+1 xn+2xn+i?1 xn+ix2n?2x2n?1 bx1 x2 : : : xi : : : xn?1 xnrIS.
20.x2 : : : xi : : : xn?1 xnx1xn?1 baxxxxxx1 2 x2 2 : : : i xi i : : : xn?1 n? 1 xnrIS. 21.6.13. nA OSNOWE KONTAKTNOGO DEREWA POSTROENA ks DLQ FUNKCIIf (x1; : : : ; xn) = x1 x2 : : : xn. dLQ \TOJ SHEMY NAJTI DLINU MINIMALXNOGO EDINI^NOGO TESTAA) RAZMYKANIQ,B) ZAMYKANIQ,W) KAK RAZMYKANIQ, TAK I ZAMYKANIQ.6.14. eDINI^NOJ SFEROJ S CENTROM W TO^KE , 2 Bn, NAZYWAETSQMNOVESTWO WSEH NABOROW KUBA B n, OTLI^A@]IHSQ OT NABORA TOLXKO WODNOJ KOORDINATE.dOKAZATX, ^TO DLINA MINIMALXNOGO EDINI^NOGO TESTA RAZMYKANIQDLQ PROIZWOLXNOJ ks, REALIZU@]EJ HARAKTERISTI^ESKU@ FUNKCI@EDINI^NOJ SFERY KUBA B n, NE MENX[E n. pOKAVITE, ^TO UKAZANNAQ OCENKA DOSTIVIMA.x3 : : :x3x4x4 :::x4x5x5:::....
. . . xr+2 : : :xr+2xr+3x r+3 : : :: : : rISx. 18. 396.15. dOKAZATX, ^TO DLQ FUNKCII f (x1; : : : ; xn) = x1 x2 : : : xn NESU]ESTWUET ks OT n PEREMENNYH, IME@]EJ POLNYJ TEST DLINY MENX[E, ^EM 2n.6.16. 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 A0xyq QQAA&_q1 :qqA A AA?@@1 A? A@@ A&A?2z0 :q11q12A_ A?1zA)zB)x1 y1x2: : :xn y2: : :ynn : 0n?1???z0 z1 z10 z2 : : : : : z?nW)rIS.
22. sHEMA SUMMATORA nx yq0Q qq^ 0 :q Q AQAQA A&A_AAAAA&AA?AA ?A_ A 00?qA)qqqqqqsHEMA ^ n :x1 y1x2: : :xn y2: : :ynqqqq^ 0z?0rIS. 23.41q^ n?1B)qz?2abxq~ 2 :qyqqA_ AA&AA_ AA&AA)a0 ? ?b0sHEMA ~ n :anbnxn?y1n?1 xn?2x1yn?2yqqqqq~ 2rIS. 24.B):::qq:::~ n?1?a1 ?b1q12) 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 SS___A A A A_ AAAAGO KONSTANTNYE NEISPRAWNOSTI NA WYHODAH f| SHEMY SUMMATORA n PRI n 3A?A?A?A?AHAAA(RIS.
22 W)), RAWNA 5.HH C HC2) 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|AXXAX AAPPXXXSSPXPS 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, ^TO SHEMA NAHODITSQ W SOSTOQNII (i), GDE 0 i 1 IPt =TOGOi=1 i 1. wWEDEM SLEDU@]IE WELI^INY, HARAKTERIZU@]IE NENADEVNOSTX SHEMY W MODELI M:Xj ;(6:1) (M) =F (j) 6= FjtX2 (M; ) =F(j )2 6 F ( )jtj ;(6:2)( )=GDE 2 N , A ZATEM POLOVIM(M) = max (M; ); 2N(6:3)(6:4)qM(x1; : : : ; xn) = (M; (x1; : : : ; xn)):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)).xxq 1qqqq nXXXXXXXXXXXXXXXXQQ112QQQQ@@Ei??@?0?A)12B)"1rIS.
26.?zAMETIM, ^TO H (0) = 0, H 12 = 12 , ^TO PERWYE DWE PROIZWOD45 NYE? FUNKCIIH?(") NA OTREZKE 0; 12 NEOTRICATELXNY, PRI^EM H 0(0) =H 00 21 = 0 I H 0 12 > 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:!1zAMETIM TAKVE, ^TO sf| (k) SODERVIT 3k PODSHEM WIDA I 1 + 3 +k + 3k?1 = 3 2?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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
