Notiunea de algoritm

Notiunea de algoritm

In cele ce urmeaza ne vom limita la o introducere intuitiva, practica, a notiunii de algoritm. O definitie riguroasa, matematica, presupune alte notiuni a caror prezentare ar ingreuna expunerea si ne-ar abate de la scopul urmarit in acest capitol.

Definitia 2.1

Prin algoritm se intelege un sir de reguli care, aplicat la o anumita clasa de probleme de acelasi tip, conduce de la conditiile initiale ale problemei, la solutia problemei respective, cu ajutorul unor operatii succesive, in numar finit si unic determinate.

Exemplul 2.1

Algoritmul lui Euclid pentru calculul celui mai mare divizor comun a doua numere intregi.

Algoritmul care descrie teorema lui Cramer pentru rezolvarea sistemelor de ecuatii liniare.

Definitia 2.2

Se numeste informatie admisibila a unui algoritm, o informatie initiala pentru care algoritmul respectiv este aplicabil. Totalitatea informatiilor admisibile ale unui algoritm formeaza domeniul algoritmului.

Exemplul 2.2

Domeniul algoritmului care descrie teorema lui Cramer pentru rezolvarea sistemelor de ecuatii liniare, este format din sisteme liniare de n ecuatii cu n necunoscute avand matricea nesingulara.

Observatia 2.1

Un algoritm poate fi definit ca o functie : D F , unde D este domeniul algoritmului , iar F este multimea informatiilor finale ce se obtin prin aplicarea algoritmului tuturor informatiilor din D (F (D )). Sirul de reguli ce constituie algoritmul , arata cum aceasta functie poate fi calculata efectiv.

Orice algoritm trebuie sa aiba urmatoarele caracteristici importante:   

Generalitatea (Universalitatea) Aceasta inseamna ca, un algoritm nu rezolva o singura problema, ci o clasa de probleme de acelasi tip, deci este aplicabil oricarei informatii din domeniul sau D

Finitudinea (Eficacitatea) Aceasta inseamna ca, numarul transformarilor ce trebuie aplicate unei informatii admisibile pentru a obtine informatia finala corespunzatoare, este finit.

Unicitatea (Claritatea) Acesta inseamna ca toate transformarile prin care trece informatia initiala, pana la obtinerea informatiei finale, sunt univoc determinate de regulile algoritmului.

Orice algoritm poate fi compus din algoritmi mai simpli. Compunerea algoritmilor se poate face in doua moduri:

compunerea prin suprapunere;

compunerea prin succesiune.

Definitia 2.3

Se numeste compunere prin suprapunere a algoritmilor si , algoritmul in care algoritmul face parte din procesul de calcul al algoritmului

Exemplul 2.3

Sa consideram metoda lui Newton pentru aproximarea unei solutii a ecuatiei algebrice P_n(x) = 0, unde P_n(x) este un polinom de gradul n, stiind ca aceasta solutie este izolata in intervalul (a, b). Daca se considera x₀ I (a, b) ca valoare de pornire, atunci

Calculul aproximantelor x_k se continua pana cand se obtine precizia ceruta. Daca se noteaza prin algoritmul metodei lui Newton si prin algoritmul de calcul al valorii unui polinom intr-un punct, atunci algoritmul problemei considerate este

Definitia 2.4

Se numeste compunere prin succesiune a algoritmilor si , algoritmul , in care informatia finala a lui face parte din domeniul algoritmului ().

Exemplul 2.4

Se cere calculul lui P_n(d), unde P_n(x) este un polinom de gradul n, iar d este c.m.m.d.c. a doua numere intregi. Daca se noteaza cu algoritmul lui Euclid pentru calculul c.m.m.d.c. a doua numere intregi si prin algoritmul pentru calculul valorii polinomului P_n(x) intr-un punct dat, algoritmul pentru calculul lui P_n(d) este

Pentru exprimarea unui algoritm se utilizeaza urmatoarele operatii:

operatii de calcul: adunarea, scaderea, inmultirea, impartirea, ridicarea la putere;

operatii de atribuire: efectul unei operatii de atribuire consta in faptul ca unei variabile i se atribuie o valoare;

operatii de decizie: efectul unei operatii de decizie consta in determinarea valorii logice de adevar a unei propozitii.

Deoarece algoritmii se studiaza, in principal, pentru rezolvarea problemelor cu ajutorul unui sistem de calcul, ca operatii in descrierea unui algoritm sunt considerate urmatoarele:

operatii de pornire si oprire a procesului de calcul;

operatii de introducere si extragere a informatiilor;

operatii de calcul si atribuire;

operatii de decizie.

In functie de operatiile pe care le contin, algoritmii pot fi impartiti in doua clase:

algoritmi liniari;

algoritmi ramificati.

Un algoritm este liniar daca nu contine nici o operatie de decizie.

Un algoritm este ramificat daca contine cel putin o operatie de decizie.

Prin ciclu se intelege o succesiune de operatii care se repeta in aceeasi ordine de un anumit numar de ori. Dupa cum contin sau nu contin cicluri, algoritmii ramificati sunt de doua categorii:

algoritmi ciclici;

algoritmi aciclici.

Numarul de repetari ale unui ciclu poate fi fix sau variabil. Astfel, putem avea :

algoritmi ciclici cu un numar cunoscut de repetari;

algoritmi ciclici cu un numar necunoscut de repetari.