Universitatea Babeş-Bolyai Cluj-Napoca
Facultatea de Matematică şi Informatică
Ciclul de studii: Licenţă
Domeniul: Informatică
Programul de studii: Informatică - linia de studiu română
Limba de predare: Română

SYLLABUS

I. Date generale
Codul	Disciplina	
MID0001	Fundamentele programării	

Semestrul	Ore: C+S+L	Categoria	Statutul	
1	2+2+2	fundamentala	obligatorie	

II. Cadre didactice cu norma de bază în Universitate
Numele şi	Titlul	Gradul	Catedra	Tipul activităţii	
prenumele	ştiinţific	didactic		C	S	L	
SERBAN Gabriela	Dr.	Conf.	Limbaje şi Metode de Programare	*			

Cadre didactice asociate
Numele şi	Titlul	Instituţia	Tipul	Tipul activităţii	
prenumele	ştiinţific		postului	C	S	L	

III. Obiectivele disciplinei
1. Intelegerea notiunii de algoritm si invatarea limbajului Pseudocod pentru descrierea algoritmilor.
2. Formarea deprinderilor de proiectare a algoritmilor.
3. Cunoasterea unor algoritmi pentru unele clase de probleme: operatii cu vectori, matrice, polinoame, rezolvari de ecuatii si sisteme liniare, cautare, interclasare si sortare.
4. Formarea deprinderilor de concepere, executie, testare si punere la punct a programelor Pascal cu structurile de date simple.
5. Formarea unui stil de programare.	

IV. Conţinutul disciplinei
1.	Algoritmi şi descrierea lor
2.	Subalgoritmi (Pseudocod)
3.	Codificarea algoritmilor Pseudocod în Pascal 
4.	Faze in viata unui program
5.	Corectitudinea algoritmilor  
6.	Dezvoltarea corecta a algoritmilor din specificatii
7.	Metode generale de elaborare a algoritmilor
8.	Metoda top-down şi Rafinarea în pasi succesivi
9.	Recursivitate
10.	Tipuri Abstracte de Date
11.	Tehnici de programare: Divide&Impera, Backtracking, Greedy, Programare dinamica, metode euristice. 
12.	Complexitatea algoritmilor
13.	Algoritmi de cautare si complexitatea lor
14.	Algoritmi de sortare si complexitatea lor	

V. Bibliografie
1.	1 Frentiu M., Pop H.F., Serban G., Programming Fundamentals, Ed.Presa Universitara Clujeana, Cluj-Napoca, 2006, 234 pagini
2.	Frentiu M., Pop H.F., Fundamentals of Programming, Ed.Presa Universitara Clujeana, Cluj-Napoca, 2006, 220 pagini 
3.	Frentiu M., Lazar I., Bazele programarii. Proiectarea algoritmilor, Ed.Univ. Petru Maior, Targu-Mures, 2000, 184 pagini 
4.	Kasa Z., Algoritmusok tervezese, Ed. Studium, Cluj, 1994	

VI. Tematica activităţilor didactice pe săptămâni
1.  Algoritmi şi descrierea lor  [1, ch. 1] (1 curs – S1 + 1 seminar – S1)
	 Noţiunea de algoritm
	 Variabila, tip, specificare
	 scheme logice
	 limbajul Pseudocod
		- Structura liniară
		- Structura alternativă
		- Structura repetitivă

2. Subalgoritmi (Pseudocod) [1, ch. 1] (1 curs – S2 + 1 laborator – S2)
	 noţiunea de subalgoritm
	 parametrii formali
 definirea unui subalgoritm (funcţie şi procedură)
 apelul unui subalgoritm
 importanţa subalgoritmilor în programare

3. Codificarea algoritmilor Pseudocod în Pascal [1, ch. 3] (1 laborator – S3)
	 Elemente de bază ale limbajului Pascal 
	 Declaraţii şi Instrucţiuni
	 Structura unui program Pascal
	 Codificare

4. Faze in viata unui program [1, ch. 3] (1 curs – S3)
 Faze în realizarea unui program:
     specificare,  proiectare,  codificare,  testare,  documentare, verificare
 intretinerea programelor: corectivă, adaptivă, perfectivă
 Testarea programelor
- Metoda cutiei negre
- Metoda cutiei transparente

5. Corectitudinea algoritmilor  [1, ch. 2] (1 curs – S4)
 stare în execuţia unui program;
 calcul efectuat de un algoritm;
 rezultatul calculului efectuat de un algoritm;
 parţial corectitudine;
 terminare;
 (total) corectitudine;
 metoda lui Floyd de demonstrare a corectitudinii

