Universitatea Babeş-Bolyai Cluj-Napoca
Facultatea de Matematică şi Informatică
Ciclul de studii: Licență

FISA DISCIPLINEI

Codul
Denumirea disciplinei
MIE0001 Structuri de date şi algoritmi
Specializarea
Semestrul
Ore: C+S+L
Categoria
Statutul
Matematică
2
2+1+0
fundamentala
obligatorie
Informatică
2
2+1+0
fundamentala
obligatorie
Matematică informatică
2
2+1+0
fundamentala
obligatorie
Ingineria informatiei
2
2+1+0
fundamentala
obligatorie
Titularii de disciplina
Conf. Dr. CZIBULA Gabriela,  gabiscs.ubbcluj.ro
Lect. Dr. CIOBAN Vasile,  vciobancs.ubbcluj.ro
Lect. Dr. TRÎMBITAS Gabriela,  gabitrcs.ubbcluj.ro
Lect. Dr. IONESCU Clara,  claracs.ubbcluj.ro
Conf. Dr. MOTOGNA Simona Claudia,  motognacs.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;
- 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.
Continutul
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
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.
Legaturi: Syllabus-urile tuturor disciplinelor
Versiunea in limba engleza a acestei discipline
Versiunea in format rtf a acestei discipline