New PROGRAMARE PROCEDURAL · 2020. 5. 6. · Scheme logice structurate Notiuni introductive privind...

PROGRAMARE PROCEDURALĂ PROCEDURAL PROGRAMMING

Disciplină obligatorie; sem 1, ore săptămânal – învăţământ de zi: 2 curs, 2 laborator, total ore semestru 56; 6 credite; colocviu

I. CONŢINUTUL TEMATIC AL DISCIPLINEI

• Algoritmi: Caracteristici. Descriere. Complexitate. Corectitudine. • Limbaje de programare. Caracteristici. • Limbajul de programare C: Entităţi sintactice. Operatori.. Expresii. Instrucţiuni.

Funcţii. Directive de preprocesare. Tablouri şi Pointeri. Comunicare inter-modulară. Funcţia main cu argumente. Pachetele: stdio.h, math.h, string.h

• Alocare statică – Alocare dinamică. Structuri de date dinamice (liste şi arbori). Aplicaţii ale utilizării tipurilor de date structurate (struct, union, typedef) cu ajutorul pointerilor: crearea şi explorarea structurilor de date. Pachetele: stdlib.h, alloc.h

• Operaţii de intrare-ieşire. Fişiere în C şi aplicaţii. • Corectitudinea programelor C. Metoda aserţiunilor (assert.h). • Complexitatea programelor (time.h). Metrici software. • Testarea programelor C. • Utilizarea bibliotecilor statice (.LIB) şi dinamice (.DLL). • Metode de proiectare a programelor.

II. BIBLIOGRAFIE MINIMALĂ OBLIGATORIE

1. G. Albeanu, Algoritmi şi limbaje de programare, Editura Fundaţiei România de mâine, Bucureşti, 2000.

2. G. Albeanu, Programare procedurală, Note de curs (Avizierul virtual / Blackboard)

3. G. Albeanu (coord.), Tehnici de programare. Lucrări practice de programarea calculatoarelor, Editura Fundaţiei România de mâine, Bucureşti, 2003.

4. Popa M., Popa M., Programare procedurală (Aplicaţii C şi C++ în structuri de date şi grafică), Editura Fundaţiei România de mâine, Bucureşti, 2006.

UNIVERSITATEA SPIRU HARET file:///C:/ACTIV/Proc/FINAL/IDD-USH.htm

1 of 1 12/9/2007 7:18 PM

UNIVERSITATEA SPIRU HARET

FACULTATEA DE MATEMATICA-INFORMATICA

Suport de curs elaborat de

Prof. Univ. Dr. Grigore ALBEANU

pentru disciplina:

PROGRAMARE PROCEDURALA

2C + 2L; Ciclul I; semestrul I

Evaluare: Examen

CUPRINS

INTRODUCERE

Ce este informatica ? Ce este un program ? Notiunea de algoritm. Cum rezolvam probleme cu ajutorul calculatorului ?

ALGORITMI: DESCRIERE, COMPLEXITATE, CORECTITUDINE

Notiuni de teoria grafurilor Scheme logice structurate Notiuni introductive privind organizarea datelor Limbaj algoritmic Analiza complexitatii Elemente privind corectitudinea algoritmilor

LIMBAJE DE PROGRAMARE

Vocabularul si sintaxa limbajelor de programare Tipuri de date. Constante. Variabile. Expresii Programare in C

Bibliografie

G. Albeanu - PROGRAMARE PROCEDURALA - Introducere file:///C:/ACTIV/Proc/FINAL/C1.HTM

1 of 6 12/9/2007 7:19 PM

1. Introducere

1.1. Ce este informatica?1.2. Ce este un program? Notiunea de algoritm1.3. Cum rezolvam probleme cu ajutorul calculatorului?

1.1. Ce este informatica?

În anul 1642, matematicianul si fizicianul Blaise Pascal (1623-1662) a inventat prima masina mecanicã, curoti dintate, capabilã sã realizeze operatii de adunare si scãdere a numerelor naturale. Totusi, de abiadupã aparitia masinilor electromecanice, în 1944, John von Neumann a formulat principiul programuluiînregistrat si a sugerat constructorilor de calculatoare trei principii care trebuie avute în vedere pentrurealizarea unui calculator:

programele si datele trebuie sã fie codificate sub formã binarã;programele si datele trebuie stocate într-o memorie a masinii de calcul;trebuie sã existe o componentã (unitate centralã de prelucrare, procesor) specialã care stie atât sãexecute operatii de calcul, cât si sã extragã, sã decodifice si sã execute instructiunile programului.

Astfel, aproape toate tipurile de sisteme de calcul ce au apãrut mai târziu sunt calculatoare de tip vonNeumann.

Aparitia sistemelor de calcul a dus la aparitia si dezvoltarea unei noi stiinte: informatica (Informatique,Informatics, Informatik în Europa, respectiv Computer Science în SUA). Informatica reprezintã uncomplex de discipline prin care se asigurã prelucrarea informatiilor cu ajutorul sistemelor de calcul.Astãzi, informatica este prezentã în industrie, bãnci, ferme, artã, medicinã, stiinte sociale etc. si estestructuratã în mai multe domenii precum:

arhitectura sistemelor de calcul: studiazã modul de organizare a sistemului fizic (hardware) pentru ase obtine o mai mare eficientã, sigurantã si utilitate.sisteme de operare: studiazã modalitãtile de gestiune eficientã a resurselor fizice si a programelor.algoritmi si structuri de date: studiazã metodele de rezolvare a problemelor si modurile de organizarea datelor pentru a obtine programe eficiente.limbaje de programare: studiazã modalitãtile prin care algoritmii si structurile de date suntprezentate calculatorului pentru a fi prelucrate.ingineria programãrii: studiazã metodele de automatizare a proceselor de proiectare, analizã, testaresi reutilizare a programelor.calcule numerice si simbolice: studiazã modalitãtile de reprezentare a informatiei numerice pentruimplementarea unor algoritmi numerici robusti, eficienti si de mare precizie.sisteme de gestiune a bazelor de date: studiazã modalitãtile de structurare si organizare eficientã a


2 of 6 12/9/2007 7:19 PM

colectiilor mari de date ce vor fi supuse diverselor prelucrãri.inteligenta artificialã: studiazã modalitãtile de reprezentare si manipulare a cunostintelor în vedereaobtinerii de noi cunostinte.animatia si robotica: studiazã modalitãtile de reprezentare, prelucrare si analizã a informatieiaudio-vizuale.

În sfera sa de preocupãri, Informatica a atras si dezvoltat o mare varietate de discipline precum: logicamatematicã, teoria automatelor, limbaje formale, cercetãri operationale, teoria grafurilor si retelelor,calcul numeric, teoria fiabilitãtii, geometrie computationalã, teoria calculabilitãtii, baze de date, baze decunostinte, sisteme expert etc.

1.2. Ce este un program? Notiunea de algoritm

Solutia unei probleme, din punct de vedere informatic, este datã printr-o multime de comenzi(instructiuni) explicite si neambigue, exprimate într-un limbaj de programare. Aceastã multime deinstructiuni prezentatã conform anumitor reguli sintactice formeazã un program. Un program poate fiprivit si ca un algoritm exprimat într-un limbaj de programare. Totusi, un algoritm descrie solutiaproblemei independent de limbajul de programare în care este redactat programul.

Existã mai multe definitii ale notiunii de algoritm. A. A. Markov, a considerat algoritmul ca fiind o notiunematematicã primarã si a descris-o astfel: Un algoritm este o retetã care descrie precis si clar un proces decalcul.El a descris un mecanism formal pentru a specifica o clasã largã de activitãti si anume: algoritmii normali.Alte modalitãti de descriere a algoritmilor ce au mai fost propuse sunt: masina Turing, sistemele Post,functiile recursive etc. În aceastã lucrare, prin algoritm vom întelege o secventã finitã de comenzi explicitesi neambigue care, executate pentru o multime de date (ce satisfac anumite conditii initiale), conduce întimp finit la rezultatul corespunzãtor. Observãm cã se face distinctie între algoritm (care se terminã întimp) si procedurã (care poate continua nedefinit).

Conform lui D. Knuth (The art of computer programming, Vol. I, 1997) un algoritm posedã cincicaracteristici importante:

Un algoritm are caracter finit. El este descris printr-o secventã finitã de etape si trebuie ca, ori de câteori sunt parcurse etapele algoritmului pentru anumite date, procesul sã se încheie în timp finit.Un algoritm are caracter determinist. Actiunile specificate de pasii algoritmului sunt clare, fiindriguros prezentate.Un algoritm are date de intrare. Se poate admite cã întotdeauna un algoritm lucreazã asupra unordate de intrare. Acestea pot fi evidentiate din contextul în care este formulatã problema a cãreisolutie o reprezintã algoritmul.Un algoritm furnizeazã cel putin o valoare de iesire ce se aflã într-o relatie specificã cu datele deintrare.Un algoritm este eficace.

Trebuie spus cã nu orice problemã admite solutie descrisã algoritmic. Problemele pentru care existã unalgoritm de rezolvare se numesc probleme decidabile. Problemele pentru care s-a demonstrat (matematic)cã nu admit un algoritm de rezolvare se numesc probleme nedecidabile. Nu este suficient ca o anumitãproblemã (clasã de probleme) sã admitã solutii (chiar si o singurã solutie). Din punctul de vedere alinformaticii, intereseazã dacã existã solutie ce poate fi descrisã algoritmic, deci dacã solutia problemeipoate fi construitã efectiv. De asemenea, pentru rezolvarea anumitor probleme pot exista mai multi


3 of 6 12/9/2007 7:19 PM

algoritmi. Stabilirea celui mai bun dintre acestia se realizeazã în urma unui proces de analizã prin care sedeterminã performantele fiecãruia dintre algoritmi.

În finalul acestei sectiuni vom descrie câtiva algoritmi elementari. Acestia vor contribui la realizarea unuiprim contact cu solutiile algoritmice. Mai întâi prezentãm câteva conventii. Datele supuse prelucrãrilorsunt manipulate cu ajutorul variabilelor. Acestea sunt entitãti ce pot referi elemente ale unei anumitemultimi. Putem vorbi de variabile întregi (respectiv reale, caracter etc.) atunci când acestea se referã lavalori întregi (respectiv reale, caracter etc.). Actiunile realizate în cadrul unui algoritm vor fi descrise prinverbe: executã, citeste, scrieetc. Notatiile matematice consacrate vor fi utilizate fãrã explicatii suplimentare. Vom utiliza constructiiprecum: dacã, atunci, altfel, cât timp, repetã, pânã când, pentru, de la, pânã la etc., a cãror semnificatieeste cea uzualã. O operatie importantã este aceea prin intermediul cãreia o variabilã "va primi" o anumitãvaloare. Aceastã actiune se mai numeste operatie de atribuire si, în continuare, se va nota prin ":="Valoarea ce se atribuie unei variabile este rezultatul evaluãrii unei expresii. Expresia poate fi de tipnumeric sau de tip logic. Într-o expresie numericã apar numere (întregi, reale etc.) si operatori aritmeticiprecum: + (adunare), - (scãdere), * (înmultire), / (împãrtire) etc. Expresiile logice (numite si expresiibooleene) contin operatori logici: and (si logic), or (sau logic), not (negatie) si operatori relationali (, = (mai mare sau egal), != sau (diferit), = (egalitate)) folositi între elemente pentrucare aceste operatii au sens. Rezultatul evaluãrii unei expresii logice poate fi: true (adevãrat) sau false(fals). În descrierea unei expresii pot fi folosite si alte simboluri dacã acestea sunt cunoscute sau explicate.Utilizarea parantezelor: "(" si ")" pentru indicarea modului de evaluare este, de asemenea, permisã.

