Cursul 2. Complexitatea Produselor Program (PP)

2.1. Rezolvarea recurenţelor de tip Divide et Impera

În general o procedură (algoritmul) Divide et Impera se aplică unui tablou (vector) V = <v1,...,vn> (V[1..n], n=dim[V]), asupra căruia vrem sa aplicăm o operaţie oarecare (sortare, determinarea valorii maxime, determinarea cmmdc, etc). Avem:

Procedura DivImp(V,p,q) //V secventa 1<=p<=q<=n//(p,q) determina o subsecventa

Daca q-p atunci Rezolva(V,p,q) altfel m=(p+q) div 2 //m se poate determina si altfel DivImp(V,p,m) //pentru (p,m)

DivImp(V,m+1,q) //pentru (m+1,q) Combina(V,p,m,q)

SfDacaSfProcedura

Observaţii generale1o. Se divide problema în subprobleme (2,3,..., a, a finit);2o. Stăpâneşte subproblemele prin

– rezolvarea nerecursivă, dacă dimensiunea lor (prag)– rezolvă subproblemele recursiv, dacă dimensiunea >.

3o. Combină soluţiile tuturor subproblemelor pentru a ajunge la soluţia finală;4o. Apel din exteriorul procedurii se face cu DivImp(V,1,n);5o. Pentru sortare avem =1 şi a=2, iar procedura Combina face interclasarea;6o. Pentru sortare avem şi varianta recursivă de mai jos:

Procedura SortMerge(V,p,q)Daca p q atunci

m=(p+q) div 2SortMerge(V,p,m)SortMerge(V,m+1,q)Interclaseaza(V,p,m,q)

sfDacasfProcedura

2.2. Analiza algoritmului Divide et Impera

Vom încerca să deducem o recurenţă

Unde: – este acel prag de la care problema este suficient de mică şi se poate rezolva direct şi/sau iterativ;– a reprezintă numărul de subprobleme;– 1/b reprezintă dimensiunea unei subprobleme din problema iniţială;

– D(n) = timpul necesar pentru a divide în a subprobleme;

1

– C(n) = timpul necesar pentru a combina soluţiile celor a subprobleme în soluţia problemei iniţiale.

Exemplu: La algoritmul de sortare prin interclasare avem– divizarea în 2 subsecvenţe de lungime n/2;, deci a=2, iar dimensiunea unei probleme este 1/2– dacă p = q avem timp constant (1) (n=1, deci =1);– D(n) = (1), pentru că se determină indicele de mijloc al secvenţei (p,q);– C(n) = (n), (pentru că interclasarea a 2 secvenţe de lungime p, respectiv q dă (p+q-1))

Avem deci:

sau

În final avem

2.3. Metode de rezolvarea a recurenţelor

Există 3 metode importante de soluţionare a tipurilor de recurenţă descrise anterior:1. medoda iteraţiei; prin iteraţii succesive şi reduceri se deduce formula

Exemplu 1) să luăm formula pentru , avem succesiv

. Revenind la n rezultă: . Pentru n natural oarecare k>0 astfel că: , deci şi de aici . Deci pentru n oarecare.

Exemplul 2) fie O iterăm astfel:

Se observă că al i-lea termen din serie este . Iteraţia ajunge la final când sau echivalent când i depăşeşte . Continuând iterarea până în acest punct şi utilizând delimitarea , descoperim că suma conţine şi o serie geometrică descrescătoare:

2. metoda substituţiei, prin intuiţie se deduce formula folosind diverse substituţii iar apoi se demonstrează prin inducţie;

Exemplu: fie recurenţa: , care pare dificilă. Putem simplifica recurenţa printr-o schimbare de variabilă, fie m=log2n şi se obţine

Acum redenumim S(m)=T(2m) şi obţinem o nouă recurenţă:

Această recurenţă este asemănatoare recurenţei de la exemplul 1, metoda iteraţiei şi are soluţia S(m)=O(mlog2m)

2

Revenind la n, obţinem T(n)=T(2m)=S(m)= O(mlog2m)=O(log2n log2(log2n)), ceea ce este o complexitate f. bună.

3. metoda master.

Această metodă se aplică problemelor recursive care au timpul de execuţie de forma:

Avem 3 cazuri (demonstrate în CORMEN, THOMAS H. LEISERSON, CHARLES RIVEST, RONALD R.: Introducere în algoritmi. Cluj-Napoca: Editura Computer Libris Agora, 2000). 1o Dacă pentru o anumită constantă ,

2o Dacă

3o Dacă , pentru o anumită constantă > 0, şi dacă (numită şi condiţie de regularitate) pentru o constantă c şi n suficient de mari, atunci

Observăm că practic se compară f(n) cu şi soluţia o va da cea mai mare dintre ele; f(n) trebuie să fie polinomial mai mică (în primul caz) şi polinomial mai mare (în cazul 3) decât

.

Utilizarea metodei master. Exemplul 1.

Fie Avem a=9, b=3 şi f(n)=n.Calculăm , apoi ,deci suntem în cazul 1o şi soluţia este:

. Exemplul 2. Fie

Avem a=1, b=3/2 şi f(n)=1.Calculăm =f(n), deci suntem în cazul 2o şi soluţia este ,

adică . Exemplul 3. Fie

Avem a=3, b=4 şi f(n)=nlog2n.Calculăm iar , deci suntem în cazul 3o şi soluţia ar fi

, dacă se verifică condiţia de regularitate:

.

Exemplul 4. Fie

Avem a=2, b=2 şi f(n)=nlog2n.

3

ar fi cazul 3o dar f(n)=nlog2n este asimptotic mai mare ca n dar nu polinomial mai mare deci nu putem rezolva.

2.4. Ciclul de viaţă al Produselor-Program

Crearea de noi PP este un proces complex a cărui structură cunoaşte o continuă perfecţionare. Dacă în anii de pionierat ai programării elaborarea unui PP era considerată o artă – D.E. Knuth îşi

4

întitula tratatul de informatică într-o manieră sugestivă „The Art of Computer Programming” – astăzi se cunosc diverse metode şi tehnici de realizare a PP. După cum precizează Schach [Schach, 2002] există peste o sută de astfel de metode şi tehnici de realizare, unele foarte generale, acceptate şi folosite de comunitatea programatorilor iar altele, foarte particulare, folosite doar de autorii lor. Complexitatea crescândă a sistemelor software realizate, pe de o parte, şi noile generaţii de limbaje, pe de altă parte, au influenţat dezvoltarea de noi metode generale de realizare a programelor: programarea structurată, programarea modulară, programarea orientată pe obiecte.

2.4.1. FAZELE CICLULUI DE VIAŢĂ

Deoarece PP sunt folosite de oameni pentru rezolvarea unor probleme reale şi sunt foarte asemănătoare unui organism viu putem vorbi că şi PP au un ciclu de viaţă.

Definiţie Ciclul de viaţă al unui PP este perioada de timp scursă de la punerea problemei şi până la retragerea PP din exploatare.

Ciclul de viaţă al PP se caracterizează fundamental, prin trei momente importante, numite faze ale acestuia:

1. Definiţia;2. Dezvoltarea;3. Exploatarea.

Fiecare dintre aceste faze are diverse etape, ce trebuie parcurse şi în care se desfăşoară diverse activităţi specifice.

1. DefiniţiaAceastă fază începe din momentul în care apare necesitatea rezolvării unei probleme, practic din

momentul formulării problemei. Accentul se pune pe CE face PP: CE informaţie se prelucrează; CE funcţii sau performanţe trebuie să aibă sistemul; CE interfeţe cu alte sisteme sunt necesare; CE restricţii de proiectare există; CE criterii de validare sunt necesare.

În această fază sunt necesare de parcurs următoarele etape: Analiza de sistem; defineşte rolul fiecărui element într-un sistem bazat pe folosirea

calculatorului şi stabileşte rolul ce-l joacă programul; Planificarea proiectului; cuprinde analiza riscurilor, estimarea costurilor şi alocarea

resurselor necesare pentru dezvoltare, definirea sarcinilor de lucru precum şi a orarului de derulare a proiectului;

Analiza cerinţelor; înseamnă definirea detaliată a informaţiei care se prelucrează, specificarea clară a funcţiilor pe care trebuie să le execute PP şi precizarea restricţiilor impuse asupra acestuia.

2. DezvoltareaFaza de dezvoltare pune accentul pe CUM trebuie făcut programul:

se definesc structurile de date şi arhitectura programului; se stabilesc detaliile de implementare ale procedurilor şi datelor; se traduc (codifică) procedurile în limbajul de implementare; se proiectează fişierele şi bazele de date;

5

se realizează testarea.Etapele fazei de dezvoltare sunt:

Proiectarea PP; se traduc cerinţele asupra softului într-un set de reprezentări (grafice, tabelare, bazate pe limbaje de descriere) numite specificaţii de proiectare; acestea descriu structurile de date, arhitectura programului, algoritmii pentru prelucrări şi caracteristicile interfeţei cu utilizatorul;

Codificarea traduce reprezentările de proiectare într-un limbaj de programare; Testarea se face atât în timpul codificării (testarea unitară) cât şi după terminarea

acesteia (testarea de integrare şi testarea de acceptare numită de multe ori validare), având rolul de a descoperi erorile logice şi de implementare.

3. ExploatareaFaza de exploatare reprezintă perioada de maturitate a PP, când el este folosit în scopul pentru

care a fost realizat: începe cu instalarea PP pe calculator, când se realizează şi construirea fişierelor sau

bazelor de date necesare; deoarece mediul în care programul este folosit se modifică continuu, este nevoie ca şi

programul să evolueze pentru a ţine pasul cu noile condiţii de exploatare.Etapele fazei de exploatare sunt:

Exploatarea propriu-zisă, programul este folosit conform documentaţiei de utilizare şi pentru atingerea funcţionalităţii principale ale problemei iniţiale;

Întreţinerea (proces aproape continuu care se suprapune peste exploatare) programului care înseamnă:

o efectuarea de modificări ale acestuia, necesare pentru corectarea erorilor depistate în timpul exploatării (întreţinere corectivă);

o adaptarea la evoluţia sistemului (întreţinere adaptivă);o îmbunătăţirea performanţelor sale (întreţinere perfectivă);

Când PP nu mai corespunde cerinţelor de exploatare sau când întreţinerea este prea costisitoare sau când este disponibil un PP mai bun, atunci el este scos din exploatare şi ciclul său de viaţă se termină.

Studiile efectuate în ultimele decenii arată că distribuţia costului de realizare a unui program se înscrie într-un raport de aproximativ 3/7:

30 % pentru definiţie şi dezvoltare şi 70 % pentru întreţinere.

Costul pentru definiţie şi dezvoltare se distribuie astfel: 40% pentru definiţie (toate etapele acesteia) şi proiectare; 20% pentru implementare (codificare); 40% pentru testare/validare;

Costul pentru întreţinere se distribuie astfel: 20% întreţinere corectivă; 20% întreţinere adaptivă; 60% întreţinere perfectivă.

Unii specialişti şi analişti consideră şi alte modalităţi de descompunere care, în esenţă, au aceleaşi activităţi. Diferenţele, care sunt neglijabile, constau în redenumirea unor etape, sau rafinarea altora în subetape şi folosirea denumirii acestora. Trebuie remarcat că această descompunere în etape distincte se face cu scopul structurării cât mai clare a activităţii de dezvoltare a unui PP şi evidenţierea succesiunii temporale a etapelor. De multe ori pentru un PP de complexitate mică, unele etape se desfăşoară în paralel, de către acelaşi personal.

Un mare specialist, Stephen R. Schach, denumeşte în [Schach, 2002] altfel etapele ciclului de viaţă din cele 3 faze fundamentale ale unui PP:

1. Definirea cerinţelor (analiza de sistem, o parte din analiza cerinţelor);

6

2. Definirea specificaţiilor (partea finală din analiza cerinţelor, planificarea proiectului);3. Proiectarea;4. Codificarea sau implementarea;5. Testarea şi Integrarea;6. Întreţinerea.

Ponderea fiecărei etape în raport cu ansamblul ciclului de viaţă este redată în diagrama următoare. Aceste date s-au obţinut în special de către Boehm [Schach, 2002] şi ele reflectă observarea unor PP în decursul mai multor ani. Procentajul trecut în dreptul fiecărei etape reprezintă costul etapei respective. Acest cost poate fi privit sub aspect temporal (timpul afectat activităţilor etapei respective) sau sub aspect valoric (în bani).

Figura 2.1. Structura ciclului de viaţăParadoxul, că faza de exploatare şi întreţinere este cea mai costisitoare, e numai aparent. Ocupă

aproximativ 2/3 din ciclul de viaţă al PP şi se motivează, printre altele, cu: instruirea personalului de exploatare; instruirea personalului de întreţinere hardware şi software; realitatea (mediul) pentru care s-a rezolvat problema este în continuă schimbare şi deci

PP trebuie să se adapteze încontinuu.

Diverse probleme de management ridică această distribuire a costului. De exemplu dacă clientul, executantul şi utilizatorul sunt una şi aceeaşi firmă. Dacă managerul are de ales între două tehnici noi, una de codificare şi cealaltă de întreţinere care reduc fiecare cu 10% costul etapei respective, va alege mai degrabă noua tehnică de întreţinere pentru că se vor reduce cheltuielile ciclului de viaţă cu 6,7% şi nu cu 1,2% cât s-ar reduce dacă ar adopta tehnica nouă de codificare. În schimb pe termen lung e mai bine să se însuşească noile tehnici de codificare pentru că se vor reflecta în toate PP dezvoltate ulterior.

Legat de raportul dintre hardware şi software (raport analizat mai pe larg în secţiunea 1) precum şi de ponderea întreţinerii este interesant de revăzut predicţia lui Boehm făcută în 1976. Redăm în continuare această diagramă a previziunii costurilor.

7

Vom reliefa în continuare unele trăsături esenţiale ale fiecărei etape definite de Schach.

2.4.1.1. Definirea cerinţelor

Acestă etapă are scopul esenţial de-a identifica problema. Clientul specifică problema de rezolvat în termenii cunscuţi de el (în limbajul clientului). De obicei enunţul este în limbaj natural, cuprinzând, eventual şi termeni specifici domeniului problemei. Etapa cuprinde:

a. un studiu de oportunitate (fezabilitate), în care se analizează avantajele şi dezavantajele economice şi sociale ale rezolvării problemei cu ajutorul calculatorului; acest studiu se poate face comparativ cu vechea metodă (dacă există) de rezolvare a problemei, totodată estimându-se într-o primă aproximare necesarul de mijloace umane şi tehnice;

b. construirea unui model conceptual al sistemului şi al mediului său; această analiză de sistem pune accentul pe descrierea proprietăţilor şi nu pe descrierea mecanismelor care le implementează;

