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.