Lista Subiecte SDA 2007-2008

Proeict la

Subiectul 1. Noiuni generale despre liste, stive, cozi, cozi complete. Subiectul 2. Liste simplu nlnuite. Creare i acces.Subiectul 3. Liste simplu nlnuite. Inserarea unui nod ntr-o list simplu nlnuitSubiectul 4. Liste simplu nlnuite. tergerea unui nod dintr-o list simplu nlnuit i tergerea listeiSubiectul 5. Stive i coziSubiectul 6. Liste circulare simplu nlnuite. Creare i acces la un nod.Subiectul 7. Liste circulare simplu nlnuite. Inserare i tergere nod i list.Subiectul 8. Liste dublu nlnuite. Creare i acces la nod.Subiectul 9. Liste dublu nlnuite. Inserare i tergere nod i list.Subiectul 10. Arbori. noiuni teoreticeSubiectul 11. Arbori. Drumul ntr-un arboreSubiectul 12. Traversarea arborilor binari. Generaliti i exempleSubiectul 13. Traversarea arborilor binari. Algoritmi de traversareSubiectul 14. Reprezentarea arborilor prin arbori binariSubiectul 15 Parcurgerea grafurilor n adncime

Subiectul 16 Sortarea topologic. Parcurgerea grafurilor n limeSubiectul 17 Grafuri AND/OR

Subiectul 19 Sortarea prin numrare

Subiectul 20 Sortarea prin inserieSubiectul 21 Metoda lui Shell

Subiectul 22 Sortarea prin interschimbareSubiectul 23 Sortarea prin selecieSubiectul 24 Sortarea prin interclasareSubiectul25Cutarea ntr-un tabel ordonatSubiectul 26 Cutarea de tip FibonacciSubiectul 27 Cutarea prin interpolare

Subiectul 28 METODA GREEDY//Subiectul 29Exemple de aplicare a metodei Greedy Subiectul 30 Algoritmul Greedy pentru colorarea unui grafSubiectul 31 ...?Subiectul 31 Algoritmul lui Kruskal

Subiectul 32Algoritmul lui PrimSubiectul 1.

Noiuni generale despre liste, stive, cozi, cozi complete.

Este important ca n cele ce urmeaz s se defineasc termeni i noiuni care vor fi n continuare frecvent utilizate, i anume:

- informaiile coninute ntr-un tabel constau dint-un set de noduri (nregistrri sau articole); se mai numesc i elemente;

- fiecare nod se compune din unul sau mai multe cuvinte consecutive din memoria calculatorului, fiind mprite n subpri componente denumite cmpuri;- n cazul cel mai simplu un nod este un singur cuvnt din memorie i are un singur cmp de lungime egal cu lungimea acestui cmp ntreg din memorie;

- adresa unui nod, denumit i pointerul sau referina acelui nod, reprezint locaia din memorie a primului cuvnt aparinnd nodului;

- coninutul oricrui cmp al unui nod poate reprezenta numere, caractere alfabetice, referine la alte noduri sau orice altceva dup necesitile de programare;

- pentru reprezentarea referinei nule se va folosi, n cele ce urmeaz, litera ;

- n memoria calculatorului va fi reprezentat printr-o valoare uor de recunoscut, care nu poate reprezenta adresa unui nod;

- introducerea de referine ctre alte elemente de date reprezint o idee deosebit de valoroas pentru programarea calculatoarelor; acesta constituie cheia reprezentrilor complexe;

- la ilustrarea reprezentrii n calculator a nodurilor este deseori convenabil ca referinele s fie reprezentate prin sgei:

NCEPUT

Figura 2.1. Reprezentarea intuitiv a referinelor- o referin nul poate fi ilustrat ca o punere la pmnt din schemele electrice. NCEPUT este o variabil tip referin numit i variabil pointer, adic o variabil n cadrul programului a crei valoare este o referin.

Definiia 2.2.1. O list linear este o colecie de noduri ale crei proprieti structurale se reduc n principal la poziiile relative lineare (unidimensionale) ale acestor noduri;

Dac este primul nod, pentru nodul este precedat de nodul i este urmat de este ultimul nod.

Principalele operaii care se execut asupra listelor lineare sunt urmtoarele:

accesul la nodul k din list pentru a examina sau modifica cmpurile sale;

inserarea unui nod naintea nodului k;

tergerea nodului k;

combinarea a dou sau mai multe liste n una singur;

desprirea unei liste lineare n una sau mai multe liste;

copierea unei liste lineare;

determinarea numrului de noduri ntr-o list;

sortarea nodurilor unei liste ntr-o ordine corespunztoare a coninuturilor anumitor cmpuri ale nodurilor;

cutarea n list a nodului cu o valoare particular a unui anumit cmp.

Listele lineare n care inserrile, tergerile i accesul la valori au loc aproape ntotdeauna la primul sau la ultimul nod sunt foarte frecvent ntlnite, purtnd i denumiri particulare (speciale).

Definiia 2.2.2. O stiv (stack) este o list linear n care toate inserrile sau tergerile sunt fcute la unul din capetele listei.

nceput

nodul II

nodul III

sfrit

Figura 2.2. Exemplu de stiv

Definiia 2.2.3. O coad (queue) este o list linear pentru care toate inserrile sunt fcute la unul din capetele listei; toate tergerile (i, de obicei, orice acces) sunt fcute la cellalt capt.

tergere

inserare

fa

nod 2

nod 3

spate

Figura 2.3. Exemplu de coad

Definiia 2.2.4. O coad complet (cu duble capete) este o list linear pentru care toate inserrile i tergerile (i, de obicei, orice acces) sunt fcute la ambele capete ale listei.

cel mai din

nod 2

nod 3 cel mai din

stnga

stnga

stnga

dreapta

inserare

inserare

sau

sau

tergere

tergere

Figura 2.4. Exemplu de coad complet.Subiectul 2.

Liste simplu nlnuite. Creare i acces.

Lista este o mulime finit i ordonat de elemente de acelai tip. Elementele listei se numesc noduri.

Listele pot fi organizate sub form static, de tablou, caz n care ordinea este implicit dat de tipul tablou unidimensional, sau cel mai des, sub form de liste dinamice, n care ordinea nodurilor este stabilit prin pointeri. Nodurile listelor dinamice sunt alocate n memoria heap. Listele dinamice se numesc liste nlnuite, putnd fi simplu sau dublu nlnuite.

n continuare se vor prezenta principalele operaii asupra listelor simplu nlnuite.

Structura unui nod este urmtoarea:

typedef struct tip_nod

{

int cheie; /* cmp neobligatoriu */

// alte cmpuri de date utile;

struct tip_nod *urm;

/* legtura spre urmtorul nod */

} TIP_NOD;

Modelul listei simplu nlnuite este prezentat n fig. 2.5.

Fig. 2.5. Model de list simplu nlnuit

Pointerii prim i ultim vor fi declarai astfel:

TIP_NOD *prim, *ultim;

1. Crearea unei liste simplu nlnuite

Crearea unei liste simplu nlnuite se va face astfel:

a) Iniial lista este vid:

prim = 0; ultim = 0;

b) Se genereaz nodul de introdus:

n=sizeof(TIP_NOD);

p=(TIP_NOD *) malloc(n);

/* rezervare spaiu de memorie n heap*/

/* citire date n nodul de adres p; */

c) Se fac legturile corespunztoare:

p->urm = 0;

/* nodul este ultimul n list */

if(ultim != 0) ultim->urm = p;

/* lista nu este vid */

else prim = p;

/* nodul p este primul introdus n list */

ultim=p;

2. Accesul la un nod al unei liste simplu nlnuite

n funcie de cerine, nodurile listei pot fi accesate secvenial, extrgnd informaia util din ele. O problem mai deosebit este gsirea unui nod de o cheie dat i apoi extragerea informaiei din nodul respectiv. Cutarea nodului dup cheie se face liniar, el putnd fi prezent sau nu n list.

