TEORIA ZOONOCI OBLICZENIOWEJ
TEORIA ZOONOCI OBLICZENIOWEJ
Układ sterujący
Deterministyczna maszyna Turinga (DTM)
Taśma nieskończonej długości
Głowica
zapisująco-
odczytująca
# 1 1 0 1 0 1 0 #
q
0
q
0
q
1
q
Y
q
N
(1,1,+1)
(0,0,+1)
(#,#,-1)
(0,0,+1)
(1,1,+1)
# 1 1 0 1 0 1 0 #
q
0
q
0
q
1
q
Y
q
N
(1,1,+1)
(1,1,+1)
(0,0,+1)
(#,#,-1)
(0,0,+1)
(1,1,+1)
# 1 1 0 1 0 1 0 #
q
0
q
0
q
1
q
Y
q
N
(1,1,+1)
(1,1,+1)
(0,0,+1)
(#,#,-1)
(0,0,+1)
(1,1,+1)
# 1 1 0 1 0 1 0 #
q
0
q
0
q
1
q
Y
q
N
(1,1,+1)
(1,1,+1)
(0,0,+1)
(#,#,-1)
(0,0,+1)
(1,1,+1)
# 1 1 0 1 0 1 0 #
q
0
q
0
q
1
q
Y
q
N
(1,1,+1)
(1,1,+1)
(0,0,+1)
(#,#,-1)
(0,0,+1)
(1,1,+1)
# 1 1 0 1 0 1 0 #
q
0
q
0
q
1
q
Y
q
N
(1,1,+1)
(1,1,+1)
(0,0,+1)
(0,0,+1)
(#,#,-1)
(0,0,+1)
(1,1,+1)
# 1 1 0 1 0 1 0 #
q
0
q
0
q
1
q
Y
q
N
(1,1,+1)
(1,1,+1)
(0,0,+1)
(#,#,-1)
(0,0,+1)
(1,1,+1)
# 1 1 0 1 0 1 0 #
q
0
q
0
q
1
q
Y
q
N
(1,1,+1)
(1,1,+1)
(0,0,+1)
(#,#,-1)
(0,0,+1)
(1,1,+1)
# 1 1 0 1 0 1 0 #
q
0
q
0
q
1
q
Y
q
N
(1,1,+1)
(1,1,+1)
(0,0,+1)
(#,#,-1)
(0,0,+1)
(1,1,+1)
# 1 1 0 1 0 1 0 #
q
0
q
0
q
1
q
Y
q
N
(1,1,+1)
(1,1,+1)
(0,0,+1)
(0,0,+1)
(#,#,-1)
(0,0,+1)
(1,1,+1)
# 1 1 0 1 0 1 0 #
q
0
q
0
q
1
q
Y
q
N
(1,1,+1)
(1,1,+1)
(0,0,+1)
(#,#,-1)
(0,0,+1)
(1,1,+1)
# 1 1 0 1 0 1 0 #
q
0
q
0
q
1
q
Y
q
N
(1,1,+1)
(1,1,+1)
(0,0,+1)
(#,#,-1)
(0,0,+1)
(1,1,+1)
# 1 1 0 1 0 1 0 #
q
0
q
0
q
1
q
Y
q
N
(1,1,+1)
(1,1,+1)
(0,0,+1)
(#,#,-1)
(0,0,+1)
(1,1,+1)
# 1 1 0 1 0 1 0 #
q
0
q
0
q
1
q
Y
q
N
(1,1,+1)
(1,1,+1)
(0,0,+1)
(0,0,+1)
(#,#,-1)
(0,0,+1)
(1,1,+1)
# 1 1 0 1 0 1 0 #
q
0
q
0
q
1
q
Y
q
N
(1,1,+1)
(1,1,+1)
(0,0,+1)
(#,#,-1)
(0,0,+1)
(1,1,+1)
# 1 1 0 1 0 1 0 #
q
0
q
0
q
1
q
Y
q
N
(1,1,+1)
(1,1,+1)
(0,0,+1)
(#,#,-1)
(#,#,-1)
(0,0,+1)
(1,1,+1)
# 1 1 0 1 0 1 0 #
q
0
q
0
q
1
q
1
q
Y
q
N
(1,1,+1)
(1,1,+1)
(0,0,+1)
(#,#,-1)
(0,0,+1)
(1,1,+1)
# 1 1 0 1 0 1 0 #
q
0
q
0
q
1
q
1
q
Y
q
N
(1,1,+1)
(1,1,+1)
(0,0,+1)
(#,#,-1)
(0,0,+1)
(0,0,+1)
(1,1,+1)
# 1 1 0 1 0 1 0 #
q
0
q
0
q
1
q
1
q
Y
q
Y
q
N
(1,1,+1)
(1,1,+1)
(0,0,+1)
(#,#,-1)
(0,0,+1)
(1,1,+1)
Układ sterujący
Niedeterministyczna maszyna Turinga (NDTM)
Taśma nieskończonej długości
Głowica
zapisująco-
odczytująca
Układ zgadujący
Głowica
zapisująca
czas
1
2
3
3
4
s=<1,2,3,4>
C
3
czas
s(k)
s(k+1)
czas
s(k)
s(k+1)
s=<s(1),....s(k-1),s(k),s(k+1),...,s(n)>
s’=<s(1),....s(k-1),s(k+1),s(k),...,s(n)>
.........
.........
.........
.........
Przykład:
Zatem możemy przedstawić następujący algorytm znalezienia
optymalnej wartości plecaka:
Wszystkie problemy decyzyjne
N
ie
r
z
s
tr
z
y
a
ln
e
o
g
NP
P
NP-zupełne
silnie
NP-zupełne
