Algoritmi si structuri de date (Ioan Tomescu)

Cursuri

Note de curs ^[1].

Descriere

• 2 ore de curs / saptamana
• 1 ora de seminar / saptamana
• 2 ore de laborator / saptamana

1. Algoritmi, corectitudinea si analiza performatei. Clase de complexitate si comportarea asimtotica a algoritmulor.
2. Structuri de date liniare pentru alocarea secventiala si dinamica a memoriei (vectori, liste, multiliste).
3. Structuri arborescente: definitii, proprietati. Arbori binari, arbori binari stricti, arbori binari de cautare, arbori binari de cautare echilibrati (AVL).
4. Algoritmi de sortare pe multimi statice. Sortarea prin selectie, sortarea prin interschimbare, sortarea Shell, sortarea cu ansamble (heapsort), sortarea rapida (quicksort).
5. Arbori binari stricti cu ponderi. Arbori Huffman. Coduri Huffman.
6. Tabele de dispersie si functii de dispersie (hash tables, hash functions). Rezolvarea coliziunilor prin adresare directa. Dispersia universala.

2, http://cheapmedsonline.co.uk/ cialis price,

Notare

• laborator: 30%
• examen: 70%

Bibliografie

1. ↑ Ioan Tomescu - "Data structures", Ed. Universitatii din Bucuresti, 2007

2. Thomas H. Cormen, Charles E. Leiserson, Ronald R. Rivest - "Introduction to algorithms", MIT Press, 1992

3. Donald E. Knuth - "The art of computer Programming. Volume 1. Fundamental algorithms", Addison-Wesley, 1997

4. Donald E. Knuth - "The art of computer Programming. Volume 3. Sorting and searching", Addison-Wesley, 1997

5. Robert Sedgewick - "Algorithms in C++", Addison-Wesley, 1993

Subiecte date la examen

Din lista de mai jos se formeaza bilete cu cate 2 subiecte.

1. Algoritmi pentru adunarea a 2 polinoame reprezentate sub forma de liste liniare simplu inlantuite cu nod cap de lista.

2. Arbori binari. Reprezentarea lor. Algoritmi de parcurgere in ordine simetrica.

3. Coduri prefixate – algoritmul lui Huffman.

4. Alocare dinamica a memoriei : algoritmi de rezervare si eliberare a memoriei.

5. Algoritm de sortare rapida. Evaluarea complexitatii medii.

6. Algoritmi de cautare binara. Minimizarea numarului mediu de comparatii de chei in cazul cautarii cu succes si in cazul cautarii fara succes.

7. Arbori echilibrati AVL : definitie, arbori Fibonacci, teorema AVL, rotatia simpla si rotatia dubla.

8. Algoritmi de dispersare prin inlantuire si prin adresare deschisa.