Cod : I1103
Titular curs : Lector dr. M. Cosulschi
Forma de invatamant : Informatica (3 ani)
Ciclul : I
Semestrul 1, Curs : 2h, Seminar : 2h
Nr. credite : 5
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
  1. Notiunea de algoritm. Limbajul algoritmic.
  2. Complexitatea algoritmilor.
  3. Recursivitate.


• Generarea submultimilor
  1. Produs cartezian
  2. Generarea submultimilor unei multimi
  3. Generare combinari
  4. Generare permutari


• Metode de elaborare a algoritmilor
  1. Metoda "Divide et Impera"
  2. Metoda Greedy
  3. Metoda Backtracking
  4. Metoda programarii dinamice


• Metode de sortare si cautare
  1. Ordonare prin metoda bulelor, ordonare prin selectie, ordonare prin comparare
  2. Ordonare prin numarare
  3. Ordonare prin insertie directa, ordonare prin insertie binara
  4. Metoda Shell-Sort
  5. Interclasarea a doua siruri ordonate. Metoda MergeSort
  6. Metoda QuickSort
  7. Metoda de cautare secventiala si metoda de cautare binara


• Structuri de date
  1. Liste liniare statice: stive, cozi. Operatii
  2. Liste liniare inlantuite. Implementare. Operatii
  3. Tabele de dispersie si functii de dispersie. Implementare.
  4. Grafuri neorientate.Reprezentare si parcurgere. Componentele conexe ale unui graf si determinarea acestora.
  5. Grafuri orientate. Reprezentare.
  6. Arbori oarecare. Reprezentare si parcurgere.
  7. Arbori binari. Reprezentare si parcurgere


• Algoritmi din teoria grafurilor
  1. Grafuri orientate. Componente tari conexe si determinarea lor.
  2. Drumuri minime intr-un graf orientat. Drumuri minime cu sursa unica - algoritmul Dijkstra. Drumuri minime intre perechi de varfuri - algoritmul Floyd.
  3. Arbori de acoperire minimi - algoritmul Kruskal
  4. Arbori binari de cautare. Interogarea, inserarea si stergerea intr-un arbore binar de cautare.
  5. Grafuri orientate. Reprezentare.
  6. Arbori oarecare. Reprezentare si parcurgere.
  7. Arbori binari. Reprezentare si parcurgere

1. M. Cosulschi: Note de curs, 2007
2. M. Cosulschi, M. Gabroveanu, Algoritmi - o abordare pragmatica, Editia a 2-a, Ed. Universitaria, 2004.
3. P. Bazavan: Elemente de Teoria Algoritmilor, Sitech, 2007.
4. T. H. Cormen, C. E. Leiserson, R. L. Rivest, Introducere ^łn Algoritmi, Computer Libris Agora, 1999.
5. Gh. Barbu, I. Vaduva, M. Bolosteanu, Bazele informaticii, Ed. Tehnica, 1997.
6. L. Livovschi, H. Georgescu, Analiza si sinteza algoritmilor, Ed. Stiintifica si Enciclopedica, Bucuresti, 1986.
7. D. D. Burdescu, Analiza complexitatii algoritmilor, Editura Albastra, 1998.
8. D. E. Knuth, Arta programarii calculatoarelor, vol. 1 Algoritmi fundamentali, Teora, 2000.
9. D. E. Knuth, Arta programarii calculatoarelor, vol. 3 Sortare si Cautare, Teora, 2002.
10. R. Sedgewick, Algorithms in C, Second Edition, Addison-Wesley, 1998

Material didactic: