Despre algoritmi • Diferenţe între informatică şi matematică

1) În lucrul pe calculator, majoritatea proprietăţilor algebrice nu sunt satisfăcute. - elementul neutru: egalitatea a+b=a poate fi satisfăcută fără ca b=0: este situaţia în

care b≠0, dar ordinul său de mărime este mult mai mic decât al lui a. - comutativitate: să considerăm următoarea funcţie scrisă în Pascal: function f(var a:integer):integer; begin a:=a+1; f:=a end; Secvenţa de instrucţiuni: a:=1; write (a+f(a)) produce la ieşire valoarea 1+2=3, pe când secvenţa de instrucţiuni: a:=1; write (f(a)+a)) produce la ieşire valoarea 2+2=4. - asociativitate: pentru simplificare vom presupune că numerele sunt memorate cu o

singură cifră semnificativă şi că la înmulţire se face trunchiere. Atunci rezultatul înmulţirilor (0.5×0.7)×0.9 este 0.3×0.9=0.2, pe când rezultatul înmulţirilor 0.5×(0.7×0.9) este 0.5×0.6=0.3.

2) Nu interesează în general demonstrarea teoretică a existenţei algoritmilor, ci

accentul este pus pe elaborarea algoritmilor. Vom pune în vedere acest aspect prezentând o elegantă demonstraţie a

următoarei propoziţii: Propoziţie. Există α,β∈R\Q cu αβ∈Q.

Pentru demonstraţie să considerăm numărul real x=aa, unde a= 2 . Dacă x∈Q, propoziţia este demonstrată. Dacă x∉Q, atunci xa∈Q şi din nou propoziţia este demonstrată.

1

• Aspecte generale care apar la rezolvarea unei probleme

Aşa cum am spus, informaticianului i se cere să elaboreze un algoritm pentru o problemă dată, care să furnizeze o soluţie (fie şi aproximativă, cu condiţia menţionării acestui lucru).

Teoretic, paşii sunt următorii: 1) demonstrarea faptului că este posibilă elaborarea unui algoritm pentru

determinarea unei soluţii; 2) elaborarea unei algoritm (caz în care pasul anterior devine inutil); 3) demonstrarea corectitudinii algoritmului; 4) determinarea timpului de executare a algoritmului; 5) demonstrarea optimalităţii algoritmului (a faptului că timpul de executare este mai

mic decât timpul de executarea al oricărui alt algoritm pentru problema studiată). • Timpul de executare a algoritmilor

Un algoritm este elaborat nu numai pentru un set de date de intrare, ci pentru o mulţime de astfel de seturi. Timpul de executare se măsoară în funcţie de lungimea n a datelor de intrare. Ideal este să determinăm o formulă matematică pentru T(n)=timpul de executare pentru orice set de date de intrare de lungime n. Din păcate, acest lucru nu este în general posibil. De aceea, în majoritatea cazurilor ne mărginim la a evalua ordinul de mărime al timpului de executare. Mai precis, spunem că timpul de executare este de ordinul f(n) şi exprimăm acest lucru prin T(n)=O(f(n)), dacă raportul între T(n) şi f(n) tinde la un număr real atunci când n tinde la ∞. De exemplu, dacă f(n)=nk pentru un anumit număr k, spunem că algoritmul este polinomial.

Un algoritm se numeşte "acceptabil" dacă este este polinomial.

• Corectitudinea algoritmilor În demonstrarea corectitudinii algoritmilor, există două aspecte importante: Corectitudinea parţială: presupunând că algoritmul se termină (într-un număr finit

de paşi), trebuie demonstrat că rezultatul este corect; Terminarea programului: trebuie demonstrat că algoritmul se încheie în timp finit.

Evident, condiţiile de mai sus trebuie îndeplinite pentru orice set de date de intrare admis.

Modul tipic de lucru constă în introducerea în anumite locuri din program a

unor invarianţi, adică relaţii ce trebuie îndeplinite la orice trecere a programului prin acel loc.

2

Exemplul 1. Determinarea concomitentă a cmmdc şi cmmmc a două numere

naturale. Fie a,b∈N*. Se caută:

(a,b)=cel mai mare divizor comun al lui a şi b; [a,b]=cel mai mic multiplu comun al lui a şi b.

Algoritmul este următorul:

x ← a; y ← b; u ← a; v ← b; while x≠y { xv+yu = 2ab; (x,y)=(a,b) } (*) if x>y then x ← x-y; u ← u+v else y ← y-x; v ← u+v write(x,(u+v)/2) Demonstrarea corectitudinii se face în trei paşi: 1) (*) este invariant:

La prima intrare în ciclul while, condiţia este evident îndeplinită. Mai trebuie demonstrat că dacă relaţiile (*) sunt îndeplinite şi ciclul se reia, ele

vor fi îndeplinite şi după reluare. Fie (x,y,u,v) valorile curente la o intrare în ciclu, iar (x',y',u',v')

valorile curente la următoarea intrare în ciclul while. Deci: xv+yu=2ab şi (x,y)=(a,b).

Presupunem că x>y. Atunci x'=x-y, y'=y, u'=u+v, v'=v. x'v'+y'u'=(x-y)v+y(u+v)=xv+yu=2ab. Cazul x>y se studiază similar.

2) Corectitudine parţială: Este binecunoscut că în x=y se obţine d=(a,b). Conform relaţiilor (*), avem

d(u+v)=2αβd2, unde a=αd şi b=βd. Atunci (u+v)/2=αβd=ab/d=[a,b]. 3) Terminarea programului:

Fie {xn}, {yn}, {un}, {vn} şirul de valori succesive ale variabilelor. Toate aceste valori sunt numere naturale pozitive. Se observă că şirurile {xn} şi {yn} sunt descrescătoare, iar şirul {xn+yn} este strict descrescător. Aceasta ne asigură că după un număr finit de paşi vom obţine x=y.

3

Exemplul 2. Metoda de înmulţire a ţăranului rus. Fie a,b∈N. Se cere să se calculeze produsul ab. Ţăranul rus ştie doar: - să verifice dacă un număr este par sau impar; - să adune două numere; - să afle câtul împărţirii unui număr la 2.

Cu aceste cunoştinţe, ţăranul rus procedează astfel: x ← a; y ← b; p ← 0 while x>0 { xy+p=ab } (*) if x impar then p ← p+y x ← x div 2; y ← y+y write(p) Să urmărim cum decurg calculele pentru x=54, y=12: x y p 54 12 0 27 24 13 48 24 6 96 72 3 192 1 384 264 0 ? 648 Ca şi la exemplul precedent, demonstrarea corectitudinii se face în trei paşi: 1) (*) este invariant:

La prima intrare în ciclul while, relaţia este evident îndeplinită. Mai trebuie demonstrat că dacă relaţia (*) este îndeplinită şi ciclul se reia, ea

va fi îndeplinită şi la reluare. Fie (x,y,p) valorile curente la o intrare în ciclu, iar (x',y',p') valorile

curente la următoarea intrare în ciclul while. Deci: xy+p=ab. Presupunem că x este impar. Atunci (x',y',p')=((x-1)/2,2y,p+y).

Rezultă x'y'+p'=(x-1)/2+p+y=xy+p=ab. Presupunem că x este par. Atunci (x',y',p')=(x/2,2y,p). Rezultă

x'y'+p'=xy+p=ab. 2) Corectitudine parţială:

Dacă programul se termină, atunci x=0, deci p=ab. 3) Terminarea programului:

Fie {xn}, {yn} şirul de valori succesive ale variabilelor corespunzătoare. Se observă că şirul {xn} este strict descrescător. Aceata ne asigură că după un număr finit de paşi vom obţine x=0.

4

• Optimalitatea algoritmilor

Să presupunem că pentru o anumită problemă am elaborat un algoritm şi am putut calcula şi timpul său de executare T(n). Este natural să ne întrebăm dacă algoritmul nostru este "cel mai bun" sau există un alt algoritm cu timp de executare mai mic.

Problema demonstrării optimalităţii unui algoritm este foarte dificilă, în mod deosebit datorită faptului că trebuie să considerăm toţi algoritmii posibili şi să arătăm că ei au un timp de executare superior.

Ne mărginim la a enunţa două probleme şi a demonstra optimalitatea algoritmilor propuşi, pentru a pune în evidenţă dificultăţile care apar.

Exemplul 1. Se cere să determinăm m=min(a1,a2,...,an). Algoritmul binecunoscut este următorul:

m ← a1for i=2,n if ai<m then m ← aicare necesită n-1 comparări între elementele vectorului a=(a1,a2,...,an). Propoziţia 1. Algoritmul de mai sus este optimal. Trebuie demonstrat că orice algoritm bazat pe comparări necesită cel puţin n-1 comparări. Demonstrarea optimalităţii acestui algoritm se face uşor prin inducţie. Pentru n=1 este evident că nu trebuie efectuată nici o comparare. Presupunem că orice algoritm care rezolvă problema pentru n numere efectuează cel puţin n-1 comparări să considerăm un algoritm oarecare care determină cel mai mic dintre n+1 numere. Considerăm prima comparare efectuată de acest algoritm; fără reducerea generalităţii, putem presupune că s-au comparat a1 cu a2 şi că a1<a2. Atunci m=min(a1,a3,...,an=1). Dar pentru determinarea acestui minim sunt necesare cel puţin n-1 comparări, deci numărul total de comparări efectuat de algoritmul considerat este cel puţin egal cu n. Exemplul 2. Se cere determinarea minimului şi maximului elementelor unui vector.

Mai precis, se cere determinarea cantităţilor m=min(a1,a2,...,an) şi M=min(a1,a2,...,an).

Determinarea succesivă a valorilor m şi M necesită timpul T(n)=2(n-1). O soluţie mai bună constă în a considera câte două elemente ale vectorului, a

determina pe cel mai mic şi pe cel mai mare dintre ele, iar apoi în a compara pe cel mai mic cu minimul curent şi pe cel mai mare cu maximul curent:

5

if n impar then m ← a1; M ← a1; k ← 1 else if a1<a2 then m ← a1; M ← a2 else m ← a2; M ← a1; k ← 2 { k = numărul de elemente analizate } while k≤n-2 if ak+1<ak+2 then if ak+1<m then m ← ak+1 if ak+2>M then M ← ak+2 else if ak+2<m then m ← ak+2 if ak+1>M then M ← ak+1 k ← k+2 Să calculăm numărul de comparări efectuate: - pentru n=2k, în faza de iniţializare se face o comparare, iar în continuare se fac

3(k-1) comparări; obţinem T(n)=1+3(k-1)=3k-3=3n/2-2=⎡3n/2⎤-2. - pentru n=2k+1, la iniţializare nu se face nici o comparare, iar în continuare se fac

3k comparări; obţinem T(n)=(3n-3)/2=(3n+1)/2-2=⎡3n/2⎤-2. În concluzie, timpul de calcul este T(n)=⎡3n/2⎤-2. Propoziţia 2. Algoritmul de mai sus este optimal. Considerăm următoarele mulţimi şi cardinalul lor:

- A= mulţimea elementelor care nu au participat încă la comparări; a=|A|; - B= mulţimea elementelor care au participat la comparări şi au fost totdeauna mai

mari decât elementele cu care au fost comparate; b=|B|; - C= mulţimea elementelor care au participat la comparări şi au fost totdeauna mai

mici decât elementele cu care au fost comparate; c=|C|; - D= mulţimea elementelor care au participat la comparări şi au fost cel puţin o dată

mai mari şi cel puţin o dată mai mici decât elementele cu care au fost comparate; d=|D|;

Numim configuraţie un quadruplu (a,b,c,d). Problema constă în determinarea numărului de comparări necesare pentru a trece de la quadruplul (n,0,0,0) la quadruplul (0,1,1,n-2).

Considerăm un algoritm arbitrar care rezolvă problemă şi arătăm că el

efectuează cel puţin ⎡3n/2⎤-2 comparări. Să analizăm trecerea de la o configuraţie oarecare (a,b,c,d) la următoarea.

Este evident că nu are sens să efectuăm comparări în care intervine vreun element din D. Apar următoarele situaţii posibile: 1) Compar două elemente din A: se va trece în configuraţia (a-2,b+1,c+1,d) . 2) Compar două elemente din B: se va trece în configuraţia (a,b-1,c+1,d+1) . 3) Compar două elemente din C: se va trece în configuraţia (a-2,b,c-1,d+1) .

6

4) Se compară un element din A cu unul din B. Sunt posibile două situaţii:

- elementul din A este mai mic: se trece în configuraţia (a-1,b,c+1,d); - elementul din A este mai mare: se trece în configuraţia (a-1,b,c,d+1). Cazul cel mai defavorabil este primul, deoarece implică o deplasare "mai lentă" spre dreapta a componentelor quadruplului. De aceea vom lua în considerare acest caz.

5) Se compară un element din A cu unul din C. Sunt posibile două situaţii: - elementul din A este mai mic: se trece în configuraţia (a-1,b,c,d+1); - elementul din A este mai mare: se trece în configuraţia (a-1,b+1,c,d). Cazul cel mai defavorabil este al doilea, deoarece implică o deplasare "mai lentă" spre dreapta a componentelor quadruplului. De aceea vom lua în considerare acest caz.

6) Se compară un element din B cu unul din C. Sunt posibile două situaţii: - elementul din B este mai mic: se trece în configuraţia (a,b-1,c-1,d+2); - elementul din B este mai mare: se rămâne în configuraţia (a,b,c,d). Cazul cel mai defavorabil este al doilea, deoarece implică o deplasare "mai lentă" spre dreapta a componentelor quadruplului. De aceea vom lua în considerare acest caz.

Observaţie. Cazurile cele mai favorabile sunt cele în care d creşte, deci ies din calcul elemente candidate la a fi cel mai mic şi cel mai mare. Odată stabilită trecerea de la o configuraţie la următoarea, ne punem problema cum putem trece mai rapid de la configuraţia iniţială la cea finală. Analizăm cazul în care n=2k (cazul în care n este impar este propus ca exerciţiu). Paşii sunt următorii: - plecăm de la (n,0,0,0)=(2k,0,0,0); - prin k comparări între perechi de elemente din A ajungem la (0,k,k,0); - prin k-1 comparări între perechi de elemente din B ajungem la (0,1,k,k-1); - prin k-1 comparări între perechi de elemente din C ajungem la (0,1,1,n-2).

În total au fost necesare k+(k-1)+(k-1)=3k-2=⎡3n/2⎤-2 comparări.

7

• Existenţa algoritmilor

Acest aspect este şi mai delicat decât precedentele, pentru că necesită o definiţie matematică riguroasă a noţiunii de algoritm. Nu vom face decât să prezentăm (fără vreo demonstraţie) câteva definiţii şi rezultate. Un studiu mai amănunţit necesită un curs aparte!

Noţiunea de algoritm nu poate fi definită decât pe baza unui limbaj sau a unei

maşini matematice abstracte.

Numim problemă nedecidabilă o problemă pentru care nu poate fi elaborat un algoritm. Definirea matematică a noţiunii de algoritm a permis detectarea de probleme nedecidabile. Câteva dintre ele sunt următoarele: 1) Problema opririi programelor: pentru orice program şi orice valori de intrare să se

decidă dacă programul se termină. 2) Problema opririi programelor (variantă): pentru un program dat să se decidă dacă

el se termină pentru orice valori de intrare. 3) Problema echivalenţei programelor: să se decidă pentru orice două programe dacă

sunt echivalente (produc aceeaşi ieşire pentru aceleaşi date de intrare).

8

• Noţiunea de clasă class C { int x; boolean y; // câmpuri C() { x=2; } // constructor C(int a, boolean b) { x=a; y=b; } // constructor int met() { // metoda if (y) return x; else return x+1; } void met(int x) { // metoda if (this.x==x) y=true; } } Apare prima caracteristică a OOP: încapsularea. Declararea şi crearea unui obiect de tipul C C Ob; Ob = new C(); sau C Ob = new C(1,true); Invocarea metodelor: int i = Ob.met(); Ob.met(); Ob.met(7); Observaţie. La invocarea metodelor se foloseşte apelul prin valoare. Observaţie. Dacă metoda este declarată cu modificatorul static, ea poate fi invocată şi prin numele clasei. Astfel, dacă metoda met cu signatura vidă era declarată prin: static int met() { . . . } atunci ea putea fi invocată şi prin: C.met(); Observaţie. Dacă un câmp w este declarat cu modificatorul static, el este comun tuturor obiectelor de tipul C, deci este memorat o singură dată. În plus el poate fi referit şi prin C.w .

9

O clasă pentru intrări/ieşiri: Clasa IO cu metode statice: read(); // întoarce un număr real citit de la intrare readch(); // întoarce un caracter citit de la intrare readString(); // întoarce un şir de caractere citit de la intrare ( "..." ) write(s); // tipăreşte şirul de caractere s writeln(s); // tipăreşte şirul de caractere s

si trece la linia urmatoare Invocările se fac de exemplu prin: IO.writeln(i + ""); Un prim program: Fie fişierul Unu.java: class Unu { public static void main(String[] sir) { for (int i=0; i<sir.length; i++) IO.writeln(sir[i]); } }

Compilarea: javac Unu.java

Executarea: java unu doi trei produce la ieşire: unu doi trei

10

• Liste

class elem { char c; elem leg; static elem p,u; elem() { } elem(char ch) { c = ch; } elem adaug(char ch) { elem x = new elem(ch); leg = x; return x; } void creare() { char ch = IO.readch(); p = new elem(ch); u = p; ch = IO.readch(); while (ch!='$') { u = u.adaug(ch); ch = IO.readch(); } }

String direct(elem x) { if (x==null) return ""; else return x.c + direct(x.leg); }

String invers(elem x) { if (x==null) return ""; else return invers(x.leg)+x.c; } } class Lista { public static void main(String[] s) { elem Ob = new elem(); Ob.creare(); IO.writeln( Ob.direct(elem.p) ); IO.writeln( Ob.invers(Ob.p) ); } }

unde operatorul != are sensul "diferit de".

Să presupunem că la intrare apare: abc$c1... La ieşire vom obţine: abc cba

11

• Arbori

Numim arbore un graf neorientat conex şi fără cicluri. Aceasta nu este singurul mod în care putem defini arborii. Câteva definiţii

echivalente apar în următoarea teoremă, expusă fără demonstraţie. Teoremă. Fie G un graf cu n≥1 vârfuri. Următoarele afirmaţii sunt echivalente:

1) G este un arbore; 2) G are n-1 muchii şi nu conţine cicluri; 3) G are n-1 muchii şi este conex; 4) oricare două vârfuri din G sunt unite printr-un unic drum; 5) G nu conţine cicluri şi adăugarea unei noi muchii produce un unic ciclu elementar; 6) G este conex, dar devine neconex prin ştergerea oricărei muchii.

În foarte multe probleme referitoare la arbori este pus în evidenţă un vârf al său, numit rădăcină. Alegerea unui vârf drept rădăcină are două consecinţe:

• Arborele poate fi aşezat pe niveluri astfel: - rădăcina este aşezată pe nivelul 0; - pe fiecare nivel i sunt plasate vârfurile pentru care lungimea drumurilor care le

leagă de rădăcină este i; - se trasează muchiile arborelui.

Această aşezare pe niveluri face mai intuitivă noţiunea de arbore, cu precizarea că în informatică "arborii cresc în jos".

Exemplul 3. Considerăm următorul arbore şi modul în care el este aşezat pe

niveluri prin alegerea vârfului 5 drept rădăcină.

9

10 8 1

7 3 9 2

6 4

5

3

2

1

0

7

3 6

5

4

2

10

8

1

• Arborele poate fi considerat un graf orientat, stabilind pe fiecare muchie sensul de la nivelul superior către nivelul inferior.

Reprezentarea pe niveluri a arborilor face ca noţiunile de fii (descendenţi) ai

unui vârf, precum şi de tată al unui vârf să aibă semnificaţii evidente. Un vârf fără descendenţi se numeşte frunză.

12

• Arbori binari

Un arbore binar este un arbore în care orice vârf are cel mult doi descendenţi, cu precizarea că se face distincţie între descendentul stâng şi cel drept. Din acestă definiţie rezultă că un arbore binar nu este propriu-zis un caz particular de arbore.

Primele probleme care se pun pentru arborii binari (ca şi pentru arborii oarecare şi pentru grafuri, aşa cum vom vedea mai târziu) sunt: - modul de reprezentare; - parcurgerea lor.

Forma standard de reprezentare a unui arbore binar constă în: - a preciza rădăcina rad a arborelui; - a preciza pentru fiecare vârf i tripletul st(i), dr(i) şi info(i), unde acestea

sunt respectiv descendentul stâng, descendentul drept şi informaţia ataşată vârfului.

Trebuie stabilită o convenţie pentru lipsa unuia sau a ambilor descendenţi, ca de exemplu specificarea lor prin simbolul λ.

Exemplul 4. Considerăm de exemplu următorul arbore binar:

7 6 4

5 3 9

8 2

1 Presupunând că informaţia ataşată fiecărui vârf este chiar numărul său de ordine, avem: - rad = 1; - st = (2,3,4,λ,6,λ,λ,λ,λ); - dr = (8,5,λ,λ,7,λ,λ,9,λ); - info= (1,2,3,4,5,6,7,8,9).

Dintre diferitele alte reprezentări posibile, mai menţionăm doar pe cea care se

reduce la vectorul său tata şi la vectorul info. Pentru exemplul de mai sus: tata=(λ,1,2,3,2,5,5,1,8). Problema parcurgerii unui arbore binar constă în identificarea unei modalităţi prin care, plecând din rădăcină şi mergând pe muchii, să ajungem în toate vârfurile; în plus, atingerea fiecărui vârf este pusă în evidenţă o singură dată: spunem că vizităm vârful respectiv. Acţiunea întreprinsă la vizitarea unui vârf depinde de problema concretă şi poate fi de exemplu tipărirea informaţiei ataşate vârfului.

13

Distingem trei modalităţi standard de parcurgere a unui arbore binar: Parcurgerea în preordine

Se parcurg recursiv în ordine: rădăcina, subarborele stâng, subarborele drept. Concret, se execută apelul preord(rad) pentru procedura:

procedure preord(x) if x=λ then else vizit(x); preord(st(x)); preord(dr(x)) end

Ilustrăm acest mod de parcurgere pentru exemplul de mai sus, figurând îngroşat rădăcinile subarborilor ce trebuie dezvoltaţi: 1 1, 2, 8 1, 2, 3, 5, 8, 9 1, 2, 3, 4, 5, 6, 7, 8, 9 Parcurgerea în inordine

Se parcurg recursiv în ordine: subarborele stâng, rădăcina, subarborele drept. Ilustrăm acest mod de parcurgere pentru Exemplul 4:

1 2, 1, 8 3, 2, 5, 1, 8, 9 4, 3, 2, 6, 5, 7, 1, 8, 9

Concret, se execută apelul inord(rad) pentru procedura: procedure inord(x) if x=λ then else inord(st(x)); vizit(x); inord(dr(x)) end Parcurgerea în postordine

Se parcurg recursiv în ordine; subarborele stâng, subarborele drept, rădăcina. Ilustrăm parcurgerea în postordine pentru Exemplul 4:

1 2, 8, 1 3, 5, 2, 9, 8, 1 4, 3, 6, 7, 5, 2, 9, 8, 1

Concret, se execută apelul postord(rad) pentru procedura:

procedure postord(x) if x=λ then else postord(st(x)); postord(dr(x)); vizit(x) end

14

• Sortarea cu ansamble Fie a=(a1,…,an) vectorul care trebuie sortat (ordonat crescător). Metoda sortării de ansamble va folosi o reprezentare implicită a unui vector ca arbore binar. Acest arbore este construit succesiv astfel: - rădăcina este 1; - pentru orice vârf descendenţii săi stâng şi drept sunt 2i şi 2i+1 (cu condiţia ca

fiecare dintre aceste valori să nu depăşească pe n). Rezultă că tatăl oricărui vârf i este tata(i)=⎣i/2⎦.

Evident, fiecărui vârf i îi vom ataşa eticheta ai.

Pentru 2k-1≤n<2k arborele va avea k niveluri, dintre care numai ultimul poate fi incomplet (pe fiecare nivel i<k-1 se află exact 2i vârfuri).

0

1

k-2

k-1

Vectorul a se numeşte ansamblu dacă pentru orice i avem ai≥a2i şi ai≥a2i+1 (dacă fiii există). Să presupunem că subarborii de rădăcini 2i şi 2i+1 sunt ansamble. Ne propunem să transformăm arborele de rădăcină i într-un ansamblu. Ideea este de a retrograda valoarea ai până ajunge într-un vârf ai cărui descendenţi au valorile mai mici decât ai. Acest lucru este realizat de procedura combin.

procedure combin(i,n) i ← 2i; b ← ai while j≤n if j<n & aj<aj+1 then j ← j+1 if b>aj then a⎣j/2⎦ ← b; exit else a⎣j/2⎦ ← aj; j ←2j a⎣j/2⎦ ← b end

i

2i+1 2i

a ans ns

Timpul de executare pentru procedura combin este O(k)=O(log n).

Sortarea vectorului a se va face prin apelul succesiv al procedurilor creare şi sortare prezentate mai jos.

Procedura creare transformă vectorul într-un ansamblu; în particular în a1 se obţine cel mai mare element al vectorului.

15

Procedura sortare lucrează astfel: - pune pe a1 pe poziţia n şi reface ansamblul format din primele n-1 elemente; - pune pe a1 pe poziţia n-1 şi reface ansamblul format din primele n-2 elemente; - etc. procedure creare procedure sortare for i=⎣n/2⎦,1,-1 for i=n,2,-1 combin(i,n) a1↔ai; combin(1,i-1) end end Timpul total de lucru este de ordinul O(n.log n). Aşa cum am menţionat chiar de la început, structura de arbore este implicită şi este menită doar să clarifice modul de lucru al algoritmului: calculele se referă doar la componentele vectorului.

3

12 11

8 6

1 5 2 4

9 10

7

16

• Arbori de sortare

Un arbore de sortare este un arbore binar în care pentru orice vârf informaţia ataşată vârfului este mai mare decât informaţiile vârfurilor din subarborele stâng şi mai mică decât informaţiile vârfurilor din subarborele drept.

11

5 20

17

15 18

7

Observaţie. Parcurgerea în inordine a unui arbore de căutare produce

informaţiile ataşate vârfurilor în ordine crescătoare. Fie a=(a1,...an) un vector ce trebuie ordonat crescător. Conform

observaţiei de mai sus, este suficient să creăm un arbore de sortare în care informaţiile vârfului să fie tocmai elementele vectorului. Pentru aceasta este suficient să precizăm modul în care prin adăugarea unei noi valori, să obţinem tot un arbore de sortare.

Pentru exemplul considerat: - adăugarea valorii 6 trebuie să conducă la crearea unui nou vârf, cu informaţia 6 şi

care este descendent stâng al vârfului cu informaţia 7; - adăugarea valorii 16 trebuie să conducă la crearea unui nou vârf, cu informaţia 16

şi care este descendent drept al vârfului cu informaţia 15.

Presupunem că un vârf din arborele de sortare este o înregistrare sau obiect de tipul varf, ce conţine câmpurile: - informaţia info ataşată vârfului; - descendentul stâng st şi descendentul drept dr (lipsa acestora este marcată, ca de

obicei, prin λ).

Crearea unui nou vârf se face prin funcţia varf_nou care întoarce un nou vârf: function varf_nou(info)

creez un nou obiect/ o nouă înregistrare x în care informaţia este info, iar descendentul stâng şi cel drept sunt λ;

return x end

Inserarea unei noi valori val (în arborele de rădăcină rad) se face prin apelul

adaug(rad,val), unde funcţia adaug întoarce o înregistrare şi are forma: function adaug(x,val) { se inserează val în subarborele de rădăcină x} if x=λ then return varf_nou(val) else if val<info(x) then st(x) ← adaug(st(x),val) else dr(x) ← adaug(dr(x),val) end

17

Programul principal întreprinde următoarele acţiuni: - citeşte valorile ce trebuie ordonate şi le inserează în arbore; - parcurge în inordine arborele de sortare; vizitarea unui vârf constă în tipărirea

informaţiei ataşate.

Prezentăm programul în Java: class elem { int c; elem st,dr; elem() { } elem(int ch) { c=ch; st=null; dr=null; } elem adaug(elem x, int ch) { if (x==null) x=new elem(ch); else if (ch<x.c) x.st=adaug(x.st,ch); else x.dr=adaug(x.dr,ch); return x; } String parcurg(elem x) { if (x==null) return(""); else return( parcurg(x.st) + x.c + " " + parcurg(x.dr)); } } class Arbsort { public static void main(String arg[]) { elem rad=null; double val; elem Ob = new elem(); val = IO.read(); while ( ! Double.isNaN(val) ) { rad = Ob.adaug(rad,(int) val); val = IO.read(); } IO.writeln(Ob.parcurg(rad)); } } • Arbori oarecare

Primele probleme care se pun sunt aceleaşi ca pentru arborii binari: modalităţile de reprezentare şi de parcurgere.

Exemplul 5. Considerăm următorul arbore:

13 10 11 12

9 8 7 6 5

4 3 2

1

3

2

1

0

18

Se consideră că arborele este aşezat pe niveluri şi că pentru fiecare vârf există o ordine între descendenţii săi.

Modul standard de reprezentare al unui arbore oarecare constă în a memora

rădăcina, iar pentru fiecare vârf i informaţiile: - info(i) = informaţia ataşată vârfului; - fiu(i) = primul vârf dintre descendenţii lui i; - frate(i) = acel descendent al tatălui lui i, care urmeză imediat după i.

Ca şi pentru arborii binari, lipsa unei legături către un vârf este indicată prin λ. Pentru arborele din Exemplul 5: fiu =(2,5,7,8,10,11,λ,λ,λ,λ,λ,8,λ); frate =(λ,3,4,λ,6,λ,λ,9,λ,λ,12,13,λ). O altă modalitate de reprezentare constă în a memora pentru fiecare vârf tatăl său. Această modalitate este incomodă pentru parcurgerea arborilor, dar se dovedeşte utilă în alte situaţii, care vor fi prezentate în continuare. În unele cazuri este util să memorăm pentru fiecare vârf atât fiul şi fratele său, cât şi tatăl său. Parcurgerea în preordine

Se parcurg recursiv în ordine rădăcina şi apoi subarborii care au drept rădăcină descendenţii săi.

Pentru Exemplul 5: 1 1,2,3,4 1,2,5,6,3,7,4,8,9 1,2,5,10,6,11,12,13,3,7,4,8,9.

Concret, executăm apelul Apreord(rad) pentru procedura: procedure Apreord(x) if x=λ then else vizit(x); Apreord(fiu(x)); Apreord(frate(x)) end Ca aplicaţie, să presupunem că informaţiile ataşate vârfurilor sunt funcţii de diferite arităţi (aritatea unei funcţii este numărul variabilelor de care depinde; o funcţie de aritate 0 este o constantă).

Pentru Exemplul 5, vectorul de aritate este: aritate=(3,2,1,2,1,3,0,0,0,0,0,0,0). Rezultatul 1 2 5 10 6 11 12 13 3 7 4 8 9 al parcurgerii în preordine este o formă fără paranteze (dar la fel de consistentă) a scrierii expresiei funcţionale: 1(2(5(10),6(11,12,13)),3(7),4(8,9)) Această formă se numeşte forma poloneză directă.

19

Parcurgerea în postordine

Se parcurg recursiv în ordine subarborii rădăcinii şi apoi rădăcina.

