UNITATEA 1: FUNDAMENTELE ALGORITMULUI

Structură

1.0 Obiective
1.1 Introducere în algoritmi
1.2 Proprietă ț ile algoritmului
1.3 Nota ț ii Algoritmice
1.4 Design and development of an algorithm
1.5 Câteva exemple simple
1.6 Summary
1.7 Keywords
1.8 Răspunsuri pentru a- ț i verifica progresul
1.9 Exerci ț ii finale ș i răspunsuri
1. 10 lecturi sugerate

1.0 OBIECTIVE

La sfârș itul acestei unităț i vei fi capabil să

•Fundamentele algoritmilor împreună cu nota ț ia.

Proprietă ț ile variate ale unui algoritm.
•Cum să scrii un algoritm sau cod pseudocod pentru orice problemă.
Algoritmi pentru varietă ț i de probleme.

1.1 Introducere în algoritmi:

Un algoritm, numit după matematicianul persan al-Khowarizmi din secolul al nouălea, este
pur ș i simplu un set de reguli folosite pentru a efectua unele calcule, fie manual, fie mai adesea
pe o maș ină Chiar ș i greaca antică a folosit un algoritm care este cunoscut în mod popular ca
Algoritmul lui Euclid pentru calcularea celui mai mare divizor comun (cmmdc) al două numere.

Un algoritm este un instrument pentru rezolvarea unei probleme date. Înainte de a scrie un program pentru a rezolva
problema dată, un programator bun mai întâi proiectează ș i scrie algoritmul corespunzător,
analizează, rafinează de câte ori este necesar ș i ajunge la forma finală „eficientă“
care funcț ionează bine pentru toate datele de intrare valide ș i rezolvă problema în cel mai scurt timp posibil
timp, utilizând un spaț iu minim de memorie.

Defini ț ia algoritmului: Algoritmul este definit ca o colec ț ie de instruc ț iuni neambigue.

instrucț iuni care apar într-o anumită secvenț ă ș i un astfel de algoritm ar trebui să producă
iesire pentru un set dat de input într-un timp finit.

1
Cerinț a de bază este ca formularea problemei să fie foarte clară
pentru că anumite concepte pot fi clare pentru cineva ș i este posibil să nu fie clare pentru altcineva.
De exemplu, calcularea rădăcinilor unei ecuaț ii cuadratice poate fi clară pentru oamenii care
ș tie despre matematică, dar poate fi neclar pentru cineva care nu este.

Un algoritm bun este ca un cuț it ascuț it - face exact ceea ce este destinat să facă cu o
cantitatea minimă de efort aplicat. Folosirea unui algoritm greș it pentru a rezolva o problemă este ca
încerci să tai un steak cu o ș urubelniț ă. Obț ii un rezultat, dar ai fi cheltuit
mai mult efort decât este necesar.

Orice algoritm ar trebui să consta în următoarele:

Gama de intrări pentru care un algoritm func ț ionează perfect.

Algoritmul ar trebui să producă întotdeauna rezultate corecte ș i ar trebui să se oprească.
3. O succesiune finită de instruc ț iuni care transformă datele de intrare date în rezultatul dorit.
output (Algorithm + Programming lanuage)

De obicei, algoritmul va fi scris în propoziț ii simple în limba engleză împreună cu simple

expresiile matematice. Definiț ia algoritmului poate fi ilustrată folosind
figura 1.1

Introducere
↓
Problemă -- Algoritm -- Calculator Ieș ire

( Fig 1.1 No ț iunea de Algoritm )

Orice metodă sistematică de calculare a rezultatului a poate fi considerată un algoritm.

De exemplu, metodele pe care le învăț ăm la ș coală pentru adunare, înmulț ire, împărț ire
numerele pot fi considerate ca algoritmi. Prin analiza paș ilor specificaț i, putem
realizează rezultatul fără să gândeș ti chiar ș i o reț etă de gătit poate fi considerată
ca un algoritm dacă paș ii:
1. Descrie cu precizie cum să prepari un anumit fel de mâncare.
2. Descrie calitatea exactă care trebuie utilizată.
3. Instruc ț iuni detaliate despre ce articole trebuie adăugate următorul la ce moment? Cât timp să
găteș te?

1.2 Proprietă ț ile algoritmilor:

Fiecare algoritm trebuie să îndeplinească anumite proprietăț i. Proprietăț ile variate sau
caracteristicile unui algoritm sunt:
1. Precise ș i neambiguu (Definitate): Un algoritm trebuie să fie simplu, precis
ș i neechivoc, adică nu ar trebui să existe nicio ambiguitate în instrucț iuni
sau afirmaț ii specificate pentru a rezolva o problemă. Fiecare instrucț iune utilizată în
algoritmul trebuie să fie clar ș i neambiguu.

2
 2. Gama de intrări: Gama de intrări pentru care algoritmul produce rezultatul dorit
rezultatul ar trebui să fie specificat.
3. Men ț ineț i ordinea: Instruc ț iunile din fiecare pas al algoritmului sunt I
ordinea specificată adică vor fi executate în succesiune (adică una după alta).
instrucț iunile nu pot fi scrise într-o ordine aleatorie.
4. Finite ș i corect: Ei trebuie să rezolve problema într-un număr finit de pa ș i.
ș i produce rezultatul corespunzător. Domeniul de intrare pentru care algoritmul
funcț ionează perfect ar trebui specificat.
5. Încheiere: algoritmul ecac ar trebui să se încheie.
6. Mai există mai multe algoritmi pentru a rezolva o problemă dată ș i viteza de execu ț ie a
each algorithm may be different. (for example, to sort various algorithms bubble
sortare, sortarea prin inserare poate fi utilizată).
7. Un algoritm poate fi reprezentat în mai multe moduri diferite.
8. Algoritmul pentru o problemă dată poate fi bazat pe idei foarte diferite (de exemplu,
to sort several methods exist such as bubble sort, insertion sort, radix sort etc.)
ș i pot avea viteze de execuț ie diferite.

1.3 Nota ț ii Algoritmice

Următoarele note sunt de obicei folosite în timpul scrierii oricărui algoritm.

1. Write the word algorithm and write what is the main objective of the algorithm.
De exemplu,
Algoritm Aria_cercului
2. Apoi o descriere scurtă a ceea ce se realizează folosind algoritmul împreună cu
intrările în algoritm trebuie să fie furnizate. De exemplu,
Description : “The algorithm computes the area of circle using the input value
raza
3. Fiecare instruc ț iune ar trebui să fie în pa ș i separa ț i, iar numărul pasului trebuie să fie
furnizate. Ce se realizează în fiecare pas trebuie să fie descris pe scurt ș i are
a fi încadrat în parantezele pătrate (pe care le numim comentariu). Pentru
de exemplu, pentru a găsi aria cercului, putem scrie:
Pasul 2: [ Găseș te aria cercului ]
Zona 3.142*raza*raza.
4. După ce toate opera ț iile au fost finalizate, algoritmul trebuie să fie terminat, ceea ce indică
sfârș itul logic al algoritmului. De exemplu, ultima etapă în algoritm va
a fi
Pasul4: [Finalizat]
ieș ire.

1.4 Proiectarea ș i dezvoltarea unui algoritm

Pa ș ii fundamentali în rezolvarea oricărei probleme date care duc la completarea

dezvoltarea unui algoritm, este următoarea:

3
 1. Declara ț ia problemei.
2. Dezvoltarea unui model matematic
3. Proiectarea algoritmului
4. Implementare
5. Analiza algoritmului pentru complexitatea sa în timp ș i spa ț iu
6. Testarea ș i depanarea programului
7. Documenta ț ie.

1. Declara ț ia problemei.
Înainte de a încerca să rezolvăm o problemă dată, trebuie să în ț elegem precis
declaraț ia algoritmului. Există din nou mai multe modalităț i de a face acest lucru. Putem lista toate
cerin ț e de specifica ț ie a software-ului ș i încearcă să pui mai multe întrebări ș i să ob ț ii
răspunsuri. Acest lucru ne-ar ajuta să înț elegem mai clar problema ș i să eliminăm orice
ambiguitate.

2. Dezvoltarea unui model matematic

Având înț eles problema, următorul pas este să căutăm un model matematic,
care este cel mai potrivit pentru problema dată. Aceasta este o etapă foarte importantă în ansamblu
procesul de soluț ionare ș i ar trebui acordată o considerabilă atenț ie. De fapt, alegerea
modelul mai are un drum lung de parcurs în procesul de dezvoltare.
Trebuie să ne gândim la
Care model matematic este cel mai potrivit pentru orice problemă dată?
- Există vreun model care a fost deja selectat pentru a rezolva o problemă care
asemănătoare cu cea actuală?

3. Proiectarea algoritmului

Deoarece suntem confortabili cu specificaț ia ș i modelul problemei în această etapă,

putem să trecem la scrierea unui algoritm.

4. Implementare

În acest pas, trebuie să fie selectate ș i codificate structuri de date adecvate într-o limbaj ț intă.
Selectarea unei limbi ț intă este un sub-pas foarte important pentru a reduce complexităț ile implicate.
în programare.

5. Analiza algoritmului pentru complexitatea sa de timp ș i spa ț iu

În această secț iune, vom folosi o serie de termeni precum complexitate, analiză, eficienț ă.
etc. Toate aceste termeni se referă la performanț a unui program. Sarcina noastră nu poate să se oprească odată ce
scriem algoritmul ș i îl codificăm în, să zicem, C sau C++ sau Java. Ar trebui să ne facem griji cu privire la
cerinț e de spaț iu ș i de timp, de asemenea. De ce? Există mai multe motive pentru aceasta ș i astfel noi
vom începe cu complexitatea temporală.
În termeni simpli, complexitatea temporală a unui program este cantitatea de timp de calculator de care are nevoie pentru a
rulează un program.

4
Complexitatea spaț ială a unui program este cantitatea de memorie necesară pentru a rula un program.

6. Testarea ș i depanarea programului

După implementarea algoritmului într-o limbă specifică, următorul pas este timpul de execuț ie. După
executarea programului ar trebui să genereze rezultatul dorit. Testarea nu are legătură cu ...
verificarea programului pentru corectitudinea sa adică dacă ieș irea programului este
corect sau nu. Folosind valori de intrare diferite, se poate verifica dacă ieș irea dorită este
ob ț inut sau nu. Orice eroare logică poate fi identificată prin testarea programului. De obicei
dezghe ț area este parte a testării. Există multe instrumente de depanare prin care cineva poate testa
program pentru corectitudinea sa.

7. Documentaț ie

Re ț ineț i că documenta ț ia nu este ultimul pas. Documenta ț ia ar trebui să existe pentru

în ț elegerea problemei până când este testată ș i debuggată. În timpul proiectării ș i
în faza de implementare, documentaț ia este foarte utilă. Pentru a înț elege designul sau
cod, comentarii corespunzătoare ar trebui să fie oferite. Pe cât posibil, programul ar trebui să fie auto-
documentat. Aș adar, utilizarea unui nume de variabilă corespunzător ș i a structurilor de date joacă un rol foarte important
rolul în timpul documentării. Este foarte dificil să citeș ti ș i să înț elegi logica celorlalț i ș i
documentaț ia permite indivizilor să înț eleagă programele scrise de
ceilalț i oameni.

1.5 Câteva exemple simple

[Link] pentru a găsi MCD-ul a două numere. (Algoritmul lui Euclid).

ALGORITM : gcd(m,n)
//Scop: Găsirea celui mai mare divizor comun al două numere
Acest algoritm calculează PGCD-ul a două numere nenegative ș i diferite de zero
valori acceptate ca parametri.
Două valori non-negative ș i diferite de zero m ș i n
GCD al m ș i n

Pasul 1: dacă n=0 returnează m ș i opreș te-te

Pasul 2: Împărț iț i m la n ș i atribuiț i restul lui r.

Pasul 3: Atribuie valoarea lui n lui m ș i valoarea lui r lui n

Pasul 4: Mergi la pasul 1.

2. Algoritm pentru a găsi GCD-ul a două numere. (Metoda verificării numerelor întregi consecutive).

5
 ALGORITM : cmmdc(m,n)
//Scop: A găsi HCM-ul a două numere
Acest algoritm calculează GCD-ul a două numere non-negative ș i non-zero.
valori acceptate ca parametrii.
Două valori non-negative ș i non-zero m ș i n
CMMDCA dintre m ș i n

Pasul 1: [găseș te minimul dintre m ș i n]

r min(m,n);
Pasul 2: [găseș te cmmdc-ul folosind verificarea numerelor întregi consecutive]
În timp ce(1)
dacă (m mod r = 0 ș i n mod r = 0)
ruptura;
încetează în timp ce
Pasul 3: întoarce r.

[Link] pentru a găsi GCD-ul a două numere. (Metoda de scădere repetitivă)

ALGORITM : gcd(m,n)
//Scop: A găsi MCD-ul a două numere
Acest algoritm calculează PCM-ul a două numere nenegative ș i diferite de zero
valori acceptate ca parametri.
Două valori non-negative ș i non-zero m ș i n
GCD al m ș i n

Pasul 1: [Dacă unul dintre cele două numere este zero, returnează numărul non-negativ a, GCD-ul]
dacă (m=0) returnează n;

dacă (n=0) întoarce m;

Pasul 2 :[Repetaț i pasul 2 atâta timp cât m ș i n sunt diferite]
În timp ce (m!=n)
dacă(m>n)
m m-n;
altfel n n-m;
sfârș it dacă
sfarș it în timp ce

Step 3: [finished : return GCD as the output]

returnează m;

Notă: Aceeaș i problemă poate fi rezolvată în multe moduri (de exemplu, Algoritmul 1, 2 ș i 3).

6
4. Algoritm pentru generarea numerelor prime folosind metoda sitului lui Eratostene. (Pseudo
cod)

ALGORITMUL SIEVE_PRIME(n)
//Scop :Generarea numerelor prime între 2 ș i n
//Description :This algorithm generates prime numbers using sieve method
Un număr întreg pozitiv n>=2
//Output : Prime numbers <=n

Pasul 1: [ Generaț i lista de întregi de la 2 la n ]

pentru p 2 până la n face
a[p] p
sfârș it pentru

Pasul 2: [Eliminaț i multiplii lui p între 2 ș i n]

pentru p 2 la √n face
dacă (a[p] != 0 )
eu p*p
while ( i <= n )
a[i] 0
i i+p
sfârș it în timp ce
termină dacă
final pentru
Pasul 3: [Obț ineț i numerele prime copiind elementele diferite de zero]
m 0
pentru p 2 la n face
dacă (a[p] != 0 )
b[m] a[p];
m m+1
sfârș it dacă
sfârș it pentru

Pasul 4: [Ieşirea numerelor prime între 2 şi n]

pentru i 0 la m-1
scrie b[i]
sfârș it pentru

Pasul 5 : [Finalizat ]
Ieşire

[Link] pentru a găsi numărul de cifre într-o reprezentare binară a unui dat
număr întreg zecimal
Algoritm : Binar(n)
//Purpose :To count the number of digits in a binary representation of a given
integer zecimal.
//Input :n : un întreg pozitiv zecimal.

7
 //Output :Number of digits in a binary representation of a given positive decimal
întreg

Numără 1;
În timp ce ( n > 1)
Numără Numără + 1
n n/2
sfârș it în timp ce
returnează Numărul

Verifică-ț i progresul

1. Ce este un algoritm? Explica no ț iunea de algoritm?

2. Care sunt diferitele proprietă ț i ale unui algoritm?
3. Explica ț i procedura de generare a numerelor prime folosind metoda „Sitului lui Eratostene”
eratosthenes ș i scrie algoritmul pentru acelaș i lucru.
4. Explica ț i pa ș ii implica ț i în proiectarea ș i dezvoltarea unui algoritm.

1.6 REZUMAT

•Algoritm: Un algoritm este o secven ț ă de instruc ț iuni neambigue pentru

rezolvarea unei probleme într-un timp finit. O intrare la un algoritm specifică un
instanț a problemei pe care algoritmul o rezolvă.
•Algoritmul poate fi specificat într-o limbaj natural sau un cod pseudo; de asemenea, ele pot fi.
să fie implementate ca programe de calculator.
Un algoritm bun este de obicei rezultatul unor eforturi repetate ș i al reîncercărilor.
•Aceea ș i problemă poate fi adesea rezolvată de mai multe algoritmi. De exemplu, trei
au fost date algoritmi pentru calcularea celui mai mare divizor comun al două
integri: algoritmul lui Euclid, algoritmul de verificare a numerelor întregi consecutive, ș i
scădere repetitivă.

1.7 KEYWORDS

Algoritm: Este o secvenț ă de instrucț iuni neambigue pentru a rezolva o problemă într-un mod finit.
cantitatea de timp.
Complexitatea timpului: Este timpul necesar pentru a executa un program.
Complexitatea spaț ială: Este cantitatea de memorie necesară pentru a rula un program.

1.8 ANSWERS TO CHECK YOUR PROGRESS

1. 1.1
2. 1.2

8
 3.1.5(4thalgoritm)
4. 1.4

UNIT-EBD EXERCITII Ș I RĂSPUNSURI

1. Găsi ț i pgcd(31415,14142) aplicând algoritmul lui Euclid.

2. Ce face algoritmul lui Euclid pentru o pereche de numere în care primul număr
este mai mic decât al doilea? Care este cel mai mare număr de ori în care acest lucru poate
ce se întâmplă în timpul execuț iei algoritmului pe un astfel de input?
3. Scrie un algoritm pentru a găsi gcd-ul a două numere folosind scăderea repetitivă
metodă. Găseș te cmmdc(36,171) folosind scăderea repetată
4. Scrie un algoritm pentru a găsi numărul de cifre într-o reprezentare binară a unui
număr întreg zecimal dat. Urmăriț i-l pentru intrarea 255.
Answers: SEE

1.5 (1stalgoritm
2. 1.5 (1stalgoritm) [ Indiciu : găseș te gcd(12,24) ]
3. 1.5 (3rdalgoritm
4. 1.5 (5thalgoritm)

1.9 SUGGESTED READINGS

1. Introducere în Designul ș i Analiza Algoritmilor de Anany Levitin

[Link], Alfred V., "Proiectarea ș i analiza algoritmilor computeriza ț i".
[Link] ș i proiectarea algoritmilor de A M Padma Reddy.

9
 MODULUL-1, UNITATEA 2 ANALIZA EFICIENȚEI ALGORITMULUI

Structură
1.0 Obiective
1.1 Introducere în algoritmi
1.2 Proprietă ț ile algoritmului
1.3 Note algoritmice
1.4 Proiectarea ș i dezvoltarea unui algoritm
1.5 Câteva exemple simple
1.6 Rezumat
1.7 Cuvinte cheie
1.8 Răspunsuri pentru a verifica progresul tău
1.9 Exerci ț ii finale ș i răspunsuri
1. 10 lecturi sugerate

1.0 OBJECTIVES
La sfârș itul acestei unităț i, vei fi capabil să

Eficien ț a unui algoritm.

•Complexitatea spa ț ială.
Complexitatea timpului.
•Măsurarea performan ț ei
Nevoia de complexitate temporală
•Eficien ț e în cel mai rău caz, cel mai bun caz ș i caz mediu.
•Notationi asimptotice.
Big-Oh (O)
Big-Omega (Ω)
Theta mare (θ)
•Complexită ț i practice.
Analiza algoritmilor iterative.
Analiza algoritmilor recursivi.

1.1 INTRODUCERE
Două modalităț i importante de a caracteriza eficacitatea unui algoritm sunt spaț iul său
complexitate ș i complexitate temporală. Complexitatea temporală a unui algoritm se referă la determinarea
o expresie a numărului de paș i necesari ca o funcț ie a dimensiunii problemei. Deoarece
măsurarea numărului de paș i este oarecum grosieră, nu se urmăreș te obț inerea unui număr exact de paș i
numără. În schimb, se încearcă doar să se obț ină limite asimptotice asupra numărului de paș i. Asimptotic
analiza foloseș te notaț ia O (Big Oh). Alte două construcț ii de notaț ie utilizate de
conducătorii de calculatoare în analiza algoritmilor sunt notaț ia Θ (Big Theta) ș i Ω (Big
Notaț ia Omega

10
1.2 Complexitatea spa ț ială
Complexitatea de spaț iu a unui program este cantitatea de memorie care poate fi necesară pentru a rula
un program.
1. Memoria principală a unui computer este o resursă importantă pentru func ț ionarea corectă
executarea unui program. Fără suficientă memorie, fie programul funcț ionează
încet sau s-ar putea să nu funcț ioneze deloc. Prin urmare, cerinț a exactă de memorie pentru o
programul trebuie să fie în avans.
2. Atunci când proiectăm un program, trebuie să ne asigurăm că cerin ț ele de memorie sunt men ț inute la
minimum astfel încât chiar ș i calculatoarele cu memorie mai puț ină să poată executa programul.
3. În zilele noastre, sistemele de operare se ocupă de utilizarea eficientă a memoriei
bazat pe conceptul de memorie virtuală sau legare ș i încărcare dinamică.

1.2.1 Analiza complexită ț ii spa ț iale

Următoarele componente sunt importante în calcularea cerinț elor de spaț iu:

•Spa ț iul de instruc ț iune
Acesta este spaț iul necesar pentru a stoca codul maș inii generat de compilator.
În general, codul obiect va fi plasat în segmentul de cod.

Spa ț iu de date
Spaț iul necesar pentru constante, variabile statice, variabile intermediare, dinamice
variabile etc. Acesta nu este altceva decât spaț iul segmentului de date.

•Spa ț iu de stivă
Pentru a stoca adresa de retur, valorile de retur, etc. Pentru a stoca aceste detalii, un segment de stivă
va fi folosit.

1.2.2 Cum să calculăm complexitatea spa ț ială?

Înainte de a trece la orice exemplu specific, trebuie să înț elegem importanț a

dimensiunea intrării, adică n. în general, fiecare problemă va fi asociată cu n. poate să se refere
către

•Numărul de ora ș e - în problema călătorului vânzător.

•Numărul de elemente – în problema sortării ș i căutării.
•Numărul de ora ș e – problema colorării hăr ț ii.
•Numărul obiectelor – problema rucsacului.
Când o problemă este independentă de n, atunci spaț iul de date ocupat de
algoritmul/programul poate fi considerat ca zero. Să începem cu câteva probleme simple
care sunt de tip iterativ.

1. Găsirea mediei a trei numere.

Funcț ia principală vidă()

{
int a,b,c,avg;
scanf("%d %d%d", a, b, c);

11
avg=(a+b+c)/3;
printf("media este=%d", avg);
}

Program pentru a ilustra complexitatea spaț ială.

Deoarece a, b, c ș i avg sunt toate variabile întregi, spaț iul ocupat de ele este
=4*sizeof(int)
=4*2bytes
=8bytes
Spaț iul ocupat de constantul 3 este = 1*2 octeț i.
Prin urmare, spaț iul total este = 8 + 2 = 10 octeț i.

1.3 Complexitate temporală

Este cantitatea de timp pe care un program sau un algoritm o ia pentru execuț ie. Asta este cât de repede un
algoritmul rulează. Reț ineț i că timpul necesar pentru compilarea unui program nu este inclus în
calculul.
În mod normal, cercetătorii acordă mai multă atenț ie eficienț ei în timp decât eficienț ei în spaț iu.
pentru că gestionarea problemelor de memorie este mai uș oară decât timpul.

1.4 ASYMPTOTIC NOTATIONS

Două moduri importante de a caracteriza eficienț a unui algoritm sunt spaț iul său
complexitatea ș i complexitatea temporală. Complexitatea temporală a unui algoritm se referă la determinarea
o expresie a numărului de paș i necesari ca o funcț ie a dimensiunii problemei. Deoarece
măsura numărului de paș i este oarecum grosolană, nu se urmăreș te obț inerea unui pas exact
număr. În schimb, se încearcă doar obț inerea limitelor asimptotice asupra numărului de paș i. Asimptotic
analiza foloseș te notaț ia O (Big Oh). Alte două constructe de notare folosite de
oamenii de ș tiinț ă computaț ionali în analiza algoritmilor sunt notaț ia Θ (Big Theta) ș i Ω (Big
Notaț ia Omega)
Evaluarea performanț ei unui algoritm se obț ine prin totalizarea numărului de
apariț iile fiecărei operaț iuni atunci când se rulează algoritmul. Performanț a unui
algoritmul este evaluat ca o funcț ie a dimensiunii de intrare n ș i trebuie considerat modulo a
constant multiplicativ.

Următoarele note sunt note utilizate frecvent în analiza performanț ei ș i sunt folosite pentru
caracterizează complexitatea unui algoritm.

Notatia Θ (Ordine similar)

Această notare limitează o funcț ie în limite constante. Spunem că f(n) = Θ(g(n)) dacă există
există constante pozitive0,c1ș i2astfel încât la dreapta lui n0valoarea off(n) se află întotdeauna

12
între1g(n) ș i c2g(n) inclusiv.

În notaț ia de seturi, scriem după cum urmează:

Θ(g(n)) = {f(n) : există constante pozitive c1,c1, andn0astfel încât 0 ≤ c1g(n) ≤ f(n)
≤c2g(n) pentru toț i n≥n0}

Spunem că isg(n) este o limită asimptotică strânsă pentru f(n).

Graficeș te, pentru toate valorile lui n la dreapta lui n0, valoarea off(n) se află la sau deasupra c1g(n)
ș i la sau sub2g(n). Cu alte cuvinte, pentru toț i n ≥ n0f(n) este egal cu g(n) la
într-un factor constant. Spunem că g(n) este o limită asimptotică strânsă pentru f(n).

În terminologia seturilor, f(n) se spune că este un membru al setului Θ(g(n)) de funcț ii. În alte
cuvinte, deoarece O(g(n)) este un set, am putea scrie

f(n)∈Θ(g(n))

pentru a indica că f(n) este un membru al Θ(g(n)). În schimb, scriem

f(n) = Θ(g(n))

pentru a exprima aceeaș i notare.

Din punct de vedere istoric, această notare este "f(n) = Θ(g(n))", deș i ideea că f(n) este egal cu
ceva numit Θ(g(n)) este înș elător.

Example:n2/2 − 2n= (n2), cu1= 1/4,c2= 1/2, ș i0= 8.

Notatia O (Limita Superioară)

13
Această notaț ie oferă o limită superioară pentru o funcț ie, în limitele unui factor constant. Noi
writef(n) = O(g(n)) dacă există constante pozitive0ș i astfel încât să fie la dreapta lui n0,
valoarea off(n) se află întotdeauna pe sau sub g(n).

În notaț ia mulț imilor, scriem după cum urmează: Pentru o funcț ie dată g(n), mulț imea funcț iilor

O(g(n)) = {f(n): există constante pozitive c ș i n0astfel încât 0 ≤f(n) ≤c g(n) pentru
toate n≥n0}

Spunem că funcț ia g(n) este o limită superioară asimptotică pentru funcț ia f(n). Folosim
O-notation pentru a oferi o limită superioară unei funcț ii, într-un factor constant.

Grafic, pentru toate valorile lui n la dreapta lui n0, valoarea funcț iei f(n) este pe sau
sub g(n). Scriem f(n) = O(g(n)) pentru a indica că o funcț ie f(n) este un membru al mulț imii
O(g(n)) adică

f(n)∈Ο(g(n))

Observaț i că f(n) = Θ(g(n)) implică f(n) = Ο(g(n)), deoarece notaț ia Θ este o notare mai puternică.
decât notaț ia Ο.

Exemplu: 2n2= O(n3), cu c = 1 ș i n0= 2.

Equivalently, we may also definefis of ordergas follows:

Dacă f(n) ș i g(n) sunt funcț ii definite pe numerele întregi pozitive, atunci f(n) este Ο(g(n)) dacă ș i
numai dacă există ac> 0 ș i an0> 0 astfel încât

|f(n)| ≤ |g(n)| pentru toț i n≥n0

14
Notă istorică: Notaț ia a fost introdusă în 1892 de matematicianul german Paul
Bachman.

Ω-Notatia (Limita Inferioară)

Această notare oferă o limită inferioară pentru o funcț ie în cadrul unui factor constant. Scriem f(n)
= Ω(g(n)) dacă există constante pozitive0ș i astfel încât să fie la dreapta lui0, valoarea
off(n) minte întotdeauna pe sau deasupra g(n).

În notaț ia mulț imilor, scriem după cum urmează: Pentru o funcț ie dată g(n), mulț imea funcț iilor

Ω(g(n)) = {f(n) : există constante pozitive c ș i n0astfel încât 0 ≤ c g(n) ≤ f(n) pentru
toate n≥n0}

Spunem că funcț ia g(n) este o limită inferioară asimptotică pentru funcț ia f(n).

Intuiț ia din spatele notaț iei Ω este prezentată mai sus.

Exemplu: √n= (lgn), cu c= 1 ș i n0= 16.

1.4.1 Analiza Algoritmilor

Complexitatea unui algoritm este o funcț ie g(n) care oferă limita superioară a
numărul de operaț iuni (sau timpul de execuț ie) efectuate de un algoritm atunci când dimensiunea de intrare este n.

Există două interpretări ale limitei superioare.

Complexitate în cel mai rău caz

Timpul de execuț ie pentru orice dimensiune dată a intrării va fi mai mic decât limita superioară
cu exceptia posibil unor valori ale intrării unde se atinge maximul.

15
 Complexitate medie
Timpul de execuț ie pentru orice dimensiune de intrare dată va fi numărul mediu de
operaț iuni asupra tuturor instanț elor problemei pentru o dimensiune dată.

Pentru că este destul de dificil să estimăm comportamentul statistic al intrării, majoritatea

ne mulț umim cu un comportament de cea mai proastă situaț ie. Cel mai adesea, complexitatea
ofg(n) este aproximat de familia o(f(n)) unde f(n) este unul dintre următoarele
funcț ii.n(complexitate liniară), logn(complexitate logaritmică),naunde a≥ 2
(complexitate polinomială),an(complexitate exponenț ială).

1.4.2 Optimalitate

Odată ce complexitatea unui algoritm a fost estimată, apare întrebarea dacă aceasta
un algoritm este optim. Un algoritm pentru o problemă dată este optim dacă complexitatea sa
atinge limita inferioară pentru toate algoritmii care rezolvă această problemă. De exemplu, orice
algoritmul care rezolvă problema „intersecț ia n segmentelor” va fi executat la
cel mai puț in2operaț iunile în cel mai rău caz chiar dacă nu face nimic altceva decât să imprime rezultatul. Acesta este
prescurtat prin a spune că problema are Ω(n2) complexitate. Dacă cineva găseș te un O(n2)
un algoritm care rezolvă această problemă, va fi optim ș i de complexitate Θ(n2).

1.5 Complexită ț i practice

Teoria complexităț ii computaț ionale este o ramură ateoria de

calculînș tiinț a teoretică a calculatoarelorș imatematicăcare se concentrează pe
clasificareprobleme computaț ionaleconform dificultăț ii lor inerente. În acest context,
o problemă computaț ională este înț eleasă ca fiind o sarcină care, în principiu, este susceptibilă de a fi
rezolvat de un computer (ceea ce înseamnă, în esenț ă, că problema poate fi formulată printr-un set de
instrucț iuni matematice). Informal, o problemă computaț ională constă în problemă
instanț e ș i soluț ii pentru aceste instanț e de probleme. De exemplu,testarea primalităț iieste
problema de a determina dacă un număr dat esteprimsau nu. Exemplele acestui
problema estenumere naturale, iar soluț ia pentru o instanț ă este da sau nu pe baza
dacă numărul este prim sau nu.

O problemă este considerată dificilă în mod inerent dacă soluț ia sa necesită resurse semnificative,
indiferent de algoritmul utilizat. Teoria formalizează această intuiț ie, introducând
matematicmodele de calcula studia aceste probleme ș i a cuantifica cantitatea
a resurselor necesare pentru a le rezolva, cum ar fi timpul ș i stocarea. Alte măsuri de complexitate
sunt de asemenea folosite, cum ar fi cantitatea de comunicare (folosită încomunicare
complexitate), numărul de porț iîntr-un circuit (utilizat încomplexitatea circuitului)
ș i numărul
de procesoare (folosite încalcul paralel). One of the roles of computational complexity
teoria este de a determina limitele practice asupra a ceea cecomputers poate ș i nu poate face.

16
Domenii strâns legate în ș tiinț a calculatoarelor teoretice suntanaliza de
algoritmiș iteoria calculabilităț iiO distincț ie cheie între analiza algoritmilor
ș i teoria complexităț ii computaț ionale se ocupă de analizarea
cantitatea de resurse necesare unei anumite algoritm pentru a rezolva o problemă, în timp ce
ultima pune o întrebare mai generală despre toate algoritmii posibili care ar putea fi folosiț i pentru
rezolvă aceeaș i problemă. Mai precis, încearcă să clasifice problemele care pot sau nu pot fi
rezolvat cu resurse corespunzător restricț ionate. La rândul său, impunând restricț ii asupra
resursele disponibile sunt ceea ce distinge complexitatea computaț ională de computabilitate
teoria: teoria de mai sus întreabă ce tip de probleme pot, în principiu, fi rezolvate
algoritmic
1.5.1 Probleme de funcț ie
Aproblemă de funcț ieeste o problemă computaț ională în care un singur rezultat (al unui funcț ie totală)
se a ș teaptă pentru fiecare input, dar output-ul este mai complex decât cel al unui decizie
problemă, adică, nu este doar da sau nu. Exemple notabile includ vânzător călător
problemăș iproblema factorizării întregilor.

Este tentant să credem că noț iunea de probleme de funcț ie este mult mai bogată decât noț iunea
al problemelor de decizie. Totuș i, acesta nu este chiar cazul, deoarece problemele de funcț ie pot fi
reformulează-le ca probleme de decizie. De exemplu, înmulț irea două întregi poate fi
exprimate ca un set de triple (a,b,c) astfel încât relaț ia a×b=cholds. Deciderea
fie că un triplet dat este membru al acestui set corespunde rezolvării problemei de
înmulț irea a două numere.
1.5.2 Măsurarea dimensiunii unei instanț e
Pentru a măsura dificultatea rezolvării unei probleme computaț ionale, cineva ar putea dori să vadă cum
timp mult algoritmul cel mai bun necesită pentru a rezolva problema. Cu toate acestea, timpul de execuț ie
poate, în general, depinde de instanț ă. În special, instanț ele mai mari vor necesita mai mult
timpul necesar pentru a rezolva. Astfel, timpul necesar pentru a rezolva o problemă (sau spaț iul necesar, sau orice

măsura complexită ț ii) este calculată ca o func ț ie a dimensiunii instan ț ei. Aceasta este
de obicei considerată a fi dimensiunea intrării în biț i. Teoria complexităț ii este interesată de modul în care
algoritmii escaladează odată cu creș terea dimensiunii intrării. De exemplu, în problema de a găsi
dacă un graf este conectat, cât mai mult timp durează să rezolvăm o problemă pentru un
grafic cu 2n vârfuri comparativ cu timpul necesar pentru un grafic cu n vârfuri?

Dacă dimensiunea de intrare este n, timpul necesar poate fi exprimat ca o funcț ie de n. Deoarece timpul
luate pe baza unor intrări diferite de aceea ș i dimensiune pot fi diferite, cazul cel mai rău în timp
complexitatea T(n) este definită ca fiind timpul maxim necesar pentru toate intrările de mărime n. Dacă T(n)
este un polinom în n, atunci algoritmul este spus a fi unpolinom
[Link] lui Cobhamspune că o problemă poate fi rezolvată cu o cantitate fezabilă

17
de resurse dacă admite un algoritm de timp polinomial.

1.6 Măsurarea performan ț ei algoritmilor simpli

1. Găsiț i complexitatea temporară a următoarelor algoritmi
a.)Algoritm :simplu
pentru (i=0; i<=n*n; i++)
pentru (j=i+1; j<i; j++)
dacă(i<j){
sum++;}

Solfor (i=1; i<=n*n; i++) Executat de n*n ori

pentru (j=0; j<i; j++) Executed <= n*n ori
sum++; O(1)
Timp de rulare: O(n4)

2. Algoritm pentru înmulț irea matricilor

Algoritm matmul(a[0…n-1],b[0..n-1])
două matrice n cu n

//output: Matricea c=ab

Pentru i 0 până la n-1 face

Pentru j 0 la n-1 fă

C[I,j] 0
Pentru k 0 la n-1 fă

C[I,j] c[I,j]+a[I,k]+b[k,j]
Returnează c
n1n1n1
Complexitatea temporala a acestui algoritm este data de M(n)= 1 =n3
i =0j =0k =0

[Link] pentru unicitatea elementelor

Algorithm : uniquelement(a[].n)

//input : n – number of elements and a- an array consisting of n elements

Pentru i 0 până la n-2 face

18
Pentru i i+1 până la n-1 fă

Dacă(a[i]=a[j])
Returnaț i 0;
Sfârș it dacă

Returnează 1;
n -2n -1
Eficienț ă în cel mai rău caz : ∑ ∑1 = n(n−1) / 2<= n2
eu
=0j =e u +1

T(n)€O(n2)
Cea mai bună eficienț ă: dacă a[0]=a[1] atunci operaț ia de bază va fi executată o singură dată.

Prin urmare, t(n)€Ω(1)

Notă: Pentru a rezolva eficien ț a temporală a algoritmilor non-recursivi, folosi ț i formula

rezultatul = limita superioară - limita inferioară + 1 în fiecare sumă.

Verifică-ț i progresul

1. Explica conceptul de complexitate a spaț iului

2. Ce înseamnă complexitatea temporală? De ce este necesară?

3. scrie o notă despre notatiile asimptotice.
4. Găsiț i complexitatea temporală a algoritmului de înmulț ire a matricei.

SUMMARY:
Complexitatea spaț ială: Complexitatea spaț ială a unui program este cantitatea de memorie care poate

be required to run a program.

Complexitatea temporală: Este timpul necesar pentru a executa un program.

Notatii asimptotice – reprezentarea complexităț ii de timp în oricare dintre notatii (big

oh, omega mare, theta mare).

1.5 KEYWORDS
Operaț iune de bază – o operaț iune care este executată de mai multe ori în program
(partea logică). De obicei, prezentă în cea mai interioară buclă (parte) a algoritmului/programului.

19
1.6 RASPUNSURI PENTRU A VERIFICA PROGRESUL TĂU

1. 1.2
2. 1.3
3. 1.4
4. 1.6
1.7 EXERCI ȚII Ș I RĂSPUNSURI LA SFÂR Ș ITUL UNITĂ ȚII

1. Găsi ț i complexitatea temporală a algoritmului transpunere a unei matrice.

2. Scrie o notă despre cel mai bun caz, cazul mediu, cel mai rău caz într-un program cu exemplu

VEZI
1. 1.4
2. 1.3

1.8LECTURI SUGERATE
1. Introducere în proiectarea ș i analiza algoritmilor de Anany Levitin
2. Analiza ș i designul algoritmilor cu C/C++ - 3rdediț ie de Prof. Nandagopalan
3. Analiza ș i proiectarea algoritmilor de către Padma Reddy

4. Chiar, Shimon., "Algoritmi Grafici", Editura Ș tiinț a Calculatoarelor.

20
 MODULE-1,UNIT 3 ALGORITMI ANALIZĂ ȘI SOLUȚIONARE
RECURRENTE

Structură
1.0 Obiective
1.1 Analizând structurile de control
1.2 Folosind un barometru

1.3 Analiza cazului mediu

1.4 Analiza amortizată
1.5 Rezolvarea recurenț elor
1.6 Summary
1.7 Cuvinte cheie

1.8 Răspunsuri pentru a-ț i verifica progresul

1.9 Exerciț ii ș i răspunsuri de final de unitate

1.10 Suggested readings

2.0 OBIECTIVE
La sfârș itul acestei unităț i vei fi capabil să
•Rezolvarea problemelor de încărcare a containerelor ș i a problemei rucsacului.

Găsi ț i cele mai scurte căi folosind algoritmul lui Prim ș i algoritmul lui Kruskal.

•Identificarea diferen ț ei dintre arborele grafic ș i arborele de acoperire minimă.

2.1 INTRODUCERE

Un instrument esenț ial pentru a proiecta un algoritm eficient ș i adecvat este 'Analiza de
Algoritmi. Nu există o formulă magică, este pur ș i simplu o chestiune de judecată, intuiț ie ș i
experienț ă. Totuș i, acestea sunt câteva tehnici de bază care sunt adesea utile, cum ar fi
ș tiind cum să te ocupi de structurile de control ș i
ecuaț ii recursive.

1.2 Analizând structurile de control

Analiza structurilor de control: În cele din urmă, analiza algoritmilor decurge din interior
ieș ire. Determinaț i mai întâi timpul necesar instrucț iunilor individuale, apoi combinaț i

21
aceste tainuri conform sistemelor de control care combină instrucț iunile în
program.

1.2.1. Secvenț iere:

Fie P1 ș i P2 două fragmente ale unui algoritm. Ele pot fi o singură instrucț iune. Ele
pot fi instrucț iuni simple sau sub-algoritmi complicaț i. Să fie t1 ș i t2 timpii
luate de P1 ș i P2. t1 ș i t2 pot depinde de diferite parametrii, cum ar fi instanț a
dimensiune. Regula de secvenț iere spune că timpul necesar pentru a calcula „P1 ș i P2” este pur ș i simplu t1
+ t2. Conform regulii maxime, acest timp este în q(max(t1, t2)). În ciuda simplităț ii sale, aplicarea
această regulă este uneori mai puț in evidentă decât ar putea părea. Ar putea să se întâmple ca unul dintre
parametrii care controlează t2 depind de rezultatele calculului efectuat P1.

1.2.2. Buclă „For”:

Ele sunt cele mai uș oare bucle de analizat. Pentru i 1 până la m fac P(i) Printr-o convenț ie pe care o vom adopta:
m=0 înseamnă că P(i) nu este executat deloc, (nu este o eroare). P(i) ar putea depinde de dimensiune. De
Desigur, cel mai simplu caz este atunci când nu o face. Să fie t timpul necesar pentru a calcula P(i) ș i
timpul total necesar este l=mt. De obicei, această abordare este adecvată, dar există un potenț ial
pitfall: We didn’t consider the time for the “loop control”. After all our for loops is
o abreviere pentru ceva de genul următor pentru bucla while.

eu 1
în timp ce i <= m face
P(i)
eu i + 1
În cele mai proaste situaț ii, este rezonabil să se considere testul i £ m la cost unitar ș i acelaș i
lucru cu instrucț iunile i ¬i + 1 ș i operaț iile de secvenț iere „mergi la” implicite în
bucle while. Să fie „c” limita superioară a timpului necesar pentru fiecare dintre operaț ii:
l <= c pentru i ¬1
+ (m+1)c teste i £ m
+ execuț ia mt a P(i)
+ execuț ie mc a i i + 1
+ operaț iunile de secvenț iere mc
l <= (t+3c)m+2c
Acest timp este clar limitat inferior de mt. Dacă c este neglijabil comparativ cu t, anteriorul nostru
estimarea că l este aproximativ egal cu mt este justificată. Analiza buclei for este mai
interesant când timpul t(i) necesar pentru P(i) variază ca o funcț ie de I ș i/sau de dimensiune
n.
Aș adar: pentru i 1 până la m face P(i) care durează un timp dat de, t(i) (ignorând timpul necesar de către
controlul buclei).

Algoritm pentru înmulț irea matricilor

22
Algoritm matmul(a[0…n-1],b[0..n-1])

matrice n pe n
matrice c=ab

Pentru i 0 până la n-1 fac

Pentru j 0 la n-1 face

C[I,j] 0

Pentru k 0 la n-1 faceț i

C[I,j] c[I,j]+a[I,k]+b[k,j]
Returnează c
n1n1n1
Complexitatea temporală a acestui algoritm este dată de M(n) = 1 €θ(n3)
=0j
eu =0k =0

1.2.3 Apeluri recursive:

Analiza algoritmilor recursivi este destul de simplă până la un anumit punct. Simplu
inspecț ia algoritmului dă adesea naș tere unei ecuaț ii de recurenț ă care "mimează"
fluxul de control în algoritm. Tehnici generale despre cum să rezolvi sau cum să transformi
ecuaț ia în ecuaț ii mai simple non-recursive va fi analizată mai târziu.

1.2.4 Buclă "While" ș i "Repeat":

Aceste două tipuri de bucle sunt de obicei mai greu de analizat decât buclele "for" deoarece există
nu există o modalitate a priori evidentă de a ș ti de câte ori va trebui să facem turul buclei.
Tehnica standard pentru analizarea acestor bucle este de a găsi o funcț ie a variabilelor
implicat unde valoarea scade de fiecare dată când se învârte. Pentru a determina de câte ori
buclele se repetă, însă trebuie să înț elegem mai bine cum se valorizează această funcț ie
scade. O abordare alternativă a analizei buclelor „while” constă în a trata
îi ca algoritmi recursivi. Ilustrăm ambele tehnici cu acelaș i exemplu,
analiza buclelor "repeat" se desfăș oară în mod similar.

1.3 Folosirea unui barometru

1.4 Exemple suplimentare

a. Algoritm pentru a găsi suma elementelor dintr-un tablou
Algoritm suma(a,n)

23
 {
s=0.0;
pentru I=1 până la n face

s= s+a[I];
returnează s;
}
Instan ț ele problemei pentru acest algoritm sunt caracterizate prin n,
numărul de elemente care trebuie sumate. Spaț iul necesar d de ‘n’ este unul
cuvânt, deoarece este de tip întreagă.
Spa ț iul necesar pentru 'a’a este spa ț iul necesar pentru variabile de tip
array de numere cu puncte flotante.
•Aceasta este de cel pu ț in 'n' cuvinte, deoarece 'a' trebuie să fie suficient de mare pentru a con ț ine 'n'
elemente de adunat.
•A ș adar, ob ț inem S sum(n)>=(n+s)
[ n pentru a[], unul fiecare pentru n, I a & s]

Complexitatea Temporală:

Timpul T(p) necesar unui program P este suma timpului de compilare

ș i timpul de execuț ie

Timpul de compilare nu depinde de caracteristicile instanț ei. De asemenea, noi

se poate presupune că un program compilat va fi rulat de mai multe ori fără
recompilare. Acest timp de rulare este notat cu tp (caracteristicile instanț ei).

Numărul de paș i al oricărei declaraț ii de problemă este atribuit în funcț ie de tipul

a declaraț iei.

De exemplu, comentarii 0 paș i.

Instrucț iuni de atribuire 1 paș i.
Care nu implică apeluri către alte algoritmi

Declaraț ie interactivă cum ar fi pentru, cât timp & repetă-până Control parț ial al
declaraț ie.

1. Introducem o variabilă, count, în declaraț ia programului pentru a incrementa count

cu valoarea iniț ială 0. Declaraț ia pentru a incrementa numărul cu suma corespunzătoare este
introdus în program.
Acest lucru este făcut astfel încât de fiecare dată când o declaraț ie din programul original este
numărul de execuț ii este incrementat cu numărul de paș i al acelei declaraț ii.

Algoritm:

Algoritm sum(a,n)
{
s = 0.0;

24
 count = count + 1;
pentru I=1 până la n face

{
count = count + 1;
s=s+a[I];
count=count+1;
}
count=count+1;
count=count+1;
returneaza s;
}

Dacă numărătoarea este zero la început, atunci va fi 2n + 3 la terminare. Aș adar, fiecare

invocarea sumei execută un total de 2n+3 paș i.
A doua metodă de a determina numărul de paș i al unui algoritm este de a construi o
tabel în care enumerăm numărul total de paș i contribuț i de fiecare afirmaț ie.

Mai întâi determină numărul de paș i pe execuț ie (p/e) al declaraț iei ș i

numărul total de ori (adică, frecvenț a) în care fiecare afirmaț ie este executată.
Prin combinarea acestor două cantităț i, contribuț ia totală a tuturor afirmaț iilor,
numărul de paș i pentru întregul algoritm este obț inut.

Declaraț ie S/e Frequency Total

1. Algoritm Suma(a, n) 0 - 0
2.{ 0 - 0
3. S=0.0; 1 1 1
4. pentru I=1 până la n fac 1 n+1 n+1
5. s=s+a[I]; 1 n n
6. returnează s; 1 1 1
7. } 0 - 0

Total 2n+3

1.5 ANALIZĂ AVERAGE - CAZ

•Majoritatea timpului, analiza cazului mediu este efectuată sub mai mult sau mai pu ț in
o presupunere realistă că toate instanț ele de orice dimensiune sunt la fel de probabile.
•Pentru problemele de sortare, este simplu de presupus că toate elementele care trebuie să fie
sortate sunt distincte.
•Să presupunem că avem ‘n’ elemente distincte de sortat prin inser ț ie ș i toate n!
permutările acestor elemente sunt la fel de probabile.

25
 •Pentru a determina timpul mediu necesar algoritmului, am putea adăuga
timpurile necesare pentru a sorta fiecare dintre permutările posibile, apoi împărț iț i la n!
răspunsul astfel obț inut.
O abordare alternativă, mai u ș oară în acest caz, este să analizăm direct timpul.
cerut de algoritm, raț ionând probabilistic pe măsură ce avansăm.
•Pentru orice I,2 I n, considera sub-array-ul, T[1….i].
Rangul par ț ial al T[I] este definit ca pozi ț ia pe care ar ocupa-o dacă sub
array-urile au fost sortate.

•De exemplu, rangul par ț ial al T[4] în [3,6,2,5,1,7,4] este 3 deoarece T[1….4]
o dată sortat este [2,3,5,6].
•Clar că rangul par ț ial al T[I] nu depinde de ordinea elementului în
•Subarray T[1…I-1].

Analiză

Cazul cel mai bun: Această analiză impune restricț ii asupra inputului, cu excepț ia dimensiunii. Rezultând în cele mai rapide.
timp de execuț ie posibil
Cazul cel mai rău: Această analiză impune constrângeri asupra inputului, în afară de mărime. Rezultând în viteze mai rapide.
timp de execuț ie posibil
Cazul mediu: Acest tip de analiză rezultă în timpul mediu de execuț ie pentru fiecare tip de
input.
Complexitate: Complexitatea se referă la rata la care timpul de stocare cre ș te ca o func ț ie
dimensiunea problemei
Analiza asimptotică: Exprimarea complexităț ii în termeni de relaț ia sa cu cunoaș terea
funcț ie. Această analiză de tip se numeș te analiză asimptotică.
Notaț ie asimptotică:
Mari 'oh': funcț ia f(n)=O(g(n)) dacă ș i numai dacă există constante pozitive c ș i n0 astfel încât
f(n)≤c*g(n) pentru toate n, n ≥ no.
Omega: funcț ia f(n)=Ω(g(n)) dacă ș i numai dacă există constante pozitive c ș i n0 astfel încât
f(n) ≥ c*g(n) pentru toate n, n ≥ no.
Theta: funcț ia f(n) = ө(g(n)) dacă ș i numai dacă există constante pozitive c1, c2 ș i n0 astfel încât
c1 g(n) ≤ f(n) ≤ c2 g(n) pentru toate n, n ≥ no.
1.6 Analiza amortizată
Îninformaticăanaliza amortizată este o metodă deanalizând algoritmiică
consideră întreaga secvenț ă de operaț iuni ale programului. Permite stabilirea
al unei limite de caz cel mai rău pentru performanț a unui algoritm, indiferent de intrări, prin
privind toate operaț iunile. La baza metodei se află ideea că, în timp ce anumite
operaț iunile pot fi extrem de costisitoare în resurse, ele nu pot avea loc la un nivel suficient de ridicat
frecvenț a de a împovăra întregul program din cauza numărului de operaț iuni mai puț in costisitoare
vor depăș i cu mult numărul celor costisitori pe termen lung, "răsplătind" programul pe o
numărul de iteraț ii. Este deosebit de util deoarece garantează cazurile cele mai proaste
performanț ă în timp ce ia în considerare întregul set de operaț ii dintr-un algoritm.
Există în general trei metode pentru a efectua analiza amortizată: agregatul
metoda, metoda contabilă ș i metoda potenț ială. Toate acestea oferă aceeaș i
răspunsuri, iar diferenț a lor de utilizare este în principal circumstanț ială ș i datorată individualităț ii
preferinț ă.

26
 . Analiza agregată determină limita superioară T(n) asupra costului total al unei
secvenț a operaț iunilor, apoi calculează costul mediu ca T(n) / n.
. Themetodă contabilă determina costul individual al fiecărei opera ț iuni,
combinând timpul său de execuț ie imediat ș i influenț a sa asupra timpului de rulare al
opera ț iuni viitoare. De obicei, multe opera ț iuni de scurtă durată acumulează o "datorie" de
o stare nefavorabilă în mici creș teri, în timp ce operaț iunile rare de lungă durată o scad
drastic
. Themetodă potenț ialăeste ca metoda contabilităț ii, dar supraîncărci operaț iunile
devreme pentru a compensa subfacturările ulterioare.

Ca un exemplu simplu, într-o implementare specifică aarray dinamicîi dublăm dimensiunea

a array-ului de fiecare dată când se umple. Din această cauză, poate fi necesară realocarea array-ului, iar în
în cel mai rău caz, o inserț ie poate necesitaO(n). Cu toate acestea, o secvenț ă de n inserț ii poate fi întotdeauna
finalizat în timp O(n), deoarece restul inserț iilor sunt realizate în timp constant, inserț iile fiului pot
se va finaliza în timp O(n). Timpul amortizat pe operaț iune este, prin urmare, O(n) / n = O(1).
O altă modalitate de a vedea asta este să ne gândim la o secvenț ă de n operaț ii. Există 2 posibilităț i.
operaț iuni: o inserț ie regulată care necesită un timp constant c pentru a fi efectuată (presupunând c = 1), ș i un
dublarea tabloului care necesită timp O(j) (unde j<n ș i este dimensiunea tabloului în momentul
înmulț irea). Clar, timpul necesar pentru a efectua aceste operaț ii este mai mic decât timpul necesar pentru a efectua n
inserț ii regulate în plus faț ă de numărul de dublări ale matricei care ar fi avut loc în
secvenț a originală de n operaț ii. Există doar atâtea dublări de tablouri în secvenț ă câte
există puteri de 2 între 0 ș i n (lg(n)). Prin urmare, costul unei secvenț e de n operaț iuni este
strict mai puț in decât expresia de mai jos:

Timpul amortizat pe operaț iune este limita de timp în cel mai rău caz pentru o serie de n operaț iuni.
împărț it la n. Timpul amortizat pe operaț iune este astfel
O(3n) /n= O(n) /n= O(1).

1.7 Recursie:

Recursia poate avea următoarele definiț ii:

Repetiț ia încuibată a unui algoritm identic este recursivitatea.
Este o tehnică de definire a unui obiect/proces prin sine însuș i.
Recursia este un proces prin care o funcț ie se apelează pe sine în mod repetat până când se îndeplinesc anumite condiț ii specificate.

condiț ia a fost îndeplinită.

Recursivitatea poate avea următoarele definiț ii:
Repetiț ia imbricată a unui algoritm identic este recursivitatea.
Recursia este un proces prin care o funcț ie se apelează pe ea însăș i în mod repetat până când se îndeplineș te o anumită condiț ie.

condiț ia a fost satisfăcută.

1.7.1 Când să foloseș ti recursia:

27
 Recursia poate fi utilizată pentru calcule repetitive în care fiecare acț iune este declarată
în ceea ce priveș te rezultatul anterior. Există două condiț ii care trebuie să fie îndeplinite de orice
procedură recursivă.

De fiecare dată când o func ț ie se apelează singură, ar trebui să se apropie de solu ț ie.
2. Trebuie să existe un criteriu de decizie pentru oprirea procesului.

În luarea deciziei dacă să scrii un algoritm într-o formă recursivă sau non-recursivă
form, este întotdeauna recomandabil să se considere o structură de arbore pentru problemă. Dacă structura este
simplu atunci foloseș te forma non-recursivă. Dacă copacul pare destul de des, cu puț ină duplicare
al sarcinilor, atunci recursia este potrivită.

Algoritmul de recursie pentru găsirea factorialului unui număr este dat mai jos,

Algoritm: factorial-recursiv
n, numărul a cărui factorial trebuie găsit.
f, factorialul lui n
Metodă: dacă(n=0)
f=1
altfel
f=factorial(n-1) * n
dacă sfârș it
algoritmul se încheie.

Procedura generală pentru orice algoritm recursiv este următoarea,

1. Salva ț i parametrii, variabilele locale ș i adresele de întoarcere.

2. Dacă criteriul de încetare este atins, efectuează calculul final ș i du-te la pasul 3
în caz contrar, efectuează calculele finale ș i mergi la pasul 1

3. Restaurează cele mai recent salvate parametri, variabila locală ș i adresa de întoarcere ș i
mergi la cea mai recentă adresă de retur.

28
1.7.2 Itera ț ie vs Recursie:

Dezavantajele algoritmilor recursive:

1. Multe limbaje de programare nu suportă recursivitatea; prin urmare, recursiv

funcț ia matematică este implementată folosind metode iterative.
2. Chiar dacă func ț iile matematice pot fi implementate u ș or folosind recursivitatea, aceasta
este întotdeauna cu costul timpului de execu ț ie ș i al spa ț iului de memorie. De exemplu,
arborele de recursie pentru generarea a 6 numere în generaț ia seriei Fibonacci este dat
în figura 2.5. O serie Fibonacci este de forma 0,1,1,2,3,5,8,13,…etc, unde a treia
numărul este suma celor două numere precedente ș i aș a mai departe. Se poate observa din
fig 2.5 că, f(n-2) este calculat de două ori, f(n-3) este calculat de trei ori, f(n-4) este
calculat de 5 ori.
3. O procedură recursivă poate fi apelată din interiorul sau din exteriorul său ș i pentru a asigura aceasta
funcț ionare corectă trebuie să salveze în anumită ordine adresele de întoarcere, astfel încât
întoarcerea la locaț ia corespunzătoare va avea loc când întoarcerea la o instrucț iune de apel este
făcut.
4. Programele recursive necesită considerabil mai mult stocare ș i vor dura mai mult timp.

1.7.3 Dezavantajele metodelor iterative:

Func ț ii matematice precum factorialul ș i generarea seriei Fibonacci pot fi

esenț ial mai uș or de implementat folosind recursie decât iteraț ie.
În tehnicile iterative, repetarea instruc ț iunilor este foarte necesară.

Recursia este o abordare de sus în jos pentru rezolvarea problemelor. Aceasta împarte problema în bucăț i.
sau selectează un pas cheie, amânând restul.
Iteraț ia este mai degrabă o abordare de jos în sus. Aceasta începe cu ceea ce este cunoscut ș i din aceasta
construieș te soluț ia pas cu pas. Funcț ia iterativă foloseș te evident un timp care este
O(n) în timp ce funcț ia recursivă are o complexitate de timp exponenț ială.
Este întotdeauna adevărat că recursia poate fi înlocuită de iteraț ie ș i stive. De asemenea, este adevărat că
stiva poate fi înlocuită de un program recursiv fără stivă.

29
1.7.4 SOLU ț IONAREA RECUREN ț ELOR :-( Se întâmplă din nou (sau) repetat)

•Ultimul pas indispensabil atunci când analizezi un algoritm este adesea să rezolvi o
ecuaț ie de recurenț ă.
•Cu pu ț ină experien ț ă ș i inten ț ie, majoritatea recuren ț elor pot fi rezolvate prin
ghicire inteligentă
•Cu toate acestea, există o tehnică puternică care poate fi utilizată pentru a rezolva anumite
clase de recurenț ă aproape automat.
•Acesta este un subiect principal al acestei sec ț iuni, tehnica ecua ț iei caracteristice.

1. Muncă de ghicire inteligentă:

Această abordare se desfăș oară, în general, în 4 etape.

1. Calculează primele câteva valori ale recuren ț ei

2. Caută regularitate.
3. Găsi ț i o formă generală potrivită.
4. Ș i în final, demonstrează prin induc ț ie matematică (poate induc ț ie constructivă).

1) (Fibonacci) Considera ț i recursivitatea.

n dacă n=0 sau n=1

fn=
f n-1+ fn-2 altfel

Rescriem recurenț a ca,

fn– fn-1- fn-2 =0.

Polinomul caracteristic este,

x2- x - 1 = 0.

Rădăcinile sunt,
-(-1) ± √((-1)² + 4)
x = ------------------------
2

1 ±√ (1 + 4)
= ----------------
2

1 ± √5
= ----------
2

30
 1+√5 1 - √5
r1= --------- și r2= ---------
2 2

Soluț ia generală este,

fn= C1r1n+ C2r2n

când n=0, f0= C1+ C2= 0

când n=1, f1= C1r1+ C2r2= 1

C1+ C2= 0 (1)

C1r1+ C2r2 = 1 (2)

Din ecuaț ia (1)

C1= -C2

Substituie C1in equation(2)

-C2r1+ C2r2= 1
C2[r2– r1] = 1

Substituiț i r1ș i r2valori

1 - √5 1 - √5
C2--------- ---------
- = 1
2 2
1 – √5 – 1 – √5
C2--------------------- = 1
2

-C2* 2√5
-------------- = 1
2

− √5C2= 1

C1= 1/√5 C2= -1/√5

Astfel,
n n
1 1 + √5 -1 1 - √5
fn= ---- --------- + ---- --------
√5 2 √5 2
n n
1 1 + √5 1 - √5
= ------------- - ---------

31
 √5 2 2

3. Recursie inomogenă :

Solu ț ia unei recuren ț e liniare cu coeficient constant devine mai dificilă.

când recurenț a nu este omogenă, adică atunci când combinaț ia liniară nu este
egal cu zero.
* Lua ț i în considerare următoarea recuren ț ă
a0tn+ a1tn-1+ … + akt n-k= bnp(n)
* Partea stângă este aceea ș i ca înainte, (homogenă) dar pe partea dreaptă
avem bnp(n), unde,
b este o constantă
p(n) este un polinom în 'n' de grad 'd'.

Exemplu(1):

Consideraț i recurenț a,
tn- 2tn-1= 3n (A)

În acest caz, b=3, p(n) = 1, grad = 0.

Polinomul caracteristic este,

(x - 2)(x - 3) = 0

Rădăcinile sunt, r1= 2, r2= 3

Soluț ia generală,
tn= C1r1n+ C2r2n
tn= C12n+ C23n (1)

când n=0, C1+ C2= t0 (2)

când n=1, 2C1+ 3C2= t1 (3)

sub n=1 în ecuaț ia (A)

t1-2t0= 3
t1= 3 + 2t0

substituent t1în eqn(3),

(2) * 2 2C1+ 2C2= 2t0

2C1+ 3C2= (3 + 2t0)
-------------------------------
-C2= -3
C2= 3

Sub C2= 3 în ecuaț ia (2)

32
 C1+ C2= t0
C1+ 3 = t0
C1= t0– 3

Prin urmare tn= (t0-3)2n+ 3. 3n

= Max[O[(t0– 3) 2n] O[3.3n]]
= Max[O(2n), O(3n] constante
= O[3n]

Exemplu: 2. Rezolvaț i următoarea relaț ie de recurenț ă

x(n)=x(n-1)+5 for n>1 , x(1)=0
Soluț ie: Relaț ia de recurenț ă de mai sus poate fi scrisă după cum urmează
x(n)={ x(n-1)+5 dacă n>1
0 dacă n=1}
consideraț i relaț ia când n>1
x(n)=x(n-1)+5 -------a
Înlocuieș te n cu n-1 în ecuaț ia a
x(n)=x(n-2)+5+5
Înlocuieș te n cu n-2 în eqv a
x(n)= x(n-2)+5+5+5
x(n)= x(n-2)+3*5
………………….
…………………..
În cele din urmă, x(n)=x[n-(n-1)]+(n-1)*5
= x(1)+(n-1)*5
=0 +(n-1)*5
x(n)=5(n-1)

4. Schimbare de variabile:
* Uneori este posibil să rezolvăm recursiuni mai complicate făcând o
schimbarea variabilei.
* În exemplul următor, scriem T(n) pentru termenul unei recursii generale.
ș i tipentru termenul unei noi recursi obț inute din prima printr-o schimbare de
variabilă.

Exemplu: (1)
Consideraț i recurenț a,

1 , dacă n=1
T(n) =
3T(n/2) + n, dacă 'n' este o putere a lui 2, n>1

Reconsidera recurenț a pe care am rezolvat-o prin ghicire inteligentă în precedentul

secț iune, dar doar în cazul în care 'n' este o putere de 2

33
 1
T(n) =
3T(n/2) + n

Înlocuim 'n' cu 2i.

Acest lucru se realizează prin introducerea unei noi recurenț e teu, definit prin teu= T(2eu)
* Această transformare este utilă deoarece n/2 devine (2eu)/2 = 2i-1
* Cu alte cuvinte, recurenț a noastră originală în care T(n) este definită ca o funcț ie de
T(n/2) a dat naș tere uneia în care teueste definit ca o funcț ie de ti-1, precis
tipul de recurenț ă pe care am învăț at să-l rezolvăm.
teu= T(2eu) = 3T(2i-1) + 2eu
teu= 3ti-1+ 2eu
teu- 3ti-1= 2eu (A)

În acest caz,
b = 2, p(n) = 1, degree = 0

Deci, ecuaț ia caracteristică,

(x - 3)(x - 2) = 0

Rădăcinile sunt, r1 = 3, r2 = 2.

Ecuaț ia generală,
tn= C1r1eu+ C2r2i
sub. r1& r2: tn= 3nC1+ C22n
tn= C13eu+ C22eu

Folosim faptul că, T(2eu) = teu& astfel T(n) = tlogn când n= 2eua obț ine
T(n) = C13log n+2 C2. 2log n 2
T(n) = C1. nlog 32+ C2.n [i = logn]
Când 'n' este o putere a lui 2, este suficient să concluzionăm că,

T(n) = O(nlog3'n' este o putere a lui 2

Verifică-ț i progresul

1. Explicaț i cum să analizaț i diferitele structuri de control ale algoritmilor.

2. Scrie o notă despre analiza cazului mediu.
3. Scrie ț i un algoritm recursiv pentru generarea seriei Fibonacci ș i construi ț i-l
relatie de recurenț ă ș i soluț ionaț i.

4. Rezolvă următoarea ecuaț ie de recurenț ă x(n)=x(n-1)+5 pentru n>1 , x(1)=0.

34
 SUMMARY:
Analiza structurilor de control: În cele din urmă, analiza algoritmilor progresează din interior
ieș ire. Determinaț i mai întâi timpul necesar instrucț iunilor individuale, apoi combinaț i
aceste tinte conform sistemelor de control care combină instrucț iunile în
program.
Recursia poate fi folosită pentru calcule repetitive în care fiecare acț iune este exprimată în termeni

rezultatul anterior.
Rezolvarea recurenț elor folosind următorii paș i: Calculează primele valori ale
recidivă. Caută regularitate. Ghiceș te o formă generală potrivită ș i, în final, dovedeș te prin
inducț ia matematică (poate inducț ie constructivă).

1.7 KEYWORDS
1. Simbolurile mari 'oh', Omega ș i Theta ale notării asimptotice.

1.8 RĂSPUNSURI PENTRU A-ȚI VERIFICA PROGRESUL

1. 1.1
2. 1.5
3. 1.7
4. 1.7
1.7 EXERCI ȚII Ș I RĂSPUNSURI LA FINALUL UNITĂ ȚII

3. Scrie ț i o notă despre analiza amortizată.

4. rezolvă ecua ț ia de recuren ț ă x(n)=x(n-1)*n dacă n>0 unde x(0)=1

VEZI
1.6
2. 1.7

1.9SUGGESTED READINGS
1. Introducere în proiectarea ș i analiza algoritmilor de Anany Levitin
2. Analiza ș i proiectarea algoritmilor cu C/C++ - 3rdediț ie de prof. Nandagopalan
3. Analiza ș i proiectarea algoritmilor de Padma Reddy

4. Even, Shimon., "Algoritmi de grafuri", Editura Ș tiinț a Computerelor.

35
 MODULUL-1, UNITATEA 4 CĂUTARE Ș I SORTARE
Structură
1.0 Obiective
1.1 Algoritmi de căutare
Căutare liniară
Căutare binară
1.2 sorting
Sortare prin selec ț ie
Sortare prin inser ț ie
Sortare prin bule
1.3 Summary
1.4 Keywords
1.5 Răspunsuri pentru a- ț i verifica progresul
1.6 Exerci ț ii ș i răspunsuri la sfâr ș itul unită ț ii
1.7 Suggested readings

3.0 OBIECTIVE
La sfârș itul acestei unităț i vei fi capabil să

• Ș tiț i cum să căuta ț i în moduri diferite

•Identifică care tehnică de căutare este mai bună
•Sorta ț i în moduri diferite, de exemplu, sortare prin inser ț ie, sortare prin selec ț ie
Măsurarea performan ț ei tehnicilor de căutare ș i sortare.

3.1 ALGORITMI DE CĂUTARE

Să presupunem că avem un fiș ier secvenț ial ș i dorim să recuperăm un element care se potriveș te
cu cheia 'k', atunci, trebuie să căutăm întregul fiș ier de la început până la sfârș it pentru a
verifică dacă elementul care se potriveș te cu k este prezent în fiș ier sau nu.
Există o serie de algoritmi de căutare complecș i pentru a îndeplini scopul căutării.
Metodele de căutare liniară ș i căutare binară sunt metode relativ simple de
searching.

1.1.1 Căutare secven ț ială: (Căutare liniară)

În această metodă, începem să căutăm de la începutul listei ș i examinăm fiecare
element până la sfârș itul listei. Dacă elementul dorit este găsit, ne oprim din căutare ș i
return the index of that element. If the item is not found and the list is exhausted the
căutarea returnează o valoare zero.

În cel mai rău caz, articolul nu este găsit sau articolul căutat este ultimul (nth) element.
{"text":"Pentru ambele situaț ii, trebuie să examinăm toate cele n elemente ale array-ului, astfel că ordinul de magnitudine"}

36
complexitatea căutării secvenț iale este n. adică, O(n). Timpul de execuț ie pentru aceasta
algoritmul este proporț ional cu n, adică algoritmul se execută în timp liniar.

Algoritmul pentru căutarea secvenț ială este următorul,

Algoritm: căutare secvenț ială

A, vector de n elemente K, element de căutare
j –indicele lui k
i=1
În timp ce(i<=n)
{
dacă(A[i]=k)
{
căutare reuș ită
scrie(k se află la locaț ia i)
ieș i();
}
altfel
i++
dacă sfârș it
în timp ce sfârș it

căutare eș uată
algoritmul se încheie.

1.1.2 Căutare binară:

Metoda de căutare binară este, de asemenea, o metodă relativ simplă. Pentru această metodă este
este necesar să aveț i vectorul într-o ordine alfabetică sau numeric crescătoare. O căutare
pentru un element particular cu X seamănă cu căutarea unui cuvânt în dicț ionar. The
aproximativ mijlocul intrării este localizat ș i valoarea sa cheie este examinată. Dacă valoarea mijlocie este
mai mare decât X, atunci lista este tăiată la (mid-1)thlocaț ie. Acum lista devine
reducere la jumătate din lista originală. Intrarea din mijloc a listei reduse pe stânga este examinată într-un
mod similar. Această procedură este repetată până când articolul este găsit sau lista nu mai are elemente.
elemente. Pe de altă parte, dacă valoarea medie este mai mică decât X, atunci lista este tăiată
la (mid+1)thlocaț ie. Intrarea din mijloc a listei reduse la dreapta este examinată ș i
procedura se continuă până când cheia dorită este găsită sau intervalul de căutare este epuizat.

Algoritmul pentru căutarea binară este după cum urmează,

Algoritm: căutare binară

A, vector de n elemente K, element de căutare
Output :low –index of k
low=1,high=n
În timp ce(low<=high-1)
{
mid=(low+high)/2

37
dacă(k<a[mid])
high=mid
altfel
low=mid
dacă se termină

}
în timp ce sfârș it

dacă(k=A[low])
{
căutare reuș ită
scrie(k este la locaț ia joasă)
ieș ire();
}
altfel
scriere (căutare nereuș ită);
dacă sfârș it;
algoritmul se încheie.

1.2 Sorting

Mai multe algoritmi sunt prezentaț i, inclusiv sortarea prin inserț ie, sortarea shell ș i sortarea rapidă.
Sortarea prin inserț ie este cea mai simplă metodă ș i nu necesită stocare suplimentară.
Sortarea Shell este o simplă modificare care îmbunătăț eș te semnificativ performanț a.

1.2.1 SORTARE_PRIN_SELEC ȚIE

Sortarea prin selecț ie este printre cele mai simple tehnici de sortare ș i funcț ionează foarte bine pentru seturi mici.
fiș iere. În plus, în ciuda evidentei sale „abordări naive”, sortarea prin selecț ie are o destul de
aplicaț ie importantă deoarece fiecare element este de fapt mutat cel mult o dată, sortarea secț ională este o
metoda aleasă pentru sortarea fiș ierelor cu obiecte foarte mari (înregistrări) ș i chei mici.

Iată un exemplu pas cu pas pentru a ilustra algoritmul sortării prin selecț ie utilizând numere:
Array original:
6354927
1-a trecere -> 2 3 5 4 9 6 7 (2 ș i 6 au fost schimbate)
2nd pass -> 2 3 4 5 9 6 7 (4 and 5 were swapped)
a treia trecere -> 2 3 4 5 6 9 7 (6 ș i 9 au fost schimbate)
a 4-a trecere -> 2 3 4 5 6 7 9 (7 ș i 9 au fost interschimbate)
A cincea trecere -> 2 3 4 5 6 7 9 (fără schimbare)
al 6-lea pas -> 2 3 4 5 6 7 9 (fără schimb)

38
Notă: Au fost 7 chei în listă ș i, prin urmare, au fost necesare 6 treceri. Cu toate acestea, doar 4
schimburile au avut loc.

Algoritm : Sortare prin selecț ie

pentru i← 1 ton-1 fă
minj←i;
minx← A[i]
pentru j ← i + 1 până la n face
Dacă A[j] < min x atunci
minj←j
minx← A[j]
A[minj] ← A[i]
A[i] ← minx

Cea mai proastă situaț ie apare dacă tabloul este deja sortat în ordine descrescătoare. Totuș i,
timpul necesar algoritmului de sortare prin selecț ie nu este foarte sensibil la ordinea originală a
array-ul care trebuie sortat: testul "ifA[j] < min x" este executat exact acelaș i număr de
timpuri în fiecare caz. Variaț ia în timp este doar din cauza numărului de ori în care apare "atunci"
partea (adică, minj←j; minx←A[j] a acestui test sunt executate.

Sortarea prin selecț ie îș i petrece cea mai mare parte a timpului încercând să găsească elementul minim în
partea „nesortată” a array-ului. Arată clar similaritatea dintre sortarea prin selecț ie ș i
Sortarea prin bule. Sortarea prin bule "selectează" elementele maxime rămase la fiecare etapă, dar
iască ceva efort pentru a impune o ordine părț ii "nesortate" a tabloului. Sortarea prin selecț ie este
cvadratic atât în cel mai rău, cât ș i în cazul mediu, ș i nu necesită memorie suplimentară.

39
Pentru fiecare ifrom 1 ton - 1, există un schimb ș i n-comparări, deci există un total
exchange-uri ofn-1 ș i (n-1) + (n-2) + . . . + 2 + 1 =n(n-1)/2 comparaț ii. Aceste
observaț iile sunt valabile indiferent de datele de intrare. În cel mai rău caz, aceasta ar putea fi
cadratic, dar în cazul mediu, această cantitate este O(nlogn).

1.2.2 Sortare prin inser ț ie

Dacă primele câteva obiecte sunt deja sortate, un obiect nesortat poate fi inserat în cele sortate
setat în locul corespunzător. Acesta se numeș te sortare prin inserț ie. Un algoritm consideră elementele unul
la un moment dat, introducând fiecare în locul său potrivit printre cei deja consideraț i (păstrând
le sortate). Sortarea prin inserț ie este un exemplu de algoritm incremental; construieș te
secvenț ă sortată, un număr deodată. Acesta este poate cel mai simplu exemplu al
tehnica de inserț ie incrementală, unde construim o structură complicată pe n elemente prin
mai întâi construind-o pe n − 1 articole ș i apoi făcând modificările necesare pentru a remedia lucrurile
adăugarea ultimului element. Secvenț ele date sunt de obicei stocate în tableau. De asemenea, ne referim la
numere ca chei. Împreună cu fiecare cheie poate exista informaț ii suplimentare, cunoscute ca sateliț i
date. [Reț ineț i că "datele satelit" nu provin neapărat din satelit!]

Algoritm: Sortare prin inserare

Funcț ionează la fel cum ai sorta o mână de cărț i de joc:

1. Începem cu o mână stângă goală [armat sortat] ș i căr ț ile cu fa ț a în jos pe

tabel [masă nesortată].
2. Apoi, îndepărtează o carte [cheie] de fiecare dată de pe masă [tablou nesortat] ș i insereaz-o
în poziț ia corectă din mâna stângă [vector sortat].
3. Pentru a găsi pozi ț ia corectă pentru card, o comparăm cu fiecare dintre carduri
deja în mână, de la dreapta la stânga.

Reț ineț i că, în orice moment, cărț ile ț inute în mâna stângă sunt sortate, iar aceste cărț i au fost
iniț ial cărț ile de sus ale grămezii de pe masă.

Pseudo cod

Folosim o procedură INSERTION_SORT. Aceasta primeș te ca parametrii un array A[1..n] ș i

lungimea array-ului. Array-ul A este sortat la faț a locului: numerele sunt reorganizate în interior.
array-ul, cu un număr maxim constant în afara array-ului în orice moment.

SORTARE_PENTRU_INSERARE (A)

40
 [Link] ← 2LAlength[A]FACI

2. cheia ←A[j]

3. {Pune A[j] în secven ț a sortată A[1 . .j− 1]}

4.i←j− 1
[Link] timp i > 0 si A[i] > cheie
6. DOA[i+1] ←A[i]
7. i←i− 1
8.A[i+ 1] ← cheie

Figura următoare (din CLRS) arată operaț ia de SORTARE PRIN INSERARE pe

array-ul A= (5, 2, 4, 6, 1, 3). Fiecare parte arată ce se întâmplă pentru o anumită iteraț ie
cu valoarea [Link] cardul "curent" fiind introdus în mână.

Citeș te figura linie cu linie. Elementele din stânga lui A[j] care sunt mai mari decât A[j] se mută
o poziț ie spre dreapta, iar A[j] se mută în poziț ia evacuată.

Analiză

Întrucât timpul de execuț ie al unui algoritm pe o anumită intrare este numărul de paș i
executat, trebuie să definim "pas" independent de maș ină. Spunem că o afirmaț ie care
îi iaeupaș ii de executat ș i timpii executaț i contribuieeuîn timpul total de rulare al
algoritmul. Pentru a calcula timpul de execuț ie, T(n), sumăm produsele costului ș i
coloana timp [vezi CLRS pagina 26]. Adică, timpul de execuț ie al algoritmului este suma
timpilor de execuț ie pentru fiecare declaraț ie executată. Aș adar, avem

T(n) = c1n+c2(n− 1) + 0 (n− 1) +c4(n− 1) +c5∑2 ≤j≤ n(tj)

+c6∑2 ≤j≤ n(tj− 1) +c7∑2 ≤j≤ n(tj- 1) +c8(n - 1)

În ecuaț ia de mai sus, am presupus căjfii numărul de ori în care bucla while (în linia
5) este executat pentru acel vârf de j. Observaț i că valoarea lui j variază de la 2 la (n− 1). Avem

41
 T(n) = c1n+c2(n− 1) +c4(n− 1) +c5∑2 ≤j≤ n(tj) + c6∑2 ≤j≤ n(tj− 1)
+c7∑2 ≤j≤ n(tj− 1) +c8(n− 1) Ecuaț ia (1)

Caz ideal

Cel mai bun caz apare dacă array-ul este deja sortat. Pentru fiecare j = 2, 3, ..., n, găsim
thatA[i] este mai mic sau egal cu cheia când i are valoarea iniț ială de (j− 1). Cu alte cuvinte,
când i=j−1, găseș te întotdeauna cheia A[i] la prima rulare a buclei WHILE.

Prin urmare,j= 1 pentru j= 2, 3, ..., n iar timpul de execuț ie în cel mai bun caz poate fi calculat folosind
ecuaț ia (1) astfel:

T(n) = c1n+c2(n− 1) +c4(n− 1) +c5∑2 ≤j≤ n(1) +c6∑2 ≤j≤ n(1 − 1) +c7∑2 ≤j≤ n(1
− 1) +c8(n− 1)

T(n) =c1n+c2(n− 1) +c4(n− 1) +c5(n− 1) +c8(n− 1)

T(n) =(c1+c2+c4+c5+c8)n+ (c2+c4+c5+c8)

Acest timp de execuț ie poate fi exprimat ca an + b pentru constantele a ș i b care depind de

declaraț ie costuriiPrin urmare, T(n) este o funcț ie liniară de n.

Linia de bază aici este că bucla while de pe linia 5 a fost executată o singură dată pentru fiecare j. Aceasta
ce se întâmplă dacă arrayA este deja sortat.

T(n) = an + b = O(n)

Este o funcț ie liniară de n.

Worst-Case

Cel mai rău caz apare dacă tabloul este sortat în ordine inversă, adică în ordine descrescătoare. În
în ordinea inversă, întotdeauna descoperim că A[i] este mai mare decât cheia în testul buclei while.
Aș adar, trebuie să comparăm fiecare element A[j] cu fiecare element din întregul sortat
subarrayA[1 ..j− 1] ș i sotj=jforj= 2, 3, ...,n. Echivalent, putem spune că, deoarece
bucle while se încheie deoarece ajunge la 0, există un test suplimentar după (j− 1) teste.
Prin urmare,j=jforj= 2, 3, ..., n iar timpul de execuț ie în cel mai prost caz poate fi calculat folosind
ecuaț ia (1) după cum urmează:

T(n) = c1n+c2(n− 1) +c4(n− 1) +c5∑2 ≤j≤ n(j) +c6∑2 ≤j≤ n(j− 1)

+c7∑2 ≤j ≤ n(j− 1) +c8(n− 1)

Ș i folosind sumele din CLRS la pagina 27, avem

42
 T(n) = c1n+c2(n− 1) +c4(n− 1) +c5∑2 ≤j≤ n[n(n+1)/2 + 1]
+c6∑2 ≤j≤ n[n(n− 1)/2] +c7∑2 ≤j≤ n [n(n− 1)/2] +c8(n− 1)

T(n) = (c5/2 +c6/2 +c7/2)n2+ (c1 +c2+c4+c5/2 −c6/2 −c7/2

+c8)n− (c2+c4+c5+c8)

Timpul de execuț ie poate fi exprimat ca (an2+bn+c) pentru constantele a, b ș i c care din nou
depinde de declaraț ia costsceuPrin urmare, T(n) este o funcț ie quadratică de n.

Aici, ideea principală este că cazul cel mai rău se produce atunci când linia 5 este executată de j ori pentru fiecare j.
Aceasta se poate întâmpla dacă arrayA începe în ordine inversă

T(n) = an2+bn+c= O(n2)

Este o funcț ie quadratică de n.

Graficul arată atunci2complexitatea sortării prin inserț ie.

Analiza cazului cel mai rău ș i a cazului mediu

De obicei ne concentrăm pe găsirea timpului de rulare în cel mai rău caz: cel mai lung timp de rulare
pentru orice dimensiune a intrării sizen. Motivele pentru această alegere sunt următoarele:

Timpul de execu ț ie în cel mai rău caz oferă o limită superioară garantată asupra timpului de execu ț ie

pentru orice input. Adică, limita superioară ne oferă o garanț ie că algoritmul va

nu lua niciodată mai mult timp.
•Pentru unele algoritmi, cel mai rău caz apare des. De exemplu, atunci când căutăm,
cel mai rău caz apare adesea când elementul căutat nu este prezent, ș i
cercetările pentru articolele absente pot fi frecvente.
De ce să nu analizăm cazul mediu? Pentru că acesta este adesea la fel de rău ca cel mai rău.
caz.

Exemplu: Să presupunem că alegem aleatoriu numere ca input pentru inserare

sorta.

43
În medie, cheia în A[j] este mai mică decât jumătate din elementele în A[1 ..j− 1] ș i este mai mare
decât cealaltă jumătate. Aceasta implică că, în medie, bucla while trebuie să caute până la jumătate.
subvectorul sortat A[1 ..j− 1] pentru a decide unde să aș eze cheia. Aceasta înseamnă căj=j/2.

Deș i timpul de execuț ie în medie este aproximativ jumătate din timpul de execuț ie în cel mai rău caz
timpul, este încă o funcț ie cuadratică de n.

Stabilitate

Deoarece mai multe chei cu aceeaș i valoare sunt plasate în array-ul sortat în aceeaș i ordine
că apar în array-ul de intrare, sortarea prin inserț ie este stabilă.

Memorie suplimentară

Acest algoritm nu necesită memorie suplimentară.

Pentru sortarea prin inser ț ie, spunem că timpul de execu ț ie în cel mai rău caz este θ( n2), ș i cel mai bun caz
timpul de execuț ie este θ(n).
Sortarea prin inser ț ie nu folose ș te memorie suplimentară, sortează în loc.

Timpul de sortare prin inser ț ie depinde de ordinea originală a unui input. Acesta durează
timp în Ω(n ) în cel mai rău scenariu, în ciuda faptului că un timp în ordinea nis
2

suficient pentru a rezolva instanț e mari în care obiectele sunt deja sortate.

1.2.2 Sortare prin bule

Sortarea prin bule, cunoscută ș i sub denumirea de sortare prin scufundare, este o metodă simplăalgoritm de sortarecare funcț ionează prin
parcurgând în mod repetat lista care trebuie sortată, comparând fiecare pereche de elemente adiacente
ș ischimbaredacă sunt în ordine greș ită. Trecea prin listă este repetată
până când nu mai sunt necesare schimbări, ceea ce indică faptul că lista este sortată. Algoritmul îș i obț ine
numele provine din modul în care elementele mai mici "bulează" la suprafaț a listei. Pentru că foloseș te doar
comparatii pentru a opera pe elemente, este unsortare prin comparare.

Să luăm tabloul de numere "5 1 4 2 8", ș i să sortăm tabloul de la cel mai mic număr la
cea mai mare număr utilizând algoritmul de sortare prin bulă. În fiecare pas, elementele scrise cu **subliniere**
fiind comparat.
Prima trecere:
(5 14 2 8 ) (1 54 2 8), Aici, algoritmul compară primele două elemente ș i le schimbă.
ei.
( 15 42 8 ) (14 52 8), Schimbă deoarece 5 > 4
( 1 45 28 ) ( 1 42 58 ), Schimbă deoarece 5 > 2
( 1 4 25 8) (1 4 25 8), Acum, deoarece aceste elemente sunt deja în ordine (8 > 5),
algoritmul nu le schimbă.
A doua trecere:
(1 42 5 8 ) (1 42 5 8 )

44
( 14 25 8 ) ( 12 45 8 ), Schimbă deoarece 4 > 2
( 1 24 58 ) ( 1 24 58 )
( 1 2 45 8) ( 1 2 45 8)
Acum, array-ul este deja sortat, dar algoritmul nostru nu ș tie dacă este complet.
algoritmul are nevoie de o singură trecere fără nicio schimbare pentru a ș ti că este sortat.
Al treilea pas:
(1 24 5 8) (1 24 5 8)
( 12 45 8 ) ( 12 45 8 )
( 1 24 58 ) ( 1 24 58 )
( 1 2 45 8) ( 1 2 45 8)
În cele din urmă, array-ul este sortat, iar algoritmul poate termina.

Algorithm :bubbleSort( A : list of sortable items )

n = lungimea(A)
pentru j 1 până la n-1 face
pentru i ← 0 la n-j-1 face
dacă A[i] >= A[i+1] atunci
schimbă(A[i], A[i+1])
sfârș it dacă
sfârș it pentru
sfârș it pentru

Analiză :
Complexitatea timpului t(n)=
n -1 n − j -1 n −1 n -1

∑ ∑1 = ∑n − j −1 − 0 +1 = ∑
j =1 eu
=0 j =1 =1
n − j = (n −1) + (n − 2) + ... + 3 + 2 +1 = n(n+!)/2
j

Deci, complexitatea temporală a sortării prin bule = θ(n2).

Verifică-ț i progresul

1. Write an algorithm for sequential search and trace it for the input { 1,9,2,4,6,8}.
2. Scrie un algoritm pentru sortarea prin bule ș i sortarea prin selecț ie. Aplică-l pentru următorul set de

numere { 5,8,3, 2,1,9}. Găsiț i complexitatea temporală a tuturor acestor algoritmi.

3. Scrie un algoritm pentru sortarea prin inserț ie Aplică-l pentru următorul set de numere
Găsiț i complexitatea temporală.

1.3 SUMMARY:

45
 Sortare: Este procesul de aranjare a elementelor fie în ordine crescătoare, fie în ordine descrescătoare.

mod. Exemplu sortare prin inserț ie, sortare prin bulă, sortare prin selecț ie etc.

Căutarea: este un proces de găsire a elementului dintr-un set de n elemente. Exemplu

linear search, binary search.

1.9 KEYWORDS
Căutarea binară: căutarea unui element prin tehnica divizării ș i cuceririi.

1.10 RĂSPUNSURI PENTRU A VERIFICA PROGRESUL TĂU

1. 1
2. 1.2.1 & 1.2.3
3. 1.2.2
1.7 EXERCI ȚII Ș I RĂSPUNSURI LA SFÂR Ș ITUL UNITĂ ȚII

5. Aplică algoritmul de sortare prin inser ț ie pentru mul ț imea A L G O R I T H M pentru a o sorta în

ordine crescătoare.
6. Aplică Algoritmul de căutare binară pentru a căuta 'G' din setul A B C F H Z X.

VEZI
1. 1.1
2. 1.2

1.10 LECTURI SUGERATE

1. Introducere în designul ș i analiza algoritmilor de Anany Levitin
2. Analiza ș i proiectarea algoritmilor cu C/C++ - 3rdediț ie de Prof. Nandagopalan
3. Analiza ș i proiectarea algoritmilor de către Padma Reddy

4. Even, Shimon., "Algoritmi Grafici", Editura Ș tiinț a Calculatoarelor.

46
 MODUL-3, UNITATEA 2: ÎMPARTĂ Ș I CONQUISTĂ

Structură
2.0 Obiective
1.1 Introducere
1.2 Structura generală a strategiilor de împărț ire ș i cucerire

1.3 Aplicaț ii pentru găsirea minimului ș i maximumului

1.4 Ecuaț ii de recurenț ă

1.6 Rezumat
1.7 Cuvinte cheie

1.8 Răspunsuri pentru a-ț i verifica progresul

1.9 Exerciț ii ș i răspunsuri la sfârș itul unităț ii

1.10 Lecturi sugerate

4.0 OBIECTIVE
La sfârș itul acestei unităț i vei fi capabil să
•Găse ș te cum să aplici metoda divide et impera

•Găsi ț i complexitatea temporală a algoritmilor de tip divizare ș i cucerire

•Identificarea rela ț iilor de recurente pentru algoritm

• Ș tiț i cum să rezolva ț i ecua ț iile de recuren ț ă

4.1 INTRODUCERE

Metoda de proiectare a algoritmului prin împărț ire ș i stăpânire este cea mai cunoscută metodă de
Rezolvarea unei probleme. Acum, să vedem "Ce este tehnica divide ș i cucereș te? Ce este
plan general folosind care aceste algoritmi funcț ionează?

Definiț ie: Divide ș i cucereș te este o tehnică de sus în jos pentru proiectarea algoritmilor care
constă în împărț irea problemei în subprobleme mai mici, sperând că soluț iile acestora
sub problemele sunt mai uș or de găsit. Soluț iile tuturor problemelor mai mici sunt apoi combinate
pentru a obț ine o soluț ie pentru problema originală.
Tehnica de divizare ș i cucerire pentru rezolvarea unei probleme implică trei paș i
Fiecare nivel al recursiei:
•.Împăr ț iț i: Problema este împăr ț ită în mai multe subprobleme

47
 Conquista: Subproblemele sunt cucerite prin rezolvarea lor recursiv.
sub Problemele sunt mai mici ca dimensiune, problema poate fi rezolvată folosind o abordare directă
metodă
Solu ț iile subproblemelor sunt combinate pentru a ob ț ine solu ț ia pentru
problema mai mare.

Teorema Master pentru a rezolva rela ț ia de recuren ț ă

Teorema maestrului se referă la relaț ii de recurenț ă de forma:

În aplicaț ia analizei unui algoritm recursive, constantele ș i funcț ia

îș i asumă următoarea semnificaț ie:

. nis este dimensiunea problemei.

. ais numărul subproblemelor din recursie.
. n/bis dimensiunea fiecărei subprobleme. (Aici se presupune că toate
subproblemele sunt în esenț ă de aceeaș i dimensiune.)

. f(n) este costul muncii efectuate în afara apelurilor recursive, care

include costul împărț irii problemei ș i costul combinării soluț iilor la
subproblemele.

Este posibil să se determine o limită asimptotică strânsă în aceste trei cazuri:

T(n)= { θ(nd) dacă a < d
b

θ(ndlogn) dacă a=bd

θ(nd logn) dacă a>bd}
Notă: Aici, d este puterea lui n în f(n).

4.2 MAXIMUM AND MINIMUM

Să luăm în considerare o altă problemă simplă care poate fi rezolvată prin împăr ț ire ș i...
tehnica de cucerire.

Problema este de a găsi elementele maxime ș i minime într-un set de 'n' elemente.

În analizarea complexită ț ii temporale a acestui algoritm, ne concentrăm din nou pe

numărul comparaț iilor de elemente.

48
•Mai important, atunci când elementele din a[1:n] sunt polinoame, vectori, foarte
numere mari, sau ș iruri de caractere, costul unei comparaț ii de elemente este mult
mai mare decât costul celorlalte operaț iuni.

Prin urmare, timpul este determinat în principal de costul total al comparării elementelor.

1. Algoritm dreapta MaxMin(a,n,max,min)

2. // setează max la maximul ș i min la minimul din a[1:n]
3. {
4. max:=min:=a[1];
5. pentru I:=2 la n fac
6. {
7. dacă(a[I]>max) atunci max:=a[I];
8. dacă(a[I]<min) atunci min:=a[I];
9. }
10. }

Algoritm: Maximum ș i Minimum Direct

•Straight MaxMin necesită 2(n-1) compara ț ii de elemente în cel mai bun, mediu ș i cel mai rău caz
cazuri.

O îmbunătă ț ire imediată este posibilă prin realizarea că compara ț ia a[I]<min

este necesar doar când a[I]>max este fals.

•A ș adar, putem înlocui con ț inutul buclei for cu,

Dacă(a[I]>max) atunci max:=a[I];
Altfel dacă (a[I]<min) atunci min:=a[I];

Cazul cel mai bun apare acum când elementele sunt în ordine crescătoare.
Numărul de comparaț ii ale elementelor este (n-1).

Cazul cel mai rău apare când elementele sunt în ordine descrescătoare.
Numărul de comparaț ii ale elementelor este 2(n-1)

Numărul mediu de comparări de elemente este mai mic decât 2(n-1)

•În medie, un a[I] este > decât maximul jumătate din timp, ș i astfel, numărul mediu de
comparatia este 3n/2-1.

•A divide- and conquer algorithm for this problem would proceed as follows:

Să notăm P=(n, a[I], …… ,a[j]) o instanț ă aleatorie a problemei.

Aici 'n' este numărul de elemente din lista (a[I],….,a[j]) ș i suntem interesaț i de

49
 găsirea valorii maxime ș i minime din listă.

Dacă lista are mai mult de 2 elemente, P trebuie să fie împăr ț it în instan ț e mai mici.

•De exemplu, am putea împăr ț i 'P' în cele 2 instan ț e, P1=([n/2],a[1],

……..a[n/2]) & P2= (n-[n/2],a[[n/2]+1],…..,a[n])

După ce am împăr ț it 'P' în 2 subprobleme mai mici, le putem rezolva prin

invocând recursiv acelaș i algoritm de împărț ire ș i cucerire.

Algoritm: Găsirea recursivă a maximului ș i minimului folosind împărț irea ș i

tehnica de cucerire

1. Algoritm MaxMin (I,j,max,min)

2. //a[1:n] is a global array, parameters I & j
3. //sunt întregi, 1<=I<=j<=[Link] este de a
4. //seta ț i max ș i min la cea mai mare ș i cea mai mică valoare
5. //în a[I:j], respectiv.
6. {
7. dacă(I=j) atunci max:= min:= a[I];
8. altfel dacă (I=j-1) atunci // Un alt caz de mic(p)
9. {
10. dacă (a[I]<a[j]) atunci
11. {
12. max:=a[j];
13. min:=a[I];
14. }
15. altfel
16. {
17. max:=a[I];
18. min:=a[j];
19. }
20. }
21. altfel
22.
23. // dacă P nu este mic, împarte P în subprobleme.
24. // găseș te unde să împărț i setulmid:=[(I+j)/2];
25. //rezolvă subproblemele
26. MaxMin(I,mid,[Link]);
27. MaxMin(mid+1,j,max1,min1);
28. //combină soluț ia
29. dacă (max<max1) atunci max=max1;
30. dacă(min>min1) atunci min = min1;
31. }
32. }

50
 •Procedura este ini ț ial invocată prin afirma ț ia,
MaxMin(1,n,x,y)
•Să presupunem că simulăm MaxMin pe următoarele 9 elemente

A: [1] [2] [3] [4] [5] [6] [7] [8] [9]

22 13 -5 -8 15 60 17 31 47
O modalitate bună de a urmări apelurile recursive este să construie ș ti un arbore prin adăugarea unui nod
de fiecare dată când se face un nou apel.
•Pentru acest algoritm, fiecare nod are 4 elemente de informa ț ie: I, j, max ș i imin.
•Examinând figura: vedem că nodul rădăcină con ț ine 1 ș i 9 ca valori pentru I ș i j
corespunzător apelului iniț ial către MaxMin.
Această execu ț ie produce 2 apeluri noi la MaxMin, unde I ș i j au valorile 1, 5
& 6, 9 respectiv & astfel împart setul în 2 sub-seturi de aproximativ aceeaș i
dimensiune.
Din copac, putem vedea imediat că adâncimea maximă a recursiunii este 4.
(inclusiv 1stapel)
Numerele incluse în col ț ul din stânga sus al fiecărui nod reprezintă ordinea în care
max ș i min sunt atribuite valori.

Numărul de elemente Comparare:

•Dacă T(n) reprezintă acest număr, atunci rela ț ia de recuren ț ă rezultată este

T(n)={ T([n/2]+T[n/2]+2 n>2

1 DACA n=2
0 DACĂ n=1

Când 'n' este o putere a lui 2, n=2^k pentru un anumit întreg pozitiv 'k', atunci
T(n) = 2T(n/2) + 2
= 2(2T(n/4)+2)+2
= 4T(n/4)+4+2
*
*
= 2^k-1T(2)+
= 2^k-1+2^k-2
= 2^k/2+2^k-2
= n/2+n-2
(n+2n)/2)-2

T(n)=(3n/2)-2

*Reț ineț i că (3n/3)-3 este media cea mai bună ș i numărul de comparaț ii în cel mai rău caz când ‘n’
este o putere a lui 2.

51
4.3 REZOLVAREA ECUAȚIILOR DE RECURENȚĂ

Rezolvăm frecvent ecuaț ii de recurenț ă în analiza complexităț ii algoritmilor, circuitelor ș i

alte astfel de cazuri.

1.3.1 Ecuaț ia de recurenț ă omogenă

O ecuaț ie de recurenț ă omogenă este scrisă ca:
a0tn+ a1tn-1 + . . . . +aktn-k = 0.

Soluț ie tehnică:
Pasul 1: Stabiliț i o ecuaț ie caracteristică corespunzătoare:
a0xn+ a1x(n-1) + …. + akx(n-k) = 0,
x(n-k) [a0xk+ a1x(k-1) + … +ak] = 0,

a0xk+ a1xk-1 + . . . . + ak = 0 [ pentru x =/= 0]

Pasul 2: Rezolvaț i ecuaț ia caracteristică ca pe o ecuaț ie polinomială. Să zicem că rădăcinile reale sunt
r1, r2, . . . . ,rk. Observa ț i, există k solu ț ii pentru ecua ț ia polinomială de ordin k.

Pasul 3: Soluț ia generală pentru ecuaț ia de recurenț ă originală este:

tn=∑i=1ceuk reun

Pasul 4: Folosind condiț iile iniț iale (dacă sunt disponibile), rezolvaț i pentru coeficienț ii din ecuaț ia de mai sus.
pentru a găsi soluț ia particulară.
Exemplu 1:
Rezolvarea ecuaț iei de recurenț ă tn- 3tn-1- 4tn-2= 0, pentru n >= 2. {Initial condition:
t0=0, t1=1}

Ecuaț ia caracteristică: xn- 3x(n-1) - 4x(n-2) = 0,

Sau, x(n-2) [x2–3x –4] = 0,
Sau, x2- 3x - 4 = 0
Sau, x2+ x - 4x - 4 = 0,
Or, x(x+1) –4(x+1) = 0,
Sau, (x+1)(x-4) = 0
Prin urmare, rădăcinile sunt, x = -1, 4.

Aș adar, soluț ia generală a ecuaț iei de recurenț ă date este:

tn= c1*(-1)n+ c2(4n)

Foloseș te t0= c1+ c2= 0 ș i t1= -c1+ 4c21. [Notă, avem nevoie de două condiț ii iniț iale pentru două
coeficienț i.

Sove pentru c1ș

i c2,
c1= -(1/5), c2 = (1/5).

52
Aș adar, soluț ia particulară este:
tn(1/5)[4n– (-1)n] = Θ(4n)

1.3.2 Ecuaț ia de recurenț ă inhomogenă

a0tn+ a1tn-1 + . . . . +aktn-k = bnp(n), unde b este un

constantă ș i p(n) este un polinom de ordin n.

Soluț ie tehnică:

Pasul 0: Homogenizaț i ecuaț ia dată într-o recurentă omogenă echivalentă

forma ecuaț iei.

Pasul 1 până la 3 (sau 4) sunt aceleaș i ca în cazul rezolvării recurenț ei omogene

ecuaț ie.

Exemplu 2:

tn- 2tn-1= 3n. [Observa ț i, acesta este un caz special cu p(n) = 1, polinom de ordinul 0, ș i
nu există o condiț ie iniț ială - aș a că obț inem doar soluț ia generală.

Transformă cu n->n+1:
tn+1 - 2tn= 3n+1 Ecuaț ia(1).

Înmulț iț i ecuaț ia originală cu 3 pe ambele părț i:

3tn- 6tn-1 = 3n+1 Eqn(2).

Scade ecuaț ia (2) din ecuaț ia (1):

tn+1 - 5tn+ 6tn-1 = 0, aceasta este o ecuaț ie recursivă omogenă care este echivalentă cu
dată ecuaț ia inhomogenă.

Ecuaț ia caracteristică: x2- 5 x + 6 = 0.

Care este (x-2)(x-3) = 0.

Deci, rădăcinile sunt x = 2, 3.

Soluț ia generală a ecuaț iei de recurenț ă date este:

tn= c1(2n) + c2(3n) = Θ(3n)

Homogenizarea poate necesita mai mulț i paș i.

Exemplul 3:

tn- 2tn-1 = n

53
Deci, tn+1 -2tn= n+1
Scăzând prima (dată) ecuaț ie din cea de-a doua ecuaț ie,
tn+1 - 3tn+ 2tn-1 = 1
Încă nu este o ecuaț ie omogenă. A doua etapă a omogenizării,
tn+2 – 3tn+1 + 2tn= 1
Scade încă odată,
tn+2 – 4tn+1 + 5tn- 2tn-1 = 0

Acum este o ecuaț ie de recurenț ă omogenă ș i o poate rezolva în modul obiș nuit.

1.3.3 Rezolvarea ecua ț iilor de recuren ț ă folosind teorema Maestrului

O clasă specială de ecuaț ii de recurenț ă care este întâlnită frecvent în algoritmi
analize
T(n) = aT(n/b) + cneu, pentru un anumit întreg constant i, ș i constantele coeficientelor a ș i c.
Trei cazuri:
a = beu, solu ț ia este T(n) = O(neujurnalbn);

a > beu, solu ț ia este T(n) = O(nlog_b a);

a < beu, solu ț ia este T(n) = O(neu);

Exemplu - Înmulț irea matricilor (algoritmul lui Strassen)

Consideraț i problema calculării produsului a două matrice. Adică, având două

matrici, A ș i B, calculează matrice , elementele cărora sunt
date de

Sec ț iunea arată că implementarea directă a ecua ț ieirezultă într-un

timp de execuț ie. În această secț iune, arătăm că utilizarea unei strategii de divizare ș i cucerire rezultă
într-un timp de execuț ie asimptotic uș or mai bun.

Pentru a implementa un algoritm de tip divide-et-impera, trebuie să descompunem problema dată în

mai multe subprobleme care sunt similare cu cea originală. În acest caz, privim fiecare dintre
the matrici ca un matrice, ale cărei elemente sunt submatrici.
Astfel, înmulț irea matricilor originale, poate fi scris ca

54
unde fiecare , și este un matrice.

Din Ecuaț ie înț elegem că submatricele rezultate pot fi calculate astfel:

Aici simbolurile + ș i sunt considerate a însemna adunare ș i înmulț ire (respectiv)

de matrice.

Pentru a calcula originalul matricea înmul ț ită trebuie să fie calculată

opt produse matriciale (împăr ț ire) urmate de patru sume matrice

(conquer). Deoarece adunarea matricelor este unoperaț iune, timpul total de funcț ionare pentru
operaț ia de înmulț ire este dată de recurenț ă:

Reț ineț i că Ecuaț ia este o instanț ă a recurenț ei generale date în Ecuaț ia . În acest
caz, a=8, b=2, ș i k=2. Putem obț ine soluț ia direct din Ecuaț ie.
Deoarece , timpul total de execu ț ie este . Dar asta nu
mai bun decât algoritmul original, direct!

Din fericire, se dovedeș te că una dintre cele opt înmulț iri de matrice este redundantă.
Consideraț i următoarea serie de ș apte matrices:

55
Fiecare ecuaț ie de mai sus are doar o înmulț ire. Zece adunări ș i ș apte înmulț iri.
sunt necesare pentru a calcula prin. Dat prin , putem calcula
elementele matricei produsului Cas sunt următoarele:

În total, această abordare necesită ș apte înmulț iri de matrice ș i

18 adăugiri. Prin urmare, timpul de execuț ie în cel mai rău caz este dat de următoarele
recurrence:

Ca mai sus, Ecuaț ie este o instanț ă a recurenț ei generale date în Ecuaț ia.
obț inem soluț ia direct din Ecuaț ie. În acest caz, a=7, b=2 ș i k=2.
Prin urmare, ș i timpul total de rulare este (Foloseș te Teorema Master)

Notă Prin urmare, timpul de execuț ie al metodei divide-and-conquer

strategia de înmulț ire a matricelor este care este mai bun (asymptotic) decât
abordare directă.

Exemplu 2 : Rezolvă următoarea ecuaț ie de recurenț ă t(n)=3t(n/2)+1 unde t(1)=1

Sol: Este de forma:

56
Unde a=3, b=2 ș i f(n)=nd= 10

Prin urmare d=0

Aici a>bdPrin urmare, soluț ia este o(nlog3 2 )

T(n)=o(nlog32 ) = o(3logn 2)

Verifică-ț i progresul
1. Explicaț i procesul de împărț ire ș i cucerire.
2. Folosind abordarea divide ș i cucereș te, scrieț i un algoritm pentru a găsi minimul ș i
maximum în tablou.
3. Masteratul de stat

1.4 SUMMARY
Împarte ș i cucereș te: este o tehnică generală de proiectare a algoritmilor care rezolvă o problemă.

instanț ă împărț indu-l în mai multe instanț e mai mici (ideal de dimensiuni egale), rezolvând fiecare
a lor recursiv, ș i apoi combinând soluț iile lor pentru a obț ine o soluț ie pentru original
instanț a problemei. Multe algoritmi eficienț i se bazează pe această tehnică, deș i
poate fi atât inaplicabil, cât ș i inferior la soluț ii algoritmice mai simple.
Eficien ț a temporală T(n) a multor tehnici de împăr ț ire ș i cucerire satisface ecua ț ia
T(n)=aT(n/b)+f(n). Teorema Maestrului stabile ș te ordinea de cre ș tere a acestuia.
soluț ia ecuaț iei.
Algoritmul lui Strassen necesită doar ș apte înmulț iri pentru a înmulț i două matrice 2×2, dar
cere mai multe adăugiri decât algoritmul bazat pe definiț ie. Prin explorarea divizării ș i
2.807
tehnica Conquer, acest algoritm poate înmul ț i două matrice n-la-n în aproximativ n
înmulț iri.

Răspunsuri: VEZI

1. 1.1
2. 1.2
3. 1.1

57
 1.11 KEYWORDS
1 θ – Notarea asimptotică
Teorema lui Master - pentru a rezolva relaț iile de recurenț ă ale divizării ș i cuceririi de specific,
formular.
3. Forme omogene ș i neomogene - acestea sunt forme ale ecuaț iilor de recurenț ă.

1.12 RĂSPUNSURI PENTRU A-ȚI VERIFICA PROGRESUL

1. 1.2
2. 1.2
3. 1.3
4. 1.4
1.7 EXERCI ȚII Ș I RĂSPUNSURI LA SFÂR Ș ITUL UNITĂ ȚII

7. Înmul ț eș te două matrici a={1,2,3,4} ș i b={1,2,3,4} folosind algoritmul Strassen.

[Link] ț i eficien ț a unui algoritm pentru găsirea minimului ș i maximului în
array-ul.
9. Discuta ț i diferitele metode de rezolvare a ecua ț iilor de recuren ț ă ș i timpul
complexităț i.
Answers: SEE
1. 1.3
2. 1.2
3. 1.3
1.11 LECTURI RECOMANDATE
1. Introducere în proiectarea ș i analiza algoritmilor de Anany Levitin
2. Analiza ș i proiectarea algoritmilor cu C/C++ - 3rdediț ie de Prof. Nandagopalan
3. Analiza ș i proiectarea algoritmilor de Padma Reddy

58
 MODUL-3, UNITATEA 2: SORTARE

Structură
3.0 Obiective
1.1 Introducere
1.2 Sortare prin îmbinare

1.3 Sortare rapidă

1.4 Căutare binară

1.6 Rezumat
1.7 Cuvinte cheie

1.8 Răspunsuri pentru a-ț i verifica progresul

1.9 Exerciț ii ș i răspunsuri de sfârș it de unitate

1.10 Suggested readings

5.0 OBIECTIVE
La sfârș itul acestei unităț i vei fi capabil să
•Identificarea diferitelor tipuri de sortare

Găsi ț i complexitatea în timp a unui algoritm de sortare

•Cazuri diferite ale algoritmului (cazul cel mai rău, cazul cel mai bun, cazul mediu)

•Identifică care sortare este mai bună ș i de ce?

•Identifica ț i de ce căutarea binară ș i complexitatea sa de timp

5.1 INTRODUCTION

59
Îninformaticăalgoritmul de sortare este unalgoritmcare pune elemente de olistăîntr-o
certacomandăCele mai utilizate comenzi sunt ordinea numerică ș iordine lexicografică.
Eficientsortareeste important pentru optimizarea utilizării altor algoritmi (cum ar ficaută
ș ifuzionarealgoritmi) care necesită liste sortate pentru a funcț iona corect; Mai formal,
ieș irea trebuie să satisfacă două condiț ii:

1. Ie ș irea este în ordinea non-descrescătoare (fiecare element nu este mai mic decât
elementul precedent conform dorinț eicomandă totală);
2. Ie ș irea este opermutare, sau reorganizarea, a inputului.

Cele două tehnici de sortare care urmează îndeaproape metoda divide et impera sunt
Sortare prin îmbinare
•Sortare rapidă (sortare prin schimbare de partitie)

5.2 SORTARE PRIN ÎMBINARE

Conceptual, un sortare prin fuziune funcț ionează astfel

1. Dacă lista are lungimea 0 sau 1, atunci este deja sortată. Altfel:
2. Împarte lista nesortată în două subliste de aproximativ jumătate din dimensiune.
3. Sortează fiecare sublistărecursivprin reaplicarea sortării prin fuziune.
4.Îmbinăcele două subliste înapoi într-o listă sortată.

Acum, să vedem "Care sunt paș ii implicaț i în sortarea prin îmbinare?" Paș ii diferiț i care sunt
implicate în timpul sortării folosind sortarea prin interclasare sunt prezentate mai jos:

Împarte: Împarte array-ul dat, care constă din n elemente, în două părț i de n/2.
Căutare element
Conquer: Sortează partea stângă a tabloului ș i partea dreaptă a tabloului recursiv
utilizând sortarea prin îmbinare...
Combină: Combină partea stângă sortată ș i partea dreaptă sortată pentru a obț ine o singură parte sortată.
aranjament.
Operaț ia cheie în sortarea prin interclasă este combinarea părț ii stângi sortate cu partea dreaptă sortată.
parte într-un singur array sortat. Acest proces de unire a două vectori sortati într-un singur
vectorul ordonat se numeș te îmbinare simplă. Singura condiț ie necesară pentru această problemă este că
Ambele aranjamente ar trebui să fie sortate. Acum, să vedem "Cum să proiectăm un algoritm simplu de unire?"

Design: Să presupunem că avem două vectori sortati A ș i B cu m ș i n elemente.

respectiv. Procedura următoare este utilizată pentru a combina aceste două vectori ordonaț i:
Compara elementul i din vectorul A cu elementul j din vectorul B ș i copiază elementul mai mic în k.
poziț ia vectorului rezultat C (cu 0 ca valoare iniț ială pentru variabilele i, j ș i k).
Codul echivalent poate fi scris după cum urmează:

60
dacă ( A[i] < B[j] ) atunci
C[k] A[i]
k k +l, i i+l
Copiază elementul cel mai mic din A în C

// Indică următorul element în C ș i A

( Fig 2.1 Exemplu pentru sortarea prin fuziune)

Algoritm SimpleMerge(A, jos, mijloc, sus)

//Scop : Combină două array-uri sortate în care primul array începe de la mic la mediu ș i //the
al doilea începe de la mid+1 până la high.

A este sortat de la poziț ia index low la mid

// A este sortat de la poziț ia index mid+1 până la high
A este sortat de la indexul jos la înalt.
eu scăzut, j mid+l, k scăzut
în timp ce (i <= mid ș i j <= high)
dacă ( A[i] < A[j] ) atunci
C[k] A[i] Copiază elementul cel mai mic din prima parte a A în C
eu i + 1 //Punctaț i următorul element în partea stângă a A
k k+1 //Punct pentru următorul element în C

61
altfel
C[k] A[j]
j j+l
k k + 1;
sfârș it dacă
sfârș it în timp ce
Copiează elementul cel mai mic din a doua parte a A în C
// Punct către următorul element în a doua parte a A
// Punctaț i următorul element în C
în timp ce (i <= mijloc) //Copiază articolele rămase din partea stângă a A în C
C[k] A[i]
k k+l , i i+l
finalizare în timp ce
în timp ce (j <= high) //Copiază elementele rămase din partea dreaptă a lui A în C
C[k] A[j]
k k+l; j j+l
sfârș it în timp ce
pentru i = mic la mare
a[i] c[i] // Copiaț i elementele din vectorul C în vectorul A
sfârș it pentru

//Sfârș itul algoritmului

Odată ce fuzionarea s-a încheiat, putem aranja cu uș urinț ă numerele în ordine crescătoare folosind
sortare prin îmbinare. iflow ș i high sunt limita inferioară ș i limita superioară într-un array, general
procedura de sortare a elementelor folosind sortarea prin interclasare este prezentată mai jos:

dacă (scăzut <înalt)

. Împarte array-ul în părț i egale
. Sortează partea stângă a array-ului recursiv
. Sortează partea dreaptă a aranjamentului recursiv.
. Îmbină partea stângă ș i partea dreaptă.
sfârș it dacă
Algoritmul complet pentru a sorta numerele folosind sortarea prin interclasare este prezentat mai jos:

AlgoritmSortarePrinInterclasare(A, jos, sus)

//Scop: Să sortezi elementele array-ului între limita inferioară ș i limita superioară
A este un vector nesortat cu low ș i high ca limită inferioară ș i limită superioară
A este un vector sortat
dacă (low < high)
mijloc (mic + mare)/2 // Împarte array-ul în părț i egale

62
 Sortare prin fuziune (a, jos, mijloc) // Sortează partea stângă a matricei,

Sortare prin combinare (a, mid + 1, high) // Sortează partea dreaptă a array-ului

SimpleMerge(a, jos, mijloc, sus) // Fuzionaț i partea stângă ș i partea dreaptă

Sfârș it dacă

Analiză: Este clar din algoritm că instanț a problemei este împărț ită în două
părț i egale.
Dacă timpul pentru operaț iile de îmbinare este proporț ional cu 'n', atunci timpul de calcul pentru
sortarea prin interclasare este descrisă prin relaț ia de recurenț ă.

T(n) = { a n=1, 'a' o constantă

2T(n/2)+cn n>1, 'c' o constantă.

Când 'n' este o putere a lui 2, n= 2^k, putem rezolva această ecuaț ie prin succesive
substituț ie.
T(n) = 2(2T(n/4) + cn/2) + cn
= 4T(n/4)+2cn
= 4(2T(n/8)+cn/4)+2cn
*
*
= 2^k T(1)+kCn.
= an + cn log n.

Este uș or de văzut că dacă s^k<n<=2^k+1, atunci T(n)<=T(2^k+1). Prin urmare,

T(n)=O(n log n)

Avantaje
Algoritmul merge sort este un algoritm stabil
Poate fi aplicat fi ș ierelor de orice dimensiune.

Dezavantaje
Algoritmul foloseș te un spaț iu suplimentar proporț ional cu N. Aș adar, algoritmul nu este în loc.
Foloseș te mai multă memorie pe stivă din cauza recursiei.

5.3 SORTARE RAPIDĂ

Abordarea de tip divide ș i cucere ș te poate fi utilizată pentru a ajunge la o sortare eficientă.
metodă diferită de sortarea prin îmbinare.

63
 În sortarea prin interclasare, fi ș ierul a[1:n] a fost împăr ț it la mijloc în sub-arrays care
au fost sortate independent ș i ulterior combinate.

În Quick sort, divizarea în 2 sub-array-uri se face astfel încât sub-array-urile sortate

nu trebuie să fie combinate mai târziu.

•Aceasta se realizează prin reorganizarea elementelor din a[1:n] astfel încât a[I]<=a[j] pentru
toate i între 1 ș i n ș i toate j între (m+1) ș i n pentru un anumit m, 1<=m<=n.

Astfel, elementele din a[1:m] ș i a[m+1:n] pot fi sortate independent.

•Nu este necesară nicio îmbinare. Această reorganizare este denumită partitionare.

Func ț ia de parti ț ie a algoritmului realizează o parti ț ionare in-place a

elementele lui a[m:p-1]

•Se presupune că a[p]>=a[m] ș i că a[m] este elementul de parti ț ionare. Dacă m=1 &
p-1=n, atunci a[n+1] trebuie să fie definit ș i trebuie să fie mai mare sau egal cu to ț i
elemente în a[1:n]

Presupunerea că a[m] este elementul de parti ț ie este doar pentru comoditate, altceva
alegerile pentru elementul de partiț ie decât primul element din set sunt mai bune în
practică.

Func ț ia interchange (a,I,j) schimbă a[I] cu a[j].

Exemplu. Sortează {1, 12, 5, 26, 7, 14, 3, 7, 2} folosind quicksort.

64
Algoritm: Partț ionaț i array-ul a[m:p-1] în jurul a[m]

1. Algoritm Partitie(a,m,p)
2. //în cadrul a[m],a[m+1],…..,a[p-1] elementele
3. // sunt reorganizate în a ș a fel încât dacă
4. //ini ț ial t=a[m], apoi după finalizare
5. //a[q]=t pentru un anumit q între m ș i
6. //p-1,a[k]<=t pentru m<=k<q, ș i
7. //a[k]>=t pentru q<k<p. q este returnat
8. //Seta ț i a[p]=infinit.
9. {
10. v=a[m];I=m;j=p;
11. repetă
12.

65
 13. repetă
14. I=I+1;
15. până când(a[I]>=v);
16. repetă
17. j=j-1;
18. până când(a[j]<=v);
19. dacă (I<j) atunci interschimbă(a,I.j);
20. }până(I>=j);
21. a[m]=a[j]; a[j]=v;
22. retun j;
23. }

1. Algoritmul Interschimbare(a,I,j)
//Schimbă a[I] cu a[j]
3. {
4. p=a[I];
5. a[I]=a[j];
6. a[j]=p;
7. }

Algoritmul Quicksort(p,q)
//Sortează elementele a[p],....a[q] care se află
2. //este tabloul global a[1:n] în ordine crescătoare
3. //comandă; a[n+1] este considerat a fi definit
4. // ș i trebuie să fie >= toate elementele din a[1:n]
5. {
6. dacă(p<q) atunci // Dacă există mai mult de un element
7.
8. // împăr ț iț i p în 2 subprobleme
9. j=partition(a,p,q+1);
10. //’j’ este poziț ia elementului de partiț ionare.
11. //rezolvă subproblemele.
12. quicksort(p,j-1);
13. quicksort(j+1,q);
14. //Nu este nevoie de combinarea soluț iei.
15. }
16. }

Design:
Sortarea rapidă se bazează pe principiul „Împarte ș i cucereș te”. Sortarea rapidă funcț ionează
foarte bine pe un set mare de date. Acum, să vedem "Care sunt paș ii
implicate în sortarea rapidă?
sortarea este prezentată mai jos:

Pasul 1: Împărț iț i matricea în două sub-matrice:

66
 Partea stângă Element pivot Partea dreaptă
A[0]A[1]….A[K-1] A[K] A[K+1]A[K+2]…..A[N-1]

Pasul 2: Cucereș te: Sortează partea stângă a array-ului A[O]A[l]...A[k-l] recursiv

Sortează partea dreaptă a array-ului A[k+l] A[k+2] A[kn-l] recursiv

Pentru a simplifica designul, presupuneț i că o valoare foarte mare este stocată la sfârș itul
array. Acest lucru se realizează prin stocarea 00 în a[n]. Pe lângă a, low ș i high, ceilalț i
variabilele care sunt utilizate sunt:
Valoarea iniț ială a indexului i este scăzută, adică, i valoarea iniț ială a indexului j este unu
mai mult decât înalt, adică, j înalt
.pivot:a[low] este tratat ca elementul pivot.
Procedura generală pentru a partitiona array-ul este prezentată mai jos:
Continuaț i să incrementaț i indexii atâta timp cât sunt pivot. a[i]. Acest lucru se realizează folosind
statement:
oare eu i + 1 în timp ce (pivot >= a[i]);
.. Odată ce condiț ia de mai sus eș uează, continuaț i să decrementezi indexul cât timp pivotS a[j]'
Acest lucru se realizează folosind declaraț ia:
fă j +- j - 1 cât timp (pivot >= a[i]);
Odată ce condiț ia de mai sus nu mai este îndeplinită, dacă i este mai mic decât j, schimbă a[i] cu a[j] ș i repetă tot.
procesul de mai sus atâta timp cât i <= j.

Performanț a sortării rapide

Timpul de execuț ie al sortării rapide depinde de faptul dacă partajarea este echilibrată sau dezechilibrată.
care la rândul său depinde de care elemente ale unui array care trebuie sortate sunt utilizate pentru
partiț ionare. O partiț ie foarte bună împarte un tablou în două tablouri de dimensiuni egale. O partiț ie proastă
partition, on other hand, splits an array up into two arrays of very different sizes. The
cea mai proastă partiț ie pune un singur element într-un array ș i toate celelalte elemente în celălalt
array. Dacă partiț ionarea este echilibrată, Quick sort rulează asimptotic la fel de repede ca merge
sortare. Pe de altă parte, dacă particionarea este dezechilibrată, Quick sort rulează asimptotic.
la fel de lent ca sortarea prin inserț ie.

Cel mai bun caz

Cel mai bun lucru care s-ar putea întâmpla în sortarea rapidă ar fi ca fiecare etapă de partiț ionare
împarte matricea exact în jumătate. Cu alte cuvinte, cel mai bine este să fie o mediană a cheilor din
A[p. .r] every time procedure 'Partition' is called. The procedure 'Partition' always split
array-ul care trebuie sortat în două array-uri de dimensiuni egale.

Dacă procedura 'Partiț ie' produce două regiuni de dimensiune n/2, relaț ia de recurenț ă este
atunci

67
T(n)=T(n/2)+T(n/2)+ (n)
= 2T(n/2) + (n)

Ș i din cazul 2 al teoremei Master

T(n) = (nlgn)

Cazul cel mai rău:

Fie T(n) cel mai rău caz de timp pentru SORTAREA RAPIDĂ pe o dimensiune de intrare n. Avem o recurenț ă

T(n) = max1≤q≤n-1(T(q) + T(n-q)) + (n) --------- 1

undeqruns de la 1 ton-1, deoarece partiț ia produce două regiuni, fiecare având dimensiune la
cel puț in 1.

Acum ghicim că T(n) ≤ cn2pentru un constantc.

Substituind presupunerea noastră în ecuaț ia 1. Obț inem

T(n) = max1≤q≤n-1(cq2) +c(n-q2)) + (n)

=cmax (q2+ (n-q)2) + (n)

Deoarece derivata a doua a expresiei q2+ (n-q)2în ceea ce priveș te q este pozitiv.
Prin urmare, expresia atinge un maxim în intervalul 1≤ q ≤ n -1 la unul dintre
punctele finale. Aceasta oferă limita maximă (q2+ (n-q)2)) 1 + (n-1)2 =n2+ 2(n-1).

Continuând cu limitarea noastră a T(n) obț inem

T(n) ≤c[n2- 2(n-1)] + (n)

=cn2- 2c(n-1) + (n)

Deoarece putem alege constanta astfel încât termenul 2c(n-1) să domine termenul (n) noi
a avea

T(n) ≤ cn2

Astfel, timpul de execuț ie în cel mai rău caz al sortării rapide este T(n) = (n2).

68
Analiza cazului mediu

Dacă împărț irea indusă de RANDOMIZED_PARTITION pune o fracț ie constantă de elemente

pe o parte a despărț irii, atunci arborele de recurenț ă are adâncime (lgn) ș i (n) munca este
efectuat la (lgn) dintre aceste niveluri. Acesta este un argument intuitiv de ce cazul mediu
timpul de execuț ie al RANDOMIZED_QUICKSORT este (nlgn).

LetT(n) denotă timpul mediu necesar pentru a sorta un tablou de n elemente. Un apel la
RANDOMIZED_QUICKSORT cu un array de 1 element durează un timp constant, aș a că avem
T(1) = (1).

După împărț ire, RANDOMIZED_QUICKSORT se apelează singur pentru a sorta două sub-array-uri. The
timpul mediu pentru a sorta un array A[1 . .q] este T[q] ș i timpul mediu pentru a sorta un array
A[q+1 . .n] este T[n-q]. Avem

T(n) = 1/n(T(1) + T(n-1) +n-1∑q=1T(q) + T(n-q))) + (n) 1

Ș tim din analiza cazului cel mai rău

T(1) = (1) ș i T(n-1) = O(n2)

n-1
T(n) = 1/n( (1) +O(n2)) + 1/n ∑q=1 (r(q) + T(n-q)) + (n)
= 1/n n-1∑q=1(T(q) + T(n-q)) + (n) ------- 2
n-1
= 1/n[2 ∑k=1(T(k)] + (n)
= 2/nn-1∑k=1(T(k) + (n) --------- 3

Rezolvă recurenț a de mai sus folosind metoda substituț iei. Presupune inductiv că T(n) ≤
anlgn+b pentru unele constante a> 0 ș i b> 0.

Dacă putem alege 'a' ș i 'b' suficient de mari astfel încât nlgn+b > T(1). Atunci pentru n > 1, avem

n-1
T(n) ≥ ∑k=1 2/n (aklgk + b) + (n)
= 2a/nn-1∑k=1klgk -1/8(n2) + 2b/n(n-1) + (n) ------- 4

În acest moment, afirmăm că

n-1
∑klgk
k=1 ≤ 1/2 n2lgn -1/8(n2)
Introdu această afirmaț ie în ecuaț ia 4 de mai sus ș i obț inem

69
 T(n) ≤ 2a/n[1/2n2lgn- 1/8(n2)] + 2/n b(n-1) + (n)
≤ anlgn-an/4 + 2b + (n)

În ecuaț ia de mai sus, vedem că (n) +bandan/4 sunt polinoame ș i cu siguranț ă

poate alege 'a' suficient de mare încât an/4 să domine (n) + b.

Concluzionăm că timpul mediu de execuț ie al QUICKSORT este (nlg(n)).

Concluzie :

Sortarea rapidă este un algoritm de sortare in situ, al cărui timp de execuț ie în cel mai rău caz este (n2) ș i
timpul de execuț ie aș teptat este (nlgn), unde constantele ascunse în (nlgn) sunt mici.

5.4 CĂUTARE BINARĂ

Să presupunem că avem un număr de întregi stocaț i într-un array A ș i vrem să localizăm un

obiectiv specific integer K în acest array. Dacă nu avem nicio informaț ie despre cum se
numerele întregi sunt organizate în matrice, trebuie să examinăm secvenț ial fiecare element al
array. Aceasta este cunoscută sub numele de căutare liniară ș i ar avea o complexitate de timp de O(n) în
cel mai rău caz. Totuș i, dacă elementele matricei sunt ordonate, să spunem în ordine ascendentă
ordinea, ș i dorim să aflăm poziț ia unui întreg ț intă K în array, nu trebuie să
realizăm o căutare secvenț ială pe întreaga matrice. Putem face o căutare mai rapidă folosind
Metoda de căutare binară.

Ideea de bază este să începem cu o examinare a elementului din mijlocul array-ului. Aceasta
va duce la 3 situaț ii posibile:
Dacă aceasta se potriveș te cu ț inta K, atunci căutarea poate termina cu succes, prin imprimarea.
indexul elementului în masiv.
Pe de altă parte, dacă K<A[middle], atunci căutarea poate fi limitată la elementele din stânga
A[mijloc]. Toate elementele din dreapta mijlocului pot fi ignorate.
Dacă se dovedeș te că K > A[middle], atunci căutarea ulterioară este limitată la elementele din dreapta.
al A[mijloc].
Dacă toate elementele sunt epuizate ș i ț inta nu este găsită în array, atunci metoda
întoarce o valoare specială, cum ar fi -1.
Aici este o versiune a funcț iei de Căutare Binara:

70
Algorithm : BinarySearch (int A[ ], int n, int K)
{
L=0, Mid, R=n-1;
în timp ce (L<=R)
{
Mid = (L + R)/2;
dacă ( K == A[Mid] )
returnează Mid;
altfel dacă ( K > A[Mid] )
L = Mid + 1;
altfel
R = Mid - 1 ;
}
return –1 ;
}
Analiza căutării binare

Cazul cel mai bun: Cazul cel mai bun apare atunci când elementul căutat este prezent în mijlocul
array-ul. Deci numărul total de comparaț ii necesar va fi 1.. Prin urmare, timpul
complexitatea căutării binare în cel mai bun caz este dată de Tbest(n)=Ω(1).
Cazul cel mai rău: Acest caz apare atunci când cheia care trebuie căutată se află fie în prima poziț ie
sau în ultima poziț ie din array. În astfel de situaț ii, numărul maxim de elemente
comparările sunt necesare, iar complexitatea temporală este dată de
T(n)={ 1 dacă n=1
T(n/2) + 1 altfel
Considera, t(n)=t(n/2)+1
Această relaț ie de recurenț ă poate fi rezolvată folosind substituț ia repetată, aș a cum este prezentat mai jos:
t(n)=t(n/2)+1 înlocuiț i n cu n/2
t(n)=1+1+t(n/2 ) 2

t(n)=1+2+t(n/23) înlocuiț i n cu n/2

…………..
…………..
În general, t(n)=i+t(n/2eu) În cele din urmă, pentru a obț ine condiț ia iniț ială t(1), să punem 2eu= n
t(n)=i+t(1) Unde t(1)=0
t(n)=i Avem n=2eu, Ia log pe ambele părț i
i*log2 = log2n
i = log2n
Aș adar, complexitatea temporală este dată de Tavg(n) € ( log2n)

Avantajele căutării binare

•Tehnică simplă
•Tehnică de căutare foarte eficientă

Dezavantajele căutării binare

Array-ul ar trebui să fie sortat.

71
 Verifică-ț i progresul
1. Ce este sortarea?
2. Scrie un algoritm pentru sortarea prin interclasare? Explică modul în care funcț ionează.

3. Scrie un algoritm pentru sortarea rapidă? calculează cazul cel mai bun, cazul cel mai rău ș i cazul mediu
complexitate temporală.

4. Explicaț i funcț ionarea căutării binare cu un exemplu? Scrieț i un algoritm ș i timpul acestuia
complexitate.

5.5 SUMMARY

Sortarea prin îmbinarea este un algoritm de tip divide ș i cucereș te. Funcț ionează prin împărț irea unei matrice în două
jumătă ț i, sortându-le recursiv ș i apoi fuzionând cele două jumătă ț i sortate pentru a ob ț ine
array-ul original sortat. Eficienț a temporală a algoritmului este aceeaș i în toate cazurile adică θ(nlogn).

Sortarea rapidă este un algoritm de împăr ț ire ș i cucerire care func ț ionează prin partitionarea inputului său.
elemente în funcț ie de valoarea lor relativă faț ă de un element preselectat. Sortarea rapidă este
notat pentru eficienț a sa superioară printre algoritmii nlogn pentru sortarea ordonărilor aleatoare
matrici, dar ș i pentru eficienț a quadratică în cel mai rău caz.

Căutarea binară este un algoritm O(logn) pentru căutarea în aranjamente sortate. Este un exemplu tipic de
o aplicaț ie a tehnicii de împărț ire ș i stăpânire pentru că trebuie să rezolve doar una
problema de jumătate din dimensiune la fiecare dintre iteraț iile sale.

RĂSPUNSURI PENTRU A VERIFICA PROGRESUL TĂU

1. 1.1
2. 1.2
3. 1.3
4. 1.4
EXERCIȚII Ș I RĂSPUNSURI PE UNITATE
10. a.) Care este cel mai mare număr de compariț ii cheie efectuate de căutarea binară în căutare

pentru o cheie în următorul array?

{ 3,14,27,31,39,42,55,70,74,81,85,93,98 }
b) Enumerati toate cheile acestui array care vor necesita cel mai mare numar de chei
comparatiile atunci când sunt căutate prin căutare binară.

Aplică sortarea rapidă la lista A N A L I Z Ă în ordine alfabetică.

72
 12. Aplică algoritmul de sortare prin interclasare pentru a sorta A L G O R I T H M în ordine alfabetică? Este

Este merge sort un algoritm stabil?

Answers: SEE
1. 1.4
2. 1.3
3. 1.2
5.6 SUGGESTED READINGS
1. Inroduction to The design and analysis of algorithms by Anany Levitin
2. Analiză ș i proiectare de algoritmi cu C/C++ - 3rdediț ie de Prof. Nandagopalan

73
 MODUL-3, UNITATEA 3: TEHNICA AVARĂ

Structură
4.0 Obiective
1.1 Introducere
1.1.1 Conceptul metodei zgârcite
1.2 Probleme de optimizare
1.3 Rezumat
1.4 Cuvinte cheie

1.5 Răspunsuri pentru a-ț i verifica progresul

1.6 Exerciț ii ș i răspunsuri de final de unitate

1.7 Suggested readings

6.0 OBJECTIVES
La sfârș itul acestei unităț i vei fi în măsură să

Găsi ț i cum să aplica ț i tehnica Greedy

•Identificarea dacă problema trebuie rezolvată folosind tehnica de tip greedy

• Ș tiț i cum să găsi ț i calea cea mai scurtă de la o sursă unică

•Construie ș te arborele Huffman ș i generează codul Huffman.

6.1 INTRODUCERE

Algoritmii zgârci ț i sunt simpli ș i direc ț i. Sunt pe termen scurt în viziunea lor.
abordare în sensul că iau decizii pe baza informaț iilor disponibile fără
îngrijorându-se cu privire la efectul pe care aceste decizii îl pot avea în viitor. Ele sunt uș or de imaginat,
uș or de implementat ș i, cel mai adesea, destul de eficient. Multe probleme nu pot fi rezolvate
corect prin abordarea greedy. Algoritmii greedy sunt folosiț i pentru a rezolva probleme de optimizare

74
1.1.1 Conceptul metodei greedy

Algoritmul gloton func ț ionează prin luarea deciziei care pare cea mai promi ț ătoare în orice moment.
moment; nu reconsideră niciodată această decizie, indiferent de situaț ia care ar putea apărea mai târziu.

Ca un exemplu, luaț i în considerare problema 'Schimbării Monedelor'.

Monedele disponibile sunt:

dolari (100 cen ț i)

monede de 25 de cen ț i
dime (10 cen ț i)
monede de 5 cen ț i
•pennies (1 cent)

Problemă: Fă o schimbare a unei sume date folosind cel mai mic număr posibil de
monede.

Algoritm informal

Începe cu nimic.
•în fiecare etapă fără a depă ș i suma dată.
•adauga-l pe cel mai mare la monedele deja alese.

Algoritm Formal

Fă schimb pentru n unităț i folosind cel mai mic număr posibil de monede.

MAKE-CHANGE(n) {

C ← {100, 25, 10, 5, 1} //constants

S ← {}; // Set care de ț ine solu ț ia

Sum ← 0

În timp ce suma != n

75
x=cel mai mare element din setul C astfel încât suma+x <= n

dacă nu există un astfel de articol atunci

Fără soluț ie

S ← S{valoareadx}
sumă ← sumă+x
ÎNTOARCE S }

Fă o schimbare pentru 2.89 (289 cenț i) aici n = 2.89 ș i soluț ia conț ine 2
dolari, 3 sferturi, 1 dime ș i 4 bănuț i. Algoritmul este lacom deoarece în fiecare etapă
alege cea mai mare monedă fără a se îngrijora de consecinț e. Mai mult, niciodată nu
îș i schimbă părerea în sensul că, odată ce o monedă a fost inclusă în setul de soluț ii, aceasta
rămâne acolo.

1.1.2 Caracteristici ș i trăsături ale problemelor rezolvate de Algoritmi Greedy

Pentru a construi soluț ia într-un mod optim. Algoritmul menț ine două seturi. Unul conț ine
articole alese ș i cealaltă conț ine articole respinse.

Algoritmul greedy constă în patru (4) funcț ii.

1. O func ț ie care verifică dacă setul de articole ales oferă o solu ț ie.
2. O func ț ie care verifică fezabilitatea unui set.
3. Func ț ia de selec ț ie indică care dintre candida ț i este cel mai promi ț ător.
4. O func ț ie obiectivă, care nu apare explicit, oferă valoarea unui
soluț ie.

Algoritm Greedy de Structură

Ini ț ial, setul de articole alese este gol, adică setul de solu ț ii.
•La fiecare pas
obiectul va fi adăugat într-un set de solu ț ii prin utilizarea func ț iei de selec ț ie.
dacă setul nu ar mai fi fezabil
. respinge articolele aflate în discuț ie (ș i nu va mai fi considerat niciodată din nou).
ALT IF set este încă fezabil ATUNCI
. adaugă articolul curent.

76
 1.1.3 Defini ț ii ale fezabilită ț ii

Un set fezabil (de candidaț i) este promiț ător dacă poate fi extins pentru a produce nu doar o
soluț ie, dar o soluț ie optimă pentru problemă. În special, mulț imea vidă este
întotdeauna promiț ător de ce? (pentru că o soluț ie optimă există întotdeauna)

Spre deosebire de Programarea Dinamică, care rezolvă subproblemele de jos în sus, o abordare greedy

strategia progresează de obicei într-o manieră de sus în jos, făcând o alegere lacomă după alta
unul, reducând fiecare problemă la una mai mică.

Proprietatea alegerii avare

Proprietatea "alegerii lacome" ș i "substructura optimă" sunt două ingrediente în

problema care duce la o strategie lacomă.

Proprietatea alegerii lacome

Se spune că o soluț ie global optimă poate fi obț inută prin realizarea unei soluț ii locale optime.
alegere.

6.2 PROBLEME DE OPTIMIZARE

1.2.1 Huffman Codes

Codul Huffman este o tehnică pentru comprimarea datelor. Algoritmul lacom al lui Huffman analizează
apariț ia fiecărui caracter ș i acesta ca un ș ir binar într-un mod optim.

Exemplu

Să presupunem că avem un set de date care constă din 100.000 de caractere pe care dorim să le comprimăm.
caracteristicile din date apar cu frecvenț ele următoare.

a b c d e f
Frequency 45,000 13,000 12,000 16,000 9,000 5,000

77
 Consideraț i problema proiectării unui "cod de caractere binar" în care fiecare caracter este
reprezentat printr-un ș ir binar unic.

Cod de lungime fixă

În codul de lungime fixă, sunt necesare 3 biț i pentru a reprezenta ș ase (6) caractere.

a b c d e f
Frecvenț ă 45,000 13,000 12,000 16,000 9,000 5,000
Lungime Fixă
000 {"001":"001"}
010 011 100 101
cod

Această metodă necesită 3000.000 de biț i pentru a codifica întreaga fiș ier.

Cum obț inem 3.000.000?

•Numărul total de caractere este 45.000 + 13.000 + 12.000 + 16.000 + 9.000 +

5.000 = 1.000.000.
•Fiecare caracter este asociat cu un cod de 3 bi ț i => 3 * 1000.000 = 3.000.000 bi ț i

Concluzie

Codul de lungime fixă necesită 300.000 de biț i, în timp ce codul variabil necesită 224.000 de biț i.

Economisire de aproximativ 25%.

Coduri de Prefix

În care nicio cuvânt de cod nu este un prefix al altui cuvânt de cod. Motivul pentru care codurile de prefix sunt
dorit este ca ei să efectueze pur ș i simplu codificarea (compresia) ș i decodificarea.

Putem să facem mai bine?

Un cod de lungime variabilă poate face mai bine oferind caractere frecvente coduri scurte ș i
caractere rare cu cuvinte lungi.

a b c d e f
Frecvenț ă 45,000 13,000 12,000 16,000 9,000 5,000
Lungime fixă
0 101 100 111 1101 1100
cod

78
Caracterul 'a' este 45.000
fiecare caracter 'a' asignat un cod de 1 bit.
1 * 45.000 = 45.000 biț i.

Personajele (b, c, d) sunt 13.000 + 12.000 + 16.000 = 41.000

fiecare caracter are un cuvânt de cod de 3 biț i
3 * 41.000 = 123.000 biț i

Caracterele (e, f) sunt 9.000 + 5.000 = 14.000

fiecare caracter are un cod de 4 biț i.
4 * 14.000 = 56.000 biț i.

Implica că totalul bitilor este: 45.000 + 123.000 + 56.000 = 224.000 biti

Codificare: Concatena ț i codurile care reprezintă fiecare caracter al fi ș ierului.

Codarea ș irurilor
CEAI 10 00 010
MARE 011 00 010
ZECE 10 00 110

Din tabela de coduri de lungime variabilă, codificăm fi ș ierul de 3 caractere abc ca:

a b c
=> 0.101.100 =
0 101 100
0101100

Decodare

Deoarece niciun cuvânt cod nu este un prefix al altuia, cuvântul cod care începe un fiș ier codificat este
neambiguu.

79
Pentru a decoda (a traduce înapoi la caracterul original), elimină-l din fiș ierul codificat ș i
analiza repetată.
De exemplu, în tabelul "cuvânt cod de lungime variabilă", ș irul 001011101 se analizează în mod unic
ca 0.0.101.1101, care este decodificat toaabe.

Reprezentarea "procesului de decodare" este un arbore binar, ale cărui frunze sunt caractere.
interpretează codul binar pentru un caracter ca fiind calea de la rădăcină până la acel caracter
unde 0 înseamnă "mergi la copilul din stânga" ș i 1 înseamnă "mergi la copilul din dreapta". Observaț i că un
Codul optim pentru un fiș ier este întotdeauna reprezentat de un arbore binar complet.

1.2.2 Algoritmul lui Dijkstra (Algoritmul drumului cel mai scurt de la o sursă unică)

Algoritmul lui Dijkstra rezolvă problema căii celei mai scurte dintr-o sursă unică atunci când toate marginile au
greutăț i non-negative. Este un algoritm glutton. Algoritmul începe de la vârful sursă, s, el
creș te un copac, T, care în final acoperă toate vârfurile accesibile din S. Vârfurile sunt adăugate la
T în ordinea distanț ei adică, mai întâi S, apoi vârful cel mai apropiat de S, apoi următorul cel mai apropiat, ș i aș a mai departe
Implementarea următoare presupune că graful G este reprezentat prin adiacentă.

Declaraț ia problemei: Găsirea celei mai scurte distanț e de la o sursă unică la diferite
oraș e.

Algoritm : DIJKSTRA (G, w, s)

1. INI Ț IALIZEAZĂ SURSA UNICĂ (G, s)

2. S ← { } // S va con ț ine în cele din urmă vârfurile greută ț ilor cele mai scurte ale drumulu
de la s
3. Inicializa ț i coada de prioritate Q adică, Q ← V[G]
4. în timp ce coada de prioritate Q nu este goală, faceti
5. u← EXTRACT_MIN(Q) // Extrage noul vârf
6. S ← S {u}
// Efectuează relaxarea pentru fiecare vârf adiacent lui u
7. pentru fiecare vârf v în Adj[u] atunci
8. Relaxare (u,v,w)

Exemplu: Funcț ionarea pas cu pas a algoritmului Dijkstra.

Pasul 1. Dat graful iniț ial G=(V, E). Toate nodurile au cost infinit, cu excepț ia
nod sursă, s, care are cost 0.

80
Pasul 2. Mai întâi alegem nodul, care este cel mai apropiat de nodul sursă, s. Inicializăm d[s]
0. Adaugă-l la S. Relaxează toate nodurile adiacente sursei, s. Actualizează predecesorul (vezi săgeata roș ie
în diagrama de mai jos) pentru toate nodurile actualizate.

Pasul 3. Alegeț i nodul cel mai apropiat, x. Relaxaț i toate nodurile adiacente nodului x. Actualizaț i
predecesorii pentru nodurile u, v ș i y (din nou, observaț i săgeț ile roș ii în diagrama de mai jos).

Pasul 4. Acum, nodul y este nodul cel mai aproape, aș a că îl adăugăm la S. Relaxaț i nodul v ș i ajustaț i-l.
predecesor (să ne amintim de săgeț ile roș ii!).

81
Pasul 5. Acum avem nodul u care este cel mai apropiat. Alegeț i acest nod ș i ajustaț i vecinul său.
nod v.

Pasul 6. În cele din urmă, adăugaț i nodul v. Lista de predecesori defineș te acum calea cea mai scurtă de la fiecare
nodul sursă, s.

82
Analiză

Ca algoritmul lui Prim, algoritmul lui Dijkstra rulează în O(|E|lg|V|) timp.

Verifică-ț i progresul

1. Explicaț i metoda lacomă de rezolvare a problemelor cu exemplul.

2. Scrie o notă despre codificarea Huffman.

3. Scrie un algoritm pentru calea cea mai scurtă de la o sursă folosind tehnica greedy, explică.
cu exemplul.

1.3 SUMMARY
Tehnica lacomă sugerează construirea unei soluț ii pentru o problemă de optimizare
printr-o secvenț ă de paș i, fiecare extinzând o soluț ie parț ial construită obț inută astfel
departe, până când se ajunge la o soluț ie completă a problemei. La fiecare pas, alegerea făcută
trebuie să fie fezabil, local optim ș i irrevocabil.
Algoritmul lui Dijkstra rezolvă problema celui mai scurt drum dintr-o sursă unicată de a găsi cel mai scurt

căile de la un vârf dat (sursa) către toate celelalte vârfuri ale unui graf ponderat sau
digraph.
Codul Huffman este un schema de codificare optimă, fără prefix, cu lungime variabilă, care atribuie bit

ș ir de caractere bazat pe frecvenț ele lor într-un text dat. Acest lucru se realizează printr-o
construcț ia lacomă a unui copac binar a cărui margini sunt etichetate cu 0 ș i 1.

1.4KEYWORDS
1 Tehnica lacomă – Este o metodă (abordare) de rezolvare a problemelor.
2. Arborele lui Huffman - Este un arbore binar generat de algoritmul Huffman având copil stâng
greutatea muchiei ca 0 ș i greutatea copilului din dreapta ca 1.

1.5 ÎNTREBĂRI PENTRU A VERIFICA PROGRESUL TĂU

1. 1.1

83
 2. 1.2
3. 1.2
1.6 EXERCI ȚII Ș I RĂSPUNSURI LA SFÂR Ș ITUL UNITĂ ȚII

1.a. Compară codificarea de lungime fixă cu codificarea de lungime variabilă

b. Demonstrează că codificarea cu lungime variabilă este mai bună decât codificarea cu lungime fixă.
c. Acesta este faptul că codificarea Huffman poate fi utilizată pentru compresia datelor, sus ț ineț i-vă

răspunde cu exemplul.
2. Discutaț i cum algoritmul lui Dijkstra aparț ine tehnicii greedy cu exemplul.
Answers: SEE
1. 1.3
2. 1.3
1.7 SUGGESTED READINGS
1. Introducere în proiectarea ș i analiza algoritmilor de Anany Levitin
2. Analiza ș i proiectarea algoritmilor cu C/C++ - 3rdediț ie de Prof. Nandagopalan
3. Analiza ș i proiectarea algoritmilor de către Padma Reddy

84
 MODULE-3,UNIT 3: APLICAȚII ALE METODEI GREEDY

Structură
5.0 Obiective
1.1 Introducere
1.2 Problema încărcării containerelor

1.3 Problema rucsacului 0/1

1.4 Algoritmi pentru arbori acoperitori minimi
1.6 Rezumat
1.7 Cuvinte cheie

1.8 Răspunsuri pentru a-ț i verifica progresul

1.9 Exerciț ii ș i răspunsuri la sfârș itul unităț ii

1.10 Lecturi sugerate

7.0 OBIECTIVE
La sfârș itul acestei unităț i vei fi capabil să
•Rezolvarea problemelor de încărcare a containerelor ș i a problemelor de rucsac.

•Găsi ț i cele mai scurte drumuri folosind algoritmul lui Prim ș i algoritmul lui Kruskal.

Identificarea diferen ț ei dintre arborele grafic ș i arborele acoperitor minim.

7.1 INTRODUCERE

Metoda greedy este tehnica cea mai simplă concepută.

•După cum sugerează numele, au o viziune pe termen scurt în abordarea lor de a lua decizii
baza informaț iilor imediat la îndemână fără a te îngrijora de
efectele pe care aceste decizii le pot avea în viitor.

DEFINIȚIE:
O problemă cu N intrări va avea anumite constrângeri. Orice submul ț ime care le îndepline ș te pe acestea.
restricț iile sunt denumite o soluț ie fezabilă.
O solu ț ie fezabilă care poate maximiza sau minimaliza o func ț ie de obiective dată.
se numeș te o soluț ie optimă.

7.2 PROBLEMA ÎNCĂRCĂRII CONTAINERULUI

85
 Problema încărcării containerelor este aproape similară cu problema rucsacului ș i de asemenea
similar cu o altă problemă interesantă numită problema de ambalare. Încărcarea containerelor
este afirmat după cum urmează:

Avem containere de dimensiuni egale care trebuie să fie încărcate pe marfă, iar la rândul său, marfa trebuie să fie
a fi încărcat pe navă. Fiecare container are o greutate, wi, iar încărcătura are o maximă
capacitatea unităț ilor c. Obiectivul acestei probleme este de a încărca nava cu maxim
numărul de containere. Să fie xi o variabilă, care ia valori 0 sau 1. Un 1 indică faptul că
containerul trebuie încărcat ș i un 0 înseamnă că nu ar trebui.
În mod formal, putem defini problema ca fiind:

Maximează
Supus constrângerilor, de la i=1 la n, [Link]<= C

Strategia lacomă
În această problemă, din fericire, nu avem profitul care trebuie luat în considerare pentru
constraints. Since the objective is to load the maximum number of containers, the
strategia lacomă pe care o folosim este:
Includeț i containerele de la cel mai mic la cel mai mare (adică în ordine crescătoare a greutăț ilor)
greutăț i astfel încât să putem încărca mai multe containere.
Exemplu
Consideraț i un container cu instanț e de încărcare cu n=7,
{w1,w2,w3,w4,w5,w6,w7}={90,190,40,80,140,40,40,10} and C=300.
Sol: Când containerele sunt aranjate în ordinea crescătoare a greutăț ilor lor, noi
get {w1,w2,w3,w4,w5,w6,w7}={ 10, 40, 40,80,90,140,190}
={ 1, 1, 1 , 1 , 1, 0, 0 }
Prin urmare, soluț ia este {1,0,1,1,0,1,1}
Numărul total de containere=5
Total weight=260

7.3 PROBLEMA RANDEI

Un ho ț jefuie ș te un magazin ș i poate transporta o greutate maximă de w în interiorul acestuia.

rucsacul. Există n articole ș i ithgreutatea articolului weuș i valorează veudolari. Ce articole
Ce ar trebui să ia un hoț ?

86
Există două versiuni ale problemei

Problema rucsacului fracț ionar

Configurarea este aceeaș i, dar hoț ul poate lua fracț iuni de obiecte, ceea ce înseamnă că obiectele pot fi
rupt în bucăț i mai mici, astfel încât hoț ul să poată decide să ia doar o fracț iune din xeude articole,
unde 0 ≤ xeu≤ 1.

Exhibă proprietatea alegerii avare.

. Algoritmul greedy există.

Exhibă proprietatea de substructură optimă.

. ?????

Problema rucsacului 0-1

Configuratia este aceeasi, dar articolele nu pot fi impartite in bucati mai mici, astfel ca hotul poate
decideț i fie să luaț i un obiect, fie să-l lăsaț i (alegere binară), dar nu puteț i lua o fracț iune din
un articol.

Exhibit nu are proprietatea alegerii zgârcite.

. Nu există un algoritm greedy.

Exhibit proprietatea de substructură optimă.

. Există doar algoritmi de programare dinamică.

1.3.1 Problema rucsacului 0-1 folosind programare dinamică

•ni se dau n obiecte ș i un rucsac sau sac cu capacitatea M pentru obiectul I are un
greutate Wi unde I variază de la 1 la N.
Problema este că trebuie să umplem geanta cu ajutorul N obiecte ș i rezultatul
profitul trebuie să fie maxim.
•Problema poate fi formulată formal ca
Maximizaț i xipi subiecț i la XiWi<=M
Unde Xi este fracț ia obiectului ș i se află între 0 ș i 1.
Există atât de multe modalită ț i de a rezolva această problemă, ceea ce va oferi multe solu ț ii fezabile.
soluț ia pentru care trebuie să găsim soluț ia optimă.
•Dar în acest algoritm, va genera doar o singură solu ț ie care va fi
fezabil, cât ș i optim.
În primul rând, găsim rata de profit ș i greutatea fiecărui obiect ș i o sortăm.
în conformitate cu ordinea descrescătoare a rapoartelor.

87
 •Selecta ț i un obiect cu cel mai mare raport p/w ș i verifica ț i dacă înăl ț imea acestuia este mai mică decât
capacitatea bagajului.
•Dacă da, plasa ț i 1 unitate din primul obiect ș i decrementează capacitatea sacului cu
greutatea obiectului pe care l-aț i plasat.
•Repeta ț i pa ș ii de mai sus până când capacitatea sacului devine mai mică decât greutatea
al obiectului pe care l-aț i selectat. în acest caz, plasaț i o fracț iune a obiectului ș i
ieș i din buclă.
•Ori de câte ori ai selectat.

Cea mai comună formulare a problemei este problema rucsacului 0-1, care
restricț ionează număruleude copii ale fiecărui tip de obiect la zero sau unu. Matematic,
Problema rucsacului 0-1 poate fi formulată ca:

. maximiza

. subiect la

Problema rucsacului cu limită restricț ionează numărul xeude copii ale fiecărui tip de articol la
o valoare întreagă maximăeu. Din punct de vedere matematic, problema rucsacului limitat poate fi
formulat ca:

. maximiza

. subiect la

Algoritm: Rucsac(n,m,w,p,v)
n - numărul de obiecte de selectat
capacitatea rucsacului
w – greutatea tuturor obiectelor
p - profiturile tuturor obiectelor
v - soluț ia optimă pentru numărul de obiecte selectate cu specificaț iile date
capacitate rămasă

Pentru i 0 până la n face

Pentru j 0 la m face
Dacă (i=0 sau j=0)
v[i,j]=0

88
 Altfel dacă(w[i]>j)
v[i,j]=v[i-1,j]
altfel
v[i,j]=max(v[i-1,j],v[i-1,j-w[i]]+p[i])
sfârș it dacă
sfârș it pentru
sfârș it pentru

Algoritm: obiectselectat(n,m,w,v,x)

n – numărul de obiecte care trebuie selectate

capacitatea rucsacului m
w – greutatea tuturor obiectelor
p- profiturile tuturor obiectelor

x - informaț iile obiectelor selectate ș i neselectate

0 la n-1 face
Pentru i
X[i]=0
Sfârș it pentru

I=n; j=m
Cât timp( i != 0 ș i j != 0)
{
Dacă(v[I,j] != v[i-1,j])
{ x[i]=1; j=j-w[i] }
}
i=i-1
}
Pentru i 1 până la n face
Dacă(x[i]=1)
obiectul pe care l-am selectat
Sfârș it dacă
Sfârș it pentru

Example :
Având unele articole, împachetează rucsacul pentru a obț ine valoarea totală maximă. Fiecare articol are
o greutate ș i o valoare. Greutatea totală pe care o putem transporta nu este mai mult decât o valoare fixă
numărul W. Aș a că trebuie să luăm în considerare greutăț ile elementelor, precum ș i
valoarea lor.
Item #Weight Value
1 2 12
2 1 10 Capacitatea maximă este adică M=5
3 3 20
4 2 15

89
Sol: profitul optim obț inut este 37 prin selectarea obiectelor 1, 2 ș i 4.

1.4 ALGORITMUL ARBORE DE PONDERI MINIME

Un arbore de acoperire al unui graf este orice arbore care include fiecare vârf din graf. Puț in mai mult
Formal, un arbore de acoperire al unui graf G este un subgraf al lui G care este un arbore ș i conț ine toate
vârfurile lui G. O margine a unui arbore acoperitor se numeș te ramură; o margine în grafic care este
nu face parte din arborele de acoperire se numeș te un chord. Construim arbore de acoperire de fiecare dată când dorim

a găsi o modalitate simplă, ieftină ș i totuș i eficientă de a conecta un set de terminale (calculatoare,
mari, fabrici, etc.). Arborii acoperiț i sunt importanț i din următoarele motive.

Arbore de acoperire minim

Un arbore de acoperire de minimum (MST) al unui graf ponderat G este un arbore de acoperire al lui G al cărui

suma marginilor este greutatea minimă. Cu alte cuvinte, un MST este un arbore format dintr-un subsistem de

marginile într-un graf neorientat dat, cu două proprietăț i:

• se extinde pe grafic, adică, include fiecare

vârful graficului.
• este un minim, adică, greutatea totală a tuturor
marginea este cât mai mică posibil.

Fie G=(V, E) un graf conectat, neorientat unde V este un set de vârfuri (noduri) ș i E
este setul de muchii. Fiecare muchie are o lungime dată, non negativă.

1 ALGORITMUL PRIM'S:

Acest algoritm a fost propus prima dată de Jarnik, dar este în general atribuit lui Prim. Acesta începe de la
un vârf arbitrar (rădăcină) ș i la fiecare etapă, adaugă o nouă ramură (muchie) la arborele existent
construit; algoritmul se opreș te când toate vârfurile din graf au fost atinse.

90
Această strategie este lacomă în sensul că la fiecare pas, arborele parț ial de acoperire este
augmentat cu un vârf care este cel mai mic dintre toate margini adiacente posibile.

Example :

Începe de la un vârf arbitrar (rădăcină). La fiecare etapă, adaugă o nouă ramură (muchie) la
arborele deja construit; algoritmul se opreș te atunci când toate vârfurile din graf au fost
ajuns.

Algoritmulprims(e,cost,n,t)

Să fie (k,l) o margine de cost minim în E;

Mincost :=cost[k,l];

T[1,1]:=k; t[1,2]:=l;

Pentru I:=1 la n fă

Dacă (cost[i,l]<cost[i,k]) atunci near[i]:=l;

Else near[i]:=k;
Near[k]:=near[l]:=0;
Pentru i:=2 până la n-1 face

{
Fie j un index astfel încât near[j]≠0 ș i
Cost[j,near[j]] este minim;
T[i,1]:=j; t[i,2]:=near[j];
Mincost:=mincost+ Cost[j,near[j]];

91
 Aproape[j]:=0;
Pentru k:=0 până la n face

Dacă near((near[k]≠0) ș i (Cost[k,near[k]]>cost[k,j])) atunci

Aproape[k]:=j;
}
Return mincost;

Algoritmul prim va începe cu un arbore care include doar o muchie de cost minim.
al lui G.
•Apoi, muchiile sunt adăugate în copac câte una. următoarea muchie (i,j) care va fi adăugată în
astfel încât I este un vârf inclus în arbore, j este un vârf care nu este încă inclus, iar cost
din (i,j), cost[i,j] este minim dintre toate marginile.
Func ț ionarea primilor va fi explicată prin următorul diagram.

Step 1: Pasul 2:

Pasul 3: Step 4:

Pasul 5: Step 6:

92
 Analysis:

Algoritmul îș i petrece cea mai mare parte a timpului căutând cea mai mică muchie. Aș adar, timpul de
algoritmul depinde în esenț ă de modul în care căutăm această margine.
Metodă simplă
Caută doar cea mai mică muchie căutând în lista de adiacenț ă a vârfurilor în V. În acest
în cazul fiecărei iteraț ii, costul este O(m), generând un timp total de execuț ie de O(mn).

2. ALGORITMUL LUI KRUSKAL:

În algoritmul lui Kruskal, funcț ia de selecț ie alege muchii în ordine crescătoare de

lungime fără a te îngrijora prea mult de conexiunea acestora cu muchiile alese anterior,
cu excepț ia că niciodată să nu formeze un ciclu. Rezultatul este o pădure de arbori care creș te până când totul
copacii dintr-o pădure (toate componentele) se combină într-un singur copac.

• În acest algoritm, un arbore minim de costuri 'T' este construit muchie cu muchie.
• Muchiile sunt luate în considerare pentru incluziunea în 'T' în ordine crescătoare a costului lor.

•O muchie este inclusă în ‘T’ dacă nu formează un ciclu cu o muchie deja în T.

Pentru a găsi arborele minim cu costul de acoperire, muchiile sunt inserate în arbore în ordine crescătoare.
ordinea costului lor

Algoritm:
Algoritmul kruskal(E,cost,n,t)
//E un set de laturi în G are „n” vârfuri.
//cost[u,v] costul muchiei (u,v).t setul de muchii în arborele acoperitor minim de cost
// primul cost este returnat.
{
pentru i=1 până la n fă parent[I]=-1;
I=0;mincost=0.0;
While((I<n-1) ș i (heap-ul nu este gol)) do
{
j=găseș te(n);

93
k=găseș te(v);
dacă(j nu este egal cu k) atunci
{
i=i+1
t[i,1]=u;
t[i,2]=v;
mincost=mincost+cost[u,v];
uniune(j,k);
}
}
daca(i nu este egal cu n-1) atunci scrie(„Niciun arbore de întindere”)
altfel returnează costul minim;
}
Analiză
Complexitatea temporală a algoritmului pentru arborele de acoperire de cost minim în cel mai rău caz este
O(|E|log|E|)
unde E este mulț imea muchiilor lui G.

Exemplu: Funcț ionarea pas cu pas a algoritmului Kurskal.

Pasul 1. În grafic, muchia(g, h) este cea mai scurtă. Fiecare vertex g, fie vertex h ar putea fi
reprezentant. Să alegem vârful g în mod arbitrar.

Pasul 2. Muchia (c, i) creează al doilea arbore. Alegeț i vârful c ca reprezentant pentru
al doilea copac.

94
Pasul 3. Muchia (g, g) este următoarea cea mai scurtă muchie. Adaugă această muchie ș i alege vârful g ca

reprezentant.

Pasul 4. Muchia (a, b) creează un al treilea copac.

Pasul 5. Adăugaț i muchia (c, f) ș i combinaț i cele două arbori. Vârful c este ales ca reprezentant.

Pasul 6. Muchia (g, i) este următoarea cea mai ieftină, dar dacă adăugăm această muchie, ar apărea un ciclu.

creat. Vârful c este reprezentantul ambelor.

Pasul 7. În schimb, adăugaț i muchia (c, d).

95
Pasul 8. Dacă adăugăm muchia (h, i), muchia (h, i) ar forma un ciclu.

Pasul 9. În loc să adăugaț i latura (h, i), adăugaț i latura (a, h).

Pasul 10. Din nou, dacă adăugăm muchia (b, c), ar crea un ciclu. Adăugaț i în schimb muchia (d, e) pentru
completează arborele acoperitor. În acest arbore acoperitor, toate arborii sunt conectaț i, iar vârful c este unică.

reprezentant.

96
 Verifică-ț i progresul

1. Explica problema încărcării containerelor cu un exemplu

2. Discutaț i problema rucsacului 0/1 cu un exemplu
3. Scrie algoritmul lui Prim pentru generarea arborelui de acoperire minimă? Explică-l cu
exemplu.
4. Scrie algoritmul lui Kruskal pentru generarea arborelui minim acoperitor. Explică-l cu
exemplu.

SUMMARY:
Problema încărcării containerelor este de a umple un număr mai mare de containere în navă supusă la
unele constrângeri specificate.
Problema rucsacului constă în selectarea obiectelor din n obiecte care oferă un profit mai mare ș i
în care suma greutăț ii obiectelor selectate nu ar trebui să depăș ească greutatea rucsacului.
Prims ș i Kruskal sunt cele două algoritmi pentru a genera arbori minimi de conexiune. Aș a că
cineva poate traversa cu uș urinț ă întregul graf cu costuri mai mici.

1.13 KEYWORDS
1 Arbore minim de acoperire - acesta este un arbore care constă din toate vârful din grafic cu foarte
un număr mic de muchii ș i de asemenea greutatea totală a arborelui acoperitor este minimă.

1.14 RĂSPUNSURI PENTRU A VERIFICA PROGRESUL TĂU

1. 1.2
2. 1.3
3. 1.4(1)
4. 1.4(2)
1.7 EXERCI ȚII Ș I RĂSPUNSURI LA FINALUL UNITĂ ȚII

13. List out the difference between Prim’s algorithm and Kruskal’s algorithm.
14. Compară problema încărcării containerelor cu problema rucsacului
Answers: SEE
1. 1.4 (1 & 2)

97
 2. 1.2 & 1.3

1.12 LECTURI SUGERATE

1. Introducere în designul ș i analiza algoritmilor de Anany Levitin
2. Analiza ș i proiectarea algoritmilor cu C/C++ - 3rdediț ie de Prof. Nandagopalan
3. Analiza ș i designul algoritmilor de Padma Reddy

4. Chiar, Shimon., "Algoritmi grafici", Editura Ș tiinț elor Computa ț ionale.

98
 MODULUL-4, UNITATEA 1 INTRODUCERE ÎN GRAFURI

Structură
1.0 Obiective
1.1 Grafuri ca structuri de date
1.2 Reprezentarea grafică
Matrice de adiacentă
Lista de adiacen ț ă
1.3 Parcurgerea prin adâncime (DFS)
1.4 Rezumat
1.5 Keywords
1.6 Răspunsuri pentru a verifica progresul tău
1.7 Exerci ț ii finale ș i răspunsuri
1.8 Suggested readings

8.0 OBIECTIVE
La sfârș itul acestei unităț i vei fi capabil să

•Reprezenta ț i graful într-un computer folosind matricea de adiacen ț ă sau adiacen ț a

tip de listă.
•Identifică ce metodă de reprezentare grafică este mai bună ș i când.
•Parcurge ț i graful folosind parcursul DFS ș i complexitatea sa de timp.

8.1 GRAFURI CA STRUCTURI DE DATE

1.1.1 Introduction to graph :

Grafurile sunt o structură folosită pe scară largă în informatică ș i în diferite domenii ale calculatoarelor.

aplicaț ii. Nu spunem structură de date aici ș i vedem diferenț a. Grafurile înseamnă să
stochează ș i analizează metadatele, conexiunile care sunt prezente în date. De exemplu,
considera ț i ora ș ele din ț ara dumneavoastră. Reteaua de drumuri, care le conectează, poate fi
reprezentate ca un grafic ș i apoi analizate. Putem examina dacă o anumită oraș poate fi atins
dintr-o altă parte sau găseș te cea mai scurtă rută între două oraș e.

În primul rând, introducem câteva definiț ii despre grafuri. Apoi, vom arăta,
cum sunt reprezentate grafurile în interiorul unui computer. Apoi poț i trece la grafurile de bază
algoritmi.

Există două seturi importante de obiecte, care specifică graficul ș i structura sa. Primul set
isV, care se numeș te setul de vârfuri. În exemplul cu reț eaua de drumuri, oraș ele sunt vârfuri.

99
Fiecare vârf poate fi desenat ca un cerc cu numărul vârfului în interior.

vârfuri

Următorul set important este E, care se numeș te setul de muchii. E este un subset al V x V. Pur ș i simplu

în termeni de vorbire, fiecare muchie leagă două vârfuri, inclusiv cazul în care un vârf este
conectat la el însuș i (o astfel de muchie se numeș te buclă). Toate grafurile sunt împărț ite în două mari
grupuri: grafuri orientate ș i neorientate. Diferenț a este că muchiile din grafurile orientate,
graficele arc, au o direcț ie. Aceste tipuri de grafice au multe în comun între ele
alte, dar diferenț e semnificative sunt, de asemenea, prezente. Vom accentua ce fel de
grafurile sunt considerate în descrierea particulară a algoritmului. O muchie poate fi trasată ca un
linie. Dacă un graf este orientat, fiecare linie are o săgeată.

graf neorientat graf direcț ionat

Acum, prezentăm câteva definiț ii de bază ale grafurilor.

•Secven ț ă de vârfuri, astfel încât să existe o muchie de la fiecare vârf la următorul în

secvenț ă, se numeș te cale. Primul vârf din cale se numeș te vârful de start; ultimul
vârful din cale este numit vârful final. Dacă vârfurile de start ș i de sfârș it sunt aceleaș i,
Calea este numită ciclu. Calea este numită simplă, dacă include fiecare vârf o singură dată.
Un ciclu se numeș te simplu, dacă include fiecare vârf, cu excepț ia vârfului de început (sfârș it) doar.
odată. Să vedem exemple de traseu ș i ciclu.

100
path (simple) ciclul (simplu)

Ultima definiț ie pe care o dăm aici este un graf ponderat. Grafuri se numesc ponderate, dacă fiecare
marginea este asociată cu un număr real, numit greutatea marginii. De exemplu, în drumul
exemplu de reț ea, greutatea fiecărei drum poate fi lungimea sa sau timpul minim necesar pentru
condu pe drum.

graf ponderat

1.2 Reprezentarea graficelor

Există mai multe moduri posibile de a reprezenta un graf în interiorul computerului. Vom
discută despre două dintre ele: matricea de adiacenț ă ș i lista de adiacenț ă.

a) Matrice de adiacenț ă

Fiecare celulă aijo matrice de adiacentă conț ine 0, dacă există o muchie între i-lea ș i j-lea

101
vârfuri ș i în alte cazuri. Înainte de a discuta despre avantajele ș i dezavantajele acestui
un fel de reprezentare, să vedem un exemplu.

Grafica prezentată de exemplu este nedirecț ionată. Asta înseamnă că matricea sa de adiacenț ă este
simetric. De fapt, în graf neorientat, dacă există o muchie (2, 5) atunci există ș i o
margine (5, 2). Aceasta este, de asemenea, motivul pentru care există două celule pentru fiecare margine în
exemplu. Buclele, dacă sunt permise într-un grafic, corespund elementelor diagonale ale
o matrice de adiacenț ă.

Avantaje. Matricea de adiacenț ă este foarte convenabilă pentru a lucra cu ea. Adăugaț i (eliminaț i) un
o margine poate fi realizată în O(1) timp, acelaș i timp este necesar pentru a verifica dacă există o margine
între două vârfuri. De asemenea, este foarte simplu de programat ș i în toate tutorialele noastre despre grafuri
vom lucra cu acest tip de reprezentare.

Dezavantaje.

Matricea de adiacen ț ă consumă o cantitate uria ș ă de memorie pentru stocarea graficelor mari.
Toate graficele pot fi împărț ite în două categorii, grafice sparse ș i grafice dense. Sparse
ones conț in nu prea multe margini (numărul de margini este mult mai mic decât pătratul de)
numărul de vârfuri, |E| << |V| 2). Pe de altă parte, grafurile dense con ț in
numărul de muchii comparabil cu pătratul numărului de vârfuri. Adiacenț ă
matricea este optimă pentru grafice dense, dar pentru cele rare este superfluă.
Următoarea dezavantajă a matricei de adiacen ț ă este că în multe algoritmi trebuie să
cunoaș te marginile, adiacente vârfului curent. Pentru a scoate în evidenț ă astfel de informaț ii
din matricea de adiacenț ă trebuie să scanezi peste linia corespunzătoare, care
rezultate cu o complexitate de O(|V|). Pentru algoritmi precum DFS sau bazaț i pe acesta, utilizarea de
matricea de adiacenț ă rezultă într-o complexitate generală de O(|V| 2), în timp ce poate fi
reducerea la O(|V| + |E|), când se foloseș te lista de adiacenț ă.
Ultimul dezavantaj, la care vrem să vă atragem aten ț ia, este că adiacen ț a
matricea necesită eforturi mari pentru adăugarea/eliminarea unui vârf. În cazul în care, un graf este

102
 folosit doar pentru analiză, nu este necesar, dar dacă vrei să construieș ti complet
structură dinamică, utilizarea matricei de adiacenț ă o face destul de lentă pentru grafuri mari.

Pe scurt, matricea de adiacenț ă este o soluț ie bună pentru graficele dense, ceea ce implică să aibă
număr constant de vârfuri.

b.) Lista de adiacenț ă

