Complexitatea Algoritmilor

Etapele rezolvării unei probleme

Este cunoscut faptul că rezolvarea unei probleme presupune în principal trei etape: I. Analiza problemei, II. Proiectarea soluţiei şi III. Implementarea şi testarea soluţiei în practică.

În funcţie de gradul de generalitate a analizei efectuate, în a doua etapă se întîlnesc două situaţii: proiectarea unei soluţii particulare, valabilă doar pentru acea problemă, şi proiectarea unei soluţii generale, valabilă pentru orice instanţiere a acelei probleme (soluţia generalizată).

În timp ce soluţia particulară este valabilă doar pentru o instanţă a problemei, soluţia generală este independentă de parametrii problemei şi oferă o metodă generală de rezolvare a problemei.

Astfel, soluţionarea imediată a ecuaţiei x3+1=0 este particulară faţă de soluţionarea ecuaţiei generalizate ax3+bx2+c=0.

Noţiunea de algoritm şi cea de program

Atunci cînd metoda generală de rezolvare a unei probleme este prezentată precis, pe paşi ce se efectuează într-o ordine bine precizată şi care conduc în timp finit la soluţia oricărei instanţieri a problemei, vorbim de algoritmul de rezolvare a problemei.

De exemplu, algoritmul de determinare a unei soluţii reale a ecuaţiei polinomiale P(x)=0, cu o aproximare  dată, prin metoda tangentei.

Avantajul major al proiectării unui algoritm de soluţionare a problemei este dat de faptul că efortul de rezolvare poate fi transferat unei maşini automate (calculator) sub forma programului executabil ce implementează algoritmul general de soluţionare.

Implementarea algoritmului general de soluţionare a problemei într-un program pe calculator permite o importantă economie prin faptul că efortul major de analiză şi proiectare a soluţiei a fost efectuat o singură dată iar rezolvarea problemei se reduce la efortul foarte redus de executare (rulare) a programului cu ajutorul calculatorului pentru fiecare instanţă diferită a problemei.

Modelul abstract al Maşinii Turing

Primul model teoretic riguros de maşină automată de calcul este Modelul maşinii abstracte Turing (1936). Acest model teoretic a stat la baza apariţiei efective a primei maşini electronice de calcul, denumită mai tîrziu computer (calculator) după denumirea operatorului uman (tehnicianului) care era angajat să facă toate calculele inginereşti sau contabile ale unui proiect sau ale unei firme.

Teza Turing-Church

Rezultă că, în ultimă instanţă, puterea de rezolvare a unui calculator se reduce la puterea de calcul a maşinii Turing. Iar puterea de calcul a acestei maşini abstracte riguroase este exprimată sub forma Tezei Turing-Church: O maşină Turing poate face tot ceea ce poate face un computer uman înzestrat cu creion, oricîte foi de hîrtie şi reguli precise ( mecanice sau automate ) de calcul.

Există, pe lîngă această formulare iniţială a lui Turing, o serie de alte formulări echivalente ale acestei teze unanim acceptate de teoreticienii ce au pus bazele teoriei informatice şi a ştiinţei calculatoarelor (computer science). Să observăm că această teză (propoziţie acceptată fără demonstraţie ca avînd valoarea logică de adevărat) stabileşte o echivalenţă perfectă între puterea de calcul a unui computer uman şi puterea de calcul a unui computer maşină .

Echivalarea subînţeleasă (tacită) a noţiunii teoretice vagi de algoritm cu noţiunea matematică riguroasă de Maşină Turing a însemnat acceptarea unanimă a Tezei Turing-Church de către iniţiatorii informaticii. În consecinţă, studiul eficienţei unui algoritm în soluţionarea unei probleme revine în studiul eficienţei în funcţionare a maşinii Turing şi implicit a eficienţei în funcţionare a programului ce implementează acel algoritm de rezolvare.

Aceasta este consecinţa faptului că, în accepţiunea originală, algoritmul de soluţionare a unei probleme este destinat unui computer uman, dar puterea de calcul a acestuia este aceeaşi cu puterea de calcul a unei maşini Turing=computer maşină care este pusă în mişcare printr-un program executabil.

Analiza, Proiectarea şi Implementarea algoritmilor şi Complexitatea algoritmilor

