Universitatea Babeş-Bolyai Cluj-Napoca
Facultatea de Matematică şi Informatică
Ciclul de studii: Licenţă
Domeniul: Matematică
Programul de studii: Matematică 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	
PREJMEREAN Vasile	Dr.	Lect.	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 si descrierea lor - notiunea de algoritm, variabila, tip, specificare, limbajul Pseudocod (Structura liniara, alternativa, repetitiva).
 2. Subalgoritmi (Pseudocod) - notiunea de subalgoritm, parametri formali, definirea unui subalgoritm (functie si procedura), apelul unui subalgoritm, importanta subalgoritmilor în programare.
 3. Codificarea algoritmilor - elemente de baza ale limbajului Pascal, declaratii şi instructiuni, structura unui program Pascal, codificare.
 4. Faze in viata unui program – faze în realizarea unui program: specificare,  proiectare,  codificare,  testare,  documentare, verificare;  întretinerea 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;
 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 Bottom-Up şi Rafinarea în pasi succesivi.
 9. Recursivitate - notiunea de  recursivitate, recursivitate directa si indirecta.
10. Tipuri Abstracte de Date -  specificarea unui TAD, Unit Pascal, implementarea unui TAD în Pascal, folosirea unui TAD în programare.
11. Metoda Greedy - prezentarea generala a metodei greedy, algoritmi Greedy, exemple si contraexemple.
12. Metoda Divide et Impera - prezentare generala, descrierea subalgoritmului, exemple.
13. Metoda Backtracking - prezentarea generala a metodei Backtracking, algoritm (subalgoritm) Backtracking, extinderi ale metodei Backtracking, exemple.
14. Metoda programarii dinamice- prezentare generală a metodei, Principiul Optimalitaţii, strategii, exemple.
15. Metoda Branch and Bound – Descrierea generală a metodei, algoritm general, exemple.
16. Metode euristice – strategia Greedy.
17. 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.
18. Algoritmi de cautare si complexitatea lor - specificarea problemei de cautare, metode de cautare (parcurgere secventiala, cautare binara), complexitatea algoritmilor de cautare.
19. 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 – InsertionSort, 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.
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.
11. Vaduva, I., Baltac, V., V.Florescu, I.Floricica, M.Jitaru, Ingineria programarii, Editura Academiei RSR, Bucuresti, 1985.

VI. Tematica activităţilor didactice pe săptămâni
 1. Algoritmi si descrierea lor 
 2. Subalgoritmi (Pseudocod) 
 3. Codificarea algoritmilor 
 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 Bottom-Up şi Rafinarea în pasi succesivi;  Recursivitate.
 9. Tipuri Abstracte de Date.
10. Metoda Greedy, Metoda Divide et Impera 
11. Metoda Backtracking, Metoda programarii dinamice
12. Metoda Branch and Bound, Metode euristice
13. Complexitatea algoritmilor, Algoritmi de cautare si complexitatea lor.
14. Algoritmi de sortare si complexitatea lor: BubbleSort, SelectSort, InsertionSort, QuickSort, MergeSort.	

VII. Metode didactice folosite
Expunerea, conversaţia, demonstraţia didactică, modelarea, algoritmizarea, problematizarea, descoperirea, alte metode.	

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.	

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
3. M.Frentiu, V.Prejmereanu, Algoritmica si programare, Lito. Univ. Babes-Bolyai, Cluj-Napoca, 1995, 261 pagini.	

	Data,							Titular curs,
	01.12.2007					Lect. Dr. PREJMEREAN Vasile