| Structuri de date | Data structures |
trul |
|||||
(Mathematics-Computer Science) |
|||||
(Computer Science) |
| Cadre didactice indrumatoare | Teaching Staff in Charge |
| Prof. Dr. FRENŢIU Militon, mfrentiu@cs.ubbcluj.ro |
| Obiective | Aims |
|
- studierea conceptului de tip abstract de date si a celor mai frecvent utilizate tipuri abstracte de date, folosite în dezvoltarea aplicatiilor (stive, cozi, liste, multimi si tabele [map]);
- studierea structurilor de date cu care se pot implementa aceste tipuri abstracte de date (tablouri, liste înlantuite, arbori binari, tabele de dispersie); - formarea deprinderilor de a proiecta si realiza aplicatii pornind de la utilizarea tipurilor abstracte de date (de exemplu: se declara variabile de tip Multime care se prelucreaza cu ajutorul operatiilor definite pentru acest tip abstract de date, fara sa se tina cont de modul în care multimea se reprezinta);formarea deprinderilor de a prelucra date stocate în diverse structuri de date: tablouri, articole, string-uri, liste înlantuite, stive, cozi, tabele de dispersie, arbori si grafuri; - formarea deprinderilor de a compara costul alocarii statice si celei dinamice în cazul diverselor structuri de date; - formarea priceperilor si capacitatilor de a alege structura adecvata unei aplicatii; - cunoasterea unor structuri de date utile în diverse domenii ale matematicii si informaticii (de exemplu teoria grafurilor, baze de date, sisteme de operare etc.); - formarea abilitatilor în proiectarea si implementarea algoritmilor care prelucreaza aceste structuri de date; - consolidarea deprinderilor de a evalua complexitatea algoritmilor. |
- understanding the most used abstract data types: arrays, linked lists, binary trees, hash tabels, and developing the abilities to use them;
- developing the abilities for designing algorithms that use these structures; - learning to estimate the algorithms complexity. |
|
I. Structuri de date. Structuri statice, semistatice si dinamice (S1)
1.1. Tabloul (array) (S1) - Descriere, proprietati - Siruri, subsiruri, subsecvente, matrice - Operatii: inserare/stergere element, cautare secventiala si binara - Interclasare - Ordonare: prin selectie, prin inserare, bubblesort, mergesort, quicksort, heapsort, ordonare numerica, radixsort, bucketsort etc. 1.2. Lista înlantuita (linked list) (S2) - Descriere, proprietati - Liste simplu si dublu înlantuitealocate dinamic - Operatii: inserare/stergere element, cautare, traversare 1.3. Tabela de dispersie (hash-tabel) (S2) - Descriere, proprietati - Tabele de dispersie închise si deschise (closed- and open-bucket) - Operatii: cautare, inserare/stergere element 1.4. Arborele binar (binary tree) (S2) - Descriere, proprietati - Arbori binari si arbori binari de cautare - Operatii: cautare, inserare/stergere element, traversare II. Tipuri abstracte de date (TAD) (S3) - Tipuri de date: valori, operatii si reprezentarea datelor - Tipuri abstracte de date: numai valori si operatii - Cerinte, contract, implementare(implementari) - Proiectarea tipurilor abstracte de date - Tipul abstract de date string - [Tipuri abstracte de date în biblioteca de clase Java] - Aplicatii 2.1. TAD-ul stiva (stack) (S3) - Concepte legate de stiva - Aplicatii ale stivelor - Tipul abstract de date stiva: cerinte, contract - Implementari ale stivelor folosind tablouri si folosind liste înlantuite - [Stive în biblioteca de clase Java] - Aplicatii 2.2. TAD-ul coada (queue) (S3) - Concepte legate de coada - Aplicatii ale cozilor - Tipul abstract de date coada: cerinte, contract - Implementari ale cozilor folosind tablouri si folosind liste înlantuite - [Cozi în biblioteca de clase Java] - Aplicatii 2.3. TAD-ul lista (list) (S4) - Concepte legate de liste - Aplicatii ale listelor - Tipul abstract de date lista: cerinte, contract - Implementari ale listelor folosind tablouri si folosind liste înlantuite - [Liste în biblioteca de clase Java] - Aplicatii 2.4. TAD-ul multime (set) (S5) - Concepte legate de multimi - Aplicatii ale multimilor - Tipul abstract de date multime: cerinte, contract - Implementari ale multimilor folosind tablouri sau vectori booleeni (de biti), folosind liste înlantuite, folosind tabele de dispersie, folosind arbori binari - [Multimi în biblioteca de clase Java] - Aplicatii 2.5. TAD-ul dictionar (map) (S5) - Concepte legate de dictionare - Aplicatii ale dictionarelor - Tipul abstract de date dictionar: cerinte, contract - Implementari ale dictionarelor folosind tablouri booleene, folosind liste înlantuite sau arbori binari, folosind tabele de dispersie - [Dictionare în biblioteca de clase Java] - Aplicatii 2.6. TAD-ul coada de prioritati (priority queue) (S6) - Concepte legate de coada de prioritati - Aplicatii cu cozi de prioritati - Tipul abstract de date coada de prioritati: cerinte, contract - Implementari ale cozilor de prioritati folosind liste înlantuite - Structura de date heap - Implementari ale cozilor de prioritati folosind heap-uri - Aplicatii 2.7. TAD-ul arbore (tree) (S6) - Concepte legate de arbori - Aplicatii cu arbori - Tipul abstract de date arbore: cerinte, contract - Implementari înlantuite ai arborilor - Tipuri abstracte de date arbore cu diferite proprietati - Aplicatii 2.8. TAD-ul graf (graph) (S7) - Concepte legate de grafuri - Aplicatii cu grafuri - Tipul abstract de date arbore: cerinte, contract - Reprezentari statice (prin multimea muchiilor, prin multimea adiacentelor, cu matrice de adiacenta) - Traversari ale grafurilor - Sortarea topologica - Aplicatii III. Structuri de date specializate 3.1. Arbori binari de cautare echilibrati - Arbori AVL (S8) - Arbori rosu si negru (S9) - B-arbori (S10) - Arbori binari splay (S11) 3.2. Arbori oarecare. Aplicatii (S12) 3.3. Heap-uri (S13) - Leftist Heap - Heap-ul binomial - Heap-uri Fibonacci (facultativ) 3.4. Structuri de date spatiale (S14) - Quad-arbori - Oct-arbori |
|
1. N. Wirth, Algorithms + Data Structures = Programs, Prentice- Hall Inc., 1976
2. T. Cormen, C. Leiserson, R. Rivest - Introducere în algoritmi, Editura Computer Libris Agora, Cluj, 2000 3. E. Horowitz - Fundamentals of Data Structures in C++, Computer Science Press, 1995 |
| Evaluare | Assessment |
|
La seminar fiecare student va primi o listă de probleme şi aplicaţii care să fie realizate practic pe parcursul semestrului, activitate pentru care vor primi o notă. La sfarsitul anului activitatea se incheie cu un examen la care se va acorta o a doua notă. Nota finala va fi media aritmetica a celor doua note mentionate mai sus.
|
Each student will receive a list of problems that must be solved during the term. For this homework the student will receive a first grade. At the end of the term the student must take an exam for which he will receive a second grade. The final grade will be the arithmetic of these two grades.
|