Громкович Ю. Теоретическая информатика. Введение в теорию автоматов, теорию вычислимости, теорию сложности, теорию алгоритмов, рандомизацию, теорию связи и криптографию
Подождите немного. Документ загружается.
α ∈ M(x) x
U
cost(α, x) = Opt
U
(x) = goal{cost(β, x) | β ∈ M(x)}.
A U
x ∈ L
• A(x) ∈ M(x)
A(x) x
U
• cost(A(x), x) = goal{cost(β, x) | β ∈ M(x)}
goal = minimum U
goal = maximum U
U
Σ
I
U
Σ
O
L ⊆ Σ
∗
I
L
{
= Σ
∗
I
−L
(Σ
I
, L)
x
M(x) x
x cost (α, x)
α ∈ M(x)
M(x) x
U M(x)
M(x)
Σ
I
Σ
O
• L
• x ∈ L
M(x)
•
•
18
TSP
(G, c) G = (V, E) V = {v
1
, . . . , v
n
}
n ∈ IN c : E → IN
{ x ∈ {0, 1, #}
∗
(G, c).}
(G, c) M(G, c)
G
v
i
1
, v
i
2
, . . . , v
i
n
, v
i
1
(i
1
, i
2
, . . . , i
n
) (1, 2, . . . , n)
{ M(G, c)
y
1
#y
2
# . . . #y
n
∈ {0, 1, #}
∗
= Σ
∗
O
y
i
∈ {0, 1}
+
i = 1, 2, . . . , n
{Number(y
1
), Number (y
2
), . . . , Number(y
n
)} = {1, 2, . . . , n},
Number (y
1
) = 1
H = v
i
1
, v
i
2
, . . . , v
i
n
, v
i
1
∈ M(G, c)
cost ((v
i
1
, . . . , v
i
n
, v
i
1
), (G, c)) =
n
X
j=1
c
{v
i
j
, v
i
(j mod n)+1
}
,
minimum
TSP
cost
(v
1
, v
2
, v
3
, v
4
, v
5
, v
1
), (G, c)
= 8 + 1 + 7 + 2 + 1 = 19,
cost
(v
1
, v
5
, v
3
, v
2
, v
4
, v
1
), (G, c)
= 1 + 1 + 1 + 1 + 1 = 5.
v
1
, v
5
, v
3
, v
2
, v
4
, v
1
TSP
TSP
U
1
= (Σ
I
, Σ
O
, L
0
, M, cost, goal )
U
2
= (Σ
I
, Σ
O
, L, M, cost, goal ) L
0
⊆ L
U
1
U
2
19
20
⊆
∈
v
1
1
1
1
1
1
22
3
v
2
7
8
v
3
v
4
v
5
TSP ∆ TSP
TSP ∆ TSP
TSP
∆ TSP
(G, c)
c({u, v}) ≤ c({u, w}) + c({w, v})
u, v, w G
u v
n > 2 G n
|M((G, c))| = (n − 1)!/2
G = (V, E) U
U ⊆ E E
U {v
2
, v
4
, v
5
}
{v
1
, v
2
, v
3
}
{v
4
, v
5
} v
1
v
2
v
3
MIN VCP
G
21
{u, v} u v
MIN VCP
{0, 1, #}
v
1
v
2
v
3
v
4
v
5
G = (V, E) U ⊆ V
{{u, v} | u, v ∈ U, u 6= v} ⊆ E
U G
|U| MAX CL
MAX CL
MAX CL
G = (V, E)
M(G) = {S ⊆ V | {{u, v} | u, v ∈ S, u 6= v} ⊆ E} M(G)
G
S ∈ M (G) cost(S, G) = |S|
maximum
T = (V, E
0
) G =
(V, E) T E
0
⊆ E
T = (V, E
0
) G
P
e∈E
0
c(e)
E
0
X = {x
1
, x
2
, . . .}
X Lit
X
= {x, x | x ∈ X} x x
22
G
0 1
x
1
∨x
3
∨x
4
∨x
7
F
,
F
X
Φ = (x
1
∨ x
2
) ∧ (x
1
∨ x
2
∨ x
3
) ∧ x
2
∧ (x
2
∨ x
3
) ∧ x
3
∧ (x
1
∨x
3
).
MAX SAT
1 1
MAX SAT
Φ = F
1
∧ F
2
∧ ··· ∧ F
m
X F
i
i = 1, . . . , m m ∈ IN
Φ n
{x
i
1
, x
i
2
, . . . , x
i
n
}
M(Φ) = {0, 1}
n
.
α = α
1
. . . α
n
∈ M(Φ) α
j
∈ {0, 1} j = 1, . . . , n
x
i
j
α
j
Φ α ∈ M(Φ) cost (α, Φ)
Φ α
maximum
Φ 8
x
1
x
2
x
3
8
001 011 101 5
Φ
ILP
ILP
ILP
m × n
A = [a
ij
]
i=1,...m,j=1,...,n
,
23
24
F
25
x
1
x
2
x
3
x
1
∨ x
2
x
1
∨ x
2
∨ x
3
x
2
x
2
∨ x
3
x
3
x
1
∨ x
3
b = (b
1
, . . . , b
m
)
T
c = (c
1
, . . . , c
n
)
n, m ∈ IN i = 1, . . . , m j = 1, . . . , n a
ij
b
i
c
j
M(A, b, c) = {X = (x
1
, . . . , x
n
)
T
∈ (IN
0
)
n
| AX = b }
{M(A, b , c)
AX = b A b
X = (x
1
, . . . , x
n
) ∈ M(A, b, c)
cost (X, (A, b, c)) = c · X =
n
X
i=1
c
i
x
i
.
minimum
Σ x ∈ Σ
∗
x A λ
x
A
A :
( )
n A
n
(01)
n
A
n
:
i = 1 n
( )
x
Σ L ⊆ Σ
∗
A
L n A
x
1
, x
2
, . . . , x
n
x
1
, x
2
, . . . , x
n
n L
Σ = {0} L = {0
p
| p
n
0
2
, 0
3
, 0
5
, 0
7
, . . . , 0
p
n
p
n
n
L
Σ
bool
w
w
w
|w|
011011011011011011011011,
(011)
8
0101101000101101001110110010.
w
w
w
Σ
bool
26
27
(Σ
bool
)
∗
(Σ
bool
)
∗
H (Σ
bool
)
∗
{0, 1, 2, 3, 4}
∗
= Σ
∗
5
x ∈ (Σ
bool
)
∗
|x| ≥ 4
|x| ≥ 2 · |H(x)|.
2
Σ
5
Σ
m
m > 5
{0, 1, (, )} w ∈ (Σ
bool
)
∗
w
a
(w)Bin(a).
(011)
8
(0)1010(010)1(01)1101 (0)
10
(010)
1
(01)
13
.
Σ
bool
{0, 1, (, )} Σ
bool
h(0) = 00 , h(1) = 11, h( ( ) = 10, h( ) ) = 01.
(011)
8
100011110111000000.
(011)
2
20
(011)
1048576
(01)1
2
2
n
, (01)
2
2
2
n
, . . .
Σ
bool
M
Σ
bool
M
x ∈ (Σ
bool
)
∗
Number (x)
p
i
1
1
· p
i
2
2
· ··· · p
i
k
k
p
1
< p
2
< ··· < p
k
i
1
, i
2
, . . . , i
k
∈ IN
p
i
1
1
·p
i
2
2
· ··· · p
i
k
k
{0, 1, (, ), }
Bin(p
1
)(Bin(i
1
))Bin(p
2
)(Bin(i
2
)) . . . Bin(p
k
)(Bin(i
k
)).
h
x
•
x
•
y
x ∈ (Σ
bool
)
∗
K (x) x
x
Σ
bool
x ∈ (Σ
bool
)
∗
x
x
K (x)
x
M
M(x) x
M
M(x) x
K(x)
K(x)
|x|
d x ∈ (Σ
bool
)
∗
K (x) ≤ |x| + d.
28
x
x ∈ (Σ
bool
)
∗
A
x
(x)
x ∈ (Σ
bool
)
∗
d x x A
x
x
|x|
ut
y
n
= 0
n
∈ {0, 1}
∗
n ∈ IN Y
n
y
n
i = 1 n
(0)
Y
n
n
n Bin(n) dlog
2
(n + 1)e n
Y
n
dlog
2
ne + 1
c
K (y
n
) ≤ dlog
2
ne + c = dlog
2
|y
n
|e + c
n ∈ IN
z
n
= 0
n
2
∈ {0, 1}
∗
n|inIN Z
n
z
n
m := n
m := m × m
i = 1 m
(0)
Z
n
n
Z
n
n d
K(z
n
) ≤ dlog
2
(n + 1)e + d ≤ dlog
2
(
p
|z
n
|e + d + 1.
Z
n
n
2
Z
n
29