Pentru Exemplul 5: 1 2,3,4,1 5,6,2,7,3,8,9,4,1 10,5,11,12,13,6,2,7,3,8,9,4,1. Concret, executăm apelul Apostord(rad) pentru procedura: procedure Apostord(x) if x=λ then else y←fiu(x); while y<>λ Apostord(y); y←frate(x) vizit(x) end Pentru aplicaţia anterioară, dorim să calculăm valoarea expresiei funcţionale, cunoscând valorile frunzelor. Evident, trebuie să parcurgem arborele în postordine. class varf { int v; varf fiu,frate; static varf rad; varf() { } varf(int val) { v = val; } void creare() { IO.write("rad : "); int i = (int) IO.read(); rad = new varf(i); creare(rad); } void creare(varf x) { // ataseaza fiu si frate lui x int i; double d; IO.write("fiul lui " + x.v + " : "); d = IO.read(); if( !Double.isNaN(d) ) { i = (int) d; x.fiu = new varf(i); creare(x.fiu); } IO.write("fratele lui " + x.v + " : "); d = IO.read(); if( !Double.isNaN(d) ) { i = (int) d; x.frate = new varf(i); creare(x.frate); } } String pre(varf x) { if (x==null) return ""; else return x.v + " " + pre(x.fiu) + pre(x.frate); } void post(varf x) { varf y = x.fiu; while (y != null) { post(y); y = y.frate; } IO.write(x.v + " "); } }

20

class Arbori { public static void main(String[] s) { varf Ob = new varf(); Ob.creare(); IO.writeln( "Preordine:\t" + Ob.pre(varf.rad) ); IO.writeln("Postordine:\t"); Ob.post(varf.rad); } } Parcurgerea pe niveluri

Se parcurg vârfurile în ordinea distanţei lor faţă de rădăcină, ţinând cont de

ordinea în care apar descendenţii fiecărui vârf. Pentru Exemplul 5: 1,2,3,4,5,6,7,8,9,10,11,12,13. Pentru implementare vom folosi o coadă C, în care iniţial apare numai rădăcina. Atâta timp cât coada este nevidă, vom extrage primul element, îl vom vizita şi vom introduce în coadă descendenţii săi: C ← ∅; C ⇐ rad while C≠∅ x ⇐ C; vizit(x); y ← fiu(x); while y≠λ y ⇒ C; y ← frate(x) end Parcurgerea pe niveluri este în general utilă atunci când se caută vârful care este cel mai apropiat de rădăcină şi care are o anumită proprietate/informaţie. Pentru a include în programul anterior şi parcurgerea pe niveluri, putem proceda astfel: - în metoda main adăugăm instrucţiunea: IO.writeln("\rNiveluri : " +"\t" + Ob.niveluri() ); - în clasa varf adăugăm clasa internă elem şi metoda niveluri: class elem { varf inf; elem leg; elem (varf v) { inf = v; } } String niveluri() { elem p,u,x; varf y; String s=""; p = new elem(null); u = new elem(root); p.leg = u; while ( p != u ) { x = p.leg; s += x.inf.v + " "; p.leg = x.leg; if(p.leg == null) u = p; y = x.inf.fiu; while ( y != null) { x = new elem(y); u.leg = x; u = x; y = y.frate; } } return s; } }

21

1

Grafuri • Parcurgerea DF a grafurilor neorientate Fie G=(V,M) un graf neorientat. Ca de obicei, notăm n=|V| şi m=|M|.

Parcurgere în adâncime a grafurilor (DF = Depth First) generalizează parcurgerea în preordine a arborilor oarecare. Eventuala existenţă a ciclurilor conduce la necesitatea de a marca vârfurile vizitate. Ideea de bazǎ a algoritmului este urmǎtoarea: se pleacǎ dinr-un vârf i0 oarecare, apelând procedura DF pentru acel vârf. Orice apel de tipul DF(i) prevede urmǎtoarele operaţii: - marcarea vârfului i ca fiind vizitat; - pentru toate vârfurile j din lista Li a vecinilor lui i se executǎ apelul DF(j) dacă şi

numai dacǎ vârful j nu a fost vizitat. Simpla marcare a unui vârf ca fiind sau nu vizitat poate fi înlocuitǎ cu atribuirea unui numǎr de ordine fiecǎrui vârf; mai precis, în nrdf(i), iniţial egal cu 0, va fi memorat al câtelea este vizitat vârful i; nrdf(i) poartǎ numele de numǎrul (de ordine) DF al lui i.

Este evident cǎ plecând din vârful i0 se pot vizita numai vârfurile din componenta conexǎ a lui i0. De aceea, în cazul în care graful nu este conex, dupǎ parcurgerea componentei conexe a lui i0 vom repeta apelul DF pentru unul dintre eventualele vârfuri încǎ neatinse. procedure DF(i)

← ndf ndf+1; nrdf(i) ndf; vizit(i); ←for toţi j∈Li

if nrdf(j)=0 then DF(j)

Programul principal este:

citeşte graful; ndf 0; ←for i=1,n nrdf(i) 0 ←for i=1,n if nrdf(i)=0 then DF(i) scrie nrdf;

Observaţie. Dacǎ dorim doar sǎ determinǎm dacǎ un graf este conex, vom înlocui al

doilea ciclu for din programul principal prin: DF(1); if ndf=n then write(’CONEX’)

else write(’NECONEX’);

Observaţie. Parcurgerea DF împarte muchiile grafului în: - muchii de avansare: sunt acele muchii (i,j) pentru care în cadrul apelului DF(i) are

loc apelul DF(j). Aceste muchii formeazǎ un graf parţial care este o pǎdure: fiecare vârf este vizitat exact o datǎ, deci nu existǎ un ciclu format din muchii de avansare.

- muchii de întoarcere: sunt acele muchii ale grafului care nu sunt muchii de avansare.

22

2

Determinarea mulţimilor A şi I a muchiilor de avansare şi întoarcere, precum şi memorarea arborilor parţiali din pădurea DF se poate face astfel: - în programul principal se fac iniţializările: A ←∅; I←∅; for i=1,n tata(i) ← 0; - instrucţiunea if din procedura DF devine: if nrdf(j)=0 then A A∪ {(i,j)}; tata(j) ← i; DF(j);

≠←

else if tata(j) i ← then I I∪ {(i,j)};

Exemplu. Pentru graful următor:

1

2

3

4

5

6

7

8

9

cu următoarele liste ale vecinilor vârfurilor: L1={4,2,3}; L2={1,4}; L3={1,5}; L4={1,2,5}; L5={3,4}; L6={8,9}; L7={9}; L8={6} L9={6,7}

pădurea DF este formată din următorii arbori parţiali corespunzători componentelor conexe: 1

2

3

4

5

6

7

8 9

Timpul cerut de algoritmul de mai sus este O(max{n,m})=O(n+m), adică liniar, deoarece:

- pentru fiecare vârf i, apelul DF(i) are loc exact o datǎ; - executarea unui apel DF(i) necesitǎ un timp proporţional cu grad(i)=|Li|; în

consecinţǎ timpul total va fi proporţional cu m=|M|.

Propoziţie. Dacǎ (i,j) este muchie de întoarcere, atunci i este descendent al lui j. Muchia (i,j) este detectatǎ ca fiind muchie de întoarcere în cadrul executǎrii

apelului DF(i), deci nrdf(j)<nrdf(i). Deoarece existǎ muchie între vârfurile i şi j, rezultǎ cǎ în timpul executǎrii lui DF(j) va fi vizitat şi vârful i, deci i este descendent al lui j.

23

3

Propoziţia de mai sus spune cǎ muchiile de întoarcere leagǎ totdeauna douǎ vârfuri situate pe aceeaşi ramurǎ a pǎdurii parţiale DF. În particular, nu există muchii de traversare (care să lege doi descendenţi ai aceluiaşi vârf dintr-un arbore DF).

Observaţie. Un graf este ciclic (conţine cel puţin un ciclu) dacǎ şi numai dacǎ în

timpul parcurgerii sale în adâncime este detectatǎ o muchie de întoarcere.

Aplicaţie. Sǎ se determine dacǎ un graf este ciclic şi în caz afirmativ sǎ se identifice un ciclu.

Vom memora pǎdurea formatǎ din muchiile de avansare cu ajutorul vectorului tata şi în momentul în care este detectatǎ o muchie de întoarcere (i,j) vom lista drumul de la i la j format din muchii de avansare şi apoi muchia (j,i).

Procedura DF va fi modificată astfel: procedure DF(i)

← ndf ndf+1; nrdf(i) ndf; vizit(i); ← for toţi j∈Li if nrdf(j)=0

← then tata(j) i; DF(j) else if tata(j)≠i then k←i; while k j ≠

write(k,tata(k)); k←tata(k); write(j,i); stop

end.

Observaţii: - dacă notăm prin nrdesc(i) numărul descendenţilor lui i în subarborele de rădăcină

i, această valoare poate fi calculată plasând după ciclul for din procedura DF instrucţiunea nrdesc(i)←ndf-nrdf(i)+1;

- un vârf j este descendent al vârfului i în subarborele DF de rădăcină i ⇔ nrdf(i)≤nrdf(j)<nrdf(i)+nrdesc(i).

• O aplicaţie: Problema bârfei Se consideră n persoane. Fiecare dintre ele emite o bârfă care trebuie cunoscută de toate celelalte persoane. Prin mesaj înţelegem o pereche de numere (i,j) cu i,j∈{1,...,n} şi cu semnificaţia că persoana i transmite persoanei j bârfa sa, dar şi toate bârfele care i-au parvenit până la momentul acestui mesaj.

Se cere una dintre cele mai scurte succesiuni de mesaje prin care toate persoanele află toate bârfele.

Cu enunţul de mai sus, o soluţie este imediată şi constă în succesiunea de mesaje:

(1,2),(2,3),...,(n-1,n),(n,n-1),(n-1,n-2),...,(2,1). Sunt transmit deci n-2 mesaje. După cum vom vedea mai jos, acesta este numărul

minim de mesaje prin care toate persoanele află toate bârfele. Problema se complică dacă există persoane care nu comunică între ele (sunt certate) şi

deci nu-şi vor putea transmite una alteia mesaje.

24

4

Această situaţie poate fi modelată printr-un graf în care vârfurile corespund persoanelor, iar muchiile leagă persoane care nu sunt certate între ele. Vom folosi matricea de adiacenţă a de ordin n în care aij este 0 dacă persoanele i şi j sunt certate între ele (nu există muchie între i şi j) şi 1 în caz contrar.

Primul pas va consta în detectarea unui arbore parţial; pentru aceasta vom folosi

parcurgerea DF. Fiecărei persoane i îi vom ataşa variabila booleană vi, care este true dacă şi numai dacă vârful corespunzător a fost atins în timpul parcurgerii; iniţial toate aceste valori sunt false. Vom pune aij=2 pentru toate muchiile de înaintare. vi ← false, ∀i=1,...n nr ← 0; DF(1) if nr<n then write('Problema nu are soluţie (graf neconex)') else rezolvă problema pe arborele parţial construit unde procedura DF are forma cunoscută: procedure DF(i) vi ← true for j=1,n if aij=1 & not vj then aij ← 2; DF(j) end

Să observăm că în acest mod am redus problema de la un graf la un arbore! Descriem în continuare modul în care rezolvăm problema pe acest arbore parţial, bineînţeles în ipoteza că problema are soluţie (graful este conex).

Printr-o parcurgere în postordine, în care vizitarea unui vârf constă în transmiterea de mesaje de la fiii săi la el, rădăcina (presupusă a fi persoana 1) va ajunge să cunoască toate bârfele. Aceasta se realizează prin apelul postord(1), unde procedura postord are forma:

procedure postord(i) for j=1,n if aij=2 then postord(j); write(j,i) end

În continuare, printr-o parcurgere în preordine a arborelui DF, mesajele vor circula de la rădăcină către frunze. Vizitarea unui vârf constă în transmiterea de mesaje fiilor săi. Pentru aceasta executăm apelul preord(1), unde procedura preord are forma: procedure preord(i) for j=1,n if aij=2 then write(i,j); preord(j); end

Observăm că atât la parcurgerea în postordine, cât şi la cea în preordine au fost listate n-1 perechi (mesaje), deoarece un arbore cu n vârfuri are n-1 muchii. Rezultă că soluţia de

25

5

mai sus constă într-o succesiune de 2n-2 mesaje. Mai rămâne de demonstrat că acesta este numărul minim posibil de mesaje care rezolvă problema.

Propoziţie. Orice soluţie pentru problema bârfei conţine cel puţin 2n-2 mesaje. Să considerăm o soluţie oarecare pentru problema bârfei. Punem în evidenţă primul mesaj prin care o persoană a ajuns să cunoască toate

bârfele; fie k această persoană. Deoarece celelate persoane trebuie să le fi emis, înseamnă că până acum au fost transmise cel puţin n-1 mesaje. Dar k este prima persoană care a aflat toate bârfele, deci celelalte trebuie să mai afle cel puţin o bârfă. Rezultă că în continuare trebuie să apară încă cel puţin n-1 mesaje. În concluzie, soluţia considerată este formată din cel puţin 2n-2 mesaje.

• Circuitele fundamentale ale unui graf

Fie G=(V,M) un graf neorientat conex. Fie A =(V,M’) un arbore parţial al lui G. Muchiile din M’\M vor fi numite corzi. Pentru fiecare coardǎ existǎ un unic drum, format numai din muchii din M’, ce uneşte

extremitǎţile corzii. Împreunǎ cu coarda, acest drum formeazǎ un ciclu numit ciclu fundamental.

Fie G1=(X1,M1) şi G2=(X2,M2) douǎ grafuri. Suma lor circularǎ este graful: G1 ⊕ G2 = (X1∪X2, M1∪M2\M1∩M2)

Observaţii:

1) Operaţia ⊕ este comutativǎ şi asociativǎ; 2) Dacǎ M1 şi M2 reprezintǎ cicluri, atunci M1 ⊕ M2 este tot un ciclu sau o reuniune

disjunctǎ (în privinţa muchiilor) de cicluri:

Teoremǎ. Pentru un graf şi un arbore parţial A al sǎu date, ciclurile fundamentale

formeazǎ o bazǎ, adicǎ sunt îndeplinite condiţiile: 1) orice ciclu se poate exprima ca sumǎ circularǎ de cicluri fundamentale; 2) nici un ciclu fundamental nu poate fi exprimat ca sumǎ circularǎ de cicluri

fundamentale.

26

6

Exemplu. Considerăm următorul graf şi un arbore parţial al său:

1

2

3

4

5 1

2

3

4

5 Arborele parţial A:

Ciclul (1,2,5,4,3,1) se poate scrie ca o sumă circulară de cicluri fundamentale astfel:

1

2

3

4

5 = 1

2

3 5

1 3

4

1 3 5

4

Demonstraţie. Considerǎm un ciclu în G, ale cǎrui muchii sunt partiţionate în

C={e1,…,ek}∪{ek+1,…,ej} unde e1,...,ek sunt corzi, iar ek+1,...,ej sunt muchii din A. Fie C(e1),...,C(ek) ciclurile fundamentale din care fac parte e1,…,ek. Fie

C’=C(e1)⊕...⊕ C(ek). Vom demonstra cǎ C=C’ (sunt formate din aceleaşi muchii). Presupunem cǎ C≠C’. Atunci C⊕C’≠∅. Sǎ observǎm cǎ atât C cât şi C’ conţin corzile

e1,…,ek. Conform unei observaţii de mai sus, C’ şi apoi C⊕C’ sunt cicluri sau reuniuni

disjuncte de cicluri. Cum atât C cât şi C’ conţin corzile e1,...,ek şi în rest muchii din A, rezultǎ cǎ C⊕C’ conţine numai muchii din A, deci nu poate conţine un circuit. Contradicţie.

Fie un ciclu fundamental care conţine coarda e. Fiind singurul ciclu fundamental ce

conţine e, el nu se va putea scrie ca sumǎ circularǎ de alte cicluri fundamentale.

Consecinţǎ. Baza formatǎ din circuitele fundamentale are ordinul m−n+1. Observaţie. O muchie din C(e1)⊕...⊕C(ek) este ştearsǎ ⇔ apare de numǎr par de ori.

Determinarea mulţimii ciclurilor fundamentale

Printr-o parcurgere a arborelui A, putem stabili pentru el legǎtura tata. Atunci pentru orice coardǎ (i,j) procedǎm dupǎ cum urmeazǎ:

1) Determinǎm vectorii: u = (u1=i, u2=tata(u1), ... , unu=tata(unu-1)=rad) v = (v1=j, v2=tata(v1), ... , vnv=tata(vnv-1)=rad).

2) Parcurgem simultan vectorii u şi v de la stânga la dreapta şi determinǎm cel mai mic indice k cu uk=vk.

27

7

Atunci ciclul cǎutat este: u1=i, u2, ... , uk=vk, ... , v1=j, i Observǎm cǎ pentru fiecare coardǎ, timpul este O(n).

• Parcurgerea DF a grafurilor orientate

Algoritmul este acelaşi ca la grafuri neorientate. Arcele de avansare formeazǎ o pǎdure constituitǎ din arbori în care toate arcele au

orientarea "de la rǎdǎcinǎ cǎtre frunze", numitǎ "pǎdure DF".

Exemplu. Pentru graful:

5

1

2

3

4

6

7 8

9

10

11

obţinem pǎdurea:

9 1

2

3

4

5

6

7 8

10

11

şi vectorul nrdf = (1,2,3,4,5,6,7,8,9,10,11).

Parcurgerea DF împarte arcele (i,j) în 3 categorii: 1) arce de avansare, caracterizate prin nrdf(i)<nrdf(j):

1.1) arce componente ale pǎdurii DF; 1.2) arce ce leagǎ un vârf de un descendent al sǎu care nu este fiu al sǎu;

2) arce de întoarcere, ce leagǎ un vârf de un predecesor al sǎu în pǎdurea DF; evident nrdf(i)>nrdf(j);

3) arce de traversare: leagǎ douǎ vârfuri care nu sunt unul descendentul celuilalt.

28

8

Pentru exemplul considerat avem: 1.2) : (1,6) 2) : (3,1), (6,4), (11,9) 3) : (7,2), (8,2), (8,7), (9,1), (11,2), (11,8)

Propoziţie. Pentru orice arc de traversare (i,j) avem nrdf(i)>nrdf(j).

i j

Sǎ presupunem prin absurd cǎ nrdf(i)<nrdf(j). Atunci în momentul în care s-a

ajuns prima datǎ la i, vârful j nu a fost încǎ atins. Din modul în care lucreazǎ algoritmul, (i,j) va fi arc de avansare:

i

j

sau

i

j

Observaţie. Spre deosebire de arcele de traversare, arcele de întoarcere determinǎ un circuit elementar (prin adǎugarea unui astfel de arc la pǎdurea DF ia naştere un circuit elementar). Putem stabili dacǎ un arc (i,j) cu nrdf(i)>nrdf(j) este de întoarcere sau de traversare astfel:

k←i; while k≠0 & k≠j k←tata(k) if k=0 then write(’traversare’) else write(’întoarcere’)

• Parcurgerea BF a grafurilor neorientate Fie un graf G=(V,M) şi fie i0 un vârf al său. În unele situaţii se pune probleme determinării vârfului j cel mai apropiat de i0 cu o anumită proprietate. Parcurgerea DF nu mai este adecvată. Parcurgerea pe lăţime BF (Breadth First) urmăreşte vizitarea vârfurilor în ordinea crescătoare a distanţelor lor faţă de i0. Este generalizată parcurgerea pe niveluri a arborilor, ţinându-se cont că graful poate conţine cicluri. Va fi deci folosită o coadă C.

La fel ca şi la parcurgerea DF, vârfurile vizitate vor fi marcate. Pentru exemplul din primul paragraf al acestui capitol, parcurgerea BF produce

vârfurile în următoarea ordine: 1,4,2,3,5,6,8,9,7. Algoritmul care urmează parcurge pe lăţime componenta conexă a lui i0:

for i=1,n vizitat(i) ← false

29

9

C ⇐ (i0} while C ≠ ∅ i ⇐ C; vizitează i; vizitat(i)←true for toţi j vecini ai lui i if not vizitat(j) then j ⇒ C Programul Java corespunzător foloseşte: • Clasa Vector:

Un vector (obiect de tipul Vector) are lungime variabilă şi conţine obiecte oarecare. Vector() : construieşte vectorul vid (de lungime 0); void addElement(Object) : adaugă obiect la sfârşitul vectorului; boolean remove Element(Object) : elimină, cu deplasare la stânga, prima apariţie; boolean isEmpty() : verifică dacă vectorul este vid; Object firstElement() : întoarce primil element al vectorului. • Clasa înfăşurătoare Integer: Integer(int): constructor ce construieşte un obiect ce conţine întregul respectiv; int intValue(): întoarce întregul asociat obiectului. = = = = = = = = = = = = class BF { public static void main(String[] s) { nivel Ob = new nivel(); Ob.parc(); } } import java.util.*; class nivel { int[][] mat; int[] temp; int n; nivel() { int[] temp; int ntemp; double d; IO.write("n= "); n = (int) IO.read(); mat = new int[n][]; temp = new int[n]; for (int i=0; i<n; i++) { IO.write("Vecinii lui "+i+" : "); ntemp = 0; d = IO.read(); while( ! Double.isNaN(d) ) { temp[ntemp++]= (int) d; d = IO.read(); } mat[i] = new int[ntemp]; for (int j=0; j<ntemp; j++) mat[i][j] = temp[j]; } IO.writeln("**************"); }

30

10

void parc() { boolean[] v = new boolean[n]; Integer Int; int i,j,k; Vector coada = new Vector(); coada.addElement(new Integer(0)); v[0] = true; while ( ! coada.isEmpty() ) { Int = (Integer) coada.firstElement(); coada.removeElementAt(0); i = Int.intValue(); IO.write(i+"\t"); for (k=0; k<mat[i].length; k++) { j = mat[i][k]; if( !v[j] ) { coada.addElement(new Integer(j)); v[j]=true; } } } } } La fel ca pentru parcurgerea DF, algoritmul poate fi completat pentru parcurgerea întregului graf, pentru determinarea unei păduri în care fiecare arbore este un arbore parţial al unei componente conexe etc.

31

Metoda Greedy

Metoda Greedy (greedy=lacom) este aplicabilă problemelor de optim.

Considerăm mulţimea finită A={a1,...,an} şi o proprietate p definită pe mulţimea submulţimilor lui A:

p:P(A)→{0,1} cu ⎩⎨⎧

⊂∀⇒=φ

XYp(Y),p(X)

1)p(

O submulţime S⊂A se numeşte soluţie dacă p(S)=1. Dintre soluţii aleg una care optimizează o funcţie p:P(A)→R dată. Metoda urmăreşte evitarea parcurgerii tuturor submulţimilor (ceea ce ar

necesita un timp de calcul exponenţial), mergându-se "direct" spre soluţia optimă. Nu este însă garantată obţinerea unei soluţii optime; de aceea aplicarea metodei Greedy trebuie însoţită neapărat de o demonstraţie. Distingem două variante generale de aplicare a metodei Greedy: S←φ for i=1,n x←alege(A); A←A\{x} if p(S∪{x})=1 then S←S∪{x}

prel(A) S←φ for i=1,n if p(S∪{ai}) then S←S∪{ai}

Observaţii:

- în algoritm nu apare funcţia f !! - timpul de calcul este liniar (exceptând prelucrările efectuate de procedurile

prel şi alege); - dificultatea constă în a concepe procedurile alege, respectiv prel, în care

este "ascunsă" funcţia f.

Exemplul 1. Se consideră mulţimea de valori reale A={a1,...,an}. Se caută submulţimea a cărei sumă a elementelor este maximă. Vom parcurge mulţimea şi vom selecta numai elementele pozitive. k←0 for i=1,n if ai>0 then k←k+1; sk←aiwrite(s)

Exemplul 2. Caut cel mai scurt şir crescător cu elemente din mulţimea {a1,...,an}. Începem prin a ordona crescător elementele mulţimii (corespunzător procedurii prel). Apoi: k←1; s1←a1; lung←1; baza←1 for i=2,n if ai>sk then k←k+1; sk ← ai else if k>lung then lung←k; baza←i-k k←1; s1←ai

32

Astfel, dacă în urma ordonării a rezultat a=(1,1,2,3,4,4,5,6,7,8,8}, vom obţine succesiv: baza=1; lung=1; s=(1) baza=2; lung=4; s=(1,2,3,4) baza=6; lung=5; s=(4,5,6,7,8).

(Contra)exemplul 3. Fie mulţimea A={a1,...,an} cu elemente pozitive. Caut submulţimea de sumă maximă, dar cel mult egală cu M dat.

Dacă procedez ca în exemplul 1, pentru A=(6,3,4,2) şi M=7 obţin {6}. Dar

soluţia optimă este {3,4} cu suma egală cu 7. Continuăm cu prezentarea unor exemple clasice. • Metoda textelor pe bandă

Textele cu lungimile L(1),...,L(n) urmează a fi aşezate pe o bandă. Pentru a citi textul de pe poziţia k, trebuie citite textele de pe poziţiile 1,2,...,k (conform specificului accesului secvenţial pe bandă).

O soluţie înseamnă o permutare p∈Sn. Pentru o astfel de permutare (ordine de aşezare a textelor pe bandă), timpul

pentru a citi textul de pe poziţie k este: Tp(k)=L(p1)+...+L(pk). Presupunând

textele egal probabile, trebuie minimizată valoarea ∑==

n

1kp(k)T

n1

T(p) .

Să observăm că funcţia T se mai poate scrie: ∑ +−==

n

1kk)1)L(pk(n

n1

T(p)

(textul de pe poziţia k este citit dacă vrem să citim unul dintre textele de pe poziţiile k,...,n).

Conform strategiei Greedy, începem prin a ordona crescător vectorul L. Rezultă că în continuare L(i)<L(j), ∀i<j. Demonstrăm că în acest mod am obţinut modalitatea optimă, adică permutarea identică minimizează funcţia de cost T. Fie p∈Sn optimă, adică p minimizează funcţia T. Dacă p este diferită de permutarea identică ⇒ ∃i<j cu L(pi)>L(pj):

)p=( pi pj

Considerăm permutarea p' în care am interschimbat elementele de pe poziţiile i şi j: p'=( pj pi )

Atunci n[T(p)-T(p’)] = (n-i+1)L(pi) + (n-j+1)L(pj) = = (n-i+1)L(pj) + (n-j+1)L(pi) = = (j-i)L(pi)+(i-j)L(pj) = = (j-i)[L(pi)-L(pj)]>0, ambii factori fiind pozitivi.

Rezultă că T(p’)<T(p). Contradicţie.

33

• Problema contiunuă a rucsacului

Se consideră un rucsac de capacitate (greutate) maximă G şi n obiecte caracterizate prin:

- greutăţile lor g1,...,gn; - câştigurile c1,...,cn obţinute la încărcarea lor în totalitate în rucsac.

Din fiecare obiect poate fi încărcată orice fracţiune a sa. Se cere o modalitate de încărcare de (fracţiuni de) obiecte în rucsac, astfel

încât câştigul total să fie maxim.

Prin soluţie înţelegem un vector x=(x1,…,xn) cu ⎪⎩

⎪⎨⎧

≤∑

∀∈

=Gxg

i[0,1],xn

1iii

i

O soluţie optimă este soluţie care maximizează funcţia . ∑==

n

1iiixcf(x)

Dacă suma greutăţilor obiectelor este mai mică decât G, atunci încarc toate

obiectele: x=(1,...,1). De aceea presupunem în continuare că g1+...+gn>G. Conform strategiei Greedy, ordonez obiectele descrescător după câştigul la

unitatea de greutate, deci lucrăm în situaţia:

n

n

2

2

1

1

g

c...

g

c

g

c≥≥≥ (*)

Algoritmul constă în încărcarea în această ordine a obiectelor, atâta timp cât nu

se depăşeşte greutatea G (ultimul obiect pote fi eventual încărcat parţial):

G1 ← G { G1 reprezintă greutatea disponibilă } for i=1,n if gi≤G1 then xi←1; G1←G1-gi else xi←G1/gi; for j=i+1,n xj ← 0 stop write(x)

Am obţinut deci x=(1,...,1,xj,0,...,0) cu xj∈[0,1). Arătăm că soluţia astfel obţinută este optimă.

Fie y soluţia optimă: y=(...,yk,...) cu

⎪⎪⎩

⎪⎪⎨

⎧

∑

∑ =

=

=n

1iii

n

1iii

yc

Gyg

maxim

Dacă y≠x, fie k prima poziţie pe care yk≠xk. Observaţii: k≤j: pentru k>j se depăşeşte G. yk<xk:

– pentru k<j: evident, deoarece xk=1; – pentru k=j: dacă yk>xk se depăşeşte G.

34

Considerăm soluţia: y’=(y1,…,yk-1,xk,αyk+1,…, αyn) cu α<1 (primele k-1 componente coincid cu cele din x). Păstrez greutatea totală G, deci: gkxk+α(gk+1yk+1+...+gnyn)=gkyk+gk+1yk+1+...+gnyn. Rezultă: gk(xk-yk)=(1-α)(gk+1yk+1+…+gnyn) (**) Compar performanţa lui y' cu cea a lui y: f(y’)-f(y) = ckxk +αck+1yk+1 +...+ αcnyn - (ckyk+ck+1yk+1 +...+cnyn) = = ck(xk-yk) + (α-1)(ck+1yk+1+...+cnyn) = = ck/gk[gk(xk-yk)+(α-1)(gk/ckck+1yk+1+...+gk/ckcnyn)]

Dar α-1>0 şi gk/ck≤ gs/cs, ∀s>k. Atunci f(y’)-f(y)>ck/gk [gk(xk-yk)+(α-1)(gk+1yk+1+...+gnyn)]=0,

deci f(y')>f(y). Contradicţie. Problema discretă a rucsacului diferă de cea continuă prin faptul că fiecare obiect poate fi încărcat numai în întregime în rucsac. Să observăm că aplicarea metodei Greedy eşuează în acest caz. Într-adevăr, aplicarea ei pentru: G=5, n=3 şi g=(4,3,2), c=(6,4,2.5) are ca rezultat încărcarea primul obiect; câştigul obţinut este 6. Dar încărcarea ultimelor două obiecte conduce la câştigul superior 6.5. • Problema arborelui parţial de cost minim. Fie G=(V,M) un graf neorientat cu muchiile etichetate cu costuri strict pozitive. Se cere determinarea unui graf parţial de cost minim. Ca exemplificare, să considerăm n oraşe iniţial nelegate între ele. Pentru fiecare două oraşe se cunoaşte costul conectării lor directe (considerăm acest cost egal cu +∞ dacă nu este posibilă conectarea lor). Constructorul trebuie să conecteze oraşele astfel încât din oricare oraş să se poată ajunge în oricare altul. Ce legături directe trebuie să aleagă constructorul astfel încât costul total al lucrării să fie minim? Este evident că graful parţial căutat este un arbore (dacă ar exista un ciclu, am putea îndepărta orice muchie din el, cu păstrarea conexităţii şi micşorarea costului total). Vom aplica metoda Greedy: adaug mereu o muchie de cost minim dintre cele nealese şi care nu formează un ciclu cu precedentele muchii alese.

Acest algoritm poartă numele de algoritmul lui Kruskal. Ca de obicei, fie |V|=n, |M|=m. Vor fi alese deci n-1 muchii. Construim o matrice mat cu m linii şi n coloane. Pe fiecare linie apar extremităţile i şi j ale unei muchii, precum şi costul acestei muchii. Începem prin a ordona liniile matricii crescător după ultima coloană (a costurilor muchiilor).

35

Exemplu. Considerăm graful de mai jos şi matricea mat ataşată. 1 2

3

4

5

2 1 2 2 1 4 2 4 5 2 1 5 3 3 4 4 2 5 5 3 3 5

5

4 2

3 5

2

Conform algoritmului lui Kruskal, vor fi alese în ordine muchiile: (1,2), (1,4), (4,5), (3,4) cu costul total egal cu 10. Muchia (1,5) nu a fost aleasă deoarece formează cu precedentele un ciclu. Dificultatea principală constă în verificarea faptului că o muchie formează sau nu cu precedentele un ciclu. Plecând de la observaţia că orice soluţie parţială este o pădure, vom asocia fiecărui vârf i un reprezentant ri care identifică componenta conexă (arborele) din care face parte vârful în soluţia parţială. Atunci:

- o muchie (i,j) va forma un ciclu cu precedentele ⇔ ri=rj; - la alegerea (adăugarea) unei muchii (i,j) vom pune rk←rj pentru orice vârf

k cu rk=ri (unim doi arbori, deci vârfurile noului arbore trebuie să aibă acelaşi reprezentant).

În algoritmul care urmează metoda descrisă, l este numărul liniei curente din

matricea mat, nm este numărul de muchii alese, iar cost este costul muchiilor alese ri ← i, ∀i=1,n l ← 1; nm ← 0; cost ← 0 while l≤m & nm<n-1 i1 ← mat(l,1); i2 ← mat(l,2) r1 ← ri1; r2 ← ri2 if r1≠r2 then nm ← nm+1; cost ← cost+mat(l,3); write(i1,i2) for k=1,n if rk=r2 then rk ← r1 l ← l+1 if nm<n-1 then write('Graf neconex') else write('Graf conex. Costul=’,cost)

Demonstrăm în continuare corectitudinea algoritmului lui Kruskal. Fie G=(V,M) un graf conex. P⊂M se numeşte mulţime promiţătoare de muchii dacă nu conţine cicluri şi

poate fi extinsă la un arbore parţial P de cost minim.

36

Propoziţia 1. Fie P promiţătoare şi Y⊂V astfel încât nici un vârf din Y nu este o extremitate a unei muchii din P. Fie m una dintre muchiile de cost minim cu cel puţin o extremitate în Y. Atunci P∪{m} este promiţătoare.

Fie P arborele parţial de cost minim la care poate fi extins P.

P Y

• i

• j

m

Dacă m∈P , O.K. Dacă m∉P, atunci P∪{m} are un ciclu. În el există, în afară de m, o altă muchie

m' adiacentă lui Y. Fie P'=P ∪{m}\{m’}. Observăm că P∪{m}⊂P' pentru că P⊂P. P' este de cost minim deoarece costul lui m este mai mic sau egal cu costul lui

m'. Rezultă că mulţimea de muchii P∪{m} este promiţătoare.

Propoziţia 2. Arborele furnizat de metoda Kruskal este arbore parţial de cost minim.

Arătăm prin inducţie că după k=0,1,...,n-1 paşi, cele k muchii alese formează o mulţime promiţătoare. Pentru k=0 rezultatul este evident.

Fie P mulţimea promiţătoare a muchiilor selectate la primii k paşi. Fie Y=V\{x | x extremitate a unei muchii din P} = mulţimea punctelor izolate. Conform Propoziţiei 1, mulţimea P∪{muchia selectată la pasul k+1} este

promiţătoare. În final, o mulţime promiţătoare cu n-1 muchii este chiar un arbore parţial de

cost minim. Observaţie. Tot o ilustrare a metodei Greedy pentru problema enunţată o constituie algoritmul lui Prim, care constă în următoarele:

- se începe prin selectarea unui vârf; - la fiecare pas aleg o muchie (i,j) de lungime minimă cu i selectat, dar j

neselectat. De această dată, la fiecare pas se obţine un arbore. Propunem ca exerciţiu

demonstrarea faptului că după n-1 paşi se obţine un arbore parţial de cost minim.

37

Vizibilitate şi acces Pachetele, clasele, metodele, câmpurile şi variabilele sunt identificate prin numele lor. Problema care se pune este de a stabili din ce loc putem face referire la aceste nume (cu semnificaţia dorită), adică de a preciza domeniul lor de vizibilitate. • Variabile locale şi etichete Prin bloc înţelegem o secvenţă (eventual vidă) de instrucţiuni, cuprinsă între acolade. Un bloc este o instrucţiune şi de aceea poate fi folosit în orice loc unde poate să apară o instrucţiune. De exemplu orice metodă şi orice constructor sunt formate dintr-un antet urmat de un bloc. În schimb ceea ce urmează după modificatorii şi numele unei clase nu constituie un bloc, deşi apar acoladele deschisă şi închisă: conţinutul unei clase nu este o succesiune de instrucţiuni. Orice bloc poate conţine la rândul său un alt bloc, putând astfel lua naştere o structură imbricată de blocuri. Prin variabilă locală înţelegem o variabilă declarată în interiorul unui bloc, inclusiv într-o instrucţiune for. Domeniul de vizibilitate al unei variabile locale este constituit din partea din blocul în care a fost declarată, ce urmează declarării. Prin urmare o variabilă locală nu poate fi referită înainte de a fi declarată. Variabilele locale există numai pe perioada în care blocul în care sunt declarate este în curs de executare.

Nu putem folosi facilitatea de imbricare a blocurilor pentru a redeclara o variabilă locală. O variabilă locală nu poate fi redefinită nici în blocul în care a fost declarată, nici într-un bloc inclus în acesta. Regulile care guvernează domeniul de vizibilitate al etichetelor sunt aceleaşi ca pentru variabilele locale. • Parametrii metodelor şi constructorilor Numele parametrilor dintr-o metodă sau dintr-un constructor sunt vizibile doar în interiorul acestora, adică în blocul care urmează antetului metodei sau constructorului. Este însă posibil ca într-un bloc dintr-o metodă sau dintr-un constructor să redeclarăm numele unui parametru; în acest caz, în partea din bloc ce urmează redeclarării, numele respectiv este considerat ca având semnificaţia dată de redeclarare. Cu alte cuvinte, domeniul de vizibilitate al unui parametru este constituit din corpul metodei sau constructorului în care apare, mai puţin blocurile (evident disjuncte) în care este redeclarat. • Vizibilitatea în interiorul unei clase Ştim că o clasă este constituită din câmpuri, constructori (folosiţi la crearea de obiecte) şi metode (folosite la invocarea lor). Din orice constructor şi din orice metodă putem să ne referim la orice câmp sau metodă a clasei. De asemenea dintr-un constructor putem apela alt constructor prin this urmat, între paranteze, de o listă de argumente ce respectă signatura noului constructor.

38

Ordinea în care apar câmpurile nestatice şi metodele în cadrul clasei nu este relevantă (de exemplu nu contează dacă un câmp nestatic este declarat la începutul sau la sfârşitul clasei). Totuşi, dacă numele unui câmp este redeclarat într-o metodă (este folosit ca nume al unui parametru sau declarat într-un bloc), atunci declararea cea mai interioară este cea care primează când se face o referire la acel nume (identificator). Putem spune că un parametru poate ascunde un câmp, iar o variabilă locală poate ascunde un parametru şi/sau un câmp. După cum vom vedea în continuare, numele unei metode nu poate fi ascuns. • Modificatorul final Modificatorul final poate fi ataşat atât variabilelor (locale sau câmpuri), cât şi metodelor. În cazul variabilelor locale, variabilei i se atribuie valoare la declarare sau înainte de a fi folosită; variabila nu poate primi de două ori valoare. Menţionăm că final este singurul modificator ce poate fi ataşat unei variabile locale. Unui câmp final trebuie să i se atribuie valoare fie prin iniţializare, fie prin constructori. Menţionăm că în general modificatorul final este folosit împreună cu static, pentru a trata un câmp ca o "constantă cu nume". Efectul modificatorului final asupra metodelor şi claselor va fi prezentat atunci când vom vorbi despre extinderea claselor. • Modificatorul static Modificatorul static poate fi folosit la declararea câmpurilor şi metodelor unei clase. O variabilă locală nu poate fi declarată cu static . Fie c un câmp declarat cu static în clasa Clasa. Această declarare are două consecinţe:

- câmpul c este comun tuturor obiectelor de tipul Clasa; - referirea la câmp din exteriorul clasei se face fie conform regulii generale

(prin crearea şi utilizarea unei instanţe a clasei Clasa), fie direct, prin precalificarea câmpului cu numele clasei (Clasa.c). Fie acum met o metodă declarată cu modificatorul static în clasa Clasa; ea se numeşte metodă statică sau metodă de clasă. Invocarea ei se poate face fie conform regulii generale (prin crearea şi utilizarea unei instanţe a clasei Clasa), fie direct, prin precalificarea metodei cu numele clasei: Clasa.met(...) ; De aceea într-o metodă statică nu poate fi folosită referinţa this. O metodă statică poate accesa numai câmpurile şi metodele statice ale clasei din care face parte sau a altei clase. Metodele statice (de clasă) sunt folosite de obicei pentru a efectua prelucrări asupra câmpurilor statice ale clasei. Putem "ocoli" însă această regulă de exemplu astfel:

- la invocarea metodei îi transmitem ca parametru o referinţă la un obiect; - în metodă construim explicit un obiect de tipul clasei la ale cărei metode şi câmpuri dorim să ne referim.

39

3

• Modificatorii de acces Toate câmpurile şi metodele unei clase sunt accesibile (pot fi referite) din interiorul clasei. Rolul modificatorilor public, protected, private şi cel implicit (numit uneori package) referitor la accesul din exteriorul unei clase la membrii săi este sintetizat în următorul tabel:

Modificator Membrii clasei cu acest modificator sunt accesibili ...

public de oriunde clasa este accesibilă protected din cod din acelaşi pachet implicit (package )

din cod din acelaşi pachet

private numai din interiorul clasei Reamintim că modificatorii de mai sus joacă un rol nu numai în privinţa accesului, dar şi pentru facilitatea de extindere a claselor, ceea ce va face diferenţa între modificatorul protected şi cel implicit. • Determinarea semnificaţiei unui nume Pentru un identificator folosit ca nume de variabilă (locală sau câmp), metodă sau clasă, semnificaţia sa se obţine la prima căutare încununată de succes din următorul şir de căutări succesive:

1) variabilele locale declarate într-un bloc sau un ciclu for; 2) numai dacă suntem în interiorul unei metode sau a unui constructor:

parametrii metodei sau constructorului; 3) membrii clasei, inclusiv cei rezultaţi prin extinderea claselor (vezi capitolul

următor) 4) tipuri importate explicit; 5) tipuri declarate în acelaşi pachet; 6) tipuri importate implicit; 7) pachete disponibile pe sistemul gazdă.

