Algoritmi - Reprezentarea Algoritmilor

1. Algoritmi

Noţiunea de algoritm este fundamentală în informatică (aşa cum este în

matematică noţiunea de mulţime). Astfel încât putem întâlni diverse definiţii ale

algoritmului. De exemplu, Enciclopædia Britannica dă următoarea definiţie: "O

procedură sistematică ce produce într-un număr finit de paşi răspunsul la o întrebare sau

rezolvarea unei probleme". Dicţionarul de calculatoare & Internet (editura Teora, 1999)

defineşte algoritmul astfel: "O procedură matematică sau logică de rezolvare a unei

probleme. O metodă de a găsi răspunsul corect la o problemă dificilă prin împărţirea ei

într-un anumit număr de etape simple."

Caracteristicile unui algoritm sunt:

- determinism (claritate): succesiunea paşilor este precis determinată;

- finitudine (eficacitate): numărul paşilor descrişi este finit;

- generalitate (universalitate): rezolvă orice problemă din clasa de probleme

pentru care a fost elaborat (pentru orice set de date de intrare).

Algoritmii se folosesc în orice limbaj, inclusiv în cel natural. O reţetă de bucătărie

este un algoritm:

"Se amestecă 30g drojdie cu o linguriţă zahăr. Se amestecă totul cu 4 linguri făină

şi 4 linguri lapte. Pauză timp de 15 minute. Se amestecă totul cu 400g făină şi două

pahare lapte timp de 5 minute. Pauză timp de 20 minute. Se unge tava. Se pune amestecul

în tavă. Se pun fructele peste amestec. Se dă la cuptor. Pauză timp de 20 minute. Se

scoate din cuptor. Pauză timp de 5 minute. Se taie şi se mănâncă".

Cuvântul algoritm provine din traducerea în latină (“Algoritmi de numero

Indorum”) a titlului scrierii matematicianului arab Al-Horezmi (“Al-Horezmi despre

numărarea indiană”). Abu Abdullah Mohamed Ibn Musa Al-Horezmi (770 – 840) a

fost unul dintre cei mai mari matematicieni ai lumii. A trăit în Bagdad, în timpul califului

Mamun. A fondat câteva din ramurile matematicii. Este faimos şi ca astronom. Cea mai

mare realizare a sa o constituie introducerea conceptului de algoritm. O alta de rang

asemănător este introducerea cifrei zero.

Algoritmii se întâlnesc mereu în viaţa obişnuită. Acţionarea unor dispozitive sau

maşini se face conform algoritmilor (apăs butonul de apel al liftului, aştept până când

ajunge, deschid uşile, intru, închid uşile, comand oprirea următoare, aştept până ajung,

deschid uşile, ies, închid uşile). Chiar şi normele de comportare sunt algoritmi (deschid

uşa sălii de aşteptare, intru, închid uşa, salut persoanele aflate aici, dacă există un scaun

liber, atunci mă aşez, aştept până îmi vine rândul).

Preşcolarii învaţă algoritmi matematici: ca să adun pe 7 cu 4, folosesc

numărătoarea astfel: trec în dreapta 7 bile de pe prima linie, trec în dreapta 4 bile de pe a

doua linie, număr câte bile am în total în dreapta.

În gimnaziu ne întâlnim cu algoritmul lui Euclid, care stabileşte care este cel mai

mare divizor comun a două numere naturale. Se observă o diferenţă fundamentală faţă de

algoritmul precedent: acesta rezolvă o clasă infinită de probleme (numerele naturale pot fi

oricare), pe când cel precedent rezolvă o singură problemă (cum adun pe 7 cu 4, dar nu

mă învaţă cum adun pe 2 cu 5).

Există întotdeauna un algoritm de rezolvare a unei clase finite de probleme. Este

varianta exhaustivă de rezolvare, adică o tabelă de valori asociată tuturor valorilor

posibile. De exemplu, problema determinării înmulţirii a două numere cel mult egale cu

10 a dus la celebra tablă a înmulţirii pe care am învăţat-o în clasa a doua.

În general, nu este uşor a răspunde la problemele care au număr infinit de valori

de luat în considerare. De exemplu: "este numărul n (natural) prim ?" sau "care este cel

mai mic multiplu comun a două numere naturale ?". De aceea algoritmii care rezolvă

astfel de probleme sunt importanţi şi sunt studiaţi în şcoală. "Elementele" lui Euclid,

apărută în anul 300, conţin un algoritm care află cel mai mare divizor comun a două

numere naturale. Găsirea de algoritmi eleganţi (simpli şi eficienţi) este unul din scopurile

cercetării în informatică.

Se disting două tipuri de algoritmi: cei care furnizează un răspuns de tipul da/nu

se numesc decizionali. Problemele rezolvate de ei se numesc probleme de decizie ("este n

prim ?"). Cei care conduc la o valoare numerică se numesc calculaţionali. Problemele

rezolvate se numesc probleme de calcul ("care este cel mai mic multiplu comun al

numerelor a şi b ?").

Câteodată nu există algoritmi pentru rezolvarea unor clase infinite de probleme,

mai ales atunci când se impun restricţii asupra metodei acceptate. De exemplu, două

probleme din vremea lui Euclid, care trebuie rezolvate cu ajutorul riglei negradate şi a

compasului: "să se construiască un pătrat cu aria egală cu a unui cerc dat" şi "să se

deseneze trisectoarea unui unghi" au fost studiate secole de-a rândul, până când s-a

demonstrat că sunt imposibile. La trecerea în secolul al XX-lea, David Hilbert

(matematician german) a propus 23 de probleme de rezolvat în următoarea sută de ani. A

doua problemă din listă cerea investigarea consistenţei axiomelor aritmeticii. Mulţi

matematicieni aveau dubii asupra rezolvării acestei probleme, până în 1931, când Kurt

Gödel (logician austriac) a demonstrat surprinzătorul rezultat că există enunţuri aritmetice

indecidabile (nu se pot nici afirma şi nici nega), deoarece conduc la o procedură

decizională infinită (deci nu duc la un algoritm). Într-un efort fără succes de a afla cel

puţin care sunt aceste enunţuri, Alan Turing (matematician şi logician englez) a definit

riguros conceptul de algoritm. Descrierea sa pentru caracteristicile esenţiale ale unei

maşini care produce algoritmi (maşina Turing) a devenit fundamentul informaticii.

Programele de calculator sunt tipuri speciale de algoritmi. Decidabilitatea şi

calculabilitatea lor sunt probleme centrale ale scrierii programelor.