.specificatii Software Orientate Obiect

I. Introducere

Calculatorul, devenit o trăsătură principală a erei contemporane, tinde să înlocuiască într-o tot mai mare măsură efortul uman, mental și indirect fizic, prin rapiditatea calculelor, programarea sistemelor și alte facilități: simulări, prelucrări grafice și audio etc. Domeniul informatic a evoluat continuu de la aparitia sa si pana in prezent: de la calcule elementare si simple automatizari ale proceselor tehnice pana la controlul activitatilor complexe (serviciul telefonic, traficul aerian etc.) tehnologia informatica a cunoscut profunde transformari.

Un program pentru o aplicatie de mici dimensiuni si complexitate redusa nu este neaparat slab calitativ. Complexitatea excesiva nu este de dorit pentru un sistem software; referindu-ne insa la sisteme de “putere industriala”, capabile sa gestioneze un numar mare de operatii in timp real, pentru care corectitudinea si precizia prezinta mare insemnatate, complexitatea este inerenta; ea trebuie “tinuta in frau”. Problema prezinta interes pentru diverse cazuri: atat in situatia mai mult sau mai putin comica in care primesti o nota de plata cu prea multe zerouri (ceea ce se poate rezolva), dar mai ales in domeniul aplicatiilor in timp real, unde consecintele pot fi dramatice (exemplu: computerele introduc acuratete si confort in mijloacele de transport care le folosesc. Ele tind din ce in ce mai mult sa capete un rol activ in managementul diverselor situatii. In acelasi timp caderea computerului inseamna scaparea masinii de sub control, cu consecinte grave).

Ce este un sistem software corect?

Un raspuns simplu ar fi ca este acela care face ce ar trebui sa faca. Ca sa intelegem ce ar trebui sa faca avem nevoie de o descriere a obiectivelor sale, pe care informal le numim specificatii. Deci un program este corect daca respecta specificatiile sale.

Dar ce reprezinta concret aceasta notiune? “O specificatie a cerintelor este un document continand cerintele; o specificatie de proiectare este un document continand informatii referitoare la partea de proiectare; o specificatie de test este un document continand procesul de test (Alan Davis – Software Requirements)”. In general este o declaratie de acord intre producatorul unui serviciu si consumatorul acelui serviciu, intre un programator si un utilizator (Carlo Ghezzi – Fundamentals of Software Engineering).

Se poate vorbi de un trio de termeni: cerinte, specificatii si programe.

Cerintele se refera numai la ceea ce se intampla in mediul inconjurator. Astfel, clientul este interesat ca obiectul de activitate programat sa functioneze corect, si nu are cunostinta de mecanismul interior al masinii de calcul. De cealalta parte, programele se refera doar la comportamentul interior al masinii.

Intre cele doua notiuni se vor situa specificatiile, ca fiind cate putin din fiecare si formand o punte intre cele doua. Pentru a le intelege mai bine, trebuie a ne imaginam raspunsul la intrebarea: ce comportament al interfetei de specificatii va produce efectele dorite de client? De aici deducem ca specificatiile sunt derivate din cerintele clientului. Tot astfel, se pune problema: ce comportament trebuie sa produca un program la nivelul interfetei de specificatii?

Construirea de specificatii are un caracter subiectiv, depinzand de viziunea abstracta sau concreta a celui care face acest lucru. Cert este ca o specificatie nu poate fi complet abstracta, deoarece sensul sau final este obligatoriu concret, implicand lumea reala, si trebuie inteles de utilizator.

De ce specificatii?

Specificatiile pot servi mai multor scopuri:

sunt folosite in documentatia programului; ele descriu abstractiile luate in considerare;

ajuta la intelegerea mai buna a cerintelor si a proprietatilor si functionalitatilor sistemului de proiectat;

reprezinta un fel de contract intre proiectantul unui program si client; definesc conditiile in care serviciile unui modul functioneaza corect si ce rezultat intoarce apelul acestor servicii;

ajuta nu doar proiectantii ci si programatorii si pe cei care intretin softul; ele constituie o sursa pentru fazele de implementare, testare, evaluare si documentare reducand efortul de programare.

Scrierea de specificatii nu este o faza separata in constructia software-ului; specificatiile trebuie adaptate de fiecare data cand se fac modificari, in oricare din fazele ciclului de viata, in special in faza de intretinere, tinand cont si de evolutia sistemului software. Fiecare dezvoltator de sisteme are o metoda aparte de descriere a specificatiilor de sistem: proza, diagrame, metodologie etc.

In perioada de inceput a tehnologiei computerelor metodele formale se axau pe intelegerea programelor (1970). In urmatorii 10 ani verificarea programelor si verificarea axiomatica au fost la moda, iar scopul era ca programul sa fie in concordanta cu o descriere formala a specificatiilor sale. Au urmat anii '80, in care interesa abilitatea de a produce programe corecte, care sa corespunda descrierii formale a specificatiilor lor.

De ce specificatii orientate obiect?

Sarcina fundamentala a unei echipe de dezvoltare software este aceea de a crea iluzia simplitatii, pentru a proteja utilizatorul de vasta lui complexitate externa. Tratarea acestei complexitati se poate face urmand trei pasi: descompunere, abstractizare, ierarhizare.

Ca modele de organizare a programelor s-au evidentiat diferite stiluri (paradigme ale programarii), in functie de tipurile de abstractii considerate: orientate obiect (clase si obiecte), orientate pe proceduri (algoritmi), logic-orientate, orientate pe reguli si orientate pe constrangeri. In literatura de specialitate pot fi gasite numeroase tehnici de dezvoltare a softului de calitate: proiectarea sistemelor prin metoda Jackson, proiectarea structurata (Yourdon-Constantine), analiza structurata (De Marco) etc. Toate acestea au insa un lucru in comun: programele sunt structurate in jurul datelor, si nu al functiilor, (acestea din urma nefiind partea cea mai stabila a sistemelor). Astfel rezulta sisteme cu un inalt grad de continuitate si reutilizabilitate.

Proiectarea orientata-obiect e diferita fundamental de tehnicile traditionale structurate; are un mod diferit de gandire asupra decompozitiei si se preteaza la arhitecturi software mult mai mari. Aceasta metoda permite in acelasi timp construirea unui soft de calitate, bazat pe corectitudine si performanta.

Ca istoric al abordarii OO, mentionam doua etape ale acestei metodologii:

limbaje bazate pe obiecte (ex: Ada). Se realizeaza organizarea obiectelor in clase; acestea definesc structura si comportarea unei intregi familii de obiecte;

limbaje orientate obiect (ex: Smalltalk, C++); se obtine o clasificare a claselor in ierarhii de clase cu mostenire, s-a dezvoltat abordarea total OO si tehnicile de programare orientate-obiectual

Mod de solutionare a problemei

Etapa de specificare de sistem din elaborarea unui produs program cuprinde o documentație detaliată despre tipurile de date folosite și descrierea pas cu pas a proceselor. Iesirea se constituie într-un document numit specificatii de sistem, care trebuie să aibă o descriere corecta si din care sa poata rezulta programul initial. Descrierea datelor în cadrul specificatiilor de program va fi comunicata specialistilor in managementul datelor pentru a putea fi verificata si integrata cu celelalte structuri de date.

Metodologia este foarte importanta. Specificatiile de program pot consta in intregime din diagrame sau liste formale asau se poate alege o metodologie adecvata.

Documentul de iesire trebuie sa reflecte doua activitati: analiza modelului si evaluarea pachetului de programe. Trebuie verificat daca in timpul analizei detaliate daca modelul corespunde cerintelor initiale sau daca acestea au fost schimbate intre timp; va trebui calculat impactul pe care il au asupra utilizatorului final. Daca problema este serioasa vor trebui revazute cerintele ori se va acorda o atentie mai mare etapelor de initiere si de definire.

Obiectiv

Lucrarea de fata prezinta intr-o abordare orientata obiect modul de constructie a specificatiilor pentru un sistem software, aratand ca un program si descrierea sa formala sunt echivalente. Ca exemple sunt date cateva metode clasice.

Structura

Materialul este organizat in continuare dupa cum urmeaza: capitolul 2 prezinta detaliat metodologia orientata obiect sub cele trei aspecte (analiza, proiectare, implementare).

In capitolul 3 este descrisă metoda de specificare formală matematică, denumită și specificații algebrice, împreună cu avantajele si limitele ce o caracterizeaza; acestea sunt insotite de exemple concrete pe structuri de date.

Capitolul 4 prezintă modalitatea de specificare a algoritmilor de rezolvare a problemelor de inteligență artificială în timp real, un domeniu de mare actualitate și cu implicații serioase în realitate.

Lucrarea este însoțită de un produs software pentru dezvoltarea de specificații orientate obiect și asistare a procesului de obținere a specificațiilor. Caracteristicile sale sunt descrise in capitolul 5.

În final, în capitolul 6 am enunțat câteva concluzii cu privire la cele prezentate.

II. Particularități de analiză, proiectare și programare orientată obiect

Preliminarii

Dezvoltarea sistemelor orientate pe obiecte (OO) bazate pe modelul calculațional orientat obiectual a cunoscut o amploare deosebită in anii '90. Alegerea unui model calculațional pentru rezolvarea unei probleme a domeniului aplicației are implicații asupra întregului lanț de dezvoltare software, de la decompoziția problemei până la soluția acesteia. Utilizarea modelului OO bazat pe conceptele de obiect și clasă și pe un set de paradigme – abstracția datelor și comunicarea prin mesaje, încapsularea, polimorfismul, moștenirea – a determinat dezvoltarea unor metode si tehnici adecvate de specificare, analiză, proiectare, implementare și validare a produselor software.

Fără îndoială ca metoda de proiectare OO este fundamental diferită de tradiționalele concepte ale proiectării structurate: impune un mod diferit de gândire asupra decompoziției și produce arhitecturi software care depășesc vizibil domeniul de competență al proiectării structurate. În cadrul modelului calculațional bazat pe paradigma algoritmică, având procedura ca principala abstracție, dezvoltarea sistemică este văzută prin intermediul entităților proces, flux de date și de control, integrate prin intermediul relației "program = structuri de date + algoritmi" (Wirth). În comparație cu acesta, modelul calculational OO este echivalent din punct de vedere al posibilităților de calcul, dar superior în ceea ce privește reutilizarea, prototipizarea rapidă si fidelitatea de modelare a domeniului aplicației, criterii cu pondere deosebită în evaluarea calităților și performanțelor software actuale.

Tendinta curenta a proceselor de reinginerizare si sistemele client/server incurajeaza de asemenea multi dezvoltatori sa priveasca spre conceptul OO in vederea gasirii unui instrument de dezvoltare a aplicatiilor. Si aceasta datorita faptului ca un obiect furnizeaza o abordare mult mai buna pentru crearea bazei sistemelor decat cea a solutiei structurate.

Premisa modelului OO este ca universul datelor oricarei aplicatii il constituie o colectie de obiecte instante ale unor clase. Arhitectura sistemelor obiectuale este bazata pe clase, obiecte si pe interactiuni intre acestea. Intr-o arhitectura orientata obiectual, controlul este distribuit intre elementele sistemului. Activarea obiectului se face prin intermediul mesajelor emise de agentii externi ai sistemului (alte obiecte), sau de catre agentii interni, obiecte ale sistemului.

Ce este un de fapt un obiect? Dar o clasa?

Un obiect modeleaza o entitate din lumea reala sau imaginara, care se manifesta printr-un comportament specific si detine un rol precis in domeniul problemei noastre. Obiectele cu proprietati comune si cu un comportament similar pot fi grupate in cadrul uentii interni, obiecte ale sistemului.

Ce este un de fapt un obiect? Dar o clasa?

Un obiect modeleaza o entitate din lumea reala sau imaginara, care se manifesta printr-un comportament specific si detine un rol precis in domeniul problemei noastre. Obiectele cu proprietati comune si cu un comportament similar pot fi grupate in cadrul unei clase de obiecte. Cele doua notiuni sunt strans legate logic, deoarece nu putem vorbi de un obiect fara sa avem in vedere clasa sa. In timp ce un obiect este o entitate concreta care exista in timp si spatiu, o clasa reprezinta o abstractie, esenta acelui obiect.

Obiectele sunt ceva relativ simplu de identificat, deoarece ele corespund cu substantivele dintr-un text, documente de specificatii ale cerintelor sau mesaje vorbite. Gasirea obiectelor si a comportamentului lor constituie obiectivele principale ale analizei si proiectarii orientate spre obiecte.

O definitie pe drept acceptata este cea introdusa de G. Booch [Booc91], unde se considera un obiect ca fiind caracterizat prin trei elemente:

stare. Corespunde memoriei obiectului: contine setul de date cu informatii referitoare la acesta. Este caracterizata prin atribute, care au nume si valori asociate (in C++ acestea se numesc date membru).

comportament. Semnifica modalitatea de actiune si reactiune a obiectului la mesaje provenite din exterior, care determina modificarea starii sale. Contine serviciile (functiile, operatiile) pe care le ofera clientilor sai, acestea (functiile) formand interfata obiectului (in C++ functii membru). O partitionare posibila a setului mesajelor asociate unui obiect este urmatoarea:

constructori – mesaje de creare si eventual initializare a obiectului;

destructor – mesaj de distrugere a obiectului (eliberarea resurselor ocupate);

modificatori – mesaje prin care se modifica starea interna a obiectului (operatii de scriere);

selectori – mesaje de testare a starii obiectului (operatii de citire);

iteratori – mesaje asociate cu obiecte cu structura complexa, prin care se returneaza partile sale componente, intr-o anumita secventa.

identitate. Este o proprietate a obiectului (instantiat dintr-o clasa) care il distinge de alte obiecte. Identitatea trebuie sa fie un concept extern obiectului, care sa îi asigure individualitatea acestuia (un fel de ID). De subliniat ca schimbarea starii obiectului nu influenteaza identitatea acestuia, dealtfel putand exista doua obiecte diferite cu aceeasi stare.

Un obiect luat de unul singur este neimportant; obiectele contribuie la comportamentul sistemului colaborand intre ele. Doua tipuri de relatii prezinta interes [Booc91]:

relatii de folosire, prin care un obiect poate juca unul din cele trei roluri:

actor (obiect activ, client), care opereaza asupra altor obiecte prin trimiterea de mesaje catre acestea;

server, care primeste mesaje si ofera serviciile sale altor obiecte;

agent, un obiect care joaca fiecare din rolurile anterioare.

relatii de continere, prin care unele atribute ale unui obiect pot fi ele insele obiecte.

Este posibila gruparea obiectelor cu comportament similar. Pentru aceasta se utilizeaza conceptul de clasa, privita ca un sablon in generarea obiectelor cu structura si comportament identice. Daca obiectele sunt entitati dinamice, care se creeaza si se distrug frecvent, clasele sunt entitati statice. Intre clase se pot stabili urmatoarele tipuri de asociatii:

de mostenire (de tipul “KIND-OF”). Este deosebit de utila in dezvoltarea sistemelor orientate obiectual, stand la baza exprimarii unor concepte esentiale pentru ingineria software OO, ca: generalizare/specializare, extensibilitate, reutilizare a codului;

de asociere in utilizare (client-server), cand o functie de interfata contine un parametru care ia valori intr-un domeniu reprezentat de alta clasa;

de continere (“PART-OF”). Se realizeaza intre doua clase, intreg si parte si este specificata in componenta structurala a clasei intreg.

Relatia intre doua clase este caracterizata si prin multiplicitatea de asociere, care specifica numarul instantelor unei clase asociate cu o instanta a celeilalte clase. Din punct de vedere conceptual, sunt importante asocierile de multiplicitate: 1:1 (“one-to-one”), 1:m (“one-to-many”) si m:n (“many-to-many”).

Paradigme OO

Exista câteva concepte caracteristice modelului OO, care determina modul de gandire si stilul de programare OO (paradigme ale modelului OO):

abstractizarea este una din metodele fundamentale de tratare a complexității. Ea separa caracteristicile esențiale ale unui obiect, care îl deosebesc de celelalte obiecte, de cele neesențiale. Abstracția se concentrează asupra vederii din exterior a obiectelor, ajutând la separarea comportării lor esențiale de detaliile de implementare.

Spre deosebire de modelul procedural care realizează abstracția funcțiilor, cel OO realizează abstracția datelor, rezultând astfel clase de obiecte. Prin intermediul acestora se definesc atributele (structura tipului) și metodele de interfață. Valorile atributelor obiectelor pot fi accesate din exterior )modificate sau observate) numai prin utilizarea operațiilor permise, specificate în interfață.

încapsularea, sau ascunderea informației, se referă la apsectul de implementare al abstracțiilor prin intermediul claselor. Prin încapsulare se interzice clientilor obiectelor instanțiate să le vadă detaliile de implementare.

polimorfismul se definește ca fiind posibilitatea unei valori de a avea mai multe tipuri, pentru a putea fi utilizată în mai multe contexte în care se cer tipuri diferite.

Un exemplu de polimorfism se referă la posibilitatea folosirii unei singure funcții (nume, funcționalitate, cod) asupra unui set de tipuri, dacă un argument al său determină tipul corespunzător fiecărui apel al funcției. Mai mult, se folosește și polimorfismul de tip supraîncărcare (overloading), care implică utilizarea unor funcții cu același nume, dar cu parametrii diferiți și cod diferit. Decizia de selecție a funcției active depinde de parametrii de apel.

Principalele avantaje ale sistemelor polimofice rezidă în: partajarea comportării, posibilitatea de definire a operațiilor abstracte asociate tipurilor, flexibilitate.

moștenirea este procesul prin care un obiect preia prototipul altui obiect, cu posibilitatea adăugarii de noi atribute și noi funcții sau redefinirea celor vechi. Prin intermediul moștenirii se pot exprima relații între clase deosebit de utile în programare, cum ar fi: clasificarea, specializarea, generalizarea.

În terminologia OO, clasa din care se moștenește se numește clasă de bază sau superclasă, iar clasa care moștenește este numită clasă derivată sau subclasă. Despre clasa derivată spunem că este o specializare a clasei de bază, aceasta fiind o generalizare a clasei derivate.

Moștenirea claselor poate fi simplă (când fiecare clasă derivată are o singură clasă de bază) sau multiplă (când are mai multe clase de bază).

Construcția sistemelor software

Realizarea produselor software a cunoscut o intensă evoluție de-a lungul timpului. De la primele sale manifestări, sub forma scrierii de cod pentru implementarea unor operații banale, s-a ajuns astăzi, ca urmare a cerințelor impuse de creșterea complexității sistemelor, tendinței de industrializare și standardizare, la metode și tehnici care să permită dezvoltarea rapidă a software-ului cu productivitate mare și satisfacerea concomitentă a unor cerințe tot mai ridicate legate de calitatea produselor software.

Scopul dezvoltatorilor de software este acela de a construi software de înaltă calitate, referindu-ne la programe extinse si complexe. Majoritatea problemelor se ivesc datorită limbajului utilizat, al ustensilelor și mediilor de dezvoltare care promovează dezvoltarea calității software. Tehnologia orientată spre obiecte se află pe direcția cea bună în eliminarea problemelor mai sus menționate.

Calitățile software-ului (numite si criterii de apreciere), se pot impărți in:

• externe

corectitudine, abilitatea sistemului software de a-și îndeplini serviciile definite de specificațiile sale sau în cadrul cerințelor;

robustețe – comportament rezonabil în situații anormale;

extendibilitate – ușurința cu care se adaptează modificărilor cerințelor și specificațiilor;

reutilizabilitate – posibilitatea refolosirii unor module în construirea de software pentru alte aplicații;

eficiență – folosirea optimă a resurselor hardware și a serviciilor sistemului de operare;

• interne

modularitatea – proprietatea softului de a fi divizat în mai multe module autonome, conectate printr-o interfață simplă. Este importantă atât la implementare (program), cât și la proiectare (specificații);

continuitatea – proprietate a softurilor care nu necesită modificări drastice ca urmare a modificării cerințelor (doar câteva module vor fi afectate). Este strâns legata de modularitate. Având în vedere tendința de evoluție a unui software, de a produce noi versiuni, această calitate este deosebit de importantă.

În vederea acestui deziderat au apărut o seamă de tehnologii de dezvoltare a produselor software, bazate pe câteva principii de inginerie și de management [Fabi98]. Ca principii de inginerie se pot preciza:

descrierea clară a problemei – care întâmpină două tipuri de dificultăți majore:

cerințele sunt exprimate de obicei în termenii problemei reale și trebuie translatate în termenii uzuali contextului software;

utilizatorul nu poate preciza complet cerințele sale sau nu poate găsi legătura dintre ele;

definirea și selectarea soluției printr-o clară definire a componentelor;

controlul riguros al relațiilor dintre componente;

În ceea ce privește principiile de management, putem aminti:

planificarea tuturor activităților necesare, din punct de vedere al timpului, bugetului, resurselor și restricțiilor de calitate;

monitorizarea continuă, îmbunătățirea progresivă a planurilor;

definirea clară a structurii, rolurilor, responsabilităților și liniilor de comunicație între persoanele implicate în realizare;

Avem de-a face cu un compromis între calitate, costuri și termenele de realizare. De exemplu, pentru creșterea calității se vor face cheltuieli suplimentare sau este necesar un timp mai mare de realizare a produsului software.

Ciclul de viață OO

Intervalul de timp de la momentul deciziei inițiale de realizare a produsului program până la scoaterea din funcțiune a acestuia sau retragerea lui de pe piață reprezintă ciclul de viață. Acest interval este împărțit în mai multe faze: analiza problemei, proiectarea produsului software, implementarea de cod, testarea, experimentarea și utilizarea acestuia. Încheierea fiecărei faze presupune elaborarea unui document de specificații utilizat în faza următoare.

Modul de grupare a activităților, precum și succesiunea fazelor cinduc la diferite modele de implementare ale ciclului de viață. Un model al ciclului de viață pentru produse software descrie activitatea de realizare a produsului software și fluxul procesului de dezvoltare. În decursul timpului au fost elaborate diferite strategii de implementare a conceptului de ciclu de viață, concretizate în diferite modele. Iată două din cele mai importante:

modelul în cascadă

Inițial a existat ideea că o fază trebuie să fie complet terminată pentru a o începe pe următoarea. Acest principiu a fost abandonat relativ repede și s-a convenit ca o fază să poată începe înainte ca precedenta să fie complet terminată.

Modelul în cascadă a avut un impact uriaș asupra metodelor ingineriei software și a fost repede adoptat. În acest model, intrările fiecărei faze sunt ieșirile alteia. Feed-back-ul este format din erori care se răsfrâng asupra fazei următoare. Erorile se propagă indirect, în plus intervin costurile modificărilor, fapt ce implică necesitatea testării foarte riguroase a fiecărei faze.

Dacă este utilizat în domenii puțin cunoscute se poate lucra mult pentru a acoperi cerințele, uneori găsite prea târziu, situație în care, la nivel conceptual este necesară utilizarea de prototipuri în fazele inițiale sau de strategii euristice, după caz.

Fazele modelului în cascadă necesită un personal cu pregătire diversă (analiști, programatori etc.) și se poate spune că este deci o strategie de implementare aproape istorică.

modelul în spirală

Problemele majore în dezvoltarea produselor software apar, în cele mai multe cazuri, în faza de mentenanță, care în realitate constă în definirea de noi cerințe de specificare, de analiză, de proiectare. Modelul în spirală poate descrie cum un produs se dezvoltă pentru a forma o nouă versiune și cum o nouă versiune se dezvoltă incremental de la un prototip la un produs complet. Modelul propune aceleași etape de realizare, dar fiecare ciclu de dezvoltare începe prin studiul de fezabilitate, apoi continuă cu specificarea cerințelor și analiza, proiectarea și implementarea.

Pe de altă parte, fiecare din etapele amintite anterior se realizează printr-o succesiune de activități:

determinarea obiectivelor etapei, a alternativelor și restricțiilor;

evaluarea alternativelor, identificarea riscurilor și rezolvarea lor;

dezvoltarea și verificarea următorului nivel al produsului;

întocmirea planului următoarei etape, ales pe baza riscurilor.

Atât etapele cât și activitățile lor componente sunt evaluate având drept criteriu de bază costurile implicate.

Modelul în spirală are avantajul că evaluează riscurile oricărei abordări în toate fazele de dezvoltare a produselor software, iar pe baza acestora alege abordarea corectă.

Metode de dezvoltare a aplicațiilor

Metodele de dezvoltare a aplicațiilor informatice reprezintă, în general, seturi de tehnici și proceduri care, aplicate într-o anumită succesiune, au ca rezultat specificarea, generarea si documentarea sistemului. Metodele actuale de dezvoltare a sistemelor și aplicațiilor informatice pot fi împărțite în două categorii, și anume:

metode tradiționale – orientate pe structura datelor, structura funcțională, fluxul datelor;

metode orientate obiect – orientate pe obiecte.

Metodele tradiționale separă modelarea datelor de modelarea funcțiilor și ca urmare, conduc la obținerea de două tipuri structuri distincte: structura datelor și structura de funcțiuni. Elementele structurii funcționale sunt elemente active și au un comportament dinamic, iar structurile de date sunt elemente pasive de date care sunt afectate de funcții. Un sistem dezvoltat utilizând o metodă tradițională este greu de întreținut și dezvoltat.

Spre deosebire, metodele orientate obiect propun modelarea concomitentă a celor două tipuri de structuri, de date și de prelucrări, prin iterarea analizei datelor și comportamentului acestora în sistem, în vederea obținerii unei ierarhii de calse și obiecte care se potrivește cel mai bine cu natura problemei. Orientarea obiect, ca metodă, își propune rezolvarea dificultăților ce apar în dezvoltarea aplicațiilor informatice în cel puțin două momente ale acestiu demers, și anume:

la trecerea descrierii problemei din limbajul specific domeniului de aplicație într-un limbaj formalizat, specific domeniului informatic;

la trecerea din limbajul formal (grafic, textual, mixt) într-un limbaj de programare.

Azi, o serie de limbaje sunt extinse pentru lucrul cu obiecte, cu biblioteci predefinite pentru lucrul cu utilizatori și oferă posibilitatea de a defini noi clase de obiecte; mai mult, instrumentele, mediile, CASE-urile și SGBD-urile sunt orientate obiect.

În prezent există peste 30 de metode de dezvoltare a sistemelor orientate obiect, dintre care unele vor evolua, altele se vor pierde. Dintre acestea cele mai cunoscute sunt:

OOD – Object Oriented Design (G. Booch);

OOSA – Object Oriented System Analysis (Shlaer&Mellor);

OMT – Object Modelling Technique (James Rumbaugh, Michael Blaha, William Premerlani);

OOA – Object Oriented Analysis (Peter Coad, Eduard Yourdon);

HOOD – Hierarchical Object Oriented Design;

OOSE – Object Oriented Software Engineering (Ivar Jacobson).

Fazele procesului de dezvoltare OO

Conceptul de orientare-obiect s-a evidențiat mai întâi la partea de implementare (OOP), prin ușurința cu care puteau fi transpuse în cod datele și funcțiile existente în aplicație, folosindu-ne de clase și obiecte. Deci “programarea orientată-obiect este metoda de implementare în care programele sunt organizate sub forma unor colecții de obiecte ce colaborează între ele, fiecare fiind o instanță a unei clase,fiecare clasă făcând parte la rândul ei dintr-o ierarhie de clase legate prin moștenire [Booc91].” Termenul de realizare OO a fost folosit pentru prima dată de Booch la dezvoltarea de software în limbajul ADA. A urmat apariția la începutul anilor ’80 a limbajului SIMULA, apoi dezvoltarea limbajului SMALLTALK și a altor limbaje bazate pe aceeași filozofie.

Dacă în metodele de programare se pune accentul pe folosirea efectivă a mecanismelor particulare de limbaj, prin contrast, la proiectare (OOD), accentul cade pe structurarea adecvată a sistemului complex. Ce este deci OOD? Este ”o metodă e proiectare ce cuprinde procesul decompoziției și câte o notație pentru descrierea logică și fizică, sub formă statică și dinamică, a modelului de proiectat.” Reiese de aici că OOD folosește modalități diferite pentru expresia modelului logic (structura claselor și obiectelor) și fizic (arhitectura modulelor și proceselor) unui sistem.

Modelul obiect a influențat și fazele mai timpurii ale ciclului e viață al dezvoltării de software, respectiv partea de analiză (OOA), constituindu-se într-un nou mod de gândire și abordare a problemelor utilizând concepte din lumea reală. OOA este deci “o metodă de analiză care tratează cerințele problemei din perspectiva claselor și obiectelor din vocabularul domeniului problemei.”

Cum sunt legate OOA, OOD, și OOP? În esență, rezultatele analizei pot servi ca modele de pornire ale etapei de proiectare; rezultatele proiectării OO pot fi apoi folosite ca schiță pentru implementarea completă a sistemului folosind metodele de programare OO.

Analiza OO

Analiza este faza care îi aduce împreună pe utilizatorii și pe designerii unui sistem, unindu-i printr-un limbaj comun provenit din domeniul problemei. Scopul analizei este acela de a furniza o descriere completă, consistentă și ușor de înțeles a problemei, pentru ambele părți implicate.

Primul pas din cadrul etapei de analiză este determinarea cerințelor utilizatorului sistemului. Se va pune deosebit accent pe înțelegerea materialului problemei și vor fi folosiți experți în domeniu, care cunosc atât medul aplicației reale, cât și noțiuni de ordin informatic. Există anumite tehnici de transpunere a conceptelor din contextul problemei, cu rolul de a constitui un liant semantic între exprimarea necesităților de către utilizator și realizarea cerințelor de către dezvoltatorul aplicației.

Transpunerea conceptelor se concentreată pe relațiile structurale de lungă durată din cadrul sistemului. Acestea au o natură statică, astfel încât nu prezintă componente comportamentale atunci când reacționează la stimuli externi. Astfel, pentru a veni în completarea acestor tehnici, sunt construite liste eveniment-răspuns și rezumate acestea descriind comportamentul dinamic și modul în care reacționează sistemul la evenimente externe.

Răspunsurile sunt reacții la evenimente. Unui eveniment i se pot asocia o listă de răspunsuri. Iată câteva exemple:

un interval de timp s-a epuizat un obiect este eliberat din memoria cache;

este acționată o pompă de benzină este pornit motorul pompei;

este eliberat mânerul pompei;

contorul pompei este adus la zero.

Rezumatele unesc aplicarea conceptelor și listele eveniment-răspuns pentru a ilustra utilizatorului conceptele sistemului.

Jacobson utilizează o serie de tehnici foarte asemănătoare cu listele eveniment-răspuns și rezumatele. El introduce noțiunea de model al cerințelor în care se definește întreaga funcționalitate necesară sistemului. Elementul central al metodei sale îl constituie modelul use case, acesta servind ca bază atât procesului de construcție cât și celui de testare. Cu ajutorul acestui sistem se poate controla o bună parte a dezvoltării sistemului. În cadrul acestui model sunt utilizați actori și cazuri de utilizare (de uz). Un actor reprezintă o entitate ce interacționează cu sistemul în timp ce un caz de uz descrie ce trebuie efectuat de către sistem. Acestea sunt concepte utile, care ajută la înțelegerea a ceea ce se întâmplă în cadrul sistemului. Deoarece actorii se situează în afara sistemului, aceștia nu sunt descriși în detaliu. Atunci când un utilizator accesează sistemul, acesta va dezvolta un lanț de tranzacții de-a lungul unui dialog cu sistemul. Un astfel de lanț îl numim caz de uz. Mulțimea tuturor cazurilor din interiorul unui sistem se constituie în funcționalitatea sistemului, așa cum este ea percepută de utilizator.

Indiferent de metodă, rezultatele etapei de determinare a cerințelor vor trebui să se concretizeze într-un document de specificare a cerințelor, ce va servi ca bază de plecare etapelor ulterioare.

În timpul analizei, ca și în primele stadii ale proiectării, dezvoltatorul de software are două sarcini principale [Booc91]:

să identifice clasele și obiectele ce formează vocabularul domeniului problemei;

să elaboreze structurile prin care seturile de obiecte să comunice pentru a furniza comportamentul ce satisface cerințele problemei.

Booch numește aceste clase și obiecte abstracțiile cheie ale problemei, iar structurile asociative – mecanisme de implementare.

În timpul fazei de dezvoltare, designerul se va concentra asupra vederii din exterior a acestor abstracții cheie și mecanisme. Această viziune reprezintă cadrul logic al sistemului. Către sfârșitul etapei de proiectare și începutul implementării, accentul cade pe vederea interioară a acestor abstracții cheie și mecanisme, implicând și repezentarea fizică.

Cum identificăm clasele și obiectele ce vor constitui structura fundamentală a sistemului? O primă soluție este aceea că ele delimitează cadrul problemei noastre: trebuie să evidențieze obiectele din sistem, care sunt relevante pentru aplicația noastră și să evite lucrurile din afara sistemului, care sunt superflue. Cea mai potrivită alegere depinde, desigur, de scopul aplicației și de granularitatea informației de manipulat.

Strâns legate de metodele de analiză OO sunt cele de analiză a domeniului. În timp ce analiza OO pune accentul pe problema existentă la un moment dat, analiza domeniului caută să identifice clasele și obiectele comune tuturor aplicațiilor dintr-un domeniu dat (ca de exemplu: compilatoare sau software de conturi). Dacă te afli în mijlocul unui proces software și cauți idei pentru abstracții cheie care există deja, analiza domeniului te poate ajuta îndrumându-te către acelea care și-au dovedit utilitatea în alte sisteme asemănătoare.

Este în general acceptat faptul că lumea reală poate fi aproximată utilizând trei modele diferite. Primul dintre acestea este modelul structural sau al obiectelor, acesta descriind obiectele din cadrul sistemului și relațiile structurale dintre acestea. Al doilea model este modelul dinamic, responsabil cu descrierea acelor aspecte ale sistemului care se modifică în timp. Ultimul dintre modele este cel funcțional, sau al proceselor, acesta descriind transformările valorilor datelor și calculele sistemului. Fiecare model poate fi studiat independent de celelalte două, acestea urmând a fi combinate în vederea trecerii la faza de proiectare a sistemului.

Pentru exemplificare, menționăm dintre etapele modelului OMT:

modelul obiectelor:

identificarea claselor de obiecte și atributele lor;

identificarea relațiilor (asocieri) dintre clase;

descoperirea relațiilor de generalizare;

crearea unui dicționar de date;

modelul dinamic:

interacțiuni temporare dintre obiecte;

stimularea obiectelor și răspunsurile acestora;

traducerea evenimentelor în operațiile obiect;

modelul funcțional:

dependențe funcționale ale valorilor;

calculul obiectelor;

fiecare proces este implementat de către o metodă a unui singur obiect.

Proiectarea OO

În cadrul etapei de proiectare se pregătește cadrul arhitectural în vederea implementării. În atenția proiectantului se află două mari obiective:

proiectarea sistemului;

proiectarea obiectelor.

Proiectarea sistemului este etapa în care se determină arhitectura hardware în concordanță cu tipul problemei enunțate. În aceatsă etapă se va stabili și structura globală a sistemului. Deoarece majoritatea problemelor sunt prea complexe sau prea mari pentru a fi rezolvate într-o singură abordare, vom partaja sistemul într-o serie de subsisteme independente. Fiecare subsistem trebuie însă să prezinte o interfață cu celelalte subsisteme, chiar dacă fiecare subsistem se va proiecta independent.

Etapa de proiectare a obiectelor nu este altceva decât o elaborare a rezultatului modelului obiectelor. Aici se vor da definițiile complete ale claselor și relațiilor dintre ele. Algoritmii care vor implementa operațiile asupra obiectelor trebuie să fie proiectați astfel încât să asigure accesul optim la datele implicate în cadrul lor.

Majoritatea problemelor din viața reală sunt atât de complexe încât nu este posibil să le ezolvăm ca pe un sistem monolitic. Unele probleme pot produce câteva sute de clase în faza de analiză. Creierul uman nu este capabil să rețină toate aceste informații la un moment dat. S-a estimat că oamenii pot reține informații doar despre șapte entități simultan.

Vom decide să despărțim un sistem în subsisteme separate. Subsistemele, în dezvoltarea OO suntgrupuri de clase înrudite, fiecare constituind o entitate având proprietăți (atribute) cât și comportament (operații). Subsistemele interacționează unele cu altele. De exemplu este posibil ca un subsistem să folosească serviciile unui alt subsistem. În acest mod am obținut un grad de cuplare între subsisteme. O proiectare bună a sistemelor va produce subsisteme care au o puternică cuplare internă și o slabă cuplare externă, cu alte subsisteme.

Cu cât potențialele subsisteme sunt mai repede descoperite, cu atât mai bine. Tehnica de aplicare a conceptelor permite proiectantului să le determine dintr-o etapă incipientă. Conceptul cheie va corespunde, de obicei, sistemului principal, în timp ce conceptele mai puțin generale vor corespunde subsistemelor. Fiecare concept mai puțin general poate fi, la rândul lui, analizat ca un concept cheie și descompus în subsisteme mai simple. Avantajele acestei abordări sunt:

fiecare potențial subsistem poate fi analizat, proiectat și testat în mod independent;

produsele care rezultă din fazele de analiză și de proiectare ale unui subsistem dat pot fi refolosite în alte subsisteme dacă situația o cere;

interfețele între subsisteme pot fi ușor descoperite;

utilizatorii înțeleg domeniul de acțiune al potențialelor subsisteme.

Inginerii software nu au fost instruiți să proiecteze în ideea schimbării, în ciuda faptului că aplicațiile software de succes trebuie adaptate permanent noilor nevoi. Cunoscând posibilele surse ce impun operarea schimbărilor aplicațiilor, putem lua măsuri pentru producerea sistemelor software care pot fi rapid adaptate la o piață în permanentă schimbare. Este important să realizăm că noi nu proiectăm un program, ci o familie de programe. Aceste familii de programe au multe în comun, dar diferă și printr-un număr de aspecte, cum ar fi:

rulează pe platforme hardware diferite;

produc rezultate în formate de ieșire diferite;

utilizează diferiți algoritmi, dependenți de resursele disponibile.

Odată ce subsistemele au fost fondate, următorul pas este alocarea fiecărui subsistem a unei unități funcționale; acesta poate fi un procesor hardware, software sau unul de uz general. Aplicațiile în care informația este distribuită printre diverse locații va fi implementată de câteva unități funcționale. De exemplu, aplicația client-server folosește un singur dispozitiv de stocat informații (serverul) în timp ce alte dispozitive conțin subsisteme ce accesează aceste informații (clienții). Fiecare client poate juca un rol important în sistem. Pentru reprezentarea unităților funcționale trebuie străbătuți următorii pași:

estimarea nevoilor de performanță;

determinarea unităților funcționale care implementează fiecare sistem;

determinarea conexiunii fizice a unităților funcționale rezultate.

Alegerea unei unități funcționale depinde de aplicație. Unele programe grafice implementează algoritmi tridimensionali de transformare genetică în dispozitive hardware, pentru a îmbunătăți execuția. Alte aplicații produc o rezervă de date într-o stație de lucru locală, în acest fel prevenindu-se nevoia de a accesa datele într-un depozit premanent, mai lent.

Unele aplicații au nevoie stringentă de performanță. Aceste aplicații vor trebui să acceseze și să modernizeze resursele critice, fiind importantă alegerea unităților funcționale care vor rezolva constrângerile de performanță impuse. Unitățile ar trebui să fie fiabile. În unele cazuri este de dorit să creăm o copie a unității principale, care poate prelua îndatoririle acesteia, în eventualitatea unei funcționări anormale. Utilizarea unităților principale împreună cu copiile lor este deosebit de importantă în aplicațiile distribuite.

Unitățile funcționale pot fi cuplate mai mult sau mai puțin. Aplicațiile distribuite utilizează una sau mai multe unități slab cuplate, fiecare servind unui scop anume. Unitățile pot comunica prin diferite căi:

transfer de date;

transfer de mesaje;

apeluri de proceduri la distanță.

Un alt pas important este alegerea și gestiunea depozitelor de date. Un depozit de date este o entitate pasivă care stochează date. Comunicarea subsistemelor prin interfețe se poate efectua prin mai multe metode, de exemplu prin fișiere, sisteme de baze de date relaționale (RDBMS) sau sisteme de baze de date orientate spre obiecte (ODBMS). Bazele de date orientate spre obiecte au avantajul că suportă cele mai importante trăsături moștenite din paradigma orientării spre obiecte, cum ar fi agregarea, moștenirea și încapsularea. Nu există nici o nepotrivire între obiecte și reprezentările bazelor de date corespunzătoare. Un obiect poate fi depozitat pe disc fără să se cunoască starea sa internă și poate fi preluat de pe disc într-o manieră la fel de transparentă. Sistemele ODBMS modelează obiectele în mod natural și folosirea lor este recomandată. Totuși, anumite subsisteme trebuie să realizeze ionterfața cu alte subsisteme care au fost scrise folosind limbaje neorientate spre obiecte și sisteme de baze de date. Aceste subsisteme nu înșeleg obiectele, astfel că interfețele lor sunt implementate de obicei ca fișiere ASCII sau tabele RDBMS.

Sistemele RDBMS au o largă utilizare și acceptare, fiind folosite cu succes în rezolvarea unei clase de probleme pentru aplicații administrative. În particular, ele sunt folositoare pentru rezolvarea problemelor unde obiectele au o structură relativ simplă și unde tranzacțiile sunt de scurtă durată, dar ele sunt nepotrivite pentru problemele în care sunt create și manevrate obiecte complexe. În aceste cazuri, sistemele ODBMS sunt mai potrivite, și au început să-și găseacă utilizare în următoarele domenii:

Proiectarea Asistată pe Calculator (CAD);

Sisteme de planificare financiară;

Sisteme de informatizare a birourilor (OIS);

Aplicații CASE;

Aplicații multimedia.

O serie de sisteme ODBMS comerciale sunt disponibile și își găsesc, încetul cu încetul, drum sper aplicațiile vitale. Ar trebui să fie considerate o alternativă serioasă a sistemelor RDBMS, în special dacă datele complexe au nevoie de modelare sau dacă aplicația este nouă.

Totuși, nu este înțelept să se neglijeze sistemele RDBMS de vreme ce baza utilizatorului pentru aplicațiile care folosesc tehnologia bazelor de date relaționale este atât de mare.

Determinarea arhitecturii sistemului. Există un număr de prototipuri de structuri arhitecturale în care se încadrează majoritatea problemelor din viața reală. Identificarea structurii poate fi utilă în găsirea componentelor reutilizabile care au fost dezvolate în proiectele anterioare pentru aplicare lor în situații noi.

Iată câteva tipuri de exemple de sistem:

manager de tranzacție;

simulare în timp real;

simulare dinamică;

interfață interactivă;

Un manager de tranzacție este un sistem de baze date a cărui funcție principală este să stocheze și să acceseze informații. Ar trebui să fie capabil să trateze atât multiplii utilizatori, cât și concurența.

Modelul obiectelor este foarte important într-un sistem manager de tranzacții. Foarte puține transformări de date au loc și astfel modelul funcțional va juca un rol relativ minor. Modelul dinamic este foarte important, de vreme ce managerii de tranzacții sunt inerent distribuiți.

O interfață interactivă este un sistem în care interacțiunile dintre sistem și agenții externi (de exemplu oamenii) joacă un rol important. O astfel de interfață poate fi o parte a unei aplicații.

Modelul dinamic este foarte important într-o interfață interactivă. Evenimentele provocate de intarea utilizatorului, determină răspunsul sub forma activării de secvențe de cod sau de meniuri pe ecran. Obiectele din modelul obiectelor sunt reprezentate prindispozitive de interacțiune cum ar fi bare de defilare, butoane, cutii de control și meniuri. Există pe oiață numeroase pachete comerciale care implementează toate aceste obiecte de interacțiune drept clase C++. Rolul modelului funcțional într-o interfață interactivă este să reprezinte cererile utilizatorului în funcții ale aplicației care sunt apoi executate.

Un sistem în timp real este acel sistem dominat de constrângerile timpului în acțiunilșe sale. Modelul dinamic este de o importanță absolută, în timp ce modelele funcțonal și cel al obiectelor pot fi importante sau nu.

Un sistem de simulare dinamică modelează obiectele din lumea reală. Simulările sunt ușor de nodelat, de vreme ce obiectele se pot baza pe lucruri tangibile din domeniul problemei. Mai mult, operațiile pot fi, de asemenea, deduse din domeniul problemei. Modelul obiectelor este deseori complex. Modelul dinamis este important, în timp ce modelul funcțional poate fi și el important.

Implementarea OO

În acest moment suntem pe punctul de a proceda la implementarea sistemului. Iată câteva alternative în acest sens:

implementare hardware;

implementare într-un limbaj neorientat spre obiecte;

implementare într-un limbaj orientat spre obiecte (C++, SMALLTALK, Eiffel, ADA etc.);

implementare utilizând un sistem relațional de baze de date.

Prezentarea unor tehnici de modelare OO consacrate

Jackson Structured Developement (JSD)

Această metodologie a fost dezvoltată de Michael Jackson, și se caracterizează prin faptul că împarte dezvoltarea unui sistem în două etape: specificarea (ce trebuie făcut) și implementarea (cum trebuie făcut).

Metoda Jackson pleacă de la structura datelor aplicației și este bazată pe proiectarea de detaliu. Obiectivul urmărit este structurarea programelor și aplicațiilor pe baza structurii problemei folosind descompunerea top-down pentru a obține descompunerea întregului în părți și apoi reprezentarea componentelor pornind de la principiile programării structurate.

Un model JSD descrie lumea real în termeni precum entitate, acțiune și succesiunea acțiunilor. Entitățile apar de obicei ca substantive în enunțul problemei, iar acțiunile se identifică cu verbele.

Metodologia JSD cuprinde următoarele etape:

determinarea datelor problemei (entitate-acțiune);

determinarea componentelor corespunzătoare din structura datelor (structura entității);

deducerea structurii programelor (modelul inițial);

determinarea operațiilor elementare și alocarea lor la structura programelor (funcțiile sistemului);

timpul sistemului;

implementarea.

Object Oriented Design (OO) – Grady Booch

Deși Booch descrie tehnici și instrumente puternice pentru asistarea proiectării, de la liste neformale la diagrame și șabloane neformalizate, el nu prescrie o ordine strictă pentru programarea orientată obiect. Totuși el propune patru pași:

identificarea claselor și obiectelor la un nivel dat al abstractizării;

identificarea semanticilor claselor și obiectelor;

identificarea relațiilor între clase și obiecte;

implementarea claselor și obiectelor.

Acest proces este recursiv, iar Booch face următoarele recomandări: “Procesul de proiectare orientată obiect începe cu descoperirea claselor și obiectelor care formează vocabularul domeniului problemei; el se încheie atunci când nu mai pot fi descoperite alte abstracții cheie sau mecanisme, sau când clasele și obiectele care au fost descoperite pot fi implementate compunându-le din componentele software reutilizabile.”

Metodologia OOD cuprinde următoarele tipuri de diagrame:

diagrama claselor – evidențiază clasele și relațiile dintre ele în stadiul de proiectare logică a sistemului;

diagrama modulelor – documentează asignarea obiectelor și claselor la module în stadiul de proiectare fizică a programului;

diagrama obiectelor – obiectele sunt conectate prin arce direcționate acre definesc legarea obiectelor prin mesaje și nu fluxul controlului;

șablonul operației – text structurat care reprezintă documentarea detaliată a proiectării în ceea ce privește operațiile;

diagrama proceselor – utilizată pentru a reprezenta alocarea proceselor la procesoare în timpul proiectării fizice a sistemului. Este utilizată numai pentru implementări în sistem multiprocesor;

diagrama stări-tranziții – evidențiază stările unei clase, evenimentele care cauzează tranzițiile și acțiunile ce rezultă în urma schimbării stării;

diagrama timpului (timing diagram) – însoțește diagrama obiectelor și evidențiază fluxul controlului și succesiunea evenimentelor dintr-un grup de evenimente cooperante.

Object Oriented Software Engineering (OOSE) – Ivar Jacobson

Este o tehnică de analiză, proiectare și programare orientată obiect utilizată în dezvoltarea sistemelor de timp real, a sistemelor de conducere a proceselor. Metodologia este implementata in medii CASE si adaptata pentru diferite limbaje de programare ca de exemplu, ADA, C++, SMALLTALK sau COBOL.

OOSE consideră, prin analogie cu procesele industriale, că procesele de dezvoltare a software-ului au aceleași componente.

Instrumente – reprezintă un suport pentru arhitectură, metode, procese, de obicei medii CASE pentru dezvoltarea eficientă de software.

Procese – cum se aplic ămetoda mai ales în procese ca părți sau activități care interacționează (activitate industrială).

Metode – explicitează modul de implementare (pas cu pas) a conceptelor arhitecturii.

Arhitectura – abordarea selectată dintr-o mulțime de abordări posibile (de exemplu abordare utilizând blocuri prefabricate).

Metodologia OOSE propune în dezvoltarea software cinci modele: modelul cerințelor, modelul de analiză, modelul de proiectare, modelul de implementare și modelul de test.

III. Specificații software – specificații algebrice

Specificațiile algebrice sunt una din metodele ce ajută la definirea clară a cerințelor și obiectivelor unei probleme prin conceptualizarea obiectelor din lumea reală, utilizând modelul matematic și având posibilitatea folosirii tuturor operațiilor definite de acesta. La baza acestei metode stă conceptul de tip de date.

Un tip este o descriere abstractă a unui grup de entități asemănătoare, prin specificarea atributelor și a operațiilor permise asupra sa. Noțiunea de tip este determinantă pentru comportarea instanțelor sale. Un tip de date abstract (ADT) se caracterizează numai prin operațiile sale, ce constituie interfața acestuia.

Pentru a înțelege mai bine ce sunt specificațiile algebrice, va trebui să facem mai întâi o descriere preliminară a unui concept mai general, acela de specificație formală.

Ce sunt specificațiile formale?

În [Salo95] specificarea formală este definită ca modalitatea de descriere matematică precisă a stării și comportamentului un unui sistem, într-o manieră independentă de implementare, prin intermediul tipurilor abstracte de date. Motivul utilizării specificațiilor formale este că sunt în același timp compacte, consistente, precise si neambigue, spre deosebire de limbajul natural care este voluminos, nepractic (poate fi folosit mai mult la introducere și la eventuale comentarii). Este necesar însă ca imediat ce apare o modificare in program, aceasta să se reflecte și în specificații; altfel acestea devin inutilizabile.

Avantaje ale specificațiilor formale (probe de corectitudine a programului [Hore89]):

folosirea unui raționament matematic riguros. Proprietățile specificațiilor pot fi demonstrate ca și teoremele în matematică, iar lipsa consistenței și a completitudinii poate fi depistata din faze mai timpurii;

posibilitatea de a verifica formal daca programul satisface specificatiile

Există specificații formale constructive care sunt direct executabile, însă cu performanțe slabe. Dupa aceasta urmează un proces de modelare rapidă. Cu ajutorul specificațiilor constructive se realizează o proiectare top-down, însemnând că specificația este tratată înaintea execuției oricărei instrucțiuni din program. Un beneficiu al folosirii specificațiilor constructive este acela ca se obtine un feed-back mai rapid al proiectantului și utilizatorului și se obișnuiesc cu sistemul înaintea începerii fazei de implementare.

Exemple de formalisme ale specificațiilor:

metode axiomatice – folosirea pre- si postconditiilor

corectitudinea funcțională

specificatii algebrice – bazat pe conceptul tipurilor abstracte de date; folosirea modelului matematic algebric ca fundament.

Specificatii algebrice

Folosirea pe scară tot mai largă a modularizării, a tipurilor de date, a programării orientate obiect au condus la un modelul numit specificații algebrice, dezvoltat de Guttag [Gutt78]. În acest model ne interesează mai mult comportamentul obiectelor definite de anumite programe decât detaliile implementării lor. De exemplu, ce definește o structură de date numită stivă? Orice exemplu ne va conduce la imaginea punerii și luării de farfurii pe/de pe o tavă. Mai formal, putem spune că punerea unei farfurii este inversul scoaterii unei farfurii de pe stivă. Cu alte cuvinte, dacă S este o stivă iar x este un obiect de pe stivă, push și pop urmează relația:

pop(push(S,x)) = S

Asta însemnă că dacă adaugi x pe stiva S și apoi îl iei înapoi, obții iarăși stiva S.

Adăugând câteva relații suplimentare, putem defini formal cum se comportă o stivă. Nu ne interesează cum este ea implementată atâta timp cât operațiile push și pop satisfac aceste relatii. Astfel, aceste relații formează acum specificatiile pentru stivă.

Specificarea algebrică introduce operațiile permise asupra ADT-ului prin semnătură (nume și funcționalitate), precum și un set de axiome reprezentate prin ecuații algebrice implicite în care intervin operațiile asociate ADT-ului. Specificarea algebrică are o semantică formală algebrică, bazată pe logica ecuațiilor și o semantică operațională bazată pe interpertarea ecuațiilor ca reguli de rescriere [Duce87]. Utilizarea regulilor de rescriere face posibilă validarea specificațiilor prin testare și utilizarea acestora ca prototipuri pentru evaluarea și confirmarea corectitudinii deciziilor de proiectare [Salo95].

Se urmărește construirea unui sistem inferențial care permite ca programele să poată fi verificate chiar atunci când programatorul aplicației dorește să îmbogățească mediul cu noi tipuri de date.

Observații istorice asupra specificațiilor algebrice

Principalul argument al concepției algebrice a specificațiilor este acela că un modul software are aceeași structură ca și algebra: diferitele tipuri de date corespund mulțimilor, iar operațiile care ne interesează sunt funcții între aceste mulțimi.

Subiectele despre specificații algebrice tratate în literatură sunt: corectitudinea, demonstrarea teoremelor, parametrizarea, tratarea erorilor etc.

Tehnicile de specificații algebrice au fost aplicate pe diferite sisteme, de la cele mărunte până la cele foarte sofisticate, și permit reutilizarea codului.

Conceptul de ADT

Specificarea ADT presupune descrierea unor clase de structuri de date prin enunțarea serviciilor disponibile la aceste structuri, și a proprietăților intrinseci ale acestor servicii ([Hore89]).

Prin specificarea unei ADT nu interesează cum este reprezentată structura de date sau cum este implementată fiecare operație, ci ce reprezintă acestea la nivelul clientului care dorește să facă instanțieri ale clasei respective.

A fi capabil să adaugi noi tipuri într-un program este o însușire puternică. Acest concept, care a evoluat din anii 1970, este cunoscut ca abstracția datelor însoțită de încapsulare, și este o tehnică importantă din genul “împarte și stăpânește”, care ajută programatorii să dezvolte produse la costuri mici ([Gann93]). Trebuie identificate cele mai des întâlnite activități sau informații, și apoi, abstractizându-le, să le desriem explicit structura informațională într-un mod compact și concis. Odată ce structura a fost izolată, un programator poate începe să implementeze rutinele de manipulare a datelor, altul poate lucra pe aplicație folosind datele, și amândoi vor fi asigurați că totul va funcționa conform planului.

De ce acest concept de “tip” este pe primul loc? Asociind un nume-tip cu o parte din date este o alegere a programatorului despre ce date vor fi folosite. Când tot ce avem de declarat despre o dată este că reprezintă un integer sau un string, cu siguranță există multă informație nefolosită despre acel tip. Oricum, când un proiectant abstractizează o colecție de proprietăți care interesează și declară colecția ca fiind un “tip nou”, îi este apoi mai ușor să deducă alte utilizări ale datei.

Activitatea de abstractizare variază de la o metodologie la alta. Totuși, odată definit un tip, este necesar ca el să îndeplinească proprietățile:

să verifice implementarea proprietăților care îl caracterizează;

să aibă un sens și un rol clar în aplicația care îl folosește.

Pentru scopurile noastre, un tip de date constă într-un set de valori (domeniul său de valori) și un set de operații pe domeniul respectiv. Definirea domeniului este de obicei clară: domeniile mici de valori pot fi enumerate. Altele pot fi definite constructiv, identificînd mai întâi un număr mic de elemente de bază, apoi se descrie cum se generează restul elementelor domeniului. De exemplu, domeniul string poate fi construit astfel:

o literă singură este un string;

orice string urmărit de o literă este un string;

Odată domeniul specificat, va trebui să descriem operațiile asupra lui. Primul pas este enumerarea numelor operatorilor, apoi se identifică într-un fel cu ce tipuri de valori operează și ce returnează. Acest pas este denumit descrierea sintaxei, și felul în care construim sintaxa este dependent de obicei de cum intenționăm să descriem funcționalitatea operatorilor (sau semantica).

Sunt mai multe căi pentru a reprezenta semantica. Unul este cel informal: a da o descriere textuală a comportamentului. Datorită ambiguităților limbajului natural, acest model este nesatisfăcător. Este neclar, nu permite o căutare automată, și necesită mai mult spațiu ca alte metode. Două alte tehnici pentru specificarea tipurilor abstracte de date (ADT) sunt mai formale. Acestea sunt specificațiile operaționale și specificațiile algebrice, și sunt descrise în detaliu în secțiunile următoare. În fiecare caz ne concentrăm asupra felului cum arată specificațiile (alături de alte noțiuni ce alcătuiesc această concepție), apoi vom verifica implementarea acestor tipuri de date. Vom concluziona pentru fiecare din abordări cu exemple detaliate despre cum programele de aplicații care ele însele folosesc ADT sunt verificate.

Scrierea de specificații pentru ADT își găsește utilitatea și în faza de proiectare a ciclului de viață. Acestea sunt concepute într-un stil modular, în corespondență cu modulele de program din faza de implementare. Modulele de specificații trebuie alese astfel încât să conducă la o complexitate minimă a interfeței și să asigure o continuitate maximă a softului. Găsirea modelului optim presupune un compromis al acestora.

În [Salo95] este descris un mod de definire a unui ADT:

ADT <nume tip>

uses

// ADT-uri importate

type

// tip introdus

functP

// specificare functii primitive

axioms

var // specificare variabile utilizate in axiome

// specificare axiome

functD

// specificare functii derivate

end <nume tip>

Constructia modulelor se face ierarhic, unele module putând importa alte module.

Exemplu de descriere (specificare) a tipului TABLOU:

ADT TAB

uses INDEX type index, ELT type elt // element de tip TABLOU

type

tab elt

functP

genTab: (index, index) tab elt

isTabMember: (tab elt, elt) bool

get: (tab elt, index) elt

put: (tab elt, index, elt) tab elt

axioms

var index i,j

var tab elt a

var elt x

isTabMember(put(a,i,x), x

get(put(a,i,x),i)=

if i=j then x

else get(a,j)

end TAB

Specificații algebrice ale ADT

Prin intermediul specificațiilor algebrice definim semantica operatorilor ADT, în termenii interacțiunii lor unul cu altul, în loc să arătăm cum interacționează în termenii unui tip concret. Poate să devină un pic mai greu să descoperim axiome mai bune în specificarea algebrică în comparație cu cea operațională, în care avem de-a face totuși cu implementări ale unor operații singulare.

Specificațiile algebrice sunt compuse din două părți: sintaxa și semantica. Descrierea sintactică se referă de obicei la semnătura algebrică, și folosește tipuri auxiliare de date. În cazul STIVEI aceștia sunt integer și boolean:

push: STACK x INTEGER → STACK

pop: STACK → STACK

top: STACK → INTEGER U {undefined}

empty: STACK → BOOLEAN

newstack: → STACK.

În acest moment trebuie să descriem domeniul tipului STIVĂ. Poate fi mai dificil decăt arată. Informal, știm că vrem ca tipul STIVĂ să cuprindă toate stivele de întregi care pot apare într-un program. Formal, ne trebuie un mod de descriere a lor. Din momentul în care avem lista operatorilor, putem identifica o submulțime a lor, care vor fi constructorii tipului. Ne trebuie un minim număr de operatori necesari pentru a putea construi toate posibilele STIVE. Intuitiv credem că newstack și push sunt constructori.

Axiomele descriu felul în care operatorii interacționează unul cu altul. De exemplu, ADT-ul STACK poate fi specificat astfel:

pop (newstack) = newstack

pop(push(S,I)) = S

top(newstack) = undefined

top(push(S,I)) = I

empty(newstack) = true

empty(push(S,I)) = false

unde S și I sunt instanțe ale tipurilor STIVĂ și INTEGER.

Noi nu considerăm că există o instanță specială a stivei numită newstack (stivă nouă). În schimb, axioma 1 poate fi citită: “efectul compunerii unui pop cu un apel la funcția newstack este același lucru cu a apela direct newstack”. Tot astfel, axioma 2 se citește: “efectul compunerii unui apel pop cu un push pe stiva S a întregului I este acela că se returnează aceeași stivă S cu care am început.”

Această alegere a axiomelor definește un tip abstract pe care îl numim STIVĂ și care pare să capteze proprietățile stivei din intuiția noastră. De remarcat însă că această specificație nu prevede însă mărginirea. Specificația de mai sus permite să identificăm stive de o adâncime arbitrară, care s-ar putea să nu corespundă în implementările pentru care a fost prevăzută. Pentru a include și această proprietate de “limitare” vom folosi o “funcție ascunsă” ( un operator care nu e disponibil accesului utilizatorului, dar care permite deținerea unor proprietăți dorite în specificația noastră) cum ar fi SIZE : STACK → INTEGER, care introduce următoarea algebră în locul celei specificate mai devreme :

pop (newstack) = newstack

pop(push(S,I))= if size(S)=MAX then pop(S) else S

top(newstack) = undefined

top(push(S,I)) = if size(S)=MAX then top(S) else I

empty(newstack) = true

empty(push(S,I)) = false

size(newstack) = 0

size(push(S,I) = if size(S)=MAX then size(S)

else size(S)+1

unde MAX e un parametru predefinit.

În general, o listă de axiome apare ca un set de ecuații, fiecare membru stâng conținănînd o compunere de operatori, și fiecare membru drept conținînd o descriere a comportării acestei compuneri în termenii operatorilor tipului și construcțiilor simple if-then-else. Iterația sau alte variabile auxiliare nu sunt folosite. Aceste axiome sunt considerate uneori reguli de rescriere, deoarece permit rescrierea unei compoziții de operatori prin reducerea la o formă mai simplă.

De remarcat că această concepție funcțională de construcție a ADT-ului tratează instanțele tipului ca fiind constante, neschimbătoare. (În contrast, din punct de vedere al implementării, considerăm o stivă ca fiind un obiect care evoluează ca urmare a operațiilor aplicate asupra sa.) Conform specificației de mai sus, toate operațiile push vor întoarce o instanță a STIVEI care e construită dintr-o altă instanță a STIVEI și un INTEGER. Această situație, împreună cu abilitatea de a vedea axiomele ca reguli de rescriere, ne permit să gândim instanțele unui ADT specificat algebric ca fiind propoziții într-un limbaj, ceea ce este o perspectivă foarte folositoare. De exemplu următoarea propoziție:

empty(pop(push(push(newstack,42),17)))

poate fi rescrisă, folosind axioma (2), astfel:

empty(push(newstack,42)))

În acest punct vom apela axioma (6) pentru a concluziona că este falsă.

În general, este foarte folositor să privim expresiile intermediare ca niște cuvinte într-un limbaj, asupra cărora se pot aplica transformări. Acest lucru ne va ajuta în înțelegera programelor folosind ADT-uri specificate algebric.

Dezvoltarea axiomelor algebrice

Pentru ca axiomizarea unui tip T să fie suficient de completă trebuie să atribuim câte o valoare fiecărui termen de tipul T. Din moment ce constructorii produc toate valorile domeniului pentru tipul definit, trebuie doar să specificăm ce operații non-constructor modifică fiecare constructor. Astfel, dacă C1 si C2 sunt operații de tip constructor de tipul T iar f este o operație non-constructor definită astfel r : T → T1, vom scrie axiome pentru a defini f(C1) și f(C2). De exemplu, pentru tipul STIVĂ, push și newstack sunt constructori, în timp ce pop, top și empty nu. Astfel, vom defini axiome pentru a defini propozițiile:

pop (newstack)

pop(push(S,i))

top(newstack)

top(push(S,I))

empty(newstack)

empty(push(S,i)

Să considerăm un alt exemplu: definim ADT-ul SET – “mulțime de întregi, fără elemente repetitive”, cu sintaxa:

newset: → SET

insert: SET x INTEGER → SET

delete: SET x INTEGER → SET

member: SET x INTEGER → BOOLEAN

cu semantica:

member (newset,i) = false

member(insert(S,i),j) = if i=j then true else member(S,j)

delete(newset,i) = newset

delete(insert(S,i),j) = if i=j then delete(S,j)

else insert(delete(S,j),i))

Alternativ putem defini ADT-ul BAG – „mulțime de întregi, cu elemente repetitive”, ca fiind:

newbag: → BAG

insert: BAG x INTEGER → BAG

delete: BAG x INTEGER → BAG

member: BAG x INTEGER → BOOLEAN

cu semantica:

member (newbag,i) = false

member(insert(B,i),j) = if i=j then true else member(S,j)

delete(newbag,i) = newbag

delete(insert(B,i),j) = if i=j then B

else insert(delete(B,j),i))

Îndrumări pentru scrierea axiomelor algebrice

Procesul de scriere a specificațiilor algebrice este similar cu cel al programării. Principala diferență este că în programare suntem interesați în eficiența soluțiilor, în timp ce în specificare ne interesează exprimerea doar a funcționalității, cu alte cuvinte doar funcția ce trebuie calculată, nu metoda de calcul. În afară de asta limbajele de specificare algebrică nu prevăd conceptul de “side effect” (atribuirea variabilelor) de fiecare dată când o nouă valoare este creată, deci specificațiile algebrice nu seamănă întru totul cu așa-zisele programe functionale.

Determinarea funcționalității

Trebuie determinat modul de utilizare al tipului de date, ce operații creează instanțe ale tipului de date, ce operații modifică, ce operații obțin valori din tipul de date. Pentru a determina aceste funcții se are în vedere utilizarea tipului de date. Acest lucru poate fi greu, mai ales dacă acest tip vizează un scop general și nu putem anticipa utilizările sale.

Scrierea semnăturilor

Odată ce ne-am decis asupra setului de funcții, vom scrie semnăturile acestora. În acest pas putem face ca tipul de date să fie destul de intuitiv dacă alegem numele potrivite și cu înțeles. Atenție: cuvântul final care exprimă cel mai bine înțelesul poate să nu fie totuși numele. Aceasta este ideea de bază a folosirii specificațiilor formale.

Alegerea constructorilor

Inițial, toate funcțiile care returnează tipul definit pot fi considerate constructori, dar aceasta ar creea probleme atât în consistența axiomelor noastre cât și în numărul de axiome (ecuații) necesare. Rezultă că avem nevoie de un set „minimal” de constructori. Acest set de constructori va avea cel puțin o funcție fără parametrii a tipului definit (de obicei va fi o funcție fără nici un parametru).

Dacă ne imaginăm cum se poate exprima semantica unei funcții în termenii celorlalte, atunci această funcție nu este un constructor. Dealtfel, modul în care se comprimă semantica unei funcții va dicta ce axiome se scriu mai târziu.

Câteodată, operațiile constructori sunt evidente din specificații; câteodată alegerile care trebuie făcute trebuie explicitate. De exemplu, să considerăm o listă cu inserție și ștergere la ambele capete. Avem două posibile seturi de constructori – {AddFront, New} și {AddBack, New}. Pe care îl folosim e o chestiune de gust dar trebuie să decidem asupra unuia din ei.

Scrierea axiomelor

Prima parte constă în a determina ce axiome trebuie scrise. Constructorii nu au nevoie de axiome; va trebui să scriem axiome doar pentru non-constructori. Pentru fiecare funcție non-constructor va trebui să acoperim toate cazurile parametrilor. Ca o regulă de principiu, dacă sunt n constructori vor fi necesare n ecuații pentru fiecare non-constructor.

Această regulă nu e completă totuși, deoarece căteodată sunt mai mulți parametri ai tipului definit, deci vom avea nevoie de mai multe axiome. De exemplu, dacă definim o funcție cu 3 parametri ai tipului definit și avem 2 constructori e posibil să trebuiască 2³=8 ecuații pentru a acoperi toate combinațiile de constructori. Din fericire, acest lucru se întâmplă rareori în practică, de obicei vom putea acoperi cazurile doar cu câteva ecuații.

Acum că știm toate cazurile care se iau în considerare, vom scrie membrii stângi ai axiomelor. Pentru a scrie membrii drepți nu există metode generale. În timp ce scriem axiomele vom observa că memebrii stângi nu prea au înțeles (ex: extrag informație dintr-o structură de date goală). Pentru aceștia definim excepții.

Exemplu: Funcții pentru numere întregi finite

Vrem să proiectăm o structură de date pentru a reprezenta funcții cu numere întregi finite. O astfel de funcție este una al cărei domeniu este finit, ceea ce înseamnă că este definită într-un număr finit de puncte. Funcțiile finite pot fi reprezentate printr-o tabelă ale cărei intrări sunt perechi ordonate.

Facem observația că, deși definim structura de date pentru cazul întregilor, specificația pe care o vom dezvolta poate fi parametrizată pentru funcții finite cu orice domeniu, de întindere aleatoare.

Determinarea funcționalității

Ne propunem să putem manipula mapări ale unor domenii de definiție pe domenii de valori finite prin crearea unor tabele simple de mapări, modificarea lor într-un punct specific (definirea unei valori, setarea unei valori ca nedefinită), și realizarea unei uniuni a tabelelor de mapări. Uniunea a două tabele nu este comutativă, deoarece dacă ambele mapări conțin un același punct de definiție, cea de-a doua tabelă ar avea prioritate. Va trebui să manevrăm tabele vide, să avem o funcție care să creeze tabele cu o singură intrare; dându-se un întreg va trebui să cunoaștem valoarea funcției în acel punct, iar pentru o tabelă să putem aflăm domeniul său.

Scrierea semnăturilor (nume și funcționalitate)

Date fiind cerințele exprimate anterior, definim următoarele funcții, cu semnăturile corespunzătoare:

EmptyMapping: mapping

SingleMapping: integer X integer mapping

Define: mapping X integer X integer mapping

Undefine: mapping X integer mapping

Union: mapping X mapping mapping

Apply: mapping X integer mapping

Domain: mapping set [integer]

Alegerea constructorilor

Funcțiile candidate pentru constructori sunt: EmptyMapping, SingleMapping, Define, Undefine, Union. Dintre acestea, EmptyMapping sau SingleMapping poate fi ales drept constructor, deoarece sunt singurele care nu au un parametru de tip mapping. Dintr-un alt punct de vedere putem alege EmptyMapping și Define drept constructori.

Scrierea axiomelor

Mai întâi, vom considera axiomele de care avem nevoie. O regulă ne spune că avem nevoie de două axiome pentru fiecare nonconstructor, cu excepția lui Union, care necesită 4 axiome. În plus, deoarece SingleMapping nu are parametrii de tip maping, o putem defini printr-o singură axiomă. Astfel, termenii stângi sunt:

SingleMapping(i,v)=

Undefine(Empty, i)=

Undefine(Define(m,i1,v),i2)=

Apply(Empty, i)=

Apply(Define(m,i1,v),i2)=

Domain(Empty)=

Domain(Define(m,i1,v))=

Acum definim semanticile pentru toate operațiile cu excepția lui Union, deoarece nu știm dacă vor trebui scrise două sau patru ecuații:

SingleMapping(i,v)= Define(Empty,i,v)

Undefine(Empty, i)= Empty

Undefine(Define(m,i1,v),i2)= if i1=i2 then Undefine(m,i2)

else Define(Undefine(m,i2),i1,v)

Apply(Empty, i)= undefined

Apply(Define(m,i1,v),i2)= if i1=i2 then v else Apply(m,i2)

Domain(Empty)= NullSet

Domain(Define(m,i1,v))= AddMember(Domain(m),i)

Acum să luăm în considerare funcția Union. Evident, reuniunea cu EmptyMapping nu modifică tabela. Ce se întâmplă însă cu două tabele nevide? Dorim ca valoarea celei de-a doua tabele de mapări să aibă precedență. Iată cele patru ecuații, pentru a considera toate cazurile posibile.

Union(Empty,Empty) = Empty

Union(Define(m,i,v),Empty) = Define(m,i,v)

Union(Empty,Define(m,i,v)) = Define(m,i,v)

Union(Define(m,i1,v1),(Define(m,i2,v2)) = Define(Union(Define(m,i1,v1),m2),i2,v2)

Privind la specificațiile complexe ale funcției Union observăm că vom folosi doar două ecuații, deoarece primul parametru nu este niciodată folosit recursiv. Dacă al doilea parametru este Empty, atunci va fi returnat primul; dacă nu, atunci vom adăuga toate definițiile sale primului. Noile ecuații sunt:

Union(m,Empty) = m

Union(m1,Define(m2,i,v)) = Define(Union(m1,m2),i,v)

3.3. Consistența

Seturile de axiome sunt consistente dacă obținem mereu același rezultat final, indiferent de ordinea în care aplicăm axiomele pentru a simplifica propozițiile.

Ca un exemplu, (adaptat din [Gutt80]), considerăm adăugarea următoarei axiome la definiția de mai devreme a tipului BAG:

member(delete(B,i),j) = if i=j then false else member(B,j)

Apoi aplicăm această simplificare în propoziția:

member(delete(insert(insert(newbag,3),3),3),3)

Prin aplicarea noii noastre axiome, propoziția se poate rescrie:

if 3=3 then false else member(…)

deci este falsă. Totuși, din axioma delete(insert(…)) originală, aceeași propoziție poate deveni:

member(if 3=3 then insert(newbag,3) else delete(…))

dar

member(insert(newbag,3),3)

este adevărată, deci

if 3=3 then true else member(…)

deci este adevărat, ceea ce duce la o contradicție. În consecință, proprietatea de consistență nu

se verifică, în acest caz

3.4 Egalitatea termenilor

Să considerăm două propoziții pentru tipul SET :

insert(insert(newset,3),4)

și

insert(insert(newset,4),3)

Intuitiv se crede că mulțimile reprezentate de aceste două propoziții sunt egale. În general, chestiunile de egalitate sunt mai greu de tratat. În așa numitele “algebre inițiale”, două propoziții sunt considerate egale doar dacă se poate dovedi aceasta ca o consecință a axiomelor.

4. Validarea prin inducție a tipului de date

Inducția tipului de date este o tehnică foarte importantă în verificarea proprietăților specificațiilor algebrice. Această inducție funcționează astfel (și este strâns legată de inducția naturală a întregilor pozitivi): dându-se un set de operații definite asupra unui ADT X, le putem separa în trei seturi:

{fi} sunt acele funcții care returnează obiecte de tipul X dar nu conțin argumente de tipul X. Aceste funcții de generare creeează obiecte primitive de tipul X.

{gi} sunt acele funcții care returnează obiecte de tipul X ;i conțin argumente de tipul X. Aceste funcții de generare creeează obiecte neprimitive de tipul X.

{hi} sunt toate celelalte funcții, bazate pe argumente de tipul X, și care returnează valori de un tip oarecare.

Pentru ADT-ul stivei, avem:

f = {newstack}

g = {push, pop}

h = {empty, top, size}

În general, va exista un singur membru f, unul sau doi memrii g și un număr mic de membrii h, dar nu sunt restricții în acest caz.

Fie P(x) un predicat, pentru xєX, în cazul ADT-ului X. În ce condiții P va fi adevărat pentru orice x є X? Asemenea inducției naturale, vrem să arătăm că obiectele primitive sunt adevărate sub predicatul P, și putem folosi aceste valori prmitive pentru a arăta că prin formarea altor valori ale tipului proprietatea rămâne adevărată.

Definim inducția tipului de date astfel:

dându-se un ADT X cu funcțiile fi, gi și hi definite ca mai sus, și predicatul P(x) pentru xєX, să arătăm că P(fi)este adevărată (cazul de bază);

presupunem că P(x) este adevărată. Să arătăm că aceasta implică P(gi(x)) este adevărată: P(x)P(gi(x));

putem concluziona că: oricare ar fi xєX P(x)

Pentru tipul de dată stivă, aceasta ar însemna să demonstrăm P(newstack) și că P(x)P(gi(x)) (atât P(push(x,i)) cât și P(pop(x))). Totuși, nu este nevoie să mai demonstrăm pentru pop, deoarece se pot genera toate obiectele de tip stivă și fără ajutorul acestuia. Lema următoare este o declarație formală pe care am referit-o mai devreme, și anume că toate instanțele de tip stivă pot fi construite folosind apeluri push și pop. Ceea ce înseamnă că fiecare stivă are o formă normală.

Lemă: Pentru orice S є STACK, avem 1. sau 2. :

S = newstack;

Există S1 є STACK și I є INTEGER astfel încât S = push(S1,I)

Această lemă ne spune că putem înlocui orice operație pop cu un set echivalent de operații newstack și push. (Unicitatea formei normale necesită o altă demonstrație, dar nu ne vom ocupa de aceasta acum.)

5. Verificarea specificațiilor algebrice

Operatorii unui ADT specificat algebric sunt descriși prin interrelația lor cu alți operatori. Dar pentru a implementa un ADT specificat algebric, este esențial să descriem mai întâi proprietățile unui al doilea tip de date care va fi folosit petru a îl implementa pe primul. În spiritul aceleiași concepții de abstracție, de obicei vom da o specificație algebrică și pentru acest al doilea tip.

Ne vom referi des la tipul pe care dorim să îl implementăm ca un tip de date “de nivel superior”, iar pentru tipul de date folosit la implementare ca un tip de date “de nivel inferior”. Totuși, aceste enunțuri sunt vagi, și rezultă doar din modul natural în care gândim despre procesul de implementare. De fapt, tipul de nivel inferior poate fi el însuși un ADT elaborat, cu semantici bogate. La rândul lui poate fi implementat pe baza unui tip de nivel mai jos, și așa mai departe. În această manieră poate rezulta deseori o ierarhie de tipuri de date. Scopul final este ca unul din aceste tipuri de date de nivel inferior să poată fi în cele din urmă reprezentat și implementat în hardware ( de exemplu, vom arăta pe scurt cum se implementează stivele specificate mai devreme în termenii unui tablou specificat algebric, și ne vom aștepta ca acest tablou să poată fi direct implementabil în limbajul nostru gazdă pe majoritatea computerelor).

Totuși, există o problemă acută în legătură cu această ierarhie de tipuri de date, anume cum vom verifica dacă un tip de date de nivel inferior poate fi implementat cu încredere pe o mașină reală. În exemplul pe care îl vom da (stive în termenii tablourilor unidimensionale), specificația noastră despre matricea unidimensională presupune că avem o matrice nelimitată și mai mult, că intrările neinițializate în matrice pot fi detectate. Aceste proprietăți sunt rareori adevărate în implementările pe mașină. De aceea, tehnicile noastre sunt tot atât de bune ca și implementarea noastră pentru tipuri de bază. Nu mai puțin, dacă dezvoltăm o specificație care poate fi implementată cu încredere pe o mașină, atunci ne vom bucura de toate avantajele unei implementări verificate. Unul dintre avantajele unor sisteme hardware este acela c[ prev[d suport pentru anumite tipuri generice de date; astfel, dezvoltatorii pot folosi instanțe ale tipului nostru de date STIVĂ, și vor fi transparente dacă le implementează utilizând matricile (pe anumite sisteme hardware) sau stivele (pe stiva proprie a calculatorului).

Odată ce am obținut specificația atât pentru tipurile de nivel superior cât și pentru cele de nivel inferior, putem descrie cum unul se poate implementa unul în termenii celuilalt. Acest lucru se face prin intermediul unui program de implementare care, ca și specificațiile originale ale ADT-urilor individuale, arată ca o listă de axiome. Totuși, în timp ce axiomele arătau în ce mod operatorii unui tip interacționau, programul de implementare expune comportamentul tipului de nivel superior în termenii celui de nivel inferior.

Pentru a completa acest program de implementare, trebuie prevăzut cu o funcție adițională, aproape esențială: funcția de reprezentare. Să ne amintim că operatorii fiecărui tip individual sunt funcții care mapează pe diferite domenii. Ar fi absurd să construim un program de implementare care va egala apoi domeniul operatorului unui tip cu domeniul altui operator al altui tip. Programul are sens doar atunci când există o funcție de reprezentare care arată cum se mapează o instanță a unui tip de nivel inferior pe o instanță a unui tip de nivel superior. Mai precis, putem indica în ce fel operatorii unui tip de nivel înalt se comportă în termenii domeniului funcției de reprezentare aplicată pe operatorii tipului de nivel inferior.

Suntem în măsură acum să recapitulăm ce înseamnă a verifica implementarea unui ADT. Cerința cea mai evidentă este că axiomele pentru tipul care ne interesează sunt menținute și la momentul implementării. Deoarece singurul mod de a caracteriza matematic ADT-urile noastre este acela de a arăta cum interacționează unele cu altele, singurul loc unde ne putem întoarce să cercetăm rațiunea unei implementări este acest corp de reguli. Acestea trebuie verificate. O obligație a unei probe, mai puțin evidentă, este de a verifica dacă interpretarea egalității nu este de fapt o relație de echivalență. În final, trebuie să demonstrăm o invarianță de reprezentare, ceea ce înseamnă să ne asigurăm că toate elementele domeniului ADT-ului nostru pot fi exprimate, de fapt, ca fiind imaginea funcției de reprezentare aplicate pe câteva instanțe ale tipului de nivel inferior.

5.2. Verificarea unei implementări a stivei

Folosind o tehnică dezvoltată de [Muss78] putem ilustra acum ideea implementării unui ADT în termenii unui altul și apoi să verificăm corectitudinea acestei implementări prin a arăta cum ADT-ul stivei definit anterior poate fi implementat în termenii unor matrice. Pentru aceasta, primul pas constă în a formula o axiomatizare a matricii. Sintaxa ei va fi:

newarray: array

assign: array X integer X integer array

access: array X integer array U {undefined}

iar semantica va fi:

access(newarray,I) = undefined

access(assign(array,I1,val),I2) = if I1=I2 then val

else (access(array,I2))

De notat că acesta este un mod mai simplist de a vedea matricile. În particular, aceasta este o matrice nelimitată, care este utilă doar în scopuri introductive. Așa cum am discutat în secțiunea anterioară, este important pentru noi să efectuăm propria noastră implementare a stivei în termenii unui tip de date care este mult mai bine implementat de hardware-ul computerului.

Vom alege funcția de reprezentare astfel:

STAK(array,integer) STACK

și de aici putem reda programul de implementare:

newstack = STAK(newarray,0)

push(STAK(arr,t),x) = STAK(assign(arr,t+1,x),t+1)

pop(STAK(arr,t)) = if t=0 then STAK(arr,0)

else (STAK(arr,t-1))

top(STAK(arr,t)) = access(arr,t)

empty(STAK(arr,t)) = (t=0)

Invariantul de reprezentare poate fi acum declarat ca fiind predicatul

P(S) = există A є ARRAY, există i є INTEGERS, i ≥ 0, S = STAK(A,i)

Unde S este o variabilă oarecare corespunzătoare unui element al stivei STACK.

Pentru a ne asigura de corespondența între un element al stivei STACK și o pereche (array,i), trebuie să demonstrăm fiecare din:

P(newstack)

P(S) => P(push(S,x))

P(S) => P(pop(S))

Deoarece am demonstrat anterior o lemă în formă normală pentru stive, ne mai rămân primele două din aceste aserțiuni. Deci:

trebuie să demonstrăm P(newstack), care este:

există A є ARRAY, există i є INTEGER, newstack = STAK(A,i)

Bazându-ne pe implementarea noastră, putem foarte simplu să alegem A să fie newarray, iar i să fie 0.

trebuie să demonstrăm P(S) => P(push(S,x)). Știm că S = STAK(A,i) și i ≥ 0 din P(S), și avem nevoie să arătăm că există A’ și i’ astfel încât push(S,x) = STAK(A’,i'). Dar

push(S,x) = STAK(assign(A,i+1,x),i+1). Putem arăta aserțiunea dorită alegând simplu A’ să fie assign(A,i+1,x) iar i' să fie i+1, cu i' ≥ 0.

Egalitatea

Interpretarea egalității este aleasă după cum urmează:

STAK(A1,t1) = STAK(A2,t2)

dacă și numai dacă

(t1=t2) și pentru orice k (1 ≤ k ≤ t1, access(A1,k) = access(A2,k))

Obligația noastră este să arătăm că este o interpretare rațională, ceea ce înseamnă că posedă proprietățile unei relații de echivalență:

reflexivitatea: x = x

simetria: x = y => y = x

tranzitivitatea: x = y și y = z => x = z

substituția: x = y => P(x) = P(y)

unde P poate fi oricare din operatorii noștri. Deci:

reflexivitatea: trebuie să arătăm că S = S pentru o stivă S și interpretarea echivalenței noastre. Știm că S se află în domeniul lui STAK, bazat pe invariantul nostru de reprezentare, care este S = STAK(A,t). Dar A = A și t = t, deci bazându-ne pe obișnuita interpretare a egalității (asupra întregilor și a matricilor), rezultă că

STAK(A,t) = STAK(A,t) în interpretarea egalității dorite de noi.

simetria: trebuie să arătăm că S1 = S2 implică S2 = S1. Deoarece S1 = S2 în propria interpretare a echivalenței, matricile și întregii care mapează în aceste stive prin STAK sunt egale între ele. Deoarece egalitatea întregilor si matricilor este simetrică, atunci S2 = S1 este de asemenea adevărat în interpretarea noastră a echivalenței.

tranzitivitatea: exact același argument folosit pentru simetrie va ajuta și în demonstrarea tranzitivității.

substituția: trebuie să demonstrăm fiecare dintre:

S1 = S2 => push(S1,x) = push(S2,x)

S1 = S2 => pop(S1) = pop(S2)

S1 = S2 => top(S1) = top(S2)

S1 = S2 => empty(S1) = empty(S2)

Vom face demonstrația pentru operația push.

Fie S1 = STAK(A1,i1) și S2 = STAK(A2,i2), și presupunem că S1 = S2 să arătăm că:

push(STAK(A1,i1),x) = push(STAK(A2,i2),x)

Folosim implementarea lui push din membrul drept al expresiei de mai sus pentru a obține:

STAK(assign(A1,i1+1,x),i1+1) = STAK(assign(A2,i2+1,x),i2+1)

În termenii interpretării noastre a egalității, trebuie să arătăm că:

(i1 = i2) și pentru orice k (1 ≤ k ≤ i1, access(A1,k) = access(A2,k) =>

(i1+1 = i2+2) și pentru orice k (1 ≤ k ≤ i1,

access(assign(A1,i1+1,x),k) = access(assign(A2,i2+1,x),k) )

Prima clauză a consecinței urmează direct din prima clauză a antecedentului. A doua clauză a consecinței se obține simplificând după cum urmează:

access(assign(A1,i1+1,x),k) = if k = i1+1 then x else access(A1,k)

potrivit programului de implementare. Tot astfel,

access(assign(A2,i2+1,x),k) = if k = i2+1 then x else access(A2,k)

De aici, deoarece i1=i2, clauza pe care o examinăm se simplifică la:

oricare ar fi k (1 ≤ k ≤ i1+1, if k = i1+1 then x = x

else (access(A1,k) = access(A2,k)))

Pentru intervalul i ≤ k ≤ i1, aceasta este demonstrată de clauza a doua a antecedentului. Când

k = i1+1, știm că expresia este adevărată datorită simetriei operatorului “=” pe mulțimea întregilor.

În final, suntem pe punctul de a verifica faptul că axiomele tipului nostru STACK se păstrează și în timpul implementării. Expresiile care trebuie verificate sunt:

pop(newstack) = newstack

pop(push(S,I)) = S

top(newstack) = undefined

top(push(S,I)) = I

empty(newstack) = true

empty(push(S,I)) = false

Vom demonstra doar două dintre ele aici. Mai întâi vom demonstra expresia 4, arătând

top(push(S,x)) = x

se menține și la implementare. Folosind invariantul repezentării, presupunem că S = STAK(A,i). Atunci:

top(push(STAK(A,i),x) =

top(STAK(assign(A,i+1,x),i+1) =

access(assign(A,i+1,x),I+1) = x

Astfel, membrul stâng se reduc la x și avem x = x.

Pentru a demonstra expresia 2, vom arăta că

pop(push(S,x)) = S

Din nou, presupunem că S = STAK(A,i).

pop(push(STAK(A,i),x)) =

pop(STAK(assign(A,i+1,x),i+1)) =

if i+1=0 then STAK(assign(A,i+1,x),0))

else STAK(assign(A,i+1,x),i))

Acum va trebui să folosim inducția tipului de date pentru a arăta că P(STAK(A,i)) implică

i ≤ 0 astfel încât vom considera un singur caz

P(newstack) = P(STAK(newarray,0)) 0 ≥ 0

P(S) => P(push(S,x))

P(STAK(A,I)) => P(push(STAK(A,i),x))

i ≥ 0 => P(STAK(assign(A,i+1,x),i+1))

i ≥ 0 => i+1 ≥ 0

Datorită lemei noastre în forma normală, nu mai avem nevoie să arătăm P(S) => P(pop(S)) separat.

Deoarece i ≥ 0, => i+1 ≠ 0, deci vom considera doar

STAK(assign(A,i+1,x),i) = STAK(A,i)

Folosind interpretarea egalității:

(i=i) și oricare ar fi k (1 ≤ k ≤ i, access(assign(A,i+1,x),k) = access(A,k))

Folosind egalitatea întregilor și implementarea accesului, se simplifică la

oricare ar fi k(1 ≤ k ≤ i, if i+1 = k then x else access(A,k) = access(A,k))

Deoarece i+1 ≠ k, oricare ar fi k(1 ≤ k ≤ i, access(A,k) = access(A,k)) și propoziția 2 este demonstrată.

5.3. Exemple de programe

folosirea stivei pentru inversarea valorilor a două variabile. De remarcat că nu este nevoie ca stiva să fie inițializată și nu contează câte variabile se află la momentul actual pe stivă:

{true}

s:=push(s,a)

s:=push(s,b)

a:=top(s)

s:=pop(s)

b:=top(s)

III. Specificarea și analiza rezolvitorilor de probleme în timp real

Rezumat – “În ultimul timp a crescut interesul în cercetarea algoritmilor de rezolvare a problemelor în câmpul inteligenței artificiale (IA). Un rezolvitor de probleme în timp real din IA execută un task sau un set de taskuri în două faze. În timpul primei faze, rezolvitorul de probleme caută o soluție care, odată executată, va satisface cerințele taskului. Ne vom referi la această fază ca fiind faza de planificare sau faza de căutare. În timpul celeilalte faze, rezolvitorul de probleme execută soluția planificată, pentru a obține rezultatele dorite ale taskului. Această fază este referită ca fiind faza de execuție. Sub constrângerea timpului, un program de rezolvare a problemelor de IA în timp real trebuie să echilibreze planificarea cu execuția pentru a micșora timpul de răspuns și pentru a respecta termenele limită. Acest capitol ilustrează o metodologie pentru specificarea algoritmilor de rezolvare a problemelor în timp real. Folosind această metodologie, vom furniza o specificație formală a problemei în timp real. În plus, este prezentată și o metodologie pentru analiza rezolvitorilor de probleme în timp real din IA. Demonstrația cuprinde un studiu de caz despre doi algoritmi de rezolvare a problemelor în timp real, pe nume DYNORA (Dynamic Near Optimal Response-time Algorithm) și RTA (Real Time Algorithm), pentru problema de planificare a drumului în timp real. Se vor furniza rezultate pentru cazurile de complexitate maximă și cel de complexitate medie ale problemei și ale algoritmului care o rezolvă. De asemenea, vom face o evaluare empirică a celor doi algoritmi, DYNORA și RTA, privind respectarea termenelor limită și minimizarea timpului de răspuns.”

1. Introducere

Un rezolvitor al problemelor în IA este format din 3 componente principale: o bază de date globală, un set de reguli de tranziție și un sistem de control. Baza de date globală conține declarații și date care reflectă imagini din lumea reală la fiecare moment de timp. Regulile de tranziție operează asupra bazei de date globale. Fiecare regulă are un set de precondiții care trebuie satisfăcute de respectivele reprezentări ale lumii reale înainte ca regula să fie aplicată. Executarea unei reguli va efectua schimbări în baza de date pentru a reflecta o nouă stare a lucrurilor. Sistemul de control are sarcina de a atinge o stare dorită, prin alegerea și ordinarea setului de reguli, astfel încât aplicarea acelor reguli în ordinea specificată să transforme baza de date globală din starea inițială în cea finală (scopul dorit). Mulțime tuturor posibilelor stări și tranziții de la o stare la alta este referită ca spațiul stărilor. Spațiul stărilor unei probleme poate fi reprezentat printr-un graf în care nodurile semnifică stările iar muchiile semnifică tranzițiile. Un sistem de control în această reprezentare poate fi caracterizat ca fiind procesul de căutare a unei secvențe de tranziții ale stărilor care formează un drum în spațiul stărilor, unind starea inițială cu starea scop.

Un exemplu de spațiu al stărilor pentru problema fermierului, păsării, pisicii și a grăunțelor este evidențiată în figura X. În această situație, fermierul trebuie să treacă în siguranță pasărea, pisica și grăunțele dincolo de râu. Râul este reprezentat de o linie orizontală într-un nod din spațiul stărilor grafului. Fermierul nu poate lăsa pasărea și grăunțele la un loc singure, și nici pasărea cu pisica, pentru că una ar mânca-o pe cealaltă. O mutare dintr-o parte a râului în cealaltă este reprezentată printr-o muchie ce conectează două noduri care reprezintă starea dinaintea mutării și cea de după mutare. Câteva din stările nedorite din spațiul stărilor sunt demonstrate prin noduri marcate printr-o linie dublă în figură.

Un rezolvitor de probleme de IA în timp real trebuie să opereze sub anumite constrângeri de timp impuse de mediul problemei. Sistemul de control va fi nevoit să-și execute procesul de căutare într-un astfel de mod încât restricțiile temporale ale problemei să fie satisfăcute. În jocul de șah contra timp, de exemplu, rezolvitorul de probleme trebuie să caute o mutare în spațiul celor posibile, înăuntrul unei limite de timp. Orice cantitate de timp salvată la o mutare poate fi folosită pentru mutări ulterioare. Astfel, algoritmul de căutare în problema jocului de șah contra timp va da neapărat un răspuns când cuanta de timp alocată expiră. Ideal ar fi ca rezolvitorul de probleme să caute să dea un răspuns într-un timp mai scurt decât cel permis de timpul limită, pentru a aduna timp pentru problemele de decizie mai complicate care vor veni.

Rezolvitorii de probleme de IA în timp real diferă de sistemele convenționale în timp real. Acestea din urmă lucrează cu procese statice în care multă informație referitoare la proces este cunoscută apriori. Aceste sisteme se pretează la probleme în care avem termene limită fixate. Ele s-au concentrat pe activități de programarea proceselor, manipularea întreruperilor și a erorilor, cerințe de comunicație, analiza și proiectarea sistemelor. Spre deosebire de cele descrise mai sus, rezolvitorii de probleme de IA în timp real au ca scop manipularea altor constrângeri ale mediului, ca de exemplu incertitudinea și lipsa de cunoștințe complete, situații dinamice ale lumii reale, timp limitat de validitate a informației, și alte restricții ale resurselor. Să considerăm, de exemplu un scenariu dinamic în care un robot se află între mai multe obiecte care se mișcă la rândul lor. Se așteaptă ca acești agenți să se miște după niște reguli de trafic, dar nu se întâmplă întotdeauna la fel. O situație în care restricțiile de timp de răspuns devin importante, în acest scenariu, este cea în care robotul trebuie să meargă dintr-un punct în altul într-un timp maxim determinat (timp limită global). În această situație, în timp ce robotul reacționează la schimbări pentru a evita coliziunile, trebuie să-și planifice un drum și sa-l urmeze într-un interval de timp determinat. Robotul are un timp limitat pentru a reacționa la schimbări (termene finale locale). Dacă robotul intenționează să se mute într-o arie liberă, ar trebui să profite de avantajul acestei situații rapid și să treacă, deoarece această stare va ține un timp limitat.

Un algoritm de rezolvare a problemelor de IA în timp real presupune 3 noțiuni:

restricții ale timpului de răspuns;

situații dinamice;

rezolvarea problemelor on-line;

1) Restricțiile timpului de răspuns se referă la limitări ale timpului total de planificare și redare a soluției. Pot fi împărțite mai departe în două clase: cele cu timp limită și cele cu timp de răspuns optimal. Situațiile cu termen final permit doar o anumită cantitate de timpînăuntrul căreia un sistem poate planifica și executa o soluție. Termenele finale pot fi fixe sau pot varia, de la caz la caz. A găsi o soluție în cazul unor timpi limită arbitrari este greu și de deseori este o problemă NP-completă. O altă clasă de probleme cu restricții ale timpului de răspuns introduce restricțiile de timp în timpul total de răspuns al sistemului. Timpul total de răspuns este suma timpilor cheltuiți pentru planificarea soluției și a celor pe care îi ia să execute soluția. Timpul total de răspuns optim nu este obținut prin planificarea soluției cu costuri minime de execuție, deoarece planificarea a astfel de soluții poate implica niște costuri de planificare foarte mari. Un compromis între timpul de planificare și calitatea soluției ar fi necesar pentru a optimiza timpul total de răspuns.

2) Situațiile dinamice sunt cele în care mediul se schimbă încet în timpul planificării. Cu cât se prelungește mai mult timpul alocat pentru planificarea unei soluții, cu atât mai învechită devine soluția la momentul execuției. Un sistem de planificare în timp real în această situație poate devia de la paradigma “planificării complete înaintea execuției“ spre paradigma “secvență de planificări parțiale urmate de execuție“, pentru a evita riscul ca planificarea să devină învechită și inutilă. În această ultimă paradigmă, planificatorul efectuează calcule pe un timp limitat, din care rezultă un plan parțial; apoi execută o mutare din plan pentru a avansa la următoarea stare. Planificatorul continuă aceste cicluri de planificare parțială urmată de execuție până la îndeplinirea sarcinilor sale.

Noțiunea de restricție timpului de răspuns este complet diferită de cea a situațiilor dinamice. Algoritmii proiectați să respecte restricțiile de timp de răspuns pot da greș în cazul situațiilor dinamice, dacă pornesc de la premisa că mediul este static în timpul planificării. Acești algoritmi vor întocmi un plan de execuție complet, pe baza stării sistemului de la începutul procesului de planificare, înaintea oricărei mișcări către faza de execuție. Într-o situație dinamică, acțiunile trebuie executate înainte ca ultimele lor consecințe să fie cunoscute. Cantitatea de planificare permisă înaintea fiecărei mutări este limitată de resursele disponibile și de schimbările care au loc în mediu.

3) Situațiile “on-line“ sunt cele în care mediul se schimbă rapid și neașteptat în timpul planificării. În aceste cazuri sunt necesare revizii majore ale soluțiilor în timpul planificării. Un sistem în timp real poate folosi componente reactive și un raționament nonmonotonic pentru a face față schimbărilor frecvente.

Va trebui să apelăm la noțiuni de inginerie software a specificațiilor, proiectării și analizei algoritmilor de rezolvare a problemelor de IA în timp real. Chestiunile de specificare și de analiză sunt foarte importante în validarea și verificarea sistemelor în timp real. Specificațiile formale ale sistemelor în timp real furnizează un set de cerințe pe care sistemul trebuie să le satisfacă, pentru a respecta îndeaproape restricțiile de timp ale taskului său. Analiza unei probleme specificate permite obținerea unor rezultate certe pentru cazul cel mai defavorabil și pentru cazul mediu. Aceste rezultate conduc la perspective realiste a cât de bine un rezolvitor de probleme în timp real poate respecta restricțiile într-o problemă specificată. Analiza unui algoritm propus pentru problema specificată poate verifica în ce măsură algoritmul îndeplinește cerințele problemei.

Multe dintre concepțiile existente relative la rezolvarea problemelor în timp real din domeniul inteligenței artificiale eșuează în a specifica o definiție precisă a problemei. De asemenea, nici nu pot furniza un set de cerințe concrete pe care soluția problemei trebuie să le satisfacă.

După specificarea și analiza problemei vom da o metodologie pentru analizarea algoritmilor de planificare în timp real. De asemenea vom introduce un nou algoritm de planificare în timp real numit DYNORA, pentru care am prevăzut analiza corectitudinii, completitudinii și a optimalității. Vom aplica metodologia noastră de analiză pe DYNORA și pe alt algoritm existent RTA. Rezultatele analizei vor arăta că DYNORA depășește RTA în medii statice și într-un model propus pentru un mediu dinamic.

Un important rol în analizarea algoritmilor în timp real este de a demonstra capacitatea acestor algoritmi de a manevra restricțiile de timp. Distribuția unui număr de sarcini complete poate ajuta la testarea acestei capacități. Un alt rol al analizării algoritmilor în timp real este acela de a demonstra capacitatea acestor algoritmi de a executa soluțiile planificate cu întârzieri minime. Vom demonstra că această capacitate poate fi testată prin analiza complexității cazului mediu în grafuri aleatoare.

2. Specificații

Specificarea unui concept se referă la codificarea conceptului într-un limbaj de descriere formală cu o semantică bine definită. Conceptele care vor fi specificate include problema, soluțiile problemei și rezolvitorul de probleme. O metodologie de specificație este un grup de metode, reguli și postulate utilizate pentru a analiza și specifica un set de concepte. Un exemplu de astfel de metodologie este cea de specificare teoretic-grafică. Această metodologie furnizează un limbaj grafic pentru a exprima codificat conceptele unei probleme, unei soluții și ale rezolvitorului de probleme. Specificarea unei probleme poate consta într-un graf, un nod de start și un nod țintă. Specificarea soluției va fi reprezentată de un set de muchii care formează drumul de la nodul de start către nodul țintă. Specificarea rezolvitorului va consta într-un algoritm de căutare în graf.

Avantajul specificării unei probleme este acela că permite examinarea unui set de cerințe pe care rezolvitorul trebuie să le satisfacă. A specifica o problemă îngăduie de asemenea analiza complexității acelei probleme. Rezultatele unei astfel de analize a complexității arată limitele a cât de bine se poate aștepta caalgoritmul să poată rezolva problema specificată. O specificație trebuie să conțină o definiție a problemei în termenii parametrilor care sunt cei mai importanți în rezolvarea acelei probleme. Un parametru important în specificarea unei probleme este mărimea unei instanțe a problemei, deoarece are implicații directe asupra cantității de timp de calcul de care are nevoie rezolvitorul pentru a produce o soluție. Specificarea unei probleme poate include de asemenea și metrici pentru măsurarea calității soluției. O soluție optimală a problemei poate fi caracterizată ca soluția care are valoarea minimă pentru metricile de calitate specificate.

Un rezolvitor de probleme din IA poate fi caracterizat prin două componente principale. O componentă este spațiul stărilor în care o soluție poate fi găsită. Un exemplu de problemă care poate fi reprezentată ca spațiu al soluțiilor este cea a fermierului care încearcă să treacă pisica, pasărea și grăunțele dincolo de râu, după cum am discutat ăn introducere. Cealaltă componentă a rezolvitorului de probleme din IA este algoritmul de căutare folosit pentru cătarea soluției. Un spațiu al stărilor este reprezentat printr-un graf G(V,E). o stare din G este reprezentată printr-un nod viєV. Anumite perechi de stări sunt conectate una cu alta prin muchii (vi vj)єE. Cele două noduri reprezentând o muchie sunt stările conectate prin acea muchie, din spațiul stărilor G. Asociat cu această muchie (vi vj) este un cost de execuție cevi vj, care este privit ca și costul transformării din vi în vj, sau costul traversării muchiei (vi vj). Costul de execuție al unei muchii este calculat prin măsurarea cantității și costului unitar al resurselor consumate pentru a traversa acea muchie. De exemplu, timpul necesar pentru a traversa o muchie poate fi folosit pentru a reprezenta costul său de execuție. Costul de planificare al unei muchii cpvi vj este cantitatea de planificare cerută pentru a ajunge la decizia de a traversa muchia (vi vj), ca parte a soluției planificate. Costul de planificare este calculat prin măsurarea cantității și a costului unitar al resurselor consumate în timpul planificării. De exemplu, timpul consunat de un planificator poate fi folosit pentru a reprezenta costul de planificare. În general, costul de planificare cpvi vj depinde de algoritmul de căutare, deoarece este costul cumulativ al examinării unui set de variante la nodul vi și al alegerii muchiei (vi vj) spre a fi traversată. Costul de planificare nu este diponibil în partea de definire a problemei.

Fiecărui graf îi sunt asociate două noduri speciale: nodul inițial s și nodul final g . Problema de căutare a drumului se referă la problema găsirii căii pi care conectează nodurile s și g prin muchii existente în graf. O cale pi este reprezentată printr-o secvență de muchii {(s,v1), (v1,v2),…,(vm,g)}. Asociat cu calea pi din graf este un cost de execuție Ce, astfel încât: Ce=Σ(vl vm)єpicevl vm, și un cost de planificare Cp, care depinde de algoritm. Discuția de mai sus poate fi generalizată pentru probleme de căutare a drumului cu mai multe noduri țintă. În problema găsirii drumului optim care trece prin toate nodurile țintă, ordonarea secvențelor în care țintele vor fi vizitate este o problemă grea. Tema țintelor multiple depășește scopul acestui capitol.

Într-un spațiu dinamic al stărilor, costurile de execuție cevi vj (t) sunt funcții e timp pentru a reflecta schimbările din mediu de-a lungul timpului. O muchie din acest graf poate înceta să mai existe pentru o scurtă perioadă de timp. Aceatsa se reprezintă printr-un cost de execuție de tipul ∞ asociat unei muchii pentru o scurtă perioadă de timp. În continuare, vom specifica un simplu model de schimbare în mediu dinamic. Modelul de schimbare propus se bazează pe procesul Markov. Procesul Markov selectat este folosit pentru a schimba costul muchiilor într-un graf pentru a simula o lume în mișcare. Un cost cevi vj (t) în acest model este considera a fi o variabilă aleatoare și o funcție de timp. Modificarea costului unei muchii în timp este modelată printr-un proces Markov limitat, după cum urmează:

Limitele procesului Markov păstrează distribuția costului muchiei între anumite granițe, pentru a nu devia prea mult de la medie. Aceste limite satisfac proprietatea următoare: 0 ≤ cevi vjmin ≤ cevi vjmax. Dacă cevi vjmax = ∞, atunci o muchie existentă poate deveni virtual inexistentă într-un interval de timp finit, din moment ce costul său devine mult prea mare decât costul celorlalte muchii. O soluție optimală la problema de căutare a drumului, în modelul mediului dinamic propus, este o cale cu cel mai mic cost mediu total al planificării și execuției la un moment dat sau într-un interval.

În fine, discutăm noțiunea de grafuri aleatoare pentru a specifica și comportamentul cazului mediu al rezolvitorilor de probleme în timp real. Definim un graf aleator ca fiind un graf G(V,P) în care fiecare muchie există cu o anumită probabilitate P. în cazul în care P = 1, graful este total conectat; adică fiecare nod este conectat la toate celelalte noduri prin câte o singură muchie. P = 0 reprezintă un graf fără muchii. Alegerea lui P influențează viitorul număr de drumuri-soluție cu anumite lungimi.

Restricțiile timpului total de răspuns al proceselor de planificare și execuție din cadrul rezolvitorilor de probleme în timp real poate fi specificat după cum urmează: Timpul total de răspuns este caracterizat prin suma timpilor consumați pentru planificarea unei soluții și pentru execuția acesteia. Dacă aceste costuri, de execuție Ce și de planificare Cp pentru drumul unei sooluții în spațiul stărilor sunt calculate în termeni de timp, timpul total de răspuns al unui plan poate fi calculat ca Ce + Cp. Constrângerile stricte asupra timpului total de răspuns sunt termene limită în cantitatea de timp disponibilă pentru planificarea și execuția unei soluții. În aceste situații, este nevoie de un algoritm de planificare pentru a căuta o cale de la nodul inițial către cel final și a executa această cale, adică să traverseze toate muchiile până la nodul țintă înainte de a atinge vreunul din termenele limită. Situațiile cu termene finale cer garanții asupra timpului total de răspuns. Alte constrângeri de timp, mai puțin stricte, sunt condiții optimale asupra timpului total de răspuns. Aceste situații, din moment ce nu reprezintă necesități stricte, cer întârzieri minime în planificarea și execuția unei soluții. O stare țintă, în aceste situații, trebuie fi atinsă într-un interval de timp cât mai mic cu putință (Ce + Cp = min). În analizarea algoritmilor referitori la problemele de planificare și căutare în timp real, vom ține cont de abilitatea acestor algoritmi de a se încadra în termenele limită, cât și de capacitatea lor de a minimiza timpul total de răspuns.

3. Studiu de caz

În aceastã secțiune vom determina un algoritm de căutare a drumului in timp real pentru a demonstra tehnologia descrisă mai devreme. Vom defini ce înseamnă problema de planificare a drumului și vom deduce rezultatele pentru cazul de complexitate maximă pentru o problemă particulară, atât în mediu static, cât și în mediu dinamic. Vom da o descriere a doi rezolvitori de probleme candidati, (RTA si DYNORA), care se preteaza la problema de planificare a drumului in timp real. DYNORA este noul nostru algoritm de cautare, care este capabil de a manipula restrictii de timp in medii dinamice. Vom demonstra ca noul algoritm este corect si complet in mediu static. Ca rezultat al cazului cel mai nefavorabil, vom arata ca acest algoritm este incomplet in medii dinamice, in care costurile muchiilor pot creste foarte mult. Apoi vom furniza niste date dintr-un det de experimente pentru a testa capacitatea acestor algoritmi de a se supune restrictiilor de timp si de a minimiza timpii de raspuns. Vom face o analiza a datelor, bazandu-ne pe metodologia descrisa mai devreme. Analizele vor arata ca DYNORA este capabil de a se descurca in conditiile unor restrictii mult mai stranse, cu un grad de siguranta mai mare decat in cazul RTA. Mai mult, aceste rezultate vor arata ca DYNORA depaseste RTA si in cazul mediilor dinamice.

Sectiunea 5.A a acestui studiu de caz prezinta o specificare a problemei si cateva chestiuni de analiza. Specificarea rezolvitorilor de probleme si analizele corectitudinii si completitudinii sunr prezentate in sectiunea 5.B, iar sectiunea 5.C furnizeaza cateva analize empirice ale rezolvitorilor de probleme.

A. Specificarea si analiza problemei de planificare a drumului in timp real

Cautarea solutiei optime in timp real (ORTS – Optial Real-Time Search) este problema gasirii si traversarii celei mai scurte cai intre doua noduri astfel incat timpul total de raspuns pentru o astfel de cale este minim. In general, caracterizarea costurilor de planificare CpORTS intr-o maniera independenta de algoritm este dificila. Costul de planificare al unei muchii poate include efortul de a examina un alt set de muchii din vecinatate, lucru care depinde de algoritmul de cautare. Lipsa unei definitii independente de algoritm a costurilor de planificare in rpoblema de ORTS face dificila caracterizarea formala a dificultatii sale. Totusi, este posibila evaluarea dificultatii unei probleme artificiale asemanatoare, numita SORTS (Simple ORTS), unde costul e planificare asociat unei muchii (CPvivjSORTS) este presupus independent de orice algoritm si reprezinta costul minim de planificare pentru acea muchie. Notiunea de cost minim de planificare pentru o muchie poate fi interpretata ca timpul consumat pentru a obtine o informatie referitoare la muchie inainte de a o include in drumul solutie. Notam ca problemele SORTS si ORTS sunt asemanatoare. Notiunea de cost de executie pentru un drum este identica in ambele probleme, iar costul de planificare in problema SORTS reprezinta o subestimare a costurilor de planificare din problema ORTS (CpSORTS ≤ CpORTS, unde CpSORTS este costul de planificare pentru o problema in SORTS, iar CpORTS este costul de planificare pentru o problema in ORTS). In paragrafele urmatoare, vom arata ca problema SORTS este NP-dificila. Presupunem, datorita relatiei intre SORTS si ORTS, ca ORTS este cel putin la fel de grea ca SORTS. Notam ca presupunerea independentei CPvivj de algoritmul de cautare este artificiala si ca aceasta presupunere nu este folosita in algoritmii de cautare in sectiunile viitoare.

Vom defini problema SORTS dupa cum urmeaza: Dandu-se un graf G(V,E), un nod de start s, un nod tinta g, costurile de executie ale muchiei cevivj, si costurile minime de planificare ale muchiei CPvivjSORTS, problema este de a gasi si de a traversa drumul cel mai scurt care leaga s si g intr-un timp total minim de raspuns (CpSORTS + Ce este minim). Se poate demonstra ca problema SORTS este NP-dificila. Vom arata acest lucru folosind metoda reductiei polinomiale. Folosind aceasta metoda formulam intai problema noastra ca o problema de decizie. Astfel de prebleme au doar doua solutii posibile: “da” si “nu”. Vom demonstra apoi ca problema noastra este NP-completa prin:

a arata ca problema P1 este in N printr-un algorit de timp polinomial nedeterministic, care rezolva P1

selectand o alta problema P2, cunoscuta ca fiind NP-completa

construind o transformare f din P2 la P1; si

aratand ca f poate fi calculata intr-un timp polinomial

Presupunem ca lungimile si costurile de planificare asociate fiecarei muchi nu sunt toate egale. Vom masura marimea problemei luata drept exemplu facand suma numarului nodurilor si a numarului muchiilor. Formulata ca o problema de decizie, SORTS poate fi definita prin urmatoarea teorema:

Teorema 1: Fiind data o instanta 1 a problemei SORTS si intregii pozitivi L&P, atunci a raspunde daca exista un drum al costului de executie egal sau mai mic decat L cu un timp de raspuns total egal sau mai mic decat P+L este o problema NP-completa.

Demonstratie: Primul pas al demonstratiei consta in a arata ca problema SORTS este NP. Pentru a arata acest lucru, vom da un algoritm polinomial nondeterministic de timp pentru a rezolva versiunea de decizie a problemei SORTS (DSORTS). Algoritmul de rezolvare DSORTS, descris in fig. X, face doar acest lucru. Acest algoritm presupune ca exista un alt algoritm, Ghiceste-un-Drum, care poate banui nedeterministic o cale-solutie, care leaga nodurile s si g intr-un graf G(V,E). deoarece marimea drumului solutie este marginita polinomial, rezolvarea prin DSORTS consuma un timp polinomial pentru a ghici si verifica solutia.

Apoi, vom selecta o problema NP-completa pe care o putem reduce la o problema SORTS in timp polinomial. Aceasta va fi problema “celui mai scurt drum cu restrictii prin ponderi” (SWCP – shortest weight-constrained path), si poate fi definita dupa cum urmeaza: dandu-se un graf G(V,E), lungimea l(e)εZ+ (unde Z+ este multimea tuturor intregilor pozitivi), ponderile w(e)εZ+ pentru fiecare eεE, nodurile speciale s, vεV, si intregii pozitivi K si W, exista oare un drum simplu in G de la s la t, cu ponderea totala W sau mai putin si lungimea totala K sau mai putin?

Definim f(I’) o functie care transforma o instanta I’ din problema SWCP intr-o instanta I din problema SORTS. Trebuie sa aratam ca o astfel de functie exista si poate fi calculata intr-un timp polinomial. O transformare directa polinomiala de la I’ la I este dupa cum urmeaza: G in I’ este acelasi ca si G in I, adica grafurile celor doua probleme au aceeasi multime de noduri si de muchii. Fiecare l(e) in I’ are un corespondent cevivj in I , astfel incat l(e)=cevivj iar e este muchie in E care leaga nodurile vi si vj (vi, vj εV). In mod similar, fiecare w(e) din I’ are un corespondent cpvivjSORTS + cevivj in I , astfel incat

w(e)= cpvivjSORTS + cevivj iar e este o muchie in E care leaga nodurile vi si vj (vi, vj εV). Este evident ca functia de transformare f poate fi calculata intr-un timp polinomial. Am aratat ca problema DSORTS este NP. De aici, tragem concluzia ca DSORTS este NP-completa. O cerinta pentru ca problema SWCP sa fie NP-completa este ca ponderile w(e) si lungimile l(e) sa nu fie toate egale. Aceasta cerinta ar trebui sa ramana de asemenea adevarata si pentru probleme simple de cautare in timp real . deoarece DSORTS este NP-completa, SORTS este NP-dificila.

Discutia de mai sus defineste dificultatea NP a problemei SORTS intr-un mediu static, in care lungimile muchiilor raman aceleasi in timp. Credem ca problema SORTS intr-un mediu dinamic, unde au loc schimbari in tim, este cel putin NP-dificila. Motivul este ca modelul static este un caz simplu, special, de mediu dinamic in care rata de schimbare este 0. Daca problema SORTS este NP-dificila intr-un caz mai simplu, atunci ea va fi cel putin NP-dificila intr-un caz mai complex.

Una din implicatiile rezultatelor de mai sus este ca ar trebui sa cautam solutii suboptimale pentru problema de cautare in timp real, sau solutii pentru cazuri speciale de probleme care sunt mai simplu de rezolvat. Acest lucru se va reflecta in algoritmii pe care ii vom dezvolta pentru problema si pentru instantele problemei pe care le-am ales sa le rezolvam. Alte implicatii ale acestor rezultate se regasesc in corolarele urmatoare.

Corolar 1: Problema cautarii unui drum de lungime optima intr-un timp limitat este cel putin NP-dificila.

Demonstratie: Problema de decizie DSORTS sustine ca a gasi un drum de lungime mai mica decat L intr-un timp mai scurt decat L+P este NP-completa. Daca P+L reprezinta termanul final inauntrul caruia algoritmul trebuie sa gaseasca o solutie optima, atunci se folosest corolarul 1.

O alta consecinta a teoremei de mai sus este ca prioblema de optimizare a solutiei in conditiile respectarii termenului limita, este NP-dificila. Aceasta consecinta este reflectata in urmatorul corolar.

Corolar 2: Problema cautarii unui drum de lungime optima, in timp ce se optimizeaza timpul otal de raspuns este cel putin NP-dificila.

Garantarea optimalitatii timpului total de raspuns este diferita in functie de termenele finale. Timpii de raspuns sunt furnizati de algoritmii care rezolva problema, in timp ce termenele finale sunt impuse de cerintele taskului. Timpii de raspuns optimali garantati sunt diferiti de cazul in care se verifica anumiti timpi de raspuns, rt. Un algoritm care produce un anume timp de raspuns, rt, poate garanta respectarea restrictiilor finale care sunt mai mari decat rt. Daca termenul final ajunge inaintea timpului de raspuns garantat, totusi acel timp limita nu poate fiu respectat.

B. Specificarea algoritmilor de cautare a drumului in timp real

In aceasta sectiune vom specifica doi rezolvitori de probleme in timp real ca algoritmi de cautare in graf. Acesti rezolvitori de probleme sunt RTA si DYNORA. Ambii. Algoritmi lucreaza in cicluri de cautare partiala urmata de executie. Paradigma cautarii partiale urmate de executie ajuta acesti algoritmi sa faca fata schimbarilor dim mediu. Fiecare din cei doi algoritmi folosesc o functie de evaluare pentru a se ghida in cautarea partiala, ca in algoritmul A (descris in [23]). Functia de evaluare f a unui nod este calculata ca suma a doua parti: g si h (f = g + h; In A, g reprezinta costul actual al drumului din nodul de start pana in nodul evaluat la momentul curent in graf, iar h reprezinta costul estimat al drumului din nodul curent pana in nodul tinta. Deseori h este numita functie euristica. S-a aratat ca A va gasi cea mai scurta cale in graf , dandu-se o functie euristica h care subestimeaza costul drumului partial din nodul curent pana in nodul tinta.

RTA si DYNORA difera din punct de vedere al criteriului de terminare folosit pentru a sfarsi cautarea partiala in fiecare ciclu iar in planificarea drumului timpul este alocat in fiecare ciclu. Criteriul de terminare al DYNORA ii permite sa manipuleze restrictiile de timp, la fel de bine ca si caracteristicile mediului dinamic. De asemenea, cei doi algoritmi se deosebesc prin modul in care controleaza priocesul de cautare. RTA face o cautare folosind o limita de adancime fixata pentru fiecare vecin al nodului curent. DYNORA duce la bun sfarsit un singur A cu un criteriu de terminare bazat pe planificarea si executia costurilor. El aloca efortul de planificare la granita nodurilor proportional cu promisiunea lor, in timp ce RTA aloca eforturi de planificare comparabile pentru toti vecinii nodului curent.

RTA: La fiecare ciclu, RTA(n) creeaza mai intai nodurile succesoare starii curente. Starea curenta este actuala pozitie a sistemului. Parametrul n corespunde numarului de noduri descendente evaluat pentru fiecare vecin in timpul ciclului. Cu fiecare nod succesor creat sunt calculate distanta sa estimata fata de tinta (h), costul din nodul curent (g) si suma lui h cu g. formula distantei euclidiene este folosita pentru a calcula valorile lui h. Aceasta formula euristica este monotonica si este garantata pentru a produce solutii optime in A. In cazul RTA, aceasta forula euristica permite reducerea substantiala a nodurilor de frontiera fara pierderea unei informatii valoroase in gasirea unei solutii partiale. De observat ca, spre deosebire de A, in care g este valoarea costului total de pana acum, adica din nodul de start pana in nodul succesor curent, in RTA, g este valoarea costului din nodul curentla fiexare din nodurile sale succesoare. Valorile h sunt calculate printr-o cautare anticipata. Algoritmul presupune ca, cu cat mai mare este numarul de anticipari (n), cu atat mai precisa va fi valoarea estimata a lui f (g+h). totusi, am intalnit cazuri in care numarul crescand de anticipari a dus algoritmul la solutii mult mai costisitoare. De asemenea, ar fi de observat ca in timp ce anticiparile mai mari sunt in general folositoare in a gasi cai mai scurte catre tinta (cost mai mic de executie), ele necesita mai multa procesare si planificare (costuri de planificare mai mari). Odata ce au fost determinate toate nodurile succesoare si valorile f ale lor, algoritmul triaza aceste noduri dupa valorile f. Ndul succesor cu cea mai mica valoare f este ales ca urmatoarea miscare fizica in algoritmul RTA. Acest proces este repetat pana este gasita o slutie.

In timp ce acest algoritm nu poate garanta terminarea in cazul grafurilor fara solutii, el suigur nu va intepeni in minime locale si cicluri in graf. Acest lucru este realizat prin excluderea ciclurilor si a cailor care se termina intr-un punct mort, si prin pastrarea valorii h a celei de-a doua cea mai buna cale la fiecare punct de decizie. Acest allgoritm s-aq aratat a fi corect si complet in medii statice.

DYNORA: face planificarea si executia ciclurilor in mod repetat pana cand un nod tinta este gasit, presupunand ca graful are o solutie. Un ciclu planificare-executie incepe cu dirijarea unei cautari euritice (faza de planificare) pentru urmatoarea miscare, pornind din starea curenta (nod) din graf. Cautarea continua din satrea de inceput pana la o adancime variabila in graf cand urmatorul criteriu de oprire este satisfacut:

Cp ≥ aCe. (1)

Acest criteriu de oprire face un compromis intre costul de planificare total (Cp) de pana acum, acumulat in timpul intregii faze de planificare a ciclului curent, si cel mai bun cost de executie estimat (Ce) al unui drum complet, gasit in timpul fazei de planificare a cucluuli curent. Acest compromis tine cont de utilitatea functiei euristice descoperita in faza curenta de planificare in comparatie cu cantitatea de planificare facuta pentru a gasi solutia.

In timpul fazei de executie, algoritmul urmeaza cea mai buna cale de actiune descoperita in timpul fazei de planificare anterioare. In cazul planificaii drumului pebtru un robot, de exemplu, faza de executie consta in mutarea fizica a robotului din pozitia sa curenta in urmatoarea sa pozitie, care a fost aleasa dintr-o multime de optiuni disponibile. Fig. 4 contine un pseudocod pentru algoritmul DYNORA.

Cp in DYNORA este determinat de un numar de noduri care au fost evaluate in timpul cautarii. Acestea sunt noduri ale carori valori h, g si f au fost calculate, unde h este distanta estimata din nodul evaluat pana la tinta, g este costul mutarii in parintele nodului evaluat pana la nu=odul evaluat, iar f este suma lui h cu g. Ce este calculata prin adaugarea la actuala lungime a drumului curent la distanta estimata intre nodul curent si nodul tinta.

Pentru a explica avantajul compromisului intre costul de planificare si cel de executie, sa onsideram RTA ca un exemplu al unui lgoritm in timp real. RTA foloseste o anticipare fixata, specificand o granita statica pentru cautarea anticipata. Cand aceasta granita de anticipare este atinsa, RTA opreste cautarea anticipata indiferent de calitatea solutiei gasite si indiferent de cantitatea de cautare efectuata. In anumite cazuri, cautarea se termina prematur, rezultand o solutie slaba din punct de vedere al costului. In alte cazuri, prea multa cautare este facuta pentru un castig mic in calitatea solutiei. In DYNORA, granita de cautare este atinsa cand se obtine un balans intre costul de cautare si cel de executie (criteriul de oprire al inegalitatii este indeplinit). De aici rezulta ca adancimea cautarii in acest algoritm este determinata dinamic.

Cand criteriul inegalitatii este satisfacut, cea mai mica valoare f gasita pana acum este returnata primului nivel al algoritmului. Nodul succesor cu cea mai mica valoare f este ales ca urmatoarea mutare fizica pentru algoritmul DYNORA. Acest proces se repeta pana este gasita o solutie.

Un parametru important implicat in compromisul intre Cp si Ce este alfa (vezi inegalitatea (1)). Valoarea potrivita a lui alfa depinde foarte mult de anumite caracteristici ale grafului si ale aplicatiei. Exemple de astfel de caracteristici sunt marimea grafului, factorukl de ramificare, si timpul disponibil pentru planificare. Regula generala este de a aalege un alfa mare cand spatiul de acutare este mic, factorul de ramificare este si el mic. Iar timpul pentru planificare este lung. Un alfa mic este ales cand spatiul de cautare este larg, factorul de ramificare este mare, si timpul pentru planificare este scurt. Rationamentul intuitiv din spatele acestor euristici este ca un graf mai mare sau un factor de ramificare mare impreuna cu un alfa mare poate creste considerabil cantitatea de planificare. De asemenea, cand timpul pentru pklan este scurt, evident ca trebuie redusa cantitatea de planificare in fiecare ciclu plan-executie.

DYNORA garanteaza terminarea daca un drum solutie din nodul de start pana uin nodul tinta exista intr-un graf finit cu muchii bidirectionale. Este de asemenea capabil sa iasa din minime locale si cicluri ale grafului. Acest lucru este facut prin eliminarea ciclurilor si a drumurilor ce se termina intr-un punct mort, si prin pastrarea valorii h a celei de-a doua cea mai buna cale la fiecare punct de decizie. In continuare, vom prezenta cateva rezultate formale cu privire la algoritm si performanta sa. Vor urma cateva rezultate empirice bazate pe experimente de comparare a performantei.

Teorema 2: Dandu-se o problema, daca DYNORA inceteaza a mai cere o solutie, raspunsul pe care il produce rezolva de fapt problema data.

Demonstratie: O solutie este corecta daca ea conecteaza starea initala cu cea finala prin mutari legal admise. Algoritmul DYNORA incepe totdeauna ciclurile sale plan-executie din starea initiala. Apoi executa planurile sale partiale pana cand se anunta gasirea unei solutii. Astfel, daca algoritmul atinge starea finala si aceasta este verificata cu succes, el a gasit solutia corecta. Este intr-adevar cazul cand algoritmul executa si ultima mutare, cea care il conduce la starea finala.

Prin demonstrarea urmatoarei teoreme, vom arata ca DYNORA, sub un set de presupuneri, garanteaza obtinerea unui raspuns (gasirea starii finale) daca o astfel de solutie exista. Vom afisa rezultatele noastre pentru cazul general al grafurilor care pot include cicluri. Presupunem un spatiu de cautare finit. Intr-un spatiu infinit, valorile euristice care contin erori pot face ca algoritmul sa urmeze un drum infinit, care nu va gasi niciodata solutia. Presupunem de asemenea costuri pozitive ale muchiilor, care raman constante in timp. In demonstratia urmatoarei teoreme, vom relaxa completitudinea algoritmului in medii dinamice. In final, vom presupune muchii bidirectionale pentru a permite algoritmului sa se intoarca din drumuri cu punct mort.

Teorema 3: Intr-un patiu al problemei finit cu muchii bidirectionale, costurile muchiilor pozitive si statice si valorile euristice finite, unde exista o cale care uneste nodul de start cu cel final, DYNORA garanteaza sa gaseasca o cale.

Demonstratie: Vom demonstra aceasta teorema prin contradictie. Presupunem ca negarea teoremei este adevarata, adica exista o cale din nodul initial catre cel final in spatiukl de cautare, si ca DYNORA nu gaseste niciodata aceasta cale. Pentru ca aceasta situatie sa fie adevarata, trebuie sa existe un ciclu in graf care nu include nodul tinta, in care algoritmul se invarte la infinit. Pe de alta parte, este adevarat ca daca exista o cale pornind din nodul initial, nodul tinta poate fi gasit din fiecare nod din componenta grafului din care fac parte nodul initial si cel tinta. Deci trebuie sa existe o muchie care iese afara din ciclu si conduce la nodul tinta. Trebuie sa aratam acum ca algoritmul poate parasi acest ciclu. Fiecarui nod din graf ii este asociata o valoare euristica care este ori calculata daca nodul nu a amai fost vizitat inainte) sau regasita (daca nodul a fost vizitat inainte si astfel a mostenit a doua cea mai buna valoare f a copiiilor sai). In mutarea de la un nod x la nodul copil C1, algoritmul calculeaza sau regaseste valorile fci ale copiilor sai, adauga costurile pozitive ale muchiilor corespunzatoare (gx(ci)), si se muta spre copil (C1 in acest caz) cu cea mai mica valoare rezultata. El asigneaza de asemenea a doua cea mai buna valoare fci ca fiind valoarea euristica a nodului x (h(x) fci). Deoarece a doua valoare este mai mare sau egala cu cea mai mare valoare, si valoarea noii stari C1, este strict mai mica decat valoarea sa dupa ce costul muchiei din vechea stare x I-a fost adaugat (datorita costurilor pozitive ale muchiilor, valoarea nodului x trebuie sa fie strict mai mare decat valoarea nodului C1. Astfel , valoarea vechii stari este totdeauna mai mare decit valoarea noii stari. Acum vom lua in considerare nodul cu cea mai mica valoare din ciclu ca fiind starea curenta. Inainte sa parasim aceasta stare ,o noua valoare mai mare este asociata acestui nod. Mai mult, pina sa intilnim acest nod pentru a doua oara, valoarea sa creste din nou datorita rationamentului de mai sus. Daca acest lucru e adevarat pentru nodul cu cea mai mica valoare, atunci este adevarat pentru toate nodurile din ciclu. In cazul unor costuri statice ale muchiilor,valorile tutulor muchiilor din ciclu cresc monoton si nelimitat. Va veni in sfirsit timpul cind valoarea nodului de pe un drum din afara acestui ciclu este mai mica decit valoarea vecinului sau din ciclu. In acest moment,algoritmul va iesi din ciclu. Aceasta este o contradictie cu presupunerea noastra de ciclare infinita. Concluzionam, ca in conditiile teoremei noastre, nu exista ciclari infinite. Aceasta demonstreaza teorema noastra pentru cazul static.

Urmatoarea teorema se refera la completitudinea DYNORA in medii dinamice. Vom arata, printr-un exemplu, ca in medii dinamice, in general, unde costurile miscarilor pot creste foarte mult, DYNORA nu este un algoritm complet. Aceasta inseamna ca DYNORA poate oscila intre un set de noduri sau poate cadea intr-un ciclu infinit si sa nu gaseasca niciodata o solutie, chiar daca o astfel de solutie exista.

Teorema 4: DYNORA nu este complet in medii dinamice in care costurile muchiilor sunt pozitive si pot creste infinit de mult.

Denonstratie: Consideram urmatorul exemplu, al unui graf cu costuri dinamice le muchiilor, ilustrat in fig. 5:

Costurile muchiilor sunt initializate cu 1. Valoarea euristica a fiecarui nod este scrisa in casute dedesubtul fiecarui nod. Presupunem nodul S in pozitia de start si vrem sa planificam un drum pana la nodul G. de asemenea, presupunem ca anticiparea lui DYNORA este astfel setata incat algoritmul poate privi catre succesorii imediati ai unui nod in timp ce se afla in cursul fazei sale de planificare. In nodul S avem doua alternative. Una este sa alegem muchia Sa (care leaga nodurile S si a), iar cealalta este sa alegem muchia Sb (care leaga nodurile S si b). Valoarea f a traversarii Sa este costul traversarii Sa, care este initial 1, plus valoarea euristica a nodului a, care este 5. Tot asa, valoarea f a traversarii Sb este 5, initial. Astfel, algoritmul selecteaza nodul cu cea mai mica valoare f pentru a se muta intr-acolo, adica nodul b, si pastreaza valoarea euristica a nodului a, (adica 6), ca valoare euristica a nodului S. Din nodul b, algoritmul are posibilitatea sa mearga in nodul c a carui valoare f este 8, sau inapoi catre nodul S a carui valoare f este acum 7. Evident, DYNORA merge inapoi catre S si pastreaza valoarea f a lui c (care este 8), ca valoare euristica a lui b. Acum, sa presupunem ca in timpul acestei perioade costul muchiei a a crescut la 5, crescand si valoare f a lui a la 10. In acest punct, intre alternativa intoarcerii la b, cu o valoare f de 9, si alternativa mutarii catre a, cu o valoare f de 10, DYNORA alege sa se intioarca la b. Sa presupunem acum ca, de asemenea, costul muchiei bc a crescut la 5, crescand valoarea f a lui c la 12. In acest punct, algoritmul va alege sa se intoarca la S, a carui valoare f este acum 11. Este usor de observat acum ca, in cazul n are costurile muchiilor Sa si bc continua sa creasca cu 3 de fiecare data, algoritmul va osclia intre nodurile b si S tot timpul, fara sa gaseasca vreodata tinta prin nodul a.

C. Analiza experimentala

In aceasta sectiune vom prezenta rezultatele a doua experimente de comparare a performantelor. Primul experiment evalueaza algoritmii in capacitatea lor de a respecta termenele limita. In aest experiment, am caracterizat prbabilitatea indeplinirii unei cautari in termenul limita fixat. Al doilea experiment evalueaza algoritmii in capacitatea lor de a reduce timpul total de raspuns in ambele medii, static si dinamic.

Evaluarea respectarii termenului limita: Un factor important luat in considerare la evaluarea algoritmilor in timp real este capacitatea acestor algoritmi de a manipul constrangeri de timp stricte. In aceasta sectiune prezentam rezultatele unor experimente care au fost proiectate sa compare preformantele algoritmilor DYNORA si RTA in respectarea termenelor limita. In dirijarea acestor experimente am folosit metodologia compararii performantelor bazata pe aplicatii controlate artificial. Aplicatia este specificata in termenii unor parametrii ai modelului de specificare, cum ar fi numarul de noduri si de muchii. Parametrii de interes sunt determinati prin cercetarea modelarii unor aplicatii alternative din lumea reala in termenii unui model de specificare. De exemplu, parametrii de interes pentru problema de planificare a drumului includ gradul de cionectivitate al grafului precum si marimea acestui graf. Performanta este masurata in termenii unitatilor modelului, cum ar fi numarul de noduri adaugate, sau lungimea unui drum solutie. Algoritmii de cautare sunt executati pentru a obtine date despre performanta acestor algoritmi. Aceste date pot ajuta la cunoasterea parametrilor ce contin performanta comparativa a algoritmilor de cautare. Concluziile pot fi extrapolate la aplicatii in timp real prin caracterizarea acestor aplicatii in termenii variabilelor modelului si prin determinarea valorilor parametrilor de control al performantei.

Planificarea drumului a fost aleasa ca domeniu de comparatie pentru experimente si pentru compararea performantelor. Planificarea drumului este problema gasirii unui drum solutie intr-un graf care leaga nodul initial de nodul tinta. Acest concept este foarte important in numeroase domenii din industrie si cercetare. Exemple de probleme care sunt direct legate de acest concept sunt planificarea on-line a robotului, planificarea dryumului in medii dinamice, teleconferinta (multimedia), rutarea mesajelor in retele de calculatoare si sisteme de navigare on-line. Informatia in toate aceste domenii este reprezentata prin grafuri. Ilustrata in acest fel, problema va fi redusa la a gasi drumurile care leaga anumite noduri unul de altul. Acest experiment a fost dirijat intr-un graf generat aleator, G(V,E), cu 30 de noduri. V in graf reprezinta multimea nodurilor, iar E reprezinta muchiile grafului. Nodurile grafului sunt descrise prin coordonatele lor euclidiene intr-un siste de coordonate de 100 X 100. Muchiile grafului sunt descrise prin cele doua noduri de la capete. Costul de executie cevivj reprezinta unitati de timp necesare pentru a traversa muchia (vivj). Costul de planificare cpvivj reprezinta timpul cumulat pentru a planifica si a alege muchia (vivj). Costul de planificare este calculat dintr-un numar de noduri si muchii examinate in timpul planificarii si timpul mediu necesar pentru a duce al bun sfarsit aceste operatii pe o platforma de executie (SUN SPARC SLC). Marimea grafului este caracterizata de numarul de noduri din graf (n). gradul de conectivitate beta reprezinta raportul intre numarul de muchii existente | E | si numarul de muchii dintr-un graf complet conectat. Astfel:

beta = (x + y)/2 (2)

Pentru a evita generarea unui graf cu drumuri solutie triviale, numarul de muchii (| E |) a fost limitat prin urmatoarea restrictie:

n – 1 « E « n (n – 1) / 2 (3)

Granita inferioara garanteaza ca graful nu are forma unui arbore iar granita superioara garantaeza ca graful nu este complet. Aceste limite ne ajuta sa evitam spatii mici ale solutiilor (multimea tuturor drumurilor solutie), ca si drumurile banale catre tinta. Ecuatiile (2) si (3) conduc la urmatoarele limite ale beta:

0 ≤ 2/n « beta « 1, pentru orice n > 1.

Pentru graful acestui experiment, beta = 4/n.

Pentru fiecare pereche posibila de noduri initial si tinta din graf (un total de 870), opt seturi de date au fost colectate. Patru din cele opt corespund lui RTA(n), pentru n = 1, 2, 3 si 4. Celelalte patru seturi corespund lui DYNORA(alfa) = 0.05, 0.1, 0.5 si 1.

In fata unor restrictii de timp riguroase, un algoritm trebuie sa garanteze rezultate intr-un timp limita dat. Ceea ce inseamna ca un algoritm trebuie sa specifice cantitatea minima de timp care ii este necesara pentru a garanta completitudinea tuturor proceselor cu care a fost insarcinat. Alternativ, un algoritm este de asteptat sa furnizeze acele procese care pot fi competate in orice timp limita. Pentru problema noastra de planificare a drumului intr-un graf al spatiului starilor, media, cel mai bun si cel mai slab timp total de raspuns pentru aceasta cautare, in multimea tuturor posibilelor noduri initiale si finale, va furniza distributia completarii sarcinilor in timp. Aceasta distributie ne va permite sa calculam numarul de procese care vor fi completate garantat inauntrul termenelor limita aleatoare.

Figurile 6 – 12 ilustreaza datele cautarii unui drum intre toate nodurile initiale si finale posibile in graful specificat. Unitatile de timp pentru terenele finale si variabilele timp de raspuns sunt unitati logice de timp. Timpul de planificare depinde de platforma de executie, care face dificila atribuirea unor unitati absolute. Unitatile noastre logice de timp pentru planificarea timpului reprezinta aproape 1 ms de lucru pe o platforma SUN SPARC SLC. Unitatea logica de timp pentru timpul de executie reprezinta timpul de traversare pentrui muchia medie din graf. Fig. 7 si 9 descriu densitatea de populatie a instantei problemei in timpul de raspuns. Densitatea de populatie reprezinta un numar de instante ale problemei cu un timp de raspuns dat. Celelalte figuri reprezinta distributia populatiei pentru instante ale problemei, peste termenele limita. Distributia populatiei reprezinta procentul de instante ale problemei care pot fi rezolvate intr-un timp de raspuns mai mic decat termenul limita dat.

Fig. 6 si 7 demonstreaza efectul parametrului alfa asupra capacitatii DYNORA de a respecta termenele limita. Fig. 8 si 9 demonstreaza aceeasi capacitate pentru RTA si valori diferite pentru parametru de anticipare n. Fig. 10, 11 si 12 ilustreaza performantele in cazul cel mai bun, cazul mediu si cazul cel mai slab, respectiv pentru cei doi rezolvitori de probleme. Cel mai bun caz pentru RTA are loc cand n = 1 pentru toate posibilele valori intregi ale lui n. cel mai bun caz pentru DYNORA este cand alfa = 1 pentru toate valorile posibile ale lui alfa dupa cum le-am aratat in fig. 9. Cazul cel mai nefavorabil pentru RTA are loc cand n = 4, dintre valorile lui n folosite in experimentele noastre. In cazul lui DYNORA acesta se intampla cand alfa = 0.1, dintre valorile lui alfa considerate in experimentele noastre. Cazul mediu de distributie a populatiei pentru un termen final dat este derivat in calculul distributiei medii a populatiei pentru un termen final dat, pentru toate posibilele valori ale parametrilor de performanta alfa si n.

3. Discuție

Performanta comparativa a celor doi rezolvitori poate fi judecata prin examinarea ig. 10, 11, 12, care ilustreaza comparatii ale respectarii termenelor limita pentru cazurile cel mai favorabil, cel mai nefavorabil si pentru cazul mediu. Algoritmul DYNORA surclaseaza RTA in toate cele trei cazuri, ceea ce inseamna ca DYNORA poate garanta un raspuns intr-un timp semnificativ mai scurt decat o face RTA. Tabelul din fig. 13.a. ilustreaza timpii de care au nevoie ambii algoritmi pentru a completa 90% din sarcini. Datele din tabel reprezinta timpii limita inauntrul carora se poate astepta un raspuns complet de la fiecare din algoritmi. Randurile tabelului prezinta timpii de raspuns in cele trei cazuri (cel mai favorabil, cel mai nefavorabil si mediu) pentru a completa corect 100% din sarcini. Primele doua coloane ale tabelelor prezinta timpii respectivi pentru algoritmii DYNORA si RTA. A treia coloana arata procentul de imbunatatire al DYNORA in manevrarea termenelor limita, fata de RTA.

Colectarea si analiza tuturor cautarilor posibile pentru un anume graf ne permit sa obtinem o distributie a tuturor sarcinilor dincolo de timpul total de raspuns. Cazurile de analiza cel mai bun si cel mai slab ale performantei unui algoritm necesita o proba completa din instantele tuturor problemelor. Aceasta distributie permite analize ale celor trei cazuri pentru performanta unui algoritm.

Chiar daca tabelul 13.a. furnizeaza date egale pentru sarcini 100% completate pentru DYNORA in cazul cel mai nefavorabil si cel mediu, aceste valori nu sunt egale pentru sarcini neindeplinite 100%. Acest lucru este evident in graficele din fig. 11 si 12.

Efectul parametrilor de performanta alfa si n asupra rezolvitorilor de probleme poate fi rezumat dupa cum urmeaza. Capacitatea lui DYNORA de a raspunde termenelor limita mai scurte se mareste odata cu cresterea valorii lui alfa, dupa cum am aratat in fig. 6 si 7. Totusi, aceasta capacitate a lui RTA descreste odata cu marirea adancimii cautarii, dupa cum se vede in fig. 8 si 9. Pentru a cerceta inegalitatea dintre cei doi algoritmi, au fost facute analize mai aprofundate asupra datelor, ale caror rezultate sunt ilustrate in fig. 13 si 14. Diferenta de performanta provine din costuri mari pentru faza de planificare in cazul algoritmului RTA, odata cu cresterea lui n. Credem ca aceste costuri mari de planificare se datoreaza faptului ca RTA nu foloseste planificarea si executia in dirijarea cautarii sale. Observam ca executia unei singure muchii pe ciclu de catre RTA(n) si DYNORA(alfa) poate conduce la urmatorul comportament. Odata cu cresterea efortului de planificare pe ciclu la valori foarte mari (alfa ∞, n ∞), ambii algoritmi pot da timpi de raspuns foarte slabi datorita planificarii excesive.

Evaluarea minimizarii timpului de raspuns. Un factor important in analiza algoritmilor in timp real este de a demonstra capacitatea algoritmului de a produce si executa o solutie cu o intarziere minima. Aceasta capacitate poate fi analizata printr-o analiza a complexitatii cazului mediu in grafuri aleatoare. In aceasta sectiune prezentam rezultatele experimentelor care compara performanta lui DYNORA si RTA in minimizarea timpului total de raspuns atat in mediul static, cat si in cel dinamic. Am folosit o metodologie similara celei din experimentul anterior, privitor la respectarea termenelor limita. Aceasta problema este specificata in termenii atator parametrii ai modelului de specificare cat numarul nodurilor si muchiilor. Performanta algoritmului este masurata in termenii unitatilor modelului de specificare, cum ar fi numarul de noduri crescute.

Analiza datelor se bazeaza pe un model probabilistic pentru analiza complexitatii cazului de timp mediu, bazata pe grafuri aleatoare si pe mostre ale instantelor problemelor. Increderea in estimarea complexitatii cazului mediu este derivata din distributia de populatie a instantelor problemelor. Presupunand o distributie normala in grafuri aleatoare, putem testa semnificatia rezultatelor obtinute prin experimentele noastre. Pentru a evalua semnificatia statistica a performantei algoritmului, vom utiliza testul ipotezelor de tip diferenta-de-medie.

Mediu static: In aceasta sectiune descriem datele colectate din experimente intr-un model static al realitatii, in care costurile muchiilor raman constante in timp. Tabelul II si fig. 15 demonstreaza performanta globala a algoritmilor RTA si DYNORA intr-un astfel de mediu. Randurile din tabel reprezinta sase cantitati. Aceste cantitati sunt: costul mediu de planificare, costul mediu de executie, costul mediu total, deviatia standard a costului de planificare, deviatia standard a costului de executie si deviatia standard a costului total. Primele doua coloane ale tabelului reprezinta date despre performanta fiecaruia dintre algoritmi. A treia coloana prezinta procentul de crestere a performantei cazului DYNORA fata de RTA.

Așa cum am arătat în tabelul 2, costul global al planificării plus execuția (Cp+Ce) este mai mic în cazul DYNORA decât în cazul lui RTA cu 42.83%. În timp ce costul de execuție a fost îmbunătățit printr-un mic procent în DYNORA, cantitatea de planificare cheltuită cu găsirea soluțiilor cu aceste costuri de execuție a fost redusă cu aproximativ 73%. De notat că, în timp ce deviațiile standard ale Ce – urilor sunt comparabile pentru ambii algoritmi, deviația standard a lui Cp este considerabil mai mică pentru DYNORA. Aceasta semnifică faptul că costul mediu de planificare obținut pentru DYNORA este un număr mai bun decât pentru RTA. Un alt lucru interesant este raportul dintre Cp și Ce în cei doi algoritmi. Acest raport este mai mic pentru DYNORA decât pentru RTA. Aceasta se datorează faptului că DYNORA monitorizează în mod constant compromisul între costul de planificare și costul de execuție.

Modelul Markov mărginit al mediilor dinamice: În următorul set de experimente, considerăm ipoteza:

Statistic DYNORA lucrează la fel de bine sau mai bine decât RTA, în modelul Markov propus pentru medii dinamice.

Am testat această ipoteză empiric, printr-un experiment similar cu cel discutat în secțiunea anterioară. În acest experiment, un set de grafuri a fost generat aleator folosind programul de generare de grafuri pentru a produce o mostră de grafuri aleatoare în experimentele noastre anterioare. Datele despre performanță au fost obținute din același set de grafuri cu cele generate pentru experimentele în mediu static. În timpul acestui experiment, lungimile muchilor se schimbă după procesul Markov mărginit descris anterior, în secțiunea de specificație a problemei. Datele colectate din experimentul în mediu static au fost comparate și analizate pentru a testa ipoteza de mai sus. Am efectuat teste statistice de semnificație pentru a furniza măsuri de încredere în rezultatele obținute din experiment.

Tabelul III și fig. 16 prezintă datele din acest experiment. Așa cum reiese din tabel, performanțele RTA și DYNORA în modelul mediului dinamic sunt foarte asemănătoare cu performanțele lor în modelul mediului static.

Discuție: Performanțele algoritmilor DYNORA și RTA sunt comparate prin metodologia de estimare a complexității cazului mediu, în doi pași:

selectând mostre posibile și netriviale ale instanțelor problemelor, și

testând semnificația ipotezei de comparare a performanțelor.

Pentru a evalua semnificația statistică a performanțelor algoritmilor DYNORA și RTA, am utilizat testul ipotezelor de tip diferență de medii. Cantitatea 8 din tabel înseamnă deviația standard a populației. Cantitatea Z reprzintă variabila standardizată. Ipotezele sunt enumerate în tabelul IV. Rezultatele testelor arată că diferența între performanțele medii ale celor doi algoritmi, în mediul static, sunt semnificative la un nivel de 0.002. De aici putem deduce că DYNORA depășește semnificativ RTA la un nivel de încredere de 99.99%, ăn mediul static. Rezultatele unui alt test arată că diferența între performanțele medii ale celor doi algoritmi în mediul dinamic sunt de asemenea semnificative la un nivel de 0.002. Rezultă că DYNORA este iarăși mai bun pentru un nivel de încredere de 99.99%. Datorită rezultatelor de mai sus, vom accepta că DYNORA > RTA în ambele medii, static și dinamic.

4. Concluzie

Rezolvitorii de probleme în timp real din IA beneficiază de modele de analiză și specificație bazate pe grafuri. Am prezentat specificația unei probleme de planificare a drumului în tinp real și algoritmul de rezolvare a problemei de planificare în timp real. Am arătat că planificarea drumului în timp real este o problemă grea pentru a ne justifica față de concepția euristică folosită de cercetătorii de IA în timp real în aceste probleme. Am furnizat un algoritm euristic de planificare a drumului în timp real, DYNORA. S-a demonstrat experimental că algoritmul propus depășește tradiționalii algoritmi în timp real din IA în respectarea termenelor limită și în minimizarea timpilor de răspuns. Intenționăm să extindem modelul de analiză și specificație pentru probleme mai mari cum ar fi planificarea în timp real, și pentru aplicații mai extinse, ca de exemplu planificarea drumului robotului. Se pot dezvolta și benchmarkuri bazate pe aceste aplicații (cum ar fi șahul contra timp, tetris, planificarea drumului robotului), pentru a compara algoritmii într-un mod mai concludent.

5. Elaborarea specificațiilor și automatizarea specificării problemelor

Această etapă din elaborarea unui produs program conduce la o documentație detaliată despre tipurile de date folosite și descrierea pas cu pas a proceselor. Iesirea se constituie într-un document numit specificații de sistem [Coog94], care trebuie să aibă o descriere corecta si din care sa poata rezulta programul initial. Descrierea datelor în cadrul specificatiilor de program va fi comunicata specialistilor in managementul datelor pentru a putea fi verificata si integrata cu celelalte structuri de date.

Metodologia este foarte importanta. Se poate folosi aceeasi metodologie ca in faza de definire a programului. Specificatiile de program pot consta in intregime din diagrame sau liste formale.

Documentul de iesire trebuie sa reflecte doua activitati: analiza modelului si evaluarea pachetului de programe.

Trebuie verificat daca in timpul analizei detaliate daca modelul corespunde cerintelor initiale sau daca acestea au fost schimbate intre timp; va trebui calculat impactul pe care il au asupra utilizatorului final. Daca problema este serioasa vor trebui revazute cerintele ori se va acorda o atentie mai mare etapelor de initiere si de definire. Aici este importanta implicarea utilizatorului. Echipa de proiectanti va sti: ce potentiale valori vor putea avea datele, ce validari sunt necesare, ce rapoarte vor trebui intocmite. Detaliile ar trebui deja stabilite, impreuna cu exemple pe calculator, pentru care se va genera cod. Managerul proiectului se va asigura daca userii sunt disponibili pentru comunicare iar echipa a inteles problema.

Inițierea fazei

Lucrul ar trebui sa inceapa cand toate partile implicate in proiect, in special utilizatorul, au revazut si acceptat propunerea de proiect ca baza a noului sistem. Se pun urmatoarele probleme:

Userul isi va da acordul pentru propunerea de sistem cat mai repede cu putinta, iar aceasta nu va fi doar o simpla formalitate;

Ce se va intimpla daca sistemul nu este livrat la timp?

Ce se va intimpla daca vor fi solicitate schimbari in sistem?

Documentatia

Poate fi scrisa in limbaj natural, dar va include aproape sigur un mare numar de diagrame metodologice, afisand impreuna datele si procesele din sistem, tabelele, planul general. Autorul va avea in vedere generatiile urmatoare de dezvoltatori de sisteme, care vor folsi datele continute in acest sistem.

Cele doua documente sunt raportul de evaluare a programelor si analiza prototipului (modelului). Primul ar trebui sa fie suficient pentru definirea interfetei sistemului, iar al doilea trebuie sa demonstreze ca scopurile modelului au fost atinse si cum pot fi ele implementate in sistem.

Documente principale:

planul proiectului

specificatii de sistem

Documente optionale:

Raport de evaluare a programelor

Analiza modelului

Specificatii de prelucrare a datelor

Planul proiectului

Trebuie verificat la inceputul fiecarei faze pentru a cerceta act de exacte au fost estimatiile. Se va face planificarea detaliata.

Proiectul ca un intreg:

Daca continutul sistemului propus sau al celorlalte documente indeplinesc cerintele initiale din faza de definire; daca necesita revizie

Daca schimbarile pot cauza probleme, avand in vedere restrictiile impuse;

Faza curenta

Ce activitati sunt planificate

Ce documente vor fi produse; cine va paticipa la ele

Cand va incepe, cand se va termina si cat va dura fiecare activitate

E folosita vreo metodologie? Daca da, oamenii sunt pregatiti, ce documente si cat de detaliate, cum vor lucra si cum vor interactiona lucratorii?

E folosit un instrument CASE? Pregatirea personalului, copii ale softului, controlul accesului distribuit.

Ce utilizatori vor fi implicati, care sunt rolurile lor

A fost creat un model? Cum afecteaza proiectarea sistemului? Va fi integrat in restul sistemului?

Au fost evaluate programele? Daca da, cand va fi disponibila interfata?

Specificarea sistemului

Contine o descriere a tot ceea ce face sistemul: procese, date, controale, relatii cu alte sisteme. Un bun pachet de programe va fi suficient de documentat pentru a fi folosit ca specificatie de sistem sau ca sursa.

Specificatiile de sistem au doua teluri: sunt sursa pentru activitatile urmatoare (programare, testare, evaluare si documentare); de as. Ele trebuie sa contina o descriere clara a functiilor de sistem. Lista de mai jos este un ghid catre principalele teme luate in considerare. Fiecare dezvoltator de sisteme are o metoda aparte de descriere a specificatiilor de sistem: proza, diagrame, metodologie etc.

Date

Ce structuri de date sunt necesare? Identificati-le, iar daca nu folositi un dictionar de date, faceti o descriere a lor.

Ce tipuri de structuri: fisiere baze de date, indexate secvetial, fisiere relative. In ce succesiune sunt folosite

Mediul de pastrare folosit

Ce structuri exista; daca trebuie schimbat ceva, ce implicatii are

Ce structuri de date externe sunt accesate

Marimea fiecarei structuri si tipul de acces

Susa fisierelor de I/ si destinatia celor de /O

Proprietarii datelor si modul de acces la date

Identitatea, tipul si marimea fiecarui element data(camp, articol); intervalul de valori, valoarea de baza. In lipsa unui dictionar se vor face descrieri.

Validari in cruce, pentru date din diferite fisiere (vezi “barbat” si “gravida”)

Date asociate sau dependente

Parametrii folositi. Marime, valori permise si semnificatia fiecaruuia

Date stocate pe alte sisteme, pe acelasi calculator sau la distanta. Cine le detine, cum sunt actualizate, accesate, efectul schimbarii formatului valorilor permise

Care este cel mai bun mod de prezentare a datelor si structurilor lor pentru cititorii specificatiilor? Daca exista o metoda, ea va trebui folosita.

Cerintele de securitate pentru fiecare element si structura de date. Clasele pentru accesul e tip scriere sau citire ar trebui date daca fac parte dintr-un SGBD. Orice alte restrictii.

Procese

Care este functia reprezentativa pentru fiecare proces? Cum este initiata?

Cat de frecvent se initiaza un proces: ad-hoc, lunar, anual etc.

Datele accesate de procese si modul de accesare

Care sunt iesirile proceselor(ex.: un fisier actualizat, un calcul complet, un rezultat intermediar)? Ce se intampla apoi cu datele de iesire?

Care este elementul care determina ca un proces sa fie complet? Ce se intampla daca apare o eroare in timpul procesului (nota: mesaje de eroare, cine le receptioneaza, ce se intampla cu mesajele de eroare generate de compilator, SO, softul BD etc.)?

Utilizatorii nu trebuie trateze erorile de natura tehnica si codurile de eroare, ci numai un set restrans de erori in limbaj natural, care sa le arate ce au de facut. Trebuie prevazut deci:

Ce trebuie sa faca utilizatorii daca sistemul cade subit, dintr-o pana de curent sau de comunicatie?

Care va fi efectul asupra procesului intr-un moment oarecare al executiei?

Care sunt procesele apelatoare si apelate de acest proces?

Cum interactioneaza un proces cu celelalte? Daca un pachet de aplicatii este parte a unui sistem, interfata va trebui considerata aici. A se scrie subrutine pe care un proces le foloseste impreuna cu alte procese

Care sunt cerintele de peformanta pentru acest proces? Cum vor fi ele indeplinite in aceasta confiuratie a procesului?

Anumite procese sunt restrictionate pe categorii de utilizatori

Securitate

Care sunt cerintele specifice de securitate identificate?

Cum va fi prevazut accesul confidential, in special cel on-line? Dar distribuirea rapoartelor confidentiale?

De ce controale de sistem este nevoie? Dar pentru fiecare proces?

Cum va fi garantata integritatea contralelor? Cum vor fi ele controlate?

Operatii functionale

Operatiunile intr-un calculator vor fi constiente de efectul pe care il au asupra hardului si softului si sa ia in considerare si cerintele initiale. Trebuie stiut:

Ce procese vor fi deschise de operatiunile executate pe computer?

Cum este accesat sistemul si cand trebuie sa fie disponibil? Cum va accesa alte sisteme, cum va folosi spatiul de memorie si procesele de pe acestea?

Cum se realizeaza accesul la distanta?

De ce alte sisteme depinde? Ce alte sisteme depind de el? In sistem, ce procese depind de cel considerat?

Ce structuri de date vor fi afectate de acest proces?

Care este rata de crestere anticipata a noilor structuri de date?

Redundante

Ce sisteme, procese si structuri de dae vor fi inlocuite de acesta?

Ce model de stocare a datelor va fi abordat in acest caz?

Raport de evaluare a programelor

Se va face o evaluare a masurii in care scopurile si cerintele au fost atinse si se va face o recomandare de incepere a lucrului. Se cerceteaza cat de bine se inteleg si cu celelalte programe din sistem.

Care set de programe este recomandat?

Pentu cel ales: au fost indeplinite toate cerintele? care nu? Se accepta si asa?

Analiza modelului

Daca definitia modelului prevede ce trebuie sa obtina acesta, analiza arata ce s-a obtinut prin aplicarea acestuia. Deoarece obiectul unui model poate varia pe o scala considerata, si impactul asupra sistemului va fi de asemenea variabil. Se pune problema:

Care au fost scopurile definitiei modelului si in ce masura au fost atinse?

Este necesar sa se revizuiasca scopurile modelului? Cu ce costuri, timp si efort?

Specificatii de intretinere a datelor

BAZE DE DATE

STRUCTURI DE DATE

ELEMENTE DE TIP DATA

GENERALITATI

Sfarsitul fazei

Cand urmatoarele activitati au fost terminate:

Specificatiile au fost incheiate si acceptate ca baza a noului sistem

Structurile de date au fost acceptate de cel ce lucreaza cu ele

In aceasta faza se unesc cele doua parti ale documentului. Se va trece la lucru pentru transformarea sistemului din nivel logic in fizic. Daca in primul pas ne-am concentat mai mult pe manipularea datelor, acum ne indreptam atentia catre procese.

Pentru a dezvolta specificații de calitate, acestea trebuie să aibă câteva proprietăți:

corecte și complete;

neambigue;

consistente;

verificabile;

să poată fi urmărite;

concise;

ușor modificabile.

Rezultatele fazei de cerințe și specificații finale pot fi sumarizate în următoarea schemă:

Metodele de specificare

În procesul de dezvoltare a specificațiilor, dorim să creăm premisa pentru o înțelegere amănunțită a software-ului pe care îl vom implementa pornind de la cerințele pe care le-am creat în faza anterioară. Vrem ca aceste specificații să fie mai precise și mai concise decât au fost cerințele, iar scopul nostru este să obținem performanța și acuratețea cerute de software. Dorim de asemenea ca specificația ce va rezulta să posede toate proprietățile impuse pentru un software de calitate, adică să fie neambigue, consistente, corecte etc. Aceasta ne va asigura că atunci când vom începe proiectarea, vom dispune de toate informațiile necesare, și într-o formă care le va face ușor de folosit. Și, în final, nu vrem ca specificațiile să conducă la o formă de proiectare particulară. Ar fi bine ca în activitatea de proiectare să avem posibilitatea să proiectăm în ce manieră ne convine.

Proprietățile metodelor de specificare

Pentru îndeplinirea cererilor de mai sus putem formula câteva proprietăți pe care ar trebui să le folosească fiecare din metodele folosite în timpul specificării:

este necesar ca o metodă să ajute la înțelegerea cerințelor informale obținute în faza anterioară;

să simplifice procesul de dezvoltare a specificațiilor formale;

să permită analiza consistenței și corectitudinii specificațiilor;

o metodă ar trebui să faciliteze validări pentru ca specificațiile (și implicit cerințele) să corespundă nevoilor utilizatorilor;

metoda nu ar trebui să interfere co domeniul de decizie al procesului de specificare.

Gradul de succes în satisfacerea acestor proprietăți poate depinde în mare măsură de alți factori cum ar fi cât de bine această funcție poate fi automatizată, în special pentru proprietatea 3. de exemplu, aproape orice tehnică de specificare va ajuta la înțelegerea cerințelor. Ele utilizează însă puncte de vedere diferite de acelea folosite în faza de descriere a cerințelor, în care atacăm problema. Prin lărgirea perspectivei de vedere, se descoperă noțiuni ascunse sau la care nu s-a gândit nimeni. Dacă textul a fost folosit pentru a se descrie cerințele, graficele sunt mai apropiate specificațiilor. Capacitatea de a vedea problema din diferite unghiuri este foarte importantă.

Simplificarea procesului de obținere a specificațiilor este o sarcină mai greu de îndeplinit, în special când este cuplată cu necesitatea de a fi precise, consistente, complete etc. Multe metode folosesc procesul formalismului. Acesta apare în mai multe variante. În unele metode el înseamnă o concepție strict matematică, în timp ce în altele o manieră mai puțin riguroasă constă din grafice și șabloane, având asociate reguli de organizare, operații permise, sunt folosite simboluri și expresii. Alte metode utilizează limbaje formalizate, similare limbajelor de programare, pentru a construi specificațiile. Cu alte cuvinte, formalizarea permite elaborarea specificațiilor concise, precise care pot fi corectate în vederea asigurării completitudinii, consistenței și completitudinii. Aceasta va duce la o automatizare mai ușoară a consistenței și completitudinii specificațiilor, mai puțin a corectitudinii.

Există totuși obiecții la folosirea formalismelor. Ele susțin ideea că folosirea tehnicilor formale este mai dificilă și implică și procesul de dezvoltare a specificațiilor. Un argument ar fi că dezvoltatorii nu au pregătirea necesară, utilizatorii finali nu-i por oricum înțelege, și sunt o pierdere de timp și de bani. Meyer susține însă că formalismul în cea mai mare parte nu este mai greu decât calculele elementare și teoria mulțimilor, și acest nivel ar trebui să fie suficient pentru înțelegerea sistemelor de specificare ([Meyer85]).

Automatizarea

Procesul de automatizare prevăzut pentru faza de specificare este mult mai extins decât cel din faza de descriere a cerințelor. Acesta nu se înscrie însă într-un trend către fazele următoare ale ciclului de viață ale produsului software, către faza de implementare. Mulți dintre dezvoltatorii de metode care sunt automatizate cer ca metodele de obținere a cerințelor să funcționeze la fel, dar criteriile noastre pentru metodele de specificare comparate cu metodele pentru cerințe nu admit revendicările lor. Motivul este că cele mai multe dintre ele pretind, cel puțin câteva informații preliminare despre cerințe ca punct de plecare. PSL/PSA [Tiec74] este un un exemplu bun în acest sens. Metodele de elaborare a cerințelor ar trebui să ajute pe cineva să gândească și să purceadă la înțelegerea problemei, în timp ce metodele de specificare ar trebui să îl ajute să își clarifice aceste gânduri. Asta nu însemnă că cerințele nu pot fi obținute prin apelarea sumară la aceste metode, doar că aceste metode nu sunt tot atât de folositoare pnetru începerea procesului cerințelor cât mai mult pentru verificarea completitudinii cerințelor.

Ca de obicei, orice metodă propusă spre a fi automatizată ar trebui supusă automatizării, iar metodele de specificare în general sunt. Folosirea metodelor formale ajută automatizării foarte mult, din moment ce regulile de manipulare a datelor sunt deja determinate. Mai mult, deoarece implică puțină informație semantică (sunt manipulate elementele sintactice ale tabelelor, nu înțelesul acestora), și deoarece volumul informației este redus datorită conciziei codării, automatizarea specificațiilor este mult mai ușoară decât automatizarea cerințelor. Acest lucru deschide mai mult calea către verificarea consistenței și completitudinii aspectelor relative la specificație.

Totuși verificarea corectitudinii nu este încă posibilă în modul automat deoarece presupune și manipularea informației semantice conținută în specificație, și probabil un mic dicționar de termeni și definițiile lor.

Automatizarea în specificare a ajutat la dezvotarea unor specificații și cerințe mai bune. Capacitatea de a executa specificații crește mult calitatea lor și sperăm și a produsului în curs de dezvoltare.

Specificații executabile

S-au făcut multe cercetări în sensul posibilității de executare a specificațiilor. Există o concepție operațională care susține că specificațiile reprezintă o procedură simplă și clară care transformă stimulii de intrare în răspunsuri de ieșire. Această procedură este apoi demonstrată și executată utilizatorului care poate verifica dacă aceasta poate verifica sau nu nevoile sale. Procedurile mai complicate pot include declarații, sincronizări și mediul sistemului. Ideea specificațiilor executabile nu este nouă, și a fost aplicată într-un anumit număr de domenii ale științei computerelor incluzând descrierea limbajelor ce folosesc gramatica în compilatoare, limbaje de interogare și schematizare și programarea logică în inteligența artificială.

Avantajele specificațiilor executabile sunt semnificative. Totdeauna necesitatea de a executa specificațiile va descuraja ambiguitatea. Rezultatele vor trebui verificate dacă se potrivesc cu cerințele utilizatorului. Aceasta forțează programatorul să ia în seamă informații care altfel ar fi fost lăsate deoparte, și acest lucru este mai necesar în atingerea performanței și acurateții pe care trebuie să o întrunească produsul software. Un alt avantaj este că pot fi incluse și informații despre resurse. Atât resursele cantitative cât și cele specifice pot fi incluse în execuție. Asta ne va ajuta mult la proiectare și ne arată dezavantajele specificațiilor executabile.

Mai întâi există acestă tendință de a proiecta înainte de a specifca. Capacitatea de a include informații despre resurse poate duce la dizolvarea granițelor între proiectare și specificare, și trebuie făcute eforturi pentru a se evita acest lucru. Totuși, în multe dintre proiectele mari, multe resurse sunt deja determinate apriori, poate din motive financiare sau politice (rareori tehnice), așa că includerea lor probabil că nu este o idee rea. Atâta timp cât metodele însele( și nu automatizarea lor) nu forțează specificatorul să ia decizii de proiectare, nu se pierde foarte mult. Abilitatea de a automatiza, și noile capacități pe care le generează, pentru utilizare sau abuz, vor fi totdeauna o problemă.

Mai există și alte dezavantaje în legătură cu folosirea specificațiilor executabile. Faptul că trebuie creat un model executabil poate încuraja specificatorul să facă ceva în detrimentul unei mai bune înțelegeri a cerințelor. Timpul consumat pentru a dezvolta o specificație executabilă poate fi de asemenea semnificativ, dacă se dorește crearea unui program. Iar în proiectele foarte mari, se întâmplă să nu poată fi executat tot produsul deodată, acest lucru făcând dificilă verificarea rezultatelor. Mai mult, execuția specificațiilor poate lua grozav de mult timp, fără a menționa resursele calculatorului. De obicei, managementul proiectului va decide cât de indicată este crearea specificațiilor executabile.

O tehnică automată, care poate ajuta la crearea specificațiilor, dar care nu este bazată pe metodă, este PSL/PSA.

PSL/PSA (Limbaj de specificare a problemei / Analizor al specificării probl.)

A fost dezvoltat în 1970 de Daniel Tiechrow la Universitatea din Michigan. Se axează în principal pe automatizarea procesului de creare a documentației de înaltă calitate. Este bazat pe un model entitate-relație, care poate fi folosit pentru a descrie un set extins de modele de sistem generale.

PSL este folosit pentru a descrie cerințele unui sistem foosind un limbaj formal. Este un limbaj formal care poate descrie un sistem din mai multe puncte de vedere. Aspecte ale sistemului care pot fi acoperite sunt:

fluxurile sale de intrare / ieșire (intercațiunea între un sistem și mediul său)

structura (ierarhia obiectelor sistemului)

structurile de date (relațiile între date)

date derivate (date obiect folosite de anumite procese)

mărime și volum (mărimea sistemului și volumul de procesare)

dinamica (comportarea sistemului)

proprietățile (atributele)

managementul proiectului (informații relative la proiect).

Aceste aspecte ale sistemului sunt descrise în termenii unei mulțimi de tipuri de obiecte și relații între ele.

Un obiect este orice nume din PSL dat de utilizatorul PSL. Sunt aproape 20 de obiecte predefinite în limbaj. Relațiile între obiecte pot fi descrise folosind una din cele 50 de relații care există deja. Tabelul de mai sus arată unele din obiectele și relațiile disponibile. Pot fi atașate de asemenea obiectelor și atribute, care descriu valori sau proprietăți ale obiectelor. Figura următoare conține un exemplu de PSL.

Descrierea PSL a cerințelor este folosită ca intrare în instrumentul automat de manipulare a bazei de date / generare de rapoarte PSA. PSA este un analizor sofisticat care verifică descrierea PSL pentru diverse informații. Există aproape 50 de tipuri de analize, numite rapoarte, care sunt disponibile. Rapoartele sunt descompuse în 4 categorii majore:

rapoarte de modificare a bazei de date

rapoarte de referire

rapoarte de cuprins

rapoarte de analiză

Rapoartele de modificare a bazei de date înregistrează schimbările care au fost făcute și prevăd diagnostice și avertismente despre posibilele inconsistențe ale datelor.

Rapoartele de referire pot fi folosite pentru sarcini ca: identificarea tuturor obiectelor, tipului lor și datei ultimei modificări (Raportul de listă de nume); listarea tuturor proprietăților și relațiilor pentru un obiect anume (Raportul de descriere a problemei); să furnizeze informații despre date din interiorul sistemului într-un format de dicționar de date (Raportul dicționar).

Rapoartele de cuprins pot oferi informații despre managementul proiectului (Raport despre cuprinsul bazei de date), să arate ierarhia sistemului (Raportul structurii), ori graficul fluxului de date (Raportul grafic extins), printre altele.

În final rapoartele de analiză pot analiza similitudini între intrări și ieșiri (Raportul de comparație a conținutului), să detecteze goluri în fluxul de informație sau date obiect nefolosite, (Raport de interacțiune a datelor în proces) sau să arate comportamentul dinamic al sistemului (Raportul de înlănțuire a proceselor).

PSL/PSA ajută foarte mult prin verificarea completitudinii și consistenței unei descrieri PSL. Totuși, nu ajută la determinarea cerințelor inițiale din care să rezulte descrierea, nici nu verifică acuratețea descrierii problemei originale. Este doar o tehnică de documentare și comunicare a informației.

PSL/PSA se înscrie în categoria automatizării valoare-tip. Este o metodă independentă, care nu specifică un format de document care ar trebui fi folosit. Ea oferă doar un ghid superficial, lăsând utilizatorul să decidă cât de bine este să-l folosească. Pentru utilizare la crearea specificațiilor poate ajuta la analizarea cerințelor pentru lipsa de informații, făcând necesară punerea unor întrebări suplimentare. Prin ea însăși, PSL/PSA este slabă dar, dacă este folsită împreună cu o metodă adecvată de specificare, puterea și utilitatea ei poate crește.

Automatizarea specificării – media aritmetică

X + Y

Se dă relația mediei aritmetice: M = –––

2

Enunț problemă: Se dau două numere reale X și Y. Să se determine numărul real M care este media aritmetică a celor două numere.

Cerințe informaționale (analiza problemei):

1. Variabilele sistemului: (prin identificarea noțiunilor corespunzătoare din text)

a) de intrare: X, Y

b) de ieșire: M

c) intermediare:

2. Domenii inițiale de definire a variabilelor:

a) de I/: X, Y – mulț. nr. reale

b) de /O: M – mulț. nr. reale

c) intermed.

3. Restricții simple: (asupra variabilelor problemei) actualizarea domeniilor de definiție

4. Identificarea relațiilor dintre variabile sistemul de ecuații al sistemului

5. Identificarea relațiilor de calcul ale variabilelor de ieșire (verificare dacă se încadrează în domeniile de definiție actualizate).

Exemplu de specificare formală a ADT

ADT <nume tip>

uses ADT-uri și tipuri importante

type tip introdus

functP specificare functii primitive

axioms

var variabile utilizate in axiome

specificare axiome

functD specificare functii derivate

end <nume tip>

1) Definirea problemei

– textual, de către utilizator (UTZ)

2) Identificarea variabilelor sistemului (cele 3 categorii) de către UTZ – highlight pe text

3) Clasarea variabilelor:

se identifică tipul (domeniul elementar) căruia aparține fiecare (pentru cele care există)

dacă nu există un astfel de tip, se definește tipul elementar căruia aparțin (dintre cele rămase)

… sau se identifică tipul elementar din care poate fi direct derivabil

se caută dacă anumite noțiuni din text se regăsesc prin abstractizare între tipurile utilizator predefinite; se pot construi doar atributele, pe baza tipurilor elementare și a ADT-urilor (din bibliotecă și cele nou definite) utilizare;

