Громкович Ю. Теоретическая информатика. Введение в теорию автоматов, теорию вычислимости, теорию сложности, теорию алгоритмов, рандомизацию, теорию связи и криптографию
Подождите немного. Документ загружается.
MMT
M MT MMT
Σ x ∈ Σ
∗
D = C
1
, C
2
, . . . , C
k
M x
Time
M
(x) M x
Time
M
(x) = k −1,
D
M Time
M
: IN
0
→ IN
0
Time
M
(n) = max{Time
M
(x) | x ∈ Σ
n
}.
Time
M
(n) n
Σ
n
M
Time
M
(n) x n
Time
A
(x) = Time
A
(n) Time
M
(n)
n
n
Time
M
(n)
x n Time
M
(n)
k ∈ IN M k MT
C = (q, x, i, α
1
, i
1
, α
2
, i
2
, . . . , α
k
, i
k
),
0 ≤ i ≤ |x| + 1 0 ≤ i
j
≤ |α
j
| + 1 j = 1, . . . , k
M C
Space
M
(C) = max{|α
i
| | i = 1, . . . , k}.
C
1
, C
2
, . . . , C
l
M x
M x
Space
M
(x) = max{Space
M
(C
i
) | i = 1, . . . , l} .
M
Space
M
: IN
0
→ IN
0
,
Space
M
(n) = max{Space
M
(x) | x ∈ Σ
n
}.
k ∈ IN
0
k
k
k ∈ IN k MT A
1 MT B
Space
B
(n) ≤ Space
A
(n).
3
M
Space
M
(n)
k ∈ IN k MT A k
MT B L(A) = L(B)
Space
B
(n) ≤
Space
A
(n)
2
+ 2.
Γ
A
A Γ
B
B
Γ
A
× Γ
A
α
1
, α
2
, . . . , α
m
i A i ∈ {1, 2, . . . , k}
α
j
j ∈ {1, 2, . . . , m} i
B
¢
α
1
α
2
α
3
α
4
. . .
α
m−1
α
m
,
m
¢
α
1
α
2
α
3
α
4
. . .
α
m−1
t
,
m
i B α
i
B
i A B
A 1 + dSpace
A
(n)/2e
A B A
B
A
MMT B
L(B) = L Space
B
(n) ≤
Space
A
(n)
2
+ 2.
ut
k MMT
Space
A
(n)
k
+ 2.
4
α
i
α
i+1
i
α
i−1
α
i
i
2
MMT A MMT
B
A
B
MMT M
MMT A
Time
A
(n) ≤
Time
M
(n)
2
+ 2n.
Time
M
Space
M
Ω O Θ o
f : IN
0
→ IR
+
O(f(n)) = {r : IN
0
→ IR
+
| ∃n
0
∈ IN
0
, ∃c ∈ IN
0
,
∀n ≥ n
0
: r(n) ≤ c · f (n)}.
r ∈ O (f(n)) r
f
g : IN
0
→ IR
+
Ω(g(n)) = {s : IN
0
→ IR
+
| ∃n
0
∈ IN
0
, ∃d ∈ IN
0
,
∀n ≥ n
0
: s(n) ≥
1
d
·g(n)}.
s ∈ Ω(g(n)) s
g
h : IN
0
→ IR
+
Θ(h(n)) = {q : IN
0
→ IR
+
| ∃c, d, n
0
∈ IN
0
, ∀n ≥ n
0
:
1
d
·h(n) ≤ q(n) ≤ c ·h(n)}
= O(h(n)) ∩ Ω(h(n)).
5
q ∈ Θ(h(n)) q h
f g IN
0
IR
+
lim
n→∞
f(n)
g(n)
= 0,
g f
f(n) = o(g(n))
• 2
n
∈ Θ(2
n+a
a ∈ IN
• 2
b·n
∈ Θ(2
n
) b ∈ IN
• log
b
n ∈ Θ(log
c
n) b, c > 1
• (n + 1)! ∈ O (n!)
• log(n!) ∈ Θ(n ·log n)
f, g : IN
0
→
IR
+
• f ∈ O(g) g ∈ O (h) ⇒ f ∈ O(h)
• f ∈ O(g) ⇔ g ∈ Ω(f )
• f ∈ Θ(g) ⇔ g ∈ Θ(f) ⇔ Θ(f) = Θ(g)
M
L
middle
M
M O(n
2
)
Time
M
(n) M
MT B
L(B) = L
middle
Time
B
(n) ∈ O (n)
A L
P
MT A
L
equal
= {w#w | w ∈ (Σ
bool
)
∗
}
Time
A
(n) ≤
3 · n ∈ O(n) Space
M
(n) ∈ O (n)
MT M L(M) = L
equal
Time
M
(n) ∈ O (
n
2
log
2
n
)
Space
M
(n) ∈
O(log
2
n)
U
MMT M U
M U
Time
A
(n) ∈ Ω(Time
M
(n))
MMT A U
MMT U U M
MMT A
MMT B n ∈ IN
Time
B
(n) ≤ log
2
(Time
A
(n)).
L f g
IN
0
IR
+
O(g(n))
L MMT A
L = L(A) Time
A
(n) ∈ O (g(n)).
Ω(f (n))
L
Time
B
(n) ∈ Ω(f(n))
MMT B L(B) = L
MMT C L
• L(C) = L
• Ω(Time
C
(n)) L
U
U
U
Ω(f (n)) f
U
f(n)
•
•
1
16 32 64
6
Ω(n log n)
7
a ≥ 2
k
a
2
k
i = 1 k a := a · a
k
a
2
:= a · a, a
4
:= a
2
·a
2
, a
8
:= a
4
· a
4
, . . . , a
2
k
:= a
2
k−1
· a
2
k−1
.
O(k) 3
3
2
k
a
2
k
2
k
Ω(2
k
)
k
8
f g IN
0
IR
+
TIME(f) = {L(B) | B MMT Time
B
(n) ∈ O (f(n))},
SPACE(g) = {L(A) | A
MMT Space
A
(n) ∈ O (g(n))},
DLOG = SPACE(log
2
n),
P =
[
c∈IN
0
TIME(n
c
),
PSPACE =
[
c∈IN
0
SPACE(n
c
),
EXPTIME =
[
d∈IN
0
TIME(2
n
d
).
t : IN
0
→ IR
+
TIME(t(n)) ⊆ SPACE(t(n)).
MMT M Time
M
(n)
Time
M
(n) MMT
M Space
M
(n) ≤ Time
M
(n) ut
P ⊆ PSPACE.
s : IN
0
→ IN
0
MT M
• Space
M
(n) ≤ s(n) n ∈ IN
0
• 0
n
n ∈ IN
0
M
0
s(n)
q
accept
t : IN
0
→ IN
0
MMT A
• T ime
A
∈ O (t(n))
• 0
n
n ∈ IN
0
A
0
t(n)
q
accept
f(n) ≥ log
2
(n + 1) f(n) ≥ n MT
dlog
2
(n + 1)e
0
n
1
t
dlog
2
(n + 1)e 0
dlog
2
(n+1)e
MT MMT
MMT MT
MMT M d
√
n e
M
i
2
≤ n < (i + 1)
2
.
i = 1, 2, . . . i
M
M 0
i
i·i ≥ n
M i ·i ¢
M
t
¢
M
M
i i · i > n
dlog
2
(n + 1)e
d
√
n e
f(n) =
n
q
q ∈ IN
0
• d
√
n e
q
q
• dn
1
3
e
•
n
q
2
q ≥ 2
• 2
n