• Nu S-Au Găsit Rezultate

Bibliografie 90

N/A
N/A
Protected

Academic year: 2022

Share "Bibliografie 90"

Copied!
91
0
0

Text complet

(1)

Cuprins

1 Introducere 1

2 Despre algoritmi 2

2.1 Limbaj algoritmic . . . 2

2.2 Probleme ¸si programe . . . 15

2.3 M˘asurarea performant¸elor unui algoritm . . . 17

3 Tipuri de date de nivel ˆınalt 23 3.1 Lista liniar˘a . . . 23

3.2 Lista liniar˘a ordonat˘a . . . 31

3.3 Stiva . . . 35

3.4 Coada . . . 38

3.5 Arbori binari . . . 42

3.6 Grafuri . . . 50

3.7 “Heap”-uri . . . 64

3.8 “Union-find” . . . 68

4 Sortare intern˘a 71 4.1 Sortare bazat˘a pe comparat¸ii . . . 71

5 C˘autare 80 5.1 C˘autare ˆın liste liniare . . . 81

5.2 Arbori binari de c˘autare . . . 81

6 Enumerare 86 6.1 Enumerarea permut˘arilor . . . 86

6.2 Enumerarea elementelor produsului cartezian . . . 89

Bibliografie 90

(2)

Capitolul 1

Introducere

Acest manual este dedicat ˆın special student¸ilor de la formele de ˆınv˘at¸˘amˆant ID (ˆInv˘at¸˘amˆant la Distant¸˘a)

¸si PU (Post universitare) de la Facultatea de Informatic˘a a Universit˘at¸ii ”Alexandru Ioan Cuza” din Ia¸si.

Cartea se dore¸ste 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˘a ˆın paralel cu consultarea materialul electronic aflat pe pagina web a cursului la adresahttp://www.infoiasi.ro/fcs/CS2101.php. De fapt cont¸inutul acestei c˘art¸i este o versiune simplificat˘a a celui inclus pe pagina cursului. Din acest motiv unele referint¸e apar ca nedefinite (marcate cu “??”). Toate acestea pot fi g˘asite pe pagina cursului.

Structura manualului este urm˘atoarea: Capitolul doi include definit¸ia limbajului algoritmic utilizat ˆımpreun˘a cu definit¸iile pentru cele dou˘a funct¸ii principale de m˘asurare a eficient¸ei algoritmilor: complex- itatea timp ¸si complexitatea spat¸iu. Tipurile de date cele mai utilizate ˆın programare sunt prezentate ˆın capitolul trei. ˆIn capitolul patru sunt prezentat¸i principalii algoritmi de sortare intern˘a bazat¸i pe comparat¸ii. Capitolul al cincilea este dedicat algoritmilor de c˘autare ¸si a principalelor structuri de date utilizate de ace¸sti algoritmi. Capitolul ¸sase include doi algoritmi de enumerare: enumerarea permut˘arilor

¸si enumerarea elementelor produsului cartezian. Fiecare capitol este acopaniat de o list˘a de exercit¸ii.

(3)

Capitolul 2

Despre algoritmi

2.1 Limbaj algoritmic

2.1.1 Introducere

Un algoritm este o secvent¸˘a finit˘a de pa¸si, aranjat˘a ˆıntr-o ordine logic˘a specific˘a care, atunci cˆand este executat˘a, produce o solut¸ie corect˘a pentru o problem˘a precizat˘a. Algoritmii pot fi descri¸si ˆın orice limbaj, pornind de la limbajul natural pˆın˘a la limbajul de asamblare al unui calculator specific. Un limbaj al c˘arui scop unic este cel de a descrie algoritmi se nume¸ste limbaj algoritmic. Limbajele de programare sunt exemple de limbaje algoritmice.

ˆIn aceast˘a sect¸iune descriem limbajul algoritmic utilizat ˆın aceast˘a carte. Limbajul nostru este tipizat, ˆın sensul c˘a datele sunt organizate ˆın tipuri de date. Untip de dateconst˘a dintr-o mult¸ime de entit˘at¸i de tip dat˘a (valori), numit˘a ¸si domeniultipului, ¸si o mult¸ime de operat¸ii peste aceste entit˘at¸i. Convenim s˘a grup˘am tipurile de date ˆın trei categorii:

• tipuri de date elementare, ˆın care valorile sunt entit˘at¸i de informat¸ie indivizibile;

• tipuri de date structurate de nivel jos, ˆın care valorile sunt structuri relativ simple obt¸inute prin asamblarea de valori elementare sau valori structurate iar operat¸iile sunt date la nivel de compo- nent˘a;

• tipuri de date structurate de nivel ˆınalt, ˆın care valorile sunt structuri mai complexe iar operat¸iile sunt implementate de algoritmi proiectat¸i de c˘atre utilizatori.

Primele dou˘a categorii sunt dependente de limbaj ¸si de aceea descrierile lor sunt incluse ˆın aceat˘a sect¸iune.

Tipurile de nivel ˆınalt pot fi descrise ˆıntr-o manier˘a independent˘a de limbaj ¸si descrierile lor sunt incluse ˆın capitolul 3. Un tip de date descris ˆıntr-o manier˘a indepenedent˘a de reprezentarea valorilor ¸si imple- mentarea operat¸iilor se nume¸stetip de date abstract.

Pa¸sii unui algoritm ¸si ordinea logic˘a a acestora sunt descrise cu ajutorulinstruct¸iunilor. O secvent¸˘a de instruct¸iuni care act¸ioneaz˘a asupra unor structuri de date precizate se nume¸steprogram. ˆIn sect¸iunea 2.2 vom vedea care sunt condit¸iile pe care trebuie s˘a le ˆındeplineasc˘a un program pentru a descrie un algoritm.

2.1.2 Modelarea memoriei

Memoria este reprezentat˘a ca o structur˘a liniar˘a de celule, fiecare celul˘a avˆand asociat˘a o adres˘a ¸si putˆand memora (stoca) o dat˘a de un anumit tip (fig. 2.1). Accesul la memorie este realizat cu ajutorul variabilelor. Ovariabil˘aeste caracterizat˘a de:

• unnumecu ajutorul c˘areia variabila este referit˘a,

• oadres˘acare desemneaz˘a o locat¸ie de memorie ¸si

• untip de date care descrie natura valorilor memorate ˆın locat¸ia de memorie asociat˘a variabilei.

Dac˘a ˆın plus ad˘aug˘am ¸si valoarea memorat˘a la un moment dat ˆın locat¸ie, atunci obt¸inem o instant¸˘a a variabilei. O variabil˘a este reprezentat˘a grafic ca ˆın fig. 2.2a. Atunci cˆand tipul se subˆınt¸elege din

(4)

712

lungime integer

a

Figura 2.1: Memoria

b)

lungime integer 712 lungime 712

a)

Figura 2.2: Variabil˘a

context, vom utiliza reprezentarea scurt˘a sugerat˘a ˆın 2.2b. Convenim s˘a utiliz˘am fontul type writer pentru notarea variabilelor ¸si fontulmathnormalpentru notarea valorilor memorate de variabile.

2.1.3 Tipuri de date elementare

Numere ˆıntregi. Valorile sunt numere ˆıntregi iar operat¸iile sunt cele uzuale: adunarea (+), ˆınmult¸irea (∗), sc˘aderea (−) etc.

Numere reale. Deoarece prin dat˘a ˆınt¸elegem o entitate de informat¸ie reprezentabil˘a ˆın memoria calcu- latorului, domeniul tipului numerelor reale este restrˆans la submult¸imea numerelor rat¸ionale. Operat¸iile sunt cele uzuale.

Valori booleene. Domeniul include numai dou˘a valori: true¸sifalse. Peste aceste valori sint definite operat¸iile logiceand,or¸sinotcu semnificat¸iile cunoscute.

Caractere. Domeniul include litere: ’a’, ’b’, . . . , ’A’, ’B’, . . . , cifre: ’0’, ’1’, . . . , ¸si caractere speciale: ’+’,’*’, . . . . Nu exist˘a operat¸ii.

Pointeri. Domeniul unui tip pointer const˘a din adrese de variabile apart¸inˆand la alt tip. Presupunem existent¸a valorii NULL care nu refer˘a nici o variabil˘a; cu ajutorul ei putem testa dac˘a un pointer refer˘a sau nu o variabil˘a. Nu consider˘am operat¸ii peste aceste adrese. Cu ajutorul unei variabile pointer, numit˘a pe scurt ¸si pointer, se realizeaz˘a referirea indirect˘a a unei locat¸ii de memorie. Un pointer este reprezentat grafic ca ˆın fig. 2.3a. Instant¸a variabilei pointerpare ca valoare adresa unei variabile de tip ˆıntreg. Am notatinteger*tipul pointer al c˘arui domeniu este format din adrese de variabile de tip ˆıntreg. Aceast˘a convent¸ie este extins˘a la toate tipurile. Variabila referit˘a depeste notat˘a cu*p. ˆIn fig. 2.3b ¸si 2.3c sunt date reprezent˘arile grafice simplificate ale pointerilor.

Pointerii sunt utilizat¸i la manipularea variabilelor dinamice. Ovariabil˘a dinamic˘aeste o variabil˘a care poate fi creat˘a ¸si distrus˘a ˆın timpul execut¸iei programului. Crearea unei variabile dinamice se face cu ajutorul subprogramuluinew. De exemplu, apelulnew(p)are ca efect crearea variabilei*p. Distrugerea (eliberarea spat¸iului de memorie) variabilei*pse face cu ajutorul apeluluidelete(p)al subprogramului delete.

2.1.4 Instruct¸iuni

Atribuirea. Sintaxa:

hvariabil˘ai ← hexpresiei

unde hvariabil˘aieste numele unei variabile iarhexpresieieste o expresie corect format˘a de acela¸si tip cu hvariabil˘ai.

(5)

p

a a’

a’

*p integer

*p integer

integer*

p

integer*

p

*p a)

b) c)

Figura 2.3: Pointer

Semantica: Se evalueaz˘ahexpresiei¸si rezultatul obt¸inut se memoreaz˘a ˆın locat¸ia de memorie desemnat˘a de hvariabil˘ai. Valorile tuturor celorlalte variabile r˘amˆan neschimbate. Atribuirea este singura instruct¸iune cu ajutorul c˘areia se poate modifica memoria. O reprezentare intuitiv˘a a efectului instruct¸iunii de atribuire este dat˘a ˆın fig. 2.4.

