Diferențe

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

Link către această vizualizare comparativă

--- laboratoare:laborator-02 [2018/02/25 21:32]
mihai.iacov
+++ laboratoare:laborator-02 [2018/02/25 21:47]
mihai.iacov
@@ Linia 12: / Linia 12: @@
 =====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.
@@ Linia 31: / Linia 56: @@
-====2.2 Metodele de sortare folosite====
+====2.3 Metodele de sortare folosite====
 Fiecare algoritm se bazează pe o metodă de sortare:
@@ Linia 178: / Linia 203: @@
 {{ :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====
@@ Linia 232: / Linia 224: @@
 {{ :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 =====
@@ Linia 270: / Linia 239: @@
 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.

Structuri de Date și Algoritmi (seria 1AB)

Unelte utilizator

Unelte site

Diferențe

Unelte pagină