Cuprins1 Introducere 2 Despre algoritmi 1. Limbaj algoritmic ...................................................................................................................................... 2. Probleme si programe ............................................................................................................................... 3. Msurarea performanelor unui algoritm ............................................................................................... 2 2 1 15 17

3 Tipuri de date de nivel nalt 23 4. Lista liniar ................................................................................................................................................. 23 5. Lista liniar ordonat ................................................................................................................................ 31 6. Stiva ............................................................................................................................................................35 7. Coada ........................................................................................................................................................... 38 8. Arbori binari ............................................................................................................................................... 42 9. Grafuri ..................................................................................................................................................... 50 10."Heap"-uri ............................................................................................................................................... 64 11."Union-find" ............................................................................................................................................ 68 4 Sortare intern 4.1 Sortare bazat pe comparaii .......................................................................................................... 5 Cutare 12.Cutare n liste liniare .............................................................................................................................. 13.Arbori binari de c utare ........................................................................................................................... 6 Enumerare 14.Enumerarea permut rilor ......................................................................................................................... 15.Enumerarea elementelor produsului cartezian ...................................................................................... 71 71 80 81 81 86 86 89

Bibliografie

90

iii

Capitolul 1

IntroducereAcest manual este dedicat n special studenilor de la formele de nvmnt ID (Invmnt la Distan) si PU (Post universitare) de la Facultatea de Informatic a Universitii " Alexandru Ioan Cuza" din Iasi. Cartea se doreste a fi un suport pentru disciplinele Algoritmi si Programare (ID) si Structuri de Date si Algoritmi (PU). Recomandam ca parcurgerea acestui suport sa se fac n paralel cu consultarea materialul electronic aflat pe pagina web a cursului la adresa http://www. infoiasi.ro/fcs/CS2101.php. De fapt coninutul acestei cri este o versiune simplifcat a celui inclus pe pagina cursului. Din acest motiv unele referine apar ca nedefinite (marcate cu "??"). Toate acestea pot fi gsite pe pagina cursului. Structura manualului este urmtoarea: Capitolul doi include definiia limbajului algoritmic utilizat mpreun cu definiiile pentru cele dou funcii principale de msurare a eficienei algoritmilor: complexitatea timp si complexitatea spaiu. Tipurile de date cele mai utilizate n programare sunt prezentate n capitolul trei. In capitolul patru sunt prezentai principalii algoritmi de sortare intern bazai pe comparaii. Capitolul al cincilea este dedicat algoritmilor de cutare si a principalelor structuri de date utilizate de acesti algoritmi. Capitolul sase include doi algoritmi de enumerare: enumerarea permutrilor si enumerarea elementelor produsului cartezian. Fiecare capitol este acopaniat de o list de exerciii.

1

Capitolul 2

Despre algoritmi2.1 Limbaj algoritmic2.1.1 IntroducereUn algoritm este o secven fnit de pai, aranjat ntr-o ordine logic specifc care, atunci cnd este executat, produce o soluie corect pentru o problem precizat. Algoritmii pot fi descrisi n orice limbaj, pornind de la limbajul natural pn la limbajul de asamblare al unui calculator specific. Un limbaj al crui scop unic este cel de a descrie algoritmi se numeste limbaj algoritmic. Limbajele de programare sunt exemple de limbaje algoritmice. In aceast seciune descriem limbajul algoritmic utilizat n aceast carte. Limbajul nostru este tipizat, n sensul c datele sunt organizate n tipuri de date. Un tip de date const dintr-o mulime de entiti de tip dat (valori), numit si domeniul tipului, si o mulime de operaii peste aceste entiti. Convenim s grupm tipurile de date n trei categorii: tipuri de date elementare, n care valorile sunt entiti de informaie indivizibile; tipuri de date structurate de nivel jos, n care valorile sunt structuri relativ simple obinute prin asamblarea de valori elementare sau valori structurate iar operaiile sunt date la nivel de component; tipuri de date structurate de nivel nalt, n care valorile sunt structuri mai complexe iar operaiile sunt implementate de algoritmi proiectai de ctre utilizatori. Primele dou categorii sunt dependente de limbaj si de aceea descrierile lor sunt incluse n aceat seciune. Tipurile de nivel nalt pot fi descrise ntr-o manier independent de limbaj si descrierile lor sunt incluse n capitolul 3. Un tip de date descris ntr-o manier indepenedent de reprezentarea valorilor si implementarea operaiilor se numete tip de date abstract. Pasii unui algoritm si ordinea logic a acestora sunt descrise cu ajutorul instruciunilor. O secven de instruciuni care acioneaz asupra unor structuri de date precizate se numeste program. In seciunea 2.2 vom vedea care sunt condiiile pe care trebuie s le ndeplineasc un program pentru a descrie un algoritm.

