ALGORITMI SI PROGRAMARE. DESCRIEREA ALGORITMILOR

Algoritmi si programare. Descrierea algoritmilor

1. Programare. Etapele programarii.

Programarea reprezinta activitatea complexa de elaborare a programelor. Programarea nu se refera strict la scrierea codului sursa (descrierea in limbaj de programare a rezolvarii problemei); aceasta activitate implica parcurgerea mai multor etape:

a. Analiza problemei. Problemele reale cu care ne confruntam nu sunt formulate intotdeauna intr-un stil clar, precis. De cele mai multe ori, problemele sunt formulate incomplet, ambiguu, lasand programatorului sarcina de a determina corect: ce se cunoaste din problema si rezultatele cerute. Etapa de analiza a problemei se finalizeaza prin identificarea celor doua elemente esentiale ale formularii unei probleme: datele de intrare si datele de iesire.

b. Proiectarea algoritmului poate fi considerata etapa de creativitate a programarii, in care folosindu-se de cunostintele si experienta dobandite, programatorul va identifica metoda de rezolvare a problemei date si va dezvolta algoritmul corespunzator. Finalitatea acestei etape o constituie un algoritm descris clar intr-una dintre variantele de reprezentare algoritmica (scheme logice, pseudocod, sau chiar limbaj de programare - in cazul in care problema este de dificultate mica).

c. Traducerea in limbaj de programare (implementarea): este etapa in care se va efectua o "traducere" in limbaj de programare a descrierii algoritmului rezultat in etapa de proiectare. Cunoasterea in detaliu a regulilor sintactice ale limbajului ales, experienta si stilul programatorului sunt ingredientele necesare si suficiente ale acestei etape.

d. Traducerea in cod masina, executia si testarea. Traducerea in cod masina se realizeaza automat cu ajutorul a doua componente ale mediului de programare: compilatorului si a editorul de legaturi. Testarea programului consta in executia sa repetata pentru o multime de date de intrare (date de test) si verificarea corectitudinii rezultatelor oferite. Rezultatele incorecte ne semnaleaza o eroare logica de proiectare si necesita o revizuire a algoritmului si re-parcurgerea etapelor programarii.

e. Intretinerea este ultima etapa a programarii si consta din actiuni de actualizare a produsului final si de asistenta oferita beneficiarului.

Dintre toate aceste etape, cea care este mai solicitanta este etapa de proiectare. Practic, parcurgerea corecta a acestei etape va face diferenta intre programatori si amatori. Esenta programarii consta in capacitatea programatorului de a elabora si descrie clar metoda de rezolvare a problemei. Orice eroare aparuta la nivelul etapei de proiectare a algoritmului va avea repercusiuni asupra produsului final, generand erori logice.

2. Definirea algoritmilor

Asa cum am subliniat mai sus, etapa de proiectare a algoritmilor este cea mai complexa dintre cele etapele enumerate ale programarii. Notiunea de algoritm, proprietatile pe care trebuie sa le indeplineasca acesta si modalitatile de reprezentare standardizata a algoritmilor fac subiectul paragrafelor urmatoare.

Cuvantul algoritm provine din pronuntia fonetica a numelui matematicianului arab Al-Khwarizmi Muhammed ibs Musa (780-850), care se refera la reguli precise pentru descrierea proceselor de calcul din aritmetica. Aceiasi descriere se regaseste in lucrarea Elementele lui Euclid, cca. 300 i.Hr., cand pentru prima data se descrie o secventa ordonata de reguli clare pentru descrierea rezolvarii unor probleme. De altfel, algoritmul de determinare a celui mai mare divizor comun a doua numere (algoritmul lui Euclid) este considerat ca primul algoritm din istorie.

In limbajul uzual, prin algoritm se intelege o metoda de rezolvare a unei probleme, alcatuita dintr-o multime de pasi, dispusi intr-o ordine stabilita, ale caror parcurgere ne conduce la rezultatul dorit. Algoritmii informatici, despre care vom discuta in acest capitol, sunt definiti mult mai riguros, surprinzand proprietatile obligatorii pe care acestia trebuie sa le indeplineasca.

Definitie: Un Algoritm (informatic) reprezinta o secventa finita si ordonata de reguli clare, a caror parcurgere ne permite ca, pornind de la o multime de date de intrare, sa obtinem in mod eficient rezultatele corecte ale problemei.

3. Proprietatile algoritmilor:

Orice algoritm informatic verifica urmatoarele proprietati:

Generalitate - un algoritm nu rezolva o singura problema, ci o clasa de probleme de acelasi tip.

Finitudine - actiunile algoritmului trebuie sa se termine dupa un numar finit de operatii, aceasta pentru orice set de date valide

Claritate - actiunile algoritmului trebuie sa fie clare, simple si riguros specificate

Corectitudine algoritmul trebuie sa produca un rezultat corect (date de iesire) pentru orice set de date de intrare valide

Eficienta - algoritmul trebuie sa fie eficient privind resursele utilizate, si anume sa utilizeze memorie minima si sa se execute intr-un timp minim.

Regulile prin care algoritmul exprima maniera de rezolvare a problemei sunt de 4 tipuri:

reguli de intrare prin care se realizeaza introducerea datelor de intrare in memoria unui sistem de calcul virtual sau real

reguli de calcul care permit efectuarea operatiilor elementare aritmetice

reguli conditionale prin care se va decide continuarea sau nu a algoritmului printr-o secventa de reguli

reguli de iesire prin care se permite furnizarea rezultatelor finale ale algoritmului

In functie de tipurile de reguli pe care le contine, un algoritm poate fi:

Algoritm liniar - contine doar reguli de tipul 1,2,4

Algoritm ramificat - contine cel putin o regula de tipul 3

Algoritmi repetitivi (ciclici) - o secventa de reguli se repeta de un numar finit de ori.

4. Obiecte si operatii ale algoritmilor

Algoritmii informatici opereaza cu urmatoarele obiecte fundamentale:

- constante

- variabile

Constanta - reprezinta o marime a carei valoare nu se modifica in timpul executiei (parcurgerii) algoritmului.

Variabila - reprezinta o marime a carei valoare este modificabila in timpul executiei algoritmului.

Cuvantul variabila este unul fundamental in programare. Prin aceasta notiune se denumesc date de tipuri diferite. Tipurile de date sunt clasificate ca tipuri elementare (intreg, real, caracter) si tipuri structurate. Datele elementare sunt unitati indivizibile de informatie, iar datele de tip structural sunt alcatuite prin asamblarea datelor elementare. Printr-un tip de data se intelege in general atat domeniul de valori posibile ale datelor, cat si operatiile specifice datelor de acel tip. Introducerea si utilizarea unei variabile in descrierea algoritmului corespunde identificarii si manipularii unei date de un tip de data presupus. Variabila are atasat un nume, o valoare curenta care apartine domeniului tipului specificat si implica cunoasterea multimii de operatii posibile la care ia parte. In algoritmii informatici, variabilele sunt toate datele de intrare, datele de iesire (rezultatele finale ale problemei) si datele intermediare (acele date care corespund unor rezultate partiale ale problemei ce intervin in procese ulterioare pentru determinarea rezultatelor finale).

In anumite situatii, actiunea algoritmilor este indreptata asupra: fisierelor si a articolelor. Fisierul reprezinta o multime structurata si omogena de date si articolul este unitatea atomica a fisierului.

Obiectele pe care le utilizeaza un algoritm sunt supuse unor operatii de manipulare. Secventa de pasi descrisa de algoritm este parcursa intr-o anumita ordine dictata de operatiile de control. Cele doua categorii de operatii formeaza operatiile principale ale algoritmilor informatici:

Operatii de intrare-iesire permit introducerea in memoria sistemului de calcul (real sau virtual) a datelor de intrare si respectiv, redarea rezultatelor obtinute

Operatii de atribuire prin intermediul acestor operatii, unei variabile i se atribuie valoarea unei alte variabile, a unei constante sau rezultatul evaluarii unei expresii

Operatii de calcul sunt operatiile executate cu ajutorul expresiilor

Operatii de decizie conditioneaza executia unui operatii sau grupe de operatii in urma evaluarii unor expresii la valorile logice - adevarat, fals.

Operatii de apel permit apelul unei instructiuni sau a unui grup de instructiuni in vederea executarii acesteia de un numar finit de ori

Operatii de salt permit continuarea algoritmului dintr-un anumit punct al acestuia

Operatii auxiliare operatii specifice lucrului cu baze de date sau fisiere.

5. Descrierea algoritmilor. Scheme logice

Reprezentarea algoritmilor poate fi facuta in doua maniere:

grafic - prin intermediul schemelor logice

textual - prin intermediul unor limbaje standardizate (limbaj pseudocod, limbaj de programare)

Schemele logice sunt reprezentari grafice ale algoritmilor informatici construite pe baza unei multimi de simboluri grafice conectate prin intermediul sagetilor. Multimea de simboluri grafice si semnificatia acestora este prezentata in continuare:

1. Simbolurile delimitatoare: avand rolul de a marca inceputul si sfarsitul schemei logice, corespunde momentelor de start si stop a algoritmului descris corespunzator.

2. Simboluri de intrare-iesire - corespunzatoare operatiilor de intrare-iesire prin care se realizeaza comunicarea cu exteriorul sistemului de calcul virtual.

3. Simboluri de atribuire - calcul - pentru reprezentarea operatiilor de calcul si atribuire. Detaliile referitoare la operatii sunt inscrise in interiorul blocului.

4. Simbolul de decizie - utilizate pentru reprezentarea operatiilor de decizie. Sunt simboluri cu o singura intrare si cel putin doua iesiri.

5. Simbolul de procedura - se folosesc pentru reprezentarea operatiilor de apel. Sunt apelate proceduri sau module externe (care sunt descrise in alta parte).

6. Simboluri auxiliare: Conectorii si sagetile - asigura consistenta schemei logice.

Utilizarea corecta a simbolurilor grafice permite descrierea oricarui algoritm informatic. Se evidentiaza trei structuri fundamentale corespunzatoare: parcurgerii secventiale a unei succesiuni de pasi, ramificarii algoritmilor si executiei repetate a unei secvente de operatii. Cele trei structuri fundamentale sunt: structura secventiala, structura alternativa, structura repetitiva, si sunt descrise prin blocuri de simboluri logice astfel:

Observatie: Diferenta dintre structurile repetitive preconditionata si postconditionata consta in pozitia simbolului de decizie corespunzator etapei de verificare a conditiei de continuare a executiei blocului:

structura preconditionata presupune initial verificarea conditiei si apoi executia secventei

structura postconditionata presupune executia secventei si apoi verificarea conditiei

Aceasta diferenta va genera un numar minim de repetari a secventei S diferit pentru cele doua structuri: minim 0 executii pentru structura preconditionata si minim 1 executie a secventei in structura postconditionata, in situatia in care de la prima evaluare a conditiei aceasta este falsa..

6. Exemple de scheme logice

Exemplul 1 Algoritmul de determinare a solutiilor ecuatiei de gradul 2: . Rezolvarea problemei presupune tratarea celor 4 cazurilor identificate in functie de datele de intrare furnizate:

1. radacinile ecuatiei sunt reale

2. ecuatia de gradul II nu are radacini reale

3. ecuatia este de gradul I

4. ecuatia este imposibila

Exemplul 2. Algoritmul de determinare a produsului primelor n numere naturale.

Exemplul 3. Algoritmul de determinare a celui mai mare divizor comun a doua numere:

7. Pseudocod

Pseudocodul este un limbaj standardizat intermediar intre limbajul natural si limbajul de programare. Descrierea algoritmilor cu ajutorul limbajului pseudocod inlatura din neajunsurile utilizarii schemelor logice, fiind mult mai flexibil si natural decat acestea. In plus, descrierea in pseudocod permite convertirea cu usurinta a algoritmilor astfel exprimati intr-un limbaj de programare.

Limbajul pseudocod foloseste doua tipuri de propozitii:

1. Propozitiile standard: proprii limbajului pseudocod

2. Propozitiile ne-standard: acele propozitii ce descriu in limbaj uzual operatii ce urmeaza a fi detaliate, rafinate ulterior. Aceste propozitii sunt marcate prin simbolul #.

Exista o concordanta intre simbolurile grafice ale schemelor logice si propozitiile limbajului pseudocod. De asemenea, structurile fundamentale pot fi descrise prin propozitii proprii limbajului pseudocod.

Tabelul urmator prezinta concordanta dintre descrierea grafica si propozitiile pseudocod pentru operatii specifice algoritmilor:

Limbajul pseudocod, pentru a usura traducerea ulterioara a algoritmului in limbaj de programare, permite folosirea unei propozitii standard echivalenta uneia dintre instructiunile populare ale limbajelor de programare. Aceasta propozitie corespunde unei structuri repetitive cu numar cunoscut de repetari si se descrie astfel:

Tabelul urmator prezinta modul de descriere a structurilor fundamentale in pseudocod:

8. Probleme propuse spre rezolvare

Sa se descrie grafic si textual (pseudocod) algoritmul de rezolvare a problemei urmatoare:

Problema 1. Sa se citeasca un numar de n valori si sa se determine cea mai mica valoare citita.

Problema 2. Sa se rezolve sistemul de 2 ecuatii liniare cu 2 necunoscute.

Problema 3. Sa se citeasca n valori si sa se calculeze media aritmetica a acestora.

9. Exemple de algoritmi descrisi in pseudocod