b) Dupa atribuirea "a <- a*b"

a 5 b -2

a -10 b -2

a) Inainte de atribuire

Figura 2.4: Atribuirea

if. Sintaxa:

ifhexpresiei

thenhsecvent¸˘a-instruct¸iuni1i elsehsecvent¸˘a-instruct¸iuni2i

undehexpresieieste o expresie care prin evaluare d˘a rezultat boolean iarhsecvent¸˘a-instruct¸iuniii,i= 1,2, sunt secvent¸e de instruct¸iuni scrise una sub alta ¸si aliniate corespunz˘ator. Parteaelseeste facultativ˘a.

Dac˘a partea else lipse¸ste ¸si hsecvent¸˘a-instruct¸iuni1i este format˘a dintr-o singur˘a instruct¸iune atunci instruct¸iuneaifpoate fi scris˘a ¸si pe un singur rˆand. De asemenea, o expresie ˆın cascad˘a de forma

if (...) then ...

else if (...) then ...

else if (...) then ...

else ...

va fi scris˘a sub urm˘atoarea form˘a liniar˘a echivalent˘a:

(6)

if (...) then ...

else if (...) then ...

else if (...) then ...

else ...

Semantica: Se evalueaz˘a hexpresiei. Dac˘a rezultatul evalu˘arii este true atunci se execut˘a hsecvent¸˘a- instruct¸iuni1idup˘a care execut¸ia instruct¸iuniiifse termin˘a; dac˘a rezultatul evalu˘arii estefalseatunci se execut˘ahsecvent¸˘a-instruct¸iuni2idup˘a care execut¸ia instruct¸iuniiifse termin˘a.

while. Sintaxa:

whilehexpresieido

hsecvent¸˘a-instruct¸iunii

unde hexpresiei este o expresie care prin evaluare d˘a rezultat boolean iar hsecvent¸˘a-instruct¸iunii este o secvent¸˘a de instruct¸iuni scrise una sub alta ¸si aliniate corespunz˘ator.

Semantica: 1. Se evalueaz˘ahexpresiei.

2. Dac˘a rezultatul evalu˘arii estetrueatunci se execut˘ahsecvent¸˘a-instruct¸iuniidup˘a care se reia procesul ˆıncepˆand cu pasul 1. Dac˘a rezultatul evalu˘arii estefalseatunci execut¸ia instruct¸iuniiwhilese termin˘a.

for. Sintaxa:

forhvariabil˘ai ← hexpresie1itohexpresie2ido hsecvent¸˘a-instruct¸iunii

sau

forhvariabil˘ai ← hexpresie1idowntohexpresie2ido hsecvent¸˘a-instruct¸iunii

unde hvariabil˘ai este o variabil˘a de tip ˆıntreg, hexpresieii, i = 1,2, sunt expresii care prin evaluare dau valori ˆıntregi, hsecvent¸˘a-instruct¸iunii este o secvent¸˘a de instruct¸iuni scrise una sub alta ¸si aliniate corespunz˘ator.

Semantica: Instruct¸iunea for i← e1 to e2 do

S

simuleaz˘a execut¸ia urm˘atorului program:

i← e1

temp← e2

while (i ≤ temp) do S

i← i+1 iar instruct¸iunea

for i← e1 downto e2 do S

simuleaz˘a execut¸ia urm˘atorului program:

i← e1

temp← e2

while (i ≥ temp) do S

i← i-1

(7)

repeat. Sintaxa:

repeat

hsecvent¸˘a-instruct¸iunii untilhexpresiei

unde hexpresiei este o expresie care prin evaluare d˘a rezultat boolean iar hsecvent¸˘a-instruct¸iunii este o secvent¸˘a de instruct¸iuni scrise una sub alta ¸si aliniate corespunz˘ator.

Semantica: Instruct¸iunea repeat

S untile

simuleaz˘a execut¸ia urm˘atorului program:

S

while(note)do S

Except¸ii. Sintaxa:

throw hmesaji

unde hmesajieste un ¸sir de caractere (un text).

Semantica: Execut¸ia programului se opre¸ste ¸si este afi¸sat textul hmesaji. Cel mai adesea,throw este utilizat˘a ˆımpreun˘a cu if:

ifhexpresieithen throw hmesaji

Obt¸inerea rezultatuluitrueˆın urma evalu˘arii expresiei are ca semnificat¸ie aparit¸ia unei except¸ii, caz ˆın care execut¸ia programului se opre¸ste. Un exemplu de except¸ie este cel cˆand proceduranewnu poate aloca memorie pentru variabilele dinamice:

new(p)

if (p = NULL) then throw ’memorie insuficienta’

2.1.5 Subprograme

Limbajul nostru algoritmic este unul modular, unde un modul este identificat de un subprogram. Exist˘a dou˘a tipuri de subprograme: proceduri ¸si funct¸ii.

Proceduri. Interfat¸a dintre o procedur˘a ¸si modulul care o apeleaz˘a este realizat˘a numai prin parametri

¸si variabilele globale. De aceea apelul unei proceduri apare numai ca o instruct¸iune separat˘a. Forma general˘a a unei proceduri este:

procedurehnumei(hlista-parametrii) begin

hsecvent¸˘a-instruct¸iunii end

Lista parametrilor este opt¸ional˘a. Consider˘am ca exemplu o procedur˘a care interschimb˘a valorile a dou˘a variabile:

procedure swap(x, y) begin

aux← x x← y y← aux end

(8)

Permutarea circular˘a a valorilor a trei variabilea, b, cse face apelˆand de dou˘a ori proceduraswap:

swap(a, b) swap(b, c)

Funct¸ii. ˆIn plus fat¸˘a de proceduri, funct¸iile ˆıntorc valori calculate ˆın interiorul acestora. De aceea apelul unei funct¸ii poate participa la formarea de expresii. Forma general˘a a unei funct¸ii este:

functionhnumei(hlista-parametrii) begin

hsecvent¸˘a-instruct¸iunii returnhexpresiei end

Lista parametrilor este opt¸ional˘a. Valoarea ˆıntoars˘a de funct¸ie este cea obt¸inut˘a prin evaluarea expresiei.

O instruct¸iunereturnpoate ap˘area ˆın mai multe locuri ˆın definit¸ia unei funct¸ii. Consider˘am ca exemplu o funct¸ie care calculeaz˘a maximul dintre valorile a trei variabile:

function max3(x, y, z) begin

temp← x

if (y > temp) then temp← y if (z > temp) then temp← z return temp

end

Are sens s˘a scriem2*max3(a, b, c)saumax3(a, b, c) < 5.

2.1.5.1 Comentarii

Comentariile sunt notate similar ca ˆın limbajul C, utilizˆand combinat¸iile de caractere/*¸si */. Comen- tariile au rolul de a introduce explicat¸ii suplimentare privind descrierea algoritmului:

function absDec(x) begin

if (x > 0) /* testeaza daca x este pozitiv */

then x← x-1 /* decrementeaza x*/

else x← x+1 /* incrementeaza x*/

end

2.1.6 Tipuri de date structurate de nivel jos

2.1.6.1 Tablouri

Untabloueste un ansamblu omogen de variabile, numitecomponenteletabloului, ˆın care toate variabilele componente apart¸in aceluia¸si tip ¸si sunt identificate cu ajutorul indicilor. Untablou 1-dimensional (uni- dimensional) este un tablou ˆın care componentele sunt identificate cu ajutorul unui singur indice. De exemplu, dac˘a numele variabilei tablou estea¸si mult¸imea valorilor pentru indice este{0,1,2, . . . , n−1}, atunci variabilele componente sunt a[0], a[1], a[2], ..., a[n-1]. Memoria alocat˘a unui tablou 1-dimensional este o secvent¸˘a contigu˘a de locat¸ii, cˆate o locat¸ie pentru fiecare component˘a. Ordinea de memorare a componentelor este dat˘a de ordinea indicilor. Tablourile 1-dimensionale sunt reprezen- tate grafic ca ˆın fig. 2.5. Operat¸iile asupra tablourilor se realizeaz˘a prin intermediul componentelor.

Prezent˘am ca exemplu init¸ializarea tuturor componentelor cu 0:

for i← 0 to n-1 do a[i]← 0

(9)

tab1d a

integer integer integer integer integer a[0]

a[1]

a[2]

a[3]

a[4]

Figura 2.5: Tablou 1-dimensional tab2d

a

integer integer integer integer a[0,0]

a[0,1]

a[1,1]

a[1,0]

Figura 2.6: Tablou 2-dimensional

Un tablou 2-dimensional (bidimensional) este un tablou ˆın care componentele sunt identificate cu aju- torul a doi indici. De exemplu, dac˘a numele variabilei tablou estea¸si mult¸imea valorilor pentru primul indice este {0,1, . . . , m−1} iar mult¸imea valorilor pentru cel de-al doilea indice este {0,1, . . . , n− 1}atunci variabilele componente sunt a[0,0], a[0,1],..., a[0,m-1], ..., a[m-1,0], a[m-1,1], ..., a[m-1,n-1]. Ca ¸si ˆın cazul tablourilor 1-dimensionale, memoria alocat˘a unui tablou 2-dimensional este o secvent¸˘a contigu˘a de locat¸ii, cˆate o locat¸ie pentru fiecare component˘a. Ordinea de memorare a componentelor este dat˘a de ordinea lexicografic˘a definit˘a peste indici. Tablourile 2-dimensionale sunt reprezentate grafic ca ˆın fig. 2.6. A¸sa cum o matrice poate fi v˘azut˘a ca fiind un vector de linii, tot a¸sa un tablou 2-dimensional poate fi v˘azut ca fiind un tablou 1-dimensional de tablouri 1-dimensionale. Din acest motiv, componentele unui tablou 2-dimensional mai pot fi notate prin expresii de formaa[0][0], a[0][1], etc (a se vedea ¸si fig. 2.7).

tab2d a

tab1d a[0]

tab1d a[1]

Figura 2.7: Tablou 2-dimensional v˘azut ca tablou de tablouri 1-dimensionale

(10)

b) punct

p.y p.x p

