Universitatea "Babeş-Bolyai" din Cluj-Napoca

Facultatea de Matematică şi Informatică
FISA DISCIPLINEI

Structuri de date Data structures
Cod
Semes-
trul
Ore: C+S+L
Credite
Tipul
Sectia
MI011
2
2+1+0
5
obligatorie
Matematică-Informatică
(Mathematics-Computer Science)
MI011
2
2+1+0
5
obligatorie
Informatică
(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.

Continut
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
Bibliografie
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.