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+P	Categoria	Statutul	
1	2+2+2+0	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	
GURAN Adriana Mihaela	Dr. 	Lect.	Limbaje şi Metode de Programare	*			
Czibula Istvan	Dr.	Asist.	Limbaje şi Metode de Programare		*	*	
Mihis Andreea		Asist.	Limbaje şi Metode de Programare			*	

Cadre didactice asociate
Numele şi	Titlul	Instituţia	Tipul	Tipul activităţii	
prenumele	ştiinţific		postului	C	S	L	
Pop Ionel	doctorand	Universitatea Babes-Bolyai, Facultatea de Matematica si Informatica				*	
Stoica Ramona	doctorand	Universitatea Babes-Bolyai, Facultatea de Matematica si Informatica				*	
Bocicor Iulia	doctorand	Universitatea Babes-Bolyai, Facultatea de Matematica si Informatica				*	
Craciun Florin	Dr.	Universitatea Babes-Bolyai, Facultatea de Matematica si Informatica			*		

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 si descrierea lor
- Notiunea de algoritm
- Variabila, tip, specificare
- scheme logice
- limbajul Pseudocod: Structura liniara, Structura alternativa, Structura repetitiva

2. Subalgoritmi (Pseudocod) 
- notiunea de subalgoritm
- parametrii formali
- definirea unui subalgoritm (functie si procedura)
- apelul unui subalgoritm
- importanta subalgoritmilor în programare

3. Codificarea algoritmilor Pseudocod în Pascal
- Elemente de baza ale limbajului Pascal 
- Declaratii si Instructiuni
- Structura unui program Pascal
- Codificare

4. Faze in viata unui program 
- Faze în realizarea unui program: specificare,  proiectare,  codificare,  testare,  documentare, verificare
- intretinerea programelor: corectiva, adaptiva, perfectiva
- Testarea programelor: Metoda cutiei negre, Metoda cutiei transparente

5. Corectitudinea algoritmilor  
- stare în executia unui program;
- calcul efectuat de un algoritm;
- rezultatul calculului efectuat de un algoritm;
- partial corectitudine;
- terminare;
- (total) corectitudine;
- metoda lui Floyd de demonstrare a corectitudinii

6. Dezvoltarea corecta a algoritmilor din specificatii
- algoritm abstract
- ideea de rafinare
- reguli de rafinare
- exemple

7. Metode generale de elaborare a algoritmilor 
- programare modulara
- programare structurata
- teorema lui Bohm-Jacopini
- importanta claritatii în programare
- elemente de claritate: indentare, spatiere, denumiri,...
- stil în programare

8. Metoda top-down si Rafinarea în pasi succesivi 
- Metoda top-down
- Metoda bottom-up
- Rafinarea în pasi succesivi

9. Recursivitate 
- Notiunea de  Recursivitate
- Recursivitate directa si indirecta
- Exemple 

10. Tipuri Abstracte de Date 
- specificarea unui TAD
- Unit Pascal
- Implementarea unui TAD în Pascal
- Folosirea unui TAD în programare

11. Metoda Divide et Impera 
- Prezentare generala
- Descrierea subalgoritmului
- Exemple

12. Metoda Backtracking 
- Prezentarea generala a metodei Backtracking
- Algoritm (subalgoritm) Backtracking
- Extinderi ale metodei Backtracking
- Exemple

13. Metoda Greedy 
- Prezentarea generala a metodei Greedy
- Algoritmul Greedy
- Exemple si contraexemple
- Euristica Greedy

14. Alte metode 
- Metoda programarii dinamice
- Metoda Branch and Bound
- Exemple
- Metode euristice

15. Complexitatea algoritmilor 
- definitia complexitatii
- 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 marime particulare
- compararea algoritmilor din punctul de vedere al eficientei
- complexitatea structurala
	
16. Algoritmi de cautare si complexitatea lor
- Specificarea problemei de cautare
- Metode de cautare: parcurgere secventiala, cautare binara
- Complexitatea algoritmilor de cautare

17. Algoritmi de sortare si complexitatea lor
- Specificarea problemei de sortare
- Metode de sortare
- Metoda  bulelor (BubbleSort)
- Sortare bazata pe selectarea minimului/maximului (SelectSort)
- Sortare prin inserare (InsertSort)
- Sortare rapida (QuickSort)
- Sortare prin interclasare (MergeSort)
- Complexitatea algoritmilor de sortare	

