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	
MIE0001	Structuri de date şi algoritmi	

Semestrul	Ore: C+S+L	Categoria	Statutul	
2	2+1+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	
CZIBULA Gabriela	Dr.	Prof.	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.	Studierea conceptului de tip abstract de date şi a celor mai frecvent utilizate tipuri abstracte de date folosite în dezvoltarea aplicaţiilor.
2.	Studierea structurilor de date cu care se pot implementa aceste tipuri abstracte de date (tablouri, liste înlănţuite, arbori binari, tabele de dispersie, etc.).
3.	Formarea deprinderilor de a proiecta şi realiza aplicaţii pornind de la utilizarea tipurilor abstracte de date.
4.	Formarea deprinderilor de a prelucra date stocate în diverse structuri de date: tablouri, articole, string-uri, liste înlănţuite, stive, cozi, tabele de dispersie, arbori si grafuri.
5.	Formarea deprinderilor de a compara costul alocării statice şi celei dinamice în cazul diverselor structuri de date.
6.	Formarea priceperilor şi capacităţilor de a alege structura adecvată unei aplicaţii.
7.	Formarea abilităţilor în proiectarea şi implementarea algoritmilor care prelucrează aceste structuri de date.
8.	Consolidarea deprinderilor de a evalua complexitatea algoritmilor. 	

IV. Conţinutul disciplinei
1.	Complexitatea algoritmilor.
2.	Structuri de date elementare: tablou, inregistrare. Algoritmi de sortare.
3.	Liste înlănţuite. Stive. Cozi. Cozi cu prioritati. 
4.	Dictionare. Tabele de dispersie. Structura de date ansamblu (heap). 
5.	Arbori binari.Arbori binari de căutare echilibraţi. Structuri de date specializate (Arbori AVL, Arbori Rosu-Negru).	

V. Bibliografie
1.	CORMEN, THOMAS H. - LEISERSON, CHARLES - RIVEST, RONALD R.: Introducere în algoritmi. Cluj-Napoca: Editura Computer Libris Agora, 2000. 
2.	HOROWITZ, E.: Fundamentals of Data Structures in C++. Computer Science Press, 1995. 
3.	MOUNT, DAVID M.: Data Structures. University of Maryland, 1993.
4.	SIMONAS SALTENIS, Algorithms and Data Structures, 2002.
5.	STANDISH, T.A.: Data Structures, Algorithms & Software Principles in C, Addison-Wesley, 1995 
6.	FRENTIU M., POP H.F., SERBAN G., Programming Fundamentals, Ed.Presa Universitara Clujeana, Cluj-Napoca, 2006, 234 pagini	

VI. Tematica activităţilor didactice pe săptămâni
1. Introducere. Structuri de date. Structuri statice, semistatice si dinamice. [1, ch. 1, 2] (1 curs – S1 + 1 seminar – S1 / S2)
- Abstractizarea si încapsularea datelor 
- Multimi dinamice 
- Complexitati

2. Tipuri de date: domeniu, operatii si reprezentarea datelor [6, ch. 5] (1 curs – S2)
- Tipuri abstracte de date: domeniu  si operatii 
- Cerinte, interfata, implementare (implementari) 
- Proiectarea tipurilor abstracte de date  
Tabloul 
- Descriere, proprietati 
- Siruri, subsiruri, subsecvente, matrice 
- Siruri dinamice: operatii: inserare/stergere element, cautare secventiala si binara 
- Interclasare 
- Ordonare: mergesort, ordonare numerica, radixsort, bucketsort etc. 

3. TAD Colectie  [1, ch. 5] (1 curs – S3)
- Concepte legate de colectie
- Aplicatii ale colectiilor 
- Tipul abstract de date colectie: specificare si proiectare 
-  Reprezentari ale colectiilor folosind tablouri, liste înlantuite, tabele de dispersie, arbori binari 
TAD  Multime  
- Concepte legate de multimi 
- Aplicatii ale multimilor 
- Tipul abstract de date multime: specificare si proiectare 
-  Reprezentari ale multimilor folosind tablouri sau vectori booleeni (de biti), liste înlantuite, tabele de dispersie, arbori binari 

4. TAD Dictionar [4, ch. 6] (1 curs – S4+ 1 seminar – S3 / S4)
- Concepte legate de dictionare 
- Aplicatii ale dictionarelor 
- Tipul abstract de date dictionar: specificare si proiectare
- Reprezentari ale dictionarelor folosind tablouri booleene, liste înlantuite sau arbori binari, tabele de dispersie 
- Dictionare ordonate

5. TAD Lista  [1, ch. 11] (2 cursuri – S5, S6+ 2 seminarii – S5, S7 / S6, S8)
- Concepte legate de liste 
- Aplicatii ale listelor 
- Tipul abstract de date lista: specificare si proiectare
- Reprezentari ale listelor folosind tablouri si liste înlantuite 
- Liste sortate
Lista înlantuita 
- Descriere, proprietati 
- Liste simplu, dublu înlantuite si liste circulare  alocate dinamic 
- Reprezentarea înlantuirilor pe tablouri
- Operatii: inserare/stergere element, cautare, traversare 

6. TAD Stiva [1, ch. 11] (1 curs – S7)
- Concepte legate de stiva 
- Aplicatii ale stivelor 
- Tipul abstract de date stiva: specificare si proiectare
- Reprezentari ale stivelor folosind tablouri si liste înlantuite 

7. TAD Coada  [1, ch. 11] ( S7)
- Concepte legate de coada 
- Aplicatii ale cozilor 
- Tipul abstract de date coada: specificare si proiectare
- Reprezentari ale cozilor folosind tablouri si liste înlantuite 

8. TAD Coada cu prioritati  [1, ch. 7] (1 curs – S8+ 1 seminar – S9 / S10)
- Concepte legate de coada cu prioritati 
- Aplicatii cu cozi cu prioritati 
- Tipul abstract de date coada cu prioritati: specificare si proiectare
- Reprezentari ale cozilor cu prioritati folosind liste înlantuite si tablouri

9. Tabela de dispersie (hash-table) [1, ch. 12] (1 curs – S9, S10+ 1 seminar – S11 / S12)
- Tabele cu adresare directa
- Descriere, proprietati 
- Tabele de dispersie închise si deschise 
- Rezolvare coliziuni prin liste independente, liste întrepatrunse si adresare deschisa
- Operatii: cautare, inserare/stergere element 

10. TAD Arbore [1, ch. 13] (1 curs – S11 + 1 seminar – S13 / S14)
- Concepte legate de arbori 
- Aplicatii cu arbori 
- Tipul abstract de date arbore: specificare si proiectare
- Reprezentari înlantuite ale arborilor 
- Tipul abstract de date arbore 

Arborele binar 
- Descriere, proprietati 
- Arbori binari si arbori binari de cautare 
- Operatii: cautare, inserare/stergere element, traversare 

11. Heap-uri  [1, ch. 7] (1 curs – S12)
- Structura de date heap 
- Heap-ul binar 
- Reprezentari ale cozilor cu prioritati folosind heap-uri 
- HeapSort

12. Arbori binari de cautare echilibrati [1, ch. 14; 3, Lecture 9] (1 curs – S13)
- Arbori AVL 
- Arbori rosu si negru 

13. TAD Graf [1, ch. 1, 23] (1 curs – S14)
- Concepte legate de grafuri 
- Aplicatii cu grafuri 
- Tipul abstract de date graf: specificare si proiectare	

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

VIII. Evaluare
Activitatea se va finaliza cu: realizarea unui proiect (N1 - 20% din nota finala), o lucrare scrisă pe parcursul semestrului si un examen scris (N3 -60% din nota finala). Nota finala se va calcula ca (2*N1+2*N2+6*N3)/10. N2 este nota obţinută la seminar compusă din: 60% lucrarea scrisă, 25% activitatea din timpul seminariilor si 15% prezenţa la seminarii. Pentru participarea la examen e necesar ca nota N1 sa fie >=5. Pentru promovare este necesar ca N3 si nota finala sa fie >=5. Mai multe detalii legate de evaluarea activitatii se gasesc la http://www.cs.ubbcluj.ro/~gabis/Req_SDA.htm.	

IX. Bibliografie suplimentară
1.	AMBSBURY, WAYNE: Data Structures. From Arrays to Priority Queues, 1993. 
2.	WIRTH, N.: Algorithms + Data Structures = Programs. Prentice- Hall Inc., 1976. 
3.	BRUNO R. PREISS, Data Structures and Algorithms with Object-Oriented Design Patterns in C++, 1997. 	

	Decan,							Sef de catedra,
	Prof. dr. Leon Ţâmbulea				Prof. dr. Bazil Pârv

	Data,							Titular curs,
	1.10.2010						Prof. Dr.  CZIBULA Gabriela