integer integer

figura

f.vizibil f

f.pozitie punct

boolean a)

Figura 2.8: Structuri 2.1.6.2 S¸iruri de caractere.

S¸irurile de caractere pot fi gˆandite ca fiind tablouri unidimensionale a c˘aror elemente sunt caractere. O constant˘a ¸sir de caractere este notat˘a utilizˆand convent¸ia din limbajul C: ‘‘exemplu de sir’’. Peste

¸siruri sunt definite urm˘atoarele operat¸ii:

• concatenarea, notat˘a cu +: ’’unu’’ + ‘‘doi’’are ca rezultat’’unudoi’’;

• strcmp(sir1, sir2) - ˆıntoarce rezultatul comp˘ar˘arii lexicografice a celor dou˘a ¸siruri: -1 dac˘a sir1<sir2, 0 dac˘asir1=sir2, ¸si +1 dac˘asir1>sir2;

• strlen(sir)- ˆıntoarce lungimea ¸sirului dat ca parametru;

• strcmp(sir1, sir2)- realizeaz˘a copierea ¸siruluisir2ˆınsir1.

2.1.6.3 Structuri

O structur˘aeste un ansamblu eterogen de variabile, numite cˆampuri, ˆın care fiecare cˆamp are propriul s˘au nume ¸si propriul s˘au tip. Numele complet al unui cˆamp se obt¸ine din numele structurii urmat de caracterul “.” ¸si numele cˆampului. Memoria alocat˘a unei structuri este o secvent¸˘a contigu˘a de locat¸ii, cˆate o locat¸ie pentru fiecare cˆamp. Ordinea de memorare a cˆampurilor corespunde cu ordinea de descriere a acestora ˆın cadrul structurii. Ca exemplu, presupunem c˘a o figur˘af este descris˘a de dou˘a cˆampuri:

f.pozitie- punctul care precizeaz˘a pozit¸ia figurii, ¸sif.vizibil- valoare booleana care precizeaz˘a dac˘a figura este desenat˘a sau nu. La rˆandul s˘au, punctul poate fi v˘azut ca o structur˘a cu dou˘a cˆampuri - cˆate unul pentru fiecare coordonat˘a (consider˘am numai puncte ˆın plan avˆand coordonate ˆıntregi). Structurile sunt reprezentate grafic ca ˆın fig. 2.8. Pentru identificarea cˆampurilor unei structuri referite indirect prin intermediul unui pointer vom utiliza o notat¸ie similar˘a celei utilizate ˆın limbajul C (a se vedea ¸si fig.

2.9).

2.1.6.4 Liste liniare simplu ˆınl˘ant¸uite

O list˘a liniar˘a simplu ˆınl˘ant¸uit˘a este o ˆınl˘ant¸uire de structuri, numite noduri, ˆın care fiecare nod, ex- ceptˆand ultimul, “cunoa¸ste” adresa nodului de dup˘a el (nodul succesor). ˆIn forma sa cea mai simpl˘a, un nod veste o structur˘a cu dou˘a cˆampuri: un cˆamp v->eltpentru memorarea informat¸iei ¸si un cˆamp v->succ care memoreaz˘a adresa nodului succesor. Se presupune c˘a se cunosc adresele primului ¸si re- spectiv ultimului nod din list˘a. O list˘a liniar˘a simplu ˆınl˘ant¸uit˘a este reprezentat˘a grafic ca ˆın fig. 2.10.

List˘a liniar˘a simplu ˆınl˘ant¸uit˘a este o structur˘a de date dinamic˘a ˆın sensul c˘a pot fi inserate sau eliminate noduri cu condit¸ia s˘a fie p˘astrat˘a proprietatea de ˆınl˘ant¸uire liniar˘a. Operat¸iile elementare ce se pot

(11)

pp->y

pp punct*

pp->x (*pp).x

(*pp).y

Figura 2.9: Structuri ¸si pointeri

0 elt2 eltn-1

elt elt1 . . .

L.prim L.ultim

Figura 2.10: List˘a liniar˘a simplu ˆınl˘ant¸uit˘a efectua asupara unei liste simplu ˆınl˘ant¸uite sunt:

• ad˘augarea unui nod la ˆınceput (a se vedea figura 2.11):

procedure adLaInc(L, e) begin

new(v) v->elt← e if (L = NULL)

then L.prim ← v /* lista vida */

L.ultim ← NULL v->succ ← NULL

else v->succ ← L.prim /* lista nevida */

L.prim ← v end

• ad˘augarea unui nod la sfˆar¸sit (a se vedea figura 2.12):

procedure adLaSf(L, e) begin

new(v) v->elt← e v->succ ← NULL if (L = NULL)

then L.prim ← v /* lista vida */

L.ultim ← NULL

else L.ultim->succ ← v /* lista nevida */

L.ultim ← v end

• ¸stergerea nodului de la ˆınceput:

procedure stLaInc(L)

(12)

n−1 elt

e

elt

elt0 e

0

elt n−1

b) Lista initiala nevida a) Lista initiala vida L.ultim

L.prim

. . . L.ultim L.prim

L.prim

. . . L.ultim

L.ultim L.prim

Figura 2.11: Ad˘augarea unui nod la ˆınceputul unei liste

0

elt eltn−1

n−1

0

elt elt

e . . .

L.ultim L.prim

. . .

L.prim L.ultim

Figura 2.12: Ad˘augarea unui nod la sfˆar¸situl unei liste

(13)

e1 e2

e0 . . . en-1

L.prim L.ultim

Figura 2.13: List˘a liniar˘a dublu ˆınl˘ant¸uit˘a begin

if (L 6= NULL)

then v ← L.prim /* lista nevida */

L.prim ← L.prim->succ

if (L.ultim = v) then L.ultim ← NULL delete v

end

• ¸stergerea nodului de la sfˆar¸sit:

procedure stLaSf(L, e) begin

if (L 6= NULL)

then v ← L.prim /* lista nevida */

if (L.ultim = v) /* un singur nod */

then L.prim ← NULL L.ultim ← NULL delete v

else /* mai multe noduri */

/* determina penultimul */

while (v->succ 6= NULL) do v ← v->succ

L.ultim ← v delete v->succ end

Aceast˘a structur˘a va fi utilizat˘a la reprezentarea obiectelor de tip dat˘a a tipurilor de date de nivel ˆınalt din capitolul 3.

2.1.6.5 Liste liniare dublu ˆınl˘ant¸uite

Listele liniare dublu ˆınl˘ant¸uitesunt asem˘an˘atoare celor simplu ˆınl˘ant¸uite cu deosebirea c˘a, ˆın plus, fiecare nod, exceptˆand primul, “cunoa¸ste” adresa nodului din fat¸a sa (nodul predecesor). Astfel, un nod vare un cˆamp ˆın plusv->pred care memoreaz˘a adresa nodului predecesor. O list˘a liniar˘a dublu ˆınl˘ant¸uit˘a este reprezentat˘a grafic ca ˆın fig. 2.13.

2.1.7 Calculul unui program

Intuitiv, calculul (execut¸ia) unui program const˘a ˆın succesiunea de pa¸si elementari determinat¸i de execut¸iile instruct¸iunilor ce compun programul. Fie, de exemplu, urm˘atorul program:

x← 0 i← 1

while (i < 10) do x← x*10+i i← i+2

Calculul descris de acest program ar putea fi descris de urm˘atorul tabel:

(14)

Pasul Instruct¸iunea i x

0 x← 0 – –

1 i← 1 – 0

2 x← x*10+i 1 0

3 i← i+2 1 1

4 x← x*10+i 3 1

5 i← i+2 3 13

6 x← x*10+i 5 13

7 i← i+2 5 135

8 x← x*10+i 7 135

9 i← i+2 7 1357

10 x← x*10+i 9 1357

11 i← i+2 9 13579

12 11 13579

Acest calcul este notat formal printr-o secvent¸˘ac0`-c1`-· · · `-c12. Prin ci am notat configurat¸iile ce intervin ˆın calcul. Oconfigurat¸ie include instruct¸iunea curent˘a (starea programului) ¸si starea memoriei (valorile curente ale variabilelor din program). ˆIn exemplul de mai sus, o configurat¸ie este reprezentat˘a de o linie ˆın tabel. Relat¸ia ci−1`-ci are urm˘atoarea semnificat¸ie: prin execut¸ia instruct¸iunii dinci−1, se transform˘aci−1ˆınci. c0se nume¸steconfigurat¸ie init¸ial˘aiarc12configurat¸ie final˘a. Not˘am c˘a pot exista

¸si calcule infinite. De exemplu instruct¸iunea while (true) do

i← i+1

genereaz˘a un calcul infinit.

2.1.8 Exercit¸ii

Exercit¸iul 2.1.1. O sect¸iune a tabloului a, notat˘a a[i..j], este format˘a din elementele a[i],a[i+ 1], . . . ,a[j], i≤j. Suma unei sect¸iuni este suma elementelor sale. S˘a se scrie un program care, aplicˆand tehnica de la problema platourilor [Luc93], determin˘a sect¸iunea de sum˘a maxim˘a.

Exercit¸iul 2.1.2. S˘a se scrie o funct¸ie care, pentru un tabloub, determin˘a valoarea predicatului:

P ≡ ∀i, j: 1≤i < j≤n⇒b[i]≤b[j]

S˘a se modifice acest subprogram astfel ˆıncˆat s˘a ordoneze cresc˘ator elementele unui tablou.

Exercit¸iul 2.1.3. S˘a se scrie un subprogram tip funct¸ie care, pentru un tablou de valori booleene b, determin˘a valoarea predicatului:

P ≡ ∀i, j : 1≤i≤j≤n⇒b[i]⇒b[j])

Exercit¸iul 2.1.4. Se consider˘a tabloulaordonat cresc˘ator ¸si tabloulbordonat descresc˘ator. S˘a se scrie un program care determin˘a cel mai micx, cˆand exist˘a, ce apare ˆın ambele tablouri.

Exercit¸iul 2.1.5. Se consider˘a dou˘a tablourila¸sib. Ambele tablouri au proprietatea c˘a oricare dou˘a elemente sunt distincte. S˘a se scrie un program care determin˘a elementele x, cˆand exist˘a, ce apar ˆın ambele tablouri. S˘a se compare complexitatea timp acestui algoritm cu cea a algoritmului din 2.1.4. Ce se poate spune despre complexit˘at¸ile celor dou˘a probleme?

Exercit¸iul 2.1.6. S˘a se proiecteze structuri pentru reprezentarea punctelor ¸si respectiv a dreptelor din plan. S˘a se scrie subprograme care s˘a rezolve urm˘atoarele probleme:

(i) Apartenent¸a unui punct la o dreapt˘a:

Instant¸˘a O dreapt˘ad¸si un punctP. ˆIntrebare P ∈d?

(15)

(ii) Intersect¸ia a dou˘a drepte:

Intrare Dou˘a drepted1¸sid2. Ie¸sire d1∩d2.

(iii) Test de perpendicularitate:

Instant¸˘a Dou˘a drepted1 ¸sid2. ˆIntrebare d1⊥d2?

(iv) Test de paralelism:

Instant¸˘a Dou˘a drepted1 ¸sid2. ˆIntrebare d1kd2?

Exercit¸iul 2.1.7. S˘a se proiecteze o structur˘a pentru reprezentarea numerelor complexe. S˘a se scrie subprograme care realizeaz˘a operat¸ii din algebra numerelor complexe.

Exercit¸iul 2.1.8. Presupunem c˘a numerele complexe sunt reprezentate ca ˆın solut¸ia exercit¸iului 2.1.7.

Un polinom cu coeficient¸i complec¸si poate fi reprezentat ca un tablou de articole. S˘a se scrie un sub- program care, pentru un polinom cu coeficient¸i complec¸si P ¸si un num˘ar complex z date, calculeaz˘a P(z).

Exercit¸iul 2.1.9. O fi¸s˘a ˆıntr-o bibliotec˘a poate cont¸ine informat¸ii despre o carte sau o revist˘a. Informat¸iile care intereseaz˘a despre o carte sunt: autor, titlu, editur˘a ¸si an aparit¸ie, iar cele despre o revist˘a sunt:

titlu, editur˘a, an, volum, num˘ar. S˘a se defineasc˘a un tip de date articol cu variante pentru reprezentarea unei fi¸se.

Exercit¸iul 2.1.10. S˘a se proiecteze o structur˘a de date pentru reprezentarea datei calendaristice. S˘a se scrie subprograme care realizeaz˘a urm˘atoarele:

(i) Decide dac˘a valoarea unei variabile din structur˘a cont¸ine o dat˘a valid˘a.

(ii) Avˆand la intrare o dat˘a calendaristic˘a ofer˘a la ie¸sire data calendaristic˘a urm˘atoare.

(iii) Avˆand la intrare o dat˘a calendaristic˘a ofer˘a la ie¸sire data calendaristic˘a precedent˘a.

Exercit¸iul 2.1.11. S˘a se scrie tipurile ¸si instruct¸iunile care construiesc listele ˆınl˘ant¸uite din fig. 2.14.

Se va utiliza cel mult o variabil˘a referint¸˘a suplimentar˘a.

Exercit¸iul 2.1.12. S˘a se scrie un subprogram care inverseaz˘a sensul leg˘aturilor ˆıntr-o list˘a simplu ˆınl˘ant¸uit˘a astfel ˆıncˆat primul nod devine ultimul ¸si ultimul nod devine primul.

Exercit¸iul 2.1.13. Se consider˘a un tablou unidimensional de dimensiune mare care cont¸ine elemente alocate (ocupate) ¸si elemente disponibile. Ne putem imagina c˘a acest tablou reprezint˘a memoria unui calculator (element al tabloului = cuvˆant de memorie). Zonele ocupate (sau zonele libere) din tablou sunt gestionate cu ajutorul unei liste ˆınl˘ant¸uite. Asupra tabloului se execut˘a urm˘atoarele operat¸ii:

• Aloc˘a(m) - determin˘a o secvent¸˘a de elemente succesive de lungime m, apoi adresa ¸si lungimea acesteia le adaug˘a ca un nou element la lista zonelor ocupate (sau o elimin˘a din lista zonelor libere)

¸si ˆıntoarce adresa zonei determinate; dac˘a nu se poate aloca o asemenea secvent¸˘a ˆıntoarce -1 (sau alt˘a adres˘a invalid˘a ˆın tablou).

• Elibereaz˘a(a, l) - disponibilizeaz˘a secvent¸a de lungimelˆıncepˆand cu adresaa; lista zonelor ocupate (sau a zonelor libere) va fi actualizat˘a corespunz˘ator.

• Colecteaz˘a- rea¸seaz˘a zonele ocupate astfel ˆıncˆıt s˘a existe o singur˘a zon˘a disponibil˘a (compactificarea zonelor disponibile); lista zonelor ocupate (¸sau a zonelor libere) va fi actualizat˘a corespunz˘ator.

(16)

0C0

0E0 • • • •

0D0

0A0

0B0

?

6

?

?

6

?

-

0B0 nil

0E0 • •

0D0

0A0

0C0 • 6 6

6 6

a)

b)

-

Figura 2.14:

Observat¸ie. Pentru funct¸ia de alocare se consider˘a urm˘atoarele dou˘a strategii:

• FirstFit- aloc˘a prima zon˘a disponibil˘a de lungime≥m;

• BestFit- aloc˘a cea mai mic˘a zon˘a de m˘arime≥m.

S˘a se proiecteze structurile de date ¸si subprogramele care s˘a realizeze operat¸iile descrise mai sus.

Exercit¸iul 2.1.14. Se consider˘a problema aloc˘arii memoriei din exercit¸iul 2.1.13. S˘a se proiecteze o structur˘a de date pentru gestionarea memoriei cˆand toate cererile au acee¸si lungimek. Mai este necesar˘a colectarea zonelor neutilizate? S˘a se scrie proceduri care aloc˘a ¸si elibereaz˘a zone de memorie utilizˆand aceast˘a structur˘a.

2.2 Probleme ¸si programe

Un algoritm constituie solut¸ia unei probleme specifice. Descrierea algoritmului ˆıntr-un limbaj algoritmic se face prin intermediul unui program. ˆIn aceast˘a sect¸iune vom preciza condit¸iile pe care trebuie s˘a le ˆındeplineasc˘a un program pentru a descrie un algoritm, adic˘a ce ˆınseamn˘a c˘a un program descrie o solut¸ie pentru o problem˘a dat˘a.

2.2.1 Not¸iunea de problem˘ a

O problem˘a are dou˘a componente: domeniul, care descrie elementele care intervin ˆın problem˘a ¸si relat¸iile dintre aceste elemente, ¸si o ˆıntrebare despre propriet˘at¸ile anumitor elemente sau o cerint¸˘a de determinare a unor elemente ce au o anumit˘a proprietate. ˆIn funct¸ie de scopul urm˘arit, exist˘a mai multe moduri de a formaliza o problem˘a. Noi vom utiliza numai dou˘a dintre ele.

Intrare/Ie¸sire. Dac˘a privim un program ca o cutie neagr˘a care transform˘a datele de intrare ˆın date de ie¸sire atunci putem formaliza problema rezolvat˘a de program ca o pereche (Intrare,Ie¸sire). Componenta Intrare descrie datele de intrare iar componenta Ie¸sire descrie datele de ie¸sire. Un exemplu simplu de problem˘a reprezentat˘a astfel este urm˘atorul:

Intrare: Un num˘ar ˆıntreg pozitivx.

Ie¸sire: Cel mai mare num˘ar prim mai mic decˆat sau egal cux.

(17)

Problem˘a de decizie. Este un caz particular de problem˘a cˆand ie¸sirea este de forma ’DA’ sau ’NU’. O astfel de problem˘a este reprezentat˘a ca o pereche (Instant¸˘a,ˆIntrebare) unde componentaInstant¸˘adescrie datele de intrare iar componenta ˆIntrebare se refer˘a, ˆın general, la existent¸a unui obiect sau a unei propriet˘at¸i. Un exemplu tipic ˆıl reprezint˘a urm˘atoarea problem˘a:

Instant¸˘a: Un num˘ar ˆıntreg x.

ˆIntrebare: Estexnum˘ar prim?

Problemele de decizie sunt preferate atˆat ˆın teoria complexit˘at¸ii cˆat ¸si ˆın teoria calculabilit˘at¸ii datorit˘a reprezent˘arii foarte simple a ie¸sirilor. Facem observat¸ia c˘a orice problem˘a admite o reprezentare sub form˘a de problem˘a de decizie, indiferent de reprezentarea sa init¸ial˘a. Un exemplu de reprezentare a unei probleme de optim ca problem˘a de decizie este dat ˆın sect¸iunea??.

De obicei, pentru reprezentarea problemelor de decizie se consider˘a o mult¸ime A, iar o instant¸˘a este de formaB⊆A, x∈A¸si ˆıntrebarea de formax∈B?.

2.2.2 Problem˘ a rezolvat˘ a de un program

Convenim s˘a consider˘am ˆıntotdeauna intr˘arile pale unei probleme P ca fiind instant¸e ¸si, prin abuz de notat¸ie, scriemp∈P.

Definit¸ia 2.1. Fie S un program ¸si P o problem˘a. Spunem c˘a o configurat¸ie init¸ial˘a c0 a lui S include instant¸a p ∈ P dac˘a exist˘a o structur˘a de dat˘a inp, definit˘a ˆın S, astfel ˆıncˆat valoarea lui inp din c0

constituie o reprezentare a lui p. Analog, spunem c˘a o configurat¸ie final˘acn a unui program S include ie¸sirea P(p) dac˘a exist˘a o structur˘a de dat˘a out, definit˘a ˆın S, astfel ˆıncˆat valoarea lui out din cn

constituie o reprezentare a lui P(p).

Definit¸ia 2.2. (Problem˘a rezolvat˘a de un program)

1. Un program S rezolv˘a o problem˘a P ˆın sensul corectitudinii totale dac˘a pentru orice instant¸˘a p, calculul unic determinat de configurat¸ia init¸ial˘a ce includepeste finit ¸si configurat¸ia final˘a include ie¸sirea P(p).

2. Un program S rezolv˘a o problem˘a P ˆın sensul corectitudinii part¸iale dac˘a pentru orice instant¸˘a p pentru care calculul unic determinat de configurat¸ia init¸ial˘a ce include p este finit, configurat¸ia final˘a include ie¸sireaP(p).

