Lectia 1

NOȚIUNEA DE ALGORITM

Definiție: Algoritmul[1] este alcătuit dintr-o succesiune de etape, numite pași, care trebuie parcurse într-o anumită ordine astfel încât plecând de la datele inițiale ale problemei, într-un timp finit sa ajungem la rezultatul dorit.

Algoritmul este noțiunea fundamentală a informaticii. Totul este construit în jurul algoritmilor (şi al structurilor de date, cum ar fi listele sau grafurile).

Definiție: Descrierea unui algoritm de rezolvare a unei probleme sau a unei situații date într-un limbaj de programare se numește program sau cod sursă.

Cele mai importante proprietăți ale unui algoritm sunt următoarele

· Corectitudinea - este proprietatea algoritmului de a furniza o soluție corectă a problemei date. În acest sens este de dorit ca algoritmii să se bazeze pe fapte și relații matematice demonstrabile.

· Caracterul univoc sau determinist - plecând de la un set de date inițial anume, rezultatul este unic, sau altfel spus, repetarea execuției algoritmului duce întotdeauna la aceleași rezultate.

· Generalitatea - este proprietatea unui algoritm de a rezolva o clasă sau categorie de probleme, și nu doar o singură problemă particulară. Spre exemplu, un algoritm care rezolvă doar ecuația x² + 5x − 6 = 0 este mai puțin general decât unul care rezolvă ecuația de gradul II care are următoare formă generală ax² + bx + c = 0, oricare ar fi valorile lui a,b,c.

· Claritatea - proprietatea algoritmului de a descrie cu exactitate și fără ambiguități pașii care trebuiesc parcurși în rezolvarea problemei.

· Verificabilitatea - acea proprietate a algoritmilor care permite ca fiecare pas să poată fi verificat într-un timp rezonabil de către om, folosind mijloace de validare de încredere.

· Optimalitatea - proprietatea unui algoritm de a se termina după un număr minim de pași. Spre exemplu, dacă se cere să se calculeze suma primelor n numere naturale, putem aplica formula de calcul, și astfel algoritmul se termină într-un singur pas, pe când dacă am aduna toate numerele de la 1 la n, el s-ar termina abia în n pași, și deci nu ar fi optim.

· Finitudinea - este proprietatea algoritmului de a se termina într-un număr finit de paşi. Există şi algoritmi care nu se termină într-un număr mărginit de paşi, dar aceştia se numesc "metode algoritmice".

· Eficienţa - este proprietatea unui algoritm de a se termina nu numai într-un număr finit, ci şi "rezonabil" de paşi, chiar dacă acesta nu este cel mai mic posibil (nu este optim). Algorimul este ineficient şi dacă rezultatul se obţine într-un timp mai lung decât cel dorit sau permis.

· Existenţa unei intrări (datele de prelucrat). Întrucât operatorii se aplică unui operand (sau şi mai multor operanzi deodată), este de neconceput un algoritm fără niciun operand. Intrările permise formează împreună un set (mulţime) specific de obiecte sau valori, care se numeşte "domeniul" algoritmului.

· Existenţa unei ieşiri (rezultatele). Este de neconceput un algoritm care nu are nicio ieşire, deoarece în acest caz intră în discuţie însăşi utilitatea sa.

Operaţiile care apar în cadrul unui algoritm sunt:

· Operaţii de intrare ieşire: datele de intrare se vor citi de la tastatră sau din fişiere text şi ele reprezintă valorile iniţiale cu care se incepe rezovarea unei probleme. Datele de ieşire reprezintă rezultatul problemei după parcurgerea algoritmului şi aceste fie vor fi afişate pe ecran, fie vor fi scrise în fişiere text.

· Operaţia de atribuire: reprezintă operaţia în urma căreia valoarea unei expresii (matematice, logice sau relaţionale) este memorată într-o variabilă

· Operaţia de decizie: determină valoarea de adevăr a unei expresii logice şi în funcţie de rezultatul obţinut se continuă execuţia programului pe una din cele doua ramificatii posibile(adevărat sau fals).

[1] Cuvântul are la origine numele matematicianului persan Al-Khwarizmi