Metode Numerice

LABORATOR NR.1

COMPLEXITATEA ALGORITMILOR NUMERICI

1. Elemente teoretice :

Calitatea unui algoritm este apreciată prin eficienţa sa spaţială (memoria necesară datelor şi programului ) şi temporală ( timpul de calcul necesar obţinerii soluţiei ) . Pentru a determina dependenţa timpului de calcul de dimensiunea problemei rezolvate de algoritm se consideră ca referinţă timpul necesar efectuării unei operaţii elementare , adunare sau înmulţire de numere reale şi apoi se evaluează numărul acestor operaţii .

O problemă poate avea doi sau mai mulţi algoritmi de rezolvare cu ordine de complexitate diferite .

În algoritmii numerici timpul de calcul este consumat preponderent în operaţiile repetate ciclic . De aceea ordinul de complexitate este dat , în general , de numărul ciclurilor :

; ordinul 0

pentru ; ordinul 1

pentru

pentru ; ordinul 2

pentru i

pentru

pentru

; ordinul 3

2. Chestiuni de studiat :

2.1. Studierea funcţiilor Matlab rand , clock , etime , sum , for , a operaţiilor cu tablouri , polyfit , polyval .

2.2. Determinarea eficienţei temporale a algoritmului de obţinere a produsului scalar a doi vectori aleatori n dimensionali .

2.3. Determinarea eficienţei temporale a algoritmului de obţinere a produsului a două matrici pătratice aleatoare n dimensionale .

2.4. Determinarea erorii relative de rotunjire pentru staţia de lucru curentă .

3. Modul de lucru :

3.1. Determinarea eficienţei temporale a algoritumului de obţinere a produsului scalar a doi vectori n dimensionali :

Lucrarea îşi propune să determine dependenţa timpului de calcul a produsului scalar în funcţie de dimensiunea vectorilor şi să estimeze ordinul de complexitate temporală . Se va crea un program Matlab . Cei doi vectori vor fi generaţi aleator folosind funcţia rand() din Matlab .

Această funcţie generează o secvenţă de numere aleatoare uniform distribuite în intervalul (0,1) . Apelată cu rand(n) generează o matrice patratică de numere aleatoare , de dimensiune n .

Pentru generarea celor doi vectori , x(n) şi y(n) funcţia va fi apelată cu rand(1,n) .

Pentru determinarea timpului de execuţie se foloseşte funcţia Matlab etime .

Timpul de execuţie al unei secvenţe de instrucţiuni se determină cu etime în felul următor :

t0=clock;

instrucţiuni

etime(clock,t0)

Funcţia clock determină ora şi data curentă .

Pentru determinarea produsului scalalr se foloseşte funcţia sum , care sumează elementele unui vector .

Utilizarea operatorului .* (operaţii cu tablouri ) permite înmulţirea celor doi vectori , componentă cu componentă .

Instrucţiunea x.*y generează un vector ale cărui componente sunt produsele x(i)*y(i) .

Instrucţiunea sum(x.*y) determină suma lor .

Funcţia plot permite reprezentarea grafică a vectorului timp de execuţie tf în funcţie de vectorul n care conţine valorile dimensiunilor vectorilor .

Instrucţiunea n=100:200:1000 generează un vector ale cărui componente variază cu pasul 200 până la 1000 .

Generarea vectorilor cu o anumită dimensiune , determinarea produsului scalar corespunzător acesteia şi a timpului de execuţie tf se fac în interiorul unui ciclu for .

La fiecare valoare a lui n se determină un i care este un contor pentru vectorul tf .

De exemplu când n=100 i=1 şi deci în prima componentă a vectorului tf , tf(1) se stochează prima valoare a timpului de execuţie corespunzătoare lui n=100 .

Algoritmul se repată până când n=100 .

Apoi i este incrementat la i+1 pentru a se memora tf-ul următor în locaţia 2 din vectorul tf .