Structuri de Date si Algoritmi exam
Scurt istoric. Noţiuni de baza: Algoritm, Structuri de date, etc.
Pentru prima data in sec 9 dHr Abu Abdullah a scris o
lucrare despre efectuarea calculelor numerice algebrice. Prin algoritm se
intelege – reguli de baza carora se fac calcule matematice. Kroneker si
Dedekind introduc funtii recursive la care se va referi algoritmul. In sec 20
se propune teoria algoritmilor, recursivitatea care se introduc axiomatic. Algoritm – succesiune de pasi si proprietatile
/ regulile sistemului cibernetic – i/o data. Cerintele algoritmului: claritate
(descriere precisa, toate etapele de calcul sa fie prevazute), generalitate (sa rezolve o anumita clasa
de probleme), finitudine (furnizeaza
rezultate intr-un nr finit de pasi), unicitate
(etapele algoritmului trebuie prezentate in mod unic), discretitate (executarea secventiala a pasilor simpli, fiecarui pas
fiindu-i dat timp). Operatori de baza
– i/o, atribuire, decizie. Reprezentarea
algoritmului – schema logica, pseudo cod, limbaj de programare. Structuri elementare – liniara (etape de calcul ce succed una
dupa alta), alternativa (ramificarea
executiei in functie de valoarea de adevar a conditiei evaluate), repetitiva (executie repetata de nr
finit de ori a unei secvente de instructiuni ciclu). Tipuri de structuri de date: baza (simboluri, cifre a caror divizare nu are sens, sunt
determinate de arhitectura calculatorului), complexe
(construite de utilizator pentru sarcini specifice). Structura de date – unitate de soft care poate stoca si
procesa multimi de acelasi tip sau date unite-n calcul logic precum adaugare,
cautare, stergere,editare; ofera funcții integrate care formeaza interfata ei;
este posibilitatea realizarii unui tip abstract de date).
Teoria algoritmilor si Mașina Turing.
Algoritm – succesiune de pasi si proprietatile
/ regulile sistemului cibernetic – i/o data. Cerintele algoritmului: claritate
(descriere precisa, toate etapele de calcul sa fie prevazute), generalitate (sa rezolve o anumita clasa
de probleme), finitudine (furnizeaza
rezultate intr-un nr finit de pasi), unicitate
(etapele algoritmului trebuie prezentate in mod unic), discretitate (executarea secventiala a pasilor simpli, fiecarui pas
fiindu-i dat timp). Operatori de baza
– i/o, atribuire, decizie. Reprezentarea
algoritmului – schema logica, pseudo cod, limbaj de programare. Schema logica – prezentare
grafica care permite vizualizarea inlantuirii si subordnarii secventelor de
operatii. Masina Turing – mecanisme
extrem de elementare de dispozitive de prelucrare a simbolurilor care pot fi
adaptate pentru a simula logica oricarui calculator. Orice problema algoritmica
poate fi rezolvata de Turing. Concept:
persoana virtuala executa procedura bine definita, schimba continutul casutelor
unui tablou plasand in ele simboluri admise, memoreaza starea sistemului. E ca
un automat cu stiva modificat prin LIFO a stivei.
Structuri de date. Clasificarea acestora. C versus C++.
Structuri elementare – liniara (etape de calcul ce succed una dupa alta), alternativa (ramificarea executiei in
functie de valoarea de adevar a conditiei evaluate), repetitiva (executie repetata de nr finit de ori a unei secvente de
instructiuni ciclu). Tipuri de
structuri de date: baza
(simboluri, cifre a caror divizare nu are sens, sunt determinate de arhitectura
calculatorului), complexe (construite
de utilizator pentru sarcini specifice). Structura
de date – unitate de soft care poate stoca si procesa multimi de
acelasi tip sau date unite-n calcul logic precum adaugare, cautare,
stergere,editare; ofera funcții integrate care formeaza interfata ei; este
posibilitatea realizarii unui tip abstract de date). Lista structurilor de date: primitive (boolean, char, float, double, int, enumerated type), composite (array, record, union, tagged
union, plain old data structure), abstracte
(containter, list, set, stack, string, tree, graph, map, queue).
C++ este un limbaj de programare de uz general proiectat
pentru programatori profesionisti. Cu exceptia unor detalii minore, C++ este
bazat pe limbajul C. C++ ofera o platforma pentru a suporta programarea
orientata pe obiecte dar si posibilitatea de abstractizare a problemelor de
nivel inalt ceea ce C nu poate oferi.
Algoritmi combinatoriali. Introducere. Permutări, Combinări, Aranjamente.
Programarea algoritmilor.
Combinatorica
–ramura care studiaza obiectele discrete in seturi.Se ocupa de studiul
multimilor si modalitatile de a le combina. Sunt studiate: combinatorica
enumerative, design combinatoric si teoria matroizilor, combinatorica
extremala, combinatorica algebrica
Permutari –
multimi finite de orice natura; - oricare multime ordonata din n elemente: n!. Combinari – n elemente neordonate
combinate cate m: n!/m!(n-m)!. Aranjamente
– n elemente ordonate cate m: n!/(n-m)!. A=m!C. Calculul acestora se face cu
ajutorul functiei recursive factorial.
Algoritmul de afisare a
permutarilor:
void permutare (int *a,int n,int index) {
for (int i=index; i
int copyOfA[n];
for(int j=0; j
int t=copyOfA[index];
copyOfA[index]=copyOfA[i];
copyOfA[i]=t;
permutare(copyOfA, n, index+1);}
if (index==n-1) { printArray(a,n);}}
Formule Herigonne, Pascal. Demonstrație. Exemple și aplicații
practice.
Sistemul major (de asemenea, numit,sistem mnemonic
fonetic, sau sistemul mnemonic al lui Herigone) este o tehnică mnemonica
utilizată pentru a ajuta la memorarea numerelor. Sistemul functionează prin
conversia numerelor în sunete consonantice, apoi în cuvinte prin adăugarea de
vocale. Sistemul functioneaza pe principiul că imaginile pot fi memorizate mai
usor decât numerele. Fiecare cifră este asociata cu unul sau mai multe
consoane. Vocalele si consoanele w, h, y si x sunt ignorate. Acestea pot fi
utilizate ca "umplutură" pentru a face cuvinte sensibile din
secventele consonantice rezultate. Un avantaj al sistemului major este aceea că
este posibil să se utilizeze la un calculator pentru a traduce automat numărul
într-un set de cuvinte. Se poate alege apoi cel mai bun din mai multe alternative.
Pascal: Cn0+Cn1+Cn2…Cnm=2^n.
Recursia. Algoritm recursiv. Funcții recursive. Exemple.
Recusia –
definitia functiei contine referire la ea insasi.
Fibonacci:
F(n)=F(n-1)*F(n-2);
int fib (int n) {if (n<2 1="1" else="else" fib="fib" font="font" n-1="n-1" n-2="n-2" return="return">
factorialul: int
fact (int n) { if ((n==0)||(n==1)) return 1; else return (fact(n-1)*n);
Programarea algoritmului “Tunurilor din Hanoi”.
Turnurile din Hanoi este un joc matematic sau puzzle.
Este format din trei tije și un număr variabil de discuri, de diferite mărimi,
care pot fi poziționate pe oricare din cele 3 tije. Jocul începe având
discurile așezate în stivă pe prima tijă, în ordinea mărimii lor, astfel încât
să formeze un turn. Scopul jocului este acela de a muta întreaga stivă de pe o
tijă pe alta, respectând următoarele reguli: Doar un singur disc poate fi
mutat, la un moment dat; Fiecare mutare constă în luarea celui mai de sus disc
de pe o tija și glisarea lui pe o altă tijă, chiar și deasupra altor discuri
care sunt deja prezente pe acea tijă; Un disc mai mare nu poate fi poziționat
deasupra unui disc mai mic.
Sortare prin
simplă înserare (Straight insertion). Posibilități de îmbunătățire a metodei.
Insertion
sort – fiecare element se compara cu vecinul sau, daca are loc schimarea se
compara cu fiecare din cele precedente.
10 2 16 23 0 4 19 21 24 9
2 10 16 23 0 4 19 21 24 9
0 2 10 16 23 4 19 21 24 9
0 2 4 10 16 23 19 21 24 9
0 2 4 10 16 19 23 21 24 9
0 2 4 10 16 19 21 23 24 9
0 2 4 9 10 16 19 21 23 24
void strightInsertion (int *a, int n) {
int i,j,x;
for(i=1;i
x=a[i];
j=i;
while((j>0)&&(x
a[j]=a[j-1];
j=j-1;}
a[j]=x;}}
Sortare prin
simplă selectare (Straight selection). Posibilități de îmbunătățire a metodei.
Selection
sort – un element se compara cu celelalte si daca gaseste unul mai mic ca el
se schimba cu locul, daca nu – ramane pe primul loc. Daca a gasit un element mai
mic ala deja se compara cu celelalte urmatoare. Complex: O(n^2).
10 2 16 23 0 4 19 21 24 9
2 10 16 23 0 4 19 21 24 9
0 10 16 23 2 4 19 21 24 9
0 2 16 23 10 4 19 21 24 9
0 2 10 23 16 4 19 21 24 9
0 2 4 23 16 10 19 21 24 9
0 2 4 16 23 10 19 21 24 9
0 2 4 10 23 16 19 21 24 9
0 2 4 9 23 16 19 21 24 10
0 2 4 9 23 10 19 21 24 16
0 2 4 9 19 10 23 21 24 16
0 2 4 9 16 10 23 21 24 19
0 2 4 9 16 10 21 23 24 19
0 2 4 9 16 10 19 23 24 21
0 2 4 9 16 10 19 21 24 23
0 2 4 9 16 10 19 21 23 24
void straightSelection (int *a, int n){
int i, indx, j, large;
for(i=n-1;i>0;i--){
large=a[0];
indx=0;
for(j=1;j<=i;j++){
if(a[j]>large){
large=a[j];
indx=j;}}
a[indx]=a[i];
a[i]=large;}}
Sortare prin
simplu schimb (Buble sort). Posibilități de îmbunătățire a metodei.
Bubble
sort – fiecare 2 elemente vecine se compara, daca al 2-lea e mai mare ca
primul nu se fac schimbari; aceasta se repeta pana nu se mai face nicio
schimbare. Complex: O(n^2).
void bubbleSort(int *a,int n){
int x;
for(int i=0; i
for(int j=0; j
if(a[j]>a[j+1]){
x = a[j+1];
a[j+1] = a[j];
a[j] = x;}}}}
Sortare de
tipul Shaker. (Shakersort).
void ShakerSort(int *a,int n)
{int i,exchange,t;
do{exchange=0;
for(i=n-1;i>0;--i){
if(a[i-1]>a[i]){
t=a[i-1];
a[i-1]=a[i];
a[i]=t;
exchange=1;}}
for(i=1;i
if(a[i-1]>a[i]){
t=a[i-1];
a[i-1]=a[i];
a[i]=t;
exchange=1;}}}
while(exchange);}
Parametrii
care reflectă eficiența algoritmilor și programelor.
Parametrii de eficienta a alogoritmilor: timpul necesar de rulare a programului
masurat in numarul de operatii pe care le efectueaza; spatiul de memorie necesar rularii algoritmului.
Sortarea cu
micșorarea incrementului. (Shell Sort)
Shell
Sort – comparare pe baza insertion sort; compararea incepe cu elementele
cele mai indepartate unul de altul pana ajunge la cele vecine. Se foloseste o
ratie h care se micsoreaza treptat pana la 1. Daca h=5, 3, 1 intr-o lista de 12
elemente se formeaza subliste pentru h=3: (a1, a6, a11), (a2, a7, a12), (a3,
a8), (a4, a9), (a5, a10). Se face insertion sort asupra acestor subliste. Apoi
se trece la h=3: se formeaza si se sorteaza sublistele (a1, a4, a7, a10), (a2,
a5, a8, a11), (a3, a6, a9, a12). Si la h=1 se face o sortare (a1 … a12). Pasi
recomanati pentru h: 1, 4, 13, 40, 121… sau 1, 3, 7, 15, 31… Compexitatea
algoritmului depinde de h: obisnuit O(nlog(2)n).
Sortarea
prin intermediul arborilor. Sortarea piramidală. (Heapsort)
Heap Sort –
algoritm de sortare bazat pe selectie si comparatie. Primul pas este sa
construim un arbore din datele initiale. Al doilea pas incepe cu excluderea
celui mai mare element din arbore si includerea acestuia in lista ordonata pe
pozitia 0. Reconstruim arborele si urmatorul element cel mai mare se incude pe
urmatoarea pozitie in lista. Complexitate O(nlogn). Nodurile mai mari nu pot
sta mai jos decat cele mai mici se controleaza si se schimba si iar se
controleaza.
Sortarea
prin divizare. (Quicksort)
Quick
sort – primul element pivot se compara incepand de la ultimul si daca
gaseste unul mai mic decat el se schimba cu locul si de acolo incepe compararea
de la inceput, cu elementele primele pana la el si deja daca gaseste unul mai
mare se schimba. Dupa schimbare se termina compararea. Ramane definitiv pe
locul cela. S-a delimitat lista. Incepe compararea cu primul – pivotul nou –
pana la locul definitivat.
Căutarea informației textuale:
Metoda
direct - Cea mai simpla si mai putin eficienta metoda pentru a vedea unde un
string apare in altul este sa verificam fiecare loc in care poate fi, unu cite
unu, pentru a-l depista. Asadar, in primul rind vedem daca este o copie in
primul character a multimii; daca nu, verificam daca e o copie incepind de la
al doilea character, si asa mai departe. Intr-un caz normal noi verificam unul
sau 2 caractere pentru fiecare pozitie gresita pentru a o depista, asadar
complexitatea e O(n+m) pasi, unde n e lungimea multimii, n – este caracterul
cautat; in cel mai rau caz cautarea unui string de tipul "aaaab"
intr-un string de tipul "aaaaaaaaab" va lua O(nm) pasi.
Algoritmul
Knuth-Morris Pratt - Calculeza un indicator determinist de
marginire care este ca un suffix prin care se recunoaste in multime. Metoda de
cautare a unui sir de caractere – model (pattern) P[0..m] intr-un sir de
caractere sursa T[0..n], n>=m; construit pe functia - prefix π(P),
fiind un exemplu clasic de programare dinamica, cu eficienta O(N+M); consta in
deplasarea modelului P de-a lungul sursei T efectuata cu un numar mai mare de
pozitii, in acelasi timp sa se memoreze partea de text care coincide cu
modelul: evitam comparatiile inutile, creste viteza de cautare.
Functia-prefix π(P) – determina prefixul maxim a lui P, care este, defapt, si sufixului
lui P. Π(abracadabra) = abra;functia se aplica pentru a construi matricea k a
lungimilor acestor prefixe, si determina daca modelul se contine in sursa
sau/si cu cite pozitii trebuie sa deplasam modelul spre dreapta pentru a cauta o noua potrivire.
Grafuri
Noțiuni
de bază.
Numim graf o pereche ordonată de mulțimi, notată G=(X,U), unde X este o mulțime finită și nevidă de elemente numite
noduri sau vârfuri, iar U este o mulțime de perechi (ordonate sau neordonate)
de elemente din X numite muchii (dacă sunt perechi neordonate) sau arce (dacă
sunt perechi ordonate). În primul caz, graful se numește neorientat, altfel
acesta este orientat. Doua virfuri unite printr-o muchie sunt adiacente. Drum –
succesiune de muchii. Lungimea drumului e egala cu numarul muchiilor care il
constituie. Drum simplu – drum in care niciun virf nu se repeat.
Gradul unui nod particular v numărul de arce care sunt conectate la
acel nod. Ciclu – drum simplu in care primul si ultimul virf coincid; P = x0,
..., xk-1 este un drum în graful G și xk-1x0 este o muchie în acest
graf, atunci P + xk-1x0 este un ciclu. Aciclic – fara cicluri.
Subgraf – o parte din graf,fara citeva noduri si muchiile lor. Partial – toate
nodurile,fara citeva muchii. Conex – neorientat, oricare 2 noduri au drum intre
ele. Tare conex – orientat, intre oricare 2 virfuri exista drum in 2 directii.
In graful neconex este problema determinarii elementelor conxe.
Modalitatea
de prezentare în memoria calculatorului utilizând diferite structuri de date.
Matrice de adiacenta – M(nxn), M(i,j)={1 – daca (i,j) apartine U (listei
muchiilor) si 0 – daca nu.}
Liste de adiacenta – o colectie de n pointeri < (1, 2, ... , n),
fiecare pointer continând adresa unei liste dupa regula urmatoare: L(i) da
adresa listei înlantuite care contine toti succesorii lui i.
Lista de muchii – Fiecare muchie a grafului poate fi privita ca o
inregistrare cu doua componente: cele doua varfuri care constitue extremitatile
muchiei.
Programarea
algoritmilor pentru determinarea drumului minim (maxim): Ford simplificat (pentru
grafuri fără circuite) - se da un graf orientat (cu arce) fara
circuite, fiecarui arc i se asociaza un numar Cij. Nodul 1 este nod cu gradul
de incidenta 0 si este nod de intrare in graf; nodul final are doar arce de
sisire. Sa identificam toate retelele d lungime minima ce pornesc de la nodul 1
pina la toate celelalte noduri. Metoda de solutionare este algoritmul Ford: se
numeroteaza corect graful prin suprimarea consecutiva a arcelor astfel incit
pentru orice muchie (i,j) i
Programarea
algoritmilor de verificare a existenței ciclurilor în grafuri. Ciclu – drum
simplu in care primul si ultimul virf coincid; P = x0, ..., xk-1 este un drum
în graful G și xk-1x0 este o muchie în acest graf, atunci P + xk-1x0 este un
ciclu. Conditia ca un arc (x,y) să nu formeze ciclu cu celelalte arce selectate
se poate exprima astfel: nodurile x si y
trebuie să se afle în componente conexe diferite. Initial fiecare nod formează
o componentă conexă, iar apoi o componentă
conexă contine toate
nodurile acoperite cu
arce din MST,
iar nodurile neacoperite formează alte componente conexe.
Programarea
algoritmilor pentru determinarea drumului minim: Dijkstra Cel mai
eficient algoritm cunoscut pentru problema drumurilor optime cu o singură sursă
este algoritmul lui Dijkstra, care poate fi descris în mai multe moduri: ca
algoritm de tip “greedy” cu o coadă cu priorităti, ca algoritm ce foloseste
operatia de “relaxare” (comună si altor algoritmi), ca algoritm cu multimi de vârfuri sau ca algoritm cu vectori.
Diferentele de prezentare provin din structurile de date utilizate. Se
foloseste un vector D astfel că d[i] este distanta minimă de la 1 la i, dintre drumurile
care trec prin noduri deja selectate. O
variabilă S de tip multime memorează numerele nodurilor cu distantă minimă fată de nodul 1, găsite până la
un moment dat. Initial S={1} si
d[i]=cost[1][i], adică se consideră arcul direct de la 1 la i ca drum minim
între 1 si i. Pe măsură ce algoritmul evoluează, se actualizează D si S.
// S =multime noduri ptr care s-a
determinat distanta minima fata de 1 repetă cât timp S contine mai putin de n
noduri ; gaseste muchia (x,y) cu x în S si y nu în S care face minim
d[x]+cost(x,y) adauga y la S
S ={1}
{d[y] = d[x] + cost(x,y)}
La fiecare pas din algoritmul Dijkstra: -
Se găseste dintre nodurile j care nu apartin lui S acel nod
"jmin" care are distanta minimă fată de nodurile din S; - Se adaugă nodul "jmin" la multimea
S; - Se recalculează distantele de la
nodul 1 la nodurile care nu fac parte
din S, pentru că distantele la nodurile din S rămân neschimbate; - Se retine în p[j] numărul nodului precedent
cel mai apropiat de nodul j (de pe drumul minim de la 1 la j). Pentru a ilustra
modul de lucru al algoritmului Dijkstra considerăm un graf orientat cu
următoarele costuri de arce:
(1,2)=5; (1,4)=2; (1,5)=6;
(2,3)=3;
(3,2)=4; (3,5)=4;
(4,2)=2; (4,3)=7; (4,5)=3;
(5,3)=3
Drumurile posibile intre 1 si 3 si costul lor:
1-2-3 = 8; 1-4-3 = 9; 1-4-2-3 = 7;
1-4-5-3 = 8; 1-5-3 = 9;
Drumurile minime de la 1 la celelalte noduri sunt în acest graf: 1-4-2 cost
4
1-4-2-3 cost 7
1-4 cost 2
1-4-5 cost 5 De observat că într-un
drum minim fiecare drum partial este minim; astfel în drumul 1-4-2-3, drumurile
partiale 1-4-2 si 1-4 sunt si ele minime.
Exemplu de functie pentru algoritmul Dijkstra:
void dijkstra (Net g,int p[]) { // Net este tipul abstract “graf cu
costuri”
int d[M],s[M]; // s= noduri ptr care se stie distanta minima
int dmin; int jmin,i,j;
for (i=2;i<=g.n;i++) {
p[i]=1; d[i]=carc(g,1,i); // distante initiale de la 1 la alte noduri
}
s[1]=1; for (i=2;i<=g.n;i++) { //
repeta de n-1 ori
// caută nodul j ptr care d[j] este minim
dmin =MARE;
for (j=2;j<=g.n;j++) // determina minimul dintre distantele d[j]
if (s[j]==0 && dmin > d[j]) { // daca j nu e in S si este mai
aproape de S
dmin =d[j]; jmin=j;
}
s[jmin]=1; // adauga nodul jmin la S
for (j=2;j<=g.n;j++) // recalculare distante noduri fata de 1
if ( d[j] >d[jmin] + carc(g,jmin,j) ) {
d[j] =d[jmin] + carc(g,jmin,j);
p[j] =jmin; // predecesorul lui j pe drumul minim
}
}
} In programul principal se apelează
repetat functia "drum":
for(j=2;j<=n;j++)
drum (p,1, j); // afisare drum minim de la 1 la j
Afisarea drumului minim pe baza vectorului "p" se poate face
recursiv sau iterativ:
// drum minim intre i si j - recursiv
void drum (int p[], int i,int j) {
if (j != i)
drum (p,i,p[j]);
printf ("%d ",j);
}
// drum minim intre i si j - iterativ
void drum (int p[], int i,int j){
int s[M], sp=0; // s este o stiva vector cu varful
in sp
printf ("%d ",i); // primul nod de pe calea i~j
while (j != i) { // pune pe stiva nodurile precedente lui j
s[++sp]=j;
j=p[j]; // precesorul lui j}
for( ; sp>=1;sp--) // afisare continut stiva
printf("%d ",s[sp]);}
Arbori.
Exemple de reprezentare:
Reprezentarea prin liste
generalizate. Nodurile terminale sunt elemente atomice, nodurile cu
gradul mai mare decit 1 sunt subsubliste. Img.
Reprezentare prin structuri
înlănțuite. Conteaza ordinea pointerilor; avind adresa unui nod se
gasesc toti predecesorii. Img.
Arbori.
Specificul programării problemei. Programarea algoritmilor care determină
arborele de cost minim într-un graf după algoritmii:
Algoritmul PRIM Algoritmul
lui Prim seamănă cu algoritmul Dijkstra pentru drumuri minime si foloseste o
coadă cu priorităti de arce
care leagă vârfuri
din MST cu
alte vârfuri (coada
se modifică pe
măsură ce algoritmul evoluează).
Algoritmul lui Prim se bazează pe observatia următoare: fie S o submultime a
vârfurilor grafului si R submultimea V-S (vârfuri care nu sunt în S); muchia de
cost minim care uneste vârfurile din S cu vârfurile din R face parte din MST.
La fiecare pas se face o nouă tăietură în graful rămas si se determină un alt
arc din MST; proces repetat de n-1 ori (sau până când S este vidă). Solutia
problemei este o multime de arce, deci un vector de perechi de noduri, sau doi
vectori de întregi X si Y, cu semnificatia că o pereche x[i]-y[i] reprezintă un
arc din MST. Este posibilă si folosirea unui vector de întregi pentru arborele
MST. Implementarea mai eficienta a algoritmului Prim folosind 2 vectori:
p [i] = numărul nodului din S cel mai apropiat de nodul
i din R
c [i] = costul arcului dintre i si p[i]
La fiecare pas se caută în vectorul “c” pentru a găsi nodul k din R cel mai apropiat de nodul i din S.
Pentru a nu mai folosi o multime S, se atribuie lui c[k] o valoare foarte mare astfel ca nodul k să nu mai fie
luat in considerare în pasii următori.
Multimea S este deci implicit multimea nodurilor i cu c[i] foarte mare.
Celelalte noduri formează multimea R.
# define M 20 // nr maxim
de noduri
# define M1 10000 // un nr. foarte
mare (cost arc absent)
# define M2 (M1+1) // alt numar
foarte mare (cost arc folosit)
// alg. Prim pentru arbore minim de acoperire
void prim (Net g, int x[ ], int y[ ]){
int c[M], cmin;
int p[M], i,j,k;
int n=g.n; // n = nr de varfuri
for(i=2;i<=n;i++) {
p[i]=1; c[i]=carc (g,1,i); //
costuri initiale
}
for(i=2;i<=n;i++) { // cauta
nodul k cel mai apropiat de un nod din mst
cmin = c[2]; k=2;
for(j=2;j<=n;j++)
if ( c[j] < cmin) {
cmin=c[j]; k=j;
}
x[i-1]=p[k]; y[i-1]= k; // retine muchie de cost minim in x si y
c[k]=M2;
// ajustare costuri in U
for(j=2;j<=n;j++)
if (carc(g,k,j) < c[j] && c[j] < M2) {
c[j]= carc(g,k,j); p[j] =k;}}}
Evolutia vectorilor “c” si “p” pentru exemplul dat este următoarea:
Au fost necesare două constante mari: M1 arată că nu există un arc între
două noduri, iar M2 arată că acel arc a fost inclus în MST si că va fi ignorat
în continuare.
Vectorul “p” folosit în programul anterior corespunde reprezentării unui
arbore printr-un singur vector, de predecesori.
Complexitatea algoritmului Prim cu vectori este O(n*n), dar poate fi redusă
la O(m*lg(n)) prin folosirea unui heap pentru memorarea costurilor arcelor
dintre U si V.
Algoritmul KRUSCAL Ideea
algoritmului Kruskal este de a alege la fiecare pas arcul de cost minim dintre
cele rămase (încă neselectate), dacă el nu formează ciclu cu arcele deja
incluse în MST (selectate). Conditia ca un arc (x,y) să nu formeze ciclu cu
celelalte arce selectate se poate exprima astfel: nodurile x si y trebuie să se afle în
componente conexe diferite. Initial fiecare nod formează o componentă conexă,
iar apoi o componentă conexă contine
toate nodurile acoperite
cu arce din
MST, iar nodurile
neacoperite formează alte componente conexe.
Algoritmul Kruskal pentru găsirea unui arbore de acoperire de cost minim
foloseste două tipuri abstracte de date: o coadă cu priorităti si o colectie de
multimi disjuncte si poate fi descris astfel:
citire date si creare coada de arce
repetă {
extrage arcul de cost minim din coada
dacă arc acceptabil atunci {
afisare arc
actualizare componente conexe
}
} până când toate nodurile conectate
Un arc care leagă două noduri dintr-o aceeasi componentă conexă va forma
un ciclu cu arcele selectate anterior si nu poate fi acceptat. Va fi acceptat
numai un arc care leagă între ele noduri aflate în două componente conexe
diferite.
Pentru reteaua cu 6 noduri si 10 arce (1,2)=6; (1,3)=1; (1,4)=5;
(2,3)=5; (2,5)=3;
(3,4)=5; (3,5)=6; (3,6)=4; (4,6)=2; (5,6)=6
Toate nodurile din graf trebuie să se afle în componentele conexe. Initial
sunt atâtea componente (multimi) câte noduri există. Atunci când un arc este
acceptat, se reunesc cele două multimi
(componente) care contin extremitătile arcului în una singura; în felul acesta
numărul de componente conexe se reduce treptat până când ajunge egal cu 1
(toate nodurile legate într-un graf conex care este chiar arborele de acoperire
cu cost minim).
Evolutia componentelor conexe pentru exemplul anterior:
Pas Componente conexe
1 {1}, {2},{3},{4},{5},{6}
2 {1,3}, {2},{4},{5},{6}
3 {1,3}, {2,5}, {4,6}
4 {1,3,4,6}, {2,5}
7 {1,2,3,4,5,6}
In programul următor graful este un vector de arce, ordonat crescător după
costuri înainte de a fi folosit. Exemplu:
typedef struct { int v,w,cost ;} Arc;
// compara arce dupa cost (ptr qsort)
int cmparc (const void * p, const void* q) {
Arc * pp =(Arc*) p; Arc *qq=(Arc*) q;
return pp->cost -qq->cost;
}
// algoritmul Kruskal
void main ( ) {
DS ds; Arc arce[M], a;
int x,y,n,na,mx,my,nm,k;
printf ("nr.noduri în graf: ");
scanf ("%d", &n);
initDS (ds,n); // ds = colectie de multimi disjuncte
printf ("Lista de arce cu costuri: \n");
nm=0; // nr de muchii in graf
while ( scanf ("%d%d%d",&a.v,&a.w,&a.cost) > 0)
arce[nm++]=a;
qsort (arce, nm, sizeof(Arc), cmparc);
// ordonare lista arce
k=0; // nr arc extras din coada
for ( na=n-1; na > 0; na--) {
a=arce[k++]; // următorul arc de cost minim
x=a.v; y=a.w; // x, y = extremitati arc
mx= findDS (ds,x); my=findDS (ds,y);
if (mx !=my ) { // daca x si y in componente conexe diferite
unifDS (ds,x,y); // atunci se reunesc cele doua componente
printf ("%d - %d \n",x,y); // si se scrie arcul gasit ptr mst
}}}
Complexitatea algoritmului Kruskal depinde de modul de implementare al
colectiei de multimi disjuncte si este în cel mai bun caz O(m*lg(n)) pentru o
implementare eficientă a tipului DS (este practic timpul de ordonare a listei
de arce).
Arbori
binari. Operaţii asupra arborilor binari.
Arborii binari sunt una dintre cele mai importante structuri neliniare in
teoria algoritmilor. Structura de arbore se refera la o relație de ramificare
la nivelul nodurilor, asemănătoare aceleia din cazul arborilor din natura.
Arborii sunt constituiți din noduri interne (puncte de ramificare) si noduri
terminale (frunze). Fiecare nod are 0, 1 sau 2 succesori; fiecare nod are un
singur predecesor, cu excepția rădăcinii care nu are niciunul; succesorii
fiecărui nod sunt ordonați (fiul stâng, fiul drept; dacă este unul singur
trebuie menționat care). Operatii: creare/inserare (Aloca memoria necesara unui
nod; Citește informația nodului si așează mesaje de invitație pentru crearea
nodurilor descendente (stâng si drept); daca numărul introdus este diferit de
0, se apelează recursiv funcția pentru crearea subarborelui stâng stocându-se
adresa de legătura pentru accesul la descendenți. Urmează apoi apelul recursiv
pentru crearea subarborelui drept; daca numărul introdus este 0, atunci nodului
i se atribuie valoarea NULL. Funcția întoarce adresa nodului creat), stergere
(se apelează recursiv ștergerea pentru descendentul stâng; se apelează recursiv
ștergerea pentru descendentul drept;se șterge nodul curent); selectia câmpului
de date dintr-un nod si selectia descendentilor. Numarul maxim de noduri de pe
nivelul i al unui arbore binar este egal cu 2 la puterea (i-1). Numarul maxim
de noduri ale arborelui binar de adâncime h este egal cu 2 la puterea h,-1.
Strategii de
traversare a arborilor binari:
Parcurgerea arborelui binar – examinarea sistematica a nodurilor sale
astfel incit fiecare nod sa fie atins o singura data sau “vizitarea vârfurilor
unui arbore”
Scopul parcurgerii – prelucrarea informației asociate vârfurilor;
transformarea arborelui dintr-o reprezentare plana intr-o structura liniara.
Orice arbore binar are 3 componente: rădăcina, subarborele stâng si
subarborele drept.
Sunt 3 metode de parcurgere a arborelui:
Preordine (rsd): se vizitează rădăcina, se parcurge subarborele stâng, apoi
subarborele drept.
Postordine (sdr): se parcurge subarborele stâng, apoi subarborele drept, se
vizitează rădăcina.
Inordine (srd): se parcurge subarborele stâng, se vizitează rădăcina, se
parcurge subarborele drept. Exemplu: 1, 2 10, 3 8 11 12, 4 9 13 14, 5 6 15, 7
Traversarea
în Preordine: prelucrare în ordinea: rsd - 1 2 3 4 5
6 7 8 9 10 11 12 13 14 15
Traversarea
în Inordine: prelucrare în ordinea: srd - 5 4 6 7 3
2 8 9 11 10 13 12 15 14
Traversarea
în Postordine: prelucrare în ordinea: sdr - 5 7 6 4 3
9 8 2 11 13 15 14 12 10 1
Arbori
binari de căutare (BST).
Tabelele
Hashing - o alta solutie pentru a retine elementele din S. Complexitatea pentru
arborele binar de cautare in cazurile: cel mai favorabil O(n), mediu O(logn).
arbore binar de cautare - arbore T ale carui noduri sunt etichetate cu atomii
continuti la un moment dat în dictionar. r ∈ V (radacina arborelui), Ts - subarborele
stâng al radacinii si Td - subarborele drept al radacinii, atunci structura
acestui arbore este definita de urmatoarele proprietati: 1) ∀ nod x ∈ Ts atunci key(data(x)) <
key(data(r)); 2) ∀ x ∈ Td atunci key(data(x)) > key(data(r));
3) Ts si Td sunt BST.
Funcții:
Search
search(rad,k) // rad - pointer la
radacina arborelui
{ // k - cheia de cautare a
arborelui cautat
if (rad = 0) then return NULL
else
if key (data (rad)) > k then
return search (lchild (rad))
else
if key (data (rad)) < k then
return search (rchild (rad))
else return rad }
Insert
Se va crea un nod în arbore care va fi plasat la un nou nod terminal.
Pozitia în care trebuie plasat acesta este unic determinata în functie de
valoarea cheii de cautare
vom
insera 19 în arborele nostru:
insert(rad,a) // rad referinta la pointerul la radacina
// arborelui
{
if (rad= 0) then rad= make_nod(a)
else if key (data (rad)) >
key(a) then
insert(lchild(rad),a)
else if key (data(rad)) < key(a)then
insert (rchild (rad),a)
}
make_nod creaza un nou nod:
make_nod(a)
{
p= get_sp() // alocare de memorie pentru un nod nou
data(p)= a
lchild(p)= 0
rchild(p)= 0
return(p)
}
La inserarea unui atom deja existent în arbore, functia insert nu
modifica structura arborelui. Exista probleme în care este utila contorizarea
numarului de inserari a unui atom în arbore.
Functia insert poate returna pointer la radacina facând apeluri de forma
p= insert(p,a).
Delete
delete(rad,k) // rad - referinta
la pointer la radacina
{ // k - cheia de cautare a
atomului care trebuie sters de noi
if rad = 0 then
return // nodul cu cheia k nu se
afla în arbore
else if key(data(rad)) > k
then delete(lchild(rad),k)
else if key(data(rad)) < k then delete(rchild(rad),k)
else delete_root(rad)
}
Stergerea
radacinii unui BST:
rad ⇒ arbore
vid
2) a) rad sau b)
rad ⇒
a) SAS sau b)
SAD
/
\
SAS
SAD
delete_root(rad) // rad -
referinta la pointer la radacina
{
if lchild(rad)=0 then
p= rchild(rad)
ret_sp(rad)
rad= p
else if rchild(rad)= 0 then
p= lchild(rad)
ret_sp(rad)
rad= p
else p=
remove_greatest(lchild(rad))
lchild(p)= lchild(rad)
rchild(p)= rchild(rad)
ret_sp(rad)
rad= p
}
Detașarea
celui mai mic (mai mare nod) din arborele BST.
Pentru a gasi cel mai mare nod dintr-un arbore binar de cautare, se
înainteaza în adâncime pe ramura dreapta pâna se gaseste primul nod care nu are
descendent dreapta. Acesta va fi cel mai mare. Vom trata aceasta procedura
recursiv:
Caz1: rad ⇒ se returneaza pointer la radacina si
arborele rezultat va fi vid.
Caz2: rad ⇒ se returneaza pointer la radacina si
arborele rezultat va fi format doar din subarborele stâng.
Caz3: rad ⇒ functia returneaza pointer la cel mai
mare nod din SAD, iar rezultatul va fi SAS - arborele care este fomat din
radacina, SAS si SAD - cel mai mare nod.
remove_greatest(rad) //rad
-referinta la pointer la
//radacina: un pointer la radacina de poate fi modificat de catre
functie
{
if rchild (rad)= 0 then
p= rad
rad= lchild (rad)
return(p)
else return (remove_greatest (rchild(rad)))
}
Functia remove_greatest modifica arborele indicat de parametru, în
sensul eliminarii nodului cel mai mare, si întoarce pointer la nodul eliminat.
Complexitatea tuturor functiilor scrise depinde de adâncimea arborelui.
În cazul cel mai defavorabil, fiecare functie parcurge lantul cel mai lung din
arbore. Functia de cautare are, în acest caz, complexitatea O(n). Structura
arborelui BST este determinata de ordinea inserarii. De exemplu, ordinea 15 13
12 11 este alta decât 15 12 11 13 .
Crearea
unui BST pornind de la secvența de atomi.
Studiem un caz de complexitate medie:
gen_BST (va fi în programul
principal)
rad= 0
for i= 1 to n
insert (rad, ai)
Calculam complexitatea medie a generarii BST: ∑ (i)=O(n*n), i=[1,n]
Notam cu T(k) - numarul de comparatii mediu pentru crearea unui BST
pornind de la o secventa de k elemente la intrare. Ordinea celor k elemente se
considera aleatoare. Pentru problema T(n)
avem de creat secventa (a1 a2 ...
an) cu observatia ca a1 este radacina
arborelui. Ca rezultat, în urma primei operatii de inserare pe care o
facem, rezulta:
a1 –a1 (ai
-ai (ai>a1)
Consideram numarul de operatii globale. Dupa ce am inserat a1, pentru
inserarea fiecarui element în SAS sau SAD a lui a1, se face o comparatie cu a1.
T(n)=(n-1) + val.med.SAS + val.med.SAD
val.med.SAS = valoarea medie a numarului de comparatii necesar pentru a
construe subarborele stâng SAS
val.med.SAD = valoarea medie a numarului de comparatii necesar pentru a
construi subarborele drept SAD
T(n)=(n-1)+1/n*∑T(i-1)+1/n*∑T(n-1)
i=[1,n]; i=[i+1,n].
Ti(n) = numarul mediu de comparatii necesar pentru construirea unui BST
cu n noduri atunci când prima valoare inserata (a1) este mai mare decât i-1
dintre cele n valori de inserat. Putem scrie:
Ti(n)=(n-1)+T(i-1)+T(n-i)
T(n)+1/n*∑Ti(n)
Deci
T(n)=2/n*∑T(i); i=[0,n-1]
Complexitatea acestei functii este: O(n⋅ln n)
Arbore binar
de căutare dinamică echilibrat (AVL). Transformarea structurii arborelui după
înserare pentru a conserva proprietatea de arbore binar echilibrat:
Un arbore binar este echilibrat daca si numai daca, pentru fiecare nod din
arbore, diferenta dintre adâncimile SAS si SAD în modul este ≤ 1. Adâncimea
unui arbore echilibrat cu n noduri este O(ln n). Se completeaza operatiile
insert si delete cu niste prelucrari care sa pastreze proprietatile de arbore
binar echilibrat pentru arborele binar de cautare. Arborele binar echilibrat
este un BST echilibrat, proprietatea de echilibrare fiind conservata de insert
si delete. Efortul, în plus, pentru completarea operatiilor insert si delete nu
schimba complexitatea arborelui binar echilibrat. Transformarea structurii
arborelui dupa inserare pentru a conserva proprietatea de arbore binar
Echilibrat. Modificarile care se vor face se vor numi rotatii. în inserarea
prin rotatie se obtine un arbore echilibrat cu adâncimea egala cu adâncimea
arborelui de dinainte de inserare. La inserarea unui nod terminal într-un
arbore AVL este necesara aplicarea a cel mult o rotatie asupra unui nod.
Trebuie, deci sa gasim nodul asupra caruia trebuie aplicata rotatia. S-a notat
pentru fiecare nod bf - balance factor (factor de dezechilibrare):
bf(nod) = depth (lchild (nod)) - depth (rchild (nod))
Calculam factorii de balansare dupa inserare. Pentru nodul terminal s-a schimbat adâncimea
si factorul de balansare; bf = -2 dupa inserare
devine nod dezechilibrat. Trebuie aplicata, deci, echilibrarea. Se numeste
nod critic primul nod cu bf ≠ 0 întâlnit la o parcurgere de jos în sus a
ramurii care leaga nodul inserat de radacina. Toate nodurile din ramura care
sunt pe nivele inferioare nodului critic vor capata bf = 1 sau bf = -1. La nodul critic exista doua
situatii: 1. Nodul critic va fi perfect balansat (bf = 0), daca dezechilibrul
creat de nodul inserat anuleaza dezechilibrul initial al nodului. În acest caz
nu este nevoie de rotatie (el completeaza un gol în arbore). 2. Factorul de
balansare devine bf = 2 sau bf = -2 atunci când nodul inserat mareste
dezechilibrul arborelui (s-a inserat nodul în subarborele cel mai mare). În
acest caz, se aplica o rotatie în urma careia se schimba structura
subarborelui, astfel încât noua radacina capata bf = 0, conservându-se
adâncimea. Problema conservarii proprietatii de echilibrare a arborelui se
rezolva aplicând o rotatie asupra nodului critic numai atunci când inserarea
dezechilibreaza acest nod. Costul suplimentar care trebuie suportat se
materializeaza prin necesitatea ca în fiecare nod sa se memoreze factorul de
dezechilibrare bf. Acesti factori de dezechilibrare vor fi actualizati în urma
operatiilor de rotatie si inserare. Operatia de stergere într-un AVL implica
mai multe rotatii.
Structuri de
date elementare şi abstracte. Exemple (pe baza elementelor din teoria
grafurilor).
Gruparea mai multor date, de tipuri diferite, într-o singură entitate,
numită “structură” în C a permis definirea unor noi tipuri de date de către
programatori si utilizarea unor date dispersate în memorie, dar legate prin
pointeri: liste înlăntuite, arbori si altele. Astfel de colectii se pot extinde
dinamic pe măsura necesitătilor si permit un timp mai scurt pentru anumite
operatii, cum ar fi operatia de căutare într-o colectie. Limbajul C asigură
structurile de date fundamentale (vectori, pointeri, structuri) si
posibilitatea combinării acestora în noi tipuri de date, care pot primi si nume
sugestive prin declaratia typedef. Dintr-o perspectivă independentă de
limbajele de programare se pot considera ca structuri de date fundamentale
vectorii, listele înlăntuite si arborii, fiecare cu diferite variante de
implementare. Alte structuri de date se pot reprezenta prin combinatii de
vectori, liste înlăntuite si arbori. De exemplu, un tabel de dispersie (“Hash
table”) este realizat de obicei ca un vector de pointeri la liste înlăntuite
(liste de elemente sinonime). Un graf se reprezintă deseori printr-un vector de
pointeri la liste înlăntuite (liste de adiacente), sau printr-o matrice (un
vector de vectori în C).
Clasificarea structurilor de date:
Un criteriu de clasificare foloseste relatiile dintre elementele colectiei:
Colectii liniare (secvente,
liste), în care
fiecare element are
un singur succesor
si un singur predecesor;
Colectii arborescente (ierarhice), în care un element poate avea mai multi
succesori (fii), dar un singur predecesor (părinte);
Colectii neliniare generale, în care relatiile dintre elemente au forma
unui graf general (un element poate avea mai multi succesori si mai multi
predecesori). Un alt criteriu poate fi modul de reprezentare a relatiilor dintre
elementele colectiei:
Implicit, prin dispunerea lor în memorie (vectori de valori, vectori de
biti, heap);
Explicit, prin adrese de legătură (pointeri). Un alt criteriu grupează
diferitele colectii după rolul pe care îl au în aplicatii si după operatiile
asociate colectiei, indiferent de reprezentarea în memorie, folosind
notiunea de tip abstract de date. Astfel putem deosebi:
Structuri de căutare (multimi si dictionare abstracte);
Structuri de păstrare temporară a datelor (containere, liste, stive, cozi
s.a.) Un tip abstract de date este definit numai prin operatiile asociate (prin
modul de utilizare), fără referire la modul concret de implementare. Pentru
programele nebanale este utilă o abordare în (cel putin) două etape:
etapă de conceptie (de proiectare), care include alegerea tipurilor
abstracte de date si algoritmilor necesari; etapă de implementare (de
codificare), care include alegerea structurilor concrete de date, scrierea de
cod si folosirea unor functii de biblioteca. Problema alegerii unei structuri
de date eficiente pentru un tip abstract nu are o solutie unică, desi există
anumite recomandări generale în acest sens. Sunt mai multi factori care pot
influenta această alegere si care depind de aplicatia concretă. Exemplul cel
mai bun este al structurilor de date folosite atunci când sunt necesare căutări
frecvente într-o colectie de date după continut (după chei de căutare);
căutarea într-un vector sau într-o listă înlăntuită este ineficientă pentru un
volum mare de date si astfel au apărut tabele de dispersie (“hash table”),
arbori de căutare echilibrati, arbori B si alte structuri de date optimizate
pentru operatii de căutare. Alt exemplu este cel al algoritmilor folositi
pentru determinarea unui arbore de acoperire de cost minim al unui graf cu
costuri (Prim, Kruskal), care au o complexitate ce depinde de structurile de
date folosite. Eficienta unei anumite structuri este determinată de doi
factori: memoria ocupată si timpul necesar pentru operatiile frecvente. Mai des
se foloseste termenul de “complexitate”, cu
variantele “complexitate temporală” si “complexitate spatială”.
Algoritmi de
tipul Backtracking. Specificul problemelor care pot fi rezolvate cu ajutorul
Backtracking. Exemple.
Backtracking este numele unui algoritm general de descoperire a tuturor
soluțiilor unei probleme de calcul, algoritm ce se bazează pe construirea
incrementală de soluții-candidat, abandonând fiecare candidat parțial imediat
ce devine clar că acesta nu are șanse să devină o soluție validă. Problema
reginelor - cere să se găsească toate modurile în care pot fi așezate pe o
tablă de șah opt regine astfel încât să nu se atace. În abordarea backtracking,
candidatele parțiale sunt aranjamente de câte k regine pe primele k rânduri ale
tablei, toate pe rânduri și coloane diferite. Orice soluție parțială ce conține
două regine care se atacă poate fi abandonată, deoarece în mod clar restul de
regine nu pot fi așezate într-o soluție validă. Tehnica backtracking se poate
aplica doar pentru probleme ce admit conceptul de „candidat parțial de soluție”
și oferă un test relativ rapid asupra posibilității ca un astfel de candidat să
fie completat către o soluție validă. Când se poate aplica, însă,
backtrackingul este adesea mult mai rapid decât căutarea prin metoda forței
brute prin toți candidații, întrucât este capabilă să elimine dintr-un singur
test un mare număr de candidați. Backtrackingul este util la rezolvarea unor
probleme de satisfacere a constrângerilor, cum ar fi cuvintele încrucișate,
jocuri de sudoku și alte probleme similare. Ea stă la baza unei serii de
limbaje de programare logică, cum ar fi Icon, Planner și Prolog. Termenul
„backtrack” a fost inventat de matematicianul american D. H. Lehmer în anii
1950.
