...rea denumirilor si semnificatiilor variabilelor folosite - verificarea algoritmului obtinut.3.2 Proiectarea ascendenta si proiectarea descendentaExista 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-don 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.3.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.3.1.1. Arbore de programare --------- PRINC --------- ------- ------- ------- ------- ------- CITDATE CALCULE TIPREZ ------- ------- ------- ------ --- ---- ---- ---- M1 M2 M3 ---- ---- ---- In multe carti metoda top-don este intalnita si sub denumirea stepise-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-don 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-don 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.3.Met...
Download