2. algoritmi. descrierea algoritmilor.complexitate

1. INGINERIA SOFTWARE.
2. ALGORITMI. DESCRIEREA ALGORITMILOR.COMPLEXITATE.
3. LIMBAJE SI GRAMATICI FORMALE.
4. INSTRUMENTE DE PROGRAMARE.
5. STRUCTURI DE DATE.

1. INGINERIA SOFTWARE

Inginerie: studiul unui proiect industrial sub toate aspectele sale ( tehnologice, economice, financiare, monetare si sociale ) si care necesita o activitate de sinteza, coordonand munca mai multor echipe de specialisti.

Ingineria software reprezinta ingineria proiectelor sistemelor informatice si are ca scop punerea la dispozitia dezvoltatorilor de software a instrumentelor teoretice necesare dezvoltarii cvasistandardizate si, eventual cvasiutomatizate, a sistemelor software.

Sistem software reprezinta o aplicatie informatica de mari dimensiuni si mare complexitate care depaseste capacitatea de analiza si sinteza a unui singur specialist, indiferent de gradul de pregatire si coeficientul de inteligenta ale acestuia, si care urmeaza a fi realizata de catre o grupa sau mai multe de specialisti, de obicei din domenii diferite. ( exemplu: un joc de strategie gen "Age of Impire", sistem de securitate al unui obiectiv important, sistem de operare, etc).

Ciclul de viata al unui sistem software poate fi reprezentat schematic ca mai jos:

Iar faza de elaborare poate fi reprezentata astfel:

In faza de analiza, specialistii software conclucreaza stans cu specialistii domeniului la care se refera sistemul informatic pentru a identifica cerintele sistemului:

a)      Cerinte functionale: descriu modul in care trebuie sa functioneze sistemul prin precizarea intrarilor si iesirilor sale si a modului in care se ajunge de la o intrare la o iesire;

b)      Cerinte nefunctionale:se refera la performantele pe care trebuie sa le atinga sistemul ( fiabilitate, grad de utilizare, rapiditate de executie, ect );

c)      Restrictii de proiectare:se refera la acea categorie de cerinte care nu afecteaza cerintele functionale dar sunt impuse de client si pot fi ( sistem de operare gazda, tip de interfata, etc.).

Procesul de analiza raspunde la intrebarea "ce trebuie realizat?" si se incheie cu un set de specificatii care se poate reprezenta sub forma text sau grafic, de corectitudinea acestei etape depinzand ciclul de viata al sistemului.

In faza de proiectare, care se bazeaza pe rezultatele primei etape, care spune de fapt ce trebuie realizat, aceasta etapa trebuind sa raspunda la intrebarea "cum trebuie realizat". Abordarea clasica a acestei etape este aceea aproictarii top-down in care sistemul este considerat o entitate abstracta, fara detalii despre modul in care este realizat in realitate. La nivelul cel mai inalt proiectantul stabileste arhitectura sistemului prin identificarea unor componente functionale ale sistemului si a relatiilor dintre acestea. In continuarea se trece la detalierea componentelor identificate mai sus, deci se poate spune ca proiectarea are doua aspecte:proiectarea arhitecturii sistemului si proiectarea detaliilor, asa cum se arata si in tabelul de mai jos:

In faza de implementare, care se bazeaza pe rezultatele etapei de proiectare, se realizeaza scrierea codului in limbajul de programare specificat. Pentru implementarea sistemelor software, la care participa mai multe echipe si care se pot modifica pe parcurs, se impune o disciplina a stilului de programare care sa permita o gestionare optima a sistemului pe termen lung ( codul scris de o persoana trebuie sa poata fi inteles usor si de alte persoane ).

Stilul de programare se refera in special la modul de folosire a urmatoarelor elemente de limbaj de programare:

a)      Comentariile, care trebuie sa permita extragerea automatizata a documentatiei si sa ofere explicatii referitoare la algoritmii folositi;

b)      Spatiile albe ( identarea ) care sa permita identificarea rapida a modulelor de program;

c)      Identificatorii care trebuie sa corespunda politicii firmei in domeniu si sa fie cat mai descriptivi in contextul modulului de program si sa evite coliziunile;

d)     Delimitatorii care trebuie sa permita diferentierea rapida intre diferitele tipuri de entitati cu forme cvasiasemanatoare.

Un alt aspect important al acestei faze il constitue proprietatile codului scris care ar trebui sa permita realizarea urmatoarelor cerinte:

a)      posibilitatea reutilizarii codului;

b)      posibilitatea de extensie rapida;

