Konsekwencje tezy CT
algorytm A
MT jest uniwersalną MO
program P realizujący
Można zbudować uniwersalną maszynę Turinga, która może
program P dane X
algorytm A napisany w
symulować działanie każdej innej maszyny Turinga z dowolnymi
uniwersalnym języku L1
dopuszczalnymi danymi zapisanymi na jej taśmie (trzeba w tym celu
opisać na taśmie zlinearyzowany diagram przejść, reprezentując
Program U
uniwersalny program U
każde przejście jako parę stanów z podaną etykietą przejścia) napisany w języku L2 , który (wykonanie programu
symuluje działanie programu P P na danych X)
Zatem konsekwencją tezy CT jest istnienie programów
na jego danych X
uniwersalnych, które mogą symulować działanie każdego innego
programu zapisanego w dowolnym języku dla dowolnych
wyniki
dopuszczalnych dla tego programu danych, tzn. kończyć działanie
(jeśli są)
w taki sam sposób jak symulowany program i podawać taki sam
wynik, jak gdyby rzeczywiście ten program został uruchomiony
dla tych danych.
Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 1 Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 2
Rozwijając tezę CT można dojść do następującego wniosku. Jeśli analizujemy algorytmy dla różnych klas problemów
w oparciu o różne modele obliczeń i różne języki ich zapisu,
Jeśli na jakimś (dowolnie szybkim) komputerze (maszynie
to z tezy CT wynika, że:
obliczeniowej) można rozwiązać pewien problem algorytmiczny
klasa problemów obliczalnych jest silna
w czasie O( f (N )), to istnieje równoważna temu komputerowi
tj. niewrażliwa na zmianę modelu lub języka,
maszyna Turinga, która potrzebuje na rozwiązanie tego problemu
nie więcej niż O( p( f (N ))) czasu, dla pewnej ustalonej funkcji
klasa problemów łatwo rozwiązywalnych P jest silna
wielomianowej p.
(jest to tzw. teza obliczania sekwencyjnego, czyli wykonywanego
krok po kroku),
2 7
Tzn. złożoność np. O(N ) może wzrosnąć do O(N ) lub nawet do
klasa NP jest silna,
64
O(N ), ale nie do O(2N). W rzeczywistości przejście na MT dla
klasa problemów o wykładniczej złożoności czasowej jest silna,
znanych problemów wiąże się z funkcjami wielomianowymi
4 5
niezbyt wysokiego rzędu np. p(x) = x lub x . Zatem dobry
klasa problemów o liniowej złożoności czasowej nie jest silna
wielomianowy algorytm nie stanie się nieakceptowalnie gorszy po
tzn. ocena złożoności tych problemów może zależeć od
redukcji do modelu uniwersalnego typu MT.
przyjętego modelu obliczeń.
Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 3 Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 4
Przykład przejścia niedeterministycznego
A jak teza CT ma się do rozstrzygnięcia, czy P = NP?
Jeśli chcemy formalnie zdefiniować klasy problemów P i NP, to
a / b P
najlepiej jest to zrobić w kategoriach obliczeń na maszynie Turinga:
?
rozmiarem danych wejściowych jest liczba komórek na taśmie
MT potrzebna do zapisania zakodowanych danych wejściowych,
a / b L
czas działania algorytmu mierzony jest liczbą przejść pomiędzy
stanami jaka jest potrzebna do wyznaczenia zamierzonego
wyniku,
Gdyby niedeterministyczne maszyny Turinga spełniały kryterium
problemy z klasy P są rozwiązywalne w czasie wielomianowym sekwencyjności, to problem P = NP byłby rozstrzygnięty
przez zwykłe maszyny Turinga, pozytywnie, ale nie spełniają, gdyż wybór właściwego przejścia
jest magiczny , a bez wyroczni oznacza konieczność
problemy z klasy NP są rozwiązywalne w czasie
równoczesnego wypróbowywania różnych możliwości, aby w tym
wielomianowym przez niedeterministyczne maszyny Turinga.
samym czasie sprawdzić jakie będą konsekwencje każdej z nich!
Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 5 Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 6
1
MT stosuje się powszechnie do dowodzenia dolnych
Na mocy tezy CT wystarczyło by pokazać, że pewien
oszacowań dla złożoności problemów algorytmicznych,
problem NP-zupełny nie może być rozwiązany
w tym także do dowodzenia ich nierozstrzygalności.
za pomocą MT w czasie krótszym niż wykładniczy,
aby wykazać, że P `" NP.
`"
`"
`"
Pewne ciekawe klasy problemów algorytmicznych można
definiować narzucając dodatkowe ograniczenia na działanie MT.
aby wyznaczyć jak najniższe górne oszacowanie złożoności
problemu algorytmicznego należy użyć jak najbogatszego
Np. klasa Pspace klasa problemów rozwiązywalnych przez MT,
i najsilniejszego formalizmu zapisu algorytmu (z instrukcjami
która może korzystać tylko z wielomianowo przyrastającej liczby
sterującymi wysokiego poziomu i rozwiniętymi strukturami
komórek na taśmie.
danych)
Okazuje się, że NP ą" Pspace
ą"
ą"
aby udowodnić jak najwyższe dolne oszacowanie złożoności ą"
problemu algorytmicznego należy użyć możliwie
najprostszego modelu obliczeń, czyli np. MT.
Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 7 Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 8
Automaty skończenie stanowe (skończone) poza zapisanymi sekwencyjnie danymi wejściowymi
automat zawiera na taśmie tylko symbole puste, z zatem
(rodzaj jednokierunkowej MT, nie będący MO)
może po prostu zatrzymywać się po przeczytaniu do końca
danych wejściowych, czyli po napotkaniu symbolu #,
STEROWANIE
W problemach decyzyjnych wystarczy umieścić
(diagram przejść
między stanami)
w diagramie tylko stany końcowe z odpowiedzią TAK,
ruch głowicy o jedną
gdyż zatrzymanie się automatu na końcu danych w każdym
głowica komórkę tylko w prawo
innym stanie można interpretować jako odpowiedz NIE,
ODCZYTUJCA
a b c d ! e f ! g : h # #
etykieta przejścia zawiera tylko jeden symbol wyzwalacz
przejścia (nie jest potrzebny człon akcji, bo jest ona tylko
PAMIĆ (jednostronnie nieskończona taśma)
jedna przejdz w prawo do następnej komórki)
każda komórka taśmy może być odczytana tylko raz ,
MT może potencjalnie wykonać nieskończenie wiele przejść
pod stanu do stanu. W automacie skończonym liczba przejść
nie można wrócić do raz odczytanych komórek, czyli nie jest
jest równa liczbie komórek z danymi, które trzeba kolejno
potrzebna dla głowicy funkcja zapisu
odczytać i jest zatem zawsze skończona.
Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 9 Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 10
Przykład automatu skończonego
A co potrafi rozstrzygnąć ten automat?
Automat pracuje na dwuelementowym alfabecie {a, b} i bada
a
parzystość wystąpień symbolu a w ciągu danych wejściowych.
a
a
TAK
b b b b
a
b b
a
TAK
1. Zestaw danych: a
a b b a a
Ten automat nie potrafi zliczyć
wystąpień a, ale o parzystości
2. Zestaw danych:
b a b b a potrafi rozstrzygnąć
Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 11 Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 12
2
Automaty skończone nie potrafią liczyć! W trakcie przesuwania się głowicy wzdłuż taśmy muszą
Teza: pojawić się dwie komórki z symbolem a, w których automat
będzie na diagramie w tym samym stanie s, gdyż liczba
Żaden automat skończony z alfabetem {a, b} nie potrafi rozstrzygnąć,
komórek z tym samym symbolem jest większa od liczby
czy wejściowy ciąg symboli zawiera taką samą liczbę symboli a i b.
stanów (zasada szufladkowa )
Dowód: (przez zaprzeczenie)
automat automat
Załóżmy, że pewien automat F potrafi rozstrzygnąć podany
w stanie s w stanie s
problem decyzyjny.
Niech liczba stanów tego automatu F wynosi N.
a a a a a a a b b b b b b b #
Rozważmy wejściową sekwencję symboli X, która zawiera X
najpierw dokładnie N + 1 symboli a, a potem N + 1 symboli b. 1 2 3 4 5 6 7 1 2 3 4 5 6 7
Np. dla N = 6: a a a a a a a b b b b b b b #
Zbudujmy nową sekwencję wejściową Y przez usunięcie z
1 2 3 4 5 6 7 1 2 3 4 5 6 7
sekwencji X zaznaczonych dwóch komórek, tak aby stan s
był osiągany tylko raz przy trzeciej komórce.
Odpowiedz powinna być TAK!
Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 13 Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 14
automat
Przykład automatu skończonego
w stanie s
Automat pracuje na dwuelementowym alfabecie {a, b}
i rozstrzyga czy w ciągu danych wejściowych pojawiła się
a a a a a b b b b b b b #
Y choć raz sekwencja baba .
1 2 3 4 5 1 2 3 4 5 6 7
a
Dla podanej sekwencji Y automat będzie działał tak samo jak dla
b a b a
sekwencji X, bo tak samo przy trzeciej komórce znajdzie się w
b ba bab TAK
stanie s i w dalszym swoim działaniu w zaznaczonym zakresie
a, b
odczyta taką samą sekwencje symboli, jaka w sekwencji X a b b
zaczynała się od piątej komórki.
Zatem istnieje wejściowa sekwencja zawierająca różną liczbę
symboli a i b, dla której automat daje odpowiedz TAK. a b b a a b a b b a b a b a a #
Przeczy to założeniu, że automat daje taką odpowiedz tylko
dla sekwencji z taką sama liczbą symboli a i b !
c.b.d.o.
Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 15 Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 16
Automaty skończone są wygodnym modelem opisującym
działanie prostych urządzeń sterowanych zewnętrznymi
a b b a a b a b b a b a b a a #
sygnałami: windy, pralki, telefony komórkowe itp.
STOP
d
c
Przykład automatu
wyświetl wyświetl wyświetl
opisującego działanie
a
a
a
a
a
a
a
a
a
a
a stoper czas datę
d
zegarka cyfrowego c
a a
b a b a
b a b a
b a b a
b a b a
b a b a
b a b a
b a b a
b a b a
b a b a
b a b a
b a b a
c
b ba bab TAK
b ba bab TAK
b ba bab TAK
b ba bab TAK
b ba bab TAK
b ba bab TAK
b ba bab TAK
b ba bab TAK
b ba bab TAK
b ba bab TAK
b ba bab TAK
a
nastaw nastaw nastaw
budzik czas minuty
a, b
a, b
a, b
a, b
a, b
a, b
a, b
a, b
a, b
a, b
a, b Etykiety automatu b
a b b
a b b
a b b
a b b
a b b
a b b
a b b
a b b
a b b
a b b
a b b
skończonego
b c b c
nazywane są
wtedy sygnałami a b
11:45 c
nastaw nastaw
c d
lub zdarzeniami
godziny 10 min.
Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 17 Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 18
3
Do czego są wykorzystywane abstrakcyjne MO lub automaty?
Do badania rozstrzygalności problemów decyzyjnych
dotyczących samych modeli obliczeń:
Do badania złożoności obliczeniowej i rozstrzygalności
- równoważność algorytmiczna dwóch maszyn Turinga jest
problemów
nierozstrzygalna,
W teorii automatów do ich analizy i syntezy
- równoważność algorytmiczna dwóch automatów skończonych
jest rozstrzygalna,
W teorii języków formalnych
- o rozstrzygalności problemu równoważności algorytmicznej
W lingwistyce strukturalnej (automaty ze stosem) i w
dwóch automatów ze stosem nic nie wiadomo (a problem ma
konstruowaniu kompilatorów
istotne znaczenie dla budowy języków programowania i
kompilatorów)
Do badania siły niedeterminizmu np. niedeterministyczny
automat ze stosem
Do analizy zagadnienia obliczalnego zapytania do bazy danych
(za pomocą specjalnych maszyn Turinga dla baz danych lub
Do badania rozstrzygalności problemów decyzyjnych
baz wiedzy)
dotyczących samych modeli obliczeń
Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 19 Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 20
4
Wyszukiwarka
Podobne podstrony:
Mieke BalW14 Kodowanie i Kryptografia kody cykliczne?le 6gAntropologia kulturowa W14bal u weteranowStauros Balsong77 Rodowicz Niech żyje bal text tabbal u senatora?DSaA W14 HuffmanCode Knapsackw14 PSYCHBAL WSZYSTKICH WI TYCHwięcej podobnych podstron