Universitatea "Babes-Bolyai" Cluj-Napoca
Facultatea de Matematica si Informatica
FISA DISCIPLINEI
| Structuri de date si algoritmi |
trul |
|||||
| Cadre didactice indrumatoare |
|
| 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. - Abstractizarea şi încapsularea datelor - Mulţimi dinamice 2. Tipuri de date: domeniu, operaţii şi reprezentarea datelor - 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 - 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 - 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ă - 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ă - 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ă - 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 - 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) - 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 - 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 - 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 - Arbori AVL - Arbori roşu şi negru 13. TAD-ul graf - Concepte legate de grafuri - Aplicaţii cu grafuri - Tipul abstract de date graf: specificare şi proiectare |
| Bibliografie |
|
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 |
| 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. |