Am vãzut cã algoritmii acceptã date de intrare si furnizeazã rezultate (date de iesire). Introducerea unvalori sau a unui sir de valori se va descrie folosind verbul citeste. Afisarea unei valori sau a unui sir devalori va fi descrisã prin verbul scrie. Vom conveni sã numerotãm pasii (etapele) unui algoritm. numerotare va fi utilizatã eventual în alti pasi. Acest mod de prezentare a algoritmilor se numestedescriere în limbaj conventional. În unele lucrãri, limbajul conventional mai este numit si limbajpseudocod.

Exemplul 1.1.Fie a si b douã variabile întregi. Dorim sã schimbãm între ele valorile celor douã variabile. Mai precis, dacã a= 640 si b = 480, dorim sã obtinem a = 480 si b = 640.

Un mod de a realiza aceastã schimbare presupune utilizarea unei variabile suplimentare, cu rol deintermediar. Folosind trei operatii de atribuire, algoritmul are urmãtorii pasi:

1. citeste a, b2. t := a3. a := b4. b := t5. scrie a,b

Lãsãm ca exercitiu realizarea urmãtoarelor transformãri:

i) a --> b --> c --> aii) a --> b --> c --> d --> a

Atunci când va fi necesar, ne vom referii la pasii 2, 3 si 4 prin constructia interschimb(a,b).

Exemplul 1.2.Se cere generarea primilor n termeni (n>1) ai sirului lui Fibonacci. Primii câtiva termeni sunt: 0, 1, 1, 2, 3, 5,8, 13, ... Mai precis, termenul curent este suma celor doi termeni anteriori.

Vom prezenta douã metode. Prima metodã descrie schema de generare c := a + b, unde a, b desemneazã


4 of 6 12/9/2007 7:19 PM

ultimii doi termeni generati, iar c va fi termenul curent. Deoarece se cer n termeni, este necesar unmecanism de numãrare (incrementarea unei variabile de contorizare). Valorile contorului vor fi referiteprin variabila k. Algoritmul de generare, în prima variantã, este:

Varianta 1:1. citeste n2. k := 23. a := 0; scrie a4. b := 1; scrie b5. repetã5.i) c := a + b; scrie c5.ii) a := b5.iii) b := c5.iv) k := k+1pânã când k = n.

Prin a doua metodã se vor genera termenii doi câte doi. Aceasta înseamnã ca uneori este generat unul înplus. Descrierea ce urmeazã foloseste numai variabilele a si b pentru a indica termenii sirului.

Varianta 2:1. citeste n2. a := 03. b :=14. k :=25. cât timp k < n executã5.i) scrie a, b5.ii) a := a + b5.iii) b := a + b5.iv) k := k+26. dacã k = n atunci scrie a, b altfel scrie a.

Exemplul 1.3. Se considerã o secventã cu n numere întregi. Se cere afisarea numerelor în ordine crescãtoare.Vom descrie sirul de numere prin x1, x2, ..., xn.Cea mai simplã metodã presupune interschimbarea a câte douã elemente, pânã când nu mai sunt necesareinterschimbãri. Pasii algoritmului sunt:

1. citeste n2. citeste x1, x2, ..., xn 3. k:=1;4. repetã4.i) ordonat := true4.ii) pentru i de la 1 pânã la n-k executãdacã xi > xi+1 atunci a) interschimb(xi, xi+1)b) ordonat := false4. iii) k:=k+1;pânã când (ordonat = true) or (k = n)5. scrie x1, x2, ..., xn.

Justificarea metodei este simplã. Trebuie sã observãm cã la prima parcurgere, elementul maxim va ajungepe ultima pozitie. La a doua parcurgere, elementul imediat mai mic (decât maximul recent obtinut), vaocupa penultima pozitie. Când nu sunt necesare interschimbãri sirul este deja ordonat.


5 of 6 12/9/2007 7:19 PM

1.3. Cum rezolvãm probleme cu ajutorul calculatorului?

Am vãzut cã existã probleme pentru care nu poate fi dat un algoritm de rezolvare. Totusi cele mai multeprobleme cu care se confruntã informatica sunt probleme decidabile. Toate temele tratate în aceastãlucrare formuleazã probleme decidabile.

Se stie cã nu învãtarea unui limbaj de programare este o sarcinã dificilã, ci rezolvarea algoritmicã aproblemelor decidabile. Este clar cã, înainte de a începe scrierea unui program trebuie, mai întâi, sã gãsim(sau sã cunoastem deja) solutia algoritmicã a problemei puse. Cum se gãseste solutia? Etapele descrise deG. Pólya (Cum rezolvãm o problemã? Editura Stiintificã, Bucuresti, 1965), pentru rezolvarea unei problemede matematicã, sunt valabile si în informaticã.

Înainte de a începe sã vedem cum se face, trebuie sã întelegem atât ipotezele problemei cât si ceea ce secere. Deci, întelegerea problemei, ocupã primul loc în procesul cãutãrii unei metode de rezolvare a acesteiacu ajutorul calculatorului. Trebuie evidentiate datele de intrare si conditiile pe care acestea trebuie sã leîndeplineascã. Este important sã identificãm esentialul. De multe ori un enunt al unei probleme continefoarte multe elemente descriptive privind importanta problemei, consideratii de naturã istoricã, exemple,uneori chiar si etape distincte pentru obtinerea solutiei. Cerinta problemei furnizeazã, de multe ori, chiaridei privind modul de a ajunge la solutie. Considerarea unor configuratii particulare pentru datele deintrare si încercarea de a lucra asupra lor, pentru a gãsi solutia, va contribui întotdeauna la o întelegeremai bunã a enuntului.

Dacã în enunt se sugereazã etapele rezolvãrii, acestea implicând rezolvarea unor subprobleme, atuncitrebuie sã aflãm solutia algoritmicã corespunzãtoare fiecãrei etape. Dacã nu se specificã etape, dar putemdescompune problema în subprobleme mai simple atunci solutia algoritmicã a problemei initiale se vaobtine prin "compunerea" solutiilor subproblemelor. Deci este foarte important sã stim sã rezolvãmprobleme simple, eventual probleme reprezentative pentru anumite clase de aplicatii si sã stim sãdescompunem (respectiv, sã reducem) problema initialã în (la) subprobleme usor de rezolvat si apoi sãconstruim solutia finalã. Abordarea prin descompuneri repetate, cu detaliere pas cu pas se numesteabordare top-down sau rafinare iterativã.Abordarea prin care pornind de la solutii algoritmice ale unor probleme cunoscute, construim solutii alealtor probleme care au însã legãturã cu problema de rezolvat, iar în final, urmând aceeasi modalitateconstruim solutia problemei a cãrei solutie se cere, se numeste abordare bottom-up. Aceastã metodãpermite reutilizarea programelor existente si este tot mai importantã odatã cu aparitia tehnicilor orientateobiect. De asemenea, pentru a obtine o solutie a unei probleme este util sã privim problema si comparativcu alte probleme întâlnite. Numai dupã investigarea acestor variante putem trece la stabilirea metodei deabordare.

Pentru probleme de complexitate ridicatã, oricare din metodele de abordare top-down sau bottom-up,conduc la o solutie modularã, bazatã pe subprograme sau, mai nou, la o solutie orientatã obiect.

Multe din problemele de programare pot fi rezolvate usor dacã solutia verificã anumite principii. Dacãsolutia problemei este o multime de elemente care se poate obtine pas cu pas, pornind de la multimea vidã,prin adãugarea celui mai bun element neconsiderat încã (si ales conform anui anumit criteriu) spunem cãavem de-a face cu o abordare de tip greedy. Pentru probleme în care se cere o solutie optimã care satisfaceprincipiul optimalitãtii (principiul lui Bellman) se va aplica metoda programãrii dinamice. Alte strategiipentru elaborarea algoritmilor sunt: metoda divide et impera, metoda backtracking, euristica etc.

Vreau sa vad începutul capitolului

Vreau sa vad Cuprinsul documentului.


6 of 6 12/9/2007 7:19 PM

Versiune prescurtatã a capitolului 1 din: G. Albeanu. Algoritmi si limbaje de programare. Editura Fundatiei"România de Mâine", 2000.

ALGORITMI I file:///C:/ACTIV/Proc/FINAL/C3.HTM

1 of 16 12/9/2007 7:20 PM

2. Algoritmi: Descriere, Complexitate, Corectitudine

2.1. Notiuni de teoria grafurilor2.2. Scheme logice structurate2.3. Notiuni introductive privind organizarea datelor2.4. Limbaj algoritmic2.5. Analiza complexitatii2.6. Elemente privind corectitudinea algoritmilor

2.1. Notiuni de teoria grafurilor

Un graf neorientat G este definit prin perechea G = (V, E), unde V este o multime nevidã de elementenumite vârfuri (vertex), iar E este o multime (posibil vidã) de perechi neordonate cu componentedistincte ale lui V care se numesc muchii (edges). Dacã E este multimea vidã spunem cã G este trivial. Încazul în care multimea V este finitã spunem cã avem un graf finit. Numãrul elementelor multimii Vdeterminã ordinul grafului finit. O muchie cu vârfurile x si y (numite extremitãti) se noteazã prin [x, y]sau [y, x]. Spunem cã vârfurile x si y sunt incidente muchiei [x,y].

Un digraf este definit printr-o pereche G=(V, E), unde V este o multime nevidã de vârfuri, iar E este oparte a produsului cartezian V x V ale cãrei elemente le numim arce. Un arc este notat prin (x,y) cu xdiferit de y, unde x se numeste sursã sau extremitate initialã, iar y se numeste destinatie sau extremitatefinalã. Atributele : trivial, respectiv finit, pentru un digraf se definesc similar.

Un graf (digraf) partial al unui graf (digraf) G = (V, E) este un graf (digraf) G1 = (V, E1), unde E este submultime a multimii E, deci este graful (digraful) G însusi sau se obtine din G prin suprimareaanumitor muchii (arce).

