1.

Liste
[Link] listelor ordonate linear
Listele ordonate liniar sunt structuri de date alcătuite dintr-o mulţime A={A1, A2, …, An }de
elemente (de obicei identice), între care există o relaţie determinată de poziţia lor relativă. Astfel,
fiecare element Ak are un predecesor A k-1 şi un succesor A k+1 (mai puţin elementele prim şi ultim).

[Link] se poate realiza reprezentarea în memorie

Reprezentarea în memorie se poate realiza:

 secvenţial;
 prin înlănţuirea elementelor

[Link] sunt dispuse elementele in reprezentarea secventiala si comparatia acesteia cu un

tablou
În acest tip de reprezentare, elementele sunt dispuse succesiv, într-o zonă contiguă de memorie.
Reprezentarea este similară cu cea a unui tablou (nu trebuie făcută identificarea listei cu obiectul tablou
în care sunt memorate elementele ei). (Un tablou este un caz particular de listă, acela în care elementul i
al listei se află memorat în tab [i]).

1.4 Avantajele si dezavantajele reprezentarii secvenţiale

Avantaje:

-accesul la oricare element din listă,

-parcurgerea listei şi

-adăugarea unui element la sfârşitul listei

se fac cu uşurinţă.

Dezavantaje:

 inserarea, ştergerea de elemente din mijlocul listei sunt operaţii costisitoare, deoarece presupun
deplasarea unor elemente.
 dacă numărul componentelor variază în limite largi în timpul execuţiei programului, memoria nu este
utilizată eficient, deoarece spaţiul alocat pentru tablou (static sau dinamic) este fix şi dimensiunea
alocată trebuie să fie acoperitoare.
[Link] listelor in funcţie de locul de acces la liste
În funcţie de locul de acces la liste

 Lista FIFO (First In First Out ) – (coada) inserarea se face la un capăt al listei (la sfârşit), extragerea de
la celălalt capăt (din faţă).
 Lista LIFO (Last In First Out) - (stivă) - operaţiile de inserare / extragere se fac de la acelaşi capăt al
listei, numit vârful stivei.

[Link] se realizează lista FIFO în reprezentare secvenţială si relatia de calcul reprezentativa

Lista FIFO se realizează în reprezentare secvenţială (folosind un tablou) ca un "tampon circular",

Folosind notaţiile:

prim = indexul primului element

ult = indexul ultimului element

ncrt = numărul de elemente din listă

n = numărul de elemente din tablou

ult = (prim + ncrt) modulo n

[Link] se controlează operaţiile de inserare/extragere in cazul listelor FIFO

Operaţiile de inserare/extragere se controlează cu două variabile în două variante:

I. -poziţia (indexul) în tablou de unde se face extragerea (primul element din listă) - prim;
-poziţia unde se va face înscrierea (după poziţia ultimului element din listă) – dupa ult.

II. -poziţia (indexul) în tablou al primului element din listă - prim;

-numărul de elemente din listă la un moment dat – ncrt.

[Link] trebuie verificat înaintea unor operaţii de extragere si de adăugare

Înaintea unei operaţii de extragere trebuie verificat dacă există elemente în listă deci ncrt > 0.

Înaintea unei operaţii de adăugare se verifică dacă există spaţiu în tablou, deci dacă ncrt < N.
Exemplul 1:
# define N 100 /* lista FIFO de N numere întregi */
Typedef struct
{
tab [N]; /* tabloul de N elemente */ „Iniţial lista este vidă şi se înscrie numărul de elemente: ncrt = 0.
int prim; /* indexul primului element din listă */ Indexul primului element=0
int ncrt; /* numărul curent de elemente din listă */
} fifo;
 [Link] înlănţuite

[Link] listelor inlantuite

Definiţie: O listă înlănţuită este alcătuită din noduri cu structura date şi legături în care:

 câmpul DATE reprezintă informaţia propriu zisă (un element al listei);

 câmpul LEGĂTURĂ reprezintă informaţia de secvenţă, legătura spre elementele adiacente din listă.

[Link] si dezavantajele listelor inlantuite