c. elaborarea unei documentaţii de analiză.

În finalul acestei etape se recomandă un feed-back, şi anume pe baza documentaţiei de analiză rezultată trebuie reluate punctele a. şi b. Se elimină eventualele neclarităţi şi ambiguităţi. Totodată se încheie contractul dintre client şi executant în care se stipulează obligaţiile fiecărei părti.

2.4.1.2. Definirea specificaţiilor

Etapa specificaţiilor are ca scop transpunerea cerinţelor într-un limbaj specific informaticii, deci de cel al dezvoltării PP. Această transpunere trebuie să urmeze documentaţia de analiză, pas cu pas, pentru a nu omite nici o cerinţă. Se cunosc mai multe forme (limbaje) de specificare care în general fac parte din următoarele clase:

a) Specificaţia formală;b) Specificaţia informală sau limbajul natural;c) Specificaţia semiformală.

a) Specificaţia formală

8

Pentru problemele de complexitate mică şi problemele tehnico-ştiinţifice este recomandabilă această formă de specificare, dar pentru problemele de complexitate medie şi mare e mai greu de urmărit o astfel de specificaţie. Principalele mijloace de specificare sunt:

formalizările din matematică (exemplu: Z-specifcation); algebrele de specificare; limbajele formale generate de gramatici sau acceptate de automate.

Exemplu:Se dă un tablou de numere de tip întreg, ordonat crescător. Să se elaboreze un program care să

determine lungimea celui mai lung platou. Un platou este o subsecvenţă maximală de elemente consecutive din tablou care conţin aceeaşi valoare.Specificarea formală folosind logica predicatelor şi a propoziţiilor matematice poate avea forma:

Intrare: nN ( a[i]Z, ); Un platou e caracterizat de o pereche de indici (j,k): (1jkn) (a[j-1]<a[j]=a[k]<a[k+1]) (lungimea platoului lp=k+1-j).

Ieşire: Cel mai lung platou este caracterizat de predicatul:( (j:0jn-lp a[j]=a[j+lp-1]) ( k:0k n-lp-1) a[k] a[k+lp] )

Pentru cei nefamiliarizaţi cu formalismul logicii propoziţiilor şi predicatelor specificarea de mai sus este mai greu de urmărit [Gries, 1983]. Alte metode formale de specificare sunt şi mai greu de înţeles şi trebuie însuşite temeinic în prealabil.

b) Specificaţia informală sau limbajul natural

În general specificarea în limbaj natural crează ambiguităţi pentru simplul motiv că limbajul natural este ambiguu. Totodată specificarea are mari şanse să conţină contradicţii şi formulări incomplete, chiar pentru probleme de complexitate relativ mică.

Exemplu:Dându-se un text format din cuvinte separate printr-un caracter spaţiu sau NewLine, să se

elaboreze un program care să convertească textul într-o secvenţa de mai multe linii după următoarele reguli:

1) Fiecare linie să conţină o parte din text ce se termină cu un cuvânt;2) Fiecare linie să conţină cât mai multe cuvinte din text;3) O linie să aibă cel mult MaxChar caractere (MaxChar dat deasemenea).

Problema a fost propusă de Naur [Schach, 1992]. Cu toate că problema este enunţată de un specialist în domeniu, ea nu este completă. Erorile, de fapt ambiguităţile şi impreciziile, au fost observate de mai mulţi informaticieni, Leavenwort, London, Goodenough, Gerhart, în anii următori şi propuse noi enunţuri, mai lungi şi mai precise. De exemplu nu se specifică dacă textul poate să înceapă sau să se termine cu un spaţiu. Goodenough şi Gerhart au dat o specificaţie formală în limbaj matematic, lungă şi complexă.

c) Specificaţia semiformalăÎn general această formă mixtă de specificare este cea mai recomandabilă, fiindcă îmbină

formalizările cu explicaţiile detaliate în limbaj natural.

În încheierea acestor precizări despre cele mai folosite trei modalităţi de specificare trebuie spus că fiecare problemă nu este definită complet şi asta cel puţin din 2 motive:

datorită cunoştiinţelor din domeniu (ale autorului problemei) nu se precizează (definesc) toate noţiunile care apar în enunţ;

diferenţa de percepţie a problemei între client şi executant datorită pregătirii diferite.

9

Această etapă se încheie cu o documentaţie de specificare care va cuprinde un model logic al PP şi un plan de conducere a proiectului. Acest plan va cuprinde:

estimarea volumului de muncă; estimarea necesarului de personal şi tehnică de calcul; planificarea temporală a fazelor de proiectare, implementare şi integrare; estimarea costului total al proiectului.

2.4.1.3. Proiectarea

Scopul acestei etape este de a preciza CUM sunt realizate specificaţiile, care sunt algoritmii folosiţi şi structurile de date cu care se lucrează. Termenul proiectare este folosit în multe accepţiuni de autorii diverselor metode, aşa încât multe metode ce se afirmă că sunt metode de proiectare includ de fapt şi aspecte ce ţin de specificare şi implementare.

