Metode si strategii deare a algoritmilor (alias tehnici de programare)

In rezolvarea sa cu ajutorul calculatorului orice problema trece prin trei etape obligatorii: Analiza problemei, Proiectarea algoritmului de solutionare si Implementarea algoritmului intr-un program pe calculator. In ultima etapa, sub acelasi nume, au fost incluse in plus doua subetape cunoscute sub numele de Testarea si Intretinerea programului. Aceste subetape nu lipsesc din “ciclul de viata” a oricarui produs-program ce “se respecta” dar , pentru simplificare, in continuare ne vom referi doar la cele trei mari etape..

Daca etapa implementarii algoritmului intr-un program executabil este o etapa exclusiv practica, realizata “in fata calculatorului”, celelalte doua etape au un caracter teoretic pronuntat. In consecinta, primele doua etape sint caracterizate de un anumit grad de abstractizare. Din punct de vedere practic si in ultima instanta criteriul decisiv ce confera succesul rezolvarii problemei este dat de calitatea implementarii propriuzise. Mai precis, succesul solutionarii este dat de performantele programului: utilitate, viteza, fiabilitate, manevrabilitate, lizibilitate, etc. Este imatura si neprofesionala “strategia” programatorilor incepatori care neglijind primele doua etape sar direct la a treia, fugind de analiza si de componenta abstracta a efortului de solutionare. Ei ofera cu totii aceeasi justificare: “Eu nu vreau sa mai pierd vremea cu . , am sa fac programul cum stiu eu. Pina cind nu o sa faca cineva altul mai bun decit al meu, pina atunci . nu am cu cine sta de vorba !”.

Este adevarat ca ultima etapa in rezolvarea unei probleme – implementarea – este intr-adevar decisiva si doveditoare, dar primele doua etape au o importanta capitala. Ele sint singurele ce pot oferi raspunsuri la urmatoarele intrebari dificile: Avem certitudinea ca solutia gasita este corecta ? Avem certitudinea ca problema este complet rezolvata ? Cit de eficienta este solutia gasita ? Cit de departe este solutia aleasa de o solutie optima ?

Sa mentionam in plus ca literatura de specialitate contine un numar impresionant de probleme “capcana” pentru incepatori si nu numai. Ele sint toate inspirate din realitatea imediata dar pentru fiecare dintre ele nu se cunosc solutii eficiente in toata literatura de profil. Exista printre ele chiar unele probleme extrem de dificile pentru care s-a demonstrat riguros ca nu admit solutie cu ajutorul calculatorului. (Mai precis, s-a demonstrat ca ele nu admit solutie prin metode algoritmice, in spiritul tezei Turing-Church). Citi dintre programatorii incepatori n-ar fi surprinsi sa afle ca problema “atit de simpla” (ca enunt) a carei solutionare tocmai au abandonat-o este de fapt o problema dovedita ca fiind intratabila sau chiar insolvabila algoritmic ? Partea proasta a lucrurilor este ca, asa cum ciupercile otravite nu pot fi cu usurinta deosebite de cele comestibile, tot astfel problemele netratabile pot fi cu usurinta confundate cu niste probleme usoare la o privire rapida si lipsita de experienta.

Sa intelegem mai intii care este “cheia” ce conduce la raspunsuri pentru intrebarile de mai sus iar apoi vom trece la prezentarea metodelor clasice de proiectare a solutiilor. Aceste metode de proiectare a algoritmilor-solutie sint cunoscute in literatura de specialitate sub numele de tehnici de programare si sint considerate metode sau instrumente soft eficiente si cu arie larga de actiune.

Daca ar fi sa sintetizam in cite un cuvint efortul asupra caruia se concentreaza fiecare din primele doua etape – analiza si proiectarea – acestea ar fi: corectitudine si eficienta. Etapa de analiza este singura care permite dovedirea cu argumente riguroase a corectitudinii solutiei, iar etapa de proiectare este singura care poate oferi argumente precise in favoarea eficientei solutiei propuse.

In general problemele de informatica au in forma lor initiala sau in enunt o caracteristica pragmatica. Ele sint foarte ancorate in realitatea imediata si aceasta le confera o anumita asemanare. Totusi ele au in forma initiala un grad mare de eterogenitate, diversitate si lipsa de rigoare. Fiecare dintre aceste atribute “negative” este un obstacol major pentru demonstrarea corectitudinii solutiei. Rolul esential al etapei de analiza este deci acela de a transfera problema “de pe nisipurile miscatoare” ale realitatii imediate de unde ea provine intr-un plan abstract, adica de a o modela. Acest “univers paralel” este dotat cu mai multa rigoare si disciplina interna, avind legi precise, si poate oferi instrumentele logice si formale necesare pentru demonstrarea riguroasa a corectitudinii solutiei problemei.

