Universitatea "Babes-Bolyai" Cluj-Napoca
Facultatea de Matematica si Informatica
FISA DISCIPLINEI

Complexitatea calculului
Cod
Semes-
trul
Ore: C+S+L
Credite
Tipul
Sectia
MC006
8
2+2+0
10
optionala
Informatică
Cadre didactice indrumatoare
Conf. Dr. TRÎMBITAS Radu Tiberiu, tradu@cs.ubbcluj.ro
Obiective
A da studentilor notiuni de complexitatea analitica si calitativa a calculului, a le permite sa analizeze algoritmi si clase de algoritmi, a le da criterii de selectie a algoritmilor si a-i face constienti de limitele calculabilitatii.
Continut
1. Formularea problemei, masurarea complexitatii.
2. Preliminarii matematice: ordin de marime, relatii de recurenta, enumerari, functii generatoare.
3. Analiza algoritmilor.
4. Algoritmi recursivi.
5. Algoritmi din teoria numerelor.
6. Metode de sortare si cautare.
7. NP - Completitudine si clase de complexitate.
8. Complexitatea algoritmilor numerici.
9. Analiza asistata de calculator a algoritmilor.
10. Elemente de complexitate calitativa.
11. Algoritmi probabilisti si aplicatii ale complexitatii in criptografie.
Bibliografie
1. Knuth, D.E., Tratat de programarea calculatoarelor. Vol.I, Algoritmi fundamentali, Ed. Tehnica, Bucuresti, 1974. Vol.II, Algoritmi seminumerici. Vol.III, Sortare si cautare, Ed. Tehnica, Bucurest, 1976.
2. Wilf, H.S., Algorithmes et complexite, Mason & Prentice Hall, 1985.
3. Baase, S., Computer Algorithms: Introduction to Design and Analysis, Addison- Wesley, 1983.
4. Aho, A.V., Hopcroft, J.E., Ullmann, J.D., The Design and Analysis of Computer Algorithms, Addison Wesley, 1974.
5. Comer, Leiserson, Rivest - Algorithms, MIT Press,1990.
Evaluare
Examen.