Notiunile fundamentale ale programarii: algoritm, limbaje de descriere a algoritmilor, program, limbaje de programare

1. Algoritmul

Se stie ca la baza oricarui program sta un algoritm (care, uneori, este numit metoda de rezolvare). Notiunea de algoritm este o notiune fundamentala in informatica si intelegerea ei, alaturi de intelegerea modului de functionare a unui calculator, permite intelegerea notiunii de program executabil. Vom oferi in continuare o definitie unanim acceptata pentru notiunea de algoritm:

Definitie. Prin algoritm se intelege o multime finita de operatii (instructiuni) elementare care executate intr-o ordine bine stabilita (determinata), pornind de la un set de date de intrare dintr-un domeniu de valori posibile (valide), produce in timp finit un set de date de iesire (rezultate).

Cele trei caracteristici esentiale ale unui algoritm sint:

Determinismul – dat de faptul ca ordinea de executie a instructiunilor algoritmului este bine precizata (strict determinata).

Acest fapt da una din calitatile de baza a calculatorului: “el” va face intotdeauna ceea ce i s-a cerut (prin program) sa faca, “el” nu va avea initiative sau optiuni proprii, “el” nu-si permite sa greseasca nici macar odata, “el” nu se va plictisi ci va duce programul la acelasi sfirsit indiferent de cite ori i se va cere sa repete acest lucru. Nu aceeasi situatie se intimpla cu fiintele umane (Errare humanum est). Oamenii pot avea in situatii determinate un comportament non-deterministic (surprinzator). Acesta este motivul pentru care numerosi utilizatori de calculatoare (de exemplu contabilii), datorita fenomenului de personificare a calculatorului (confundarea actiunilor si dialogului “simulat” de programul ce ruleaza pe calculator cu reactiile unei personalitati vii), nu recunosc perfectul determinism ce sta la baza executarii oricarui program pe calculator. Exprimindu-se prin propozitii de felul: “De trei ori i-am dat sa faca calculele si de fiecare data mi-a scos aceleasi valori aiurea!” ei isi tradeaza propria viziune personificatoare asupra unui fenomen determinist.

Universalitatea – data de faptul ca, privind algoritmul ca pe o metoda automata (mecanica) de rezolvare, aceasta metoda are un caracter general-universal. Algoritmul nu ofera o solutie punctuala, pentru un singur set de date de intrare, ci ofera solutie pentru o multime foarte larga (de cele mai multe ori infinita) de date de intrare valide. Aceasta este trasatura de baza care explica deosebita utilitate a calculatoarelor si datorita acestei trasaturi sintem siguri ca investitia financiara facuta prin cumpararea unui calculator si a produsului-soft necesar va putea fi cu siguranta amortizata. Cheltuiala se face o singura data in timp ce programul pe calculator va putea fi executat rapid si economicos de un numar oricit de mare de ori, pe date diferite !

De exemplu, metoda (algoritmul) de rezolvare invatata la liceu a ecuatiilor de gradul doi: ax²+bx+c=0, se aplica cu succes pentru o multime infinita de date de intrare: (a,b,c)IAxAxA

Finitudinea – pentru fiecare intrare valida orice algoritm trebuie sa conduca in timp finit (dupa un numar finit de pasi) la un rezultat. Aceasta caracteristica este analoga proprietatii de convergenta a unor metode din matematica: trebuie sa avem garantia, dinainte de a aplica metoda (algoritmul), ca metoda se termina cu succes (ea converge catre solutie).

Sa observam si diferenta: in timp ce metoda matematica este corecta chiar daca ea converge catre solutie doar la infinit (!), un algoritm trebuie sa intoarca rezultatul dupa un numar finit de pasi. Sa observam deasemenea ca, acolo unde matematica nu ofera dovada, algoritmul nu va fi capabil sa o ofere nici el. De exemplu, nu este greu de scris un algoritm care sa verifice corectitudinea Conjecturii lui Goldbach: “Orice numar par se scrie ca suma de doua numere prime”, dar, desi programul rezultat poate fi lasat sa ruleze pina la valori extrem de mari, fara sa apara nici un contra-exemplu, totusi conjectura nu poate fi astfel infirmata (dar nici afirmata!).

2. Descrierea algoritmilor

Doua dintre metodele clasice de descriere a algoritmilor sint denumite Schemele logice si Pseudo-Codul. Ambele metode de descriere contin doar patru operatii (instructiuni) elementare care au fiecare un corespondent atit schema logica cit si in pseudo-cod.

In cele ce urmeaza vom insira doar varianta oferita de pseudo-cod intrucit folosirea schemelor logice s-a redus drastic in ultimii ani. Schemele logice mai pot fi intilnite sub numele de diagrame de proces in anumite carti de specialitate ingineresti. Avantajul descrierii algoritmilor prin scheme logice este dat de libertatea totala de inlantuire a operatiilor (practic, sageata care descrie ordinea de executie, pleaca de la o operatie si poate fi trasata inspre orice alta operatie). Este demonstrat matematic riguros ca descrierea prin pseudo-cod, desi pare mult mai restrictiva (operatiile nu pot fi inlantuite oricum, ci trebuie executate in ordinea citirii: de sus in jos si de la stinga la dreapta), este totusi perfect echivalenta. Deci, este dovedit ca plusul de ordine, rigoare si simplitate pe care il ofera descrierea prin pseudo-cod nu ingradeste prin nimic libertatea programarii. Totusi, programele scrise in limbajele de asamblare, care sint mult mai compacte si au dimensiunile mult reduse, nu ar putea fi descrise altfel decit prin scheme logice.

Atribuirea var:=expresie;

Intrare/Iesire Citeste var₁, var₂, var₃, . ;

Scrie var₁, var₂, var₃, . ; sau Scrie expresia₁, expresia₂, expresia₃, . ;

Conditionala Daca <conditie_logica> atunci instructiune₁ [altfel instructiune₂];

Ciclurile – Exista (din motive de usurinta a descrierii algoritmilor) trei tipuri de instructiuni de ciclare. Ele sint echivalente intre ele, oricare varianta de descriere putind fi folosita in locul celorlalte doua, cu modificari sau adaugiri minimale:

Repeta instructiune₁, instructiune₂, . pina cind <conditie_logica>;

Cit timp <conditie_logica> executa instructiune;

Pentru var_contor:=val_initiala pina la val_finala executa instructiune;

In cazul ciclurilor, grupul instructiunilor ce se repeta se numeste corpul ciclului iar conditia logica care (asemenea semaforului de circulatie) permite sau nu reluarea executiei ciclului este denumita conditia de ciclare sau conditia de scurt-circuitare (dupa caz). Observam ca ciclul de tipul Repeta are conditia de repetare la sfirsit ceea ce are ca si consecinta faptul ca corpul ciclului se executa cel putin odata, in mod obligatoriu, inainte de verificarea conditiei logice. Nu acelasi lucru se intimpla in cazul ciclului de tipul Cit timp, cind este posibil ca instructiunea compusa din corpul ciclului sa nu poata fi executata nici macar odata. In plus, sa mai observam ca ciclul de tipul Pentru . pina la contine (in mod ascuns) o instructiune de incrementare a variabilei contor.

In limba engleza, cea pe care se bazeaza toate limbajele actuale de programare acestor instructiuni, exprimate in limba romana, le corespund respectiv: 2. Read, Write;  If-Then-Else; 4. Repeat-Until, Do-While, For. Sa observam ca, mai ales pentru un vorbitor de limba engleza, programele scrise intr-un limbaj de programare ce cuprinde aceste instructiuni este foarte usor de citit si de inteles, el fiind foarte apropiat de scrierea naturala. Limbajele de programare care sint relativ apropiate de limbajele naturale sint denumite limbaje de nivel inalt (high-level), de exemplu limbajul Pascal, spre deosebire de limbajele de programare mai apropiate de codurile numerice ale instructiunilor microprocesorului. Acestea din urma se numesc limbaje de nivel scazut (low-level), de exemplu limbajul de asamblare. Limbajul de programare C are un statut mai special el putind fi privit, datorita structurii sale, ca facind parte din ambele categorii.

Peste tot unde in pseudo-cod apare cuvintul instructiune el poate fi inlocuit cu oricare din cele patru instructiuni elementare. Aceasta substituire poarta numele de imbricare (de la englezescul brick-caramida). Prin instructiune se va intelege atunci, fie o singura instructiune simpla (una din cele patru), fie o instructiune compusa. Instructiunea compusa este formata dintr-un grup de instructiuni delimitate si grupate in mod precis (intre acolade in C sau intre begin si end in Pascal).

Spre deosebire de pseudo-cod care permite doar structurile noi formate prin imbricarea repetata a celor patru instructiuni (caramizi) in modul precizat, schemele logice permit structurarea in orice succesiune a celor patru instructiuni elementare, ordinea lor de executie fiind data de sensul sagetilor. Repetam ca desi, aparent, pseudo-codul limiteaza libertatea de descriere doar la structurile prezentate, o teorema fundamentala pentru programare afirma ca puterea de descriere a pseudo-limbajului este aceeasi cu cea a schemelor logice.

Forma de programare care se bazeaza doar pe cele patru structuri se numeste programare structurata (spre deosebire de programarea nestructurata bazata pe descrierea prin scheme logice). Teorema  de echivalenta a puterii de descriere prin pseudo-cod cu puterea de descriere prin schema logica afirma ca programarea structurata (aparent limitata de cele patru structuri) este echivalenta cu programarea nestructurata (libera de structuri impuse). Evident, prin ordinea, lizibilitatea si fiabilitatea oferita de cele patru structuri elementare (si asta fara a ingradi libertatea de exprimare) programarea structurata este net avantajoasa. In fapt, limbajele de programare nestructurata (Fortran, Basic) au fost de mult scoase din uz, ele (limbajele de asamblare) sint necesare a fi folosite in continuare doar in programarea de sistem si in programarea industriala (in automatizari).

3 Programul

Prin program se intelege un sir de instructiuni-masina care sint rezultatul compilarii algoritmului proiectat spre rezolvarea problemei dorite ce a fost descris intr-un limbaj de programare (ca si cod sursa).

Etapele realizarii unui program sint:

Editarea codului sursa, etapa ce se realizeaza cu ajutorul unui program editor de texte rezultatul fiind un fisier Pascal sau C, cu extensia .pas sau .c (.cpp)

Compilarea, etapa de traducere din limbajul de programare Pascal sau C in limbajul intern al micro-procesorului, si este realizata cu ajutorul programului compilator Pascal sau C si are ca rezultat un fisier obiect, cu extensia .obj (in limbajul C) sau .exe (in limbajul Pascal)

Link-editarea, etapa la care  se adauga modului obiect rezultat la compilare diferite module continind subprograme si rutine de biblioteca, rezultind un fisier executabil (aceasta etapa este comasata in Turbo Pascal sau Borland Pascal cu etapa de compilare), cu extensia .exe

Executia (Run), etapa de lansare in executie propriu-zisa a programului obtinut, lansare realizata de interpretorul de comenzi al sistemului de operare (command.com pentru sistemele DOS+Windows)

Observam ca aceste patru (sau trei, pentru Turbo Pascal) etape sint complet independente in timp unele de altele si necesita utilizarea a patru programe ajutatoare: Editor de texte, Compilator Pascal sau C, Link-editor si Interpretorul de comenzi al S.O. In cazul mediilor de programare integrate (Turbo sau Borland) comandarea acestor patru programe ajutatoare precum si depanarea erorilor de executie este mult facilitata.

Deasemenea, merita subliniat faptul ca in timp ce fisierul text Pascal sau C, ce contine codul sursa, poate fi transportat pe orice masina (calculator) indiferent de micro-procesorul acesteia urmind a fi compilat la fata locului', in cazul fisierului obiect acesta nu mai poate fi folosit decit pe masina (calculatorul) pentru care a fost creat (datorita instructiunilor specifice micro-procesorului din care este compus). Deci, pe calculatoare diferite (avind micro-procesoare diferite) vom avea nevoie de compilatoare Pascal sau C diferite.

In plus, sa remarcam faptul ca fisierele obiect rezultate in urma compilarii pot fi link-editate (cu grija !) impreuna chiar daca provin din limbaje de programare diferite. Astfel, un program rezultat (un fisier .exe sau .com) poate fi compus din module obiect care provin din surse diferite (fisiere Pascal, C, asamblare, etc.).