Această formă de reprezentare a grafului este una dintre alternativele la matricea de adiacenț ă.
necesită o cantitate mai mică de memorie ș i, în situa ț ii particulare, chiar poate depă ș i
matrice de adiacenț ă. Pentru fiecare vârf, lista de adiacenț ă stochează o listă de vârfuri, care sunt
adjacent to current one. Let us see an example.

1 4
2 4 5
3 5
4 2 5

Grafic Lista de adiacenț ă

Avantaje. Lista adiacentă ne permite să stocăm graful într-o formă mai compactă decât
matrice de adiacenț ă, dar diferenț a scade pe măsură ce un graf devine mai dens. Următorul
avantajul este că lista adjacentă permite obț inerea listei de vârfuri adiacente în timp O(1),
care este un mare avantaj pentru unele algoritmi.

Dezavantaje.

Adăugarea/îndepărtarea unei muchii din lista de adiacen ț ă nu este atât de u ș oară ca pentru adiacen ț ă.

matrice. Necesită, în medie, O(|E| / |V|) timp, ceea ce poate duce la cubic.
complexitate pentru grafuri dense pentru a adăuga toate muchiile.
•Verificarea, dacă există o muchie între două vârfuri se poate face în O(|E| / |V|) atunci când
lista vârfului adiacente este neordonată sau O(log2(|E| / |V|)) atunci când este sortat. Acest
operaț ia rămâne destul de ieftină.