O funcie de cutare a unui nod de cheie key va conine secvena de program de mai jos; ea returneaz adresa nodului respectiv n caz de gsire sau pointerul NULL n caz contrar:

TIP_NOD *p;

p=prim;

while( p != 0 )

if (p->cheie == key)

{

/* s-a gsit nodul de cheie dat */

/* el are adresa p */

return p;

}

else

p=p->urm;

return 0;/* nu exist nod de cheie = key */

Subiectul 3.

Liste simplu nlnuite. Inserarea unui nod ntr-o list simplu nlnuit

Nodul de inserat va fi generat dup structura urmtoarea:


{





} TIP_NOD;



ca la paragraful 2.2.1.1; se presupune c are pointerul p.

Dac lista este vid, acest nod va fi singur n list:

if (prim == 0)

{

prim=p; ultim=p; p->urm=0;

}

Dac lista nu este vid, inserarea se poate face astfel:

a) naintea primului nod

if(prim != 0)

{

p->urm = prim; prim = p;

}

b) dup ultimul nod:

if (ultim != 0)

{

p -> urm = 0; ultim -> urm = p; ultim = p;

}

c) naintea unui nod precizat printr-o cheie key:

c1) se caut nodul de cheie key:

TIP_NOD *q, *q1;

q1=0; q=prim;

while(q!=0)

{

if(q->cheie==key) break;

q1=q; q=q->urm;

}

c2)se insereaz nodul de pointer p, fcnd legturile corespunztoare:

if(q!=0)

{/*nodul de cheie key are adresa q */

if (q==prim)

{

p->urm=prim; prim=p;

}

else

{

q1->urm=p; p->urm=q;

}

}

d) dup un nod precizat printr-o cheie key:

d1)se caut nodul avnd cheia key:

TIP_NOD *q;

q=prim;

while(q!=0)

{

if(q->cheie==key) break;

q=q->urm;

}

d2) se insereaz nodul de adres p, fcnd legturile corespunztoare:if (q !=)0)

{ /* nodul de cheie key are adresa q */

p -> urm = q -> urm;

q -> urm=p;

if (q == ultim) ultim = p;

}

Subiectul 4.

Liste simplu nlnuite. tergerea unui nod dintr-o list simplu nlnuit i tergerea listei



{





} TIP_NOD;



1. tergerea unui nod.

La tergerea unui nod se vor avea n vedere urmtoarele probleme: lista poate fi vid, lista poate conine un singur nod sau lista poate conine mai multe noduri.

De asemenea se poate cere tergerea primului nod, a ultimului nod sau a unui nod dat printr-o cheie key. a) tergerea primului nod

TIP_NOD *p;

if(prim!=0)

{/* lista nu este vid */

p=prim; prim=prim->urm;

elib_nod(p);

/*eliberarea spaiului de memorie */

if(prim==0) ultim=0;

/* lista a devenit vid */

}

b) tergerea ultimului nod

TIP_NOD *q, *q1;

q1=0; q=prim;

if(q!=0)

{ /* lista nu este vid */

while(q!=ultim)

{

q1=q; q=q->urm;

}

if(q==prim)

{

prim=0; ultim=0;

}

else

{

q1->urm=0; ultim=q1;

}

elib_nod(q);

}

c) tergerea unui nod de cheie key

TIP_NOD *q, *q1;

/* cutare nod */

q1=0; q=prim;

while (q!=0)

{

if(q->cheie == key) break;

/* s-a gsit nodul */

q1=q; q=q->urm;

}

if(q != 0)

/*exist un nod de cheie key */

if (q == prim)

{

prim=prim_>urm;

elib_nod(q);

/*eliberare spaiu */

if( prim==0) ultim=0;

}

else

{

q1->urm=q->urm;

if(q==ultim) ultim=q1;

elib_nod(q);

/*eliberare spaiu */

}

2. tergerea unei liste simplu nlnuite

n acest caz, se terge n mod secvenial fiecare nod:

TIP_NOD *p;

while( prim != 0)

{

p=prim; prim=prim->ultim;

elib_nod(p);

/*eliberare spaiu de memorie */

}

ultim=0;

Subiectul 5. Stive i cozi

Stive.

Stiva este o list simplu nlnuit bazat pe algoritmul LIFO (Last In First Out), adic ultimul nod introdus este primul scos. Modelul stivei, este prezentat n fig.2.6.

Fig. 2.6. Model de stiv

Fiind o structur particular a unei liste simplu nlnuite, operaiile principale asupra unei stive sunt:

- push - pune un element pe stiv; funcia se realizeaz prin inserarea unui nod naintea primului;

if(prim != 0)

{

p->urm = prim; prim = p;

}

- pop - scoate elementul din vrful stivei; funcia se realizeaz prin tergerea primului nod;

TIP_NOD *p;

if(prim!=0)



elib_nod(p);




}

clear - tergerea stivei; funcia se realizeaz conform

TIP_NOD *p;

while( prim != 0)

{


elib_nod(p);


}

ultim=0;

n concluzie, accesul la o stiv se face numai pe la un capt al su.

Cozi

Coada este o list simplu nlnuit, bazat pe algoritmul FIFO (First In First Out), adic primul element introdus este primul scos. Modelul cozii care se are n vedere n consideraiile urmtoare, este prezentat n fig.2.7.

Fig.2.7. Model de coad

Deci coada are dou capete, pe la unul se introduce un element, iar de la celalalt capt se scoate un element.

Operaiile importante sunt:

- introducerea unui element n coad - funcia se realizeaz prin inserarea dup ultimul nod,

if (ultim != 0)

{

p -> urm = 0; ultim -> urm = p; ultim = p;

}

- scoaterea unui element din coad funcia se realizeaz prin tergerea primului nod,

TIP_NOD *p;

if(prim!=0)



elib_nod(p);




}

tergerea cozii funcia se realizeaz conform

TIP_NOD *p;

while( prim != 0)

{


elib_nod(p);


}

ultim=0;

Subiectul 6.

Liste circulare simplu nlnuite. Creare i acces la un nod.

Lista circular simplu nlnuit este lista simplu nlnuit a crei ultim element este legat de primul element; adic ultim -> urm = prim.

n cadrul listei circulare simplu nlnuite nu exist capete. Pentru gestionarea ei se va folosi un pointer ptr_nod, care adreseaz un nod oarecare al listei, mai precis ultimul introdus (fig.2.8).

Ca i la lista simplu nlnuit, principalele operaii sunt:

crearea;

accesul la un nod;

inserarea unui nod;

tergerea unui nod,

tergerea listei.



{

int cheie;

/* nu este obligatoriu acest cmp */

/*cmpuri;*/struct tip_nod *urm;

} TIP_NOD;

Crearea listei circulare simplu nlnuite

Iniial lista este vid:

ptr_nod = 0;

Introducerea n list a cte unui nod se va face astfel:

/* crearea nodului */

n = sizeof(TIP_NOD);/* dimensiunea nodului */

p = (TIP_NOD *)malloc(n); /* rezervarea memorie n heap */

citire date n nod la adresa p;

if (ptr_nod = = 0)

{ /* lista este vid */

ptr_nod = p;

ptr_nod -> urm = p;

}

else

{ /* lista nu este vid */

p -> urm = ptr_nod -> urm;

ptr_nod -> urm = p;

ptr_nod=p;/* ptr_nod pointeaz la ultimul nod inserat */

}

Accesul la un nod

Nodurile pot fi accesate secvenial plecnd de la nodul de pointer ptr_nod:

p=ptr_nod;

if(p! = 0)/* lista nu este vid */

do

{

acceseaaz nodul i preia informaia;

p = p -> urm;

}

while (p! = ptr_nod);

sau cutnd un nod de cheie dat key; n acest caz o funcie care va returna pointerul la nodul gsit va conine urmtoarea secven de program:

p = ptr_nod;

if (p! = 0)/* lista nu este vid */

do

{

if ( p -> cheie == key)

{


/* nodul are adresa p */

return p;

}

p = p -> urm;

}


return 0;

Subiectul 7.

Liste circulare simplu nlnuite. Inserare i tergere nod i list.

Inserarea unui nod

Se pun urmtoarele probleme:

- inserarea naintea unui nod de cheie dat;

- inserarea dup un nod de cheie dat.

n ambele cazuri se caut nodul de cheie dat avnd adresa q; dac exist un astfel de nod, se creeaz nodul de inserat de adres p i se fac legturile corespunztoare.

a) Inserarea naintea unui nod de cheie dat- se caut nodul de cheie dat (adresa sa va fi q):TIP_NOD *p,*q,*q1;

q = ptr_nod;

do

{

q1 = q; q = q -> urm;

if(q -> cheie == key ) break;


}

while (q! = ptr_nod);

- se insereaz nodul de adres p;

if (q -> cheie == key)

{

q1 -> urm = p; p -> urm = q;

}

b) Inserarea dup un nod de cheie dat- se caut nodul de cheie dat:

TIP_NOD *p,*q;

q = ptr_nod;

do

{

if (q -> cheie == key ) break;

q = q -> urm;

}

while(q!=ptr_nod);

- se insereaz nodul de adres p:

if (q -> cheie == key)

{

p -> urm =q -> urm;

q -> urm = p;

}

tergerea unui nod de cheie dat

tergerea unui nod de cheie dat key se va face astfel:

- se caut nodul de cheie dat:

q = ptr_nod;

do

{

q1 = q; q = q -> urm;

if (q -> cheie == key ) break;


}

while (q! = ptr_nod);

- se terge nodul, cu meniunea c dac se terge nodul de pointer ptr_nod, atunci ptr_nod va pointa spre nodul precedent q1:

if (q-> cheie == key)

{

if (q==q -> urm) ptr_nod==0;


else

{

q1 -> urm = q -> urm;

if (q == ptr_nod) ptr_nod = q1;

}

elib_nod(q);

}

tergerea listei

tergerea listei circulare simplu nlnuite se va face astfel:

p = ptr_nod;

do

{

p1 =p; p = p -> urm;

elib_nod(p1);

}


ptr_nod = 0;

Subiectul 8.

Liste dublu nlnuite. Creare i acces la nod.

Lista dublu nlnuit este lista dinamic ntre nodurile creia s-a definit o dubl relaie: de succesor si de predecesor. Modelul listei dublu nlnuite, pentru care se vor da explicaiile n continuare, este prezentat n figura 2.10.

Figura 2.10. Modelul listei circulare dublu nlnuite

Tipul unui nod dintr-o list dublu nlnuit este definit astfel:


{

cheie; /* nu este obligatoriu */

date;


/* adresa urmtorului nod */

struct tip_nod * prec;

/* adresa precedentului nod */

} TIP_NOD;

Ca i la lista simplu nlnuit, principalele operaii sunt:

crearea;

accesul la un nod;

inserarea unui nod;

tergerea unui nod,

tergerea listei.

Lista dublu nlnuit va fi gestionat prin pointerii prim i ultim:


prim -> prec = 0;

ultim -> urm = 0;

Crearea unei liste dublu nlnuite

Iniial lista este vid:

prim = 0; ultim = 0;

Dup alocarea de memorie i citirea datelor n nod, introducerea nodului de pointer n list se va face astfel:

if(prim= =0)

{ /* este primul nod n list */

prim = p; ultim = p;

p -> urm = 0; p -> prec = 0;

}

else


ultim -> urm = p; p -> prec = ultim;

p -> urm = 0; p -> prec = ultim;

ultim = p;

}

Accesul la un nod

Accesul la un nod se poate face:

- secvenial nainte (de la prim spre ultim):

p = prim;

while (p != 0)

{

vizitare nod de pointer p;

p = p -> urm;

}

- secvenial napoi ( de la ultim spre prim):

p = ultim;

while (p != 0)

{

vizitare nod de pointer p;

p = p -> prec;

}

- pe baza unei chei; cutarea unui nod de cheie dat key se va face identic ca la lista simplu nlnuit

TIP_NOD *p;

p=prim;

while( p != 0 )

if (p->cheie == key)

{

/* s-a gsit nodul de cheie dat el are adresa p */

return p;

}

else

p=p->urm;

return 0;/* nu exist nod de cheie = key */

Subiectul 9.

Liste dublu nlnuite. Inserare i tergere nod i list.

Inserarea unui nod ntr-o list dublu nlnuit se poate face astfel:

- naintea primului nod:

if (prim == 0)



p -> urm = 0; p -> prec = 0;

}

else

{ /* lista nu este vid /*

p -> urm =prim; p -> prec = 0;

prim -> prec = p; prim = p;

}

- dup ultimul nod:

if (prim == 0)



p -> urm = 0; p -> prec = 0;

}

else

{ /* lista nu este vid /*

p -> urm =0; p -> prec = ultim;

utim -> urm = p;

ultim = p;

}

- naintea unui nod de cheie dat key: dup cutarea nodului de cheie key, presupunnd c acesta exist i are adresa q, nodul de adres p va fi inserat astfel:

p -> prec = q -> prec; p -> urm = q;

if (q -> prec != 0) q -> prec -> urm = p;

q -> prec = p;

if (q == prim) prim = p;

- dup un nod de cheie dat key: dup cutarea nodului de cheie key, presupunnd c acesta exist i are adresa q, nodul de adres p va fi inserat astfel:

p -> prec = q; p -> urm = q -> urm;

if (q -> urm != 0) q -> urm -> prec = p;

q -> urm = p;

if (ultim == q) ultim = p;

tergerea unui nod

Exist urmtoarele cazuri de tergere a unui nod din list:

a) tergerea primului nod; acest lucru se poate face cu secvena de program:p = prim;

prim = prim -> urm;

/* se consider list nevid */

elib_nod(p); /* eliberarea nodului */

if (prim == 0) ultim = 0;


else prim -> prec = 0;b) tergerea ultimului nod:

p = ultim;

ultim = ultim -> prec;

/* se consider c lista nu este vid */

if (ultim == 0) prim = 0;


else ultim -> urm = 0;

elib_nod(p); /* tergerea nodului */

c) tergerea unui nod precizat printr-o cheie key. Presupunem c nodul de cheie key exist i are adresa p (rezult din cutarea sa):if ((prim == p) && (ultim = =p))

{ /* lista are un singur nod */

prim = 0;ultim = 0;

/*lista devine vid*/

elib_nod(p);/*tergere nod*

}

else if(p == prim)

{ /* se terge primul nod */

prim = prim -> urm; prim -> prec =0;

elib_nod(p);

}

else if (p == ultim)

{ /* se terge ultimul nod */

ultim = ultim -> prec;

ultim -> urm = 0;

elib_nod(p)

}

else

{/*nodul de ters este diferit de capete */

p -> urm -> prec = p -> prec;

p -> prec -> urm = p -> urm;

elib_nod(p);

}

tergerea listei

tergerea ntregii liste se realizeaz tergnd nod cu nod astfel:

TIP_NOD *p;

while (prim != 0)

{

p = prim; prim = prim -> urm;

elib_nod(p);

}

ultim = 0;

Subiectul 10.

ARBORI. NOIUNI TEORETICE

Structurile arborescente sunt cele mai importante structuri nelineare ce intervin n algoritmii de prelucrare.

Definiia 4.1.1. Un arbore este o mulime TT de noduri n care:

a) unul din noduri (de obicei, notat T) se numete tulpin (rdcina) i are o destinaie special;