Mai mult, se face distincţie clară între tipurile de identificatori: nume de variabile (locale), de pachete, de clase, de metode şi de câmpuri; iată de ce numele unei metode nestatice nu poate fi ascuns. Aceasta permite să folosim un acelaşi identificator pentru a numi una sau mai multe astfel de entităţi.

40

Metoda Backtracking

Aşa cum s-a subliniat în capitolele anterioare, complexitatea în timp a

algoritmilor joacă un rol esenţial. În primul rând un algoritm este considerat "acceptabil" numai dacă timpul său de executare este polinomial, adică de ordinul O(nk) pentru un anumit k; n reprezintă numărul datelor de intrare.

Pentru a ne convinge de acet lucru, vom considera un calculator capabil să efectueze un milion de operaţii pe secundă. n=20 n=40 n=60 n3 − − 0,2 sec 2n 1 sec 12,7 zile 366 secole 3n 58 min 3855 secole 1013 secole

Chiar dacă în prezent calculatoarele performante sunt capabile de a efectua zeci de miliarde de operaţii pe secundă, tabelul de mai sus arată că algoritmii exponenţiali nu sunt acceptabili. • Descrierea metodei

Fie X=X1 × ... × Xn. Caut x∈X cu ϕ(x), unde ϕ:X → {0,1} este o proprietate definită pe X.

Din cele de mai sus rezultă că generarea tuturor elementelor produsului cartezian X nu este acceptabilă.

Metoda backtracking încearcă, dar nu reuşeşte totdeauna, micşorarea timpului

de calcul. X este numit spaţiul soluţiilor posibile, iar ϕ sintetizeazǎ condiţiile interne. Vectorul x este construit progresiv, începând cu prima componentǎ. Se

avanseazǎ cu o valoare xk dacǎ este satisfǎcutǎ condiţia de continuare ϕk(x1,...,xk). Condiţiile de continuare rezultǎ de obicei din ϕ; ele sunt strict necesare, ideal fiind sǎ fie şi suficiente.

Distingem urmǎtoarele cazuri posibile la alegerea lui xk: 1) ”Atribuie şi avanseazǎ”: mai sunt valori neconsumate din Xk şi valoarea xk

aleasǎ satisface ϕk ⇒ se mǎreşte k. 2) ”Încercare eşuatǎ”: mai sunt valori neconsumate din Xk şi valoarea xk

aleasǎ dintre acestea nu satisface ϕk ⇒ se va relua, încercându-se alegerea unei noi valori pentru xk.

3) "Revenire": nu mai existǎ valori neconsumate din Xk (Xk epuizatǎ) ⇒ întreaga Xk devine disponibilǎ şi k←k-1.

4) "Revenire dupǎ determinarea unei soluţii": este reţinutǎ soluţia.

Reţinerea unei soluţii constă în apelarea unei proceduri retsol care prelucrează soluţia (o tipăreşte, o compară cu alte soluţii etc.) şi fie opreşte procesul (dacă se doreşte o singură soluţie), fie prevede k←k-1 (dacă dorim să determinăm toate soluţiile.

41

Notǎm prin Ck⊂Xk mulţimea valorilor consumate din Xk. Algoritmul este

următorul: Ci←∅, ∀i; k←1; while k>0 if k=n+1 then retsol(x); k←k-1; { revenire după obţinerea unei soluţii } else if Ck≠Xk then alege v∈Xk\Ck; Ck←Ck∪{v}; if ϕk(x1,…,xk-1,v) then xk←v; k←k+1; { atribuie şi avanseazǎ } else { încercare eşuatǎ } else Ck←∅; k←k-1; { revenire }

Pentru cazul particular X1=...=Xn={1,…,s}, algoritmul se simplifică astfel: k←1; xi←0, ∀i=1,...,n while k>0 if k=n+1 then retsol(x); k←k-1; { revenire dupǎ obţinerea unei soluţii } else if xk<s then xk←xk+1; if ϕk(x1,…,xk) then k←k+1; { atribuie şi avanseazǎ } else { încercare eşuatǎ } else xk←0; k←k-1; { revenire }

42

• Exemple

În exemplele care urmează, ϕk va fi notatǎ în continuare prin cont(k). Se aplică algoritmul de mai sus pentru diferite forme ale funcţiei de continuare.

1) Colorarea hǎrţilor. Se consideră o hartă. Se cere colorarea ei folosind cel mult

n culori, astfel încât oricare două ţări vecine (cu frontieră comună de lungime strict pozitivă) să fie colorate diferit.

Fie xk culoarea curentă cu care este coloratǎ ţara k. function cont(k: integer): boolean; b ← true; i ← 1; while b and (i<k) if vecin(i,k) & xi=xk then b ← false else i ← i+1 cont ← b end;

2) Problema celor n dame Se consideră un caroiaj n×n. Prin analogie cu o tablă de şah (n=8), se doreşte

plasarea a n dame pe pătrăţelele caroiajului, astfel încât să nu existe două dame una în bătaia celeilalte (adică să nu existe două dame pe aceeaşi linie, coloană sau diagonală).

Evident, pe fiecare linie vom plasa exact o damă. Fie xk coloana pe care este plasatǎ dama de pe linia k.

Damele de pe liniile i şi k sunt: - pe aceeaşi coloană: dacă xi=xk ; - pe aceeaşi diagonală: dacă |xi-xk|=k-i.

function cont(k:integer): boolean; b ← true; i ← 1; while b and i<k if |xi-xk|=k-i or xi=xk then b ← false else i ← i+1; cont ← b end;

43

3) Problema ciclului hamiltonian

Se consideră un graf neorientat. Un ciclu hamiltonian este un ciclu care trece exact o dată prin fiecare vârf al grafului.

Pentru orice ciclu hamiltonian putem presupune că el pleacă din vârful 1. Vom

nota prin xi al i-lea vârf din ciclu. x=(x1,...,xn) soluţie dacă:

x1=1 & {x2,...,xn}={2,...,n} & xn,x1 vecine. Vom considera că graful este dat prin matricea sa de adiacenţă. function cont(k:integer): boolean; if a(xk-1,xk)=0 then cont ← false else i ← 1; b ← true; while b & (i<k) if xk=xi then b ← false else i ← i+1; if k=n then b ← b ∧ a(xn,x1)=1; cont ← b end;

44

• O descriere succintă a metodei backtracking

Metoda backtracking poate fi descrisă astfel:

Backtracking = parcurgerea limitată *) în adâncime a unui arbore *) conform condiţiilor de continuare

Rolul condiţiilor de continuare este ilustrat în figura ce urmează. Dacă pentru xk este aleasă o valoare ce nu satisface condiţiile de continuare, atunci la parcurgerea în adâncime este evitată parcurgerea unui întreg subarbore.

x1

x2

xk

45

• Variante

Variantele cele mai uzuale întâlnite în aplicarea metodei backtracking sunt

următoarele: - soluţia poate avea un numǎr variabil de componente şi/sau - dintre ele alegem una care optimizeazǎ o funcţie datǎ. Exemplu. a=(a1,…,an)∈Zn. Caut un subşir crescǎtor de lungime maximǎ. Deci caut 1≤x <...<x ≤n cu k maxim 1 k

ax1 < ax2 <...< axk Pentru n=8 şi a=(1,4,2,3,7,5,8,6) va rezulta k=5. Aici, soluţia posibilǎ: care nu poate fi continuată; exemplu: (4,7,8). Notǎm prin xf şi kf soluţia optimǎ şi lungimea sa.

Completez cu -∞ şi +∞ : a0 ← -∞; n←n+1; an ← +∞; Funcţia cont are următoarea formă:

function cont(k) cont ← axk-1<ak end;

Procedura retsol are forma:

procedure retsol(k) if k>kf then xf←x; kf←k;

end;

Algoritmul backtracking se modifică astfel:

k←1; x ←0; x1←0; kf←0; 0

while k>0 if xk<n then xk←xk+1; if cont(k) then if xk=n { an=+∞ } then retsol(k); k←k-1 else k←k+1; xk←xk-1 else else k←k-1;

Observaţie. Se face tot o parcurgere limitatǎ în adâncime a unui arbore.

46

• Varianta recursivǎ

O descriem pentru început pentru X1=...=Xn={1,...,s}. Apelul iniţial este: back(1).

procedure back(k) if k=n+1 then retsol else for i=1,s xk←i; if cont(k)

then back(k+1); revenire din recursivitate else end.

Exemplu. Dorim să producem toate şirurile de n paranteze ce se închid corect.

Existǎ soluţii ⇔ n par.

Fie dif=nr( - nr). Condiţiile sunt : dif≥0 pentru k<n; dif=0 pentru k=n.

Pornirea algoritmului backtracking se face prin: a1←’( ’; dif←1; back(2);

Procedura back are următoarea formă: procedure back(k) if k=n+1 then retsol {scrie soluţia} else ak←’( ’; dif++; if dif ≤ n-k then back(k+1) dif--; ak←’)’; dif--; if dif≥0 then back(k+1) dif++; end.

Observaţie. În exemplul tratat backtracking-ul este optimal! : se avansează dacă şi numai dacă există şanse de obţinere a unei soluţii. Cu alte cuvinte, condiţiile de continuare nu sunt numai necesare, dar şi suficiente.

47

Metoda backtracking în plan

Se consideră un caroiaj (matrice) A cu m linii şi n coloane. Poziţile pot fi: - libere: aij=0; - ocupate: aij=1.

Se mai dǎ o poziţie (i0,j0). Se caută toate drumurile care ies în afara matricii, trecând numai prin poziţii libere.

Variante:

- cum pot ajunge într-o poziţie (i1,j1) dată? - se cere determinarea componentelor conexe.

Mişcǎrile posibile sunt date printr-o matrice depl cu două linii şi ndepl

coloane. De exemplu, dacă deplasările permise sunt cele către poziţiile vecine situate la Est, Nord, Vest şi Sud, matricea are forma:

⎟⎟⎠

⎞⎜⎜⎝

⎛−

−1010

0101

Bordez matricea cu 2 pentru a nu studia separat ieşirea din matrice. Pentru refacerea drumurilor, pentru fiecare poziţie atinsǎ memorăm minte

legǎtura la precedenta. Dacǎ poziţia e liberǎ şi pot continua, pun aij=-1 (a fost atinsǎ), continuăm şi apoi repunem aij←0 (întoarcere din recursivitate).

Programul în Java are următoarea formă:

class elem { int i,j; elem prec; static int m,n,i0,j0,ndepl; static int[][] mat; static int[][] depl = { {1,0,-1,0}, {0,-1,0,1} }; static { ndepl = depl[0].length; } elem() { int i,j; IO.write("m,n = "); m = (int) IO.read(); n = (int) IO.read(); // de fapt m+2,n+2 mat = new int[m][n]; for(i=1; i<m-1; i++) for(j=1; j<n-1; j++) mat[i][j] = (int) IO.read(); for (i=0; i<n; i++) {mat[0][i] = 2; mat[m-1][i] = 2; } for (j=0; j<m; j++) {mat[j][0] = 2; mat[j][n-1] = 2; } IO.write("i0,j0 = "); i0 = (int) IO.read(); j0 = (int) IO.read(); } elem(int ii, int jj, elem x) { i = ii; j = jj; prec = x; } String print(elem x) { if (x == null) return "(" + i + "," + j + ")"; else return x.print(x.prec)+" "+"("+i+","+j+")"; }

48

void p() { elem x; int ii,jj; for (int k=0; k<ndepl; k++) { ii = i+depl[0][k]; jj = j+depl[1][k]; if (mat[ii][jj] == 1); else if (mat[ii][jj] == 2) IO.writeln(print(prec)); else if (mat[ii][jj] == 0) { mat[i][j] = -1; x = new elem(ii,jj,this); x.p(); mat[i][j] = 0; } } } } class DrumPlan { public static void main(String[] args) { new elem(); elem start = new elem(elem.i0,elem.j0,null); start.p(); } } Contraexemplu. În plan, se cere sǎ se determine toate punctele în care se poate ajunge din (i0,j0), precum şi numǎrul minim de deplasǎri pânǎ la ele.

0 0 4 3 0 0 1 2

(i0,j0) Soluţia corectă constă în a folosi o coadǎ!

49

EXTINDEREA CLASELOR

Cum se definesc clasele extinse

Limbajul Java pune la dispoziţie şi o altă facilitate importantă legată de OOP : posibilitatea de extindere a claselor. Pe scurt, deci incomplet, aceasta constă în:

- o clasă poate fi extinsă, adăugându-se noi câmpuri şi noi metode, care permit considerarea unor atribute suplimentare (dacă ne gândim la câmpuri) şi unor operaţii noi (asupra câmpurilor "iniţiale", dar şi asupra câmpurilor nou adăugate);

- unele metode ale clasei pe care o extindem pot fi redefinite, iar anumite câmpuri ale acestei clase pot fi "ascunse";

- un obiect având ca tip clasa extinsă poate fi folosit oriunde este aşteptat un obiect al clasei care a fost extinsă.

La prima vedere, rezolvarea problemelor de mai sus se poate face simplu: modificăm clasa, introducând sau/şi modificând câmpurile şi metodele clasei. În practica programării, această soluţie este de neconceput. Pe de o parte se pot introduce erori, iar pe de altă parte utilizatorii clasei vechi nu vor mai putea folosi clasa aşa cum o făceau înainte şi cum vor în continuare să o facă; clasa (firma care a elaborat-o) îşi va pierde astfel vechii clienţi. Să reţinem deci ca o regulă generală de programare faptul că nu trebuie modificată o clasă testată şi deja folosită de mulţi utilizatori; cu alte cuvinte, nu trebuie modificat "contractul" ce a dus la scrierea clasei.

De aceea vechea clasă trebuie să rămână nemodificată, iar actualizarea ei trebuie făcută prin mecanismul de extindere a claselor, prezentat în continuare.

Exemplu. Să presupunem că dorim să urmărim mişcarea unui punct în plan. Vom începe prin a considera clasa:

class Punct { int x,y; Punct urm; Punct(int x, int y) { this.x=x; this.y=y; } void Origine() { x=0; y=0; } Punct Miscare(int x, int y) { Punct p = new Punct(x,y); urm=p; return p; } }

Clasa Punct conţine: - câmpurile x, y, urm ; - constructorul Punct cu signatura (int, int); - metoda Origine cu signatura () şi metoda Miscare cu signatura

(int,int).

Vom extinde clasa Punct astfel încât punctul să aibă şi o culoare: class Pixel extends Punct { String loar cu e; Pixel(int x, int y, String culoare) { super(x,y); this.culoare=culoare; } void Origine() { super.Origine(); culoare="alb"; } }

50

Clasa Pixel conţine: - câmpurile x,y,urm (moştenite de la clasa Punct) şi culoare (care a fost

adăugat prin extindere); - constructorul Pixel cu signatura (int,int,String); - metoda Miscare cu signatura (int,int), moştenită de la clasa Punct,

precum şi metoda Origine cu signatura (), care redefineşte metoda Origine a clasei Punct.

Este adoptată următoarea terminologie: clasa Punct este superclasă a lui Pixel, iar Pixel este subclasă (clasă extinsă) a lui Punct.

În Java, clasele formează o structură de arbore în care rădăcina este clasa Object, a cărei definiţie apare în pachetul java.lang. Orice clasă extinde direct (implicit sau explicit) sau indirect clasa Object. Ştim că în informatică arborii "cresc în jos", deci rădăcina (clasa Object) se află pe cel mai de sus nivel.

Termenii de superclasă şi subclasă se referă exclusiv la relaţia tată ↔ fiu, conform relaţiei de extindere, în arborele de clase. Este incorect de a interpreta aceşti termeni în sensul de incluziune!

În exemplul de mai sus, apelurile super.Origine() şi super(x,y) se referă respectiv la metoda Origine şi la constructorul din superclasa Punct a lui Pixel. Vom reveni însă cu toate detaliile legate de super.

Fie Sub o clasă ce extinde clasa Super. Sunt importante următoarele precizări:

- obiectele de tip Sub pot fi folosite oriunde este aşteptat un obiect de tipul Super. De exemplu dacă un parametru al unei metode este de tipul Super, putem invoca acea metodă cu un argument de tipul Sub;

- spunem că Sub extinde comportarea lui Super; - o clasă poate fi subclasă a unei singure clase (moştenire simplă) deoarece,

reamintim, clasele formează o structură de arbore. Drept consecinţă o clasă nu poate extinde două clase, deci nu există moştenire multiplă ca în alte limbaje (există însă mecanisme pentru a simula această facilitate şi anume interfeţele);

- o metodă din superclasă poate fi rescrisă în subclasă. Spunem că metoda este redefinită (dacă nu este statică) sau ascunsă (dacă este statică). Evident, ne referim aici la o rescriere a metodei folosind aceeaşi signatură, pentru că dacă scriem în subclasă o metodă cu o signatură diferită de signaturile metodelor cu acelaşi nume din superclasă, atunci va fi vorba de o metodă nouă. La rescriere nu putem modifica tipul valorii întoarse de metodă. Accesul la metoda cu aceeaşi signatură din superclasă se face, după cum vom vedea, prin precalificare cu super;

- un câmp redeclarat în Sub ascunde câmpul cu acelaşi nume din Super; - câmpurile neascunse şi metodele nerescrise sunt automat moştenite de

subclasă (în exemplul de mai sus este vorba de câmpurile x şi y şi de metoda Miscare);

- apelurile super din constructorii subclasei trebuie să apară ca primă acţiune.

Despre iniţializare şi constructori

Suntem acum în măsură să prezentăm mai complet şi acţiunile întreprinse la crearea unui obiect.

Prima acţiune constă în a atribui câmpurilor valorile iniţiale implicite:

51

0 - pentru tipuri numerice \u0000 - pentru tipul char false - pentru tipul boolean null - pentru referinţe (la obiecte, inclusiv tablouri şi String).

În continuare este invocat constructorul corespunzător (determinat de signatură, în acelaşi mod ca pentru metode); acţiunea sa cuprinde trei faze:

1) Invocarea unui constructor al superclasei şi anume: - explicit, cu super(...) ; - implicit: este vorba de constructorul fără argumente.

2) Executarea, în ordinea în care apar, a iniţializărilor directe ale câmpurilor; 3) Executarea corpului constructorului.

Observaţii: - un constructor poate invoca un alt constructor şi anume prin this(...);

această invocare poate avea loc numai ca primă acţiune a constructorului (deci nu pot fi invocaţi doi constructori). În schimb acest mecanism nu poate fi folosit pentru a invoca, din corpul unei metode, un constructor;

- un constructor poate invoca o metodă, caz în care se consideră implementarea metodei corespunzătoare tipului real al obiectului (vezi subcapitolul următor).

Exemplu. Să considerăm clasele:

class a { int va=1, v; a() { v=va; } } class b extends a { int vb=2; b() { v=va+vb; } }

La crearea unui obiect de tipul b, prin new b(), au loc în ordine următoarele acţiuni:

- câmpurile v, va, vb primesc valoarea implicită 0; - este invocat constructorul b; - este invocat constructorul a (al superclasei); - are loc iniţializarea directă a lui va, care primeşte valoarea 1; - este executat corpul constructorului a şi ca urmare v primeşte valoarea 1; - are loc iniţializarea directă a lui vb, care primeşte valoarea 2; - este executat corpul constructorului b şi ca urmare v primeşte valoarea 3. Dacă o clasă este declarată cu modificatorul public, constructorul implicit

are automat acest modificator. Constructorii unei clase nu sunt consideraţi membri ai clasei. De aceea ei nu

pot fi moşteniţi sau redeclaraţi. Constructorilor li se pot ataşa modificatori de acces la fel ca metodelor (vezi

subcapitolele următoare). Dar, spre deosebire de metode, un constructor nu poate fi declarat cu alţi modificatori decât cei de acces.

Într-un constructor poate fi folosită instrucţiunea return, dar neînsoţită de o expresie.

52

Dacă un constructor se invocă (direct sau indirect) pe el însuşi, la compilare este semnalată o eroare.

Într-o invocare explicită a unui constructor, argumentele nu pot fi instanţieri de câmpuri declarate în aceeaşi clasă sau într-o superclasă; de asemenea nu este permisă utilizarea lui this şi super în expresii.

Exemplificăm în continuare acest aspect pentru câmpuri.

Exemplu. Să considerăm următoarea clasă: class C { int x; int y; C() { this(x); } C(int x) { y = x; } }

În clasa C, constructorul fără parametri invocă pe cel cu un parametru. Va fi semnalată o eroare la compilare. În schimb clasa va fi corectă dacă de exemplu câmpul x ar fi fost declarat cu modificatorul static.

Rescrierea metodelor şi ascunderea câmpurilor

Câmpurile pot fi ascunse prin redeclararea lor într-o subclasă. Câmpul cu acelaşi nume din superclasă nu mai poate fi accesat direct prin numele său, dar ne putem referi la el folosind super (vezi subcapitolul următor) sau o referinţă la tipul superclasei.

O metodă declarată într-o clasă poate fi rescrisă într-o subclasă prin declararea ei în subclasă cu acelaşi nume, aceeaşi signatură şi acelaşi tip al valorii întoarse.

În metoda rescrisă putem schimba modificatorul de acces, cu condiţia ca dreptul de acces să crească; reamintim că modificatorii de acces, în ordine de la cel mai restrictiv la cel mai permisiv, sunt: private, protected, cel implicit (package) şi public.

Spunem că metodele rescrise sunt ascunse (dacă e vorba de metode statice) sau redefinite (în cazul metodelor nestatice). Nu este vorba numai de o diferenţă de terminologie, deoarece metodele statice pot fi rescrise (ascunse) numai de metode statice, iar metodele nestatice pot fi rescrise (redefinite) numai de metode nestatice. Alte precizări vor fi făcute în continuare.

Fie A o clasă şi fie B o subclasă a sa. Să considerăm următoarele patru acţiuni echivalente din punctul de vedere al obiectului a ce ia naştere:

1) A a; a = new B(...); 2) A a = new B(...); 3) A a; B b; b = new B(...); a = b; 4) A a; B b; b = new B(...); a = (A) b; Să observăm că este vorba de o conversie de la o subclasă la o superclasă,

conversie numită upcasting ; ea poate fi implicită (ca în primele trei acţiuni) sau explicită (ca în cea de a patra acţiune).

Vom spune că obiectul a are tipul declarat A şi tipul real B, ceea ce pune în evidenţă noţiunea de polimorfism.

53

Tipul real al unui obiect coincide cu tipul său declarat (este cazul obiectului b) sau este o subclasă a tipului declarat (vezi obiectul a).

Fie camp un câmp al clasei A, ce este redeclarat (ascuns) în subclasa B. Dacă obiectul a face referire la câmpul camp, atunci este vorba de câmpul declarat în clasa A, adică este folosit tipul declarat al obiectului.

Fie met o metodă a clasei A, care este rescrisă în subclasa B. La invocarea metodei met de către obiectul a, este folosită fie implementarea corespunzătoare metodei ascunse (dacă este statică), fie cea corespunzătoare metodei redefinite (dacă este nestatică). Cu alte cuvinte, pentru metode statice este folosit tipul declarat (la fel ca pentru câmpuri), iar pentru metode nestatice este folosit tipul real al obiectului. În ambele cazuri, se pleacă de la tipul indicat mai sus şi se merge în sus spre rădăcină (clasa Object) în arborele de clase până când se ajunge la primul tip în care apare metoda respectivă (evident cu signatura corespunzătoare); inexistenţa unui astfel de tip este semnalată chiar în faza de compilare.

Exemplu. Următorul program: class Super { static void met1() { IO.writeln("static_Super"); } void met2() { IO.writeln("Super"); } } class Sub extends Super { static void met1() { IO.writeln("static_Sub"); } void met2() { IO.writeln("Sub"); } } class Test1 { public static void main(String[] s) { Super Ob = new Sub(); Ob.met1(); Ob.met2(); } } produce la ieşire: static_Super Sub

