METODE DE PROIECTARE A ALGORITMILOR

1 Elaborarea algoritmilor

Prin elaborarea (proiectarea) unui algoritm intelegem intreaga activitate depusa de la enuntarea problemei pana la realizarea algoritmului corespunzator rezolvarii acestei probleme.

In elaborarea unui algoritm deosebim urmatoarele activitati importante:

- specificarea problemei;

- descrierea metodei alese pentru rezolvarea problemei;

- proiectarea propriu-zisa. Ea consta in descompunerea problemei in subprobleme, obtinerea algoritmului principal si a tuturor subalgoritmilor apelati, conform metodelor prezentate in sectiunile urmatoare. Ea se termina cu descrierea algoritmului principal si a subalgoritmilor mentionati, dar si cu precizarea denumirilor si semnificatiilor variabilelor folosite;

- verificarea algoritmului obtinut.

2 Proiectarea ascendenta si proiectarea descendenta

Exista doua metode generale de proiectare a algoritmilor, a caror denumire provine din modul de abordare a rezolvarii problemelor: metoda descendenta si metoda ascendenta. Proiectarea descendenta (top-down) porneste de la problema de rezolvat, pe care o descompune in parti rezolvabile separat. De obicei aceste parti sunt subprobleme independente, care la randul lor pot fi descompuse in subprobleme. La prima descompunere accentul trebuie pus pe algoritmul (modulul) principal nu asupra subproblemelor. La acest nivel nu ne intereseaza amanunte legate de rezolvarea subproblemelor, presupunem ca le stim rezolva, eventual ca avem deja scrisi subalgoritmi pentru rezolvarea lor. Urmeaza sa consideram pe rand fiecare subproblema in parte si sa proiectam (in acelasi mod) un subalgoritm pentru rezolvarea ei. In final, se va descrie subalgoritmul de rezolvare al fiecarei subprobleme, dar si interactiunile dintre acesti subalgoritmi si ordinea in care ei sunt folositi.

Notiunea de modul va fi definita in sectiunea urmatoare. Deocamdata intelegem prin modul orice subalgoritm sau algoritmul principal. Legatura dintre module se prezinta cel mai bine sub forma unei diagrame numita arbore de programare. Fiecarui modul ii corespunde in arborele de programare un nod, ai carui descendenti sunt toate modulele apelate direct. Nodul corespunzator algoritmului principal este chiar nodul radacina.

Astfel, in arborele de programare din fig.1.1 exista un algoritm principal (modulul PRINC), care apeleaza trei subalgoritmi (modulele CITDATE, CALCULE si TIPREZ). La randul sau, modulul CALCULE apeleaza trei subalgoritmi (modulele M1, M2 si M3).

Fig.1.1. Arbore de programare

+---------+

| PRINC |

+---------+

+-------+ | +-------+

| | |

+-------+ +-------+ +-------+

|CITDATE| |CALCULE| |TIPREZ |

+-------+ +-------+ +-------+

+------+ | +---+

+----+ +----+ +----+

| M1 | | M2 | | M3 |

+----+ +----+ +----+

In multe carti metoda top-down este intalnita si sub denumirea stepwise-refinement, adica rafinare in pasi succesivi. Este vorba de un proces de detaliere pas cu pas a specificatiei, denumit proiectare descendenta. Algoritmul apare in diferite versiuni succesive, fiecare fiind o detaliere a versiunii precedente.

Scopul urmarit este acelasi: concentrarea atentiei asupra partilor importante ale momentului si amanarea detaliilor pentru mai tarziu. Daca ar fi necesar sa le deosebim am spune ca metoda top-down se refera la nivelul macro iar metoda rafinarii succesive la nivel micro. La nivel macro se doreste descompunerea unei probleme complexe in subprobleme. La nivel micro se doreste obtinerea unui modul in versiune finala. Intr-o versiune intermediara pot fi prezente numai partile importante ale acestuia, urmand sa se revina asupra detaliilor in versiunile urmatoare (asa cum s-a aratat in sectiunea 1.5), dupa ce aspectele importante au fost rezolvate.

Avantajele proiectarii top-down (cunoscuta si sub denumirea 'Divide et impera') sunt multiple. Avantajul principal consta in faptul ca ea permite programatorului sa reduca complexitatea problemei, subproblemele in care a fost descompusa fiind mai simple, si sa amane detaliile pentru mai tarziu. In momentul in care descompunem problema in subprobleme nu ne gandim cum se vor rezolva subproblemele ci care sunt ele si conexiunile dintre ele.

