ALGORITMI

NOŢIUNI GENERALE

Algoritmul este conceptul fundamental al informaticii. Orice echipament de calcul poate fi considerat o maşină algoritmică. Într-o definiţie aproximativă algoritmul este un set de paşi care defineşte modul în care poate fi dusă la îndeplinire o anumită sarcină. Exemplu de algoritm: algoritmul de interpretare a unei bucăţi muzicale (descris în partitură). Pentru ca o maşină de calcul să poată rezolva o anumită problemă, programatorul trebuie mai întâi să stabilească un algoritm care să conducă la efectuarea la sarcinii respective.

Exemplu:

Algoritmul lui Euclid pentru determinarea celui mai mare divizor comun (cmmdc) a 2 numere întregi pozitive.

Date de intrare: cele 2 numere întregi

Date de iesire: cmmdc

  1. Se notează cu A şi B- cea mai mare, respectiv cea mai mică, dintre datele de intrare
  2. Se împarte A la B şi se notează cu R restul împărţirii
  3. a. Dacă R diferit de 0, se atribuie lui A valoarea lui B şi lui B valoarea lui R. Se revine la pasul 2.
  4. b. Dacă R este 0, atunci cmmdc este B.

Probleme legate de algoritmi

Descoperirea unui algoritm care să rezolve o problemă echivalează în esenţă cu descoperirea unei soluţii a problemei. După descoperirea algoritmului, pasul următor este ca algoritmul respectiv să fie reprezentat într-o formă în care să poată fi comunicat unei maşini de calcul. Algoritmul trebuie transcris din forma conceptuală într-un set clar de instrucţiuni. Aceste instrucţiuni trebuie reprezentate într-un mod lipsit de ambiguitate. În acest domeniu, studiile se bazează pe cunoştinţele privitoare la gramatică şi limbaj şi au dus la o mare varietate de scheme de reprezentare a algoritmilor (numite limbaje de programare), bazate pe diverse abordări ale procesului de programare (numite paradigme de programare).

Căutarea unor algoritmi pentru rezolvarea unor probleme din ce în ce mai complexe a avut ca urmare apariţia unor întrebări legate de limitele proceselor algoritmice, cum ar fi:

Ce probleme pot fi rezolvate prin intermediul proceselor algoritmice?

Cum trebuie procedat pentru descoperirea algoritmilor?

Cum pot fi îmbunătăţite tehnicile de reprezentare şi comunicare a algoritmilor?

Cum pot fi aplicate cunoştinţele dobândite în vederea obţinerii unor maşini algoritmice mai performante?

Cum pot fi analizate şi comparate caracteristicile diverşilor algoritmi?

 

DEFINIŢII ŞI CARACTERISTICI

Definiţii:

Succesiunea etapelor rezolvarii unei probleme,in ordinea parcurgerii lor,prin care se prelucreaza un set de date de intrare, in scopul obtinerii unor date de iesire,se numeste algoritmul problemei.

Algoritmul unei prelucrări constă într-o secvenţă de primitive care descrie prelucrarea.

Algoritmul este un set ordonat de paşi executabili, descrişi fără echivoc, care definesc un proces finit.

Proprietăţile fundamentale ale algoritmilor:

1)Caracterul finit: orice algoritm bine proiectat se termină într-un număr finit de paşi;

2)Caracterul unic şi universal: orice algoritm trebuie să rezolve toate problemele dintr-o clasă de probleme;

3)Realizabilitatea: orice algoritm trebuie să poată fi codificat într-un limbaj de programare;

4)Caracterul discret: fiecare acţiune se execută la un moment dat de timp;

5)Caracterul determinist: ordinea acţiunilor în execuţie este determinată în mod unic de rezultatele obţinute la fiecare moment de timp.

Nerespectarea acestor caracteristici generale conduce la obţinerea de algoritmi neperformanţi, posibil infiniţi sau nerealizabili.

 

REPREZENTAREA ALGORITMILOR

Reprezentarea (descrierea) unui algoritm nu se poate face în absenţa unui limbaj comun celor care vor să îl înţeleagă. De aceea s-a stabilit o mulţime bine definită de primitive (blocuri elementare care stau la baza reprezentării algoritmilor). Fiecare primitivă se caracterizează prin sintaxă şi semantică. Sintaxa se referă la reprezentarea simbolică a primitivei; semantica se referă la semnificaţia primitivei. Exemplu de primitivă: aer-din punct de vedere sintactic este un cuvânt format din trei simboluri (litere); din punct de vedere semantic este o substanţă gazoasă care înconjoară globul pământesc.

Algoritmii se reprezintă prin:

-)scheme logice;

-) pseudocod.

Reprezentarea algoritmilor prin scheme logice

Primitivele utilizate în schemele logice sunt simboluri grafice, cu funcţiuni (reprezentând procese de calcul) bine precizate. Aceste simboluri sunt unite prin arce orientate care indică ordinea de execuţie a proceselor de calcul.

Categorii de simboluri:

Simboluri de început şi sfârşit

Simbolul START desemnează începutul unui program sau al unui subprogram. Simbolul STOP desemnează sfârşitul unui program sau al unui subprogram. Prezenţa lor este obligatorie.

paralelogramSemnifică procese (operaţii) de intrare/ieşire (citirea sau scrierea)


dreptunghiSemnifică o atribuire (modificarea valorii unei date).


decizieSimbolul romb este utilizat pentru decizii . Se testează îndeplinirea condiţiei din blocul de decizie. Dacă această condiţie este îndeplinită, se execută ACŢIUNE1. Dacă nu, se execută ACŢIUNE2. La un moment dat, se execută sau ACŢIUNE1, sau ACŢIUNE2.




Cu ajutorul acestor simboluri grafice se poate reprezenta orice algoritm.

Repetarea unei secvenţe se realizează prin combinarea simbolurilor de decizie şi de atribuire.

Structurile repetitive obţinute pot fi: cu test iniţial sau cu test final.

Structuri repetitive cu test initial

testinitial1Se evaluează condiţia de test. Dacă aceasta este îndeplinită, se execută ACŢIUNE1. Se revine apoi şi se testează iar condiţia. Dacă este îndeplinită, se execută (se repetă) ACŢIUNE1, ş.a.m.d. Abia în momentul în care condiţia nu mai este îndeplinită, se trece la execuţia ACŢIUNE2. Astfel, cât timp condiţia este îndeplinită, se repetă ACŢIUNE1. În cazul în care, la prima testare a condiţiei, aceasta nu este îndeplinită, se execută ACŢIUNE2. Astfel, este posibil ca ACŢIUNE1 să nu fie executată niciodată.


Exisă şi situaţii în care se ştie de la început de câte ori se va repeta o anumită acţiune. În aceste cazuri se foloseşte tot o structură de control repetitivă cu test iniţial. Se utilizează un contor (numeric) pentru a ţine o evidenţă a numărului de execuţii ale acţiunii. De câte ori se execută acţiunea, contorul este incrementat.

Structuri repetitive cu numar cunoscut de pasi

testinitial2Se atribuie contorului valoarea iniţială . Cât timp condiţia (valoarea contorului este mai mică sau egală cu valoarea finală) este îndeplinită, se repetă:

-) ACŢIUNE

-) incrementare contor (se adună 1 la valoarea anterioară a contorului).




Structuri repetitive cu test final

testfinalSe execută mai întâi ACŢIUNE1.

Se testează apoi condiţia.

Se repetă ACŢIUNE1 cât timp condiţia este îndeplinită.

În acest caz, corpul ciclului (ACŢIUNE1) este executat cel puţin o dată.




 

Reprezentarea algoritmilor prin pseudocod 

Pseudocodul este inspirat din limbajele de programare, nefiind însă atât de formalizat ca acestea. Pseudocodul reprezintă o punte de legătură între limbajul natural şi limbajele de programare. Nu există un standard pentru regulile lexicale. Limbajul pseudocod permite comunicarea între oameni, şi nu comunicarea om-maşina (precum limbajele de programare). Pseudocodul utilizează cuvinte cheie (scrise cu majuscule subliniate) cu următoarele semnificaţii:

Sfârşit algoritm:                                  SFÂRŞIT                   

Început algoritm:                                ÎNCEPUT       

Citire (introducere) date:                     CITEŞTE   lista

Scriere (afişare) date:                          SCRIE     lista

Atribuire:                                            <-

Structura de decizie (alternativă):       DACĂ condiţie

                                                           ATUNCI    acţiune1

                                                           ALTFEL    acţiune2

Structuri repetitive cu test iniţial:        CÂT TIMP  condiţie

                                                        REPETĂ    acţiune

Structuri repetitive cu test final:         REPETĂ acţiune

                                                       CÂT TIMP condiţie

sau:

                                                       REPETĂ acţiune

                                                       PÂNĂ CÂND condiţie

Structuri repetitive cu numar cunoscut de pasi:    PENTRU contor=val_iniţ LA val_fin [PAS]

                                                                          REPETĂ acţiune;