STRUCTURI DE DATE SI ALGORITMI

 

1. Titularul disciplinei: Prof. dr. ing. Florina Ungureanu, conf. dr. ing. Vasile Manta

2. Tipul si codul disciplinei: AC204

3. Structura cursului:

-         Numar credite: 5

-         Numar ore: cursul = 2 ore/sapt., laboratorul = 2 ore/sapt.

-         Forma examinare: Examen

 

4. Obiectivele disciplinei, concordanţa între obiectivele disciplinei şi planul de învăţământ:

-         prezentarea structurilor de date fundamentale şi algoritmii de bază asociaţi acestor structuri

-         disciplina utilizează noţiunile predate la disciplinele de Introducere în ştiinţa sistemelor şi a calculatoarelor, Programarea calculatoarelor, Analiză matematică.

-         noţiunile predate la disciplina Structuri de date şi algoritmi sunt folosite la disciplinele de specialitate Proiectarea algoritmilor, Tehnici de programare, Baze de date,  etc.

 

5. Proceduri folosite la predarea disciplinei

-         prelegerea: expunere la tablă, proiecţie pentru unele aplicaţii;

-         recomandarea, pentru studiul individual, a unor paragrafe din bibliografia indicată, în vederea aprofundării sau extinderii cunoştinţelor căpătate la curs;

-         prezentarea unor exemple şi a unor probleme aplicative în cadrul cursului.

Cerinţe la examinare: nota finală se stabileşte astfel: - 70% nota de la examen şi 30% nota de la laborator. Examenul constă dintr-o probă practică cu ponderea de 70% din notă şi o probă scrisă (test grilă) cu ponderea 30% din nota de examen.

 

6. Conţinutul disciplinei:

 

            a) Curs:

1.

Elemente de teoria analizei algoritmilor

-         Aspecte generale privind analiza şi complexitatea unui algoritm;

-         Evaluarea complexităţii. Exemple de analiză a unor algoritmi. Clase de complexitate.

2.

Structuri de date. Aspecte generale

-         Tipuri şi structuri de date;

-         Organizarea structurilor de date.

3.

Tipul abstract de date listă

-         Operaţii caracteristice;

-         Implementări de liste liniare simplu şi dublu înlănţuite. Creare, parcurgere,  inserare, ştergere, etc.;

-         Implementări de liste circulare simplu şi dublu înlănţuite. Creare, parcurgere, inserare, ştergere, etc.;

-         Implementări ce folosesc funcţii recursive

-         Implementarea listelor generice;

-         Exemple de utilizare a listelor.

4.

Tipurile abstracte de date stivă şi coadă.

-         Stive. Operaţii caracteristice. Implementări de stive: ordonate, înlănţuite;

-         Aplicaţie. Evaluarea expresiilor aritmetice;

-         Cozi. Operaţii caracteristice. Implementări de cozi: ordonate, înlănţuite;

-         Utilizarea stivei şi cozii în aplicaţii generice C++.

5.

Liste generalizate

-         Reprezentarea listelor generalizate;

-         Operaţii de bază.

6.

 Arbori

-         Noţiuni generale;

-         Metode de reprezentare a arborilor: prin tablouri, prin liste generalizate, reprezentările tată-fii, fiu-tată, fiu-frate;

-         Aplicaţie. Evaluarea expresiilor aritmetice

-         Arbori binari oarecare. Parcurgerea arborilor: preordine, inordine, postordine, lăţime. Arbori binari înşiruiţi;

-         Arbori binari de căutare (BST). Operaţii caracteristice. Complexitatea operaţiilor pe arbori BST;

-         Arbori binari de căutare AVL – echilibraţi. Metode de echilibrare;

-         Arbori parţial ordonaţi (Arbori heap). Operaţii caracteristice. Aplicaţii ale arborilor heap. Analiza complexităţii operaţiilor pe arbori heap;

-         B-arbori.

7.

Grafuri

-         Aspecte generale;

-         Modalităţi de reprezentare a grafurilor;

-         Modalităţi de parcurgere a grafurilor: în adâncime, în lăţime.

 

            b) Lista lucrărilor de laborator:

 

1.

Recapitularea unor noţiuni ale limbajului C: pointeri şi structuri

2.

Complexitatea algoritmilor. Algoritmi recursivi

3.

Tablouri

4.

Liste liniare simplu înlănţuite

5.

Liste liniare dublu înlănţuite. Liste circulare

6.

Stive

7.

Cozi

8.

Liste generalizate

9.

Arbori. Reprezentarea arborilor de grad oarecare in limbajul C

10.

Arbori binari. Reprezentări şi parcurgeri

11.

Arbori binari de căutare

12.

Arbori binari de căutare echilibraţi (AVL)

13.

Arbori heap. Algoritmul HeapSort

14.

Grafuri. Reprezentare, DFS, BFS

 

7. Baza materială:

-         4  laboratoare, fiecare laborator fiind dotat cu 8 calculatoare (Pentium III)

  conectate în reţea

 

8. Bibliografie recomandată:

1.      M. Craus, C. Bârsan, Structuri de date şi algoritmi, Ed. „Gh. Asachi” Iaşo, 2002

2.      M. D. Zaharia, Structuri de date şi algoritmi. Exemple în limbajele C şi C++, Ed.

3.      Albastră, Cluj-Napoca, 2002

4.      T. Cormen, C. Leiserson, R. Rivest, Introducere în algoritmi, Ed. Computer Libris Agora,     Cluj-Napoca, 2000

5.      M. A. Weiss, Data Structures and Algorithm Analzsis in C, The Benjamin/Cummings  Publishing Companz, Inc., 1993

6.      E. Horowitz, S. Sahni, S. Anderson-Freed - Fundamental of Data Structures in C,

7.      Computer Science Press, 1993

8.      S. Sahni - Data Structures and Algorithms in C++, WCB McGraw-Hill, 1998

9.      J. G. Brookshear, Introducere în informatică, Ed. Teora, Bucureşti, 1998

10.  Schildt, C++ manual complet, Editura Teora, 2002, Bucureşti

11.  L. Negrescu, Limbajele C şi C++, vol. 1, 2 Ed. Albastră, Cluj-Napoca, 2000