Algoritmi

Definitii:

Algoritm: o procedura de calcul bine definita care primeste la intrare o multime

de valori (input) si produce la iesire un alt set de valori (output).

Instantele unei probleme: multimea tuturor intrarilor din care se poate calcula

o solutie pentru problema

Corectitudine: un alg e corect daca pt fiecare instanta el furnizeaza

rezultatele corecte (rezolva problema).

Analiza unui algoritm: identificarea resurselor necesare (timp calcul, memorie,

latime banda de comunicare, etc.)

Modelul tehnologiei pe care se implementeaza alg: un procesor cu memorie RAM,

multiprocesor cu memorie partajata, fiecare avand proprii algoritmi.

Instrumente matematice de analiza a alg:

analiza combinatorica discreta, teoria probabilitatii, identificarea

termenilor cei mai semnificanti dintr-o formula

Cazuri de analiza: cel mai bun (favorabil), cel mai rau (defavorabil), caz mediu

de complexitate

Eficienta asimptotica a alg: determinarea gradului de crestere

Notatii asimptotice:

- Complexitatea unui algoritm este o functie bine definita.

- De obicei ne intereseaza doar gradul de crestere al acesteia, deoarece

el influenteaza cel mai mult pentru o instanta a problemei de

dimensiune mare.

- Fie f(n) functia de complexitate a unui algoritm.

- Se numesc functii asimptotice pozitive functiile f(n) care au valoare

pozitiva pt orice n suficient de mare.

- Notatiile asimtotice urmatoare folosesc doar functii asimtotice

pozitive.

Notatie asimptotica limitata strans la ambele capete: Q()

Q(f(n)) = {g(n) | exista c1>0, c2>0, n0>0 ai

0<=c1*f(n)<=g(n)<=c2*f(n) pt orice n>n0 }

fie g(n) = 1/2n^2 - 3n

Atunci pt a arata ca g(n) apartine Q(f(n)), adica notam ca

g(n)=Q(f(n)), tre sa gasim constantele pozitive c1,c2,n0 astfel

incat 0<=c1*f(n)<=g(n)<=c2*f(n) pt orice n>n0.

Aratam ca g(n)=Q(n^2). Din calcule, rezulta ca pt n0=7, avem c1=1/14

si c2=1/2

Notatie asimptotica limitata strans superior: O()

O(f(n)) = {g(n) | exista c>0 si n0>0 ai

0<=g(n)<=c*f(n) pt orice n>n0}

Notam ca o functie g(n) aprtine lu O(f(n)) prin g(n)=O(f(n))

O(f(n)) reprezinta timpu de rulare al unui algoritm pt cazu cel mai

defavorabil. De exemplu pt sortarea prin insertie, pentru cazul cel

mai favorabil avem timpu de rulare O(n).

Notatie asimptotica limitata strans inferior: W()

W(f(n)) = {g(n) | exista c>0 si n0>0 ai

0<=c*f(n)<=g(n) pt orice n>n0}

Teorema: Pt orice f(n) si g(n), avem f(n)=Q(g(n)) dsnd f(n)=O(g(n)) si

f(n)=W(g(n))

Notatii asimptotice in ecuatii:

Dc notatia asmpt. apare ca unic element in partea dr. a unei ecuatii,

f(n)=O(g(n)) atunci semnifica f(n) apartine O(g(n)).

Dc notatia apare intr-o formula in partea dreapta, atunci o interpretam

ca pe o functie anonima k(n) care apartine lui O(g(n)).

Ex: 2n^2+3n+1 = 2n^2+Q(n) -> k(n)=3n+1=Q(n).

Notatia o():

Echivalentu lu O() insa fara limitare stransa:

o(f(n)) = {g(n) | pt orice c>0 exista n0>0 ai

0<=g(n)<=c*f(n) pt orice n>n0}

ex: 2n=o(n^2), insa 2n^2 != o(n^2).

Notatia w():

similar cu o() pentru limitare inferioara.

ex: n^2=w(n), n^2 != w(n^2)