Proiectarea descendenta permite lucrul in echipe mari. Prin descompunerea problemei in mai multe subprobleme, fiecare subproblema poate fi data spre rezolvare unei subechipe. Fiecare subechipa nu cunoaste decat subproblema pe care trebuie sa o rezolve.

Metoda 'Divide et Impera' poate fi folosita nu numai la impartirea problemei in subprobleme ci si la impartirea datelor in grupe mai mici de date. Un astfel de procedeu este folosit de subalgoritmul Quicksort, care va fi prezentat in sectiunea 7.

Metoda ascendenta (bottom-up) porneste de la propozitiile limbajului si de la subalgoritmi existenti, pe care ii asambleaza in alti subalgoritmi pentru a ajunge in final la algoritmul dorit. Cu alte cuvinte, in cazul metodei ascendente va fi scris mai intai subalgoritmul apelat si apoi cel care apeleaza. Ca rezultat al proiectarii ascendente se ajunge la o multime de subalgoritmi care se apeleaza intre ei. Este important sa se cunoasca care subalgoritm apeleaza pe care, lucru redat printr-o diagrama de structura, ca si in cazul programarii descendente.

Aceasta metoda are marele dezavantaj ca erorile de integrare vor fi detectate tarziu, abia in faza de integrare. Se poate ajunge abia acum la concluzia ca unii subalgoritmi, desi corecti, nu sunt utili.

De cele mai multe ori nu se practica o proiectare ascendenta sau descendenta pura ci o combinare a lor, o proiectare mixta.

3 Proiectarea modulara

Prin proiectare (programare) modulara intelegem metoda de proiectare (programare) a unui algoritm pentru rezolvarea unei probleme prin folosirea modulelor.

Dar ce este un modul? Modulul este considerat o unitate structurala de sine statatoare, fie program, fie subprogram, fie o unitate de program. Un modul poate contine sau poate fi continut intr-alt modul. Un modul poate fi format din mai multe submodule. Astfel, in Pseudocod fiecare subalgoritm si algoritmul principal sunt considerate module. In limbajele de programare cu structura de bloc UNIT-urile pot fi considerate module. La compilarea separata un grup de subprograme compilate deodata constituie un modul, dar acest modul poate fi considerat ca o multime de submodule din care este compus.

Este insa important ca fiecare modul sa-si aiba rolul sau bine precizat, sa realizeze o functie in cadrul intregului program. El apare in mod natural in descompunerea top-down.

Indiferent ca privim modulul ca un singur subalgoritm, un grup de subalgoritmi, sau un algoritm de sine statator ce apeleaza alti subalgoritmi, consideram modulele relativ independente, dar cu posibilitati de comunicare intre ele. Astfel, un modul nu trebuie sa fie influentat de maniera in care se lucreaza in interiorul altui modul. Orice modificare ulterioara in structura unui program, daca functia pe care o realizeaza un modul M inca este necesara, acest modul trebuie sa fie util si folosit in continuare fara modificari.

Rezulta ca programarea modulara se bazeaza pe descompunerea problemei in subprobleme si proiectarea si programarea separata a subalgoritmilor corespunzatori. De altfel, consideram ca intr-o programare serioasa nu se poate ajunge la implementare fara a avea in prealabil algoritmii descrisi intr-un limbaj de descriere (la noi Pseudocod). Deci programarea modulara se refera in primul rand la proiectarea modulara a algoritmilor si apoi la traducerea lor in limbajul de programare ales, tinand seama de specificul acestui limbaj. Programarea modulara este strans legata de programarea ascendenta si de programarea descendenta, ambele presupunand folosirea subalgoritmilor pentru toate subproblemele intalnite.

Avantajele programarii modulare sunt multiple. Mentionam in cele ce urmeaza cateva dintre ele. Descompunerea unei probleme complexe in subprobleme este un mijloc convenabil si eficient de a reduce complexitatea (Principiul Divide et impera actioneaza si in programare). Este evident ca probabilitatea aparitiei erorilor in conceperea unui program creste cu marimea programului, lucru confirmat si de experienta practica. De asemenea, rezolvand o problema mai simpla, testarea unui modul se poate face mult mai usor decat testarea intregului algoritm.

Apoi, faptul ca trebuiesc proiectate mai multe subprograme pentru subproblemele intalnite, permite munca mai multor programatori. S-a ajuns astfel la munca in echipa, modalitate prin care se ajunge la scurtarea termenului de realizare a produsului program.