Avantaje:

 inserarea şi ştergerea unui element se reduc la modificări ale legăturilor elementelor vecine;
 spaţiul de memorare poate fi alocat individual, pentru fiecare element al listei;
 reordonarea unei liste nu mai necesită transferuri memorie-memorie pentru interschimbarea
elementelor.
Dezavantaje:

 ocuparea unui spaţiu mai mare de memorie, pentru informaţia de secvenţă;

 căutarea unui element al listei se face tot secvenţial

[Link] este o lista simplu inlantuita.

Listă simplu înlănţuită - conţine noduri în care este specificată legătura (adresa) spre elementul următor.
Exemplul 2:
struct nlsi
{
double data; /* informaţia din nodul listei */
struct nlsi *urm;} /* adresa nodului următor */
};

[Link]: lant si lista circulara

Definiţie: O listă înlănţuită în care legătura ultimului element are valoarea NULL, care marchează sfârşitul listei, se
numeşte lanţ.
Definiţie: Dacă legătura elementului final specifică primul element se obţine o listă circulară.

[Link] neajuns remediaza listele dublu inlantuite

Există operaţii precum înserarea înaintea elementului curent sau ştergerea elementului curent,
care presupun referirea elementului dinaintea elementului curent, operaţie care se realizează cu
dificultate. Pentru a remedia acest neajuns se utilizează liste dublu înlănţuite.
[Link] este o lista dublu inlantuita
Listă dublu înlănţuită - conţine noduri în care se specifică legături către nodul precedent şi
către nodul următor, oferind o mai mare flexibilitate.
Prin legarea între ele a primului şi ultimului element rezultă o listă circulară, la care nu se mai
folosesc elemente false (santinele).

[Link] cu liste
[Link] se clasifica operatiile cu liste dpdv al gradului de complexitate
După gradul de complexitate, operaţiile cu liste se pot clasifica în:

-Operaţii primitive:
-Operaţii de caracterizare:
-Operaţii complexe:

[Link] operatii primitive

 adăugarea unor elemente noi la sfârşitul listei;
 înserarea unor elemente noi în orice loc din listă;
 ştergerea unor elemente din orice poziţie a listei;
 modificarea unui element dintr-o poziţie dată;
 iniţializarea unui liste ca o listă vidă.

[Link] operatii complexe

 separarea unei liste în două sau mai multe liste;
 combinarea a două sau mai multe liste în una singură;
 concatenarea (alipirea);
 interclasarea (rearanjarea conform cu un criteriu).
 ordonarea unei liste după valorile (crescătoare sau descrescătoare) ale unei chei;
 selecţia elementelor dintr-o listă care satisfac la unul sau mai multe criterii, dintr-o nouă
listă.

[Link] operatii de caracterizare

 determinarea lungimii listei (numărul de elemente);
 localizarea elementului din listă care îndeplineşte o anumită condiţie;
 [Link]
[Link] arbori si necesitatea organizarii pe baza ierarhiei de componente

Organizarea liniară de tip listă nu este întotdeauna cea mai adecvată pentru unele aplicaţii. Astfel,
dacă trebuie să descriem structura unui produs, de cele mai multe ori nu prezentăm o listă a tuturor
componentelor, ci utilizăm o descriere ierarhică. De exemplu, din punct de vedere constructiv, un
calculator este compus din unitate centrală, terminal, claviatură, alte periferice. Unitatea centrală are o
carcasă în care se află conectori şi plăci, pe fiecare placă fiind montate diverse componente - circuite
integrate, condensatori, etc.

De altfel, în vederea studierii unor proprietăţi, aproape orice obiect poate fi descompus în alte
obiecte, mai simple. Procesul de descompunere poate fi continuat pe mai multe niveluri, terminându-se
însă după un număr finit de etape, dependent de natura aplicaţiei. Fiecare obiect în parte este definit
printr-un set de atribute şi prin mulţimea obiectelor componente, care la rândul lor, sunt descrise în acelaşi
mod . Se observă că această definiţie este recursivă (un obiect este compus din mai multe obiecte) şi pune
în evidenţă o ierarhie a obiectelor.

