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
Document Outline
- Lmax1.pdf
- Lmax2.pdf
- DTM.pdf
- turing.pdf
- Strona 1
- TPI2.pdf
- klasy.pdf
- 3color1.pdf
- PCmax.pdf
- Strona 1
- Strona 2
- Strona 3
- Strona 4
- Strona 5
- Strona 6
- Strona 7
- Strona 8
- Strona 9
- Strona 10
- Strona 11
- Strona 12
- Strona 13
- Strona 14
- Strona 15
- Strona 16
- Strona 17
- Strona 18
- Strona 19
- Strona 20
- Strona 21
- Strona 22
- Strona 23
- Strona 24
- Strona 25
- Strona 26
- PCmax.pdf
- Strona 1
- Strona 2
- Strona 3
- Strona 4
- Strona 5
- Strona 6
- Strona 7
- Strona 8
- Strona 9
- Strona 10
- Strona 11
- Strona 12
- Strona 13
- Strona 14
- Strona 15
- Strona 16
- Strona 17
- Strona 18
- Strona 19
- Strona 20
- Strona 21
- Strona 22
- Strona 23
- Strona 24
- Strona 25
- Strona 26
- 1 strona.pdf
- Lmax1.pdf
- Strona 1
- Lmax2.pdf
- Strona 1
- DTM.pdf
- Strona 1
- Strona 2
- Strona 3
- Strona 4
- Strona 5
- Strona 6
- Strona 7
- Strona 8
- Strona 9
- Strona 10
- Strona 11
- Strona 12
- Strona 13
- Strona 14
- Strona 15
- Strona 16
- Strona 17
- Strona 18
- Strona 19
- Strona 20
- Strona 21
- turing.pdf
- Strona 1
- TPI2.pdf
- klasy.pdf
- Strona 1
- 3color1.pdf
- Strona 1
- Strona 2
- PCmax.pdf
- Strona 1
- Strona 2
- Strona 3
- Strona 4
- Strona 5
- Strona 6
- Strona 7
- Strona 8
- Strona 9
- Strona 10
- Strona 11
- Strona 12
- Strona 13
- Strona 14
- Strona 15
- Strona 16
- Strona 17
- Strona 18
- Strona 19
- Strona 20
- Strona 21
- Strona 22
- Strona 23
- Strona 24
- Strona 25
- Strona 26
- PCmax.pdf
- Strona 1
- Strona 2
- Strona 3
- Strona 4
- Strona 5
- Strona 6
- Strona 7
- Strona 8
- Strona 9
- Strona 10
- Strona 11
- Strona 12
- Strona 13
- Strona 14
- Strona 15
- Strona 16
- Strona 17
- Strona 18
- Strona 19
- Strona 20
- Strona 21
- Strona 22
- Strona 23
- Strona 24
- Strona 25
- Strona 26
- klasy.pdf
- Lmax1.pdf
- 2 strona.pdf
- Lmax1.pdf
- Strona 1
- Lmax2.pdf
- Strona 1
- DTM.pdf
- Strona 1
- Strona 2
- Strona 3
- Strona 4
- Strona 5
- Strona 6
- Strona 7
- Strona 8
- Strona 9
- Strona 10
- Strona 11
- Strona 12
- Strona 13
- Strona 14
- Strona 15
- Strona 16
- Strona 17
- Strona 18
- Strona 19
- Strona 20
- Strona 21
- turing.pdf
- Strona 1
- TPI2.pdf
- klasy.pdf
- Strona 1
- 3color1.pdf
- Strona 1
- Strona 2
- PCmax.pdf
- Strona 1
- Strona 2
- Strona 3
- Strona 4
- Strona 5
- Strona 6
- Strona 7
- Strona 8
- Strona 9
- Strona 10
- Strona 11
- Strona 12
- Strona 13
- Strona 14
- Strona 15
- Strona 16
- Strona 17
- Strona 18
- Strona 19
- Strona 20
- Strona 21
- Strona 22
- Strona 23
- Strona 24
- Strona 25
- Strona 26
- PCmax.pdf
- Strona 1
- Strona 2
- Strona 3
- Strona 4
- Strona 5
- Strona 6
- Strona 7
- Strona 8
- Strona 9
- Strona 10
- Strona 11
- Strona 12
- Strona 13
- Strona 14
- Strona 15
- Strona 16
- Strona 17
- Strona 18
- Strona 19
- Strona 20
- Strona 21
- Strona 22
- Strona 23
- Strona 24
- Strona 25
- Strona 26
- klasy.pdf
- Lmax1.pdf
Wyszukiwarka
Podobne podstrony:
2009-11-05, pedagogium, wykłady, Teoria edukacji obronnej i bezpieczeństwa publicznego
Autor opisuje 4 koncepcje psychologiczne człowieka, mteody wykład, teoria wychowania wykłady
wykład Teoria Bezpieczeństwa, Sudia - Bezpieczeństwo Wewnętrzne, Semestr I, Teoria Bezpieczeństwa
wyklady teoria metodyki i rekreacji-1, pedagogika czasu wolnego, rekreacja, metodyka rekreacji
zalacznki 01, Wykłady-teoria, Ogólne zasady ruchu oraz piesi
Teoretyczne podstawy wychowania, wyklady z teorii wych, Wykład 3: Teoria jako narzędzie poznawania r
Jadczak R Badania operacyjne, wyklad teoria podejmowania decyzji
Jadczak R, Badania operacyjne wyklad teoria podejmowania decyzji
31 Wyklad 6 Teoria przywiazania
29 Wyklad 7 Teoria wspolzaleznosci a
wyklad6 teoria zachowan konsumenta
wykład23 teoria wzgl
Leszek wyklad9 teoria pasmowa ciala stalego
Wykład 4 Teoria estymacji
Wyklad1 Teoria i Metodyka
2009-11-19, pedagogium, wykłady, Teoria edukacji obronnej i bezpieczeństwa publicznego
więcej podobnych podstron