| Analiza si complexitatea algoritmilor |
trul |
|||||
| Cadre didactice indrumatoare |
| Prof. Dr. KASA Zoltan, kasa@cs.ubbcluj.ro |
| Obiective |
|
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. |
| 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 |
|
Examen scris. |