Operatia de inserare Œntr-o lista Œnlantuita

Presupune adaugarea unui element Œntr-o pozitie specificata Œn lista. Exista posibilitati diferite de a specifica pozitia Œn care vrem sa inseram elementul: s6f17fd
Situatia Œn care pozitia de inserat este data printr-un numar care sa indice al cƒtelea element trebuie sa fie Œn lista elementul inserat;
Situatia Œn care pozitia de inserat este data prin valoarea atomului dupa care sau Œnainte de care se face inserarea;
Situatia Œn care pozitia de inserat poate fi data implicit prin valoarea atomului de inserat.

Inserarea Œn fata unui element specificat

Functia Œnscrie un element Œn fata altui element dintr-o lista:

insert (l, a, b)

// l lista (pointer la primul element)
// a valoarea atomului de inserat
// b valoarea atomului Œn fata caruia se insereaza
A p=get_sp(); data(p)=a; if (l==0) or (data(l)==b) then
A link(p)=l; l=p;
S else
A q=l;
while ((link(q)!=0)and (data(link(q)!=b)) do q=link(q); link(p)=link(q); link(q)=p;
S
S

Operatia de stergere dintr-o lista Œnlantuita
Operatia delete sterge un atom dintr-o lista. Deci vom avea Œn pseudocod, o functie de forma:

delete(l, a)
// l lista
// a valoarea atomului care trebuie sters
A if l=0 then eroare ("Atomul nu se afla Œn lista") else if data(l)=a then |½ p=1
| l=link(l)
|_ ret_sp(p) else |½ q=l
| while(link(q)!=0)and(data(link(q))!=a) do
| q=link(q)
| if link(q=0) then eroare("S-a ajuns la sfƒrsitul
| listei si atomul nu a fost gasit")
| else
| p=link(q)
| link(q)=link(p)
|_ ret_sp(p)
S

Operatia de parcurgere a listei Œnlantuite
Operatia de parcurgere a listei Œnlantuite consta dintr-o secventa de instructiuni care se foloseste de fiecare data cƒnd dorim sa prelucram elementele listei Œntr-un anumit scop.
O parcurgere a listei presupune o prelucrare efectuata asupra fiecarui element din lista (asadar nu o functie, ci o secventa de instructiuni):

Fie p pointer-ul care indica pe rƒnd fiecare element al listei, si consideram ca p Œncepe cu l:

while (p!=0) do |½ prelucrare (data(p)) // ex:afisarea | //atomului
|_ p=link(p) // trece la urmatorul

Stive ordonate
O stiva este o structura de date de tip "container" (depoziteaza obiecte de un anumit tip) organizata dupa principiul LIFO (Last In First Out).
Operatiile de acces la stiva (push - adauga un element in stiva si pop - scoate un element din stiva) sunt create astfel Œncƒt pop scoate din stiva elementul introdus cel mai recent.
O stiva este un caz particular de lista, si anume este o lista pentru care operatiile de acces (inserare, stergere, accesare element) se efectueaza la un singur capat al listei.
Daca STACK este de tip stiva si ATOM tipul obiectelor continute Œn stiva atunci operatiile care definesc tipul structura de stiva pentru tipul STACK sunt:

CREATE() STACK
Operatia CREATE nu primeste parametri, creeaza o stiva care pentru Œnceput este vida (nu contine nici un obiect).
PUSH(STACK, ATOM) STACK
Operatia PUSH primeste ca parametri o stiva si un obiect si produce stiva modificata prin adaugarea obiectului Œn stiva.
POP(STACK) STACK, ATOM
Operatia POP primeste ca parametri o stiva pe care o modifica scotƒnd un obiect. De asemenea produce ca rezultat obiectul scos din stiva.
TOP(STACK) ATOM
Operatia TOP Œntoarce ca rezultat obiectul din vƒrful stivei pe care o primeste ca parametru.
ISEMPTY(STACK) boolean
Operatia ISEMPTY este folosita pentru a testa daca stiva este vida.

Facem notatiile:
S stiva
S.vect vectorul Œn care se reprezinta elementele stivei S
S.sp indicele vƒrfului stivei

Elementele sunt memorate asadar unul dupa altul Œn vectori, nefiind neaparat
Œn ordine crescatoare. Zona de memorat trebuie sa contina aceste doua informatii: S.vect si S.sp grupate Œntr-o structura:

struct Stack A int sp;
Atom vect aDIMMAXi
S;

Conditia de stiva vida este: S.sp=0
Se scrie:

push(S,a)
A if S.sp >=DIMMAX then eroare("Stiva plina") else |½ S.sp=S.sp+1
|_ S.vectaS.spi=a //atomul este pus pe prima
//pozitie
S

Functia pop scoate un element din stiva:

pop(S)
A if S.sp=0 then eroare ("Stiva vida") else S.sp=S.sp-1
S

Observatie: Se obisnuieste ca pe lƒnga stergerea elementului, functia pop sa returneze elementul scos din lista.

top(S)
A if S.sp=0 then eroare("Stiva vida") else return(S.vectaS.spi)
S

Functia isEmpty(S) testeaza conditia stiva vida: isEmpty(S)
A return(S.sp==0)
S

Stive Œnlantuite
O stiva poate fi implementata ca o lista Œnlantuita pentru care operatiile de acces se fac numai asupra primului element din lista. Deci, operatia PUSH va Œnsemna inserare Œn prima pozitie din lista (Œn fata) iar POP va Œnsemna stergerea primului element din lista. Pentru a manevra o stiva vom avea nevoie de un pointer la primul element din Œnlantuire, deci, vom echivala tipul Stack cu tipul "pointer la element de lista", iar functiile care implementeaza operatiile de acces vor avea aceleasi prototipuri cu cele date mai sus.

struct Element A
Atom data;
Element* link; //legatura
S; typedef Element* Stack;

Fie S pointer-ul la primul element din Œnlantuire, se echivaleaza tipul Stack cu typedef Element* Stack, iar conditia de stiva vida este S=0 : push(S,a)
A p=get_sp() data(p)=a link(p)=S
S=p
S

pop(S)
A if S=0 then eroare("Stiva vida") else |½ p=S;
| S=link(S)
|_ ret_sp(p)
S

top(S)
A if S=0 then eroare("Stiva vida") else return(data(S))
S isEmpty(S)
A return(S==0)
S

Stivele sunt cele mai simple structuri de date, ele avƒnd si operatiile imediate.

Cozi ordonate
O coada este o lista Œn care operatiile de acces sunt restrictionate la inserarea la un capat si stergerea de la celalat capat.

Pricipalele operatii de acces sunt:
PUT(Coada, Atom) Coada
Adauga un element la coada.
GET(Coada) Coada, Atom
Scoate un Atom din coada.
Returneaza atomul scos.
O coada poate fi organizata pe un spatiu de memorare de tip tablou (vector).

Sunt necesari doi indicatori: head indica: primul element care urmeaza sa fie scos. tail indica: locul unde va fi pus urmatorul element adaugat la coada.

Conditia "coada vida" este echivalenta cu: head = tail. Initial indicatorii vor fi initializati astfel Œncƒt sa indice ambii primul element din vector.
Operatia PUT Œnseamna:
- Vataili primeste Atomul adaugat;
- incrementeaza tail.
Operatia GET Œnseamna:
- Œntoarce Vaheadi;
- incrementeaza head
Se observa ca adaugari si stergeri repetate Œn coada deplaseaza continutul cozii la dreapta, fata de Œnceputul vectorului. Pentru a evita acest lucru ar trebui ca operatia GET sa deplaseze la stƒnga continutul cozii cu o pozitie.
Primul element care urmeaza sa fie scos va fi Œntotdeauna Œn prima pozitie, indicatorul head pierzƒndu-si utilitatea. Dezavantajul acestei solutii consta
Œn faptul ca operatia GET necesita o parcurgere a continutului cozii.
Facem notatiile:
C coada
C.vect vectorul Œn care sunt memorate elementele cozii
C.head indicele elementului ce va fi scos din coada la urmatoarea operatie get
C.tail indicele (pozitia) Œn care va fi memorat urmatorul element adaugat la coada.
Conditia coada vida este
C.head=C.tail.
Functia put pune Œn coada C un atom a:

put(C,a)
A if C.tail>DIMMAX then eroare("Coada plina") else |½ C.vect aC.taili=a
|_ C.tail=C.tail+1
S

Functia get scoate un element din coada si-l returneaza:

get(C)
A if C.head=C.tail then eroare("Coada vida") else |½ C.head=C.head+1
| return C.vect aC.head-1i;
S

isEmpty(C)
A return(C.head==C.tail)
S

Cozi ordonate circulare
Pentru a obtine o coada circulara vom porni de la o coada liniara simpla
(cu doi indicatori) si vom face Œn asa fel Œncƒt la incrementarea indicatorilor head si tail, cƒnd acestia ating ultima pozitie din vector sa se continue cu prima pozitie din vector.
Functia urmatoare poate realiza aceasta cerinta:

int nextPoz(int index)
A if (index<DIMVECTOR-1) return index+1; else return 0;
S

unde DIMVECTOR este dimensiunea vectorului Œn care se memoreaza elementele cozii.

Continutul cozii va arata asa:

sau asa:

Conditia "coada vida" ramƒne echivalenta cu: head = tail

Coada va fi plina daca: head=1 si tail=DIMVECTOR

sau daca: tail+1 = head

Ambele situatii sunt continute Œn conditia: nextPoz(tail) = head // conditia "coada plina"
Coada circulara ordonata asigura reutilizarea spatiului eliberat de get la urmatoarele inserari Œn coada.

Observatie:
In coada circulara de dimensiune DIMMAX pot fi memorate DIMMAX elemente.

"Coada plina" se realizeaza Œn 2 situatii: a) C.head=1 si C.tail=DIMMAX b) C.tail+1=C.head
Iar, conditia C.head=inc(C.tail) le contine pe amƒndoua.

In cazul cozilor circulare se modifica doar operatiile put si get: put(C,a)
A if C.head=inc(C.tail) then eroare("Coada plina") else |½ C.vectaC.taili=a
|_ C.tail=inc(C.tail)
S

get(C)
A if C.head=C.tail then eroare("Coada vida") else |½ a=C.vect aC.headi
| C.head= inc (C.head)
|_ return(a)
S

Cozi Œnlantuite
O coada poate fi implementata printr-o lista Œnlantuita la care operatiile de acces sunt restrictionate corespunzator.

Este nevoie de doi indicatori (pointeri): head indica primul element din coada (primul care va fi scos); tail indica ultimul element din coada (ultimul introdus).

O coada vida va avea: head=tail=nil
In mod obisnuit, adaugarea unui element Œn coada modifica numai tail iar stergerea unui element numai head. ×ntr-un mod special trebuie sa fie tratate cazurile: adaugare Œntr-o coada vida:
Initial: head=tail=nil
Final: Coada cu un element:

stergere dintr-o coada cu un element:
Initial: Coada cu un element
Final: head=tail=nil
In aceste cazuri se modifica atƒt head cƒt si tail.
Facem notatiile :
C.head pointer la primul element din coada;
C.tail pointer la ultimul element din coada;
C coada.
Conditia de coada vida este head=0.