103
 •Lista adiacentă nu ne permite să facem o implementare eficientă, dacă este dinamică.
schimbarea numărului de vârfuri este necesară. Adăugarea unui nou vârf poate fi făcută în O(V),
dar eliminarea rezultă într-o complexitate O(E).

Concluzie: Lista de adiacenț ă este o soluț ie bună pentru grafuri rare ș i ne permite să facem modificări.
numărul de vârfuri mai eficient, decât dacă ar folosi o matrice de adiacenț ă. Dar totuș i există
soluț ii mai bune pentru a stoca grafuri complet dinamice.

1.3 Algoritmi asociaț i cu grafuri ș i complexităț ile lor de timp

1.3.1 Căutare în adâncime (DFS) pentru grafuri neorientate

Căutarea în adâncime, sau DFS, este o metodă de a parcurge graful. Iniț ial, aceasta
permite vizitarea doar a vârfurilor grafului, dar există sute de algoritmi pentru grafuri,
care se bazează pe DFS. Prin urmare, înț elegerea principiilor căutării în adâncime este
destul de important să avansăm în teoria graficelor. Principiul algoritmului este
destul de simplu: a merge înainte (în profunzime) atâta timp cât exista o astfel de posibilitate, altfel să
contesta

Algoritm
Algoritm: Parcurgerea DFS(G)
//Implementaț i o traversare în adâncime a unui graf
Graf G=<V,E>
Graf G cu vârfurile sale marcate cu numere întregi consecutive în ordinea în care au
a fost întâlnit pentru prima dată de traversarea DFS
Marchează fiecare vârf în V cu 0 ca marcaj al stării „nevizitat”
Numără 0
Pentru fiecare vârf v în V face
Dacă v este marcat cu 0
dfs(v)
//sfârș it explorare DFS

