Andreialexandrudaniel Algnr2017 Tema1 B [618548]

1

ALGORITMI NUMERICI
TEMA 1

MASTERAND: [anonimizat]

2

CUPRINS

Introducere …………………………………………………………………………………………………. ………………. 3
Complexitate …………………………………………………………………………………… …………………….. ……. 4
Evaluarea timpului de calcul……………………………………………………………………………………. …….. . 4
Memorie ………………………………………………………………… ……………………………………………………. 8
Implementari eficiente în Matlab……………………………………………………………………………………… 8
Erori ……………………………………………. ……………………………………………………………………………… 9
Concluzii ……………………………………………………………………………………………………. ………………. 10
Anexe ………. …………………………………………………………………………………………………………… ……. 11
Referinte ………………………………………………………………………………………………….. ………………….. 12

3

INTRODUCERE

Un algoritm (cuvântul are ca origine numele matematicianului persan Al-Khwarizmi) si
înseamnă în matematică și informatică o metodă sau o procedură de calcul, alcătuită din pașii
elementari necesari pentru rezolvarea unei probleme sau categorii de probleme.

Un limbaj pseudocod este o scriere intermediară, menită să simplifice scrierea unui
algoritm într-un limbaj de programare și să ajute la realizarea clarității algoritmului, în timp
scurt.

Amintim cateva proprietati ale algoritmilor pe care le vom folosi mai departe:

 Eficiența – este proprietatea unui algoritm de a se termina nu numai într -un număr finit,
ci și "rezonabil" de pași, chiar dacă acesta nu este cel mai mic posibil (nu este optim).
Algorimul este ineficient și dacă rezultatul se obține într -un timp mai lung decât cel dorit
sau permis.

 Existența unei intrări (datele de prelucrat). Întrucât opera torii se aplică unui operand
(sau și mai multor operanzi deodată), este de neconceput un algoritm fără niciun operand.
Intrările permise formează împreună un set (mulțime) specific de obiecte sau valori, care
se numește "domeniul" algoritmului.

 Existența unei ieșiri (rezultatele). Este de neconceput un algoritm care nu are nicio
ieșire, deoarece în acest caz intră în discuție însăși utilitatea sa.

 Timpul de calcul al unui algoritm depinde de complexitatea problemei de rezolvat, de
performantele intrinseci ale calculatorului si limbajului de programare folosit si evident,
de algoritm.

4
COMPLEXITATE

Complexitatea unui algoritm din punct de vedere al necesarului de memorie este
dependența dintre necesarul de memorie exprimat in numărul de locații elementare de memorie
și dimensiunea problemei.
Unul dintre criteriile de evaluare a unui algoritm il reprezintă eroarea cu care se obtine
rezultatul. Erorile nu pot fi înlaturate total dintr -un calcul, iar acestea se propagă, astfe l incat,
chiar dacă datele de intrare ale unui program sunt foarte precise, rezultatul poate avea doar
cateva cifre semnificative corecte. De aceea este foarte important sa se estimeze eroarea
rezultatului unui algoritm.

Evaluarea Timpului de calcul

Timpul de calcul al unui algoritm depinde de complexitatea problemei de rezolvat, de
performanțele intrinseci ale calculatorului si limbajului de programare folosit și evident, de
algoritm .
Timpul de calcul este de fapt suma timpilor necesari pentru exec utarea tuturor
instrucțiunilor algoritmului. Nu toate instructiunile durează la fel de mult, de aceea, estimarea
complexității nu se poate face foarte precis, dar nici nu este necesar acest lucru. Se alege o
operație elementară, considerată a fi cea care d urează cel mai mult și se numara câte astfel de
operații elementare sunt executate.
Considerând ca operație elementară orice operatie algebrică și neglijand timpul de calcul
petrecut in declaratii și atribuiri, rezultă ca timpul de calcul este proportiona l cu dimensiunea
problemei. Exista mai multe tipuri de algoritmi clasificati dupa acest criteriu, si anume:

Algoritm lini ar (de ordinul 1), notat T=O(n)
– convertirea unei temperaturi din grade Celsius in grade Farenheit.
Algoritm pătrati c (de ordinul 2), notat T=O(n2)
– produsul dintre o matrice si un vector.
Algoritm cubi c (de ordinul 3), notat T=O(n3)
– inmultirea a doua matrice pătrate
Algor itm de ordin zero, notat T=O(1)
– algoritm pentru care timpul de calcul nu depinde de dimensiunea problemei.

5
Exercițiul 2.1:
Scrieți pseudocodul pentru înmulțirea a două matrice pătrate de dimensiune n și evaluați ordinul
de complexitate din punct de vedere al timpului de calcul.
intreg n;
matrice A,B;
pentru i = 1,n
pentru j = 1,n
intreg d = 0;
pentru k = 1,n;
d = d + A[i,k] * B[k,j]
A[i,j] = d;
Ordinul de complexitate este: 2* n3

Exercițiul 2.2:
Fie pseudocodul:

6
a) Estimați ordinul de complexitate din punct de vedere al timpului de calcul.
Particularizați rezultatul pentru cazul m = n.
Ordinul de complexitate este: 2* 𝐧𝟐
b) Implementați procedura gaxpy în Matlab.

function[y]=gaxpy(m,n,a,x,y)
b=zeros(m,1)
for i = 1:m
b[i,1)=y(1,1);
for j= 1:n
b(i,1)=b(i,1)+a[i,j)*x(i,1);
end
end
y=b;
c) Cum veți apela această funcție în Matlab pentru ca rezultatul să se scrie tot în variabila
y?

clear all;
clc;
a=[1,1,1;1,1,1];
x=[1;1;1;];
y=[1;1;];
y=gaxpy(2,3,a,x,y);

d) Scrieți un script care să contorizeze timpul de calcul necesar acestei proceduri, pentru
cazul n = m. Observați că rulări distincte ale acestuia nu conduc la exact aceleași valori numerice
pentru timpul de calcul. Comparați timpul obținut cu cel necesar instrucțiunii Matlab scrise cu
vectori. Pentru aceasta, realizați un grafic de tipul celui din figura 2.1. Comentați rezultatele
obținute.

În figura de mai jos putem observa că după rularea repetată a scriptului care contorizează
durata de calcul necesară procedurii gaxpy , rezultatele numerice ale timpului de calcul diferă
într-o mică măsur ă la fiecare execuție iar timpul de calcul este direct proportional cu
dimensiunea problemei.
Acestea variază într -un interval relativ mic, în cazul de față durata de execuție în cele
două cazuri se găsește în intervalul [ 0.041, 0.04 7] secunde, astfel diferența fiind de aproximativ 6
milisecunde .

7

8
Necesarul de memorie

Complexitatea unui algoritm din punct de vedere al necesarului de memorie este depen –
denta dintre necesarul de memorie exprimat ın numar de locatii elementare de memorie
si dimensiunea problemei
Spatiul de memorare este influentat de modul de reprezentare a datelor. De exemplu, o
matrice cu elemente ıntregi avand 100 de linii ¸si 100 de coloane din care doar 50 sunt nenule
(matrice rara) poate fi re prezentata ın una dintre variantele:
1. tablou bidimensional 100 × 100 (10000 de valori ıntregi);
2. tablou unidimensional ın care se ret¸in doar cele 50 de valori nenule si indicii
corespunzatori (150 de valori ıntregi).
De obicei, o locatie elementara de memorie este cea corespunzatoare unui numar real. Se
spune ca un algoritm este polinomial de ordin k din punct de vedere al necesarului de memorie
M, si se noteaza M=O(nk) daca si numai daca exista o constanta C astfel in cat M este mai mic
sau egal cu Cnk, unde n este dimensiunea problemei.
Exemplu:

Care este ordinul de complexitate din punct de vedere al necesarului de memorie pentru
algoritmul implementat la exercit iul 2.1?

întreg n,i,j,
tablou real X[n][n]
tablou real Y[n][n]
tablou real R[n][n]
citește n,X,Y,R
pentru i = 1,n
pentru j = 1,n
pentru k = 1,n
R[i][j] = X[i][k] * Y[k][j]