Reluînd ideea iniţială, în rezolvarea automată a unei probleme (adică rezolvarea cu ajutorul calculatorului a oricărei instanţe diferite problemei) se trece prin cele trei etape: Analiza teoretică a problemei, Proiectarea algoritmului de soluţionare şi Implementarea algoritmului într-un program executabil pe calculator.

În timp ce în prima etapă –analiza problemei- rezultatul cheie, pe care se concentrează preponderent efortul de analiză, este demonstrarea corectitudinii soluţiei, în a doua etapă –proiectarea algoritmului de soluţionare- cuvîntul cheie este eficienţa de rezolvare. Studiul cu un pronunţat caracter teoretic conţinut în această a doua etapă îşi propune să prevadă eficienţa în funcţionare (necesarul de timp şi spaţiu calculator) a programului executabil ce va implementa algoritmul, eventual prin compararea teoretică a algoritmilor de soluţionare diferiţi.

De exemplu, în cazul problemei sortării unui şir de n chei prin comparaţii se poate estima teoretic comparativ că algoritmul de sortare QuickSort este printre cele mai eficiente soluţii.

Disciplina informaticii care se ocupă cu studiul teoretic al eficienţei algoritmilor este numită Complexitatea algoritmilor.

Operaţia de bază, cheia studiului complexităţii

La baza studierii complexităţii unui algoritm stă detectarea în descrierea algoritmului a operaţiei sau a operaţiilor de bază, acea operaţie (acele operaţii) aflată (aflate) în cel mai interior corp de ciclu repetitiv şi a cărei (a căror) contorizare permite estimarea în avans, înainte de lansarea în execuţie, a timpului de execuţie a programului executabil corespunzător.

În majoritatea cazurilor există o legătură foarte strînsă între operaţia de bază (cea mai repetată operaţie) şi operaţia care este dedusă în etapa de analiză a problemei ca fiind operaţia inevitabilă pentru rezolvarea problemei.

De exemplu, în cazul problemei sortării unui şir de n chei prin comparaţii este limpede că operaţia de comparare a “mărimii” cheilor este operaţia inevitabilă şi deasemenea ea va fi şi operaţia de bază a cărei contorizare va permite estimarea, înainte de execuţie, a duratei de funcţionare a programului ce implementează algoritmul de sortare respectiv.

Clase de algoritmi

În această situaţie, toţi algoritmii diferiţi care soluţionează aceeaşi problemă şi care se bazează pe aceeaşi operaţie de bază (inevitabilă) formează clasa algoritmilor de soluţionare a problemei. Deobicei numele clasei va fi dat chiar de numele acelei operaţii de bază ce este conţinută de fiecare algoritm al clasei în mod inevitabil.

De exemplu, în cazul problemei sortării unui şir de n chei prin comparaţii, algoritmii diferiţi ce soluţionează problema sînt grupaţi în clasa algoritmilor de sortare prin comparaţii, spre deosebire de clasa algoritmilor de sortare prin distribuire ce soluţionează aceeaşi problemă bazîndu-se însă pe altă operaţie de bază: distribuirea cheilor de sortat.

Operaţia de bază a algoritmilor dintr-o clasă de algoritmi poate fi comparată cu o vergea verticală pe care sînt înşiraţi toţi algoritmii clasei. Ea este cea care permite studiul comparativ a eficienţei algoritmilor din acea clasă (ea fiind o veritabilă coloană vertebrală a clasei respective).

Eficienţa algoritmilor

Compararea eficienţei a doi algoritmi diferiţi ce soluţionează aceeaşi problemă se face prin determinarea teoretică a numărului de repetiţii a operaţie de bază în fiecare algoritm şi compararea celor două valori. În final rezultatul comparării va permite estimarea comparativă a duratei de funcţionare a programelor şi alegerea celui mai bun.

Compararea eficienţei a doi algoritmi din punct de vedere practic se face prin compararea timpilor medii de execuţie a celor două programe ce îi implementează. Această metodă pragmatică are dezavantajul că necesită rularea programelor care, în anumite situaţii, poate dura un timp surprinzător de mare.

Funcţiile de complexitate

Numărul de repetiţii al operaţiei de bază se exprimă matematic printr-o funcţie de complexitate individuală asociată algoritmului, funcţie ce depinde în mod inevitabil de dimensiunea (mărimea) vectorului datelor de intrare.