Operatiile cozii Œnlantuite

Functia put insereaza un element Œn coada, Œn pozitia fata:

put(C,a)

A p= get_sp(); data(p); link(p)= 0; if C.head=0 then |½ C.head= p
|_ C.tail= p else |½ link(C.tail)= p
|_ C.tail= p
S

Functia get scoate un element din pozitia fata:

get(C,a)
A if C.head= 0 then eroare("Coada plina") else |½ a= data(C.head)
| p= C.head
| C.head= link(C.head)
| ret_sp(p)
|_ return(a)
S

Functia front returneaza elementul din fata cozii, fara a-l scoate din coada.

front(C)
A if C.head=0 then eroare("Coada vida") else return data(C.head)
S

isEmpty(C)
A return(C.head=0)
S

Exista aici un element de redundanta: ar fi convenabil sa nu mai avem spatiu suplimentar de memorare, ci, sa avem un singur pointer ca sa putem manevra coada. De aceea apar utile cozile Œnlantuite circulare.

Cozi Œnlantuite circulare

Daca reprezentam coada printr-o structura Œnlantuita circulara va fi nevoie de un singur pointer prin intermediul caruia se pot face ambele operatii de adaugare si stergere din coada:

Fie:
C pointer la ultimul element din coada link(C) pointer la primul element din coada
Operatiile de plasare si de scoatere din coada, sunt:

put(C,a)
A p= get_sp() data(p)=a if C=0 then |½ C= p
| link(C)= p else |½ link(p)= link(C)
| link(C)= p
|_ C= p
S get(C)
A if C= 0 then eroare("Coada vida") else if C=link(C) then |½ a= data(C)
| ret_sp(C)
| C= 0
|_ return(a) else |½ Ap= link(C)
| link(C)= link(p)
| a= data(p)
| ret_sp(p)
|_ return(a)
S

front(C) returneaza data(link(C)) isEmpty(C) retuneaza conditia C=0.

Complexitatea algoritmilor
La evaluarea (estimarea) algoritmilor se pune Œn evidenta necesarul de timp si de spatiu de memorare al lui.

Studierea complexitatii presupune analiza completa Œn cadrul algoritmului a urmatoarelor 3 puncte de vedere:
1.configuratia de date cea mai defavorabila (cazurile degenerate);
2.configuratia de date cea mai favorabila;
3.comportarea medie.

Punctul 3 presupune probabilitatea de aparitie a diferitelor configuratii de date la intrare.
Punctul 1 este cel mai studiat si este folosit, de obicei, pentru compararea algoritmului. Si Œn ceea ce priveste timpul, se studiaza configuratia cea mai defavorabila a algoritmului.

Complexitatea unui algoritm se noteaza cu: O(f(n)).

Definitie
Fie f : N N si g : N N doua functii.
Spunem ca f O(g) si notam f = O(g) daca si numai daca o constanta c R si un numar n0 N astfel Œncƒt pentru n n0 f(n) cg(n)

Observatie: f : N N este o functie f(n) cu n dimensiunea datelor de intrare. f(n) reprezinta timpul de lucru al algoritmului exprimat Œn "pasi".

Lema 1
Daca f este o functie polinomiala de grad k, de forma: f(n) = ak nk + ak-1nk-1 + ... + a1 n + a0, atunci f = O(nk).

Facƒndu-se majorari Œn membrul drept, obtinem rezultatul de mai sus: f(n) = ak nk + ak-1 nk-1 + ... +a1 n +a0 < nkú (ak + ak-1 + a0) < nk c pentru n > 1 f(n) < c nk, cu n0 = 1.

Concluzie: f = O(nk), si ordinul O exprima viteza de variatie a functiei, functie de argument.

Exemplu: Calcularea maximului unui sir

maxsir(A,n)
A max = Aa1i for i= 2 to n do if Aaii > max then max = Aaii return (max)
S

Exprimam:
T(n) timpul de executie Œn pasi al acestui algoritm;
T(n)= 1 + 2(n-1) = numarul de atribuiri si comparatii
Cazul cel mai defavorabil: situatia Œn care vectorul este ordonat crescator
(pentru ca de fiecare data se face si comparatie si atribuire).
Putem spune ca T(n) = O(n), este o functie polinomiala de gradul I. Conteaza doar Ordinul polinomului, nu coeficientul termenului de grad maxim. Iar la numararea pasilor ne concentram asupra numarului buclelor, nu asupra pasilor din interiorul buclei.

Exemplu: Insertion Sort (algoritmul de sortare prin inserare)
Algoritmul INSERTION SORT considera ca Œn pasul k, elementele Aa1ök-1i sunt sortate, iar elementul k va fi inserat, astfel Œncƒt, dupa aceasta inserare, primele elemente Aa öki sa fie sortate.
Pentru a realiza inserarea elementului k Œn secventa Aa1ök-1i, aceasta presupune: memorarea elementului intr-o varibila temporara; deplasarea tuturor elementelor din vectorul Aa1ök-1i care sunt mai mari decƒt

Aaki, cu o poziie la stƒnga (aceasta presupune o parcurgere de la dreapta la stƒnga); plasarea lui Aaki Œn locul ultimului element deplasat.

Complexitate: O(n)

