Ministerul educatiei stiintei si sport

Ministerul Educaiei iTineretului al Republicii MoldovaUniversitatea Tehnic a Moldovei

Facultatea IM

Catedra: Automatica si Tehnologii Informationale

RaportNr1

ANALIZA SI PROIECTAREA ALGORITMILORTEMA: Analiza algoritmilorA elaborat:

st. gr.TI-142 Tincu M. ___________

A verificat:

Prof. Universitar Bagrin V. ____________

Chiinu 2015Scopul lucrrii:1. Analiza empiric a algoritmilor.

2. Analiza teoretic a algoritmilor.

3. Determinarea complexitii temporale i asimptotice a algoritmilor

Consideratii teoretice:

Numerele lui Fibonacci.

Sirul lui Fibonacci este definit prin urmatoarea recurenta:

Analiza matematic a complexitii algoritmilor poate fi dificil n cazul unor algoritmi care nu sunt simpli.O alternativ la analiza matematic a complexitii o reprezint analiza empiric.Etapele analizei empirice

1. Se stabilete scopul analizei.

2. Se alege metrica de eficien ce va fi utilizat (numr de execuii ale unei/unor operaii sau timp de execuie a ntregului algoritm sau a unei poriuni din algoritm.3. Se stabilesc proprietile datelor de intrare n raport cu care se face analiza (dimensiunea datelor sau proprieti specifice).4. Se implementeaz algoritmul ntr-un limbaj de programare.5. Se genereaz mai multe seturi de date de intrare.6. Se execut programul pentru fiecare set de date de intrare.7. Se analizeaz datele obinute.Pentru a efectua o analiz empiric nu este suficient un singur set de date de intrare ci mai multe, care s pun n eviden diferitele caracteristici ale algoritmului.Sarcina

Executarea unui program in limbajul de programare C++ care va compara cele 3 metode expuse in materialul teoretic p-ru diferite valori ale lui n.

Listingul programului:

#include using namespace std;

int fibonacci(int n)

{

if ((n == 1) || (n == 0))

{

return(n);

}

else

{

return(fibonacci(n - 1) + fibonacci(n - 2));

}

}

int fib3(int n)//3 metoda dupa pseudocod{

n = n - 1;

int i = 1, j = 0, k = 0, h = 1, t = 1;

while (n > 0) {

if (n % 2 != 0)

{

t = h*j;

j = i*h + j*k + t;

i = i*k + t;

}

{

t = h*h;

h = 2 * k*h + t;

k = k*k + t;

n = (n / 2);

}

}

return j;

}

int main()

{

//iteratie

int range, first = 0, second = 1, fibonaci = 0;

cout range;

cout