В.Б. Алексеев, А.А. Вороненко, С.А. Ложкин, Д.С. Романов и др. - Задачи по курсу «Основы кибернетики» (2002) (1132782)
Текст из файла
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]).n2L(n) = n (1 + n);(1)GDE n ! 0 PRI n ! 1.tEOREMA 1.3.
eSLI Q | INWARIANTNYJ KLASS S HARAKTERISTIKOJ , > 0,TOnLQ(n) 2n (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 QnjQ(n)j 2.POSLEDOWATELXNOSTX jQ(n)j NE WOZRASTAET I 1 nlim!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.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
