Unelte utilizator

Unelte site


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
laboratoare:laborator-01 [2017/02/20 12:25]
iulian.matesica
laboratoare:laborator-01 [2018/02/21 16:32] (curent)
mihai.iacov [Reguli esenţiale pentru promovarea laboratorului]
Linia 1: Linia 1:
 ====== Laborator 01: Introducere ====== ====== Laborator 01: Introducere ======
  
-===== 1. Obiectivele laboratorului pe întreg semestrul=====+===== 1. Reguli pentru laborator=====
  
-* familiarizarea cu structuri de date +Mai multe detalii pot fi găsite pe pagina [[informaii-generale:notare|Reguli de notare]].
-    * liste +
-    * stive +
-    * cozi+
  
 +==== Reguli esenţiale pentru promovarea laboratorului====
  
-introducere in algoritmi și tehnici de programare +* **MAXIM** 3 absenţe la laborator (**NU*se poate reface la alte grupe) 
-    recursivitate  +**MINIM** jumătate din punctajul de laborator
-    divide et impera +
-    greedy +
-    programare dinamică +
-    backtracking +
- +
- +
-introducere în teoria grafurilor +
-    parcurgeri de grafuri/arbori +
-    arbori binari, arbori minimi de acoperire +
-    * drumuri minime in graf (Dijkstra)+
  
  
Linia 270: Linia 258:
  
  
-===== 4. Calculul complexității algoritmilor =====+===== 4. GDB =====
  
-Analiza complexității unui algoritm are ca scop estimarea volumului de resurse de calcul necesare pentru execuția algoritmuluiPrin resurse se înțelege:\\ +GDB (GNU Debugger) este unealta standard pentru debugging (depanare) din GNUEste portabil şi poate fi folosit, printre altele, pentru a detecta instrucţiunea ce determina blocarea unui program la rulare (precum şi semnalul asociat erorii).
-• //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 problemeIn acest fel timpul de executie va fi exprimat prin numarul de operatii elementare executateSunt considerate operatii elementare cele aritmetice (adunare, scadere, ınmulțire, ımpartire), comparatiile si cele logice (negatie, conjuncte și disjunctie).+Exemplu de lansare:\\ 
 +<code> 
 +gcc -Wall -g my_file.c -o my_file.exe 
 +gdb my_file.exe 
 +</code>
  
-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.+**Câteva comenzi utile în timpul depanării:**\\ 
 +• **list** - arată conţinutul unui fişier (câteva rânduri, în jurul unui punct numit) \\ 
 +• **run** - porneşte executia\\ 
 +• **n** (sau **next**) - trece la instrucţiunea următoare (fără intra în apeluri de funcţii)\\ 
 +• **s** (sau **step**) - intră în apel de funcţie pentru a inspecta execuţia\\ 
 +• **b** (sau **break** sau **breakpoint**) - setează un breakpoint ce va forţa oprirea execuţiei în punctul respectiv\\ 
 +• **continue** - continuă execuţia până la următorul breakpoint\\ 
 +• **fin** (sau **finish**) - iese din funcţia curentă\\
  
-**Exemplul 1 - Suma a n numere** \\ +<note important>**list** şi **breakpoint** au nevoie de un parametru care să indice o instrucţiune ("punctul" dorit).</note>
-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 |}}+
  
 +Exemple de identificare a instrucţiunilor (la fel pentru list) - funcţie, rândul din fişier, adresa din memorie (eventual cu explicitarea fişierului):\\
 +<code>
 +breakpoint my_function
 +breakpoint 13
 +breakpoint *0x401377
  
-**Exemplul 2 - Înmulțirea a 2 matrici** \\ +breakpoint my_file:10 
-Consideram problema determinarii produsului a doua matriciA de dimensiune m×n si B de dimensiune n×p. In acest caz dimensiunea problemei este determinata de trei valori: (m, n, p). \\ +breakpoint my_file:my_function 
-In practica nu este necesara o analiza atat de detaliata ci este suficient sa se identifice +</code>
-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 |}} 
  
 ---- ----
Linia 312: Linia 309:
 ---- ----
 ===== 6. Referințe ===== ===== 6. Referințe =====
-[[https://users.info.uvt.ro/~dzaharie/alg/algoritmica_cap3.pdf|Analiza complexității]]+  - [[https://ocw.cs.pub.ro/courses/so/laboratoare/laborator-01|More about GCC, Linux, Makefiles]]
  
  
laboratoare/laborator-01.1487586301.txt.gz · Ultima modificare: 2017/02/20 12:25 de către iulian.matesica