Decan Sef de catedra Prof. Univ. Dr. Rodica TRANDAFIR Conf. Univ. Dr. Rodica IOAN VIZAT

FISA DISCIPLINEI

I. UNIVERSITATEA SPIRU HARET FACULTATEA MATEMATICA-INFORMATICA DOMENIUL DE LICENTA SPECIALIZAREA Anul universitar 2008 - 2009 Forma de invatamant ZI II. DENUMIRE DISCIPLINA ALGORITMI SI STRUCTURI DE DATE

III. CODUL DISCIPLINEI IV. Statut disciplina Obligatorie Optionala Facultativa (se marcheaza cu X) X V. Structura disciplinei (nr. ore) Semestrul (numar de la 1 la 6)

Curs (nr. ore/sapt. si total nr.ore/sem.)

Seminar (nr. ore/sapt. si total nr.ore/sem.)

Laborator (nr. ore/sapt. si total nr.ore/sem.)

Lucrari practice (nr. ore/sapt. si total nr.ore/sem.)

Proiecte (nr. ore/sapt. si total nr.ore/sem.)

2 2/28 - 2/28 - - VI.(ETCS) Numar credite 5 VII. OBIECTIVELE DISCIPLINEI 1. Prezentarea structurilor de date fundamentale şi algoritmii de bază asociaţi acestor structuri. 2. Utilizarea noţiunilor predate la disciplinele Arhitectura sistemelor de calcul (introducere in programarea intr-un limbaj de asamblare) si Programare procedurala (programare avansata in limbajul C). 3. Formarea deprinderii de a utiliza structuri de date potrivite contextului aplicativ. Pregatirea background-ului pentru disciplinele Proiectare si programare orientata obiect, Tehnici avansate de programare, Algoritmica grafurilor, Baze de date, Inteligenta artificiala, etc. 4. Asigurarea compatibilitatii in cadrul invatamantului de excelenta : University of Cambridge (http://www.cl.cam.ac.uk/DeptInfo/CST05/node30.html); Harvard University Extension School (http://www.extension.harvard.edu/2008-09/courses/csci.jsp#e-119). VIII. CONTINUT TEMATIC 1. Elemente de teoria analizei algoritmilor (2 ore) 1.1. Aspecte generale privind analiza şi complexitatea unui algoritm; 1.2. Evaluarea complexităţii. Exemple de analiză a unor algoritmi. Clase de complexitate. 1.3. Algoritmi iterativi si algoritmi recursivi. Avantaje si dezavantaje. 1.4. Introducere in proiectarea algoritmilor.

2. Metode de sortare : interschimbare, interclasare, insertie, sortare rapida, alte metode (4 ore) 3. Structuri de date fundamentale (12 ore) - Liste simple, duble, liniare, circulare, generalizate: operatii, implementari, aplicatii - Stive si cozi : operatii, implementari, aplicatii. - Arbori : clase de arbori (oarecare, binari, de sortare/cautare, AVL, heap, B si B+), metode de reprezentare, metode de explorare, aplicatii. 4. Algoritmi de cautare : liniara, binara, arborescenta, functii hash, cautare in siruri (6 ore). 5. Clase speciale de algoritmi : probabilisti, evolutionisti(2 ore). 6. Structuri de date multidimensionale (2 ore). IX. TEME SEMINAR - X. LUCRARI DE LABORATOR 1. Bazele limbajului Java/C++: clase, constructori, intrari-iesire simple (4 ore). 2. Complexitatea algoritmilor. Algoritmi recursivi. Programarea aplicatiilor procedurale in C++/Java (4 ore). 3. Tablouri. Metode de sortare (2 ore). 4. Liste liniare simple. Liste circulare simple. Liste liniare duble. Liste circulare duble. Stive si cozi (2 ore) 5. Arbori binari. Arbori R-B. Reprezentări şi parcurgeri. Aplicatii (2 ore). 6. Arbori binari de căutare. Arbori echilibrati (2 ore) 7. Arbori oarecare. Metode de explorare in adancime/latime. Aplicatii (2 ore) 8. Arbori Heap. Sortare avansata (2 ore). 9. Functii de dispersie. Cautare avansata (2 ore). 10. Algoritmi specifici sirurilor (2 ore). 11. Clase speciale de algoritmi (4 ore). XI. LUCRARI PRACTICE (daca este cazul) XII. PROIECTE (daca este cazul) XIII. Forma de evaluare (procent din nota finala) Examen Colocviu Verificare pe

parcurs Lucrari practice

Laborator Proiecte

- - 70% - 30% - XIV. Bibliografie Obligatorie minimala Suplimentara Facultativa 1. Albeanu G., Algoritmi si limbaje de programare, Editura FRM, 2000 (pag: 60-65, 70-74, 98-99, 175-197, 207-216, 254-276)

1. T. Cormen, C. Leiserson, R. Rivest, Introducere în algoritmi, Ed. Computer Libris Agora, Cluj-Napoca, 2000. 2. P. S. Deshpande, O. G. Kakde, C & Data Structures, Charles River Media, 2004, ISBN:1584503386. 3. A. Drozdek, Data

1. Cormen, T.H., Leiserson, C.D., Rivest, R.L. & Stein, C. (2001). Introduction to Algorithms. MIT Press (2nd ed.). ISBN 0-262-53196-8. 2. Roberge J., Brandle S.,

2. Barză S., Luciana-Maria Morogan, Structuri de date, Ed. FRM., Bucureşti, 2007 (integral).

3. Carabineanu A., Structuri de date, Editura Universitatii din Bucuresti, Editura MATRIX ROM, Bucuresti, 2006: (disponibila in format electronic la http://ebooks.unibuc.ro/informatica/carabineanu/CARA_STR.pdf )

structures and algorithms in C++, Brooks/Cole, 2001. 4. A.E. Eiben, J.E. Smith, Introduction to evolutionary computing, Springer, 2003. 5. D.E. Knuth, The Art of Computer Programming, Vol 1 : Fundamental algorithms, Vol 3 : Sorting and Searching, Addison-Wesley. 6. Tomescu I., Data Structures, Bucharest University Press, Bucharest, 1997, 2004 (integral). 7. Waite M., Lafore R., Structuri de date şi algoritmi în Java, Ed. Teora, 2001 (integral). 8. Marin Popa, Mariana Popa, Programare procedurala (Aplicatii C si C++ in structuri de date si grafica), Editura FRM, 2006 (Sectiunea 1.5)

Whittington D., A laboratory course in C++ data structures (ed. 2), Jones and Bartlett Publishers, 2003.

XV. Metode didactice (clasice/moderne) 1. Prelegerea - proiecţie in amfiteatru, programe demonstrative; 2. Recomandarea, pentru studiul individual, a unor paragrafe din bibliografia indicată, în vederea aprofundării sau extinderii cunoştinţelor căpătate la curs/laborator ; 3. Prezentarea unor exemple şi a unor probleme aplicative în cadrul cursului pentru sporirea interesului cursantilor. 4. Evaluare folosind platforma Blackboard. Data Titular disciplina

Titlul didactic, Numele si prenumele

Prof. Univ. Dr. ALBEANU GRIGORE

29.09.2008 _____________________ Semnatura

_______________________

ALGORITMI SI STRUCTURI DE DATE

CONSULTATII 1. Elemente de teoria analizei algoritmilor 1.1. Aspecte generale privind analiza şi complexitatea unui algoritm; 1.2. Evaluarea complexităţii. Exemple de analiză a unor algoritmi. Clase de complexitate. 1.3. Algoritmi iterativi si algoritmi recursivi. Avantaje si dezavantaje. 1.4. Introducere in proiectarea algoritmilor. Se presupune cunoscuta notiunea de algoritm precum si caracteristicile algoritmilor ([1], pag. 7-11). In completare la materialul descris in ([1] ; pag 60-65) se adauga partea de algoritmi recursivi (introdusi in [1], pag. 133-136) cu elemente privind complexitatea algoritmilor recursivi. In acest sens, se introduc cateva elemente privind rezolvarea recurentelor de ordinul 1 si 2 (omogene si neomegene). Recomandam pentru studiu individual si resursa: http://www.ginfo.ro/revista/14_1/mate2.pdf; http://www.teora.ro/manuale/0086/0086-122.pdf, http://www.teora.ro/manuale/0086/0086-123.pdf, http://www.teora.ro/manuale/0086/0086-124.pdf ca si o continuare a metodelor pentru determinarea termenului general al unui sir dat printr-o relatie de recurenta prezentate in cadrul cursului de Analiza matematica. Relatii de recurenta de ordinul intai:

a) f(n) = c f(n-1), n >0, f(0) = k cu solutie de forma f(n) = kcn. b) f(n) = bn f(n-1), n>1, f(0) cunoscut, iar bn este un sir cunoscut. Astfel f(n) =

b1b2...bnf(0). c) f(n)+cf(n-1) = p(n), n>0.

Daca p(n) neindentic nul atunci relatia este neomogena, in caz contrar relatia se numeste omogena. Unele relatii de recurenta neliniare, printr-o anumita substitutie algebrica, se pot transforma in relatii liniare care se pot rezolva imediat. De exemplu (f(n))2 = 8(f(n-1))2, f(0)=2 -> f(20) = 231. Solutia generala a unei astfel de relatii este de forma f(n)=f(n)(0)+f(n)(p) unde f(n)(0) reprezinta solutia relatiei omogene asociate f(n)+cf(n-1) =0, iar f(n)(p) este o solutie particulara. 1) Daca p(n)=kan nu este solutie a relatiei omogene asociate, atunci o solutie particulara va fi de forma f (n)(p) = man unde m este o constanta care urmeaza a se din conditia initiala. 2) Daca p(n)=kan este solutie a relatiei omogene asociate, atunci se va considera f(n)( p) = qnan , unde q este o constanta care se va determina din conditia initiala. O relatie de forma f(n) = af(n-1) + bf(n-2), n>1, f(0) si f(1) fiind valori cunoscute, iar a si b fiind constante, se va numi relatie de recurenta omogena de ordinal doi cu coeficienti constanti.

