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