Universitatea Babeş-Bolyai Cluj-Napoca
Facultatea de Matematică şi Informatică
Ciclul de studii: Licenţă
Domeniul: Matematică
Programul de studii: Matematică informatică -linia de studiu germană
Limba de predare: Germană

SYLLABUS

I. Allgemeine Daten
Kennnummer	Disziplin	
MIE0001	Structuri de date şi algoritmi	

Semester	Stunden: C+S+L	Kategorie	Status	
2	2+1+0	fundamentala	obligatorie	

II. Lehrkräfte der Universität
Name und	Wiss.	Position	Lehrstuhl	Lehrveranstaltung	
Vorname	Grad			V	S	L	
TRÎMBITAS Gabriela	Dr. 	Lect.	Sisteme Informatice	*			

Assozierte Lehrkräfte
Name und	Wiss.	Institution	Position	Lehrveranstaltung	
Vorname	 			V	S	L	

III. Ziele der Disziplin
- 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; 
- 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; 
- formarea abilităţilor în proiectarea şi implementarea algoritmilor care prelucrează aceste structuri de date; 
- consolidarea deprinderilor de a evalua complexitatea algoritmilor. 
- 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; 
- 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; 
- formarea abilităţilor în proiectarea şi implementarea algoritmilor care prelucrează aceste structuri de date; 
- consolidarea deprinderilor de a evalua complexitatea algoritmilor. 

IV. Inhalte der Disziplin
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-ul 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-ul 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-ul 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-ul 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-ul 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-ul 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-ul 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-ul 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-ul graf [1, ch. 1, 23] (1 curs - S14)
- Concepte legate de grafuri 
- Tipul abstract de date graf
- Aplicatii

V. Pflichtliteratur
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

	

VI. Thematik der wöchentlichen Lehrveranstaltungen

VII. Didaktische Methoden

VIII. Beurteilung der studentischen Leistungen
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.	

IX. Zusatzliteratur

	Dekan,						Lehrstuhlleiter,

	Datum,						Verantwortliche Lehrkraft,
								Lect. Dr.  TRÎMBITAS Gabriela