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ă

Both sides previous revision Versiuni anterioare
Ultima versiune Both sides next revision
laboratoare:laborator-02 [2018/02/25 19:32]
mihai.iacov
laboratoare:laborator-02 [2018/02/25 19:47]
mihai.iacov
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 31: Linia 56:
  
  
-====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 203:
  
 {{ :​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 224:
 {{ :​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 239:
 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.txt · Ultima modificare: 2018/02/25 20:02 de către mihai.iacov