Structuri de Date și Algoritmi (seria 1AB)

Unelte utilizator

Unelte site

Ești aici: Structuri de date și algoritmi » Laboratoare » Laborator 01: Introducere
Traseu:
laboratoare:laborator-01

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
Urmatoarea versiune Ambele părți următoarea reviziune
laboratoare:laborator-01 [2017/02/19 23:23]
florina_elena.barbu [4. Calculul complexității algoritmilor] 		laboratoare:laborator-01 [2017/02/20 12:21]
iulian.matesica [5. Exerciții]
Linia 269: Linia 269:
  * **$<** se expandează la prima cerință (la prima dependență)  * **$<** se expandează la prima cerință (la prima dependență)
  
-----+
 ===== 4. Calculul complexității algoritmilor ===== ===== 4. Calculul complexității algoritmilor =====
  
Linia 281: Linia 281:
  
 **Exemplul 1 - Suma a n numere** \\ **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 +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
->=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). problemei.  Costurile operatiilor elementare influenteaza doar constantele ce intervin ın functia T(n).
 {{ :laboratoare:complexitati1.png?600 |}} {{ :laboratoare:complexitati1.png?600 |}}
Linia 288: Linia 287:
  
 **Exemplul 2 - Înmulțirea a 2 matrici** \\ **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 |}} {{ :laboratoare:complexitati2.png?600 |}}
  
Linia 293: Linia 296:
 ===== 5. Exerciții ===== ===== 5. Exerciții =====
  
-==== Exercițiul 1 - Hello world (2p) ==== +Realizati un program un C/C++ care afiseaza mesajul //Hello, World// la iesirea standard. 
-==== Exercițiul 2 - Makefile (3p) ==== + 
-==== Exercițiul 3 - Makefile cu surse multiple (3p) ==== +==== Exercițiul 1 - Hello world  ==== 
-==== Exercițiul 4 - ?? ====+==== Exercițiul 2 - Makefile  ==== 
 +==== Exercițiul 3 - Makefile cu surse multiple  ==== 
 + 
 +---- 
 +===== 6. Referințe ===== 
 +[[https://users.info.uvt.ro/~dzaharie/alg/algoritmica_cap3.pdf|Analiza complexității]] 
  
laboratoare/laborator-01.txt · Ultima modificare: 2018/02/21 16:32 de către mihai.iacov

Unelte pagină

Exceptând locurile unde este altfel specificat, conținutul acestui wiki este licențiat sub următoarea licență: CC Attribution-Share Alike 4.0 International
CC Attribution-Share Alike 4.0 International Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki