Extras din curs
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.
Preview document
Conținut arhivă zip
- Algoritmi si Structuri de Date.Pdf
Alții au mai descărcat și
1. Generalitati asupra limbajului C 1.1. Introducere Limbajul C a fost creat la începutul anilor '70 de catre Brian W Kernigham si Dennis M...
1. Un tur rapid al C++Builder Pentru moment, nu vom acorda decât o privire rapidă mediului de dezvoltare C++Builder, urmând ca în lecţia a şasea...
Introducere Un algoritm este o metoda de rezolvare a unei probleme printr-un numar finit de pasi. Printr-un pas se întelege o operatie...
• Modele de proces software • Metode ale ingineriei software • Modelarea sistemelor software folosind UML • Metode de testare a sistemelor...
PREZENTAREA GENERALĂ A MEDIULUI DE DEZVOLTARE Borlandc C++, produs al firmei Borland International, este un pachet de programe care oferă o...
Cap 1 INTRODUCERE ÎN LIMBAJUL C 1.1 Scurt istoric 1.2 Forma unui program C 1.3 Compilarea unui program C 1.1 Scurt istoric Strămoşii...
Limbajele de programare sunt împartite pe diferite niveluri în functie de gradul de interactiune cu suportul hardware: - Limbaje masina –...
Sistemul de gestiune a bazelor de date (SGBD) este componenta unui sistem de baza de date care are rolul de a permite descrierea si manipularea...
Te-ar putea interesa și
<<INTRODUCERE>> Procesele desfăşurate într-o activitate organizată nu au loc la întam-plare, ci sunt declanşate de anumite informaţii care...
Sistem informational = ansamblu de elemente interconectate si interconditionate între ele în vederea realizarii unui scop; este un ansamblu de...
Introducere: Semiotica se ocupã cu studiul semnelor în natura si în societate. Semnul nu este o calitate în sine a unui obiect, ci o functie pe...
Capitolul I Sistem informaţional - sistem informatic Un sistem este un ansamblu de elemente care pot fi conectate prin diferite tipuri de...
1. TEORIE Sistemul informaţional-informatic Activitatea desfasurata intr-un sistem organizat, in vederea realizarii unui obiectiv poate fi...
1 Tema:Implimentarea tipului abstract de date.Tabloul de structuri. 2 Sarcina:De implimentat tipul abstract de date,tablou de structuri si de...
8. Arbori 8.1. Arbori generalizaţi 8.1.1. Definiţii În definirea noţiunii de arbore se porneşte de la noţiunea de vector. Fie V o mulţime având...
Modulul 0. Alocare dinamica in limbajul C Capitolul 0. Pointeri si alocare dinamica. Tipul de date struct 0.1 Pointeri si alocare dinamica O...