c)      robustetea codului ( tratarea exceptiilor si a erorilor).

Limbajul de programare folosit este stabilit de obicei in cadrul fazelor anterioare si depinde de caracteristicile sistemului software proiectat de mediul in care acesta va rula si nu in ultimul rand de pregatirea achipelor de programatori la dispozitie. Se pot folosi limbaje de programare structurate ( C, Pascal, etc. ) sau limbaje de programare orientate pe obiecte ( C++, Java, Simula, Eiffel, Smalltalk, Object Pascal, etc).

In faza de testare se verifica codurile scrise, separat pe module functionale si integrat in sistem, in scopul depistarii erorilor existente. In afara celor doua categorii de teste se mai executa teste asupra elementelor de baza ale codului ( functii, subrutine, clase ) precum si teste de acceptare ( se ofera clientului o varianta pentru a o testa live si a-si expune parerile asupra faptului daca sistemul corespunde cerintelor ).

Pe toata durata ciclului de viata a unui sistem software se elaboreaza documentatia care descrie sistemul din puncte de vedere diferite, in functie de utilizatorii sistemului. In functie de utilizatorii sistemului documentatia poate fi clasificata astfel:

a)      Documentatia de sistem care cuprinde:

Specificatia cerintelor;

Specificatia de proiectare;

Descrierea planului de testare;

etc.

b)      Documentatia utilizatorului care cuprinde:

Manual introductiv;

Manual de referinta;

Descrierea functionala;

Documentatia de instalare;

Ghidul administratorului de sistem.

Elaborarea asistata de calculator a sistemelor software

Pentru elaborarea sistemelor software de mare complexitate se impune ca activitatile de rutina sa poata fi automatizate astfel incat cea mai mare parte a timpului sa poata fi afectata activitatilor de conceptie ( analiza si sinteza ) a sistemului. Instrumentele de automatizare a procesului de elaborare a sistemelor software se numesc instrumente CASE ( Computer Aided Software Engineering ) si au putut fi create numai dupa ce s-a adoptat un standard al procesului de elaborare si un limbaj unificat de schimb de date. Un limbaj unificat de schimb de date a fost creat de catre un consortiu non-profit de aproximativ 800 de firme ( printre care toate firmele mari de software ) care se cheama OMG ( Object Management Group ) si care are drept scop promovarea uneo arhitecturi bazata pe modele MDA ( Model Driven Architecture) , care sa asigure o abordare deschisa a aplicatiilor, independenta de firma furnizoare, folosind standardele de modelare: UML ( Unified Modeling Langauage ), MOF ( Meta Object Facility) si CWM ( Common Warehouse Meta-model). Clasele de produse CASE pot fi categorisite astfel:

UML ( Unified Modeling Langauge )

Limbajul UML este un limbaj de modelare, independent de limbajele de programare sau de procesul de eleborare a sistemelor software, care poate fi folosit pentru specificarea, construirea si vizualizarea sistemelor software si crearea documentatiei acestora. UML face parte, alaturi de: MOF ( Meta-Object Facility ), XMI ( XML Metadata Interchange ) si CWM ( Common Warehouse Meta-model ), din arhitectura MDA ( Model Driven Architecture ) promovata de OMG.

Ca notatii UML foloseste urmatoarele tipuri de diagrame:

a)      Diagrama cazurilor de utilzare;

b)      Diagrama de clase;

c)      Diagrama secventiala;

d)     Diagrama de colaborare;

e)      Diagrama de stare;

f)       Diagrama de activitati;

g)      Diagrama de componente;

h)      Diagrama repartizarii resurselor;

i)        Diagrama sistemului modelat la nivel inalt.

2. ALGORITMI

Algoritmul reprezinta o multime finita de operatii elementare care constitue schema de calcul sau de rezolvare a unei probleme. In contextul informaticii algoritmul este o notiune fundamentala si poate fi definit ca un sistem de reguli elementare conform caruia o informatie initiala ( de intrare ) este transformata intr-o informatie finala ( de iesire ).

Orice algoritm trebuie sa indeplineasca simultan urmatoarele cerinte:

a)      Generalitate: un algoritm poate fi aplicat oricarei informatii din domeniul sau altfel spus un algoritm rezolva o clasa de probleme de acelasi tip;

b)      Finitudine: numarul transformarilor ce trebuie aplicate unei informatii de intrare pentru a se obtine informatia de iesire este finit.

c)      Unicitate: daca informatia de intrare apartine domeniului unui algoritm, atunci toate transformarile prin care trece aceasta pentru a se obtine informatia finala, sunt univoc determinate de regulile algoritmului ( algoritmul nu contine ambiguitati sau bucle infinite ).

