Universitatea "Babes-Bolyai" Cluj-Napoca
Facultatea de Matematica si Informatica
FISA DISCIPLINEI

Analiza si proiectarea algoritmilor
Cod
Semes-
trul
Ore: C+S+L
Credite
Tipul
Sectia
MI112
6
2+1+0
5
optionala
Informatică
Cadre didactice indrumatoare
Lect. IONESCU Clara, clara@cs.ubbcluj.ro
Obiective
Dupa insusirea materialului prezentat la aceasta disciplina studentul ar trebui:
* sa realizeze problemele care se ridica in activitatea de dezvoltare a produselor software
* sa inteleaga necesitatea proiectarii programelor in acord cu cerintele utilizatorilor
* sa poata verifica un produs program in urma realizarii lui
* sa poata realiza produse program de dimensiuni medii
* sa aiba deprinderi de folosire a instrumentelor de asistare a activitatii de dezvoltare a programelor
Continut
1. Introducere (1)
1.1. Algoritmi
1.2. Analiza algoritmilor.
1.3. Proiectarea algoritmilor

2. Instrumente de analiză (2)
2.1. Notaţia asimptotică
2.2. Notaţii standard şi funcţii comune
2.3. Analiza amortizată

3. Sume (3-4)
4. Recurenţe şi recursivitate
5. Mulţimi
6. Numărare şi probabilitate

7. Algoritmi din teoria numerelor (5-6)
7.1. Algoritmi de combinatorică iterativi
7.2. Cutia lui Dirichlet

7. Tehnici de programare
7.1. Clasificarea problemelor în funcţie de complexitate. NP-completitudine (7)
7.2. Divide et Impera (8)
7.3. Sortări (9)
7.4. Căutări (10)
7.5. Potrivirea şirurilor (11)

8. Tehnici avansate (12-13)
8.1. Algoritmi greedy
8.2. Euristica greedy
8.3. Programare dinamică

9. Rezolvarea problemelor NP-complete şi comparaţia diferitelor soluţii (14)
9.1. Backtracking
9.2. Euristica greedy
9.3. Algoritm probabilişti
9.4. Algoritmi aproximativi
9.5. Algoritmi evolutivi şi genetici
Bibliografie
1. T. Cormen, C. Leiserson, R. Rivest, Introducere in algoritmi, Computer Libris Agora, Cluj-Napoca, 2000
2. James A. Storer, An Introduction to Data Structures and Algorithms, Springer, New York, 2002
Evaluare
In timpul semestrului studentii vor proiecta, implementa, si testa programe de dimensiuni medii. La sfarsitul semestrului vor sustine un examen scris. Nota finala obtinuta se va calcula astfel:
* Activitate laborator: 4 pct
* Examen scris - o problema de programare: 6 pct