Download - Algoritmi si Structuri de date
![Page 1: Algoritmi si Structuri de date](https://reader033.vdocumente.com/reader033/viewer/2022061512/56813491550346895d9b76c8/html5/thumbnails/1.jpg)
Algoritmi si Structuri de date
![Page 2: Algoritmi si Structuri de date](https://reader033.vdocumente.com/reader033/viewer/2022061512/56813491550346895d9b76c8/html5/thumbnails/2.jpg)
Cuprins (Structuri elementare):
Structuri lineare– in alocare statica– in alocare dinamica - liste– structuri lineare cu restrictii la i/o: stive si cozi
Structuri arborescente– arbori oarecari– arbori binari– cautare folosind arbori binari
Sortari interne Arbori binari stricti. Aplicatii.
Conf. Dr. Rodica Ceterchi “Structuri de date si algoritmi: aspecte matematice si
aplicatii”, Ed. Univ. Buc. 2001
![Page 3: Algoritmi si Structuri de date](https://reader033.vdocumente.com/reader033/viewer/2022061512/56813491550346895d9b76c8/html5/thumbnails/3.jpg)
tipuri de date structurate– lineare– ne-lineare: arbori si grafuri
tehnici de sortare– clasa algoritmilor de sortare bazati pe comparatii intre chei– sortare prin interclasare (merging)– alte tipuri de sortari
tehnici de cautare– cautare lineara– cautare bazata pe comparatii intre chei….– structuri arborescente pt. cautare: arbori binari de cautare, arbori
binari de cautare echilibrati AVL, …– tabele de dispersie– alte structuri
Cuprins (alta abordare):
![Page 4: Algoritmi si Structuri de date](https://reader033.vdocumente.com/reader033/viewer/2022061512/56813491550346895d9b76c8/html5/thumbnails/4.jpg)
ALGORITHMS +
DATA STRUCTURES=
PROGRAMS
(N. Wirth, 1976)
![Page 5: Algoritmi si Structuri de date](https://reader033.vdocumente.com/reader033/viewer/2022061512/56813491550346895d9b76c8/html5/thumbnails/5.jpg)
avem de reprezentat multimi (finite, de date omogene)– statice - componenta nu se schimba in timp– dinamice - componenta se schimba in timp
multimi … pe care facem diverse operatii … in scopul rezolvarii unor probleme
![Page 6: Algoritmi si Structuri de date](https://reader033.vdocumente.com/reader033/viewer/2022061512/56813491550346895d9b76c8/html5/thumbnails/6.jpg)
Algoritmi
Algorithm = well-defined computational procedure thatTakes some value/set of values as input, andProduces some value/set of values as output
(computational) Problem = a desired input/output relationship, specified in general terms
Algorithm = tool for solving a problem= computational procedure which achieves the desired input/output relationship
![Page 7: Algoritmi si Structuri de date](https://reader033.vdocumente.com/reader033/viewer/2022061512/56813491550346895d9b76c8/html5/thumbnails/7.jpg)
Example of Problem: sorting
Input: a sequence (a1, a2, …, an)Output: a permutation p of the set {1,…,n} such that in (ap(1), ap(2), …, ap(n)) we have
ap(1) <= ap(2)<= …<= ap(n)
(we can add further constraints, such as:-the space occupied by the input and the output data should be the same-the algorithm is essentially based on direct comparisons of keys, ai < aj
which will be the case for the algorithms considered in the sequel)
For any i in [1..n] ai belongs to X a totally ordered set
all inputs of size n = Xn
an input instance = an element (a1, a2, …, an) of Xn
An algorithm is correct (solves the given problem) iff-it halts-it produces the desired output
![Page 8: Algoritmi si Structuri de date](https://reader033.vdocumente.com/reader033/viewer/2022061512/56813491550346895d9b76c8/html5/thumbnails/8.jpg)
pseudo-cod; independenta de implementare
![Page 9: Algoritmi si Structuri de date](https://reader033.vdocumente.com/reader033/viewer/2022061512/56813491550346895d9b76c8/html5/thumbnails/9.jpg)
Sortarea prin insertie directa
pas iterativ (1): se ia componenta A[2] şi se inserează la locul ei în vectorul sortat de lungime 1, A[1], producând un vector sortat de lungime 2.
pas iterativ (i): (pasă) vectorul este împărţit în două părţi: A[1], …, A[i] este sortată crescător şi se numeşte destinaţie, iar A[i+1], …, A[n] este încă nesortată şi se va numi sursă. Se ia prima componentă din sursă, A[i+1], şi se caută să se insereze la locul ei în destinaţie. Căutarea locului lui A[i+1] în destinaţie se face linear, parcurgând destinaţia de la dreapta la stânga şi mutând pe rând câte o poziţie la dreapta componentele care sunt mai mari decât valoarea de inserat, până când găsim locul valorii x = A[i+1] şi o inserăm.
![Page 10: Algoritmi si Structuri de date](https://reader033.vdocumente.com/reader033/viewer/2022061512/56813491550346895d9b76c8/html5/thumbnails/10.jpg)
Sortarea prin insertie directa
procedure InsDir (A){sortare prin insertie directa a vectorului A[1..n]}for i:= 2 to n do
x:= A[i];{se caută locul valorii x în destinaţie}j:= i- 1;while (j > 0) and (x < A[j]) do
A[j+1]:= A[j]j:= j- 1
endwhile{inserarea lui x la locul lui}A[j+1]:= x
endforendproc.
![Page 11: Algoritmi si Structuri de date](https://reader033.vdocumente.com/reader033/viewer/2022061512/56813491550346895d9b76c8/html5/thumbnails/11.jpg)
Sortarea prin insertie directa (cont.)
procedure InsDir1(A) {s. prin insertie directa a vectorului A[1..n] cu componenta marcaj A[0]}
for i:= 2 to n do{se introduce valoarea în componenta marcaj}A[0]:= A[i];{se caută locul valorii în destinaţie}j:= i-1;while (A[0] < A[j]) do
A[j+1]:= A[j]j:= j-1
endwhileA[j+1]:= A[0]
endforendproc.
![Page 12: Algoritmi si Structuri de date](https://reader033.vdocumente.com/reader033/viewer/2022061512/56813491550346895d9b76c8/html5/thumbnails/12.jpg)
Colectii finite, de date omogene fiecare data (element al colectiei) identificata printr-o
cheie structura de date - mentinerea unei asemenea colectii, cu
o anumita organizare interna operatii specifice de efectuat pe elementele structurii
![Page 13: Algoritmi si Structuri de date](https://reader033.vdocumente.com/reader033/viewer/2022061512/56813491550346895d9b76c8/html5/thumbnails/13.jpg)
Traversarea– operatia care acceseaza fiecare element al structurii, o
singura data, in vederea procesarii (vizitarea elementului)
Cautarea– se cauta un element cu cheie data in structura– cu sau fara succes– consta dintr-o traversare - eventual incompleta a
structurii, in care vizitarea revine la comparatia cu elementul cautat
– problema cheilor multiple - gasirea primei aparitii, a tuturor aparitiilor
Operatii de baza
![Page 14: Algoritmi si Structuri de date](https://reader033.vdocumente.com/reader033/viewer/2022061512/56813491550346895d9b76c8/html5/thumbnails/14.jpg)
Inserarea– adaugarea unui nou element structurii, cu pastrarea
tipului structurii
Stergerea– extragerea unui element al structurii (eventual in
vederea unei procesari), cu pastrarea tipului structurii pe elementele ramase
Operatii de baza (cont.)
Inserarea si Stergerea - reprezentarea multimilor cu caracter dinamic
costuri mici
![Page 15: Algoritmi si Structuri de date](https://reader033.vdocumente.com/reader033/viewer/2022061512/56813491550346895d9b76c8/html5/thumbnails/15.jpg)
Initializarea structurii cu structura vida Crearea - prin inserari repetate
Operatii (cont.)
(1) iniţializarea structurii cu structura vidă(2) un ciclu repetitiv (de lungime variabilă)
(a) se ia câte un element dintr-un fişier de intrare;(b) pentru fiecare asemenea element se apelează o procedură ce implementează operaţia de inserare.
![Page 16: Algoritmi si Structuri de date](https://reader033.vdocumente.com/reader033/viewer/2022061512/56813491550346895d9b76c8/html5/thumbnails/16.jpg)
Operatii (cont.)
Combinare (merge)– din doua structuri de acelasi tip se produce o
alta structura, de acelasi tip, ce contine reuniunea elementelor structurilor de intrare
ex: interclasarea a doua str. liniare ordonate
Sortarea– ordonarea totala a elementelor
sortarea multimilor statice sortarea multimilor dinamice
![Page 17: Algoritmi si Structuri de date](https://reader033.vdocumente.com/reader033/viewer/2022061512/56813491550346895d9b76c8/html5/thumbnails/17.jpg)
Observatii
Legatura operatiilor intre ele inserare/stergere - inverse una alteia inserare/stergere - sunt precedate de cautarea
locului in care se fac cautarea - traversare (eventual incompleta)
NU toate operatiile se implementeaza pe toate structurile!
fiecare structura are operatii specifice
![Page 18: Algoritmi si Structuri de date](https://reader033.vdocumente.com/reader033/viewer/2022061512/56813491550346895d9b76c8/html5/thumbnails/18.jpg)
Structura de date
Colectie finita de date omogene… o anume organizare - structura un anumit tip de acces la date
impreuna cu o multime de operatii specifice - gestionarea structurii
algoritmi specifici ce implementeaza aceste operatii
![Page 19: Algoritmi si Structuri de date](https://reader033.vdocumente.com/reader033/viewer/2022061512/56813491550346895d9b76c8/html5/thumbnails/19.jpg)
Clase principale de structuri
Lineare
Nelineare arborescente grafuri
![Page 20: Algoritmi si Structuri de date](https://reader033.vdocumente.com/reader033/viewer/2022061512/56813491550346895d9b76c8/html5/thumbnails/20.jpg)
Structuri Lineare
In alocare statica - vectori dinamica - liste inlantuite
Operatii de i/o (inserari/stergeri) fara restrictii i/o cu restrictii la i/o (stive si cozi)
![Page 21: Algoritmi si Structuri de date](https://reader033.vdocumente.com/reader033/viewer/2022061512/56813491550346895d9b76c8/html5/thumbnails/21.jpg)
Structuri lineare in alocare statica
Traversare Inserare Stergere Cautare
![Page 22: Algoritmi si Structuri de date](https://reader033.vdocumente.com/reader033/viewer/2022061512/56813491550346895d9b76c8/html5/thumbnails/22.jpg)
Traversarea(unei str. liniare in alocare statica)
procedure Traversare(A, 1, n)k := 1; {iniţializarea indicelui pentru traversare}while k <= n do {test pentru nedepăşirea structurii}
vizitează A[k];k := k+1; {trecem la componenta următoare}
endwhileendproc
![Page 23: Algoritmi si Structuri de date](https://reader033.vdocumente.com/reader033/viewer/2022061512/56813491550346895d9b76c8/html5/thumbnails/23.jpg)
Inserarea (intr-o str. liniara in alocare statica)
procedure Insert(A, 1, n, k, Elem){inserează în structura liniară A[1 .. n], pe poziţia k, valoarea lui Elem}
{mută pe rând elementele de la A[n] până la A[k] câte o locaţie la dreapta}i := n;while i >= k do
A[i+1] := A[i];i := i-1;
endwhile{inserarea propriu-zisă}A[k] := Elem;{creşte dimensiunea structurii}n := n+1;
endproc
![Page 24: Algoritmi si Structuri de date](https://reader033.vdocumente.com/reader033/viewer/2022061512/56813491550346895d9b76c8/html5/thumbnails/24.jpg)
Stergerea (dintr-o str. liniara in alocare statica)
procedure Delete(A, 1, n, k, X){extrage în X valoarea A[k] şi reface vectorul}
{extragerea propriu-zisă}X := A[k];{refacerea structurii de vector}for i := k to n-1 do
A[i] := A[i+1];endfor{scade dimensiunea structurii}n := n-1;
endproc
![Page 25: Algoritmi si Structuri de date](https://reader033.vdocumente.com/reader033/viewer/2022061512/56813491550346895d9b76c8/html5/thumbnails/25.jpg)
Costuri - inserare
pi = probabilitatea evenimentului de a insera o valoare nouă pe componenta i, i [1..n].
La inserarea pe poziţia i trebuie să mutăm n-i+1 componente.
Numărul mediu de mutări la inserare M = pi (n - i+1) .
Dacă p1 = …= pn = 1/n atunci
M = (1/n) ( n + ( n –1) + …. + 1 ) =(n+1)/2
In functie de mutari de componente
![Page 26: Algoritmi si Structuri de date](https://reader033.vdocumente.com/reader033/viewer/2022061512/56813491550346895d9b76c8/html5/thumbnails/26.jpg)
Costuri - stergere
pi = probabilitatea evenimentului de a sterge componenta i, i [1..n].
La stergerea lui A[i] trebuie să mutăm n-i componente.
Numărul mediu de mutări la stergere M = pi (n - i) .
Dacă p1 = …= pn = 1/n atunci
M = (1/n) ( ( n –1) + …. + 1 ) =(n-1)/2
In functie de mutari de componente
![Page 27: Algoritmi si Structuri de date](https://reader033.vdocumente.com/reader033/viewer/2022061512/56813491550346895d9b76c8/html5/thumbnails/27.jpg)
Cautarea(unei valori date intr-o str. lineara in alocare statica)
procedure SearchLin ( A, 1, n, Val, Loc){caută liniar valoarea Val în A[1..n] şi returnează Loc = 0 dacă nu o găseşte, şi o valoare Loc [1..n] dacă o găseşte pe componenta A[Loc]} Loc: = 0 i:= 1; while (i <= n) and (A[i] <> Val) do
i:= i+1endwhileif i<= n then
Loc:= iendif
endproc {SearchLin}
![Page 28: Algoritmi si Structuri de date](https://reader033.vdocumente.com/reader033/viewer/2022061512/56813491550346895d9b76c8/html5/thumbnails/28.jpg)
Cautarea lineara - componenta marcaj
procedure SearchLin1 ( A, 1, n, Val, Loc){Căutare lineară de la stanga la dreapta}
A[n+1]: = Val {introducem Val pe componenta marcaj, care va fi la capatul din dreapta}
Loc: = 1while A[Loc] <> Val do
Loc: =Loc +1endwhileif Loc = n+1 then
"Căutare fără succes"else
"Am găsit pe componenta Loc"endif
endproc; {SearchLin1}
![Page 29: Algoritmi si Structuri de date](https://reader033.vdocumente.com/reader033/viewer/2022061512/56813491550346895d9b76c8/html5/thumbnails/29.jpg)
Complexitate (costuri) - cautare lineara
pi = probabilitatea evenimentului Val=A[i] (gasim valoarea căutată pe componenta i), i [1..n].
q = probabilitatea ca Val să nu se găsească în A[1..n].
Avem pi + q = 1 .
Pentru fiecare i [1..n+1], pentru a decide că prima apariţie a lui Val este pe componenta A[i], facem i comparaţii.Numărul mediu de comparaţii va fi:
C = pi i + q(n+1) .
In functie de componente accesate (comparatii)
![Page 30: Algoritmi si Structuri de date](https://reader033.vdocumente.com/reader033/viewer/2022061512/56813491550346895d9b76c8/html5/thumbnails/30.jpg)
Complexitate (costuri) - căutare lineară (cont.)
Cazul căutării cu succes:
- Val se găseşte precis în vector, i.e. q=0
- se găseşte cu probabilitate egală pe oricare din componente, i.e. p1 = …= pn = 1/n
C = (1/n) ( 1 + 2 + ……. + n) = (n+1)/2
numărul mediu de comparaţii în cazul căutării cu succes.
Cazul căutării fără succes:
- se traversează toata structura, se accesează n+1 comp.
C = n+1
![Page 31: Algoritmi si Structuri de date](https://reader033.vdocumente.com/reader033/viewer/2022061512/56813491550346895d9b76c8/html5/thumbnails/31.jpg)
Caz particular - vector ordonat crescător
Structură lineară in alocare statica (secventiala) organizare suplimentara
A[1] A[2] … A[n]
Informatie in plus– permite imbunatatirea cautarii
lineare alta cautare - cautarea binara
– necesita modificarea algoritmilor de inserare
![Page 32: Algoritmi si Structuri de date](https://reader033.vdocumente.com/reader033/viewer/2022061512/56813491550346895d9b76c8/html5/thumbnails/32.jpg)
Cautarea lineara intr-un vector sortat
procedure SearchLinOrd (A, 1, n, Val, Loc) Loc:= 0i:= 1while (i <= n) and (A[i] < Val) do
i:=i+1endwhileif i <= n then
if A[i] = Val then {căutare cu succes}
Loc:= i else {A[i] > Val}
{căutare fără succes**}endif
else{căutare fără succes}
endif
endproc{ SearchLinOrd}
![Page 33: Algoritmi si Structuri de date](https://reader033.vdocumente.com/reader033/viewer/2022061512/56813491550346895d9b76c8/html5/thumbnails/33.jpg)
Cautarea binara (intr-un vector sortat)
A[1..n] un vector cu A[1] A[2] … A[n]
Algoritmul de căutare binară:
(1) Se începe cu segmentul definit de indicii Left:= 1 şi Right:= n(2) Pentru fiecare subvector A[Left..Right] se repetă:
(a) Se calculează mijlocul segmentului Mid:= (Left + Right) div 2
(b) Se compară Val cu A[Mid]:- dacă Val = A[Mid] căutarea se termină cu succes;- dacă Val < A[Mid] se reia pasul (2) pe [Left..Mid-1];- dacă Val > [Mid] se reia pasul (2) pe [Mid+1..Right].
![Page 34: Algoritmi si Structuri de date](https://reader033.vdocumente.com/reader033/viewer/2022061512/56813491550346895d9b76c8/html5/thumbnails/34.jpg)
procedure SearchBin(A, 1, n, Val, Loc)Left:= 1; Right:= n;Mid:=(Left + Right) div 2;Loc:= 0while (Left <= Right) and (Val <> A[Mid] ) do
if Val < A[Mid] then {se continuă pe subintervalul din stânga}Right:= Mid-1
else {Val > A[Mid]} {se continuă pe subintervalul din dreapta}Left:= Mid+1
endif Mid:= (Left + Right) div 2
endwhileif A[Mid] = Val then
Loc:= Mid {căutare cu succes}else Loc:= 0 {căutare fără succes}endifendproc{SearchBin}
![Page 35: Algoritmi si Structuri de date](https://reader033.vdocumente.com/reader033/viewer/2022061512/56813491550346895d9b76c8/html5/thumbnails/35.jpg)
Cautarea binara - complexitate
C(n) = numărul de comparaţii pe care îl necesită căutarea binară pe un vector cu n componente. După fiecare comparaţie dimensiunea segmentului pe care căutăm se reduce la jumătate.
Dacă după C(n) comparaţii am încheiat căutarea, atunci 2C(n) > n > 2C(n)-1
de undeC(n) = log2 n +1
complexitatea căutării binare - O(log2 n)complexitatea căutării lineare (secventiale) - O(n)
![Page 36: Algoritmi si Structuri de date](https://reader033.vdocumente.com/reader033/viewer/2022061512/56813491550346895d9b76c8/html5/thumbnails/36.jpg)
Bibliografie
![Page 37: Algoritmi si Structuri de date](https://reader033.vdocumente.com/reader033/viewer/2022061512/56813491550346895d9b76c8/html5/thumbnails/37.jpg)
Bibliografie1. D.E. Knuth :"Tratat de programarea calculatoarelor", vol. I si III2. T. H. Cormen, C. E. Leiserson, R. L. Rivest: "Introduction to Algorithms", The MIT Press, 19903. N. Wirth: "Algorithms + Data Structures = Programs", Prentice Hall Inc., 19764. A. V. Aho, J. E. Hopcroft, J. D. Ullman: "Data Structures and Algorithms", Addison-Wesley Publ. Comp., 19835. S. Baase: "Computer Algorithms: Introduction to Design and Analysis", Addison-Wesley Publ. Comp., 19886. L. Nyhoff, S. Leestma: "Advanced programming in Pascal with Data Structures", MacMillan Publ. Comp. N.Y., 19887. L. Livovschi, H. Georgescu: "Sinteza si analiza algoritmilor", Ed. Stiintifica si Enciclopedica, Bucuresti, 19868. C. Ionescu Texe, I. Zsako: "Structuri arborescente cu aplicatiile lor", Ed. Tehnica, Bucuresti, 19909. I. Tomescu: "Data Structures", Editura Univ. din Bucuresti, 199710. Rodica Ceterchi "Structuri de date", Editura Univ. din Bucuresti, 2001