6. Dezvoltarea corecta a algoritmilor din specificatii [1, ch. 2] (1 curs – S4)
 algoritm abstract
 ideea de rafinare
 reguli de rafinare
● exemple

7. Metode generale de elaborare a algoritmilor [1, ch. 4] (1 curs – S5 + 1 laborator – S4)
 programare modulara
-	diagrama de structura
-	specificarea modulelor
 programare structurata
-	teorema lui Bohm-Jacopini
-	importanţa clarităţii în programare
-	elemente de claritate: indentare, spaţiere, denumiri,...
● stil în programare

8. Metoda top-down şi Rafinarea în pasi succesivi  [1, ch. 4] (1 curs – S6 + 2 laboratoare – S5, S6)
 metoda top-down
 metoda bottom-up
	 rafinarea în paşi succesivi

9. Recursivitate [3, ch. 3, 4] (1 curs – S7 + 1 laborator – S7)
● Noţiunea de  Recursivitate
● Recursivitate directa si indirecta
● Exemple 

10. Tipuri Abstracte de Date [1, ch. 5] (1 curs – S8 + 2 laboratoare – S8, S9)
	 specificarea unui TAD
	 Unit Pascal
	 Implementarea unui TAD în Pascal
	 Folosirea unui TAD în programare

11. Metoda Divide et Impera [1, ch. 7] (1 curs – S9)
  Prezentare generala
● Descrierea subalgoritmului
● Exemple

12. Metoda Backtracking [1, ch. 7] (1 curs – S9 + 1 laborator – S10)
 Prezentarea generală a metodei Backtracking
	 Algoritm (subalgoritm) Backtracking
	 Extinderi ale metodei Backtracking
● Exemple

13. Metoda Greedy [1, ch. 7] (1 curs – S10)
	 Prezentarea generală a metodei greedy
 Algoritmul Greedy
● Exemple si contraexemple
● Eusristica Greedy

14. Alte metode [1, ch. 7] (1 curs – S10)
	 Metoda programării dinamice
 Metoda Branch and Bound
 Metode euristice
● Exemple

15. Complexitatea algoritmilor [1, ch. 6] (2 cursuri – S11, S12 + 1 laborator – S11)
	 definitia complexităţii
	 complexitatea ca timp de executie
	 complexitatea ca memorie suplimentara necesara
	 analiza empirica si analiza asimptotica
	 notatia asimptotica: o-mare, o-mic, omega-mare, omega-mic, theta; proprietati
	 ordine de mărime particulare
	 compararea algoritmilor din punctul de vedere al eficienţei
	 complexitatea structurală
	
16. Algoritmi de cautare si complexitatea lor [1, ch. 8] (1 curs – S13)
	 Specificarea problemei de căutare
	 Metode de căutare
- parcurgere secvenţială
- căutare binară
 Complexitatea algoritmilor de căutare

17. Algoritmi de sortare si complexitatea lor [1, ch. 8] (1 curs – S14)
	 Specificarea problemei de sortare
	 Metode de sortare
	    - Metoda de sortare a bulelor (BubbleSort)
	    - Sortare bazată pe selectarea minimului/maximului (SelectionSort)
	    - Sortare prin inserare (InsertSort)
	    - Sortare rapidă (QuickSort)
- Sortare prin interclasare (MergeSort)
	 Complexitatea algoritmilor de sortare	

VII. Metode didactice folosite
Prelegeri, expuneri, conversatii, proiecte, exercitii, studiu individual.	

VIII. Evaluare
La sfarsitul semestrului activitatea se incheie cu examen scris (nota E) si o proba practica la laborator (nota P). Subiectele de examen vor consta din intrebari teoretice din toata materia predata si o problema, dintre cele tratate la curs, seminar si laborator. Studentii vor da o lucrare de control la seminar (nota C). Activitatea de laborator se incheie cu o apreciere a activitatii din timpul anului (nota L), iar documentatiile elaborate pentru lucrarile de laborator vor primi o nota D. Nota finala este media ponderata a celor patru note mentionate mai sus, cu conditia ca toate notele sa fie cel putin 5, in caz contrar nu se promoveaza examenul. Nota Finala = 50%E + 15%P + 15%C + 10%L + 10%D.	

IX. Bibliografie suplimentară
1.	Knuth, D.E., Tratat de programare a calculatoarelor. Algoritmi fundamentali. Ed.Tehnica, Bucuresti 1974 
2.	Knuth, D.E., Tratat de programare a calculatoarelor. Sortare si cautare. Ed.Tehnica, Bucuresti 1976 	

	Data,							Titular curs,
	10.04.2007						Conf. Dr. SERBAN Gabriela