Structuri de Date i Algoritmi INFORMATIC romn, sem. 2

Cadre didactice ndrumtoare Prof. dr. CZIBULA Gabriela Drd. MARIAN Zsuzsanna I. Obiective

Studierea conceptului de tip abstract de date i a celor mai frecvent utilizate tipuri abstracte de date folosite n dezvoltarea aplicaiilor.

Studierea structurilor de date cu care se pot implementa aceste tipuri abstracte de date (tablouri, liste nlnuite, arbori binari, tabele de dispersie, etc.) i analiza complexitii operaiilor.

Formarea deprinderilor de a proiecta i realiza aplicaii pornind de la utilizarea tipurilor abstracte de date.

Formarea deprinderilor de a prelucra date stocate n diverse structuri de date: tablouri, articole, liste nlnuite, stive, cozi, tabele de dispersie, arbori.

Formarea priceperilor i capacitilor de a alege tipul abstract de date i structura de date adecvat unei aplicaii.

Formarea abilitilor n proiectarea i implementarea algoritmilor care prelucreaz structurile de date.

II. Cunotine preliminare

Proiectare algoritmi simpli Specificaii Complexiti Stil de programare

III. Bibliografie 1. NICULESCU V., CZIBULA G., Structuri fundamentale de date. O perspectiva orientat

obiect. Editura Casa Cartii de Stiinta, Cluj-Napoca,2011 2. CORMEN, THOMAS H. - LEISERSON, CHARLES - RIVEST, RONALD R.: Introducere n

algoritmi. Cluj-Napoca: Editura Computer Libris Agora, 2000. 3. HOROWITZ, E.: Fundamentals of Data Structures in C++. Computer Science Press, 1995. 4. MOUNT, DAVID M.: Data Structures. University of Maryland, 1993. 5. SIMONAS SALTENIS, Algorithms and Data Structures, 2002.

6. STANDISH, T.A.: Data Structures, Algorithms & Software Principles in C, Addison-Wesley, 1995

7. FRENTIU M., POP H.F., SERBAN G., Programming Fundamentals, Ed.Presa Universitara Clujeana, Cluj-Napoca, 2006

IV. Coninut 1. Introducere. Tipuri abstracte de date. Structuri de date. Containere i iteratori. (Curs 1-2) 2. Tablouri. Vectori dinamici (Curs 3) 3. Colectii, Multimi, Dictionare, Dictionare ordonate (Curs 4) 4. Liste, liste sortate, liste circulare. Lista nlanuit (Curs 5-6) 5. Stive, cozi, cozi cu prioriti. (Curs 7) 6. Tabele cu adresare directa, tabele de dispersie. Rezolvare coliziuni prin liste independente, liste

ntrepatrunse si adresare deschis (Curs 8-10) 7. Arbori. Arbori binari. Parcurgeri iterative ale arborilor. Ansamblu (heap). HeapSort. (Curs 11-

12) 8. Arbori binari de cautare. Arbori binari de cautare echilibrati (Arbori AVL). Rotaii pentru

echilibrare. (Curs 13-14) V. Acordarea notei finale NP Proiect 20% NS Nota de seminar 20% NE Examenul scris 60% -------------------------------------------- Total 100% Participarea la examenul scris este conditionata de nota NP, care trebuie sa fie 5. Pentru promovare, nota NE si nota finala trebuie sa fie 5. VI. Predarea i evaluarea proiectului Proiectul va consta n realizarea unei aplicaii care va fi rezolvat folosind un anumit container

de date/TAD i o anumit structur de date pentru implementarea acestuia. Stabilirea temelor se va face la seminarul 4. Temele de proiect se gasesc in fisierul TemeProiect.pdf.

Proiectul va fi predat la ULTIMUL seminar, exceptnd proiectele cu Arbori care vor fi predate n ziua examenului scris.

Predarea proiectului const n: documentaia sa realizat conform cerinelor de mai jos (scris sau listat) + CD care s conin aplicaia. CD-ul va conine n directoare separate: sursele, executabilele, detalii de rulare. Pentru predarea proiectului este OBLIGATORIU ca aplicaia realizat s fie funcional. Limbajul ales pentru implementarea aplicaiei este LA ALEGERE.

n cazul n care apar probleme la evaluarea proiectului (nelmuriri, neclariti), dup examenul scris vei fi solicitai sa v PREZENTAI proiectul i s dai explicaii legate de realizarea/implementarea sa.

Proiecte IDENTICE/COPIATE se noteaz cu 1 (UNU). Notarea proiectului se va face astfel: 1p Oficiu 1p Enunul problemei (aplicaia s fie aleas n aa fel nct s se dovedeasc utilitatea folosirii containerului i a structurii de date) 1.5p TAD - specificare i interfa (independente de reprezentare)

OBLIGATORIU iterator pentru containerele care pot fi iterate. 2.75p - stabilirea reprezentrii TAD-ului i scrierea n PSEUDOCOD a operaiilor din interfa conform reprezentarii alese - scrierea complexitii operaiilor (pentru una din operaii - la alegere se va face deducia complet a complexitii) 2.75p - diagrama de apeluri pentru aplicaie

- proiectarea aplicaiei (scrierea n PSEUDOCOD a subalgoritmilor din aplicaie independent de reprezentarea TAD (folosind doar operaiile din interfaa)

- complexitatea operaiilor din aplicaie 1p Stil VII. Nota de seminar Nota de seminar se va calcula astfel:

60% lucrarea de control 25% activitatea din timpul seminariilor 15% prezena la seminarii (o absen nemotivat este permis, restul se depuncteaz).

Lucrarea de control se va da n cadrul seminarului 4 i va dura 50 minute. VIII. Participarea n sesiunea de restane n cazul participrii n sesiunea de restane, calculul notei se va face conform punctului V. Activitatea de seminar (inclusiv lucrarea de control) i proiectul se consider activiti din timpul semestrului i NU pot fi refcute.