| Structuri de date |
trul |
|||||
| Cadre didactice indrumatoare |
| Lect. SERBAN Gabriela, gabis@cs.ubbcluj.ro Conf. Dr. POP Horia Florin, hfpop@cs.ubbcluj.ro Lect. IONESCU Clara, clara@cs.ubbcluj.ro |
| Obiective |
|
- 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. |
| Continut |
|
I. Structuri de date. Structuri statice, semistatice si dinamice (S1)
1.1 Notiuni introductive - Algoritmi. Complexitate (sume,recurente) - Abstractizarea si incapsularea datelor - Multimi dinamice - Tehnici de analiza a algoritmilor 1.2. Tabloul (array) - 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.3. Lista înlantuita (linked list) - Descriere, proprietati - Liste simplu si dublu înlantuitealocate dinamic - Operatii: inserare/stergere element, cautare, traversare 1.4. Tabela de dispersie (hash-tabel) - Descriere, proprietati - Tabele de dispersie închise si deschise (closed- and open-bucket) - Operatii: cautare, inserare/stergere element 1.5. Arborele binar (binary tree) - Descriere, proprietati - Arbori binari si arbori binari de cautare - Operatii: cautare, inserare/stergere element, traversare II. Tipuri abstracte de date (TAD) - 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 - Aplicatii 2.1. TAD-ul lista (list) - Concepte legate de liste - Aplicatii ale listelor - Tipul abstract de date lista: cerinte, contract - Implementari ale listelor folosind tablouri si folosind liste înlantuite - Aplicatii 2.2. TAD-ul stiva (stack) - Concepte legate de stiva - Aplicatii ale stivelor - Tipul abstract de date stiva: cerinte, contract - Implementari ale stivelor folosind tablouri si folosind liste înlantuite - Aplicatii 2.3. TAD-ul coada (queue) - Concepte legate de coada - Aplicatii ale cozilor - Tipul abstract de date coada: cerinte, contract - Implementari ale cozilor folosind tablouri si folosind liste înlantuite - Aplicatii 2.4. TAD-ul multime (set) - 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 - Aplicatii 2.5. TAD-ul dictionar (map) - 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 - Aplicatii 2.6. TAD-ul coada de prioritati (priority queue) - 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) - 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) - 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 - Arbori rosu si negru - B-arbori - Arbori binari splay 3.2. Arbori oarecare. Aplicatii 3.3. Heap-uri - Leftist Heap - Heap-ul binomial - Heap-uri Fibonacci (facultativ) 3.4. Structuri de date spatiale - Quad-arbori - Oct-arbori |
| Bibliografie |
|
1. T. Cormen, C. Leiserson, R. Rivest - Introducere în algoritmi, Editura Computer Libris Agora, Cluj, 2000
2. E. Horowitz - Fundamentals of Data Structures in C++, Computer Science Press, 1995 3. David M. Mount - Data Structures, University of Maryland, 1993 4. wayne Ambsbury - Data Structures - From Arrays to Priority Queues, 1993 3. N. Wirth, Algorithms + Data Structures = Programs, Prentice- Hall Inc., 1976 |
| Evaluare |
|
Activitatea se va finaliza cu: realizarea unui proiect (N1 - 30% din nota finala) si un examen scris (N2 - 70% din nota finala). Nota finala se va calcula ca (3*N1+7*N2)/10. Pentru promovare este necesar ca ambele note sa fie >=5. |