Algoritmi

Trimis la data: 2003-04-11 Materia: Informatica Nivel: Liceu Pagini: 52 Nota: / 10 Downloads: 12582
Autor: Denis-Andrei Dimensiune: 83kb Voturi: Tipul fisierelor: doc Acorda si tu o nota acestui referat: 1 2 3 4 5 6 7 8 9 10
vezi mai multe detalii vezi mai putine detalii
Raporteaza o eroare
1.1 Algoritm, program, programare
Calculatoarele pot fi folosite pentru a rezolva probleme, numai dacă pentru rezolvarea acestora se concep programe corespunzătoare de rezolvare. Termenul de program (programare) a suferit schimbări în scurta istorie a informaticii. Prin anii '60 problemele rezolvate cu ajutorul calculatorului erau simple şi se găseau algoritmi nu prea complicaţi pentru rezolvarea lor.

CAPITOLUL I. DESCRIEREA ALGORITMILOR
Prin program se înţelegea rezultatul scrierii unui algoritm întrun limbaj de programare. Din cauza creşterii complexităţii problemelor, astăzi pentru rezolvarea unei probleme adesea vom concepe un sistem de mai multe programe.

Dar ce este un algoritm? O definiţie matematică, riguroasă, este greu de dat, chiar imposibilă fără a introduce şi alte noţiuni. Vom încerca în continuare o descriere a ceea ce se înţelege prin algoritm.

Ne vom familiariza cu această noţiune prezentând mai multe exemple de algoritmi şi observând ce au ei în comun. Cel mai vechi exemplu este algoritmul lui Euclid, algoritm care determină cel mai mare divizor comun a două numere naturale. Evident, vom prezenta mai mulţi algoritmi, cei mai mulţi fiind legaţi de probleme accesibile absolvenţilor de liceu.

Vom constata că un algoritm este un text finit, o secvenţă finită de propoziţii ale unui limbaj. Din cauză că este inventat special în acest scop, un astfel de limbaj este numit limbaj de descriere a algoritmilor. Fiecare propoziţie a limbajului precizează o anumită regulă de calcul, aşa cum se va observa atunci când vom prezenta limbajul Pseudocod.

Oprindu-ne la semnificaţia algoritmului, la efectul execuţiei lui, vom observa că fiecare algoritm defineşte o funcţie matematică. De asemenea, din toate secţiunile următoare va reieşi foarte clar că un algoritm este scris pentru rezolvarea unei probleme. Din mai multe exemple se va observa însă că, pentru rezolvarea aceleaşi probleme, există mai mulţi algoritmi.

