Complexitatea Calculului

Teoria complexităţii constituie un domeniu foarte important al teoriei algoritmilor care investighează rezolvabilitatea individuală a problemelor sub anumite restricţii de resurse.

Teoria complexitatii calculului cuprinde:

1) Un studiu analitic al complexităţii unor clase de probleme în raport cu diverse tipuri concrete de maşini matematice care le rezolvă;

2) Un studiu calitativ al complexităţii algoritmilor care rezolvă astfel de probleme.

Mai precis, complexitatea calculului se bazează pe legăturile existente între problemele rezolvabile algoritmic şi resursele de calcul.

Inainte de a trece la analiza unui algoritm, trebuie să se cunoască o tehnologie de implementare a acestuia care va include un model pentru resursele sale şi costurile corespunzătoare. Aşadar, resursele de calcul sunt introduse prin definirea unui model de calcul care, de regulă, reprezintă o maşină. In acest sens pot fi utilizate: ma]ini Turing de diverse tipuri, ma]ini cu acces aleator (random-acces machine, RAM), circuite booleene etc. Resursele tipice sunt: timp, spatiu, benzi, capete de citire/scriere, nivele intr-un circuit etc.

Pentru tratarea celor două elemente fundamentale, problema si masina, considerăm trei nivele abstracte în complexitatea calculului.

a) Un nivel înalt care pune în evidenţă complexitatea abstractă a calculului, cunoscută sub numele de „teoria Blum de complexitate a calculului", care este independentă atât de problemă cât şi de maşină. O astfel de teorie este construită pe o enumerare efectivă a tuturor funcţiilor parţial recursive, o enumerare a aşa numitelor funcţii „ cost-măsură " şi două axiome de bază (axiomele lui Blum).

b) Un nivel mediu care pune în evidenţă complexitatea structurală, independentă de problemă dar dependentă de maşină. Scopul unei astfel de complexităţi este de a studia capabilitatea unor modele de calcul concrete pentru resurse sau combinaţii de resurse, independent de problema propusă.

c) Un nivel inferior ce indică o complexitate concretă care depinde atât de maşină cât şi de problemă. Scopul său este de a detecta o bună evaluare, cu un cost pe cât posibil minim, folosind o resursă (sau combinaţii de resurse) într-un model precizat pentru rezolvarea problemei.

In general, dificultatea unei probleme P se poate măsura prin resursele de calcul limitate asociate algoritmului secvenţial care o rezolvă. Aceste resurse sunt timpul si spatiul de memorie necesare pentru execuţia algoritmului respectiv. O astfel de măsură se poate evalua în diverse moduri. In termenii maşinii Turing, ca model de calcul, complexitatea temporală este stabilită de numărul de deplasări necesare realizării calculului respectiv, iar pentru un computer digital, de numărul de ciclări ale maşinii sau timpul real solicitat de maşină pentru acel calcul. In ceea ce priveşte complexitatea spaţială, pentru maşina Turing, ea constă în numărul de celule (pătrate) ale benzii folosite în calcul, iar pentru computer, în numărul de bytes utilizaţi.

Prin urmare, ideea de complexitate a unui algoritm poate fi privită sub două aspecte:

a) static, prin structura sa.

b) dinamic, prin durata execuţiei sale.

Complexitatea spatiala se exprimă prin dimensiunea spaţiului de memorie necesar algoritmului, independent de comportarea pe care o are el pe parcursul execuţiei.

Complexitatea temporala se exprimă prin timpul necesar execuţiei sale. Axiomele lui Blum, de exemplu, pun în evidenţă măsuri de complexitate dinamică cu consecinţe ca: teorema corelării măsurilor, teorema accelerării, teorema lacunei etc.

Există numeroase probleme de optimizare în reţele de transport, informatică, electronică, logistica construcţiilor, teoria comunicaţiilor (în codurile corectoare de erori), criptografie etc. Pentru algoritmii de rezolvare a acestor probleme este obligatoriu un studiu al complexităţii lor. Complexitatea algoritmilor relativ la coduri, reprezentarea compactă a mesajelor în vederea transmiterii lor prin diverse canale, permite o analiză asupra eficacităţii metodelor de codificare/decodificare. Relativ la criptografie, studiul complexităţii implică elaborarea unor tehnici care să permită cifrarea mesajelor sub o formă care să le asigure, pe cât posibil, inviolabilitatea.