b) restul nodurilor se mpart ntr-un numr de clase disjuncte, iar fiecare asemenea clas este un arbore.

Observaii:

1. Aceast definiie este recursiv, adic s-a definit un arbore n funcie de un arbore.

2. Aici nu se pune problema de circularitate, deoarece arborii cu un singur nod vor consta numai din tulpin.

3. Definiia recursiv pare cea mai potrivit, deoarece recursivitatea reprezint o caracteristic normal a structurilor arborescente.

Definiia 4.1.2. Numrul ramurilor aparinnd unui nod reprezint gradul acelui nod.

Definiia 4.1.3. Un nod de gradul 0 se numete nod terminal sau frunz.

Definiia 4.1.4. Un nod neterminal se numete nod de ramificare.

Definia 4.1.5. Nivelul unui nod n raport cu tulpina (T) se definete prin convenia c tulpina are nivelul 1, iar celelalte noduri au nivelele cu 1 mai mari dect nivelul lor n raport cu subarborele tulpinei , care le conine.

Fie un drum de la x la y. Exist un drum simplu de la x la y. S reamintim c dac G este un graf cu vrfuri i dac x i y sunt vrfuri n G, se spune c este un drum de lungime n de la x la y, dac , este adiacentul lui pentru i .

Drumul este simplu dac sunt distincte.