2.1.2

Modelarea memoriei

Memoria este reprezentat ca o structur liniar de celule, fiecare celul avnd asociat o adres si putnd memora (stoca) o dat de un anumit tip (fig. 2.1). Accesul la memorie este realizat cu ajutorul variabilelor. O variabil este caracterizat de: un nume cu ajutorul creia variabila este referit, o adres care desemneaz o locaie de memorie si un tip de date care descrie natura valorilor memorate n locaia de memorie asociat variabilei. Dac n plus adugm si valoarea memorat la un moment dat n locaie, atunci obinem o instan a variabilei. O variabil este reprezentat grafic ca n fig. 2.2a. Atunci cnd tipul se subnelege din2

a 712

Figura 2.1: Memoria 712 a) Figura 2.2: Variabil context, vom utiliza reprezentarea scurt sugerat n 2.2b. Convenim s utilizm fontul type writer pentru notarea variabilelor i fontul mathnormal pentru notarea valorilor memorate de variabile. 712b)

2.1.3 Tipuri de date elementareNumere ntregi. Valorile sunt numere ntregi iar operaiile sunt cele uzuale: adunarea (+), nmulirea (*), scderea () etc. Numere reale. Deoarece prin dat nelegem o entitate de informaie reprezentabil n memoria calculatorului, domeniul tipului numerelor reale este restrns la submulimea numerelor raionale. Operaiile sunt cele uzuale. Valori booleene. Domeniul include numai dou valori: true si f alse. Peste aceste valori sint definite operaiile logice and, or si not cu semnificaiile cunoscute. Caractere. Domeniul include litere: ' a ' , ' b ' , . . . , ' A ' , ' B ' , . . . , cifre: ' 0 ' , ' 1 ' , . . . , si caractere speciale: ' +', ' *', . . . . Nu exist operaii. Pointeri. Domeniul unui tip pointer const din adrese de variabile aparinnd la alt tip. Presupunem existena valorii NULL care nu refer nici o variabil; cu ajutorul ei putem testa dac un pointer refer sau nu o variabil. Nu considerm operaii peste aceste adrese. Cu ajutorul unei variabile pointer, numit pe scurt si pointer, se realizeaz referirea indirect a unei locaii de memorie. Un pointer este reprezentat grafic ca n fig. 2.3a. Instana variabilei pointer p are ca valoare adresa unei variabile de tip ntreg. Am notat integer* tipul pointer al crui domeniu este format din adrese de variabile de tip ntreg. Aceast convenie este extins la toate tipurile. Variabila referit de p este notat cu *p. In fig. 2.3b si 2.3c sunt date reprezentrile grafice simplificate ale pointerilor. Pointerii sunt utilizai la manipularea variabilelor dinamice. O variabil dinamic este o variabil care poate fi creat si distrus n timpul execuiei programului. Crearea unei variabile dinamice se face cu ajutorul subprogramului new. De exemplu, apelul new(p) are ca efect crearea variabilei *p. Distrugerea (eliberarea spaiului de memorie) variabilei *p se face cu ajutorul apelului delete(p) al subprogramului

delete.