Relatia de recurenta data admite o solutie particulara de forma f(n) = αn (α nenul). Introducand pe f(n) in relatia data initial si impartind prin αn-2 in ambii membri, se obtine o ecuatie de gradul al doilea α2 = aα +b numita si ecuatie caracteristica. Solutiile acestei ecuatii, numite radacini caracteristice, pot fi:reale si distincte α1 , α2. In aceasta situatie, (α1)n si (α2)n sunt solutii liniar independente, adica ele nu se pot exprima una ca un multiplu de cealalta pentru orice n > 0. In concluzie, solutia relatiei date va fi de forma f(n)= c1 (α1)n + c2 (α2)n, iar constantele c1, c2 sunt determinate din valorile initiale f(0) si f(1). Daca cnf(n) + cn-1f(n-1) + … + cn-kf(n-k) = 0 cu cn , cn-1 , … ,cn-k constante reale nenule, iar α este o radacina caracteristica multipla de ordin m (1 <m <k+1 ), atunci solutia generala se va lua de forma f(n)= c0 αn + c1nαn + … +cm-1 nm-1αn. Algoritmii recursive desi au o implementare scurta (ca numar de instructiuni) conduc la o complexitate efectiva mai mare datorita necesitatii autoapelului si pot sa epuizeze stiva programului. Ca tehnici de proiectare a algoritmilor se remarca abordarea IPO (Input-Processing-Output), metoda de reducere la o problema (functie, procedura) cunoscuta, metode precum divide et impera, greedy, programare dinamica, branch and bound, etc. 2. Metode de sortare: interschimbare, interclasare, insertie, sortare rapida, alte metode Descrierea acestor metode se gaseste in [1], pag. 11, 65, 213, 214, [2] (capitolul special dedicat metodelor de sortare). Analiza acestor metode este dezvoltata in : http://www.ginfo.ro/revista/12_1/focus.pdf si [3] (pag. 59-92) Lista metodelor de sortare cuprinde :

1. Metoda interschimbarii (Bubble sort) [1, pag 11], [3, pag. 64-69]; 2. Metoda selectiei (min, max, min-max, heap) [3, pag. 69-74], [1, pag. 97-98,

192-196]; 3. Metoda insertiei directe [3, pag. 63, 64], [1, pag. 64-65]. O varianta mai rapida

a metodei foloseste cautarea binara [1, pag. 98] pentru a stabili locul insertiei. Se obtine algoritmul descris in [1, pag. 136];

4. Sortare prin numarare [3, pag. 61-62]; 5. Sortare prin interclasare [3, pag. 74-77], [1, pag. 213-214]; 6. Sortare prin partitionare (numita si sortare rapida… qsort) [1, pag. 214-215],

[3, pag. 65-69]. 3. Structuri de date fundamentale - Tablouri. - Liste simple, duble, liniare, circulare, generalizate: operatii, implementari, aplicatii - Stive si cozi : operatii, implementari, aplicatii. - Arbori : clase de arbori (oarecare, binari, de sortare/cautare, AVL, heap, B si B+), metode de reprezentare, metode de explorare, aplicatii. Se considera structuri de date de baza ca find tablourile uni si multidimensionale. Tablourile bidimensionale sunt asimilate matricelor, dar pot avea si alte elemente decit numere. Tablourile cu n dimensiuni se numesc si masive n-dimensionale.