Ori de cˆate ori spunem c˘a un programS rezolv˘a o problem˘aP vom ˆınt¸elege de fapt c˘aS rezolv˘a o problem˘aPˆın sensul corectitudinii totale.

Definit¸ia 2.3. (Problem˘a rezolvabil˘a/nerezolvabil˘a)

1. O problem˘aP esterezolvabil˘adac˘a exist˘a un program care s˘a o rezolve ˆın sensul corectitudinii totale.

Dac˘aP este o problem˘a de decizie, atunci spunem c˘aP estedecidabil˘a.

2. O problem˘a de decizie P este semidecidabil˘a sau part¸ial decidabil˘a dac˘a exist˘a un program S care rezolv˘a P ˆın sensul corectitudinii part¸iale astfel ˆıncˆat calculul lui S este finit pentru orice instant¸˘a p pentru care r˘aspunsul la ˆıntrebare este ’DA’.

3. O problem˘aP estenerezolvabil˘adac˘a nu este rezolvabil˘a, adic˘a nu exist˘a un program care s˘a o rezolve ˆın sensul corectitudinii totale. Dac˘aP este o problem˘a de decizie, atunci spunem c˘aP estenedecidabil˘a.

2.2.3 Un exemplu de problem˘ a nedecidabil˘ a

Pentru a ar˘ata c˘a o problem˘a este decidabil˘a este suficient s˘a g˘asim un program care s˘a o rezolve. Mai complicat este cazul problemelor nedecidabile. ˆIn leg˘atur˘a cu acestea din urm˘a se pun, ˆın mod firesc, urm˘atoarele ˆıntreb˘ari: Exist˘a probleme nedecidabile? Cum putem demonstra c˘a o problem˘a nu este decidabil˘a? R˘aspunsul la prima ˆıntrebare este afirmativ. Un prim exemplu de problem˘a necalculabil˘a este cea cunoscut˘a sub numele de problema opririi. Not˘am cu A mult¸imea perechilor de forma hS, xi unde S este un program ¸six este o intrare pentru S, iar B este submult¸imea format˘a din acele perechi hS, xipentru care calculul luiSpentru intrareaxeste finit. Dac˘a not˘am prinS(x) (a se citiS(x) =true) faptul c˘ahS, xi ∈B, atunci problema opririi poate fi scris˘a astfel:

(18)

Problema opririi

Instant¸˘a: Un programS,x∈Z. ˆIntrebare: S(x)?

Teorema 2.1. Problema opririi nu este decidabil˘a.

Demonstrat¸ie. Un programQ, care rezolv˘a problema opririi, are ca intrare o perechehS, xi¸si se opre¸ste ˆıntotdeauna cu r˘aspunsul ’DA’, dac˘aS se opre¸ste pentru intrarea x, sau cu r˘aspunsul ’NU’, dac˘aS nu se opre¸ste pentru intrareax. FieQ0 urm˘atorul program:

while (Q(x, x) =0DA0)do /*nimic*/

Reamintim c˘aQ(x, x) =0DA0ˆınseamn˘a c˘a programul reprezentat dex se opre¸ste pentru intrareax, adic˘a propria sa codificare. Presupunem acum c˘ax este codificarea luiQ0. Exist˘a dou˘a posibilit˘at¸i.

1. Q0 se opre¸ste pentru intrareax. Rezult˘aQ(x, x) =0N U0, adic˘a programul reprezentat dex nu se opre¸ste pentru intrareax. Dar programul reprezentat dexeste chiarQ0. Contradict¸ie.

2. Q0 nu se opre¸ste pentru intrareax. Rezult˘aQ(x, x) = 0DA0, adic˘a programul reprezentat de x se opre¸ste pentru intrareax. Contradict¸ie.

A¸sadar, nu exist˘a un programQcare s˘a rezolve problema opririi. sfdem Observat¸ie: Rezolvarea teoremei de mai sus este strˆans legat˘a de urm˘atorul paradox logic. “Exist˘a un ora¸s cu un b˘arbier care b˘arbiere¸ste pe oricine ce nu se b˘arbiere¸ste singur. Cine b˘arbiere¸ste pe b˘arbier?”

sfobs

2.3 M˘ asurarea performant¸elor unui algoritm

Fie P o problem˘a ¸si A un algoritm pentruP. Fie c0`-Ac1· · · `-Acn un calcul finit al algoritmuluiA.

Not˘am cut(ci) timpul necesar obt¸inerii configurat¸ieicidinci−1, 1≤i≤n, ¸si cus(ci) spat¸iul de memorie ocupat ˆın configurat¸iaci, 0≤i≤n.

