1 Algoritmi Greedy

1.1 Paradigme de proiectare a algoritmilor

Conform DEX, paradigmă ı̂nseamnă model sau exemplu. O paradigmă de proiectare a algo-
ritmilor este o metodă generală de a rezolva o clasă de probleme. Dintre cele mai importante
paradigme de proiectare a algoritmilor fac parte divide et impera (vezi cursul Structuri de Date),
greedy (acest curs), programare dinamică (cursurile următoare) s, i backtracking.

1.2 Probleme de optimizare

Paradigma greedy este folosită ı̂n special pentru a rezolva probleme de optimizare, adică prob-
leme ı̂n care datele de intrare au o formă oarecare, iar cerint, a problemei presupune maximizarea
sau minimizarea unei anumite cantităt, i, respectând anumite constrângeri:
Problemă de optimizare:
Input: . . .
Output: cel mai mare/cel mai mic număr cu proprietatea că . . .
Un exemplu de problemă de optimizare este găsirea celui mai scurt drum ı̂ntre două noduri
ı̂ntr-un graf:
Problema celui mai scurt drum ı̂ntr-un graf:
Input: Un graf G = (V, E) s, i două noduri s, t ∈ V .
Output: Lungimea n a celui mai scurt drum de la s la t ı̂n graf.
Într-o problemă de optimizare, este posibil ca datele de ies, ire să cont, ină informat, ii supli-
mentare. De exemplu, pentru problema celui mai scurt drum ı̂ntr-un graf, putem cere s, i drumul
de lungime minimă (nu doar lungimea acestuia:
Problema celui mai scurt drum ı̂ntr-un graf (cu output explicit):
Input: Un graf G = (V, E) s, i două noduri s, t ∈ V .
Output: v1 , . . . , vn - cel mai scurt drum ı̂ntre s s, i t.
În contextul acestei probleme, orice drum ı̂ntre s s, i t se numes, te solut, ie, iar un drum ı̂ntre s s, i
t mai scurt decât toate celelalte drumuri ı̂ntre s s, i t este solut, ia optimă.
În general, o problemă de optimizare cere să alegem din mult, imea de solut, ii posibile (ı̂n exem-
plul de mai sus, mult, imea de drumuri ı̂ntre s s, i t) solut, ia optimă (cea de cost minim, sau cea de
câs, tig maxim – ı̂n funct, ie de cerint, a problemei).
O problemă de optimizare este rezolvată corect de un algoritm dacă aceasta produce ı̂n toate
cazurile o solut, ie optimă.
Exerciţiul 1. Dat, i alte exemple de probleme de optimizare pe care le-at, i ı̂ntâlnit până acum.

1.3 Paradigma greedy

Greedy este una dintre cele mai simple paradigme de proiectare a algoritmilor. Multe probleme
de optimizare pot fi rezolvate eficient folosind algoritmi greedy. Algoritmii greedy sunt de obicei
foarte simplu de implementat, dar nu neapărat simplu de demonstrat.
Pentru alte probleme de optimizare, algoritmii greedy nu produc solut, ia optimă. În aceste
cazuri, există două strategii:

1. Dacă se dores, te o solut, ie optimă, se caută o altă metodă de rezolvare decât greedy (folosind,
e.g., backtracking sau programare dinamică);

2. Dacă diferent, a dintre răspunsul optim s, i răspunsul produs de algoritmul greedy este tolera-
bilă ı̂n practică, se poate folosi algoritmul greedy (algoritmul produce o solut, ie aproximativă,
ı̂n acest caz se numes, te algoritm de aproximare).

1
 1.4 Exemple de probleme care pot fi rezolvate prin strategii greedy
Algoritmii de tip greedy (lacom) sunt aplicat, i deseori ı̂n practică, inclusiv ı̂n viat, a de zi cu
zi. De exemplu, dacă plecat, i ı̂ntr-o excursie s, i vă pregătit, i bagajul, vet, i introduce ı̂ntâi ı̂n bagaj
lucrurile mari s, i apoi cele mici. Această strategie vă ajută să folosit, i spat, iul din bagaj ı̂n mod
eficient.

1.4.1 Bin-packing
Problemele computat, ionale ı̂n care la intrare se dau un container s, i o mult, ime de obiecte s, i la ies, ire
se cere o modalitate de a aranja obiectele ı̂n container se numesc probleme de tip bin-packing s, i
apar ı̂n diferite domenii.
De exemplu, ı̂n contextul jocurilor 2D, mai multe sprite-uri (imagini mici (e.g. 128x128 sau
64x64) sau serii de imagini mici reprezentând un personaj sau un alt element grafic din joc) trebuie
as, ezate fără să se suprapună ı̂ntr-un număr cât mai mic de imagini de dimensiuni mai mari (e.g.
1024x1024) care pot fi ı̂ncărcate de placa video ca texturi s, i apoi afis, ate pe ecran cât mai eficient.
Folosirea unui număr cât mai mic de texturi cres, te performant, a jocului s, i din acest motiv este de
dorit să “ı̂nghesuim” cât mai multe sprite-uri ı̂ntr-o singură textură. Cele mai multe framework-uri
pentru programarea jocurilor cont, in implementarea unor algoritmi pentru sprite-packing (căutat, i
“sprite packer” folosind un motor de căutare).
În cele mai multe cazuri, pentru problemele de tip bin-packing nu se cunoas, te o rezolvare
polinomială s, i din acest motiv se preferă un algoritm greedy care calculează o solut, ie aproximativă.

1.4.2 Plata unei sume folosind număr minim de bancnote

Un alt exemplu de problemă unde aplicăm un algoritm greedy este plata unei sume de bani
folosind un număr minim de bancnote. De exemplu, pentru a plăti (exact) 86 de lei, folosim 6
bancnote: una de 50 de lei, trei de 10 lei, una de 5 lei s, i una de 1 leu. Orice altă metodă de a plăti
suma de 86 de lei foloses, te mai multe bancnote. Formal, problema poate fi exprimată astfel:
Problema plăt, ii cu număr minim de bancnote.
Input: un număr natural n – suma ce trebuie plătită
Output: numerele n500 , n200 , n100 , n50 , n10 , n5 , n1
(ni - câte bancnote de i RON folosesc), astfel ı̂ncât
Σi∈{500,200,100,50,10,5,1} ni să fie minimă s, i
n = Σi∈{500,200,100,50,10,5,1} i × ni .
Strategia greedy pe care o folosim este să plătim mereu cea mai mare bancnotă care este mai
mică decât suma pe care o avem de achitat. De exemplu, pentru 86 de lei, cea mai mare bancnotă
este de 50 de lei. Rămân de achitat 36 de lei. Cea mai mare bancnotă este de 10 lei. Rămân de
achitat 26 de lei. (...).
Se poate demonstra că această strategie conduce la un număr minim de bancnote, pentru
sistemul de bancnote pe care ı̂l avem ı̂n t, ară (bancnote de 500, 200, 100, 50, 10, 5, 1). Pentru alte
sisteme de bancnote, strategia greedy nu conduce tot timpul la o solut, ie optimă.

1.4.3 Problema select, iei activităt, ilor

Azi, un student poate participa la una sau mai multe activităt, i. De exemplu:

curs de la 10 la 12 poate participa la cursul PA;

codecamp de la 9 la 17 poate participa la CodeCamp;
teatru de la 18 la 20 poate merge la teatru;
film de la 21 la 22 poate merge la film;

club de la 19 la 24 poate merge ı̂n club.

2
 Scopul studentului este să participe la cât mai multe activităt, i (dar trebuie să participe la
fiecare de la ı̂nceput la sfârs, it s, i nu poate fi ı̂n două locuri ı̂n acelas, i timp). Ce activităt, i trebuie
să aleagă? În exemplul de mai sus, studentul poate participa la maxim 3 activităt, i: curs, teatru,
film sau codecamp, teatru, film.
Formal, problema select, iei activităt, ilor este următoarea:
Input: n - numărul de activităt, i
s[0..n − 1] - un tablou care cont, ine timpul de ı̂nceput al activităt, ilor
f [0..n − 1] - un tablou care cont, ine timpul de final al fiecărei activităt, i
a.ı̂. s[i] < f [i] pentru orice 0 ≤ i ≤ n − 1 s, i
f este ı̂n ordine crescătoare.
Output: A ⊆ {0, . . . , n − 1}
A este o mult, ime de activităt, i care nu se suprapun
A este de cardinal maxim.
Considerăm că activitatea i ı̂ncepe exact ı̂n momentul si s, i se termină put, in ı̂nainte de momen-
tul fi . Cu alte cuvinte, activitatea i durează de la si (inclusiv) până la fi (exclusiv). Astfel, două
activităt, i i, j se suprapun dacă [si , fi ) ∩ [sj , fj ) ̸= ∅ (remarcat, i faptul că intervalele sunt ı̂nchise la
stânga s, i deschise la dreapta).
Exerciţiul 2. Arătat, i că două activităt, i i, j nu se suprapun (sunt compatibile ı̂ntre ele) dacă s, i
numai dacă si ≥ tj sau sj ≥ ti .
De exemplu, pentru n = 5 s, i pentru tablourile s s, i f date mai jos:

i 0 1 2 3 4
s[i] 10 9 18 21 19
f [i] 12 17 20 22 24,

un răspuns corect este: A = {0, 2, 4}.

IDEE 1.
O primă idee de rezolvare a problemei printr-o strategie greedy este să aleg activităt, ile ı̂n
ordinea duratei lor. De exemplu, ı̂n exemplul de mai sus, aleg activitatea 4 deoarece durează 1
oră, apoi activitatea 1 s, i activitatea 3, deoarece durează amândouă 2 ore. Totus, i, această strategie
nu conduce ı̂n general la o solut, ie optimă. De exemplu, pentru următoarele activităt, i:

i 0 1 2
s[i] 9 15 17
f [i] 16 18 23,

strategia descrisă mai sus alege activitatea 1, care are durată de 3 ore. Dar activitatea 1 se
suprapune atât cu 0 cât s, i cu 2 s, i deci nu mai putem alege nicio altă activitate. Solut, ia {1} nu
este optimă, deoarece solut, ia {0, 2} cont, ine mai multe activităt, i.
IDEE 2.
În continuare, vom vedea o strategie greedy pentru problema select, iei activităt, ilor care conduce
ı̂n toate cazurile la solut, ia optimă.
Strategia pe care o vom folosi:

1. ı̂ncepem cu mult, imea A = ∅;

2. dintre activităt, ile care au rămas, alegem activitatea i care se termină cel mai devreme
(intuitiv, deoarece ı̂mi lasă timp mai mult pentru următoarele activităt, i);
3. adăugăm i la A;
4. s, tergem i s, i toate celelalte activităt, i care se suprapun cu i din lista de activităt, i disponibile;

5. repetăm procesul dacă mai sunt activităt, i disponibile.

3
 În pseudocod, strategia de mai sus poate fi descrisă astfel:

• A=∅ (mult, imea de activităt, i selectate)

• time = 0 (timpul ı̂ncepând cu care sunt disponibil)
• for i = 0 to n − 1 (activităt, ile sunt deja ı̂n ordine descrescătoare a timpului de final)

– if s[i] >= time (sunt disponibil pentru activitatea i)

∗ A = A ∪ {i} (selectez activitatea i)
∗ time = f [i] (marchez că nu pot accepta activităt, i mai devreme de f [i])

Întrebare. Strategia de rezolvare IDEE 1 nu produce tot timpul solut, ia optimă. Cum pot
fi sigur ca strategia descrisă ı̂n IDEE 2 produce tot timpul solut, ia optimă? Răspuns. Putem
demonstra acest lucru.
În primul rând, vom arăta că, pentru orice mult, ime S de activităt, i, există o submult, ime S ′ de
activităt, i care:
• cont, ine doar activităt, i compatibile ı̂ntre ele (care nu se suprapun),
• este de cardinal maxim s, i
• cont, ine activitatea care se termină cel mai devreme din S.
Cu alte cuvinte, fără a pierde din generalitate, ı̂ntr-o mult, ime de cardinal maxim de activităt, i
compatibile ı̂ntre ele se poate alege activitatea care se termină cel mai devreme:
Lemă 1 (Lema de alegere lacomă). Fie S ⊆ {0, 1, . . . , n − 1} o mult, ime nevidă de activităt, i (nu
neapărat compatibile ı̂ntre ele).
Fie x activitatea din S care se termină cel mai devreme.
Există o submult, ime S ′ ⊆ S a mult, imii S care:

• cont, ine doar activităt, i compatibile ı̂ntre ele;

• este de cardinal maxim (dintre toate submult, imile lui S de activităt, i compatibile ı̂ntre ele);
• cont, ine activitatea x: x ∈ S ′ .

Proof. Fie S ′′ o submult, ime oarecare a lui S de activităt, i compatibile ı̂ntre ele de cardinal maxim.
Nu s, tim dacă x ∈ S ′′ .
Fie y activitatea din S ′′ care se termina cel mai devreme.
Alegem S ′ = (S ′′ \ {y}) ∪ {x}.
Observăm că:

• S ′ are acelas, i cardinal cu S ′′ ;

• S ′ cont, ine x.

Mai avem de arătat că S ′ cont, ine doar activităt, i compatibile ı̂ntre ele:
Cum y este activitatea care se termină cel mai devreme din S ′′ s, i cum S ′′ cont, ine doar activităt, i
compatibile ı̂ntre ele, rezultă că ∀z ∈ S ′′ \ {y}, f [y] ≤ s[z]. Dar y ∈ S ′′ , S ′′ ⊆ S s, i x ∈ S este
activitatea din S care se termină cel mai devreme. Deci x se termină ı̂naintea lui y: f [x] ≤ f [y].
Rezultă că ∀z ∈ S ′′ \ {y}, f [x] ≤ s[z], ceea ce ı̂nseamnă că x este compatibilă cu toate activităt, ile
din S ′′ \ {y}, deci S ′ cont, ine doar activităt, i compatibile ı̂ntre ele.
Am arătat că, fără a pierde optimalitatea, putem alege activitatea care se termină cel mai
devreme.
Pentru a arăta că algoritmul, ı̂n ı̂ntregimea sa, produce o solut, ie optimă, a mai rămas de arătat:
combinarea activităt, ii care se termină cel mai devreme cu restul activităt, ilor alese de algoritm este
o solut, ie optimă. Pentru a formaliza acest lucru, avem nevoie de not, iunea de subproblemă:

4
Definiţie 1. În contextul problemei select, iei activităt, ilor, o subproblemă este o submult, ime de
activităt, i.
Example 1. Pentru instant, a n = 5 s, i pentru tablourile s s, i f date mai jos:

i 0 1 2 3 4
s[i] 10 9 18 21 19
f [i] 12 17 20 22 24,

subproblemele sunt ı̂n număr de 25 = 32 s, i includ: ∅, {0, 2, 3, 4}, {1, 2, 3, 4}, {0, 2, 4}, {0, 1, 2, 3, 4}.
Lemă 2 (Proprietatea de substructură optimă). Fie S o subproblemă nevidă s, i x ∈ S activitatea
aleasă prin strategia greedy (cea care se termină cel mai devreme). Fie A ⊆ S o submult, ime de
activităt, i compabilite ı̂ntre ele de cardinal maxim care cont, ine x (x ∈ A – prin lema de alegere
greedy, această mult, ime A există).
Fie B = A \ {x}. Atunci B este o solut, ie optimă pentru S \ {z | z se suprapune peste x}.
Proof. Presupunem (prin reducere la absurd) că există o solut, ie C mai bună decât B pentru
subproblema S \ {x}. Atunci C ∪ {x} ar fi o solut, ie pentru S mai bună decât A, ceea ce contrazice
optimalitatea lui A.

Demonstrat, ia proprietăt, ii de substructură optimă este ı̂n general foarte simplă. În general,
proprietatea de substructură optimă indică faptul că subsolut, iile unei solut, ii optime sunt la rândul
lor solut, ii optime pentru subprobleme.
Prin induct, ie, folosindu-ne de cele două leme de mai sus, este us, or de demonstrat corectitudinea
algoritmului:
Teoremă 1. Strategia greedy de mai sus produce o solut, ie optimă.
Proof. Vom proceda prin induct, ie după mult, imea S de activităt, i disponibile.
Prin lema de alegere greedy, există o solut, ie optimă A pentru S astfel ı̂ncât x ∈ A. Prin ipoteza
de induct, ie, algoritmul găses, te o solut, ie optimă B pentru subproblema T = {i ∈ S | s[i] ≥ f [x]}
(T este strict inclusă ı̂n S). Prin lema de substructură optimă, {x} ∪ A este o solut, ie optimă (cea
găsită de algoritm).

O demonstrat, ie alternativă, care poate fi mai simplu de ı̂nt, eles fiindcă pasul inductiv este
explicitat:
Proof. Fie s1 , . . . , sk lista de activităt, i selectată de algoritmul greedy. Presupunând că nu e optimă,
căutăm cel mai mic număr j ∈ {1, 2, 3, . . .} astfel ı̂ncât să existe o listă optimă de activităt, i care
cont, ine primele j − 1 activităt, i din s1 , . . . , sn s, i apoi alte activităt, i:

s1 , . . . , sj−1 , tj , . . . , tm .(tj ̸= sj )

Presupunem că activităt, ile din solut, ia optimă s1 , . . . , sj−1 , tj , . . . , tm sunt ordonate crescător
(fiind compatibile ı̂ntre ele, nu contează dacă după timpul de ı̂nceput sau după cel de sfârs, it –
obt, inem aceeas, i ordine).
Prin definit, ie, sj este compatibilă cu s1 , . . . , sj−1 s, i ı̂ncepe mai devreme decât tj . Deci
s1 , . . . , sj−1 , sj , tj+1 , . . . , tm ar fi s, i ea o solut, ie optimă, contrazicând minimalitatea lui j.

1.4.4 Algoritmii greedy

Algoritmii greedy

1. Algoritmii greedy = secvent, ă de alegeri locale, alegeri care par a fi cele mai bune ı̂n momentul
respectiv;

5
 2. Odată făcută o alegere, nu ne putem răzgândi.
3. Câteodată această solut, ie conduce la un optim global (e.g. problema select, iei activităt, ilor);
alteori nu (e.g. problema discretă a rucsacului).

Algoritmii greedy - proces de proiectare

1. Identificăm subprobleme ale problemei de optimizare (e.g. Stime = {i | s[i] ≥ time} astfel
ı̂ncât o alegere greedy ı̂ntr-o subproblemă să conducă la o altă subproblemă).
2. (greedy-choice property) Arătăm că există o solut, ie optimă a problemei init, iale care foloses, te
alegerea greedy.
3. (optimal substructure property) Arătăm că dacă facem o alegere greedy, combinat, ia dintre
alegerea greedy s, i o solut, ie optimă pentru subproblema rezultată este o solut, ie optimă pentru
problema init, ială.

1.4.5 Problema rucsacului - varianta continuă

Problema rucsacului - varianta continuă
Un hot, a spart un magazin s, i a găsit n bunuri. Al i-lea bun valorează vi lei s, i cântăres, te wi
kilograme. Hot, ul are un rucsac care poate să ducă cel mult W kilograme de bunuri. Orice bun
poate fi sect, ionat iar valoarea unei părt, i este proport, ională cu dimensiunea acesteia (e.g. jumătate
dintr-un obiect cu vi = 10 s, i wi = 6 cântăres, te 3 kg s, i valorează 5 lei). Hot, ul vrea să maximizeze
valorea obiectelor pe care le va pune ı̂n rucsac.

Problema rucsacului - formalizare varianta continuă

Input: n, v[0..n − 1], w[0..n − 1], W , toate numere naturale
Output: p[0..n − 1], p[i] ∈ [0, 1] astfel ı̂ncât:
1. Σi p[i]w[i] ≤ W (părt, ile alese ale obiectele ı̂ncap ı̂n rucsac)
2. Σi p[i]v[i] este maxim (valoarea părt, ilor este maximă)

Problema rucsacului - exemplu instant, ă

Avem n = 3 obiecte:

i 0 1 2
w[i] 1 2 3
v[i] 10 15 20
Rucsacul are capacitate de W = 5 kg.
O solut, ie optimă pentru varianta continuă:
1. iau 100% din primul obiect (deci p[0] = 1). Câs, tig: 1 × 10 = 10, capacitate rămasă: 5 − 1 = 4
kg.
2. iau 100% din al doilea obiect (deci p[1] = 1). Câs, tig: 10 + 1 × 15 = 25, capacitate rămasă:
4 − 2 = 2 kg.
3. iau 2/3 din al treilea obiect (deci p[2] = 0.66 . . .). Câs, tig: 25 + 2/3 × 20 = 38.33 . . ..
O abordare greedy care conduce la solut, ia optimă este să alegem cât mai mult din obiectul cu
câs, tig unitar (câs, tig / kilogram) cel mai mare.
Exerciţiul 3. Identificat, i subproblemele pentru problema rucsacului - varianta continuă.
Enunt, at, i s, i demonstrat, i lema de alegere greedy.
Enunt, at, i proprietatea de substructură optimă (s, i demonstrat, i-o, dar demonstrat, ia va fi sur-
prinzător de simplă).

6
Problema rucsacului - varianta discretă
Un hot, a spart un magazin s, i a găsit n bunuri. Al i-lea bun valorează vi lei s, i cântăres, te wi
kilograme. Hot, ul are un rucsac care poate să ducă cel mult W kilograme de bunuri. Niciun
bun nu poate fi sect, ionat - obiectul i trebuie furat integral sau deloc. Hot, ul vrea să
maximizeze valorea obiectelor pe care le va pune ı̂n rucsac.

Problema rucsacului - formalizare varianta discretă

Input: n, v[0..n − 1], w[0..n − 1], W , toate numere naturale
Output: p[0..n − 1], p[i] ∈ {0, 1} astfel ı̂ncât:

1. Σi p[i]w[i] ≤ W (obiectele ı̂ncap ı̂n rucsac)

2. Σi p[i]v[i] este maxim (valoarea obiectelor este maximă)

Problema rucsacului - exemplu instant, ă

Avem n = 3 obiecte:

i 0 1 2
w[i] 1 2 3
v[i] 10 15 20
Rucsacul are capacitate de W = 5 kg.
O solut, ie optimă pentru varianta discretă:

1. nu iau primul obiect (p[0] = 0);

2. iau al doilea obiect (p[1] = 1);

3. iau al treilea obiect (p[2] = 2).

Abordările greedy nu produc solut, ii optime pentru varianta discretă (vezi capitolele următoare:
programare dinamică, backtracking).

1.4.6 Problema codurilor Huffman

Motivat, ie
Să presupunem că avem un fis, ier care cont, ine 100 de caractere. Caracterul a apare de 45 de
ori, b de 30 de ori, c de 10 ori s, i d de 15 ori.
Fis, ierul init, ial ocupă 100 ∗ 8 = 800 de bit, i.
Deoarece ı̂n fis, ier apar doar caracterele a, b, c, d, putem comprima fis, ierul ı̂nlocuind fiecare
aparit, ie a lui a cu secvent, a de bit, i 00, b cu 01, c cu 10 s, i d cu 11.
Obt, inem ı̂n acest fel 100 ∗ 2 = 200 de bit, i.
Se poate obt, ine o compresie mai bună? Da, folosind coduri de lungime variabilă: a = 1, b = 01,
c = 000, d = 001. Fis, ierul comprimat este reprezentat acum prin 1∗45+2∗30+3∗10+3∗15 = 180
de bit, i (90% din dimensiunea obt, inută folosind prima codare).

Coduri prefix
Orice astfel de cod se poate reprezenta ı̂n mod unic printr-un arbore binar cu n frunze:

7
 0 1

a
0 1

b
0 1

c d

Formalizarea problemei
Input: n - numărul de caractere distincte; c[0..n − 1] - numărul de aparit, ii ale fiecărui caracter.
Output: un arbore binar care reprezintă codul prefix optim.
Exemplu: dacă n = 4 s, i c = [45, 30, 15, 10], atunci arborele precedent este un răspuns corect
(a = 1, b = 01, c = 000, d = 001).
Ideea: combină caracterele cu frecvent, ele cele mai reduse (pe tablă).

Algoritmul greedy pentru coduri prefix

1. Q = ∅ (coadă cu prioritate)
2. for i = 0 to n − 1
[Link](info : i, frec : c[i], left : null, right : null)
3. for i = 0 to n − 2
x = new()
[Link] o = −1
[Link] = [Link]()
[Link] = [Link]()
[Link] = [Link] + [Link]
[Link](x)
4. return [Link]()

Corectitudinea s, i analiza algoritmului

1. (Proprietatea de alegere greedy) Există un cod optim ı̂n care ultimele două caractere dpdv
al frecvent, ei au aceeas, i lungime s, i diferă doar ı̂n ultimul bit.
2. (Proprietatea de substructură optimă) Fie x, y cele două caractere cu frecvent, a cea mai mică.
Fie z un nou caracter astfel ı̂ncât c[z] = c[x] + c[y]. Fie T arborele binar care determină
codul optim pentru Σ \ {x, y} ∪ {z} s, i T ′ arborele binar obt, inut din T prin ı̂nlocuirea lui z
cu un nou nod având copiii x s, i y. Atunci T ′ este optim pentru Σ.
3. Timp de rulare: O(nlogn), dacă coada cu prioritate este implementată printr-un heap binar.

8
1.4.7 Matroizi
Matroid
Mult, i algoritmi de tip greedy pot fi demonstrat, i folosind teoria matroizilor.
Definiţie 2. Un matroid este o pereche M = (S, I) cu proprietăt, ile:

1. S este o mult, ime finită

2. (ereditate) I este o mult, ime nevidă de submult, imi ale lui S (numite mult, imi independente)
s, i

dacă B ∈ I s, i A ⊆ B, atunci A ∈ I.

3. (interschimbare) dacă A ∈ I, B ∈ I s, i |A| < |B|, atunci există x ∈ B \ A astfel ı̂ncât

A ∪ {x} ∈ I.

Exerciţiul 4. Demonstrat, i că ∅ ∈ I (Hint: folosit, i proprietatea de ereditate).

Matroid - exemplu
Fie G = (V, E) un graf s, i MG = (SG , IG ) definit astfel:

1. SG = E, muchiile grafului
2. A ⊆ E ∈ I ddacă A nu cont, ine ciclu.

Exerciţiul 5. Arătat, i că MG este matroid.

Exerciţiul 6. Arătat, i că, dacă la itemul 2 cerem ca A să fie arbore, MG nu este matroid.
Exerciţiul 7. Arătat, i că orice mult, ime maximală (dpdv al incluziunii) din I are acelas, i cardinal.

Matroid ponderat
Fie M = (S, I).
Fie w : S → N o funct, ie care asociază fiecărui element x din S o pondere w(x).
Funct, ia w se extinde la mult, imi A ⊆ S astfel: w(A) = Σx∈A w(x).
Teoremă 2. Dacă M este matroid, atunci există un algoritm greedy pentru găsirea unei mult, imi
independente de pondere maximă.

Algoritmul greedy (general pentru matroizi)

1. A = ∅ (ı̂ncep cu mult, imea vidă)

2. sortează M.S ı̂n ordine descrescătoare a ponderilor
3. for each x ∈ M.S (ı̂n ordine descrescătoare)

• if A ∪ {x} ∈ I
A = A ∪ {x}

Teoremă 3. Algoritmul găses, te o mult, ime independentă de pondere maximă.

Pentru a demonstra teorema de mai sus, este suficient să arătăm că matroizii det, in cele două
proprietăt, i prin care am demonstrat corectitudinea algoritmilor greedy:
Lemă 3 (Proprietatea de alegere greedy pentru matroizi ponderat, i). Fie M = (S, I) un matroid.
Fie w : S → N funct, ia de ponderare. Fie x cel mai mare (dpdv al funct, iei de ponderare) element
din S astfel ı̂ncât {x} ∈ I (mult, imea singleton alcăuită doar din x este independentă).
Atunci există o submult, ime optimă (dpdv al funct, iei de ponderare) A ⊆ S astfel ı̂ncât x ∈ A.

9
Lemă 4 (Proprietatea de substructură optimă). Fie x primul element ales de algoritm pentru
matroidul M = (S, I).
Fie matroidul M ′ = (S ′ , I ′ ), definit astfel:

• S ′ = {y ∈ S | {x, y} ∈ I};
• I ′ = {B ⊆ S \ {x} | B ∪ {x} ∈ I}.

Fie A solut, ia optimă găsită de algoritm pentru matroidul M (x ∈ A). Atunci A \ {x} este
solut, ie optimă pentru M ′ .

1.4.8 Problema APM

Problema arborelui part, ial de cost minim
Input: un graf G = (V, E) conex, fiecare muchie e ∈ E având un cost l(e)
Output: un arbore G = (V, A), astfel ı̂ncât suma muchiilor arborelui să fie de cost minim.
Algoritmul lui Kruskal, pe care l-at, i discutat la liceu, ı̂ncepe cu mult, imea vidă de muchii s, i
procesează muchiile ı̂n ordin crescătoare a costurilor. Dacă adăugarea unei muchii nu produce
ciclu, atunci aceasta este adăugată la solut, ie. La final, mult, imea de muchii
Studii de caz selectate va forma
Arborele parţial de cost un
minim
arbore. Iată o posibilă execut, ie a algoritmului lui Kruskal pentru graful ce urmează:
Algoritmul lui Kruskal
Algoritmul lui Kruskal - instant, a

10
1 2 1 2

20
20 30

50
30
3 4 3 4

40
10

5 5

Algoritmul lui Kruskal - pasul 1

D. Lucanu (FII - UAIC) Algoritmi greedy PA 2014/2015

10
 Studii de caz Arborele parţial de cost minim

Algoritmul lui Kruskal

10
1 2 1 2

20
20 30

50
30
3 4 3 4

40
10

5 5
Studii de caz Arborele parţial de cost minim

Algoritmul lui Kruskal

Algoritmul lui Kruskal - - pasul
D. Lucanu (FII UAIC) 2 Algoritmi greedy PA 2014/2015 38 / 42

10 10
1 2 1 2

20
20 30

50
30
3 4 3 4

40
10

5 5

Studii de caz Arborele parţial de cost minim

Algoritmul luiAlgoritmul
Kruskal lui
UAIC) Kruskal
D. Lucanu (FII- - pasul 3 Algoritmi greedy PA 2014/2015 38 / 42

10 10
1 2 1 2

20
20 30

50
30
3 4 3 4

40
10 10

5 5

Algoritmul lui Kruskal - -pasul

D. Lucanu (FII UAIC) 4 Algoritmi greedy PA 2014/2015 38 / 42

11
 Studii de caz Arborele parţial de cost minim

Algoritmul lui Kruskal

10 10
1 2 1 2

20 20
20 30

50
30
3 4 3 4

40
10 10

5 5
Studii de caz Arborele parţial de cost minim

Algoritmul lui Kruskal

Algoritmul lui Kruskal - pasul 5
D. Lucanu (FII - UAIC) Algoritmi greedy PA 2014/2015 38 / 42

10 10
1 2 1 2

20 20
20 30 30

50
30
3 4 3 4

40
10 10

5 5

Algoritmul lui Kruskal

D. Lucanu (FIIca instant, ă a unui
- UAIC) matroid
Algoritmi greedy PA 2014/2015 38 / 42
Fie G = (V, E) graful pentru care aplicăm algoritmul lui Kruskal.
Definim MG = (SG , IG ) ca mai sus (am arătat că este matroid):

1. SG = E, muchiile grafului

2. A ⊆ E ∈ I ddacă A nu cont, ine ciclu.

Exerciţiul 8. Arătat, i că mult, imile maximale din I sunt arbori.

Dacă definim w(e) = M − l(e) (unde M este un număr suficient de mare), atunci algoritmul
lui Kruskal este o instant, ă a algoritmului general pentru matroizi.

Concluzii

1. Greedy este o paradigmă importantă de proiectare a algoritmilor.

2. De obicei algoritmii greedy sunt us, or de implementat (nu neapărat s, i de demonstrat). Pen-
tru a demonstra corectitudinea unui algoritm greedy, arătăm că problema are proprietatea
de alegere greedy s, i proprietatea de substructură optimă (trebuie identificate convenabil
subproblemele).

12
 3. Multe probleme de optimizare au solut, ii optime ce pot fi găsite cu greedy (e.g. problema
continuă a rucsacului). Pentru alte probleme (e.g. problema discretă a rucsacului), algoritmii
greedy nu produc solut, ia optimă.
4. Matroidul este structură matematică cu ajutorul căreia putem modela diverse probleme de
optimizare. Dacă problema se poate modela cu ajutorul unui matroid (ponderat), atunci
algoritmul greedy produce solut, ia optimă. Avantajul este că nu mai avem de demonstrat
algoritmul, deoarece am arătat deja că este corect pentru orice matroid. Este suficient să
arătăm că putem modela problema ca un matroid.

1 Exercit, ii seminar
1.1 Problema select, iei activităt, ilor
1. Arătat, i că strategiile greedy care urmează nu conduc ı̂ntotdeauna la solut, ia optimă:

• selectează activitatea cea mai scurtă (care nu se suprapune cu activităt, ile deja alese);
soluţie ▶pentru activităţile: [1,5), [4,7), [6,10) se alege cea mai scurtă [4,7) şi ulterior nu se mai
poate adăuga nicio activitate. Soluţia optimă e [1,5), [6,10).◀
• selectează activitatea care se suprapune cu cât mai put, ine alte activităt, i (s, i care nu
se suprapune cu activităt, ile deja alese). soluţie ▶11 activitaţi: ı̂n soluţia optimă sunt 4
activităţi: [1,7) [9,15), [17, 22), [24,29). Singura activitate care se suprapune cu doar alte două
activitaţi este [12, 18). Două grupuri a câte trei activităţi identice cresc numărul de suprapuneri
peste cele 4 din soluţia optimă, astfel ele nu vor fi alese ı̂n prima etapă şi nici nu vor putea fi alese
ulterior din cauza suprapunerii cu [12,18). Din cele două grupuri de câte trei putem selecta doar
câte una. Activitatea [- -x- -) incepe la pozitia caracterului [, se termina la ) si se suprapune cu x
alte activitati.◀
00000000011111111112222222222 c i f r a z e c i l o r
12345678901234567890123456789 c i f r a u n i t a t i l o r a l e c a p e t e l o r
[−−3−−) [−−4−−) [−−4−) [−−3−)
[−−4−−) [−−2−−) [−−4−−)
[−−4−−) [−−4−−)
[−−4−−) [−−4−−)

2. Scriet, i ı̂n Alk algoritmul greedy care rezolvă problema.

1.2 Problema plăt, ii unei sume cu număr cât mai mic de bancnote
1. Imaginat, i-vă că trăit, i ı̂ntr-o t, ară ı̂n care sunt disponibile bancnote de 1 leu, de 7 lei s, i de 8
lei. Dat, i exemplu de o sumă de bani pentru care strategia greedy descrisă ı̂n notele de curs
nu produce solut, ia optimă.
soluţie ▶Pentru suma 14 de exemplu, algoritmul greedy alege prima monedă de valoare 8, şi este nevoit
ulterior să mai folosească aloce ı̂ncă 6 bancnote de valoare 1, ajungând la 7 bancnote ı̂n total. Optim e
7 + 7 = 14 deci două bancnote.◀
(ı̂n continuare presupunem că avem la dispozit, ie bancnotele standard)
2. Scriet, i ı̂n Alk algoritmul greedy pentru plata unei sume de bani folosind număr minim de
bancnote.
3. Identificat, i subproblemele pe care le rezolvă algoritmul greedy.
4. Demonstrat, i proprietatea de alegere greedy: Fie b valoarea celei mai mari bancnote care este
mai mică decât suma s de achitat. Atunci există o solut, ie optimă de a plăti s care ı̂ncepe
cu b.

13
 5. Enunt, at, i s, i demonstrat, i proprietatea de substructură optimă (demonstrat, ia ı̂n sine este
foarte us, oară).

1.3 Matroizi
1. Fie M = (S, I) un matroid. Arătat, i că ∅ ∈ I.
2. Fie M = (S, I) un matroid. Arătat, i că orice mult, ime maximală (dpdv al incluziunii) din I
are acelas, i cardinal.
3. Arătat, i că matroidul MG asociat grafului G (definit ı̂n notele de curs) este ı̂ntr-adevăr
matroid.

2 Exercit, ii suplimentare
1. Demonstrat, i că algoritmul greedy produce solut, ia optimă dacă bancnotele disponibile sunt
puteri ale unui număr (e.g. 1, 2, 4, 8, . . .).

2. Arătat, i că problema select, iei activităt, ilor ı̂n care vectorul f este ordonat s, i problema select, iei
activităt, ilor ı̂n care vectorul f nu este neapărat ordonat se reduc una la cealaltă (formalizat, i-
le ı̂ntâi ca pereche input-output).
3. Găsit, i ı̂ncă o strategie greedy pentru problema select, iei activităt, ilor care să conducă la solut, ia
optimă.
4. Găsit, i un algoritm care primes, te n puncte x1 , . . . , xn de pe dreapta Ox s, i găses, te numărul
minim de intervale-unitate ([a, b] este interval-unitate dacă b = a + 1) care acoperă toate
punctele.
5. Găsit, i codul Huffman corespunzător următoarelor frecvent, e: 1, 1, 2, 3, 5, 8, etc.
soluţie ▶Considerând caracterele a, b, c, d, e, f cu frecvenţele 1, 1, 2, 3, 5 şi respectiv 8, codurile
asociate caracterelor vor fi: f − 0, e − 10, d − 110, c − 1111, b − 11101, a − 11100.
referinţe calculator, generator arbore, algoritm şi descriere◀

6. Arătat, i că (S, Ik ) este matroid, dacă S este o mult, ime finită s, i Ik este mult, imea tuturor
submult, imilor lui S de cardinal ≤ k.

7. Căutat, i algoritmul lui Prim ı̂n literatură s, i arătat, i că produce solut, ia optimă. Poate fi
exprimat cu ajutorul matroizilor?
8. Fie S un şir de caractere definit peste alfabetul binar {0, 1}. Peste acest şir se poate aplica
următoarea operaţie: se alege o poziţie Si astfel ı̂ncât Si = 1 şi se atribuie elementului
respectiv valoarea 0. Care este numărul minim de operaţii ce trebuie aplicate lui S astfel ı̂ncât
şirul să nu conţină cuvântul 101 ca substring (factor). De exemplu, pentru S = 1101101010,
numărul minim de operaţii este 2, o posibilitate fiind aplicarea operaţiei peste pozitiile
subliniate: 1101101010 ⇒ 1001100010. Descrieţi un algoritm greedy de complexitate liniară
şi argulentaţi corectitudinea algoritmului.
soluţie ▶Se parcurge şirul de la stânga la dreapta, atunci când ı̂ntâlnim o valoare Si = 1 precedată de
10, formându-se astfel un 10 + 1 = 101, se aplica operaţia peste Si . Deoarece prefixul până la poziţia
i − 1 este deja rezolvat, liber de 101, nu are sens să aplicăm operaţia peste Si−2 , iar poziţia i e prefrabilă
pentru că poate elimina o eventuală apariţie 101 ulterioară, dacă următoatele caractere de la poziţiile i
şi i + 1 sunt 01. sursă, tutorial - ı̂n partea dreapta a paginii, la Contest materials.◀

14