Громкович Ю. Теоретическая информатика. Введение в теорию автоматов, теорию вычислимости, теорию сложности, теорию алгоритмов, рандомизацию, теорию связи и криптографию
Подождите немного. Документ загружается.
b=
b=
b=
b=
b=
U = (Σ
I
, Σ
O
, L, M, cost, minimum)
f
U f
SA(f)
x ∈ L
α ∈ M(x)
T
g
I := 0
T > 0 T
β f
x
(α)
cost (β) ≤ cost(α) α := β
r [0, 1]
r < e
−
cost(β)−cost(α)
T
α := β
I := I + 1
T := g(T, I)
α
T g
SA(f)
SA(f)
SA(f) |M(x)|
T g
NP P 6= NP
TSP MAX VC MAX CUT P 6= NP
TSP
NP
α
α α
28
29
α
NP
1
2
{2, 4, 6}
3
O(n
12
)
4
5
6
S
S
E
E
1
0
Prob(E) E
Prob(S) = 1
S
Prob({2, 4, 6}) =
Prob({2}) + Pro b({4}) + Prob({6})
Prob(S)
= Prob({2}) + Prob({4}) + Prob({6 })
=
1
6
+
1
6
+
1
6
=
1
2
,
1/2
X Y
Prob(X ∪ Y ) =
Prob(X) + Prob(Y )
Prob(S)
= Prob(X) + Prob(Y ).
S
S
Prob : P(S) → [0, 1],
7
• Prob({x}) ≥ 0 x
• Prob(S) = 1
• Prob(X ∪ Y ) = Prob(X) + Prob(Y ) X, Y ⊆ S
X ∩ Y = ∅
Prob(X) X (S, Prob)
x, y ∈ S
Prob({x}) = Prob({y}),
Prob S
(S, Prob)
• Prob(∅) = 0
• Prob(S − X) = 1 − P rob(X) X ⊆ S
• Prob(X) ≤ Prob(Y ) X, Y ⊆ S X ⊆ Y
• Prob(X ∪ Y ) = Pr ob(X) + Prob(Y ) − Prob(X ∩ Y )
≤ Prob(X) + Prob(Y )
X, Y ⊆ S
• Prob(X) =
P
x∈X
Prob(x)
X ⊆ S
Prob(i) =
1
6
i ∈ { 1, 2, . . . , 6}
S
2
= {(i, j) | i, j ∈ {1, 2, . . . , 6}}
(i, j) i
j
Prob
2
S
2
({1, 2, . . . , 6}, Prob)
i, j ∈ {1, 2, . . . , 6}
Prob
2
({(i, j)}) = Prob({i}) · Prob({j}) =
1
6
·
1
6
=
1
36
.
S
2
36
(i, j) ∈ S
2
Prob
2
({(i, j)}) =
1
36
.
k ∈ IN S = {0, 1, 2, . . . , 2
k
−1}
(S, Prob) k
k
k 1/k
S
A,x
HMT A x
C S
A,x
Prob(C)
(S
A,x
, Prob)
(S
A,x
, Prob)
x
S
A,x
A
x Error
A
(x) A
Error
A
: IN
0
→ IN
0
Error
A
(n) = max{E rror
A
(x) | |x| = n}.
t A x
t(n)
A
A x
S
A,x
A x
S
A,x
8
t(|x|) + 1