Introducere in Stiinta Calculatoarelor 2013 | Page 93

toate piesele n de date. Complexitatea algoritmului este indicată de ordinul său. În urma analizei unui algoritm rezultă un ordin al acestuia, care poate fi încadrat în una din clasele de complexitate de mai jos în scopul comparării la un nivel mai general a algoritmilor: Clasa P pentru probleme polinomiale, ce se pot rezolva într-un număr de operaţii exprimabil printr-un polinom de n – numărul de piese de date, într-un mod determinist (adică cunoscut şi stabilit perfect privind operaţiile şi rezultatul lor). Clasa NP pentru probleme nedeterminist polinomiale, ce se pot rezolva într-un timp polinomial într-un mod nedeterminst (de exemplu prin „ghicirea” soluţiei folosind algoritmi genetici, apoi se verifică dacă soluţia este corectă. În clasa NP există o subclasă de probleme numite NP-complete care nu se pot rezolva în timp polinomial dar măcar se poate verifica în timp polinomial o eventuală soluţie. Soluţia propriu-zisă necesită un timp de rezolvare cuprins între unul exprimat polinomial şi unul exprimat exponenţial. 6.3. Categorii de prelucrare şi prezentare a informaţiilor În acest paragraf se vor trece în revistă o serie de prelucrări uzuale realizate de sisteme de calcul, cu caracteristicile lor. Scopul paragrafului este de a se completa noţiunile prezentate în paragrafele anterioare, cu locul şi rolul prelucrărilor de date şi modului cum acestea sunt utilizate de către om. Se va începe cu prelucrări matematice (cele care dau şi numele instrumentului „calculator”) dar se vor trece în revistă şi categorii de prelucrări care emulează modul de a raţiona sau reacţiona al omului, precum şi prelucrări care prezintă informaţia către acesta. Nu se vor trece în revistă domenii de utilizare a calculatorului în viaţa omului ci caracteristicile diferitelor prelucrări pe care le poate (şi trebuie) să le facă în susţinerea unei utilităţi umane. 93