Planul abstract in care sint “transportate” toate problemele este planul sau universul obiectelor matematice. Acest univers al matematicii este unanim acceptat (de ce ?!) iar corespondentul problemei in acest plan va fi modelul matematic abstract asociat problemei. Demonstrarea corectitudinii proprietatilor ce leaga obiectele universului matematic a fost si este sarcina matematicienilor. Celui ce analizeaza problema din punct de vedere informatic ii revine sarcina (nu tocmai usoara) de a dovedi printr-o demonstratie constructiva ca exista o corespondenta precisa (bijectiva) intre partile componente ale problemei reale, “dezasamblata” in timpul analizei, si partile componente ale modelului abstract asociat. Odata descoperita, formulata precis si dovedita, aceasta “perfecta oglindire” a problemei reale in planul obiectelor matematice ofera certitudinea ca toate proprietatile si legaturile ce exista intre subansamblele modelului abstract se vor regasii precis (prin reflectare) intre partile interne ale problemei reale, si invers. Atunci, solutiei abstracte descoperita cu ajutorul modelului matematic abstract ii va corespunde o solutie reala concretizata printr-un algoritm ce poate fi implementat intr-un program executabil.

Aceasta este calea generala de rezolvare a problemelor si orice poate verifica. Ca si exercitiu, sa se demonstreze corectitudinea (sa se aduca argumente precise, clare si convingatoare in favoarea corectitudinii) metodei de extragere a radicalului invatata inca din scoala primara sau a algoritmului lui Euclid de determinare a celui mai mare divizor comun a doua numere prin impartiri intregi repetate. Argumentele elevilor de forma: “Este corect pentru ca asa ne-a invatat doamna profesoara!” sau “Este corect pentru ca asa face toata lumea !” sint “normale” atit timp cit nu li se ofera o argumentatie matematica riguroasa.

Ideea centrala a etapei a doua – proiectarea uni algoritm de solutionare eficient poate fi formulata astfel: din studiul proprietatilor si limitelor modelului matematic abstract asociat problemei se deduc limitele inferioare ale complexitatii minimale (“efortului minimal obligatoriu”) inerente oricarui algoritm ce va solutiona problema in cauza. Complexitatea interna a modelului abstract si complexitatea solutiei abstracte se va reflecta imediat asupra complexitatii reale a algoritmului, adica asupra eficientei, de solutionare a problemei. Acest fapt permite prognosticarea inca din aceasta faza – faza de proiectare a algoritmului de solutionare – a eficientei practice, masurabila ca durata de executie, a programului.

Proiect: Fisa de lucru - operatii cu numere intregi Referat: Jocuri didactice matematica - lantul buclucas

Aceasta corespondenta exacta intre complexitatea modelului abstract si complexitatea algoritmului de solutionare ofera cheia unor demonstratii riguroase a imposibilitatii existentei solutiei prin metode algoritmice pentru o lista intreaga de probleme (cum ar fi de exemplu Problema a 10-a a lui Hilbert, formulata inca din 1900).

Detailind cele prezentate deja, vom construi in continuare cadrul teoretic general pentru intelegerea strategiilor de proiectare a algoritmilor.

Cresterea impresionanta a puterii de calcul a calculatoarelor i-a “obligat” pe informaticienii ultimilor treizeci de ani sa nu se mai eschiveze de la abordarea problemelor dificile cu caracter algoritmic din diverse domenii care au intrat in atentia matematicienilor inca de la inceputul acestui secol. De altfel, astfel de probleme cu solutii algoritmice nu constituiau neaparat o noutate pentru matematicienii inceputului de secolul. Inca de pe vremea lui Newton matematicienii si-au pus, de exemplu, problema descoperirii unor metode precise (adica algoritmi!) de determinare in pasi de aproximare succesiva a solutiei unei ecuatii ce nu poate fi rezolvata prin radicali. Dar “boom-ul” dezvoltarii tehnicii de calcul din a doua jumatate a secolului a creat posibilitatea abordarii unor probleme cheie pentru anumite domenii strategice (de exemplu, controlul si dirijarea satelitilor pe orbita, probleme de planificare sau optimizare in economie, etc.) care se reduc in fapt la solutionarea eficienta a unor probleme de optimizare matematica prin metode iterative (algoritmi).

Spre deosebire de aceste probleme a caror succes in solutionare a fost total si cu consecintele ce se vad, exista insa o serie de probleme dificile inspirate din realitate care se cer imperios rezolvate eficient cu ajutorul calculatorului.

Principala caracteristica a acestora este ca, datorita generalitatii lor sau datorita dificultatii “ascunse”, in literatura de specialitate nu exista metode iterative eficiente de rezolvare a lor si nu se stie daca ele admit astfel de solutii. Singurul fapt ce poate fi stabilit dinainte in cazul solutionarii unor astfel de probleme este “spatiul” in care solutia trebuie cautata. Ceea ce trebuie atunci construita este o strategie corecta si cit mai generala de cautare a solutiei (solutiilor) in acel spatiu de cautare a solutiilor.