Notă: există o astfel de bibliotecă de specificații (tipuri elementare și ADT-uri utilizator) predefinită; ea poate fi îmbogățită.

se caută ADT-uri derivabile (prin agregare, moștenire simplă, multiplă)

se definesc noi ADT-uri, pe baza unor noțiuni relativ complexe identificate pe textul problemei (care reprezintă abstractizări ale unor obiecte reale)

se actualizează secțiunea functD a ADT-urilor primitive

Notă: aceasta este o clasare preliminară. Există posibilitatea efectuării unor modificări, revocări.

4) Reprezentarea restricțiilor simple

Vor fi reflectate prin axiome în cadrul tipurilor pe carele implică direct și a celor derivate din acestea. Astfel:

cele de la pct. 3a) se vor deriva; vor rezulta tipuri noi, prin adăugarea noii axiome

celor de la pct. 3b) și 3c) li se va adăuga noua axiomă

Notă: implicit algoritmul se va relua de la punctul 3) pentru funcțiile derivate din ADT-urile ulterior modificate.

idem pentru 3d), 3e), 3f)

5) Reprezentarea relațiilor dintre variabile (până aici s-au identificat ADT-urile standard și s-a construit scheletul celorlalte)

relațiile de calcul se reprezintă prin funcții primitive

numeFuncție : (tipParam1, tipParam2, …) tipRez

unele relații de tip restricție pot fi reprezentate prin axiome; celelalte țin de specificul problemei

6) Reprezentarea relațiilor de calcul ale variabilelor de ieșire:

se cercetează dacă se află între primitimele deja existente ale ADT-ului variabilei

se construiește, dacă este posibil, o primitivă pentru calculul variabilei

relația e mai complicată și nu este reprezentativă pentru tipul respectiv. Se reportează pentru partea de implementare

7) Se completează ADT-urile existente cu noi atribute și primitive, până se ajunge la o reprezentare cât mai fidelă a obiectului real. Se pot completa

chiar și cele predefinite, dacă atributele sau primitivele sunt intrinseci tipului

noile tipuri utilizator și tipuri elementare

Implementarea algoritmului

Există o bază de date ce stochează ADT-urile și relațiile lor (un fel de MFC). Aceasta va ajuta și la construcția documentației. Prin cunoașterea sintaxei limbajului C++ se construiesc clasele corespunzătoare ADT-urilor și se stabilește ierarhia de clase. Se va construi funcția utilizator care returnează rezultatele problemei.