Algoritmi si Structuri de Date

Imagine preview
(8/10 din 1 vot)

Acest curs prezinta Algoritmi si Structuri de Date.
Mai jos poate fi vizualizat un extras din document (aprox. 2 pagini).

Arhiva contine 1 fisier pdf de 182 de pagini .

Profesor: Ardelean Gheorghe

Iti recomandam sa te uiti bine pe extras si pe imaginile oferite iar daca este ceea ce-ti trebuie pentru documentarea ta, il poti descarca.

Fratele cel mare te iubeste, acest download este gratuit. Yupyy!

Domeniu: Limbaje de Programare

Extras din document

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.

Fisiere in arhiva (1):

  • Algoritmi si Structuri de Date.Pdf