ALGORITMI SI STRUCTURI DE DATE

Vom incepe prin a discuta cativa termeni generali legati de predarea Informaticii in Liceu - probabil - cunoscuti. Pe parcurs, din motive de spatiu, vom apela si la reprezentarea unor algoritmi in limbaj real (PASCAL sau C/C++, obiecte care vor fi studiate ulterior), nu numai in pseudocod. Speram ca anumite probleme de intelegere sa fie inlaturate prin discutii individuale.

1. Notiuni fundamentale in Informatica

Notiunile, temele, domeniile abordate in studiul disciplinelor de informatica sunt practic direct stabilite de obiectivele cadru si de referinta. Ele nu pot constitui obiect de polemici dar modalitatile de abordare ale lor constituie cel mai prolific motiv de disputa metodica si stiintifica.

Asa cum nu putem aborda nici un domeniu al matematicii (de exemplu), fara cunoasterea unor notiuni fundamentale, cum ar fi cele legate de teoria multimilor, teoria numerelor, etc., nici in Informatica nu pot lipsi notiunile fundamentale specifice disciplinei. Una dintre notiunile fundamentale este aceea de algoritm. Prin algoritm (imperativ!) se intelege ansamblul de transformari (metoda) ce se aplica asupra unui set de date de intrare si care determina obtinerea intr-un timp finit si dupa o succesiune precisa si finita de pasi, a unui set de date de iesire. Matematic (logic) vorbind, aceasta nu este o definitie, ci o descriere a unui concept "de baza". Spre deosebire de matematica clasica (in care notiunile primordiale nu sunt - practic - definite ci doar descrise si sunt - relativ - simple: multime, punct, plan, etc.), notiunile informatice "corespondente" sunt mult mai complicate (inafara de algoritm, mai amintim : baza de date, program concurent, etc.).

Introducerea conceptuala a notiunii de algoritm si a reprezentarii acestuia se bazeaza, initial, pe cunostintele de matematica ale elevilor. Un accent deosebit trebuie pus pe caracteristicile algoritmilor: generalitatea (universalitatea), determinismul si finitudinea.

Insa, introducerea oricarei notiuni (chiar ne-fundamentale), trebuie sa urmeze urmatoarele etape:

Etapa de elaborare si motivatie (initiala). Fundamentata si eficient integrata intr-un sistem, o notiune "cere" noi domenii de aplicare. Prin urmare atrage dupa sine (motiveaza) introducerea unor noi notiuni sau furnizarea unor noi rezultate, evident pana cand aria de extindere se ingusteaza.

Etapa de formare a notiunii. Ilustrata prin exemple, argumentata teoretic si "demonstrata" matematic, o notiune se constituie ca un util si puternic mijloc de "productie" pentru domeniul pentru care a fost elaborata. Ramane doar sa-l "exploatam" adecvat. Didactic, acest aspect cuprinde argumentarea stiintifica a notiunii introduse si reliefarea unor noi, posibile domenii de aplicabilitate.

Etapa de consolidare, prin operare cu notiunea. O notiune poate fi considerata asimilata daca ea devine si instrument de dobandire a unor cunostinte si daca elevii pot opera cu aceasta notiune in situatii noi.

De exemplu, in privinta reprezentarii algoritmilor, utilizarea schemelor logice poate fi considerata etapa initiala. Reprezentarea algoritmilor cu ajutorul pseudocodului sau altor tipuri de diagrame a urmat in mod natural. Nici un efort metodic nu este prea mare pentru a avea o reusita deplina in intelegerea si abordarea notiunilor de algoritm si de reprezentare a acesteia. Notiunile ulterior introduse vor apare in mod firesc, capatand caracteristicile unor inlantuiri cauzale.

De aceea este necesar ca in mintea elevilor sa existe o "ordonare" a notiunilor, o corelare fireasca a lor, o motivatie, pentru ca numai peste cunostinte bine asimilate se pot asterne in mod eficient cunostinte noi. Elevul trebuie sa inteleaga ca ordinea in care se predau notiunile nu este intamplatoare si ca el trebuie sa faca un efort de asimilare, care va fi rasplatit prin reusite viitoare.

Unele teme de predare pot fi organizate in "spirala" (ceea ce presupune o reintoarcere la acelasi continut, dar pe un nivel superior). Acest mod de planificare corespunde sistemului concentric propriu-zis (concentric calitativ) si sistemului concentric cantitativ (concentric liniar).

Sistemul concentric calitativ desemneaza modul de organizare a cunostintelor in programele de invatamant, manuale si lectii, in asa fel incat notiunile (cunostintele) se insusesc prin reluari, restructurari, reinterpretari, pana la formarea lor completa. In aceasta maniera pot fi - de exemplu - abordati algoritmii de sortare.

Sistemul concentric cantitativ este modul de organizare a cunostintelor in programele scolare, manuale si lectii, constand in reluarea adaugita si detaliata a materiei parcurse anterior, reluare reclamata nu atat de dificultatea intelegerii notiunilor, cat mai ales de nevoia largirii cunostintelor in succesiunea claselor si treptelor scolare.

Exemplu (Algoritmul lui Euclid pentru determinarea celui mai mare divizor comun a doua numere naturale nenule). Metoda prezentata va folosi ideea lui E.W. Dijkstra (scaderi repetate).

Observatie. Alte exemple care pot fi date sunt:

calculul sumei a n numere naturale;

produsul a doua numere naturale prin adunari repetate.

Nu recomandam prezentarea algoritmului lui Euclid sub forma impartirilor repetate (Algebra clasa a-X-a).

Intuitiv vorbind, pentru a parcurge drumul de la realitatea de modelat la implementarea pe calculator, mai trebuie intelese macar la acest nivel descriptiv si alte notiuni, cum ar fi cele de problema, complexitate, corectitudine / verificare, etc.

O problema este un concept caracterizat prin enunt, multime de informatii de intrare (instante ale problemei), multime de informatii de iesire (raspunsuri ale problemei). Ca urmare, rezolvarea unei probleme inseamna ca pentru fiecare instanta trebuie sa se furnizeze (intr-un timp finit) un anumit raspuns. Daca acest raspuns este doar de tipul DA sau NU, atunci avem de-a face cu o problema de decizie.

Algoritmul A rezolva problema P daca avand la intrare orice instanta a problemei, acesta se termina avand ca rezultat un element din multimea de raspuns.

Exista probleme semirezolvabile. Diferenta fata de problemele rezolvabile este aceea ca algoritmul care le rezolva poate sa nu se termine pentru fiecare instanta. Exista de asemenea si probleme nerezolvabile (nedecidabile), cu alte cuvinte probleme pentru care nu exista algoritmi care sa le rezolve. In limbajul informatic curent a intrat si termenul de problema netratabila, pentru a desemna o problema rezolvabila, dar intr-un timp practic inaccesibil duratei umane de viata sau cerintelor sociale.

Exemplu

Enunt problema: Sa se calculeze suma primelor zece numere naturale.

Instante: } - primele zece numere naturale.

Raspuns

Algoritm

Intrare n = 10 - cate numere se considera in aceasta suma.

Iesire suma si 'DA'.

Metoda: Notam cu suma, suma primelor zece numere naturale. Aceasta suma se va calcula iterativ astfel: initial suma va avea valoarea 0, apoi vom aduna succesiv la suma numerele . Pasii (etapele) algoritmului sunt:

Pas 1. n = 10 cate numere adunam;

Pas 2. suma = 0 aici vom pastra rezultatul;

Pas 3. i = 1 primul numar natural nenul;

Pas 4. daca i > n am depasit n = 10 numere?

suma contine rezultatul; scrie suma; scrie 'DA'

altfel

suma = suma + i adun numarul

i = i + 1 trec la urmatorul numar

Execut din nou Pas 4.

sfarsit daca

Analizand algoritmul de mai sus constatam urmatoarele:

a)      In fiecare pas este cunoscut modul de executare a operatiei corespunzatoare cat si pasul (operatia) care urmeaza. Aceasta caracteristica a algoritmilor se numeste determinism.

b)      Oricare ar fi valoarea numarului natural n, suma poate fi calculata, deci secventa de operatii se aplica unei intregi clase de probleme de acelasi gen. Aceasta caracteristica a algoritmilor se numeste generalitate sau universalitate.

c)      Secventa de operatii este finita atat ca descriere cat si ca timp de calcul, in ipoteza ca fiecare operatie se termina intr-un timp finit. Aceasta caracteristica a algoritmilor se numeste finitudine.

Putem demonstra in acest caz ca algoritmul este finit (adica executia sa se termina), ca este corect ( adica valoarea variabilei suma reprezinta exact suma primelor zece numere naturale) si ca este tratabil, timpul sau de executie (numarul de operatii efectiv executate) fiind de aproximativ 2n+3

Dupa cum am mai precizat, pentru ca notiunea de algoritm este data printr-o descriere si nu prin utilizarea unei metode matematice, implicand genul proxim si diferenta specifica, avem mai intai nevoie de metode de reprezentare a algoritmilor.

O prima forma de reprezentare este desigur limbajul obisnuit (natural).

O alta forma de reprezentare a algoritmilor este limbajul pseudocod. Limbajul pseudocod, fata de limbajul natural, este o forma de reprezentare mai exacta, ajungandu-se la nivel de detaliu. Nu exista un limbaj pseudocod "standard" care sa permita reprezentarea algoritmilor, ci in functie de experienta celor care il utilizeaza sau carora li se adreseaza, limbajul pseudocod poate avea forme diferite, influentate chiar pana si de limbajul in care urmeaza a fi implementat algoritmul, daca acest lucru este imediat posibil. Anumite elemente si structuri de reprezentare, nu lipsesc din nici un limbaj pseudocod:

a)      un set standard de operatii elementare:

atribuirea unei valori pentru o variabila;

citirea unei valori pentru o variabila (in fond tot o atribuire);

scrierea sau afisarea valorii unei variabile la dispozitivul de iesire, la care se adauga:

b)      un set de structuri de control:

structura de control secventiala;

structura de control alternativa;

structurile de control repetitive.

Un posibil limbaj pseudocod poate fi descris astfel:

var := expresie (operatia de atribuire a valorii expresiei din dreapta semnului ':= ', variabilei din stanga semnului ':= ');

citeste var (operatia de introducere de la dispozitivul de intrare a unei valori si atribuirea acesteia variabilei var

scrie var (operatia de afisare la dispozitivul de iesire a valorii variabilei).

Consideram ca evaluarea unei expresii, indiferent de tipul acesteia este o operatie de un nivel inferior celui elementar (nivel intern) si prin urmare nu va fi luat in discutie.

Definim o un bloc de operatii ca fiind format din:

o operatie elementara de tipul celor enumerate mai sus sau

o secventa (succesiune) de blocuri care se vor executa in ordinea in care apar in secventa.

O structura de control alternativa poate avea una din formele:

a) forma incompleta;

daca conditie atunci

Bloc1

sfdaca

sau

b) forma completa

daca conditie atunci

Bloc1

altfel

Bloc2

sfdaca

O structura de control repetitiva poate avea una din formele:

a) cu test la intrarea in ciclu

cat timp conditie executa

Bloc

sf cat timp

sau

b) cu test la iesirea din ciclu

repeta

Bloc

pana cand conditie

Observatie. Daca Bloc2 nu contine nici o operatie (este bloc vid), structura alternativa, forma completa se transforma in structura alternativa, forma incompleta.

Printr-un bloc de operatii am creat o operatie compusa, care poate fi privita, la un anumit grad de detaliu in reprezentarea algoritmilor ca o operatie elementara.

Daca aparent, un algoritm reprezentat in pseudocod, la un anumit grad de detaliu este o secventa de blocuri, la un grad de detaliu superior, vom constata ca parcurgerea secventiala este intrerupta prin intalnirea structurilor alternative care, prin evaluarea conditiilor si stabilirea valorii de adevar a expresiei booleene asociate acestora, poate decide care bloc sa se execute sau nu, sau mai mult chiar, o structura repetitiva determina executia unui bloc o data sau de mai multe ori. Pana la acest nivel de detaliu, limbajul natural ofera o forma de reprezentare plastica, usor de exprimat si de retinut (memorat). In continuare insa, inaintand ca grad de detaliere pseudocodul isi dovedeste superioritatea prin exactitate si eliminarea oricaror ambiguitati de exprimare sau redundante.