Analiza unui algoritm conduce la stabilirea eficienţei sale şi implică, în principal, ideea de complexitate pentru că ea prevede resursele solicitate de algoritmul respectiv. Stabilirea complexităţii unui algoritm este necesară, pe de o parte, datorită faptului că mulţi algoritmi sunt eliminaţi de practică deoarece necesită un timp de execuţie şi un spaţiu de memorie foarte mari, iar pe de altă parte, se caută algoritmi cât mai performanţi în vederea rezolvării cu calculatorul a unor probleme destul de complexe impuse de practică. Un calculator, oricât de performant ar fi, este în esenţă un automat finit, deci el are posibilităţi limitate. Performanţa unui algoritm se stabileşte conform unui criteriu care, de cele mai multe ori, îl constituie timpul de execuţie al algoritmului respectiv.

Având în vedere faptul că pentru seturi de date de intrare diferite acelaşi algoritm foloseşte timpi de execuţie diferiţi este necesar a lua în consideraţie:

• timpul in cazul cel mai favorabil (durata minimă pentru execuţia algoritmului);

• timpul mediu (raportul dintre suma timpilor necesari pentru toate seturile de date posibile şi numărul acestor seturi);

• timpul in cazul cel mai defavorabil (durata maximă pentru execuţia algoritmului).

Acesta din urmă oferă o margine superioară a timpului de execuţie pentru toate intrările de o dimensiune fixă şi reprezintă situaţia cea mai indicată pentru căutarea de informaţii într-o bază de date.

Să considerăm implementarea unui algoritm oarecare care să primească intrări de dimensiuni diferite. La o intrare de dimensiune n vom asocia o măsură f(n) de folosire a resurselor sale care, de regulă, trebuie să se minimizeze. In mod normal, f(n) va reprezenta timpul solicitat de algoritm pentru intrarea de dimensiune n în cazul cel mai defavorabil sau mediu (la alegerea noastră). Există o serie de factori care complică mai mult sau mai puţin calculul exact al lui f(n). De exemplu:

a) Timpul solicitat pentru execuţia unei instrucţiuni individuale dintr-un program, cu aceeaşi instanţă şi pe aceeaşi maşină, poate varia.

b) Poate exista o mare variaţie de folosire a resurselor pentru intrări de o anume dimensiune constantă n.

c) Cazul cel mai defavorabil poate fi mai rar întâlnit în practică, iar cazul mediu să fie nereprezentativ.

d) Unii algoritmi se pot executa mai bine pe anumite clase de intrări.

In acest sens se impun câteva sugestii, cum ar fi:

- Identificarea operaţiilor abstracte folosite de algoritm. Pentru a obţine o maximizare a independenţei de maşină este necesară o analiză a acestor operaţii abstracte, pentru că resursele solicitate de o mare parte din ele vor fi neimportante. Unele din ele sunt utilizate o singură dată la iniţializare.

- Un algoritm, în general, posedă cel puţin un ciclu. Acesta trebuie identificat pentru că instrucţiunile din interiorul său se execută mult mai des şi ele vor juca un rol important în analiza timpului de execuţie a algoritmului. Prin contorizarea acestor instrucţiuni se determină o margine superioară corespunzătoare pentru valoarea timpului de execuţie în cazul cel mai defavorabil şi, dacă este posibil, o configurare a cazului mediu. Această limită superioară este necesară pentru că, în mod practic, nu poate fi găsită o valoare exactă a timpului de execuţie în cazul cel mai defavorabil.

- Timpul necesar unui algoritm pentru rezolvarea unei probleme cu o instanţă dată, reprezintă numărul operaţiilor elementare (primitive) efectuate de algoritm pentru acea instanţă. Se acceptă o astfel de interpretare deoarece se presupune că execuţia unei astfel de operaţii se produce într-un timp constant şi nu depinde de mărimea operanzilor şi nici de timpul de memorare a rezultatului. De aceea resursa timp asociată se analizează independent de sistemul de calcul pe care se implementează algoritmul respectiv.

- Deşi progresele tehnologice actuale fac ca necesarul de memorie să treacă pe un plan secund, există totuşi situaţii în care spaţiul de memorie utilizat este folosit ca argument în stabilirea unor limite inferioare pentru timpul de execuţie.

- Viteza de calcul ce caracterizează actuala generaţie de calculatoare are drept consecinţă faptul că problema timpului de execuţie se pune, în general, pentru valori foarte mari ale dimensiunii intrării. Aceasta conduce la ideea unei analize a termenului dominant (cel care tinde cel mai repede la infinit) din formula de exprimare a numărului de operaţii elementare executate de către algoritm.