Definit¸ia 2.4. FieAun algoritm pentru problemaP,p∈P o instant¸˘a a problemeiP ¸sic0`-c1`-· · ·`-cn

calculul luiAcorespunz˘ator instant¸eip. Timpulnecesar algoritmuluiApentru rezolvarea instant¸eipeste:

TA(p) =

n

X

i=1

t(ci)

Spat¸iul (de memorie) necesar algoritmului Apentru rezolvarea instant¸ei peste:

SA(p) = max

0≤i≤ns(ci)

ˆIn general este dificil de calculat cele dou˘a m˘asuri ˆın funct¸ie de instant¸e. Acesta poate fi simplificat astfel. Asociem unei instant¸e p∈ P o m˘arimeg(p), care, ˆın general, este un num˘ar natural, pe care o numim m˘arimea instant¸ei p. De exemplu, g(p) poate fi suma lungimilor reprezent˘arilor corespunzˆand datelor din instant¸a p. Dac˘a reprezent˘arile datelor din pau aceea¸si lungime, atunci se poate lua g(p) egal˘a cu num˘arul datelor. Astfel dac˘apconst˘a dintr-un tablou atunci se poate luag(p) ca fiind num˘arul de elemente ale tabloului; dac˘apconst˘a dintr-un polinom se poate luag(p) ca fiind gradul polinomului (= num˘arul coeficient¸ilor minus 1); dac˘apeste un graf se poate luag(p) ca fiind num˘arul de vˆarfuri sau num˘arul de muchii etc.

Definit¸ia 2.5. FieA un algoritm pentru problemaP.

(19)

1. Spunem c˘aA rezolv˘a Pˆın timpulTAf av(n) dac˘a:

TAf av(n) = inf

TA(p)|p∈P, g(p) =n 2. Spunem c˘aA rezolv˘a Pˆın timpulTA(n) dac˘a:

TA(n) = sup

TA(p)|p∈P, g(p) =n 3. Spunem c˘aA rezolv˘a Pˆın spat¸iulSf avA (n)dac˘a:

SAf av(n) = inf

sa(p)|p∈P, g(p) =n 4. Spunem c˘aA rezolv˘a Pˆın spat¸iulSA(n)dac˘a:

SA(n) = sup

sa(p)|p∈P, g(p) =n

Funct¸ia TAf av (SAf av) se nume¸ste complexitatea timp (spat¸iu) a algoritmului A pentru cazul cel mai favorabiliar funct¸ia TA (SA) se nume¸stecomplexitatea timp (spat¸iu) a algoritmuluiApentru cazul cel mai nefavorabil.

Exemplu: Consider˘am problema c˘aut˘arii unui element ˆıntr-un tablou:

Problema P

Intrare: n,(a0, . . . , an−1), znumere ˆıntregi.

Ie¸sire: poz=

(min{i|ai=z} dac˘a{i|ai=z} 6=∅,

−1 altfel.

Presupunem c˘a secvent¸a (a1, . . . , an) este memorat˘a ˆın tabloul (a[i]|1≤i≤n). Algoritmul descris de urm˘atorul program rezolv˘aP:

i← 0

while (a[i] 6= z) and (i < n-1) do i← i+1

if (a[i] = z) then poz← i else poz← -1

Convenim s˘a not˘am acest algoritm cu A. Consider˘am ca dimensiune a problemei P num˘aruln al ele- mentelor din secvent¸a ˆın care se caut˘a. Deoarece suntem cazul cˆand toate datele sunt memorate pe cˆate un cuvˆant de memorie, vom presupune c˘a toate operat¸iile necesit˘a o unitate de timp. Mai ˆıntˆai calcul˘am complexit˘at¸ile timp. Cazul cel mai favorabil este obt¸inut cˆanda[0] =z¸si se efectueaz˘a trei comparat¸ii ¸si dou˘a atribuiri. Rezult˘aTAf av(n) = 3 + 2 = 5. Cazul cel mai nefavorabil se obt¸ine cˆandz6∈ {a0, . . . , an−1} sauz=a[n−1] ¸si ˆın acest caz sunt executate 2n+1 comparat¸ii ¸sin+1 atribuiri. Rezult˘aTA(n) = 3n+2.

Pentru simplitatea prezent˘arii, nu au mai fost luate ˆın considerare operat¸iileand¸si operat¸iile de adunare

¸si sc˘adere. Complexitatea spat¸iu pentru ambele cazuri esten+ 6. sfex Observat¸ie: Complexit˘at¸ile pentru cazul cel mai favorabil nu ofer˘a informat¸ii relevante despre eficient¸a algoritmului. Mult mai semnificative sunt informat¸iile oferite de complexit˘at¸ile ˆın cazul cel mai nefavor- abil: ˆın toate celelalte cazuri algoritmul va avea performant¸e mai bune sau cel put¸in la fel de bune.

Pentru complexitatea timp nu este necesar totdeauna s˘a num˘ar˘am toate operat¸iile. Pentru exemplul de mai sus, observ˘am c˘a operat¸iile de atribuire (f˘ar˘a cea init¸ial˘a) sunt precedate de comparat¸ii. Astfel c˘a putem num˘ara numai comparat¸iile, pentru c˘a num˘arul acestora domin˘a num˘arul atribuirilor. Putem merge chiar mai departe ¸si s˘a num˘ar˘am numai comparat¸iile ˆıntrez¸si componentele tabloului. sfobs Exist˘a situat¸ii cˆand instant¸elepcug(p) = npentru careTA(p) este egal˘a cuTA(n) sau ia valori foarte apropiate deTA(n) apar foarte rar. Pentru aceste cazuri este preferabil s˘a calcul˘am comportarea ˆın medie

(20)

a algoritmului. Pentru a putea calcula comportarea ˆın medie este necesar s˘a privim m˘arimea TA(p) ca fiind o variabil˘a aleatoare (o experient¸˘a = execut¸ia algoritmului pentru o instant¸˘ap, valoarea experient¸ei

= durata execut¸iei algoritmului pentru instant¸a p) ¸si s˘a preciz˘am legea de repartit¸ie a acestei variabile aleatoare. Apoi,comportarea ˆın medie (complexitatea medie)se calculeaz˘a ca fiind media acestei variabile aleatoare (consider˘am numai cazul complexit˘at¸ii timp):

TAmed(n) =M({TA(p)|p∈P∧g(p) =n})

Dac˘a mult¸imea valorilor variabilei aleatoareTA(p) este finit˘a ,x1, . . . , xk, ¸si probabilitatea caTA(p) =xi

estepi, atunci media variabilei aleatoareTA(complexitatea medie) este:

TAmed(n) =

k

X

i=1

xi·pi

Exemplu: Consider˘am problema P din exemplul anterior. Mult¸imea valorilor variabilei aleatoare TA(p) este{3i+ 2|1≤i≤n}. ˆIn continuare trebuie s˘a stabilim legea de repartit¸ie. Facem urm˘atoarele presupuneri: probabibilitatea caz∈ {a1, . . . , an}esteq¸sipoz=icu probabilitateaq

n(indiciiicandideaz˘a cu aceea¸si probabilitate pentru prima aparit¸ie a luiz). Rezult˘a c˘a probabilitatea caz6∈ {a1, . . . , an}este 1−q. Acum probabilitatea caTA(p) = 3i+ 2 (poz=i) este q

n, pentru 1≤i < n, iar probabilitatea ca TA(p) = 3n+ 2 estepn= q

n+ (1−q) (probabilitatea capoz=nsau caz6∈ {a1, . . . , an}). Complexitatea medie este:

TAmed(n) =

n

P

i=1

pixi=

n−1

P

i=1

nq ·(3i+ 2) + (q

n + (1−q))·(3n+ 2)

= 3q n ·Pn

i=1

i+q n

n

P

i=1

2 + (1−q)·(3n+ 2)

= 3q

n ·n(n+ 1)

2 + 2q+ (1−q)·(3n+ 2)

= 3q·(n+ 1)

2 + 2q+ (1−q)·(3n+ 2)

= 3n−3nq 2 +3q

2 + 2

Pentruq= 1 (z apare totdeauna ˆın secvent¸˘a) avemTAmed(n) = 3n 2 +7

2 ¸si pentruq= 12 avemTAmed(n) = 9n4 +11

4 . sfex

Exemplu: FieP0 urm˘atoarea problem˘a: dat un num˘ar natural n≤N M ax, s˘a se determine cel mai mic num˘ar naturalxcu proprietatean≤2x. P0 poate fi rezolvat˘a prin metoda c˘aut˘arii secvent¸iale:

x← 0 doilax← 1

while (n > doilax) do x← x+1

doilax← doilax * 2

Dac˘a se ia dimensiunea problemei egal˘a cun, atunci exist˘a o singur˘a instant¸˘a a problemeiP0 pentru un nfixat ¸si deci cele trei complexit˘at¸i sunt egale. Dac˘a se ia dimensiunea problemei ca fiindN M ax, atunci cele trei complexit˘at¸i se calculeaz˘a ˆıntr-o manier˘a asem˘an˘atoare cu cea de la exercit¸iul precedent. sfex

2.3.1 Calcul asimptotic

ˆIn practic˘a, atˆat TA(n) cˆat ¸si TAmed(n) sunt dificil de evaluat. Din acest motiv se caut˘a, de multe ori, margini superioare ¸si inferioare pentru aceste m˘arimi. Urm˘atoarele clase de funct¸ii sunt utilizate cu succes ˆın stabilirea acestor margini:

O(f(n)) ={g(n)|(∃c >0, n0≥0)(∀n≥n0)|g(n)| ≤c· |f(n)|}

Ω(f(n)) ={g(n)|(∃c >0, n0≥0)(∀n≥n0)|g(n)| ≥c· |f(n)|}

Θ(f(n)) ={g(n)|(∃c1, c2>0, n0≥0)(∀n≥n0)c1· |f(n)| ≤ |g(n)| ≤c2· |f(n)|}

(21)

Cu notat¸iileO, Ω ¸si Θ se pot forma expresii ¸si ecuat¸ii. Consider˘am numai cazulO, celelalte tratˆandu-se similar. Expresiile construite cu Opot fi de forma:

O(f1(n)) opO(f2(n)) unde “op” poate fi +,−,∗etc. ¸si noteaz˘a mult¸imile:

{g(n)|(∃g1(n), g2(n), c1, c2>0, n1, n2>1)((∀n)g(n) =g1(n) opg2(n)∧ (∀n≥n1)g1(n)≤c1f1(n)∧(∀n≥n2)g2(n)≤c2f2(n))}

De exemplu:

O(n) +O(n2) ={f(n) =f1(n) +f2(n)|(∀n≥n1)f1(n)≤c1n∧(∀n≥n2)f2(n)≤c2n2} Utilizˆand regulile de asociere, se obt¸in expresii de orice lungime:

O(f1(n)) op1O(f2(n)) op2 · · ·

Orice funct¸ief(n) o putem gˆandi ca o notat¸ie pentru mult¸imea cu un singur elementf(n) ¸si deci putem forma expresii de forma:

f1(n) +O(f2(n)) ca desemnˆand mult¸imea:

{f1(n) +g(n)|(∃c >0, n0>1)(∀n≥n0)g(n)≤c·f2(n)} Peste expresii consider˘am “ecuat¸ii” de forma:

expr1 =expr2

cu semnificat¸ia c˘a mult¸imea desemnat˘a de expr1 este inclus˘a ˆın mult¸imea desemnat˘a de expr2. De exemplu, avem:

nlogn+O(n2) =O(n2)

pentru c˘a (∃c1>0, n1>1)(∀n≥n1)nlogn≤c1n2, dac˘ag1(n)∈O(n2) atunci (∃c2>0, n2>1)(∀n≥ n2)g1(n) ≤ c2n2 ¸si de aici (∀n ≥ n0)g(n) = nlogn+g1(n) ≤ nlogn+c2n2 ≤ (c1 +c2)n2, unde n0= max{n1, n2}. De remarcat nesimetria ecuat¸iilor: p˘art¸ile stˆanga ¸si cea dreapt˘a joac˘a roluri distincte.

Ca un caz particular, notat¸iaf(n) =O(g(n)) semnific˘a de faptf(n)∈O(g(n)).

Notat¸iile O,Ω ¸si Θ ofer˘a informat¸ii cu care putem aproxima comportarea unei funct¸ii. Pentru ca aceast˘a aproximare s˘a aib˘a totu¸si un grad de precizie cˆat mai mare, este necesar ca mult¸imea desemnat˘a de partea dreapt˘a a ecuat¸iei s˘a fie cˆat mai mic˘a. De exemplu, avem atˆat 3n=O(n) cˆat ¸si 3n=O(n2).

Prin incluziunea O(n) =O(n2) rezult˘a c˘a prima ecuat¸ie ofer˘a o aproximare mai bun˘a. De fiecare dat˘a vom c˘auta mult¸imi care aproximeaz˘a cel mai bine comportarea unei funct¸ii.

Cu notat¸iile de mai sus, dou˘a programe, care rezolv˘a aceea¸si problem˘a, pot fi comparate numai dac˘a au complexit˘at¸ile ˆın clase diferite. De exemplu, un algoritmA cuTA(n) =O(n) este mai eficient decˆat un algoritm A0 cu TA0(n) = O(n2). Dac˘a cei doi algoritmi au complexit˘at¸ile ˆın aceea¸si clas˘a, atunci compararea lor devine mai dificil˘a pentru c˘a trebuie determinate ¸si constantele cu care se ˆınmult¸esc reprezentant¸ii clasei.

2.3.2 Complexitatea problemelor

ˆIn continuare extindem not¸iunea de complexitate la cazul problemelor.

Definit¸ia 2.6. Problema P are complexitatea timp (spat¸iu) O(f(n)) ˆın cazul cel mai nefavorabildac˘a exist˘a un algoritm Acare rezolv˘a problema Pˆın timpul TA(n) =O(f(n)) (spat¸iulSA(n) =O(f(n))).

Problema P are complexitatea timp (spat¸iu) Ω(f(n)) ˆın cazul cel mai nefavorabildac˘a orice algoritm A pentruP are complexitatea timpTA(n) = Ω(f(n))(spat¸iuSA(n) = Ω(f(n))).

Problema P are complexitatea Θ(f(n)) ˆın cazul cel mai nefavorabil dac˘a are simultan complexitatea Ω(f(n))¸si complexitatea O(f(n)).

(22)

Observat¸ie: Definit¸ia de mai sus necesit˘a cˆateva comentarii. Pentru a ar˘ata c˘a o anumit˘a problem˘a are complexitateaO(f), este suficient s˘a g˘asim un algoritm pentruP care are complexitateaO(f(n)). Pentru a ar˘ata c˘a o problem˘a are complexitatea Ω(f(n)) este necesar de ar˘atat c˘a orice algoritm pentru P are complexitatea ˆın cazul cel mai nefavorabil ˆın clasa Ω(f(n)). ˆIn general, acest tip de rezultat este dificil de ar˘atat, dar este util atunci cˆand dorim s˘a ar˘at˘am c˘a un anumit algoritm este optimal. Complexitatea unui algoritm optimal apart¸ine clasei de funct¸ii care d˘a limita inferioar˘a pentru acea problem˘a. sfobs

2.3.3 Calculul complexit˘ at¸ii timp pentru cazul cel mai nefavorabil

Un algoritm poate avea o descriere complex˘a ¸si deci evaluarea sa poate pune unele probleme. De aceea prezent˘am cˆateva strategii ce sunt aplicate ˆın determinarea complexit˘at¸ii timp pentru cazul cel mai nefavorabil. Deoarece orice algoritmul este descris de un program, ˆın cele ce urmeaz˘a consider˘amS o secvent¸˘a de program. Regulile prin care se calculeaz˘a complexitatea timp sunt date ˆın funct¸ie de structura luiS:

1. Seste o instruct¸iune de atribuire. Complexitatea timp a luiSeste egal˘a cu complexitatea evalu˘arii expresiei din partea dreapt˘a.

2. S este forma:

S1

S2

Complexitatea timp a luiS este egal˘a cu suma complexit˘at¸ilor programelorS1 ¸siS2.

3. S este de formaifethenS1 elseS2. Complexitatea timp a lui S este egal˘a cu maximul dintre complexit˘at¸ile programelorS1¸siS2 la care se adun˘a complexitatea evalu˘arii expresieie.

4. Seste de formawhileedoS1. Se determin˘a cazul cˆand se execut˘a num˘arul maxim de execut¸ii ale bucleiwhile¸si se face suma timpilor calculat¸i pentru fiecare iterat¸ie. Dac˘a nu este posibil˘a deter- minarea timpilor pentru fiecare iterat¸ie, atunci complexitatea timp a luiS este egal˘a cu produsul dintre maximul dintre timpii execut¸iilor bucleiS1 ¸si num˘arul maxim de execut¸ii ale bucleiS1. Plecˆand de la aceste reguli de baz˘a, se pot obt¸ine ˆın mod natural reguli de calcul a complexit˘at¸ii pentru toate instruct¸iunile. Consider˘am c˘a obt¸inerea acestora constituie un bun exrcit¸iu pentru cititor.

2.3.4 Exercit¸ii

Exercit¸iul 2.3.1. S˘a se arate c˘a:

1. 7n2−23n= Θ(n2).

2. n! =O(nn).

3. n! = Θ(nn).

4. 5n2+nlogn= Θ(n2).

5. Pn

i=1ik = Θ(nk+1).

6. nk

logn =O(nk) (k >0).

7. n5+ 2n=O(2n).

8. log5n=O(log2n).

Exercit¸iul 2.3.2. S˘a se determine complexitatea timp, pentru cazul cel mai nefavorabil, a algoritmului descris de urm˘atorul program:

(23)

x← a y← b z← 1

while (y > 0) do

if (y impar) then z← z*x y← y div 2

x← x*x

Indicat¸ie. Se va t¸ine cont de faptul c˘a programul calculeaz˘az=abnot= f(a, b) dup˘a formula

f(u, v) =





1 ,dac˘av= 0 uv−1∗u ,dac˘a v este impar (uv2)2 ,dac˘a v este par.

Exercit¸iul 2.3.3. S˘a se determine complexitatea timp a algoritmului descris de urm˘atorul program:

x← a y← b s← 0

while x<>0 do

while not odd(x) do y← 2*y

x← x div 2 s← s+y

x← x-1

Exercit¸iul 2.3.4. S˘a se scrie un program care pentru un tablou unidimensional dat, determin˘a dac˘a toate elementele tabloului sunt egale sau nu. S˘a se determine complexit˘at¸ile timp pentru cazul cel mai nefavorabil ¸si ˆın medie ale algoritmului descris de program.

Exercit¸iul 2.3.5. Se consider˘a polinomul cu coeficient¸i realip=a0+a1x+· · ·+anxn ¸si punctulx0. a) S˘a se scrie un program care s˘a calculeze valoarea polinomuluipˆınx0, utilizˆand formula:

p(x0) =

n

X

i=0

ai·xi0

b) S˘a se ˆımbun˘at˘at¸easc˘a programul de mai sus, utilizˆand relat¸iaxi+10 =xi0·x0.

c) S˘a se scrie un program care s˘a calculeze valoarea polinomului pˆın x0, utilizˆand formula (schema lui Horner):

p(x0) =a0+ (· · ·+ (an−1+an·x0)· · ·)

Pentru fiecare dintre cele trei cazuri, s˘a se determine num˘arul de ˆınmult¸iri ¸si de adun˘ari ¸si s˘a se compare.

Care metod˘a este cea mai eficient˘a?

Exercit¸iul 2.3.6. S˘a se scrie un program care caut˘a secvent¸ial ˆıntr-un tablou ordonat. S˘a se determine complexit˘at¸ile timp pentru cazul cel mai nefavorabil ¸si ˆın medie, ale algoritmului descris de program.

(24)

Capitolul 3

Tipuri de date de nivel ˆınalt

3.1 Lista liniar˘ a

3.1.1 Tipul de date abstract LLIN

3.1.1.1 Descrierea obiectelor de tip dat˘a

Olist˘a liniar˘aeste o secvent¸˘a finit˘a (e0, . . . , en−1) ˆın care elementeleeiapart¸in unui tip datElt. Compo- nentele unei liste nu trebuie s˘a fie neap˘arat distincte; adic˘a, putem aveai6=j ¸siei=ej. Lungimeaunei listeL= (e0, . . . , en−1), notat˘a cuLung(L), este dat˘a de num˘arul de componente din list˘a: Lung(L) =n.

Lista vid˘a( ) este lista f˘ar˘a nici o component˘a (de lungime 0).

3.1.1.2 Operat¸ii.

ListaVid˘a. ˆIntoarce lista vid˘a.

Intrare: – nimic;

Ie¸sire: – lista vid˘a ( ).

EsteVid˘a. Testeaz˘a dac˘a o list˘a dat˘a este vid˘a.

Intrare: – o list˘a liniar˘aL;

Ie¸sire: –truedac˘aL= ( ), –falsedac˘aL6= ( ).

Lung. ˆIntoarce lungimea unei listei date.

Intrare: – o list˘a liniar˘aL= (e0, . . . , en−1) cun≥0;

Ie¸sire: –n.

Copie. ˆIntoarce o copie distinct˘a a unei liste date.

Intrare: – o list˘a liniar˘aL;

Ie¸sire: – o copieL0 distinct˘a a luiL.

Egal. Testeaz˘a dac˘a dou˘a liste liniare sunt egale.

Intrare: – dou˘a listeL= (e0, . . . , en−1) ¸siL0 = (e00, . . . , e0n0−1);

Ie¸sire: –truedac˘an=n0 ¸sie0=e00, . . . , en−1=e0n−1, –false, ˆın celelalte cazuri.

(25)

Poz. Caut˘a dac˘a un element datx apare ˆıntr-o list˘a liniar˘a dat˘aL.

Intrare: – o list˘a liniar˘aL= (e0, . . . , en−1) ¸si un elementx dinElt;

Ie¸sire: – adres˘a invalid˘a (−1 sau NULL) dac˘ax nu apare ˆınL, – adresa elementului ei dac˘aei =x¸si (∀j)0≤j < i⇒ej6=x.

Parcurge. Parcurge o list˘a liniar˘a dat˘a efectuˆand o prelucrare uniform˘a asupra componentelor acesteia.

Intrare: – o list˘a liniar˘aL¸si o procedur˘aViziteaz˘a(e);

Ie¸sire: – listaLdar ale c˘arei componente au fost prelucrate de proceduraViziteaz˘a.

Cite¸ste. ˆIntoarce elementul de la o pozit¸ie dat˘a dintr-o list˘a dat˘a.

Intrare: – o list˘a liniar˘aL= (e0, . . . , en−1) ¸si o pozit¸iek≥0;

Ie¸sire: –ek dac˘a 0≤k < n, –eroare, ˆın celelalte cazuri.

Insereaz˘a. Adaug˘a un element dat ˆıntr-o list˘a liniar˘a dat˘a la o pozit¸ie dat˘a.

Intrare: – o list˘a liniar˘aL= (e0, . . . , en−1), un elementedinElt¸si o pozit¸ie k≥0;

Ie¸sire: –L= (e0, . . . , ek−1, e, ek, . . . , en−1) dac˘a 0≤k < n, –L= (e0, . . . , en−1, e) dac˘ak≥n.

Elimin˘aDeLaK. Elimin˘a elementul de la o pozit¸ie dat˘a dintr-o list˘a liniar˘a dat˘a.

Intrare: – o list˘a liniar˘aL= (e0, . . . , en−1) ¸si o pozit¸iek≥0;

Ie¸sire: –L= (e0, . . . , ek−1, ek+1, . . . , en−1) dac˘a 0≤k < n, –L= (e0, . . . , en−1) dac˘ak≥n.

Elimin˘a. Elimin˘a un element dat dintr-o list˘a liniar˘a dat˘a.

Intrare: – o list˘a liniar˘aL= (e0, . . . , en−1) ¸si un elementedinElt;

Ie¸sire: – listaLdin care s-au eliminat toate elementeleei egale cu e.

3.1.2 Implementarea dinamic˘ a cu liste simplu ˆınl˘ ant¸uite

3.1.2.1 Reprezentarea obiectelor de tip dat˘a

O list˘a liniar˘aL= (e1, . . . , en) este reprezentat˘a printr-o list˘a ca cea din fig. 3.1. Fiecare component˘a a listei liniare este memorat˘a ˆıntr-un nod al listei simplu ˆınl˘ant¸uite. Exist˘a doi pointeriL.prim¸siL.ultim care fac referire la primul ¸si respectiv ultimul nod.

. . . n-1

L.prim L.ultim

e0 e1 e2 e

Figura 3.1: Reprezentarea listei liniare cu list˘a simplu ˆınl˘ant¸uit˘a

3.1.2.2 Implementarea operat¸iilor

ListaVid˘a. Este reprezentat˘a de lista f˘ar˘a nici un nod: L.prim=L.ultim=NULL.

EsteVid˘a. Este suficient s˘a se testeze dac˘a pointerulL.primeste egal cuNULL.

(26)

Lung. Parcurge lista ¸si contorizeaz˘a fiecare nod parcurs. Timpul necesar determin˘arii lungimii esteO(n).

Acesta poate fi redus la O(1) dac˘a lungimea ar fi inclus˘a ˆın reprezentarea listei. Aceasta ar presupune ca toate operat¸iile care modific˘a lungimea listei s˘a actualizeze corespunz˘ator variabila responsabil˘a cu memorarea lungimii.

function lung(L) begin

lg← 0 p← L.prim

while (p 6= NULL) do lg← lg+1

p← p->succ return lg end

Copie. Parcurge lista surs˘a ¸si adaug˘a la lista destinat¸ie o copie a fiec˘arui nod parcurs. Dac˘a presupunem c˘a operat¸ia de copiere a unui nod se face ˆın timpulO(t) atunci copierea ˆıntregii liste se realizeaz˘a ˆın timpul O(n·t).

procedure copie(L, Lcopie) begin

if (L.prim = NULL) then Lcopie.prim← NULL

Lcopie.ultim← NULL else new(Lcopie.prim)

Lcopie.prim->elt← L.prim->elt Lcopie.ultim← Lcopie.prim p← L.prim->succ

while (p 6= NULL) do

new(Lcopie.ultim->succ)

Lcopie.ultim← Lcopie.ultim->succ Lcopie.ultim->elt← p->elt

p← p->succ

Lcopie.ultim->succ← NULL end

Egal. Parcurge simultan cele dou˘a liste ¸si compar˘a perechile de noduri corespunz˘atoare. Dac˘a pre- supunem c˘a operat¸ia de comparare a unei perechi de noduri se face ˆın timpulO(1) atunci compararea listelor se realizeaz˘a ˆın timpul O(n) ˆın cazul cel mai nefavorabil, unde n este valoarea minim˘a dintre lungimile celor dou˘a liste.

function egal(L1, L2) begin

p1← L1.prim p2← L2.prim

while ((p1 6= NULL) and (p2 6= NULL)) do if (p1->elt 6= p2->elt) then return false p1← p1->succ

p2← p2->succ

if ((p1 = NULL) and (p2 = NULL)) then return true

else return false end

Poz. Se aplic˘a tehnica c˘aut˘arii secvent¸iale: se pleac˘a din primul nod ¸si se interogheaz˘a nod cu nod pˆan˘a cˆand este g˘asit primul care memoreaz˘a pe x sau au fost epuizate toate nodurile. Plecˆand de la ipoteza

(27)

c˘a interogarea unui nod se face ˆın timpul O(1), rezult˘a c˘a operat¸ia de c˘autare necesit˘a timpulO(n) ˆın cazul cel mai nefavorabil.

function poz(L, x) begin

p← L.prim

while (p 6= NULL) do

if (p->elt = x) then return p p← p->succ

return NULL end

Parcurge. Se parcurge lista nod cu nod ¸si se aplic˘a proceduraViziteaz˘a. Se obt¸ine un grad mai mare de aplicabilitate a operat¸iei dac˘a procedurile de tip Viziteaz˘a au ca parametru adresa unui nod ¸si nu informat¸ia memorat˘a ˆın nod. Dac˘ateste timpul necesar procedurii Viziteaz˘apentru a prelucra un nod, atunci complexitatea timp a operat¸iei de parcurgere esteO(n·t).

procedure parcurge(L, viziteaza()) begin

p← L.prim

while (p 6= NULL) do viziteaza(p) p← p->succ end

Cite¸ste. Pentru a putea citi informat¸ia din cel de-alk-lea nod, este necesar˘a parcurgerea secvent¸ial˘a a primelork-noduri. Deoarecek < n, rezult˘a c˘a avem o complexitate ˆın cazul cel mai nefavorabil egal˘a cu O(n).

function citeste(L, k) begin

p← L.prim i← 0

while ((p 6= NULL) and (i < k)) do i← i + 1

p← p->succ

if (p = NULL) then throw ‘eroare’

return p->elt end

Insereaz˘a. Ca ¸si ˆın cazul operat¸iei de citire, este necesar˘a parcurgerea secvent¸ial˘a a primelork−1 noduri (noul nod va fi al k-lea). Dac˘a avemk= 0 sauk≥Lung(L) atunci pointeriiprim¸si respectivultimse actualizeaz˘a corespunz˘ator. Deoarece operat¸ia de ad˘augare a unui nod dup˘a o adres˘a dat˘a se realizeaz˘a ˆın timpulO(1), rezult˘a c˘a operat¸ia de inserare necesit˘a timpulO(n) ˆın cazul cel mai nefavorabil.

procedure insereaza(L, k, e) begin

if (k < 0) then throw ‘eroare’

new(q) q->elt← e

if ((k = 0) or (L.prim = NULL)) then q->succ← L.prim

L.prim← q

if (L.ultim = NULL) then L.ultim← q else p← L.prim

i← 0

while ((p 6= L.ultim) and (i < k-1)) do

(28)

i← i + 1 p← p->succ q->succ← p->succ p->succ← q

if (p = L.ultim) then L.ultim← q end

Elimin˘aDeLaK. Se realizeaz˘a ˆıntr-o manier˘a asem˘an˘atoare cu cea a operat¸iei de inserare.

procedure eliminaDeLaK(L, k) begin

if ((k < 0) or (L.prim = NULL)) then throw ‘eroare’

if (k = 0) then p← L.prim

L.prim← L.prim->succ delete(p)

else p← L.prim i← 0

while ((p 6= NULL) and (i < k-1)) do i← i + 1

p← p->succ if (p 6= NULL) then q← p->succ

p->succ← q->succ

if (L.ultim = q) then L.ultim← p delete(q)

end

Elimin˘a. Se parcurge lista secvent¸ial ¸si fiecare nod care memoreaz˘a un element egal cueeste eliminat.

Eliminarea unui nod presupune cunoa¸sterea adresei nodului anterior; aceasta este determinat˘a ˆın timpul parcurgerii secvent¸iale. Dac˘a se elimin˘a primul sau ultimul nod atunci pointerii L.prim ¸si respectiv L.ultim se actualizeaz˘a corespunz˘ator. Operat¸ia de eliminare a unui nod se realizeaz˘a ˆın timpulO(1).

Dac˘a operat¸ia de comparare se realizeaz˘a ˆın timpul O(1) atunci operat¸ia de eliminare necesit˘a timpul O(n) ˆın cazul cel mai nefavorabil.

procedure elimina(L, e) begin

while ((L.prim 6= NULL) and (L.prim->elt = e)) do q← L.prim

L.prim← q->succ delete(q)

if (L.prim = NULL) then L.ultim← NULL else p← L.prim

while (p 6= NULL) do q← p->succ

if ((q 6= NULL) and (q->elt = e)) then p->succ← q->succ

if (L.ultim = q) then L.ultim← p delete(q)

p← p->succ end

(29)

3.1.3 Implementarea static˘ a cu tablouri

3.1.3.1 Reprezentarea obiectelor de tip dat˘a

O list˘a liniar˘aL= (e0, . . . , en−1) este reprezentat˘a printr-un tablouL.tab¸si o variabil˘a indiceL.ultim ca ˆın fig. 3.2. Cele ncomponente a listei liniare sunt memorate ˆın primelencomponente ale tabloului.

Dimensiunea maxim˘a a tabloului este M AX astfel c˘a vor putea fi reprezentate numai liste de lungime

≤M AX. Pointerul indiceL.ultimmemoreaz˘a adresa ˆın tablou a ultimului element din list˘a; el coincide

¸si cu lungimea listei.

1 1

0 2 n-1 MAX-1

L.tab

L.ultim

e0 e e2 en-1

Figura 3.2: Reprezentarea listei liniare cu tablouri

3.1.3.2 Implementarea operat¸iilor

ListaVid˘a. Este reprezentat˘a faptul c˘a valoarea pointerului ultimeste−1.

EsteVid˘a. Se testeaz˘a dac˘a pointerulL.ultimeste egal cu−1.

Lung. ˆIntoarce valoarea pointeruluiL.utimadunat˘a cu 1. Deci este realizat˘a ˆın timpulO(1).

function lung(L) begin

return L.ultim+1 end

Copie. Parcurge tabloul surs˘a ¸si copie fiecare component˘a parcurs˘a. Dac˘a presupunem c˘a operat¸ia de copiere a unui nod se face ˆın timpul O(t) atunci copierea ˆıntregii liste se realizeaz˘a ˆın timpulO(n·t).

procedure copie(L, Lcopie) begin

Lcopie.ultim← L.ultim for i← 0 to L.ultim do

Lcopie.tab[i]← L.tab[i]

end

Egal. Parcurge simultan cele dou˘a tablouri ¸si compar˘a perechile de componente corespunz˘atoare. Dac˘a presupunem c˘a operat¸ia de comparare a unei perechi de elemente se face ˆın timpulO(1) atunci compararea listelor se realizeaz˘a ˆın timpul O(n) ˆın cazul cel mai nefavorabil, unde n este valoarea minim˘a dintre lungimile celor dou˘a liste.

function egal(L1, L2) begin

if (L1.ultim 6= L2.ultim) then return false

else for i← 0 to L1.ultim do

if (L1.tab[i] 6= L2.tab[i]) then return false return true

end

Referințe

DOCUMENTE SIMILARE

De¸si ˆıntreb˘arile au un caracter general, ˆın sensul c˘a ¸si le poate pune orice profesor de matematic˘a (sau om de ¸stiint¸a, sau ¸si mai general, orice om) r˘aspunsurile

Dac˘a avem ˆın vedere un parametru al populat¸iei, cum ar fi media ˆıntregii populat¸ii statistice µ sau dispersia ei σ 2 (care sunt parametri ˆın cazul unei caracteristici

• nume_setare este un argument opt , ional dat de un s , ir de caractere (scris între dou˘a apostrofuri) care poate fi utilizat pentru a specifica anumite set˘ari pentru

chmod 600 fişier Un fişier privat, care poate fi schimbat doar de utilizatorul care a introdus această comandă. chmod 644 fişier Un fişier care poate fi accesat public dar care poate

elevii scriu: 3 concepte din ce au ˆınv˘ at¸at, 2 idei despre care ar dori s˘ a ˆınvet¸e mai multe ˆın continuare ¸si o capacitate pe care au dobˆ andit-o ˆın urma

Pentru a suprprinde acest aspect, cuvintele care apar m˘ acar de 5 ori ˆın datele de antrenament ¸si dac˘ a apar de 5 ori mai des ˆın glume decˆ at ˆın non-glume sunt p˘

Cea mai simpl˘a modalitate de a g˘asi o replicare pentru func¸tia de plat˘a având la dispozi¸tie instrumentele prezen- tate în enun¸t este s˘a folosim urm˘atoarea imagine...

Dac˘ a, în orice moment, parametrii c˘ auta¸ti de utilizator sunt satisf˘ acu¸ti cu toate relat , iile specificate, compozit , ia este complet˘ a, ¸si este returnat˘ a air