Organizarea ierarhică este întâlnită în cele mai diverse domenii, de la organizarea administrativă a
unei ţări, la planificarea meciurilor în cadrul unui turneu sportiv, de la structurarea unei cărţi, până la
stabilirea ordinii de execuţie a operaţiilor efectuate pentru determinarea valorii unei expresii aritmetice.

Tot o structură ierarhică este şi cea a cataloagelor în care sunt grupate fişierele de pe discurile fixe
sau flexibile. Această organizare este impusă, in principal, de raţiuni de gestionare cât mai comodă a
fişierelor de diverse tipuri, aparţinând diverşilor utilizatori ai aceluiaşi sistem de calcul.

Generalizând, într-o viziune sistemică, orice entitate din natura sau societate poate fi reprezentată
ca un tot sau ca o ierarhie de componente.

O definiţie mai riguroasă a structurii de arbore este următoarea: un arbore A este fie vid, fie
format dintr-un nod rădăcină (R) , căruia îi este ataşat un număr finit de arbori. Aceştia sunt
denumiţi subarbori ai lui A, datorită relaţiei de “subordonare” faţă de rădăcină.

În concluzie, orice nod dintr-un arbore este rădăcina unui subarbore, iar orice arbore poate fi sau
poate deveni subarbore. Relaţia dintre doi subarbori nu poate fi decât de incluziune (unul este subarbore al
celuilalt) sau excluziune (cei doi subarbori nu au noduri comune, dar aparţin aceluiaşi arbore).

În literatura de specialitate se folosesc o serie de termeni consacraţi, pe care îi voi prezenta în

continuare. Mulţi dintre aceştia au fost preluaţi din terminologia utilizată în cazul arborilor genealogici.
Astfel, pentru a exprima relaţiile directe între nodurile unui arbore, se utilizează termenii tată, fiu şi frate
(parent, child, sibling în limba engleză), iar pentru a exprima relaţiile indirecte (de tipul “fiul fiului …
fiului“ şi “tatăl tatălui … tatălui“) se utilizează termenii descendent şi strămoş.
 [Link] de noduri; inaltimea unui arbore

Nodurile fără descendenţi sunt denumite noduri terminale sau, prin analogie cu arborii din natură,
frunze .

Accesul de la rădăcina unui (sub)arbore nevid la oricare alt nod presupune parcurgerea unei căi formate
din a arce (a  0) pe care se găsesc n noduri (n = a +1). Valoarea n reprezintă nivelul pe care se găseşte
nodul faţă de rădăcină, al cărei nivel este, prin convenţie, 1.

Înălţimea unui arbore se poate defini ca maximul dintre nivelurile nodurilor terminale, deci înălţimea unui arbore
nevid este cel puţin 1 (în cazul în care arborele are un singur nod).
O altă definiţie, recursivă, este următoarea: înălţimea unui arbore este egală cu 1 + maximul dintre
înălţimile subarborilor săi. Numărul de descendenţi direcţi ai unui nod reprezintă ordinul nodului.

[Link] arbore binar si arbore multicai; numarul de noduri dintr-un arbore si

in particular arbore binar.

Observaţie: o listă este de fapt un arbore degenerat, în care toate nodurile, cu excepţia ultimului,
sunt de ordinul 1 (au câte un singur descendent direct).

Dacă toate nodurile dintr-un arbore au cel mult doi descendenţi direcţi (fii), atunci arborele este
denumit arbore binar, iar cei doi potenţiali subarbori ai unui arbore nevid sunt denumiţi subarbore stâng
şi subarbore drept. În cazul in care ordinul nodurilor nu este limitat, arborele este denumit arbore
multicăi. Totuşi, orice arbore multicăi poate fi privit ca arbore binar, dacă orice nod este considerat în
relaţie directă cu maximum alte două noduri - primul fiu şi următorul frate. Din acest motiv, în cele ce
urmează se va considera, dacă nu se precizează explicit altfel, cazul arborilor binari.

Numărul de noduri dintr-un arbore se situează între limitele determinate de ordinul şi înălţimea acestuia.
Astfel, în cazul unui arbore binar de înălţime H, numărul de noduri N este cuprins între H si 2 H-1. Rezultă
că înălţimea unui arbore binar cu N noduri poate varia între log2N şi N.

[Link] sunt modurile in care se poate parcurge un arbore

De exemplu, dacă memorăm într-o structură de arbore multicăi informaţiile despre organizarea unei
societăţi comerciale, acest arbore poate fi parcurs în mai multe moduri, în funcţie de prelucrarea dorită.
În cazul în care este solicitată lista personalului cu funcţii de conducere, aceasta poate fi tipărită in două
variante:

1. grupind persoanele pe nivelurile ierarhice;

2. astfel încât să reflecte relaţiile de subordonare.

În prima variantă, parcurgerea arborelui se efectuează în lăţime (lărgime), iar în cea de-a doua în
adâncime.
[Link] sunt modurile particulare de parcurgere in adancime a unui arbore; detaliati
referindu-va la nodurile specifice

Tot o parcurgere implică şi calculul numărului de persoane angajate în fiecare

compartiment (reprezentat printr-un subarbore). Cele două parcurgeri în adâncime menţionate se
deosebesc prin ordinea relativă de prelucrare a nodului rădăcină şi, respectiv, a subarborilor. În
primul caz, informaţia specifică nodului rădăcină este prelucrată (tipărită) înaintea informaţiilor
din celelalte noduri ale (sub)arborelui. Acest tip de parcurgere este denumit parcurgere în
preordine. Deoarece numărul de persoane angajate într-un compartiment poate fi calculat (şi
eventual tipărit) numai atunci când se cunoaşte numărul de angajaţi din toate compartimentele
subordonate, rezultă că prelucrarea de la nivelul nodului rădăcina se face după prelucrarea
restului arborelui respectiv, deci parcurgerea se realizează în postordine.

[Link] cazul parcurgerii în lăţime a arborilor

În cazul parcurgerii în lăţime, se tipăreşte mai întâi informaţia din nodul rădăcină, după care sunt
prelucrate, de la stânga spre dreapta, nodurile aflate pe primul nivel, apoi cele aflate pe al doilea
nivel, etc. Pentru a realiza parcurgerea, se poate folosi o coadă, iniţializată cu nodul rădăcină.
Apoi, cât timp există noduri în coadă, se repeta următoarele operaţii:

1. este extras primul nod din coadă;

2. nodul extras este prelucrat;

3. fiii săi sunt adăugaţi în coadă, în vederea parcurgerii ulterioare.

[Link] cazul parcurgerii în adancime a arborilor

În cazul parcurgerii in adâncime, fiii unui nod sunt vizitaţi tot de la stânga spre dreapta, dar
trecerea de la fiul curent la fratele din dreapta se realizează numai după tratarea tuturor
descendenţilor fiului curent (deci a întregului subarbore dominat de acesta).
 [Link]
a. Definitii graf, arc, cale
Printr-un graf se înţelege o mulţime de noduri (numite şi vârfuri) şi o aplicaţie definită pe această
mulţime cu valori în aceeaşi mulţime, care face legătura între aceste noduri, legături numite arce, care pot
fi sau nu orientate.

O cale este o succesiune de noduri aleasă astfel încât să existe arce care să reunescă nodurile respective.
O cale este simplă dacă toate nodurile, cu excepţia primului şi ultimului, sunt distincte între ele.

b. Definitii graf aciclic, digraf, graf neorientat

Un graf aciclic este un graf care nu conţine nici o cale de la un nod la el însuşi.

Un graf orientat sau digraf (prescurtare de la directed graf) G=(V,E) constă deci într-o mulţime V de
vârfuri (sau noduri) şi o mulţime E de arce. Un arc poate fi privit ca o pereche ordonată de vârfuri (v,w)
unde v este baza arcului iar w este vârful arcului. Se spune că w este adiacent lui v.

Un graf neorientat sau graf G=(N,R) este alcătuit dintr-o mulţime de noduri N şi o mulţime R de muchii.
O muchie este atunci o pereche ordonată de noduri (v,w)=(w,v).

c. Definitii graf conex, componenta conexa, graf biconex

Un graf este conex dacă oricare două noduri ale sale sunt conectate. Această proprietate este foarte
importantă, astfel într-o reţea de calculatoare este necesar ca oricare dintre ele să poată comunica cu toate
celelalte schimbând date direct sau prin intermediul altor noduri.

O componentă conexă a unui graf G este un subgraf conex indus maximal. Un graf conex aciclic este un
arbore numit arbore liber. El poate fi convertit într-un arbore orientat alegând un nod oarecare drept
rădăcină şi înlocuind fiecare muchie cu un arc orientat dinspre rădăcină.

Un graf conex G=(N,R) este biconex dacă prin omiterea oricărui nod v din N se obţine un graf G'=G-v
conex. O componentă biconexă a unui graf este un subgraf maximal conex. Un nod v din N este punct de
articulare al lui G dacă G-v nu este conex.
 d. Moduri de reprezentare mai des utilizate pentru grafuri si cum trebuie sa fie
făcută alegerea unuia dintre ele

Pentru grafuri există două moduri de reprezentare mai des utilizate: matricea de adiacenţe şi listele de
adiacenţe. Alegerea uneia dintre ele trebuie fi făcută în funcţie de frecvenţa operaţiilor de acces la
nodurile şi muchiile grafurilor.

e. Avantajele si dezavantajele reprezentarii prin matrice de adiacenţe

Reprezentarea prin matrice de adiacenţe permite un acces rapid la arcele (muchiile) grafului fiind
utilă în algoritmii în care se testează prezenţa sau absenţa unui arc oarecare. Ea este
dezavantajoasă dacă numărul de arce este mai mic decât n × n, caz în care memoria necesară
pentru a păstra matricea este folosită inefficient

f. Avantajele si dezavantajele reprezentarii prin liste de adiacenţe

Reprezentarea prin liste de adiacenţe foloseşte mai bine memoria, dar determină o căutare mai
anevoioasă a arcelor. În această reprezentare, pentru fiecare nod se păstrează lista arcelor către
nodurile adiacente. Întregul arbore poate fi reprezentat ca un tablou Cap, indexat după noduri,
fiecare element Cap[I] fiind un pointer spre lista nodurilor adiacente lui i. Memoria necesară
reprezentării este proporţională cu suma dintre numărul de noduri şi numărul de arce ale grafului.
În schimb, căutarea unui arc este proporţională cu numărul de noduri ale grafului.

g. Criteriul si modalităţile de explorare a grafurilor; explicati pe scurt fiecare

dintre aceste modalitati

Ideea de bază a parcurgerii unui graf este simplă: se utilizează două mulţimi de noduri: vizitate şi
neexplorate cu următoarea semnificaţie:

 Vizitate este mulţimea nodurilor vizitate;

 Neexplorate este o submulţime a lui Vizitate, cu noduri ai căror vecini au fost doar parţial
exploraţi.
După ordinea de explorare a arcelor se cunosc două modalităţi de explorare: în lărgime şi în
adâncime
a. Explorarea în lărgime

La explorarea în lărgime, după vizitarea nodului iniţial, se explorează toate nodurile adiacente
lui, se trece apoi la primul nod adiacent şi se explorează toate nodurile adiacente acestuia.

b Explorarea în adâncime

La explorarea în adâncime se marchează vizitarea nodului iniţial după care se parcurge în

adâncime, recursiv, fiecare nod adiacent cu el. După vizitarea tuturor vârfurilor ce pot fi atinse
din nodul de start parcurgerea se consideră încheiată. Dacă rămân noduri nevizitate se alege un
nou nod de start şi se repetă procedeul.

[Link]
[Link] se mai numeste metoda Backtracking; justificati utilizarea acestei metode - in
general ineficiente - in contextul modularizarii
Modularizarea este o metodă cunoscută de descompunere într-un set de subprobleme. Metoda
Backtracking (a căutării cu revenire), în general ineficientă, având complexitate exponenţială,
poate fi utilizată la optimizarea procesului de căutare, evitând căile care nu duc la o soluţie.

[Link] de cautare
h. Ce este o regula euristica; justificati utilizarea acestei metode in cazul
algoritmilor de cautare
Cei mai mulţi algoritmi de acest tip au caracter euristic. O regulă euristică oferă o metodă de
rezolvare a problemelor, sau o metodă de căutare. Ea nu dă rezultate corecte la orice moment de timp şi
nu este garantată că găseşte cea mai bună soluţie, dar în acelaşi timp poate reduce timpul de căutare.
Metodele de acest tip pot fi folosite pentru reducerea mărimii arborilor de căutare în cazurile arborilor
foarte mari
 i. Câteva dintre avantajele strategiei de căutare înapoi
Strategia de control înapoi
Prin aplicarea regulilor de descompunere problema se transformă în subprobleme de
complexitate mai mică.
Aceasta poartă şi denumirea de control dirijat prin obiectivul problemei sau control de sus în
jos. Datorită caracteristicilor sale, această metodă se mai numeşte şi reductive
Se pot menţiona câteva dintre avantajele strategiei de căutare înapoi, şi anume:
 atunci când sunt necesare sau când toate posibilităţile au fost explorate, sistemul recurge la
întrebări adresate utilizatorului;
 arborele de căutare este adesea mai puţin adânc decât cel aferent strategiei de căutare înainte;
procesul de raţionare este interactiv

[Link] pentru minimizare cai

[Link] problemei căii de cost minim de la sursă la destinatar prin algoritmul
Dijkstra; tehnica folosita, in ce consta si ce structuri de date utilizeaza
Dijkstra

Rezolvarea acestei probleme se bazează pe o tehnică “greedy” datorată lui E.W. Dijkstra. Ea
constă în păstrarea unei mulţimi Selectate de vârfuri ale căror distanţe minime faţă de sursă sunt
cunoscute. Iniţial, Selectate conţine doar vârful sursă; la fiecare pas, se adaugă la Selectate un
vârf a cărui distanţă faţă de un vârf din Selectate este minimă. În rezolvare se utilizează:

 un tablou Distanţă al distanţelor minime de la sursă la fiecare vârf.

 o matrice Cost de costuri, în care Cost  i, j  este costul asociat arcului (i,j); dacă nu există un
arc (i,j), atunci se consideră pentru Cost  i, j  o valoare infinit (practic, foarte mare).

Algoritmul lui Dijkstra lucrează de fapt în felul următor. La fiecare pas al algoritmului, tabloul
Distanţe (notat mai departe cu D) conţine lungimea celui mai scurt drum special către fiecare vârf al
grafului. După ce adaugăm un vârf v la S, cel mai scurt drum special către v va fi de asemenea cel
mai scurt dintre toate drumurile către v. Când algoritmul se termină, toate vârfurile din graf sunt în
S, deci toate drumurile de la sursă către celelalte vârfuri sunt speciale şi valorile din D reprezintă
soluţia problemei.
 8.2Cum se mai numeste metoda Kruskal si pe ce se bazeaza algoritmul
Kruskal
O metodă de asemeni des utilizată în calcule este aceea a arborelui minim de acoperire
(Kruskal). Algoritmul construieşte treptat mulţimea T a muchilor arborelui minimal adăugând la
fiecare pas muchia care nu formează cicluri cu muchiile aflate deja în T.

8.3Asemanarea esentiala si deosebirea esentiala intre algoritmii Prim si

Kruskal
Un alt algoritm greedy pentru determinarea arborelui parţial de cost minim ale unui graf se
datorează lui Prim (1957). Deosebirea constă în faptul că, la fiecare pas, mulţimea A de muchii
alese împreună cu mulţimea U a vârfurilor pe care le conectează formează un subarbore de cost
minim pentru subgraful (U,A) al lui G (şi nu o pădure ca în algoritmul lui Kruskal).

8.4Graf si componente biconexe – ce sunt; scurta explicatie

Rezolvarea unui graf (neorientat) se poate face printr-o metodă bazată pe parcurgerea în adâncime a
grafului.