Un subgraf (subdigraf) al unui graf (digraf) G este un graf (digraf) H = (U, E'), unde U este submultimea multimii V, E' este submultime a multimii E, iar muchiile (arcele) din E' sunt toate muchiile (arcele)din E, care au ambele extremitãti în multimea de vârfuri U.

Uneori, arcele (muchiile) sunt etichetate. Dacã etichetele sunt numere reale pozitive se spune cã digraful(graful) este ponderat.

În continuare vom considera numai grafuri (digrafuri) finite. De obicei un graf se reprezintã prinindicarea unor puncte din plan (ce corespund vârfurilor) si a unor segmente de curbã (sau de dreaptã)pentru indicarea muchiilor (vezi figura 2.1a). În cazul digrafurilor arcele sunt segmente de curbãorientate, sensul fiind de la sursã spre destinatie (vezi figura 2.1b).

Definitia 2.1.1.


2 of 16 12/9/2007 7:20 PM

Fie G = (V,E) un digraf, iar x si y douã vârfuri. Numim x-y drum (de lungime n) o secventã de vârfuri D:v0, v1, ..., vn dacã v0 = x, vn = y , iar (vi, vi+1) apartine multimii E pentru toti i, ≤ i ≤ n-1. Vârfurile x si y senumesc extremitãtile drumului D. Un drum fãrã nici un arc este un drum trivial. Un x-y drum se numestecircuit (sau drum închis) dacã x=y; dacã x diferit de y, se spune cã drumul este unul deschis. Circuitul esteelementar dacã toate vârfurile circuitului, cu exceptia primului si a ultimului vârf care coincid, suntdistincte douã câte douã.

Definitia 2.1.2. Fie G = (V, E) un graf neorientat, iar x si y douã vârfuri. Secventa de vârfuri L: v0, v1, ..., vneste un x-y lant (de lungime n) dacã [ vi, vi+1] apartine multimii E, pentru toti i, 0 ≤ i ≤ n-1, iar x=v0 si y=vn. L este ciclu dacã x=y. Atributul elementar, pentru un lant, poate fi introdus similar.

Uneori, chiar pentru un digraf, putem folosi notiunea de lant, dacã se verificã proprietatea cã oricaredouã arce vecine au o extremitate comunã.

Definitia 2.1.3.Numim lant (drum) hamiltonian un lant (drum) elementar al unui graf care contine toate vârfurilegrafului.

Definitia 2.1.4.Fie G = (V, E) un graf netrivial. Spunem cã x, y din V sunt conectate în G dacã existã un x-y lant în G.Graful G este un graf conex dacã oricare douã vârfuri din V sunt conectate în G. Dacã G este un graf trivial(E multime vidã) se acceptã cã este graf conex. Dacã G nu este conex atunci existã cel putin douãcomponente conexe (subgrafuri conexe maximale, disjuncte douã câte douã relativ la vârfuri). Un digraf Gcu proprietatea cã pentru oricare douã vârfuri x si y existã atât un x-y drum cât si un y-x drum în G senumeste graf tare conex.

În sectiunea urmãtoare prezentãm o metodã de reprezentare a algoritmilor folosind schemele logice.Acestea sunt introduse folosind terminologia teoriei grafurilor.

2.2. Scheme logice structurate

O transcriere graficã a etapelor (pasilor) unui algoritm este numitã organigramã. De cele mai multe orieste folositã denumirea de "schemã logicã". Fiecãrui pas, al algoritmului, i se asociazã un bloc ceconstituie eticheta unui arc. Blocurile folosite într-o schemã logicã descriu instructiuni (comenzi) saupredicate (expresii logice). Predicatele apar în cadrul instructiunii de ramificare. Celelalte instructiunisunt:

Instructiunea START: eticheteazã arcul initial (acel arc în a cãrui extremitate initialã nu pot sosialte arce). Orice schemã logicã are un unic arc initial. Acesta va indica punctul de unde începeexecutia unui program.

1.

Instructiunea STOP: eticheteazã un arc final (acel arc din a cãrui extremitate finalã nu pot plecaalte arce). O schemã logicã poate avea mai multe arce finale. Acestea indicã oprirea executieiprogramului descris prin intermediul schemei logice.

2.

Instructiunea CITESTE: eticheteazã un arc ce indicã introducerea de la mediul de intrare(tastaturã, disc etc.) a unei secvente de valori (numite date de intrare). Cuvântul CITESTE esteînsotit de variabilele ce descriu datele de intrare.

3.

Instructiunea SCRIE: eticheteazã un arc ce indicã înregistrarea la mediul de iesire (display, discetc.) a rezultatelor (datelor de iesire). Cuvântul SCRIE este însotit de variabilele sau constantele cedesemneazã datele de iesire.

4.

Instructiunea de atribuire: eticheteazã un arc cu eticheta v := e, unde v este o variabilã, iar e este oexpresie de acelasi tip (numeric sau logic) cu variabila v.

5.

Instructiunea de ramificare: este caracterizatã prin n arce ce pleacã din acelasi punct, arce6.


3 of 16 12/9/2007 7:20 PM

etichetate cu predicatele p1, p2, ..., pn definite astfel încât:

p1 or p 2 or ... or pn = TRUE (adevãrat) sipi and pj = FALSE (fals) pentru oricare i si j diferiti.

Definitia 2.2.1. Se numeste schemã logicã (sau program sub formã de schemã logicã) un graf orientat, încare:

existã o unicã instructiune START si cel putin o instructiune STOP;Orice vârf (diferit de extremitatea finalã a unei instructiuni STOP) este extremitatea initialã a uneiunice instructiuni;Orice arc este etichetat cu una dintre instructiunile: START, STOP, CITESTE, SCRIE, atribuire saucu un predicat. In ultimul caz, extremitatea initialã a arcului trebuie sã coincidã cu extremitateainitialã a unei instructiuni de ramificare.pentru orice arc existã cel putin un drum care începe cu instructiunea START, se terminã cu oinstructiune STOP si contine arcul considerat.

Schemele logice sunt folosite pentru descrierea algoritmilor. Se pot pune în evidentã structurifundamentale precum:

structura secventialã- formatã din arce conectate etichetate cu instructiuni distincte de cea de ramificare. O structurãsecventialã formatã din douã arce etichetate prin a, respectiv b se va nota prin SEQ(a,b) si aresemnificatia " executã a urmat de b".

1.

structuri decizionale(alternative) - contin, obligatoriu, cel putin un predicat si cel putin un bloc functional (instructiunealta decât START sau ramificativã). Structurile decizionale sunt de urmãtoarele forme:

IF(p; a, b) - Dacã p este adevãrat, atunci executã a altfel executã b (vezi figura 2.2a).IF0(p; a) - Dacã p este verificat, atunci a (vezi figura 2.2b).CASE(p1,p2,...,pn; a1, a2, ..., an) - Dacã p1 atunci a1, dacã p2 atunci a2, ..., dacã pn atunci an(vezi figura 2.2c).

2.

Structuri repetitive(structuri de tip ciclu, structuri iterative) - contin obligatoriu un bloc predicativ si un blocfunctional care se executã de un numãr finit de ori pânã când predicatul îsi schimbã valoarea.Sunt posibile trei situatii:

WHILE(p; a) - Cât timp conditia p este adevãratã se executã a, apoi se continuã cuurmãtoarea instructiune ( vezi figura 2.3a: ciclu cu test initial).REPEAT(p; a) - Repetã a pânã când conditia p este adevãratã, apoi executã instructiuneaurmãtoare ( vezi figura 2.3b: ciclu cu test final).FOR(p; a, b, c) - Este echivalentã cu SEQ(a, WHILE(p; SEQ(b, c))). Blocul a este un blocfunctional de initializare. Blocul b descrie instructiunea ce se va executa când conditia p esteadevãratã. Blocul c (prezentat explicit în aceastã structurã) va descrie actualizarea stãrilorvariabilelor programului cu rol deosebit în evaluarea conditiei p ( vezi figura 2.3c: ciclu cu contor).

3.

Exemplul 2.2.1. Urmãtoarea descriere reprezintã o secventã. Uneori secventele se pot eticheta (* vezi figura 2.4).

ET1 SEQ write('Introduceti 3 numere:'); read(x,y,z); media:=(x+y+z)/3;


4 of 16 12/9/2007 7:20 PM

writeln('Media = ',media);ET1 END

Eticheta secventei de mai sus este ET1, iar componentele secventei sunt instructiuni Pascal. Secventadescrie citirea a trei numere, calculul mediei aritmetice si afisarea rezultatului.

Exemplul 2.2.2. Urmãtoarele secvente ilustreazã structurile decizionale.

a)(* vezi figura 2.5a *)

ET2 SEQ read(x);> if (x>0) or (x=0) then write('Numar nenegativ') else write('Numar negativ');ET2 END

b)(* vezi figura 2.5b *)

ET3 SEQ read(titlu); cod:=0; if nume='algebra' then cod:=1; write(cod);ET3 END

c)(* exercitiu *)

ET4 SEQ zar:=1+random(6); case zar of 1, 3, 5 : impar:=impar+1; 2, 4, 6 : par:=par+1; endET4 END

Secventa ET2 descrie citirea unei valori (se presupune cã x este un numãr) si afisarea unui mesaj înfunctie de semnul numãrului x. Secventa ET3, citeste un titlu, iar dacã se introduce 'algebra' atuncicodul asociat este 1, în rest codul este 0. În final se scrie codul. Prin secventa ET4 se genereazã un numãraleator între 1 si 6. Apoi se analizeazã paritatea numãrului. Dacã secventa ET4 s-ar repeta, atuncivariabila impar ar contine numãrul de aparitii ale numerelor impare. Similar, variabila par va reprezenta numãrul numerelor pare generate.

Exemplul 2.2.3. Prin urmãtoarele secvente exemplificãm structurile repetitive: While, Repeat si For(Elaborarea schemelor logice este lãsatã ca exercitiu).

