В.Б. Алексеев - Электронный коспект лекций, страница 7

eSLI VE W PROGRAMME MA[INY NET KOMANDY, W LEWOJ ^ASTIKOTOROJ STOIT PARA ciqj , TO MA[INA OSTANAWLIWAETSQ.mY BUDEM RASSMATRIWATX TOLXKO DETERMINIROWANNYE MA[INYtX@RINGA, TO ESTX TAKIE, U KOTORYH W PROGRAMME KAVDAQ PARA ci qjWSTRE^AETSQ W LEWYH ^ASTQH KOMAND NE BOLEE ODNOGO RAZA. w \TOM SLU^AEKAVDYJ [AG MA[INY OPREDELQETSQ ODNOZNA^NO.oPREDELENIE. eSLI A - ALFAWIT, TO ^EREZ A BUDEM OBOZNA^ATXMNOVESTWO WSEH (KONE^NYH) SLOW W ALFAWITE A. pUSTX C - LENTO^NYJALFAWIT MA[INY M , C0 = C n fg I PUSTX ZADAN NEKOTORYJ WHODNOJ ALFAWIT A, TAKOJ, ^TO A C0. tOGDA MY BUDEM S^ITATX, ^TOMA[INA M OSU]ESTWLQET PREOBRAZOWANIE 'M : A ! C0 [ fg, KOTOROE OPREDELQETSQ SLEDU@]IM OBRAZOM (ZDESX W fg TRAKTUETSQ KAKNEOPREDELENNOSTX).

pUSTX ZADANO NEKOTOROE SLOWO a = a1a2 : : : an 2 A..35rAZMESTIM SIMWOLY \TOGO SLOWA W POSLEDOWATELXNYE Q^EJKI LENTY, A WOSTALXNYE Q^EJKI POMESTIM , POMESTIM GOLOWKU NA Q^EJKU, W KOTOROJSTOIT a1, USTANOWIM MA[INU W NA^ALXNOE SOSTOQNIE q1 I NA^NEM RABOTUMA[INY. eSLI POSLE \TOGO MA[INA M BUDET RABOTATX BESKONE^NO DOLGO, TO S^ITAEM, ^TO 'M (a1a2 : : : an) = . eSLI MA[INA M OSTANOWITSQI GOLOWKA BUDET OBOZREWATX , TO TAKVE S^ITAEM, ^TO 'M (a) = .eSLI VE M OSTANOWITSQ I OBOZREWAEMYJ SIMWOL OTLI^EN OT , TORASSMOTRIM MAKSIMALXNU@ SWQZNU@ (SOSTOQ]U@ IZ POSLEDOWATELXNYHQ^EEK) OBLASTX LENTY, KOTORAQ SODERVIT OBOZREWAEMU@ Q^EJKU I NESODERVIT .

pUSTX W Q^EJKAH \TOJ OBLASTI ZAPISANO SLOWO b = b1b2 : : : bk(\TA OBLASTX, O^EWIDNO, KONE^NA). tOGDA S^ITAEM, ^TO 'M (a) = b.tEZIStX@RINGA. dLQ L@BOGO ALGORITMI^ESKOGO PREOBRAZOWANIQ ' : A ! C0 [ fg SU]ESTWUET MA[INA tX@RINGA M OSU]ESTWLQ@]AQ PREOBRAZOWANIE 'rASPOZNAWANIE SIMMETRIIpUSTX A = f0; 1g I SLOWO a = a1a2 : : : an 2 A.

bUDEM GOWORITX,^TO SLOWO a SIMMETRI^NO, ESLI a1 = an; a2 = an;1 I T.D. pUSTX MA[INAtX@RINGA M IMEET LENTO^NYJ ALFAWIT C I MNOVESTWO SOSTOQNIJ Q,PRI^EM A C I q0 2 Q, q00 2 Q. bUDEM GOWORITX, ^TO M RASPOZNAETSIMMETRI@, ESLI DLQ L@BOGO WHODNOGO SLOWA a 2 A MA[INA M WSEGDAOSTANAWLIWAETSQ I PRI \TOM NAHODITSQ W SOSTOQNII q0 , ESLI a SIMMETRI^NO, ILI q00, ESLI a NE SIMMETRI^NO.uTWERVDENIE. sU]ESTWUET MA[INA tX@RINGA M KOTORAQRASPOZNAET SIMMETRI@ I DELAET PRI L@BOM WHODNOM SLOWE DLINY nNE BOLEE cn2 [AGOW GDE c NEKOTORAQ KONSTANTAdOKAZATELXSTWO dOSTATO^NO POSTROITX MA[INU M , KOTORAQ ZAPOMINAET I STIRAET PERWYJ SIMWOL, PEREGONQET GOLOWKU W KONEC SLOWAI SRAWNIWAET SIMWOL W PAMQTI S POSLEDNIM SIMWOLOM SLOWA.

eSLIONI NE SOWPADA@T, TO M PEREHODIT W SOSTOQNIE q00 I OSTANAWLIWAETSQ.eSLI SOWPADA@T, TO ONA STIRAET POSLEDNIJ SIMWOL, WOZWRA]AETSQ WNA^ALO SLOWA I POWTORQET PROCESS. eSLI SLOWO POLNOSTX@ STERTO, TOM PEREHODIT W SOSTOQNIE q0 I OSTANAWLIWAETSQ. pRI \TOM GOLOWKA NEBOLEE n RAZ PROBEGAET PO SLOWU DLINY NE BOLEE n. pO\TOMU OB]EE ^ISLO[AGOW ESTX O(n2).-,-.,,-..36oB]IE UTWERVDENIQ O SLOVNOSTI ZADA^rASSMOTRIM WSE MA[INY tX@RINGA, IME@]IE W LENTO^NOM ALFAWITE SIMWOLY I j. pUSTX Z + = f0g[ N , GDE N - MNOVESTWO NATURALXNYH ^ISEL.

bUDEM PREDSTAWLQTX ^ISLO k 2 Z + NA LENTE MA[INY W WIDEKODA jj : : : j , GDE KOLI^ESTWO j RAWNO k + 1 (OSTALXNYE SIMWOLYNA LENTE ). nABOR (k1; k2; : : : ; kn ) BUDEM PREDSTAWLQTX W WIDE KODA jj : : : j jj : : : j : : : jj : : : j ,GDE W PERWOM MASSIWE k1 +1 SIMWOLOW j,WO WTOROM k2 + 1 I T.D. pRIMENQQ MA[INU M K KODU ^ISLA ILI NABORA,BUDEM POME]ATX GOLOWKU NA SAMYJ PERWYJ SIMWOL j I USTANAWLIWATXMA[INU M W EE NA^ALXNOE SOSTOQNIE q1.oPREDELENIE. dLQ L@BOJ MA[INY tX@RINGA M I L@BOGO NATURALXNOGO ^ISLA n BUDEM S^ITATX, ^TO MA[INA M WY^ISLQET FUNKCI@f (x1; x2; : : : ; xn) : (Z + )n ! Z + [ fg KOTORAQ OPREDELQETSQ SLEDU@]IMOBRAZOM. pRIMENIM MA[INU M K KODU NABORA (a1; a2; : : : ; an).

eSLI MOSTANOWITSQ I POSLE OSTANOWKI NA LENTE BUDET TOLXKO KOD NEKOTOROGO^ISLA b 2 Z + , TO f (a1; a2; : : : ; an) = b. wO WSEH OSTALXNYH SLU^AQHf (a1; a2; : : : ; an) = (NEOPREDELENNOSTX).oPREDELENIE. fUNKCIQ f (x1; x2; : : : ; xn) : (Z +)n ! Z + [ fg NAZYWAETSQ WY^ISLIMOJ, ESLI SU]ESTWUET MA[INA tX@RINGA M , KOTORAQEE WY^ISLQET.oPREDELENIE. gOWORQT, ^TO MA[INA M PRAWILXNO WY^ISLQET FUNKCI@ f (x1; x2; : : : ; xn), ESLI NA^INAQ RABOTU S KODA NABORA(a1; : : : ; an) MA[INA M W TOM SLU^AE, KOGDA f (a1; a2; : : : ; an) NE OPREDELENO, OBQZATELXNO RABOTAET BESKONE^NO DOLGO, A W TOM SLU^AE, KOGDAf (a1; a2; : : : ; an) = b, MA[INA OSTANAWLIWAETSQ, NA LENTE OSTAETSQ KOD bI GOLOWKA MA[INY OBOZREWAET SAMYJ LEWYJ SIMWOL j.uTWERVDENIE. eSLI f (x1; x2; : : : ; xn) WY^ISLIMA TO SU]ESTWUET MA[INA tX@RINGA M KOTORAQ EE WY^ISLQET PRAWILXNOdOKAZATELXSTWO SM., NAPRIMER, W [ ].oPREDELENIE.

wS@DU OPREDELENNYE WY^ISLIMYE FUNKCII MYBUDEM NAZYWATX OB]EREKURSIWNYMI FUNKCIQMI. (oBY^NO OB]EREKURSIWNYE FUNKCII OPREDELQ@T INA^E, NO DANNOE OPREDELENIE \KWIWALENTNO OBY^NOMU; SM., NAPRIMER, [ ]).fUNKCIQ, WY^ISLQEMAQ MA[INOJ M , NE IZMENITSQ, ESLI PROIZWOLXNO PEREIMENOWATX WSE SIMWOLY LENTO^NOGO ALFAWITA, KROME Ij, I WSE SOSTOQNIQ, OSTAWLQQ NA^ALXNOE SOSTOQNIE NA^ALXNYM (KONE^NO, RAZNYE SIMWOLY DOLVNY PEREIMENOWYWATXSQ W RAZNYE).

pO\TOMUMY BUDEM S^ITATX, ^TO ESTX BESKONE^NYJ FIKSIROWANNYJ ALFAWITfc1 = ; c2 =j; c3; c4; : : : g, IZ KOTOROGO BERETSQ LENTO^NYJ ALFAWIT,,-.37MA[INY M , I BESKONE^NYJ FIKSIROWANNYJ ALFAWIT fq1; q2; : : : g, IZKOTOROGO BERUTSQ SOSTOQNIQ MA[INY M . bUDEM ZAPISYWATX INDEKSYW STROKU POSLE c ILI q, PREDSTAWLQQ IH W DWOI^NOJ SISTEME S^ISLENIQ(NAPRIMER, c6 = c110). pROGRAMMU MA[INY M BUDEM ZAPISYWATX W WIDEPOSLEDOWATELXNOSTI WSEH EE KOMAND ciqj ;! ck qr T , RAZDELENNYH TO^KOJS ZAPQTOJ.

tOGDA PROGRAMMA L@BOJ MA[INY BUDET PREDSTAWLQTX SOBOJSLOWO W ALFAWITE D = f; j; c; q; 0; 1; ;!; R; L; S; ; g.tEOREMA. sU]ESTWUET ALGORITM NUMERACII WSEH MA[IN tX@RINGA IZ UKAZANNOGO WY[E SEMEJSTWA TAKOJ ^TO DLQ WOSSTANOWLENIQPROGRAMMY PO EE NOMERU TAKVE SU]ESTWUET ALGORITMdOKAZATELXSTWO bUDEM S^ITATX, ^TO SIMWOLY ALFAWITA D UPORQDO^ENY (NAPRIMER, TAK, KAK \TO SDELANO WY[E). tOGDA WSE SLOWAODNOJ DLINY k MOVNO UPORQDO^ITX LEKSIGRAFI^ESKI (KAK W SLOWARE).bUDEM TEPERX PROSMATRIWATX WSE SLOWA W ALFAWITE D W SOOTWETSTWII SIH DLINOJ: SNA^ALA DLINY 1, ZATEM DLINY 2 I T.D. sLOWA ODNOJ DLINY kPROSMATRIWAEM W LEKSIKOGRAFI^ESKOM PORQDKE. dLQ KAVDOGO SLOWA PRIMENQEM ALGORITM, KOTORYJ PROWERQET, QWLQETSQ LI \TO SLOWO PRAWILXNO POSTROENNOJ PROGRAMMOJ NEKOTOROJ DETERMINIROWANNOJ MA[INYtX@RINGA.

eSLI DA, TO PRIPISYWAEM \TOJ PROGRAMME O^EREDNOJ NOMER(NA^INAQ S 0). pRI \TOM L@BOJ MA[INE tX@RINGA (IZ RASSMATRIWAEMOGO SEMEJSTWA) PO EE PROGRAMME BUDET (ALGORITMI^NO) SOPOSTAWLQTXSQNEKOTORYJ NOMER. tOT VE PEREBOR OSU]ESTWLQEM, ESLI ZADAN NOMER ITREBUETSQ NAJTI SOOTWETSTWU@]U@ \TOMU NOMERU PROGRAMMU.zAFIKSIRUEM DALEE NEKOTORU@ NUMERACI@ MA[IN tX@RINGAi ! Mi, UDOWLETWORQ@]U@ TEOREME. tAK KAK MA[INA Mi WY^ISLQETNEKOTORU@ FUNKCI@ f (x), TO MY POLU^AEM TAKVE NEKOTORU@ NUMERACI@ WSEH WY^ISLIMYH FUNKCIJ ODNOJ PEREMENNOJ i ;! 'i(x). zAMETIM,^TO PRI \TOM MOVET BYTX 'i(x) 'j (x) PRI i =6 j , POSKOLXKU RAZNYEMA[INY tX@RINGA MOGUT WY^ISLQTX ODNU I TU VE FUNKCI@ f (x).dOKAVEM TEPERX TEOREMY O TOM, ^TO SU]ESTWU@T SKOLX UGODNOSLOVNO WY^ISLIMYE FUNKCII.tEOREMA.

dLQ L@BOJ OB]EREKURSIWNOJ FUNKCII T (x) SU]ESTWUET OB]EREKURSIWNAQ FUNKCIQ f (x) PRINIMA@]AQ TOLXKO ZNA^ENIQI I TAKAQ ^TO DLQ L@BOJ MA[INY tX@RINGA Mi WY^ISLQ@]EJ f (x)HOTQ BY PRI ODNOM x WYPOLNQETSQ NERAWENSTWO ti(x) > T (x) GDE ti (x)WREMQ RABOTY MA[INY Mi NA WHODE x TO^NEE NA KODE ^ISLA xzAME^ANIE. oTMETIM, ^TO FUNKCIQ T (x) MOVET RASTI O^ENXBYSTRO.

nAPRIMER, FUNKCII g1(n) = n, g2(n) = nn, g3(n) = ng2(n),: : : , gm+1 (n) = ngm(n) , : : : OB]EREKURSIWNY. tAKVE OB]EREKURSIWNA I-,..-,12,0,,,|(38,).FUNKCIQ h(n) = gn(n), KOTORAQ RASTET S ASTRONOMI^ESKOJ SKOROSTX@.dOKAZATELXSTWO dLQ WSEH i 2 Z + I x 2 Z + PUSTX ti(x) OBOZNA^AETWREMQ RABOTY MA[INY S NOMEROM i, ESLI WHODOM QWLQETSQ KOD ^ISLA x(ti(x) MOVET BYTX I BESKONE^NYM), I PUSTX 'i(x) OBOZNA^AET FUNKCI@,WY^ISLQEMU@ MA[INOJ Mi. oPREDELIM FUNKCI@ f (x) SLEDU@]IM OBRAZOM:(f (x) = 1; ESLI tx(x) 6 T (x) I 'x (x) = 0;(12)0; INA^E:uTWERVDENIE.