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
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.
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
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.
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:
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
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
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
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
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
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)
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
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:
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?
(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.
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.
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:
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.
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
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)|}
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)).
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:
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.
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.
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.
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
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
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
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