Universitatea "Babeş-Bolyai" din Cluj-Napoca

Facultatea de Matematică şi Informatică
FISA DISCIPLINEI

Analiza şi complexitatea algoritmilor

Analysis and complexity of algorithms

Cod	Semes- trul	Ore: C+S+L	Credite	Tipul	Sectia
MI019	6	2+1+0	5	optionala	Informatică (Computer Science)

Cadre didactice indrumatoare

Teaching Staff in Charge

Prof. Dr. KASA Zoltan, kasa@cs.ubbcluj.ro

Obiective	Aims
Cursul are scopul de a initia studentii in problemele de analiza si complexitatea algoritmilor. Sunt prezentate diferite metode de calcul al complexitatii. Se studiaza clasa problemelor polinomiale si a celor NP-complete.	The aim of this course is to introduce the students in the problems of analysing and complexity of the algorithms. Several methods of computing the complexity are presented. Polynomial and NP-complete problems are treated.

Continut

1. Analiza algoritmilor: principii si exemple. 2. Complexitatea algoritmilor de sortare interna: bubblesort, quicksort, heapsort, shellsort, bucket sort, interclasare binara. 3. Complexitatea algoritmilor de sortare externa: algoritmi polifaza, realizarea monotoniilor, sortare cu mai multe benzi. 4. Complexitatea algoritmilor de teoria grafurilor: arbore de acoperire minimal, algoritmi de drumuri, cel mai scurt drum, componente conexe, probleme de cuplaj si flux. 5. Complexitatea algoritmilor referitoare la siruri de caractere: algoritmul Morris-Pratt-Knuth de cautare. 6. Complexitatea algoritmilor de algebra matriceala: produsul matricelor, metodele: Winograd, Strassen, transformata Fourier discreta. 7. Complexitatea algoritmilor boolene (relatii, matrice booleene): algoritmul lui Warshall pentru inchiderea tranzitiva, inmultirea matricelor de biti. 8. Probleme NP-complete. 9. Algoritmi de aproximare: problema rucsacului, problema inpachetarii, problema colorarii grafurilor.

Bibliografie

1. S. Baase: Computer Algorithms. Introduction to design and analysis, Addison-Wesley, 1983 (Second ed. 1988) 2. M.R. Garey, D.S. Johnson: Computers and intractability. A guide to the theory od NP-completeness, Freeman, 1979. 4. Lovasz L., Algoritmusok bonyolultsaga, ELTE, Budapest, 1992. 5. M. Sipser, Introduction to the theory of computation, PWS Publ. Co. 1997 6. Papadimitriu, C. H., Computational Complexity, Addison-Wesley, 1994. 7. Cormen, T. H.–Leiserson, C. E.–Rivest, R. L., Algoritmusok, Műszaki Kiadó, Budapest, 1997. 8. Wagner, K.–Wechsung, G., Computational Complexity, D. Reidel P. Co., 1986

Evaluare	Assessment
Examen scris.	Written exam.