2.1.4 InstrucAtribuirea.

iuni

Sintaxa:

(variabil) 0; - n.

Intrare: Ieire: Copie.

Intoarce o copie distinct a unei liste date. - o list liniar L; - o copie L' distinct a lui L.

Intrare: Ieire: Egal.

Testeaz dac dou liste liniare sunt egale. - dou liste L = (e0,..., e_i) si L' = (e' o ,..., e^/^-J; - true dac n = n' si e0 = e' o ,..., e_i = e^_ 1; - false, n celelalte cazuri.

Intrare: Ieire:

23

Poz.

Caut dac un element dat x apare ntr-o list liniar dat L. - o list liniar L = (e0,..., e_i) si un element x din Elt; - adres invalid ( 1 sau NULL) dac x nu apare n L, - adresa elementului ei dac e^ = x si (Vj)0 < j < i => ej ^ x.

Intrare: Ieire:

Parcurge. Parcurge o list liniar dat efectund o prelucrare uniform asupra componentelor acesteia. Intrare: Ieire: Citete. Intrare: Ieire: Insereaz. Intrare: Ieire: - o list liniar L si o procedur Viziteaz(e); - lista L dar ale crei componente au fost prelucrate de procedura Viziteaz. Intoarce elementul de la o poziie dat dintr-o list dat. - o list liniar L = (e0,..., e_i) si o poziie k > 0; - ek dac 0 < k < n, - eroare, n celelalte cazuri. Adaug un element dat ntr-o list liniar dat la o poziie dat. - o list liniar L = (e0,..., e_i), un element e din Elt si o poziie k > 0; L = (e0, . . ., e^-i, e, ek,... , en_i) dac 0 < k < n, - L = (e0,..., e_i, e) dac k > n.

EliminDeLaK. Elimin elementul de la o poziie dat dintr-o list liniar dat. Intrare: Ieire: - o list liniar L = (e0,..., e_i) si o poziie k > 0; - L = (e0,..., efc_i,efc_|_i,... , e_i) dac 0 < k < n, - L = (e0, . . ., en_i) dac k > n.

Elimin. Elimin un element dat dintr-o list liniar dat. Intrare: Ieire: - o list liniar L = (e0,..., e_i) si un element e din Elt; - lista L din care s-au eliminat toate elementele ei egale cu e.

3.1.2 Implementarea dinamic3.1.2.1

cu liste simplu nlnuite

Reprezentarea obiectelor de tip dat

O list liniar L = (e1,..., en) este reprezentat printr-o list ca cea din fig. 3.1. Fiecare component a listei liniare este memorat ntr-un nod al listei simplu nlnuite. Exist doi pointeri L.prim si L.ultim care fac referire la primul si respectiv ultimul nod.

1 e03.1.2.2

(

e1

e2

-

en-1

Figura 3.1: Reprezentarea listei liniare cu list simplu nlnuit Implementarea operaiilor

ListaVid. Este reprezentat de lista fr nici un nod: L.prim = L.ultim = NULL. EsteVid. Este suficient s se testeze dac pointerul L.prim este egal cu NULL.

24

Lung. Parcurge lista si contorizeaz fiecare nod parcurs. Timpul necesar determinrii lungimii este Acesta poate fi redus la O(1) dac lungimea ar fi inclus n reprezentarea listei. Aceasta ar presupune ca toate operaiile care modifc lungimea listei s actualizeze corespunztor variabila responsabil cu memorarea lungimii. function lung(L) begin l g ^ 0 p succ Lcopie.ultim->elt elt p succ Lcopie.ultim->succ < NULL end

O(n).

Egal. Parcurge simultan cele dou liste si compar perechile de noduri corespunztoare. Dac presupunem c operaia de comparare a unei perechi de noduri se face n timpul O(1) atunci compararea listelor se realizeaz n timpul O(n) n cazul cel mai nefavorabil, unde n este valoarea minim dintre lungimile celor dou liste. function egal(L1, L2) begin p1elt) then return false p1 succ p2 succ if ((p1 = NULL) and (p2 = NULL)) then return true else return false end Poz. Se aplic tehnica cutrii secveniale: se pleac din primul nod si se interogheaz nod cu nod pn cnd este gsit primul care memoreaz pe x sau au fost epuizate toate nodurile. Plecnd de la ipoteza

