Unelte utilizator

Unelte site


laboratoare:laborator-02

Diferențe

Aici sunt prezentate diferențele dintre versiunile selectate și versiunea curentă a paginii.

Link către această vizualizare comparativă

Ambele părți revizuirea anterioară Versiuni anterioare
Urmatoarea versiune
Versiuni anterioare
laboratoare:laborator-02 [2018/02/25 21:32]
mihai.iacov
laboratoare:laborator-02 [2018/02/25 22:02] (curent)
mihai.iacov [2.2 Caracterizarea unui algoritm]
Linia 12: Linia 12:
 =====2. Introducere===== =====2. Introducere=====
  
-====2.1 Caracterizarea unui algoritm====+==== 2.1 Calculul complexităţii algoritmilor ==== 
 + 
 +Analiza complexității unui algoritm are ca scop estimarea volumului de resurse de calcul necesare pentru execuția algoritmului. Prin resurse se înțelege:\\ 
 +• //Spațiul de memorie// necesar pentru stocarea datelor pe care le prelucrează algoritmul.\\ 
 +• //Timpul necesar pentru execuția// tuturor prelucrărilor specificate în algoritm.  
 + 
 +Această analiză este utilă pentru a stabili dacă un algoritm utilizează un volum acceptabil de resurse pentru rezolvarea unei probleme. In acest fel timpul de executie va fi exprimat prin numarul de operatii elementare executate. Sunt considerate operatii elementare cele aritmetice (adunare, scadere, ınmulțire, ımpartire), comparatiile si cele logice (negatie, conjuncte și disjunctie). 
 + 
 +Este așadar suficient sa se contorizeze doar anumite tipuri de operații elementare,  numite //operații de bază//. Timpul de executie  al ıntregului algoritm se obtine ınsumand timpii de executie ai prelucrarilor componente. 
 + 
 +**Exemplul 1 - Suma a n numere** \\ 
 +Consideram problema calculului sumei .  Dimensiunea acestei probleme poate fi considerata //n//  Algoritmul si tabelul cu costurile corespunzatoare prelucrărilor sunt prezentate ın Tabel. Insumand timpii de executie ai prelucrarilor elementare se obtine: T(n)=n(c<sub>3</sub> + c<sub>4</sub> + c<sub>5</sub>) + c<sub>1</sub> + c<sub>2</sub> + c<sub>3</sub> deci T(n)=k<sub>1</sub>n + k<sub>2</sub>, adica timpul de executie depinde liniar de dimensiunea 
 +problemei.  Costurile operatiilor elementare influenteaza doar constantele ce intervin ın functia T(n). 
 +{{ :laboratoare:complexitati1.png?600 |}} 
 + 
 + 
 +**Exemplul 2 - Înmulțirea a 2 matrici** \\ 
 +Consideram problema determinarii produsului a doua matrici: A de dimensiune m×n si B de dimensiune n×p. In acest caz dimensiunea problemei este determinata de trei valori: (m, n, p). \\ 
 +In practica nu este necesara o analiza atat de detaliata ci este suficient sa se identifice 
 +operatia dominantă si sa se estimeze numarul de repetari ale acesteia. Prin operatie dominanta se ıntelege operatia care contribuie cel mai mult la timpul de executie a algoritmului si de regulă este operatia ce apare ın ciclul cel mai interior. În exemplul  ar putea fi considerata ca operatie dominanta, operatia de ınmultire. In acest caz costul executiei algoritmului ar fi T(m, n, p)=mnp  
 + 
 +{{ :laboratoare:complexitati2.png?600 |}} 
 + 
 +---- 
 + 
 +====2.2 Caracterizarea unui algoritm====
  
 Numim **sortare** orice aşezare(sau - mai clar - **reaşezare**) a unor elemente date în aşa fel încât, după aşezare, să existe o  **ordine completă** în funcţie de un atribut(numit **cheie**) al elementelor. Numim **sortare** orice aşezare(sau - mai clar - **reaşezare**) a unor elemente date în aşa fel încât, după aşezare, să existe o  **ordine completă** în funcţie de un atribut(numit **cheie**) al elementelor.