Exemplu concret: exista o clasa intreaga de probleme ce cer implicit sa se genereze toate obiectele unei multimi (cum ar fi problema generarii tuturor permutarilor unei multimi cu n elemente). In acest caz este cunoscuta dinainte proprietatea ce trebuie sa o indeplineasca fiecare solutie ca sa fie un obiect al spatiului de cautare a solutiilor. Efortul de solutionare va fi redus atunci la aflarea, cautarea sau generarea pe baza proprietatii respective a tuturor obiectelor posibile, fara insa a lasa vreunul pe dinafara.

Modelul matematic abstract cel mai general care permite modelarea acestui tip de probleme este graful. Un graf este un obiect matematic riguros care, simplificat, poate fi privit ca fiind o diagrama formata din noduri unite prin sageti (muchii). De exemplu, orice harta feroviara sau rutiera poate fi privita ca un graf cu multimea nodurilor formata din localitati iar multimea muchiilor formata din rutele de transport directe dintre localitatile respective. Graful permite descrierea legaturilor si a relatiilor ce exista intre diferite obiecte abstracte reprezentate prin noduri. Experienta arata ca acest model matematic abstract este cel mai general si cel mai potrivit pentru descrierea unui spatiu de cautare a solutiilor unei probleme. In cazul spatiului de cautare, nodurile sint solutiile posibile (ipotetice). Doua noduri in graf vor fi unite prin sageti (muchii) daca cele doua solutii posibile au in comun o aceeasi proprietate. Muchiile grafului sint “puntile” ce vor permite algoritmului trecerea de la un nod la altul, de la o solutie ipotetica la alta, in timpul procesului de cautare a solutiei (sau a tuturor solutiilor). Rezulta ca strategiile cele mai generale de cautare a solutiei (solutiilor) pe modelul abstract asociat problemei sint reductibile la metodele generale de traversare a unui graf.

Ordinea de traversare a grafului determina precis arborele de traversare a grafului. Acest arbore este de fapt un subgraf particular al grafului initial, avind acelasi numar de noduri si ca radacina virful initial de pornire. Cele doua metode clasice de traversare a unui graf (cautare intr-un graf) poarta in literatura de specialitate numele: BreathFirstSearch (BFS) si DepthFirstSearch (DFS), respectiv Traversarea in latime (sau traversarea pe nivele) si Traversarea in adincime (traversarea “labirintica”) a grafului. Ambele metode stau la baza celei mai cunoscute strategii de proiectare a algoritmilor (impropriu denumita tehnica de programare): BackTracking respectiv cautare (traversare) in spatiul de cautare a solutiilor (a grafului) cu revenire pe “urma” lasata.

Iata un exemplu de graf (7 noduri si 10 arce-sageti) si ordinea sa de traversare prin cele doua metode:

Ordinea de parcurgere a celor 7 virfuri ale grafului, tinind cont si de sensul dat de sageti, este in cazul DFS (in adincime): 1,2,4,5,6,3,7 asa cum se vede din arborele parcurgerii in adincime. Din fiecare nod se continua cu nodul (nevizitat inca) dat de prima alegere posibila: de exemplu, din 4 se continua cu 5 (ales in favoarea lui 7). Se poate observa cum din nodul 3, nemaiexistind continuare, are loc o revenire pe “pista lasata” pina in nodul 6 de unde se continua parcurgerea in adincime cu prima alegere posibila. In cazul BFS (in latime) ordinea de traversare este: 1,2,3,4,5,7,6 asa cum se poate vedea in arborele parcurgerii in latime. In aceasta situatie, dintr-un nod sint vizitati toti vecinii (nevizitati inca), iar apoi se face repeta acelasi lucru pentru fiecare nod vecin, in ordinea vizitarii. Se observa cum nodul 7 este vizitat inaintea nodului 6, fiind vecin cu nodul 4. (De fapt, aceasta se explica prin faptul ca distanta de la 1 la 7 este mai mica cu o unitate decit distanta de la 1 la 6.) Putem spune ca in cazul traversarii in latime ordinea de traversare este data de departarea nodurilor fata de nodul de start.

Iata cum arata procedura generala DepthFirstSearch (DFS) de traversare a unui graf descrisa in pseudo-cod in varianta recursiva:

Procedura DFS(v:nod);

Viziteaza v;

Marcheaza v; // v devine un nod vizitat //

Cit timp (exista w nemarcat nod adiacent lui v) executa DFS(w);

Sa nu uitam ca aceasta procedura poate fi privita ca “scheletul” pe care se construieste orice procedura backtracking recursiva