ALGORITMI - Sistemul informational - sistem informatic

UNIVERSITATEA ROMANO-AMERICANA

FACULTATEA DE INFORMATICA MANAGERIALA

ANUL I

ALGORITMI

Sistemul informational

Def: Un sistem poate fi privit ca un ansamblu de elemente interconectate si interconditionate prin relatii fizice, sociale si de alta natura care functioneza in vederea relizarii unui scop sau finalizarii unui obiect.

El este deci o metoda de realizare a unui scop.

Procesele desfasurate intr-o activitate organizata nu au loc la intamplare, ci sunt declansate de anumite informatii, care prelucrate, sevesc la luarea unor decizii.

Activitatea defasurata in vederea realizarii unui obiectiv poate fi definita ca rezultatul actiunii conjugate, a trei subsisteme ce actioneaza intr-o stransa interdependenta si care la randul lor pot fi considerate sisteme:

sistemul deconducere sau decizional (S.D.)

sistemul condus,de executie sau operational (S.O.)

sistemul informational

Sistemul de conducere are rolul de dispune, indruma, coordona activitatea in vederea realizarii obiectivelor fixate, cu eficienta maxima.

Sistemul condus are rolul de a executa practic deciziile luate si de a furniza date privind actiunile realizate sau in curs de executie, folosind pentru aceasta resursele materiale, financiare si umane existente, repartizate pe obiective dinainte stabilite.

Sistemul infomational este un instrument indispensabil conducerii, avand ca parti componente mijloacele si procedeele ce asigura legaturile intre elementele de executie si elementele decizionale pentru conducere si organizare.

Sistemul informatic - instrument al conducerii stiintifice a societatilor economice

In acest context sisteul informatic reprezinta un ansamblu de elemente intercorelate functional in scopul automatizarii obtinerii informatiilor necesare conducerii in procesul de elaborare a deciziilor.

Un sistem informatic este compus, in principal, din urmatoarele elemente:

a)      Baza tehnica sau HARDWARE-ul sistemului informatic, care este construita din totalitatea mijloacelor tehnice de culegere, transmitere, stocare si prelucrare a datelor, in care locul central revine calculatorului electronic

b)      Sistemul de programe sau SOFTWARE-ul sistemului, ce cuprinde totalitatea programelor pentru functionarea sistemului informatic, in concordata cu functiunile si obiectivele ce i-au fost stabilite. Se au in vedere, atat programele de baza ( software-ul de baza), cat si programele aplicative (software-ul aplicativ)

c)      Baza stiintifico-metodologica, care este construita din modele matematice ale proceselor si fenomenelor economice, metodologii, metode si tehnici de realizare a sistemelor informatice.

d)     Baza informationala cuprinde datele supuse prelucrarii, fluxurile informationale, sistemele si nomenclatorele de coduri.

e)      Resursele umane si cadrul organizatoric, care cuprinde personalul de specialitate si cadrul necesar functionarii sistemului informatic. Personalul de specialitate include informaticieni cu studii superioare si pregatire medie, analisti, programatori, ingineri de sistem, administratori de retea, analisti-programatori ajutori, operatori, controlori date.

Clasificare sistemelor informatice

A) In functie de domeniul de utilizare, acestea se clasifica in patru grupe:

a) Sisteme informatice pentru conducerea activitatilor unitatilor economico - sociale, care se caracterizeaza prin aceea ca datele de intrare, de regula, sunt furnizate prin documente, intocmite de om, iar la iesire sunt furnizate de catre sistem tot sub forma de documete pentru perceperea acestora de catre om

b) Sisteme informatice pentru conducerea sistemelor tehnologice, care se caracterizeaza prin aceea ca datele de intrare sunt asigurate prin intermediul unor dispozitive automate care transmit sub forma de semnale informatii despre diversi parametri ai procesului tehnologic, iar datele de iesire se transmit de asemenea sub forma de semnale unor organe de exectie, regulatoare, care modifica automat parametrii procesului tehnologic.

c) Sisteme informatice pentru activitatea de cercetare stiintifica, si proiectare, care asigura automatizarea calculelor tehnico-ingineresti, proiectarea asistata de calculator si alte facilitati necesare specialistilor din domeniile respective.

d) Sisteme informatice speciale, care sunt destinate unor domenii specifice de activitate, ca de exemplu: informare si documetare tehnico-stiintifica, medicina, etc.

B) Nivelul ierarhic ocupat de sistemul economic in structura organizatorica a societatii:

a) Sisteme informatice pentru conducerea activitatii la nivelul unitatilor economice. Aceste pot fi decompuse in subsisteme informatice asociate functiilor economico - sociale sau chiar unor activitati

b) Sisteme informatice pentru conducerea activitatii la nivelul organizatiilor economico - sociale cu structura de grup

c) Sisteme informatice teritoriale. Sunt constituite la nivelul unitatilor administrativ - teritoriale si servesc la fundamentarea deciziilor adoptate de catre organismele locale de conducere

d) Sisteme informatice pentru conducerea ramurilor, subramurilor si activitatilor la nivelul economiei nationale

e) Sisteme informatice functionale generale au ca atribut principal facptul ca intersecteaza toate ramurile si activitatile ce au loc in spatiul economiei nationale, furnizand informatii necesare coordonarii de ansamblu si sincronizarii lor in procesul de reproductiei din cadrul economiei de piata. In acesta categorie sunt cuprinse sistemele pentru planificare, statistica, financiar - bancar.

C) Modul de organizare a datelor in cadrul sistemelor informatice:

a) Sisteme informatice cu organizarea datelor in fisiere clasice. Acest mod de organizarea a datelor are tendinta de rasfrangere sub aspectul aplicabilitatii, datorita neajunsurilor pe care le prezinta.

b) Sisteme informatice cu organizarea datelor in baze de date. Aceasta categorie de sisteme reprezinta o tendinta de extindere si dezvoltare.

Concepte de baza

Odata cu aparitia bazelor de date, in terminologia curenta au fost introduse si utilizate trei concepte de baza in organizarea datelor, si anume: entitate, atribut si valoare.

Entitatea reprezinta un obiect concret sau abstract, reprezentat prin proprietatile lui. Pe de alta parte, orice proprietate a unui obiect poate fi descrisa printr-o pereche (atribut, valoare). Prin urmare, o entitate poate fi reprezentata prin mai multe proprietati, deci mai multe perechi de forma (atribut,valoare).

Notiunea de atribut este cunoscuta si sub numele de camp sau caracteristica.

Fiecare atribut este caracterizat de natura valorilor pe care le poate lua.

Notiunea de data

In informatica prin date se intelege un model de reprezentare a informatiilor despre obiectele supuse prelucrarii automate, accesibil atat utilizatorului cat si componentelor calculatorului (hard si soft).

In functie de obiectele pe care le reprezinta datele se pot clasifica in:

Date elementare sau scalare, care se prezinta sub forma unor entitati indivizibile

Colectii de date, care se prezinta sub forma unor multimi de date elementare, intre care se definesc si se descriu sau nu anumite relatii

Datele elemetare pot fi tratate sub doua aspecte:

Nivelul fizic - corespunde modului de organizare si reprezentare interna a datelor. Astefel o data elementara se memoreaza intr-o zona de memorie situata la o anumita adresa.

Nivelul logic - corespunde modului de organizare si prelucrare sa datelor de catre utilizatori. Pentru identificare unica a datelor, utilizatorul va preciza, pentru fiecare data, urmatoarele elemente:

o       Identificatorul de data sau numele asociat datei.

o       Multimea valorilor pe care lepoate lua o data in procesul prelucrarii.

o       Atributele datelor precizeaza caracteristicile, proprietatile acestora in procesul de prelucrare.

Se numeste structura de date o colectie de date pentru care s-a definit un mecanism de selectare si identificare a componentelor. Deci, pentru o colectie de date se pot introduce relatii care sa asigure ordonarea datelor dupa criteriile dorite si sa faciliteze prelucrarea lor.

Asemenea datelor elementare, structurile de date pot fi create pentru reprezentarea lor in memoria interna sau pentru reprezentarea pe un suport extern de date. In mod corespunzatori structurile de date vor putea fi:

Structuri de date interne, cu caracter temporar, deoarece sunt realizate in memoria interna de tip RAM(volatila)

Structuri de date externe, care au caracter relativ permanent deoarece sunt memorate pe suporti externi. Aceste structuri de date pot cuprinde:

o       Fisiere de date

o       Baze de date

o       Banci de date

Tipuri de structuri de date

O structura de date reprezinta practic o colectie de date intre care practic s-au definit o serie de relatii care duc la un anumit mecanism de selectie si identificare a datelor.

Aceste relatii pot fi de tipul:

de echivalenta

deordine

de ordine totala

de preordine

Se numeste tip de structura de date o multime ordonata de date, intre care s-au stabilit anumite relatii si care folosesc, pentru realizarea operatiilor, un grup de operatori de baza cu o anumita semantica.

Principalele tipuri de structuri de date (logice sunt):

Structura punctuala, reprezentata de oentitate grup izolata

Structura liniara, definita atunci cand intre elementele unei colectii de date exista o relatie de ordine totala

Structura arborescenta, sau descendenta sau ierarhica este definita atunci cand intre elementele colectiei de date exista o reatie de ordine.

Arbori binari

Datorita specificului lor, arborii binari admin o reprezentare grafica simetrica, axa de simetrie trecand prin radacina arborelui. De aceea, subarborii unui element oarecare sunt denumiti subarbore stang si respectiv subarbore drept, functie de pozitia relativa a acestora fata de elemntul respectiv.

Pentru aplicatiile de prelucrare automata a datelor se utilizeaza structuri arborescente si pentru reprezentarea pe suport a acestor structuri o problema deosebit de importanta o constituie parcurgerea elementelor structurii intr-o anumita ordine.

Astfel, pentru arborii binari, s-au identficat si s-au descris trei modalitati de parcurgere a elemetelor arborelui, denumite:

parcurgere in preordine

parcurgere in inordine

parcurgere in finordine (postordine)

