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.