Universitatea Babeş-Bolyai Cluj-Napoca
Facultatea de Matematică şi Informatică
Ciclul de studii: Licenţă
Domeniul: Calculatoare şi tehnologia informaţiei
Programul de studii: Ingineria informatiei - in limba romana
Limba de predare: Română

SYLLABUS

I. Date generale
Codul	Disciplina	
MID0040	Programarea calculatoarelor si limbaje de programare	

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	
VESCAN Andreea	Dr.	Lector.	Limbaje şi Metode de Programare	*			
CIOBAN Vasile	Dr.	Lector	Limbaje şi Metode de Programare		*	*	
GROSAN Crina	Dr.	Lector	Limbaje şi Metode de Programare			*	
MIHOC Tudor		Drd. 	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
- 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.
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
Tematica activitatilor pentru Curs

C1: Limbaje de descriere a algoritmilor (Scheme logice, Pseudocod, Pascal)
C2: Subalgoritmi (Pseudocod)
C3: Programe Pascal simple
C4: Faze in viata unui program (specificare, proiectare, codificare, testare, documentare, intretinere). Consecinte. Testarea programelor
C5: Corectitudinea algoritmilor (Floyd). Dezvoltarea corecta a algoritmilor din specificatii
C6: Metode generale de elaborare a algoritmilor: topdown, rafinare în pasi succesivi, programare modulara, programare structurata. Reguli importante în programare. Stil
C7+8: Tipuri Abstracte de date
C9: Complexitatea algoritmilor
C10: Recursivitate. Tehnici de programare: Backtracking.
C11+12: Metoda greedy + Programare dinamica+Divide&Impera+Branch&Bound+ Metode euristice
C13: Algoritmi de cautare si complexitatea lor
C14: Algoritmi de sortare si complexitatea lor (BubbleSort, SelectSort, InsertionSort, QuickSort, MergeSort.)

Tematica activitatilor pentru Seminar 

S1: Noţiunea de algoritm. Specificarea unei probleme. Limbajul Pseudocod.
S2: Limbajul Pseudocod. Tablouri unidimensionale.
S3: Limbajul Pseudocod. Tablouri bidimensionale.
S4: Limbajul Pascal. Subalgoritmi si functii. Tablouri unidimensionale. Numere mari.
S5: Limbajul Pascal. Subslgoritmi si functii. Functii transmise ca si parametru.
S6: Testare: White box si Black box.
S7: Lucrare de control; Tip Abstract de Date
S8: Tip abstract de Date; Complexitati.
S9: Backtraking
S10: Greedy;  Programare dinamica
S11: Divide et Impera
S12: Complexitati; Tip Abstract de Date cu elemente generice
S13: Pregatirea probei practice
S14:Pregatirea probei scrise

Tematica activitatilor pentru Laborator

L1:  Algoritmi simpli
L2:  Tablouri unidimensionale
L3: Tablouri bidimensionale
L4:  Rafinari in pasi succesivi, testare, fisiere
L5:  Top-down (1)
L6:  Top-down (2)
L7:  TAD (1)
L8: TAD (2) , Complexitati, recursivitate
L9: Backtraking
L10:  Greedy, Programare dinamica
L11: DivideEtImpera,Branch and Bound
L12: Predare laborator
L13: Predare laborator
L14: Examen practic	

VII. Metode didactice folosite
Expunerea: prelegeri introductive, prelegeri curente, explicaţia.
Conversaţia: dezbaterea, dialogul, conversaţii de fixare şi consolidare a cunoştinţelor.
Demonstraţia didactică: demonstraţia cu ajutorul execuţiei la tablă, demonstraţia cu ajutorul mijloacelor didactice electronice. 
Algoritmizarea: utilizarea diferiţilor algoritmi de învăţare: algoritmi de percepere, înţelegere, generalizare şi sistematizare a cunoştinţelor; algoritmi de recunoaştere; algoritmi de rezolvare; algoritmi de creaţie. 
Problematizarea: utilizarea întrebărilor-problemă, problemelor şi situaţiilor-problemă. 
Alte metode: studiul individual, exerciţiul. 

VIII. Evaluare
        La sfarsitul semestrului activitatea se incheie cu examen scris (nota E) si o proba practica la 
 Laborator in saptamana a 14-a de activitati didactice (nota P).
 Subiectele de examen vor consta din intrebari teoretice din toata materia predata si 
 probleme, dintre cele tratate la curs, seminar si laborator. 
Studentii vor da o lucrare de control la seminar (prezenta obligatorie). Activitatea de seminar se incheie cu o apreciere a activitatii din timpul anului (nota C, aceasta nota tinand seama de nota de la lucrare si de activitatea de la seminar a studentului).
 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 se calculeaza dupa formula de mai jos, 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.
          Mai multe informatii legate de modalitatea de evaluare a activitatilor asociate acestei discipline pot fi gasite la adresa:
    WebPage: http://www.cs.ubbcluj.ro/~avescan/
Sectiunea Teaching, disciplina Programarea calculatoarelor si limbaje de programare.
sau in reteaua locala: \\labor\Romana\An1\FP_2009_2010

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.	

	Decan,							Sef de catedra,
Prof. Dr. Leon TAMBULEA 			Prof. Dr. Bazil PARV

	Data,							Titular curs,
		1.10.2009						Lect. dr.  AndreeaVESCAN