Cauta rapid aici ↑

NOTIUNEA DE ALGORITM SI ELEMENTE DE PROGRAMARE STRUCTURATA

ELEMENTE DE PROGRAMARE STRUCTURATA

In general programarea poate fi interpretata ca fiind scrierea unor secvente de instructiuni pentru indeplinirea unor scopuri. Pentru aceasta, prelucrarea informatiei prin program se bazeaza pe un fundament mathematic adecvat. De aceea programarea nu poate fi conceputa in afara ideii de altgoritm si organizare. Daca se stabileste un altgoritm, programarea este un proces iterative. Deci, sunt necesare dezvoltarea aptitudinilor operationale, rigoarea in rationament si exprimarea precisa.

NOTIUNEA DE ALGORITM

Notiunea de algoritm este o notiune matematica foarte veche. Cu toate acestea, o definitie unanim acceptata a algoritmului nu a fost inca data. Se cunosc insa definitii riguroase pentru cateva tipuri de algorimi. Adesea algoritmul este considerat o notiune primara si de cele mai multe ori i se dau definitii de lucru. Potrivit unei asemenea definitii, un altgoritm este un sistem de reguli pe baza carora se obtine solutia problemei corespunzatoare unui set de date initiale dupa un numar finit de operatii numite pasi.

Este posibil ca pentru rezolvarea unei problem sa existe mai multi algoritmi. In asemenea situatii, la alegerea algoritmului se tine seama de diverse criteria. Dintre acestea, pot fi mentionate: viteza de calcul, marimea erorilor de calcul, spatial de memorie interna a calculatorului necesar programului corespunzator algoritmului etc. Marimea erorilor de calcul este importanta, in special la algoritmii care au la baza metode numerice. De cele mai multe ori algoritmii care dau erori mici de calcul au o viteza redusa. Criteriul legat de volumul de memorie necesar este un parametru important. Daca algoritmul conduce la un program care este mai mare decat memoria interna a calculatorului, atunci nu putem opta pentru el. De regula nu putem construi un algoritm care sa satisfaca toate criteriile de performanta. De aceea se alege algoritmul care raspunde cel mai bine cerintelor care se inpun.

Orice altgoritm trebuie sa aibe o serie de proprietati. Printre acestea, cele mai importante sunt:

  • Claritatea - un algoritm trebuie sa descrie cu precizie ordinea operatiilor care se vor efectua.
  • Universalitatea - un algoritm trebuie sa poata fi aplicat oricarui set de date initiale ale problemei pentru care a fost intocmit.
  • Eficacitatea - un algoritm trebuie sa conduca la solutia problemei dupa un numar finit de operatii.
  • Finitudinea - procesul de prelucrare ia sfarsit dupa un numar finit de pasi.
  • Determinismul - daca aplicam algoritmul de mai multe ori acelorasi date de intrare, trebuie sa obtinem rezultate identice.

Matematica furnizeaza cele mai multe exemple de algoritmi:

  • Algoritmul lui Euclid de aflare a celui mai mic divizor comun pentru doua numere intregi.
  • Algoritmul de extragere a radacinii patrate.
  • Algoritmul de rezolvare a ecuatiei de gradul 1.

Sa ne oprim putin asupra urmatorului exemplu:

Forma generala a unei ecuatii de gradul 1 este ax+b = 0. Datele de intrare vor fi coeficientii ecuatiei: a si b. Datele de iesire (rezultatul prelucrarii):

  • Radacina x a ecuatiei
  • Un mesaj (“x real” sau “nu exista solutie”).

Procesul prelucrarii datelor de intrare poate fi descries astfel:

  • Se introduce (se citesc) valorile coeficientilor a si b.
  • Daca a = 0 si b = 0 atunci se afiseaza “ecuatia are o infinitate de solutii
  • Daca a = 0 si b > 0 atunci se afiseaza “ecuatia nu are solutii”.
  • Daca a < 0 atunci solutia este x =-b/a.
  • Afiseaza valoarea lui x.

Aceste mod de prezentare a prelucrarilor dintr-un algoritm se mai numeste si pseudocod (este un tip de pseudocod in care operatiile sunt descries in limbaj natural). Din exemplul de mai sus reies cu claritate finititudinea algoritmului si eficacitatea acestuia. Este un algoritm universal, deoarece poate rezolva orice ecuatie de gradul 1 si nu numai o ecuatie particulara. Pentru conservarea universalitatii in cadrul algoritmului nu se lucreaza cu valori efective, ci prin intermediul unor obiecte si anume variabilele (a, b, xsunt variabile).

O variabila este un obiect cu urmatoarele caracteristici:

  • Nume
  • Valoare
  • Tip de date
  • Zona de memorie in care este stocata valoarea variabilei

Variabila isi poate schimba valoarea pe parcursul prelucrarilor din algoritm. Valoarea variabilei poate fi utilizata prin intermediul numelui: oriunde apare numele unei variabile se intelege de fapt valoarea pe care aceasta o are la momentul respectiv. Fiecare variabila poate sa memorize o valoare de un anumit tip.