( nivelul 1

( nivelul 2

( nivelul 3

( nivelul 4

Figura 4.1 Exemplu de arboreDin punct de vedere al echivalenei a doi arbori este de mare importan caracterul ordonat sau neordonat al celor doi arbori.

Astfel, arborii din figura 4.2 sunt echivaleni n cazul n care i sunt neordonai i nu sunt echivaleni n cazul n care cei doi arbori sunt ordonai.

A1

A2

Figura 4.2 Arbori echivaleni sau nuO deosebit importan o au arborii ordonai de ordinul doi, denumii arbori binari.

EXEMPLE DE UTILIZRI ALE ARBORILOR

a) Formulele algebrice constituie un exemplu de structur arborescent. Astfel, formulelor

i

(1)

li se pot ascocia arborii reprezentai mai jos:

Figura 4.3 Arbori asociai formulelor (1)

Subiectul 11.

ARBORI. DRUMUL NTR-UN ARBORE

Definiia 4.4.1. Prin drum ntr-un arbore de la nodul p la nodul q vom nelege o succesiune de sgei care au pe p ca domeniu al primei sgei i pe q codomeniu al ultimei sgei a succesiunii.

Fiind dat un arbore a i nodurile p i q n acest arbore, un drum de la p la q se poate construi dup urmtorul algoritm:

Algoritmul 4.4.1:

Pasul P1:Fie subarborii arborelui care are nodul p drept rdcin. Atunci q este un nod ntr-unul dintre arborii sau q nu aparine nici unuia dintre aceti arbori. n acest ultim caz nu exist nici un drum de la p la q n arborele dat. n primul caz, fie subarborele care conine nodul q.

Pasul P2:Dac q este rdcin a arborelui , atunci drumul cutat este . Dac q nu este rdcin a arborelui , atunci fie rdcina lui i subarborii lui . Nodul q se gsete ntr-unul din aceti arbori, fie el . Dac q este rdcina lui , atunci drumul cutat este .

Dac q nu este rdcina lui , atunci fie rdcina lui , i subarborii lui . Nodul q este o rdcin sau un nod diferit de rdcin ntr-unul din aceti arbori.

Pasul P3:Dup un numr finit de pai P1 i P2, avnd n vedere c arborele este o mulime finit de puncte, se ajunge la situaia n care q este rdcina unui subarbore i atunci drumul de la p la q este .

Observaie.

Din algoritmul de construire a drumului de la nodul p la nodul q n arborele a rezult c ntre cele dou noduri p i q ale unui arbore a exist cel mult un drum n subarborele respectiv. Lungimea drumului, precum i nodurile lui p pot fi deduse cu ajutorul algoritmului matriceal, asociind fiecrui arc lungimea 1.

Legenda variabilelor folosite n pseudocodul corespunztor algoritmului:

a = arborele n care se caut drumul;

p,q = cele dou noduri;

rad = nodul pentru care se determin subarborii;

drum[i] = ir care conine nodurile ce compun drumul;

nrnod = numrul de noduri ale drumului;

nod[i] = subarborele i al nodului rad;

T(nod[i]) = nodul rdcin al subarborelui i;

S(nod[i]) = mulimea tuturor nodurilor subarborelui i.

Pseudocodul corespunztor algoritmului precedent este urmtorul:

* citetea, p, q;

rad = p;

nrnod = 1;

drum[nrnod] = p;

repet

*determin nod[1],,nod[m];

indice = 0;

pentru i = 1,m execut

dac atunci

indice = i

dac indice = 0 atunci

* tiprte drum inexistent;

nrnod = nrnod + 1;

drum[nrnod] = T(nod[indice]);

rad = T(nod[indice]);

pn cnd q = rad

* scrie drum[i], i = 1, nrnod;

sfrit.

Subiectul 12.

Traversarea arborilor binari. Generaliti i exemple

Definiia 4.5.1. Un arbore binar poate fi definit ca fiind o mulime finit de noduri care este fie vid, fie este format dintr-o tulpin (rdcin) i doi arbori binari.

Aceast definiie sugereaz o cale natural de a reprezenta arborii binari n codul calculatoarelor.

Pot exista dou referine LLINK i RLINK n cadrul fiecrui nod i o variabil de tip referin T care este un pointer de arbore. Dac un arbore este vid, atunci ; n caz contrar, T este adresa tulpinei arborelui, iar LLINK(T) i RLINK(T) sunt pointeri la arborele din stnga, respectiv din dreapta tulpinei.

Aceste reguli definesc recursiv reprezentarea n memorie a oricrui arbore binar.

Traversarea unui arbore binar reprezint o metod de a examina nodurile unui arbore n mod sistematic, astfel nct fiecare nod s fie vizitat o singur dat.

Exemplu:

--

-- -- -- -- -- --

Figura 4.4 Reprezentarea unui arbore binar

Observaie. O traversare complet a arborelui va conduce la o aranjare linear a nodurilor.

Se pot folosi trei ci principale de traversare a arborilor binari:

n preordine denumit TSD;

n inordine denumit STD;

n postordine denumit SDT.

Traversarea n preordine:

se viziteaz tulpina;

se viziteaz subarborele din stnga;

se viziteaz subarborele din dreapta.

Traversarea n inordine:

se traverseaz subarborele din stnga;

se viziteaz tulpina;

se traverseaz subarborele din dreapta.

Traversarea n postordine:

se traverseaz subarborele din stnga;

se traverseaz subarborele din dreapta;

se viziteaz tulpina.

Dac se aplic cele trei ci de traversare a arborelui reprezentat anterior, se obine:

pentru traversare n preordine: A B C D E F;

pentru traversare n inordine: D B A E C F;

pentru traversare n postordine: D B E F C A.

Regula mnemonic presupune folosirea notaiilor cu paranteze n reprezentarea arborilor.

Fie arborele urmtor:

Figura 4.5 Un exemplu de arbore folosit pentru exemplificarea unei traversri

Folosim urmtoarea notaie pentru a exprima structuri de arbori folosind paranteze n paranteze:

(A (B, C(K)), D ( E (H), F (J), G)).

n acest caz dac se efectueaz o traversare n preordine,se vor vizita nodurile n ordinea lor natural, nlturnd parantezele i virgulele: A B C K D E H F J G.

Fie acum arborele binar din figura 4.6.

Figura 4.6. Arbore binar

n notaia cu paranteze, acest arbore binar poate fi reprezentat astfel:

.

Traversare n preordine:

.

Traversare n postordine:

se scrie reprezentarea anterioar astfel:

i se obine: a b * c + d e f / - *

Traversare n inordine:a * b + c * d e / f.

Subiectul 13.

Traversarea arborilor binari. Algoritmi de traversare

Algoritmul 4.5.3: Travesarea n inordine a unui arbore binar.

Fie T un pointer spre un arbore binar. Algoritmul urmtor realizeaz parcurgerea tuturor nodurilor arborelui binar n inordine, folosind o stiv A.

Pasul 1 (iniializare):

(stabilire A vid)

.

Pasul 2 (testeaz dac ):

Dac treci la Pasul 4 altfel treci la Pasul 3.

Pasul 3 ():

Se stabilete:

(se insereaz nodul P n stiva A)

LLINK(P)

i se revine la Pasul 2.

Pasul 4: Dac stiva este vid () atunci STOP.

Dac nu, se stabilete:

(nodul din vrful stivei trece n P).

Pasul 5 (vizitarea lui P):

Se viziteaz NOD(P)

Se stabilete

RLINK(P)

i se revine la Pasul 2.

Pseudocodul algorirmului 4.5.3 este:

repet

dac atunci

dac atunci

altfel

*extrage (P,A);

*viziteaz (P);

RLINK(P);

altfel

*insereaz (P,A);

LLINK(P);

pn cnd ;

sfrit.

Traversarea unui arbore binar n preordine

Pentru a realiza un algoritm de treversare a unui arbore binar n preordine, se va face urmtoarea modificare n algoritmul anterior: vizitarea nodului P se va face ntre paii P2 i P3, i nu ntre paii P4 i P2.

Astfel, algoritmul scris n pseudocod pentru traversarea arborilor binari n preordine arat astfel:

repet

dac atunci

dac atunci

altfel

*extrage (P, A);

RLINK(P);

altfel

*insereaz (P, A);

*viziteaz (P);

LLINK(P);

pn cnd ;

sfrit.

Legenda variabilelor folosite n cei doi algoritmi este urmtoarea:

- codsf = variabila care indic terminarea procesului de parcurgere, atunci cnd are valoarea 1;

- va = vrful stivei A;

- A = stiva (simulat printr+un vector);

- P = variabila de lucru, care face referirea la nodul curent;

- T = variabila care reprezint un pointer la rdcina arborelui.

O valoare -1 n stiv sau ntr-o alt variabil semnific faptul c stiva este vid, respectiv arborele care are ca pointer variabila cu valoarea -1 este vid.

Subiectul 14.

REPREZENTAREA ARBORILOR PRIN ARBORI BINARiDiferenele dintre arbori i arborii binari sunt:

1) un arbore nu este niciodat vid, adic el are cel puin un nod; fiecare nod al unui arbore poate avea 0, 1, .... , n fii;

2) un arbore binar poate fi vid i fiecare nod al su poate avea 0, 1 sau 2 fii; se face distincie ntre un fiu din stnga i un fiu din dreapta.

Se reamintete c o pdure reprezint o mulime ordonat de zero sau mai muli arbori.

Subarborii existeni imediat sub un nod oarecare al unui arbore formeaz un arbore.

Exist o cale naural de reprezentare a unei pduri ca un arbore binar; arborele binar se obine prin legarea mpreun a fiilor fiecrei familii i se nltur legturile verticale, cu excepia legturii de la tat la primul su fiu.

De exemplu, fie pdurea:

Figura 4.7 Exemplu de pdureConform regulii de mai sus, arborele binar corespunztor este:

Figura 4.8 Arbore binar corespunztor pdurii anterioareTransformarea de mai sus este foarte important; ea poart denumirea de coresponden natural ntre pduri i arbori binari.

Prin nclinarea diagramei de mai sus cu se obine:

Figura 4.9 Arbore binar nclinat Subiectul 15Parcurgerea grafurilor n adncime

Fie G = un graf orientat sau neorientat, ale crui vrfuri dorim s le consultm. Presupunem c avem posibilitatea s marcm vrfurile deja vizitate n tabloul global marca. Iniial, nici un vrf nu este marcat.

Pentru a efectua o parcurgere n adncime, alegem un vrf oarecare, vV, ca punct de plecare i l marcm. Dac exist un vrf w adiacent lui v (adic, dac exist muchia (v,w) n graful orientat G, sau muchia {v,w} n graful neorientat) care nu a fost vizitat, alegem vrful w ca noul punct de plecare i apelm recursiv procedura de parcurgere n adncime. La ntoarcerea din apelul recursiv, dac exist un alt vrf adiacent lui v care nu a fost vizitat, apelm din nou procedura etc. Cnd toate vrfurile adiacente lui v au fost marcate, se ncheie consultarea nceput n v. Dac au rmas vrfuri n V care nu au fost vizitate, alegem unul din aceste vrfuri i apelm procedura de parcurgere. Continum astfel, pn cnd toate vrfurile din V au fost marcate. Iat algoritmul:

procedure parcurge(G)

for fiecare vV do marca[v]nevizitat

for fiecare vV do

if marca[v]= nevizitat then ad(v)

procedure ad(v)

{virful v nu a fost vizitat}

marca[v]nevizitat

for fiecare virf w adiacent lui v do

if marca[w]= nevizitat then ad(w)

Acest mod de parcurgere se numete n adncime, deoarece ncearc s iniieze ct mai multe apeluri recursive nainte de a se ntoarce dintr-un apel. Parcurgerea n adncime a fost formulat cu mult timp n urm, ca o tehnic de explorare a unui labirint. O persoan care caut ceva ntr-un labirint i aplic aceasta tehnic are avantajul c urmtorul loc n care caut este mereu foarte aproape.

(a)

(b)

Figura 9.1 Un graf neorientat i unul din arborii si parialiPentru graful din figura 9.1(a), presupunnd c pornim din vrful 1 i c vizitm vecinii unui vrf n ordine numeric, parcurgerea vrfurilor n adncime se face n ordinea: 1, 2, 3, 6, 5, 4, 7, 8.

Desigur, parcurgerea n adncime a unui graf nu este unic; ea depinde att de alegerea vrfului iniial, ct i de ordinea de vizitare a vrfurilor adiacente. Ct timp este necesar pentru a parcurge un graf cu n vrfuri i m muchii?

Deoarece fiecare vrf este vizitat exact o dat, avem n apeluri ale procedurii ad. n procedura ad, cnd vizitm un vrf, testm marcajul fiecrui vecin al su. Dac reprezentm graful prin liste de adiacen, adic prin ataarea la fiecare vrf a listei de vrfuri adiacente lui, atunci numrul total al acestor testri este: m, dac graful este orientat, i 2m, dac graful este neorientat. Algoritmul necesit un timp n ((n) pentru apelurile procedurii ad i un timp n ((m) pentru inspectarea mrcilor. Timpul de execuie este deci n ((max(m,n))=((m+n).

Dac reprezentm graful printr-o matrice de adiacen, se obine un timp de execuie n ((n2).

Parcurgerea n adncime a unui graf G, neorientat i conex, asociaz lui G un arbore parial. Muchiile arborelui corespund muchiilor parcurse n G, iar vrful ales ca punct de plecare devine rdcina arborelui. Pentru graful din figura 9.1(a), un astfel de arbore este reprezentat n figura 9.1(b) prin muchiile continue; muchiile din G care nu corespund unor muchii ale arborelui sunt ntrerupte. Dac graful G nu este conex, atunci parcurgerea n adncime asociaz lui G o pdure de arbori, cte unul pentru fiecare component conex a lui G.

Dac dorim s i marcm numeric vrfurile n ordinea parcurgerii lor, adugm n procedura ad, la nceput:

num num + 1

preord[v] num unde num este o variabil global iniializat cu zero, iar preord[1,..,n] este un tablou care va conine n final ordinea de parcurgere a vfurilor. Pentru parcurgerea din exemplul precedent, acest tablou devine:12345678

Subiectul 16Sortarea topologic. Parcurgerea grafurilor n lime

n aceast seciune, vom arta cum putem aplica parcurgerea n adncime a unui graf, ntr-un procedeu de sortare esenial diferit fa de sortrile ntlnite pn acum. S presupunem c reprezentm diferitele stagii ale unui proiect complex printr-un graf orientat aciclic: vrfurile sunt strile posibile ale proiectului, iar muchiile corespund activitilor care se cer efectuate pentru a trece de la o stare la alta.

Figura 9.2 d un exemplu al acestui mod de reprezentare. O sortare topologic a vrfurilor unui graf orientat aciclic este o operaie de ordonare liniar a vrfurilor, astfel nct, dac exist o muchie (i,j), atunci i apare naintea lui j n aceast ordonare.

preparat

but

cafea

cafea

trezire duul

mbrcare plecare

Figura 9.2 Un graf orientat aciclicPentru graful din figura 9.2, o sortare topologic este A,B,C,E,D,F, iar o alta este A,B,E,C,D,F. n schimb, secvena A,B,C,D,E,F nu este n ordine topologic.

Dac adugm la sfritul procedurii ad linia:

write v atunci procedura de parcurgere n adncime va afia vrfurile n ordine topologic invers. Pentru a nelege de ce se ntmpl acest lucru, s observm c vrful v este afiat dup ce toate vrfurile ctre care exist o muchie din v au fost deja afiate.

Parcurgerea grafurilor n lime

Procedura de parcurgere n adncime, atunci cnd se ajunge la un vrf v oarecare, exploreaz prima dat un vrf w adiacent lui v, apoi un vrf adiacent lui w etc.

Pentru a efectua o parcurgere n lime a unui graf (orientat sau neorientat), aplicm urmtorul principiu: atunci cnd ajungem ntr-un vrf oarecare v nevizitat, l marcm i vizitm apoi toate vrfurile nevizitate adiacente lui v, apoi toate vfurile nevizitate adiacente vrfurilor adiacente lui v etc. Spre deosebire de parcurgerea n adncime, parcurgerea n lime nu este n mod natural recursiv.

Pentru a putea compara aceste dou tehnici de parcurgere, vom da pentru nceput o versiune nerecursiv pentru procedura ad. Versiunea se bazeaz pe utilizarea unei stive. Presupunem c avem funcia ftop care returneaz ultimul vrf inserat n stiv, fr s l tearg. Presupunem date i funciile push (care adaug nodul v n stiva S) i pop (care terge ultimul nod din stiv i l returneaz). procedure iterad(v)

S stiva vida

marca[v] vizitat

push(v,S)

while S nu este vida do

while exista un varf w adiacent lui ftop(S)

astfel incat marca[w] = nevizitat do

marca[w] vizitat

push(w,S)

pop(S)

Pentru parcurgerea n lime, vom utiliza o coad i funciile insert-queue (adaug nodul v n capul cozii C), delete-queue (terge nodul din coada listei i l returneaz). Iat acum algoritmul de parcurgere n lime:

procedure lat(v)

C coada vida

marca[v] vizitat insert-queue(v,C)

while C nu este vida do

u delete-queue(C)

for fiecare vrf w adiacent lui u do

if marca[w] = nevizitat then

marca[w] vizitat

insert-queue(w, C)

Procedurile iterad i lat trebuie apelate din procedura:

procedure parcurge(G)

for fiecare vV do marca[v] nevizitat

for fiecare vV do

if marca[v]=nevizitat then

{iterad sau lat}(v)

De exemplu, pentru graful din figura 9.1, ordinea de parcurgere n lime a vrfurilor este: 1,2,3,4,5,6,7,8.

Ca i n cazul parcurgerii n adncime, parcurgerea n lime a unui graf G conex asociaz lui G un arbore parial. Dac G nu este conex, atunci obinem o pdure de arbori, cte unul pentru fiecare component conex.

Analiza eficienei algoritmului de parcurgere n lime se face la fel ca pentru parcurgerea n adncime. Pentru a parcurge un graf cu n vrfuri i m muchii timpul este n:

i)((m+n), dac reprezentm graful prin liste de adiacen;

ii)((n2), dac reprezentm graful printr-o matrice de adiacen. Parcurgerea n lime este folosit de obicei atunci cnd se exploareaz parial anumite grafuri infinite, sau cnd se caut cel mai scurt drum dintre dou vrfuri.

Subiectul 17Grafuri AND/OR Multe probleme se pot descompune ntr-o serie de subprobleme, astfel nct rezolvarea tuturor acestor subprobleme, sau a unora din ele, s duc la rezolvarea problemei iniiale. Descompunerea unei probleme complexe, n mod recursiv, n subprobleme mai simple poate fi reprezentat printr-un graf orientat. Aceast descompunere se numete reducerea problemei i este folosit n demonstrarea automat, integrarea simbolic i, n general, n inteligena artificial. ntr-un graf orientat de acest tip vom permite unui vrf oarecare neterminal v dou alternative.

Vrful v este de tip AND dac reprezint o problem care este rezolvat doar dac toate subproblemele reprezentate de vrfurile adiacente lui v sunt rezolvate. Vrful v este de tip OR dac reprezinta o problem care este rezolvat doar dac cel puin o subproblem reprezentat de vrfurile adiacente lui v este rezolvat. Un astfel de graf este de tip AND/OR. De exemplu, arborele AND/OR din figura 9.5 reprezint reducerea problemei A. Vrfurile terminale reprezint probleme primitive, marcate ca rezolvabile (vrfurile albe), sau nerezolvabile (vrfurile galbene). Vrfurile neterminale reprezint probleme despre care nu se tie a priori dac sunt rezolvabile sau nerezolvabile.

Figura 9.5 Un arbore AND/OR

Vrful A este un vrf AND (marcm aceasta prin unirea muchiilor care pleac din A), vrfurile C i D sunt vrfuri OR. S presupunem acum c dorim s aflm dac problema A este rezolvabil. Deducem succesiv c problemele C, D i A sunt rezolvabile.

ntr-un arbore oarecare AND/OR, urmtorul algoritm determin dac problema reprezentat de un vrf oarecare u este rezolvabil sau nu. Un apel sol(u) are ca efect parcurgerea n postordine a subarborelui cu rdcina n u i returnarea valorii true, dac i numai dac problema este rezolvabil.

function sol(v)

case

v este terminal: if v este rezolvabil

then return true

else return false v este un virf AND: for fiecare virf w

adiacent lui v do

if not sol(w)

then return false

return true

v este un virf OR: for fiecare virf wadiacent lui v do

if sol(w)

then return true

return false

Dac n timpul explorrii se poate deduce c un vrf este rezolvabil sau nerezolvabil, se abandoneaz explorarea descendenilor si. Printr-o modificare simpl, algoritmul sol poate afia strategia de rezolvare a problemei reprezentate de u, adic subproblemele rezolvabile care conduc la rezolvarea problemei din u.

Cu anumite modificri, algoritmul se poate aplica asupra grafurilor AND/OR oarecare. Similar cu tehnica backtracking, explorarea se poate face att n adncime (ca n algoritmul sol), ct i n lime.

Subiectul 19

Sortarea prin numrare

Aceast metod se bazeaz pe ideea c, n secvena final sortat a cheie este mai mare dect a din celelalte chei. Metoda const n compararea fiecrei perechi de chei, numrnd cte vor fi mai mici dect fiecare cheie particular. Calea evident de a face comparaiile const n: compar cu , pentru .

Se observ ns c peste jumtate din aceste comparaii sunt redundante, nefiind necesar a se compara o cheie cu ea nsi i apoi nu e necesar s se compare . vom avea nevoie numai de a compara cu , pentru i . Aceasta conduce la urmtorul algoritm:

Algoritmul 5.1.3.1. Sortarea prin numrare

Acest algoritm va sorta dup cheile , prin intermediul unui tabel auxiliar COUNT(1),..., COUNT(n), pentru a numra cte chei sunt mai mici dect o cheie dat.

Dup terminarea algoritmului, COUNT(j)+1 va specifica poziia final a nregistrrii .

Pasul P1: (terge COUNT-urile):pune COUNT(1) pn la COUNT(N) pe zero.

Pasul P2: (cicleaz dup i):execut pasul P3 pentru apoi termin algoritmul.

Pasul P3: (cicleaz dup j):execut pasul P4 pentru .

Pasul P4: (compar cu ):Dac incrementeaz COUNT(j) cu 1;

altfel incrementeaz COUNT(i) cu 1.

Algoritmul este similar cu o sortare prin tabel de adrese i nu compar nici o deplasare de nregistrri. Acest algoritm furnizeaz rezultatul corect, indiferent de numrul de chei egale care sunt prezentate. Pseudocodul corespunztor acestui algoritm este:

* procedura SORTNUM (n, k, COUNT) este

pentru i =1,2,, N execut

COUNT(i) = 0

SYMBOL 168 \f "Wingdings"

pentru i =N,, 2 execut

pentru , ,2,1 execut

dac atunci

COUNT(j) = COUNT (j) + 1

altfel

COUNT(i) = COUNT (i) + 1

SYMBOL 168 \f "Wingdings"SYMBOL 168 \f "Wingdings"

scrie (COUNT(i), )

sfrit.

Dac vom considera c pentru execuia fiecrei operaii este necesar o unitate de timp calculator, atunci timpul total de rulare al acestui program va fi:

.

Factorul N care apare n relaia de mai sus arat c algoritmul de sortare prin numrare nu este o cale eficient n cazul n care N este mare.

Deoarece metoda solicit compararea tuturor perechilor de chei distincte , nu exist aparent nici o posibilitate de a reduce timpul de rulare.

Totui, algoritmul prezint interes prin simplitatea sa, i nu prin eficien.

Numrarea distribuiilor

Algoritmul 5.1.3.2. Numrarea distribuiilor.

considerm c toate cheile sunt ntregi n domeniul

Acest algoritm va sorta nregistrrile , utiliznd un tabel auxiliar: COUNT(u),..., COUNT(v). La terminarea algoritmului nregistrrile sunt deplasate ntr-o zon de ieire n ordinea dorit.

pasul P1: (terge COUNT-urile):

pune COUNT(u) pn la COUNT(v) pe zero.

pasul P2: (cicleaz dup j):

se execut pasul P3 pentru apoi se merge la pasul P4.

pasul P3: (mrete COUNT()):

se mrete valoarea lui COUNT() cu 1.

pasul P4: (acumuleaz):

(n acest moment COUNT(i) va fi egal cu numrul de chei ce sunt

egale cu i)

pune pentru


(n acest moment COUNT(i) va fi egal cu numrul de chei ; n particular, COUNT(v) = N).

execut pasul P6 pentru .

pasul P6: (ieirea ):

pune

.

Subiectul 20

Sortarea prin inserie

nainte de a examina nregistrarea vom considera c nregistrrile precedente au fost deja sortate, apoi vom insera n locul ce-irevine ntre nregistrrile sortate anterior.Inseria direct

Sortarea cea mai simpl prin inserie este i cea mai evident. Se consider i nregistrrile precedente aranjate astfel nct:

.

Vom compara pe rnd noua cheie cu , pn vom descoperi c trebuie inserat ntre nregistrrile ; apoi deplasm nregistrrile cu un spaiu i introducem noua nregistrare n poziia . Din cele descrise anterior obinem:

Algoritmul 5.1.4.1. sortarea prin inserie direct

nregistrrile sunt rearanjate pe locurile lor; dup sortare, cheile vor fi n ordinea .


Execut paii P2-P5 pentru j = 2,...,N, apoi termin algoritmul.

pasul P2: (Fixeaz i, k, r):

Pune

n paii urmtori vom ncerca s inserm R n poziia corect,comparnd K cu pentru valori descresctoare ale lui i.

pasul P3: (Compar K, ):

Dac mergi la pasul P5 (s-a gsit poziia corespunztoarepentru R).

pasul P4: (deplaseaz , descrete i):

Pune

, apoi

i mergi la pasul P3.

(Dac i = 0, atunci K va fi cea mai mic cheie gsit pn acum,deci R va trebui plasat pe poziia 1).

pasul P5: (R n ):

Pune

.

Pseudocodul corespunztor algoritmului de mai sus este prezentat n continuare:

procedura sortinsdir (N,K) este

pentru j = 2,, N execut

scrie ;

;

repet

dac atunci

;

;

SYMBOL 168 \f "Wingdings" pn cnd i = 0 sau ;

;

SYMBOL 168 \f "Wingdings"

sfrit.Analiza stocastic a algoritmuluiPresupunnd c pentru fiecare operaie este necesar o unitate de timp calculator, timpul total de rulare a acestei rutine este:

u.t., unde:

A = numrul de cazuri n care i descrete la zero;

B = numrul de deplasri ale nregistrrii cu un pas; B este egal cu numrul de inversiuni ale permutrii:

.

Vom avea deci:

;

;

;

;

ordonate cresctor;

ordonate cresctor;

;

.

Rezult c timpul total T este

.

Pentru n suficient de mare putem aproxima:

.

Dac nregistrrile sunt parial ordonate, crete i deci timpul de rulare scade. Termenul este ns dominant.

Totui, algoritmul de sortare prin inserie direct este mult mai eficient dect algoritmul de sortare prin numrare, datorit faptului c nu exist compararea tuturor perechilor diferite de chei. Algoritmul prezint interes pentru eficiena sa raportat la simplitatea sa deosebit.

Subiectul 21Metoda lui ShellDac vrem s mbuntim substanial inseria direct, avem nevoie de un mecanism prin intermediul cruia nregistrrile s efectueze salturi lungi, n loc de pai mici. O asemenea metod a fost propu s de Donald L. Shell n 1959 i va fi denumit sortare cu micorarea incrementului.

Algoritmul 5.1.4.2. Metoda lui Shell:

- nregistrrile sunt rearanjate pe loc;

- dup terminarea sortrii cheile lor vor fi n ordinea ;

- o secven auxiliar de incremeni va fi utilizat pentru controlul procesului de sortare, unde .

pasul P1: (cicleaz dup s):

Execut pasul P2 pentru , apoi termin algoritmul.


Pune i execut paii P3SYMBOL 184 \f "Symbol"P6 pentru .

(Vom utiliza metoda inseriei directe pentru a sorta elementele ce sunt la distana de h poziii, astfel nct , pentru . Paii de la P3 la P6 sunt aceiai cu paii de la P2 la P5 din algoritmul anterior).

pasul P3: (fixeaz i, K, R):

Atribuie

pasul P4: (compar ):Dac , atunci mergi la pasul P6.

pasul P5: (deplaseaz , descrete i):

Atribuie

Dac , mergi la P4.

pasul P6: (R n ):

Pune .

Inserii prin liste

Aceasta este o metod de mbuntire a inseriei directe. Inseria direct implic dou operaii de baz:

1) parcurgerea unui fiier ordonat pentru a gsi cea mai mare cheie, mai mare sau egal cu o cheie dat;

2) inserarea unei nregistrri noi ntr-o anumit parte a fiierului ordonat.

Fiierul este, evident, o list liniar i algoritmul de sortare prin inserie direct (algoritmul 5.1.4.1) va manipula aceast list utiliznd alocarea secvenial.

n concluzie, structura adecvat de date pentru inserie direct este o list liniar cu legturi, unidirecional. Este convenabil s revedem algoritmul menionat mai sus, astfel ca lista s fie parcurs n ordine cresctoare.

Astfel, vom obine algoritmul urmtor:

Algoritmul 5.1.4.3. inserii de liste

Se consider c nregistrrile conin cheile i cmpurile de legtur , capabile de a conine numere de 0 la n. Exist un cmp de legtur ntr-o nregistrare , artificial, la nceputul fiierului. Algoritmul va fixa cmpurile de legtur, astfel nct nregistrrile s fie legate n ordine ascendent. Astfel, dac este o permutare stabil care ordoneaz , acest algoritm va da:


Atribuie

( acioneaz n calitate de cap al listei, iar 0 n calitate delegtura zero, deci lista este circular). Execut paii de la P2 la P5 pentru , apoi termin algoritmul.

pasul P2: (fixeaz p, q, K):

Atribuie

(n paii ce urmeaz vom insera la locul potrivit n lista legat,comparnd K cu cheile anterioare n ordine ascendent. Variabilele p i q au rol de indicatoare spre locul cunoscut n list,cu , astfel c variabila q este cu un pas n urma lui p).

pasul P3: (compar ):

Dac , mergi la pasul P5.

(Am gsit poziia dorit pentru nregistrarea R, ntre , nlist).

pasul P4:

Atribuie

i .

Dac mergi napoi la pasul P3(Dac , k va fi cheia cea mai mare gsit pn n prezent,deci nregistrarea R aparine sfritului listei, ntre ).

pasul P5: (insereaz n list):

Atribuie

Acest algoritm apare des ca o component a altor algoritmi deprelucrare a listelor.Subiectul 22Sortarea prin interschimbareAceast metod interschimb perechea de elemente care nu este n ordine, pn cnd nu mai exist nici o astfel de pereche. Procesul de inserie direct poate fi vizualizat ca o metod de interschimbare: vom lua fiecare nregistrare Rj i-o vom interschimba cu vecinii si din stnga, pn cnd ajunge la locul potrivit.

Probabil c cea mai evident cale de sortare prin interschimbri const n compararea lui K1 cu K2 i interschimbarea lui R1 cu R2, dac cheile nu sunt n ordine, apoi se va face acelai lucru pentru nregistrrile R2 i R3, R3 i R4 etc. n timpul acestei secvene de operaii, nregistrrile cu chei mari tind s se deplaseze spre dreapta, i de fapt nregistrarea cu cheia cea mai mare va avansa pentru a devenii Rn. Repetarea acestui proces va pune nregistrrile potrivite n poziiile Rn-1, Rn-2 etc., astfel nct toate nregistrrile vor fi sortate. Algoritmul corespunztor acestei metode este urmtorul:

Algoritmul 5.1.5.1:

nregistrrile sunt rearanjate dup terminarea sortrii, cheile vor fi n ordine, .

pasul P1: (iniializeaz BOUND):

Stabilete

(BOUND este indice).


Stabilete .

Efectueaz pasul P3 pentru i apoi mergi la pasul P4.

pasul P3: (compar/interschimb ):

Dac interschimb i stabilete .

pasul P4: (sunt interschimbri?):

Dac t = 0, algoritmul se termin.

n caz contrar, stabilete i revino la pasul P2.

Iat o schem bloc de funcionare a algoritmului:

Organigrama pentru sortare prin metoda bulelor

Algoritmul prezentat mai sus poate fi realizat i ntr-o alt variant, n care la pasul P2 ciclarea se execut pentru i se schimb variabila BOUND.

Aceast a doua variant consum ns un timp de lucru mai mare dect prima variant, deoarece necesit efectuarea unor operaii de comparare suplimentare n subiruri deja ordonate.

Desi s-au incercat unele perfectionari ale metodei de mai sus , se observa ca ele nu conduc la un algoritm mai bun decat insertia directa .

Subiectul 23

Sortarea prin selecieO alt familie important de tehnici de sortare este bazat pe idea seleciei repetate. Cea mai simpl metod de selecie este urmtoarea:

i) Aflai cheia cea mai mic; transferai nregistrarea corespunztoare n aria de ieire; apoi nlocuii cheia prin valoarea infinit (care se presupune c este mai mare dect orice cheie actual).

ii) Repetai pasul (i). De aceast dat va fi selectat urmtoarea cheie cu valoarea cea mai mic, deoarece cea mai mic valoare a fost nlocuit prin infinit.

(iii) Continuai repetarea pasului (i) pn cnd cele N nregistrri au fost selectate.

De notat ca o astfel de metod de selecie necesit ca toate elementele de intrare s fie prezentate nainte ca sortarea s poat ncepe i ea genereaz datele finale de ieire, una dup alta, n secvene. Aceasta, n esen se deosebete de inserie, unde intrrile se primesc secvenial, dar nu se tie nimic despre ieiri, pn cnd sortarea este complet.

Metoda de mai sus implic N-1 comparaii de fiecare dat cnd o nou nregistrare este selectat i de asemenea, necesit un spaiu separat de memorie pentru datele de ieire. Exist un mod evident pentru ameliorarea acestei situaii, evitnd utilizarea lui infinit. Se poate lua valoarea selectat i muta ntr-o poziie adecvat ei, prin interschimbarea cu nregistrarea curent care ocupa acea poziie. Apoi nu mai este necesar s considerm aceast poziie n seleciile viitoare. Aceast idee conduce la urmtorul algoritm de sortare prin selecie:

Algoritmul 5.1.6.1:

nregistrrile sunt de sortat; dup ce sortarea este complet, cheile acestor nregistrri vor fi n ordinea . Sortarea se bazeaz pe faptul c se selecteaz la nceput elementul cel mai mare, apoi al 2-lea element cu valoarea cea mai mare etc.

pasul P1: (bucleaz pe j):

Se execut paii P2 i P3 pentru .

pasul P2: (gsete:

:

Se caut pentru cheile cea mai mare dintre ele

(fie aceasta ).

pasul P3: (interschimb):

Se interschimb nregistrrile

(Acum nregistrrile sunt n poziia lor final).

Sortare prin selecie direct

Exemplu numeric

Subiectul 24Sortarea prin interclasareInterclasarea (sau colaionarea) nseamn combinarea a dou sau mai multe fiiere ntr-un singur fiier ordonat.

Observaie. Cnd unul din fiiere este epuizat este necesar ceva mai mult atenie.

De exemplu putem interclasa dou fiiere:

pentru a obine:

087503512677703765 .

Observaie. Un mod simplu pentru realizarea acestui deziderat const n a compara elementele cele mai mici, de a extrage pe cel mai mic etc.

Algoritmul de sortare prin interclasare este prezentat mai jos:

Algoritmul 5.1.7.1:

Acest algoritm interclaseaz fiierele ordonate i ntr-un singur fiier .

pasul P1: (iniializare):

Stabilete

pasul P2: (gsete pe cel mai mic):

Dac , treci la pasul P3 altfel treci la pasul P5.

pasul P3: (extrage ):

Stabilete

Dac , treci la pasul P2.

pasul P4: (transmite ):

Stabilete i termin algoritmul.

pasul P5: (extrage ):

Stabilete

Dac , treci la pasul P2.

pasul P6: (transmite ):

Stabilete i termin algoritmul.

Observaie. Interclasarea necesit o munc mai simpl dect sortarea. Cantitatea total de munc implicat n acest algoritm este de fapt proporional cu m+n, astfel este clar c interclasarea este o problem mai simpl dect sortarea. Mai mullt, putem reduce problema de sortare la interclasare i n acest caz este posibil s se continue interclasarea subfiierelor, din ce n ce mai lungi pn cnd toate elementele sunt sortate; inseria unui nou element ntr-un fiier sortat reprezint cazul special de interclasare cnd n=1.

Interclasare X1

Lista Subiecte SDA 2007-2008

Documents

Transcript of Lista Subiecte SDA 2007-2008