Reprezentarea algoritmilor

Am vazut ca un algoritm reprezinta un sistem de reguli pentru rezolvarea unei clase de probleme. Daca dorim sa rezolvam cu calculatorul o problema din clasa respectiva, este necesar sa descriem mai intai algoritmul corespunzator. Doar pentru probleme suficient de simple si, desigur, in urma dobandirii unei experiente in programare, ne putem dispensa de aceasta etapa. In procesul de asimilare a primelor cunostinte de programare si pentru intelegerea unor algoritmi fundamentali este bine sa utilizam descrieri explicite ale algoritmilor.

Formele de reprezentare ale unui algoritm sunt:

in cuvinte, pe pasi;

schema logica;

pseudocod;

alte forme.

1. Scheme logice

Schemele, departe de a fi utilizate numai in informatica, sunt un instrument de lucru general, utilizat in chimie, fizica, inginerie, stiinte socio-umane, administratie etc. In general, schemele sunt folosite pentru a arata dinamica unui proces, de la initierea pana la incheierea sa. Structura schemelor poate fi conceputa diferit in domenii diferite, dar in mod obisnuit sunt constituite din blocuri (cu forme diverse) conectate prin linii. Ordinea de parcurgere a blocurilor, indicata de obicei prin sageti, trebuie sa rezulte clar din schema. Daca este loc, procesul reprezentat este descris in interiorul blocului. Daca nu, se folosesc simboluri explicate in afara schemei. O schema este un desen care permite intelegerea intregului proces prin urmarirea diferitelor aspecte aparute si intelegerea ordinii si relatiilor intre aspecte.

La sfarsitul anilor '40, cand s-a conturat conceptul programului memorat, a devenit clar ca scrierea programelor complexe, de mii de instructiuni, nu putea fi realizata fara o metoda de planificare si urmarire a etapelor intermediare. Primul care a folosit metoda de descriere logica a etapelor unui program a fost John von Neumann. El a folosit o schema logica pentru a evidentia succesiunea transformarilor datelor de intrare pana cand se obtin datele de iesire. Toti programatorii au preluat acest mod de lucru, preliminar scrierii unui program. American National Standard Institute (ANSI) a publicat un standard al blocurilor folosite in informatica. Cele uzuale sunt:

Exemple de folosire a acestor blocuri:

Variabila x primeste valoarea b² - 4ac.

Se preiau de la dispozitivul de intrare valorile variabilelor a, b si c.

Daca i este mai mic sau egal cu n, atunci se trece la executia blocului aflat pe sageata marcata cu 'da'. Altfel, se executa blocul aflat pe sageata marcata cu 'nu'. Acest bloc are doua puncte de iesire.

Se calculeaza valoarea functiei f in 2.

Inceputul si sfarsitul schemei.

Aceste blocuri apar o singura data intr-o schema.

Conectori pe pagina.

Conectori intre pagini.

Pentru a scrie o schema logica, programatorul trebuie sa gandeasca in pasi elementari rezolvarea problemei. De obicei, se incepe cu citirea datelor de intrare. Apoi urmeaza partea de calcule si de decizii care se iau in functie de rezultatele unor comparatii. Incheierea o constituie scrierea datelor de iesire. Fiecare dintre acesti pasi elementari este redat de un bloc standardizat din tabelul de mai sus. In fiecare bloc se plaseaza o descriere a operatiei executate.

Alaturat este prezentata o schema care citeste doua variabile reale a si b si scrie variabila x, calculata astfel: x = -b/a daca a este nenul, sau x = b-7 daca a=0.

2. Structuri de control

Problema care a aparut era ca fiecare programator avea stilul sau de lucru si folosea propriul set de reguli pentru descrierea logica a programului. Fiecare folosea propria structura (grup de blocuri) pentru a descrie etape din program. De aceea citirea, intelegerea si modificarea structurilor era dificila. Era necesara o uniformizare a metodelor de scriere a unei scheme. Astfel, 'arta' programarii trebuia transformata in 'stiinta'. In anul 1964, Corrado Böhm si Giuseppe Iacopini au prezentat o lucrare la Congresul International de Lingvistica Algebrica si Teoria Automatelor din Israel. In aceasta lucrare ei demonstreaza ca orice schema logica poate fi scrisa cu ajutorul a numai trei structuri, numite structuri de control de baza. Acestea sunt: structura secventiala, structura alternativa binara si structura repetitiva conditionata anterior.

Structura secventiala

Evenimentele descrise in blocuri se executa unul

dupa altul, in ordinea specificata.

Structura alternativa binara

In blocul de decizie este testata conditia inscrisa. Daca este adevarata, atunci se executa operatia descrisa in blocul de pe ramura marcata cu 'da'. Daca nu, atunci se executa operatia descrisa in blocul de pe ramura marcata cu 'nu'.

