18c0693f

Оценка сложности построения таблицы ?-кортежей


В разд. «Минимальная инверсная машина»(см. стр. 17) введено понятие ?-пла (мюпла), который далее будем называть ?-кортежем. ?-кортеж представляет собой последовательность значений на выходе последних ? переходов, первый из которых появляется при переходе из заданного состояния КАМСИ.

PS

NS,z

x=0

x=1

A

C,0

D,1

B

D,0

С,1

C

А,0

B,0

D

C,1

D,1

(a)

 

A

B

C

D

00

+

 

+

 

01

 

+

+

 

10

 

+

 

+

11

+

 

 

+

(b)

 

 

 

PS

NS,x

 

z=0

z=1

S0

(A,0,0)

(C, 0,0),0

(C, 0,1),0

S1

(A,0,0)

(C,0,0),0

(C,0,1),0

S2

(A,1,1)

(D,1,0),1

(D,1,1),1

S3

(B,0,1)

(D,1,0),0

(D,1,1),0

S4

(B,1,0)

(C,0,0),1

(C,0,1),1

S5

(C,0,0)

(A,0,0),0

(B,0,1),1

S6

(C,0,1)

(B,1,0),1

(A,1,1),0

S1

(D,1,0)

(C,0,0),0

(C,0,1),0

S2

(D,1,1)

(D,1,0),1

(D,1,1),1

(c)[11]

 

 

 

PS

NS,x

z=0

z=1

S0

S5,0

S6,0

S1

S5,0

S6,0

S2

S1,1

S2,1

S3

S1,0

S2,0

S4

S5,1

S6,1

S5

S1,0

S3,1

S6

S4,1

S2,0

(d)

 

 

(e)

 

P

0

0

1

0

1

1

0

0

1

1

1

0

0

 

 

Au

A

C

A

D

C

B

C

A

C

B

C

B

D

C

 

E

 

0

0

1

1

0

1

0

0

0

1

0

0

1

 

SS

 

S0

S5

S1

S6

S2

S1

S6

S4

S5

S1

S6

S4

S5

S3

P

 

 

0

0

0

0

1

0

1

1

0

0

1

1

1

P

0

0

1

0

1

1

0

0

1

1

1

0

0

 

 

SS

S0

S5

S1

S6

S4

S6

S2

S1

S5

S3

S2

S2

S1

S5

 

E

 

0

0

0

1

1

0

1

0

1

0

1

1

0

 

Au

 

A0

C

A

C

B

C

A

D

C

B

D

D

D

C

P

 

 

0

0

0

0

1

0

1

1

0

0

1

1

1
<
(f)

 

Table 11

Построим таблицу ?-кортежей, которая состоит из 2?  строк и N столбцов. Для заполнения клетки таблицы, которая расположена в j-ой строке и p-ом столбце следует проверить, существует ли переход из p-го

состояния, который порождает j-ый  ?-кортеж на выходе кодирующего КАМСИ. Если кортеж существует, то соответствующую клетку необходимо отметить (в Table 11(b) клетка отмечена крестиком, см. стр. 23).

Не трудно показать, что для заполнения одной клетки таблицы следует проверить ? переходов, и, учитывая, что общее число клеток равно N•2?, общее число операций, которые необходимо выполнить равно ?=N•?•2?. 

 

Кратн.

Комп.

 Число сост. табл. перех.

N

 Число операций опр.

?-порядка 



?

 Число опер. заполн. табл. корт. инверт.

?=N?2?


Общ. число опер. для постр. инверт.

2?•(3N + 2?)
a

 b

 c

 d

 e

 f

 h
1

 5

 ?25

 6

 ?211

 ?211

 ?212
2

 25

 ?210

 12

 ?222

 ?222

 ?224
3

 125

 ?215

 18

 ?229

 ?229

 ?236
4

 250

 ?217

 24

 ?236

 ?236

 ?248
5

 1250

 ?221

 30

 ?245

 ?245

 ?260?1018
6

 6250

 ?226

 36

 ?253

 ?253

 ?272?1022
7

 31250

 ?231

 42

 ?262

 ?262

 ?284?1025
8

 156250

 ?235

 48

 ?270

 ?270

 ?296?1029
ПРИМЕЧАНИЕ. В таблице приведен пример оценки числа операций для КАМСИ, заданного таблицей переходов с пятью состояниями (первая строка). В строках 2 .. 8 приведены значения для композиции автоматов (см. ниже)

  
Table 12

В Table 12 в столбцах (d,e)  показано, как изменяется  сложность построения таблицы ?-кортежей  (?, ? = N?2?) в зависимости от ?.

Так как конечной целью построения таблицы ?-кортежей является построение таблицы переходов инверсного автомата, то оценим сложность построения таблицы переходов инверсного автомата. Число строк в такой таблице равно числу заполненных клеток в таблице ?-кортежей (см. выше). Не трудно показать, что оно  ?2?.



Оценим величины компонентов, из которых складывается сложность построения таблицы переходов для инверсного автомата: