Disciplina: Structuri de date si algoritmi	Cod: MIE0001	

Semestrul	Ore: C+S+L	Tipul	Specializarea	
2	2+1+0	obligatorie	Matematica	
2	2+1+0	obligatorie	Informatică	
2	2+1+0	obligatorie	Matematică informatică	
2	2+1+0	obligatorie	Matematici aplicate	

Cadre didactice indrumatoare	Conf. Dr. SERBAN Gabriela, gabis@cs.ubbcluj.ro
Conf. Dr. NICULESCU Virginia, vniculescu@cs.ubbcluj.ro
Lect. Dr. IONESCU Clara, clara@cs.ubbcluj.ro
Lect. Dr. CIOBAN Vasile, vcioban@cs.ubbcluj.ro
Asist. MIHIS Andreea Diana, mihis@cs.ubbcluj.ro	
Obiective	- studierea conceptului de tip abstract de date şi a celor mai frecvent utilizate tipuri  abstracte de date folosite în dezvoltarea aplicaţiilor; 
- 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.); 
- formarea deprinderilor de a proiecta şi realiza aplicaţii pornind de la utilizarea tipurilor abstracte de date (de exemplu: se declară variabila de tip Mulţime care se prelucrează cu ajutorul operaţiilor definite pentru acest tip abstract de date, fără să se ţină cont de modul în care mulţimea se reprezintă); 
- 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; 
- formarea deprinderilor de a compara costul alocării statice şi celei dinamice în cazul diverselor structuri de date; 
- formarea priceperilor şi capacităţilor de a alege structura adecvată unei aplicaţii; 
- cunoaşterea unor structuri de date utile în diverse domenii ale matematicii şi informaticii (de exemplu teoria grafurilor, baze de date, sisteme de operare etc.); 
- formarea abilităţilor în proiectarea şi implementarea algoritmilor care prelucrează aceste structuri de date; 
- consolidarea deprinderilor de a evalua complexitatea algoritmilor.
	
Continut	1. Introducere. Structuri de date. Structuri statice, semistatice şi dinamice. (1 curs + 1 seminar)
- Abstractizarea şi încapsularea datelor 
- Mulţimi dinamice 
- Complexitati

2. Tipuri de date: domeniu, operaţii şi reprezentarea datelor (1 curs)
- Tipuri abstracte de date: domeniu  şi operaţii 
- Cerinţe, interfaţă, implementare (implementări) 
- Proiectarea tipurilor abstracte de date  

Tabloul 
- Descriere, proprietăţi 
- Şiruri, subşiruri, subsecvenţe, matrice 
- Şiruri dinamice: operaţii: inserare/ştergere element, căutare secvenţială şi binară 
- Interclasare 
- Ordonare: mergesort, ordonare numerică, radixsort, bucketsort etc. 

3. TAD-ul mulţime  (1 curs)
- Concepte legate de mulţimi 
- Aplicaţii ale mulţimilor 
- Tipul abstract de date mulţime: specificare şi proiectare 
-  Reprezentări ale mulţimilor folosind tablouri sau vectori booleeni (de biţi), folosind liste înlănţuite, folosind tabele de dispersie, folosind arbori binari 

4. TAD-ul dicţionar (1 curs + 1 seminar)
- Concepte legate de dicţionare 
- Aplicaţii ale dicţionarelor 
- Tipul abstract de date dicţionar: specificare şi proiectare
- Reprezentări ale dicţionarelor folosind tablouri booleene, folosind liste înlănţuite sau arbori binari, folosind tabele de dispersie 
- Dicţionare ordonate (sorted map)

5. TAD-ul listă  (2 cursuri + 2 seminarii)
- Concepte legate de liste 
- Aplicaţii ale listelor 
- Tipul abstract de date listă: specificare şi proiectare
- Reprezentări ale listelor folosind tablouri şi folosind liste înlănţuite 
- Liste sortate

Lista înlănţuită 
- Descriere, proprietăţi 
- Liste simplu, dublu înlănţuite şi liste circulare  alocate dinamic 
- Reprezentarea înlănţuirilor pe tablouri
- Operaţii: inserare/ştergere element, căutare, traversare 

6. TAD-ul stivă (1 curs)
- Concepte legate de stivă 
- Aplicaţii ale stivelor 
- Tipul abstract de date stivă: specificare şi proiectare
- Reprezentări ale stivelor folosind tablouri şi folosind liste înlănţuite 

7. TAD-ul coadă  (1 curs)
- Concepte legate de coadă 
- Aplicaţii ale cozilor 
- Tipul abstract de date coadă: specificare şi proiectare
- Reprezentări ale cozilor folosind tablouri şi folosind liste înlănţuite 

8. TAD-ul coadă cu priorităţi  (1 curs + 1 seminar)
- Concepte legate de coada cu priorităţi 
- Aplicaţii cu cozi cu priorităţi 
- Tipul abstract de date coadă cu priorităţi: specificare şi proiectare
- Reprezentări ale cozilor cu priorităţi folosind liste înlănţuite şi tablouri

9. Tabela de dispersie (hash-table) (1 curs + 1 seminar)
- Tabele cu adresare directă
- Descriere, proprietăţi 
- Tabele de dispersie închise şi deschise 
- Rezolvare coliziuni prin liste independente, întrepătrunse şi adresare deschisă
- Operaţii: căutare, inserare/ştergere element 

10. TAD-ul arbore (1 curs + 1 seminar)
- Concepte legate de arbori 
- Aplicaţii cu arbori 
- Tipul abstract de date arbore: specificare şi proiectare
- Reprezentări înlănţuite ale arborilor 
- Tipuri abstracte de date arbore cu diferite proprietăţi 

Arborele binar 
- Descriere, proprietăţi 
- Arbori binari şi arbori binari de căutare 
- Operaţii: căutare, inserare/ştergere element, traversare 

11. Heap-uri  (1 curs)
- Structura de date heap 
- Heap-ul binar 
- Reprezentări ale cozilor cu priorităţi folosind heap-uri 
- HeapSort

12. Arbori binari de căutare echilibraţi (1 curs)
- Arbori AVL 
- Arbori roşu şi negru 

13. TAD-ul graf (1 curs)
- Concepte legate de grafuri 
- Aplicaţii cu grafuri 
- Tipul abstract de date graf: specificare şi proiectare
	
Bibliografie selectiva	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. AMBSBURY, WAYNE: Data Structures. From Arrays to Priority Queues, 1993. 
5. WIRTH, N.: Algorithms + Data Structures = Programs. Prentice- Hall Inc., 1976.
6. STANDISH, T.A.: Data Structures, Algorithms & Softwae Principles in C, Addison-Wesley, 1995
7. SEDGEWIK: Algorithmen
8. Frentiu, M., Pop, H.F., Serban, G.: Programming Fundamentals, Ed. Presa Universitara Clujeana, Cluj-Napoca, 2006

Evaluare	Activitatea se va finaliza cu: realizarea unui proiect (N1 - 20% din nota finala), o lucrare scris pe parcursul semestrului (N2 - 20% din nota finala) si un examen scris (N3 -60% din nota finala). Nota finala se va calcula ca (2*N1+2*N2+6*N3)/10. Pentru participarea la examen e necesar ca nota N1 sa fie >=5. Pentru promovare este necesar ca N3 si nota finala sa fie >=5