Background Image
Previous Page  6 / 16 Next Page
Information
Show Menu
Previous Page 6 / 16 Next Page
Page Background

Обозначим через

k

чиcло подряд идущих вентилей в схеме. При

k

=

o

(

n

)

и

k

=

o

(

s

)

, можно утверждать на основании условия эквива-

лентности обратимых схем, что

C

(

n, s

)

6

r

s

+1

1

(

k

!)

b

s/k

c

(

r

1)

6

r

s

+1

1

(

k

!)

(

s/k

)

1

(

r

1)

.

(2)

Число всех четных подстановок на множестве

Z

n

2

равно

|

A

(

Z

n

2

)

|

=

= (2

n

)!

/

2

. По формуле Стирлинга

x

!

&

(

x/e

)

x

. Оценим величину

log

2

(

C

(

n, s

)

/

|

A

(

Z

n

2

)

|

)

:

log

2

C

(

n, s

)

|

A

(

Z

n

2

)

|

6

log

2

2

r

s

+1

(

k

!)

(

s/k

)

1

(

r

1)(2

n

)!

6

log

2

2

r

s

+1

e

2

n

+

s

k

k

s

k

(

r

1)2

n

2

n

;

log

2

C

(

n, s

)

|

A

(

Z

n

2

)

|

&

1 + (

s

+ 1) log

2

r

+ (2

n

+

s

k

) log

2

e

(

s

k

) log

2

k

log

2

(

r

1)

n

2

n

.

Согласно формуле (1),

r

6

n

3

:

log

2

C

(

n, s

)

|

A

(

Z

n

2

)

|

&

3

s

log

2

n

+ 2(2

n

+

s

k

)

(

s

k

) log

2

k

n

2

n

.

Выберем значение

s

так, чтобы выполнялось условие

log

2

(

C

(

n, s

)

/

|

A

(

Z

n

2

)

|

)

6

log

2

n

. Пусть

k

=

n/

log

2

n

, тогда

3

s

log

2

n

+ 2 2

n

+

s

n

log

2

n

s

n

log

2

n

(log

2

n

log

2

log

2

n

)

n

2

n

=

log

2

n

;

s

(2 log

2

n

+ 2 + log

2

log

2

n

) + 2

n

+1

2

n

log

2

n

+

n

n

log

2

log

2

n

log

2

n

n

2

n

=

log

2

n

;

s

=

n

2

n

+

o

(

n

2

n

)

2 log

2

n

+

o

(log

2

n

)

.

Очевидно, что при таком значении

s

величина

log

2

(

C

(

n, s

)

/

|

A

(

Z

n

2

)

|

)

→ −∞

при

n

→ ∞

, т.е. доля четных подстановок, которые задаются

обратимой схемой, состоящей из вентилей множества

Ω

2

n

и не исполь-

зующей дополнительные входы, с вентильной сложностью менее

s

,

стремится к нулю.

Следует отметить, что при указанном выборе значений

s

и

k

вы-

полняются условия

k

=

o

(

n

)

,

k

=

o

(

s

)

, таким образом, применение

формулы (2) корректно. Тогда

s

n

2

n

1

/

log

2

n

, откуда следует истин-

ность утверждения теоремы.

I

Асимптотическая верхняя оценка вентильной сложности.

В ра-

боте [7] был предложен алгоритм синтеза обратимых схем, состоящих

72 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2015. № 1