Pentru asigurarea portabilitatii inter platforme se practica liniarizarea tablourilor n dimensionale (adica matricele, structurile spatiale, etc. se vor memora intr-un tablou ale carui elemente se parcurg cu un singur indice). De exemplu elementele unui tablou bidimensional A cu n randuri si m coloane vor fi stocate intr-un sir B prin corespondenta : A[i][j] este stocat in B[k] daca si numai daca k=i*m+j. Similar se formuleaza conditii si pentru tablourile cu mai multe dimensiuni. Este importanta formarea deprinderilor de a lucra cu tablouri diagonale : Dia, tablouri banda B(r, s), tablouri tridiagonale : TriD, tablouri triunghiulare : Inf3(A) si Sup3(A), tablouri de tip Hessenber : H(A). Regiunea Dia se refera la elementele pentru care indicele liniei coincide cu indicele coloanei. Regiunea TriD este multimea elementelor cu indici (i, j) pentru care |i-j|<2 ; Regiunea B(r,s) este multimea elementelor cu indici (i, j) pentru care j>=i-r sau j <=i+s, i = 1, 2, …, n (daca indicii sunt numerotati de la 1) Regiunea H(A) defineste ceea ce se numeste matricea superioara Hessenberg : (i, j) pentru care j>=i-1, i=1, 2, …, n. Prin similitudine se poate defini si matricea inferioara Hessenberg. Tablourile triunghiulare se refera la multimea perechilor de indici care descriu elementele de pe diagonala si de sub diagonala (Inf3), respectiv de pe diagonala si cele situate deasupra diagonalei (Sup3). Tablourile pot fi utilizate in alocarea statica a structurilor de date : liste, arbori, grafuri care suporta si o alocare dinamica. Listele liniare, stivele [LIFO], cozile [FIFO] si algoritmii fundamentali (inserare, stergere) in implementari liniare sau circulare sint discutate in [1, pag. 175-179], [3, pag. 5-20] si in [2]. Arborii sint introdusi in [1, pag. 179-197] unde se prezinta si principalele metode de reprezentare, explorare si operatii de inserare/stergere. O aplicatie a arborilor binari se refera la compresia informatiei prin algoritmul lui Huffman [3, pag. 20-39]. Arborii permit implementarea unor algoritmi eficienti de cautare/sortare si de accea stau la baza sistemelor de gestiune a bazelor de date. Principalele tipuri de arbori, in acest context, sunt :

1. Arbore binar de sortare si cautare [1, pag. 272-276]. 2. Arbori balansati/echilibrati (AVL, B, B+) [3, pag. 108-135]

4. Algoritmi de cautare : liniara, binara, arborescenta, functii hash, cautare in siruri A permite regasirea rapida a informatiei reprezinta o cerinta importanta a sistemelor informatice actuale. Se au in vedere urmatoarele metode :

1. Cautare liniara [2], [3, pag. 94-96]. 2. Cautare binara in siruri ordonate si arborele de decizie asociat cautarii

optimale [1, pag. 98], [3, pag. 77-81]. 3. Cautare arborescenta [1, pag. 272-276], [3, pag. 108-113] 4. Functii hash [3, pag. 136-139] 5. Cautare in siruri [1, pag. 72-73]

5. Clase speciale de algoritmi: probabilisti, evolutionisti Pentru diverse aplicatii (simulare, criptografie, optimizari) se utilizeaza si alte clase de algoritmi. O categorie aparte o reprezinta metodele bazate pe numere pseudo-aleatoare [1, pag. 70-72] si cei de tip evolutionist (construirea unor generatii de candidati la solutia optima : http://www.ginfo.ro/11_8/focus.pdf ), un caz special fiind reprezentat de algoritmii genetici : http://www.ginfo.ro/revista/11_6/focus.pdf 6. Structuri de date multidimensionale Astfel de structuri sunt utile in aplicatii de grafica, sisteme informatice geografie si sunt implementate folosind toate tipurile prezentate anterior, precum si grafuri. O clasa speciala de structura este reprezentata de arborii Quad utilizati in compresia imaginilor. Elemente teoretice si cod in limbajul C pentru implementarea algoritmilor de creare, explorare (traversare), actualizare (inserare, modificare, stergere), prelucrare (cautare, sortare, numarare, studiul unor proprietati) se gasesc in [1] si [4]. Pentru unele aspecte se recomanda si parcurgerea materialelor din Gazeta de Informatica (indicate prin link-urile de mai sus). Bibliografie

1. G. Albeanu, Algoritmi si limbaje de programare, Editura FRM 2000. 2. S. Barză, Luciana-Maria Morogan, Structuri de date, Ed. FRM., Bucureşti,

2007 3. I. Tomescu, Data Structures, Editura Universitatii din Bucuresti, 1997. 4. A. Carabineanu, Structuri de date, Editura Universitatii din Bucuresti, Editura

MATRIX ROM, Bucuresti, 2006: (disponibila in format electronic la http://ebooks.unibuc.ro/informatica/carabineanu/CARA_STR.pdf )