Proiectarea este etapa în care sistemul ce urmează a fi realizat este despărţit de mediul său. Modelul logic produs în faza anterioară, de specificare, este rafinat succesiv şi concretizat, obţinându-se modelul fizic. Accentul se pune pe realizarea proprietăţilor structurii sistemului. Se disting cel puţin două nivele de proiectare:

proiectarea de ansamblu, la nivelul PP, sau la nivel macro; se stabileşte arhitectura acestuia, adică a subsistemelor (în cazul PP ce depăşesc complexitatea medie) şi/sau a modulelor şi a interdependeţelor dintre acestea;

proiectarea de detaliu, la nivel de modul; proiectarea structurilor de date şi a operaţiilor.Există mai multe forme de reprezentare a proiectului. La nivel macro se folosesc mai ales

diagramele de structură de genul celei care se redă în figura următoare (dreptunghiurile reprezintă module):

La nivel de detaliu se vor preciza algoritmii care rezolvă procedurile/funcţiile fiecărui modul. Cele mai folosite formalizări pentru descrierea algoritmilor sunt:

limbajul schemelor logice; limbajele de tip pseudocod.

Dacă schemele logice au avantajul că sunt mai sugestive (diagramele sau desenele sunt întotdeauna mai sugestive decât un text oricât de structurat) în schimb au dezavantajul că fluxul de control al algoritmului poate fi foarte complicat, dacă nu se folosesc riguros D-structurile de control, sau se poate întinde pe mai multe pagini, şi deci mai greu de urmărit.

10

Limbajul pseudocod are o mare varietate de structuri, se aseamănă cu structurile de control ale limbajelor procedurale de programare. Are şi o mare flexibilitate, un astfel de limbaj pseudocod putând fi extins sau redefinit de executant pentru fiecare PP. În pseudocod se definesc de obicei propoziţii standard şi propoziţii nestandard. Un exemplu de propoziţie standard este structura repetitivă pretestată:

CâtTimp condiţie Execută instrucţiuni

SfCâtTimp;

Sau o altă formă în engleză, apropiată de structura similară din limbajul PASCAL:While condiţie

Do instrucţiuni EndWhile;

Propoziţiile nestandard specifică acţiuni (sau funcţii) mai complexe care se vor detalia în propoziţii standard la nivele de rafinare ulterioare. Totodată pseudocodul este mai flexibil la numele cheie folosite în structurile sale de control (după cum s-a văzut din exemplul anterior) şi este mult mai apropiat de un limbaj de programare procedural.

Reluând problema platoului de lungime maximă o rezolvare simplă reprezentată în pseudocod ar fi următoarea:Prima abordare

BEGIN// problema celui mai lung platou ijk1; // i indice de scanare a tabloului a // j, k indici de delimitare a platoului lp0; // lp conţine lungimea platoului WHILE i<=n DO BEGIN

@ Determina lp // propoziţie nestandard ENDWHILE;END.

A doua rafinareBEGIN// problema celui mai lung platou ijk1; // i indice de scanare a tabloului a // j, k indici de delimitare a platoului lp0; // lp conţine lungimea platoului WHILE i<=n DO BEGIN IF a[i-lp] = a[i] THEN

BEGIN lplp+1; ji-lp+1; ki; END ii+1;

ENDWHILE;END.

Etapa de proiectare se încheie cu documentul aferent numit documentaţie de proiectare care conţine atât proiectul de ansamblu cât şi proiectele de detaliu pentru fiecare modul.

2.4.1.4. Implementarea

Implementarea (codificarea proiectului într-un limbaj de programare, sau programarea propriu-zisă) constă în procesul translatării algoritmilor, deduşi în urma proiectării, într-un limbaj de programare. Implementarea codifică modulele logice ale proiectului rezultând modulele fizice. Accentul se pune pe codificarea proiectului utilizând primitivele (tipurile de date şi instrucţiunile)

11

limbajului de programare ales dar şi mecanismele implementării obiectelor, dacă s-au ales metode specifice proiectării obiect. În acest punct al procesului, sunt deja definite atât structura cât şi comportamentul sistemului. De obicei, în funcţie de complexitatea PP, acest proces este realizat fie de un singur programator, fie de o echipă de programatori. Pentru problemele de complexitate mică şi medie e recomandabil ca implementarea să fie făcută de un singur programator, iar pentru PP de complexitate mare programarea în echipă devine obligatorie.

Indiferent de forma de organizare aleasă, individual sau în echipă, există câteva activităţi mai importante ale acestei etape:

a) alegerea limbajului de programare;b) codificarea propriu-zisă;c) testarea fiecărui modul.

a) Alegerea limbajului de programare

Această alegere a limbajului de programare, sau a limbajelor de programare, se face în funcţie de natura problemei, de metodele de proiectare şi în funcţie de calificarea personalului.

b) Codificarea propriu-zisă

La prima vedere nu pare a ridica probleme deosebite, dar cei ce se ocupă de această activitate, trebuie să cunoască foarte bine limbajele de programare alese şi trebuie de multe ori să decidă asupra unor părţi care nu se programează banal – de exemplu interfeţele PP, structurile de control din pseudocod care nu au echivalent în limbaj, etc.

Când munca este organizată în echipă, trebuie rezolvat managementul la acest nivel, trebuie să se găsească mijloacele de comunicare între programatori, etc. În literatura de specialitate sunt menţionate mai ales două organizări:

echipa democratică; echipa programatorului şef.

În echipa democratică propusă de Weinberg [Weinberg, 1971] fiecare programator îşi încurajează colegii să-i găsească erorile în modulele sale. Erorile nu sunt considerate ca proprii unui individ ci ca erori ale echipei. O astfel de organizare dă rezultate mai ales la problemele dificile. Schach nu consideră această formă de organizare ca fiind optimă, punând accent pe timpul ce se pierde privind

comunicaţiile interpersonale arătând că pentru n persoane există canale de comunicaţii.

Totodată există riscul ca majoritatea timpului să se piardă în multe discuţii de grup asupra unor momente critice ivite în programare.

Echipa programatorului şef, a fost folosită după modelul echipei medicale de intervenţie chirurgicală (un chirurg conducător, ajutorul său, anestezistul şi asistentele medicale, fiecare foarte specializat) şi este alcătuită din:

un conducător (programatorul şef) care cunoaşte foarte bine proiectul; un secretar care se ocupă cu toate documentele echipei (documentaţie, listare text sursă,

menţinerea fiabilităţii tehnicii de calcul, etc.); un programator adjunct care trebuie să cunoască derularea procesului de programare la

fel ca programatorul şef, la nevoie să-l înlocuiască; 2 – 4 programatori ajutori care fac munca de programare a fiecărui modul la termene

precise.

Structura acestei echipe este redată în figura următoare. Se observă că este o structură ierarhică cu două nivele.

12

Figura 2.4 Echipa programatorului şef

Această formă de organizare a fost folosită de IBM, în 1971 la sistemul informatic al ziarului „New York Times”. Acest proiect se referea la crearea unei bănci de articole de ziar privind stocarea şi regăsirea lor după diverse criterii. Proiectul a fost realizat în 22 de luni calendaristice printr-o muncă echivalentă a 11 persoane timp de un an de zile. S-au scris 83000 de linii sursă (în primul an s-au realizat doar 12 000 linii sursă, majoritatea liniilor sursă fiind scrise în ultimele şase luni) iar greşelile găsite au fost 22 în primele 5 săptămâni în etapa de integrare a modulelor şi 25 de greşeli în primul an de exploatare.

Schach relevă 3 argumente care au dus la succesul proiectului: prestigiul programatorilor de la IBM; programarea s-a făcut în limbajul PL/1, limbaj promovat intensiv de IBM în acei ani,

echipa având permanent la dispoziţie asistenţa celor care au realizat compilatorul PL/1 (mai mult de jumătate din subprograme, cu un număr de linii sursă între 200 şi 400, au fost corecte la prima compilare);

programatorul şef, F. Terry Baker, s-a remarcat în acelaşi timp ca un superprogramator şi ca un manager aproape perfect.

În anii următori această formă de organizare nu a mai avut acelaşi succes iar Schach explică acest lucru prin faptul că e greu să se găsească persoane pentru funcţia de programator şef care să aibă cele două calităţi fundamentale: să fie un programator excepţional şi să fie un manager perfect. Bill Gates, proprietarul principal al MICROSOFT, este un alt exemplu de superprogramator şi manager excepţional [Ichbiah, 1995].

Schach propune aşa numita echipa programatorului şef modificată în care există 2 manageri: unul pe linie tehnică (programare) şi altul pe linie organizatorică, reflectată în figura următoare.

13

Figura 2.5. Echipa cu 2 manageri

Pentru proiectele de mare complexitate Schach propune organizarea următoare:

Figura 2.6. Echipa centralizată

Această structură este ierarhică şi centralizată fără căi de comunicaţie la acelaşi nivel, de aceea există şi un model descentralizat în care e permisă comunicarea pe acelaşi nivel. Figura următoare redă acest lucru.

Figura 2.7. Echipa descentralizată

14

Trebuie să remarcăm că aceste propuneri de echipe nu se referă strict la etapa de programare. Acestea pot fi folosite începând cu etapa de specificare.

Există mijloace software care ajută programatorii în implementare: editoare de text, compilatoare, depanatoare, medii de programare integrate şi vizuale, produse CASE (Computer Aided Software Engineering).

c) Testarea

Testarea fiecărui modul se face într-o primă fază de către cei care l-au programat dar e recomandabil să se facă şi de cei care au scris specificaţiile. Testarea ar trebui să arate corectitudinea modulului dacă verifică în totalitate specificaţiile acestuia. De multe ori trebuie construite simulatoare (programe de test) pentru verificarea fiecărui modul. Un exemplu foarte sugestiv este cel al lui Paul Allen şi Bill Gates, fondatorii firmei MICROSOFT, care au folosit simulatoare pentru testarea compilatorului BASIC scris pentru microcalculatorul ALTAIR. Deoarece nu dispuneau de un astfel de calculator, Paul Allen a elaborat un simulator al limbajului de asamblare pe care îl foloseau pe minicalculatorul DEC PDP-11. Bill Gates a elaborat toate modulelele compilatorului BASIC în limbajul de asamblare al calculatorului ALTAIR. Împreună au testat compilatorul BASIC pe DEC PDP-11 cu ajutorul simulatorului [Ichbiah, 1995].

Testarea trebuie să arate că nu există erori în module. IEEE face distincţie între eroare („fault” sau în jargonul programatorilor „bug”) şi comportamentul anormal („failure”) al unei modul din cauza unei erori.

Din păcate testarea pune în evidenţă erori în programare dar nu este un mijloc de a demonstra absenţa lor, [Dijkstra, 1972]

Goodenough defineşte testarea ca un proces inferenţial de observare a comportamentului unui program în urma execuţiei lui într-un mediu cunoscut cu date de test, [Frenţiu,Pârv,1994]. Schach critică procesul de deducere (inferenţial) a comportamentului, pentru că acesta se face de obicei cu date de test puţine şi, afirmă el, că doar pentru acestea se deduce comportamentul. Mediul în care se execută programul nu este de multe ori sigur (cunoscut), deci nu e sigur că sistemul de calcul este perfect hardware şi software (mai ales în privinţa sistemului de operare). Pe de altă parte nu există un criteriu eficient de a găsi datele de test cele mai semnificative.

Acelaşi Goodenough consideră că pentru stabilirea comportamentului programului trebuie urmărite cel puţin cinci caracteristici:

utilitate (utility); siguranţă în funcţionare (reliability); robusteţe (robustness); performanţă (performance); corectitudine (corectness).

Utilitatea se referă în general la respectarea specificaţiilor PP. A respecta specificaţiile deduse din cerinţele clientului înseamnă a rezolva pentru acesta o parte din munca care se face cu ajutorul calculatorului.

Siguranţa în funcţionare este o măsura a frecvenţei apariţiei erorilor precum şi a frecvenţei apariţiei momentelor critice. De obicei momentele critice apar pentru sistemele în timp real (conducerea proceselor tehnologice, tranzacţii bancare, etc.) şi sunt caracterizate prin restricţii de timp în răspunsul programului, partajarea unor resurse hardware şi software, etc. Goodenaough consideră că trebuie cunoscute cel puţin 2 elemente:

timpul mediu estimativ între două „căderi” consecutive ale programului;

15

timpul mediu estimativ pentru repararea oricărei erori.De reţinut că cele două elemente nu sunt independente în marea majoritate a cazurilor. Pentru a reliefa importanţa acestor estimări să considerăm că un sistem de tranzacţii bancare are o medie de 6 luni între apariţia a două erori. S-ar deduce că are o siguranţa de funcţionare ridicată. Dar dacă repararea erorii necesită 2 zile (determinarea tipului de eroare, localizarea erorii în modul, rescrierea codului apoi înregistrarea tranzacţiilor pentru cele două zile pe un alt suport, transcrierea lor în sistem, eventuale probleme cu comunicaţiile, etc) se poate spune că programul are o siguranţă scăzută în funcţionare.

Robusteţea se referă în general la funcţionarea corectă (fără căderi) a programului indiferent de modificarea mediului de rulare. De exemplu un program trebuie să dea un răspuns pentru orice fel de date de intrare, chiar dacă valorile de intrare nu fac parte din domeniul de definiţie al variabilelor de intrare. Dacă la intrare se cer valori numerice şi se introduc valori de alt tip, programul are o robusteţe mică dacă se blochează şi dă controlul sistemului de operare care emite şi un mesaj de eroare. În schimb dacă programul execută o rutină de eroare, dă câteva explicaţii despre tipul valorilor de intrare şi revine la citirea altor date se poate spune că are o robusteţe ridicată. Multe firme de software oferă recompense celor care depistează o eroare legată de robusteţea programelor lor.Exemplu de procedură robustă la citirea datelor de intrare:

rutinaRobustaCitireCiteste x; // x are domeniul D de valori CâtTimp xD Executa

rutinaEroareAtentionare;Citeste x;

SfCâtTimp;SfRutinaRobustaCitire

Alt exemplu: următorul cod sursă este corect:

xn/d;

dar nu este robust pentru că variabila d nu verifică condiţia d 0.Mai robust este următorul cod sursă care rezolvă acelaşi lucru:

if d = 0 then rutinaEroareelse x:=n/d

endif;

Performanţele unui program sunt legate în general de mijloacele hardware folosite, timpul de răspuns, munca depusă, personalul folosit în exploatare, etc., toate în raport cu complexitatea funcţiilor rezolvate de program.

Corectitudinea. Se confundă de multe ori testarea cu demonstrarea corectitudinii unui program. În general demonstrarea corectitudinii unui program este o verificare (demonstrare) matematică formală a faptului că din specificaţia de intrare se deduce specificaţia de ieşire şi nu necesită execuţia programului. Înainte de a demonstra corectitudinea unui program trebuie să se demonstreze corectitudinea specificaţiilor sale. De exemplu următoarea specificare pentru o problemă de sortare pare corectă la prima vedere:

Intrare: nN*, A=<a1..an>, aiZ, i= ;Ieşire: B : (B=<b1..bn>; biZ, i= ; ) (b1 b2 ... bn);

Nu se specifică dacă elementele tabloului B sunt sau nu o permutare a elementelor tabloului A, acest aspect subînţelegându-se. Dar logic nu e corectă specificarea pentru că de exemplu, valorile b i = 0,

îndeplinesc specificaţia de ieşire. Mai corectă este următoare specificare:

16

Intrare: nN*, A=<a1..an>, aiZ, i= ;Ieşire: B : (B=<b1..bn>; biZ, i= ; ) (b1 b2 ... bn);

(elementele lui B sunt o permutare a elementelor lui A).

Verificarea corectitudinii specificaţiilor a dus la aceea adevărată poveste a problemei lui Naur, prezentată la paragraful 2.1.2. Naur a scris un program de 25 de linii sursă în limbajul ALGOL 60 şi a demonstrat matematic corectitudinea lui. Dar pentru specificaţia dată de el. Ceilalţi specialişti au completat specificaţia şi au demonstrat apoi corectitudinea ei. Alte 4 erori au fost apoi depistate la testarea programului pe diverse seturi de date de test. Concluzia este că testarea şi demonstrarea corectitudinii programelor sunt lucruri diferite care sunt complementare.

În [Văduva,1986], [Gries, 1983], [Schach, 1992], [Schach, 2002], [Frenţiu,Pârv, 1994] se dau exemple mai complexe de demonstrare a corectitudinii unor programe, precum şi clasificări ale metodelor de demonstrare.

2.4.1.5. Testarea şi integrarea

Componentele (subsistemele/modulele) sunt integrate în fişiere şi biblioteci şi apoi produsul este testat în întregul său. Acestă etapă cuprinde două activităţi:

testarea producătorului; testarea clientului sau validarea (testarea de acceptare).

Testarea producătorului cuprinde testarea mai multor elemente: funcţiile locale şi globale ale PP (specificaţiile); interfeţele între module; interfeţele cu utilizatorul; testarea globală a produsului pe mai multe seturi de date.

Este bine ca aceste elemente să fie testate de altă echipă decât cea care a realizat implementarea pentru că este posibil să se descopere erori ascunse care pentru echipa de implementare să nu fie evidente.Testarea de acceptare se face de către client sub supravegherea şi îndrumarea producătorului. Se testează funcţiile globale ale sistemului şi interfaţa cu utilizatorul (ceea ce face şi nu cum se face). PP este privită ca o cutie neagră de către utilizator, se verifică ieşirile deduse din intrări. La sfârşitul acestei etape produdul trece din faza de dezvoltare în faza de exploatare şi întreţinere.

2.4.1.6. Exploatarea şi întreţinerea

Această etapă este partajată în două activităţi complementare exploatare şi întreţinere. În timpul exploatării pot apare erori care trebuie remediate, pot apare noi cerinţe din partea clientului şi deci apare necesitatea modificării PP, în fapt a întreţinerii.Exploatarea cuprinde atât instruirea beneficiarului cât şi utilizarea propriu-zisă a PP.Întreţinerea include toate modificările aduse PP după ce clientul a făcut testarea de acceptare.În funcţie de tipul modificărilor specificaţiilor iniţiale ale PP întreţinerea este de două feluri:

întreţinere corectivă (întreţinere de reparare), adică eliminarea erorilor care apar în timpul exploatării, fără modificarea specificaţiilor, 20%;

întreţinere de actualizare care presupune modificarea specificaţiilor şi implementarea acestor modificări şi cuprinde la rândul ei:

o întreţinere perfectivă care se face ca urmare a perfecţionării funcţiilor sistemului, a adăugării de funcţii noi; se adaugă noi specificaţii, 60%;

o întreţinere adaptivă care e necesară în momentul când mediul se schimbă; deci pentru aceeaşi problemă e nevoie de alte specificaţii, 20%.

17

Procentajele medii sunt date de Schach în [Schach, 1992], [Schach, 2002] citând studii efectuate de Lientz, Swanson şi Tompkins.Exploatarea şi întreţinerea este considerată nu numai cea mai costisitoare etapă a ciclului de viaţă ci şi cea mai dificilă. Orice modificare în specificaţii aduce după sine modificare în programele PP, iar acestea induc posibile erori, Noile versiuni al programelor trebuie testate şi trebuie verficată influenţa lor asupra celorlalte părţi ale PP. Pentru a face modificări într-un program sunt necesare cât mai multe0020informaţii despre acesta. Apare astfel necesitatea folosirii şi actualizării documentaţiei aferente PP.

18