В.Б. Алексеев, А.А. Вороненко, С.А. Ложкин и др. - Задачи по курсу Основы кибернетики (2002)

mOSKOWSKIJ GOSUDARSTWENNYJ UNIWERSITETIMENI m. w. lOMONOSOWAfAKULXTET WY^ISLITELXNOJMATEMATIKI I KIBERNETIKIw. b. aLEKSEEW, a. a. wORONENKO, s. a. lOVKIN,d. s. rOMANOW, a. a. sAPOVENKO, s. n. sELEZNEWAzada~i po kursu\osnowy kibernetiki"mOSKWA2002mOSKOWSKIJ GOSUDARSTWENNYJ UNIWERSITETIMENI m w lOMONOSOWAfAKULXTET WY^ISLITELXNOJ MATEMATIKI I KIBERNETIKI..w. b. aLEKSEEW, a. a.

wORONENKO, s. a. lOVKIN,d. s. rOMANOW, a. a. sAPOVENKO, s. n. sELEZNEWAzada~i po kursu\osnowy kibernetiki"U^EBNOE POSOBIE PO KURSU\oSNOWY KIBERNETIKI"mOSKWA2002udk 510.5, 519.71bbk 22.12:22.18A47aLEKSEEW w. b., wORONENKO a. a., lOVKIN s. a.,rOMANOW d. s., sAPOVENKO a. a., sELEZNEWA s. n.zADA^I PO KURSU \oSNOWY KIBERNETIKI" (U^EBNOE POSOBIE DLQSTUDENTOW) | m.: iZDATELXSKIJ OTDEL FAKULXTETA wmIk mgu (LICENZIQ id N 05899 OT 24.09.2001), 2002 G. | 66 c.rECENZENTY:PROF. mAR^ENKOW s. s., D. F.-M.

