|
|
| Linia 1: |
Linia 1: |
| ==Inne modele dla złożoności==
| |
|
| |
|
| W poprzednim rozdziale przedstawiliśmy bardzo prosty, ale zarazem potężny model
| |
| obliczeń - maszynę Turinga. Przekonaliśmy się, że można na niej zaimplementować
| |
| proste operacje takie jak dodawanie; nietrudno uwierzyć w to, że za jej pomocą
| |
| można rozwiązywać również dużo bardziej skomplikowane problemy programistyczne.
| |
|
| |
| Maszyna Turinga ma jednak zasadniczą wadę - programowanie na niej jest bardzo
| |
| mało wygodne. W tym module poznamy dwa modele obliczeń dużo bardziej
| |
| przypominające wygodne współczesne mikrokomputery takie jak ZX Spectrum.
| |
|
| |
| ===Maszyna RAM===
| |
|
| |
| Maszyna RAM (ang. Random Access Machine - maszyna o dostępie swobodnym) jest
| |
| modelem obliczeń bardziej
| |
| złożonym od maszyny Turinga. Składa się ona z programu - skończonego ciągu
| |
| rozkazów definiujących jej działanie - oraz z potencjalnie nieograniczonego
| |
| zbioru rejestrów, z których każdy może przechowywać dowolną liczbę naturalną.
| |
| Rejestry indeksujemy liczbami naturalnymi, a więc ich wartości będziemy
| |
| zapisywać jako <math>R_0, R_1, R_2, \ldots</math>. Rejestr o indeksie 0 zwyczajowo nazywany jest akumulatorem i ma pewne specjalne (opisane poniżej) własności. Zbiór rejestrów zazwyczaj kolektywnie nazywamy pamięcią operacyjną lub po prostu pamięcią.
| |
|
| |
| Oprócz programu i pamięci operacyjnej maszyna RAM posiada również dwie taśmy:
| |
| wejściową i wyjściową. Podobnie jak taśmy maszyny Turinga składają się one z
| |
| komórek, mogących zawierać symbole pewnego skończonego alfabetu; w przypadku
| |
| maszyny RAM na taśmach wejściowej i wyjściowej znajdują się liczby naturalne
| |
| z zakresu <math>[0, k]</math>, gdzie <math>k</math> to liczba ustalona z góry dla danej maszyny.
| |
| Różnicą w stosunku do maszyny Turinga
| |
| jest to, że po dokonaniu zapisu na komórce taśmy wyjściowej głowica przesuwana
| |
| jest w ustalonym kierunku (dla ustalenia uwagi w prawo) i nie można
| |
| już do tej komórki powrócić; taśma wyjściowa nie może zatem służyć jako miejsce
| |
| wykonywania obliczeń. To na programiście spoczywa odpowiedzialność zapisania
| |
| fragmentów wyjścia w bezpiecznym miejscu, jeżeli planuje w przyszłości z nich
| |
| skorzystać.
| |
|
| |
| [[ZO-2-1. Schemat maszyny RAM]]
| |
|
| |
| '''Zestaw instrukcji'''
| |
|
| |
| W przeciwieńswie do maszyny Turinga, gdzie wszystkie wykonywane operacje były
| |
| tego samego typu, maszyna RAM posiada stosunkowo złożony zestaw instrukcji.
| |
| Warto przy tym zauważyć, że zestaw podany poniżej jest jednym z wielu możliwych
| |
| zestawów instrukcji,
| |
| które można znaleźć w literaturze. Zestawy te są zasadniczo równoważne (tzn.
| |
| program napisany dla jednego z nich można przetłumaczyć na równoważny program
| |
| dla innego zestawu instrukcji), mogą jednak wystąpić pewne niuanse przy
| |
| rozważaniu złożoności obliczeniowej.
| |
|
| |
| {| border=1
| |
| |+ <span style="font-variant:small-caps"></span>
| |
| |-
| |
| !Kod !! Symbol !! Argument !! Operacja !!
| |
| |-
| |
| | 1 || LOAD || =n || <math>R_0 := n</math>
| |
| |-
| |
| | 2 || LOAD || n || <math>R_0 := R_n</math>
| |
| |-
| |
| | 3 || LOAD || <math>\uparrow</math>n || <math>R_0 := R_{R_n}</math>
| |
| |-
| |
| | 4 || STORE || n || <math>R_n := R_0</math>
| |
| |-
| |
| | 5 || STORE || <math>\uparrow</math>n || <math>R_{R_n} := R_0</math>
| |
| |-
| |
| | 6 || READ || n || <math>R_n := I</math>
| |
| |-
| |
| | 7 || READ || <math>\uparrow</math>n || <math>R_{R_n} := I</math>
| |
| |-
| |
| | 8 || WRITE || n || <math>O := R_n</math>
| |
| |-
| |
| | 9 || WRITE || <math>\uparrow</math>n || <math>O := R_{R_n}</math>
| |
| |-
| |
| | 10 || NEXT || || przesunięcie głowicy taśmy wejściowej w prawo
| |
| |-
| |
| | 11 || PREV || || przesunięcie głowicy taśmy wejściowej w lewo
| |
| |-
| |
| | 12 || ADD || =n || <math>R_0 := R_0 + n</math>
| |
| |-
| |
| | 13 || ADD || n || <math>R_0 := R_0 + R_n</math>
| |
| |-
| |
| | 14 || ADD || <math>\uparrow</math>n || <math>R_0 := R_0 + R_{R_n}</math>
| |
| |-
| |
| | 15 || SUB || =n || <math>R_0 := \max(R_0 - n, 0)</math>
| |
| |-
| |
| | 16 || SUB || n || <math>R_0 := \max(R_0 - R_n, 0)</math>
| |
| |-
| |
| | 17 || SUB || <math>\uparrow</math>n || <math>R_0 := \max(R_0 - R_{R_n}, 0)</math>
| |
| |-
| |
| | 18 || MUL || =n || <math>R_0 := R_0 \cdot n</math>
| |
| |-
| |
| | 19 || MUL || n || <math>R_0 := R_0 \cdot R_n</math>
| |
| |-
| |
| | 20 || MUL || <math>\uparrow</math>n || <math>R_0 := R_0 \cdot R_{R_n}</math>
| |
| |-
| |
| | 21 || DIV || =n || <math>R_0 := R_0 / n</math>
| |
| |-
| |
| | 22 || DIV || n || <math>R_0 := R_0 / R_n</math>
| |
| |-
| |
| | 23 || DIV || <math>\uparrow</math>n || <math>R_0 := R_0 / R_{R_n}</math>
| |
| |-
| |
| | 24 || JUMP || n || skok do instrukcji o numerze n
| |
| |-
| |
| | 25 || JZERO || n || skok do instrukcji o numerze n gdy <math>R_0 = 0</math>
| |
| |-
| |
| | 26 || JNZERO || n || skok do instrukcji o numerze n gdy <math>R_0 \not= 0</math>
| |
| |-
| |
| | 27 || HALT || || zakończenie działania maszyny
| |
| |}
| |
|
| |
| W powyższej tabeli symbol I oznacza zawartość komórki taśmy wejściowej,
| |
| znajdującej się pod głowicą. Analogicznie O to zawartość odpowiedniej komórki
| |
| na taśmie wyjściowej.
| |
|
| |
| '''Działanie maszyny RAM'''
| |
|
| |
| W chwili początkowej konfiguracja maszyny wygląda następująco:
| |
| *wszystkie rejestry mają wartość 0,
| |
|
| |
| *na taśmie wejściowej umieszczone jest słowo wejściowe; głowica taśmy wejściowej ustawiona jest na pierwszej (skrajnie lewej) komórce słowa wejściowego,
| |
|
| |
| *licznik rozkazów wskazuje na pierwszą instrukcję programu.
| |
|
| |
| W kolejnych krokach maszyna wykonuje instrukcje wskazywane przez licznik
| |
| rozkazów. W przypadku instrukcji 1-23 po wykonaniu operacji na rejestrach lub
| |
| taśmach licznik rozkazów zwiększany jest o jeden. W przypadku instrukcji skoku
| |
| licznik rozkazów modyfikowany jest zgodnie z wartością argumentu (lub zwiększany o jeden gdy skok jest warunkowy i warunek nie jest spełniony). Wykonanie instrukcji HALT kończy działanie programu. Dodatkowo instrukcja WRITE
| |
| przesuwa głowicę taśmy wyściowej o jedną komórkę w prawo, a instrukcje
| |
| NEXT i PREV przesuwają odpowiednio głowicę taśmy wejściowej.
| |
|
| |
| {{uwaga|[na marginesie]||
| |
| Można się w tym momencie zastanawiać, co się stanie, gdy maszyna wykona
| |
| ostatnią instrukcję programu i nie będzie to instrukcja HALT ani instrukcja
| |
| skoku; albo też co się stanie gdy jedna z instrukcji reprezentuje skok za
| |
| ostatni rozkaz programu. Dla porządku przyjmiemy, że program zachowa się tak,
| |
| jakby wykonał instrukcję HALT. Można też jednak przyjąć, że program dopuszczający taką sytuację jest niepoprawnie napisany i należy go poprawić
| |
| - co nie jest zadaniem trudnym.
| |
| }}
| |
|
| |
| Wynikiem działania programu dla zadanego słowa wejściowego nazywamy ciąg
| |
| liczb wypisanych na taśmę wyjściową od rozpoczęcia działania programu aż do
| |
| wykonania instrukcji HALT.
| |
|
| |
| {{przyklad|||
| |
| Poniższy program liczy największy wspólny dzielnik dwóch liczb naturalnych
| |
| podanych na wejściu.
| |
|
| |
| <math>\verb''
| |
| 1. READ 1\\
| |
| 2. NEXT\\
| |
| 3. READ 2\\
| |
| 4. LOAD 2\\
| |
| 5. JZERO 19\\
| |
| 6. SUB 1\\
| |
| 7. JNZERO 12\\
| |
| 8. LOAD 1\\
| |
| 9. SUB 2\\
| |
| 10. STORE 1\\
| |
| 11. JUMP 4\\
| |
| 12. LOAD 2\\
| |
| 13. STORE 3\\
| |
| 14. LOAD 1\\
| |
| 15. STORE 2\\
| |
| 16. LOAD 3\\
| |
| 17. STORE 1\\
| |
| 18. JUMP 4\\
| |
| 19. WRITE 1\\
| |
| 20. HALT</math>
| |
| }}
| |
|
| |
| Jest on generalnie równoważny poniższemu programowi w języku Pascal:
| |
|
| |
| ''function gcd(a:integer; b:integer):integer;
| |
| var
| |
| c:integer;
| |
| begin
| |
| while b <> 0 do {linie 4-5}
| |
| begin
| |
| if a >= b then {linie 6-7}
| |
| a := a - b {linie 8-10}
| |
| else
| |
| begin
| |
| c := b; {linie 12-13}
| |
| b := a; {linie 14-15}
| |
| a := c; {linie 16-17}
| |
| end;
| |
| end;
| |
| gcd := a;
| |
| end;''
| |
|
| |
| [[Animacja we flashu przedstawiajaca dzialanie algorytmu dla dwoch ustalonych
| |
| liczb, np. 15 i 35. - mozna by tez zrobic dla dowolnych liczb wpisanych
| |
| przez uzytkownika, ale chyba nie warto - nie o to chodzi w ZO]]
| |
|
| |
| '''Rozpoznawanie języków'''
| |
|
| |
| Większość problemów omawianych w ramach tego kursu jest natury decyzyjnej
| |
| - to znaczy dla zadanego słowa wejściowego program ma udzielić odpowiedzi
| |
| ''tak'' lub ''nie''. Warto zatem umówić się, w jaki sposób maszyna
| |
| ma nam zakomunikować swoją odpowiedź.
| |
|
| |
| {{definicja|||
| |
| Mówimy, że maszyna RAM akceptuje słowo wejściowe ''w'' wtedy i tylko wtedy
| |
| gdy po uruchomieniu jej ze słowem ''w'' umieszczonym na taśmie wejściowej
| |
| maszyna wypisuje na taśmę wyjściową dokładnie jedną liczbę - 1 - i
| |
| zatrzymuje się po skończonej ilości kroków. Językiem akceptowanym przez
| |
| maszynę RAM nazywamy zbiór wszystkich skończonych słów akceptowanych przez
| |
| tą maszynę.
| |
| }}
| |
|
| |
| {{cwiczenie|1||
| |
| Uzasadnij, czemu żądamy, żeby rejestry maszyny RAM mogły przechowywać dowolnie
| |
| duże liczby naturalne.
| |
| }}
| |
|
| |
| <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">
| |
| Zastanów się z jakiej funkcjonalności maszyny RAM korzystamy, jeśli do wykonania
| |
| obliczenia potrzebujemy ilości pamięci rosnącej wraz ze wzrostem wielkości
| |
| wejścia.
| |
| </div></div>
| |
|
| |
| <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
| |
| Kluczem do odpowiedzi na postawione pytanie jest zastosowanie w maszynie RAM
| |
| ''adresowania pośredniego'' - trybu adresowania, oznaczanego powyżej za pomocą
| |
| symbolu <math>\uparrow</math>. Warto zauważyć, że jeśli nasz program nie korzysta z adresowania pośredniego, to w trakcie swojego działania używa ustaloną z góry, skończoną liczbę rejestrów; dla przykładu powyższy program, liczący największy wspólny dzielnik, korzysta tylko z rejestrów o numerach 0-3. Jeżeli jednak do wykonania programu potrzebujemy potencjalnie nieograniczonej ilości pamięci, będziemy zmuszeni do skorzystania z adresowania pośredniego.
| |
| </div></div>
| |
|
| |
| Adresowanie pośrednie jest kluczową cechą maszyny RAM; poniższe ćwiczenie
| |
| ma na celu zaznajomienie Cię z jego działaniem.
| |
|
| |
| {{cwiczenie|2||
| |
| Zasymuluj program maszyny Turinga z ćwiczenia ''(tu numer ćwiczenia z
| |
| modułu 1'', ''polegającego na dodaniu dwóch liczb unarnych) '' na maszynie RAM.
| |
| Oblicz, ile najwięcej kroków wykonuje skonstruowana przez Ciebie maszyna RAM
| |
| podczas jednego kroku symulowanej maszyny Turinga. Jeśli liczba takich kroków
| |
| nie jest ograniczona, popraw maszynę w ten sposób, aby była.
| |
| }}
| |
|
| |
| <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">
| |
| Zauważ, że w trakcie działania wspomnianej maszyny Turinga głowica nigdy nie
| |
| znajduje się na lewo od swojej pozycji początkowej. ''(mam nadzieję, że tak
| |
| faktycznie będzie'' - ''jeśli nie to to poprawię)''
| |
| </div></div>
| |
|
| |
| <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none"> Powyższe ćwiczenie ilustruje ważną własność - każdy program dla jednotaśmowej, jednostronnie ograniczonej (czyli posiadającej nieskończoną taśmę tylko w jednym kierunku) maszyny Turinga można w prosty sposób przekształcić na równoważny program maszyny RAM. Łatwo się przekonać, że maszyna Turinga z obustronnie nieograniczoną taśmą nie jest potężniejsza od maszyny z taśmą jednostronnie ograniczoną; aby przekształcić program napisany dla pierwszej z nich wystarczy umówić się, że komórki o nieparzystych numerach będą reprezentowały komórki oryginalnej maszyny o ujemnych numerach, a komórki o
| |
| parzystych numerach będą reprezentowały komórki oryginalnej maszyny o numerach
| |
| dodatnich; dodatkowo należy w dość prosty sposób zmodyfikować program.
| |
| </div></div>
| |
|
| |
| '''Złożoność obliczeniowa w modelu RAM'''
| |
|
| |
| Zastanówmy się teraz, w jaki sposób można określić czas i pamięć zużyte
| |
| w trakcie działania maszyny RAM. Pierwszy - zapewne wyglądający na najbardziej
| |
| naturalny - sposób definiowania tych wielkości to tak zwane ''kryterium
| |
| jednostajne''. Jego założenia są następujące:
| |
|
| |
| *uznajemy, że każdy rozkaz maszyny jest wykonywany w pewnym z góry ustalonym, stałym czasie,
| |
|
| |
| *uznajemy, że miarą pamięci "zużytej" przez program w trakcie działania jest ilość rejestrów, do których program się odwoływał (w postaci odczytu lub zapisu).
| |
|
| |
| Takie podejście po chwili zastanowienia nie wydaje się jednak właściwe; co
| |
| gorsza - założenie o wykonywaniu operacji arytmetycznych na dowolnie dużych
| |
| liczbach w stałym czasie nie jest obecnie możliwe do zrealizowania, i nie
| |
| wygląda na to, aby mogło zostać zrealizowane również w przyszłości.
| |
|
| |
| Będziemy zatem stosować inne miary dla czasu i pamięci, zwane ''kryterium
| |
| logarytmicznym''. Jego założenia są następujące:
| |
|
| |
| *czas wykonania operacji na liczbie <math>n</math> jest proporcjonalny do <math>\lfloor \log n \rfloor + 1</math>. Czas wykonania operacji na dwóch liczbach <math>m</math> i <math>n</math> jest proporcjonalny do <math>\lfloor \log (m + n) \rfloor + 1</math> (oczywiście trzeba pamiętać, że logarytm liczby <math>0</math> jest niezdefiniowany; koszt wykonania operacji w tym przypadku równy jest <math>0</math>),
| |
|
| |
| *jeżeli operacja używa adresowania pośredniego, to czas dostępu do <math>k</math>-tej komórki jest proporcjonalny do <math>\lfloor \log k \rfloor + 1</math>,
| |
|
| |
| *do czasu wykonania każdej operacji doliczana jest pewna stała wielkość, mogąca reprezentować koszt pobrania i rozpoznania instrukcji. Chodzi tutaj głównie o to, by programy wykonujące same instrukcje skoku lub trywialne (czyli w tym przypadku operujące na samych zerach) operacje arytmetyczne miały niezerowy czas działania,
| |
|
| |
| *jako miarę pamięci używanej przez program w danym momencie uznajemy
| |
| sumę logarytmów wartości wszystkich rejestrów, do których odwoływał się
| |
| program w trakcie swojego dotychczasowego działania.
| |
|
| |
| Tak zdefiniowane miary ilości zasobów dużo lepiej odpowiadają rzeczywistości
| |
| współczesnych komputerów - do zapisania w pamięci liczby <math>n</math> potrzebujemy <math>\lfloor \log n \rfloor + 1</math> cyfr w systemie binarnym, natomiast dodanie dwóch liczb <math>m</math> i <math>n</math> zajmuje czas <math>O(\log(m + n))</math>. Niedoszacowany może się wydawać czas mnożenia i dzielenia (takie same jak dodawania) - jednak jak się okaże dla naszych celów taka definicja zupełnie wystarczy.
| |
|
| |
| '''Porównanie czasu działania maszyny Turinga i maszyny RAM'''
| |
|
| |
| {{uwaga|[na marginesie]||
| |
| Umówmy się, że czas działania określamy tylko dla maszyn z własnością stopu
| |
| - zarówno w przypadku maszyn Turinga i maszyn RAM.
| |
| }}
| |
|
| |
| W jednym z poprzednich ćwiczeń symulowaliśmy działanie maszyny Turinga na
| |
| maszynie RAM; stwierdziliśmy, że liczba kroków wykonywanych przez maszynę
| |
| RAM jest proporcjonalna do liczby kroków wykonanych przez symulowaną maszynę
| |
| Turinga. Jeżeli zatem <math>T(n)</math> określa największą ilość kroków wykonywaną przez
| |
| daną maszynę Turinga przy słowie wejściowym o długości <math>n</math>, a <math>T'(n)</math> jest analogicznie zdefiniowaną maksymalną ilością kroków dla maszyny RAM, to zachodzi następująca własność:
| |
|
| |
| <math>T'(n) = O(T(n))</math>
| |
|
| |
| {{uwaga|[na marginesie]||
| |
| W rzeczywistości w tym momencie powinniśmy zapisać:
| |
|
| |
| <math>T'(n) = O(T(n) + n)</math>
| |
|
| |
| Skąd się wzięło <math>n</math>? Otóż maszyna Turinga może dać odpowiedź jeszcze przed przeczytaniem całego słowa wejściowego. Maszyna RAM, skonstruowana w
| |
| zaprezentowany we wspomnianym ćwiczeniu sposób, symulująca działanie
| |
| maszyny Turinga przed rozpoczęciem symulacji przepisze całe słowo wejściowe do
| |
| rejestrów, po czym dopiero rozpocznie właściwe działanie. Można jednak łatwo
| |
| wyobrazić sobie schemat, w którym maszyna RAM sprowadza znaki z wejścia niejako
| |
| "na żądanie", zapamiętując jednocześnie liczbę sprowadzonych wcześniej
| |
| znaków. Taki schemat postępowania sprawia, że własność
| |
|
| |
| <math>T'(n) = O(T(N))</math>
| |
|
| |
| naprawdę zachodzi.
| |
| }}
| |
|
| |
| Zauważmy, że powyższa definicja funkcji czasu <math>T'(n)</math> dokładnie odpowiada definicji złożoności czasowej przy zastosowaniu kryterium jednostajnego. Warto się zastanowić, jak będzie wyglądała złożoność obliczeniowa w przypadku zastosowania kryterium logarytmicznego.
| |
|
| |
| {{cwiczenie|3||
| |
| Oszacuj czas działania maszyny RAM, symulującej działanie maszyny Turinga,
| |
| przy zastosowaniu kryterium logarytmicznego.
| |
| }}
| |
|
| |
| <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">
| |
| Wskaż instrukcje maszyny RAM, które nie są wykonywane w stałym czasie i oszacuj ich czas działania.
| |
| </div></div>
| |
|
| |
| <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none"> Należy zauważyć, że jedynym rejestrem, którego zawartości nie można a priori oszacować przez stałą, jest rejestr przechowujący pozycję symulowanej głowicy. Pozycję tą można jednak w prosty sposób oszacować od góry - nie będzie ona nigdy większa niż <math>T(n)</math>. Operacje o zmiennym czasie działania - czyli zwiększanie i zmniejszanie wskaźnika pozycji głowicy oraz dostęp za pomocą adresowania pośredniego do komórki pod głowicą - odbywają się w czasie <math>O(log T(n))</math>. Jeżeli zatem jako <math>T''(n)</math> oznaczymy pesymistyczny czas działania maszyny RAM w zależności od wielkości wejścia, to możemy zapisać następujący fakt:
| |
|
| |
| <math>T''(n) = O(T(n) log T(n))</math>
| |
|
| |
| a rozluźniając nieco oszacowanie:
| |
|
| |
| <math>T''(n) = O(T(n)^2)</math>
| |
| </div></div>
| |
|
| |
| '''Symulowanie maszyny RAM na wielotaśmowej maszynie Turinga'''
| |
|
| |
| Wyniki z poprzedniego paragrafu nie są specjalnie zaskakujące; gołym okiem
| |
| widać, że maszyna RAM jest narzędziem co najmniej równie potężnym jak
| |
| maszyna Turinga. W tym paragrafie zajmiemy się zagadnieniem odwrotnym
| |
| - pokażemy, że maszynę RAM da się symulować na maszynie Turinga i oszacujemy
| |
| wydajność takiej symulacji.
| |
|
| |
| Aby tego jednak dokonać uprościmy sobie najpierw definicję maszyny RAM.
| |
| Będziemy zatem tylko rozpatrywać maszyny RAM spełniające następujące warunki:
| |
|
| |
| *wejście i wyjście stanowią słowa nad alfabetem <math>\{ 0, 1 \}</math>,
| |
|
| |
| *maszyna nie używa instrukcji MUL ani DIV,
| |
|
| |
| *jedynymi operacjami, dopuszczającymi adresowanie pośrednie, są instrukcje LOAD i STORE.
| |
| Maszynę RAM będziemy symulować na wielotaśmowej maszynie Turinga, posiadającej:
| |
|
| |
| *taśmę wejściową nad alfabetem <math>\{ 0, 1 \}</math>,
| |
|
| |
| *taśmę wyjściową nad alfabetem <math>\{ 0, 1 \}</math>,
| |
|
| |
| *cztery taśmy robocze nad alfabetem <math>\{ 0, 1, \$, *, \% \}</math>
| |
|
| |
| Maszyna Turinga będzie symulowała po kolei rozkazy maszyny RAM, przy czym
| |
| zakładamy, że na początku symulacji każdego rozkazu głowice taśm roboczych
| |
| znajdują się w takim położeniu, jak na początku działania programu. Taśma
| |
| robocza nr 1 będzie służyła do reprezentacji aktualnej zawartości rejestrów
| |
| maszyny RAM. Taśma robocza nr 2 będzie służyła do przechowywania jednego
| |
| adresu komórki. Taśmy robocze 3 i 4 będą służyły do wykonywania operacji
| |
| arytmetycznych. Najciekawiej wygląda taśma nr 1; sposób reprezentacji pamięci
| |
| RAM jest przedstawiony na poniższym schemacie:
| |
|
| |
| <math>\verb''\$011*01*11*101**1011\$</math>
| |
|
| |
| Na taśmie znajdują się pary liczb, zapisane w postaci binarnej, zaczynając
| |
| od najmniej znaczącej cyfry. Powyższy zapis mówi, że:
| |
|
| |
| *rejestr 6 ma wartość 2,
| |
|
| |
| *rejestr 3 ma wartość 5,
| |
|
| |
| *rejestr 0 ma wartość 13 (zakładamy, że reprezentacja binarna liczby 0 ma 0 cyfr).
| |
| Prześledźmy teraz działanie maszyny dla operacji ADD n (przypominamy, że
| |
| nie jest tutaj stosowane adresowanie pośrednie, zatem <math>n</math> jest stałą określoną
| |
| w czasie pisania programu). Maszyna Turinga zachowa się w następujący sposób:
| |
|
| |
| *na taśmie numer 2 zapisze ciąg symboli <math>\$ \langle reprezentacja\_binarna\_liczby\_n \rangle \$</math> po czym przesunie głowicę tej taśmy do położenia początkowego,
| |
|
| |
| *przesuwając się w prawo na taśmie nr 1, maszyna będzie szukać reprezentacji komórki o numerze <math>n</math>; w tym celu będzie porównywać numery komórek, zapisane na taśmie nr 1, z adresem zapisanym na taśmie nr 2. Jeśli adresy się nie będą zgadzały maszyna wycofa głowicę taśmy nr 2 do położenia początkowego, zignoruje zawartość komórki na taśmie nr 1 i przejdzie do następnej pary adres-zawartość,
| |
|
| |
| *jeżeli maszyna znajdzie odpowiedni adres, to przepisze zawartość komórki na taśmę nr 3. W przeciwnym wypadku - gdy dojdzie do symbolu '' - zapisze na taśmie nr 3 reprezentację liczby 0,
| |
|
| |
| *podobna procedura zostanie zastosowana do przekopiowania na taśmę nr 4 zawartości akumulatora (rejestru o numerze 0),
| |
|
| |
| *maszyna doda liczbę zawartą na taśmie nr 3 do liczby z taśmy nr 4 za pomocą algorytmu pisemnego dodawania liczb binarnych,
| |
|
| |
| *maszyna zapisze wynik dodawania na taśmie nr 1.
| |
|
| |
| Ostatni krok może nastręczyć pewnych problemów: Nie wiemy co powinniśmy zrobić,
| |
| jeśli wynik dodawania zajmuje więcej bitów niż oryginalna liczba zawarta w
| |
| akumulatorze. Rozwiązanie w tym przypadku jest bardzo brutalne: Nasza maszyna
| |
| po prostu zapisze wynik na samym końcu taśmy nr 1; jeżeli po drodze na koniec
| |
| taśmy napotka parę adres-wartość, odpowiadającą akumulatorowi, to zarówno adres
| |
| jak i wartość oraz występujący między nimi separator <math>\'\*\'</math> zamaże wpisując w ich miejsca symbole <math>\%</math>. Na poniższym schemacie przedstawiony jest stan taśmy nr 1 po wykonaniu operacji ADD 3 (dodanie do
| |
| akumulatora zawartości komórki 3)
| |
|
| |
| <math>\verb''\$011*01*11*101**\%\%\%\%**01001\$</math>
| |
|
| |
| Operacja <math>LOAD \uparrow n</math> nie jest dużo bardziej skomplikowana; trzeba znaleźć zawartość komórki <math>n</math>, następnie znaleźć zawartość komórki <math>R_n</math>, a na końcu zapisać wynik w akumulatorze (w razie potrzeby zamazując jego poprzednią zawartość).
| |
|
| |
| Oszacujemy teraz czas potrzebny do zasymulowania maszyny RAM. Wykonanie operacji
| |
| arytmetycznych (pomijając czas dostępu do pamięci) zajmuje czas <math>O(log(m+n))</math>, gdzie <math>m</math> i <math>n</math> to argumenty operacji. Operacja kopiowania zawartości jednego rejestru do drugiego zajmuje czas <math>O(log n)</math>, gdzie <math>n</math> to kopiowana wartość. Stwierdzamy zatem, że samo wykonanie operacji na maszynie Turinga jest "wolniejsze" od wykonania tych operacji na maszynie RAM o stały czynnik. Innymi słowy jeśli <math>T(n)</math> to czas wykonania programu dla danych o wielkości <math>n</math> na maszynie RAM, a <math>T'(n)</math> to czas wykonania (pomijając dostępy
| |
| do pamięci) tych samych operacji na maszynie Turinga, to zachodzi następująca
| |
| własność:
| |
|
| |
| <math>T'_1(n) = O(T(n))</math>
| |
|
| |
| Pozostaje zatem kwestia oszacowania, ile zajmuje wyszukiwanie (i ewentualne
| |
| zamazywanie) komórek na taśmie nr 1. Łatwo jednak zauważyć, że w każdym
| |
| momencie symulacji ilość symboli na taśmie 1 jest co najwyżej proporcjonalna
| |
| do czasu działania symulowanej maszyny RAM. Zatem czas łącznie spędzony przez
| |
| maszynę Turinga na dostępy do pamięci można oszacować w następujący sposób:
| |
|
| |
| <math>T'_2(n) = O(T(n)\cdot T(n)) = O(T(n)^2)</math>
| |
|
| |
| Zatem łączny czas działania maszyny Turinga - a więc czas dostepu do pamięci
| |
| plus czas właściwych operacji - spełnia własności:
| |
|
| |
| <math>T'(n) = O(T(n)^2)</math>
| |
|
| |
| {{cwiczenie|4||
| |
| Oszacuj zależność między złożonością czasową programu dla maszyny RAM a
| |
| złożonością czasową programu maszyny Turinga, symulującego działanie maszyny
| |
| RAM, przy założeniu, że program maszyny RAM może używać wszystkich rozkazów
| |
| }}
| |
|
| |
| <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none"> Przekształć wywołania "zabronionych" rozkazów maszyny RAM na sekwencje rozkazów "dozwolonych" i oszacuj czas wykonania tych sekwencji.
| |
| </div></div>
| |
|
| |
| <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none"> Jest jasne, że adresowanie pośrednie dla operacji innych niż LOAD i STORE jest łatwe do zasymulowania: Wystarczy zastąpić te operacje poprzez sekwencje wykorzystujące akumulator i być może pewne z góry ustalone tymczasowe rejestry, w przypadku gdy trzeba będzie odtworzyć zawartość akumulatora.
| |
|
| |
| Pozostają więc operacje MUL i DIV. Zaczniemy od MUL =2 i DIV =2.
| |
| Widać, że operacja MUL =2 jest prosta do zaimplementowania za pomocą dodawania.
| |
| Operację DIV =2 można zaimplementować w sposób opisany za pomocą poniższego
| |
| pseudokodu:
| |
|
| |
| ''function div2(n:integer):integer;
| |
| var
| |
| a, b, c, res:integer;
| |
| begin
| |
| res := 0;
| |
|
| |
| while n >= 2 do
| |
| begin
| |
| a := 4;
| |
| b := 2;
| |
| c := 1;
| |
|
| |
| while n >= a do
| |
| begin
| |
| a := 2 * a;
| |
| b := 2 * b;
| |
| c := 2 * c;
| |
| end;
| |
|
| |
| n := n - b;
| |
| res := res + c;
| |
| end;
| |
|
| |
| div2 := res;
| |
| end;''
| |
|
| |
| W skrócie działanie tej procedury można opisać następująco: procedura znajduje
| |
| największą potęgę dwójki nie większą od argumentu (czyli najbardziej znaczący
| |
| bit) i dodaje do wyniku tą liczbę podzieloną przez 2 (czyli bit przesunięty
| |
| o jedną pozycję "w prawo"). Każda pętla wykonuje się co najwyżej <math>O(log n)</math> a operacje wewnątrz nich zajmują czas <math>O(log n)</math> - zatem powyższa procedura działa w czasie <math>O(log^3 n)</math>. Warto też zauważyć, że używana jest tutaj stała liczba zmiennych tymczasowych, o rozmiarze porównywalnym do rozmiaru liczby <math>n</math>.
| |
|
| |
| Powyższa procedura pozwala na prostą implementację funkcji MOD = 2 - czyli
| |
| funkcji zwracającej najmniej znaczący bit liczby. Z wykorzystaniem tej funkcji
| |
| możemy zaimplementować mnożenie dwóch dowolnych liczb:
| |
|
| |
| ''function multiply(n:integer; m:integer):integer;
| |
| begin
| |
| res := 0;
| |
|
| |
| while n > 0 do
| |
| begin
| |
| if n mod 2 = 1 then
| |
| res := res + m;
| |
|
| |
| n := n div 2;
| |
| m := m mul 2;
| |
| end;
| |
|
| |
| multiply := res;
| |
| end;''
| |
|
| |
| Czas działania powyższej procedury można oszacować od góry jako <math>O(log^4 (n+m))</math>.
| |
|
| |
| Do zaimplementowania pozostało nam już zatem tylko dzielenie; można tą procedurę skonstruować w następujący sposób:
| |
|
| |
| ''function divide(n:integer; m:integer):integer;
| |
| var
| |
| lo, hi, med:integer;
| |
| begin
| |
| lo := 0;
| |
| hi := 1;
| |
|
| |
| while m * hi <= n do
| |
| m := 2 * m;
| |
|
| |
| while (hi - lo) > 1 do
| |
| begin
| |
| med := (lo + hi) div 2;
| |
|
| |
| if med * hi <= n then
| |
| lo := med
| |
| else
| |
| hi := med;
| |
| end;
| |
|
| |
| divide := lo;
| |
| end;''
| |
|
| |
| Tutaj złożoność czasową można oszacować przez <math>O(log^5 (n+m))</math>.
| |
|
| |
| Widzimy zatem, że każdą "zabronioną" operację arytmetyczną można zasymulować
| |
| w czasie <math>O(log^5 (n+m))</math>. W związku z tym każdy program maszyny RAM działający w czasie <math>O(T(n))</math> można przekształcić w równoważny program nie korzystający z "zabronionych" operacji i działający w czasie <math>O(T(n)^5)</math>.
| |
|
| |
| W powyższych procedurach zdecydowanie większa waga była przyłożona do
| |
| prostoty rozwiązania niż do jego wydajności; również przedstawione powyżej
| |
| odgórne oszacowanie jest bardzo zgrubne - jest ono prawdziwe w przypadku gdy
| |
| w programie często używane jest dzielenie dużych liczb.
| |
|
| |
| </div></div>
| |
|
| |
| Powyższe paragrafy pokazały zależność pomiędzy złożonościami czasowymi
| |
| równoważnych programów dla maszyn RAM i Turinga. Taką zależność pomiędzy
| |
| modelami obliczeń nazywamy <math>\textit{wielomianową równoważnością}</math>.
| |
|
| |
| {{definicja|||
| |
| Mówimy, że modele obliczeń <math>\mathcal A</math> i <math>\mathcal B</math> są wielomianowo równoważne (w sensie złożoności czasowej) wtedy i tylko wtedy, gdy dla dowolnego języka <math>L \subseteq \Sigma^{\star}</math> (gdzie <math>\Sigma</math> jest skończonym alfabetem):
| |
|
| |
| * istnienie programu dla maszyny modelu <math>\mathcal A</math> o złożoności czasowej <math>f(n)</math> implikuje istnienie programu dla maszyny modelu <math>\mathcal B</math> o złożoności czasowej <math>O(w(f(n)))</math>, gdzie <math>w(x)</math> jest wielomianem,
| |
|
| |
| * zachodzi własność symetryczna.
| |
|
| |
| }}
| |
|
| |
| Wielomianowa równoważność sprawia, że jeśli dla danego problemu na maszynie
| |
| jednego typu istnieje algorytm o wielomianowej złożoności czasowej, to również
| |
| na drugiej maszynie istnieje algorytm o wielomianowej złożoności czasowej.
| |
|
| |
| ===Obwody logiczne===
| |
|
| |
| Rozważymy teraz model obliczeń w znaczący sposób różniący się od dwóch
| |
| poprzednio opisanych -- obwody logiczne. Obwód logiczny można formalnie
| |
| zdefiniować jako acykliczny graf skierowany o następujących własnościach:
| |
|
| |
| * każdy wierzchołek jest wierzchołkiem wejściowym, wierzchołkiem wyjściowym, koniunkcją, alternatywą albo negacją,
| |
|
| |
| * w zależności od typu wierzchołka spełnione są ograniczenia na jego stopnie wejściowe i wyjściowe:
| |
| ** wierzchołek wejściowy - stopień wejściowy 0,
| |
| ** wierzchołek wyjściowy - stopień wejściowy 1, stopień wyjściowy 0,
| |
| ** alternatywa i koniunkcja - stopień wejściowy 2,
| |
| ** negacja - stopień wejściowy 1.
| |
|
| |
| Węzły wewnętrzne - koniunkcję, alternatywę i negację - zwyczajowo nazywa
| |
| się bramkami. Ich semantyka zgodna jest z powszechnie przyjętym w logice
| |
| zwyczajem. Załóżmy, że obwód logiczny ma <math>m</math> wejść i <math>n</math> wyjść, z pewnym ustalonym na nich porządkiem. Możemy wtedy patrzeć na układ logiczny jako na funkcję następującego typu:
| |
|
| |
|
| |
| <math>f: \{ 0, 1 \}^m \rightarrow \{ 0, 1 \}^n</math>
| |
|
| |
| {{cwiczenie|5||
| |
| Skonstruuj układ logiczny, obliczający funkcję XOR.
| |
| }}
| |
|
| |
| <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none"> Jeden z możliwych układów przedstawiony jest na poniższym rysunku.
| |
|
| |
| [[ZO-2-3. Implementacja funkcji XOR.]]
| |
| </div></div>
| |
|
| |
| Stopień skomplikowania układu można mierzyć na dwa sposoby:
| |
|
| |
| * poprzez ilość bramek w układzie logicznym,
| |
|
| |
| * poprzez ilość bramek na najdłuższej ścieżce występującej w układzie (''głębokość'' układu logicznego).
| |
|
| |
| W dalszej części tego rozdziału będziemy się zajmować pierwszą z tych miar.
| |
|
| |
| W odróżnieniu od dwóch poprzednich modeli, każdy układ logiczny ma z góry
| |
| określoną wielkość wejścia i wyjścia, a co za tym idzie skończoną liczbę
| |
| możliwych zestawów danych wejściowych. Dla takiej rodziny układów będziemy
| |
| określać ''miarę złożoności ilościowej'':
| |
|
| |
| {{definicja|[Miara złożoności ilościowej]||
| |
| Niech <math>\mathcal R</math> będzie rodziną układów logicznych taką, że dla każdej liczby naturalnej <math>n </math> rodzina zawiera dokładnie jeden układ o <math>n </math> węzłach wejściowych. Miarą złożoności ilościowej nazwiemy wtedy funkcję <math>f: \mathbb N \rightarrow \mathbb N</math>, która każdej liczbie naturalnej <math>n </math> przyporządkowuje liczbę bramek zawartych w jedynym układzie z <math>\mathcal R</math>, posiadającym <math>n </math> wejść.
| |
| }}
| |
|
| |
| Pokażemy teraz, jaki jest związek między złożonością czasową obliczenia na
| |
| maszynie Turinga (rozpoznającej pewien język <math>L</math>), a złożonością czasową rodziny układów logicznych rozpoznających ten sam język. W tym celu zasymulujemy działanie jednotaśmowej maszyny Turinga dla słów wejściowych o ustalonej długości.
| |
|
| |
| Załóżmy zatem, że maszyna Turinga <math>M</math> rozpoznaje język <math>L</math>, jej alfabet taśmowy zawiera <math>k</math> elementów, a zbiór stanów zawiera <math>s</math> elementów. Załóżmy dodatkowo, że maszyna w trakcie swojego działania nie musi w każdym ruchu przesuwać głowicy - może ją pozostawiać w miejscu; ponadto zażądajmy, by maszyna po ustaleniu wyniku działania wracała do położenia początkowego i przechodziła do stanu akceptującego (a dokładniej, żeby się w tym stanie "zapętlała"). Łatwo zauważyć, że każdą maszynę można "zmusić" do tego, aby spełniała te założenia nie zwiększając jej czasu działania więcej niż dwukrotnie. Złożoność czasową tej maszyny oznaczmy jako <math>T(n) </math>.
| |
|
| |
| Ustalmy teraz pewną długość słowa wejściowego - <math>n </math>; ponieważ znamy złożoność czasową maszyny <math>M</math>, możemy jeszcze przed rozpoczęciem działania stwierdzić, ile najdłużej może jej zająć rozwiązywanie problemu decyzyjnego i ile najwięcej może zużyć miejsca podczas tego procesu. Skonstruujemy zatem następujący układ logiczny, z <math>\lceil \log k \rceil \cdot n</math> wejściami, symulujący maszynę <math>M</math> - jego schemat przedstawiony jest na poniższym rysunku:
| |
|
| |
| [[ZO-2-4. Układ logiczny symulujący maszynę Turinga.]]
| |
|
| |
| Na powyższym schemacie prostokąty reprezentują pewne podukłady logiczne.
| |
| "Wyjścia" (czyli wartości węzłów na "dolnej" warstwie) prostokątów
| |
| na <math>i </math>-tej warstwie reprezentują konfigurację maszyny po <math>i</math> krokach. Wyjście <math>j</math>-tego prostokąta na <math>i</math>-tej warstwie składa się z <math>w = \lceil log k \rceil + \lceil log (s+1) \rceil </math> węzłów (bitów). Pierwsza część wyjścia oznacza symbol, który znajduje się w <math>j</math>-tej komórce taśmy maszyny Turinga po <math>i</math> krokach. Pozostała część mówi, czy w <math>i</math>-tym kroku
| |
| głowica znajduje się nad <math>j </math>-tą komórką, i, jeśli tak, w jakim stanie znajduje się maszyna (robimy to dodając jeden "sztuczny" stan, mówiący, że w danym miejscu nie ma głowicy; stąd na zapisanie stanu potrzebne jest
| |
| <math>\lceil log (s+1) \rceil </math> bitów). Zastanówmy się teraz, jakie powinno być zachowanie typowego "prostokąta" (oznaczonego symbolem A). Wynik działania tego podukładu zależy tylko i wyłącznie od wyników działania trzech podukładów z poprzedzającej go warstwy; jego funkcja jest zdefiniowana przez zachowanie maszyny Turinga, to znaczy:
| |
|
| |
| * jeśli żadna z trzech komórek poprzedniej warstwy nie zawierała głowicy, to należy przepisać symbol taśmy z prostokąta położonego bezpośrednio nad rozpatrywanym układem,
| |
|
| |
| * jeśli prostokąt położony bezpośrednio nad rozpatrywanym układem posiadał symulowaną głowicę, to należy odpowiednio zmodyfikować otrzymany od niego symbol taśmowy, i - w zależności od tego czy głowica się przesuwa czy nie - zapisać stan symulowanej maszyny lub zapisać sztuczny stan "brak głowicy",
| |
|
| |
| * analogiczne zasady (oczywiście odpowiednio zmodyfikowane) dla sytuacji, gdy głowica na <math>i-1</math>-szej warstwie znajdowała się w jednej z dwóch sąsiadujących z rozpatrywaną komórek.
| |
|
| |
| Prostokąty A reprezentują więc pewne z góry określone funkcje typu <math>\{ 0, 1 \}^{3w} \rightarrow \{ 0, 1 \}^w</math>. Wiedząc, że układ operatorów <math>\{ \wedge, \vee, \neg \}</math> jest układem funkcjonalnie pełnym, można stwierdzić, że prostokąt A jest implementowany przez określoną z góry, stałą liczbę bramek (oznaczmy ją <math>c_1</math>; stała ta jest zależna tylko od funkcji przejścia - w szczególności nie jest w żaden sposób zależna od <math>n</math>). Rozumując analogicznie możemy też stwierdzić, że prostokąty B, C, D i E reprezentują pewne funkcje logiczne i możemy je zaimplementować z użyciem co najwyżej <math>c_2</math> bramek.
| |
|
| |
| Pozostaje nam tylko ustalić, jak obliczamy wartość wyjścia układu logicznego;
| |
| tutaj postępowanie jest proste z powodu wymagań, jakie nałożyliśmy na maszynę:
| |
| Maszyna <math>M</math> akceptuje słowo wtedy i tylko wtedy, gdy po <math>T(n)</math> krokach głowica znajduje się w pozycji początkowej i maszyna jest w ustalonym stanie akcpetującym. Oba te warunki można sprawdzić na podstawie wyjścia podukładu reprezentowanego przez środkowy prostokąt <math>T(n)</math>-tej warstwy.
| |
|
| |
| Przedstawiliśmy zatem sposób, w jaki dla algorytmu o złożoności czasowej <math>T(n)</math> można skonstruować rodzinę układów logicznych o
| |
|
| |
|
| |
| <math>c_1 (2 T(n) - 1) \cdot T(n) + c_2 (4 T(n) + 1) = O(T(n)^2)</math>
| |
|
| |
| bramkach.
| |
|
| |
| {{wniosek|||
| |
| Jeżeli dla określonego problemu decyzyjnego istnieje algorytm dla maszyny
| |
| Turinga o wielomianowej złożoności czasowej, to istnieje rodzina układów
| |
| logicznych o wielomianowej złożoności ilościowej, rozwiązująca ten sam
| |
| problem decyzyjny.
| |
| }}
| |
|
| |
| Kontrapozycja tego wniosku jest czasami używana do pokazywania, że dla danego
| |
| problemu nie istnieje algorytm wielomianowy.
| |