a)ET5 SEQ read(x);i:=1; cod:=0; while ((i


5 of 16 12/9/2007 7:20 PM

for i:=1 to n do begin read(x); suma:=suma+x end; writeln('Suma =', suma);ET7 END

Secventa ET5 descrie citirea unui element x si verificarea ipotezei: "Elementul x se aflã printre cele nelemente din tabloul a". În secventa ET6 se descrie generarea repetatã de numere pânã la aparitiavalorii 6. Secventa ET7, folosind variabila de contorizare i, citeste n numere, le calculeazã suma si apoi oafiseazã. Observati prezenta predicatului la iteratiile de tip While si Repeat.

Definitia 2.2.2. Un algoritm exprimat în functie de structurile SEQ, IF si WHILE se numeste structurat, schema logicãasociatã se numeste schemã logicã structuratã, iar programul corespunzãtor se numeste programstructurat.

Evident, familia algoritmilor structurati este nevidã. Un rezultat foarte important afirmã: Orice algoritm poate fi transformat într-un algoritm structurat. Aceastã afirmatie are la bazã teorema Bohm-Jacopini.Pentru a transforma o schemã logicã (nestructuratã) într-o schemã logicã structuratã se poate folosiregula variabilei booleene (ce rezultã din demonstratia teoremei Bohm-Jacopini). Cititorul interesat dedetalii poate consulta lucrarea: Corrado Bohm, Giuseppe Jacopini - Flow-diagrams, Turing Machines andlanguages with only two formation rules. Comm. ACM. 9 (May, 1966), 366-371. Una din consecintele importante ale programãrii structurate este eliminarea instructiunii de salt neconditionat (goto) dinprograme. Totusi, existã situatii când instructiunea goto este utilã. Lungimea programelor nu va creste,iar claritatea algoritmului nu va avea de suferit. Important este ca numãrul instructiunilor goto folositesã fie foarte mic, iar salturile sã fie locale.

2.3. Notiuni introductive privind organizarea datelor

Organizarea datelor, în vederea prelucrãrii acestora, este un proces complex, dar de o deosebitãimportantã. De modul în care sunt structurate datele, depinde eficienta algoritmilor de prelucrare.Unele date sunt de tip simplu: data apare ca o entitate indivizibilã atât din punct de vedere a informatieipe care o reprezintã cât si în raport cu unitatea centralã de prelucrare. Alte date sunt descrise princomponente, cu acelasi tip sau cu tipuri diferite. O colectie de date pe care s-a evidentiat un anumit modde structurare si s-au stabilit procedeele de înregistrare/identificare a componentelor se va numistructurã de date. Componentele unei structuri de date pot fi de tip elementar sau pot fi, la rândul lor,structuri. Identificarea unei componente se poate face prin pozitia pe care o ocupã în structurã sau prinnume.

Pentru o datã elementarã trebuie specificate: un identificator, atribute (domeniul de valori, modul dereprezentare în sistemul de calcul, precizia reprezentãrii) si valorile datei (pot fi enumerate sau indicateprintr-o proprietate comunã). Din punct de vedere al domeniului de valori asociat unei date se distingurmãtoarele clase:

date de tip integer (numere întregi);date de tip real sau float (cu elemente din multimea numerelor rationale);date de tip boolean (se referã la valorile de adevãr true (adevãrat), false (fals));date de tip char (cu elemente ale multimilor ASCII sau Unicode);date de tip string (obtinute prin concatenarea datelor de tip caracter);date de tip array(structurã cu componente de acelasi tip ce ocupã locatii succesive din memoria sistemului de


6 of 16 12/9/2007 7:20 PM

calcul, identificate prin pozitie);date de tip record (structurã cu componente oarecari, identificate prin nume).

Un mod special de organizare a datelor este întâlnit când avem de prelucrat liste. O listã liniarã este ostructurã de date omogenã, secventialã, formatã din elemente apartinând unei multimi date. O listãpoate fi vidã (nu are nici un element) sau plinã (nu mai existã spatiu pentru stocarea unor componentesuplimentare). Este foarte important sã putem accesa un element al listei, sã inserãm sau sã stergem unelement etc.

Listele pot fi stocate în memoria unui sistem de calcul în douã moduri: secvential si înlãntuit. Modulsecvential presupune stocarea elementelor listei în locatii succesive de memorie conform ordiniielementelor din listã si retinerea adresei primului element al listei (adresa de bazã). Modul înlãntuitpresupune cã fiecare element al listei este înlocuit cu o celulã formatã dintr-o parte de informatie(corespunzãtoare elementului listei) si o parte de legãturã ce contine adresa celulei urmãtorului elementdin listã. Se va retine adresa de bazã a listei, iar ultima celulã va indica, în partea de legãturã, o valoarespecialã (ce nu poate desemna o legãturã).

Structura de date elementarã adecvatã reprezentãrii secventiale a listelor este tabloul unidimensional.

Orice listã liniarã are un început si un sfãrsit pe care le numim bazã, respectiv vârf. O listã liniarã lacare inserarea si extragerea elementelor se face prin vârful listei se numeste stivã (stack). O listã liniarãîn care inserãrile se efectueazã la baza listei, iar extragerile prin vârful listei se numeste coadã (queue).

Listele liniare pot fi transformate în liste circulare considerând cã legãtura ultimului element indicãadresa bazei listei.

2.4. Limbaj algoritmic

O altã modalitate de reprezentare a algoritmilor o constituie utilizarea limbajului algoritmic. Limbajulalgoritmic foloseste o scriere similarã limbajelor de programare moderne. El permite atât descriereainstructiunilor algoritmului cât si descrierea exactã a tipului datelor cu care lucreazã algoritmul. Unalgoritm descris folosind limbajul algoritmic este o succesiune finitã de declarãri si instructiuni.Declarãrile precizeazã tipul si organizarea datelor. Ele apar înaintea instructiunilor ce descriu pasiialgoritmului. Din punct de vedere al scrierii instructiunilor, o instructiune poate ocupa mai multerânduri sau pe un rând pot fi scrise mai multe instructiuni. Instructiunile vor fi separate, între ele,folosind caracterul ';'.

Cuvintele care identificã un tip de date sau o instructiune, numite în continuare cuvinte cheie, aparevidentiate pentru a fi deosebite de numele variabilelor. O declarare utilizeazã unul dintre cuvintelecheie integer, real, boolean, char, string, array, record, stack, queue, urmat de o listã de nume devariabile. Declarãrile sunt separate, între ele, folosind caracterul ';'. Variabilele prezente într-o listã autipul si organizarea precizatã prin cuvântul cheie respectiv. De exemplu, declarãrile:integer array a(10);record (integer cod; string nume; real media) x, y; stack S; queue Q; char ch; boolean ind;indicã faptul cã a este un tablou cu maxim 10 elemente întregi; x si y sunt înregistrãri (cu treicomponente: cod - o valoare întreagã, nume - un sir de caractere, media - un numãr real), S este o stivã,Q este o coadã, ch este un caracter, iar ind este o variabilã logicã.

O importantã deosebitã o au declarãrile de subprograme. În rezolvarea multor probleme aparenecesitatea executãrii repetate a acelorasi calcule pentru date diferite. Subprogramele permit descriereaacestor calcule o singurã datã. Subprogramul poate fi apelat ori de câte ori este necesarã efectuarea


7 of 16 12/9/2007 7:20 PM

acestor operatii. Un subprogram este identificat printr-un nume si o listã de parametri. Subprogramelese împart în proceduri si functii. Delararea unei proceduri constã în specificarea cuvântului procedure, a unui identificator al procedurii si a unei liste de declarãri (între paranteze rotunde) ce indicãinformatiile ce fac obiectul transferului între apelant si apelat. Pentru declararea unei functii se folosestecuvântul cheie function. Spre deosebire de proceduri, functiile întorc obligatoriu un rezultat. De aceea,în declaratii, declararea unei functii începe cu specificarea multimii de valori ce corespunde rezultatului,a cuvântului function, a identificatorului functiei si a listei parametrilor (similar ca la o procedurã).

Un algoritm este complet cunoscut dacã este descrisã si definitia subprogramelor folosite. Definitia unuisubprogram presupune descrierea (prin instructiuni) modului în care se efectueazã calculele si setransmit rezultatele. Mai multe detalii prezentãm în finalul acestei sectiuni.

Instructiunile limbajului algoritmic sunt urmãtoarele:

Instructiunea de atribuire. Aceastã instructiune are forma: v := E (atribuire simplã) sau (v1, v2, ..., vn) := (E1, E2, ..., En) ce realizeazã simultan atribuirile vi :=Ei, pentru oricare i = 1, 2, ..., n. Operatia de atribuire este permisã când variabila v (variabilele v1, v2, ..., vn) din membru stâng siexpresia E (expresiile E1, E2, ..., En) sunt compatibile (se referã la aceeasi aclasã de obiecte). Oexpresie contine paranteze (optional), operanzi (inclusiv apeluri de functii) si operatori adecvati.

1.

Instructiuni de intrare/iesire.Vom presupune cã citirea datelor (de intrare) se face de la un mediu de intrare (de exemplu:tastatura sistemului de calcul), iar scrierea rezultatelor (de iesire) se face la un mediu de iesire (deexemplu: ecranul, imprimanta, plotterul etc.). Forma instructiunilor de intrare/iesire este:read v1, v2, ..., vnwrite v1, v2, ..., vnunde v1, v2, ..., vn sunt variabile de tip elementar.

2.

Instructiunea repetitivã While. Aceastã instructiune are forma: while p do S, unde p este unpredicat, iar S este o secventã de instructiui. Deoarece instructiunile sunt separate între ele,folosind ';' va trebui sã delimitãm secventa S. Pentru aceasta se utilizeazã constructia SEQ..ENDprezentatã mai sus. Semnificatia acestei instructiuni este aceeasi ca pentru sub-schema logicãWhile(p; S).

3.

Instructiunea If_then_else. Aceastã instructiune are forma: if p then S1 [elseS2 ], unde p este un predicat, iar S1 si S2 sunt secvente de instructiuni. Dacã neîndeplinirea predicatului p nu indicãvreo actiune, portiunea elseS2 poate lipsi, fapt reprezentat prin includerea între paranteze drepte, exprimarea fiindechivalentã cu IF0(p; S1). Atunci când atât S1 cât si S2 sunt actiuni prevãzute, instructiunea esteechivalentã cu sub-schema logicã IF(p; S1, S2).

4.

Instructiunile insert si extract. Aceste instructiuni sunt necesare pentru lucrul cu liste. Acesteasunt o prelungire a instructiunii de atribuire. Dacã se specificã o listã L atunci insert i, L (sau L:=i)exprimã introducerea elementului specificat prin i în lista L, iar instructiunea extract i, L (saui:=L) specificã extragerea elementului curent din lista L si depunerea acestuia în i.

5.

Instructiunea apel de procedurã. Apelarea unei proceduri se face prin instructiunea apel deprocedurã care are una din formele: identificator_procedurasauidentificator_procedura(lista de argumente)unde identificator_procedura specificã o procedurã declaratã, iar argumentele sunt expresiiseparate prin virgulã.

Se presupune cã atunci când se ajunge la un apel de procedurã se stabileste corespondenta întreargumente si parametri, si se executã toate instructiunile specificate în definitia procedurii. Dupãultima instructiune a procedurii se continuã cu instructiunea urmãtoare apelului de procedurã.

6.


8 of 16 12/9/2007 7:20 PM

Un apel de procedurã este corect atunci când între argumente si parametri existã o concordantã canumãr, tip si mod de organizare. Convenim ca atunci când referim o variabilã (într-o procedurã)de fapt, facem o referire la locatia de memorie corespunzãtoare argumentului respectiv. Spunemcã se realizeazã un transfer prin referintã. Sunt posibile si alte moduri de transfer, dar acestea nusunt considerate momentan.

Instructiunea return. Aceastã instructiune provoacã pãrãsirea corpului unui subprogram. În cazulîn care cuvântul returneste urmat de o expresie, valoarea expresiei este folositã ca valoare de retur a subprogramului.Instructiunea returnfãrã valoare de retur este folositã pentru a pãrãsi executia unei proceduri si a reveni în unitatea deprogram din care a avut loc apelul; si anume la instructiunea ce urmeazã imediat acestui apel.

7.

Pentru a usura descrierea algoritmilor admitem prezenta, ca instructiuni ale limbajuluialgoritmic, a instructiunilor Repeat si For. Instructiunea Repeat este modelatã de structurarepetitivã REPEAT (p; S). Ea are forma: Repeat S until p;unde S este o secventã (eventual vidã) de instructiuni, iar p modeleazã o expresie logicã.

Instructiunea For este modelatã de structura iterativã FOR(p; a,b,c) si are forma simplificatãFor v := e1, e2, e3 do Sunde: S este o secventã de instructiuni, iar expresiile e1, e2 si e3 au acelasi domeniu de valori cavariabila v. În forma prezentatã, instructiunea determinã executarea secventei S pentru v luândsuccesiv valorile e1, e1+e3, e1+2e3, ..., fãrã a trece dincolo de e2. Formei de mai sus îi corespundestructura iterativã:FOR((v-v2)*v3≤0; SEQ v:= e1; v1 :=e2; v3:=e3 END, S, v := v +v3).

8.

2.5. Analiza complexitãtii

Existenta unui algoritm de rezolvare a unei probleme genereazã, imediat, întrebãri ca: Mai existã un altalgoritm de rezolvare? Este algoritmul gãsit "cel mai rapid"? Acest paragraf introduce notiunilefundamentale privind complexitatea algoritmilor si prezintã exemple simple de algoritmi pentru care sedeterminã complexitatea.

Analiza complexitãtii unui algoritm presupune determinarea resurselor de care acesta are nevoie pentrua produce datele de iesire. Prin resursã întelegem timpul de executare, dar uneori este necesar sãanalizãm si alte resurse precum: memoria internã, memoria externã etc. Modelul masinii pe care va fiexecutat algoritmul nu presupune existenta operatiilor paralele; operatiile se executã secvential.

Timpul de executare al unui algoritm reprezintã numãrul de operatii primitive executate. Trebuie,pentru fiecare algoritm, sã definim notiunea de operatie primitivã, independent de masina secventialã pecare se va executa algoritmul.

În analiza complexitãtii unui algoritm avem în vedere cazul cel mai defavorabil din mai multe motive:

Timpul de executare în cazul cel mai defavorabil oferã o limitã superioarã a timpului de executare(avem certitudinea cã executarea algoritmului nu va dura mai mult).

1.

Situatia cea mai defavorabilã este întâlnitã des.2.Timpul mediu de executare este, uneori, apropiat de timpul de executare în cazul cel maidefavorabil, dar dificil de estimat.

3.

Analiza exactã a complexitãtii unui algoritm conduce la formule extrem de complicate. De aceea sefolosesc notatii asimptotice, care evidentiazã doar termenul preponderent al formulei.


9 of 16 12/9/2007 7:20 PM

Fie f si g douã functii reale. Atunci:

f(x) = o(g(x)) dacã existã si este egalã cu 0 (zero) limita:

f(x) = O(g(x)) dacã existã c si x0 astfel încât

f(x) = theta(g(x)) dacã existã constantele C1 si C2 pozitive, si x0 astfel încât pentru orice x≥ x0:

f(x) ~ g(x) dacã

f(x) = Omega(g(x)) dacã existã M>0 si un sir x1, x2, ..., xn, ... Inf astfel încât pentru oricare j>0 areloc inegalitatea

În general, se considerã cã un algoritm este mai rapid decât altul dacã are un ordin de mãrime pentrutimpul de executare mai mic. Pentru o dimensiune micã a datelor de prelucrat, aceste comparatii pot fi(însã) eronate.

Notatia theta este utilizatã pentru a specifica faptul cã o functie este mãrginitã (inferior si superior).Semnificatia notatiei O este de limitã superioarã, în timp ce semnificatia notatiei Omega este de limitãinferioarã.Exemple: x3 = o (x5); sin(x) = o (x); (x+1)2 = theta (2x2); x2+3x ~ x2.

Definitia 2.5.1.Fie A un algoritm, n dimensiunea datelor de intrare si T(n) timpul de executare estimat pentrualgoritmul A. Se spune cã algoritmul A are comportare polinomialã (apartine clasei P) dacã existã p>0astfel încât T(n) = O(np).

Definitia 2.5.2. O functie care creste mai rapid decât functia putere xp, dar mai lent decât functiaexponentialã axcu a>1 se spune cã este cu crestere exponentialã moderatã. Mai precis: f este cu crestere exponentialãmoderatã dacã pentru oricare p>0 avem f(x) = Omega(xp) si oricare M>0 avem f(x) = o((1+ M)x).

Definitia 2.5.3. O functie f are crestere exponentialã dacã existã a>1 astfel încât f(x) = Omega(ax) siexistã b>1 astfel încât f(x) = O(bx).

Printre functiile n -> f(n), nemãrginite, functiile ce cresc cel mai lent sunt, de exemplu, de forma log log nsau (log log n)1,02. Pentru n = 1000000, log log n ~ 2,6. Deci un algoritm a cãrui complexitate este log logn este preferabil unui algoritm (elaborat pentru rezolvarea aceleiasi probleme) de complexitate log n.Algoritmii de tip polinomial sunt mai lenti (cresterea functiei T(n) este mai rapidã) decât algoritmii detip logaritmic. Urmeazã apoi algoritmii moderati (cu T(n) de forma nlogn etc.) si cei cu crestereexponentialã (2n, n33netc.). Algoritmii cei mai lenti sunt cei pentru care functia T(n) este foarte rapid crescãtoare (de exemplu:T(n) = n!).

În informaticã sunt interesanti numai algoritmii care conduc la un timp de calcul cel mult moderat.Dacã un algoritm necesitã timp de calcul exponential sau factorial, acesta va fi utilizat numai în cazuri


10 of 16 12/9/2007 7:20 PM

exceptionale. Tabelul urmãtor ilustreazã cele de mai sus.

n 10 100 1000 10000

n2 100 10000 1000000 100000000

n3 1000 1000000 1000000000 1000000000000

log n 1 2 3 4log log n 0 0.30103 0.47712 0.60206

Exemplul 2.5.1. (Produsul a douã numere complexe). Considerãm numerele complexe a+bi si c+di (i2 = -1; a, b, c, d numere reale). Un algoritm pentru calculul produsului (a+bi)(c+di) este urmãtorul:

real a,b,c,d,p,q; real t1,t2; P1 SEQ Read a, b, c, d; t1:=a*c; t2:=b*d; p:=t1-t2; t1:=a*d; t2:=b*c; q:=t1+t2; write p,q; P1 END

Acest algoritm (notat P1) necesitã 4 înmultiri, o adunare si o scãdere. În final p reprezintã partea realã,iar q furnizeazã partea imaginarã a produsului celor 2 numere complexe. Urmãtorul algoritm (notat P2)calculeazã acelasi produs folosind 3 înmultiri, 3 adunãri si 2 scãderi:

real a,b,c,d,p,q; real t1,t2,t3,t4;P2 SEQ Read a, b, c, d; t1:=a+b; t2:=t1*c; t1:=d-c; t3:=a*t1; q:=t2+t3; t1:=d+c; t4:=b*t1; p:=t2-t4; write p,q;P2 END

Algoritmul P1 necesitã 2 locatii temporare, în timp ce algoritmul P2 necesitã 4 locatii suplimentare. Înplus, necesarul de memorie depinde de metoda de reprezentare a numerelor reale într-un sistem decalcul.

(Determinarea valorii maxime si a indicelui corespunzator, dintr-un sir (tablou)). Fie X un tablou cu nelemente apartinând unei multimi total ordonate Q: X = (x1, x2, ..., xn) cu xi din Q pentru i = 1, 2, ..., n. Fie y o variabilã de tipul Q. Se cautã un indice k, între 1 si n astfel ca y := max{xi : i=1, 2, ..., n | = xk, iar k este cel mai mic numãr cu aceastã proprietate.

Pentru rezolvarea acestei probleme putem utiliza urmãtorul algoritm, denumit în continuare MAXIM,pentru Q = real.

procedure maxim(x,n,y,k) integer n;real array x(n); real y; integer i,k; SEQ k:=1; y:=x[1]; for i = 2, n, 1 do if y < x[i] then SEQ y := x[i]; k:=i END; return END


11 of 16 12/9/2007 7:20 PM

Observãm cã T(n) = n-1. Necesarul de memorie pentru stocarea datelor de prelucrat se exprimã înfunctie de metoda de reprezentare a informatiei în calculator.

Propozitia 2.5.1.Pentru determinarea maximului dintre n elemente ale unei multimi total ordonate sunt necesare celputin n-1 comparãri (T(n) = n-1).

Exemplul 2.5.3. (Determinarea celui mai mare divizor comun). Fie m si n douã numere întregi pozitive si,q si r câtul, respectiv restul împãrtirii lui n la m, adicã n = qm+r (0 ≤ r < m). Spunem cã m divide n dacãrestul împãrtirii lui n la m este zero.

Pentru determinarea celui mai mare divizor comun (cmmdc) a douã numere se poate utiliza algoritmullui Euclid. Dacã d este un divizor oarecare al numerelor n si m, atunci d divide restul r. Reciproc, dacã deste un divizor al numerelor m si r, relatia n = mq + r aratã cã d este divizor al numãrului n. Deci:

cmmdc(n, m) = cmmdc(m, r).

Dacã r = 0 atunci n = qm. Deci cmmdc(n, m) = m. Folosind notatia n mod m pentru r, putem scrie:

cmmdc(n, m) = cmmdc(m, n mod m).

Necesarul de memorie pentru stocarea numerelor n si m se poate exprima prin

theta(log m) + theta(log n) ~ theta(log (mn)) biti.

Timpul necesar executãrii algoritmului este dat de urmãtorul rezultat.

Propozitia 2.5.2.Fie n si m douã numere întregi pozitive. Algoritmul lui Euclid pentru a determina cmmdc(m, n)efectueazã cel mult [2log2M]+1 operatii de împãrtire întreagã, unde M = max (m, n).

Exemplul 2.5.4. (Sortare prin insertie). Fiind datã o secventã de elemente caracterizate de valorile x1, x2,..., xn apartinând unei multimi total ordonate T, sã se determine o permutare xi(1), xi(2), .., xi(n) asecventei date, astfel încât xi(j) ≤ xi(k)pentru i(j) ≤ i(k), unde " ≤ " este relatia de ordine pe multimea T. Metoda ce va fi prezentatã încontinuare se mai numeste si "metoda jucãtorului de cãrti", si este una dintre cele mai cunoscute metodede sortare.

Sortarea prin insertie se bazeazã pe urmãtoarea procedurã: Fie un tablou x cu n elemente (x[i] este ali-lea element din secventa de intrare). Pornim cu subtabloul x[1] si la primul pas cãutãm pozitia în carear trebui sã se gãseascã elementul x[2]. Dacã x[2] < x[1], atunci x[2] trebuie sã fie mutat în loculelementului x[1]. La un pas i (pentru i între 1 si n), avem subtabloul x[1..i-1] ordonat si încercãm sã-lplasãm pe x[i] astfel încât sã obtinem un tablou sortat între pozitiile 1 si i. Pentru aceasta, se comparãsuccesiv x[i] cu elementele tabloului x[1..i-1] pentru a se determina acea pozitie j pentru care x[i] ≥ x[j],indexul de plasare fiind j+1.

Algoritmul prezentat în continuare utilizeazã insertia directã:

procedure insert_sort(n,x); integer n; integer array x(n); integer i,j,temp; SEQ for i = 2, n, 1 do SEQ


12 of 16 12/9/2007 7:20 PM

temp :=x[i]; j:=i-1; while (j>=1) and (x[j] > temp) do SEQ x[j+1] :=x[j]; j:=j-1 END x[j+1]:=temp END; return END

Este clar cã, timpul de executie nu depinde doar de n, numãrul de elemente de sortat, ci si de pozitiainitialã a elementelor din secventã.

Fie F(n) - numãrul de comparãri necesare, iar G(n) numãrul de mutãri necesare algoritmului insert_sortpentru sortarea unui tablou cu n elemente.

Propozitia 2.5.3.Complexitatea metodei de sortare prin insertie directã este caracterizatã prin: F(n) = O(n2), G(n) =O(n2).

2.6. Elemente privind corectitudinea algoritmilor

A verifica corectitudinea unui algoritm înseamnã a verifica dacã algoritmul conduce într-un intervalfinit de timp la obtinerea solutiei corecte a problemei pentru care a fost elaborat. Vom vedea în capitolul5 câteva metode de rezolvare a problemelor, deci de a elabora algoritmi. Metodele descrise în acestcapitol se vor exemplifica pentru algoritmi simpli. Pentru aspecte suplimentare legate de corectitudineaalgoritmilor se poate folosi lucrarea: Tudor Bãlãnescu. Corectitudinea algoritmilor. Editura Tehnicã,Bucuresti, 1995.

Notatie. Constructia {P}A{Q}, numitã si formulã de corectitudine totalã contine urmãtoarele elemente:

P - comentariu care descrie proprietãtile datelor de intrare (preconditia);

A - algoritmul (secventa de instructiuni) supus analizei;

Q - comentariu care descrie propriet{tile datelor de iesire (postconditia).

Definitia 2.6.1. Un algoritm {P}A{Q} este corect când propozitia urmãtoare este validã:

Dacã

datele de intrare satisfac preconditia P

Atunci

1) executarea lui A se terminã (într-un interval finit de timp) si

2) datele de iesire satisfac postconditia Q.

Folosind elementele fundamentale ale logicii matematice rezultã cã urmãtoarele observatii suntadevãrate:

Algoritmul {false}A {Q} este corect, oricare ar fi A si Q.1.


13 of 16 12/9/2007 7:20 PM

Algoritmul {P}A{true} este corect dacã si numai dacã executarea lui A se terminã atunci cânddatele initiale satisfac proprietatea P.

2.

Dacã{P}A{Q} si {R}A{Q} sunt formule corecte, atunci {P v R}A {Q} este formulã corectã.3.

Pentru a stabili corectitudinea algoritmilor complecsi se procedeazã la descompunerea acestora îelemente simple a cãror corectitudine se analizeazã. În continuare vor fi prezentate reguli pentru aanaliza corectitudinea unor astfel de algoritmi. Pentru o formalizarea avansatã a acestor reguli, cititorulinteresat poate parcurge lucrarea: C. A. R. Hoare et al. Laws of Programming. Comm. ACM. 30(8), 1987,672-687.

Regula compunerii secventiale (CS):

Dacã A este de forma SEQ B; C END atunci a verifica formula {P}A{Q}, revine la a verifica form{P}B{R} si {R}C{Q}, unde R este un predicat asupra datelor intermediare.

Este evident cã regula CS poate fi aplicatã iterativ. Mai precis, dacã A este de forma SEQ A1; A2; ..., AnEND atunci obtinem regula compunerii secventiale generale:

&t9;CSG: Dacã {P0} A1 {P1}, {P1} A2 {P2}, ...., {Pn-2}An-1{Pn-1} si

{Pn-1}An{Pn} sunt algoritmi corecti,

atunci{P0}A{Pn} este algoritm corect.

Exemplul 2.6.1.Este usor de verificat cã urmãtorul algoritm este corect (presupunem cã x si y sunt variabile întregi, iara si b constante întregi):

{ x = a si y = b} SEQ x:=x+y; y:=x-y; x:=x-y END{ x = b si y = a }

Regula implicatiei (I):

Aceastã regulã este utilã în cazul algoritmilor ce urmeazã a fi aplicati în conditii mai tari decât pentrucele care au fost deja verificati.

O proprietate P este mai tare decât proprietatea Q dacã este adevãratã propozitia compusã: P -> Q.

Regula implicatiei are urmãtoarea formã:

I: Dacã{P} A {Q} este algoritm corect, P1 -> P si Q -> Q1,

atunci {P1} A {Q1} este algoritm corect.

Regula instructiunii de atribuire (A):


14 of 16 12/9/2007 7:20 PM

Fie notatiile:

x Variabilã simplã

e Expresie;

Def(e) Proprietatea satisfãcutã de acele elemente pentru care evaluareaexpresiei e este corectã (Exemplu: pentru integer array b(10),Def(b(i)):= (i=1, 2, ..., 10));

P(x) Formulã în care apare variabila x;

P(x/e) Formula obtinutã din P(x) prin substituirea variabilei simple x cuexpresia e, ori de câte ori x este variabilã liberã în P, iar dacã econtine o variabilã y care apare legatã în P, înainte de substitutievariabila y se înlocuieste printr-o nouã variabilã (care nu mai apareîn e).

Valoarea de adevãr a propozitiei P -> Q(x/e) nu se schimbã dacã în Q(x/e) se efectueazã substitutiadescrisã de atribuirea x := e. Regula atribuirii este deci:

A: Dacã P -> (Def(e) and Q(x/e)) atunci algoritmul {P} x:=e {Q} este corect.

Exemple de instructiuni corecte:

a){x = n!} n:=n+1; x:=x*n {x = n!}

b){(x = a) and (y = b)} t:=x; x:=y; y:=t {(x = b) and (y = a)}