insertion_sort(A,n)
A for k= 2 to n do
|½temp = Aaki
|i=k-1;
|while (i>=1) and (Aaii > temp) do |½ Aai+1i = Aaii
|_ i=i-1
|_ Aai+1i = temp
S
Cazul cel mai dafavorabil: situatia Œn care deplasarea (la dreapta cu o pozitie Œn vederea Œnserarii) se face pƒna la Œnceputul vectorului, adica sirul este ordonat descrescator.
Exprimarea timpului de lucru:
T(n) = 3ú(n - 1) + (1 + 2 + 3+ ... + n - 1) = 3(n-1) + 3n (n - 1)/2
Rezulta complexitatea: T(n) = O(n2) functie polinomiala de gradul II.

Observatie: Cƒnd avem mai multe bucle imbricate, termenii buclei celei mai interioare dau gradul polinomului egal cu gradul algoritmului.

Bucla cea mai interioara ne da complexitatea algoritmului.

Exemplu: Inmultirea a doua matrici

prod_mat(A,B,C,n)
A for i = 1 to n do for j = 1 to n do
| Cai,ji = 0
|for k = 1 to n do
| Cai,ji = Cai,ji + Aai,ki * Bak,ji
S
Rezulta complexitatea O(n3).

Exemplu: Cautarea binara(Binary Search)

Fie A, de ordin n, un vector ordonat crescator. Se cere sa se determine daca o valoare b se afla printre elementele vectorului. Limita inferioara se numeste low, limita superioara se numeste high, iar mijlocul virtual al vectorului, mid
(de la middle).

Binary_search(A,n,b)
A low = 1; high = n;
while low >= high do
|½ mid = a(low + high)/2i //partea Œntreaga
| if Aamidi=b then return (mid)
| else if Aamidi>b then high=mid-1 //restrƒng
| //cautarea la partea
| //stƒnga
|else low = mid+1 //restrƒng cautarea
//la dreapta return(0)
S

Calculul complexitatii algoritmului consta Œn determinarea numarului de ori pentru care se executa bucla while.
Se observa ca, la fiecare trecere, dimensiunea zonei cautate se Œnjumatateste.
Cazul cel mai defavorabil este ca elementul cautat sa nu se gaseasca Œn vector.
Pentru simplitate se considera n = 2k unde k este numarul de Œnjumatatiri.
Rezulta k = log2 n si facƒnd o majorare, T(n) log2 n + 1 n, a.Œ. 2k n < 2k+1.
Rezulta complexitatea acestui algoritm: este O(log2n). Dar, baza logaritmului se poate ignora, deoarece: logax = logbx logab si logab este o constanta, deci ramƒne O(log n), adica o functie logaritmica.

Proprietati:

1) Fie f, g : N N.
Daca f = O(g) | k f = O(g)
| f = O(k g) , k R constant.

2) Fie f, g, h : N N. si: f = O(g) | g = O(h) | f = O(h)

3) Fie f1, f2, g1, g2 : N N. si: f1 = O(g1) | | f1 + f2 = O(g1 + g2) f2= O(g2) | | f1 f2 = O(g1g2)

Aceasta proprietate permite ca, atunci cƒnd avem doua bucle imbricate (de complexitati diferite), complexitatea totala sa se obtina Œnmultindu-se cele doua complexitati. Cele doua complexitati se aduna, daca buclele sunt succesive.

Teorema:
Oricare ar fi doua constante c > 0, a > 1, si f : N N, o functie monoton strict crescatoare, atunci:
(f(n))c= O(af(n))
Demonstratia se bazeaza pe limita:

Intre clasa functiilor logaritmice, si cea a functiilor polinomiale exista relatia: O(nc) O(an).
Au loc urmatoarele incluziuni:
O(1) O(log n) O(n) O(nlog n) O(n2) O(nklog n) O(nk+1) O(2n)
Pentru calculul complexitatii se va Œncerca Œncadrarea Œn clasa cea mai mica de complexitate din acest sir:
O(1) lasa algoritmilor constanti;
O(log n) clasa algoritmilor logaritmici;
O(n) clasa algoritmilor liniari;
O(nlog n) clasa algoritmilor polilogaritmici;
O(n2) clasa algoritmilor patratici;
O(nklog n) clasa algoritmilor polilogaritmici;
O(nk+1) clasa algoritmilor polinomiali;
O(2n) clasa algoritmilor exponentiali.

Tehnici de calcul a complexitatii
Se folosesc urmatoarele sume:

Sa calculam, de exemplu, suma:
Se noteaza:

Prin aceeasi tehnica se calculeaza suma: