Laboratorium :Algorytmy i struktury danych.
Temat:	Maszyna o Dostępie Swobodnym (RAM)
Wykonał:	Mariusz Daszkiewicz	Data:99-12-13 Gr.27	Ocena:

1.Cel ćwiczenia:

Ćwiczenie ma na celu zapoznanie ze strukturą i zasadą działania Maszyny o Dostępie Swobodnym (RAM).

2. Podstawowe pojęcia:

2.1: Algorytm: Przepis postępowania, który ma prowadzić w sposób automatyczny do rozwiązania określonego zadania, a posługiwanie się nim polega tylko na automatycznym wykonywaniu się instrukcji, które są zdefiniowane odpowiednio wcześniej.

2.2: Poprawność algorytmu jest spełniona dla trzech warunków:

1. Częściowa poprawność - dla każdych poprawnych danych wejściowych , jeżeli obliczenie algorytmu dochodzi do końca to wyniki są poprawne.

2. Własność określoności obliczeń - dla każdych poprawnych danych wejściowych, obliczenie algorytmu nie zostaje przerwane

3. Własność stopu - dla każdych poprawnych danych wejściowych, obliczenie algorytmu nie jest nieskończone

2.3: Złożoność obliczeniowa algorytmów jest to ilość zasobów, potrzebnych do jego wykonania.

Podstawowe zasoby: czas działania algorytmu oraz ilość potrzebnej pamięci.

W przypadku złożoności pamięciowej za jednostkę przyjmuje się słowo pamięci maszyny. Natomiast w przypadku złożoności czasowej wyznaczone zostały klasy złożoności czasowej. Zapis O(F(n)) oznacza, że czas pracy algorytmu jest rzędu F(n). Wyróżniamy następujące klasy złożoności:

1. LOG - problemy o algorytmach logarytmicznych O(log(n)):

2. P - problemy o algorytmach co najwyżej wielomianowych;

3. NP - problemy o niedeterministycznych algorytmach;

4. co - NP - problemy, których dopełnienie lub wersja dualna posiada niedeterministyczne algorytmy wielomianowe;

5. NPC (NP - zupełna) - klasa problemów o dolnej granicy wielomianowej i górnej ekspotencjalnej, każde dwa problemy NPC mogą być przekształcone w siebie algorytmem wielomianowym;

6. EXP - problemy o algorytmach ekspotencjalnych O(2^n);

2.4: Maszyna RAM

Jest modelem komputera o jednym akumulatorze i instrukcjach, które nie mogą być modyfikowane. Składa się z taśmy wejściowej, taśmy wyjściowej, licznika rozkazów, programu oraz pamięci jak jest to pokazane na rysunku:

2.5: Opis działania maszyny:

2.5.1: Taśma wejściowa jest potencjalnie nieskończona i podzielona na komórki, w których można umieszczać litery słowa wejściowego, będącego skończonym ciągiem liczb naturalnych. Z taśmy wejściowej wyłącznie można odczytywać informacje.

2.5.2: Taśma wyjściowa jest tego samego kształtu co taśma wyjściowa. Służy wyłącznie do zapisywania liczb naturalnych. Na początku wszystkie komórki taśmy wyjściowej są puste. Jeśli instrukcja wyjścia jest wykonywana to do komórki nad którą aktualnie znajduje się głowica, zostaje zapisana liczba.

2.5.3: Pamięć RAM składa się z ciągu rejestrów. Każdy z nich może przechowywać liczę naturalną dowolnym rozmiarze. Nie jest ustalone żadne ograniczenia na liczbę rejestrów.

2.5.4: Licznik rozkazów jest pojedynczą komórką, w której przechowywana jest liczba wykonywanych operacji.

2.5.5: Program maszyny jest przechowywany w pamięci, zatem nie może sam się modyfikować. Program jest ciągiem instrukcji, wśród których znajdują się operacje arytmetyczne( MULT, DIV, ADD, SUB), wejścia - wyjścia (LOAD, STORE, READ, WRITE, HALT) oraz instrukcje warunkowe (JUMP, JGTZ, JMPZ)

3. Ćwiczenia do wykonania:

3.1.1: Program na maszynę Ram wyznacz jacy wartości ciągu xi = (i-2)^2 dla i=1..n

READ 1

LOAD 1

ADD =1

STORE 1

SUB 1

ADD = 1

STORE 2

ET:

LOAD 2

SUB 2

STORE 3

MULT 3

STORE 4

WRITE 4

LOAD 2

ADD =1

STORE 2

SUB 1

JMPZ END

JUMP ET

END:

HALT

3.1.2: Program w języku Pascal

program ciag;

uses crt;

var x,i:integer;

begin

writeln('Podaj liczbę i: ');

readln(i);

x:=sqr(i-2);

writeln('Wartość ciagu wynosi: ',x);

repeat until keypressed;

end.

3.2.1: Program na maszynę Ram wyznacz jacy wartość w = i^i dla i = 5

READ 1

LOAD 1

STORE 3

SUB =1

STORE 2

ET:

LOAD 3

MULT 1

STORE 3

LOAD 2

SUB =1

STORE 2

JGTZ ET

WRITE 3

HALT

3.2.2: Program w języku pascal:

program potega;

uses crt;

const i=5;

var w:integer;

begin

w:=i*i*i*i*i;

writeln('Wartosc w wynosi: ',w);

repeat until keypressed;

end.

3.3.1: Program na maszynę Ram wyznacz jacy n!

READ 1

LOAD 1

STORE 2

ODEJMUJ:

SUB =1

JMPZ KONCZ

STORE 1

MULT 2

STORE 2

LOAD 1

JUMP ODEJMUJ

KONCZ:

WRITE 2

HALT

3.3.2: Program w języku Pascal

program silnia;

uses crt;

var sil,n:integer;

begin

write('Liczba n=');

readln(n);

begin

sil:=1;

while n>1 do

begin

sil:=sil*n;

n:=n-1;

end;

end;

writeln('n! wynosi ',sil);

repeat until keypressed;

end.

4. Złożoność czasowa i pamięciowa:

		Przykład a) N=4	Przykład a) N=5	Przykład b) N=4	Przykład b) N=5	Przykład c) N=4	Przykład c) N=5
Złożoność pamięciowa	Pascal	2	2	2	2	2	2
	RAM	5	5	4	4	3	3
Złożoność czasowa dominująca	Pascal	1	1	1	1	2	2
	RAM	7	7	3	3	2	2
Złożoność czasowa jednostkowa	Pascal	1	1	2	2	5	5
	RAM	52	63	27	34	25	31

4.Wnioski:

Z przeprowadzonego ćwiczenia wynika, że te same zadania realizowane w języku Pascal oraz za pomocą maszyny o swobodnym dostępie potrzebują różnej ilości zasobów , mianowicie maszyna RAM potrzebuje ich znacznie więcej. W maszynie tej wraz ze wzrostem liczby N zwiększa się złożoność czasowa, jednocześnie w języku Pascal mała zmiana wartości N nie wpływa znacząco na złożoność pamięciową i czasową powyższych programów. W maszynie RAM złożoność pamięciowa jest odzwierciedleniem zajętych rejestrów podczas pracy maszyny, natomiast w Pascalu jest proporcjonalna do ilości zmiennych znajdujących się w programie.

Porównując ze sobą Pascal i Maszynę RAM dochodzimy do wniosku, iż Pascal jest bezsprzecznie bardziej ekonomiczny pod względem złożoności czasowej i pamięciowej.

---