c){(1 Def(c) este adevãratã

Atunci formula

{P} if c then A else B {Q} este corectã.

IFR: Dacã


15 of 16 12/9/2007 7:20 PM

{P and c} A {Q} este corectã, iar P and (not c) -> Q si P -> Def(c) sunt adevãrate

Atunci

{P} if c then {Q} este formulã corectã.

Se poate observa cã aplicarea regulilor instructiunii de decizie nu este în sine dificilã corectitudineaacestei instructiuni se reduce la corectitudinea instructiunilor componente.

Exemple de instructiuni corecte:

a){true} if x>y then SEQ t:=x; x:=y; y:=t END {x =y then m:=x else m:=y {m = max(a,b)}

c){x=a} if x Def(c)).

Proprietatea I rezultã prin executarea secventei A (adicã, {P} A {I} este algoritm corect).

La terminarea instructiunii while, proprietatea finalã Q poate fi dedusã (adicã, I and (not C) -> Q).

I este proprietate invariantã la executarea unei iteratii: dacã I este adevãratã înainte de executareasecventei S si expresia booleanã c este adevãratã, atunci executarea secventei S se terminã într-uninterval finit de timp si I este adevãratã la sfârsit (adicã, {I and c} S {I} este algoritm corect).

Dacã rezultatul evaluãrii expresiei c este true si proprietatea I este adevãratã, atunci existã celputin o iteratie de efectuat (adicã, I and c -> (t > =1)).

