Teoria complexitatii are ca obiect de studiu clasificarea problemelor, bazata pe timpul de executie si spatiul de lucru utilizat de algoritmi pentru solutionarea lor.
Cind se analizeaza algoritmi paraleli, se poate lua in considerare si numarul de procesoare.
Desi teoria complexitatii a fost dezvoltata pentru probleme de decizie, aceasta nu este o restrictie severa deoarece multe alte probleme pot fi formulate in termeni de probleme de decizie.
De exemplu o problema de optimizare poate fi rezolvata prin punerea intrebarii existentei unei solutii cu cel mult sau cel putin o valoare specificata.
Complexitatea timpului de executie a unui algoritm paralel care rezolva o instanta de dimensiune n a unei probleme, pe o masina paralela cu p procesoare (p=dimensiunea masinii) se noteaza a cu T (p, n) =Tp (n). O problema se numeste dependenta de dimensiunea masinii (PDD) daca n este o functie de variabila p.
Altfel, problema se numeste independenta de dimensiunea masinii (PID). Un algoritm dependent de dimensiunea masinii este un algoritm ce rezolva o problema PDD. altfel, algoritmul se numeste independent de dimensiunea masinii.
Factorul de incarcare (L) a unei probleme este raportul n/p. Viteza Sp (n)) unui algoritm paralel este raportul T1 (n) /Tp (n). Eficienta (Ep (n)) unui algoritm paralel se defineste ca fiind raportul dintre viteza si numarul procesoarelor: Fiind date doua functii f si g pozitive de variabile p si n se noteaza: o (g) ={f/ ( () (>0, ([{p0, n0 (p) } (N] a.
i. ( () [ (p>p0) ( (n>n0 (p)) ]: f (p, n) < ( (g (p, n) } Rezulta ca f este in o (g) daca limn ( ( (f/g) =0. O (g) ={f/ ([{p0, n0 (p) } (N (c (R (] a.
i. ( () [ (p>p0) ) ( (n>n0 (p)) ]: f (p, n) p0) ) ( (n>n0 (p)) ]: 0 ...
Pentru a descărca acest document,
trebuie să te autentifici in contul tău.
