Universitatea "Babeş-Bolyai" din Cluj-Napoca

Facultatea de Matematică şi Informatică
FISA DISCIPLINEI

Complexitatea calculului

Computation complexity

Cod	Semes- trul	Ore: C+S+L	Credite	Tipul	Sectia
MC006	8	2+2+0	10	optionala	Informatică (Computer Science)

Cadre didactice indrumatoare

Teaching Staff in Charge

Conf. Dr. TRÎMBIŢAŞ Radu Tiberiu, tradu@cs.ubbcluj.ro

Obiective	Aims
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.	To introduce students in basics of Computation Complexity, to allow them analize and chose algorithms and to make them aware of limits of computability.

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	Assessment
Examen.	Exam.