Exemplu. Să considerăm următorul program: class A { String s="Super"; void scrie() { IO.writeln("A : "+s); } } class B extends A { String s="Sub"; void scrie() { IO.writeln("B : "+s); } } class AB1 { public static void main(String[] s) { B b = new B(); A a = b; a.scrie(); b.scrie(); IO.writeln(a.s + "\t" + b.s); }

54

La executare sunt tipărite următoarele: B : Sub B : Sub Super Sub adică rezultatele aşteptate, ţinând cont că:

- pentru obiectul b: tipul declarat coincide cu cel real şi este B; - pentru obiectul a: tipul declarat este A, iar tipul real este B.

Să considerăm o clasă C şi două subclase X şi Y ale sale, precum şi următoarea secvenţă de instrucţiuni: C Ob; . . . Ob = new X(...); . . . Ob = new C(...); . . . Ob = new Y(...); . . . în care Ob are mai întâi tipul real X, apoi tipul real C, apoi tipul real Y. Spunem că Ob este o variabilă polimorfică, deoarece are pe rând forma (comportamentul) a mai multor clase.

Cuvântul cheie super

Putem folosi cuvântul cheie super în orice metodă nestatică a unei clase extinse, şi anume sub una dintre formele:

- super(...) : pentru a invoca un constructor al superclasei clasei curente; - super.met(...) : pentru a invoca o metodă a superclasei, metodă ce a fost

redefinită în clasa curentă; - super.c : pentru a accesa un câmp c al superclasei, câmp ce a fost ascuns în

clasa curentă prin redefinirea sa. Observăm că la accesarea unui câmp sau a unei metode, super acţionează ca

referinţă la obiectul curent ca instanţiere a superclasei sale.

Exemplu. Programul următor: class A { String s="Super"; void scrie() { IO.writeln("A : "+s); } void metoda() { IO.writeln("A:"); } } class B extends A { String s="Sub"; void scrie() { IO.writeln("B : "+s+" "+super.s); } void metoda() { scrie(); super.scrie(); super.metoda(); } } class AB2 { public static void main(String[] x) { B b = new B(); b.metoda(); IO.writeln(b.s); IO.writeln("****************"); A a; a = b; a.metoda(); IO.writeln(a.s); IO.writeln("****************"); A c = new A(); c.metoda(); IO.writeln(c.s); } }

55

produce la ieşire următorul rezultat: B : Sub Super A : Super A: Sub **************** B : Sub Super A : Super A: Super **************** A: Super

Moştenire, polimorfism şi legare dinamică

Reamintim următoarele: - orice obiect care instanţiază o clasă poate fi folosit în orice cod menit să

lucreze cu instanţieri ale superclaselor sale; - orice obiect care instanţiază o clasă poate folosi (în modurile descrise mai

sus) codul supraclasei.

La aceste două caracteristici legate de moştenire (extinderea claselor), Java adaugă polimorfismul şi legarea dinamică, între care există o strânsă relaţie.

Polimorfismul constă în posibilitatea ca o invocare Ob.met(...) să aibă drept consecinţă invocarea unei anumite metode cu numele met, în funcţie de tipul real al obiectului Ob. Unii autori consideră că şi cele două facilităţi enunţate mai sus fac parte din conceptul de polimorfism.

Legarea dinamică identifică metoda met respectivă la executarea programului. Polimorfismul şi legarea dinamică sunt două caracteristici esenţiale ale programării orientate pe obiecte şi vor fi analizate în acest subcapitol.

Aşa cum ştim, fiecare obiect are un tip declarat şi un tip real; tipul real coincide cu cel declarat sau este un subtip al acestuia. La invocarea metodelor nestatice se foloseşte tipul real, iar la invocarea metodelor statice şi la referirea câmpurilor se foloseşte tipul declarat.

Pentru metode nestatice se foloseşte tipul real al obiectelor care le invocă deoarece:

- cronologic, superclasa a fost scrisă înaintea clasei şi este de presupus că a fost folosită de mai mulţi utilizatori, care vor în continuare să lucreze cu ea;

- în metodele noii clase se pot face referiri la câmpuri nou definite, ceea ce nu este posibil pentru metodele superclasei.

Utilizarea tipului declarat pentru metodele statice se datorează următorului fapt: compilatorul "face tot ce poate" pentru a detecta metoda ce trebuie invocată. Java foloseşte legarea dinamică, adică identificarea metodei nestatice concrete care este folosită la o invocare se face la executare şi nu la compilare. De aceea legarea dinamică se mai numeşte legare târzie.

Necesitatea legării dinamice apare din următorul exemplu:

56

Exemplu. Fie A o clasă în care este definită o metodă met, iar B o subclasă a sa în care metoda met este redefinită. Secvenţa de instrucţiuni: double d = IO.read(); A Ob; if (d>0) Ob = new A(...); else Ob = new B(...); Ob.met(...); arată că doar la momentul invocării metodei devine clar care dintre cele două metode met va fi invocată.

Despre modificatori

Reluăm discuţia despre modificatori, pentru a include şi aspectele legate de extinderea claselor.

Lista completă a modificatorilor folosiţi în Java este următoarea: - modificatorii de acces (public, protected, private şi cel implicit); - abstract, static, final, synchronized, native, transient,

volatile.

Ei pot fi folosiţi astfel: - pentru clase: public,cel implicit, abstract, final; - pentru interfeţe: modificatorii de acces; - pentru constructori: modificatorii de acces; - pentru câmpuri: modificatorii de acces, final, static, transient,

volatile; - pentru metode: modificatorii de acces, final, static, abstract,

synchronized, native.

Modificatorul final poate fi asociat (în afara variabilelor locale şi câmpurilor) şi metodelor şi claselor. El trebuie înţeles în sensul de "variantă finală":

- o metodă cu acest modificator nu poate fi rescrisă într-o subclasă; - o clasă cu acest modificator nu poate fi extinsă. Metodele declarate cu private sau/şi static sunt echivalente cu final,

din punctul de vedere al redefinirii: nu pot fi redefinite. Dacă o metodă este finală, "ne putem baza" pe implementarea ei (bineînţeles

dacă nu invocă metode nefinale). În unele situaţii, este bine să marcăm toate metodele cu final, dar nu şi clasa.

57

Vizibilitate şi acces Pachetele, clasele, metodele, câmpurile şi variabilele sunt identificate prin numele lor. Problema care se pune este de a stabili din ce loc putem face referire la aceste nume (cu semnificaţia dorită), adică de a preciza domeniul lor de vizibilitate. • Variabile locale şi etichete Prin bloc înţelegem o secvenţă (eventual vidă) de instrucţiuni, cuprinsă între acolade. Un bloc este o instrucţiune şi de aceea poate fi folosit în orice loc unde poate să apară o instrucţiune. De exemplu orice metodă şi orice constructor sunt formate dintr-un antet urmat de un bloc. În schimb ceea ce urmează după modificatorii şi numele unei clase nu constituie un bloc, deşi apar acoladele deschisă şi închisă: conţinutul unei clase nu este o succesiune de instrucţiuni. Orice bloc poate conţine la rândul său un alt bloc, putând astfel lua naştere o structură imbricată de blocuri. Prin variabilă locală înţelegem o variabilă declarată în interiorul unui bloc, inclusiv într-o instrucţiune for. Domeniul de vizibilitate al unei variabile locale este constituit din partea din blocul în care a fost declarată, ce urmează declarării. Prin urmare o variabilă locală nu poate fi referită înainte de a fi declarată. Variabilele locale există numai pe perioada în care blocul în care sunt declarate este în curs de executare.

Nu putem folosi facilitatea de imbricare a blocurilor pentru a redeclara o variabilă locală. O variabilă locală nu poate fi redefinită nici în blocul în care a fost declarată, nici într-un bloc inclus în acesta. Regulile care guvernează domeniul de vizibilitate al etichetelor sunt aceleaşi ca pentru variabilele locale. • Parametrii metodelor şi constructorilor Numele parametrilor dintr-o metodă sau dintr-un constructor sunt vizibile doar în interiorul acestora, adică în blocul care urmează antetului metodei sau constructorului. Este însă posibil ca într-un bloc dintr-o metodă sau dintr-un constructor să redeclarăm numele unui parametru; în acest caz, în partea din bloc ce urmează redeclarării, numele respectiv este considerat ca având semnificaţia dată de redeclarare. Cu alte cuvinte, domeniul de vizibilitate al unui parametru este constituit din corpul metodei sau constructorului în care apare, mai puţin blocurile (evident disjuncte) în care este redeclarat. • Vizibilitatea în interiorul unei clase Ştim că o clasă este constituită din câmpuri, constructori (folosiţi la crearea de obiecte) şi metode (folosite la invocarea lor). Din orice constructor şi din orice metodă putem să ne referim la orice câmp sau metodă a clasei. De asemenea dintr-un constructor putem apela alt constructor prin this urmat, între paranteze, de o listă de argumente ce respectă signatura noului constructor.

58

Ordinea în care apar câmpurile nestatice şi metodele în cadrul clasei nu este relevantă (de exemplu nu contează dacă un câmp nestatic este declarat la începutul sau la sfârşitul clasei). Totuşi, dacă numele unui câmp este redeclarat într-o metodă (este folosit ca nume al unui parametru sau declarat într-un bloc), atunci declararea cea mai interioară este cea care primează când se face o referire la acel nume (identificator). Putem spune că un parametru poate ascunde un câmp, iar o variabilă locală poate ascunde un parametru şi/sau un câmp. După cum vom vedea în continuare, numele unei metode nu poate fi ascuns. • Modificatorul final Modificatorul final poate fi ataşat atât variabilelor (locale sau câmpuri), cât şi metodelor. În cazul variabilelor locale, variabilei i se atribuie valoare la declarare sau înainte de a fi folosită; variabila nu poate primi de două ori valoare. Menţionăm că final este singurul modificator ce poate fi ataşat unei variabile locale. Unui câmp final trebuie să i se atribuie valoare fie prin iniţializare, fie prin constructori. Menţionăm că în general modificatorul final este folosit împreună cu static, pentru a trata un câmp ca o "constantă cu nume". Efectul modificatorului final asupra metodelor şi claselor va fi prezentat atunci când vom vorbi despre extinderea claselor. • Modificatorul static Modificatorul static poate fi folosit la declararea câmpurilor şi metodelor unei clase. O variabilă locală nu poate fi declarată cu static . Fie c un câmp declarat cu static în clasa Clasa. Această declarare are două consecinţe:

- câmpul c este comun tuturor obiectelor de tipul Clasa; - referirea la câmp din exteriorul clasei se face fie conform regulii generale

(prin crearea şi utilizarea unei instanţe a clasei Clasa), fie direct, prin precalificarea câmpului cu numele clasei (Clasa.c). Fie acum met o metodă declarată cu modificatorul static în clasa Clasa; ea se numeşte metodă statică sau metodă de clasă. Invocarea ei se poate face fie conform regulii generale (prin crearea şi utilizarea unei instanţe a clasei Clasa), fie direct, prin precalificarea metodei cu numele clasei: Clasa.met(...) ; De aceea într-o metodă statică nu poate fi folosită referinţa this. O metodă statică poate accesa numai câmpurile şi metodele statice ale clasei din care face parte sau a altei clase. Metodele statice (de clasă) sunt folosite de obicei pentru a efectua prelucrări asupra câmpurilor statice ale clasei. Putem "ocoli" însă această regulă de exemplu astfel:

- la invocarea metodei îi transmitem ca parametru o referinţă la un obiect; - în metodă construim explicit un obiect de tipul clasei la ale cărei metode şi câmpuri dorim să ne referim.

59

• Modificatorii de acces Toate câmpurile şi metodele unei clase sunt accesibile (pot fi referite) din interiorul clasei. Rolul modificatorilor public, protected, private şi cel implicit (numit uneori package) referitor la accesul din exteriorul unei clase la membrii săi este sintetizat în următorul tabel:

Modificator Membrii clasei cu acest modificator sunt accesibili ...

public de oriunde clasa este accesibilă protected din cod din acelaşi pachet implicit (package )

din cod din acelaşi pachet

private numai din interiorul clasei Reamintim că modificatorii de mai sus joacă un rol nu numai în privinţa accesului, dar şi pentru facilitatea de extindere a claselor, ceea ce va face diferenţa între modificatorul protected şi cel implicit. • Determinarea semnificaţiei unui nume Pentru un identificator folosit ca nume de variabilă (locală sau câmp), metodă sau clasă, semnificaţia sa se obţine la prima căutare încununată de succes din următorul şir de căutări succesive:

1) variabilele locale declarate într-un bloc sau un ciclu for; 2) numai dacă suntem în interiorul unei metode sau a unui constructor:

parametrii metodei sau constructorului; 3) membrii clasei, inclusiv cei rezultaţi prin extinderea claselor (vezi capitolul

următor) 4) tipuri importate explicit; 5) tipuri declarate în acelaşi pachet; 6) tipuri importate implicit; 7) pachete disponibile pe sistemul gazdă.

Mai mult, se face distincţie clară între tipurile de identificatori: nume de variabile (locale), de pachete, de clase, de metode şi de câmpuri; iată de ce numele unei metode nestatice nu poate fi ascuns. Aceasta permite să folosim un acelaşi identificator pentru a numi una sau mai multe astfel de entităţi.

Exemplul 3. Următoarea clasă este corectă din punct de vedere sintactic, compilatorul nesemnalând vreo eroare:

class obsesie { obsesie obsesie; obsesie() { obsesie = new obsesie(); } obsesie obsesie (obsesie obsesie) { obsesie: while (obsesie != null) if obsesie.obsesie(obsesie)==obsesie ) break obsesie; ( return obsesie; } }

60

Nu recomandăm însă să abuzăm în acest mod de distincţia menţionată. Clasa

de mai sus poate fi scrisă sub următoarea formă mai clară şi "neobsesivă": class obsesie { obsesie C; obsesie() { C = new obsesie(); } obsesie met (obsesie param) { et: while (param != null) { if ( param.met(param)==param ) break et; } return param; } }

61

Principiul lui Dirichlet Principiul lui Dirichlet are un enunţ simplu şi care nu necesită demonstraţie:

Dacă m>k×n obiecte sunt plasate în n căsuţe, atunci va exista o căsuţă ce va conţine mai mult de k obiecte.

Prezentăm în continuare câteva aplicaţii ale acestui principiu.

Exemplul 1. Există un număr de n perechi de pantofi de mărimi diferite, dar nearanjaţi pe perechi. Care este numărul minim de pantofi care trebuie cercetaţi pentru a forma o pereche ?

Răspunsul este imediat. Folosim câte o cutie (iniţial goală) pentru fiecare mărime. Este evident că după aşezarea în cutii a n+1 pantofi, o cutie va conţine doi pantofi (m=n+1, k=1).

Exemplul 2. Se consideră un vector a=(a1,...,an) de numere naturale. Se caută indicii

i<j cu ai+...+aj multiplu de n. În continuare, pentru orice număr natural x, vom nota prin x clasa sa de echivalenţă

modulo n. Considerăm sumele sk=a1+...+ak pentru k=1,...,n. Fie sk clasele de echivalenţă

corespunzătoare. Deosebim două situaţii:

1) dacă există k cu sk=0, atunci o soluţie este (i,j)=(1,k); 2) în caz contrar, este clar că s1,...,sn∈{1,2,...,n-1}. Conform principiului lui Dirichlet,

vor exista indicii k<l cu sk=sl. Atunci o soluţie este (i,j)=(k+1,l). Exemplul 3. Pentru un număr natural n dat, caut un multiplu N al său în a cărei scriere

obişnuită (în baza 10) apar numai cifrele 0 şi 1. Problema este asemănătoare celei precedente. Pentru k=1,...,n consider numărul sk a cărui scriere în baza 10 este formată din k de

1, adică s1=1, s2=11 etc.; fie sk clasa de echivalenţă modulo n corespunzătoare. La fel ca mai sus, deosebim două situaţii:

1) dacă există k cu sk=0, atunci o soluţie este chiar sk; 2) în caz contrar, este clar că s1,...,sn∈{1,2,...,n-1}. Conform principiului lui Dirichlet,

vor exista indicii k<l cu sk=sl. Atunci o soluţie este sl-sk, adică numărul în a cărei scriere apar l-k de 1 urmaţi de k de 0.

Exemplul 4. Teorema lui Erdös. Se dau (m-1)(n-1)+1 numere naturale oarecare. Să se arate că printre ele există m care

se divid unul pe altul, sau există n care nu se divid între ele. Vom aplica tot principiul lui Dirichlet, dar în plan. Se ordonează mai întâi crescător numerele date. Consider un caroiaj cu n-1 linii şi m-1 coloane. Mai consider că există şi linia imaginară

cu numărul de ordine 0, pe care este plasat numărul 1.

62

Considerăm pe rând numerele (în ordine crescătoare). Fiecare număr va fi plasat pe linia i cu i minim şi cu proprietatea că numărul curent se divide cu un număr aflat pe o linie anterioară.

Pentru exemplificare, să considerăm că m=5, n=4, iar numerele sunt: 3,5,9,12,14,15,33,x,... După plasarea primelor 8 numere, suntem în situaţia:

3 5 14 9 12 15 33 24

Dacă de exemplu x=72, atunci el ar trebui plasat pe a patra linie (inexistentă) şi am obţine n=4 numere care se divid unul pe altul (de exemplu 3, 12, 24, 72). Dacă de exemplu x=35, atunci el ar trebui plasat pe a doua linie şi am obţine m=5 numere care nu se divid între ele: 9, 12, 15, 33, 35.

Este important de notat că pe fiecare linie numerele plasate apar în ordine crescătoare. Principiul lui Dirichlet ne asigură că cel mai târziu după plasarea ultimului număr vom ieşi din "cutie": aici caroiajul (n-1)×(m-1).

O variantă a principiului lui Dirichlet este următoarea:

Fie k1,...kn , K=(k1+...+kn)/n şi x un număr oarecare. Atunci: dacă x<K ⇒ ∃i cu x<ki dacă x>K ⇒ ∃i cu x>ki

Exemplul 5. Dacă vârfurile unui decagon sunt etichetate distinct cu numerele 0,1,...,9 într-

o ordine oarecare, atunci există 3 vârfuri consecutive pentru care suma etichetelor este mai mare decât 13.

Fie xi∈{0,1,...,9} eticheta vârfului i, pentru i=1,...,10. Considerăm numerele:

k1=x1+x2+x3 k2=x2+x3+x4. . . . . k9=x9+x10+x1 k10=x10+x1+x2 Atunci K=(k1+...+kn)/n = 3(0+1+...+9)/10 = 13,5. Conform principiului lui Dirichlet, va exista i cu ki>13,5>13. Exemplul 6. Se consideră m calculatoare şi n imprimante (m>n). Fie α=numărul minim de legături calculator↔imprimantă ce trebuie stabilite, astfel încât dacă orice n calculatoare doresc să scrie simultan, acest lucru să fie este posibil. Se cere să se arate că α≥n(m-n+1). Fie ki numărul de calculatoare legate la imprimanta i. Numărul de legături este deci α=(k1+...+kn).

63

Dacă α<n(m-n+1), atunci (k1+...+kn)/n<m-n+1. Conform variantei principiului lui Dirichlet, există o imprimantă i legată la cel mult m-n calculatoare, deci care nu este legată la cel puţin n calculatoare; dacă acestea vor să scrie simultan, nu vor reuşi. Contradicţie. Exerciţiu. Să se descrie o modalitate prin care problema poate fi rezolvată cu exact n(m-n+1) legături.

64

Metoda Divide et Impera Metoda Divide et Impera ("desparte şi stăpâneşte") constă în împărţirea repetată a unei probleme de dimensiuni mari în mai multe subprobleme de acelaşi tip, urmată de rezolvarea acestora şi combinarea rezultatelor obţinute pentre a determina rezultatul corespunzător problemei iniţiale. Pentru fiecare subproblemă procedăm în acelaşi mod, cu excepţia cazului în care dimensiunea ei este suficient de mică pentru a fi rezolvată direct. Este evident caracterul recursiv al acestei metode. • Schema generală

Descriem schema generală pentru cazul în care aplicăm metoda pentru o prelucrare oarecare asupra elementelor unui vector. Funcţia DivImp, care întoarce rezultatul prelucrării asupra unei subsecvenţe ap,...au, va fi apelată prin DivImp(1,n).

function DivImp(p,u)

up if u–p<ε then r ← Prel(p,u) else m ← Interm(p,u); r1 ← DivImp(p,m); r2 ← DivImp(m+1,u); r ← Combin(r1,r2) return r end; unde: - funcţia Interm întoarce un indice în intervalul p..u (de obicei m=⎣(p+u)/2⎦ ). - funcţia Prel este capabilă să întoarcă rezultatul subsecvenţei p..u, dacă aceasta este

suficient de mică; - funcţia Combin întoarce rezultatul asamblării rezultatelor parţiale r1 şi r2.

Exemple: Calculul maximului elementelor unui vector; Parcurgerile în preordine, inordine şi postordine ale unui arbore binar; Sortarea folosind arbori de sortare.

165

Căutarea binară Se consideră vectorul a=(a1, ...,an) ordonat crescător şi o valoare x. Se cere

să se determine dacă x apare printre componentele vectorului. Problema enunţată constituie un exemplu pentru cazul în care problema se reduce

la o singură subproblemă. Ţinând cont de faptul că a este ordonat crescător, vom compara pe x cu elementul din "mijlocul" vectorului. Dacă avem egalitate, algoritmul se încheie; în caz contrar vom căuta fie în "jumătatea" din stânga, fie în cea din dreapta. Vom adăuga a =-∞, a0 n+1=+ ∞. Căutăm perechea (b,i) dată de: (true,i) dacă ai=x; (false,i) dacă ai-1<x<ai.

Deoarece problema se reduce la o singură subproblemă, nu mai este necesar să

folosim recursivitatea. Algoritmul este următorul:

procedure CautBin p ← u; u ← n while p≤u i ← ⎣(p+u)/2⎦ case ai>x : u ← i-1 ai=x : write(true,i); stop ai<x : p ← i+1 write(false,p) end Algoritmul necesită o mică analiză, legată de corectitudinea sa parţială. Mai precis, ne întrebăm: când se ajunge la p>u? pentru cel puţin 3 elemente : nu se poate ajunge la p>u; pentru 2 elemente, adică pentru u=p+1: se alege i=p. Dacă x<ai, atunci u←p-1. Se

observă că se iese din ciclul while şi ai-1<x<ai=ap; pentru un element, adică p=u: se alege i=p=u. Dacă x<ai atunci u←p-1, iar dacă x>ai atunci p←u+1; în ambele cazuri se părăseşte ciclul while şi tipăreşte un rezultat corect.

• Problema turnurilor din Hanoi

Se consideră 3 tije. Iniţial pe tija 1 se află n discuri cu diametrele decrescătoare privind de la bază către vârf, iar pe tijele 2 şi 3 nu se află nici un disc. Se cere să se mute aceste discuri pe tija 2, ajutându-ne şi de tija 3, respectând condiţia ca în permanenţă pe orice tijă sub orice disc să se afle baza tijei sau un disc de diametru mai mare.

266

O mutare este notată prin (i,j) şi semnifică deplasarea discului din vârful tijei i deasupra discurilor aflate pe tija j. Se presupune că mutarea este corectă (vezi condiţia de mai sus).

Fie H(m;i,j) şirul de mutări prin care cele m discuri din vârful tijei i sunt

mutate peste cele de pe tija j, folosind şi a treia tijă, al cărei număr este evident 6-i-j. Problema constă în a determina H(n;1,2).

Se observă că este satisfăcută relaţia: H(m;i,j)= H(m-1;i,j) (i,j) H(m-1;i,j) (*) respectându-se condiţia din enunţ. Deci problema pentru m discuri a fost redusă la două probleme pentru m-1 discuri, al căror rezultat este asamblat conform (*). Corespunzător, vom executa apelul Hanoi(n,1,2), unde procedura Hanoi are forma: procedure Hanoi(n,i,j) if n=1 then write(i,j) else k←6-i-j; Hanoi(n-1,i,k); Hanoi(1,i,j); Hanoi(n-1,k,j) end Observaţie. Numărul de mutări este 2n-1. • Sortare prin interclasare

Fie a=(a1,...,an) vectorul care trebuie ordonat crescător. Ideea este următoarea: împărţim vectorul în doi subvectori, ordonăm crescător

fiecare subvector şi asamblăm rezultatele prin interclasare. Se observă că este aplicată tocmai metoda Divide et Impera.

Începem cu procedura de interclasare. Fie secvenţa de indici p..u şi fie m un

indice intermediar. Presupunând că (ap,...,am) şi (am+1,...,au) sunt ordonaţi crescător, procedura Inter va ordona crescător întreaga secvenţă (ap,...,au).

Mai precis, vom folosi notaţiile: k1 = indicele curent din prima secvenţă; k2 = indicele curent din a doua secvenţă; k3 = poziţia pe care va fi plasat cel mai mic dintre ak1 şi ak2 într-un vector auxiliar b. procedure Inter(p,m,u) k1←p; k2←m+1; k3←p; while k1≤m & k2≤u if ak1<ak2 then k1←k1+1; bk3←ak1 else k2←k2+1; bk3←ak2 k3←k3+1

367

if k1>m { au fost epuizate elementelei primei subsecvenţe } then for i=k2,u bk3←ai; k3←k3+1 else { au fost epuizate elementelei primei subsecvenţe } for i=k1,m bk3←ai; k3←k3+1 for i=p,u ai←biend

Timpul de calcul este de ordinul O(u-p), adică liniar în lungimea secvenţei analizate.

Programul principal urmează întocmai strategia Divide et Impera, deci se face

apelul SortInter(1,n), unde procedura recursivă SortInter are forma: procedure SortInter(p,u) if p=u then else m←⎣(p+u)/2⎦; SortInter(p,m); SortInter(m+1,u); Inter(p,m,u) end

Calculăm în continuare timpul de executare T(n), unde T(n) se poate scrie: • t0 (constant), pen tru n=1; • 2T(n/2)+an, pentru n>1, unde a este o constantă: problema de dimensiune n s-a

descompus în două subprobleme de dimensiune n/2, iar combinarea rezultatelor s-a făcut în timp liniar (prin interclasare).

Presupunem că n=2k. Atunci:

T(n) = T(2k) =2 T(2k-1) + a 2k = =2[2T(2k-2) + a 2k-1] + a 2k = 22T(2k-2) + 2 a 2k =

=22[T(2k-3) + a 2k-2] + 2 a 2k = 2 T(23 k-3) + 3 a 2k = . . . = 2iT(2k-i) + i a 2k = . . . =2kT(0) + k a 2k = nt0 + a n log n. 2

Rezultă că T(n)=0(n.log n).

Se observă că s-a obţinut acelaşi timp ca şi pentru sortarea cu ansamble. Menţiune. Se poate demonstra că acest timp este optim.

468

Metoda Quicksort

Prezentăm încă o metodă de sortare a unui vector a=(a1,...,an). Va fi aplicată tot metoda Divide et Impera. Şi de această dată fiecare problemă va fi descompusă în două subprobleme mai mici de aceeaşi natură, dar nu va mai fi necesară combinarea (asamblarea) rezultatelor rezolvării subproblemelor.

Fie (ap,...,au) secvenţa curentă care trebuie sortată. Vom poziţiona pe ap în secvenţa (ap,...,au), adică printr-o permutare a elementelor secvenţei: x=ap va trece pe o poziţie k; toate elementele aflate la stânga poziţiei k vor fi mai mici decât x; toate elementele aflate la dreapta poziţiei k vor fi mai mari decât x.

În acest mod ap va apărea pe poziţia sa finală, rămânând apoi să ordonăm crescător elementele aflate la stânga sa, precum şi pe cele aflate la dreapta sa.

Fie poz funcţia cu parametrii p,u care întoarce indicele k pe care va fi poziţionat

ap în cadrul secvenţei (ap,...,au). Atunci sortarea se realizează prin apelul QuickSort(1,n), unde procedura

QuickSort are forma:

procedure QuickSort(p,u) if p=u then else k ← poz(p,u); QuickSort(p,k-1); QuickSort(k+1,n) end Funcţia poz lucrează astfel: function poz(p,u) i←p; j←u; ii←0; jj←-1 while i<j if ai<aj then else ai<aj; (ii,jj) ← (-ii,-jj) i←i+ii; j←j+jj (*) poz ← i end Să urmărim cum decurg calculele pentru secvenţa: (a4,...,a11)=(6,3,2,5,8,1,9,7) se compară 6 cu a11,a10,... până când găsim un element mai mic. Acesta este a9=1. Se interschimbă 6 cu 1. Acum secvenţa este (1,3,2,5,8,6,9,7) şi vom lucra în continuare pe subsecvenţa (3,2,5,8,6), schimbând direcţia de comparare conform (*);

6 va fi comparat succesiv cu 3,2,... până când găsim un element mai mare. Acesta este a8=8. Se interschimbă 6 cu 8.

569

Se obţine astfel (1,3,2,5,6,8,9,7), în care la stânga lui 6 apar valori mai mici, iar la dreapta lui 6 apar valori mai mari, deci l-am poziţionat pe 6 pe poziţia 8, valoare întoarsă de funcţia poz. Observaţie. Cazul cel mai defavorabil pentru metoda Quicksort este cel în care vectorul este deja ordonat crescător: se compară a1 cu a2,...,an rezultând că el se află pe poziţia finală, apoi se compară a2 cu a3,...,an rezultând că el se află pe poziţia finală etc. Trecem la calculul timpul mediu de executare al algoritmului Quicksort. Vom număra câte comparări se efectuează (componentele vectorului nu sunt neapărat numere, ci elemente dintr-o mulţime ordonată oarecare). Timpul mediu este dat de formulele:

( )⎪⎩

⎪⎨⎧

==

∑ −+−+−==

00T(1)

k)]T(n1)[T(kn1

1nT(n)n

1k

T

deoarece: în cazul cel mai defavorabil a1 se compară cu celelalte n-1 elemente; a1 poate fi poziţionat pe oricare dintre poziţiile k=1,2,...,n; considerăm aceste

cazuri echiprobabile; T(k-1) este timpul (numărul de comparări) necesar ordonării elementelor aflate la

stânga poziţiei k, iar T(n-k) este timpul necesar ordonării elementelor aflate la dreapta poziţiei k.

nT(n) = n(n-1)+2[T(0) +T(1)+….+T(n-1)] (n-1)T(n-1) = (n-1)(n-2)+2[T(0)+….+T(n-2)] Scăzând cele două relţii obţinem: nT(n)–(n-1)T(n-1) = 2(n-1)+ 2T(n-1), dci: nT(n) = (n+1)T(n-1)+2(n-1). Împart cu n(n+1):

⎟⎠⎞

⎜⎝⎛ −+=

⎟⎠⎞

⎜⎝⎛

−−+

−−

=−

⎟⎠⎞

⎜⎝⎛ −

++

−=

+

+−

+−

=+

21

32

22

T(1)3

T(2)

...........................

1n1

n2

21)T(n2)T(n

n1)T(n

n1

1n2

2T(n)

1)T(n1n

T(n)

1)n(n1)2(n

n1)T(n

1nT(n)

Prin adunarea relaţiilor de mai sus obţinem:

2 3 n n+1

f(x)=ln x

11n

231

.....n1

1n1

21n

T(n)−

++⎟

⎠⎞

⎜⎝⎛ +++

+=

+

Cum suma ultimilor doi termeni este negativă, rezultă:

670

1n2

1n

2|2lnxdx

x1

1nT(n) +

+∫ =≤

+ ≤ 2 ln(n+1)

(am folosit o inegalitate bazată pe sumele Rieman pentru funcţia f(x)=ln x). Deci T(n)=0(n.log n).

Încheiem cu menţiunea că metoda Divide et Impera are o largă aplicativitate în calculul paralel.

771

Metoda programării dinamice

Vom începe prin a enunţa o problemă generală şi a trece în revistă mai mulţi algoritmi de rezolvare. Abia după aceea vom descrie metoda programării dinamice. 1. O problemă generală

Fie A şi B două mulţimi oarecare. Fiecărui element x∈A urmează să i se asocieze o valoare v(x)∈B. Iniţial v este cunoscută doar pe X⊂A, X≠Ø. Fiecărui x∈A\X îi asociem:

Ax⊂A : mulţimea elementelor din A de a căror valoare depinde v(x); fx : funcţie care specifică dependenţa de mai sus. Dacă Ax={a1,...,ak},

atunci v(x)=fx(v(a1),...,v(ak)). Se mai dă z∈A. Se cere să se calculeze, dacă este posibil, valoarea v(z).

Exemplu.

A={1,2,...,12}; X={1,2,6,7,8,9}; A3={1,2}; A4={1,2,3}; A5={1,4}; A10={7,8}; A11={8,9}; A12={10,11}.

Elementele din X au asociată valoarea 1. Fiecare funcţie fx calculează v(x) ca fiind suma valorilor elementelor din Ax. z=5. Este evident că vom obţine v=(1,1,2,4,5,1,1,1,1,1,2,2,4). O ordine

posibilă de a considera elementele lui A\X astfel încât să putem calcula valoarea asociată lor este: 3,10,11,12,4,2.

Lucrurile devin mai clare dacă reprezentăm problema pe un graf de dependenţe.

Vârfurile corespund elementelor din A, iar descendenţii unui vârf x sunt vârfurile din Ax. Vârfurile din X apar îngroşate.

10

5 4

2 1

3 6 11

12

7 8 9 10

72

Problema enunţată nu are totdeauna soluţie, aşa cum se vede pe graful de dependenţe de mai jos, în care există un circuit. z=3.

1

3

4 2

Observaţii: - A poate fi chiar infinită; - B este de obicei N, Z, R, {0,1} sau un produs cartezian; - fx poate fi un minim, un maxim, o sumă etc.

Pentru orice x∈A, spunem că x este accesibil dacă, plecând de la X, poate fi calculată valoarea v(x). Evident, problema are soluţie dacă şi numai dacă z este accesibil.

Pentru orice x∈A, notăm prin Ox mulţimea vârfurilor observabile din x, adică

mulţimea vârfurilor y pentru care există un drum de la y la x. Problema enunţată are soluţie dacă şi numai dacă: 1) Oz nu are circuite; 2) vârfurile din Oz în care nu sosesc arce fac parte din X.

Prezentăm în continuare mai multe metode de rezolvare a problemei enunţate.

• Metoda şirului crescător de mulţimi

Fie A o mulţime finită şi X o submulţime a sa. Definim următorul şir crescător de mulţimi:

X0 = X Xk+1 = Xk ∪ {x ∈ A⏐Ax ⊂ Xk}, ∀k>0

Evident, X0 ⊂ X1 ⊂ ... ⊂ Xk ⊂ Xk+1 ⊂ ...

Propoziţie. Dacă Xk+1=Xk, atunci Xk+i=Xk ,∀i∈N. Facem demonstraţia prin inducţie după i. Pentru i=1 rezultatul este evident.

Presupunem Xk+i=Xk şi demonstrăm că Xk+i+1=Xk : Xk+i+1 = cf. definiţiei şirului de mulţimi = Xk+i ∪ {x ∈ A ⏐ Ax⊂Xk+i} = cf. ipotezei de inducţie = Xk ∪ {x ∈ A ⏐ Ax⊂Xk} = cf. definiţiei şirului de mulţimi = Xk+1 = cf. ipotezei de inducţie = Xk.

73

Consecinţe.

- ne oprim cu construcţia şirului crescător de mulţimi la primul k cu Xk=Xk+1 (A este finită!);

- dacă aplicăm cele de mai sus pentru problema generală enunţată, aceasta are soluţie dacă şi numai dacă z∈Xk.

Prezentăm în continuare algoritmul corespunzător acestei metode, adaptat la

problema generală. Vom lucra cu o partiţie A=U∪V, unde U este mulţimea curentă de vârfuri a căror

valoare asociată este cunoscută.

U ← X; V ← A\X repeat W ←V for toţi x∈V if Ax⊂U then U ←U ∪{x}; V ←V\{x} calculează v(x) conform funcţiei fx if x=z then write v(x); stop until V=W { nu s-a avansat! } write(z, 'nu este accesibil’)

Metoda descrisă are două deficienţe majore:

- la fiecare reluare se parcurg toate elementele lui V; - nu este precizată o ordine de considerare a elementelor.

Aceste deficienţe fac ca această metodă să nu fie performantă.

Metoda şirului crescător de mulţimi este larg folosită în teoria limbajelor formale, unde de cele mai multe ori ne interesează existenţa unui algoritm şi nu performanţele sale. • Sortarea topologică

Fie A={1,…..,n} o mulţime finită. Pe A este dată o relaţie tranzitivă, notată prin "<". Relaţia este dată prin mulţimea perechilor (i,j) cu i<j.

Se cere să se listeze elementele 1,..,n ale mulţimii într-o ordine ce satisface cerinţa: dacă i<j, atunci i apare la ieşire înaintea lui j.

Problema enunţată apare de exemplu la înscrierea unor termeni într-un dicţionar

astfel încât explicaţiile pentru orice termen să conţină numai termeni ce apar anterior. Este evident că problema se transpune imediat la grafurile de dependenţă: se cere

o parcurgere a vârfurilor grafului astfel încât dacă există un arc de la i la j, atunci i trebuie vizitat înaintea lui j.

74

Observaţii: - problema are soluţie dacă şi numai dacă graful este aciclic; - dacă există soluţie, ea nu este neapărat unică.

În esenţă, algoritmul care urmează repetă următorii paşi:

- determină i care nu are predecesori; - îl scrie; - elimină perechile pentru care sursa este i.

Fie M mulţimea curentă de vârfuri. Iniţial M=A. Fie C coada elementelor din M care nu au predecesori. Pentru fiecare i∈A, considerăm:

Si = lista succesorilor lui i; nrpredi = numărul predecesorilor lui i din mulţimea M curentă.

Etapa de iniţializare constă în următoarele:

Si ← Ø, nrpredi←0, ∀i C ← Ø; nr ← 0 { nr este numărul elementelor produse la ieşire } for k=1,m { m este numărul perechilor din relaţia "<" } read(i,j) Si ⇐ j; nrpredj ← nrpredj+1 for i=1,n if nrpredi=0 then i ⇒ C Să observăm că timpul cerut de etapa de iniţializare este de ordinul O(m+n). Algoritmul propriu-zis, adaptat la problema generală, este următorul: while C ≠Ø i ⇐ C; write(i); calculează v(x) conform funcţiei fx if i=z then write v(i); stop for toţi j∈Si nrpredj ← nrpredj-1 if nrpred =0 then j ⇒ C j

if nr<n then write('Nu)

Fiecare executare a lui while necesită un timp proporţional cu ⏐Si⏐. Dar |S1|+...+|Sn|=m, ceea ce face ca timpul de executare să fie de ordinul O(m).

Ţinând cont şi de etapa de iniţializare, rezultă că timpul total este de ordinul O(m+n), deci liniar.

Totuşi, sortarea topologică aplicată problemei generale prezintă un dezavantaj: sunt calculate şi valori ale unor vârfuri "neinteresante", adică neobservabile din z.

75

• Încercare cu metoda Divide et Impera

Este folosită o procedură DivImp, apelată prin DivImp(z). procedure DivImp(x) for toţi y∈A \X x

DivImp(y) calculează v(x) conform funcţiei fxend; Apare un avantaj: sunt parcurse doar vârfurile din Oz. Dezavantajele sunt însă decisive pentru renunţarea la această încercare:

- algoritmul nu se termină pentru grafuri ciclice; - valoarea unui vârf poate fi calculată de mai multe ori, ca de exemplu pentru

situaţia: • Soluţie finală

Etapele sunt următoarele: - Identificăm Gz = subgraful asociat lui Oz ; - Aplicăm sortarea topologică.

Fie Gz=(Xz,Mz). Iniţial Xz=Ø, Mz=Ø. Pentru a obţine graful Gz executăm apelul DF(z), unde procedura DF este:

procedure DF(x) x ⇒ Xz for toţi y∈Ax if y∉Xz then (y,x) ⇒ Mz; DF(y) end;

Timpul este liniar. Observaţie. Ar fi totuşi mai bine dacă :

- am cunoaşte de la inceput Gz; - forma grafului ar permite o parcurgere mai simplă.

76

2. Metoda programării dinamice Definim un PD–arbore de rădăcină z ca fiind un graf de dependenţe în care:

- ∀x, x∈Oz (există drum de la x la z); - X={x⏐grad-(x)=0}.

Exemplu. Următorul graf este un PD-arbore de rădăcină z=5.

55

Un PD-arbore nu este neapărat un arbore, dar: - poate fi pus pe niveluri: fiecare vârf x va fi pus pe nivelul egal cu lungimea celui

mai lung drum de la x la z; - poate fi parcurs (cu mici modificări) în postordine;

Prin parcurgerea în postordine, vârfurile apar sortate topologic.

Algoritmul de parcurgere în postordine foloseşte un vector parcurs pentru a ţine evidenţa vârfurilor vizitate. Este iniţializat vectorul parcurs şi se începe parcurgerea prin apelul postord(z):

for toate vârfurile x parcurs(x) ← x∈X postord(z)

unde procedura postord are forma: procedure postord(x) for toţi j∈Ax cu parcurs(j)=false postord(j) calculează v(x) conform funcţiei fx; parcurs(x)←true end

Timpul de executare a algoritmului este evident liniar. Metoda programării dinamice se aplică problemelor care urmăresc calcularea unei valori şi constă în următoarele:

1) Se asociază problemei un graf de dependenţe; 2) În graf este pus în evidenţă un PD-arbore; problema se reduce la determinarea

valorii asociate lui z (rădăcina arborelui); 3) Se parcurge în postordine PD-arborele.

21

3

44

3

1 2

77

Mai pe scurt, putem spune:

Metoda programării dinamice constă în identificarea unui PD-arbore şi parcurgerea sa în postordine.

În multe probleme este util să căutam în PD-arbore regularităţi care să evite memorarea valorilor tuturor vârfurilor. Vom începe cu câteva exemple foarte simple, dar care pun în evidenţă anumite caracteristici ale metodei programării dinamice.

Exemplul 1. Şirul lui Fibonacci Ştim că acest şir este definit astfel: F0=0; F1=1; Fn = Fn-1 + Fn-2 , ∀n≥2 Dorim să calculăm Fn pentru un n oarecare.

Aici A={0,...,n}, X={0,1}, B=N, iar Ak={k-1,k-2}, ∀k≥2 v(k)=Fk ; fk(a,b)=a+b, ∀k≥2 Un prim graf de dependenţe este următorul:

2 31

n-2 n-1 n=z

0 4

Să observăm că o mai bună alegere a mulţimii B simplifică structura BD-arborelui. A={1,2,….,n}; B=N×N; v(k)=(Fk-1, Fk); fk(a,b)=(b,a+b) v(0)=(0,1).

nn-13 2 1

şi obţinem algoritmul binecunoscut: a←0; b←1 for i=2,n (a,b)←(b,a+b) write(b)

78

Exemplul 2. Calculul sumei a1+ ...+an

Este evident că trebuie calculate anumite sume parţiale. O primă posibilitate este să considerăm un graf în care fiecare vârf să fie o submulţime {i1,...,ik} a lui {1,2,...,n}, cu valoarea asociată ai1+...+aik. Această abordare este nerealizabilă: numărul de vârfuri ar fi exponenţial. O a doua posibilitate este ca vârfurile corespundă mulţimilor {i,i+1,...,j} cu i≤j şi cu valoarea ataşată si,j=ai+...+aj. Vom nota un astfel de vârf prin (i:j). Dorim să calculăm valoarea vârfului z=(1:n). Putem considera mai mulţi PD-arbori: Arborele liniar constituit din vârfurile cu i=1. Obţinem relaţiile de recurenţă: s1,1=a1; s1,j=s1,j-1+aj , j≥i care corespund asociativităţii la stânga: (...((a1+a2)+a3)+...). Arborele liniar constituit din vârfurile cu j=n. Acest arbore corespunde asociativităţii

la dreapta a sumei. Arborele binar strict în care fiecare vârf (afară de frunze) are descendenţii (i:k) şi (k+1:j) cu k=⎣(i+j)/2⎦. Prezentăm acest arbore pentru n=7:

(1:7)

(1:4) (5:7)

(1:2) (3:4) (5:6)

(7:7)(1:1) (2:2) (3:3) (4:4) (5:5) (6:6)

Relaţiile de recurenţă sunt: sii=ai si,j=sik+sk+1,j pentru i<j. iar algoritmul este următorul:

k←1 while k<n k2←k+k; i←1 while i+k≤n ai←ai+ai+k; i←i+k2 k ←k2

79

Rezultatul este obţinut în a1. Evoluţia calculelor apare în următorul tabel:

4 2 1 a1←a1+a3 5 a5←a5+a7 9 8 4 1 a1←a1+a5 9

n k2 k i 7 2 1 1 a1←a1+a2 3 a3←a3+a4 5 a5←a5+a6 7

Algoritmul de mai sus nu este atât de stupid şi inutil pe cât apare la prima vedere

pentru o problemă atât de simplă. Calculele pentru fiecare reluare a ciclului while interior sunt executate asupra

unor seturi de date disjuncte. De aceea, în ipoteza că pe calculatorul nostru dispunem de mai multe procesoare, calculele pe fiecare nivel al arborelui (mergând de jos în sus) pot fi executate în paralel. Drept urmare, timpul de calcul va fi de ordinul O(log n), deci sensibil mai bun decât cel secvenţial, al cărui ordin este O(n).

Exemplul 3. Deteminarea subşirului crescător de lungime maximă.

Se consideră vectorul a=(a1,...,an). Se cer lungimea celui mai lung şir crescător, precum şi toate subşirurile crescătoare de lungime maximă.

Introducem notaţiile:

nr = lungimea maximă căutată; lung(i)= lungimea maximă a subşirului crescător ce începe cu ai. A={1,2,...,n}; X={n}; Ai={i+1,...,n}, ∀i<n; fi=lung(i) Evident, suntem în prezenţa unui PD-arbore de rădăcină 1. Determinarea lui nr se face astfel: nr ←1; lung(n)←1 for i=n-1,1,-1 lung(i)←1+max{lung(j)⏐j>i & ai<aj} nr ←max{nr,lung(i)} Determinarea tuturor subşirurilor crescătoare de lungime maximă se face printr-un backtracking recursiv optimal. Subşirurile se obţin în vectorul s, iar ind reprezintă ultima poziţie completată din s. for i=1,n if lung(i)=nr then ind ←1; s(1)←ai; scrie(i) unde procedura scrie are forma:

80

procedure scrie(i) if ind=nr then write(s) else for j=i+1,n if ai<aj & lung(i)=1+lung(j) then ind++; s(ind)←a(j); scrie(j); ind←ind-1 end; Observaţie. Dacă dorim să obţinem un singur subşir crescător de lungime nr, este suficient să eliminăm instrucţiunea ind←ind-1.

Exemplul 4. Înmulţirea optimă a unui şir de matrici. Avem de calculat produsul de matrici A1×A2×...×An, unde dimensiunile matricilor sunt respectiv (d1,d2), (d2,d3), ... ,(dn,dn+1). Ştiind că înmulţirea matricilor este asociativă, se pune problema ordinii în care trebuie înmulţite matricile astfel încât numărul de înmulţiri elementare să fie minim. Presupunem că înmulţirea a două matrici se face în modul uzual, adică produsul matricilor A(m,n) şi B(n,p) necesită m×n×p înmulţiri elementare. Pentru a pune în evidenţă importanţa ordinii de înmulţire, să considerăm produsul de matrici A1×A2×A3×A4 unde A1(100,1), A2(1,100), A3(100,1), A4(1,100).

Pentru ordinea de înmulţire (A1×A2)×(A3×A4) sunt necesare 1.020.000 de înmulţiri elementare. În schimb, pentru ordinea de înmulţire (A1×(A2×A3))×A4 sunt necesare doar 10.200 de înmulţiri elementare. Fie cost(i,j) numărul minim de înmulţiri elementare pentru calculul produsului Ai×...×Aj. Punând în evidenţă ultima înmulţire de matrici, obţinem relaţiile: cost(i,i) = 0 cost(i,j) = min {cost(i,k)+cost(k+1,j)+di×dk+1×dj+1 | i≤k<j}. Valoarea cerută este cost(1,n). Vârfurile grafului de dependenţă sunt perechile (i,j) cu i≤k. cost(i,j) depinde de vârfurile din stânga şi de cele de deasupra. Se observă uşor că suntem în prezenţa unui PD-arbore. i

j

(i,j)

n j

i

1

(j,j)

(i,i)

81

Forma particulară a PD-arborelui nu face necesară aplicarea algoritmului general de parcurgere în postordine: este suficient să parcurgem coloanele 2,...,n, iar pe fiecare coloană să mergem de la diagonală până la (i,j). for j=2,n for i=j-1,1,-1 cost(i,j) calculat ca mai sus; fie k valoarea pentru care se realizează minimul cost(j,i)←k write cost(1,n) (se observă că am folosit partea inferior triunghiulară a matricii pentru a memora indicii pentru care se realizează minimul). Dacă dorim numai costul final, nu este nevoie să memorăm întreaga matrice, ci este suficient să folosim un vector.

Dacă dorim să producem şi o ordine de înmulţire optimă, avem nevoie de întreaga matrice. Vom apela sol(1,n), unde procedura sol are forma:

procedure sol(p,u) if p=u then write(p) else k←cost(u,p) write('('); sol(p,k); write(','); sol(k+1,u); write(')') end;

Pentru evaluarea timpului de lucru, vom calcula numărul de comparări efectuate. Aceste este:

[ ]∑ =−−=∑ ∑ +−=

−−

=

−

=

n

2j

32

2)1)(j(jn

2j

1j

1i)O(n1)j(j1)i(j

Exemplul 5. Descompunerea unui dreptunghi în pătrate

Se consideră un dreptunghi cu laturile de m, respectiv n unităţi (m<n). Asupra sa se pot face tăieturi complete pe orizontală sau verticală. Se cere numărul minim de pătrate în care poate fi descompus dreptunghiul. Fie aij = numărul minim de pătrate în care poate fi descompus un dreptunghi de laturi i şi j. Evident aij=aji. Rezultatul căutat este amn. Vârfurile grafului de dependenţe sunt (i,j), iar valorile asociate sunt aij .

j-kk

k

i-k

i

j

82

Pentru calculul lui aij avem de ales între a face: - o tăietură pe verticală; costurile sunt: aik+ai,j-k, k≤ ⎣j/2⎦ ; - o tăietură pe orizontală; costurile sunt: ak,j+ai-k,j, k≤ ⎣i/2⎦ .

Rezultă că valoarea aij a unui vârf (i,j) depinde de valorile vârfurilor din stânga sa şi de cele aflate deasupra sa. Se observă că graful de dependenţe este un PD-arbore. j

i (i,j)

Dependenţele pot fi exprimate astfel: ai,1=i, ∀i=1,...,m a1,j=j, ∀j=1,…,n aii=1, ∀=1,...,m aij = min{α,β}, unde

α=min{aik+ai,j-k | k≤ ⎣j/2⎦} , iar β=min{ ak,j+ai-k,j, | k≤ ⎣i/2⎦ }.

Forma particulară a PD-arborelui permite o parcurgere mai uşoară decât aplicarea algoritmului general de postordine. De exemplu putem coborâ pe linii, iar pe fiecare linie mergem de la stânga la dreapta. După iniţializările date de primele 3 dependenţe de mai sus, efectuăm calculele: for i=2,m

for j=i+1,n calculul lui aij conform celei de a patra dependenţe de mai sus if j≤m then aji←aij

Observaţie. Am lucrat numai pe partea superior triunghiulară, cu actualizări dedesubt.

83

Drumuri în grafuri

Fie G=(V,M) graf orientat cu n=|V|, m=|M|. Fie A matricea sa de adiacenţă. Considerăm şirul de matrici:

⎪⎩

⎪⎨⎧

≥∀=

=

2k ·A,AA

AA1-kk

1

a cărui semnificaţie este următoarea: Propoziţia 1. Ak-1(i,j) = numărul drumurilor de lungime k de la i la j.

- pentru k=1: evident.

- k-1 → k : ∑ ⋅==

−n

1s

1kk j)A(s,s)(i,Aj)(i,A , unde s este penultimul vârf din

drumul de la i la j.

În continuare dorim să determinăm numai existenţa drumurilor de lungime k. Considerăm şirul de matrici:

⎪⎩

⎪⎨⎧

≥∀=

=

2k ·A,AA

AA1)-(k(k)

(1)

unde j)(s,As)(i,Aj)(i,A 1)(k1)(kn

1s

(k) −−

=∧∨=

a cărui semnificaţie este următoarea (elementele matricilor sunt 0 sau 1): Propoziţia 2. Ak-1(i,j)=1 ⇔ există drum de lungime k de la i la j. Demonstraţia se face prin inducţie ca mai sus. Definim matricea drumurilor D prin:

D(i,j)=1 ⇔ ∃ drum de la i la j. D=A(1)∨...∨A(n-1), deoarece dacă există un drum de la i la j, există şi un

drum de lungime cel mult egală cu n-1 de la i la j. Construcţiile matricilor de mai sus necesită un timp de ordinul O(n4).

Vom căuta să obţinem un timp de executare mai bun, inclusiv pentru cazul în care lungimea arcelor este oarecare (în cele de mai sus s-a presupus implicit că arcele au lungimea egală cu 1).

84

În continuare, fiecare arc <i,j> va avea o etichetă et(<i,j>) strict pozitivă, ce reprezintă lungimea arcului.

Consider ⎪⎩

⎪⎨

⎧

∞+=

>∈<><=

altfeldacădacă

ji0

Mji,)ji,et(

j)P(i,

şi şirul de matrici:

{⎩⎨⎧

≥∀+==

−−− 1kj)(k,Pk)(i,Pj),(i,Pj)(i,P

PP

1k1k1kk

0

},min

Propoziţia 3. Pn este matricea celor mai scurte drumuri. Vom demonstra prin inducţie după k următoarea afirmaţie: Pk(i,j) = lungimea celui mai scurt drum de la i la j în care numerele de ordine ale nodurilor intermediare sunt cel mult egale cu k. - pentru k=0: evident. - k-1 → k : Considerăm un drum de lungime minimă de la i la j.

Dacă drumul nu trece prin k, Pk(i,j)=Pk-1(i,j). Dacă drumul trece prin k, el va trece o singură dată prin k (are lungime minimă) şi în drumurile de lungime minimă de la i la k şi de la k la j vârful k nu apare ca vârf intermediar, deci Pk(i,j)=Pk-1(i,k)+Pk-1(k,j).

i k j

Observaţii: 1) s-a folosit metoda programării dinamice; 2) Pk(i,i)=0; 3) Pk(i,k)=Pk-1(i,k) şi Pk(k,j)=Pk-1(k,j), deci la trecerea de la Pk-1 la Pk

linia k şi coloana k rămân neschimbate. Rezultă că putem folosi o singură matrice. Algoritmul se simplifică astfel:

for k=1,n for i=i,n for j=1,n P(i,j) ← min {P(i,j),P(i,k)+P(k,j)} Timpul de executare este evident de ordinul O(n3).

85

Dacă dorim să determinăm doar existenţa drumurilor şi nu lungimea lor minimă, vom proceda similar. Considerăm şirul de matrici:

⎩⎨⎧

≥∀∧∨==

−−− 0kj)](k,Ak)(i,[Aj)(i,Aj)(i,A

0A

1k1k1kk

0

,

Propoziţia 4. An este matricea drumurilor. Demonstrăm prin inducţie după k următoarea afirmaţie:

Ak(i,j)=1 ⇔ ∃ drum de la i la j cu numerele de ordine ale vârfurilor intemediare egale cu cel mult k. - pentru k=0: evident; - k-1 → k:

Dacă A(i,j)=1, atunci fie Ak-1(i,j)=1, fie Ak-1(i,k)=Ak-1(k,j)=1; în ambele situaţii va exista, conform ipotezei de inducţie, un drum de la i la j cu numerele de ordine ale vârfurilor intemediare egale cu cel mult k. Dacă există un drum de la i la j cu numerele de ordine ale vârfurilor intemediare egale cu cel mult k, prin eliminarea ciclurilor drumul va trece cel mult o dată prin k. Este suficient în continuare să considerăm cazul în care drumul trece prin vârful k şi cazul în care drumul nu trece prin k.

Sunt valabile aceleaşi observaţii ca la Propoziţia 3, iar algoritmul are o formă similară: D←A for k=1,n for i=1,n for j=1,n

D(i,j) ← D(i,j) ∨ D(i,k)∧D(k,j) Timpul de executare este evident de ordinul O(n3).

86

În continuare ne vor interesa numai drumurile ce pleacă dintr-un vârf x0 fixat. Este de aşteptat ca timpul de executare să scadă. Mai precis, căutăm d(x) = lungimea drumului minim de la x0 la x, pentru

orice vârf x. În plus, dorim să determinăm şi câte un astfel de drum. Prezentăm în continuare algoritmul lui Dijkstra pentru problema enunţată. Pentru simplificare, presupunem că orice vârf este accesibil din x0.

Pentru regăsirea drumurilor vom folosi vectorul tata. Perechiile (d(x),tata(x)) sunt iniţializate astfel:

- (0,0) pentru x=x0; - (et(<x0,x>),x0) dacă <x0,x>∈M; - +∞ altfel.

Fie T = mulţimea vârfurilor x pentru care d(x) are valoarea finală.

T ← {x0} while T≠V

Fie x’∈V\T cu d(x’) minim T ← T∪{x’}

for toţi x∉T if d(x)>d(x’)+et(<x’,x>) then d(x) ← d(x’)+et(<x’,x>); tata(x)←x’

Pentru a demonstra corectitudinea algoritmului, vom arăta prin inducţie după |T| că:

1) ∀ x∈T : d(x) = lungimea celui mai scurt drum de la x0 la x; 2) ∀ x∉T : d(x) = lungimea celui mai scurt drum de la x0 la x, ce trece numai

prin vârfuri din T.

Pentru |T|=1, concluzia este evidentă. |T| → |T|+1: Fie x' vârful nou adăugat. Demonstrăm cele două afirmaţii de mai sus: 1) d(x’) este cel final:

Presupunem prin absurd că există un drum de la x0 la x’ de lungime mai mică decât d(x’). Acest drum trebuie să treacă printr-un vârf y∉T.

x'

T

x0

•x

Evident d(y)<d(x’). Contradicţie, pentru că a fost ales x’ cu d(x’) minim.

x0 y∉T

x

2) Conform actualizărilor (*) efectuate de algoritm.

Observaţii. 1) Timpul de executare este de ordinul O(n2). 2) Pe baza vectorului tata, putem regăsi pentru orice x∈V drumul minim ce îl

leagă de x0 în timp liniar. Regăsirea tuturor acestor drumuri necesită un timp de ordinul O(n2), deci complexitatea în timp a algoritmului nu creşte.

3) Dacă dorim numai drumul minim de la x0 la un vârf x1 dat, ne oprim când x’=x1; aceasta nu implică însă o reducere a ordinul de mărime al timpului de calcul.

4) Algoritmul de mai sus poate fi încadrat la metoda Greedy, dar şi la metoda şirului crescător de mulţimi.

87

Metoda Branch and Bound

• Prezentare generală

Metoda Branch and Bound se aplică problemelor care care pot fi reprezentate pe un arbore: se începe prin a lua una dintre mai multe decizii posibile, după care suntem puşi în situaţia de a alege din nou între mai multe decizii; vom alege una dintre ele etc. Vârfurile arborelui corespund stărilor posibile în dezvoltarea soluţiei.

Deosebim două tipuri de probleme: 1) Se caută un anumit vârf, numit vârf rezultat, care evident este final (nu are descendenţi). 2) Există mai multe vârfuri finale, care reprezintă soluţii posibile, dintre care căutăm de

exemplu pe cel care optimizează o anumită funcţie.

Exemplul 1. Jocul 15 (Perspico). Un număr de 15 plăcuţe pătrate sunt incorporate într-un cadru 4×4, o poziţie fiind liberă.

Fiecare plăcuţă este etichetată cu unul dintre numerele 1,2,...,15. Prin configuraţie înţelegem o plasare oarecare a plăcuţelor în cadru. Orice plăcuţă adiacentă cu locul liber poate fi mutată pe acest loc liber. Dându-se o configuraţie iniţială şi una finală, se cere o succesiune de mutări prin care să ajungem din configuraţia iniţială în cea finală. Configuraţiile iniţială şi finală pot fi de exemplu:

1 2 3 4 1 2 3 4 5 7 8 5 6 7 8 9 6 10 11 9 10 11 12 13 14 15 12 13 14 15

unde locul liber mai poate fi considerat drept conţinând plăcuţa imaginară cu eticheta 16.

Prezentăm întâi o condiţie de existenţă a unei succesiuni de mutări prin care se poate trece

de la configuraţia iniţială în cea finală. Cele 16 locaşuri sunt considerate ca fiind ordonate de la stânga la dreapta şi de jos în sus.

Pentru plăcuţa etichetată cu i definim valoarea n(i) ca fiind numărul locaşurilor care urmează celei pe care se află plăcuţa şi care conţin o plăcuţă a cărei etichetă este mai mică decât i. De exemplu pentru configuraţia iniţială de mai sus avem: n(8)=1; n(4)=0; n(16)=10; n(15)=1 etc.

Fie l şi c linia şi coloana pe care apare locul liber. Fie x∈{0,1} definit astfel: x=0 dacă şi numai dacă l+c este par. Se poate demonstra următorul rezultat:

Propoziţie. Fiind dată o configuraţie iniţială, putem trece din ea la configuraţia finală de mai sus ⇔ n(1)+n(2)+...+n(16)+x este par.

În continuare vom presupune că putem trece de la configuraţia iniţială la cea finală. Cum locul liber poate fi mutat spre N, S, E, V (fără a ieşi din cadru), rezultă că fiecare

configuraţie (stare) are cel mult 4 descendenţi. Se observă că arborele astfel construit este infinit. Stările finale sunt stări rezultat şi corespund configuraţiei finale.

88

Exemplul 2. Circuitul hamiltonian de cost minim. Se consideră un graf orientat cu arcele etichetate cu costuri pozitive. Inexistenţa unui arc

între două vârfuri este identificată prin "prezenţa" sa cu costul +∞. Presupunem că graful este dat prin matricea C a costurilor sale. Se cere să se determine, dacă există, un circuit hamiltonian de cost minim.

Să considerăm de exemplu graful dat de matricea de costuri:

⎟⎟⎟⎟⎟

⎠

⎞

⎜⎜⎜⎜⎜

⎝

⎛

∞∞

∞∞

=

626384915273

C Arborele spaţiului de stări, în care vârfurile corespund vârfurilor din graf, iar muchiile reprezintă arce din graf, este următorul:

(3,2) (2,3) (4,2)

(4,3)

(2,4) (4,5) (3,4)

(4,2) (3,4) (3,2) (2,4) (2,3)

(1,4) (1,3) (1,2)

1

2 3 4

5 6 7 8 9 10

11 12 13 14 15 16

subînţelegându-se că se pleacă din vârful 1 şi că din frunze se revine la acest vârf. Revenim la descrierea metodei Branch and Bound.

Ştim că şi metoda backtracking este aplicabilă problemelor reprezentabile pe arbori. Există însă multe deosebiri, dintre care menţionăm următoarele: - ordinea de parcurgere a arborelui; - modul în care sunt eliminaţi subarborii care nu pot conduce la o soluţie; - faptul că arborele poate fi infinit (prin natura sa sau prin faptul că mai multe vârfuri pot

corespunde la o aceeaşi stare).

În general arborele de stări este construit dinamic. Este folosită o listă L de vârfuri active, adică de stări care sunt susceptibile de a fi

dezvoltate pentru a ajunge la soluţie (soluţii). Iniţial, lista L conţine rădăcina arborelui, care este vârful curent. La fiecare pas, din L alegem un vârf (care nu este neapărat un fiu al vârfului curent!), care devine noul vârf curent.

89

Când un vârf activ devine vârf curent, sunt generaţi toţi fiii săi, care devin vârfuri active (sunt incluşi în L). Apoi din nou este selectat un vârf curent.

Legat de modul prin care alegem un vârf activ drept vârf curent, deci implicit legat de modul de parcurgere a arborelui, facem următoarele remarci: − parcurgerea DF nu este adecvată, deoarece pe de o parte arborele poate fi infinit, iar pe de altă parte soluţia căutată poate fi de exemplu un fiu al rădăcinii diferit de primul fiu şi parcurgerea în adâncime ar fi ineficientă: se parcurg inutil stări, în loc de a avansa direct spre soluţie; − parcurgerea pe lăţime conduce totdeauna la soluţie (dacă aceasta există), dar poate fi ineficientă dacă vârfurile au mulţi fii.

Metoda Branch and Bound încearcă un "compromis" între cele două parcurgeri menţionate mai sus, ataşând vârfurilor active câte un cost pozitiv, ce intenţionează să fie o măsură a gradului de "apropiere" a vârfului de o soluţie. Alegerea acestui cost este decisivă pentru a obţine un timp de executare cât mai bun şi depinde atât de problemă, dar mai ales de abilitatea programatorului.

Observaţie. Totdeauna costul unui vârf va fi mai mic decât cel al descendenţilor (fiilor).

De fiecare dată drept vârf curent este ales cel de cost minim (cel considerat ca fiind cel mai "aproape" de soluţie). De aceea L va fi în general un min-ansamblu: costul fiecărui vârf este mai mic decât costul descendenţilor.

Din analiza teoretică a problemei deducem o valoare lim care este o aproximaţie prin adaos a minimului căutat: atunci când costul unui vârf depăşeşte lim, atunci vârful curent este ignorat: nu este luat în considerare şi deci este eliminat întregul subarbore pentru care este rădăcină. Dacă nu cunoaştem o astfel de valoare lim, o iniţializăm cu +∞.

Se poate defini o funcţie de cost ideală, pentru care c(x) este dat de:

nivelul pe care se află vârful x dacă x este vârf rezultat; +∞ dacă x este vârf final, diferit de vârf rezultat; min {c(y) | y fiu al lui x } dacă x nu este vârf final.

Această funcţie este ideală din două puncte de vedere: - nu poate fi calculată dacă arborele este infinit; în plus, chiar dacă arborele este finit, el trebuie

parcurs în întregime, ceea ce este exact ce dorim să evităm; - dacă totuşi am cunoaşte această funcţie, soluţia poate fi determinată imediat: plecăm din

rădăcină şi coborâm mereu spre un vârf cu acelaşi cost, până ajungem în vârful rezultat.

Neputând lucra cu funcţia ideală de mai sus, vom alege o aproximaţie ĉ a lui c, care trebuie să satisfacă condiţiile: 1) în continuare, dacă y este fiu al lui x avem ĉ(x)<ĉ(y); 2) ĉ(x) să poată fi calculată doar pe baza informaţilor din drumul de la rădăcină la x ; 3) este indicat ca ĉ≤c pentru a ne asigura că dacă ĉ(x)>lim, atunci şi c(x)>lim, deci x nu va

mai fi dezvoltat.

O primă modalitate de a asigura compromisul între parcurgerile în adâncime şi pe lăţime este de a alege funcţia ĉ astfel încât, pentru o valoare naturală k, să fie îndeplinită condiţia: pentru orice vârf x situat pe un nivel nx şi orice vârf situat pe un nivel ny≥nx+k, să avem ĉ(x)> ĉ(y), indiferent dacă y este sau nu descendent al lui x.

90

Condiţia de mai sus spune că niciodată nu poate deveni activ un vârf aflat pe un nivel ny≥nx+k dacă în L apare un vârf situat pe nivelul nx, adică nu putem merge "prea mult" în adâncime. Dacă această condiţie este îndeplinită, este valabilă următoarea propoziţie:

Propoziţie. Dacă există soluţie, ea va fi atinsă într-un timp finit, chiar dacă arborele este infinit.

Putem aplica cele de mai sus pentru jocul Perspico, alegând: ĉ(x) = suma dintre lungimea drumului de la rădăcină la x şi numărul de plăcuţe care nu sunt la locul lor (aici k=15).

• Algoritmul Branch & Bound pentru probleme de optim Să presupunem că dorim să determinăm vârful final de cost minim şi drumul de la

rădăcină la el. Fie lim aproximarea prin adaos considerată mai sus. Algoritmul este următorul (rad este rădăcina arborelui, iar ifinal este vârful rezultat):

i ← rad; L ⇐ {i}; min ← lim; calculez ĉ(rad); tata(i) ← 0 while L ≠ ∅ i ⇐ L {este scos vârful i cu ĉ(i) minim din min-ansamblul L} for toţi j fii ai lui i calculez ĉ(j); calcule locale asupra lui j; tata(j) ← i if j este vârf final then if ĉ(j)<min then min ← ĉ(j); ifinal ← j elimină din L vârfurile k cu ĉ(k)≥min (*) else if ĉ(j)<min then j ⇒ L if min=+lim then write('Nu există soluţie') else writeln(min); i ← ifinal while i ≠ 0 write(i); i ← tata(i)

Observaţie. La (*) am ţinut cont de faptul că dacă j este descendent al lui i, atunci ĉ(i)<ĉ(j).

Vom aplica algoritmul de mai sus pentru problema circuitului hamiltonian de cost minim, pe exemplul considerat mai sus. Pentru orice vârf x din arborele de stări, valoarea c(x) dată de funcţia de cost ideală este: lungimea circuitului corespunzător lui x dacă x este frunză min {c(y) | y fiu al lui x } altfel.

Fiecărui vârf x îi vom ataşa o matrice de costuri Mx (numai dacă nu este frunză) şi