25

c interogarea unui nod se face n timpul O(1), rezult c operaia de cutare necesit timpul cazul cel mai nefavorabil. function poz(L, x) begin p < L.prim while (p ^ NULL) do if (p->elt = x) then return p >succ return NULL end

O(n) n

p < p-

Parcurge. Se parcurge lista nod cu nod si se aplic procedura Viziteaz. Se obine un grad mai mare de aplicabilitate a operaiei dac procedurile de tip Viziteaz au ca parametru adresa unui nod si nu informaia memorat n nod. Dac t este timpul necesar procedurii Viziteaz pentru a prelucra un nod, atunci complexitatea timp a operaiei de parcurgere este O(n t). procedure parcurge(L, viziteaza()) begin p < L.prim while (p ^ NULL) do viziteaza(p) p succ end Cite te. Pentru a putea citi informaia din cel de-al k-lea nod, este necesar parcurgerea secvenial a primelor k-noduri. Deoarece k < n, rezult c aavem o complexitate n cazul cel mai nefavorabil egal cu O(n). function citeste(L, k) begin p < L.prim i Lung(L) atunci pointerii prim si respectiv ultim se actualizeaz corespunztor. Deoarece operaia de adugare a unui nod dup o adres dat se realizeaz n timpul O(1), rezult c operaia de inserare necesit timpul O(n) n cazul cel mai nefavorabil. procedure insereaza(L, k, e) begin if (k < 0) then throw 'eroare' new(q) q->elt succ < L.prim L.primlstg este adresa predecesorului lui v n inordine, v->tdrp = true dac v are subarbore dreapta, v->tdrp = false dac v nu are subarbore dreapta si n acest caz v->drp este adresa succesorului lui v n inordine. Un asemenea arbore se numeste nsilat. (i) S se scrie o procedur de parcurgere n inordine a arborilor nsilai. (ii) S se scrie o procedur care copie un arbore binar obisnuit ntr-un arbore nsilat. Exerciiul 3.5.9. S se scrie o procedur care s numere nodurile de pe frontiera arbore binar. Exerciiul 3.5.10. Se consider arbori binar care au ca informaie n noduri numere ntregi. Lungimea extern ponderat a arborelui t este ^2{v->inf * lung(v) | v este nod pe frontiera lui t}, unde lung(v) este lungimea drumului de la rdcin la nodul v. S se scrie un subprogram care determin lungimea extern a unui astfel de arbore. Exerciiul 3.5.11. (Reprezentarea expresiilor aritmetice) Considerm expresii formate numai din numere ntregi si operatorii binari +, , /,*, %. Unei expresii e i se poate asocia un arbore ninar a(e) astfel: dac e este un numr ntreg atunci a(e) este format dintr-un singur nod [e]:e

a(e) =

dac e = e1ope2 atunci a(e) este arborele [](a(e1),a(e2)):

48

a(e) =

Rdcina lui a(e) are eticheta "op", subarborele din stnga rdcinii este a(e1) iar subarborele din dreapta rdcinii este a S se scrie un subprogram care are la intrare o list liniar ce reprezint o expresie si ofer la iesire arborele binar asociat expresiei. Arborele asociat este unic? S se justifice cum rezolv programul problema unicitii. Exerciiul 3.5.12. Asa cum am vzut n exerciiul 3.5.11, orice expresie aritmetic poate fi reprezentat prin arbori. Notaia postfixat a unei expresii se obine prin parcurgerea n postordine a arborelui. De exemplu, expresia a/b* 2 + b * d a*care urmtoarea form postfxat: a b 2 * /b d* +a c* . Urmtorul algoritm realizeaz conversia unei expresii din notaia infixat n notaia postfixat (listele cu formele infixate si respectiv infixate sunt reprezentate prin cozi):S V dat prin numeG(i) = v - indexG(v) = i. 3.6.2.2GrafVid.

Operaii - nimic; - graful vid G = (0,0).

Intrare: Ieire:EsteGrafVid.

Intrare: - un graf G = (V, E); Ieire: - true dac G este vid, false n caz contrar..InsereazVrf.

Intrare: Ieire:

- un graf G = (V, E) cu V = {0,1,..., n - 1}; - graful G la care se adaug vrful n ca vrf izolat (nu exist muchii incidente n n).

InsereazMuchie.

Intra re:

u n g r a G = ( V , E ) s i d o v r f u ri i , j V ; f u

Ieire:tergeVrf.

- graful G la care se adaug muchia {i,j}.

Intrare: Ieire:

- un graf G = (V, E) si un vrf k k sunt redenumite ca fiind i 1.

tergeMuchie.

In tra re:

u n g r a G = ( V , E ) s i d o v r f u ri i , j V ; Ieire: f u

- graful G din care a fost eliminat muchia {i,j}.ListaDeAdiacen.

Intrare: - un graf G = (V, E) si un vrf i V; Ieire: - mulimea vrfurilor adiacente cu vrful i.ListaVrfurilorAccesibile.

Intrare: Ieire:

- un graf G = (V, E) si un vrf i V; - mulimea vrfurilor accesibile din vrful i. Un vrf j este accesibil din i dac i numai dac exist un drum de la i la j.

53

3.6.33.6.3.1

Tipul de dat abstract DigrafDescrierea obiectelor de tip dat

Obiectele de tip dat sunt digrafuri D = (V,A), unde mulimea de vrfuri V o considerm de forma {0,1,..., n 1}, iar mulimea de arce este o submulime a produsului cartezian V x V. Tipul Vrf are aceeasi semnificaie ca n cazul modelului constructiv Graf, iar tipul Arc este produsul cartezian Vrf x Vrf. 3.6.3.2DigrafVid.

Operaii - nimic; - digraful vid D = (0, 0).

Intrare: Ieire:

EsteDigrafVid.

Intrare: - un digraf D = (V,A); Ieire: - true dac D este vid, false n caz contrar..InsereazVrf.

Intrare: Ieire:InsereazArc.

- un digraf D = (V,A) cu V = {0,1,..., n - 1}; - digraful D la care s-a adugat vrful n.

Intrare:

u n d i g r aDf = ( V , As )i d o v r f u ri i , j V ; u

Ieire:tergeVrf.

- digraful D la care s-a adugat arcul (i,j).

Intrare: Ieire:tergeArc.

- un digraf D = (V, A) si un vrf k V; - digraful D din care au fost eliminate toate arcele incidente n k (au o extremitate n k) iar vrfurile i > k sunt redenumite ca fiind i 1.

Intrare: Ieire:

u n d i g r aDf = ( V , As )i d o v r f u ri i , j V ; u d i-g r a f uD d i n c a r e s - a e l i m i n a t (a ir ,c ju )l . l

ListaDeAdiacenlnterioar.

Intrare: Ieire:

- un digraf D = (V, A) si un vrf i V; - mulimea surselor (vrfurilor de plecare ale) arcelor care sosesc n vrful i.

ListaDeAdiacenExterioar.

Intrare: Ieire:

- un digraf D = (V, A) si un vrf i V; - mulimea destinaiilor (vrfurilor de sosire ale) arcelor care pleac din vrful i.

ListaVrfurilorAccesibile.

Intrare: Ieire:

- un graf D = (V, A) si un vrf i V; - mulimea vrfurilor accesibile din vrful i. Un vrf j este accesibil din i dac i numai dac exist un drum de la i la j.54

3.6.4

Reprezentarea grafurilor ca digrafuri

Orice graf G = (V,E)