Aici sunt prezentate diferențele dintre versiunile selectate și versiunea curentă a paginii.
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/20 12:25] iulian.matesica |
laboratoare:laborator-01 [2018/02/19 20:35] mihai.iacov [6. Referințe] |
||
---|---|---|---|
Linia 270: | Linia 270: | ||
- | ===== 4. Calculul complexității algoritmilor | + | ===== 4. GDB ===== |
- | Analiza complexității unui algoritm are ca scop estimarea volumului de resurse de calcul necesare | + | GDB (GNU Debugger) este unealta standard |
- | • //Spațiul de memorie// necesar | + | |
- | • //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 | + | Exemplu |
+ | < | ||
+ | gcc -Wall -g my_file.c -o my_file.exe | ||
+ | gdb my_file.exe | ||
+ | </ | ||
- | Este așadar suficient sa se contorizeze doar anumite tipuri | + | **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ă | ||
+ | • **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> |
- | Consideram problema calculului sumei . Dimensiunea acestei probleme poate fi considerata // | + | |
- | problemei. | + | |
- | {{ : | + | |
+ | 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): | ||
+ | < | ||
+ | breakpoint my_function | ||
+ | breakpoint 13 | ||
+ | breakpoint *0x401377 | ||
- | **Exemplul 2 - Înmulțirea a 2 matrici** \\ | + | breakpoint my_file:10 |
- | 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). \\ | + | breakpoint my_file:my_function |
- | 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 | + | |
- | {{ : | ||
---- | ---- | ||
Linia 312: | Linia 321: | ||
---- | ---- | ||
===== 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/ |