Universitatea Babeş-Bolyai Cluj-Napoca
Facultatea de Matematică şi Informatică
Ciclul de studii: Licenţă
Domeniul: Matematică
Programul de studii: Matematică - 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	
CIOBAN 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
- 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. Conţinutul disciplinei
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 
      - sortare: 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. 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	

VI. Tematica activităţilor didactice pe săptămâni
1. Introducere. Structuri de date. Structuri statice, semistatice si dinamice. (1 curs - S1 + 1 seminar - S1 / S2)
2. Tipuri de date: domeniu, operatii si reprezentarea datelor (1 curs - S2)
    Tabloul 
     - sortare: mergesort, ordonare numerica, radixsort, bucketsort etc. 
3. TAD-ul colectie  (1 curs - S3)
    TAD-ul multime  
4. TAD-ul dictionar  (1 curs - S4+ 1 seminar - S3 / S4)
5. TAD-ul lista  (2 cursuri - S5, S6+ 2 seminarii - S5/S6; S7 / S8)
    Lista înlantuita 
6. TAD-ul stiva (1 curs - S7)
7. TAD-ul coada  (1 curs - S7)
8. TAD-ul coada cu prioritati   (1 curs - S8+ 1 seminar - S9 / S10)
9. Tabela de dispersie (hash-table)  (1 curs - S9, S10+ 1 seminar - S11 / S12)
10. TAD-ul arbore (1 curs - S11 + 1 seminar - S13 / S14)
     Arborele binar 
11. Heap-uri  (1 curs - S12)
12. Arbori binari de cautare echilibrati (1 curs - S13)
       - arbori AVL - arbori rosu si negru 
13. TAD-ul graf [1, ch. 1, 23] (1 curs - S14)	

VII. Metode didactice folosite
Expunerea: descrierea, explicaţia, prelegeri curente, prelegeri de sinteză. 
Conversaţia: conversaţia euristică, dezbaterea, conversaţii introductive, conversaţii de sistematizare şi sinteză, conversaţii de aplicare 
Modelarea: utilizarea modelelor materiale, modelelor iconice, modelelor ideale, modelelor cibernetice. 
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 de caz; cooperarea, simularea, brainstorming-ul, studiul individual, exerciţiul. 	

VIII. 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.
WebPage: http://www.cs.ubbcluj.ro/~vcioban	

IX. Bibliografie suplimentară
1. LUCANU Dorel, Craus Mitică: Proiectarea Algoritmilor,Editura Polirom, 2008	

	Decan,							Sef de catedra,

	Data,							Titular curs,
            6.03.2009						Lect. Dr.  CIOBAN Vasile