Rutina
dfs (v)
//vizitează recursiv toate vârfurile nevizitate conectate la vârful v ș i le alocă
numerele în ordinea în care sunt întâmpinate prin variabila globală count
Numără Numără+1
Marchează v cu numărătoarea
Pentru fiecare vârf w din V adiacent lui v, fă

104
 Dacă w este marcat cu 0
Dfs(w)
//sfârș it dfs

În DFS, fiecare vârf are trei culori posibile care reprezintă starea sa:

alb: vârful nu este vizitat;

gray: vertex is in progress;

negru: DFS a terminat de procesat vârful.

Notă. Pentru majoritatea algoritmilor, clasificarea booleană nevizitat / vizitat este suficientă, dar
aratăm cazul general aici.

Iniț ial, toate vârfurile sunt albe (nevizitate). DFS începe într-un vârf arbitrar ș i rulează ca
următoarele:

1. Marchează vârfurile de culoare gri (vizitate).

2. Pentru fiecare muchie (u, v), unde u este alb, rulează căutare în adâncime pentru u recursiv.
3. Marchează vârful de culoare neagră ș i revino la părinte.

Exemplu: Parcurge ț i un graf prezentat mai jos, folosind DFS. Începe ț i de la un vârf cu
numărul 1.

Graf sursă.

