Громкович Ю. Теоретическая информатика. Введение в теорию автоматов, теорию вычислимости, теорию сложности, теорию алгоритмов, рандомизацию, теорию связи и криптографию
Подождите немного. Документ загружается.
x
0
x
1
y
0
y
1
(0, 0)
(0, 0)
(1, 0)
(0, 1)
(1, 1)
(2, 1)
r β But
r
(r +
1) · 2
r
r + 1 2
r
j = 0, 1, . . . , 2
r
− 1
• x x
j
(0, w) Number (w) = j
• y y
j
(r, w
0
) Number (w
0
) = j
(i, j) (i, w) w
Number (w) = j
(i, x) (i + 1, y)
• x = y
• x y i
r = 2
(x
d
, y
c
), d, c ∈ {0, 1, . . . , 2
r
− 1},
x
d
y
c
a
k
, b
k
∈ {0, 1} k = 0, 1, . . . , r − 1
d = Number(a
0
a
1
. . . a
r−1
) c = Number(b
0
b
1
. . . b
r−1
).
(0, a
0
a
1
. . . a
r−1
) x x
d
(r, b
0
b
1
. . . b
r−1
)
y y
c
a
0
= b
0
{(0, a
0
a
1
. . . a
r−1
), (1, a
0
a
1
. . . a
r−1
)}.
a
0
6= b
0
45
0
46
47
0 0 1 1 1 2
{(0, a
0
a
1
. . . a
r−1
), (1, b
0
a
1
. . . a
r−1
)}.
1 1
(1, b
0
a
1
. . . a
r−1
).
(0, a
1
. . . a
r−1
) (r, b
0
b
1
. . . b
r−1
)
k
(k, b
0
b
1
. . . b
k−1
a
k
a
k+1
a
k+2
. . . a
r−1
)
(k+1)
{(k, b
0
b
1
. . . b
k−1
a
k
a
k+1
. . . a
r−1
), (k + 1, b
0
b
1
. . . b
k
a
k+1
. . . a
r−1
)}.
s
s a
s
b
s
But
r
x y
r But
r
(b
r
2
c, b
0
b
1
. . . b
br/2c
a
br/2c+1
. . . a
r−1
)
{(0, f
0
f
1
. . . f
br/2c
a
br/2c+1
. . . a
r−1
| f
i
∈ {0, 1} i = 0, 1, . . . , b
r
2
c}
{(r, b
0
b
1
. . . b
br/2c
e
br/2c+1
. . . e
r−1
) | e
j
∈ {0, 1}
j = b
r
2
c + 1, . . . , r − 1}.
2
r
2
−1
2
But
r
Benes
1
But
1
Benes
3
2
r
2r + 1 2
r
But
1
But
3
r + 1
r β
r + 1 r β
2
r
48
But
r
Benes
r
r β
x
0
x
1
x
2
x
3
x
4
x
5
x
6
x
7
y
0
y
1
y
2
y
3
y
4
y
5
y
6
y
7
Benes
r
r ≥ 2
Benes
r
Benes
r−1
2
r−1
Benes
r−1
A 2
r−1
Benes
r−1
B
r
Benes
r
r Benes
r
2
r
(i
0
, . . . , i
2
r
−1
),
x
0
x
1
x
2
r−1
−1
x
2
r−1
x
2
r−1
x
2
r−1
+1
y
0
y
1
y
2
r−1
−1
y
2
r−1
y
2
r−1
y
2
r−1
+1
Benes
r −1
Benes
r −1
A B
2
r
x
j
y
i
j
j = 0, 1, . . . , 2
r
−1
2
r
(i
0
, . . . , i
2
r
−1
)
r r = 1 Benes
1
2
r ≥ 2 Benes
r−1
(0, 1, . . . , 2
r−1
−1) 2
r−1
2
r−1
x 2
r−1
y Benes
r
Benes
r−1
A B
β But
r
• A
• A B
(0, 1, . . . , 2
r−1
− 1)
49
Benes
r
v A B
Benes
r
u A B
x
0
x
2
r−1
x
i
x
i+2
r−1
y
j
y
j+2
r−1
y
i
2
r−1
y
i
0
+2
r−1
mod 2
r
y
i
2
r−1
+2
r−1
y
i
0
A
A
B
B
i ∈ { 0, 1, . . . , 2
r−1
} x
x
i
x
i+2
r−1
,
50
v Benes
r
51
u
Benes
r
Benes
r−1
A B
j ∈ {0, 1, . . . , 2
r−1
} y
y
j
y
j+2
r−1
,
Benes
r−1
(i
0
, i
1
, . . . , i
2
r
−1
)
(0, 1, . . . , 2
r
− 1)
(x
0
, y
i
0
)
(x
2
r−1 , y
i
2
r−1
).
x
0
y
i
0
A x
2
r−1
y
i
2
r−1
B
|i
2
r−1
− i
0
| = 2
r−1
,
|i
2
r−1
− i
0
| 6= 2
r−1
y
y
i
0
+2
r−1
mod 2
r
B y
y
i
2
r−1
+2
r−1
mod 2
r
A
x
q+2
r−1
mod 2
r
x
s+2
r−1
mod 2
r
i
q
= (i
2
r−1
+ 2
r−1
) mod 2
r
i
s
= (i
0
+ 2
r−1
) mod 2
r
.
ut
Benes
3
(7, 2, 1, 3, 0, 5, 6, 4) (0, 1, 2, 3, 7, 6, 5, 4) (0, 7, 1, 6, 2, 5, 3, 4)
52
|((q + 2
r −1
) mod 2
r
) − ((s + 2
r −1
) mod 2
r
)| 6= 2
r −1
n
Benes
r
2
r
(2r + 1) · 2
r
r · 2
r+2
x n = 2
r
O(n·log
2
n)
x y
2r
∗
G = (V, E)
G (V
1
, V
2
)
• V = V
1
∪ V
2
V
1
∩ V
2
= ∅
• −1 ≤ |V
1
| − |V
2
| ≤ 1
(V
1
, V
2
)
cost (V
1
, V
2
) = |E ∩ {{v, u} | v ∈ V
1
, u ∈ V
2
}|
V
1
V
2
G
But
r
Benes
r
Ω(2
r
)
a
b
(mod n)
53
m Ω(
m
log m
)
PSPACE
NP
RSA
IP = P SPACE