valoarea ĉ(x). Observaţie. Dacă micşorăm toate elementele unei linii sau coloane cu α, orice circuit

hamiltonian va avea costul micşorat cu α, deoarece în orice circuit hamiltonian din orice vârf pleacă exact un arc şi în orice vârf soseşte exact un arc.

Conform acestei observaţii, vom lucra cu matrici de costuri reduse (în care pe orice linie sau coloană apare cel puţin un zero, exceptând cazul când linia sau coloana conţine numai ∞).

91

Pentru rădăcina rad=1 plecăm de la matricea de costuri C. Matricea ataşată va fi matricea

redusă obţinută din C, iar ĉ(1) = cantitatea cu care s-a redus C. În general, pentru un vârf y oarecare al cărui tată este x şi muchia (x,y) este etichetată

cu (i,j): dacă y este vârf terminal, ĉ(x) va fi chiar c(y), adică costul real al circuitului; în caz contrar, plecând de la Mx şi ĉ(x) procedăm astfel:

- elementele liniei i devin ∞, deoarece mergem sigur către vârful j din graf; - elementele coloanei j devin ∞, deoarece am ajuns sigur în vârful j din graf; - Mx(j,1) ← ∞, pentru a nu reveni prematur în rădăcina 1; - reducem noua matrice Mx şi obţinem My; fie r cantitatea cu care s-a redus Mx. Vom lua ĉ(y) ← ĉ(x)+r+Mx(i,j).

Concret, pentru exemplul dat, calculele se desfăşoară astfel:

Pentru rădăcină: - reduc liniile în ordine cu 2, 1, 3, 2;

⎟⎟⎟⎟⎟

⎠

⎞

⎜⎜⎜⎜⎜

⎝

⎛

∞∞

∞∞

=

403

050

803

051

M1- reduc prima coloană cu 1; - în acest mod obţin ĉ(1)=9, iar matricea M1 este:

♦ Acum min←9; L={1}. Este extras vârful 1 şi sunt consideraţi fiii săi. Pentru vârful 2:

- plec de la M1 şi pun ∞ pe linia 1 şi coloana 2;

⎟⎟⎟⎟⎟

⎠

⎞

⎜⎜⎜⎜⎜

⎝

⎛

∞∞∞∞

∞∞∞∞∞∞

=

10

00

80M2

- reduc linia 3 cu 3; - în acest mod obţin ĉ(2)=3+9+1=13, iar matricea M2 este:

Pentru vârful 3:

- plec de la M1 şi pun ∞ pe linia 1 şi coloana 3;

⎟⎟⎟⎟⎟

⎠

⎞

⎜⎜⎜⎜⎜

⎝

⎛

∞∞∞∞∞∞

∞∞∞∞

=

03

05

50M3

- reduc linia 2 cu 3; - în acest mod obţin ĉ(3)=3+9+5=17, iar matricea M3 este:

Pentru vârful 4:

- plec de la M1 şi pun ∞ pe linia 1 şi coloana 4;

⎟⎟⎟⎟⎟

⎠

⎞

⎜⎜⎜⎜⎜

⎝

⎛

∞∞∞∞∞∞∞∞∞∞

=

40

50

03M4

- nu este necesară vreo reducere; - în acest mod obţin ĉ(4)=0+9+0=9, iar matricea M4 este

♦ Acum L={2,3,4} cu ĉ(2)=13, ĉ(3)=17, ĉ(4)=9. Devine activ vârful 4. Pentru vârful 9:

- plec de la M4 şi pun ∞ pe linia 4 şi coloana 2;

⎟⎟⎟⎟⎟

⎠

⎞

⎜⎜⎜⎜⎜

⎝

⎛

∞∞∞∞∞∞∞∞∞∞∞∞∞∞

=0

0M9

- nu este necesară vreo reducere; - în acest mod obţin ĉ(9)=0+9+0=9, iar matricea M9 este:

92

Pentru vârful 10:

- plec de la M4 şi pun ∞ pe linia 4 şi coloana 3;

⎟⎟⎟⎟⎟

⎠

⎞

⎜⎜⎜⎜⎜

⎝

⎛

∞∞∞∞∞∞∞∞∞∞∞∞∞∞

=0

0M10

- reduc linia 2 cu 3, iar linia 3 cu 5; - în acest mod obţin ĉ(10)=8+9+4=21, iar matricea M10 este:

♦ Acum L={2,3,9,10} cu ĉ(2)=13, ĉ(3)=17, ĉ(9)=9, ĉ(10)=21. Devine activ vârful 9.

Singurul său descendent este 15, care este frunză. ĉ(15)=c(15)=9 (costul real al circuitului). Sunt eliminate din L vârfurile cu costurile mai mari decât 9, deci L devine vidă. min rămâne egal cu 9, va fi produs la ieşire circuitul căutat (1,4,2,3,1) şi algoritmul se opreşte.

93

Algoritmi probabilişti

Este vorba de algoritmi în care este posibilă continuarea calculelor prin alegerea (aleatoare) a uneia dintre mai multe variante posibile. Pentru aceasta va fi folosită o funcţie random, prezentă în orice limbaj de progamare.

Drept urmare, pentru aceleaşi date de intrare, la executări diferite vom obţine rezultate diferite.

Vom începe prin prezentarea câtorva probleme specifice, iar apoi vom

prezenta o clasificare a algoritmilor probabilişti. Exemplul 1. Acul lui Buffon. Se consideră o mulţime de linii paralele astfel încât oricare două linii vecine

sunt la distanţă de o unitate. Un ac (segment) de lungime o jumătate de unitate este aruncat aleator şi se numără de câte ori a intersectat vreo linie.

Se poate demonstra că probabilitatea ca acul să intersecteze o linie este 1/π. Practic, după un număr "suficient de mare" de încercări, raportul între:

- numărul total de încercări şi - numărul cazurilor în care acul a intersectat vreo linie va fi "suficient de aproape" de π.

Exemplul 2. Fie G un graf neorientat. Vom înţelege prin mutare eliminarea unui vârf împreună cu toţi vecinii săi. Se cere numărul minim de mutări prin care se pot elimina toate vârfurile. Această problemă a fost propusă la o olimpiadă şcolară. Specificul acestor olimpiade constă în faptul că programul este rulat pe 10 exemple şi se contabilizează numărul de exemple pentru care rezultatul furnizat este corect. Pentru a "aduna" puncte, nu este necesar să ne gândim la o soluţie efectivă, ci este suficient să aplicăm următorul algoritm probabilist: - se alege aleator un vârf şi se elimină împreună cu vecinii săi; - se repetă pasul anterior pe noul graf până când sunt eliminate toate vârfurile; - se memorează numărul de mutări efectuat.

Se reia algoritmul (fără a depăşi timpul maxim fixat pentru un test) şi se păstrează cel mai mic număr de mutări.

Dincolo de cadrul în care a fost propusă problema, strategia de mai sus este

aplicabilă atunci când se cere doar o aproximaţie suficient de bună a rezultatului dorit şi/sau trebuie să ne încadrăm într-un timp dat.

Exemplul 3. Se dau n texte (n foarte mare) cu următoarele proprietăţi:

- există un unic text t0 care apare de cel puţin 10% ori; - celelalte texte sunt distincte. Se cere determinarea textului t0. Problema a fost propusă la un concurs studenţesc A.C.M. Un algoritmul probabilistic eficient este următorul:

94

repeat generez aleator i,j∈{1,...,n} diferite if ti=tj then write ti; stop until false

Probabilitatea ca alegerea unui indice să conducă la textul t0 este 1/10, deci probabilitatea ca să obţinem o pereche de indici (i,j) cu ti=tj=t0 este 1/100. Cu alte cuvinte, teoretic sunt suficiente 100 de încercări, independent de valoarea lui n.

Exemplul 4. Problema celor n dame. Am prezentat o rezolvare a acestei probleme folosind metoda backtracking.

Implementarea şi executarea algoritmului corespunzător arată că se ajunge la o soluţie în timp "rezonabil" doar pentru valori mici ale lui n (n≤20).

Un algoritm probabilist pentru această problemă, care furnizează rapid o soluţie chiar pentru valori ale lui n mai mari decât 100 este următorul: - plasăm o damă pe prima linie; - presupunând că am plasat neantagonist câte o damă pe liniile 1,...,k-1, facem un

inventar al poziţiilor posibile pentru dama de pe linia k şi alegem aleator una dintre ele. Exista două posibilităţi:

1) Am reuşit să plasăm o damă pe linia n ⇒ am determinat o soluţie, deci o listăm şi oprim programul;

2) Am ajuns la o linie k şi nu există poziţii posibile. Atunci reluăm întreg algoritmul (deci nu ne întoarcem la linia precedentă ca la backtracking).

Pentru implementarea algoritmului, trebuie ţinută o evidenţă a coloanelor şi

diagonalelor ocupate (pe care nu putem plasa o damă). Pentru aceasta vom folosi vectorii booleeni NV_SE[-n+1..n-1] , NE_SV[2..2n] şi C[1..n] ale căror valori ne spun dacă o diagonală NV-SE, o diagonală NE-SV sau o coloană sunt libere (nu există plasată o damă pe diagonala sau coloana respectivă).

-1

0 1 n-1

-n+1

2 3 n+1

n+2

2n

NV_SE NE_SV

Observaţie. Dacă sunt pe linia k, pot plasa o damă pe coloana i dacă: ϕ(k,i) : Ci liberă & NV_SEi-k liberă & NE_SVi+k liberă. În algoritmul care urmează, soluţia este obţinută în vectorul x=(x1,...xn).

95

repeat repeat iniţializarea componentelor celor 3 vectori booleeni cu valoarea true k ← 1 inventar al poziţiilor i∈{1,...,n} cu ϕ(k,i) pun aceste poziţii în primele na componente ale unui vector a if na>0 then aleg aleator i∈{1,...,na}; i ← ai xk ← i ; NV_SEi-k ← false; NE_SVi+k ← false Ci ← false; k ← k+1 until na=0 ∨ k=n+1 until k=n+1 write(x) Observaţie. Este indicat să ne mulţumim să plasăm damele pe primele aprox. 90% din linii, iar pentru restul liniilor să folosim backtracking.

96

Algoritmi genetici

Algoritmii genetici constituie o generalizare a algoritmilor probabilişti. Problema generală: Fie f:D → R. Se caută max{ f(x) | x∈D }. Presupunem că orice x∈D poate fi codificat ca:

x=(x1,...,xr) cu xi∈{0,1}, ∀ i=1,...,r. x se numeşte cromozom. Nu vom lucra cu un singur cromozom, ci cu o populaţie de n cromozomi, care se transformă prin trecerea de la o generaţie la alta. Observaţie. O populaţie este un multiset (un element poate să apară de mai multe ori). Schimbarea de generaţie se face prin selecţia unei subpopulaţii şi modificarea acesteia prin operaţiile de încrucişare (crossover) şi mutaţie, ce vor fi descrise mai jos. Algoritmul se încheie dacă s-a efectuat un număr dat de schimbări de configuraţii sau dacă s-a găsit o aproximare suficient de bună a maximului. Considerăm în continuare prima variantă. Notaţii: P - populaţia curentă; P={p1,...,pn}, deci n=|P|; r - lungimea cromozomilor; valmax - valoarea maximă curentă ; xmax - punctul pentru care este atinsă valmax; nmax - numărul maxim admis de schimbări de configuraţii; pc - probabilitatea de crossover; pm - probabilitatea de mutaţie.

Se mai foloseşte o funcţie J:X → R pentru evaluarea performanţelor cromozomilor din P.

O modalitate simplă de crossover este:

cromozom 1

cromozom 2

adică din doi părinţi se obţin 2 descendenţi. O modalitate simplă de mutaţie este alegerea aleatoare a unei poziţii din cromozom şi modificarea ei: 0↔1.

97

Algoritmul general este următorul:

P ← aleator; valmax ← -∞ for t=1,nmax determin cel mai bun p∈P (conform funcţiei J) if J(p)>valmax then xmax ← p; valmax ← J(p) . . . . . . . . . . . . . . . . . . . . . . Q ← ∅ for i=1,n aleg k∈[0,1] aleator if k<pc then P ← P\{pi}; Q ← Q ∪ {pi} aleg aleator perechi de elemente din Q şi aplic crossover (dacă │Q│ nu este par, un element rămâne neschimbat) P ← P ∪ Q . . . . . . . . . . . . . . . . . . . . . . Q ← Ø for i=1,n aleg k∈[0,1] aleator if k<pm then P ← P\{pi}; Q ← Q ∪ {pi} pentru fiecare q∈Q aplic operatorul de mutaţie P ← P ∪ Q

Observaţii: - de obicei pc este de ordinul 10-1 (de exemplu 0.3), iar pm de ordinul 10-3 (de

exemplu 0.007). Experienţele arată că alegerea lui pc şi pm nu are foarte mare importanţă. Alegerea lor se face şi în funcţie de lungimea r a cromozomilor;

- de obicei cel mai performant individ este reţinut şi pentru viitoarea configuraţie; - în funcţia de evaluare (dar nu numai) pot fi folosite distanţe ca de exemplu:

cea euclidiană; Hamming - numărul de poziţii pe care cromozomii diferă; Levenstein - numărul minim de ştergeri + adăugări + modificări pentru a trece de la un cromozom la celălalt.

98

• Aplicaţii

1) Ghicirea unei submulţimi (interactiv)

O submulţime a lui {1,2...,r} poate fi reprezentată ca un vector x∈{0,1}r cu semnificaţia că i face parte din submulţime dacă şi numai dacă xi=1.

Programul a fost rulat pentru n=r=25; pc=0.3; pm=0.2. J(p) = numărul de poziţii pe care p coincide cu p0 căutată.

Variante folosite pentru crossover: - clasic; - selectăm doi indici p1<p2 şi interschimbăm porţiunile corespunzătoare din cromozomi.

Ne oprim dacă J(p)≥n-2. 2) Ghicirea unei permutări (interactiv) Programul a fost rulat pentru n=10, r=10, pc=0.3. Funcţia J şi variantele de crossover sunt aceleaşi ca în exemplul precedent. Mutaţie: determinăm aleator j,k∈{1,...,n} şi interschimbăm p[j] cu p[k].

3) Maximul unei funcţii.

Dorim să determinăm max{f(x) | x ∈[0,1]}. Fiecare cromozom se scrie ca x=0,c1...cr cu ci∈{0,1}, ∀i=1,...r. Programul a fost rulat pentru n=30, r=20, pc=0.25, pm=0.1.

Variante folosite pentru crossover: - clasic; - modificăm ultimele k poziţii aleator; - selectăm doi indici p1<p2 şi interschimbăm porţiunile corespunzătoare din cromozomi.

99

• Variante pentru selecţie şi pentru alegerea operatorilor

Pentru crossover se mai pot folosi următoarele variante: - cu k>2 puncte de tăietură; - cu amestec.

La selecţia subpopulaţiei putem folosi o selecţie Monte Carlo.

∑=

=n

1i)iJ(pT

Tp

iiq = ,∀i=1,...,n ⇒ 1

n

1i iq =∑=

Pot folosi o ruletă: q2q1

Rotesc ruleta de n (sau de un număr dat) de ori.

100

Algoritmi nedeterminişti

Este vorba de algoritmi secvenţiali care, spre deosebire de cei obişnuiţi, admit şi următoarele instrucţiuni suplimentare:

1) success şi failure, care arată că algoritmul se termină cu succes, respectiv cu eşec. Ele înlocuiesc instrucţiunea stop. Forma lor arată că vom studia doar probleme de decizie, pentru care rezultatul poate fi doar afirmativ sau negativ (după cum se va vedea, foarte multe probleme pot fi aduse la aceasta formă).

2) choice(A), unde A este o mulţime finită; este o funcţie care întoarce ca rezultat un element oarecare al lui A.

Se consideră că cele 3 instrucţiuni nou introduse necesită un timp constant.

Maşina abstractă care execută un astfel de algoritm, când întâlneşte o instructiune choice lucrează astfel: - dacă există o valoare din A care conduce la o instrucţiune success, va fi aleasă o

altfel de valoare; - în caz contrar, va fi aleasă o valoare oarecare.

Cu alte cuvinte, un algoritm nedeterminist se termină cu eşec dacă nu există o modalitate de a efectua alegeri care să conducă la o instrucţiune success.

Funcţionarea maşinii abstracte se aseamănă calculului paralel. De câte ori este întâlnită o instrucţiune choice, intră în acţiune atâtea procesoare câte elemente are mulţimea A. Algoritmul se termină cu succes dacă unul dintre procesoarele active ajunge la o instrucţiune success. Timpul de executare va fi, în cazul unei terminări cu succes, timpul necesar ajungerii la respectiva instrucţiune success .

Mai precizăm că ne interesează doar terminările cu succes. Exemplul 1. Se cere să se verifice dacă un număr x apare sau nu în mulţimea

{a1,...,an}. Ştim că timpul de executare pentru algoritmul determinist pentru această problemă este de ordinul O(n), adică liniar. Putem scrie următorul algoritm nedeterminist:

i ← choice({1,2,...,n}) if ai=x then write i; success else failure

care rezolvă problema în timp constant.

101

Exemplul 2. Se cere să se ordoneze crescător vectorul a=(a1,...,an). Ştim că cel mai bun algoritm determinist pentru această problemă necesită un

timp de ordinul O(n.log n). Ideea algoritmului nedeterminist este următoarea: copiem elementele vectorului a într-un vector auxiliar b într-o ordine oarecare, după care verificăm dacă elementele lui b apar în ordine crescătoare. for i=1,n bi ← ∞ { iniţializarea lui b }

for i=1,n j ← choice({1,2,...,n}) if bj=∞ then bj ← ai { fiecare ai trece pe o poziţie nouă din b } else failure

for i=1,n-1 if bi>bi+1 then failure write(b); success

Timpul de executare al acestui algoritm este O(n), deci liniar. Se observă că: - am obţinut un timp de executare mai bun; - problema sortării a fost tratată ca o problemă de decizie.

Exemplul 3. Problema validării. Fie F(x1,...,xn) o expresie booleană în forma normală conjunctivă (FNC):

F=C1∧...∧Ck , unde C1,...,Ck sunt disjuncţii de variabile de forma xj sau xj' (xj' este negaţia lui xj). Se cere să se determine dacă există a1,...,an∈{0,1} cu F(a1,...,an)=1. Problema va fi referită în continuare sub numele VALID.

O instanţă a problemei este: F(x1,x2,x3)=(x1∨x2∨x3)∧(x1'∨x2'∨x3'). Putem scrie următorul algoritm nedeterminist simplu care rezolvă problema: for i=1,n

xi ← choice({0,1}) if F(x1,...,xn)=1 then success else failure Timpul este proporţional cu lungimea formulei, deci liniar.

Observaţie. Nu se cunoaşte un algoritm determinist polinomial pentru problema validării ! Ştim că doar algoritmii polinomiali sunt eficienţi, deci scopul este de a elabora algoritmi polinomiali. Este evident că nu există algoritmi polinomiali pentru orice problemă, de exemplu cei pentru care numărul datelor de ieşire nu este polinomial: determinarea tuturor submulţimilor unei mulţimi finite, generarea permutărilor etc. De aceea căutăm să delimităm clasa problemelor pentru care încercăm să elaborăm algoritmi polinomiali.

102

Introducem clasele de probleme (de decizie) următoare: P - clasa problemelor pentru care există algoritmi determinişti polinomiali; NP - clasa problemelor pentru care există algoritmi nedeterminişti polinomiali. Vom studia problema existenţei algoritmilor (determinişti) polinomiali doar pentru problemele din NP.

Evident P⊂NP. Este însă incluziunea strictă sau P=NP ? Precizăm de la început că această problemă este deschisă!

În 1976, Samuel Cook a obţinut un rezultat care a simplificat problema şi a părut promiţător în rezolvarea ei: Teoremă. P=NP ⇔ VALID∈P

Teorema spune că dacă reuşim să găsim un algoritm determinist polinomial pentru VALID, atunci va exista un algoritm determinist polinomial pentru orice problemă din NP.

Întrucât nu s-a reuşit să se obţină un algoritm polinomial pentru VALID, s-a încercat să se rezolve probleme "echivalente" cu VALID. Mai precis s-a definit clasa NPC .

NPC

P

NP

Clasa de probleme NPC este definită astfel: 1) VALID∈NPC 2) Pentru o problemă P, P∈NPC dacă:

2.1) Se cunoaşte pentru P un algoritm nedeterminist polinomial; 2.2) VALID se poate reduce la P în timp determinist polinomial. Problemele din NPC se numesc NP−complete. Observaţie. Este suficient să arătăm pentru o singura problema NP–completă

că admite un algoritm polinomial, pentru a obţine egalitatea P=NP. Lista problemelor NP–complete a depăşit 1000, dar pentru nici una dintre ele nu s-a reuşit să se obţină un algoritm determinist polinomial. Drept urmare, aşa cum am menţionat anterior, problema egalităţii P=NP rămâne o problema deschisă. Prezentăm în continuare una dintre multele probleme NP–complete.

103

Problema clicii maximale. Fie G=(X,M) un graf neorientat. Y⊂X se numeşte clică dacă pentru ∀i,j∈Y

avem (i,j)∈M. Se caută ordinul unei clici maximale. Problema de decizie corespunzătoare este următoarea: Pentru un k dat, există în G o clica de ordin k ? Pentru această problemă vom scrie procedura clica(G,k), care furnizează răspunsul în timp nedeterminist polinomial. Presupunând cunoscut acest lucru, algoritmul pentru problema clicii maximale va fi: for k=n,1,-1 clica(G,k) care este tot polinomial. procedure clica(G,k) for i=1,n ales(i) ← 0 {elementul i nu a fost ales} { pentru fiecare i aleg un element j din {1,...,n} pe care îl pun în bi } for i=1,k j ← choice({1,...,n}) if ales(j)=1 then failure else ales(j) ← 1; bi ← j { s-au ales k vârfuri distincte b1,...,bk } for i=1,k for j=1,k

if i≠j & (bi,bj)∉M then failure

write(k); success end; Timpul este evident polinomial ⇒ CLICA(k), deci şi CLICA ∈ NP.

Arătăm în continuare că VALID se reduce la CLICA în timp determinist polinomial.

Fie F(x1,...,xn) o expresie booleană în forma normală conjunctivă (FNC): F=C1∧...∧Ck , unde C1,...,Ck sunt disjuncţii de variabile de forma xj sau xj', numiţi literali.

Ataşăm lui F graful G=(X,M) astfel: X = {(α,i) | α literal din Ci} M = {[(α,i),(β,j)] | α≠β'}, adică α şi β pot fi satisfăcuţi concomitent.

De exemplu, pentru F(x1,x2,x3)=(x1∨x2∨x3)∧(x1'∨x2'∨x3'), graful este:

(x3',2)

(x2',2)

(x1',2)

(x3,1)

(x2,1)

(x1,1)

Construcţia grafului necesită un timp determinist polinomial.

104

Mai trebuie demonstrat că: în G există o clică de ordin k ⇔ F este validabilă. Începem cu demonstrarea necesităţii. Fie S = {(αi,i) | i=1,...k} o clică de ordin k.

Fie S1 = {αi | i=1,...,k}. Conform construcţiei lui M, nu este posibil ca αi,αi' să apară simultan în S1. Alegem fiecare ai astfel: 1 dacă xi∈S1, adică αi=xi0 dacă xi'∈S1arbitrar în caz contrar. Pentru aceasta alegere, F(a1,...,an)=1, fiecare conjuncţie având valoarea 1.

Pentru exemplul considerat: S={(x1,1),(x3',2)} ; S1={x1,x3'} ; a1=1 ; a2 arbitrar ; a3=0. Continuăm cu demonstrarea suficienţei. Conform ipotezei, există a1,...,an cu Ci(a1,...,an)=1, ∀i=1,...,k.

Pentru fiecare i=1,...,k, există un literal αi din Ci care are valoarea 1. Fie S = {(αi,i) | i=1,...,k}. S este o clică. Într-adevăr, pentru (αi,i),(αj,j)∈S diferite rezultă i≠j şi

αi≠αj deoarece pentru a=(a1,...,an) avem αi=αj=1.

Încheiem prin a prezenta enunţul altor probleme NP-complete. 1) Fie G=(X,M) un graf. Y⊂X se numeşte k-acoperire dacă |Y|=k şi pentru orice

(i,j)∈M avem i∈Y sau i∈Y. Există o k-acoperire? 2) Problema ciclului hamiltonian. 3) Problema colorării hărţilor. 4) Fie A o mulţime şi fie s:A→Z+. Caut B⊂A cu s(A\B)=s(B).

105

10 ALTE TIPURI DE ALGORITMI

10.1. Algoritmi probabilişti

În multe probleme, în timpul rezolvării, putem ajunge la un moment dat în situaţia de a avea de ales între mai multe variante de continuare. Am văzut că în această situaţie putem analiza pe rând variantele, putem încerca să determinăm varianta optimă şi să o urmăm etc.

Algoritmii probabilişti adoptă o altă abordare: se alege aleator una dintre variante. Vom vedea că în unele situaţii această abordare poate conduce la determinarea mai rapidă a unei soluţii (exacte sau aproximative).

Pentru alegerea aleatoare se presupune că avem la dispoziţie o funcţie random, care întoarce o valoare aleatoare dintr-un interval [a,b) de numere reale sau dintr-o secvenţă a..b de numere întregi consecutive.

Este evident că la executări diferite ale unui algoritm probabilist, rezultatele sunt în general diferite.

Există trei categorii mari de algoritmi probabilişti, pe care le prezentăm în

continuare.

• Algoritmi numerici Algoritmii de acest tip sunt caracterizaţi prin următoarele:

- urmăresc determinarea aproximativă a unei valori; - cu cât timpul alocat executării algoritmului este mai mare, precizia rezultatului se îmbunătăţeşte.

Exemplul 1. Acul lui Buffon. Se consideră o mulţime de linii paralele astfel încât oricare două linii

vecine sunt la distanţă de o unitate. Un ac (segment) de lungime o jumătate de unitate este aruncat aleator şi se numără de câte ori a intersectat vreo linie.

Se poate demonstra că probabilitatea ca acul să intersecteze o linie este 1/π. Practic, după un număr "suficient de mare" de încercări, raportul între: - numărul total de încercări şi - numărul cazurilor în care acul a intersectat vreo linie va fi "suficient de aproape" de π.

106

94 10. ALTE TIPURI DE ALGORITMI

Exemplul 2. Se aruncă repetat cu o săgeată într-un panou pătrat. Se presupune că săgeata nimereşte totdeauna panoul. Atunci raportul dintre: - numărul cazurilor în care săgeata nimereşte în cercul înscris în pătrat şi - numărul total de încercări tinde la π/4, număr egal cu raportul dintre aria cercului înscris în pătrat şi aria pătratului.

Exemplul 3. Dată fiind o funcţie f:[a,b]→[c,d], se cere determinarea

aproximativă a valorii I= ∫b

adx)x(f .

Un algoritm probabilist de tip numeric pentru determinarea valorii I este următorul:

s ← 0 for i=1,n x ← random([a,b]); s ← s+f(x) s ← s.(b-a)/n write(s) • Algoritmi Monte Carlo

Algoritmii de acest tip urmăresc determinarea unei soluţii exacte şi sunt

caracterizaţi prin următoarele: - furnizează totdeauna un rezultat, care însă nu este neapărat corect; - probabilitatea ca rezultatul să fie corect creşte pe măsură ce timpul disponibil creşte.

Exemplul 4. Se consideră vectorul x=(x1,...,xn) cu elemente distincte. Se cere determinarea unui element al vectorului care să fie mai mare sau egal cu media aritmetică a celor n numere.

Problema are sens dacă valoarea lui n este foarte mare, iar timpul avut la dispoziţie este mic (în caz contrar alegem, în timp liniar, cel mai mare element al vectorului, care satisface evident condiţia dată).

Un algoritm probabilist, de tipul Monte Carlo, este următorul: alegem aleator un element al vectorului şi repetăm această operaţie fără a depăşi timpul disponibil, păstrând într-o variabilă v cel mai mare dintre elementele alese. Rezultatul întors va fi v.

Să presupunem că în timpul disponibil am analizat k elemente ale vectorului; v este cel mai mare dintre ele. Valoarea v nu îndeplineşte condiţia din enunţ numai în cazul când toate cele k elemente alese sunt mai mici decât media

107

10.1. Algoritmi probabilişti 95

aritmetică a elementelor lui x. Cum probabilitatea ca un element să fie mai mic decât media aritmetică este 1/2, probabilitatea ca toate elementele (deci şi v) să fie

mai mici ca media aritmetică este 2

1k

. Rezultă că probabilitatea ca valoarea

întoarsă de algoritm să fie corectă este 2

11

k− . De exemplu pentru k=20, această

probabilitate este mai mare decât 0,999999. Exemplul 5. Fie G un graf neorientat. Vom înţelege prin mutare eliminarea

unui vârf împreună cu toţi vecinii săi. Se cere numărul minim de mutări prin care se pot elimina toate vârfurile. Această problemă a fost propusă la o olimpiadă şcolară pe timpul când programul era rulat pe 10 exemple şi se contabiliza numărul de exemple pentru care rezultatul furnizat este corect. Pentru a "aduna" puncte, nu este necesar să ne gândim la o soluţie efectivă, ci este suficient să aplicăm următorul algoritm probabilist: - se alege aleator un vârf şi se elimină împreună cu vecinii săi; - se repetă pasul anterior pe noul graf până când sunt eliminate toate vârfurile; - se memorează numărul de mutări efectuat.

Se reia algoritmul (fără a depăşi timpul maxim fixat pentru un test) şi se păstrează cel mai mic număr de mutări. • Algoritmi Las Vegas

Algoritmii de acest tip urmăresc, ca şi algoritmii Monte Carlo,

determinarea unei soluţii exacte şi sunt caracterizaţi prin următoarele: - nu furnizează totdeauna un rezultat, dar dacă furnizează un rezultat atunci acesta este corect; - probabilitatea ca rezultatul să fie corect creşte pe măsură ce timpul disponibil creşte.

Exemplul 5. Se dau n texte (n foarte mare) cu următoarele proprietăţi: - există un unic text t0 care apare de cel puţin 10% ori; - celelalte texte sunt distincte. Se cere determinarea textului t0. Problema a fost propusă la un concurs studenţesc A.C.M. Un algoritm probabilist eficient este următorul:

108

96 10. ALTE TIPURI DE ALGORITMI

repeat i ← random(1..n); j ← random(1..n); if i≠j & ti=tj then write ti; stop until false

Probabilitatea ca alegerea unui indice să conducă la textul t0 este 1/10, deci probabilitatea ca să obţinem o pereche de indici (i,j) cu ti=tj=t0 este 1/100. Cu alte cuvinte, teoretic sunt suficiente 100 de încercări, independent de valoarea lui n. Pe de altă parte este posibil ca algoritmul să nu producă vreun rezultat într-un interval limitat de timp.

Exemplul 6. Problema celor n dame.

Am prezentat o rezolvare a acestei probleme folosind metoda backtracking. Implementarea şi executarea algoritmului corespunzător arată că se ajunge la o soluţie în timp "rezonabil" doar pentru valori mici ale lui n (n≤20).

Un algoritm probabilist pentru această problemă, care furnizează rapid o soluţie chiar pentru valori ale lui n mai mari decât 100 este următorul: - plasăm o damă pe prima linie; - presupunând că am plasat neantagonist câte o damă pe liniile 1,...,k-1, facem

un inventar al poziţiilor posibile pentru dama de pe linia k şi alegem aleator una dintre ele. Exista două posibilităţi:

1) Am reuşit să plasăm o damă pe linia n. Atunci am determinat o soluţie, deci o listăm şi oprim programul;

2) Am ajuns la o linie k şi nu există poziţii posibile. Atunci reluăm întreg algoritmul (deci nu ne întoarcem la linia precedentă ca la backtracking).

Pentru implementarea algoritmului, trebuie ţinută o evidenţă a coloanelor

şi diagonalelor ocupate (pe care nu putem plasa o damă). Pentru aceasta vom folosi vectorii booleeni NV_SE[-n+1..n-1] , NE_SV[2..2n] şi C[1..n] ale căror valori ne spun dacă o diagonală NV-SE, o diagonală NE-SV sau o coloană sunt libere (nu există plasată o damă pe diagonala sau coloana respectivă).

109

10.2. Algoritmi genetici 97

-1

0 1 n-1

-n+1

2 3 n+1

n+2

2n

NV_SE NE_SV

Observaţie. Dacă suntem pe linia k, putem plasa o damă pe coloana i dacă este îndeplinită condiţia: ϕ(k,i) : Ci liberă & NV_SEi-k liberă & NE_SVi+k liberă.

În algoritmul care urmează, soluţia este obţinută în vectorul x=(x1,...xn).

repeat repeat iniţializăm componentele celor 3 vectori booleeni cu valoarea true k ← 1 facem inventarul poziţiilor i∈{1,...,n} cu ϕ(k,i) plasăm aceste poziţii în primele na componente ale unui vector a if na>0 then aleg aleator i∈{1,...,na}; i ← ai xk ← i ; NV_SEi-k ← false; NE_SVi+k ← false Ci ← false; k ← k+1 until na=0 ∨ k=n+1 until k=n+1 write(x)

10.2. Algoritmi genetici

Algoritmii genetici sunt tot algoritmi probabilişti, dar de o natură complet diferită, după cum vom vedea în continuare.