Dacă (v,w) aparţine lui R, atunci subgraful având nodurile v şi w şi muchia (v,w) este biconex.
Fiecare muchie a grafului aparţine unei singure componente biconexe. Altfel spus, componentele
biconexe ale unui graf induc o partiţie pe muchiile sale. Totodată, dacă există un ciclu simplu prin
nodurile u şi v atunci u şi v aparţin aceleiaşi componente biconexe.
 [Link] pentru simulare 3D

[Link] de tratare a problemei reprezentarii corpurilor 3D; detaliati

grupele mari de algoritmi; care dintre grupe este mai eficient dpdv al
timpului de executie?
Există două modalităţi de abordare a problemei:

 Algoritmi "spaţiu-obiect"
 Algoritmi "spaţiu-imagine
Primii iau în considerare faptul că la receptorul vizual ajung numai razele de lumină
reflectate de porţiunile de faţetă nemascate (între acestea şi observator nu se interpune nici o
altă faţetă). Deci se compară fiecare faţetă dintre cele NF existente cu toate celelalte faţete ale
corpului, în scopul de a elimina acele porţiuni care nu sunt vizibile (sunt mascate).
Subrutinele de comparare sunt parcurse de NF × NF ori.

Algoritmii "spaţiu-imagine" presupun analiza pixel cu pixel a zonei de lucru din ecran pentru
a determina care anume dintre faţete este vizibilă într-un anumit punct. Dacă ecranul are NP
pixeli, atunci subrutinel de comparare vor fi parcurse de NF × NP ori.

Se observă că NF2 << NF × NP. Am fi tentaţi să credem că efortul de calcul va fi mai important
în abordarea "spaţiu-imagine". În realitate, chiar pentru valori relativ mici ale NF, algoritmii
"spaţiu imagine" sunt mai rapizi, deoarece subrutinele de comparare individuală sunt mult mai
simple şi deci consumă mai puţin timp.

[Link] matematic al tratarii imaginilor prin algoritmii "spaţiu-obiect"

Transpunerea matematică se bazează pe propoziţia: "Un punct este interior unui triunghi atunci
când, faţă fiecare latură, el se află de aceeaşi parte a acesteia caşi vârful opus laturii respective.
[Link] si dezavantaje ale Buffer-ului de adâncime
Sunt uşor de implementat, dar prezintă dezavantajul de a necesita memorie suplimentară pentru
păstrarea valorilor cotei Z ale unor mulţimi de puncte bine detreminate. Cel mai eficient algoritm
din această familie (ca viteză de lucru) este algoritmul "ecran z-buffer.

[Link] algoritmilor Linie de baleiaj (scan-line), cand se recomanda,

dezavantaje
Algoritmii de acest tip reconstituie imaginea linie cu linie, tratând ansamblul faţetelor poligonale
care descriu corpul. Sunt recomandabile atunci când nu se dispune de memorie foarte mare,
pentru număr mare de faţete, fiind însă mai lenţi şi performanţele lor fiind dependente de
complexitatea corpului de reprezentat.
Consumul de memorie este dictat de necesitatea creării unor tabele în care se ţine evidenţa
muchiilor şi faţetelor parcurse de linia de baleiaj la un moment dat, în procesul de construire linie
cu linie a imaginii.

[Link] de reprezentare a suprafetelor in spatiu; scurta descriere a formei

de reprezentare
Pentru reprezentarea în 3D se poate utiliza o metodă de reprezentare a suprafeţelor în spaţiu
folosind două familii de curbe cubice corespunzătoare celor două direcţii într-un plan xOy. Prin
urmare, ecuaţia suprafeţei trebuie să se exprime în funcţie de doi parametri s şi t, adică

x =x (t,s) , y = y (t,s) , z = z (t,s) , s, t  0,1

Aceste relaţii sunt ecuaţiile unei suprafeţe bicubice.

Pentru reprezentarea imaginii suprafeţei pe ecran s-a utilizat forma de reprezentare Hermite:
suprafaţa să treacă prin patru puncte din spaţiu, corespunzătoare valorilor extreme 0 şi 1 pentru
parametrii s şi t (notate cu P00, P01, P10, P11, ) şi să aibă trei tangente la suprafaţă, date în fiecare
dintre aceste puncte.