O forma grafica, exacta si intuitiva, de reprezentare a algoritmilor este schema logica. Considerata ca prima forma de reprezentare sugestiva a unui algoritm, aceasta s-a perfectionat ajungand la un nivel care permite o standardizare acceptabila. O schema logica are ca parti constitutive, reprezentari grafice ale operatiilor si structurilor prezentate la definirea unui limbaj pseudocod.

Astfel, pentru reprezentarea:

unei operatii de atribuire se va folosi

Fig. 1.

unei operatii de citire se va folosi

Fig. 2.

unei operatii de scriere se va folosi

Fig. 3.

unei structuri secventiale se va folosi

Fig. 4.

- unei structuri de control alternative incomplete se va folosi

Fig. 5.

- unei structuri de control alternative complete se va folosi

Fig. 6.

unei structuri de control repetitive cu test la intrarea in ciclu se va folosi

Fig. 7.

unei structuri repetitive cu test la iesirea din ciclu

Fig. 8.

Se observa ca orice operatie sau structura reprezentata mai sus poate fi asimilata cu un bloc care are o singura intrare si o singura iesire. Prin urmare, chiar un algoritm, la nivelul cel mai redus de detaliu poate fi privit ca un bloc cu o singura intrare si o singura iesire. Asociem acestui bloc alte doua blocuri afunctionale, unul la intrare si unul la iesire:

Fig. 9.

In 1966 s-a demonstrat ca "orice algoritm poate fi reprezentat folosind numai structurile: secventiala, alternativa si repetitiva". Rezultatul obtinut a condus la aparitia unei noi viziuni de proiectare a algoritmilor, proiectarea modulara si structurata.

Exemplu. Se dau doua numere naturale nenule. Sa se determine cel mai mare divizor comun al acestora.

In cele ce urmeaza, vom prezenta algoritmul de calcul al celui mai mare divizor comun a doua numere naturale prin scaderi repetate, in cele trei forme de reprezentare ale algoritmilor.

a)      Reprezentarea in limbaj natural

Pas 1. (intrare) Citeste numerele naturale nenule a si b

Pas 2. (metoda) Scade din numarul cel mai mare numarul cel mai mic pana cand cele doua numere devin egale.

Pas 3. (iesire) Afiseaza numarul obtinut.

b)      Reprezentarea in limbaj pseudocod

Pas1. Citeste a, b (a b

Pas2. Cat timp a<>b executa

Daca a<b atunci

b := b - a

altfel

a := a - b

sf daca

Pas3. Scrie a.

Observatie: Numerotarea pasilor unui algoritm nu este obligatorie. Aceasta numerotare se va face ori de cate ori este nevoie sa se faca o referire la un pas anume din algoritm sau daca este necesar a fi scos in evidenta blocul de operatii care constituie acest pas.

c) Reprezentarea prin schema logica:

Fig. 10.

Vom incheia cu un alt exemplu care va conduce la o concluzie naturala si in acelasi timp interesanta.

Exemplu. Fie a₁ = 0 si a₂ = 1. Se cere sa se construiasca un sir de numere pornind de la acestea, sir in care un nou termen se obtine ca suma ultimilor doi termeni din sir determinati anterior.

Deci un nou termen (cel cu numarul de ordine n, notat a_n) va fi

a_n = a_n-1 + a_n-2

Se obtine sirul: 0,1,1,2,3,5,8,13,, cunoscut sub numele de sirul lui Fibonacci.

Dar daca a₁ si a₂ ar avea alte valori? Sa luam, de exemplu a₁ = 1 si a₂ = atunci se va obtine sirul:

Se observa ca, chiar daca algoritmul este mereu acelasi, rezultatul final este conditionat de 'datele initiale'.

