| Profesori: |
|
|
Cristian Giumale, Stefan Trausan-Matu
|
| Obiective: |
|
|
Prezentarea conceptelor si tehnicilor de baza ale analizei si demonstrarii corectitudinii algorimilor. Analiza algoritmilor esentiali de prelucrare a grafurilor si a principalelor structuri de cautare. Analiza unor algoritmi eficienti de sortare interna si externa.
|
| Continut: |
|
|
Elemente de analiza a algoritmilor. Recurente si comportare asimptotica. Elemente privind corectitudinea si verificarea algoritmilor. Tehnici de proiectare a algoritmilor, programare dinamica, algoritmi "lacomi". Analiza algoritmilor fundamentali pentru grafuri: traversare īn latime/adāncime, sortare topologica, determinarea drumurilor de cost minim, puncte de articulatie si punti, bicomponente, componente tare conexe, arbori minimi de acoperire. Algoritmi specifici de prelucrare a structurilor fundamentale de cautare: tabele de dispersie, arbori de cautare echilibrati, arbori optimi de cautare, arbori B. Arbori de codificare. Algoritmi eficienti pentru sortare interna, cautare si selectie. Algoritmi de sortare externa.
|
| Cunostinte: |
|
|
Programare si structuri de date fundamentale. Matematica elementara.
|
| Notare: |
|
|
40% examen final 25% proiect 35% laborator
|
| Bibliografie: |
|
Cormen, Leiserson, Rivest - Introducere in algoritmi - Ed. Teora
Knuth E. Donald - Tratat de programare a calculatoarelor - Ed. Tehnica, 1977
C.A. Giumale, L. Negreanu, S. Calinoiu - Proiectarea si analiza algoritmilor: algoritmi de sortare - Ed. All, 1996
L. Negreanu, S. Calinoiu - Structuri de cautare - Indrumar de laborator, Lit. UPB, 1994
L. Livovski, H. Georgescu - Bazele informaticii. Algoritmi. - Ed. Univ. Bucuresti, 1985
Baase Sara - Computer Algoritms, Introduction to Design and Analysis - Addison-Wesley, 1988
|