105
Marchează un vârf ca fiind gri.

Există o muchie (1, 4) ș i un vârf 4 care nu a fost vizitat.

Mergi acolo.

Marcaț i vârful ca fiind gri.

106
Există oMuchie(4, 2)ș i vârful a2 este nevizitat.
Du-te acolo.

Marchează vârful ca fiind gri.

Există o arie (2, 5) ș i un vârf 5 este nevizitat.

Du-te acolo.

107
Marchează vârful5 ca fiind gri.

There is an edge(5, 3)and a vertex3is unvisited.

Du-te acolo.

Marchează vârful 3 ca gri.

108
Nu există căi pentru a merge de la vârful 3. Marcheză-l
ca negru ș i să revină la vârful 5.

Există o muchie(5, 4), dar vârful 4 este gri.

Nu există nicio cale de a ajunge de la vârful 5. Marchează-l

ca negru ș i retrage-te la vertex2.

109
Nu mai sunt margini, adiacente cu
vertex2. Marcaț i-l ca negru ș i reveniț i la
vertex4.

Există o muchie (4, 5), dar vârful 5 este negru.

Nu mai sunt margini, adiacente la

vertex4. Marchează-l ca negru ș i întoarce-te la
vârful1.

110
 Nu mai există margini, adiacente la
vertex1. Marchează-l ca negru. DFS s-a terminat.

După cum puteț i observa din exemplu, DFS nu trece prin toate muchiile. Vârfurile ș i
muchiile, pe care căutarea în adâncime le-a vizitat, sunt un arbore. Acest arbore conț ine toate vârfurile de
graful (dacă este conectat) ș i se numeș te arbore de acoperire al grafului. Acest arbore exact
corespunde apelurilor recursive ale DFS.

Dacă un grafic este deconectat, DFS nu va vizita toate vârfurile sale. Pentru detalii, vezi găsirea
algoritmul componentelor conectate.

Analiza complexităț ii

Presupuneț i că graful este conectat. Căutarea în adâncime vizitează fiecare vârf din graf ș i
verifică fiecare muchie a sa. Prin urmare, complexitatea DFS este O(V + E). A ș a cum a fost
aș a cum s-a menț ionat anterior, dacă o matrice de adiacenț ă este folosită pentru reprezentarea unui graf, atunci toate

margini, adiacente unui vârf nu pot fi găsite eficient, ceea ce duce la O(V2) complexitate.

Verifică-ț i progresul

1. Scrie un algoritm pentru parcurgerea DFS ș i analizează-i complexitatea.

2. Care sunt diferitele moduri de a reprezenta un grafic, explică-l cu un exemplu.

3. Care sunt avantajele ș i dezavantajele matricei de adiacen ț ă ș i listei de adiacen ț ă
metoda de reprezentare a graficului.

