Algoritmi

Notiunea de algoritm este fundamentala in informatica (asa cum este in matematica notiunea de multime). Astfel incat putem intalni diverse definitii ale algoritmului. De exemplu, Enciclopædia Britannica da urmatoarea definitie: 'O procedura sistematica ce produce intr-un numar finit de pasi raspunsul la o intrebare sau rezolvarea unei probleme'. Dictionarul de calculatoare & Internet (editura Teora, 1999) defineste algoritmul astfel: 'O procedura matematica sau logica de rezolvare a unei probleme. O metoda de a gasi raspunsul corect la o problema dificila prin impartirea ei intr-un anumit numar de etape simple.'

Caracteristicile unui algoritm sunt:

determinism (claritate): succesiunea pasilor este precis determinata;

finitudine (eficacitate): numarul pasilor descrisi este finit;

generalitate (universalitate): rezolva orice problema din clasa de probleme pentru care a fost elaborat (pentru orice set de date de intrare).

Algoritmii se folosesc in orice limbaj, inclusiv in cel natural. O reteta de bucatarie este un algoritm:

'Se amesteca 30g drojdie cu o lingurita zahar. Se amesteca totul cu 4 linguri faina si 4 linguri lapte. Pauza timp de 15 minute. Se amesteca totul cu 400g faina si doua pahare lapte timp de 5 minute. Pauza timp de 20 minute. Se unge tava. Se pune amestecul in tava. Se pun fructele peste amestec. Se da la cuptor. Pauza timp de 20 minute. Se scoate din cuptor. Pauza timp de 5 minute. Se taie si se mananca'.

Cuvantul algoritm provine din traducerea in latina ("Algoritmi de numero Indorum") a titlului scrierii matematicianului arab Al-Horezmi ("Al-Horezmi despre numararea indiana"). Abu Abdullah Mohamed Ibn Musa Al-Horezmi (770 - 840) a fost unul dintre cei mai mari matematicieni ai lumii. A trait in Bagdad, in timpul califului Mamun. A fondat cateva din ramurile matematicii. Este faimos si ca astronom. Cea mai mare realizare a sa o constituie introducerea conceptului de algoritm. O alta de rang asemanator este introducerea cifrei zero.

Algoritmii se intalnesc mereu in viata obisnuita. Actionarea unor dispozitive sau masini se face conform algoritmilor (apas butonul de apel al liftului, astept pana cand ajunge, deschid usile, intru, inchid usile, comand oprirea urmatoare, astept pana ajung, deschid usile, ies, inchid usile). Chiar si normele de comportare sunt algoritmi (deschid usa salii de asteptare, intru, inchid usa, salut persoanele aflate aici, daca exista un scaun liber, atunci ma asez, astept pana imi vine randul).

Prescolarii invata algoritmi matematici: ca sa adun pe 7 cu 4, folosesc numaratoarea astfel: trec in dreapta 7 bile de pe prima linie, trec in dreapta 4 bile de pe a doua linie, numar cate bile am in total in dreapta.

In gimnaziu ne intalnim cu algoritmul lui Euclid, care stabileste este cel mai mare divizor comun a doua numere naturale. Se observa o diferenta fundamentala fata de algoritmul precedent: acesta rezolva o clasa infinita de probleme (numerele naturale pot fi oricare), pe cand cel precedent rezolva o singura problema (cum adun pe 7 cu 4, dar nu ma invata cum adun pe 2 cu 5).

Exista intotdeauna un algoritm de rezolvare a unei clase finite de probleme. Este varianta exhaustiva de rezolvare, adica o tabela de valori asociata tuturor cazurilor posibile. De exemplu, problema determinarii rezultatului inmultirii a doua numere cel mult egale cu 10 a dus la celebra tabla a inmultirii pe care am invatat-o in clasa a doua.

In general, nu este usor a raspunde la problemele care au numar infinit de valori de luat in considerare. De exemplu: 'este numarul n (natural) prim ?' sau 'care este cel mai mic multiplu comun a doua numere naturale ?'. De aceea algoritmii care rezolva astfel de probleme sunt importanti si sunt studiati in scoala. 'Elementele' lui Euclid, aparuta in anul 300, contin un algoritm care afla cel mai mare divizor comun a doua numere naturale. Gasirea de algoritmi eleganti (simpli si eficienti) este unul din scopurile cercetarii in informatica.

Se disting doua tipuri de algoritmi: cei care furnizeaza un raspuns de tipul da/nu se numesc decizionali. Problemele rezolvate de ei se numesc probleme de decizie ('este n prim ?'). Cei care conduc la o valoare numerica se numesc calculationali. Problemele rezolvate se numesc probleme de calcul ('care este cel mai mic multiplu comun al numerelor a si b ?').

Exista clase de probleme pentru care nu se cunosc algoritmi de rezolvare (mai ales daca se impun restrictii asupra metodei acceptate). De exemplu, doua probleme din vremea lui Euclid, care trebuie rezolvate cu ajutorul riglei negradate si al compasului: 'sa se construiasca un patrat cu aria egala cu cea a unui cerc dat' si 'sa se deseneze trisectoarea unui unghi' au fost studiate secole de-a randul, pana cand s-a demonstrat ca sunt imposibile. La trecerea in secolul al XX-lea, David Hilbert (matematician german) a propus 23 de probleme de rezolvat in urmatoarea suta de ani. A doua problema din lista cerea investigarea consistentei axiomelor aritmeticii. Multi matematicieni aveau dubii asupra rezolvarii acestei probleme, pana in 1931, cand Kurt Gödel (logician austriac) a demonstrat surprinzatorul rezultat ca exista enunturi aritmetice indecidabile (nu se pot nici afirma si nici nega), deoarece conduc la o procedura decizionala infinita (deci nu duc la un algoritm). Intr-un efort fara succes de a afla cel putin care sunt aceste enunturi, Alan Turing (matematician si logician englez) a definit riguros conceptul de algoritm. Descrierea sa pentru caracteristicile esentiale ale unei masini care produce algoritmi (masina Turing) a devenit fundamentala pentru informatica. Programele de calculator sunt tipuri speciale de algoritmi. Decidabilitatea si calculabilitatea lor sunt probleme centrale ale scrierii programelor.

Verificarea corectitudinii algoritmilor. Dupa elaborarea unui algoritm, se trece la verificarea corectitudinii acestuia. Adica, ar trebui parcurs algoritmul pentru orice problema din clasa de probleme pentru care a fost scris, si vazut daca furnizeaza rezultate corecte. Acest lucru este imposibil, daca algoritmul rezolva o clasa infinita de probleme. De aceea, se recomanda urmatoarele verificari ale algoritmilor simpli:

daca se incheie dupa un numar finit de pasi (se verifica structurile repetitive);

daca selectiile s-au construit corect (se verifica structurile alternative);

daca se asigura valori pentru toate datele folosite (se verifica daca tuturor datelor li se atribuie valori).

Dupa incheierea cu succes a verificarilor de mai sus, se trece la testul intregului algoritm, pe diferite seturi de date, de obicei cazuri limita.