Алексеев - Сложность алгоритмов (1123759), страница 7
Текст из файла (страница 7)
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. fUNKCIQ f (x) WY^ISLIMAQ A SLEDOWATELXNO OB]EREKURSIWNAQdOKAZATELXSTWO oPI[EM ALGORITM WY^ISLENIQ f (x). pO ZADANNOMU x 2 Z + NAHODIM PROGRAMMU MA[INY Mx (SM. TEOREMU).
wY^ISLQEM T (x) (TAK KAK T (x) - OB]EREKURSIWNA, TO DLQ \TOGO SU]ESTWUETALGORITM). iMEQ PROGRAMMU MA[INY Mx, MODELIRUEM EE RABOTU W TE^ENIE T (x) TAKTOW, WZQW W KA^ESTWE WHODNOGO SLOWA KOD ^ISLA x. eSLI ZAT (x) TAKTOW MA[INA OSTANOWITSQ I REZULXTATOM BUDET KOD ^ISLA 0, TOWYDAEM OTWET 1, INA^E WYDAEM OTWET 0. mODELIRUQ RABOTU MA[INY, MYMOVEM RABOTATX TOLXKO S TOJ ^ASTX@ LENTY, NA KOTOROJ ZAPISYWAETSQWHODNOE SLOWO, A TAKVE KOTORAQ POSE]AETSQ GOLOWKOJ WO WREMQ RABOTY.tOGDA NA KAVDOM [AGE NAM DOSTATO^NO HRANITX LI[X KONE^NYJ KUSOKLENTY, ^TO POZWOLQET OPREDELITX SODERVIMOE LENTY I POSLE OSTANOWAMA[INY.
sLEDOWATELXNO, WESX PROCESS WY^ISLENIQ f (x) ALGORITMI^EN.w SOOTWETSTWII S TEZISOM tX@RINGA SU]ESTWUET MA[INA tX@RINGA,KOTORAQ WY^ISLQET f (x). mY PRIMEM ZDESX \TO UTWERVDENIE, HOTQ DLQOPISANNOJ FUNKCII f (x) MOVNO I QWNO POSTROITX WY^ISLQ@]U@ EEMA[INU tX@RINGA (PRAWDA, DOLGO I GROMOZDKO).pUSTX MA[INA Mi WY^ISLQET f (x), TO ESTX f (x) = 'i(x). w^ASTNOSTI 'i (i) = f (i) I ZNA^IT OPREDELENO. dOPUSTIM, ^TO ti(i) 6 T (i).tOGDA PO OPREDELENI@ f (x) POLU^AEM: ESLI 'i (i) = 0, TO f (i) = 1, A ESLI'i(i) =6 0, TO f (i) = 0.
w L@BOM SLU^AE f (i) =6 'i(i) | PROTIWORE^IE.sLEDOWATELXNO (OT PROTIWNOGO) ti(i) > T (i). tEOREMA DOKAZANA.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)SU]ESTWUET BESKONE^NOE ^ISLO ZNA^ENIJ x DLQ KOTORYH WYPOLNQETSQNERAWENSTWO ti (x) > T (x)dOKAZATELXSTWO pUSTX g(x) = x ; (bpxc)2. tOGDA FUNKCIQ g(x) WY^ISLIMA I WS@DU OPREDELENA (TO ESTX OB]EREKURSIWNA).
pRI x = 0; 1; 2; 3; : : : FUNKCIQ g(x) PRINIMAET ZNA^ENIQ.|,,-..-,12,,,..390,0; 0; 1; 2; 0; 1; 2; 3; 4; 0; 1; : : : . lEGKO DOKAZATX, ^TO FUNKCIQ g(x) PRINIMAET KAVDOE ZNA^ENIE IZ Z + BESKONE^NOE ^ISLO RAZ. oPREDELIM FUNKCI@f (x) SLEDU@]IM OBRAZOM:(f (x) = 1; ESLI tg(x)(x) 6 T (x) I 'g(x) (x) = 0;(13)0; INA^E:tOGDA FUNKCIQ f (x) OB]EREKURSIWNA (DOKAZYWAETSQ TAK VE, KAKW PREDYDU]EJ TEOREME).
pUSTX MA[INA Mi WY^ISLQET f (x), TO ESTXf (x) = 'i(x). pUSTX j - L@BOE ^ISLO, TAKOE, ^TO g(j ) = i (TAKIH jBESKONE^NO MNOGO). dOPUSTIM, ^TO ti (j ) 6 T (j ). tOGDA PO OPREDELENI@f (x) POLU^AEM: ESLI 'i (j ) = 0, TO f (j ) = 1, A ESLI 'i (j ) 6= 0 , TOf (j ) = 0. w L@BOM SLU^AE f (j ) 6= 'i (j ) - PROTIWORE^IE. sLEDOWATELXNO,ti(j ) > T (j ). tEOREMA DOKAZANA.sPRAWEDLIWO E]E BOLEE SILXNOE UTWERVDENIE, KOTOROE MY PRIWEDEM BEZ DOKAZATELXSTWA.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@]EJf (x) MNOVESTWO TEH x DLQ KOTORYH ti(x) 6 T (x) KONE^NOtEOREMY POKAZYWA@T, ^TO SU]ESTWU@T SKOLX UGODNO SLOVNO WY^ISLIMYE OB]EREKURSIWNYE FUNKCII S DWUMQ ZNA^ENIQMI (ILI, ^TO\KWIWALENTNO, SKOLX UGODNO SLOVNO RASPOZNAWAEMYE QZYKI).
wOZNIKAETWOPROS: A KAKOJ WOOB]E MOVET BYTX SLOVNOSTX ZADA^ (QZYKOW)? sU]ESTWENNYJ OTWET NA \TOT WOPROS DAET SLEDU@]AQ TEOREMA, KOTORU@MY PRIWODIM BEZ DOKAZATELXSTWA.tEOREMA. pUSTX OB]EREKURSIWNYE FUNKCII t(n) I T (n) TAKOWYT(n)^TO t(n) log2 t(n) ! 1 PRI n ! 1 tOGDA SU]ESTWUET QZYK L KOTORYJ RASPOZNAETSQ NEKOTOROJ MA[INOJ tX@RINGA S ^ISLOM [AGOW NEBOLEE T (n) DLQ WSEH WHODNYH SLOW L@BOJ DLINY n I NE RASPOZNAETSQNIKAKOJ MA[INOJ tX@RINGA S ^ISLOM [AGOW t(n)|TA TEOREMA POKAZYWAET, ^TO WOZMOVNYE FUNKCII SLOVNOSTIQZYKOW OBRAZU@T DOWOLXNO PLOTNOE MNOVESTWO.
mOVNO LI POLU^ITXREZULXTAT O BOLX[EJ PLOTNOSTI W OB]EM SLU^AE NEIZWESTNO. oDNAKODLQ ODNOGO WAVNOGO INTERWALA MY SEJ^AS POLU^IM OTRICATELXNYJ OTWET. a IMENNO, MY POKAVEM, ^TO NE SU]ESTWUET QZYKOW SO SLOVNOSTX@RASPOZNAWANIQ PO PORQDKU MEVDU n I n log n.-,012,,,,,.,.,().40-rEGULQRNYE QZYKIrEGULQRNYE QZYKI | \TO QZYKI, RASPOZNAWAEMYE AWTOMATAMI. w\TOM KONTEKSTE AWTOMAT MOVNO OPREDELITX KAK MA[INU tX@RINGA SOSLEDU@]IMI OGRANI^ENIQMI: GOLOWKA MA[INY NA KAVDOM [AGE DWIVETSQ WPRAWO ILI MA[INA OSTANAWLIWAETSQ; MA[INA OSTANAWLIWAETSQTOGDA I TOLXKO TOGDA, KOGDA GOLOWKA OBOZREWAET SIMWOL ; MA[INAOSTANAWLIWAETSQ W ODNOM IZ DWUH SOSTOQNIJ q0 ("PRINQTX") ILI q00("OTWERGNUTX").oPREDELENIE. pUSTXC - LENTO^NYJ ALFAWIT AWTOMATA M I A =C nfg.
pUSTX L A . bUDEM GOWORITX, ^TO AWTOMAT M RASPOZNAETQZYK L, ESLI DLQ L@BOGO SLOWA a 2 A RABOTA M PRI WHODNOM SLOWEa (W STANDARTNOJ NA^ALXNOJ KONFIGURACII) ZAKAN^IWAETSQ SOSTOQNIEMq0, ESLI a 2 L, I ZAKAN^IWAETSQ SOSTOQNIEM q00 , ESLI a 2= L.oPREDELENIE. pUSTX A - NEKOTORYJ ALFAWITI L A - NEKOTORYJ QZYK W ALFAWITE A. dLQ KAVDOGO SLOWA a 2 A OSTATO^NYJ QZYKLb OPREDELIM SLEDU@]IM OBRAZOMb 2 La () ab 2 L:qZYK NAZYWAETSQ REGULQRNYM, ESLI U NEGO LI[X KONE^NOE ^ISLO RAZLI^NYH OSTATO^NYH QZYKOW. (zDESX RASSMATRIWAETSQ I b = | PUSTOESLOWO; PRI \TOM 2 La () a 2 L).w TEORII AWTOMATOW I QZYKOW DOKAZYWAETSQ SLEDU@]AQ TEOREMA(SM., NAPRIMER, [ ]).tEOREMA.
qZYK RASPOZNAWAEMYJ L@BYM AWTOMATOM REGULQREN dLQ L@BOGO REGULQRNOGO QZYKA SU]ESTWUET RASPOZNA@]IJ EGOAWTOMATsLEDSTWIE. eSLI QZYK L REGULQREN TO DLQ NEGO SU]ESTWUETRASPOZNA@]AQ EGO MA[INA tX@RINGA WREMQ RABOTY KOTOROJ ^ISLO[AGOW NA KAVDOM WHODNOM SLOWE DLINY n RAWNO n + 1oKAZYWAETSQ, ^TO NE SU]ESTWUET QZYKOW, DLQ RASPOZNAWANIQ KOTORYH NA MA[INAH tX@RINGA DOSTATO^NO WREMENI SU]ESTWENNO MENX[EGO, ^EM n log2 n (n - DLINA WHODNOGO SLOWA) I NE DOSTATO^NO WREMENIn + 1.
bOLEE TO^NO \TO WYRAVAETSQ W PRIWODIMYH NIVE TEOREMAH.oPREDELENIE. rASSMOTRIM TO^KU NA LENTE MA[INY tX@RINGAMEVDU Q^EJKAMI S NOMERAMI i I i + 1. sLEDOM W \TOJ TO^KE PRI RABOTEMA[INY NA NEKOTOROM WHODNOM SLOWE BUDEM NAZYWATX POSLEDOWATELXNOSTX WSEH SOSTOQNIJ, W KOTORYE PEREHODIT MA[INA, KOGDA EE GOLOWKASME]AETSQ IZ Q^EJKI i W Q^EJKU i + 1 ILI NAOBOROT (TO ESTX PROHODITNAD \TOJ TO^KOJ).1),,-.
2).,,)(.41tEOREMA. pUSTX MA[INA tX@RINGA M RASPOZNAET QZYK L AI PUSTX SU]ESTWUET KONSTANTA c > 0 TAKAQ ^TO PRI RABOTE M NAL@BOM WHODNOM SLOWE a 2 A DLINA SLEDA W L@BOJ TO^KE NE PREWOSHODIT c tOGDA L REGULQRNYJ QZYK LEDOWATELXNO SU]ESTWUETAWTOMAT RASPOZNA@]IJ L S c = 1dOKAZATELXSTWO pUSTX a 2 A.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