Un algoritm trebuie sa fie transpus intr-un sistem de comunicare pentru a fi transmis si inteles de catre terti. Dupa cum tertul este om sau masina sistemul de comunicare poate fi pseudocod, schema logica sau limbaj de programare ( pseudocodul si schemele logice se adreseaza omului, iar limbajul de programare masinii ).

Limbajul pseudocod este un sistem de comunicare in cadrul caruia ideile pot fi exprimate mai putin formal ( independent de masina si mai apropiat de limbajul natural) prin folosirea unor cuvinte denumite mnemonice. Operatiile elementare intalnite in cadrul unui algoritm sunt urmataoarele:

a)      operatii de selectie;

b)      operatii repetitive;

c)      operatii de atribuire;

Deasemenea la descrierea unui algoritm in limbaj pseudocod se mai pot folosi comentariile si identarea. In continuare vom folosi urmatorul limbaj pseudocod:

a)      pentru reprezentarea operatiei de atribuire se va folosi semnul , respectiv expresia: a b semnifica faptul ca variabilei "a" i se atribuie valoarea variabilei "b";

b)      pentru reprezentarea operatiei de selectie simpla se va folosi secventa:

DACA (<conditie> )ATUNCI

[ALTFEL

c)      pentru reprezentarea operatiei de selectie multipla se va folosi secvaenta:

COMUTA DUPA(<expresie>)

d)     pentru reprezentarea operatiei repetitive cu numar cunoscut de iteratii:

PENTRU contor val_i PANA LA val_f

e)      pentru reprezentarea operatiei repetitive cu numar necunoscut de iteratii preconditie:

CAT TIMP (<conditie>)

f)       pentru reprezentarea operatiei repetitive cu numar necunoscut de iteratii postconditie:

EXECUTA

CAT TIMP (<conditie>)

Schema logica se foloseste pentru reprezentarea grafica a algoritmilor. Simbolurile folosite pentru reprezentarea grafica a algoritmilor sunt:

a) terminatorul: arata inceputul (START) sau sfarsitul ( STOP ) unui algoritm

b)operatie intrare/iesire

c) operatie de decizie

d) bloc de prelucrare ( executie )

e) conector

g)      inceputul unui subalgoritm

h)      apelul unui subalgoritm

Analiza algoritmilor, algoritmi de sortare.

3. LIMBAJE SI GRAMATICI FORMALE

Constructia limbajelor de programare se bazeaza pe teoria limbajelor formale. Strict formal un limbaj este o multime de cuvinte create dupa anumite reguli, reguli stabilite de gramatica limbajului. Un cuvant este format dintr-o multime de simboluri. Multimea de simbolurile folosita pentru crearea cuvintelor se numeste alfabet si o notam cu V Deci orice element w al multimii V^*=se numeste cuvant peste alfabetul V. Numarul de simboluridin care este compus cuvantul se numeste lungimea cuvantului. Cuvantul vid se noteaza cu λ. Limbajele se pot reprezenta fie prin intermediul automatelor, fie prin intermediul sistemelor de ecuatii fie prin intermediul regulilor de productie si a gramaticilor asociate.

O gramatica formala este un sistem G=(V_N,V_T,S,P) unde V_N si V_T sunt alfabete disjuncte, S V_N, iar P (V_N V_T)^*V_N(V_N V_T)^*X(V_N V_T)^*. Elementele multimii V_N se numesc simboluri neterminale sau variabile, elementele multimii V_T se numesc simboluri terminale, S este simbolul de start al gramaticii, iar P reprezinta multimea regulilor de productie.

Dupa caracteristicile regulilor de productie gramaticile se impart in :

a)      gramatici dependente de context in care orice productie u v staisface conditia |u| |v| (lungimea cuvantului u este cel mult egala cu a cuvantului v ):

b)      gramatici independente de context in care orice productie u v satisface conditiile |u|=1 si v

c)      gramatici regulate in care orice productie u v satisface conditiile |u|=1 si v∈,v

4. INSTRUMENTE DE PROGRAMARE

Un program executabil este o forma binara de fisier care executa deferite operatii in cadrul unui context dat ( sistem de operare, masina locala sau la distanta, local sau in retea, etc). programele executabile in format binar sunt generate de compilatoare si editoare de legaturi. In mod ibisnuit un program este constituit din mai multe fisiere sursa ( fisiere in format ASCII ) si apeleaza mai multe functii de biblioteca ( statica sau dinamica ).

Pentru crearea programelor sunt necesare urmatoarele instrumente:

a)      un editor de texte in format ASCII care permite crearea programelor sursa;

b)      un compilator care permite crearea programelor obiect;

c)      un editor de legaturi care permite crearea programelor executabile;

d)     un depanator care permite depistarea si inlaturarea eroriolor;

e)      un sistem de compilare si editare de legaturi automat care asigura compilarea si editarea de legaturi numai pentru fisierele modificate.

La momentul actual sunt disponibile instrumente integrate de programare, instrumente care se poat categorisi astfel:

a)      Medii Integrate de Programare ( Integrate Develeoment Enviroment -IDE) sunt acele instrumente care contin toate instrumentele necesare programarii in acelati cadru;

b)      Medii Rapide de Programare ( Rapid Aplication Development -RAD) sunt acele instrumente care pe langa instrumentele necesare programarii ofera si o serie de componente soft gata de utilizare ( in special pentru interfata cu utilizatorul );

c)      Cadru de Lucru ( FrameWork) care ofera un schelet gata fabricat si functional pentru o serie de tipuri de aplicatii.

5. STRUCTURI DE DATE

Programele sunt constituite din date si din operatii care se executa asupra acestora. Limbajele de programare permit folosirea a doua categorii de date: date fundamentale ( date intriseci specifice compilatoarelor ) si date utilizator ( date derivate de utilizatori din datele fundamentale ). In continuare vom prezenta tehnici de baza pentru reprezentarea multimilor dinamice finite si pentru manipularea lor cu ajutorul calculatoarelor. Intr-o implementare tipica a unei multimi dinamice, fiecare element al multimii este reprezentat de un obiect ale carui campuri pot fi exeminate si manipulate daca avem un pointer ( referinta ) la acel obiect. Unul din cimpurile elementelor multimii este un cimp cheie, de identificare.Operatiile pe o multime dinamica finita pot fi impartite in doua categorii si anume:

a)      interogarile sunt acele operatii care nu modifica multimile dar returneaza informatii despre acestea;

b)      operatii de modificare sunt acele operatii care modifica continutul multimilor.

Aceste operatii le vom nota in pseudocod astfel:

CAUTA(S,k):intoarce un pointer spre elementul al carui camp cheie este k sau NULL daca nu exista nici un element cu campul cheie egal cu k

INSEREAZA(S,x): modifica multimea S prin introducerea elementului referit de x;

STERGE(S,x): modifica multimea S prin eliminarea elementului referit de x;

MINIM(S) : returneaza elementul din multimea S cu cea mai mica valoare a cheii;

MAXIM(S): returneaza elementul din multimea S cu cea mai mare valoare a cheii;

SUCCESOR(S,x):returneaza elementul imdiat urmator mai mare decat x ( se presupune ca multimea este total ordonata ) sau NULL daca nu exista un succesor pentru x;

PREDECESOR(S,x): returneaza elementul imdiat anterior mai mic decat x ( se presupune ca multimea este total ordonata ) sau NULL daca nu exista un predecesor pentru x;

Structuri de date elementare

Structurile de date elementare sunt structurile de date de tip stiva, coada, lista si arbori cu radacina.

Stive

O stiva este o multime dinamica de tip LIFO ( Last Input First Output ) la care operatia INSEREAZA se mai numeste si PUSH ( PUNE ), iar operatia STERGE se mai numeste si POP ( SCOATE ). O stiva este caracterizata de ultimul element introdus care se numeste varful stivei si de dimensiunea stivei n. Daca varf[S]=0 atunci stiva este goala ( nu se mai pot efectua operatii de stergere ), iar daca varf[S]=n atunci stiva este plina ( nu se mai pot esecuta operatii de punere in stiva ). Stiva poate fi implementata printr-un tablou S[1 . n] sau cu ajutorul obiectelor alocate dinamic, obiecte ce contin un camp cu o referinta spre obiectul anterior si cel putin un camp ce contine informatia utila. In acest caz primul element al stivei va contine o referinta spre NULL, iar dimensiunea maxima a stivei depinde de cantitatea de memorie disponibila.

Pentru implementarea stivei este necesara o procedura care sa verifice daca stiva este vida, STIVA_VIDA(S), o procedura de punere in stiva, PUSH( S,x) si o procedura de scoatere din stiva, POP(S), proceduri al caror pseudocod se arata mai jos:

STIVA_VIDA(S)

1:DACA varf[S]=0 ATUNCI

2: returneaza ADEVARAT

3:ALTFEL

4: returneaza FALS

PUSH(S,x)

1:DACA varf[S]+1>n ATUNCI

2: EROARE "stiva este plina"

3:ALTFEL

4: varf[S] varf[S]+1

5: S[varf[S]+1] x

POP(S)

1:DACA STIVA_VIDA(S) ATUNCI

2: EROARE "stiva vida"

3:ALTFEL

4: returneaza S[varf[S]]

5: varf[S] varf[s]-1

Reprezentare grafica:

Cozi

Cozile sunt structuri de date elementare de tip FIFO ( First Input First Output ) foarte asemanatoare cu stivele, singura diferenta fiind faptul ca primul element introdus este primul element extras. Pentru aceasta primul element introdus are un statut special, se numeste cap si indica spre urmatorul element. Elementul curent este de fapt coada si indica spre NULL.

Reprezentare grafica:

Liste

Listele sunt structuri de date elementare ale caror elemente sunt obiecte care contin unul sau doua campuri referinte si cel putin un camp cu informatia utila. Atunci cand exista doua campuri de referinte lista este dublu inlantuita ( o referinta indica spre urmatorul element, iar celalata referinta spre elementul anterior ), iar cand are numai un camp referinta lista este simplu inlantuita.

Pentru manevrarea facila a operatiilor de la capetele unei liste se poate folosi un element special numit santinela. Santinela este un element special care are doua campuri referinta, unul inidicand spre primul element al listei, iar altul spre ultimul element al listei, adresa santinelei fiind NULL.

Reprezentare grafica fara santinela:

Reprezentare grafica cu santinela:

Inserarea intr-o lista inlantuita fara santinela:

LISTA_INSERARE(L,x)

1:next[x] cap[L]

2:DACA cap[L]<>NULL ATUNCI

prec[cap[L]] x

4:cap[L] x

5:prec[x] NULL

Stergerea unui element din lista fara santinela:

LISTA_STERGE (L,x)

1:DACA prec[x]<>NULL ATUNCI

2: next[prec[x]] next[x]

3:ALTFEL

cap[L] next[x]

5:DACA next[x]<>NULL ATUNCI

prec[next[x]] prec[x]

Cautarea intr-o lista inlantuita fara santinela:

LISTA_CAUTA(L,k)

1:x cap[L]

2:CAT TIMP( x<>NULL SI cheie[x]<>k)

4:returneaza x

Operatiile de mai sus in listele cu santinela:

LISTA_STERGE_1(L,x)

1:next[prec[x]] next[x]

2:prec[next[x] prec[x]

LISTA_INSEREAZA_1(L,x)

1:next[x] next[santinela[L]]

2:prec[next[santinela[L]]] x

3:next[santinela[L]] x

4:prec[x] santinela[L]

LISTA_CAUTA_1(L,k)

1:x next[santinela[L]]

2:CAT TIMP(x<>NULL SI cheie[x]<>k)

4:reurneaza x

Arbori binari

Un arbore binar cu radacina este o structura de date elementara, asemanatoare listei dublu inlantuita, in care campurile referinta indica spre descendentul din stanga si spre descendentul din dreapta, existand un element special numit radacina de la care incepe ramificatia.

Reprezentarea grafica a arborilor binari:

Orice nod poate avea un descendent ( fiu) stanga si un descendent ( fiu ) dreapta. Nodurile care nu au descendenti se numesc noduri terminale. Un arbore binar poate fi definit dupa cum urmeaza: un arbore binar T este o structura de date definita pe o miltime finita de noduri care:

a)      nu contine nici un nod sau

b)      este constituita din trei multimi de noduri disjuncte:un nod radacina, un arbore binar numit subarborele stang al sau si un arbore binar numit subarborele drept al lui T.

Un nod fara nici un descendent se numeste nod extern sau frunza, iar un nod care nu este frunza se numeste nod intern. Numarul descendentilor unui nod x dintr-un arbore cu radacina T se numeste gradul lui x. Lungimea drumului de la radacina la un nod x se numeste adancimea lui x in T. cea mai mareadancime a unui nod constitue inaltimea lui T. Un arbore binar complet este un arbore binar care are pe ultimul nivel numai noduri frunza. Arborii binari pot fi parcursi ( vizitati ) in trei moduri diferite si anume:

a)      in inordine (SRD): se viziteaza mai intai subarborii din stanga apoi radacina si la urma subarborii din dreapta;

b)      in preordine ( RSD): se viziteaza mai intai radacina apoi subarborii din stanga si la urma subarborii din dreapta;

c)      in postordine (SDR): se viziteaza mai intai subarborii din stanga, apoi cei din drepta si la urma radacina.