NOTIUNEA DE ALGORITM

Aceasta lucrare o fost elaborata pentru a veni in sprijinul celor care doresc sa invete si sa practice programarea in limbajul PASCAL. Lucrarea trebuie privita ca o introducere in problematica limbajului PASCAL. Odata stapanite notiunile prezentate in continuare, oricine poate aprofunda oricat si in orice directie toate subtilitatile diverselor variante ale limbajului TURBOPASCAL.

Scrierea algoritmului de rezolvare a problemei.

Definitie: - algoritmul este un ansamblu de reguli de prelucrare, impreuna cu ordinea in care se succed in vederea solutionarii unui tip de probleme.

-un sistem de reguli care pentru o problema data, pornind de la datele initiale se ajunge la rezultatele finale pe baza unui proces unic, finit, proces deschis printr-o succesiune de operatii de rutina la care nu intervine aportul creator al omului.

Proprietatile algoritmului

generalitatea - consta in aceea ca un algoritm nu rezolva o singura problema ci o clasa de probleme de acelasi tip;

Finititudinea - numarul transformarilor ce trebuie aplicat unei informatii de intrare pentru a obtine imformatia finala este finit;

Unicitatea - toate transformarile prin care trece informatia finala sunt univoc determinate de regulile algoritmului.

Marimi cu care opereaza algoritmii

Variabile - o marime care poate lua o multime de valori posibile in cursul prelucrarii.

Constante o marime ce are atribuita o valoare care nu se modifica in timpul executiei.

Marimile pot fi succesiuni de caractere alfabetice, numerice si chiar speciale. Este indicat ca aceste numere atribuite marimilor sa fie sugestive.

Operatii utilizate in algoritmi

Intr-un algoritm, regulile trebuie sa precizeze foarte clar operatiile ce se executa asupra datelor.

1.Operatii de calcul - sunt operatiile obisnuite de : adunare (+), scadere (-), inmultire (*), impartire (/), ridicare la putere.

Acestea intervin in cadrul expresiilor care sunt o succesiune de variabile si constante legate intre ele prin operatori ( semne de operatii ) si eventual paranteze, dupa reguli bine definite.

In cadrul expresiilor operatiile se executa in ordinea naturala, conform prioritatilor.

Intr-un algoritm o expresie apare intotdeauna in cadrul unei operatii de atribuire.

2.Operatii de atribuire: printr-o asemenea operatie se atribuie unei variabilie o valoare a unei - constante, variabile, expresii.

Operatia de atribuire se noteaza cu: " := " sau "←"

Ex: NUME : = 'IOAN' (constanta) NUME ← 'IOAN'

NUME : = NUMEP (variabila) NUME ← NUMEP

A:= 1, A←1, A:= X-1, A:= A+1

3.Operatii de test (decizie): scopul acestei operatii este de a verifica relatiile existente intre datele asupra carora opereaza algoritmul pentru a decide transmiterea controlului executiei catre o anumita instructiune.

In urma executarii unei operatii de test rezultatul obtinut este una din asa numitele valori logice de adevar: " adevarat" sau "fals".

Operatiile de test se reprezinta prin semnele: <;

4.Operatii de intrare/iesire : se refera la introducerea datelor de intrare respectiv furnizarea rezultatelor.

Operatii de intrare - citire, atribuire - citeste

Operatii de iesire - scriere, afisare -scriere

Simboluri grafice

Schema logica este forma grafica de reprezentare a unui algoritm utilizand simbolurile de reprezentare a operatiilor.

Operatii

- aritmetice: avem operatii cu - numere intregi (+, - , *, DIV, MOD )

- numere reale (+, -, *, / )

operatii pe biti - se aplica numai operanzilor de tip intreg.

Operatori pot fi:

AND    SI aritmetic (conjunctie)

OR    SAU aritmetic (disjunctie)

XOR    SAU EXCLUSIV

NOT    NEGATIE (inlocuirea lui 0 cu 1 si invers)

SHL    deplasare stanga bit cu bit

SHR    deplasare dreapta bit cu bit

Deplasare se face pe toata lungimea in biti a tipului la care se aplica.

- operatii cu multimi - reuniune, intersectia, diferenta.

- operatii cu siruri de caractere - operanzii pot fi de tip sir de caractere (string) sau de tip chart. Rezultatul este intotdeauna de tip sir de caractere

- operatia de adresare - se aplica asupra identificatorilor de variabila, constanta simbolica, functii, proceduri

- operatii logice ( AND, OR, XOR, NOT ) - operanzii sunt de tip logic (Boolean).

- operatii relationale (relatii)- permit compararea a doi operanzi, rezultatul va fi de tip boolean.

Exemple de scheme logice

Schema logica a inmultirii

Schema logica a algoritmului care rezolva ecuatia de gradul 2 de forma:

Ax² + Bx + C = 0

Pentru rezolvare se calculeaza D : = B² - 4 * A * C, iar apoi valorile pentru x1 si x2 in cazul cand acestea au valori reale, iar in cazul cand x1 si x2 au valori complexe se scrie un mesaj.

3. Sa se deseneze schema logica a unui algoritm de calcul al valorii minime din trei numere date ( A, B, C ) si sa se tiparesca aceasta valoare.

Pentru a gasi minimul a trei elemente se compara primele doua si cel mai mic dintre ele se compara cu al treilea. Cel mai mic dintre acestea este elementul cu valoarea minima.

4. Sa se deseneze schema logica pentru suma a doua matrici.

Operatiile asupra matricilor impun parcurgerea acestora element cu element, fapt care presupune modificarea ciclica a indicilor de linie si de coloana. Presupunem ca avem matricea A [ M, N ] si matricea B [ M, N ] iar matricea rezultat va fi C [ M, N ] unde M reprezimta numarul de linii iar N reprezinta numarul de coloane.

I = 1, M

J = 1, N

NU

5. Se considera un sir de N numere reale x1, x2, xn si numerele reale A si B. Sa se deseneze schema logica al unui algoritm de calcul al numarului de elemente din sir care sunt cuprinse in intervalul ( A, B ).

6.Se considera sirul x₁x ₁₀₀. Sa se deseneze schema logica a unui algoritm de calcul a mediei aritmetice a termenilor pozitivi din sir.

7.Se da un sir de N numere reale A₁ .. A_n . Sa se deseneze schema logica a unui algoritm de calcul care sa ordoneze sirul crescator.

Etapele de executie a unui program

Limbajul de programare constituie mijlocul de comunicare intre om si calculator, iar descrierea succesiunii de operatii pe care trebuie sa le efectueze calculatorul se numeste program.

Etapele necesare realizarii unui program sunt urmatoarele:

a) scrierea programului (intr-un anumit limbaj de programare);

b) compilarea programului;

c) editarea de legaturi (link-editarea);

d) executia programului;

e) eventuala depanare a sa, reluand procedeul de la etapa a);

f) imbunatatirea performantelor programului;

a) Scrierea programului presupune editarea unui fisier ce contine textul programului. Acest fisier se cheama fisier-sursa si este un fisier text in format ASCII. In interiorul sau el contine instructiuni ale limbajului in care se face programarea.

Un limbaj de programare este foarte asemanator limbajului obisnuit (natural); el reprezinta un sistem de conventii pe baza caruia se efectueaza o comunicare. Deci limbajul de programare este un sistem de cuvinte (cheie), semne, constructii cu cuvinte si semne care ne asigura de faptul ca transmitem calculatorului ceea ce dorim sa realizeze.

b)"Propozitiile" si "frazele" unui limbaj de programare nu sunt direct intelese de calculator. Ele sunt traduse din aceasta forma usor manevrabila in instructiuni masina (singurele recunoscute de microprocesor) de cate un program ce se cheama compilator. Acest program recunoaste notiunile din fisierul-sursa si le converteste in echivalentele lor in limbaj masina pe care le depune intr-un fisier de iesire numit fisier-obiect.

Fisierul-obiect produs de un compilator nu este, inca, gata de a fi executat necesitand o prelucrare suplimentara .

Daca fiecare instructiune din fisierul-sursa ar produce instructiuni care realizeaza scrierea unui mesaj aceasta portiune de cod s-ar gasi repetata (cu mici modificari) in mai multe locuri din program. Pentru inlaturarea unui astfel de lucru nedorit, operatiile cel mai des folosite sunt "izolate" intr-o colectie de rutine, de unde pot fi apelate oricand este nevoie.

Deci dupa compilare, fisierul-obiect produs nu va contine intotdeauna instructiunile necesare unei operatii ci eventuale referiri la rutina de biblioteca ce executa operatia in cauza.

c) Editarea de legaturi (link-editare) va rezolva aceste referiri stabilind conexiunile dintre referiri si punctele referite. Ea va conecta referintele nerezolvate de compilator cu modulele de biblioteca ce le corespund.

Din colectia de rutine (denumita biblioteca) vor fi extrase numai acele rutine (module) referite care impreuna cu instructiunile din fisierul-obiect vor constitui un program coerent, adica un fisier-executabil.

d) Executia programului este scopul final al etapelor anterioare si presupune lansarea fisierului-executabil astfel obtinut. Pentru aceasta operatie sunt eventual necesare:

indeplinirea unor cerinte din partea sistemului;

specificarea de parametri corespunzatori pentru program.

e) In cazul unui program mai amplu sau in cazul unui debut in programare va fi intotdeauna necesara depanarea programului obtinut deoarece (fara gres) acesta nu va functiona din prima. Pentru depistarea eventualelor erori stau la dispozitie pachete de programe numite depanatoare.

f) Dupa ce programul a fost convins sa functioneze corect, abia atunci este cazul a incerca imbunatatirea performantelor sale (viteza de executie, resurse sistem mai reduse, protejare la erori). Pentru acest reglaj "fin" stau la dispozitie programe de tip "profiler" care detecteaza zonele de programe ce consuma cea mai mare cantitate de timp - puncte in care trebuie sa se concentreze atentia programatorului.

De regula se obisnuieste a se lansa o versiune de test a aplicatiei care este exploatata efectiv pentru a constata eventualele erori de functionare.

Etapele de compilare si link-editare sunt necesare pentru realizarea unui program compilat. Se pot "executa" aplicatii si fara producerea fisierelor obiect si executabil. Metoda folosita este cea a unui interpretor.

Un interpretor, compileaza, link-editeaza si executa un program "linie-cu-linie". Pe masura ce sunt citite linii din fisierul-sursa ele sunt transformate in instructiuni masina si executate imediat. Pentru un program dat, un interpretor nu mai produce fisiere-obiect si executabil, operand numai cu fisierul-sursa.

Care din metode este cea mai buna, cea a unui compilator sau cea a unui interpretor?

Pentru interpretor pledeaza un singur avantaj, si anume reducerea timpului de punere la punct a unei aplicatii (prin "eliminarea" etapelor intermediare), dar acest avantaj este infim, deoarece in momentul de fata, mediile de programare de tip compilator, sunt extrem de rapide (sute de linii de text-sursa pe secunda) si realizeaza automat link-editarea si executia, astfel incat intarzierile provocate de etapele "suplimentare" sunt neglijabile.

In schimb, avantajele unui program compilat fata de un program interpretat sunt zdrobitoare:

viteza de executie de cateva ori (chiar zeci de ori) mai mare;

posibilitatea de a rula de sine statator; odata compilat, compilatorul nu este necesar in executia programului, pe cand un program interpretat nu se poate "executa" decat daca interpretorul se afla in memoria calculatorului;

deci programul compilat dispune de resursele sistemului in intregime, pe cand cel interpretat le imparte cu interpretorul (mai ales memoria, care este de multe ori critica);

flexibilitatea sporita in realizarea programelor compilate (adaugarea de noi biblioteci, redefinirea unei rutine deja existente etc).

Toate aceste consideratii au determinat ca interpretoarele sa fie pe cale de disparitie la ora de fata sau oricum, sa fie dublate de un compilator. Spre exemplu limbajul BASIC ce beneficia initial numai de interpretor poseda in prezent si compilatoare care incearca sa-l mentina in atentia programatorilor.

Mediul de programare

Un pachet de programe ce asigura toate operatiile de mai inainte poarta numele de mediu de programare.

Cu ajutorul sau:

se editeaza un program;

se compileaza si eventual link-editeaza automat;

se lanseaza in executie;

se depaneaza un program;

se poate "regla" executia unui program (cu un profiler).

Mediile de programare disponibile in prezent sunt deosebit de performante si ofera utilizatorului toata gama de servicii necesare (help, exemple gata-construite etc), prin intermediul unor prgrame puternic interactive. Ele transforma munca laborioasa a programatorului intr-un succes aproape sigur.