Alg Struct Date

7
 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.

Transcript of Alg Struct Date

Page 1: Alg Struct Date

5/10/2018 Alg Struct Date - slidepdf.com

http://slidepdf.com/reader/full/alg-struct-date 1/7

 

Decan Sef de catedra

Prof. Univ. Dr. Rodica TRANDAFIR Conf. Univ. Dr. Rodica IOANVIZAT

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.

Page 2: Alg Struct Date

5/10/2018 Alg Struct Date - slidepdf.com

http://slidepdf.com/reader/full/alg-struct-date 2/7

 

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.,

Page 3: Alg Struct Date

5/10/2018 Alg Struct Date - slidepdf.com

http://slidepdf.com/reader/full/alg-struct-date 3/7

 

 2. Barză S., Luciana-Maria Morogan,

Structuri de date, Ed. FRM., Bucureşti, 2007

(integral).

3. Carabineanu A., Structuri de date, EdituraUniversitatii din Bucuresti, Editura MATRIX

ROM, Bucuresti, 2006: (disponibila in

format electronic la

http://ebooks.unibuc.ro/informatica/carabinea

nu/CARA_STR.pdf )

 structures and algorithms inC++, Brooks/Cole, 2001.

4. A.E. Eiben, J.E. Smith,

 Introduction to evolutionarycomputing , 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

BartlettPublishers, 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ă, învederea 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

GRIGORE29.09.2008

 _____________________  Semnatura

 _______________________ 

Page 4: Alg Struct Date

5/10/2018 Alg Struct Date - slidepdf.com

http://slidepdf.com/reader/full/alg-struct-date 4/7

 

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) = kc n.

 b)  f(n) = bn

f(n-1), n>1, f(0) cunoscut, iar bn

este un sir cunoscut. Astfel f(n) =

 b1 b2...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.

Page 5: Alg Struct Date

5/10/2018 Alg Struct Date - slidepdf.com

http://slidepdf.com/reader/full/alg-struct-date 5/7

 

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 relatieidate 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-k f(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.

Page 6: Alg Struct Date

5/10/2018 Alg Struct Date - slidepdf.com

http://slidepdf.com/reader/full/alg-struct-date 6/7

 

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 :

Page 7: Alg Struct Date

5/10/2018 Alg Struct Date - slidepdf.com

http://slidepdf.com/reader/full/alg-struct-date 7/7

 

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 )