Deterministyczna maszyna Turinga (DTM)
Uk ad steruj cy
G owica
zapisuj co-
odczytuj ca
Ta ma niesko czonej d ugo ci
(1,1,+1)
q1
q0 (#,#,-1)
q
0
(1,1,+1)
(0,0,+1)
(0,0,+1)
qY
qN
0 1 1
# 1 1 0 0 #
(1,1,+1)
(1,1,+1)
q1
q0 (#,#,-1)
q
0
(1,1,+1)
(0,0,+1)
(0,0,+1)
qY
qN
0 1 1
# 1 1 0 0 #
(1,1,+1)
(1,1,+1)
q1
q0 (#,#,-1)
q
0
(1,1,+1)
(0,0,+1)
(0,0,+1)
qY
qN
0 1 1
# 1 1 0 0 #
(1,1,+1)
(1,1,+1)
q1
q0 (#,#,-1)
q
0
(1,1,+1)
(0,0,+1)
(0,0,+1)
qY
qN
0 1 1
# 1 1 0 0 #
(1,1,+1)
(1,1,+1)
q1
q0 (#,#,-1)
q
0
(1,1,+1)
(0,0,+1)
(0,0,+1)
qY
qN
0 1 1
# 1 1 0 0 #
(1,1,+1)
(1,1,+1)
q1
q0 (#,#,-1)
q
0
(1,1,+1)
(0,0,+1)
(0,0,+1)
(0,0,+1)
qY
qN
0 1 1
# 1 1 0 0 #
(1,1,+1)
(1,1,+1)
q1
q0 (#,#,-1)
q
0
(1,1,+1)
(0,0,+1)
(0,0,+1)
qY
qN
0 1 1
# 1 1 0 0 #
(1,1,+1)
(1,1,+1)
q1
q0 (#,#,-1)
q
0
(1,1,+1)
(0,0,+1)
(0,0,+1)
qY
qN
0 1 1
# 1 1 0 0 #
(1,1,+1)
(1,1,+1)
q1
q0 (#,#,-1)
q
0
(1,1,+1)
(0,0,+1)
(0,0,+1)
qY
qN
0 1 1
# 1 1 0 0 #
(1,1,+1)
(1,1,+1)
q1
q0 (#,#,-1)
q
0
(1,1,+1)
(0,0,+1)
(0,0,+1)
(0,0,+1)
qY
qN
0 1 1
# 1 1 0 0 #
(1,1,+1)
(1,1,+1)
q1
q0 (#,#,-1)
q
0
(1,1,+1)
(0,0,+1)
(0,0,+1)
qY
qN
0 1 1
# 1 1 0 0 #
(1,1,+1)
(1,1,+1)
q1
q0 (#,#,-1)
q
0
(1,1,+1)
(0,0,+1)
(0,0,+1)
qY
qN
0 1 1
# 1 1 0 0 #
(1,1,+1)
(1,1,+1)
q1
q0 (#,#,-1)
q
0
(1,1,+1)
(0,0,+1)
(0,0,+1)
qY
qN
0 1 1
# 1 1 0 0 #
(1,1,+1)
(1,1,+1)
q1
q0 (#,#,-1)
q
0
(1,1,+1)
(0,0,+1)
(0,0,+1)
(0,0,+1)
qY
qN
0 1 1
# 1 1 0 0 #
(1,1,+1)
(1,1,+1)
q1
q0 (#,#,-1)
q
0
(1,1,+1)
(0,0,+1)
(0,0,+1)
qY
qN
0 1 1
# 1 1 0 0 #
(1,1,+1)
(1,1,+1)
(#,#,-1)
q1
q0 (#,#,-1)
q
0
(1,1,+1)
(0,0,+1)
(0,0,+1)
qY
qN
0 1 1
# 1 1 0 0 #
(1,1,+1)
(1,1,+1)
q1
q
q0 (#,#,-1)
q
1
0
(1,1,+1)
(0,0,+1)
(0,0,+1)
qY
qN
0 1 1
# 1 1 0 0 #
(1,1,+1)
(1,1,+1)
q1
q
q0 (#,#,-1)
q
1
0
(1,1,+1)
(0,0,+1)
(0,0,+1)
(0,0,+1)
qY
qN
0 1 1
# 1 1 0 0 #
(1,1,+1)
(1,1,+1)
q1
q
q0 (#,#,-1)
q
1
0
(1,1,+1)
(0,0,+1)
(0,0,+1)
qY
q
Y
qN
0 1 1
# 1 1 0 0 #
Niedeterministyczna maszyna Turinga (NDTM)
Uk ad zgaduj cy Uk ad steruj cy
G owica
zapisuj co-
G owica
odczytuj ca
zapisuj ca
Ta ma niesko czonej d ugo ci
s=<1,2,3,4>
1 2 3 4
3
czas
C3
s=
......... .........
s(k) s(k+1)
czas
s =
.........
.........
s(k+1) s(k)
czas
Przykład:
Zatem możemy przedstawić następujący algorytm znalezienia
optymalnej wartości plecaka:
Wszystkie problemy decyzyjne
NP
NP-zupe ne
P
silnie
NP-zupe ne
ierozstrzygalne
N
Wyszukiwarka
Podobne podstrony:
pytania egzaminacyjne do wykladu teoriakultuy
wyklad teoria podejmowania?cyzji
ProgCPP Wyklad Teoria 2
wyklad 7 teoria post modernistyczna
wyklad teoria masowej obslugi
Wykład 6 Teoria informacji
wyklad 8 teoria wyboru racjonalnego
wyklad teoriagier (2)
wyklad 4 teoria polityki biurokratycznej
wyklad 6 teoria zarzadzania publicznego
Wykład 2 teoria oczekiwanej użyteczności
teoria integracji plan wykladow?
Egzamin Teoria Wykład 01 (10) 14 (15) v 0 12 63 BETA
MIKROEKONOMIA WYKŁAD 4 (10 12 2011) struktury rynku,teoria podziału
Informatyka Wykład 07 B Teoria języków i automatów
więcej podobnych podstron