Элементы теории алгоритмов - 183 стр.

UptoLike

ВУЗ: 

ЯрГУ | Ярославль

Составители: 

Рубрика: 

§1 NP
E
ijkt
= ¬Hi, t∨¬Ci, j, t∨¬Sk, t∨
∨
q
α
,a
β
,D
γ
∈δ(q
k
,a
j
)
(Ci, β, t +1)&Sα, t +1& Hi + γ,t +1),
D
−1
= L, D
0
= S, D
+1
= R.
T δ(q
k
,a
j
)
q
α
,a
β
,D
γ
T
E O(p
2
(n))
E O(p
3
(n))
W = a
j
1
...a
j
n
T F
0 n
W p(n) − n
a
0
q
1
F =&
1≤i≤n
Ci, j
i
, 0&&
n<i≤p(n)
Ci, 0, 0& S1, 0& H1, 0.
E O(p(n))
E O(p
2
(n))
G
t ≤ p(n) T
G = S0,p(n).
Ψ(W )
A& B& C & D& E & F & G.
Ψ(W ) O(p
4
(n)) W Ψ(W )
Ψ(W )
W L(T )
T Ψ(W )
NP

Страницы