V. Bibliografie
1. Frentiu, M., H.F. Pop, Fundamentals of Programming, Cluj University Press, 2006, 220 pagini
2. M.Frentiu si altii, Manualul incepatorului in Programarea Pascal, Ed. Microinformatica, Cluj-Napoca, 1995, 252 pagini, ISBN 973-9215-04-1
3. M.Frentiu si altii, Programare Pascal. Programe ilustrative, probleme propuse, pentru elevi si studenti, Ed. Promedia, 1995, 229 pagini, ISBN 973-96862-1-4.
4. M.Frentiu, V.Prejmereanu, Algoritmica si programare, Lito. Univ. Babes-Bolyai, Cluj-Napoca, 1995, 261 pagini.
5. Frentiu, M., I.Lazar, S.Motogna si V.Prejmereanu, vol.I - Elaborarea algoritmilor, 1997, 188 pagini; vol.II - Programare Pascal, 392 pagini; Ed.Universitatii Babes-Bolyai, Cluj-Napoca.
6. M.Frentiu si B.Parv, Elaborarea programelor. Metode si tehnici moderne, Ed.Promedia, Cluj-Napoca, 1994, 217 pag.
7. Kasa Z., Ismerkedes az informatikaval, Editura Dacia, 1983.	
8. Kasa, Z., Algoritmusok tervezese, Ed. Studium, Cluj, 1994.
9. Knuth, D., Tratat de programarea calculatoarelor, Ed. Tehnica (Algoritmi fundamentali;  Cautare si sortare)
10. Livovschi, L., H.Georgescu, Sinteza si analiza algoritmilor, Editura St. si Enciclopedica, Bucuresti, 1986.	

VI. Tematica activităţilor didactice pe săptămâni
Programarea cursurilor
Sapt 1: Descrierea algoritmilor [1, cap. 1]
Sapt 2: Subalgoritmi (Pseudocod) [1, cap. 1]
Sapt 3:Limbajul Pascal [1, cap. 1]
Sapt 4: Ciclul de viata al programelor soft. Testare [1, cap. 3]
Sapt 5: Paradigme de programare. Programarea top-down [1, cap. 4]
Sapt 6: Programarea modulara. Tipuri abstracte de date [1, cap. 5]
Sapt 7: Tipuri abstracte de date  [1, cap. 5]
Sapt  8: Analiza algoritmilor [1, cap. 7]
Sapt  9: Recursivitate. Backtracking [1, cap. 6], [3, cap. 3, 4]
Sapt  10: Divide et impera. Metoda Greedy [1, cap. 6]
Sapt  11:. Programare dinamica. Branch and Bound [1, cap. 6]
Sapt  12: Algoritmi de cautare [1, cap. 7]
Sapt  13: Algoritmi de sortare [1, cap. 7]
Sapt 14: Corectitudinea algoritmilor [1, cap. 2]

Programarea seminariilor

Sapt 1: Subalgoritmi (Pseudocod)
Sapt 2: Subalgoritmi (Pseudocod)
Sapt 3: Programe Pascal 
Sapt 4: Programe Pascal cu subprograme
Sapt 5: Programe Pascal cu subprograme
Sapt 6: Proiectare Top-down 
Sapt 7: TAD
Sapt 8: TAD 
Sapt 9: Analiza algoritmilor
Sapt 10: Recursivitate. Complexitati.
Sapt 11: Backtracking. Complexitati.
Sapt 12: Divide et impera.. Complexitati
Sapt 13: Pregatire pentru examenul practic
Sapt 14: Pregatire pentru examenul scris

Planificarea laboratoarelor 
Numarul saptamanii indica saptamana la care studentilor li se da tema, predarea facandu-se o saptamana mai tarziu.
Sapt 1: Algoritmi
Sapt 2: Subalgoritmi (Pseudocod)
Sapt 3: Programe Pascal. Tablouri unidimensionale.
Sapt 4: Programe Pascal. Tablouri bidimensionale.
Sapt 5, 6: Programare top-down, rafinare in pasi succesivi
Sapt 7: Testare. Fisiere text.
Sapt 8, 9: TAD
Sapt 10: Backtracking
Sapt 11: Analiza algoritmilor
Sapt 12, 13: Predarea laboratoarelor restante
Sapt 14: Examinare practica	

VII. Metode didactice folosite

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 aritmetica a celor patru note mentionate mai sus, cu conditia ca toate notele sa fie cel putin 5, in caz contrar nu se promoveaza examenul.
Deci nota finala = 50%E + 15%P + 15%C + 10%L + 10%D.
WebPage: http://www.cs.ubbcluj.ro/~adriana/Teaching.html	

IX. Bibliografie suplimentară

	Decan,							Sef de catedra,

	Data,							Titular curs,
	1.10.2010	         			Lect. Dr.  GURAN Adriana Mihaela