Algoritmii genetici reprezintă tehnici de căutare şi optimizare. Denumirea lor se datorează preluării unor mecanisme din biologie: moştenirea genetică şi evoluţia naturală pentru populaţii de indivizi.

110

98 10. ALTE TIPURI DE ALGORITMI

Problema generală: Fie f:D → R. Se caută max{ f(x) | x∈D }. Presupunem că mulţimea D poate fi pusă în corespondenţă biunivocă cu o

mulţime C ⊂ {0,1}r, adică orice element al lui D poate fi codificat ca: x=(x1,...,xr) cu xi∈{0,1}, ∀ i=1,...,r. Vectorul x se numeşte cromozom. Nu vom lucra cu un singur cromozom, ci cu o populaţie de n cromozomi (indivizi), care se transformă prin trecerea de la o generaţie la alta.

Observăm deci că spre deosebire de algoritmii iterativi uzuali de optimizare, în care la fiecare etapă se trece de la un element din C la următorul, în algoritmii genetici la fiecare etapă se trece de la o submulţime a lui C la o altă submulţime a lui C. O altă trăsătură a algoritmilor genetici este că la trecerea de la o populaţie la următoarea, cromozomii se combină între ei. Observaţie. O populaţie este un multiset (un element poate să apară de mai multe ori). Schimbarea de generaţie se face prin selecţia din populaţia curentă a unei subpopulaţii şi modificarea acesteia prin operaţiile de încrucişare (crossover) şi mutaţie, ce vor fi descrise mai jos. Toate populaţiile succesive au acelaşi număr de indivizi. Algoritmul se încheie dacă s-a efectuat un număr dat de schimbări de configuraţii sau dacă după un număr de schimbări de generaţie maximul curent rămâne neschimbat. Considerăm în continuare prima variantã. Notaţii: P - populaţia curentă; P={p1,...,pn} valmax - valoarea maximă curentă ; xmax - punctul pentru care este atinsă valmax; nmax - numărul maxim admis de schimbări de configuraţii; pc - probabilitatea de încrucişare; pm - probabilitatea de mutaţie; r - lungimea cromozomilor; n=|P|.

Se mai foloseşte o funcţie J:C → R pentru evaluarea performanţelor cromozomilor din P. În general J este corespondenta funcţiei f:D → R.

Algoritmul general este următorul:

P ← aleator; valmax ← -∞ for t=1,nmax

se calculează valorile J(p), ∀ p∈P şi se actualizează eventual valorile xmax şi valmax

etapa de selecţie etapa de încrucişare etapa de mutaţie

111

10.2. Algoritmi genetici 99

Scopul principal al celor trei etape este de a ne apropia cât mai mult de maxim, dar şi de a acoperi prin căutări întregul domeniu de definiţie, pentru a obţine maximul general şi nu unul local. Etapa de selecţie urmăreşte păstrarea (chiar multiplă) a celor mai performanţi indivizi (cromozomi) ai populaţiei curente, dar incluzând şi factorul aleator. Pentru selecţie se foloseşte de obicei algoritmul Monte Carlo descris în continuare.

Fie P={p1,...,pn} şi S= ∑=

n

ii)x(J

1. Fie si=

S

)x(J i probabilitatea de

selecţie a cromozomului pi. Deci s1+...+sn=1. Mai considerăm valoarea s0=0. De n ori procedăm astfel: - generăm un număr aleator x în intervalul [0,1); - este selectat acel cromozom pi pentru care s0+...+si-1≤x<s0+...+si. Cei n cromozomi selectaţi vor constitui noua populaţie după etapa de selecţie. Se observă că un cromozom poate fi selectat de mai multe ori şi de aceea o populaţie este un multiset. Algoritmul de mai sus mai este numit şi algoritmul ruletei, deoarece lucrurile se petrec exact ca la o ruletă împărţită în sectoare corespunzătoare cromozomilor, de mărimi proporţionale cu valorile s1,...,sn ; la fiecare rotire (aleatoare) a ruletei se ajunge în dreptul unui cromozom. Etapa de încrucişare (crossover ) constă în selectarea unei subpopulaţii a populaţiei curente şi recombinarea a câte doi indivizi din subpopulaţie. Este folosit un parametru pc∈[0,1) numit probabilitatea de încrucişare.

Prin recombinarea (încrucişarea) a doi cromozomi se obţin doi descendenţi ce au caracteristici ale ambilor părinţi. O modalitate simplă de încrucişare a doi cromozomi este cea cu un punct de tăietură, în care din "părinţii" : x=(x1,...,xk,xk+1,...,xr) şi y=(y1,...,yk,yk+1,...,yr) se obţin "descendenţii": x'=(y1,...,yk,xk+1,...,xr) şi y'=(x1,...,xk,yk+1,...,yr) unde k este ales aleator din secvenţa 1..r-1. În etapa de încrucişare extragem mai întâi o subpopulaţie Q a lui P, apoi încrucişăm câte doi indivizi din Q, după care adăugăm noul Q lui P:

Q ← ∅ for i=1,n x ← random([0,1)) if x<pc then P ← P \ {pi}; Q ← Q ∪ {pi}

112

100 10. ALTE TIPURI DE ALGORITMI

alegem aleator perechi de elemente din Q şi le încrucişăm (dacă │Q│ nu este par, un element rămâne neschimbat) P ← P ∪ Q Există o mare varietate de modalităţi de încrucişare a doi indivizi. Ne mărginim la cele ce folosesc puncte de tăietură. Considerăm cromozomii: Dacă vom folosi două puncte de tăietură vor rezulta descendenţii: iar dacă vom folosi trei puncte de tăietură vom obţine descendenţii: cu precizarea că punctele de tăietură sunt alese aleator. Etapa de mutaţie constă în selectarea unei subpopulaţii a populaţiei curente şi aplicarea unor mici perturbări cromozomilor din această subpopulaţie. Este folosit un parametru pm∈[0,1) numit probabilitatea de mutaţie. O modalitate simplă de mutaţie a unui cromozom constă în alegerea aleatoare a unei poziţii din cromozom şi modificarea ei: 0↔1. În etapa de mutaţie extragem mai întâi o subpopulaţie Q a lui P, apoi aplicăm mutaţia fiecărui cromozom din Q, după care adăugăm noul Q lui P:

Q ← ∅ for i=1,n x ← random([0,1)) if k<pc then P ← P \ {pi}; Q ← Q ∪ {pi} pentru fiecare q∈Q aplicăm operatorul de mutaţie P ← P ∪ Q

Observaţii: - de obicei pc este de ordinul 10-1 (de exemplu 0.3), iar pm de ordinul 10-3 (de

exemplu 0.007). Experienţele arată că alegerea lui pc şi pm nu are foarte mare importanţă. Alegerea lor se face şi în funcţie de lungimea r a cromozomilor;

113

10.2. Algoritmi genetici 101

- de regulă, în etapa de selecţie, cel mai performant individ este reţinut şi pentru viitoarea configuraţie;

- în funcţia de evaluare (dar nu numai) pot fi folosite distanţe ca de exemplu: cea euclidiană; Hamming - numărul de poziţii pe care cromozomii diferă; Levenstein - numărul minim de ştergeri + adăugări + modificări pentru

a trece de la un cromozom la celălalt. • Aplicaţii

1) Ghicirea interactivă a unei submulţimi p0 a lui {1,2...,r}. Inter-activitatea constă în faptul că pentru fiecare submulţime p "calculatorul" întoarce numărul de poziţii pe care p şi p0 coincid.

O submulţime a lui {1,2...,r} poate fi reprezentată ca un vector x∈{0,1}r cu semnificaţia că i face parte din submulţime dacă şi numai dacă xi=1.

Programul a fost rulat pentru n=r=25, pc=0.3, pn=0.2. J(p) = numărul de poziţii pe care p coincide cu p0 căutată. Variante folosite pentru încrucişare: - cea clasică; - selectăm doi indici p1<p2 şi interschimbăm porţiunile corespunzătoare din

cromozomi. Ne oprim dacă J(p)≥n-2. Determinarea soluţiei exacte poate fi realizată

apoi încercând variantele posibile. 1) Ghicirea unei permutări (interactiv)

Programul a fost rulat pentru n=10, r=10, pc=0.3. Funcţia J şi variantele de crossover sunt aceleaşi ca în exemplul precedent. Mutaţia aplicată unui cromozom p constă în a determina aleator indicii

j,k∈{1,...,n} şi a interschimba p[j] cu p[k].

2) Maximul unei funcţii.

Dorim să determinăm valoarea x0 care maximizează funcţia f:[a,b]→R. Pentru x0 sunt cerute k cifre zecimale.

Fie r cel mai mic număr natural cu (b-a)10k≤2r. Atunci vom lucra cu cromozomi c=(c1,c2,...,cr) de lungime r, unde fiecare ci∈{0,1}. Valoarea x∈[a,b] corespunzătoare lui c se calculează astfel:

- fie x' numărul zecimal egal cu (crcr-1...c2c1)2;

114

102 10. ALTE TIPURI DE ALGORITMI

- x=a+12 −

−r

abx'.

Programul a fost rulat pentru n=30, r=20, pc=0.25, pm=0.1. Variante folosite pentru crossover: - cea clasică; - modificăm ultimele k poziţii aleator; - selectăm doi indici p1<p2 şi interschimbăm porţiunile corespunzătoare

secvenţei de indici p1..p2.

10.3. Principiul lui Dirichlet Prezentăm în acest subcapitol un principiu simplu, cu multe aplicaţii, dar care nu are generalitatea algoritmilor probabilişti şi genetici, studiaţi anterior. Principiul lui Dirichlet are un enunţ simplu şi care nu necesită demonstraţie:

Dacă m>k×n obiecte sunt plasate în n căsuţe, atunci va exista o căsuţă ce va conţine mai mult de k obiecte.

Prezentăm în continuare câteva aplicaţii ale acestui principiu.

Exemplul 1. Există un număr de n perechi de pantofi de mărimi diferite, dar nearanjaţi pe perechi. Care este numărul minim de pantofi care trebuie cercetaţi pentru a forma o pereche ?

Răspunsul este imediat. Folosim câte o cutie (iniţial goală) pentru fiecare mărime. Este evident că după aşezarea în cutii a n+1 pantofi, o cutie va conţine doi pantofi (m=n+1, k=1).

Exemplul 2. Se consideră un vector a=(a1,...,an) de numere naturale.

Se caută indicii i<j cu ai+...+aj multiplu de n. În continuare, pentru orice număr natural x, vom nota prin x clasa sa de

echivalenţă modulo n. Considerăm sumele sk=a1+...+ak pentru k=1,...,n. Fie sk clasele de

echivalenţă corespunzătoare. Deosebim două situaţii:

1) dacă există k cu sk=0, atunci o soluţie este (i,j)=(1,k);

115

10.3. Principiul lui Dirichlet 103

2) în caz contrar, este clar că s1,...,sn∈{1,2,...,n-1}. Conform principiului lui Dirichlet, vor exista indicii k<l cu sk=sl. Atunci o soluţie este (i,j)=(k+1,l).

Exemplul 3. Pentru un număr natural n dat, se caută un multiplu N al său

în a cărei scriere obişnuită (în baza 10) apar numai cifrele 0 şi 1. Problema este asemănătoare celei precedente. Pentru k=1,...,n considerăm numărul sk a cărui scriere în baza 10 este

formată din k de 1, adică s1=1, s2=11 etc.; fie sk clasa de echivalenţă modulo n corespunzătoare.

La fel ca mai sus, deosebim două situaţii: 1) dacă există k cu sk=0, atunci o soluţie este chiar sk; 2) în caz contrar, este clar că s1,...,sn∈{1,2,...,n-1}. Conform

principiului lui Dirichlet, vor exista indicii k<l cu sk=sl. Atunci o soluţie este sl-sk, adică numărul în a cărei scriere apar l-k de 1 urmaţi de k de 0.

Exemplul 4. Teorema lui Erdös. Se dau (m-1)(n-1)+1 numere naturale oarecare. Să se arate că printre

ele există m care se divid unul pe altul, sau există n care nu se divid între ele. Vom aplica tot principiul lui Dirichlet, dar în plan. Se ordonează mai întâi crescător numerele date. Considerăm un caroiaj cu n-1 linii şi m-1 coloane. Vom presupune că

există şi linia imaginară cu numărul de ordine 0, pe care este plasat numărul 1. Considerăm pe rând numerele (în ordine crescătoare). Fiecare număr va fi

plasat pe linia i cu i minim şi cu proprietatea că numărul curent se divide cu un număr aflat pe linia anterioară.

Pentru exemplificare, să considerăm că m=5, n=4, iar numerele sunt: 3,5,9,12,14,15,33,x,... După plasarea primelor 8 numere, suntem în situaţia:

3 5 14 9 12 15 33 24

Dacă de exemplu x=72, atunci el ar trebui plasat pe a patra linie (inexistentă) şi am obţine n=4 numere care se divid unul pe altul (de exemplu 3, 12, 24, 72).

116

104 10. ALTE TIPURI DE ALGORITMI

Dacă de exemplu x=35, atunci el ar trebui plasat pe a doua linie şi am obţine m=5 numere care nu se divid între ele: 9, 12, 15, 33, 35.

Este important de notat că pe fiecare linie numerele plasate apar în ordine crescătoare. Principiul lui Dirichlet ne asigură că cel mai târziu după plasarea ultimului număr vom ieşi din "cutie": aici caroiajul (n-1)×(m-1).

O variantă a principiului lui Dirichlet este următoarea:

Fie k1,...kn , K=(k1+...+kn)/n şi x un număr oarecare. Atunci: dacă x<K ⇒ ∃i cu x<ki dacă x>K ⇒ ∃i cu x>ki

Exemplul 5. Dacă vârfurile unui decagon sunt etichetate distinct cu numerele 0,1,...,9 într-o ordine oarecare, atunci există trei vârfuri consecutive pentru care suma etichetelor este mai mare decât 13.

Fie xi∈{0,1,...,9} eticheta vârfului i, pentru i=1,...,10. Considerăm numerele: k1=x1+x2+x3 k2=x2+x3+x4. . . . . k9=x9+x10+x1 k10=x10+x1+x2 Atunci K=(k1+...+kn)/n = 3(0+1+...+9)/10 = 13,5. Conform principiului lui Dirichlet, va exista i cu ki>13,5>13. Exemplul 6. Se consideră m calculatoare şi n imprimante (m>n). Fie α=numărul minim de legături calculator↔imprimantă ce trebuie stabilite, astfel încât dacă orice n calculatoare doresc să scrie simultan, acest lucru să fie este posibil. Se cere să se arate că α≥n(m-n+1).

Fie ki numărul de calculatoare legate la imprimanta i. Numărul de legături este deci α=k1+...+kn. Dacă α<n(m-n+1), atunci (k1+...+kn)/n<m-n+1. Conform variantei principiului lui Dirichlet, există o imprimantă i legată la cel mult m-n calculatoare, deci care nu este legată la cel puţin n calculatoare; dacă acestea vor să scrie simultan, nu vor reuşi. Contradicţie. Exerciţiu. Să se descrie o modalitate prin care problema poate fi rezolvată cu exact n(m-n+1) legături.

117

Expresii aritmetice. Evaluare şi generarea codului Ne vom ocupa de expresiile aritmetice în care intervin operatorii binari +,-,*,/ şi cuprinderea între paranteze. Vom considera că expresiile cu care lucrăm sunt corecte. Pentru simplificare, vom presupune că variabilele care apar în expresii sunt litere. Scopul propus constă în evaluarea expresiilor (presupunând că variabilele au valori stabilite oarecare) şi în generarea codului corespunzător expresiei, într-un limbaj de asamblare ad-hoc. Ştim că: - o expresie este o "sumă" de termeni (între care intervin numai operatorii de adunare şi

scădere); - un termen este un "produs" de factori (între care intervin numai operatorii de

înmulţire şi împărţire); - un factor este fie o variabilă, fie o expresie între paranteze.

Gramatica independentă de context corespunzătoare, cu simbolul iniţial E, este: E → T+E | T-E | T X → λ T → T*F | T/F | F F → literă | (E) Primul pas în rezolvarea problemelor enunţate constă în construcţia arborelui binar ataşat expresiei. Exemplu. Expresiei aritmetice ((a-b)*(a+c))/(d-(e+f)) îi corespunde arborele:

121110 9 8

765 4

32

1

13

unde etichetele vârfurilor sunt et=(/,*,-,-,+,d,+,a,b,a,c,e,f).

Am văzut că acest arbore binar poate fi construit pe baza algoritmului de analiză sintactică. Vom prezenta însă şi un program Java care construieşte direct acest arbore; la intrare poate să apară orice expresie aritmetică (cu condiţia să fie corectă).

118

• Evaluarea expresiilor aritmetice

Pe baza expresiei aritmetice vom construi arborele asociat. Este clar că pentru evaluarea expresiei, acest arbore trebuie parcurs în postordine; evident, trebuie cunoscute valorile variabilelor ce intervin în expresie.

Construcţia arborelui urmează întocmai definiţia expresiilor aritmetice: va fi scrisă câte o metodă pentru expresie, termen şi factor.

Fiecare vârf (obiect de tipul clasei varf) are câmpurile st, dr şi et desemnând respectiv descendentul stâng, cel drept şi eticheta sa.

Se presupune că variabilele sunt litere mici de la începutul alfabetului şi până la o literă last citită de la intrare. Deci numai pentru literele de la 'a' până la last vor fi citite valorile lor.

Mai este folosită o variabilă ch care joacă rolul unui "spion" către caracterul următor din expresie.

Vom folosi asociativitatea la stânga a operatorilor. De exemplu dacă un termen

începe cu un "produs" de factori pentru care am construit arborele de rădăcină x şi urmează un factor pentru care am construit obiectul y, x va deveni descendent stâng al lui y, care va fi rădăcina noului arbore corespunzător termenului:

y

x

Prezentăm programul Java pentru construirea arborelui ataşat expresiei şi evaluarea expresiei:

class Expresie { public static void main(String[] s) { varf Ob = new varf(); varf.rad = Ob.expresie(); IO.writeln("Val. expresiei: " + Ob.valoare(varf.rad)); } }

class varf { static varf rad; static char last,ch; static double[] val; char et; varf st,dr;

varf() { IO.write("Ultima litera: "); last = IO.readch(); val = new double[last-'a'+1]; for (char c='a'; c<=last; c++) { IO.write(c + "= "); val[c-'a'] = IO.read(); } ch = IO.readch(); }

119

varf(char e) {et =e; } varf factor() { varf x; if ((ch>='a') && (ch<=last)) { x=new varf(ch); ch = IO.readch(); } else { ch = IO.readch(); x = expresie(); ch = IO.readch(); } return x; } varf termen() { varf x,y; x = factor(); while ( (ch=='*') || (ch=='/') ) { y = new varf(ch); y.st = x; ch = IO.readch(); y.dr = factor(); x=y; } return x; } varf expresie() { varf x,y; x = termen(); while ( (ch=='+') || (ch=='-') ) { y = new varf(ch); y.st = x; ch = IO.readch(); y.dr = termen(); x=y; } return x; } double valoare(varf x) { if (x.st == null) return val[x.et - 'a']; else if (x.et == '+') return valoare(x.st) + valoare( x.dr); else if (x.et == '-') return valoare(x.st) - valoare( x.dr); else if (x.et == '*') return valoare(x.st) * valoare( x.dr); else if (x.et == '/') return valoare(x.st) / valoare( x.dr); else return 9999; } }

120

• Generarea codului pentru expresii aritmetice

Presupunem că nu avem restricţii de memorie (deci putem introduce oricâte variabile suplimentare) şi că dispunem de un registru r pentru efectuarea operaţiilor. Instrucţiunile disponibile şi semnificaţiile lor sunt următoarele: 1) LOAD x r ← x 2) STORE x r → x 3) ⊗ x r ← r ⊗ x, unde ⊗∈{+,-,*,/}. Observăm că toate instrucţiunile au două câmpuri. Se consideră că toate aceste instrucţiuni necesită acelaşi timp de executare. Nu vom lua în considerare nici una dintre proprietăţile algebrice ale operaţiilor (comutativitate, asociativitate, distributivitate), nici posibilitatea reducerilor unor termeni şi nici eventuala apariţie a unor subexpresii care se repetă. Dorim să construi un un cod (o succesiune de instrucţiuni de tipurile de mai sus), a cărui executare să aducă în registrul r valoarea expresiei aritmetice. Dorim de asemenea ca acest cod să fie optim, adică să fie format dintr-un număr minim de instrucţiuni.

Observaţie. În orice cod neredundant: 1) numărul de instrucţiuni de tipul 3) este egal cu numărul vârfurilor interne, deci cu

numărul operatorilor ce apar în expresie; prin urmare acest număr este fix; 2) orice instrucţiune LOAD, afară de prima, este precedată imediat de o instrucţiune

STORE. Codul începe cu o instrucţiune LOAD. Cu alte cuvinte, numărul instrucţiunilor LOAD este mai mare cu o unitate decât cel

al instrucţiunilor STORE: #(LOAD)=#(STORE)+1. De aceea un cod optim este un cod cu un număr minim de instrucţiuni STORE .

Este evident că pentru construirea codului, arborele trebuie parcurs în postordine. Ataşăm fiecărui vârf x codul Cx în care în prima instrucţiune lipseşte câmpul

LOAD. Vârfurilor terminale (frunzelor) x le ataşăm codul: _ et(x). Pentru vârfurile neterminale x vom folosi codurile ataşate subarborelui stâng st

şi subarborelui drept dr. Deosebim următoarele cazuri: 1) dacă descendentul drept al lui x este o frunză, codul Cx va fi:

Cstet(x) Cdr2) dacă descendentul drept al lui x nu este o frunză, se observă că este mai convenabil

(din punctul de vedere al numărului de instrucţiuni) să începem cu evaluarea subarborelui drept:

CdrSTORE T LOAD Cstet(x) T unde T este o variabilă suplimentară.

121

Variabilele suplimentare vor fi notate cu Tk, unde k este iniţial 0 şi creşte cu o unitate la fiecare construcţie a unui nou cod pentru un vârf al cărui descendent drept nu este o frunză.

Pentru exemplul considerat mai sus obţinem succesiv:

C8: a C9: b C4: a - b C10: a C11: c C5: a + c C2: a + c STORE T1 LOAD a

- b * T1

C6: d C12: e

C13: f C7: e + f C3: e + f STORE T2 LOAD d - T2 C1: e + f STORE T2 LOAD d - T2 STORE T3 LOAD a

STORE T1 LOAD a

- b * T1

/ T3

În programul Java prezentat mai sus efectuăm următorele modificări: - în metoda principală adăugăm instrucţiunea: IO.writeln("Codul atasat:\n" + "LOAD\t" + Ob.cod(varf.rad)); - în clasa varf adaugăm câmpul static k pentru evidenţa variabilelor suplimentare: static int k;

precum şi metoda cod care produce codul ataşat expresiei, conform parcurgerii în postordine:

String cod(varf x) { int k1; if (x.dr==null) return x.et + ""; if (x.dr.dr==null) return cod(x.st) +"\n" + x.et + "\t" +cod(x.dr); k1=k; k++; return cod(x.dr) + "\nSTORE\tT" + k+ "\nLOAD\t" + cod(x.st) + "\n" + x.et + "\tT" + k; }

122

Mai rămâne de demonstrat optimalitatea codului obţinut în modul descris mai sus. Propoziţie. În orice cod ataşat unui arbore binar, #(STORE) este cel puţin egal

cu numărul vârfurilor al căror descendent drept nu este frunză. Vom face demonstraţia prin inducţie după numărul n al vârfurilor din arbore. Pentru n=1, afirmaţia este evident adevărată. Presupunem afirmaţia din enunţul propoziţiei adevărată pentru orice arbore cu cel

mult n vârfuri şi considerăn un arbore cu n+1 vârfuri. Dacă descendentul drept al rădăcinii este o frunză, atunci numărul vârfurilor al

căror descendent drept nu este frunză coincide cu numărul vârfurilor din subarborele stâng al căror descendent drept nu este frunză; cum acest subarbore are cel mult n vârfuri, putem aplica ipoteza de inducţie.

Dacă descendentul drept al rădăcinii nu este o frunză, atunci fie: n= numărul vârfurilor din arbore al căror descendent drept nu este frunză; s= numărul de instrucţiuni STORE din codul ataşat arborelui; n1= numărul vârfurilor din subarborele stâng al căror descendent drept nu este frunză; s1= numărul de instrucţiuni STORE din codul ataşat subarborelui stâng; n2= numărul vârfurilor din subarborele drept al căror descendent drept nu este frunză; s2= numărul de instrucţiuni STORE din codul ataşat subarborelui drept. Conform ipotezei de inducţie avem: s1≥n1 şi s2≥n2. Evident, n=n1+n2+1. Pe de altă parte în codul ataşat arborelui mai trebuie introdusă cel puţin o instrucţiune STORE, deci s≥s1+s2+1. Rezultă s≥n1+n2+1=n.

Optimalitatea algoritmului prezentat rezultă acum din faptul că el introduce o

nouă instrucţiune STORE numai pentru vârfurile al căror descendent drept nu este o frunză.

123

12 NP-COMPLETITUDINE

Ştim că doar algoritmii polinomiali sunt eficienţi, deci urmărim totdeauna să elaborăm astfel de algoritmi. Este evident însă că nu există algoritmi polinomiali pentru orice problemă, ca de exemplu în cazul în care numărul datelor de ieşire nu este polinomial: determinarea tuturor submulţimilor unei mulţimi finite, generarea permutărilor etc. De aceea căutăm să delimităm clasa problemelor pentru care încercăm să elaborăm algoritmi polinomiali. În acest scop introducem noţiunea de algoritm nedeterminist.

Algoritmii nedeterminişti sunt algoritmi secvenţiali care, spre deosebire de cei obişnuiţi, admit şi următoarele instrucţiuni suplimentare:

1) success şi failure, care arată că algoritmul se termină cu succes, respectiv cu eşec. Ele înlocuiesc instrucţiunea stop. Forma lor arată că vom studia doar probleme de decizie, pentru care rezultatul poate fi doar afirmativ sau negativ (după cum vom vedea, foarte multe probleme pot fi aduse la aceasta formă).

2) choice(A), unde A este o mulţime finită; este o funcţie care întoarce ca rezultat un element oarecare al lui A.

Se consideră că cele trei instrucţiuni nou introduse necesită un timp constant.

Maşina abstractă care execută un astfel de algoritm, când întâlneşte o instrucţiune choice lucrează astfel: - dacă există o valoare din A care conduce la o instrucţiune success, va fi

aleasă o altfel de valoare; - în caz contrar, va fi aleasă o valoare oarecare.

Cu alte cuvinte, un algoritm nedeterminist se termină cu eşec dacă nu există o modalitate de a efectua alegeri care să conducă la o instrucţiune success.

Funcţionarea maşinii abstracte se aseamănă calculului paralel. De câte ori este întâlnită o instrucţiune choice, intră în acţiune atâtea procesoare câte

124

114 12. NP-COMPLETITUDINE

elemente are mulţimea A. Algoritmul se termină cu succes dacă unul dintre procesoarele active ajunge la o instrucţiune success. Timpul de executare va fi, în cazul unei terminări cu succes, timpul necesar ajungerii la respectiva instrucţiune success.

Mai precizăm că ne interesează doar terminările cu succes. Exemplul 1. Se cere să se verifice dacă un număr x apare sau nu în

mulţimea {a1,...,an}.

Ştim că timpul de executare pentru algoritmul determinist pentru această problemă este de ordinul O(n), adică liniar. Putem scrie următorul algoritm nedeterminist:

i ← choice({1,2,...,n}) if ai=x then write i; success else failure

care rezolvă problema în timp constant.

Exemplul 2. Se cere să se ordoneze crescător vectorul a=(a1,...,an).

Ştim că cel mai bun algoritm determinist pentru această problemă necesită un timp de ordinul O(n.log n). Ideea algoritmului nedeterminist este următoarea: copiem elementele vectorului a într-un vector auxiliar b într-o ordine oarecare, după care verificăm dacă elementele lui b apar în ordine crescătoare.

for i=1,n bi ← ∞ { iniţializarea lui b }

for i=1,n j ← choice({1,2,...,n}) if bj=∞ then bj ← ai { fiecare ai trece pe o poziţie nouă din b } else failure

for i=1,n-1 if b >b then failure i i+1

write(b); success

Timpul de executare al acestui algoritm este O(n), deci liniar. Se observă că: - am obţinut un timp de executare mai bun; - problema sortării a fost tratată ca o problemă de decizie.

125

12. NP-COMPLETITUDINE 115

Exemplul 3. Problema validării. Fie F(x1,...,xn) o expresie booleană în forma normală conjunctivă

(FNC): F=C1∧...∧Ck , unde C1,...,Ck sunt disjuncţii de variabile de forma xj sau jx ( jx este negaţia lui xj). Se cere să se determine dacă există a1,...,an∈{0,1} cu F(a1,...,an)=1. Problema va fi referită în continuare sub numele VALID.

Un exemplu de instanţă a problemei este: F(x1,x2,x3)=(x1∨x2∨x3)∧( 1x ∨ 2x ∨ 3x ). Un algoritm nedeterminist simplu care rezolvă problema este următorul:

for i=1,n xi ← choice({0,1}) if F(x1,...,xn)=1 then success else failure

Timpul este proporţional cu lungimea formulei, deci liniar. Observaţie. Nu se cunoaşte un algoritm determinist polinomial pentru

problema validării !

Introducem clasele de probleme (de decizie) următoare: P - clasa problemelor pentru care există algoritmi determinişti polinomiali; NP - clasa problemelor pentru care există algoritmi nedeterminişti polinomiali. Vom studia problema existenţei algoritmilor (determinişti) polinomiali doar pentru problemele din NP.

Evident P⊂NP. Este însă incluziunea strictă sau P=NP ? Precizăm de la început că această problemă este deschisă!

În 1976, Samuel Cook a obţinut un rezultat care a simplificat problema şi care a părut promiţător în rezolvarea ei:

Teoremă. P=NP ⇔ VALID∈P.

Teorema spune că dacă reuşim să găsim un algoritm determinist polinomial pentru VALID, atunci va exista un algoritm determinist polinomial pentru orice problemă din NP.

126

116 12. NP-COMPLETITUDINE

Întrucât nu s-a reuşit să se obţină un algoritm polinomial pentru VALID, s-a încercat să se rezolve probleme "echivalente" cu VALID. Mai precis s-a definit clasa NPC . Clasa de probleme NPC este definită astfel: 1) VALID∈NPC 2) Pentru o problemă P, P∈NPC dacă:

2.1) se cunoaşte pentru P un algoritm nedeterminist polinomial; 2.2) VALID se poate reduce la P în timp determinist polinomial. Problemele din NPC se numesc NP−complete.

NPC

P

NP

Observaţie. Este suficient să arătăm pentru o singură problemă NP–completă că admite un algoritm polinomial, pentru a obţine egalitatea P=NP. Lista problemelor NP–complete a depăşit 1000, dar pentru nici una dintre ele nu s-a reuşit să se obţină un algoritm determinist polinomial. Drept urmare, aşa cum am menţionat anterior, problema egalităţii P=NP rămâne o problema deschisă. Prezentăm în continuare una dintre multele probleme NP–complete.

Problema clicii maximale. Fie G=(X,M) un graf neorientat. Y⊂X se numeşte clică dacă pentru

∀i,j∈Y avem (i,j)∈M. Se caută ordinul unei clici maximale. Problema de decizie corespunzătoare este următoarea: Pentru un k dat, există în G o clică de ordin k ? Pentru această problemă vom scrie procedura clica(G,k), care furnizează răspunsul în timp nedeterminist polinomial. Presupunând cunoscut acest lucru, algoritmul pentru problema clicii maximale va fi:

for k=n,1,-1 clica(G,k)

care este tot polinomial.

127

12. NP-COMPLETITUDINE 117

procedure clica(G,k) for i=1,n ales(i) ← 0 {elementul i nu a fost ales} { pentru fiecare i alegem un element j∈{1,...,n} pe care îl punem în bi } for i=1,k j ← choice({1,...,n}) if ales(j)=1 then failure else ales(j) ← 1; bi ← j { s-au ales k vârfuri distincte b1,...,bk }

for i=1,k for j=1,k

if i≠j & (bi,bj)∉M then failure

write(k); success end; Timpul este evident polinomial. Prin urmare CLICA(k) ∈ NP, deci şi CLICA ∈ NP.

Arătăm în continuare că VALID se reduce la CLICA în timp determinist polinomial.

Fie F(x1,...,xn) o expresie booleană în forma normală conjunctivă (FNC): F=C1∧...∧Ck , unde C1,...,Ck sunt disjuncţii de variabile de forma xj sau jx , numiţi literali.

Ataşăm lui F graful G=(X,M) astfel: X = {(α,i) | α literal din Ci} M = {[(α,i),(β,j)] | α ≠ β}, adică α şi β pot fi satisfăcuţi concomitent.

De exemplu, pentru F(x1,x2,x3) = (x1∨x2∨x3) ∧ ( 1x ∨ 2x ∨ 3x ), graful este:

( 3x ,2)

( 2x ,2)

( 1x ,2)

(x3,1)

(x2,1)

(x1,1)

Construcţia grafului necesită un timp determinist polinomial. Mai trebuie demonstrat că: în G există o clică de ordin k ⇔ F este

validabilă.

128

118 12. NP-COMPLETITUDINE

Începem cu demonstrarea necesităţii. Fie S = {(αi,i) | i=1,...,k} o clică de ordin k.