Valoarea lui t descreste dupã executarea unei iteratii (adicã, {(I and c) and (t=a)} S {t < a}).

În aceste conditii, algoritmul considerat este corect.

Exemplul 2.6.2. (Determinarea celui mai mare divizor comun a douã numere întregi). Fie a si b douãnumere întregi, iar m = |a| si n = |b|. Atunci urmãtorul algoritm este corect.

{(x > 0) and (y > 0) and (x = m) and (y = n)}

while x y do

if x > y then x := x - y else y := y - x;


16 of 16 12/9/2007 7:20 PM

{x = cmmdc(m,n)}

Într-adevãr, existã proprietatea invariantã

I: (cmmdc(x,y) = cmmdc(m,n)) and (x > 0) and (y > 0),

iar ca functie de terminare se poate lucra cu: t(x,y) = x+y. Verificarea ipotezelor regulii W este simpl˜.

Exemplul 2.6.3. (Al n-lea termen al sirului lui Fibonacci). Fie fn, al n-lea termen al sirului lui Fibonacci.Urmãtorul algoritm este corect.

{n >= 0}

a:=0; b:=1; k:=n;

while (k > 0) do

SEQ

temp := b;

b := a + b;

a := temp;

k := k-1

END;

{a = fn}

Într-adevãr, luãm functia de terminare t(k) = k, iar proprietate invariantã este:

I: (a = fn-k ) and (b = fn-k+1) and (temp = fn-k) and (0

Limbaje de programare - C Autor: Prof. Univ. Dr. Grigore Albeanu file:///C:/ACTIV/Proc/FINAL/C4.HTM

1 of 48 12/9/2007 7:21 PM

3. Limbaje de programare

3.1. Vocabularul si sintaxa limbajelor de programare3.2. Tipuri de date. Constante. Variabile. Expresii3.3. Programare în C

3.1. Vocabularul si sintaxa limbajelor de programare

Vocabularul unui limbaj de programare este format din cele mai simple elemente cu semnificatie lingvisticãnumite entitãti lexicale sau tokens. Elementele vocabularului sunt alcãtuite din caractere Unicode (cconstituie alfabetul limbajului). Standardul Unicode contine ca subset codul ASCII, dar reprezentareainternã a caracterelor Unicode foloseste 16 biti. Cele mai utilizate simboluri sunt: literele mari si malfabetului englez, cifrele sistemului zecimal, diferite semne speciale.

Unitãtile lexicale sunt separate, între ele, prin comentarii si spatii. Pentru aproape toate limbajeleprogramare se pot evidentia unitãti lexicale precum: cuvinte cheie, identificatori, literali, separatorioperatori. Cuvintele cheie sunt secvente de caractere ASCII rezervate (nu pot avea altã semnificatie)utilizate pentru definirea unitãtilor sintactice fundamentale. Pentru exemplificare ne referim la limbajele deprogramare Pascal si Java:

Cuvinte cheie Pascal: absolute, and, array, begin, case, const, div, do, downto, else, end, external, file,for, forward, function, goto, if, implementation, in, inline, interface, interrupt, label, mod, nil, not, of,or, packed, procedure, program, record, repeat, set, shl, shr, string, then, to, type, unit, until, uses,var, while, with, xor.

1.

Cuvinte cheie Java: abstract, boolean, break, byte, case, cast, catch, char, class, const, continue,default, do, double, else, extends, final, finally, float, for, future, generic, goto, if, implements, import, inner, instanceof, int, interface, long, native, new, null, operator, outer, package, private, protected, public, rest, return, short, static, super, switch, synchronized, this, throw, throws, transient, try, var, void, volatile, while, byvalue. Cuvintele cheie subliniate sunt prezente si in limbajul C alaturi de altele.

2.

Identificatorii sunt secvente, teoretic nelimitate, de litere si cifre Unicode, începând cu o literã sau liniuta desubliniere (în limbajul C). Identificatorii nu pot fi identici cu cuvintele rezervate.

Literalii ne permit introducerea valorilor pe care le pot lua tipurile de date primitive si tipul sir decaractere. Mai precis, lieralii sunt constante întregi, flotante, booleene, caracter si, siruri de caractere.

Literalii întregi, în general, pot fi descrisi prin reprezentãri în una din bazele de numeratie: 10, 16 sLungimea reprezentãrii interne depinde de implementarea limbajului. De exemplu, în limbajul Pascal, literal întreg, cu semn, este reprezentat pe 16 biti, descrierea sa în baza 16 fiind o secventã a simbolurasociate reprezentãrii numãrului întreg în baza 16 având prefixul $.

Literalii flotanti reprezintã numere rationale. Ei sunt formati din urmãtoarele elemente: partea întreapartea fractionarã si exponent. Exponentul, dacã existã, este introdus de litera E sau e urmatã optional deun semn al exponentului. Exemple: 3.14; 23.5 e+2; 3e-123.

Literalii booleeni sunt TRUE si FALSE, primul reprezentând valoarea booleanã de adevãr, iar celãlvaloarea booleanã de fals. Desi TRUE si FALSE nu sunt cuvinte rezervate, acestea nu pot fi folos


2 of 48 12/9/2007 7:21 PM

identificatori (în Pascal, Java s.a).

Literalii caracter sunt folositi pentru a desemna caracterele codului Unicode (sau ASCII, acolo unde escazul). Descrierea unui literal caracter se fie folosind o literã, fie o secventã specialã. Secventele specia(numite secvente escape în C, C++ si Java) permit specificarea caracterelor fãrã reprezentare graficãprecum si a unor caractere speciale. Caracterele ce au reprezentare graficã pot fi descrise între apostrofuri,ca în exemplele: 'P', 'A', '3', '!'. Secventele speciale se descriu diferit de la un limbaj la altul. Vomexemplifica folosind limbajele Pascal si Java.

Secvente speciale în limbajul Pascal: 1) Un întreg din domeniul 0, ..., 255 precedat de simbolul #desemneazã un caracter dat prin codul sãu ASCII. 2) Un caracter imprimabil precedat de semnuldesemneazã un "caracter de control" având codul ASCII în domeniul 0, ..., 31.

Secventele escape în limbajul Java se descriu folosind apostrofuri, semnul \, litere si cifre. Vom exemindicând câteva secvente predefinite: '\b' (backspace = #8), '\n' (linefeed), '\r' (carriage return) etc.

Un literal sir de caractere este constituit din zero sau mai multe caractere între delimitatori. Secventcaractere ce formeazã sirul poate contine atât caractere imprimabile cât si secvente speciale. În limbajPascal se utilizeazã apostroful ca delimitator, iar în limbajul C( C++, Java) ghilimelele.

Separatorii sunt caractere ce indicã sfârsitul unui token si începutul altuia. Acestia participã si laconstructia sintaxei limbajelor de programare. Ei nu trebuie confundati cu spatiile care si acestea sepaunitãti lexicale distincte. Separatorii sunt necesari când unitãtile lexicale diferite sunt scrise fãrã spatii întreele. Cei mai întâlniti separatori sunt: ( ) { } [ ] ; , . Exemple: x[10], f(x,y), carte.autor etc. Operatorii suntsimboluri grafice ce desemneazã operatiile definite de un limbaj de programare. În unele limbajeprogramare este posibilã redefinirea operatorilor, acelasi simbol fiind utilizat pentru operatii diferite rezultã din contextul în care apar. Lista minimalã a operatorilor aritmetici include: +(adunare), /(împãrtire), *(înmultire). Mai sunt admise si operatii precum: % (C, Java) sau mod (Pascal, Modu(împãrtire întreagã în limbajul Pascal). Alti operatori sunt: operatori logici, operatori relationali, operatoriasupra sirurilor de caractere etc. Toti operatorii pot fi priviti si ca separatori.

O constructie aparte utilizatã în programe pentru explicarea sau documentarea textului programcomentariul. Comentariile sunt delimitate de textul programului folosind anumiti delimitatori. În limbPascal, un comentariu este scris între acoladele ã } sau între secventele (*, *). Programele C++, Java pcontine comentarii pe o singurã linie si încep cu //, sau pe mai multe linii si sunt cuprinse între /* si */.

Alte elemente lexicale ce pot fi prezente într-un program sunt etichetele si clauzele. Etichetele sunt siruri decifre zecimale/hexazecimale sau identificatori folosite în legãturã cu o instructiune de salt (goto) penmarcarea unor instructiuni. Clauzele (numite si directive) sunt cuvinte cheie ce desemneazã instructiuniefect în timpul compilãrii.

Prin sintaxa unui limbaj de programare se întelege, în general, un ansamblu de reguli privind agregunitãtilor lexicale pentru a forma structuri mai complexe (declaratii, instructiuni, module, prograPrezentarea acestor reguli se poate folosind limbajul natural sau mecanisme formalizate. Descriereasintaxei în limbaj natural poate conduce la neclaritãti sau specificatii incomplete. Cu ajutorul mecanismelorformale sintaxa unui limbaj este complet specificatã. Cea mai folositã notatie este cunoscutã sub numelnotatie BNF (Backus-Naum-Form) si a fost folositã pentru prima datã, în anul 1959, la specificarealimbajului Algol-60. Aceastã notatie are aceeasi putere generativã cu gramaticile independente de cintroduse de N. Chomsky. Totusi, limbajele de programare nu sunt independente de context ci numaportiuni ale acestora pot fi modelate cu ajutorul limbajelor independente de context. Pentru a puteaspecifica un întreg limbaj de programare se poate folosi notatia BNF extinsã. În prezentarea din acestcapitol vom utiliza opt metasimboluri: ::= < > { } [ ] | pentru a defini unitãtile sintactice ale limbajuluiPascal. Metasimbolurile < si > sunt folosite pentru delimitarea numelui unei unitãti sintactice. Presupunem,de asemenea, existenta unei operatii de concatenare pe multimea unitãtilor sintactice. Metasimbolul ::=


3 of 48 12/9/2007 7:21 PM

apare dupã numele unei unitãti sintactice si are semnificatia "se defineste prin". Metasimbolul | este utilizatpentru a delimita mai multe variante de definire ale unei unitãti sintactice, aceasta fiind obtinutã preuniunea variantelor. Metasimbolurile { si } indicã repetarea posibilã (de zero sau mai multe ori)simbolurilor pe care le delimiteazã. Pentru a desemna prezenta optionalã a unor simboluri se utildelimitatori, metasimbolurile [ si ]. Vom admite, pentru prescurtare metasimbolul ... care indicãcontinuarea unui sir de valori conform contextului în care apare. Iatã câteva exemple:

::= A ... Z descrie multimea literelor mari;1.

::= 0 ... 9 descrie multimea cifrelor zecimale;2.

::= { | } descrie modul de formare a identificatorilor: un sir delitere si/sau cifre, primul semn fiind o literã.

3.

::= { } descrie modul de formare a unei secvente de cifre;4.

::= defineste un numãr întreg fãrã semn;5.

::= + | -6.

::= [ spune cã un întreg cu semn este un întreg fãrã semnprecedat de un semn: + sau -.

7.

Prin diagrame sintactice se realizeazã o reprezentare graficã a modului de agregare a unitãtilor sintactice.În cele ce urmeazã vom prefera limbajul natural (în anumite cazuri) si notatia BNF extinsã (în alte cacititorul interesat asupra diagramelor sintactice poate consulta, de exemplu: N. Wirth: SystematicProgramming: An introduction, Prentice Hall, 1972.

3.2. Tipuri de date. Constante. Variabile. Expresii

Un tip de date este o structurã compusã din: 1) o multime X de valori numite date si 2) o multime dcompozitie pe X (operatii ce se pot efectua cu valori din X). O datã are un singur tip (apartine unei smultimi). Existã limbaje de programare puternic tipizate (în sensul verificãrii cu regularitate a apartenteunei date la multimea de valori a tipului sãu, încã din faza de compilare). Astfel de limbaje de programasunt: Pascal, Modula, Ada etc.

Tipurile de date sunt standard sau definite de utilizator. Tipurile definite de utilizator se introducintermediul unei definitii folosind un cuvânt cheie precum type (în Pascal), typedef (în C) sau class (limbajele C++ si Java). De asemenea se vor utiliza diverse cuvinte cheie pentru a specifica structura tipuDacã pentru o anumitã structurã a unui tip nu este stabilit un identificator, spunem cã avem de-a cu uanonim.

Valorile unui tip de date (elementele multimii X sunt referite fie prin variabile, fie prin constante (literalisau constante simbolice). O locatie de memorie care poate stoca o valoare a unui anumit tip de date snumeste, prin abuz de limbaj, variabilã. Orice variabilã trebuie sã fie declaratã pentru a putea fi folositã. Odeclaratie contine un tip de valori - ce indicã: ce se stocheazã, cum se stocheazã si în ce operatii intervvalorile stocate - si un identificator pentru a ne referi la variabila ce obiectul declaratiei. Practic o variabilãeste un obiect caracterizat de tip, adresã si valoare, pentru care atributul valoare poate fi modificat.

În limbajul Pascal declaratia variabilelor este precedatã de cuvântul cheie var:


4 of 48 12/9/2007 7:21 PM

var { }

unde

::= {,}: .

În limbajele C, C++ si Java declaratia variabilelor aratã astfel:

{,} În functie de locul în care apare declaratia unei variabile, acesteia ise pot atribui atribute precum: local, global, static etc.

Existã limbaje de programare (de exemplu Java) care definesc o valoare implicitã pentru fiecare variabatunci când prin program aceasta nu "primeste" nici o valoare. Totusi, cele mai multe limbaje deprogramare nu oferã acest serviciu si este necesar sã se realizeze operatii de "initializare" explicitã.

Initializarea unei variabile chiar în momentul declarãrii acesteia, în limbajele de programare care peaceasta, se realizeazã folosind o descriere de forma:

IdentificatorulTipului IdentificatorulVariabilei = ValoareInit;unde se presupune cã ValoareInit este de acelasi tip cu tipul variabilei sau poate fi convertitã (transformatãfoarte usor) într-o valoare de acest tip.

Prezentarea elementelor unui tip este posibilã fie prin intermediul literalilor, fie prin intermediuconstantelor simbolice. Constantele simbolice sunt identificatori asociati unor elemente ale anumitormultimi. Declararea unei constante simbolice Pascal se realizeazã conform regulii:

const = ;

unde este un literal, o expresie constantã (în care intervin literali) sau elemente structuralimbajul C, constantele simbolice se pot introduce prin intermediul directivei #define sau cuvântului cheieconst atunci când sunt declarate variabile ce nu pot fi modificate în program.

Operatiile cu elemente ale unui tip sunt fie predefinite, fie sunt introduse prin declaratii function sauprocedure (în Pascal) sau operator(în C++). Agregarea variabilelor, constantelor si a operatorilor conduce la constructii numite expreExpresiile sunt evaluate în cursul executãrii unui program. Rezultatul unei expresii depinde de vavariabilelor în momentul evaluãrii.

Tipurile de date întâlnite în limbajele de programare actuale sunt clasificate în: tipuri de date simple; tipuride date structurate, tipuri referintã (pointer), tipuri procedurale. În limbajele C, C++ si Java existã tipuvoid. Aceastã multime notatã prin void înseamnã fie multimea vidã, fie o multime neprecizatã.

Tipurile de date simple numite si tipuri primitive (sau tipuri standard) se referã la multimi de elemenprecum: numere întregi, numere rationale, valori de adevãr (logice sau booleene), caractere, valorapartinând unei enumerãri sau unui interval (subdomeniu). O parte dintre tipurile simple sunt tipurordinale, adicã tipuri caracterizate printr-o multime finitã de valori, pe care este definitã o ordine liniarã si,prin urmare, pentru orice element al unei asemenea multimi se stabileste numãrul de ordine ord(.),elementul predecesor pred(.) si cel succesor succ(.). Tipurile ordinale sunt cele care se referã la multiprecum: multimea numerelor întregi, multimea valorilor de adevãr, multimea caracterelor, multimevalorilor unei enumerãri, multimea valorilor dintr-un subdomeniu al uneia dintre multimile anterioaTipurile rationale (simplã precizie, dublã precizie, precizie extinsã etc.) nu sunt considerate tipuri ordinaldesi sunt tot multimi finite de elemente. Trebuie observat cã metoda de reprezentare în memorcalculatorului a numerelor rationale ar permite considerarea unei ordini liniare si, elementele unei astfel demultimi ar avea un numãr de ordine.


5 of 48 12/9/2007 7:21 PM

Tipurile întregi ale limbajului Pascal sunt :

a) Tipul Byte : reprezintã multimea numerelor întregi fãrã semn începând de la 0 pânã la 255, reprezenintern folosind 8 biti (un byte).

b) Tipul întreg scurt Shortint : reprezintã multimea numerelor întregi cu semn începând de la -128 pânã127, reprezentate în complement fatã de doi, pe 8 biti.

c) Tipul întreg Integer : se referã la domeniul de valori dintre -32768 si 32767, reprezentate pe 16 complement fatã de doi.

d) Tipul Word : reprezintã multimea numerelor naturale de la 0 la 65535 reprezentate pe 16 biti.

5) Tipul întreg lung Longint : defineste un domeniu reprezentabil, cu semn, pe 32 de biti, în complementfatã de doi.

Tipuri întregi ale limbajului Java sunt:

a) Tipul byte : este echivalent cu tipul Shortint al limbajului Pascal.

b) Tipul short (întreg scurt): este acelasi cu tipul integer al limbajului Pascal.

c) Tipul int (întreg): corespunde tipului Longint al limbajului Pascal.

d) Tipul întreg lung (long): reprezintã multimea numerelor întregi, reprezentabile cu semn în complemenfatã de doi, pe 8 bytes adicã 64 de biti.

