В.Б. Алексеев, А.А. Вороненко, С.А. Ложкин, Д.С. Романов и др. - Задачи по курсу «Основы кибернетики» (2002) (1132782), страница 8
Текст из файла (страница 8)
uKAZANIE. wOSPOLXZOWATXSQ TOVDESTWAMI: (x_y)(x_z) = (x_yz);ESLI FORMULY Y I Z NEVZAWISQTOT x, TO (x _ Y )(x _ Z ) RAWNO Y _ Z ;Vy1y2 : : : yk _ z1z2 : : : zl = 1ik 1jl(yi _ zj ).2.8. sM. [7]2.9. wOSPOLXZUJTESX SWODIMOSTQMI ZADA^I 2.8.2.10.
1) dOKAVITE, ^TO ZADA^A wyp POLINOMIALXNO SWODITSQ K RAS-SMATRIWAEMOJ ZADA^E;2) DOKAVITE, ^TO ZADA^A 3-wyp POLINOMIALXNO SWODITSQ K RASSMATRIWAEMOJ ZADA^E.2.11. 1), 3) zADA^I PRINADLEVAT KLASSU P;2) NP-POLNAQ ZADA^A. uKAZANIE. pUSTX D | NEKOTORAQ dnf OT PEREMENNYH x1; : : : ; xn. pREOBRAZUEM EE W dnf D0, D0, REALIZU@]U@ FUNKCI@ t D1 _ x1 y1 _ : : : _ xn yn, GDE PEREMENNAQ t NE WSTRE^AETSQ W dnfD, A dnf D1 POLU^ENA IZ dnf D ZAMENOJ KAVDOJ BUKWY WIDA xi NAPEREMENNU@ yi. tOGDA dnf D OBRA]AETSQ W NOLX NA NEKOTOROM NABORETOGDA I TOGDA, KOGDA SU]ESTWU@T DWA PROTIWOPOLOVNYH NABORA, NA KOTORYH dnf D0 OBRA]AETSQ W NOLX.
kROME TOGO, POSTROITX dnf D0 POdnf D NA DETERMINIROWANNOJ mt MOVNO ZA POLINOMIALXNOE WREMQ.53tAKIM OBRAZOM, NP-POLNAQ ZADA^A O SU]ESTWOWANII NABORA, OBRA]A@]EGO dnf W NOLX (SM. ZADA^U 2.10 P. 1)) POLINOMIALXNO SWODITSQ KRASSMATRIWAEMOJ ZADA^E.4) NP-POLNAQ ZADA^A. uKAZANIE. sWEDITE K NEJ ZADA^U 3-wyp.5) zADA^A PRINADLEVIT KLASSU P. uKAZANIE.
wOSPOLXZUJTESX KRITERIEM SU]ESTWOWANIQ \JLEROWA CIKLA W GRAFE. (tEOREMA |JLERA. wSWQZNOM GRAFE SU]ESTWUET CIKL, PROHODQ]IJ PO WSEM REBRAM, PRI^EMPO KAVDOMU W TO^NOSTI ODIN RAZ, TOGDA I TOLXKO TOGDA, KOGDA STEPENXKAVDOJ EGO WER[INY ^ETNA.)6) NP-POLNAQ ZADA^A.7) zADA^A PRINADLEVIT KLASSU P. uKAZANIE. wOSPOLXZUJTESX KRITERIEM 2-RASKRA[IWAEMOGO GRAFA. (tEOREMA. gRAF MOVNO RASKRASITX WDWA CWETA TOGDA I TOLXKO TOGDA, KOGDA ON NE SODERVIT CIKLOW NE^ETNOJDLINY.)8) NP-POLNAQ ZADA^A. uKAZANIE.
pUSTX D, D = K1 _ : : : Kl , | NEKOTORQ dnf BEZ OTRICANIJ PEREMENNYH. sOPOSTAWIM EJ GIPERGRAFG =< V; E >, GDE MNOVESTWO WER[IN V ESTX MNOVESTWO PEREMENNYH,WSTRE^A@]IHSQ W dnf D, MNOVESTWO REBER E ESTX fE1 : : : El g, PRI^EMREBRO Ei SOSTOIT IZ PEREMENNYH, SODERVA]IHSQ W \LEMENTARNOJ KON_@NKCII Ki, i = 1; : : : ; l. tOGDA dnf D OBRA]AETSQ W NOLX NA NEKOTORYHDWUH PROTIWOPOLOVNYH NABORAH TOGDA I TOLXKO TOGDA, KOGDA GIPERGRAF G MOVNO RASKRASITX W DWA CWETA. pOSTROITX GIPERGRAF G PO ISHODNOJ dnf D NA DETERMINIROWANNOJ mt MOVNO ZA POLINOMIALXNOEWREMQ.
tAKIM OBRAZOM, NP-POLNAQ ZADA^A OB OBRA]ENII W NOLX NA DWUHPROTIWOPOLOVNYH NABORAH dnf BEZ OTRICANIJ (SM. P. 2)) SWODITSQ KRASSMATRIWAEMOJ ZADA^E.2.12. 1) A), G) zADA^I PRINADLEVAT KLASSU P. uKAZANIE. wOSPOLXZUJTESX TEM FAKTOM, ^TO LINEJNAQ FUNKCIQ RAWNA EDINICE NA NABORAHLIBO TOLXKO S NE^ETNYM, LIBO TOLXKO S ^ETNYM ^ISLOM EDINIC.1) B), W) NP-POLNYE ZADA^I. uKAZANIE.
sWEDITE K RASSMATRIWAEMYMZADA^AM NP-POLNU@ ZADA^U OB OBRA]ENII dnf W NOLX (SM. ZADA^U 2.10P. 1)). pUSTX D | NEKOTORAQ NE RAWNAQ TOVDESTWENNO NUL@ dnf, A dnfD0 REALIZUET FUNKCI@ D t, GDE t | PEREMENNAQ, NE WSTRE^A@]AQSQ Wdnf D. tOGDA dnf D NA NEKOTOROM NABORE OBRA]AETSQ W NOLX TOGDAI TOLXKO TOGDA, KOGDA dnf D0 REALIZUET NELINEJNU@ FUNKCI@.2) A) zADA^A PRINADLEVIT KLASSU P.
uKAZANIE. mOVNO WOSPOLXZOWATXSQ OPREDELENIEM MONOTONNOJ FUNKCII.542) B) NP-POLNAQ ZADA^A. uKAZANIE. sWEDITE K RASSMATRIWAEMYM ZADA^AM NP-POLNU@ ZADA^U OB OBRA]ENII dnf W NOLX (SM. ZADA^U 2.10 P.1)). pUSTX D | NEKOTORAQ NE RAWNAQ TOVDESTWENNO NUL@ dnf, A dnfD0 REALIZUET FUNKCI@ D _ t, GDE t | PEREMENNAQ, NE WSTRE^A@]AQSQ Wdnf D. tOGDA dnf D NA NEKOTOROM NABORE OBRA]AETSQ W NOLX TOGDAI TOLXKO TOGDA, KOGDA dnf D0 REALIZUET NEMONOTONNU@ FUNKCI@.2) W) zADA^A PRINADLEVIT KLASSU P.
uKAZANIE. wOSPOLXZUJTESX SWOJSTWOM: ESLI MONOTONNAQ FUNKCIQ RAWNA EDINICE NA NEKOTOROM NABORE,TO ONA RAWNA EDINICE NA WSEH SLEDU@]IH ZA NIM NABORAH.2) G) zADA^A PRINADLEVIT KLASSU P. uKAZANIE. wOSPOLXZUJTESX SWOJSTWOM: SOKRA]ENNAQ dnf MONOTONNOJ FUNKCII NE SODERVIT OTRICANIJPEREMENNYH.2) D) zADA^A PRINADLEVIT KLASSU P. uKAZANIE. wOSPOLXZUJTESX SWOJSTWOM: FUNKCIQ f (x1; : : : ; xn) MONOTONNA TOGDA I TOLXKO TOGDA, KOGDA DLQ KAVDOGO i, i = 1; : : :; n, WERNO TOVDESTWOf (x1; : : : ; xi?1; 0; xi+1; : : : ; xn) (f (x1; : : : ; xi?1; 1; xi+1; : : : ; xn) 1) = 0.3) A, G) zADA^I PRINADLEVAT KLASSU P.3) B), W) NP-POLNYE ZADA^I.
uKAZANIE. sWEDITE K RASSMATRIWAEMYMZADA^AM NP-POLNU@ ZADA^U OB OBRA]ENII dnf W NOLX (SM. ZADA^U 2.10P. 1)). pUSTX D | NEKOTORAQ NE RAWNAQ TOVDESTWENNO NUL@ dnf, A dnfD0 REALIZUET FUNKCI@ D t, GDE t | PEREMENNAQ, NE WSTRE^A@]AQSQ Wdnf D. tOGDA dnf D NA NEKOTOROM NABORE OBRA]AETSQ W NOLX TOGDA ITOLXKO TOGDA, KOGDA dnf D0 REALIZUET NESAMODWOJSTWENNU@ FUNKCI@.3) D) zADA^I PRINADLEVAT KLASSU P. uKAZANIE. wOSPOLXZUJTESX OPREDELENIEM SAMODWOJSTWENNOJ FUNKCII I SWOJSTWOM: ESLI l | ^ISLO SLAGAEMYH POLINOMA SAMODWOJSTWENNOJ FUNKCIIPROIZWOLXp 2, A r | RANGrNOGO EGO SLAGAEMOGO, TO WERNO NERAWENSTWO l ? 1 2 .4) A) zADA^A PRINADLEVIT KLASSU P.4 B) NP-POLNAQ ZADA^A (SM.
ZADA^U 2 IZ WWEDENIQ K PARAGRAFU).k PARAGRAFU 33.1. 4)(x1(x2x3))(x4x5) = ((x1x2)x3)(x4x5) = (((x1x2)x3)x4)x5:3.2. uKAZANIE. dOKAVITE INDUKCIEJ PO n, ^TO WYRAVENIE x1 x2 : : : xnS L@BOJ PRAWILXNOJ RASSTANOWKOJ SKOBOK MOVNO S POMO]X@ TOVDESTWA(6) PREOBRAZOWATX W WYRAVENIE (: : : ((x1 x2) x3) : : : xn?1) xn (SM.ZADA^U 3.1).553.3. uKAZANIE. 2) I 4) PRIWEDITE K WIDU xx, OSTALXNYE K SOWER[ENNOJDIZ_@NKTIWNOJ NORMALXNOJ FORME.= xy (xz _ y) (5=;4) xyxz _ xyy (5=;8) xx _ yy (14=;13) xx.2) x _ y (xz _ y) (1)5) xy _ yz (11)= (z _ z)xy _ (x _ x)yz (4)= zxy _ zxy _ xyz _ xyz (5)= xyz _(10;12)(13)xyz _ xyz _ xyz = (xyz _ xyz) _ xyz _ xyz = xyz _ xyz _ xyz:3.5. sM. ZADA^U 3.4.3.6.
wYWEDEM (1), ISPOLXZUQ (2)-(9): x1 _ x2 (3)= x1 _ x2 (2)= x1&x2 (3)=x1&x2:wYWEDEM (10), ISPOLXZUQ (2)-(9): x1 _ x2 (3)= x1 _ x2 (2)= x1 x2 (5)= x2 x1 (2)=(3)x2 _ x1 = x2 _ x1:uKAZANIE. dLQ WYWODA (11), (12) I (13) SWODITE, ISPOLXZUQ (2)-(3),DIZ_@NKCI@ K KON_@NKCII I OBRATNO I ISPOLXZUJTE (9), (6) ILI (7),SOOTWETSTWENNO. dLQ WYWODA (14) ISPOLXZUJTE (8) I (5).3.7. uKAZANIE: PRI POMO]I TOVDESTW (1)-(14) PRIWEDITE OBE FORMULYK SOWER[ENNOJ D.N.F. oTWET: 1), 3), 5)-11) | DA; 2), 4) | NET.3.8. uKAZANIE: PRI POMO]I TOVDESTW (1)-(14) OBE FORMULY MOVNOPRIWESTI K SOWER[ENNOJ D.N.F.3.9.
1) uKAZANIE: POSTROJTE SISTEMU TOVDESTW, POZWOLQ@]U@ L@BU@FORMULU NAD BAZISOM B = fxy; x y; 1g PEREWODITX W POLINOM vEGALKINA.2) nAPRIMER: TOVDESTWA (4)-(7), (10), (12), (13) WMESTE S TOVDESTWAMI0&0 = 0, 1&1 = 1, x&0 = 0, x&1 = x, 0 _ 0 = 0, 1 _ 1 = 1, x _ 0 = x,x _ 1 = 1.k PARAGRAFU 44.2. uKAZANIE. TII : ISPOLXZUJTE TOVDESTWO t2; TIII : MNOGOKRATNO PRI-MENQJTE TOVDESTWO ZADA^I 4.2 P. 3) I TOVDESTWO t3; TIV : MNOGOKRATNOPRIMENITE TOVDESTWO t4 I TOVDESTWO ZADA^I 4.2 P.
3); TV : MNOGOKRATNOPRIMENITE TOVDESTWAt5 I t2; TV I : PRIMENITE TOVDESTWO TV , A ZATEM(n)TOVDESTWO t6 ; TV II : MNOGOKRATNO PRIMENITE TOVDESTWO ZADA^I 4.2 P.1); TV III : SNA^ALA PRIMENITE TOVDESTWO TV I , A ZATEM MNOGOKRATNO TOVESTWO TV ; TIX : PRIMENITE TOVESTWA TV I I TV .4.4. 1) nET; 2) DA.4.5. uKAZANIE.
2) dLQ ODNOJ IZ RASSMATRIWAEMYH SHEM WELI^INAR() RAWNA 1, DLQ DRUGOJ | 0; 3) DOKAZYWAETSQ ANALOGI^NO P. 2); 4)56SLEDUET IZ P. 3); 5) WYTEKAET IZ P. 4) S U^ETOM TOGO, ^TO ESLI W KLASSE WSEH KONTAKTNYH SHEM IMEETSQ POLNAQ SISTEMA TOVDESTW, TO W SILUTEOREMY 4.1 ONA IMEETSQ I SREDI OSNOWNYH TOVDESTW.k PARAGRAFU 55.1. 1) 2; 2) 3; 3) 2; 4) 3; 5) 2; 6) 3.5.2. 1) n; 2) n ? 1; 3) n ? 1; 4) n.5.3. uKAZANIE. dWA STOLBCA MATRICY M RAZLI^A@TSQ W j -J STROKE(2)TOGDA I TOLXKO TOGDA, KOGDA j -Q STROKA MATRICY M POKRYWAET SUMMUPO MODUL@ 2 \TIH STOLBCOW.5.5.
1), 4), 5), 7) | dA. 2), 3), 6), 8), 9) | wOOB]E GOWORQ, NET.5.6. pUSTX A I B | TUPIKOWYE TESTY MATRICY M S m STROKAMI.tOGDA NI ODNO IZ WKL@^ENIJ A B , B A NE IMEET MESTA. oTS@DAWYTEKAET, ^TO ^ISLO TUPIKOWYH TESTOW NE PREWOSHODIT MAKSIMALXNOGO^ISLA POPARNONESRAWNIMYH NABOROW W B m, A ZNA^IT, NE PREWOSHODIT?WELI^INY bmm c .5.7. ~ISLO MATRIC RAZMERNOSTI k n S POPARNO RAZLI^NYMI STOLBCAMI RAWNO 2k (2k ? 1) : : : (2k ? n +1).
~ISLO MATRIC RAZMERNOSTI m n,U KOTORYH k STROK S FIKSIROWANNYMI NOMERAMI ZADANY, RAWNO 2n(m?k).5.8. 1) f1; 2g, f1; 4g, f2; 3g, f3; 4g; 2) f1; 2; 3g, f1; 2; 4g, f1; 3; 4g; 5)f1; 2; 3g, f1; 2; 5g, f2; 3; 4g, f1; 4; 5g, f3; 4; 5g; 6) f1; 2; 3g, f2; 3; 5g, f3; 4; 5g.5.9. uKAZANIE. nIVNQQ OCENKA DOKAZYWAETSQ OT PROTIWNOGO IZ PREDPOLOVENIQ O SU]ESTWOWANII TESTA DLINY MENX[EJ, ^EM dlog2 ne. dLQDOKAZATELXSTWA WERHNEJ OCENKI IZU^ITE ^ISLO KLASSOW \KWIWALENTNOSTI, NA KOTORYE WSE n STOLBCOW MATRICY TUPIKOWOGO TESTA RAZBIWA@TSQ EE PERWYMI l STROKAMI (l 2 f1; : : : ; n ? 1g).
dOSTIVIMOSTX NIVNEJ(WERHNEJ) GRANICY DOKAZYWAET MATRICA IZ ZADA^I 5.2.1 (SOOTWETSTWENNO 5.2.2 PRI k = 0).5.10. nET. uKAZANIE. rASSMOTRITE MATRICU M (2), DOKAZYWAJTE OTPROTIWNOGO.5.11. uKAZANIE. rASSMOTRITE MATRICU M (2) I OCENITE SWERHU ^ISLOEDINIC W TEH EE STROKAH, KOTORYE SWQZANY S TESTOM.5.12. pUSTX T , T b1; me | TEST MATRICY M , A Ji, Ji b2; n + 1e| MNOVESTWO NOMEROW TEH STOLBCOW MATRICY M , KOTORYE OBRAZU@TGRUPPU S NOMEROM i, i = 1; :::; s, IZ USLOWIQ ZADA^I.
pUSTX, DALEE, Ji0, i =1; :::; s, | MNOVESTWO TEH ^ISEL j , j 2 Ji, DLQ KOTORYH STOLBEC M hT; j iSODERVIT ROWNO ODNU EDINICU. tAK KAK W KAVDOJ STROKE PODMATRICY257M hT; Jii IMEETSQ NE BOLEE ODNOJ EDINICY, TO jJi0j + 2(jJij ? jJi0j) jT j,I, SLEDOWATELXNO, jJi0j 2jJij ? jT j. sUMMIRUQ POSLEDNIE NERAWENSTWA PO WSEM i, i = 1; :::; s, I U^ITYWAQ, ^TO W PODMATRICE M hT i ^ISLO STOLBCOW, SODERVA]IH ODNU EDINICU, NE BOLX[E, ^EM jT j, POLU^IM:jT j 2n ? s jT j.k PARAGRAFU 66.1. f(100); (101)g, f(100); (111)g, f(101); (110)g, f(101); (111)g,f(110); (111)g.6.2. oTWETY PUNKTOW A) I B) SOWPADA@T: f(000); (001); (010)g, f(000);(001); (100)g, f(000); (010); (111)g, f(000); (100); (111)g, f(001); (010);(101)g, f(001); (100); (101)g, f(010); (101); (111)g, f(100); (101); (111)g.6.3.
A) f(000); (101)g, f(011); (110)g; B) f(000); (011); (101)g, f(000);(101); (110)g, f(000); (011); (110)g, f(011); (101); (110)g.6.4. oTWETY PUNKTOW A) I B) SOWPADA@T: f(000); (001); (101)g, f(001);(101); (110)g, f(000); (001); (111)g, f(001); (110); (111)g.6.5. oTWETY PUNKTOW A) I B) SOWPADA@T: f(000); (100); (111)g, f(000);(101); (111)g, f(010); (100); (111)g, f(010); (101); (111)g.6.6.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