Fie S1 = {αi | i=1,...,k}. Conform construcţiei lui M, nu este posibil ca αi şi iα să apară simultan în S1. Alegem fiecare ai astfel: 1 dacă xi∈S1, adică αi=xi0 dacă ix ∈S1arbitrar în caz contrar. Pentru această alegere, F(a1,...,an)=1, fiecare conjuncţie având valoarea 1.

Pentru exemplul considerat: S={(x1,1),( 3x ,2)} ; S1={x1, 3x } ; a1=1 ; a2 arbitrar ; a3=0. Continuăm cu demonstrarea suficienţei. Conform ipotezei, există a1,...,an cu Ci(a1,...,an)=1, ∀i=1,...,k.

Pentru fiecare i=1,...,k, există un literal αi din Ci care are valoarea 1. Fie S = {(αi,i) | i=1,...,k}. S este o clică. Într-adevăr, pentru (αi,i),(αj,j)∈S diferite rezultă i≠j

şi αi≠ jα , deoarece pentru x=(a1,...,an) avem αi=αj=1.

Încheiem prin a prezenta enunţul altor probleme NP-complete. 1) Fie G=(X,M) un graf. Y⊂X se numeşte k-acoperire dacă |Y|=k şi dacă pentru

orice (i,j)∈M avem i∈Y sau i∈Y. Există o k-acoperire? 2) Problema ciclului hamiltonian. 3) Problema colorării hărţilor. 4) Fie A o mulţime şi fie s:A→Z+. Căutăm B⊂A cu proprietatea că suma

elementelor lui B să fie egală cu suma elementelor lui A\B.

129

Analiza sintactică

Toate gramaticile cu care vom lucra în acest sunt independente de context; de

aceea nu vom mai specifica explicit acest lucru. Fie G=(VN,VT,S,P) o gramatică (independentă de context). Analiza sintacticǎ constǎ în următoarele: - se dǎ ; *

TVw∈- se cere sǎ se determine dacǎ w∈L(G) şi, în caz afirmativ, sǎ se determine producţiile

care trebuie aplicate pentru a obţine o derivare stângǎ a lui w din S.

Observaţie. Dacă producţiile au numere de ordine, şirul numerelor de ordine ale producţiilor ce trebuie aplicate este numit sintaxa stângă a lui w. Ea este importantă, deoarece pe baza ei se poate construi uşor arborele de derivare asociat lui w.

Vom folosi următoarele convenţii de notaţii:

a,b,c,... ∈ VTA,B,C,... ∈ VN x,y,z,u,v,w,...∈ *

TV

α,β,γ,... ∈ *)V(V TN ∪ şi se va specifica explicit când ele sunt încǎlcate.

În continuare considerǎm cǎ în G nu apar neterminale "nefolositoare", adică: - din orice neterminal derivă un cuvânt format numai din terminale (neterminalul este

observabil); - pentru orice neterminal există o derivare din S în care apare acel neterminal

(neterminalul este accesibil). Ştim că pentru orice gramatică independentă de context există una echivalentă de

acelaşi tip, în care nu apar neterminale nefolositoare, deci presupunerea făcută nu este restrictivă.

De asemenea, toate derivările care vor apărea în continuare sunt derivări stângi (ştim că existenţa unei derivări este echivalentă cu existenţa unei derivări stângi).

În sfârşit, închiderea tranzitivă şi reflexivă a relaţiei de derivare ⇒ va fi notată tot prin ⇒, pentru a nu încărca scrierea.

Definim două funcţii cu care vom lucra în continuare.

ϕ : (VN∪VT)* → P(VT∪{λ}) (prin P am notat mulţimea părţilor), dată de: ϕ(α) = {a∈VT|α⇒ax} ∪ {λ|dacă α⇒λ}. Funcţia ϕ mai poartă numele FIRST. Caz particular: pentru ,Vα *

T∈ ϕ(α)={a}, unde a este prima literǎ din α (dacǎ α≠λ) sau este λ (dacǎ α=λ).

Definiţia funcţiei ϕ se poate extinde la mulţimi de cuvinte din *

TN )V(V ∪ . Pentru definim: ϕ(L)=∪{ϕ(α)|α∈L}. *

TN )V(VL ∪⊂

130

Definim funcţia { }( )λ∪⎯→⎯ TN VV:ψ P prin:

)}(,|}{{)( βϕβαβαλψ ∈⇒∃∪∈= acuAScuVaA T

}|{},|{*

AScudacaAaScuVa T ααλβαβα ⇒∃∪⇒∃∈=

Definiţie. G este o gramaticǎ LL(1) dacǎ:

wxwwAS ⇒⇒⇒ βαα

wywwAS ⇒⇒⇒ γαα ⇒ γβ =

)()( yx ϕϕ = adicǎ, dat fiind un cuvânt wAα şi un terminal a, existǎ cel mult o producţie (cu A în membrul stâng) care se poate aplica astfel încât în final sǎ se obţinǎ un cuvânt format din terminale în care imediat dupǎ w sǎ aparǎ a.

Teoremǎ. G este de tip LL(1) ⇔ PAA ∈→→∀ γβ , distincte, avem φγψϕβψϕ =∩ ))(())(( AA .

„⇐” Fie wxwwAS ⇒⇒⇒ βαα

wywwAS ⇒⇒⇒ γαα

)()( yx ϕϕ = Cum γβ ≠ , conform ipotezei, avem: φγψϕβψϕ =∩ ))(())(( AA . Dar ))(()()( Ax βψϕβαϕϕ ⊂⊂ ))(()()( Ay γψϕγαϕϕ ⊂⊂ )()( yx ϕϕ = , deci φγψϕβψϕ ≠∩ ))(())(( AA . Contradicţie. „⇒” Fie PAA ∈→→ γβ , distincte. Presupunem cǎ ))(())((},{ AAaVa T γψϕβψϕλ ∩∈∪∈∃ . • Dacǎ a ∈ VT avem patru situaţii:

1) deci 21 , axax ⇒⇒ γβ)()(ϕ β ∩∈a γϕ

∃ w,α cu (nu existǎ neterminale nefolositoare) αwAS ⇒

11 ywaxwwAS ⇒⇒⇒ βαα

}{)()( 2211

22

ayaxyax

ywaxwwAS

==

⇒⇒⇒

ϕϕ

γαα ⇒ γβ = . Contradicţie.

131

2) )()( γϕψ ∩∈ Aa

adicǎ , deci ax⇒⇒ γλβ ; ax⇒γ

α,w∃ cu şi αwAS ⇒ ay⇒α

waywwwAS ⇒⇒⇒⇒ αβαα

⇒ β = γ. Contradicţie. waxayw ⇒⇒ γα}{)()( aaxayay == ϕϕ

3) )()( Aa ψβϕ ∩∈ Se face la fel ca la 2).

4) λγλβψ ⇒⇒∈ ,),(Aa

Deci α,w∃ cu cu αwAS ⇒ ax⇒α

waxwwwAS ⇒⇒⇒⇒ αβαα

⇒ β = γ. Contradicţie. waxww ⇒⇒⇒ αγα

}{)()( aaxax == ϕϕ

• Dacǎ a = λ

Atunci avem γ )(Aψλ

λ

λβ

∈⇒

⇒

şi deci ∃ w, α cu şi αwAS*

)(αϕλ ∈ , adicǎ . λα⇒

λαβαα wwwwwAS =⇒⇒⇒⇒

⇒ β = γ. Contradicţie. λαγα wwww =⇒⇒⇒

λ = λ

Corolar. G este LL(1) ⇔ PAA n ⊂→→∀ },...,{ 1 αα , φαϕαϕ =∩ )()( ji

pentru i ≠ j; dacă . ijAji ≠∀=∩⇒ φψαϕλα )()(atunci,

132

Traducătorul sintactic

Este asemǎnǎtor unui automat push-down. Are însǎ în plus o bandǎ de ieşire şi funcţioneazǎ pe baza unui tabel de analizǎ sintacticǎ conform unui algoritm sintactic.

Bandǎ de intrare

$

X

Banda de ieşire

Π

Tabel de analizǎ sintacticǎ

Memorie push-down

Dacǎ G este o gramaticǎ LL(1), atunci: - pe banda de intrare apar cuvinte ; *

TVw∈- pe banda de ieşire apar şiruri π formate din numerele de ordine ale producţiilor

din gramaticǎ; - în memoria pushdown apar cuvinte de forma α $ cu . *)( TN VV ∪∈α

Prin configuraţie înţelegem un triplet (x, α, π) unde:

- este cuvântul care a mai rǎmas de citit de pe banda de intrare; *TVx∈

- α este cuvântul din memoria p.d.; - π este şirul aflat pe banda de ieşire.

Configuraţia iniţialǎ este (w, S$, λ) unde w este cuvântul care trebuie analizat

sintactic.

Trecerea de la o configuraţie la alta este datǎ de algoritmul sintactic pe baza tabelului de analizǎ sintacticǎ.

133

Tabelul de analizǎ sintacticǎ Tabelul de analiză sintactică este o funcţie M definită pe

}){({$})( λ∪×∪∪ TTN VVV . Pentru gramaticile de tipul LL(1) vom defini acest tabel conform regulilor:

1) Fie . Definim PA i ∈⎯→⎯ α ),(),( iaAM α= pentru }{\)( λαϕ∈∀ a . Dacǎ în plus )(αϕλ ∈ , definim )(),,(),( AbibAM ψα ∈∀= .

2) SALT =),( aaM3) =)($,λM DA 4) În rest, =NU. ),( ⋅⋅M

Observaţie: Fie . Atunci PA i ∈⎯→⎯ α ))((),(),( AaiaAM αψϕα ∈⇔=

Aceastǎ observaţie aratǎ, pe baza corolarului precedent, cǎ funcţia M este bine definitǎ.

Exemplu: M a b λ S aAS,1 b,2 A a,3 bSA,4 a SALT b SALT $ DA

1) aASS → 2) bS → 3) aA→ 4) bSAA→ Algoritmul sintactic

Pentru gramaticile LL(1) definim urmǎtorul algoritm sintactic: 1) ),,( παXx |⎯ ),,( ix πβα dacǎ ),())(,( ixXM βϕ = , adicǎ ))(()( Xx βψϕϕ ∈ 2) ),,( παaax |⎯ ),,( παx , ceea ce corespunde situaţiei =),( aaM SALT 3) Algoritmul se terminǎ dacǎ: 3.1) se ajunge la ),$,( πλ ; se aplicǎ deci =)($,λM DA 3.2) se ajunge la ),,( παXx cu =))(,( xXM ϕ NU.

Exemplu. Pentru gramatica de mai sus: )$,,( λSabbab |⎯ |⎯ )1$,,( aASabbab )1$,,( ASbbab |⎯ (bbab,bSAS$,14) |⎯ (bab,SAS$,14) |⎯ (bab,bAS$,142) |⎯ (ab,AS$,142) |⎯ (ab,aS$,1423) |⎯ (b,S$,1423) |⎯ (b,b$,14232) |⎯ (λ,$,14232) deci w=abbab∈L(G) şi sintaxa sa stângă este π=14232.

134

Fie acum un tabel de analizǎ sintacticǎ M oarecare şi fie A un algoritm sintactic construit pe baza acestui tabel. Atunci pentru definim ∗∈∀ TVw

π=)(wA ,dacǎ )$,,( λSw |⎯ ),$,( πλ nedefinit , în caz contrar Definiţie. Algoritmul şi tabelul sunt corecte dacǎ: 1) )$,,()( λSwGLw ⇔∈ |⎯ ),$,( πλ *

2) Dacǎ da, . wSπ∗⇒

Definiţie. Algoritmul A este corect dacǎ :

1) })(|{)( definitwAVwGL T∗∈=

2) Dacǎ A(w) = π, atunci π este sintaxa stângǎ a lui w (adicǎ ). wSπ⇒

Definiţie. Tabelul M este corect dacǎ algoritmul construit pe baza lui este corect. Remarcǎm cǎ în cazul unui tabel şi a unui algoritm corecte, algoritmul se opreşte

într-una dintre situaţiile: 1) w ∈ L(G), adicǎ w este „corect sintactic”; în acelaşi timp este furnizatǎ sintaxa lui; 2) w ∉ L(G), adicǎ w „nu este corect sintactic”; în aceastǎ situaţie va trebui produs

un mesaj de eroare.

Teoremǎ. Algoritmul sintactic şi tabelul de analizǎ sintacticǎ definite mai sus pentru gramaticile LL(1) sunt corecte. Demonstraţia cuprinde doi paşi.

• Arătăm mai întâi că din (xy, S$, λ) |⎯ (y, α$, π) rezultă : απ

xS∗

⇒*

Demonstraţia se face prin inducţie dupǎ numǎrul n de schimbǎri de configuraţie. Pentru n = 1 (xy, S$, λ) |⎯ (y, α$, π) implicǎ x = λ, π = i, M(S, ϕ(y)) = (α, i) unde

. Rezultǎ . PS i ∈⎯→⎯ α απ

xS∗

⇒n → n+1 (xy, S$, λ) |⎯ (ay, β$, π’) |⎯ (y, α$, π), unde a∈ VT ∪ {λ}. Implicǎ x = x’a. *

n

Conform ipotezei de inducţie, din (x’(ay), S$, λ) |⎯ (ay, β$, π’) rezultǎ . βπ

''

xS∗

⇒n*

Dacă a = λ, atunci β = Aγ, α = δγ, π =π’i, . Rezultǎ

.

),())(,(, iyAMPA i δϕδ =∈⎯→⎯

αδγγβπ

xxxAxSi

=⇒=⇒∗

''

Dacă a ≠ λ , atunci β = aα, π’ = π şi ααβπ

xaxxS ==⇒∗

'' .

135

• Mai arătăm că:

)$,,( λαπ

SxyxSn

⇒⇒∗

|⎯ (y, α$, π) ∀ y cu ϕ(y) ⊂ ϕ(α), unde α este fie λ, fie începe cu

un neterminal.

*

n = 1 : . Fie y cu ϕ(y) ⊂ ϕ(α). αxS i⎯→⎯ 1) x ≠ λ : (xy, S$, λ)|⎯ (xy, xα$, λ) pentru cǎ ϕ(xy) ⊂ ϕ(xαψ(S))

i

|⎯ (y, α$, π) *

2) x = λ : (y, S$, λ)|⎯ (y, α$, i) pentru cǎ ϕ(y) ⊂ ϕ(α )⊂ ϕ(αψ(S)). n → n+1

cu π = π’i (am pus în evidenţă ultimul pas) ααπ

xAxSi

n⇒⇒

∗

11

'

α1 x1 α2 x2

α1 A x1 22αxA i⎯→⎯

x α Din α2 început al lui α rezultă că α2 = λ sau α2 începe cu un neterminal. Fie y cu ϕ(y) ⊂ ϕ(α). Trebuie )$,,( λSxy |⎯ (y, α$, π). *Cf. ipotezei de inducţie, pentru ∀ z cu ϕ(z) ⊂ ϕ(Aα1), avem : (x, z, S$, λ)|⎯ (z, Aα1$, π’). *Luăm z = x2y. Atunci ϕ(x2y) ⊂ ϕ(Aα1) deoarece ϕ(x2y) ⊂ ϕ(x2α) ⊂ ϕ(Aα1) pt. că Aα1 ⇒ x2α2α1 = x2α. Deci (x1x2y, S$, λ) |⎯ (x2y, Aα1$, π’). * = x Mai trebuie (x2y, Aα1$, π’) |⎯ (x2y, x2α2α1$, π’i) |⎯ (y, α$, π). ? * ? dacǎ ϕ(x2y) ⊂ ϕ(x2α2ψ(A)):

1) dacǎ x2 ≠ λ, evident 2) dacǎ x2 = λ trebuie ϕ(y) ⊂ ϕ(α2ψ(A)). Dar ϕ(y) ⊂ ϕ(α) = ϕ(α2α1) = ϕ(α2ϕ(α1))

⊂ ϕ(α2ψ(A)) pentru cǎ . 11 αAxS∗

⇒

Înlocuind acum y = α = λ în paşii notaţi cu •, sse obţine rezultatul din enunţul teoremei.

136

Aplicaţie Considerăm următoarea gramatică ce generează expresiile aritmetice corecte în care apare variabila a, operaţiile binare + şi *, precum şi cuprinderea între paranteze. S → S+T S → T T → T*F T → F F → (S) F → a Este evident că această gramatică nu este de tipul LL(1). Ea poate fi adusă însă la o gramatică de tipul LL(1), folosind faptul că ansamblul de producţii: A → Aα A → β este echivalent cu ansamblul de producţii: A → βA' A'→ αA' A'→ λ Obţinem astfel următoarea gramatică echivalentă de tipul LL(1): (1) S → TE (2) E → +TE (3) E → λ (4) T → FU (5) U → *FU (6) U → λ (7) F → (S) (8) F → a

Tabelul de analiză sintactică este următorul: a ( ) + * λ S TE,1 TE,1 E λ,3 +TE,2 λ,3 T FU,4 FU,4 U λ,6 λ,6 *FU,5 λ,6 F a,8 (S),7 a SALT ( SALT ) SALT + SALT * SALT $ DA

137

Să considerăm cuvântul w=(a*a) şi să aplicăm algoritmul sintactic: [(a*a),S$,λ] ├⎯ [(a*a),TE$,1] ├⎯ [(a*a),FUE$,14] ├⎯ [(a*a),(E)UE$,147] ├⎯ [a*a),E)UE$,147] ├⎯ [a*a),TE)UE$,1471] ├⎯ [a*a),FUE)UE$,14714]├⎯ [a*a),aUE)UE$,147148] ├⎯ [*a),UE)UE$,147148]├⎯ [*a),*FUE)UE$,1471485] ├⎯ [a),FUE)UE$,1471485]├⎯ [a),aUE)UE$,14714858] ├⎯ [),UE)UE$,14714858]├⎯ [),E)UE$,147148586] ├⎯ [),)UE$,1471485863] ├⎯ [λ,UE$,1471485863] ├⎯ [λ,E$,14714858636] ├⎯ [λ,$,147148586363] Rezultă că w este corect ( adică w∈L(G) ) şi sintaxa sa stângă este π=147148586363, pe baza căruia putem construi arborele de derivare. Observaţie. De fapt am redus problema la determinarea funcţiilor ϕ şi ψ, sarcină ce nu este deloc facilă!

138

1. Interclasare optimă de şiruri ordonate Pentru n şiruri ordonate crescător se dau lungimile acestora. Se doreşte să se

obţină un singur şir ordonat care conţine toate elementele şirurilor iniţiale, interclasând şiruri două câte două. Să se determine ordinea în care trebuie efectuate aceste interclasări astfel încât numărul de deplasări să fie minim (pentru interclasarea a două şiruri de lungimi m şi respectiv n sunt necesare m+n deplasări). Să se afişeze şi numărul total de deplasări efectuate.

Observatie: Se cere doar ordinea interclasarilor, nu si interclasarea propriu-zisa.

Indicaţie: Strategia Greedy pentru rezolvarea acestei probleme este următoarea: la fiecare pas se combină cele mai scurte două şiruri disponibile la momentul respectiv. procedure INTERCLASARE_OPTIMA

for i :=1 to n do adauga( (Li, i), A)

for i:= n+1 to 2n-1 (Lj, j) := extrage_minim(A) (Lk, k) := extrage_minim(A) adauga((Lj + Lk, i), A) writeln 'interclasare S’,j, ' de lungime ', Lj, ' cu

S',k, ' de lungime ', Lk Pentru a reţine perechile (lungime, număr şir) se va folosi un min-ansamblu în raport cu lungimea şirurilor (ai≤a2i şi ai≤a2i+1 ,dacă fiii există). Elementul minim va fi a[1]. La adăugarea unui element nou nu se va recrea întreg ansamblu. Se poate folosi o metodă nouă (faţă de cele făcute la sortarea cu ansamble) de a găsi locul în ansamblu pentru noul element introdus, interschimbând elementul cu părintele dacă părintele este mai mare (deci nu este verificată condiţia de min-ansamblu) şi urcând astfel în arbore până este găsit locul elementului nou introdus. O altă modalitate de a evita crearea ansamblului din nou după fiecare interclasare este să nu extragem cel de al doilea minim din ansamblu, ci sa îl înlocuim cu noul şir obţinut, apelând apoi procedura de refacere a ansamblului din rădăcina, ţinând cont că subarborii drept şi stâng verifică ambii condiţia de ansamblu ( combin(1,n) ). Procedura devine procedure INTERCLASARE_OPTIMA

A := creare_ansamblu((Li, i), i = 1,..,n ) for i:= n+1 to 2n-1

(Lj, j) := extrage_minim(A) (Lk, k) := minim(A) inlocuieste_minim(A, (Lj + Lk, i)) combin(A,1,n) writeln 'interclasare S’,j, ' de lungime ', Lj, ' cu

S',k, ' de lungime ', Lk 2. Algoritmul lui Prim de determinare a unui arbore parţial de cost minim. 3. Numere frumoase

139

Numerele frumoase sunt numerele care au ca factori primi doar pe 2, 3 şi 5. Dat un număr natural n (1 ≤ n ≤ 1500) afişaţi primele n numere frumoase (în ordine). Indicaţie: Se reţine la fiecare moment cel mai mic multiplu de 2 încă neadăugat şi indicele din tablou care conţine elementul din care s-a obţinut prin înmulţire cu 2. La fel pentru 3 şi 5. SAU 3. Se dau n şi k naturale, k ≤ n. Să se construiască o matrice n×n care îndeplineşte simultan condiţiile: - conţine toate numerele de la 1 la n2 o singură dată - pe fiecare linie numerele sunt aşezate în ordine crescătoare, de la stânga la dreapta - suma elementelor de pe coloana k să fie minimă.

140

Clasa String Câteva metode ale clasei String care pot fi utile în problemele date sunt public int length()

Returnează lungimea şirului

public char charAt(int index) Returnează caracterul de pe poziţia index din şir. Poziţiile în şir sunt numerotate

de la 0 la lungimea şirului minus 1. Dacă index nu se încadrează între aceste limite, metoda aruncă excepţie (IndexOutOfBoundsException) public String substring(int beginIndex, int endIndex)

Returnează un nou şir care reprezintă subşirul care începe pe poziţia beginIndex a şirului curent şi se termină pe poziţia endIndex - 1. public String substring(int beginIndex)

Returnează un nou şir care reprezintă subşirul care conţine caracterele de la poziţia beginIndex a şirului curent până la sfârşit (se termină pe poziţia length()-1) public boolean equals(Object anObject)

Compară şirul curent cu un obiect. Rezultatul returnat este true dacă argumentul este un obiect nenul de tip String şi reprezintă aceeaşi secvenţă de caractere ca şi şirul curent, şi false în caz contrar . public int indexOf(int ch)

Returnează poziţia primei apariţii a caracterului ch în şir şi -1 în cazul în care caracterul ch nu se găseşte în şir

Programare Dinamică 1. Se dă un şir de cuvinte. Să se determine cel mai lung subşir al şirului dat cu proprietatea că oricare două cuvinte consecutive din acest subşir verifică relaţia: ultimele două litere din primul cuvânt coincid cu primele două litere din următorul cuvânt. (Subşirul unui şir este format din elemente ale şirului, nu neapărat consecutive, dar care respectă ordinea din şirul iniţial. Un subşir al şirului a1, a2, …, an este de forma ai1, ai2, …, aik, cu 1≤i1<i2<…<ik≤n) De exemplu, pentru şirul

seara, carte, teorema, temperatura, rar, mare, arbore cel mai lung subşir care verifică cerinţele este

carte, temperatura, rar, arbore

141

2. Se consideră un şir de n piese de domino. O piesă de domino are formă dreptunghiulară şi are înscrisă pe ea două numere, cuprinse între 1 şi 6. O piesă poate fi întoarsă (rotită cu 1800), inversându-se astfel ordinea celor două numere înscrise pe ea.

Conform regulilor la domino, un lanţ este un subşir al şirului de piese iniţial constituit din piese care respectă următoarea condiţie: pentru oricare două piese consecutive din lanţ, al doilea număr înscris pe prima din cele două piese coincide cu primul număr înscris pe cea de a doua piesă. Să se determine cel mai lung lanţ care se poate obţine cu piesele din şirul dat . Exemplu: pentru n = 8 şi şirul de piese (1,5), (1,3), (2,6), (2,5), (4,3), (6,4), (2,4), (1,6) lungimea celui mai lung lanţ este 5, un astfel de lanţ fiind format cu piesele de pe poziţiile 1(inversată), 2, 5(inversată), 6(inversată), 8(inversată) şi anume (5,1), (1,3), (3,4), (4,6), (6,1) 3. Se dau cuvintele dintr-un dicţionar. Să se descompună un cuvânt dat într-un număr minim de cuvinte existente în dicţionar. Exemplu: pentru dicţionarul cu cuvintele

a, apa, apar, ne, par, ţi, ţine descompunerea minimă pentru cuvântul aparţine este formată din cuvintele apar, ţine; descompunerea minimă pentru cuvântul apar este formată doar din cuvântul apar, deoarece acesta este în dicţionar. 4. Se consideră alfabetul A format din literele mici începând cu ‘a’ şi terminând cu litera mică last citită de la intrare. Pe acest alfabet este dată o lege de compoziţie printr-o matrice t (nu se presupune că legea este asociativă sau comutativă). Fiind dat un cuvânt x de lungime n peste alfabetul A şi o literă dest din A, să se determine dacă există o parantezare a literelor cuvântului astfel încât rezultatul efectuării calculelor să fie dest Divide et Impera 1. Problema tăieturilor: Se dă o placă dreptunghiulară cu lungimea L şi înălţimea h în care există n găuri punctiforme, poziţiile găurilor fiind date prin coordonatele carteziene ale acestora (x, y). Să se determine placa de arie maximă care se poate decupa din placa iniţială şi care nu conţine în interior nici o gaură. Sunt permise numai tăieturi verticale şi orizontale complete (de la o latură la latura opusă)

142

Sistemul de axe se poate considera cu originea în colţul din stânga-jos al plăcii. Un dreptunghi va fi identificat prin coordonatele colţului din stânga-jos (x1,y1) şi coordonatele colţului din dreapta-sus (x2,y2) . 2. Problema plierii: Se consideră un vector de lungime n. Definim plierea vectorului prin suprapunerea unei jumătăţi numită donatoare peste cealaltă numită receptoare, cu precizarea că dacă numărul de elemente este impar, numărul din mijloc este eliminat. În acest mod se ajunge la un subşir ale cărui elemente au numerotarea corespunzătoare jumătăţii receptoare. Plierea se poate aplica în mod repetat până se ajunge la un subşir de lungime 1, numit element final. a) Să se precizeze toate elementele finale b) Dat un element i, să se scrie o succesiune de plieri prin care se ajunge la el – dacă i este element final; dacă i nu este final se va afişa un mesaj corespunzător. De exemplu, vectorul (1, 2, 3, 4, 5) se poate plia în două moduri (1, 2) sau (4, 5), elementul 3 fiind eliminat. 3. Se dau n cărţi de matematică (M), română (R), fizică (F) şi informatică (I) şi trei rafturi corespunzătoare tipurilor cărţilor: RR – raftul cărţilor de română RMI – raftul cărţilor de matematică sau de informatică RF – raftul cărţilor de fizică Pentru fiecare carte se citesc numele cărţii şi tipul ei. Cărţile sunt aşezate în teanc pe un raft A în ordinea în care sunt citite. Având la dispoziţie două rafturi B şi X, să se transfere cărţile de pe raftul A pe rafturile RR, RMI şi RF după următoarele reguli:

- pe rafturile A şi B se pot pune sau lua oricâte cărţi - pe raftul X se poate pune sau lua o singură carte - pe RR, RMI şi RF se pot pune cărţi, nu şi lua - la orice mutare avem acces la o singură carte – cea din vârful teancului - tipul cărţii se poate citi numai în B şi numai când este o singură carte pe acest raft - în final cărţile pe RR, RMI şi RF trebuie să fie în aceeaşi ordine în care erau pe A. a) Să se afişeze mutările pentru transferul cărţilor fără să se facă deosebire între

cărţile de matematică şi informatică. Se vor afişa numărul de cărţi mutate şi rafturile între care se mută, iar când se face un transfer al unei cărţi din B pe raftul corespunzător tipului se va afişa titlul cărţii care se repartizează şi tipul ei (vezi exemplul)

b) Rezolvaţi problema astfel încât în final cărţile de matematică să apară în raftul RMI înaintea celor de informatică (respectând ordinea în care erau în A).

Exemplu: Pentru cărţile de intrare (date cu nume şi tip) Mate1 de tip M Fizica1 de tip F Rom1 de tip R Info1 de tip I

143

Info2 de tip I Mate2 de tip M Rom2 de tip R Fizica2 de tip F O posibilă soluţie la punctul a) ar fi (o carte s-a afişat sub forma nume – tip) initial A=[Mate1 - M, Fizica1 - F, Rom1 - R, Info1 - I, Info2 - I, Mate2 - M, Rom2 - R, Fizica2 - F] Sir mutari 7 carti A->B, 1 carti A->X, 7 carti B->A , 1 carti X->B, Repartizez Mate1 – M, 6 carti A->B, 1 carti A->X, 6 carti B->A, 1 carti X->B, Repartizez Fizica1 - F 5 carti A->B, 1 carti A->X, 5 carti B->A, 1 carti X->B, Repartizez Rom1 – R, 4 carti A->B, 1 carti A->X, 4 carti B->A, 1 carti X->B, Repartizez Info1 – I, 3 carti A->B, 1 carti A->X, 3 carti B->A, 1 carti X->B, Repartizez Info2 - I 2 carti A->B, 1 carti A->X, 2 carti B->A, 1 carti X->B, Repartizez Mate2 - M, 1 carti A->B , 1 carti A->X, 1 carti B->A, 1 carti X->B, Repartizez Rom2 - R, 1 carti A->B, Repartizez Fizica2 - F, Rafturi carti dupa repartizare RF: [Fizica1 - F, Fizica2 - F] RMI: [Mate1 - M, Info1 - I, Info2 - I, Mate2 - I] RR: [Rom1 - R, Rom2 - R] Observaţii pentru implementare în Java Rafturile se pot memora ca stive, deoarece putem pune sau lua cărţi de la un singur cap al raftului (mutăm mereu cartea din capul teancului). În Java există clasa Stack (din pachetul java.util) pentru lucru cu stive. Pentru a introduce un element în stivă există metoda push, pentru a elimina vârful stivei – metoda pop (care returnează elementul eliminat)

144

Până la varianta 5.0 într-o stivă (obiect de tip Stack) se puteau introduce obiecte de orice tip. La extragerea unui element din stivă programatorul trebuia să ştie ce tip de elemente a introdus în stivă şi să facă o conversie explicită la acel tip. Chiar dacă elementele introduse erau de acelaşi tip, tot era nevoie de conversie explicită, elementul extras dintr-o stivă fiind de tip Object. Spre exemplu, puteam introduce în stivă alternativ numere întregi şi şiruri de caractere

Stack stiva=new Stack(); for (int i=0;i<5;i++){

stiva.push(new Integer(i)); stiva.push("valoarea "+i);

} String sirTop=(String)stiva.pop(); System.out.println(sirTop); Integer x=(Integer)stiva.pop(); System.out.println(x);

Acest cod este corect şi în varianta 5.0, doar la compilare se va semnala ca observaţie faptul că programul foloseşte operaţii nesigure. Începând cu această variantă s-a introdus posibilitatea de a defini de la declararea stivei tipul elementelor care se vor introduce în stivă. Pe parcursul programului în stivă se vor putea introduce doar elemente de acest tip, iar la extragere nu mai este nevoie de conversie explicită, cunoscându-se tipul elementului extras. Spre exemplu, să considerăm clasa Carte care poate fi folosită pentru problema rafturilor import java.util.Stack; class Carte{

String nume; int tip;//0-F,1-M,2-I, 3-R Carte(){ } Carte(String s, int t){

nume=s; tip=(byte)t;

} public String toString(){

switch(tip){ case 0: return nume+" - F"; case 1: return nume+" - M"; case 2: return nume+" - I"; case 3: return nume+" - R"; } return "";

} }

145

class Rafturi{ public static void main(String arg[]){

Stack<Carte> raft=new Stack<Carte>(); raft.push(new Carte("romana",3)); raft.push(new Carte("fizica",0)); raft.push(new Carte("matematica",1)); raft.push(new Carte("informatica",2)); Carte c=raft.pop(); //nu mai este necesara conversie System.out.print("UltimSystem.out.println(c);

a carte introdusa: ");

System.out.print("Cartile ramase pe raft "); System.out.println(raft);

} } Observaţie

Metoda println apelată cu parametru un obiect invocă metoda public String toString()

şi afişează rezultatul întors de aceasta. Orice clasă extinde clasa Object, care are metoda toString(). Suprascriind în clasa Carte această metodă putem afişa un obiect de tip Carte

sub forma dorită. (Dacă nu suprascriem această metodă, ea va returna numele clasei şi adresa de memorie corespunzătoare obiectului) .

Mai mult, metoda toString() a clasei Stack va apela metoda toString a fiecărui element al stivei (Nu mai este astfel nevoie să facem o metodă de afişare a stivei, care să parcurgă fiecare element al stivei şi să-l afişeze).

Programul va afişa Ultima carte introdusa: informatica - I Cartile ramase pe raft [romana - R, fizica - F, matematica - M] Se vor prezenta 5 probleme din care obligatoriu 2 probleme de programare dinamică şi 2 de divide et impera.

146