Prin tip de date se intelege o multime de valori de acelasi fel. In general tipurile de date utilizate in informatica sunt submultimi ale multimilor cunoscute din matematica. De obicei, pentru rezolvarea unei probleme se intocmeste un algoritm. De cele mai multe ori algoritmii se reprezinta sub forma de schema logica. Oschema logica se elaboreaza, de regula, in mai multe etape. La inceput se face o schita a schemei logice. Aceasta schita se rafineaza ulterior pana cand se ajunge la forma finala.

MODALITATI DE REPREZENTARE A ALGORITMILOR

Cea mai utilizata metoda de scriere a algoritmilor, cel putin pentru incepatorii in programare, este aceea a utilizarii schemelor logice. Schema logica se intocmeste cu ajutorul unor figuri geometrice simple numite blocuri. Ordinea de parcurgere a blocurilor in schemele logice se precizeaza cu ajutorul sagetilor. In continuare vom prezenta blocurile cele mai utilizate.

BLOCUL START

Este blocul care indica inceputul oricarei scheme logice si este folosit o singura data (orice schema logica are un inceput unic). Blocul delimitator are forma unei elipse alungite iar in interiorul sau se scrie cuvantul START.

BLOCUL STOP

Este blocul care incheie schema logica si este binenteles unic. Se reprezinta tot printr-o elipsa, dar in care se scrie cuvantul STOP.

BLOCUL DE CITIRE

Blocul de intrare are forma unui parallelogram. Acest bloc se foloseste la introducerea datelor in calculi si afisarea rezultatelor.

De obicei, datele de intrare ale unei probleme se introduce initial cu ajutorul tastaturii intr-o zona de memorie numita zona tampon. De aici ele sunt preluate de program. Aceasta operatie de preluare a datelor dintr-o zona tampon se numeste operatie de citire. Datele preluate din zona tampon sunt introduse in memoria interna a calculatorului. Aceasta operatie se precizeaza in schemele logice prin cuvantul CITESTE. Reprezentarea dintr-un astfel de bloc este o comanda de citire care cere sa se citeasca valorile variabilelor sis a se introduca aceste valori in memoria interna.

BLOCUL DE SCRIERE

Operatia de preluare a valorilor unor variabile din memoria interna si afisarea lor pe ecranul calculatorului se numeste operatie de scriere. De aceea, aceasta operatie se precizeaza in schemele logice prin cuvantul CITIRE. Reprezentarea dintr-un astfel de bloc este o comanda care cere sa se scrie valoarea variabilei x pe ecranul monitorului. In programe pot aparea si operatii de citire din fisiere de date. De asemenea este posibila si scrierea datelor in fisiere de date.

BLOCUL DE CALCUL

Blocul de calcul se foloseste pentru a preciza calculele care se fac. In blocurile de acest tip apar comenzi de forma: v = expr unde v este o variabila iar expr este o expresie de tip compatibil cu v. La intalnirea comenzii v = expr se determina valoarea expresiei expr , se converteste, daca este cazul, valoarea lui expr la o valoare de tipul lui v si se atribuie aceasta valoare variabilei v.

CONECTORI

Conectarea blocurilor ce formeaza o schema logica se realizeaza cu ajutorul unor sageti, acestea indicand si sensul de efectuare a operatiilor ce compun schema logica. Blocul conector are forma de cerc. El se foloseste pentru a conecta diferite secvente ale unei scheme logice.

Schema logica poate fi definita ca o succesiune de blocuri de tipurile prezentate mai sus, cu urmatoarele caracteristici:

  • Contine un singur bloc START si un singur bloc STOP.
  • In fiecare bloc intra o singura sageata si iese tot o singura sageata (blocurile au o singura intrare si o singura iesire).
  • Exista cel putin un traseu ce pleaca din blocul START si care mergand in sensul sagetilor ajunge in blocul STOP.

O schema logic ace are aceste proprietati reprezinta un algoritm structurat.

PROGRAMAREA STRUCTURATA

Intr-un program instructiunile sunt executate in ordinea in care sunt scrise. Insa aceasta ordine nu este intotdeauna suficienta pentru a rezolva anumite probleme. In practica pot aparea situatii in care un grup de instructiuni trebuie executat numai in anumite conditii sau altele trebuie executate in mod repetat. De aceea, in toate limbajele de programare exista instructiuni cu ajutorul carora se pot controla astfel de situatii.

La baza programarii structurate sta teorema conform careia orice schema logica cu un singur punct de intrare si un singur punct de iesire poate fi reprezentata cu ajutorul a unei structure de baza si anume:

  • Structura secventiala
  • Structura alternativa
  • Structura ciclica (cu test initial)

O schema logica construita numai cu structure de acest tip este numita schema logica structurata.