Acest lucru este valabil in orice algoritm. Mai mult chiar, intr-un algoritm, succesiunea operatiilor este determinata de datele de intrare si de rezultatele intermediare datorate secventei de operatii executate pana la un moment dat. Datele initiale, rezultatele intermediare si deciziile luate in structurile alternative si repetitive determina o 'traiectorie' a executiei operatiilor.

Daca notam cu:

- t₀ secventa (traiectoria) initiala si cu

- d₀ datele initiale,

atunci o noua traiectorie se obtine din cea initiala, dupa executarea primei operatii:

t₁ = h(t₀, d₀) si

d₁ = p(t₁,d₀)

unde cu h am notat functia de decizie (stabilita pe durata executarii operatiei curente), iar cu p prelucrarile suferite de datele cu care se incepe operatia curenta. Functia h determina urmatoarea operatie ce se va executa, iar functia p determina datele intermediare rezultate din executia operatiei curente. In general avem:

t_k = h(t_k-1, d_k-1) si

d_k = p(t_k,d_k-1).

Obtinem astfel o succesiune

t₀, t₁, t₂, t₃, , t_k, de operatii si succesiunea

d₀, d₁, d₂, d₃, , d_k, a valorilor intermediare ale datelor intrate in prelucrare (initiale) sau obtinute pe parcursul prelucrarilor.

Daca reluam exemplul algoritmului pentru determinarea celui mai mare divizor comun a doua numere naturale nenule prin scaderi repetate prezentat anterior, schemei logice din Fig.10 i se poate asocia un digraf (<Croitoru>), ca in figura de mai jos:

Fig. 10.a.

Pentru a ilustra traiectoria si dinamica prelucrarilor se vor determina cele doua siruri dand ca valori initiale a = 24 si b = 32

Initial t₀ = 1 d₀ este multimea vida , apoi cele doua siruri se formeaza astfel:

t₁ : 1,2 si d₁ : 24,32

t₂ : 1,2,3 si d_2: 24,32

t₃ : 1,2,3,4 si d₃ : 24,32

t₄ : 1,2,3,4,5 si d₄ : 24,8

t₅ : 1,2,3,4,5,3 si d₅ : 24,8

t₆ : 1,2,3,4,5,3,4 si d₆ : 24,8

t₇ : 1,2,3,4,5,3,4,6 si d₇ : 16,8

t₈ : 1,2,3,4,5,3,4,6,3 si d₈ : 16,8

t₉ : 1,2,3,4,5,3,4,6,3,4 si d₉ : 16,8

t₁₀ : 1,2,3,4,5,3,4,6,3,4,6 si d₁₀ : 8,8

t₁₁ : 1,2,3,4,5,3,4,6,3,4,6,3 si d₁₁ : 8,8

t₁₂ : 1,2,3,4,5,3,4,6,3,4,6,3,7 si d₁₂ : 8,8

t₁₃ : 1,2,3,4,5,3,4,6,3,4,6,3,7,8 si d₁₃ : 8,8 .

Prin urmare, traiectoria prelucrarilor, induc in digraful asociat algoritmului, un drum de la nodul initial, asociat primei operatii din algoritm (Start), la nodul final asociat ultimei operatii din algoritm (Stop

2. Metode de elaborare a algoritmilor

Mult timp, elaborarea unui nou algoritm pentru rezolvarea unei probleme a constituit o forma de manifestare a inteligentei, o exprimare a capacitatii de sinteza si analiza, a bagajului de cunostinte si experienta ale celui care il elabora punandu-se in evidenta caracterul de creativitate, de arta chiar a acestei activitati. Reusitei standardizarii reprezentarii algoritmilor i s-a alaturat dorinta de standardizare a elaborarii algoritmilor. Cu toate succesele obtinute in acest sens, activitatea de elaborare a algoritmilor beneficiaza inca de o doza substantiala de libertate de exprimare a experientei si creativitatii. Primele metode de elaborare a algoritmilor au avut perioade mai lungi sau mai scurte de 'priza la mase', dar o analiza atenta a eficientei (complexitatii) algoritmilor elaborati au etalat avantaje si neajunsuri, care au condus la o ierarhizare a acestor metode. In cele ce urmeaza, vom prezenta succint cele mai uzitate metode de elaborare a algoritmilor.