1. ALGORITMI SI MODURI DE REPREZENTARE
Prelucrarea datelor cu ajutorul calculatorului se realizeazã prin executia
unor operatii simple (aritmetice, logice, pe iruri de caractere etc.). Înlãntuirea
acestora poate conduce la prelucrãri deosebit de complexe. Aceastã înlãntuire
nu este fãcutã la întîmplare, ci în conformitate cu reguli definite riguros, adicã
în conformitate cu algoritmul de prelucrare sau de rezolvare a problemei.
Nu existã o definitie unanim acceptatã a notiunii de algoritm. În mod
intuitiv, un algoritm este o multime de operatii cunoscute (aritmetice, logice
etc.), care executate într-o ordine bine stabilitã, pornind de la o multime de
valori (numitã intrarea algoritmului) care fac parte dintr-o multime de astfel de
multimi (numitã domeniul de definitie al algoritmului), produc în timp finit un o
altã multime de valori numitã iesirea algoritmului.
Pentru a analiza proprietãtile algoritmilor vom prezenta doi algoritmi
cunoscuti:
determinarea celui mai mare divizor comun a douã numere naturale nenule
(algoritmul lui Euclid);
rezolvarea aproximativã a ecuatiilor algebrice si transcendente prin metoda
înjumãtãtirii intervalului.
Algoritmul lui Euclid
A determina cel mai mare divizor comun a douã numere naturale nenule,
notate m si n, înseamnã a gãsi cel mai mare numãr natural care divide numerele
date. Algoritmul lui Euclid de determinare a cmmdc constã în urmãtoarea
secventã de operatii:
(E1) Împarte m la n si fie restul r
(E2) Dacã r=0 treci la (E6)
(E3) Noteazã cu m valoarea lui n (sau atribuie lui m valoarea n)
(E4) Noteazã cu n valoarea lui r (sau atribuie lui n valoarea r)
(E5) Treci la (E1)
(E6) Cel mai mare divizor comun este n (afiseazã cmmdc este n)
(E8) Stop
Rezolvarea ecuatiilor algebrice si transcendente prin metoda înjumãtãtirii
intervalului
Fie f : [a,b] R o functie realã de o variabilã realã, continuã pe [a,b], cu
f(a)*f(b)<0 si care are pe intervalul [a,b] exact o rãdãcinã. Ne propunem sã
determinãm rãdãcina ecuatiei cu o precizie datã e. Rezolvarea ecuatiei se
realizeazã conform urmãtoarelor reguli
(I1) Fie c mijlocul intervalului [a,b], adicã
(a + b)
c := ;
(I2) Dacã f(c)=0 treci la (I10)
(I3) Dacã |a-b| e treci la (I9)
(I4) Dacã f(a)*f(c) < 0, treci la (I7)
(I5) Atribuie lui a valoarea lui c
(I6) Treci la (I1)
(I7) Atribuie lui b valoarea lui c
(I8) Treci la (I1)
(I9) Atribuie lui c valoarea lui b
(I10) Afiseazã ‘Radacina ecuatiei este’, c
(I11) Stop
Proprietãtile algoritmilor
Analizînd cei doi algoritmi constatãm cã:
algoritmii rezolvã problemele unei clase de probleme: algoritmul lui
Euclid este aplicabil oricãrei perechi de numere naturale nenule, iar
algoritmul de rezolvare a ecuatiilor algebrice si transcendente prin
înjumãtãtirea intervalului este aplicabil oricãrei functii f care satisface
conditiile problemei si orice eroare de aproximare e. Prin urmare, ei au
caracter general. Din acest motiv, algoritmii debuteazã cu precizarea
datelor initiale (sau citirea datelor initiale);
secventele de operatii descrise mai sus se încheie dupã un numãr finit de
operatii. Prima se încheie pentru cã sirul resturilor formeazã un sir de
numere naturale strict descrescãtor (restul fiind mai mic decît
împãrtitorul). A doua secventã se terminã dupã un numãr finit de operatii,
fiindcã lungimile intervalelor [a,b] formeazã un sir strict descrescãtor de
numere pozitive convergent la zero (la a n-a aplicare a operatiei de
înjumãtãtire, lungimea intervalului este
|b - a|
), deci pentru un n
suficient de mare lungimea sa va fi mai micã decît e. Pentru acest n, orice
punct din intervalul [a,b] poate fi considerat rãdãcinã a ecuatiei.
Prin urmare algoritmii au un caracter finit ;
operatiile care alcãtuiesc algoritmii se executã riguros si fãrã ambiguitãti.
Prin urmare, pornind de la aceleasi date de intrare se obtin aceleasi date
de iesire, deci algoritmii au un caracter de unicitate.
Documentul este oferit gratuit,
trebuie doar să te autentifici in contul tău.
