Ingineria Sistemelor de Programe - Capitolul 3

1. Definirea unui algoritm. Proprietati.

Un algoritm reprezintă, în mod uzual, o metodă de descriere a rezolvării unor probleme. Mai exact, un algoritm reprezintă un ansamblu finit de operaţii care se aplică asupra unor informaţii numite mărimi sau date de intrare ale unei probleme in vederea obţinerii unor rezultate numite mărimi sau date de ieşire ale acesteia.

În practica utilizării algoritmilor se disting două etape : descrierea unui algoritm si execuţia algoritmului. Pentru a descrie corect un algoritm, trebuie ales un limbaj adecvat de descriere, cu o suficientă putere expresivă, care să poată descrie operaţiile ce se pot efectua asupra datelor problemei. Execuţia unui algoritm se referă la componenta pragmatică a limbajului de descriere; în mod uzual un algoritm trebuie să poată fi executat de către o persoană care are cunostinţe din domeniul problemei de rezolvat, folosind doar creionul si hârtia.

Unul dintre primele limbaje de descriere a algoritmilor a fost limbajul natural. Acesta are o mare flexibilitate şi permite descrierea multor tipuri de operaţii. În mod uzual, se folosesc propoziţii pentru a descrie fiecare operaţie din cadrul algoritmilor. Pentru a evidenţia succesiunea operaţiilor, acestea se numerotează cu numere crescătoare. O asemenea operaţie descrisă printr-o propoziţie numerotată se mai numeşte pas. În acest mod, un algoritm este reprezentat de o secvenţă de paşi.

Exemplul 1.1. Să se determine cel mai mare divizor comun a două mumere întregi folosind algoritmul lui Euclid.

Analiza problemei :

Se notează cu m şi n numerele pentru care trebuie determinat cel mai mare divizor comun. Astfel, variabilele m şi n reprezintă datele sau variabile de intrare pentru problemă. Algoritmul lui Euclid presupune efectuarea repetată a unor operaţii de împărţire cu rest, până când se obţine un rest zero. Fie de exemplu: m=12, n=16:

12:16=0 rest 12 (r1=12)

16 :12=1 rest 4 (r2=4)

12 :4=3 rest 0 (r3=0)

Ultimul rest diferit de zero (r2=4) va fi solutia problemei.

Pentru generalizare se noteză următoarele variabile: m pentru desemnarea deîmpărţitului, n pentru desemnarea împărţitorului şi r pentru desemnarea restului (câtul nu intervine în algoritm). Se observă faptul că la fiecare pas, în afară de primul, valorile deîmpărţitului m si împărţitorului n se determină din valorile pasului precedent: noua valoare a deîmpărţitului m este vechea valoare a împărţitorului n şi noua valoare a împărţitorului n este vechea valoare a restului r. Astfel, ultimul rest nenul va fi memorat în variabila n, care devine si o variabilă de ieşire.

Descrierea algoritmului:

1. Se citesc de la intrare valori pentru m şi n.

2. Se împarte m la n şi se obţine un rest r.

2. Dacă r=0, atunci scrie la ieşire c.m.m.dc =n şi algoritmul se termină.

3. Dacă r<>0, atunci se atribuie: m=n, n=r şi se face salt la pasul 2.

4. Sfârşit.

Se observă că algoritmul din exemplul precedent se termină la pasul 4. O primă întrebare se refeă la faptul dacă după un număr finit de paşi, restul devine zero pentru ca algoritmul să se termine. O argumentare la această întrebare este următoarea afirmaţie: şirul de resturi: r1, r2, r3, , este un şir descrescător de numere întregi pozitive şi care tinde la zero.

Pe baza examinării algoritmului precedent, se pot descrie principalele caracteristici ale unui algoritm:

1. Generalitatea unui algoritm, se referă la faptul că în mod uzual algoritmii descriu rezolvarea unor categorii de probleme, nu a unor probleme singulare. În exemplul precedent, algoritmul descrie determinarea celui mai mare divizor comun a oricăror numere întregi, nu numai a numerelor 12 şi 16.

2. Cracterul finit al algoritmului, reprezintă cerinţa ca numărul de operaţii efectuate pentru determinarea mărimilor de ieşire să fie finit, altfel algoritmul nu poate să determine soluţiile problemei aferente.

3. Claritatea algoritmului, se referă la cerinţa ca operaţiile din algoritm să fie clare şi concise, fiind astfel înlăturate nedeterminismul şi ambiguităţile anumitor operaţii.

4. Intrarea în algoritm, este reprezentată introducerea sau citirea a zero sau mai multe mărimi care trebuie specificate algoritmului, pantru ca el să poată fi executat. În mod uzual intrarea în algoritm se face prin intermediul unor varabile de intrare, care la începutul execuţiei algoritmului vor fi iniţializate cu valorile de intrare curente.

5. Ieşirea din algoritm, constă în extragerea sau scrierea unei mărimi sau mai multor mărimi de ieşire care sunt determinate prin execuţia algoritmului, mărimi ce reprezintă rezultatele problemei aferente algoritmului. Ieşirea se realizează în mod uzual prin intermediul unor variabile de ieşire. Algoritmii pot să nu aibe mărimi de intrare, dar trebuie obligatoriu să aibe mărimi de ieşire adică rezultate, pentru că acestea reprezintă soluţiile problemelor aferente.

Toate caracteristicile, în fara caracteristicii 3, sunt verificate de algoritmul din exemplul 1. Ambiguităţile care pot apare se referă la semnificaţia operaţiilor efectuate în algoritm: de exemplu, nu se specifică dacă valorile variabilelor m şi n sunt întregi sau reale. În cazul în care valorile sunt reale, nu are sens efectuarea unor operaţii cu rest.

În general, limbajul natural nu permite eliminarea completă a ambiguităţilor operaţiilor. Din acest motiv, pentru specificarea algoritmilor se utilizează limbaje de descriere cu o semantică mai puternică.

2. Limbajul algoritmic

Limbajul algoritmic (sau limbajul pseudocod) reprezintă o metodă uzuală de descriere a algoritmilor, mai formalizată decât limbajul natural. Avantajul constă în faptul că descrierea operaţiilor unui algoritm poate fi făcută mai clar şi cu mai puţine ambiguităţi decât în cazul utilizării limbajului natural.

2.1 Elemente de gramatică

Este necesară prezentarea unui set minim de reguli pentru a putea defini sintaxa acestui limbaj.

Majoritatea propoziţiilor din limbaj sunt propoziţii imperative, adică instrucţiuni, fiecare având o semnificaţie foarte clară şi desemnând operaţii precise. Puţinele propoziţii declarative au doar rolul de a delimita din punct de vedere sintactic algoritmii, sau de a specifica în cazul funcţiilor şi procedurilor modul în care se face transferul de informaţie între funcţia/procedura apelată şi algoritmul apelant.

În afara acestor propoziţii, în cadrul algoritmilor pot apare propoziţii dintr-o categorie aparte, numite comentarii. Comentariile nu sunt luate în considerare la execuţia algoritmilor, ele având doar un rol de explicare a anumitor operaţii din cadrul acestora. Un comentariu începe cu şirul de caractere // şi se termină la sfârşitul liniei curente.

Desemnarea acţiunilor din cadrul propoziţiilor imperative, adica a instrucţiunilor, se face prin intermediul unuia sau a mai multor cuvinte cheie. Acestea sunt cuvinte rezervate şi nu pot fi utilizate de către programator în alte scopuri. A doua categorie importantă de cuvinte sunt cuvintele utilizator, numite şi identificatori, care sunt nume date de programatori anumitor obiecte din algoritm. Pentru a deosebi cuvintele din cele două categorii, cuvintele cheie sunt subliniate. Identificatorii sunt şiruri de caractere alfabetice, care încep întotdeauna cu o literă.

În mod curent, identificatorii desemnează nume de variabile. Întrucât o mare parte a problemelor, a căror rezolvare poate fi descrisă algoritmic, sunt de natură ştiinţifică, o parte a noţiunilor şi conceptelor din matematică au fost preluate în limbajul algoritmic. Astfel, noţiunea de variabilă reprezintă o entitate cu două atribute: numele variabilei, care este un identificator, şi valoarea sa curentă sau instantanee. În timpul execuţiei unui algoritm, valoarea curentă a unei variabilă se poate modifica. Acţiunea prin care unei variabile i se asociază o valoare curentă se numeşte asignarea variabilei respective.

O altă noţiune utilizată este cea de expresie. O expresie este formată din operanzi, operatori şi perechi de paranteze rotunde. Operanzii pot fi constante, variabile şi apeluri de funcţii. Operatorii reprezintă operaţiile elementare ce se pot efectua asupra operanzilor.

Evaluarea unei expresii presupune aplicarea operatorilor asupra operanzilor într-o anumită ordine, pentru obţinerea rezultatului final. Schimbarea ordinii de evaluare se realizează prin utilizarea parantezelor rotunde.

Pentru a nu formaliza excesiv acest limbaj, anumite noţiuni din limbajele de programare de nivel înalt nu sunt luate în considerare. De exemplu, noţiunea de tip de date este utilizată în mod implicit. Tipul de date al unei variabile reprezintă mulţimea valorilor pe care variabila le poate lua în timpul execuţiei unui algoritm. Se subînţelege faptul că o variabilă nu poate lua valori diferite în timpul execuţiei unui algoritm (valori întregi şi valori logice de exemplu).