|
Cod:
Titular curs:
Lector dr. P. Bazavan
Forma de invatamant
: Informatica (3 ani)
Ciclul :
I
Semestrul 1, Curs : 2h, Seminar : 2h
Nr. credite:
10
Profil :
Informatica
Specializare :
Informatica
Tip disciplina :
obligatorie
Categoria formativa
: de formare
Obiective:
- Insusirea principalelor concepte din teoria
algoritmilor : metode de elaborare a algoritmilor, structuri de date,
tehnici de sortare si cautare.
Continutul
cursului:
· Notiuni generale legate de algoritmi
si complexitate
- Notiunea de algoritm. Limbajul algoritmic.
- Masini Turing.
- Complexitatea algoritmilor. Tipuri de probleme si
complexitatea lor.
- Recursivitate. Tipuri de recursie. Ecuatii
recurente
· Metode de elaborare a algoritmilor
- Metoda Backtracking. Exemple.
- Metoda Gready. Exemple.
- Metoda "Divide et Impera". Exemple.
- Metoda programarii dinamice. Exemple
· Structuri de date
- Multimi. Reprezentare. Operatii.
- Liste liniare statice. Stive, cozi. Operatii.
- Liste liniare inlantuite. Implementare. Operatii.
- Tabele de dispersie si functii de dispersie.
Rezolvarea coliziunilor. Implementare.
- Grafuri neorientate. Reprezentare si parcurgere.
- Grafuri orientate. Reprezentare si parcurgere.
- Arbori oarecare. Parcurgere.
- Arbori binari. Reprezentare si parcurgere.
- Structuri heap si aplicatii. Algoritmul HeapSort.
- Structuri de date pe multimi disjuncte.
Reprezentare. Aplicatii
· Metode de sortare si cautre
- Sortare prin enumerare si insertie directa.
- Sortare prin interschimbare. Metoda bulelor.
Sortare rapida.
- Interclasare si sortare prin interclasare.
- Cautarea secventiala si cautarea binara.
Forma de evaluare: examen (sem. 1)
Bibliografie:
- P. Bazavan : Elemente de Teoria Algoritmilor, Ed.
Sitech, 2007.
- T.H. Cormen, C.E. Leiserson, R. Rivest :
Introducere in algoritmi, Editura Agora, 2001.
- G. Barbu, I. Vaduva, M. Bolosteanu : Bazele
Informaticii, Ed. Tehnica, Bucuresti,1997.
- L. Livovschi, H. Georgescu : Bazele Informaticii,
Repr. Univ. Bucuresti, 1985.
- D.E. Knuth : Tratat de programarea calculatoarelor.
Algoritmi fundamentali. Sortare si cautare, Ed. Tehnica, Bucuresti,
1985.
-
Material didactic:
·
Probleme propuse pentru examen, I
Probleme propuse pentru examen, II
|
