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

UptoLike

ВУЗ: 

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

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

Рубрика: 

w L
v |v|≤q(|w|)
T
w L
v p(|w|+|v|+1)
T q
1
a
0
wa
0
q
0
a
0
a
1
a
0
...a
0
|v|≤q(|w|)
w L p(|w| + q(|w|)+
1)
T q
1
a
0
wa
0
q
0
a
0
a
1
a
0
...a
0
p(n) q(n)
p(n + q(n)+1)
L Σ NP−
TIME
T q(n) p(n)
Σ ⊆A
T
\{a
0
}
w Σ u A
T
\{a
0
}
T q
1
a
0
wa
0
va
0
p(|w|+ |v| +1)
w Σ
w L
v A
T
\{a
0
} |v|≤q(|w|)
q
1
a
0
wa
0
va
0
T
q
0
a
0
a
1
a
0
...a
0
p(|w| + |v| +1)
T
0
A
T
q
1
a
0
wa
0
q
0
a
0
wa
0
va
0
v
A
T
\{a
0
}
T
0
T T
0
T
2(n +1+q(n)) + p(n + q(n)+1)
L
L Σ
T = A
T
,Q
T
,P
T
,q
0
,q
1
p(n)
Σ ⊆A
T
\{a
0
}

Страницы