Notiunea de algoritm

Notiunea de algoritm

Cuvantul "algoritm" exprima o notiune matematica foarte veche si este de origine araba. El deriva din numele matematicianului "Abu Ja'far Mohammed ibn Mûsa al Horezmi", care a scris o celebra carte "Kitab al jabr w'al - muquabala". Din titlul acestei carti provine si cuvantul "algebra".

Initial, termenul "algorism" era folosit in evul mediu cu intelesul de proces al efectuarii operatiilor aritmetice cu ajutorul cifrelor arabe. Se presupune ca din asocierea cuvantului algorism cu domeniul lui de referinta, aritmetica, a rezultat termenul "algoritm".

Incepand cu anul 1950, in toate manualele de specialitate, cuvantul algoritm era frecvent asociat cu procesul de aflare a celui mai mare divizor comun a doua numere naturale, asa numitul "algoritm al lui Euclid".

Totodata, regulile operatiilor aritmetice poarta denumirea de algoritmi de efectuare a operatiilor respective.

Un algoritm este compus din unul sau mai multi pasi, un pas reprezentand efectuarea unei singure operatii din sirul celor care alcatuiesc algoritmul.

Exemplul 1.1

a. Algoritmul impartirii intregi a doua numere naturale

Se stie ca impartirea intreaga a doua numere consta din efectuarea unor scaderi succesive, pana cand descazutul devine mai mic decat scazatorul.

Pentru fiecare scadere care se efectueaza, descazutul este rezultatul scaderii precedente, iar scazatorul este impartitorul. Rezultatul ultimei scaderi efectuate este tocmai restul impartirii celor doua numere, iar numarul de scaderi efectuate reprezinta catul impartirii.

Pasii acestui algoritm sunt constituiti de operatiile de scadere si de operatiile de comparare a descazutului cu scazatorul. Este evident ca sirul acestor operatii este finit, deoarece descazutul se micsoreaza cu fiecare noua scadere, in timp ce scazatorul ramane neschimbat.

Fie, de exemplu, numerele 23 si 7. Pasii algoritmului care duc la aflarea catului si restului impartirii sunt prezentati in tabelul 1.1. 

Tabelul 1.1

Numarul de scaderi efectuate este 3, iar rezultatul ultimei scaderi efectuate este 2, deci catul impartirii numarului 23 prin 7 este 3, iar restul este 2.

b. Algoritmul lui Euclid

Acest algoritm se foloseste pentru obtinerea celui mai mare divizor comun a doua numere naturale. Notam cele doua numere naturale a si b.

Algoritmul consta din efectuarea unui sir de impartiri intregi pana cand se obtine un rest nul. Pentru fiecare impartire care se efectueaza, impartitorul este restul impartirii precedente, iar deimpartitul este impartitorul din impartirea precedenta. Impartitorul din ultima impartire efectuata constituie cel mai mare divizor comun al celor doua numere.

Pasii acestui algoritm sunt constituiti din operatiile de impartire si de verificare a anularii restului. Deoarece restul unei impartiri este mai mic decat impartitorul, sirul de resturi al impartirilor succesive este strict descrescator, astfel ca numarul de impartiri din algoritm este finit.

Fie, de exemplu, numerele 78 si 30. Pasii algoritmului care conduc la aflarea celui mai mare divizor comun al acestor numere sunt prezentati in tabelul 1.2. Algoritmul se incheie in momentul obtinerii restului zero, iar rezultatul in acest caz este 6.

Tabelul 1.2

Test de autoevaluare 1.1

Alegeti varianta corecta pentru urmatoarele intrebari. Fiecare intrebare valoreaza 20 de puncte.

Adevarat / Fals

1. Notiunea de algoritm a aparut odata cu aparitia primelor calculatoare personale.............................. A/F

2. Termenul de algoritm se poate defini in termeni matematici foarte exacti............................... A/F

3. In cazul algoritmului de impartire prin scaderi repetate, numarul de scaderi efectuate va reprezenta, in final, catul impartirii............. A/F

4. Aplicand algoritmul lui Euclid pentru numerele 84 si 20, vor fi efectuate 2 impartiri............................A/F

5. Algoritmul lui Euclid nu se poate aplica daca primul numar este mai mic decat al doilea..............................A/F