Exemplul 1 Algoritmul de determinare a solutiilor ecuatiei de gradul 2: .

Algoritm EcuatieGradII este:

Citeste a, b, c

Daca a ≠ 0 atunci

Daca b ≠ 0 atunci

x = -c / b

Tipareste "Sol. Ec. grad I",x

Altfel

Tipareste "Imposibil de rezolvat"

SfDaca

Altfel

= b²-4ac

Daca 0 atunci

Tipareste x1,x2

Altfel

Tipareste "Radacini complexe"

SfDaca

SfDaca   

Sfarsit EcuatieGradII

Exemplul 2. Algoritmul de determinare a produsului primelor n numere naturale.

Algoritm Factorial este:

Citeste n

P:=1

Pentru i de la 1 la n cu pasul 1

Executa P:=P * i

Sfarsit Pentru

Tipareste P

Sfarsit Factorial

Exemplul 3. Algoritmul de determinare a celui mai mare divizor comun a doua numere.

Algoritm Euclid este:

Citeste a,b

rest = a modulo b

Cattimp (rest ≠ 0)

Structura repetitiva preconditionata

a = b

b = rest

rest = a modulo b

Sfarsit cattimp

Tipareste b

Sfarsit Euclid

10. Subalgoritmi

O problema de dificultate sporita necesita uneori o impartire in subprobleme de dificultate mai mica in baza principiului divide et impera. Algoritmii de rezolvare a subproblemelor rezultate sunt mai usor de descris si vor constitui subalgoritmi ai algoritmului global de rezolvare a problemei considerate. Deseori se poate intalni situatia ca o anumita secventa de operatii sa fie executata de mai multe ori pentru date de intrare diferite. In aceste cazuri este utila construirea unui subalgoritm corespunzator secventei de operatii si apelarea acestuia in algoritmul global ori de cate ori este nevoie.

Subalgorimii sunt practic algoritmi care rezolva subprobleme ale unei probleme date. Acest lucru indica faptul ca orice subalgoritm verifica proprietatile de generalitate, finitudine, claritate, corectitudine ale algoritmilor informatici. Caracterul de generalitate va fi asigurat prin parametrizarea subalgoritmilor. Acestia vor primi la intrare nu datele de intrare ale problemei ci date intermediare ale problemei globale sau rezultate partiale din procesele de calcul. Iesirile subalgoritmilor sunt date pe care algoritmul general le va prelucra ulterior. Comunicarea dintre subalgoritm si algoritmul "parinte" se realizeaza prin intermediul parametrilor. In pseudocod sintaxa generala a unui subalgoritm este urmatoarea:

Subalgoritm NumeSubalgoritm ( lista parametrii formali)

.. // operatii asupra parametrilor din lista

Sfarsit NumeSubalgoritm

Apelarea unui subalgoritm din algoritmul apelant se face prin propozitia:

Cheama NumeSubalgoritm (lista parametrii actuali)

Lista parametrilor formali va contine nume generice ale datelor de intrare si datelor de iesire ale subalgoritmului. Lista parametrilor actuali contine numele datelor concrete care se doresc a fi transmise subalgoritmului si numele sub care se retin rezultatelor partiale ale subalgoritmului.

La apelul unui subalgoritm parametrii formali (generici) din lista se vor inlocui cu parametrii concreti (actuali).

Exemplu: Sa se descrie un algoritm de determinare a maximului dintre 4 valori date, evidentiind subalgoritmul de determinare a maximului dintre oricare doua valori.

Subalgoritm Maxim2(DI: x ,y; DE: Max)

Daca x>y atunci

Max=x

Altfel

Max=y

SfDaca

Sfarsit Maxim2

Apelul repetat al subalgoritmului, pentru diferiti parametri actuali

Algoritm Maxim4 este:

Citeste a,b,c,d

Cheama(a,b; max1)

Cheama(c,d; max2)

Cheama(max1,max2 ; maxim)

Tipareste maxim

Sfarsit Maxim4

Rezolvarea problemelor cu ajutorul calculatorului presupune:

1. Modelarea matematica a problemei
2. Alegerea unei metode de rezolvare

Modelarea matematica si alegerea metodei de rezolvare se imbina cu conceperea algoritmului rezultand ceea ce numim proiectarea programului. In faza de elaborare a algoritmului trebuie sa se tina seama de proprietatile fundamentale ale algoritmilor: generalitate, claritate, finitudine, corectitudine si eficienta. Calitatea implementarii software este dependenta de calitatea algoritmului elaborat. De aceea, faza de dezvoltare a algoritmului de rezolvare a unei clase de probleme trebuie abordata cu o deosebita atentie.