Tipurile de numere rationale ale limbajului Pascal sunt desemnate prin identificatorii standard real (6 bytes),single (4 bytes), double (8 bytes), extended (10 bytes) si comp (8 bytes) si descriu submultimi de numrationale reprezentate în memoria internã în virgulã mobilã. Tipul de date comp este o multime de numîntregi utilizate în calcule fãrã parte fractionarã.

Tipurile de numere rationale ale limbajului Java se mai numesc tipuri flotante. Sunt disponibile multimilefloat (4 bytes) si double (pe 8 bytes). Ca si pentru reprezentãrile single, double, extended si comp allimbajului Pascal, în cazul tipurilor float si double se utilizeazã standardul IEEE 754.

Tipul booleaneste folosit pentru descrierea multimii valorilor de adevãr desemnate prin literalii true si false. Pendeclararea unei variabile de tip boolean în limbajele Pascal si Java se foloseste cuvântul boolean. Înversiunea 7.0 a limbajului Turbo Pascal au fost introduse încã trei tipuri booleene: bytebool, wordbolongbool. Lungimea reprezentãrii este: boolean - 8 biti, bytebool - 8 biti, wordbool - 16 biti, longbool - 32biti. Referitor la tipul boolean, în Pascal, sunt adevãrate: false < true, ord(false) = 0, ord(true) =1,succ(false) = true, pred(true) = false.

Limbajul C++ nu are un cuvânt rezervat pentru variabile logice. Totusi, limbajul permite utilizareoperatiilor uzuale ale calculului cu propozitii: si, sau, negatia prin intermediul operatorilor: &&, ||, Limbajul trateazã orice valoare nenulã drept true si valoarea zero drept false. Valoarea rezultatã în urmunei operatii logice este 1 pentru rezultat true si 0 pentru rezultat false.

Pentru declararea variabilelor de tip caracter se utilizeazã cuvântul char. O variabilã de tip caracter poateavea ca valori coduri Unicode (pe 16 biti, în Java) sau coduri ASCII (pe 8 biti, în Pascal, C, etc.). caracterelor fiind ordonatã, au sens functiile: ord, pred si succ. Functia ord(.) întoarce codul caracterudintre paranteze. O altã functie utilizatã este chr, care transformã o valoare întreagã într-un caracter ccodul Unicode corespunzãtor. Caracterele pot fi comparate între ele pe baza pozitiei lor în setul decaractere Unicode.


6 of 48 12/9/2007 7:21 PM

Tipul enumerareeste reprezentat printr-o multime finitã de identificatori separati prin virgule si inclusi între paComponentele acestui tip se considerã ordonate, deci se pot aplica functiile: pred, succ si ord. De asemenease pot realiza comparatii între elemente. În limbajul Pascal, enumerarea (R, G, B) poate fi utilizatã pentru aintroduce tipul RGB, iar ord(R) = 0, pred(B) = G, R


7 of 48 12/9/2007 7:21 PM

unde [ si ] sunt elemente ale limbajului Pascal, iar { si } sunt elemente ale metalimbajului, {,} descrie multimea I, iar descrie multimea T din definitie. Multimea I se poateobtine ca produsul cartezian al unui numãr oarecare, dar finit de multimi de tip ordinal (fãrã longint), darzona din memoria internã utilizatã pentru stocarea elementelor tabloului nu trebuie sã depãseascã oanumitã dimensiune, dependentã de implementare. Multimea T este orice tip de date cu exceptia tipuluifisier.

Exemple:

type a = array [1..10] of integer; b = array [-5..5, -10..7] of real; T = (r, g, b); c = array [T] of char; d = array [1..10] of array[-5..5] of array[char] of integer;

Referirea unui element al unui tablou se prin identificatorul tabloului si indexul elementului scris înparanteze drepte: x['a'] dacã x este un tablou cu = char. Dacã un tablou este multi-dimensional,referirea la o componentã se poate în mai multe moduri. De exemplu, dacã x este un tablou bidimensioatunci x[i,j] si x[i][j] reprezintã acelasi element.

Limbajul Borland Pascal permite definirea unui tip numit sir de caractere (string). Lungimea sirurilor estcel putin 0 (null) si cel mult 255. Din punct de vedere al reprezentãrii interne, pentru un sir de caracterealocã n+1 bytes (în conventia ASCII pe 8 biti), unde n este lungimea efectivã a sirului. Octetul cu adrerelativã zero este rezervat pentru memorarea lungimii efective. Declararea unui tip sir de caracter sesupune regulii:

type identificator = string[lungime_maxima] | string;

unde stabileste limita superioarã a numãrului de caractere ce pot fi stocate; cparantezele drepte si aceastã limitã lipsesc se considerã siruri de lungime maximã 255. Un caracter din sireste accesat similar ca elementul unui tablou, lungimea efectivã a sirului x este obtinutã fie prin ord(x[0])sau prin length(x).

Exemplu:Definitia Type T30 = string[30]; introduce T30 ca fiind multimea sirurilor de caractere cu cel mult caractere.

Tipul de date înregistrare (record) se introduce în Pascal prin:

type = ; unde este definit prin urmãtoarele reguli BNF:

::= record [;]end

::= [; ] |

::= {; }

::= {, }:

::= case[ :] of {; }

::= {, } :[] [;])

adicã un element de tip record este în general format dintr-o parte fixã si una variabilã, fiecare dintreacestea fiind alcãtuitã din câmpuri.

Exemple:


8 of 48 12/9/2007 7:21 PM

1) Tipuri de date predefinite în Pascal:

const maxim = 100000;{constanta este de tip longint}

pi = 3.14159;

mint:integer :=maxint-1; {o expresie constanta}

pi2 = pi / 2; {o alta expresie constanta}

stop:char = 'Z';

type T1 = 0..maxint; { subdomeniu al tipului integer; maxint este constanta predefinita 32767}

const st:T1 = 100;

var x,y:T1; {x, y sunt variabile de tip T1}

a, b : real; { a, b sunt variabile de tip real}

flag, poz: boolean; {flag, poz sunt variabile logice}

ch: char;

i,j,k: integer; wi, wj, wk: word;

li, lj,lk:longint;

u:single; v:double; w:extended; {tipuri flotante - standardul IEEE 754}

2) Tipuri de date structurate în Pascal:

Type Data = record

ziua: 1..31;

luna: 1..12;

anul: 1..9999

end;

Figura = (triunghi, patrulater, cerc, elipsa);

Stare = array [Figura] of boolean;

Rvariante = record

{parte fixa}

cod:byte;

nume: string[30];

dataNasterii: Data;

{parte variabila}


9 of 48 12/9/2007 7:21 PM

case studii : (medii, superioare) of

medii:(NrClase:byte; Scoala:string[30];);

superioare: (Facultatea:string[20]; specializarea: string[15])

end; {un singur end}

Var d:Data; f: Figura; S: Stare; R: Rvariante;

{Constante denumite impropriu constante cu tip, de fapt sunt variabile initializate}

const d1:Data =(ziua:30; luna:5; anul:1999);

d2:Figura = cerc;

d3: Stare = (true, true, false, false);

d4:Rvariante = (cod:123;

nume:'Ionescu';

dataNasterii: (ziua:12; luna:8; anul:2000);

studii:medii;

Nrclase:12;

Scoala:'Liceul XXXX');

Un identificator de câmp trebuie sã fie unic numai în înregistrarea unde a fost definit. Un câmp al uvariabile de tip record este referit prin identificatorul variabilei si identificatorul câmpului separateprintr-un punct. Exemplu: R.cod, R.nume, R.dataNasterii.ziua, R.studii, R.Nrclase, R.Scoala, d.anul etc.

Tipul multime (prezent în Pascal, Modula etc.) permite definirea multimilor ale cãror elemente suntmultimi. Fie T un tip scalar diferit de real si de tipurile flotante. Se numeste tip set cu tipul de bazã Tmultimea P(T) formatã din toate submultimile multimii T. Definitia unui tip set se prin:

type = set of ;

unde este tipul de bazã. Constructia unui element de tip set urmeazã regulile:

::= [listã de elemente] | []

::= {, }

::= | ..

cu [ , ] elemente ale limbajului Pascal, |, { si } simboluri ale metalimbajului, iar reprezintã oexpresie a cãrei valoare apartine tipului de bazã. Astfel, pentru a ne referi la multimea vidã folosim notatia[], pentru a definii multimea vocalelor scriem ['a', 'e', 'i', 'o', 'u'], iar pentru a definii primele cinci numerenaturale nenule putem scrie în una din formele: [1, 2, 3, 4, 5], [5, 4, 3, 2, 1], [1..5], [1..3, 4, 5] etc.

Cu variabile de tip set se pot efectua urmãtoarele operatii: + (reuniune), - (diferentã), * (intersectie) ce auca rezultat un element de tip set, sau operatii relationale cu rezultat de tip logic: = (egalitate), = (include pe), (diferit). Apartenenta unui element t la o multime A este datã de valoarea de adevexpresiei t in A. Aceastã expresie este adevãratã dacã primul operand - element de tip ordinal - este element


10 of 48 12/9/2007 7:21 PM

al operandului al doilea - cu multimea de bazã compatibilã cu t.

Dacã tipul de bazã are n valori, o variabilã de tip set corespunzãtoare tipului de bazã va fi reprezentamemorie folosind n biti, depusi într-o zonã de memorie contiguã cu lungimea (n div 8) + 1 bytes dacã n nueste divizibil cu 8, respectiv (n div 8) bytes dacã n este multiplu de 8. Prin urmare tipul set of char reprezentat pe 32 de bytes.

Operatorii sunt simboluri care specificã operatii efectuate asupra unor variabile sau constante denuoperanzi. Combinatiile valide de operanzi si operatorii reprezintã expresii.

Limbajele de programare oferã o multitudine de operatori: operator de atribuire (simbolizat prin := sau =),operatori aritmetici unari (utilizarea semnului, incrementare, decrementare), operatori aritmetici b(adunare, scãdere, înmultire, împãrtire, obtinerea câtului si restului împãrtirii a douã numere întreoperatori logici (si, sau, negare), operatori relationali (egal, diferit, mai mic, mai mic sau egal, mai mare,mai mare sau egal, apartine), operatori la nivel de bit (si, sau, negare, sau exclusiv, deplasare stângadeplasare dreapta), operatori combinati (în limbajele C, C++ si Java), operatori asupra multimilor(reuniune, intersectie, diferentã), operatori asupra sirurilor de caractere (concatenare) precum si aoperatori.

Evaluarea expresiilor trebuie sã tinã seama de pozitia parantezelor si de proprietãtile operatorilo(precedentã, asociativitate, conversii implicite în cazul tipurilor compatibile, conversii explicite). Precedentastabileste ordinea de evaluare a operatiilor în cazul expresiilor care contin mai multi operatori diferiti.Dacã într-o expresie se întâlnesc operatii cu aceeasi precedentã atunci ordinea de evaluare este datã de tipulasociativitãtii (de la stânga la dreapta sau de la dreapta la stânga). Când într-o expresie apar operatioperanzi de tipuri diferite, înainte de efectuarea operatiei are loc un proces de conversie implicitã (când nuse semnaleazã ex

New PROGRAMARE PROCEDURAL · 2020. 5. 6. · Scheme logice structurate Notiuni introductive privind...

Documents

Transcript of New PROGRAMARE PROCEDURAL · 2020. 5. 6. · Scheme logice structurate Notiuni introductive privind...