Modulele se pot refolosi ori de cate ori avem nevoie de ele. Astfel, s-a ajuns la compilarea separata a subprogramelor si la pastrarea subprogramelor obtinute in biblioteci de subprograme, de unde ele se pot refolosi la nevoie. Sunt cunoscute astazi multe astfel de biblioteci de subprograme. Reutilizabilitatea acestor subprograme este o proprietate foarte importanta in activitatea de programare. Ea duce la marirea productivitatii in programare, dar si la cresterea sigurantei in realizarea unui produs corect.

Uneori, in timpul proiectarii algoritmului sau a implementarii lui, se ajunge la concluzia ca proiectarea a fost incompleta sau ca unele module sunt ineficiente. si in aceasta situatie programarea modulara este avantajoasa, ea permitand inlocuirea modulului in cauza cu altul mai performant.

Una din activitatile importante in realizarea unui program este verificarea corectitudinii acestuia. Experienta a aratat ca modulele se pot verifica cu atat mai usor cu cat sunt mai mici. Abilitatea omului de a intelege si analiza corectitudinea unui subalgoritm este mult mai mare pentru texte scurte. In unele carti chiar se recomanda a nu se folosi subalgoritmi mai mari decat 50 de propozitii. Sigur ca o astfel de limita nu exista, dar se recomanda descompunerea unui subalgoritm in alti subalgoritmi oricand acest lucru este posibil in mod natural, deci acesti noi subalgoritmi rezolva subprobleme de sine statatoare, sau realizeaza functii bine definite.

4 Programarea structurata

Programarea structurata este un stil de programare aparut in urma experientei primilor ani de activitate. Ea cere respectarea unei discipline de programare si folosirea riguroasa a catorva structuri de calcul. Ca rezultat se va ajunge la un algoritm usor de urmarit, clar si corect.

Termenul programare, folosit in titlul acestei sectiuni si consacrat in literatura de specialitate, este folosit aici in sens larg si nu este identic cu cel de programare propriu-zisa. Este vorba de intreaga activitate depusa pentru obtinerea unui program, deci atat proiectarea algoritmului cat si traducerea acestuia in limbajul de programare ales.

Bohm si Jacopini au demonstrat ca orice algoritm poate fi compus din numai trei structuri de calcul:

- structura secventiala;

- structura alternativa;

- structura repetitiva.

Fiecare din aceste structuri, ca parte dintr-o schema logica, are o singura intrare si o singura iesire si sunt prezentate in figura 1.1.

Knuth considera programarea structurata ca fiind un mijloc de a face produsele program mai usor de citit. De asemenea, programarea structurata este definita ca fiind programarea in care abordarea este top-down, organizarea muncii este facuta pe principiul echipei programatorului sef, iar in proiectarea algoritmilor se folosesc cele trei structuri de calcul definite de Bohm-Jacopini.

Alti autori considera programarea structurata nu ca o simpla metoda de programare ci ansamblul tuturor metodelor de programare cunoscute. Dar programarea modulara, programarea top-down, sau bottom-up (ascendenta sau descendenta) au aparut inaintea programarii structurate. Important este faptul ca programarea structurata presupune o disciplina in activitatea de programare.

Consideram ca programarea structurata se poate intalni:

- la nivel micro, privind elaborarea unui subalgoritm;

- la nivel macro, privind dezvoltarea intregului produs informatic (algoritm).

La nivel micro programarea structurata este cea in care autorul este atent la structura fiecarui modul in parte, cerand claritate si ordine in scriere si respectarea structurilor de calcul definite mai sus.

La nivel macro programarea structurata presupune practicarea proiectarii top-down, a programarii modulare si a celorlalte metode de programare, cerand ordine in intreaga activitate si existenta unei structuri clare a intregii aplicatii, precizata prin diagrama de structura a aplicatiei.

In acest scop am definit limbajul Pseudocod, care are structurile de calcul mentionate. Schemele logice obtinute dintr-o descriere in Pseudocod a unui algoritm, conform semanticii propozitiilor Pseudocod, se numesc D-scheme (de la Dijkstra) sau scheme logice structurate.

Referitor la faza de codificare intr-un limbaj de programare a unui algoritm obtinut in urma unei proiectari structurate se cere respectarea structurii acestui algoritm, ceea ce este posibil si usor de realizat daca limbajul de programare are structurile de calcul respective. In acest caz programul va fi o copie fidela a algoritmului proiectat.