N.N. S. kUZNECOW `. w., K. F.-M. N.pE^ATAETSQ PO RE[ENI@ rEDAKCIONNO-IZDATELXSKOGO SOWETA FAKULXTETA WY^ISLITELXNOJ MATEMATIKI I KIBERNETIKI mgu IM. m. w. lOMONOSOWAzADA^NIK SODERVIT MATERIAL DLQ SEMINARSKIH ZANQTIJ PO KURSU \oSNOWY KIBERNETIKI". w NEGO WKL@^ENY ZADA^I PO INWARIANTNYM KLASSAM, PONQTI@ SWODIMOSTI I NP-POLNOTE, \KWIWALENTNYM PREOBRAZOWANIQM, TESTAM, NADEVNOSTI I SAMOKORREKCII.ISBN 5-89407-147-Xc iZDATELXSKIJ OTDEL FAKULXTETAWY^ISLITELXNOJ MATEMATIKI IKIBERNETIKI mgu IM.

m. w. lOMONOSOWA,2002 G.wWEDENIEw NASTOQ]EM POSOBII SOBRANY UPRAVNENIQ PO KURSU \oSNOWY KIBERNETIKI". zADA^I SGRUPPIROWANY PO TEMAM, SREDI KOTORYH SLEDU@]IE:INWARIANTNYE KLASSY, SLOVNOSTX ALGORITMOW, \KWIWALENTNYE PREOBRAZOWANIQ UPRAWLQ@]IH SISTEM, TESTY, NADEVNOSTX I SAMOKORREKCIQ.kAVDOJ TEME OTWEDEN PARAGRAF, W NA^ALE KOTOROGO DA@TSQ NEOBHODIMYE OPREDELENIQ I TEORETI^ESKIE SWEDENIQ. pOSOBIE PREDNAZNA^ENO DLQSTUDENTOW TRETXEGO-^ETWERTOGO KURSOW. pREDPOLAGAETSQ, ^TO ^ITATEL@ZNAKOMY OSNOWNYE PONQTIQ DISKRETNOJ MATEMATIKI.pARAGRAF 1 POSWQ]EN INWARIANTNYM KLASSAM.w PARAGRAFE 2 SOBRANY ZADA^I, KASA@]IESQ PONQTIJ SWODIMOSTI INP-POLNOTY.

~ASTX ZADA^ POSWQ]ENA OCENKAM SLOVNOSTI KONKRETNYHALGORITMOW.w PARAGRAFAH 3 I 4 PREDLAGA@TSQ ZADA^I PO \KWIWALENTNYM PREOBRAZOWANIQM FORMUL I SHEM.pARAGRAFY 5 I 6 POSWQ]ENY ALGORITMAM POSTROENIQ TESTOW I OCENKAM DLINY TESTOW DLQ TABLIC I SHEM.pARAGRAF 7 POSWQ]EN PROBLEME NADEVNOSTI. w NEM TAKVE SOBRANYZADA^I PO POSTROENI@ I OCENKAM SLOVNOSTI SAMOKORREKTIRU@]IHSQSHEM.3~ASTX 1. iNWARIANTNYE KLASSY I SLOVNOSTX ALGORITMOWx 1. iNWARIANTNYE KLASSYpONQTIE INWARIANTNOGO KLASSA BYLO WWEDENO s.w.qBLONSKIM [8].mNOVESTWO FUNKCIJ Q P2 NAZYWAETSQ INWARIANTNYM KLASSOM,ESLI NARQDU S KAVDOJ FUNKCIEJ f 2 Q ONO SODERVIT WSE FUNKCII,POLU^A@]IESQ IZ f PRIMENENIEM SLEDU@]IH TREH OPERACIJ:1) DOBAWLENIE I IZ_QTIE FIKTIWNYH PEREMENNYH;2) PEREIMENOWANIE PEREMENNYH (BEZ OTOVDESTWLENIQ);3) PODSTANOWKA KONSTANT NA MESTA NEKOTORYH PEREMENNYH.oBOZNA^IM ^EREZ Q(n) MNOVESTWO WSEH FUNKCIJ f IZ Q, ZAWISQ]IH(NE OBQZATELXNO SU]ESTWENNO) OT PEREMENNYH x1; x2; : : : ; xn.pn~ISLO = log2 nlimjQ(n)j NAZYWAETSQ HARAKTERISTIKOJ INWARI!1ANTNOGO KLASSA Q.

iNOGDA HARAKTERISTIKA BUDET UKAZYWATXSQ W KA^ESTWE INDEKSA PRI Q ILI Q(n). sPRAWEDLIWA SLEDU@]AQtEOREMA 1.1 (s. w. qBLONSKIJ [9]). dLQ L@BOGO 2 [0; 1) SU]ESTWUET2KONTINUUM POPARNO RAZLI^NYH INWARIANTNYH KLASSOW Q S HARAKTERISTIKOJ .oBOZNA^IM ^EREZ L(f ) SLOVNOSTX MINIMALXNOJ SHEMY IZ FUNKCIONALXNYH \LEMENTOW, REALIZU@]EJ FUNKCI@ f , I PUSTX L(n) =max L(f ), LQ(n) = fmaxL(f ). w DALXNEJ[EM ISPOLXZU@TSQ SLEDUf 2P (n)2Q(n)@]IE UTWERVDENIQ.tEOREMA 1.2 (o.

b. lUPANOW [5]).n(1)L(n) = 2n (1 + n);GDE n ! 0 PRI n ! 1.tEOREMA 1.3. eSLI Q | INWARIANTNYJ KLASS S HARAKTERISTIKOJ , > 0,TOn2LQ(n) n (1 + n);(2)GDE n ! 0 PRI n ! 1.fUNKCIQ fn(x1; : : : ; xn) NAZYWAETSQ SLOVNOJ, ESLI L(fn) =L(n). bESKONE^NAQ POSLEDOWATELXNOSTX BULEWYH FUNKCIJ (f1(x1);f2(x1; x2); : : :; fn(x1; : : : ; xn); : : :) NAZYWAETSQ SLOVNOJ, ESLI DLQ L@BOGO N SU]ESTWUET n N TAKOE, ^TO FUNKCIQ fn(x1; : : : ; xn) QWLQETSQSLOVNOJ.24aLGORITM, STROQ]IJ BESKONE^NU@ POSLEDOWATELXNOSTX BULEWYHFUNKCIJ (fi(x1; : : : ; xi))1i=1 IZ P2 NAZYWAETSQ PRAWILXNYM, ESLI ON STROIT WSE FUNKCII MINIMALXNOGO PO WKL@^ENI@ INWARIANTNOGO KLASSA,SODERVA]EGO \TU POSLEDOWATELXNOSTX.tEOREMA 1.4 (s.

w. qBLONSKIJ [8]). l@BOJ PRAWILXNYJ ALGORITM1 ,STROQ]IJ SLOVNU@ POSLEDOWATELXNOSTX FUNKCIJ (fi(x1; : : : ; xi))i=1IZ P2, STROIT WSE MNOVESTWO P2.1.1. pUSTX A I B | INWARIANTNYE KLASSY. wERNO LI, ^TO WSEGDAINWARIANTNYM KLASSOM QWLQETSQ:1) A \ B ;2) A [ B ;3) A n B ;4) P2 n A.1.2. 1) wSQKIJ LI ZAMKNUTYJ KLASS QWLQETSQ INWARIANTNYM?2) wSQKIJ LI INWARIANTNYJ KLASS QWLQETSQ ZAMKNUTYM?1.3.

pUSTX A | ZAMKNUTYJ KLASS, SODERVA]IJ KONSTANTY 0 I 1.wERNO LI, ^TO A | WSEGDA INWARIANTNYJ KLASS?1.4. wYQSNITX, KAKIE IZ SLEDU@]IH KLASSOW QWLQ@TSQ INWARIANTNYMI KLASSAMI:1) KLASS L LINEJNYH FUNKCIJ;2) KLASS M MONOTONNYH FUNKCIJ;3) KLASS T0 FUNKCIJ, SOHRANQ@]IH KONSTANTU 0;4) KLASS T0 \ T1, GDE T , 2 f0; 1g, | KLASS FUNKCIJ, SOHRANQ@]IHKONSTANTU ;5) KLASS S SAMODWOJSTWENNYH FUNKCIJ;6) KLASS SIMMETRI^ESKIH FUNKCIJ, TO ESTX FUNKCIJ, NE IZMENQ@]IHSQ PRI L@BOJ PERESTANOWKE IH PEREMENNYH;7) KLASS SIMMETRI^ESKIH FUNKCIJ I FUNKCIJ, POLU^AEMYH IZ SIMMETRI^ESKIH DOBAWLENIEM FIKTIWNYH PEREMENNYH;8) KLASS FUNKCIJ, PRINIMA@]IH EDINI^NYE ZNA^ENIQ TOLXKO NA NABORAH S ^ETNYM ^ISLOM EDINIC;9) KLASS FUNKCIJ, STEPENX POLINOMA vEGALKINA KOTORYH NE BOLX[ENEKOTOROGO ZADANNOGO ^ISLA;10) KLASS FUNKCIJ, ^ISLO SLAGAEMYH POLINOMA vEGALKINA KOTORYHNE BOLX[E POLOWINY WSEH WOZMOVNYH.51.5.

dOKAZATX, ^TO pDLQKAVDOGO NEPUSTOGO INWARIANTNOGOpn KLASSA QnPOSLEDOWATELXNOSTX jQ(n)j NE WOZRASTAET I 1 nlimjQ(n)j 2.!11.6. dOKAZATX, ^TO ESLI INWARIANTNYJ KLASS Q NE SOWPADAET SP2; TO < 1:1.7. wY^ISLITX HARAKTERISTIKI SLEDU@]IH INWARIANTNYH KLASSOW:1) KLASS L LINEJNYH FUNKCIJ;2) KLASS M MONOTONNYH FUNKCIJ;3) KLASS FUNKCIJ, PREDSTAWIMYH W WIDEf (x1; : : : ; xn) = l(x1; : : : ; xn)&g(x1; : : : ; xn);(3)GDE l | LINEJNAQ FUNKCIQ, A g | PROIZWOLXNAQ FUNKCIQ IZ P2, U KOTOROJ KAVDAQ SU]ESTWENNAQ PEREMENNAQ QWLQETSQ SU]ESTWENNOJ PEREMENNOJ FUNKCII l.1.8. 1) pUSTX P2(n) | MNOVESTWO FUNKCIJ IZ P2(n),n SU]ESTWENNOZAWISQ]IH OT n PEREMENNYH. pOKAZATX, ^TO jP2(n)j 22 n22n ;2) pUSTX Q, Qn m P2, | INWARIANTNYJ KLASS.

dOKAZATX NERAWENSTWOjQ(n)j jQ(m)j2 PRI n m.1.9. pUSTX s(f ) | ^ISLO POPARNO RAZLI^NYH PODFUNKCIJ FUNKCIIf , A s(n) = maxf 2P (n) s(f ). dOKAZATX, ^TO1) s(n) 3n;2) DLQ WSQKOGO " > 0 SU]ESTWUET N TAKOE, ^TO s(n) 3n(1 ") DLQWSEH n > N .1.10. dOKAZATX TEOREMU 1.4 IZ WWEDENIQ K PARAGRAFU.22126x 2. sLOVNOSTX ALGORITMOWtERMIN \MA[INA tX@RINGA" (SOKRA]ENNO mt) UPOTREBLQETSQ ZDESXDLQ ODNOLENTO^NYH DETERMINIROWANNYH MA[IN (SM., NAPRIMER, [10]).nEKOTOROE (NEPRINCIPIALXNOE) OTLI^IE SOSTOIT W TOM, ^TO, KAK PRAWILO, RASSMATRIWA@TSQ mt S ODNOSTORONNEJ LENTOJ, BESKONE^NOJ WPRAWO.aLFAWIT SIMWOLOW LENTY mt OBOZNA^IM ^EREZ A, A MNOVESTWO SOSTOQNIJ | ^EREZ Q. aLFAWITY A I Q KONE^NY.

sIMWOLOM q1 OBOZNA^AETSQNA^ALXNOE SOSTOQNIE, SIMWOLOM a1 | PUSTOJ SIMWOL, PRISUTSTWU@]IJPO OPREDELENI@ W ALFAWITE A. s^ITAETSQ, ^TO W NA^ALXNYJ MOMENT SLOWO w = b1 b2 : : : bn, OBRABATYWAEMOE mt, ZAPISANO W PERWYH n Q^EJKAHLENTY, A WSE OSTALXNYE Q^EJKI LENTY SODERVAT SIMWOL a1. dETERMINIROWANNOSTX mt OZNA^AET, ^TO DLQ KAVDOJ PARY WIDA (a; q), GDE a |SIMWOL WHODNOGO ALFAWITA, A q | SIMWOL SOSTOQNIQ, W PROGRAMME mtPRISUTSTWUET NE BOLEE ODNOJ KOMANDY WIDA: aq ! a0q0d, NA^INA@]EJSQS aq.pUSTX W PROCESSE RABOTY mt NA NEKOTOROM TAKTE t OKAZALOSX, ^TONA LENTE ZAPISANO SLOWO w = b1 b2 : : : bm. |TO OZNA^AET, ^TO W PERWYHm Q^EJKAH LENTY SODERVATSQ SIMWOLY b1; : : : ; bm, A Q^EJKI, NA^INAQ S(m + 1)-J, SODERVAT SIMWOL a1.

pUSTX DALEE NA TAKTE t mt NAHODITSQ WSOSTOQNII qj , A GOLOWKA OBOZREWAET Q^EJKU S NOMEROM k. kONFIGURACIEJ(MGNOWENNYM OPISANIEM), SOOTWETSTWU@]EJ \TOMU TAKTU t, NAZYWAETSQ SLOWO Ct WIDA b1b2 : : : bk 1 qj bk : : : bm PRI k < m ILI SLOWO Ct WIDA b1b2 : : : bk 1 bk : : : bm; a1:::a1qj (k m PUSTYH SIMWOLOW PERED qj ) PRIk m.

kONFIGURACIQ, SOOTWETSTWU@]AQ PERWOMU TAKTU, NAZYWAETSQNA^ALXNOJ, A POSLEDNEMU (ESLI mt OSTANAWLIWAETSQ), | ZAKL@^ITELXNOJ. wY^ISLENIEM mt M NA WHODE w NAZYWAETSQ POSLEDOWATELXNOSTXKONFIGURACIJ C1; C2; :::; Ct; :::, WOZNIKA@]AQ PRI RABOTE NAD SLOWOM w.pODRAZUMEWAETSQ, ^TO KONFIGURACIQ Ct+1 ODNOZNA^NO OPREDELQETSQ KONFIGURACIEJ Ct I KOMANDOJ mt M , NA^INA@]EJSQ S PARY (bk ; qj ), GDE bk| SIMWOL, OBOZREWAEMYJ mt W MOMENT t, A qj | SOSTOQNIE mt W MOMENTt. wREMQ RABOTY ILI ^ISLO [AGOW tM (w) mt M NA WHODE w OPREDELQETSQ KAK ^ISLO KONFIGURACIJ W WY^ISLENII mt M NA WHODE w. eSLIWY^ISLENIE BESKONE^NO, POLAGAEM tM (w) = 1.

pUSTX SREDI SOSTOQNIJmt IME@TSQ WYDELENNYE ZAKL@^ITELXNYE SOSTOQNIQ | PRINIMA@]EEI OTWERGA@]EE. tOGDA WY^ISLENIE NAZYWAETSQ PRINIMA@]IM (OTWERGA@]IM), ESLI ONO ZAKAN^IWAETSQ W PRINIMA@]EM (OTWERGA@]EM) SO7STOQNII.nEDETERMINIROWANNYE MA[INY tX@RINGA. oTLI^IE NEDETER-MINIROWANNOJ mt (SOKRA]ENNO, nmt) OT DETERMINIROWANNOJ SOSTOITW TOM, ^TO W PROGRAMME nmt DLQ PARY (a; q), GDE a | SIMWOL IZ ALFAWITA mt, A q | SIMWOL SOSTOQNIQ, W EE PROGRAMME MOVET PRISUTSTWOWATX NESKOLXKO KOMAND, NA^INA@]IHSQ S aq. bEZ POTERI OB]NOSTIMOVNO OGRANI^ITXSQ SLU^AEM, KOGDA PARE aq MOVET SOOTWETSTWOWATXNE BOLEE DWUH KOMAND c NA^ALOM aq. pUSTX W PROGRAMME nmt IMEETSQPARA KOMAND aq ! a0q0L I aq ! a00q00R.

tOGDA, NAHODQSX W SOSTOQNII qI OBOZREWAQ SIMWOL a NA LENTE, nmt MOVET WYBRATX L@BU@ IZ DWUHWOZMOVNOSTEJ: ZAPISATX W OBOZREWAEMU@ Q^EJKU SIMWOL a0, PEREJTI WSOSTOQNIE q0 I SDWINUTX GOLOWKU WLEWO, LIBO ZAPISATX W OBOZREWAEMU@Q^EJKU SIMWOL a00, PEREJTI W SOSTOQNIE q00 I SDWINUTX GOLOWKU WPRAWO.pRI \TOM S^ITAETSQ, ^TO nmt KAK BY SOZDAET DWE KOPII SAMOJ SEBQI PROSLEVIWAET POSLEDOWATELXNOSTX WY^ISLENIJ OBOIH SPOSOBOW DEJSTWIQ. pONQTIE KONFIGURACII DLQ nmt NE OTLI^AETSQ OT TOGO, ^TOOPREDELENO WY[E DLQ OBY^NOJ mt. wY^ISLENIEM nmt NA WHODE w NAZYWAETSQ POSLEDOWATELXNOSTX KONFIGURACIJ C1; C2; :::; Ct; :::, W KOTOROJC1 = q1w, A Ct+1 POLU^AETSQ IZ Ct S POMO]X@ ODNOJ IZ KOMAND, SOOTWETSTWU@]IH PARE a(t)q(t), GDE q(t) | SIMWOL SOSTOQNIQ, WHODQ]IJ WCt, A a(t) | BUKWA IZ Ct, STOQ]AQ SPRAWA OT q(t). wSQKOE WY^ISLENIEMOVNO IZOBRAZITX ORIENTIROWANNOJ CEPX@, WER[INAMI KOTOROJ QWLQ@TSQ KONFIGURACII, A KAVDAQ DUGA SOEDINQET DWE POSLEDOWATELXNYEWER[INY.

w SLU^AE DETERMINIROWANNYH mt WY^ISLENIE ODNOZNA^NOOPREDELQETSQ WHODOM. w SLU^AE nmt OB_EDINENIE CEPEJ, SOOTWETSTWU@]IH WY^ISLENIQM NA WHODE w, PREDSTAWLQET SOBOJ ORIENTIROWANNOE(OT KORNQ) DEREWO S KORNEM C1 = q1w.rASPOZNAWANIE QZYKOW. pUSTX A | KONE^NYJ ALFAWIT. ~EREZ A!OBOZNA^IM MNOVESTWO WSEH SLOW (KONE^NYH POSLEDOWATELXNOSTEJ) W ALFAWITE A. ~EREZ jjwjj OBOZNA^IM DLINU SLOWA w, OPREDELQEMU@ KAK ^ISLO BUKW W w. pROIZWOLXNOE PODMNOVESTWO L A! NAZYWAETSQ QZYKOMW ALFAWITE A. gOWORQT, ^TO mt (nmt) M S DWUMQ ZAKL@^ITELXNYMISOSTOQNIQMI (PRINIMA@]IM I OTWERGA@]IM) RASPOZNAET QZYK L, ESLI DLQ WSQKOGO SLOWA w 2 A! PRINIMA@]EE WY^ISLENIE M NA WHODE wSU]ESTWUET TOGDA I TOLXKO TOGDA, KOGDA w 2 L.