Linia 30: Linia 55:
  *o dimensiune de ordinul lui n pentru memoria alocată. În acest caz, spunem că avem "**complexitate de spaţiu de ordinul lui n**"  *o dimensiune de ordinul lui n pentru memoria alocată. În acest caz, spunem că avem "**complexitate de spaţiu de ordinul lui n**"
  
 +<note important>
 +În acest material se face abuz de notaţie. **NU** confundaţi cu notaţiile **Big-O (O)**, **Big-Omega (Ω)**, **Big-Theta (θ)**. De fapt, notaţia din acest material "O(n)" se apropie ca semnificaţie de notaţia Big-Theta.
 +</note>
  
-====2.Metodele de sortare folosite====+====2.Metodele de sortare folosite====
  
 Fiecare algoritm se bazează pe o metodă de sortare: Fiecare algoritm se bazează pe o metodă de sortare:
Linia 178: Linia 206:
  
 {{ :laboratoare:merge-sort-example-300px.gif?nolink |}} {{ :laboratoare:merge-sort-example-300px.gif?nolink |}}
- 
-===Implementare :=== 
-<file cpp> 
-void mergeSort(int a[],int st, int m, int dr) 
-{ 
-    int b[100]; 
-    int i, j, k; 
-    i = 0; j = st; 
-    // copiem prima jumatate a vectorului a in b 
-    while (j <= m) 
-        b[i++] = a[j++]; 
-    i = 0; k = st; 
-    // copiem inapoi cel mai mare element la fiecare pas 
-    while (k < j && j <= dr) 
-        if (b[i] <= a[j]) 
-            a[k++] = b[i++]; 
-        else 
-            a[k++] = a[j++]; 
-    // copiem elementele ramase daca mai exista 
-    while (k < j) 
-        a[k++] = b[i++]; 
-} 
-void merge(int a[],int st, int dr) 
-{ 
-    if (st < dr) 
-    { 
-        int m = (st+dr)/2; 
-        merge(a,st, m); 
-        merge(a,m+1, dr); 
-        mergeSort(a,st, m, dr); 
-    } 
-} 
-</file> 
  
 ====3.5 Quick sort==== ====3.5 Quick sort====
Linia 232: Linia 227:
 {{ :laboratoare:sorting_quicksort_anim.gif?nolink |}} {{ :laboratoare:sorting_quicksort_anim.gif?nolink |}}
  
-===Implementare :=== 
-<file cpp> 
-void qSort(int a[],int st,int dr) 
-{ 
-    int temp,min,max,mijl; 
-    mijl = a[st+(dr-st)/2]; //luam mijlocul intervalului 
-    min = st; max = dr; 
-    do 
-    { 
-        while(a[min] < mijl) min++; 
-        while(a[max] > mijl) max--; 
-        if(min <= max) //interschimbare 
-        { 
-            temp = a[min]; 
-            a[min++] = a[max]; 
-            a[max--] = temp; 
-        } 
-    }while(min <= max); //la fiecare pas sortam "mai bine" intervalul st-dr 
-    //cand numai avem ce face schimbam intervalul 
-    if(st < max) qSort(a,st,max); //crescator 
-    if(dr > min) qSort(a,min,dr); //crescator 
-} 
-</file> 
  
 ===== 4. Exerciţii ===== ===== 4. Exerciţii =====
Linia 270: Linia 242:
 Puteţi utiliza următorul model pentru exerciţiile propuse: {{ :laboratoare:scheletsortare.zip |}} Puteţi utiliza următorul model pentru exerciţiile propuse: {{ :laboratoare:scheletsortare.zip |}}
  
-===== 4. Exerciţii de laborator (Linux) =====+===== 5. Exerciţii de laborator (Linux) =====
 Pentru acest laborator puteți descărca scheletul de cod de [[http://elf.cs.pub.ro/sda-ab/wiki/_media/laboratoare/lab8_sortari-skel.zip|aici]]. Descărcați arhiva și dezarhivați-o.  Pentru acest laborator puteți descărca scheletul de cod de [[http://elf.cs.pub.ro/sda-ab/wiki/_media/laboratoare/lab8_sortari-skel.zip|aici]]. Descărcați arhiva și dezarhivați-o. 
  
laboratoare/laborator-02.1519587134.txt.gz · Ultima modificare: 2018/02/25 21:32 de către mihai.iacov