Proprietatile algoritmilor
1. Claritatea: proprietatea algoritmului de a descrie cu exactitate (fara ambiguitati) pasii care trebuiesc parcursi pentru rezolvarea unei probleme.
De exemplu, nu putem scrie un algoritm pentru urmatoarea problema: Daca Ionut ia nota 10 la examenul de bacalaureat la matematica fie urmeaza cursurile la Automatica fie urmeaza cursurile la Telecomunicatii.
De asemenea, e bine ca un algoritm sa fie clar pentru ca, in cazul in care il implementam intr-un limbaj de programare si rulam programul, sa stim locul de unde ar putea proveni greseala.
2. Corectitudinea: reprezinta proprietatea algoritmului de a prezenta o solutie corecta a problemei date. Din acest motiv este preferabil ca algoritmii sa se bazeze pe fapte si relatii matematice demonstrabile.
De exemplu: Se dau valorile pentru lungimea si latimea unui dreptunghi. Sa se gaseasca aria dreptunghiului.
3. Caracterul determinist: reprezinta proprietatea algoritmului de a furniza intotdeauna aceiasi solutie pentru aceleasi date de intrare.
Un algoritm nu trebuie sa furnizeze la prima executie pentru problema 2+5=? rezultatul 7 iar la o alta executie rezultatul -7 sau alt rezultat.
4. Verificabilitatea: reprezinta proprietatea algoritmilor ca in orice moment, in orice etapa sa i se poata verifica corectitudinea de catre o persoana umana.
De exemplu, atunci cand un algoritm este transpus intr-un limbaj de programare, programatorul poate sa execute programul dupa terminarea fiecarei etape a problemei pe care doreste sa o rezolve iar in felul acesta sa elimine inca din faza de proiectare cea mai mare parte din erori sau toate. De asemenea, precizam faptul ca majoritatea limbajelor de programare prezinta o functie de executarea a programului pas cu pas si de urmarire a rezultatelor intermediare care se obtin.
5. Optimalitatea: proprietatea algoritmilor de a gasi o solutie optima pentru rezolvarea problemei atat din punct de vedere a timpului de executie cat si a memoriei ocupate.
De exemplu, daca dorim sa realizam suma primelor n numere naturale: 1+2+3+...+n
metoda 1: folosim formula n*(n+1)/2
metoda 2: adunam numerele 1,2,3,..,n pe rand
Metoda 1 este cea optima atat din punct de vedere al timpului de executie (o singura instructiune) cat si a memoriei ocupate de variabilele pe care le folosim.
6. Eficienta: reprezinta proprietatea unui algoritm de a se termina intr-un numar finit si "rezonabil" de pasi chiar daca aceasta solutie nu este cea optima. Un algoritm este ineficient daca se termina dupa un timp mai lung sau dorit.
De exemplu, daca un programul in care a fost implementat algoritmul are ca limita de timp pentru rulare 1 secunda si el se termina in 2 secunde, atunci algoritmul nu este eficient.
7. Existenta unei intrari: deoarece un algoritm trebuie sa rezolve o problema pe baza unor date cunoscute, existenta acestor date de intrare este obligatorie.
8. Existenta unei iesiri: utilitatea unei algoritm nu se vede daca nu furnizeaza o solutie. De exemplu, daca implementam intr-un limbaj de programare algoritmul pentru suma a doua numere si programatorul uita sa scrie instructiunea pentru afisarea rezultatului pe ecran, utilizatorul care executa programul nu poate vedea solutia problemei.
9. Generalitatea: un algoritm se scrie pentru o clasa de probleme nu doar pentru o problema.
De exemplu, problema urmatoare este un caz particular.
Maria are la informatica notele 9 si 8. Ce medie va avea Maria?
Pe cand urmatoarea este o problema enuntata pentru un caz general:
La o disciplina sunt doua note x si y. Care este media pentru disciplina respectiva?
10. Finititudinea: reprezinta proprietatea algoritmilor de a se termina dupa un numar finit de pasi. Daca un algoritm ruleaza la nesfarsit atunci trebuie introdusa o conditie la indeplinirea careia algoritmul sa se opreasca.
De exemplu: Sa se afiseze divizorii naturali numarului x.
In acest caz numarul de divizorii sunt