Structura repetitiva conditionata anterior

Este cea care permite ciclarea in programe. Se testeaza conditia inscrisa. Daca este adevarata, atunci se executa procesarea descrisa. Din nou se testeaza conditia. Cat timp conditia este adevarata, se reia procesarea. Daca insa conditia este falsa, atunci se incheie aceasta structura.

Observam ca fiecare din cele trei structuri descrise mai sus are un singur punct de intrare si un singur punct de iesire.

Programarea structurata este metoda de programare care foloseste numai aceste trei structuri. Acum exista produse software care ajuta desenarea schemelor logice. Procesorul de texte Word (sub Windows) are predefinite blocurile standard ale schemelor. Flowchart Maker, ajuns la versiunea 1.3, este un produs pentru Macintosh, destinat exclusiv desenarii schemelor.

In afara structurilor de control de baza, mai exista structuri de control auxiliare: structura de control alternativa generalizata, structura de control conditionata posterior si structura repetitiva cu contor. Aceste structuri au fost admise datorita frecventei lor utilizari, dar se arata ca pot fi simulate cu ajutorul structurilor de baza.

Structura de control alternativa generalizata

Alegerea urmatoarei prelucrari se face in functie de valoarea unei expresii numite selector. Daca selector este egal cu v1, atunci se executa 'Eveniment 1'; daca are valoarea v2, se executa 'Eveniment 2' si asa mai departe.

. . .

Structura de control conditionata posterior

Se executa 'Eveniment'. Se testeaza conditia inscrisa. Daca este falsa, atunci se reia procesarea descrisa prin 'Eveniment'. Se testeaza conditia din nou. Cat timp conditia este falsa, se reia procesarea. Daca insa conditia este adevarata, atunci se incheie aceasta structura.

Structura repetitiva cu contor

Este o structura pentru care se cunoaste numarul de repetitii. Contorul repetitiei este variabila intreaga v. Contorul primeste valoarea initiala v_i. Se testeaza daca v este mai mic sau egal cu v_f (valoarea finala). Daca da, atunci se executa 'Eveniment', se creste v cu pasul p si se reia testul. Se paraseste aceasta structura daca v este mai mare decat v_f.

3. Modularizare

Pe masura ce programele deveneau tot mai lungi si mai complexe, programatorii au inteles ca era tot mai greu ca de la inceputul scrierii sa fie cunoscute toate prelucrarile ce trebuiau efectuate. S-a conturat astfel conceptul de proiectare 'top-down', prin care se impartea un program in mai multe parti care indeplineau fiecare o anumita functiune. Fiecare din aceste parti erau scrise de programatori diferiti, care urmareau rezolvarea unei anumite probleme. La nivel central, trebuia coordonat ansamblul, adica trebuia urmarita compatibilitatea transferului de date intre parti. Prima rezolvare a constat in aparitia subprogramelor. Acestea sunt apelate din programul principal pentru a executa o aceeasi operatie, de cate ori este nevoie. De exemplu, se poate scrie un subprogram care afla daca un numar este prim sau nu si acest subprogram se apeleaza la nevoie din programul principal. Spre sfarsitul anilor '60, s-a introdus conceptul de modularizare a programelor, prin care efectiv se descompunea un program in parti mici (module), cu o logica simpla si usor de urmarit.

Acest procedeu este asemanator celui descris in continuare. In principiu, se urmareste descompunerea operatiilor ce trebuie executate pana la nivel elementar, cand se transforma direct in instructiuni acceptate de limbajul de programare.

Exemplu. Sa presupunem ca avem un robot inzestrat cu brate, picioare si ochi, pe care dorim sa-l programam astfel incat sa pregateasca o cana cu ceai.

Deci, sarcina principala (de nivelul 1) este:

	1. Fa-mi o cana cu ceai

1. Fa-mi o cana cu ceai

Deocamdata robotul nu poate indeplini cerinta, deoarece el doar recunoaste obiectele si indeplineste comenzi simple, de genul: 'pune ceainicul pe plita'. De aceea, cerinta noastra va fi descompusa in comenzi mai simple, de nivelul 2, pe care le punem in ordine:

					1. 3. Pune apa in cana
	Fierbe apa

 

1. 2. Pune ceai in cana

 

Fiecare din aceste cerinte este greu de indeplinit, astfel incat trebuie descompusa, la randul ei, in altele de nivel inferior (nivelul 3).

Majoritatea programelor contin activitati de introducere, prelucrare de date si extragere de rezultate. Proiectand programul si formand module, va deveni, in curand, evident pentru fiecare modul, ce functie indeplineste in introducere, prelucrare sau extragere.

Iata cum arata intreaga diagrama de tip arbore pentru nivelul 3:

	1. Fa-mi o cana cu ceai