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