L1. Notiunea de algoritm

Istoric. Definitie

Cuvantul algoritm provine de la numele unui matematician arab (Mohammed ibn-Musa al-Khowarizmi) a carui lucrari au fost traduse in latina sub numele de Algoritmus.

Definitia actuala a cuvantului algoritm :

• Ansamblu de simboluri folosite în matematică și în logică, permițând găsirea în mod mecanic (prin calcul) a unor rezultate.


• Succesiune de operații necesare în rezolvarea unei probleme oarecare

Din punctul de vederea al informaticii, algoritmul reprezinta rezolvarea etapizata, in pasi mici, elementari, a unei probleme.

Scopul folosirii algoritmului este aplicarea lui la o serie pe probleme care au aceeasi metoda de rezolvare; adica, pentru orice dateale problemei, algortimul trebuie sa se incheie cu un raspuns.

Un exemplu in acest sens este acuatia de gradul I. Exista o infinitate de ecuatii de gradul I dar toate se subscriu aceleiasi ecuatii generice A*X+B=0. Algoritmul trebuie sa rezolve aceasta ecuatie generica pentru a obtine rezultate corecte pentru intreaga clasa se ecuatii de gradul I sau sa anunte eroarea in cazul in care simbolul A ar avea valoarea 0.

Caracteristici

Deducem de aici o serie de proprietati pe care un algoritm corect trebuie sa le indeplineasca:

• sa aiba caracter de generalitate: sa rezolve o intreaga clasa de probleme de acelasi gen (pentru orice date de intrare)


• sa aiba finitudine: sa ofere un raspuns la problema si sa se incheie in timp util


• sa fie clar: calculul/etapele sa fie descriese intr-o maniera fara dubii

DATE DE INTRARE -> ALGORITM -> DATE DE IESIRE

Reprezentarea algoritmilor

S-au identificat cateva structuri folosite in descrierea unui algoritm:

• secventa: pasii sa se execute unul dupa altul


• testul: in cazul in care rezolvarea trebuie sa raspunda unei intrebari sa putem aplege traseul logic ce trebuie urmat


• repetitia: sa putem repeta o anumita secventa daca algoritmul o cere

De asemeni,  pentru exprimarea algoritmilor s-au incercat metode care sa poata fi intelese de toti. Iata cateve dintre ele:

• scheme logice: metoda grafica care specifica traseul ce trebuie urmat


• pseudocod: un set de reguli de scriere , in principiu in limba engleza; pt elevi s-a simplificat, folosindu-se aceleasi notatii si limba romana (o varianta care se poate folosi in laborator gasiti la http://www.haskell.org/haskellwiki/Rodin)


• limbaj de programare: mult mai strict ca exprimare dar folosind aceleasi concepte.

Limbajul RODIN - prezentare succinta

Obs: Nu exista declaratii de variabile

Programul principal

• {... instr; ...}

Instructiuni de citire/afisare

• citeste variabila;


• scrie expresie;


• text ".... text...";

Atribuirea

• fie variabila = expresie;

Operatori logici:

• SAU, SI,

Instructiune de test

• daca (COND) atunci instr altfel instr;

Instructiuni repetitive

• cat timp (COND) {instr;...};


• executa {inst1; instr2;} atat cat (COND);


• repeta {instr1; instr2;...} pana cand (COND)


• pentru (atribuire; test ;pasul urm) {instr;...};