Метода

pRIMER

A[INA tX@RINGA

x

x

KOTORAQ

ML : q1001 0 ` q001 0 ,

3. M x

SDWIGAET SLOWO 1

NA ODNU Q^EJKU WLEWO, MOVET IMETX PROGRAMMU,

SOSTOQ@]U@ IZ SLEDU@]IH KOMAND:

q10 ! q20R, q20 ! q31R, q31 ! q31R, q30 ! q40L,

q41 ! q50L, q51 ! q51L, q50 ! q00E.

x2. wY^ISLENIE FUNKCIJ MA[INAMI tX@RINGA

bUDEM PREDSTAWLQTX NABOR ^ISEL (x1; : : : ; xn)

TAKIM OBRAZOM:

01x1 01x2 0 : : : 01xn 0 .

oPREDELENIE 1. mA[INA T

PRAWILXNO WY^ISLQET FUNKCI@

y = f(x1; : : : ; xn) ,

GDE xi; y

2

N0 , ESLI DLQ (x1; : : : ; xn)

2

D(f)

WERNO, ^TO T : q101x1 01x2 0 : : : 01xn 0

`

q001y0 , GDE y = f(x1; : : : ; xn) ,

A DLQ

WERNO

x1

x2

xn

(x1 ; : : : ; xn) 2= D(f)

,

^TO

T

: q1

01 01 0 : : : 01 0 ` .

zADA^A 1

pOSTROITX M

T

x

KOTORAQ PRAWILXNO

.

Z

: q101 0 ` q000 ,

-

WY^ISLQET FUNKCI@ Z(x)

0 .

rE[ENIE. mA[INA tX@RINGA Z MOVET IMETX SLEDU@]U@ PRO-

GRAMMU

0

! q2

0R , q21

! q21R

, q20 ! q30L , q31 ! q30L ,

: q1

q30 ! q00E .

|TA MA[INA SNA^ALA, IDQ WPRAWO, PERE[AGIWAET ^EREZ ^ISLO x ,

ZATEM, IDQ WLEWO, ZAMENQET EGO EDINICY NA NULI I OSTANAWLIWAETSQ

W STARTOWOJ Q^EJKE.

zADA^A 2

pOSTROITX M

T

x

x+1

KOTORAQ PRA

.

N

: q1

01 0 ` q001

0 ,

-

-

WILXNO WY^ISLQET FUNKCI@ N(x) = x + 1 .

rE[ENIE. mA[INA tX@RINGA N MOVET IMETX SLEDU@]U@ PRO-

GRAMMU

0

! q2

0R , q21

! q21R

, q20 ! q31L , q31 ! q31L ,

: q1

1)

q10 ! q20R {

NA^ALO RABOTY

,

[AG WPRAWO

;

2) q20 ! q00L {

W SLU^AE

x = 0

DOSTATO^NO WERNUTXSQ NAZAD I

OSTANOWITXSQ, T.K. sg(0) = 0;

3)

q21 ! q31R {

ESLI

x >

0,

TO SOHRANQEM ODNU EDINICU

,

T

K

.

.

sg(x) = 1 I DELAEM [AG WPRAWO;

4)

q31 ! q30R {

ZAMENQEM OSTALXNYE EDINICY ^ISLA

x

NA NU

-

LI, IDQ WPRAWO;

5)

q30 ! q40L {

DO[LI DO KONCA ^ISLA

x

I DELAEM [AG WLEWO

;

6)

q40 ! q40L {

PROSKAKIWAEM WLEWO ^EREZ WSE NULI

;

7)

q41 ! q01L {

DO[LI DO SOHRANENNOJ EDINICY I OSTANAWLI

-

1) q10 ! q20R {

NA^ALO RABOTY

,

[AG WPRAWO

;

2) q21 ! q30R {

OSTAWILI METKU

0;

3) q31 ! q31R {

PROSKO^ILI WPRAWO ^EREZ OSTAW[IESQ EDINI

-

CY ^ISLA x;

4) q30 ! q40R {

DO[LI DO

0

MEVDU ^ISLOM

x

I EGO KOPIEJ

;

5) q41 ! q41R {

PROSKO^ILI WPRAWO ^EREZ RANEE SKOPIROWAN

-

NYE EDINICY;

6) q40 ! q51L {

SKOPIROWALI O^EREDNU@ EDINICU

;

42

EDINICY ^ISLA x;

10) q60 ! q21R

{

DO[LI DO OSTAWLENNOJ METKI

,

ZAMENILI EE NA

EDINICU I "ZACIKLILISX" NA KOMANDU 2 DLQ

KOPIROWANIQ O^EREDNOJ EDINICY ^ISLA x;

11) q20 ! q70L

{

WYHOD IZ CIKLA

,

WSE EDINICY SKOPIROWANY I

NADO WOZWRA]ATXSQ NA STARTOWU@ Q^EJKU;

12) q71 ! q71L

{

PROSKO^ILI WLEWO ^EREZ ^ISLO

x;

13) q70 ! q00E

{

OSTANOWILISX NA STARTOWOJ Q^EJKE

.

oTWET. mA[INA C MOVET IMETX SLEDU@]U@ PROGRAMMU:

fq10 ! q20R, q21

! q30R, q31

! q31R, q30

! q40R,

q41

! q41R,

q40

! q51L, q51

! q51L, q50

! q60L,

q61

! q61L,

q60 ! q21R, q20 ! q70L, q71

! q71L,

q70 ! q00Eg.

x4. pERESTANOWKA ^ISEL MA[INOJ tX@RINGA

zADA^A

pOSTROITX M

T

x y

` 01

y

x

KOTORAQ

.

T R : 01 q101 0

q001 0 ,

-

PERESTAWLQET MESTAMI DWA ^ISLA x I y .

6) q40 ! q51E {

WOSSTANOWILI ^ISLO

y,

TEM SAMYM SDWINUW

EGO WLEWO NA ODNU Q^EJKU;

7)

q51 ! q61L

{

PERE[LI NA PRAWU@ EDINICU ^ISLA xl;

8)

q61 ! q70R

{

UMENX[ILI xl NA 1, ESLI xl > 0;

9) q71

! q71R {

PROSKO^ILI WPRAWO ^EREZ ^ISLO

y;

10)

q70 ! q81L

{

UWELI^ILI xr NA 1 I [AG WLEWO;

11)

q81

! q90L

{

W SLU^AE

y > 0

UMENX[AEM EGO NA

1;

12)

q91 ! q91L

{

PROSKO^ILI WLEWO ^EREZ ^ISLO y

; 1;

13)

q90 ! q51E

{

WOSSTANOWILI ^ISLO

y

I

"

ZACIKLILISX

"

NA KO

-

MANDU 7 DLQ PERENOSA WLEWO O^EREDNOJ EDI-

NICY ^ISLA xl;

14)

q60 ! q100R

{

^ISLO xl = 0, PERESTANOWKA ^ISEL ZAWER[ENA,

[AG WPRAWO;

15)

q101 ! q101R

{

PROSKO^ILI WPRAWO ^EREZ ^ISLO

y;

16)

q100 ! q00E

{

OSTANOWILISX MEVDU ^ISLAMI

y

I

x,

KONEC

SLU^AQ y > 0;

17)

q30 ! q111L

{

NA^ALO ^ASTI PROGRAMMY DLQ OBRABOTKI SLU

-

^AQ y = 0; W \TOM SLU^AE NADO PROSTO SDWI-

NUTX x NA ODNU Q^EJKU WPRAWO, DLQ ^EGO EGO

SNA^ALA UWELI^ILI SPRAWA NA 1;

18)

q111 ! q111L

{

PROSKO^ILI WLEWO ^EREZ ^ISLO

x;

19)

q110 ! q120R

{

[AG WPRAWO

;

20)

q121 ! q00E

{

WOSSTANOWILI ^ISLO

x

I OSTANOWILISX

MEVDU

^ISLAMI y = 0 I x.

oTWET. mA[INA T R MOVET IMETX SLEDU@]U@ PROGRAMMU:

fq10 ! q20R, q21

! q21R,

q20

! q30L,

q31

! q40L,

q41

! q41L,

q40

! q51E,

q51

! q61L,

q61

! q70R,

q71

! q71R,

q70

! q81L,

q81

! q90L,

q91

! q91L,

q90

! q51E,

q60

! q100R,

q101 ! q101R, q100

! q00E,

q30 ! q111L,

q111 ! q111L, q110 ! q120R, q121 ! q00Eg.

x5. kOMPOZICIQ MA[IN tX@RINGA

oPREDELENIE 1. pUSTX T1 = (A; Q1; P1) ,

T2 = (A; Q2; P2) |

DWE MA[INY tX@RINGA S OB]IM ALFAWITOM

0

0

0

A , Q1 = fq0

; q1; : : : ; qrg ,

00

00

00

Q2 = fq0

; q1 ; : : : ; qs g .

kOMPOZICIEJ T1 I

T2

PO PARE SOSTOQNIJ

(q0

; q0 ) NAZYWAETSQ MA[INA tX@RINGA T q0q0

T

= (A; Q; P) , U KO-

i

j

q

0

; q

0

0

; q

00

; : : : ; q

00

1 i j

2

q

0

I

TOROJ Q =

f

0

1

; : : : ; q

1

s g

S NA^ALXNYM SOSTOQNIEM

1

r

q

0

P =

~

~

,

~

ZAKL@^ITELXNYM SOSTOQNIEM

; PROGRAMMA

P1

P2

P1

PO-

0

LU^AETSQ IZ P1

ZAMENOJ ZAKL@^ITELXNOGO SOSTOQNIQ[q0

NA q00

, A

~

i

1

PROGRAMMA

POLU^AETSQ IZ P2

ZAMENOJ ZAKL@^ITELXNOGO SOSTO-

P2

QNIQ q00 NA

q0 .

0

j

kOMPOZICIQ

T1 I

T2

PO PARE SOSTOQNIJ

(q0

; q0 )

NAZYWAETSQ

0

0

PROSTO KOMPOZICIEJ T1

I T2

I OBOZNA^AETSQ T1 T2 .

sMYSL KOMPOZICII

0

0

SOSTOIT W TOM

^TO

T1qiqj

T2 = (A; Q; P)

,

0

, W

SNA^ALA RABOTAET MA[INA

T1 ,

POKA NE PEREJDET W SOSTOQNIE q

i

\TOT MOMENT NA^INAET RABOTATX M-T T2 ; POSLE OKON^ANIQ EE RABO-

TY M-T T

PEREHODIT W SOSTOQNIE

q0 I PRODOLVAET RABOTATX DO

1

j

POLU^ENIQ OKON^ATELXNOGO REZULXTATA.

w SLU^AE OBY^NOJ KOMPOZICII T1 T2 SNA^ALA RABOTAET M-T T1 .

eSLI ONA ZAWER[IT SWO@ RABOTU

T

E

. T1 : K1 ` K2 ,

TO S KONFIGURA

0

,

.

-

CIEJ K2 , POLU^ENNOJ IZ K2

ZAMENOJ ZAKL@^ITELXNOGO SOSTOQNIQ

M-T T1 NA NA^ALXNOE SOSTOQNIE M-T T2 , NA^INAET RABOTATX MA[I-

NA tX@RINGA

T2 . eSLI ONA ZAWER[IT SWO@ RABOTU, TO OSTANOWKA

PROISHODIT PRI FORMALXNOM PEREHODE W M-T T1 .

sLEDU@]IE SWOJSTWA NEPOSREDSTWENNO WYTEKA@T IZ OPREDELENIQ

KOMPOZICII.

sWOJSTWO 1.

eSLI T1 : K1

` K2 ,

A T2 : K20 ` K3 , TO KOMPOZICIQ

T1 T2 : K1

` K3 .

0: K1

` , TO KOMPOZICIQ T1 T2 : K1 ` . eSLI

zAME^ANIE. eSLI T1

T1 : K1 ` K2 , NO T2 : K2

`

, TO T1

T2 : K1 ` .

! N0 ,

sWOJSTWO 2.

eSLI M-T T1

PRAWILXNO WY^ISLQET f : N0

A T2 PRAWILXNO WY^ISLQET

g :

N0

! N0 , TO

T1 T2

PRAWILXNO

WY^ISLQET f

g : N0 ! N0 .

zADA^A 1.

pOSTROITX MA[INU MLCn , KOTORAQ OSU]ESTWLQET

CIKLI^ESKIJ SDWIG NABORA IZ

n ^ISEL NA ODNO ^ISLO WLEWO,

T.E.

MLCn : q101x1 0 : : : 01xn 0

` q001x2 0 : : : 01xn 01x1 0 .

rE[ENIE. pOSTROIM MA]INU MLCn W WIDE KOMPOZICII NESKOLX-

HR : K01

` K2,

r

GDE K2 = x1rx2

: : : xn;

T R : K

20

`

K3,

GDE K3

= x2 x1x3 : : : xn;

r

HR : K03

` K4,

GDE K4

= x2x1rx3 : : : xn;

T R : K

4

`

K5,

GDE K5

.

x1x4 : : : xn;

= x2x3

.

.

HR : K20n;3

K2n;2,

GDE K2n;2 = x2x3 : : : xn;1x1rxn;

T R : K

0

` K2n;1,

GDE K2n;1 = x2x3 : : : xn;1xnrx1;

n;1

2n;20

`

r

HL

: K2n;1 ` Kr

,

GDE Kr =

x2x3

: : : xn;1xnx1.

KONFIGURACIQ DLQ Ci

IMEET WID K1 = rx1x2 : : : xi . dALEE RASSMOT-

RIM POSLEDOWATELXNO KOMPOZICI@ SLEDU@]IH MA[IN:

HRi;1 : K1

`

K2,

GDE K2 = x1x2 : : : xi;1rxi;

C :

0

,

GDE K3 = x1x2 : : : xi;1

r

xixi;

K2

` K3

HLi;1 : K30

` K4,

GDE K4 = rx1x2 : : : xi;1xixi;

MLCi;1

: K

0

`

K5,

GDE K5 = rxixix1x2

: : : xi;1;

i2+1

0

4

r

HR

:

K50

` K6,

GDE K6 = xixirx1x2

: : : xi;1;

Ci;1

: K

60

`

K7,

GDE K7 = xixi x1x2

: : : xi;1x1x2 : : : xi;1;

2

r

HL

: K7

0` K8,

GDE K8 = rxixix1x2

: : : xi;1x1x2 : : : xi;1;

MLC2i : K08

` K9,

GDE K9 = rxix1x2 : : : xi;1x1 x2 : : : xi;1xi;

MLCi : K9

` Kr,

GDE Kr

=

x1x2 : : : xi;1xix1x2 : : : xi;1xi.

pOSKOLXKU KONFIGURACIQ

Kr

QWLQETSQ ISKOMOJ PRI KOPIROWA-

NII i ^ISEL,

TO W KA^ESTWE MA[INY Ci MOVNO WZQTX KOMPOZICI@

MLCk;1 : K

1

`

K

,

GDE K

= rx x

k+1

: : : x x x : : : x

k;1

;

n

2

2

k

n 1 2

n;1

0

,

GDE K3

= xk xk+1 : : : xnx1x2 : : : xk;2

r

xk;1;

HR

: K2

`

K3

(Z HL)n;1 : K30

` Kr,

GDE Kr = rxk.

oTWET. INK = MLCnk;1 HRn;1 (Z HL)n;1 .

dOKAZATELXSTWO. pO USLOWI@ FUNKCIQ h(x; y)

PRAWILXNO WY^IS-

LIMA

ZNA^IT SU]ESTWUET M

T

x y

`

h(x;y)

pUSTX

M

T

,

c

-

H : q101 01 0

q001

0 .

G : q100 ` q001 0

WY^ISLQET ZNA^ENIE

f(0) .

pOSTROIM MA[INU

-

` q001

f(x)

tX@RINGA

F : q101

x

0

0

W ^ETYRE \TAPA

.

` K1r ,

x

A

nA PERWOM \TAPE POSTROIM

T1 : K11

GDE

K11

= q101 0 ,

K1r = q001

x

001

c

0 . oNA RAWNA KOMPOZICII SLEDU@]IH MA[IN:

HR2 : K11

`

K12,

GDE K12 = 01x0q00;

G :

K

0

`

GDE K13 = 01

x

0q001

c

0;

120

K13,

2

` K1r,

GDE K1r = q001

x

c

HL

: K13

001

0.

4) q40 ! q50R {

[AG WPRAWO

;

x;i

5) q51 ! q51R {

PERESKO^ILI WPRAWO ^EREZ

1

;

6) q50 ! q61L {

UWELI^ILI ^ISLO

i

NA

1;

7) q61 ! q70L

{

UMENX[ILI ^ISLO x

; i NA 1;

8) q71 ! q71L {

PERESKO^ILI WLEWO ^EREZ

1

x;i;1

;

9) q70 ! q10E

{

POLU^ILI q101x;i;101i+101f(i+1)0 I ZACIKLI-

LISX NA KOMANDU 1;

10) q20 ! q00L

{

WYHOD IZ CIKLA

,

POLU^ILI

KONFIGURACI@

K3r = q0001x01f(x)0.

nA ^ETWERTOM \TAPE POSTROIM MA[INU T4 : K41 ` K4r , GDE

K41 = K30r

= q1001x01f(x)0 , A K4r = q001f(x)0

{ ITOGOWAQ KONFI-

GURACIQ. oNA RAWNA KOMPOZICII SLEDU@]IH MA[IN:

HR2 : K41

` K42,

GDE K42 = 001xq001f(x)0;

T R : K420

` K43,

GDE K43 = 001f(x) q001x0;

Z : K430 ` K44,

GDE K44 = 001f(x) q00;

dOKAZATELXSTWO. dLQ PROSTOTY OGRANI^IMSQ SLU^AEM

n = 1 .

pOSKOLXKU P(x; t)

{ WY^ISLIMYJ PREDIKAT, TO SU]ESTWUET M-T P A ,

KOTORAQ WY^ISLQET HARAKTERISTI^ESKU@ FUNKCI@ JP (x; t) S SOHRA-

NENIEM ARGUMENTOW

,

T E

. P A : q101

x

01

t

0 ` q001

x

01

t

01

JP (x;t)

0 .

tREBU

-

.

ETSQ POSTROITX M-T F , WY^ISLQ@]U@ FUNKCI@ f(x) = t P (x; t) ,

T E

x

`

f(x)

sNA^ALA POSTROIM WSPOMOGATELXNU@

. F : q101 0

q001

0 .

.

K2 = 01x01f(x)q00

MA[INU T : K1

`

K2 , GDE K1 = q101x0 ,

SO SLE-

DU@]IMI KOMANDAMI:

1) q10 ! q20E {

NA^ALO RABOTY

;

2) (q2; q3)P A HR2 {

PO PARE SOSTOQNIJ (q2; q3) PODKL@^ILI M-T

P A

HR2, W REZULXTATE POLU^ILI KONFI-

GURACI@ 01x010q301JP (x;0)0;

3) q30 ! q40R

{

[AG WPRAWO;

7) q70 ! q10E {

ZACIKLILISX NA KOMANDU

1

DLQ WY^ISLENIQ

JP (x; t) DLQ SLEDU@]EGO ZNA^ENIQ t;

50