1.4 SUMMARY:
Un graf poate fi reprezentat în două moduri, adică matricea de adiacenț ă ș i metoda listei de adiacenț ă.

111
 Matricea de adiacenț ă este o soluț ie bună pentru grafuri dense, iar lista de adiacenț ă este bună pentru

graf rar
Căutarea în adâncime (DFS) este un algoritm pentru traversarea sau căutarea unui arbore, structură de arbore,

sau grafic. Se începe de la rădăcină (selectând un anumit nod ca rădăcină în cazul graficului) ș i
explorează cât mai departe posibil pe fiecare ramură înainte de a reveni.

1.15 KEYWORDS
Grafic: un grafic este o reprezentare abstractă a unui set de obiecte unde anumite perechi de
obiectele sunt conectate prin legături. Obiectele interconectate sunt reprezentate de
abstrac ț ii matematice numite vârfuri ș i legăturile care conectează unele perechi de
vârful sunt numite margini.
Digraful este un grafic cu direcț ii pe marginile sale.

1.16 RĂSPUNSURI PENTRU A-ȚI VERIFICA PROGRESUL

1. 1.3.1
2. 1.2.
3. 1.2
1.7 EXERCI ȚII Ș I RĂSPUNSURI LA FINA UNITĂ ȚII

15. Aplică o parcugere DFS pentru un grafic având o matrice de adiacenț ă

Matricea 1
16. a.) Scrie graficul echivalent pentru matricea de mai sus (adică matricea1).
b.) Reprezentaț i matricea1 sub formă de listă de adiacenț ă.

[Link] a note on path , weighted graph, cycle, loop.

Answers: SEE

112
 1. 1.3.1
2. 1.2
3. 1.1

1.13 LECTURI SUGERATE

1. Introducere în designul ș i analiza algoritmilor de Anany Levitin
2. Analiza ș i proiectarea algoritmilor cu C/C++ - 3rdediț ie de Prof. Nandagopalan
3. Analiza ș i proiectarea algoritmilor de către Padma Reddy

4. Even, Shimon., "Algoritmi de grafuri", Editura Ș tiinț a Computerelor.

5. Structuri de date, Algoritmi ș i aplicaț ii în C++ -2ndediț ie, De Sartaj Sahni.

113
114