Fisierul se defineste ca o multime de date omogene din punct de vedere a semnificatiei lor si alcerintelor de prelucrare. Aceasta multime este organizata ca o lista liniara, cu elemente structurate arborescente. Aceste elemete ale fisierului, considerat ca o lista liniara, se numesc inregistrari.

Inregistrarile au, in general, o structura arborescenta, elementele structurii fiind numite campuri.

Baza de date se defineste ca o colectie de date aflate in interdependenta, memorata pe un suport impreuna cu descrierea datelor si a relatiilor dintre ele. Ea are sens ca element al unei banci de date.

Banca de date reprezinta un sistem de organizare si prelucrare, respectiv teleprelucrare a datelor.

Structuri de date

Cele mai frecvent utilizate structuri statice de date sunt:

Masive (tablouri)

Articole (inregistrari logice)

Masivul sau tabloul reprezinta o structura de date omogena cu una, doua sau n dimensiuni. Masivul cu o dimensiune se numeste in mod uzual, vector, iar cu doua dimensiuni, matrice.

In memoria interna tabloul se reprezinta liniar, intr-o zona compacta de memorie care se divide in subzone de aceeasi lungime, corespunzatoare fiecarui element al masivului. Adresarea fiecarui element al masivului s va face relativ la adresa de baza (adica adresa de inceput) unde a fost memorat masivul, la care se adauga lungimea elemetelor care il preced.

Articole. Fisiere de date

Articolul sau inregistrarea logica reprezinta o structura de date interna, eterogena, de tipul ,,structura arborescenta".

Un articol este format din capuri de date, care se identifica in mod unic printr-un identificator sau nume asociat.

Campurile de date pot fi date elemetare sau structuri de date incluse intr-un articol, formand asa numitele date de grup.

Fisierul de date este format din articole sau inregistrari logice, care desciu aceleasi entitati si formeaza astefel o colectie de date omogene din punct de vedere al semnificatiei si al cerintelor de prelucrare.

Articolul se constituie ca unitate elementara de organizare si prelucrare a unui fisier de date.

Metodele de organizare a fisierelor definesc regulile care stau la baza constituirii articolelor in fisiere si se stabilesc la operatia de creare a fisierelor.

Astefel fisierele pot avea:

Organizare secventiala, care memoreaza articolele de date secvential, in ordinea introducerii lor

Organizare secvential - indexata, care presupune crearea fisierului de date cu articolele ordonate crescator dupa valoarea unui camp de date numit cheie de indexare, ce are si rolul de identificare a oricarui articol existent in fisier.

Organizare directa, care presupune memorarea si apoi identificarea articolelor printr-o cheie care poate fi un camp de date sau nu, dar a carei valoare se asociaza fiecarui articol in parte

Metodele de acces la articolele unui fisier stabilesc modalitatile prin care selocalizeaza un articol in fisierul de date.

Astfel, pot fi definite urmatoarele tipuri de acces la articolele unui fisier:

Acces secvential, care presupune parcurgerea secventiala, unul dupa altul, incapand cu primul articol, a tuturor articolelor ce preced articolul cautat

Acces direct, care presupune localizarea directa a articolului cautat, pe baza unei informatii de identificare asociate fiecarui articol in parte.

Definitii, tipuri

Notiunile de algoritm si schema logica pot fi definite, explicate si mai ales foarte des utilizate in legatura cu elemete de teoria grafurilor.

Se numeste graf neorientat o pereche ordonata G=(X,U), unde X este o multime finita si nevida de elemente numite noduri (varfuri), iar U este este o multime de perechi (neordonata) de elemente distincte ale lui X, numite muchii

O muchie avand varfurile i s j, numite extremitatile sale, este notata prin [i,j] sau [j,i].

Un subgraf al lui G este un graf =(Y,V), unde Y X, iar V este format din toate muchiile lui U care unesc varfuri din U.

Un graf partial al lui G este un graf (X,V) cu V U.

Se numeste lant intr-un graf G=(X,U) o succesiune de muchii de forma [i₁,i₂],[i₂,i₃],..,[i_n-1,i_n], notata prescurtat prin [i₁, i₂, ..., i_n]

Un lant [i₁, i₂, ..., i_n] unde i₁, i₂, ..., i_n sunt distecte se numeste lant elementar.

Se numeste ciclu un lant [i₁, i₂, ..., i_n, i₁] cu [i₁, i₂, ..., i_n] lant elementar si n>=3. Ciclul in care varfurile sunt diferite doua cate doua se numeste ciclu elemetar.

Un varf care este extremitatea unei singure muchii se numeste varf terminal.

Doua varfuri unite printr-o muchie se numesc varfuri adiacente.

Un graf neorientat se numeste conex daca oricare varfuri diferite ale sale sunt unite prin cel putin un lant.

Un graf neorientat este o pereche ordonata G=(X,U), deosebirea fata de graful neorientat constand in faptul ca elementele lui U sunt perechi ordonate de varfuri numite arce.

Deci fiecare arc (i,j) are un sens de parcurgere ca anume de la extremitatea sa initiala la extremitatea sa finala.

In cazul grafurilor orientate, notiunile de lant si ciclu isi au corespondent in notiunile de drum si circuit.

Se numeste arbore binar un arbore orientat (prin precizarea radacinii sale), in care fiecare varf are cel mult doi descendenti, facandu-se insa distinctia intre descendentul stang si cel drept al fiecarui varf; in particular, daca un varf are un singur descendent, trebuie precizat daca acesta este descendent stang sau descendent drept.

O problema deosebit de importanta de arbori o reprezinta metodele de parcurgere a arborilor binari. Cele mai utilizate metode sunt cele denumite.

Parcurgere in inordine

Parcurgere in preordine

Parcurgere in postordine

Se numeste arbore de sortare un arbore binar cu proprietatile:

inf(i)>=inf(j) pentru orice varf j din subarborele stang al lui i;

inf(i)<=inf(j) pentru orice varf j din subarborele drept al lui i.

Programarea este practic activitatea prin care se concepe si se realizeaza programul pentru dezvoltarea unei probleme, cu ajutorul calculatorului electronic.

Un program reprezinta o succesiune de instructiuni si comenzi apartinand unui/unor limbaje de programare, (Pascal, Basic, C, Visual Basic, Java, etc) care conduc la solutionarea problemei formulate. Calculatorul va efectua aceste comenzi in ordinea stabilita de programator, pentru a obtine rezultatele dorite, in forma de prezentare ceruta.

Formularea problemei - prima etapa in activitatea de programare - este deosebit de importanta, pentru ca in cadrul ei se stabilesc datele de intrare si forma lor de organizare, datele de iesire si forma lor de prezentare, precum si prelucrarile necesare

Formularea problemei clara, completa si corecta reprezinta o cerinta importanta a activitatii de proiectare si realizare a programelor, de ea depinzand intreaga activitate care ii urmeaza.

Daca problema abordata este complexa, atunci activitatea de proiectare si realizarea practica se desfasoara in echipe - formate din analisti, programatori, ingineri de sistem, etc.

Elaborarea algoritmului este o etapa deosebit de importanta in activitatea de programare, deoarece ea presupune analiza corecta, exacta si completa a problemei formulate, pentru gasirea algoritmului ei corect de rezolvare si apoi descrierea lui corecta.

Notiunea de algoritmi

Cuvantul algoritm este de origine araba, derivand din numele matematicianului Abu Ja'far Mohammed ibn Musa al-Kahowarizmi.

Considerata ca notiune primara, notiunea de algoritm a fost definita de matematicianul sovietic A.A. Marcov ca fiind: o perspectiva care determina un proces de calcul si care este precisa, perfect inteligibila, nepermitand nici un fel de interpretari din partea celui care o duce la indeplinire.

Se spune ca o problema este decidabila daca exista un algoritm pentru rezolvarea ei.

Putem spune ca algoritmul reprezinta un sistem de reguli care aplicat unei clase de probleme de acelasi tip, pornit de la datele initiale, conduce la obtinerea solutiei prin intermediul unor operatii succesiv ordonate si unic determinate.

Proprietatile algoritmilor

a)      Generalitatea - consta in aceea ca un algoritm nu rezolva in general o singura problema, o problema particulara concreta, ci o clasa de probleme de acelasi tip. Cu alte cuvinte, algoritmul trebuie sa se aplice la date initiale ce pot varia intre anumite limite precizate

b)      Finititudinea - presupune ca dupa executia unui anumit numar transformari asupra datelor initiale, sa poata fi obtinuta solutia finala. In caz contrar, algoritmul va permite efectuarea la infinit a transformarilor asupra datelor initiale sau intermediare - se spune atunci ca algoritmul cicleaza, este deci incorect.

c)      Determinismul - inseamna cuprinderea tuturor cazurilor posibile ce pot sa apara in rezolvarea clasei respective de probleme, inlaturand ambiguitatile sau neclaritatile.

d)     Unicitatea - se refera la faptul ca transformarile, precum si ordinea lor, prin care se trece de la o anumita informatie initiala la informatia finala, sunt univoc determinate de regulile algoritmului. Aceasta inseamna, ca nu este posibil ca, aplicand un algoritm aupra unei aceleiasi informatii de mai multe ori, sa obtine rezultate diferite. Rezultatele obtinute trebuie sa fie aceleasi.

e)      Claritatea, precizia algoritmului - sunt deosebit de importante in stabilirea si descrierea unui algoritm. Acesta trebuie sa specifice clar si precis, in fiecare moment, care este etapa imediat urmatoare in rezolvarea problemei respective. In prezentarea unui algoritm nu trebuie deci folosite expresii echivoce.

Structura unui algoritm

Din punct de vedere structural, un algoritm cuprinde urmatoarele etape:

Initializarea - care are rolul de a furniza dateleinitiale ce se vor prelucra si eventualele valori initiale ale unor variabile ce-si modifica valoarea pe parcursul executiei lucrarilor

Prelucrarea - care inseamna de fapt transformarile efective ale datelor initiale cu scopul obtinerii solutiilor finale

Prezentarea solutiei finale - care inseamna prezentarea, afisarea, sau transmiterea formatului dorit, a rezultatelor finale obtinute in urma prelucrarilor specificate.

Scheme logice

Practica programarii calculatoarelor a demonstrat ca schemalogica este cea maiutilizata forma de reprezentare a algoritmilor. Ea realizeaza redarea expresiva, sintetica si usor de urmarit, prin vizualizarea clara a etapelor cuprinse in algoritm, a tuturor blocurilor sale componente.

Schema logica este deci o forma de reprezentare a algoritmului si modului de lucru al acestuia sub forma grafica, folosind diferite simboluri grafice.

In cadrul schemelor logice identificam urmatoarele tipuri de blocuri:

Blocul de inceput - indica inceputul descrierii algoritmului cu ajutorul schemei logice. El apare o singura data, la inceputul schemei logice si contine in interiorul lui de regula cuvantul Start sau Inceput.

Blocul de sfarsit - indica sfarsitul procesului de calcul si a schemei logice. El apare o singura data,la sfarsitul scheei logice si contine in interiorul lui de regula unul din cuvintele STOP, SFARSIT sau EXIT.

Blocul de intrare (de citire) - indica citirea, de pe un suport extern, a datelor de intrare necesare pentru functionarea algoritmului de calcul si inscrierea lor in locatii de memorie interna. El poarta eticheta Citeste, iar lista - intrare contine variabile care precizeaza zonele de memorie interna receptoare. Blocul are o intrare si o iesire, pentru a indica continuarea algoritmului de calcul. De regla daca este necesar, acest bloc apare la inceputul schemei logice, dupa blocul de Start.

Blocul de iesire (de scriere) - are aceleasi format cu cel de intrare, numai ca specifica datele de iesire, deci cele care trebuie afisate (scrise) pe un suport extern de date, pentru a putea fi ulterior utilizate, cum ar fi: pe ecran, pe imprimanta sau pe un suport magnetic. Aceastea constituie practic rezultatele prelucrarilor.

Blocul de prelucrare, de calcul sau de atribuire - reprezinta grafic o etapa a procesului de calcul in care se efectuiaza diferite calcule. De regula in acest bloc se calculeaza valoarea unei expresii (e) si sa atribuie rezultatul sau unei variabile (v). Simbolul = este operator de atribuire si nu operatorul relational din matematica. De exemplu x=z inseamna ca valoarea lui z se muta in variabila x sau, altfel spus,variabilei x i se atribuie valoarea lui z.

Blocul de decizie, de ramificatie sau de selectie - marcheaza locul unde se decide, se hotaraste, functie de continutul blocului, pe ce cale se va continua procesului de prelucrare (calcul). El poate fi un bloc de decizie simplu, cu o intrare si doua iesiricorespunzatoare celor doua valori logice posibile la testarea unei conditii logice, si anume de:Adevarat sau False. In interiorul blocului se scrie conditia ce se va testa.

Bloc de conexiune pe aceeasi pagina (conector) - este practic un cerculet folosit pentru a uni doua blocuri de pe aceeasi pagina. Astfel, daca o sageata uneste doua blocuri de pe aceeasi pagina, se foloseste drept conector un cerculet. Un conector se va plasa in acest caz in punctul de intrerupere al sagetii, iar altul in locul unde trebuie sa continue sageata. Cei doi conectori trebuie sa aiba inscris acelasi continut (grup de litere sau cifre).

Conectori de pagina sau bloc de conexiune pe o alta pagina - se utilizeaza in acelasi mod, dar pentru a continua schema logica pe o alta pagina

Scheme logice structurate

O schema logica este structurata, daca indeplineste urmatoarele conditii:

contine un singur bloc de intrare.

contine un singur bloc de iesire.

contine una din structurile de control, denumite sau structuri fundamentale, cum sunt:

- structura secventiala;

- structura alternativa;

- structura repetitiva;

Structura secventiala sau liniara

Desemneaza una sau mai multe operatii ce se executa una dupa cealalta, in mod liniar (secvential).

Structura alternative sau selectia

Structura alternativa desemneaza executia unei secvente de operatii S₁ sau a alteia S₂ in functie de indeplinirea sau nu a unei conditii.

Structura repetitiva

Structura repetitiva indica repretarea unei operatii sau secvente de operatii , atat timp cat este implinita o anumita conditie.

In functie de momentul in care se face testarea conditiei specificate, structurile repetitive sunt de mai multe tipuri.

Astfel:

conditia poate fi testate anterior executiei secventei de comenzi si atunci avem o structura de tip WHILE - DO

conditia se testeaza posterior executiei secventei de comenzi si atunci avem o structura de tip DO-UNTIL

Structura repetitive mai poate fi analizata si din punct de vedere al numarului de reluari. Din acest punct de vedere, o strucura repetitiva poate fi:

fara numerator, caci nu se cunoaste delainceputnumarul de reluari. Asa este cazul structurii de tip WHILE, indifferent de tip ei.

cu numarator, atunci cand se stie sau se poate calcula automat numarul de reluari. Asa este cazul structurii DO-FOR.

Teoreme ale programarii structurate

Programarea structurata beneficiaza si de un puternic suport teoretic constand intr-o constructie de principii, termeni si teoreme matematice specifice.

Teorema de structura Bohm si Jacopini spune:

orice schema logica este echivalenta cu o schema logica structurata

daca o organigrama cuprinde o multime F de actiuni si o multime P de predicate, pot fi adaugate lui F si P noi functii, respectiv noi predicate, astfel incat organigrama sa fie structurata si sa fie echivalenta cu cea initiala. Teorema de structura (existenta) ilustreaza faptul ca orice program poate fi pus sub forma structurata, adica sa contine numai structuri fundamentale si/sau varinatele acceptate ale acestora, prin utilizarea unor variabile boleene asociate unor functii suplimentare

corolarul ,,de sus in jos" (top - down): Un program structurat este echivalent cu un program scris sub una din urmatoarele forme:

P=Secvential (f,g)

P=Alternativ (p,f,g)

P=Repetitiv(p,f)

Unde p este un predicat al lui P, iar f si g sunt secvente structurate sau functii ale programelor.

Teorema de corectitudine:

Corectitudinea unui program structurat poate fi verificata prin examinarea fiecarui nod din arborescenta sa. Daca fiecare nod se verifica local, se spune ca programul structurat este corect.

Se stie acum ca algoritmul exprima inmod explicit si neambiguu calea de rezolvare a unei probleme; el se exprima de regula, pentru prelucrarea automata a datelor, sub forma unei secvente de instructiuni scrise intr-un limbaj de programare (program). Dupa ce algoritmula fost creat si deci programul corespunzator a fost scris, este necesar sa i se dovedeasca corectitudinea, deci faptul ca procesul de calcul si prelucrari consecutive conduc, intr-un intervaldetimp finit, la obtinerea solutiei corecte a problemei formulate.

Corectitudinea reprezinta o conditie indispensabila a oricarui algoritm si daca mergem mai departe, in cadrul prelucrarii automate a datelor, a oricarui program.

In literatura de specialitate sunt prezentate numeroare tehnici de verificare si validare a algoritmilor.

Dintre aceste tehnici, metode, amintim urmatoarele:

testarea programelor si depanarea programelor

verificarea formalizata a programelor

cea mai slaba preconditie

cea mai tare postconditie

instructiuni generalizate

sintaxa expresiilor logice, ect

Testarea programelor

Actiunea de testare a programelor se deosebeste de celelalte faze prin care trec acestea prin caracterul ei in aparenta ,,demolator". Astfel, in timp ce alte faze au o esenta constructiva, testarea are in esenta un caracter distructiv, deoarece scopul ei este de a pune in evidenta proasta functionare a programului.

Procesul de detectare si apoi de eliminare a erorilor unui algoritm/program are doua componente, numite: verificare si validare.

Activitatea de validare si verificare a unui progra, urmareste in principal, urmatoarele:

descoperirea defectelor programului

certificarea faptului ca programul va functiona corect in conditii de exploatare curenta

Tehnici de testare a programelor

Prin testarea prograului se intelege deci executarea programului respectiv cu scopul de a descoperi o anomalie sau eroare. Ea se bazeaza pe construirea unor esantioane de date de intrare care sa conduca la depistarea unor erori in functionarea programului, intr-un interval de timp cat mai scurt si cu effort cat mai mic.

In ultimul timp au aparut o serie de metode de elaborare a datelor de test, care ajuta programatorul, oferindu-I posibilitatea de a aborda sistematic activitatea de testare a programelor, cu o probabilitate crescuta de depistare a erorilor.

Aceste metode pot fi denumite:

testarea functionala sau metoda cutiei negre, care presupune construirea datelor de test astfel incat sa permita testarea fiecarei functiuni a programului

testarea structurala sau metoda cutiei transparente, care presupune construirea datelor de test astfel inct toate partile programului sa poata fi testate

Depanarea programelor

Testarea unui program trebuie sa se finalizeze, pentru a fi utila, cu semnalarea erorii si localizarea ei. De aceea, testarea prograului este urmata de depanarea lui.

Depanarea unui program consta in localizarea erorii, determinarea naturii sale si corectarea ei. Ea se poate face in mod:

static, dupa executarea programului

dinamic, in timpul executiei acestuia

Depanarea statica se poate face prin mai multe metode, dintre care mai utilizata este cea denumita ,,storage dump", care presupune analiza continutului locatiilor de memorie, afisate de sistem in sistem de numeratie hexazecimal sau octal.

Depanarea simbolica, o alta metoda de depanare, ofera posibilitatea de a urmari executarea programului la nivelde limbaj sursa. Limbjele de programare ofera,in ultimele lor versiuni, un depanator simbolic integrat, care permite depanarea usoara, placuta si eficienta a programelor.

Verificarea formalizata a programelor

Practica a dovedit, in timp, ca oricat de numeroase ar fi testele efectuate asupra unor programe foarte complexe, ele nu pot garanta functionarea corecta a acestora.

Probleme de testare apar indeosebi atunci cand avem de a face cu algoritmi complexi; daca acestia ar putea fi descompusi, pe baza a unor reguli precise, in elemente simple consecutive, usor de testat, atunci problema ar putea fi mai usor rezolvata.

Astfel de reguli, care sa permita ansamblarea elementelor simple constituive si corecte in algoritmi complxi corecti, sunt urmatoarele:

regula compunerii secventiale, care presupune algoritmul A constituit din doua parti B si C, in ordinea aceasta. In acest caz daca datele de iesire in B sunt date de intrare in C, si daca cei doi algoritmi sunt corecti, algoritmul A este corect

regula implicatiei, care presupune ca daca un algoritm A este corect si urmeaza sa se implice in conditii initiale ,,mai tari" ca P, pentru a obtine rezultate ,,mai slabe" decat Q, atunci el ramane un algoritm corect

regula intructiunii de atribuire, care precizeaza conditiile in care instructiunea de atribuire, fundamentala intr-un limbaj de programare procedural, poate avea efecte laterale, influentand sau chair modificand valorile altor variabile

regula de decizie care stabileste pentru fiecare forma a ei, cate o regula de corectitudine

reguli pentru intructiunile iterative care precizeaza conditiile in care fiecare dintre aceste comenzi sunt corecte. Se stie ca executia unei instructiuni iterative se numeste iteratie, iar o astfel de comanda poate avea zero iteratii, un numar finit de iteratii sau un numar de iteratii infinit, functie de corectitudinea conditiei care controleaza ciclul si al datelor prelucrate

Utilizarea instructiunilor generalizate

Este o metoda utila pentru scrierea mai concisa a algoritmilor, care pot fi astfel mai usor de citit, de inteles si de testat.

Sintaxa expresiilor, aconditiilor si a formulelor logice

Ori de cate ori analizam, testam un algoritm sau depanam unprogram, o atentie deosebita trebuie acordata contructiei si evaluarii conditiilor logice, care pot fi simple dar pot fi si complexe, formate din mai multe conditii simple legate prin operatori logici. In acest sens trebuie verificata ordinea de evaluare a acestora, trebuie folosita si verificata facilitatea de cuprindere a expresiilor simple si/sau complexe, pentru a stabili noua ordine de executie stabilita. Aceste expresii trebuie verificate in mod deosebit, pentru ca stabilesc fie formule de calcul, fie reprezinta conditii de reluare a unui ciclu iterativ sau de selectie intr-un bloc de decizie.

Probleme

Problema 1.

Sa se determine un algoritm eficient prin care sa se preia elementele unei matrice de n linii si m coloane de numere reale. Sa se determine minimul., maximul pentru fiecare linie si coloana si la nivel de matrice cu pozitiile acestor valori. Sa se determine media elementelor nenule pentru fiecare linie, coloana si la nivel de matrice. OBS.: una din conditiile ca algoritmul sa fie eficient este ca parcurgerea elementelor matricei sa se faca de cat mai putine ori. In final se vor afisa toate rezultatele obtinute.

Program matrice;

Var i,j,n,m,g,h,pozmin,pozmax:integer;

a:array[1..100,1..100] of real;

s,ma,min,max:reall;

Begin

Readln(n,m);

For i:=1 to n do

For j:=1 to m do

Readln(a[i,j]);

g:=0;

s:=0;

for i:=1 to n do

begin

For j:=1 to m do

Begin

ma:=0;

h:=0;

If a[i, 1]<>0 then begin

g:=g+1;

s:=s+a[i, 1];

ma:=ma+a[i,1];

h:=h+1;

end;

Min:=a[i, 1];

Max:=a[i, 1];

If (a[i, j]<min) then begin

min:=a[i,j];

pozmin:=j;

end;

If (a[i,j]>max) then begin

max:=a[i,j];

pozmax:=j;

end;

end;

writeln('Elem cel mai mic de pe linia ',k,' este: ',min,' pe poz: ', i,pozmin:2);

writeln('cel mai mare elem de pe linia ',k,' este: ',max,' pe poz: ',i,pozmax:2);

writeln('Med. Aritm. pe linia ',i', este: ',ma/h);

End;

Writeln('Media aritmetica a elem nenule din matrice este: ',s/g);

For j:=1 to m do

begin

Min:=a[1, j];

Max:=a[1, j];

If a[1,j] <>0 then begin

s:=a[1, j];

g:=1;

end

else begin

s:=0;

g:=0;

end;

For i:=2 to n do

Begin

If (a[i, j]<min) then begin

min:=a[i, j ];

pozmin:=i;

end;

If (a[i, j]>max) then begin

max:=a[i, j];

pozmax:=i;

end;

if a[i, j] <>0 then begin

s:=s+a[I,j];

g:=g+1;

end;

end;

writeln('Media aritm. pe col ',j,' este: ',s/g);

writeln('Elem min de pe coloana ',j,' este: ',min,' si se afla pe poz: ', pozmin, j:2);

writekn('elem max de pe col ',j,' este: ',max,' si se afla pe poz: ', pozmax,j:2);

end;

g:=0;

s:=0;

min:=a[1,1];

max:=a[1,1];

pozmax:=0;

h:=0;

for i:=1 to n do

for j:=1 to m do begin

if a[i, j]< min then begin

min:=a[i , j];

s:=i;

g:=j;

end;

if a[i, j]> max then begin

max:=a[i , j];

h:=i;

pozmax:=j;

end;

end;

writeln('Min pe matrice este:' min,' pe poz:' ,s,g:2)

writeln('Max pe matrice e :',max,' pe poz: ',h,pozmax:2);

end.

• schema logica

Problema 2.

Sa se calculeze suma elementelor de rang impar ale unui vector de dimensiune n data. Elementele vectorului sunt numere reale si se introduc de la tastatura.

• cod

var x:array[1..100]of real;

n,i:byte;

s:real;

begin

write('dimensiunea vectorului ');readln(n);

for i:=1 to n do begin

write('x[',i,']=');readln(x[i]) end;

s:=0;

for i:=1 to n do

if odd(i) then s:=s+x[i];

writeln('suma = ',s:10:2)

end.

• schema logica

Problema 3.

Determinarea ultimei aparitii a unei valori date intr-un vector neordonat, de dimensiune n.

• cod

var x:array[1..100]of real;

n,i,poz:byte;

a:real;

begin

write('dimensiunea vectorului ');readln(n);

for i:=1 to n do begin

write('x[',i,']=');readln(x[i]) end;

write('valoarea cautata ');readln(a);

poz:=0;

for i:=1 to n do

if x[i]=a then poz:=i;

if poz<>0 then writeln('pozitia = ',poz)

else writeln('valoare negasita')

end.

• schema logica

Problema 4.

Determinarea elementului maxim dintr-un vector si a tuturor aparitiilor sale.

• cod

var x:array[1..100]of real;

poz:array[1..100]of byte;

n,i,poz:byte;

max:real;

begin

write('dimensiunea vectorului ');readln(n);

for i:=1 to n do begin

write('x[',i,']=');readln(x[i]) end;

max:=x[1];k:=1;poz[k]:=1;

for i:=2 to n do

if x[i]>max then begin max:=x[i];k:=1;poz[k]:=i end

else if x[i]=max then begin k:=k+1;poz[k]:=i end;

write('maximul este ',max:10:2,' pe pozitiile ');

for i:=1 to k do write(poz[i],' ')

end.

• schema logica

Problema 5.

Suma elementelor unei matrice dreptunghiulare, de dimensiune m*n.

• cod

var a:array[1..10,1..20]of real;

m,n,i,j:byte;

s:real;

begin

writeln('nr linii');readln(m);

writeln('nr coloane');readln(n);

for i:=1 to m do

for i:=1 to n do begin write('a[',i,',',j,]='); readln(a[i,j]) end;

s:=0;

for i:=1 to m do for j:=1 to n do s:=s+1a[i,j];

writeln('suma',s)

end.

• schema logica

Problema 6.

Determinarea elementelor maxim si minim dintr-o matrice dreptunghiulara, de dimensiune m*n.

• cod

var a:array[1..10,1..20]of real;

m,n,i,j:byte;

min,max:real;

begin

writeln('nr linii');readln(m);

writeln('nr coloane');readln(n);

for i:=1 to m do

for i:=1 to n do begin write('a[',i,',',j,]='); readln(a[i,j]) end;

max:=a[1,1];min:=max;

for i:=1 to m do

for j:=1 to n do

if a[i,j]>max then max:=a[i,j]

else if a[i,j]<min then min:=a[i,j];

writeln('maximul=',max:10:2);

writeln('minimul=',min:10:2)

end.

• schema logica

Problema 7.

La o petrecere intre prieteni, Alin sugereaza sa-l sune la telefon pe Catalin pentru a participa si el la acest eveniment. Alin a reusit sa stranga urmatoarele informatii:

1. numarul are 7 cifre
2. a doua jumatate a numarului (ultimile trei cifre) este de 4ori mai mare decat numarul format cu cifre de pe pozitiile 2, 3, 4
3. doua cifre (a patra si a cincea) sunt identice
4. a treia cifra este dublul celei de-a doua, iar suma acestora este egala cu prima cifra
5. a patra cifra este dublu celei de-a treia sau a doua cifra marit cu2.

Care este numarul lui Catalin

• rezolvare

1. 7 cifre - abcdefg
2. efg=4*bcd
3. d=e
4. c=2*b
5. c+b=a
6. d=2*c si d=2+c

Din 6. rezulta c=2, d=4. Din 3. rezulta e=4. Din 4. rezulta b=1. Din 5. rezulta a=3. Numarul este 31244fg. Din 1. efg=4*bcd => efg=4*124 => efg = 496. Deci numarul este 3124496

Problema 8.

Intr-o camera avem 3 intrerupatoare. Intr-o camera alaturata avem 3 becuri. Becurile sunt legate la intrerupatoare. Intrand o singura data in camera cu intrerupatoare si pe urma in camera cu becuri determinati becul fiecarui intrerupator.

Problema este destul de simpla daca se tine cont de efectele pe care le are curentul electric asupra filamentului unui bec, si anume efectul de incalzire.

Intrand in camera cu intrerupatoare apasam pe doua dintre ele dintre care unul il lasam aprins, iar pe celalalt il stingem dupa o perioada de timp. Intrand in camera cu becuri facem urmatoarea deductie :

becul care este aprins apartine intrerupatorului lasat aprins, cel care este incandescent apaertine celui cu care ne-am " jucat ", iar cel care este rece apartine celui care nu l-am atins.