M=O(n2+2n+2)=O(n2) => un necesar de memorie de ordin 2.

Implementari eficiente in matlab

Algoritmul ideal trebuie sa fie simplu, sa dea o solutie corecta ıntr -un timp scurt ¸si sa
ocupe o zona mica de memorie. Nu exista ınsa nici un algoritm care sa rezolve perfect o
problema, fara nici un fel de eroare si atunci vom urmari sa avem erori rezonabile pentru o
anumita aplicatie . O analiza a erorilor posibile dintr -un algoritm este prezentata ın paragraful
urmator. De asemenea, criteriul referitor la timpul de calcul intra de multe ori ın contradictie cu
criteriul referitor la memoria necesara algoritmului.
In consecinta, la ale gerea unui algoritm potrivit pentru o aplicatie data, trebuie facut
un compromis ıntre trei criterii: timpul de calcul necesar obtinerii solutiei, necesarul de
memorie si acuratetea solutiei.

9
Erori de calcul

Erorile dintr -un algoritm se pot clasifica in functie de tipul cauzelor care le genereaza, si avem:
 Erori inerente
 Erori de rotunjire
 Erori de trunchiere

Erorile inerente sunt erorile cauzate de reprezentarea imprecisa a datelor de intrare,
erorile de rotunjire sunt cauzate de reprezentarea finita a numerelor reale in calculator iar erorile
de trunchiere provin din finitudinea inerenta unui algoritm corect construit.

Eroarea absoluta unei marimi din Rn este diferenta dintre valoarea aproximativa si
valoarea exacta a marimii. Definim marginea erori i absolute ax ca fiind majorarea normei erorii
absolute
Eroarea relativa a unei marimi este raportul dintre eroarea absoluta si norma marimii.
Se prefera folosirea unei margini a erorii relative rx, marime care satisface
Marginea erorii relative de rotunjire a unui sistem de calcul depinde doar de numarul
de cifre semnificative ce pot fi memorate. Pentru un sistem de calcul ce lucreaza cu k cifre
semnificative, marginea erorii relative de rotunjire este 10-k+1.
Erorile de trunchiere provin din carac terul finit al algoritmilor. Exista metode
matematice a caror solutie exacta necesita efectuarea unui numar infinit de calcule. Estimarea
erorilor de trunchiere se poate face de multe ori apriori, folosind rezultatele teoretice ale
matematicii.

Erorile i nerente sunt erorile cauzate de reprezentarea imprecisa a datelor de intrare.
Aceste erori nu pot fi eliminate, fiind important sa putem evalua modul in care ele se propaga in
calculele numerice, astfel incat sa poata fi estimata eroarea rezultatului in fu nctie de erorile
datelor de intrare.

10
Concluzii

O serie de exercitii capitolul 1 au in vedere realizarea unor implementari pentru cateva
operatii deja disponibile in Matlab , cu scopul de a putea compara timpii de calcul si de a
optimiza respectivele implementari pe baza indicatiilor date de Matlab folosind instructiunea
mlint prin ur mare acest capitol trecere in revista a conceptelor si functionalitatile oferite de
mediul de lucru Matlab.
Din reprezentarile grafice ale timpilor de calcul se observa ca operatiile deja disponiblie
in Matlab sunt foarte bine optimizate.

Elaborarea unu i algoritm inseamna intotdeauna stabilirea unui compromis intre timp de
calcul si necesar de memorie.
In general, algoritmii se concep astfel incat ei sa ofere si informatii despre eroare .
Algoritmii care nu fac asa ceva, sunt algoritmi lipsiti de valoare practica.

11
Anexe:
Ex 2.2 ( Pentru Figura 1.T Timp de calcul)

12

Bibliografie

[1] Algoritmi numerici prin exeritii si implementari in Matlab Editura MatrixROM, 2013
[2] https://romanta1.files.wordpress.com/2011/11/analiza -complexitatii -algoritmilor.pdf