Java - Metoda Backtracking, Arbori, Grafuri, Greedy, Divide et Impera, Metoda Programării Dinamice, Algoritmi

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ă ,RQ cu Q.

Pentru demonstraţie să considerăm numărul real x=aa, unde a= .

Dacă xQ, propoziţia este demonstrată.

Dacă xQ, atunci xaQ şi din nou propoziţia este demonstrată.

• 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.