Pentru fiecare problemă P există date presupuse cunoscute (date iniţiale pentru algoritmul corespunzător, A) şi rezultate care se cer a fi găsite (date finale). Evident, problema s-ar putea să nu aibă sens pentru orice date iniţiale. Vom spune că datele pentru care problema P are sens fac parte din domeniul D al algoritmului A. Rezultatele obţinute fac parte dintr-un domeniu R, astfel că executând algoritmul A cu datele de intrare x(D vom obţine rezultatele r(R. Vom spune că A(x)=r şi astfel algoritmul A defineşte o funcţie
A : D ---> R .
Algoritmii au următoarele caracteristici: generalitate, finitudine şi unicitate.
Prin generalitate se înţelege faptul că un algoritm este aplicabil pentru orice date iniţiale x(D. Deci un algoritm A nu rezolvă problema P cu nişte date de intrare, ci o rezolvă în general, oricare ar fi aceste date. Astfel, algoritmul de rezolvare a unui sistem liniar de n ecuaţii cu n necunoscute prin metoda lui Gauss, rezolvă orice sistem liniar şi nu un singur sistem concret.

Prin finitudine se înţelege că textul algoritmului este finit, compus dintr-un număr finit de propoziţii. Mai mult, numărul transformărilor ce trebuie aplicate unei informaţii admisibile x(D pentru a obţine rezultatul final corespunzător este finit.

Prin unicitate se înţelege că toate transformările prin care trece informaţia iniţială pentru a obţine rezultatul r(R sunt bine determinate de regulile algoritmului. Aceasta înseamnă că fiecare pas din execuţia algoritmului dă rezultate bine determinate şi precizează în mod unic pasul următor. Altfel spus, ori de câte ori am executa algoritmul, pornind de la aceeaşi informaţie admisibilă x(D, transformările prin care se trece şi rezultatele obţinute sunt aceleaşi.

În descrierea algoritmilor se folosesc mai multe limbaje de descriere, dintre care cele mai des folosite sunt: limbajul schemelor logice; limbajul Pseudocod.
În continuare vom folosi pentru descrierea algoritmilor limbajul Pseudocod care va fi definit în cele ce urmează. În ultima vreme schemele logice sunt tot mai puţin folosite în descrierea algoritmilor şi nu sunt deloc potrivite în cazul problemelor complexe. Prezentăm însă şi schemele logice, care se mai folosesc în manualele de liceu, întrucât cu ajutorul lor vom preciza în continuare semantica propoziţiilor Pseudocod.

1.2 Scheme logice
Schema logică este un mijloc de descriere a algoritmilor prin reprezentare grafică. Regulile de calcul ale algoritmului sunt descrise prin blocuri (figuri geometrice) reprezentând operaţiile (paşii) algoritmului, iar ordinea lor de aplicare (succesiunea operaţiilor) este indicată prin săgeţi. Fiecărui tip de operaţie îi este consacrată o figură geometrică (un bloc tip) în interiorul căreia se va înscrie operaţia din pasul respectiv.

Prin execuţia unui algoritm descris printr-o schemă logică se înţelege efectuarea tuturor operaţiilor precizate prin blocurile schemei logice, în ordinea indicată de săgeţi.

În descrierea unui algoritm, deci şi într-o schemă logică, intervin variabile care marchează atât datele cunoscute iniţial, cât şi rezultatele dorite, precum şi alte rezultate intermediare necesare în rezolvarea problemei. Întrucât variabila joacă un rol central în programare este bine să definim acest concept. Variabila defineşte o mărime care îşi poate schimba valoarea în timp. Ea are un nume şi, eventual, o valoare. Este posibil ca variabila încă să nu fi primit valoare, situaţie în care vom spune că ea este neiniţializată. Valorile pe care le poate lua variabila aparţin unei mulţimi D pe care o vom numi domeniul variabilei. În concluzie vom înţelege prin variabilă tripletul
(nume, domeniul D, valoare)unde valoare aparţine mulţimii D ( {nedefinit}.

Blocurile delimitatoare Start şi Stop (Fig.1.2.1.a şi 1.2.1.b) vor marca începutul respectiv sfârşitul unui algoritm dat printr-o schemă logică. Descrierea unui algoritm prin schemă logică va începe cu un singur bloc Start şi se va termina cu cel puţin un bloc Stop.

Blocurile de intrare/ieşire Citeşte şi Tipăreşte (Fig. 1.2.1.c şi d) indică introducerea unor Date de intrare respectiv extragerea unor Rezultate finale. Ele permit precizarea datelor iniţiale cunoscute în problemă şi tipărirea rezultatelor cerute de problemă. Blocul Citeşte iniţializează variabilele din lista de intrare cu valori corespunzătoare, iar blocul Tipăreşte va preciza rezultatele obţinute (la execuţia pe calculator cere afişarea pe ecran a valorilor expresiilor din lista de ieşire).Blocurile de atribuire (calcul) se utilizează în descrierea operaţiilor de atribuire (:=). Printr-o astfel de operaţie, unei variabile var i se atribuie valoarea calculată a unei expresii expr (Fig.1.2.1.e).


Blocurile de decizie marchează punctele de ramificaţie ale algoritmului în etapa de decizie. Ramificarea poate fi dublă (blocul logic, Fig.1.2.1.f) sau triplă (blocul aritmetic, Fig. 1.2.1.g). Blocul de decizie logic indică ramura pe care se va continua execuţia algoritmului în funcţie de îndeplinirea (ramura Da) sau neîndeplinirea (ramura Nu) unei condiţii. Condiţia care se va înscrie în blocul de decizie logic va fi o expresie logică a cărei valoare poate fi una dintre valorile "adevărat" sau "fals". Blocul de decizie aritmetic va hotărî ramura de continuare a algoritmului în funcţie de semnul valorii expresiei aritmetice înscrise în acest bloc, care poate fi negativă, nulă sau pozitivă.

Blocurile de conectare marchează întreruperile săgeţilor de legătură dintre blocuri, dacă din diverse motive s-au efectuat astfel de întreruperi (Fig.1.2.1.h).Pentru exemplificare vom da în continuare două scheme logice, corespunzătoare unor algoritmi pentru rezolvarea problemelor P1.2.1 şi P1.2.2.
P1.2.1. Să se rezolve ecuaţia de grad doi aX2+bX+c=0 (a,b,c(R _i a(0).
Metoda de rezolvare a ecuaţiei de gradul doi este cunoscută. Ecuaţia poate avea rădăcini reale, respectiv complexe, situaţie recunoscută după semnul discriminantului d = b2 - 4ac.

Algoritmul de rezolvare a problemei va citi mai întâi datele problemei, marcate prin variabilele a, b şi c. Va calcula apoi discriminantul d şi va continua în funcţie de valoarea lui d, aşa cum se poate vedea în fig.1.2.2.

Nota explicativa
Referatele si lucrarile oferite de Referate.ro au scop educativ si orientativ pentru cercetare academica.

Iti recomandam ca referatele pe care le downloadezi de pe site sa le utilizezi doar ca sursa de inspiratie sau ca resurse educationale pentru conceperea unui referat nou, propriu si original.

Referat.ro te invata cum sa faci o lucrare de nota 10!
Filmele zilei
Linkuri utile
Programeaza-te online la salonul favorit Descarca gratuit aplicatiile pentru iOS si Android Filmulete haioase Filme, poante si cele mai tari faze Jocuri Cele mai tari jocuri de pe net Referate scoala Resurse, lucrari, referate materiale pentru lucrari de nota 10 Bacalaureat 2019 Vezi subiectele examenului de Bacalaureat din 2019 Evaluare Nationala 2019 Ultimele informatii despre evaluare nationala
Toate imaginile, textele sau alte materiale prezentate pe site sunt proprietatea referat.ro fiind interzisa reproducerea integrala sau partiala a continutului acestui site pe alte siteuri sau in orice alta forma fara acordul scris al referat.ro. Va rugam sa consultati Termenii si conditiile de utilizare a site-ului. Informati-va despre Politica de confidentialitate. Daca aveti intrebari sau sugestii care pot ajuta la dezvoltarea site-ului va rugam sa ne scrieti la adresa webmaster@referat.ro.
Confidentialitatea ta este importanta pentru noi

Referat.ro utilizeaza fisiere de tip cookie pentru a personaliza si imbunatati experienta ta pe Website-ul nostru. Te informam ca ne-am actualizat politica de confidentialitate pentru a integra cele mai recente modificari privind protectia persoanelor fizice in ceea ce priveste prelucrarea datelor cu caracter personal. Inainte de a continua navigarea pe Website-ul nostru te rugam sa aloci timpul necesar pentru a citi si intelege continutul Politicii de Cookie. Prin continuarea navigarii pe Website-ul nostru confirmi acceptarea utilizarii fisierelor de tip cookie conform Politicii de Cookie. Nu uita totusi ca poti modifica in orice moment setarile acestor fisiere cookie urmarind instructiunile din Politica de Cookie.


Politica de Cookie
Am inteles