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/18 21:23]
iulian.matesica [2.3.2. Fișiere header și include guards] 		laboratoare:laborator-01 [2017/03/05 19:19]
iulian.matesica [6. Referințe]
Linia 1: Linia 1:
 ====== Laborator 01: Introducere ====== ====== Laborator 01: Introducere ======
  
-===== 1. Obiectivele laboratorului =====+===== 1. Obiectivele laboratorului pe întreg semestrul=====
  
 * familiarizarea cu structuri de date * familiarizarea cu structuri de date
Linia 181: Linia 181:
 Utilitarul **make** folosește un fișier de configurare denumit ''%%Makefile%%''. Un astfel de fișier conține reguli și comenzi de automatizare. Utilitarul **make** folosește un fișier de configurare denumit ''%%Makefile%%''. Un astfel de fișier conține reguli și comenzi de automatizare.
  
-== Exemplu de utilizare ==+=== Exemplu de utilizare ===
 <file Makefile Makefile> <file Makefile Makefile>
 all: all:
Linia 209: Linia 209:
  
  
-== Sintaxa unei reguli ==+=== Sintaxa unei reguli === 
 +Sintaxa unei reguli dintr-un fișier Makefile:
  
 +{{ :laboratoare:makefile.png?nolink |}}
  
  
 + * **target** - este, de obicei, fișierul care se va obține prin rularea comenzii command. După cum s-a observat și din exemplul anterior, poate să fie o țintă virtuală care nu are asociat un fișier. 
 + * **prerequisites** - reprezintă dependențele necesare pentru a urmări regula; de obicei sunt fișiere necesare pentru obținerea țintei.
 + * **<tab>** - reprezintă caracterul tab și trebuie neaparat folosit înaintea precizării comenzii.
 + * **command** - o listă de comenzi (niciuna, una, oricâte) rulate în momentul în care se trece la obținerea țintei.
 +
 +
 +Un exemplu recomandat pentru un fișier ''%%Makefile%%'' este:
 +<file Makefile Makefile>
 +all: hello
 + 
 +hello: hello.o
 +        gcc hello.o -o hello
 + 
 +hello.o: hello.c
 +        gcc -c hello.c
 + 
 +clean:
 +        rm -f *.o *~ hello
 +</file>
 +
 +Observăm prezeța regulii ''%%all%%'' care va fi executată implicit.
 +
 + * **all** are ca dependență ''%%hello%%'' și nu execută nicio comandă
 + * **hello** are ca dependență ''%%hello.o%%'' și realizează link-editarea fișierului ''%%hello.o%%''
 + * **hello.o** are ca dependență ''%%hello.c%%'' și realizează compilarea fișierului ''%%hello.c%%'' în fișierul obiect ''%%hello.o%%''.
 +
 +<note>La regula cu target-ul ''%%hello.o%%'' se observă folosirea opțiunii ''%%-c%%'' a utilitarului ''%%gcc%%''. Aceasta opțiune se folosește pentru a obține doar fișierul obiect din codul sursă. Se oprește procesul de compilare inainte de obținerea executabilului. La final se continua compilarea cu unirea tuturor fișierelor obiect ''%%.o%%'' într-un fișier executabil. </note>
 +
 +=== Folosirea variabilelor ===
 +Un fișier ''%%Makefile%%'' permite folosirea de variabile. Astfel, un exemplu uzual de fișier ''%%Makefile%%'' este:
 +
 +<file Makefile Makefile>
 +CC = gcc
 +CFLAGS = -Wall -g
 + 
 +all: hello
 + 
 +hello: hello.o
 +        $(CC) $^ -o $@
 + 
 +hello.o: hello.c
 +        $(CC) $(CFLAGS) -c $<
 +        
 +clean:
 +        rm -f *.o *~ hello
 +</file>
 +
 +În exemplul de mai sus au fost definite variabilele ''%%CC%%'' și ''%%CFLAGS%%''. Variabia ''%%CC%%'' reprezintă compilatorul folosit, iar variabila ''%%CFLAGS%%'' reprezintă opțiunile de compilare utilizate; în cazul de față sunt afișarea tuturor warning-urilor (**-Wall**) cu suport de depanare (**-g**).
 +
 +Variabilele predefinte sunt:
 + * **$@** se expandează la numele target-ului
 + * **$^** se expandează la lista de cerințe (prerequisites - lista de dependențe)
 + * **$<** se expandează la prima cerință (la prima dependență)
 +
 +
 +===== 4. 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 |}}
  
 ---- ----
-===== 3. Ceva chestii cu surse si headere =====+===== 5. Exerciții ===== 
 + 
 +==== Exercițiul 1 - Hello world  ==== 
 +Realizați un program un C/C++ care afișează mesajul //Hello, World// la ieșirea standard. 
 + 
 +==== Exercițiul 2 - Makefile  ==== 
 +Realizați un fișier Makefile pentru programul de la exercițiul 1 astfel încat: 
 + 
 + * la rularea comenzii ''%%make build%%'' să se obțină executabilul ''%%hello%%'' 
 + * la rularea comenzii ''%%make clean%%'' să se șteargă fișierul ''%%hello%%'' de pe disc. 
 + 
 + 
 +==== Exercițiul 3 - Makefile cu surse multiple  ==== 
 + 
  
 ---- ----
-===== 4. Exerciții =====+===== 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]]
  
-==== Exercițiul 1 - Hello world (2p) ==== 
-==== Exercițiul 2 - Makefile (3p) ==== 
-==== Exercițiul 3 - Makefile cu surse multiple (3p) ==== 
-==== Exercițiul 4 - ?? ==== 
  
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