Realizarea unui program pentru o anumita aplicatie presupune implicarea mai multor etape. Aceste etape sunt independente de limbajul de programare utilizat si implica existenta câtorva restrictii cu privire la computerul utilizat.
Etapele realizarii unui program sunt urmatoarele:
Studierea detaliata a cerintelor aplicatiei. Este foarte important ca cerintele impuse de aplicatie sa fie foarte bine explicitate. Adica înainte de a trece la realizarea unui program pentru o anumita aplicatie trebuie ca cea aplicatie sa fie foarte bine analizata si cerintele pe care aceasta le impune trebuie sa fie complete si consistente. De exemplu o cerinta de genul "scrie un program care sa rezolve ecuatiile" este evident ca este incompleta si se impun întrebari de genul "ce tip de ecuatii", "câte ecuatii", "care este precizia", etc.
Analiza problemei si determinarea rezolvarii acesteia. Adica în aceasta etapa se decide asupra unei metode care poate sa rezolve problema. O astfel de metoda este des denumita ALGORITM.
Traducerea algoritmului realizat la etapa anterioara 242g615c într-un limbaj de programare evoluat corespunzator. Forma scrisa a acestui program este denumita program sursa (source program sau source code). În aceasta etapa programul trebuie citit si verificat pentru a i se stabili corectitudinea. Aceasta se face prin introducerea unui set de valori si verificarea daca programul furnizeaza valorile corespunzatoare corecte. O data verificat programul este introdus în computer prin intermediul unui Editor.
Compilarea programului în limbaj masina. Astfel programul obtinut în limbaj masina se numeste object code. În aceasta etapa compilerul poate determina erori de sintaxa ale programului. O eroare de sintaxa este o greseala în gramatica limbajului. de exemplu C++ necesita ca fiecare linie sa se termine cu ;. Daca se uita plasarea ; atunci compilerul va semnala eroarea de sintaxa. Astfel se repeta compilarea pâna la eliminarea tuturor erorilor de sintaxa.
Programul obtinut în urma compilarii, object code, este apoi corelat (linked) cu o serie de biblioteci de functii (function libraries) care sunt furnizate de sistem. Toate acestea se petrec cu ajutorul unui program numit linker iar apoi programul linked object code este încarcat în memoria computerului de catre un program numit loader.
Rularea programului compilat, linked si încarcat cu un set de date pentru testare. Astfel se vor pune în evidenta erorile de logica ale programului. Erorile de logica sunt erori care sunt produse de metoda de rezolvare a problemei. Astfel desi programul este scris corect din punct de vedere al sintaxei acesta poate executa ceva ce este incorect în contextul aplicatiei. Poate fi ceva simplu, de exemplu realizarea unei operatii de scadere în loc de adunare. O forma particulara a erorilor de logica este aparitia erorilor de rulare (run-time error). O eroare de rulare va produce o oprire a programului în timpul executiei pentru ca nu anumite instructiuni nu pot fi realizate. De exemplu o împartire la zero sau încercarea de accesare a datelor dintr-un fisier inexistent.
Astfel se impune ca în aceasta etapa programul sa fie reverificat si apoi erorile sa fie recorectate prin intermediul Editorului ceea ce impune ca etapele 3,4, si 5 sa fie repetate pâna la obtinerea rezultatelor satisfacatoare.
Programul poate fi pus în executie pentru rezolvarea problemei pentru care a fost conceput. Este posibil ca pe parcursul executiei sale sa se mai depisteze anumite erori de logica. Astfel se impune reformularea algoritmului si reluarea etapelor de realizarea a programului.
Prin algoritm se întelege un ansamblu de reguli (instructiuni) de prelucrare, împreuna cu ordinea în care se succed în vederea solutionarii unui tip de probleme.
Algoritmul este o formula sau un set de pasi pentru rezolvarea unei probleme particulare. Pentru ca un set de reguli sa formeze un algoritm este necesar ca acestea sa nu fie ambigue si sa aiba un punct de oprire bine precizat. Algoritmii pot fi exprimati în orice limba, de la limbajele naturale (engleza, româna, etc) la limbajele de programare (C++, etc).
Algoritmii sunt folositi peste tot în viata de zi cu zi. Astfel reteta de realizare a unei prajituri este un algoritm. Majoritatea programelor sunt formate din algoritmi. cea mai importanta provocare din programare este aceea de a inventa un algoritm elegant care sa fie simplu si sa necesite un numar minim de pasi.
Sa se precizeze algoritmul de rezolvare a ecuatiei de gradul I AX +B = 0, valorile coeficientilor A si B fiind cunoscute.
R0. Declanseaza procesul de rezolvare;
urmeaza regula R1
R1 Precizeaza valorile concrete ale coeficientilor A si B;
urmeaza regula R2.
R2 Daca A≠ 0
atunci
urmeaza regula R3
altfel
urmeaza regula R6.
R3 Calculeaza valoarea expresiei -B/A si
atribuie rezultatul lui X;
urmeaza regula R4.
R4 Afiseaza rezultatul (valoarea lui X);
urmeaza regula R5.
R5 Opreste procesul de rezolvare.
R6 Daca B=0
atunci
afiseaza mesajul "ecuatie nedeterminata"
urmeaza regula R5
altfel
afiseaza mesajul "ecuatie imposibila"
urmeaza regula R5.
Dupa cum se observa regulile (instructiunile) algoritmilor au fost notate cu R0, .R6. Fiecare regula precizeaza operatia ce îi este proprie precum si regula care îi urmeaza.
Sa se precizeze algoritmul pentru calculul sumei primilor 50 de termeni ai sirului: 1, 4, 7, 10, 13, 16, .
Înainte de a trece la rezolvare vom adopta urmatoarele notatii:
T pentru valoarea unui termen al sirului;
I pentru rangul unui termen al sirului;
S pentru suma primilor 50 de termeni
I0 Start
I1 Atribuie lui S valoarea 0
I2 Atribuie lui T valoarea 1
I3 Atribuie lui I valoarea 1
I4 Daca I>50
atunci
urmeaza instructiunea I8
altfel
urmeaza instructiunea I5
I5 Aduna T la S
I6 Aduna 3 la T
I7 Aduna 1 la I
urmeaza instructiunea I4
I8 Afiseaza valoarea lui S
I9 Stop
În cazul exemplului 2 regulile (instructiunile) s-au notat cu I0, .I9.
În cele doua exemple apar unele elemente ca 0, 1, 3, 50 ale caror valori nu se modifica în cursul executiei si care de regula se numesc constante, iar alte elemente ca A, B, T, S, I ce pot lua diverse valori în cursul executiei si care de obicei se numesc variabile. Deoarece prelucrarea datelor nu presupune numai lucrul cu cifre, notiunea de constanta va fi utilizata într-o acceptiune mai larga. De exemplu daca se doreste memorarea (în calculator) a numelui unei persoane (POPESCU) se va rezerva în acest scop o zona de memorie în care se va introduce sirul de caractere POPESCU. Daca zona de memorie o identificam prin variabila NUME atunci POPESCU va constitui valoarea acestei variabile. Evident ca în acest caz este vorba de o valoare nenumerica. Pentru a face deosebirea între numele de variabile si constantele numerice, acestea din urma se scriu între apostrofuri.
Constantele si variabilele reprezinta datele asupra carora opereaza algoritmii. Variabilele pot fi interpretate ca nume de zone de memorie iar valorile atribuite lor în timpul executiei algoritmului trebuie interpretate ca fiind continutul acestor zone.
Pentru rezolvarea oricarei probleme, utilizatorul va furniza algoritmului o serie de elemente numite date de intrare sau date initiale iar algoritmul va furniza utilizatorului solutia problemei sub forma unor rezultate partiale si/ rezultate finale.
Se constata ca exista posibilitatea ca unele reguli sa execute de mai multe ori pâna la obtinerea rezultatului final. Se spune în acest caz ca algoritmul contine un ciclu (ex. regulile I4, I5, I6, I7).
Ciclul este caracterizat de doua elemente constitutive:
corpul ciclului (grupul de instructiuni care se executa în mod repetat);
conditia de iesire din ciclu;
Exista doua categorii de cicluri:
cicluri cu numar necunoscut de pasi (la care numarul de reluari ale corpului ciclului nu poate fi cunoscut din înainte);
cicluri cu numar cunoscut de pasi (la care numarul de reluari ale corpului ciclului poate fi cunoscut din înainte)
Fiind date valoarea initiala VI, valoarea finala VF si pasul variabilei de ciclare P, se poate determina numarul de executii ale corpului ciclului N, utilizând formula:
unde [X] reprezinta partea întreaga a numarului X.
Instructiunile unui algoritm pot fi clasificate în doua mari categorii:
instructiuni de tip prelucrare prin care se realizeaza initializarea, atribuirea, calculul sau afisarea unei valori si care transmit controlul procesului de rezolvare cel mult unei reguli;
instructiuni de tip predicat care presupun efectuarea unui test asupra unei variabile, sau care contin o conditie, în asa fel încât starea momentana a datelor face ca controlul sa se transmita catre una si numai una din instructiunile ce pot primi controlul.
Definibilitate: algoritmul este bine definit, fiecare regula este bine precizata si nu conduce la ambiguitati, succesiunea instructiunilor sale este bine stabilita.
Realizabilitate: (efectivitate) exista posibilitatea efectuarii operatiilor prevazute în instructiunile algoritmului.
Finititudine: algoritmul conduce la rezultate dupa un numar finit de executii ale instructiunilor sale.
Generalitate: algoritmul se poate utiliza la rezolvarea unei clase întregi de probleme aplicându-se datelor initiale proprii fiecarei probleme în parte (date de intrare) si furnizând rezultatul (solutia) problemei concrete (date de iesire).
Automatism: algoritmul poate fi aplicat fara ca instructiunile sale sa ceara un efort de gândire deosebit, utilizatorul putând executa în mod mecanic operatiile simple indicate.
Într-un algoritm fiecare regula trebuie sa precizeze foarte clar operatiile ce se executa asupra datelor, lucru nu tocmai simplu de realizat în contextul limbajului natural. De aceea pentru operatiile ce pot sa apara în descrierea unui algoritm au fost introduse si consacrate notatii simple, care sa nu genereze ambiguitati. Aceste notatii se vor prezenta în continuare.
Prin operatii de calcul se înteleg operatiile elementare de adunare, scadere, înmultire, împartire si ridicare la putere.
Alte operatii algebrice (extragerea radacinii, logaritmarea, etc) sunt considerate neelementare si ele pot fi executate numai prin reducere la operatii elementare.
Reprezentarea operatiilor în cadrul unui algoritm se poate face fie prin simbolurile consacrate în aritmetica fie prin simbolurile consacrate în limbajele de programare:
+ adunare
- scadere
* inmultire
/ pentru împartire
** pentru ridicare la putere
Aceste operatii intervin în cadrul expresiilor. Expresia este o succesiune de variabile si constante legate între ele prin semne de operatii si eventual paranteze, dupa reguli bine definite.
Într-un algoritm o expresie apare în cadrul unei operatii de atribuire.
Printr-o asemenea operatie se atribuie o valoare unei variabile, valoare ce poate fi a unei constante, a unei alte variabile sau a unei expresii.
Scopul acestor operatii este de a verifica relatiile existente între datele asupra carora opereaza algoritmul pentru a decide transmiterea controlului executiei. Aceste operatii sunt cunoscute deja din algebra si se reprezinta prin semnele: <, >, =, ≠, ≤, ≥.
În urma executarii unei operatii de test rezultatul obtinut este una din asa numitele valori logice: adevarat sau fals.
Aceste operatii au o semnificatie bine definita în cadrul prelucrarii automate a datelor si se refera la introducerea datelor initiale, respectiv furnizarea rezultatelor.
Operatia de intrare se mai numeste si operatie de citire si reprezinta practic operatia de atribuire a unor valori din afara algoritmului, înregistrate pe diferite suporturi de stocare a datelor, unor variabile utilizate de acesta.
Operatia de iesire se mai numeste si operatia de scriere sau operatia de afisare si din punct de vedere practic consta în furnizarea de la algoritmi catre utilizator a valorilor unor variabile, valori ce constituie rezultate si care pot fi scrise pe diferite suporturi de stocare a datelor.
Descrierea algoritmilor într-un limbaj natural prezinta serie de inconveniente care se reflecta negativ asupra caracteristicilor acestora. De aceea a fost necesara introducerea unor limbaje pentru descrierea algoritmilor, care sa permita o prezentare simpla, într-o forma apropiata de limbajul natural, dar în acelasi timp având o structura apropriata de cea a limbajelor de programare.
Schemele logice constituie un asemenea limbaj de descriere a algoritmilor, usor de învatat, usor de transpus într-un limbaj de programare.
În continuare vor fi prezentate simbolurile si structurile elementare care stau la baza elaborarii schemelor logice.
Simbolurile utilizate sunt de fapt figuri geometrice compuse din arce (sageti) si noduri. Un nod se reprezinta printr-o figura geometrica simpla (dreptunghi, romb, etc). În cele ce urmeaza vor fi prezentate patru tipuri de simboluri.
|
Figura 1 |
În figura 1 este reprezentat simbolul pentru o instructiune de prelucrare. S-a utilizat simbolul f pentru reprezentarea functiei care opereaza modificarea asupra datelor ce intra în acest nod si care poate fi o operatie elementara sau o operatie complexa. |
Printr-un astfel de simbol se reprezinta regulile de tip prelucrare. În practica sunt folosite urmatoarele variante ale acestui simbol:
|
Figura 2 |
. Figura 3 |
În figura 2 este prezentat simbolul utilizat pentru operatiile de intrare/iesire. În figura 3 este prezentat simbolul utilizat pentru reprezentarea unor prelucrari complexe care urmeaza sa fie detaliate ulterior.
|
Figura 4 |
În figura 4 este reprezentat simbolul pentru o instructiune predicat. S-a utilizat simbolul P pentru reprezentarea unei conditii, unui test, sau o expresie booleana. În functie de valorile datelor, când se ajunge la acest nod, p poate lua valoarea adevarat sau fals, alegându-se o iesire sau cealalta, conform unei conventii facute anterior. Prin acest simbol se reprezinta regulile de tip predicat. |
|
Figura 5 |
Acest simbol nu joaca nici un rol în prelucrarea efectiva a datelor. El permite regruparea a doua iesiri într-o singura intrare în modul urmator, precum si etichetarea acestui nod prin înscrierea în cerculet a unui cod de identificare. |
|
Figura 6 |
Aceste doua simboluri nu au nici un rol în prelucrarea efectiva a datelor ele fiind utilizate numai ca semnificatie a începerii respectiv terminarii unor prelucrari. |
Reprezentarea algoritmilor prin scheme logice reprezinta una din cele mai utilizate tehnici pentru exprimarea clara si completa a modului de rezolvare a unei probleme.
Prin schema logica se întelege forma grafica de reprezentare a unui algoritm utilizând simbolurile prezentate anterior.
Pentru a obtine schema logica a unui algoritm se procedeaza astfel:
v se înlocuiesc regulile algoritmului prin simboluri adecvate reprezentând în noduri operatiile ce trebuie executate.
v se unesc simbolurile în sensul indicat de succesiunea regulilor algoritmului
Pentru exemplificare în continuare se vor prezenta schemele logice ale algoritmilor celor doua exemple prezentate la cursul anterior.
v Sa se precizeze algoritmul de rezolvare a ecuatiei de gradul I AX +B = 0, valorile coeficientilor A si B fiind cunoscute. (Figura 7);
v Sa se precizeze algoritmul pentru calculul sumei primilor 50 de termeni ai sirului: 1, 4, 7, 10, 13, 16, . (Figura 8)
Notatii:
T pentru valoarea unui termen al sirului;
I pentru rangul unui termen al sirului;
S pentru suma primilor 50 de termeni.
|
Figura 7 |
Figura 8 |
O schema logica se numeste normalizata daca îndeplineste urmatoarele reguli:
v Are un singur arc de intrare (bloc terminal de început) si un singur arc de iesire (bloc terminal de sfârsit);
v Exista un traseu de la intrare catre orice nod si de la orice nod catre iesire.
Schemele logice normalizate prezinta interes prin faptul ca pot fi înlocuite în întregime prin noduri de tip prelucrare. Aceasta si pentru ca într-o acceptiune mai larga nodurile de tip prelucrare pot prezenta un anumit stadiu de analiza a problemei, de prelucrari foarte complexe ce pot fi detaliate ulterior. Uneori o asemenea schema logica se mai numeste si schema functionala sau program normalizat.
|
|
|
Figura 9Scheme logice nenormalizate |
|
|
Figura 10Schema logica normalizata |
Unele structuri întâlnite în schemele logice normalizate se remarca prin generalitatea functionarii lor. Este vorba de acele structuri care se refera la prelucrari în serie, alternative si repetitive. În continuare se vor prezenta tipurile de structuri de baza pentru fiecare precizându-se notatia si reprezentarea lor sub forma de schema logica normalizata.
|
Figura 11 |
Se refera la înlantuirea (tratarea succesiva) a doua prelucrari g si h care pot fi instructiuni simple sau orice prelucrare admisa, conform cu cele prezentate pâna la acest moment, precum si orice parte de schema logica, daca aceasta parte are ea însasi o structura se schema normalizata. |
|
Figura 12 |
În aceasta structura p este un predicat iar g si h sunt doua prelucrari. În functie de variabilele datelor controlul va fi transmis catre una din instructiunile g si h. Cu conventia ca g se executa în cazul în care predicatul ia valoarea "adevarat", iar h se executa în cazul în care p ia valoarea "fals", aceasta structura IF-THEN-ELSE (p, g, h) admite urmatoarea exprimare: "DACĂ p, ATUNCI executa g, ALTFEL executa h". |
Structurile de tip alternativ admit doua variante:
|
v Tipul pseudo-alternativ: este o structura de tip alternativ în care prelucrarea h este vida. Se citeste: "DACĂ p, ATUNCI executa g". |
Figura 13 |
v Tipul multialternativ. Reprezinta o generalizarea tipului alternativ propriu zis, în care apare si o regrupare automata a iesirilor.
|
Figura 14 |
|
Figura 15 |
În aceasta structura p reprezinta un predicat iar g o prelucrare. Aceasta structura se numeste ciclu, si admite exprimarea: "CÂT TIMP p este adevarat, EXECUTĂ g" |
Trebuie remarcat ca daca p este de la început fals g nu se executa nici macar o data.
Tipul repetitiv admite la rândul sau doua variante:
|
v Structura DO-UNTIL: unde g se executa cel putin o data. Admite exprimarea "EXCUTĂ g PÂNĂ CÂND p". |
Figura 16 |
|
v Structura DO-FOR: este o varianta a structurii WHILE-DO în care predicatul p nu da numai conditia de iesire din ciclu, dar precizeaza si numarul de executii ale corpului ciclului. Acest control se realizeaza cu variabila de control (aici notata cu I) careia I se precizeaza valoarea initiala VI, valoarea finala VF si pasul VP. Variabila de control poate fi utilizata în calculele din prelucrarea g daca prin aceasta nu I se modifica valoarea. Prelucrarea g se mai noteaza în aceasta varianta si prin g(I), pentru a sugera faptul ca executia lui g se face sub controlul variabilei I. Din acelasi motiv se obisnuieste ca predicatul sa se noteze cu p(I). |
Figura 17 |
|
