Retele DE Tranzitie DE Baza Implementare In Java

Cuprins

Capitolul 1: Introducere ……………………………………………… 3

Locul și rolul sistemelor expert. Sisteme expert celebre….3

Analiza conceptului de sistem expert. Structura generală a unui sistem expert………………………………………… 5

Modulele unui sistem expert…………………………….. 9

Capitolul 2: Modelarea limbajului natural…………………………….12

Limitele gramaticelor context free………………………. 12

Gramatici clauzal definite. Concordanțe sintactice și semantice………………………………………………… 14

Implementarea semanticii gramaticilor clauzal definite . 19

Rețele de tranziție de bază……………………………… 19

Capitolul 3: Cunoștințe, reprezentarea lor și inferența…………………25

Sisteme de decizie și raționament prin mulțimi rough……25

Sisteme de decizie……………………………… 25

Mulțimi rough…………………………………… 29

Reprezentarea și utilizarea incertitudinii………………… 30

Factori de certitudine………………………………30

Sisteme de diagnosticare………………………….. 32

3.3 Rețele semantice………………………………………… 36

3.3.1 Mediu de raționament……………………………… 36

3.3.2 Rețele semantice elementare………………………..40

3.3.3 Rețele semantice cu drumuri confluente……………45

3.4 Moștenire. Teoria cadrelor……………………………… 50

Capitolul 4: Prezentarea limbajului Java………………………………..53

Introducere în limbajul Java……………………………… 53

Platforma Java…………………………………………… 56

Descrierea mediului JDK………………………………… 57

Pachete fundamentale……………………………….57

Unelte Java………………………………………….58

Capitolul 5: Prezentarea aplicației……………………………………….60

Bibliografie………………………………………………………………69

=== l ===

Cuprins

Capitolul 1: Introducere ……………………………………………… 3

Locul și rolul sistemelor expert. Sisteme expert celebre….3

Analiza conceptului de sistem expert. Structura generală a unui sistem expert………………………………………… 5

Modulele unui sistem expert…………………………….. 9

Capitolul 2: Modelarea limbajului natural…………………………….12

Limitele gramaticelor context free………………………. 12

Gramatici clauzal definite. Concordanțe sintactice și semantice………………………………………………… 14

Implementarea semanticii gramaticilor clauzal definite . 19

Rețele de tranziție de bază……………………………… 19

Capitolul 3: Cunoștințe, reprezentarea lor și inferența…………………25

Sisteme de decizie și raționament prin mulțimi rough……25

Sisteme de decizie……………………………… 25

Mulțimi rough…………………………………… 29

Reprezentarea și utilizarea incertitudinii………………… 30

Factori de certitudine………………………………30

Sisteme de diagnosticare………………………….. 32

3.3 Rețele semantice………………………………………… 36

3.3.1 Mediu de raționament……………………………… 36

3.3.2 Rețele semantice elementare………………………..40

3.3.3 Rețele semantice cu drumuri confluente……………45

3.4 Moștenire. Teoria cadrelor……………………………… 50

Capitolul 4: Prezentarea limbajului Java………………………………..53

Introducere în limbajul Java……………………………… 53

Platforma Java…………………………………………… 56

Descrierea mediului JDK………………………………… 57

Pachete fundamentale……………………………….57

Unelte Java………………………………………….58

Capitolul 5: Prezentarea aplicației……………………………………….60

Bibliografie………………………………………………………………69

Sisteme Expert

Capitolul I – Introducere

Locul și rolul sistemelor expert. Sisteme expert celebre

Perioada anilor 1955-1975 este considerată ca etapa apariției inteligenței artificiale și a primelor sisteme expert. Principalele evenimente din aceea perioadă sunt următoarele:

Anul 1956: prezentarea la Darmouth College a programului Logic Theorist de demonstrare automată în calcul prepozițional; pentru acest motiv se consideră că anul 1956 este anul apariției inteligenței artificiale;

În anul 1959 apare limbajul LISP elaborat de Mc Carthy;

În anul 1960 este prezentat la Universitatea Stanford programul DENDRAL, care determină structura unei molecule plecând de la informațiile date de un spectograf; acesta este considerat primul sistem expert;

În anul 1970 este prezentat la Universitatea Stanford sistemul expert MYCIN care era utilizat în diagnosticul infecțiilor bacteriene; acest sistem utilizează cunoștințe incerte și este realizat în LISP; următorul sistem expert este sistemul PROSPECTOR utilizat în prospecțiuni geologice;

În perioada 1970-1975 apare limbajul PROLOG, limbaj de programare bazat pe calculul predicatelor de ordinul 1.

În perioada 1975-2000 atenția generală s-a concentrat pe următoarele direcții:

identificarea unor metode eficiente care să fie utilizate în demonstrarea automată;

proiectarea și realizarea de produse software (shell-uri) sub care să se poată implementa sisteme expert;

proiectarea și implementarea de sisteme expert pe domenii de expertiză specifice.

Produsele software destinate sistemelor expert s-au dezvoltat atât prin produse oferite în mod gratuit, cât și sub forma produselor comerciale. Dintre produsele distribuite în mod gratuit menționăm următoarele:

FOCL: este un shell pentru sisteme expert și program de învățare automată; este scris în Common Lisp, include o interfață grafică pentru fapte și reguli, un interpretor de reguli care utilizează metoda forward.

BABYLON este un mediu de dezvoltare al sistemelor expert care include cadre, constrângeri și formalism logic de tip Prolog și un limbaj pentru aplicații de diagnosticare.

ES este un program care suportă raționament backward și forward, relații pe mulțimi fuzzy și este înzestrat cu un modul de explicații.

MOBAL este un sistem de dezvoltare de modele operaționale într-o reprezentare a logicii de ordinul 1; este înzestrat cu un motor de inferențe care realizează deducția pe baza faptelor și regulilor introduse de utilizator; are un modul de achiziție de cunoștințe și utilizează metode și tehnici de învățare automate.

Clips (C Language Intergrated Production Systems) a fost realizat la NASA/Johnson Space Center conține un motor de inferențe bazat pe raționament de tip forward; include un limbaj orientat pe obiect numit COOL, care este integrat cu motorul de inferență.

Dintre produsele comerciale enumerăm următoarele:

ACQUIRE este un sistem de achiziție de cunoștințe și un shell pentru sistem expert, un mediu de dezvoltare a aplicațiilor bazate pe cunoștințe; modulul de achiziție de cunoștințe se bazează pe recunoașterea formelor, permite reprezentarea cunoștințelor prin obiecte, reguli și tabele de decizie.

– ADS (Aion Development System): include reprezentarea pe obiecte a cunoștințelor , motor de inferență bazat pe raționament backward, forward și bidirecțional și se poate utiliza în conexiune limbajele de programare C și Pascal.

– C-PRS (Procedural Reasoning System în C) este utilizat în controlul proceselor și aplicații de supervizare și a fost utilizat în monitorizarea unor subsisteme NASA, diagnosticarea și supravegherea rețelelor de comunicații, controlul roboților, sistemul de control al zborurilor aviatice și managementul traficului aerian.

– GURU este un mediu de dezvoltare a sistemelor expert produs de MICRO DATA SYSTEMS INC

În domeniul realizării de sisteme expert, considerăm că cele mai spectaculoase rezultate s-au obținut în domeniul contabil, financiar-bancar, asigurărilor și a burselor de valori.

1.2 Analiza conceptului de sistem expert

Structura generală a unui sistem expert

Sistemele expert sunt produse ale inteligenței artificiale, ramură a științei calculatoarelor ce urmărește dezvoltarea de programe inteligente. Remarcabil pentru sistemele expert este aria de aplicabilitate ce a cuprins multe domenii de activitate de la informatica și ingineria sistemelor până la economie, bănci, comerț, educație și medicină.

Un sistem expert (SE) este un program ce analizează un grup de cunoștințe și interacționează pentru obținerea rezultatelor într-o activitate dificilă întreprinsă uzual doar de experții umani.

Principala caracteristică a unui sistem expert este derivată din baza de cunoștințe împreună cu un algoritm de căutare specific metodei de raționare. Un sistem expert tratează cu succes probleme pentru care o soluție algoritmică clară nu există.

În vedera proiectării și implementării unui sistem expert se ține seama de următoarele componente :

Inginerul de cunoștințe

Expertul în domeniu

Echipa inginerului de cunoștințe

Mediul de dezvoltare al sistemului expert

Utilizatorii sistemului expert

Să identifice problema pe care o are de rezolvat

Să clarifice coceptele din domeniul de specialitate necesare reprezentării cunoștințelor

Să proiecteze structura cunoștințelor de reprezentat, adică să fixeze metoda de reprezentare a cunoștințelor

Să înțeleagă metodele de reprezentare pe care le utilizează expertul uman

În principal un sistem expert este alcătuit din următoarele componente :

Un motor de inferențe

Un modul de explicații

O bază de cunoștințe

O interfață de intrare/ieșire

Se cuvine să subliniem faptul că aceste componente pentru a funcționa corect trebuie implementate utilizând un mediu de dezvoltare, iar pentru a rezolva o anumită problemă din domeniul de competență, sistemul expert dispune de o bază de fapte.

Mediul de dezvoltare este un produs software care pune la dispoziția programatorului posibilitatea de a proiecta și implementa componente software de natură diferită, dar compatibile unele cu altele. El ar trebui să dea posibilitatea proiectării și procesării bazelor de date, spread-sheet-urilor, utilizarea procesoarelor de text, facilități de transmitere la distantă, facilități de proiectare și implementare a componentelor unui sistem expert.

Ierarhia componentelor unui sistem expert este următoarea :

În figura 2 am prezentat o ierarhie de entități software care conduc în final la sistemul expert. La baza acesteia stă mediul de dezvoltare, care poate fi un mediu de programare sau unul sau mai multe limbaje de programare.

Pe nivelul imediat superior se găsește motorul de inferențe. Această componentă este dependentă de metoda de reprezentare a cunoștințelor aleasă de inginerul de cunoștințe. Legătura dintre motorul de inferențe și metoda de reprezentare a cunoștințelor este deosebit de puternică. El preia din baza de cunoștințe faptele utilizate pentru construirea raționamentului. Mecanismul de inferențe urmărește o serie de obiective majore cum ar fi :

Alegerea strategiei de control în funcție de problema curentă ;

Elaborarea planului de rezolvare al problemei după necesități ;

Comutarea de la o strategie de control la alta ;

Executarea acțiunilor prevăzute în planul de rezolvare.

Deși mecanismul de inferențe este constituit dintr-un ansamblu de proceduri în sensul obișnuit al termenului, modul în care utilizează cunoștințele nu este prevăzut program ci depinde cunoștințele pe care le are la dispoziție.

Pe nivelul aflat imediat deasupra motorului de inferențe se găsește baza de cunoștințe care se obține prin reprezentarea cunoștințelor din domeniul de competență definit și delimitat în urma discuțiilor dintre inginerul de cunoștințe și expertul în domeniu. Performanțele unui sistem expert depind în mare măsură de cantitatea de informații conținută de baza de cunoștințe. Baza de cunoștințe este formată din ansamblul cunoștințelor specializate introduse de Expertul uman.

Cunoștințele stocate aici sunt în principal descrierile obiectelor și a relațiilor dintre acestea. Baza de cunoștințe face parte din sistemul cognitiv, cunoașterea fiind memorată într-un spațiu special organizat. Forma de stocare trebuie să asigure căutarea pieselor de cunoaștere specificate direct prin simboluri identificatoare sau indirect, prin proprietăți asociate care pornesc de la alte piese de cunoaștere.

Baza de fapte reprezintă o memorie auxiliară care conține toate datele utilizatorului – faptele inițiale care descriu enunțul problemei de rezolvat și rezultatele intermediare produse în cursul raționamentului.

Modulul de explicații este acea componentă a sistemului expert care reface drumul parcurs de motorul de inferență în obținerea raționamentului. El realizează o trasare a raționamentului utilizând baza de cunoștințe și baza de fapte.

Interfața de intrare/ieșire este acea componentă a sistemului expert care asigură transferul de date între utilizator și sistem. Ea este utilizată pentru introducerea informațiilor în baza de cunoștințe și în baza de fapte , deci proiectarea ei depinde de metoda de reprezentare a cunoștințelor. Un factor determinant în proiectarea interfeței de intrare/ieșire este cerința ca interfața să poarte dialogul în limbaj natural.

Se cuvine să subliniem că unele sisteme expert mai evoluate mai conțin o componentă: modulul de achiziție al cunoștințelor. Proiectarea acestui modul utilizează tehnici de învățare și prin intermediul acestei componente sistemul expert dobândește capacitatea de a-și adăuga cunoștinte noi, obținute în procesul de inferență.

1.3 Modulele unui sistem expert

Pe lângă cele enumerate mai sus , un sistem expert mai conține o serie de module ce asigură comunicarea cu operatorul și expertul uman.

Modulul de comunicație asigură interfețele specifice pentru utilizatori cât și pentru achiziția de cunoștințe. Interfața cu utilizatorul este cea care permite dialogul între utilizator și sistem în limbaj cvasinatural, comunică mecanismului de inferență cererile utilizatorului și utilizatorului rezultatele prelucrărilor.

Se facilitează în egală măsură achiziția enunțului problemei inițiale și comunicarea rezultatului.

Modulul de achiziție al cunoștințelor preia cunoștințele specializate furnizate de expertul uman prin intermediul inginerului de cunoștințe într-o formă nespecifică reprezentării interne.

O serie de cunoștințe pot apărea sub forma unor fișiere specifice bazelor de date sau altor programe externe. Acest modul recepționează cunoștințele, verifică validitatea lor și generează în final o bază de cunoștințe coerentă.

Modulul de explicare permite trasarea drumului urmat în procesul de raționament de către sistemul rezolutiv și emiterea justificărilor pentru soluțiile obținute, evidențiindu-se astfel cauzele eventualelor greșeli sau motivul unui eșec. El ajută expertul să verifice consistența bazei de cunoștințe.

Reprezentarea prelucrarea utilizarea

cunoștințelor cunoștințelor cunoștințelor

Explicare și utilizare

În funcție de aplicația pentru care este construit, structura efectivă a unui sistem expert poate fi diferită față de structura standard. De exemplu, faptele inițiale pot fi achiziționate atât de la utilizator cât și de la un echipament de conducere automatizate.

Este însă important ca sistemele expert să aibă două caracteristici:

Să explice raționamentul. Dacă acest lucru nu este posibil, utilizatorii umani s-ar putea să nu-l accepte. În acest scop trebuie să existe suficiente cunoștințe pentru explicații iar programul trebuie să lucreze în pași inteligibili.

Să poată dobândi noi cunoștințe și să-și poată modifica cunoștințele vechi. De obicei, singurul mod de a introduce cunoștințe într-un sistem expert e prin interacțiune cu un expert uman.

Capitolul 2

Modelarea limbajului natural

2.1 Limitele gramaticilor context free

Există două categorii de limbaje:

Limbaje artificiale

Limbaje naturale

Limbajele artificiale sunt definite de experții din domeniu prin explicitarea regulilor de construcție corecte. Limbajele formale cum sunt cele din gramatica lui Chomsky sunt limbaje artificiale.

Limbajele naturale sunt cele utilizate de oameni pentru a comunica (ex :limba română,limba germană).

O frază în limbaj natural este o secvență finită de cuvinte peste un anumit alfabet. Combinația de cuvinte utilizate în frază trebuie să respecte anumite reguli, care formează sintaxa limbajului. De asemenea, combinația respectivă trebuie să reprezinte o semnificație coerentă, adică să respecte semantica limbajului.

Alfabetul împreună cu sintaxa și semantica definesc în mod complet un limbaj. Din punct de vedere formal, mecanismul de definirea sintaxei limbilor naturale nu este elucidat până în momentul actual. Deci, nu se cunoaște un mecanism care să cunoască toate construcțiile corecte ale unui limbaj natural. Totuși, există modele matematice pentru aproximarea limbajelor naturale.

Un prim mecanism prin intermediul căruia putem defini limbaje îl constitue gramatica context free din clasificarea lui Chomsky. O asemenea gramatică este un sistem

G=(vN,vT,S,P), unde

VN este o mulțime finită de simboluri numite simboluri neterminale ;

VT este o mulțime finită de simboluri numite simboluri terminale ;

SVN se numește simbolul inițial al gramaticii :

P VN (VN VT )* este o mulțime finită de elemente numite producțiile gramaticii.

Un element (A,)P se notează de obicei A. Această notație sugerează înlocuirea lui A cu . Procesul de substituire este descris de relația :

(VN VT)* (VNVT)* definită astfel: uv dacă există AVN, există x, y(VN VT) și există producția A astfel încât u=xAy și v=xy. Relația se numeste relație de derivare directă. Închiderea reflexivă și tranzitivă a relației se notează * . Aceasta înseamnă că u* v dacă se întâmplă unul din următoarele două cazuri :

u=v

există k 1 și există u0,u1,…………uk (VNVT)* astfel încât

u=u0

v=uk

uiui+1 pentru i{0,……..,k-1}

Relația * se numește relația de derivare . Limbajul generat de gramatica G este mulțimea notată cu L(G), definită astfel :

L(G)={wVT* /S*W}

Elementele lui L(G) și numai acestea se consideră că sunt entitățile corecte sintactic în raport cu gramatica G.

Posibilitățile gramaticii context free sunt limitate în ceea ce privește generarea de fraze corecte sau cu acoperire semantică în limba română.

În mare măsură aceste posibilități limitate ale gramaticilor context-free se datorează înlocuirii unui neterminal indiferent de contextul în care acesta

apare.

În concluzie, gramaticile context-free nu satisfac suficient cerințele unui mecanism generativ de fraze într-un limbaj natural. Pentru aceste motive, cercetătorii lingviști, informaticieni, matematicieni și de altă natură au propus alte mecanisme generative pentru limbile naturale.

2.2 Gramatici clauzal definite.

Concordanțe sintactice și semantice

O gramatică clauzal definită este reprezentată prin clauze Prolog și menirea acestui tip de mecanism constă în creșterea puterii generative a gramaticilor context free.

Orice gramatică context free poate fi transpusă într-o mulțime de clauze. Deci, orice gramatică context free este o gramatică clauzal definită. Folosim mijloacele pe care ni le oferă programarea logică și este posibil să realizăm două tipuri de concordanțe într-o asemenea gramatică: concordanța sintactică și concordanța logică.

Concordanța sintactică se referă la realizarea acordului gramatical între diferite entități sintactice al frazei. Pentru exemplificare vom considera problema realizării concordanței dintre genul substantivului pe de o parte și articolul sau nehotărât sau adjectivul asociat acestuia pe de alta parte.

Pentru aceasta presupunem că urmărim să proiectăm pentru recunoașterea propozițiilor de tipul :

o fată frumoasă

un băiat scund

Același mecanism ar trebui să respingă propoziții de forma :

O fată scund

Un băiat frumoasă

Un fată scund

Care sunt corecte într-o gramatică context-free. Pentru aceasta vom considera următoarele clauze:

prop(X,Y,Z):art(C,X), subst(C,Y), adj(C,Z).

art(masculin,un)

art(feminin, o)

subs(masculine,băiat)

subst(feminin,fată)

adj(masculin, scund)

adj(feminin,scundă)

adj(masculin, frumos)

adj(feminin, frumoasă).

Se observă că prop(un,băiat,scund) și prop(o,fată,frumoasă) sunt satisfăcute, iar prop(un,băiat,frumoasă) sau prop(un,fată,scund) nu sunt satisfăcute. Aceasta se explică prin faptul că prima clauză din definiție asigură corespondența dintre articolul nehotărât, substantiv și adjectiv prin intermediul unificării la nivelul variabilei C.

Vom considera acum o altă fațetă a reprezentării prin clauze, care nu poate fi realizată cu gramaticile context free. Este vorba de concordanța semantică care există între diferite entități ale frazei. Să presupunem că dorim să definim sub formă clauzală un mecanism prin care să recunoaștem construcții de forma :

descrie cea mai frumoasă stradă din oraș

numește cel mai mare oraș din zonă

arată cea mai bogată zonă a țării

Iar construcții de forma :

descrie cea mai frumoasă țară din oraș

numește cel mai mare oraș din stradă

Să fie identificate construcții incorecte. Este evident că între cuvintele stradă, oraș, zonă, țară, trebuie să stabilim o relație de ordine. Vom presupune că atașăm fiecărui cuvânt menționat un număr natural, astfel încât două cuvinte diferite să aibă atașate numere diferite și ordinea dintre cuvinte este definită de relația de inegalitate dintre numerele naturale. În aceste condiții construcțiile corecte sunt de forma :

descrie cea mai frumoasă X din Y

numește cel mai mare X din Y

și alte propoziții de aceeași structură, unde numărul atașat lui X este mai mic decât cel atașat lui Y.

Descrierea clauzală a acestei gramatici este următoarea :

frază([X\L]) :verb(X),grup(L,_)

grup(L,K2) :grup_rep(L,K1,Q),prim(Q,Y,L1),

Leg(Y),grup (L1,K2),K1<K2.

grup(L,K):grup_rep(L,K,[])..

grup([x],K:subst(X,K).

grup_rep(L,K,Q):prim(l,Y,L1),entity(Y,C),

prim (L1,_,L2),prim(L2,Z,L3),

adj(Z,C),prim(L3,S,Q),subst(S,K).

prim([X\L],X,L)

Includerea acestei descrieri într-un limbaj Prolog nu este dificil de realizat. Un aspect mai puțin plăcut al descrierii de mai sus este legat de faptul că fraza trebuie dată sub formă de listă. În implementarea Prolog această problemă se rezolvă prin scrierea unei clauze care descompune o frază în cuvintele care o compun și introduce aceste cuvinte ca elemente ale unei liste, în ordinera în care apar în frază. Astfel în limbajul TURBO PROLOG obținem următorul program:

domains

lista=string*

predicates

fraza(lista)

grup(lista,integer)

grup_rep(lista,integer,lista)

leg(string)

prim(lista,string,lista)

verb(string)

subst(string,integer)

entity(string,string)

adj(string,string)

citeste(lista)

form(string,lista)

start

clauses

fraza([X\L]):verb(X),grup(L,_).

grup(L,K2) :grup_rep)L,K1,Q),prim(Q,Y,L1),

leg(Y),grup(L1,K2),K1<K2

grup(L,K2):grup_rep(L,K,[]).

grup([X,K]):subst(X,K).

grup_rep(L,K,Q):prim(L,Y,L1),entity(Y,C),

prim(L1,_,L2),prim(L2,Z,L3),

adj(Z,C),prim (L3,S,Q),subst(S,K).

prim([X\L],X,L).

verb(numeste).

verb(descrie).

subst(oras,1)

subst(zona,2).

subst(tara,3).

entity(cel,masc0).

entity(cea ,fem).

leg(din).

adj(mare,masc).

adj(mare,fem).

adj(frumos,masc)

adj(frumoasa,fem)

citeste(Y) :readln(X),form(X,Y).

form(X,[T]U]) :fronttoken(X,T,S),form(S,U).

form(“”,[]).

start:citeste(X),fraza(X).

Satisfacerea scopului start va avea ca efect citirea unei fraze de la tastatură, descompunerea acesteia în cuvintele care o compun și analiza sintactică corespunzătoare gramaticii. Ca exemple de fraze corecte putem enumera fraze de tipul:

numește cel mai mare oraș

numește cel mai frumos oraș din zonă

descrie cel mai frumos oraș din cea mai mare zonă din țară

În același timp fraze de tipul :

numește cea mai frumoasă țară din oraș

descrie cel mai frumoasă oraș

Nu sunt corecte. Prima frază încalcă ordinea dintre cuvinte stabilită de clauzele

Subst(oras,1).

Subst(zona,2).

Subst(tara,3).

2.3 Implementarea semanticii gramaticilor clauzal definite

Comunicarea cu calculatorul în limbaj natural presupune luarea în considerație a următoarelor două aspecte:

analiza sintactică a textului comunicat;

analiza semantică a textului care s-a dovedit corect din punct de vedere sintactic.

În consecință mai întâi se alege sau se proiectează un model matematic convenabil pentru descrierea sintaxei de comunicare. După alegerea unui model, problema se pune de a extrage semnificația frazelor comunicate sistemului prin intermediul interfeței. Această problemă se rezolvă ținând seama atât de modelul ales cât și de facilitățile oferite de limbajul în care se realizează implementarea.

Este evident că alegerea gramaticilor clauzal definite ca model pentru proiectarea interfeței de comunicare ne îndeamnă să realizăm implementarea corespunzătoare în limbajul prolog.

2.4 Rețele de tranziție de bază

În această secțiune vom prezenta un alt mecanism utilizat în procesarea limbajului natural și pentru aceasta vom analiza diagrama prezentată în următoarea figură.

Structura prezentată în această figură o numim diagramă de tranziție. Ea sugerează comportarea unui automat finit. Avem o mulțime de stări notate de la q0………..q7 și reprezentate cu dreptunghiuri. Între unele dintre acestea există legături reprezentate prin arce orientate. Aceste arce definesc trecerea de la o stare la alta. Stările în care nu intră nici un arc se numesc stări inițiale, iar stările din care nu iese nici un arc se numesc stări finale.

bilet

trateaza

primul al doilea

subiect din

lecție

FIG.1

Diagrama de tranziție

Diagrama de tranziție prelucrează o frază în sensul următor. Presupunem că fraza este descompusă în entități. În general aceste entități sunt cuvinte aparținând unor categorii sintactice ale limbajului. O succesiune (e1…….en) de entități se numește succesiune acceptată de diagramă dacă există o succesiune de stări (s0…….,sn) astfel încât :

s0 este stare inițială

sn este stare finală

pentru fiecare i{0,…..,n-1} există un arc de la starea si la starea si+1 pe care se gasește înscrisă entitatea ei+1.

Analizând diagrama de tranziție din figură constatăm că ea dispune de o singură stare inițială, q0 și două stări finale q6 și q7. Există numai două drumuri de la q0 la q6 și q7 , deci diagrama din această figură va accepta numai două fraze.

Evident cele două fraze sunt următoarele :

tratează primul subiect din lecție

tratează primul subiect din al doilea bilet

Prima frază va determina trecerea diagramei din starea q0 în q7, iar a doua frază va realiza trecerea din q0 în q6.

Pentru a extinde puterea generativă a diagramelor de tranziție vom înlocui entitățile arcelor cu categoriile sintactice care corespund acestora. În acest fel obținem figura următoare pe care o denumim rețea de tranziție de bază ; în literatura de specialitate se utilizează pentru acest concept prescurtarea BTN, care provine de la Basic Transition Network. În concluzie, o rețea de tranziție de bază este o diagramă de tranziție în care arcele nu sunt etichetate cu cuvinte ci cu categorii sintactice ale limbajului.

Dintr-o rețea de tranziție de bază se pot obține mai multe diagrame de tranziție dacă înlocuim categoriile sintactice cu cuvinte care aparțin acestor categorii. Nu este greu de observat că rețeaua de tranziție de bază acceptă fraze de tipul următor :

fotografiază prima scară din bloc

vizitează primul muzeu din ultima zonă

<subst>

<verb>

<num.> <num>

<subst.> <prep>

<subst>

FIG.2

Rețea de tranziție de bază

Puterea generativă a rețelelor de tranziție de bază este aceeași cu puterea automatelor finite sau, echivalent, cu puterea gramaticelor regulate. Să considerăm automatul finit reprezentat în figura următoare :

FIG.3

Considerăm că starea inițială este s1, iar s4 este singura stare finală, limbajul acceptat este {0(10)n}n0 . Reprezentarea din fig. 3 poate fi privită ca o shemă de tranziție de bază. Pentru aceasta vom remarca mai întâi faptul că unii autori consideră că trecerea de la o stare la alta într-o rețea de tranziție de bază se poate realiza și fără a consuma nici o entitate din textul analizat, adică se poate realiza un salt necondiționat la o altă stare, și în acest caz pe arcul respectiv se trece cuvântul JUMP. Pe de altă parte etichetele înscrise pe arcele de tranziție pot fi codificate astfel:

WRD w precizează faptul că tranziția respectivă trebuie să consume cuvântul w.

CAT xyz specifică faptul că trebuie să se consume o entitate aparținând categoriei sintactice xyz.

Cu aceste precizări avem următoarea schemă unde rețeaua de tranziție care acceptă același limbaj ca și automatul finit este prezentat în schema următoare :

WRD 0 WRD 1

WRD 0

JUMP

O rețea de tranziție poate fi descrisă nu numai sub formă grafică. Utilizând scrierea cu ajutorul listelor ca în limbajul Lisp, rețeaua din figura 4 poate fi descrisă sub forma :

( ( s1 (WRD 0 TO s2))

(s2 (WRD 1 TO s3))

(s3 (WRD 0 TO s2))

( s2(JUMP TO s4)))

Capitolul 3

Cunoștințe, reprezentarea lor și inferența

3.1 Sisteme de decizie și raționament prin mulțimi rough

3.1.1 Sisteme de decizie

Conceptul de mulțime rough a fost introdus de Z.Pawlak într-o lucrare apărută în 1982. Motivația inițială a introducerii acestui concept a fost necesitatea clasificării obiectelor unei mulțimi pe baza cunoștințelor despre acestea. În cazul în care nu există suficiente informații despre obiecte astfel încât să se obțină o clasificare exactă și totală a acestora, s-a pus problema de a se obține o aproximare a clasificării.

Au fost dezvoltate multe sisteme de reprezentare și procesare a cunoștințelor bazate pe teoria mulțimilor rough :

Analiza de imagini și baze de date în domeniul medical

Evaluarea riscului de faliment, politici de credite bancare

Teoria controlului, procesarea semnalelor și analiza de imagini în inginerie

Regăsirea informațiilor din data mining

Analiza conflictelor sociale și a preferințelor din alegeri

Ca și în alte sisteme de reprezentare și procesare a cunoștințelor, reprezentarea bazată pe mulțimi rough utilizează conceptul de atribut atașat unui obiect. Totuși trebuie să evidențiem faptul că în timp ce în teoria cadrelor fiecare obiect poate avea atributele sale, în teoria mulțimilor rough toate obiectele se bucură de aceleași atribute. Valorile acestor atribute pentru fiecare obiect al sistemului formează cunoștințele pe baza cărora se efectuează raționamente și se obțin concluzii.

Un sistem de informații este o pereche A=(U,A), unde :

U este o mulțime finită și nevidă de elemente numite obiecte

A este o mulțime finită și nevidă de atribute

Atributele sunt atașate elementelor lui U. Deoarece fiecare atribut are o valoare atașată fiecărui obiect, putem considera că un atribut oarecare aA este o funcție a : U Va , unde Va este mulțimea valorilor atributului. Dacă notăm

A={a1,………..,ak) mulțimea atributelor, atunci mulțimea valorilor acestor funcții poate fi descrisă de un tabel care are k coloane și atâtea linii câte elemete are mulțimea U. Dacă U={o1,……..os} atunci obținem o mulțime de date de tipul următor :

Tabelul 1

Invers dacă pornim de la un asemenea tabel putem reconstitui elementele sistemului de informații de la care se pleacă. De exemplu tabelul următor este atașat sistemului A=(U,A), unde

U={Petre,Ana,Maria,George}

A={studii,vârstă,salariu}

Vvârstă={33,45,29,36} cu vârsta :UVvârstă,

vârsta(Petre)=33,vârsta(Ana)=45 și așa mai departe.

În general nu se impun condiții speciale atributelor unui sistem. De exemplu se acceptă cazul în care un atribut oarecare a, nu este o funcție injectivă. Aceasta înseamnă că este posibil să existe o1o2 astfel încât a(o1)=a(o2). Dacă se întâmplă această situație spunem că obiectele o1 și o2 sunt indiscernabile din punct de vedere al atributului a.

Un sistem de decizie este un sistem de informații A=(U,A{d}), unde atributul d este evidențiat separat de celelalte atribute deoarece joacă un rol special. El se numește atribut de decizie.

Tabelul 2

Tabelul 3

Nu sunt rare cazurile când acest atribut este binar, adică are două valori. Atributul de decizie este în general utilizat pentru a obține o clasificare a obiectelor. Sistemul de informații considerat anterior devine sistem de decizie în cazul în care adăugăm atributul sex cu valoarea M pentru masculine și F pentru feminine.

Pe baza atributului de decizie sex se obține o clasificare a obiectelor sistemului în două clase : {Petre,George} și {Ana,Maria}. În general valorile atributului de decizie sunt valori calculate. Aceste valori se obțin din aplicarea unei reguli de forma IF condiție THEN, unde condiție este o expresie logică formată cu ajutorul atributelor din A.

Considerăm datele din tabelul următor. Atributul de decizie are numele selectat. El provine din selectarea unor persoane prezentate la interviu în vederea angajării. Condițiile de angajare sunt următoarele :

Studii superioare în informatică cu vechime peste 15 ani în activitate

Tehnoredactor cu studii medii și vechime cel mult 15 ani

Ajutor programator cu studii medii, atestat, vechime în muncă cel mult 20 de ani

Tabelul 4

pentru orice persoană care indeplineste una din aceste condiții valoarea atributului selectat este Da; pentru toate celelalte cazuri valoarea atributului este Nu.

Exprimarea sub formă de regulă a condițiilor de angajare este următoarea :

IF c1(x)c2(x)c3(x) THEN seclectat (x)=DA

Unde:

C1(x):(studii(x)=sup)(calific(x)=inform)

(vechime(x)>15)

C2(x):(studii(x)=medii)(calific(x)=tehnored)

(vechime (x)10)

C3(x):(studii(x)=medii)(calific(x)=atestat aj-progr)

(vechime(x)20)

Din exprimarea regulei se subînțelege că în cazul în care condiția exprimată este falsă atunci selectat(x)=NU

Muțimi rough

Considerăm un sistem de informații A=(U,A) și BA o submulțime a mulțimii de atribute. Mulțimea de atribute B induce o relație binară I N D(B)UU definită astfel:

I N D (B)={(x,y)UUaB:a(x)=a(y)}

Relația I N D(B) este reflexivă, simetrică și tranzitivă, deci este o relație de echivalență. Prin această relație mulțimea de obiecte U se partiționeză în clase de echivalență.

Pentru sistemul reprezentat în tabelul 4 avem următoarele partiții în funcție de alegerea mulțimii B.

U/I N D {studii}={{Petre,Maria,Ion},{Ana,George,Elena}}

U/I N D{studii,calific}}={{Petre,Ion},{Ana,Elena},

{Maria},{George}}

Se observă că luând două obiecte oarecare ale unei clase de echivalență, acestea au aceleași valori pentru atributele din B. Astfel avem :

Studii(Petre)=studii(Ion)

Calific(Petre)=calific(Ion)

În cazul B={studii,calific}, obiectele Petre și Ion formează o clasă de echivalență. Deoarece atributele studii și calific au aceleași valori atât pentru obiectul Petre cât și pentru obiectul Ion aceste două obiecte nu se pot distinge unul de celălalt prin utilizarea valorilor atributelor din B. De aceea obiectele unei clase de echivalență se numesc obiecte B-indiscernabile.

Clasa de echivalență a unui obiect xU în raport cu mulțimea de atribute B va fi notată cu [x]B.

O mulțime XU se numește mulțime rough pe baza cunoștințelor din B dacă BNB(X). Mulțimea X se numește mulțime crisp pe baza cunoștințelor din B dacă

BNB(X)=

Altfel, o mulțime este mulțime rough dacă există elemente posibil apartenente lui X care nu aparțin cu certitudine lui X, se observă de asemenea că o submulțime dată este ori mulțime rough ori mulțime crisp

3.2. Reprezentarea și utilizarea incertitudinii

3.2.1 Factori de certitudine

În general cunoștințele pot fi clasificate în două mari categorii:

Cunoștințe primare

Cunoștințe deduse

Cunoștințele primare sunt în general valori de atribute ale unor obiecte, iar aceste valori se obțin fie din piese de cunoștințe, ca valori imediate, fie prin observare, cum ar fi :

Constatarea temperaturii ridicate la om ;

Funcționarea anormală a unui aparat ;

Dezvoltarea anormală a unui microorganism ;

Deprecierea calității unei șosele ;

Sunt cunoștințe observabile.

Cunoștințele deduse sunt acele valori ale atributelor care se obțin pe baza unui raționament. Ele se obțin din cunoștințe primare sau alte cunoștințe deduse anterior prin utilizarea unor reguli de raționament.

De multe ori raționamentul se obține prin aplicarea unor reguli de forma :

IF condiție THEN efect

În particular cunoștințele incerte pot fi primare sau deduse. Reprezentarea și procesarea cunoștințelor incerte presupune:

– alegerea unui interval [a,b] al axei reale din care se iau valori pentru factorii de incertitudine;

– stabilirea cunoștințelor incerte primare și atașarea factorilor de certitudine acestora

– stabilirea structurii cunoștințelor deduse și limitelor privind capacitatea de raționament, adică stabilirea dimensiunilor spațiului de raționament ;

– stabilirea legăturilor de forma cauză efect , adică a regulilor de forma IF…..Then…. :

– definirea unui model matematic de combinare și/sau ajustare a factorilor de certitudine pentru cunoștințele deduse ;

– stabilirea modului de raționament, adică, definirea stategiei de combinare a regulilor ;

– implementarea pe calculator.

Factorul de certitudine atașat unui atribut, luat din intervalul [a,b], indică gradul de cunoaștere a valorii atributului. Dacă valoarea acestuia este a, adică extremitatea stângă a intervalului, atunci valoarea atributului prezintă maximum de incertitudine. Dacă factorul de certitudine este extremitatea dreaptă a intevalului [a,b] atunci valoarea atributului este certă. Toate celelalte valori ale intevalului deschis(a,b) arată un grad mai mare sau mai mic al certitudinii. Dacă certitudinea este mare, atunci incertitudinea este mică și invers.

În logica binară orice informație este ori adevărată, ori falsă. Reprezentând cunoștințele în acest sistem, orice răspuns la o întrebare nu poate fi decât Da sau Nu. În reprezentarea cunoștințelor incerte vom considera că orice propoziție este adevărată și vom specifica un factor de certitudine al adevărului. Astfel, dacă considerăm că factorii de certitudine se iau din intervalul [0,1] și notăm cu fc factorul de certitudine atunci :

Enunțul afară plouă fc 0 ne sugerează semnificația faptului că afară nu plouă

Enunțul afară plouă fc 0.6 ne transmite informația că afară plouă destul de mult, dar mai puțin decât ne transmite enunțul :

Afară plouă fc 0.9

3.2.2 Sisteme de diagnosticare

Sistemele de diagnosticare sunt o categorie importantă de sisteme de reprezentare și procesare a cunoștințelor care stabilesc pe baza unor cunoștințe o concluzie numită diagnostic.

Ele se utilizează în diagnoza unor maladii, a unei funcționări necorespunzătoare a unor mecanisme sau procese. Se mai spune că ele identifică defectele sau anumite stări ale obictelor.

Proiectarea unui sistem de diagnosticare presupune parcurgerea următoarelor etape :

fixarea domeniului general în care va fi utilizat sistemul: medical, juridic, mecanic;

stabilirea cunoștințelor primare;

stabilirea cunoștințelor deductibile și a regulilor de deducție.

Prin stabilirea cunoștințelor primare se înțelege identificarea cunoștințelor particulare privind un obiect, care sunt necesare stabilirii unui diagnostic. În vederea obținerii acestor date sistemul poartă un dialog cu utilizatorul. Acesta este modelat în cadrul unei interfețe de comunicare, care are un dublu rol :

utilizatorul este interogat cu privire la faptele observate de acesta ;

se transmite utilizatorului diagnosticul stabilit de sistem.

Vom descrie mai jos proiectarea și implementarea unui sistem de diagnosticare în care se prezintă și se procesează cunoștințe incerte. În vederea proiectării acestuia este necesar să stabilim următoarele :

ce întrebări se pot pune utilizatorului

care sunt problemele pe care le poate rezova sistemul

Întrebările adresate utilizatorului au scopul de a stabili cunoștințele primare în vederea diagnosticării. Este evident că nu orice întrebare poate fi pusă utilizatorului. Pe de altă parte, orice sistem de diagnosticare poate identifica numai anumite cauze și prin urmare el are anumite limite cu privire la capacitatea sa de acțiune. Stabilirea problemelor pe care le poate rezolva sistemul conduce la definirea competențelor sale.

Se notează cu IP={s1,…….,sk} o mulțime de simboluri, fiecare simbol reprezentând o întrebare care se poate pune utilizatorului. Proiectantul sistemului deține o corespondență între simbolul si IP și întrebarea efectivă pe care o reprezintă.

Notăm cu PR={p1,………,pn} o mulțime de simboluri, fiecare reprezentând o problemă pe care o poate rezolva sistemul. Mulțimea PR definește limitele capacității de diagnosticare a sistemului. Notăm cu SI={q1,……….,qn} o mulțime de simboluri, fiecare reprezentând o cunoștință parțială dedusă prin raționament. Baza de cunoștințe utilizată de sistem va fi alcătuită din faptele observate de utilizator și reguli de forma :

IF condiție THEN concluzie fc z

În care:

condiție este o expresie logică formată cu ajutorul simbolurilor din IP și PR;

concluzie este un simbol din SI și PR ;

z este factorul de certitudine pentru concluzie.

Fără să restrângem din generalitate se poate presupune că expresia logică condiție este o conjuncție de simboluri din IPSI.

Orice regulă în care apare disjuncția în condiție se poate descompune într-o mulțime finită de reguli care satisfac cerința formulată. Astfel regula :

IF (ab)c THEN d fc z

Se poate substitui pe baza calculului Boolean cu următoarele două reguli :

IF ac THEN d fc z

IF bc THEN d fc z

Utilizatorul va răspunde întotdeauna cu Da la întrebările puse de sistem, chiar dacă are loc negația enunțului afișat. Aceasta se explică prin faptul că utilizatorul va indica un factor de incertitudine al adevărului. Astfel se presupune că factorii de certitudine sunt reprezentați în intervalul [0,1] și că printre simtomele unui pacient nu se află simtomul tuse uscată. La întrebarea « «  Pacientul prezintă tuse uscată ?? » » utilizatorul va răspunde Da fc 0 .

Raționamentul se realizează de către un motor de inferențe. Acesta va combina elementele bazei de cunoștințe pentru a obține concluzii parțiale și apoi concluzia finală. Există următoarele trei metode de combinare a acestor elemente :

metoda forward

metoda backward

metoda combinată forward+backward

Metoda forward pleacă de la faptele cunoscute. Motorul de inferentă caută acele reguli în care expresia condiție se reprezintă numai prin fapte cunoscute (cunoștințe primare sau fapte deduse). O regulă devine aplicabilă dacă toate componentele din expresia condiție a regulei respective sunt cunoscute.

Se consideră prima regulă aplicabilă. Concluzia acesteia devine un fapt cunoscut. Urmând o anumită strategie se identifică următoarea regulă aplicabilă și acest proces continuă până se ajunge la o regulă în care concluzie este identică cu una din problemele pe care le poate rezolva sistemul. Denumirea metodei provine de la faptul că fiecare regulă se aplică de la condiție la concluzie.

Descrierea matematică a metodei forward este următoarea. Vom nota cu Ri(c1,……,ck;d) faptul că regula Ri este de forma :

IF c1………..ck THEN d

Unde expresia logică c1………ck are valoarea logică TRUE.

Metoda backward aplică o regulă de la concluzie la condiție, algoritmul acestei reguli este următorul : pentru fiecare piPR considerăm toate regulile pentru care concluzie =pi ; pi se numește scop al raționamentului și motorul de inferențe caută să stabilească dacă nu scopul poate fi satisfăcut.

Printr-o anumită strategie specifică motorului de inferențe se alege una din regulile pentru care concluzie =pi. Se analizează premisa regulei. Dacă ea este logic adevărată, atu atunci o soluție a problemei este pi. Dacă premisa este falsă atunci se extrage o altă regulă. Dacă premisa nu este nici adevărată și nici falsă, atunci ea conține simboluri a căror valoare este necunoscută și aceste simboluri devin scopuri parțiale sau subscopuri pe care sistemul urmărește să le satisfacă.

Prin urmare scopul final este fie satisfăcut direct prin intermediul unei reguli pentru care premisa este adevărată pe baza faptelor , fie că este descompus în subscopuri pentru care se aplică aceeași metodă.

Considerând că avem aceeași bază de cunoștințe ca în cazul metodei forward, avem următoarele reguli de analizat:

Nici o regulă nu poate să satisfacă pe p1 sau pe p2 direct din cunoștințele primare ;

Se alege a treia regulă, scopul este p1. Premisa d=9b4 conduce la considerarea subscopului d=9. Dar condiția d=9 nu poate fi satisfăcută nici de prima, nici de a doua regulă.

Se alege a patra regula, scopul este p2. Este necesar să se verifice satisfacerea subscopului d9. Se selectează prima regulă. Dacă utilizatorul a răspuns prin dialog cu a=5 și b=7 atunci soluția identificată este p2, altfel sistemul nu poate identifica soluția.

Metoda combinată utilizează o anumită strategie prin care în anumite condiții raționamentul se ghidează după metoda backward (sau forward) și în continuare se aplică metoda forward (sau backward). Secvențele de metode alternează, iar unele motoare de inferență acceptă intervenția utilizatorului cu privire la momentele de timp în care se aplică o metodă sau alta.

Cele trei metode prezentate mai sus se aplică în particular pentru cazul cunoștințelor incerte.

Proiectarea și implementarea unui sistem de diagnosticare cu factori de certitudine trebuie să țină seama de următoarele elemente :

Limbajul în care se face implementarea

Prezența factorilor de certitudine în fapte sau reguli

Modul de reprezentare a faptelor și a regulilor, adică reprezentarea elementelor bazei de cunoștințe

Metoda de combinare a factorilor de certitudine din premisa unei reguli cu factorul de certitudine din concluzie.

Ajustarea factorilor de certitudine pentru cunoștințele deduse

Stabilirea unui prag de veridicitate a cunoștințelor; toate cunoștințele care au factor de certitudine sub acest prag nu se iau în considerare în procesul de raționament

Strategia de combinare a regulilor

3.3 Rețele semantice

3.3.1 Mediu de raționament

Rețeaua semantică este o metodă de tip graf pentru reprezentarea cunoștințelor. Graful prezintă anumite particularități, iar procesarea cunoștințelor se face prin combinarea conceptelor și rezultatelor generale din teoria grafurilor cu cele specifice reprezentării.

Rețeaua semantică este o metodă de reprezentare a cunoștințelor, care permite efectuarea de deducții automate. Primul tip de rețea semantică care a apărut în literatură a utilizat un mecanism de deducție bazat pe moștenire. Acest tip de raționament poate fi descris prin utilizarea anumitor reguli :

Dacă orice x este y și orice y este z atunci orice x este z

Dacă x este y și orice y este z atunci x este z

Dacă orice x este y și y este z atunci orice x este z

Dacă x este y și y este z atunci x este z

Mai jos se va prezenta un tip de rețea semantică, și vom vedea cum pot fi reprezentate cunoștințele într-o astfel de rețea, cum se analizează deducția și cum se implementează o astfel de structură.

Prin piesa de cunoștințe se înțelege o mulțime finită de propoziții sau fraze enunțate în mod natural. Se presupune că această mulțime nu conține propoziții interogative, nici propoziții exclamative și nici reguli de forma dacă…atunci.

Pentru a reprezenta o piesă de cunoștințe sub forma unei rețele semantice este necesar să punem în evidență pe de o parte obiectele prezentate în piesa de cunoștințe și pe de altă parte relațiile care există între acestea. Vom desemna obiectele pisei de cunoștințe prin numele lor . Fiecărei relații binare i se atașează o etichetă prin intermediul căreia ne referim la relația respectivă.

Fie X o mulțime finită. O relație pe X este o submulțime XX. Dacă =, atunci se numește relație vidă.

Fie 1 și 2 două relații binare pe X . Notăm cu 1 2 următoarea relație binară : (x,y) 12 dacă și numai dacă există z astfel încât (x,y)1 și ( z,y)2.

a

Figura. Arc orientat

Este cunoscut faptul că operația de compunere a relațiilor este asociativă. De asemenea putem avea 12= chiar dacă 1 și 2.

Definiție : Considerăm două mulțimi finite X și L0 astfel încât XL0=. Un element al lui X se numește etichetă de cod. Elementele lui L0 se numesc etichete de arce. Fie T0 o mulțime de relații binare pe X astfel încât T0. Fie f0 :L0T0 o funcție surjectivă. Sistemul (X,L0,T0,f0) se numește graf etichetat.

Un graf etichetat G=(X,L0,T0,f0) se reprezintă astfel : fiecare element al lui X va desemna un nod al graficului, care va fi reprezentat printr-un dreptunghi în interiorul căruia se scrie elementul respectiv ; se trasează un arc orientat de la nodul xX la nodul yX și acest arc se etichetează cu elementul a L0 dacă și numai dacă (x,y)f0(a). Din punct de vedere grafic situația se prezintă ca în figura anterioară.

Deoarece funcția f0 este surjectivă, orice relație din T0 are cel puțin o reprezentare etichetată cu un element din L0.

Dacă se consideră un tuplu (X,L0,T0,f0) care satisfac definiția de mai sus, atunci el admite o reprezentare grafică de forma unui graf orientat în care arcele sunt etichetate cu elemente din L0. Un exemplu de graf etichetat este prezentat în figura următoare :

b b

a a a

Invers, dacă se consideră reprezentarea unui graf etichetat cum este cea din figura de mai sus, atunci din reprezentarea respectivă putem extrage relațiile binare și funcția de etichetare f0. Dacă extragem toate perechile de noduri care sunt unite cu arce etichetate cu același simbol, obținem aceste elemente. Pentru graful de mai sus se obțin :

1={(x1,x2),(x2,x3),(x3,x4)} ; f0(a)=1

2={(x1,x2),(x2,x3)}; f0(b)=2

3={(x1,x3),(x3,x4)}; f0(c)=3

Considerăm o piesă de cunoștințe P. Notăm cu X mulțimea obiectelor prezentate în piesa P și cu L0 mulțimea etichetelor care desemnează relațiile binare specificate în piesa respectivă. Pentru exemplificare să considerăm următoarea piesă K1:

Orice aliment are gust și miros. Brânza este un aliment. Ea este albă. Orice pasăre are aripi și pene. Somonul este un pește. El este roz. Orice pește este un animal. Orice pasăre este un animal. Orice pește este un tip de aliment. Bob este un papagal. Orice papagal este o pasăre.

Din enunțul piesei K1 extragem următoarea mulțime de obiecte:

X={aliment, gust, miros, pasăre, pene, aripi, somonul, pește,

Roz, albă, animal, Bob, papagal, brânză}

Se observă că obiectele unei cunoștințe pot fi obiecte particulare (cum este Bob), obiecte generale (aliment, animal) obiecte abstracte (gust, miros) și atribute (culoarea alba, roz).

Pentru a stabili care sunt relațiile binare din piesa K1 trebuie să extragem semnificația asociată unei perechi de obiecte. Vom obține următoarele relații binare:

1={(aliment,gust), (aliment,miros), (pasăre,aripi), (pasăre,pene)}

2={(somonul, pește), (brânză, aliment)}

3={(somonul, roz), (brânză, albă)}

4={(pește, animal), (pasăre, animal), (papagal, pasăre)}

5={(Bob, papagal)}

6={(pește,aliment)}

Observăm că pentru fiecare pereche (x,y) care aparține unei relații, avem o anumită semnificație care leagă obiectul x de obiectul y și această semnificație este aceeași pentru toate perechile unei relații date, astfel faptului că (x,y)4 îi este asociată semnificația orice x este un y.

Notăm T0={1, 2, 3 , 4, 5, 6}

L0={a1 , a2, a3, a4, a5, a6}

Și considerăm funcția f0 : L0 T0 definită prin f0(ai)=I pentru i{1,……,6}. Se obține următorul graf etichetat :

alba

a3 a1

a2 a4

a6

a2 a4

a4

a3

a5 a4

a1 a1

Pentru a justifica necesitatea ca funcția f0 să fie surjectivă vom presupune că avem piesa de cunoștințe K2 care provine din K1 prin înlocuirea propoziției Bob este un papagal cu propozițiile Bob vorbește ca un papagal și Bob are figură de papagal. Pentru piesa K2 vom avea aceleași relații binare , dar pentru relația 5 avem nevoie de două etichete deoarece obiectul Bob este legat de obiectul papagal în două moduri cu semnificații diferite.

Din punct de vedere intuitiv, fiecare etichetă x specifică o anumită semnificație atașată perechilor din relația binară f0(x). În consecință, trebuie să combinăm aceste semnificații pentru a obține proprietăți existente între alte obiecte ale piesei de cunoștințe. Ele vor fi obținute cu ajutorul unui mecanism de deducție. De exemplu, un asemenea mecanism ar trebui să deducă că din proprietățile Bob este pasăre și Orice pasăre are aripi să deducă proprietatea Bob are aripi.

Definiție. Fie X o mulțime finită și T02*. Notăm cu C(T0) cea mai mică mulțime A2* care satisface următoarele proprietăți :

T0A

Dacă d1,d2A și d1d2 atunci d1d2 A.

Propoziția care urmează ne conduce la un algoritm prin care putem calcula mulțimea C(T0).

Secvența {Xn}n definită prin :

X0=T0

Xn+1=Xn{dd1,d2Xn :d=d1d2}, n0

Satisfac următoarele proprietăți :

XnXn+1 pentru orice n0

Dacă Xn=Xn1 atunci Xn=Xnp pentru orice p1.

C(T0)=Xp, unde peste cel mai mic număr n care satisface condiția anterioară.

Fie A și B două mulțimi de relații binare pe o mulțime X. Se notează

AB={1A, 2B:=12}

Fie T02*. O mulțime T care satisface proprietățile:

T0TC(T0)

Există un număr natural n și există o secvență crescătoare T0……..Tn=T astfel încât

Ti-1TiTi-1Ti-1Ti-1 pentru orice i{1,…,n} se numește mediu de raționament pentru T0.

3.3.2 Rețele semantice elementare

Din punct de vedere intuitiv, faptele afirmate de o piesă de cunoștințe sunt reprezentate de elementele lui T0 și L0. Dimensiunea raționamentului într-o rețea semantică este dată de dimensiunea mulțimii T\T0 deoarece numai aceste elemente pot fi obținute prin mecanismul de raționament. Mulțimea T\T0 încorporează în general metanivelul cunoașterii. În particular pentru T-T0 obținem un proces degenerat de raționament deoarece în acest caz numai elementele prezentate direct în piesa de cunoștințe pot fi deduse.

Semantica noilor proprietăți va fi specificată cu ajutorul unor etichete atașate și a unui spațiu care definește semantica.

Definiție. Considerăm graful etichetat G=(X,L0,T0,f0). Fie T un mediu de raționament pentru T0. O rețea semantică elementară peste (G,T) este un tuplu (G,T,L,f,, g,S), unde :

L0L și L se numește spațiul etichetelor

 :LxL L este o operație algebrică parțială pe spațiul etichetelor, care se numește compunerea etichetelor

f :LT este o expresie surjectivă a lui f0 astfel încât dacă (a,b)dom() atunci f ((a,b))=f(a)f(b).

S este o mulțime care se numește spațiu semantic

g :X x L x XS este numită aplicația semantică.

În general, deoarece răspunsul la o interogare se dă în limbaj natural, spațiul semantic S este o mulțime de enunțuri ale acestui limbaj. Spunem că în acest caz utilizăm semantica de comunicare. Din punct de vedere intuitiv, g(x, e , y) specifica semantică este o etichetă pentru o anumită relație binară care conține perechea (x,y).

Pentru a specifica un drum într-un graf etichetat G=(X,L0,T0,f0) nu este suficient să enumerăm lista nodurilor acestuia deoarece arcele sunt etichetate și doă noduri pot fi unite cu două arce pe care se găsesc etichete diferite. De aceea un drum d de la x la y în G este o pereche d=([x1,x2,……..xn+1],[e1,……..en] astfel încât să fie îndeplinite următoarele proprietăți :

x1,……..,xn+1X

e1,……..,enL0.

x1=x, xn+1=y

(xi, xi+1)f0(ei) pentru orice i{1,……,n}.

Notăm cu D(x,y) mulțimea tuturor drumurilor de la x la y în graful etichetat G. Daca d=([x1, x2, ……,xn+1],[e1,..…en])D(x,y)

atunci vom nota pr2d=(e1……..en)

Se definește recursiv aplicația parțială

 :i 2 Li L

prin următoarele relații :

(e1,e2)=(e1,e2)

(e1,e2, ……en)=((e1,e2,…..en-1),en) pentru n3.

Facem precizarea că (e1,e2) este definit dacă și numai dacă (e1,e2) este definit dacă și numai dacă (e1,……en-1) și ((e1,…..en-1),en) sunt elemente definite.

Definiție. Considerăm o rețea semantică elementară (G, T, L, f, , g, S). Definim aplicația:

deduc:X x X2s prin

deduc(x, y)={g(x, (pr2d), y)/ dD(x, y)} dacă D(x, y)0 și

deduc(x, y)= dacă nu este satisfăcută condiția de mai sus.

Pentru realizarea inferenței într-o rețea semantică elementară, se consideră două obiecte oarecare x și y. Se calculează deduc(x, y) și cu ajutorul acestei valori se obține valoarea funcției Ans în (x, y) conform următoarei definiții :

Definiție. Răpunsul la o interogare este dat de aplicația Ans

definită prin :

Ans : X x X=deduc(x, y) dacă deduc(x, y) și

Ans(x, y)= unknown dacă nu este satisfăcută condiția.

În continuare vom prezenta implementarea în BORLAND PROLOG a mecanismului de deducție prezentat :

domains

nod=symbol

nodlist=nod*

database

d(nod, nod, nod)

fi(nod, nod, nod)

nr_solutii(integer)

predicates

go(nod, nod)

append(nodlist, nodlist, nodlist)

drum(nod, nod, nodlist, nodlist)

prim(nodlist, nod, nodlist)

compun(integer, nodlist, nod)

nr_list(nodlist, integer)

member(nod, nodlist)

explica(nodlist, nodlist, char)

deduc(nodlist, nod)

start

include “sem.pro”

clauses

Motorul de inferențe

go(Aici,Acolo):-drum(Aici,Acolo,,[Aici],fail

go (_,_) :-nr.soluții(k),k=0,

Write(“NU EXISTĂ SOLUȚII”)

gO(_,_)

drum(N,N,Ev,Nv):-deduc(Ev,K),concluzia(Nv,K),nl,

write(“Doriți explicații?(y/n)”),

nl,readchar(T),explică(Ev,Nv,T),

nr_soluții(KS),K1=KS+1,

retract(nr_soluții(KS)),

assert(nr_soluții(K1)).

drum(N,V,Ev,Nv) :-d(N,Y,Z),not(member(Y,Nv)),

append (Nv,[Y],N1),append(Ev,[Z],E),

drum(Y,V,E,N1).

deduc(Ev,K) :nr_list(Ev,N),compun(N,Ev,K).

compun(1,[X],X).

compun(N,E,X) :-n>=2,prim(E,Y,L),prim(L,Z,U),fi(Y,Z,T),

NN=N-1,compun(NN,[T/U],X).

concluzia(Nv,K) :-prim(Nv,Y,L),uelem(l,Z),

Semantica(Y,Z,K).

Modulul de explicații

explică([X/Ev],[U/Nv], ‘y’) :-prim(Nv,V,_),

Semantica(U,V,X),nl,explică(ev,Nv,’y’).

explică(,_,’y’).

explică(_,_,_).

Predicate auxiliare

nr_list(,0).

nr_list([_/H],N) :_nr_list(H,NN), N=NN+1.

append(,L,L).

append([X/L1],L2,[x/l3]):_append(l1,L2,L3).

prim(Q/R],Q,R).

member(x,[x/_]).

member(x,[_/Y]):-member(X,Y).

eelem( [H],H).

uelem([_/L],X:-uelem(L,X)

start:-write(“DAȚI NUMELE BAZEI UTILIZATE:”),

readln(M),concat(M,”.dat”,KM),consult(KM),

wRITE(“DAȚI NUMELE PRIMULUI OBIECT:”),

readln(X),nl,

write(“DAȚI AL DOILEA OBIECT:”),

readln(y),nl,assert(nr_soluții(0)),go(X,Y).

goal

clearwindow,start.

Referitor la implementarea de mai sus facem următoarele precizări:

predicatul fi are trei argumente : fi(a,b,c) are valoarea TRUE dacă și numai dacă c=(a,b).

modulul sem.pro conține clauzele care definesc aplicația g

baza de cunoștințe solicitată are numele cu extensia dat și conține definiția grafului sub formă de clauze de forma d(x, y, z) unde x și y sunt noduri ale grafului, iar z este eticheta arcului care leagă nodul x de y ; de asemenea, această bază conține definițiile predicatului fi.

3.3.3 Rețele semantice cu drumuri confluente

Într-o rețea semantică elementară se pot defini la nivel de meta-cunoștință relații noi în comparație cu implementarea variantei anterioare, pentru aceasta se utilizează conceptul de drumuri confluente.

Definiție. Drumurile p1D(x,z) și p2D(y,z) se numesc drumuri confluente, astfel între obiectele x și y se stabilește o relație nouă care este legată de faptul că cele două drumuri conduc la același obiect z.

Considerăm o rețea semantică elementară RS=(G,T,L,f,,g,S) și o operație algebrică parțială :

Confluent :LxLL

Perechea (RS,confluent) se numește rețea semantică cu drumuri confuente.

Procesarea cunoștințelor într-o rețea semantică cu drumuri confluente presupune procesarea din varianta rețelei semantice elementare și în plus se utilizează drumurile confluente în sensul următor :

să notăm p1=([x1, …….,xn+1],[a1,……an])

p2=([y1,………,yk+1],[b1,……bk])

două drumuri din rețeaua RS.

Presupunem că xn+1=yk+1, deci p1 și p2 sunt drumuri confluente

Dacă funcția confluent este definită în ((pr2p1), (pr2p2)) și valoarea ei este etic atunci etic este eticheta unei relații de la nodul x1 la nodul y2.

Operația confluent nu este neapărat comutativă. Într-adevăr, dacă compusa etichetelor lui p1 este a și compusa etichetelor lui p2 este b atunci confluent(a,b) va reprezenta, dacă este definită, eticheta unei relații din care face parte perechea (x1,y1), iar confluent(b,a) va reprezenta, dacă este definită eticheta unei relații din care face parte (y1,x1). Desigur că există posibilitatea ca elementul confluent(a,b) să fie definit iar confuent(b,a) să nu fie definit.

Pentru a prezenta modul în care se procedează în cazul drumurilor confluente să considerăm următoarea piesă de cunoștințe pe care o vom nota K :

Petre este fiul Mariei, iar Ana este fiica acesteia. Maria este soția lui Ion. Jean este șoferul lui Petre. Ana este mama lui Rodica. Rodica învață la Școala Generală nr.1.Petre este prieten cu Ștefan. Ștefan este director la Școala Generală nr.1.

Graful etichetat care corespunde acestei piese este reprezentat în figura următoare :

director învață

prieten mama

fiu fiica

șofer soția

Graf pentru K etichetat

Relațiile primare ale piesei K sunt următoarele :

1={(Petre, Maria)} ; 2={(Ana, Maria)} ;

3={(Maria, Ion)} ; 4={(Jean, Petre)} ;

5={(Petre, Ștefan)} ; 6={(Ana, Rodica)} ;

7={(Ștefan, SG1)} ; 8={(Rodica, SG1)} ;

Este evident că există perechi care beneficiază de confluența drumurilor (Petre, Ana), (Jean, Ana) și altele. Astfel din faptul că Petre este fiul lui Maria și Ana este fiica Mariei putem deduce că Petre este fratele lui Ana și Ana este sora lui Petre.

Considerăm următoarele mulțimi de etichete :

L0={fiu, fiică, soția, șofer, prieten, mamă, învăța, director}

L =L0{a, b, c, frate, soră, pd, mi, pdmi}

Și funcția f0 definită prin :

f0(fiu)=1, f0(fiică)=2, f0(soția)=3, f0(șofer)=4,

f0(prieten)=5, f0(mamă)=6,

f0(director)=7, f0(învăța)=8

Definim compunerea etichetelor :

(fiu, soția)=fiu ;

(fiica,soția)=fiica ;

(șofer,fiu)=a ;

(prieten, director)=pd ;

(mama, învăța)=mi ;

și următoarea operație algebrică parțială :

confluent(fiu, fiică)=frate ;

confluent(fiică, fiu)=soră ;

confluent(a, fiică)=b ;

confluent(fiică, a)=c ;

confluent(pd, mi)=pdmi 

se notează CONFL(x, y)= zX [D(x,y) x D(y,z)]

Sc(x,y)= {g(x,e,y)\ e=(p,q),

Cu (p,q)CONFL(x,y) si (p,q)=confluent((pr2p), ((pr2q)).

Definiție. Funcția Ansc:X x X2s definită prin

Ansc(x, y)=

Ans(x,y)Sc(x, y) dacă Ans(x,y)unknown

Sc(x,y) dacă Ans(x,y)=unknown, Sc(x,y)

unknown dacă Ans(x,y)=unknown, Sc(x,y)=

se numește funcția răspuns pentru rețele semantice cu drumuri confluente. Mai jos vom prezenta implementarea funcției Sc , iar cele prezentate anterior ne determină să considerăm următoarea bază de cunoștințe :

d(“Petre”,”Maria”,”fiu”)

d(“Ana”,”Maria”,”fiică”)

d(“Maria”,”Ion”,”soție”)

d(“Jean”,”Petre”,”șofer”)

d(“Petre”,”Ștefan”,”prieten”)

d(“Ștefan”,”SG1”,”director”)

d(“Ana”,”Rodica”,”mama”)

d(”Rodica”,”SG1”,”învăța”)

fi(“prieten”,”director”,”pd”)

fi(“mama”,”învăța”,”mi”)

fi(“ șofer “ ,“fiu”,”a”)

fi(“fiu”,”soție”, “fiu”)

fi(“ fiică “, “soție “, “fiică “)

confluent(“a “,”fiică”,”b”)

confluent(“fiică”,”a”,”c”)

confluent(”fiu”,fiică”,”frate”)

confluent(“fiică”,”fiu”,”soră”)

confluent(“pd”,”mi”,”pdmi”)

Semantica va fi definită ca în programul de mai jos:

Predicates

Semantica(nod,nod, nod)

Clauses

Semantica(x,y,fiu):-write(“\n”,x),

write(“este fiul lui”),write(y), nl.

Semantica(x,y,fiica):-write(“\n”,x),

write(“este fiica lui”,y),nl.

Semantica(x,y,sofer):-write(“\n”,x)

Write(“este șoferul lui”),write(y),nl.

Semantica(x,y,frate):-write (“\n”,x,”este fratele lui”,y).

Semantica(x,y, sora):-write(“\n”, x, “este sora lui”,y).

Semantica(x,y,a):-write(”\n”,x,”este șoferul fiului lui”),

Write(y),nl.

Semantica(x,y,c):-write(“\n”,x),write(“ are un frate “)

Write(“al cărui șofer este”,y),nl

Semantica(x,y,prieten):-write(“\n”,x,”este prieten cu”,y).

Semantica(x,y,director):-write(“n”,x,”este director la”,y).

Semantica(x,y,mama):-write(“\n”,x,”este mama lui”,y)

Semantica(x,y,învăța):-write(“\n”,x,”învață la “,y).

Semantica(x,y,pd):-write(“\n”,x,”este prieten cu”),

Write(“directorul de la “,y).

Semantica(x,y,mi):-write(“\n”,”copilul lui”,x,”învață la”,y).

Semantica(x,y,pdmi):-

Write(“\n”,x,”este prieten cu directorul”),

Write(“școala unde învață copilul lui”,y).

Semantica(x,y,sotie):-write(“\n”,x,”este soția lui”,y).

3.4 Moștenire. Teoria cadrelor

Conceptele de obiect, frame și moștenire apar în literatură în diferite moduri, de cele mai multe ori conceptul de obiect este utilizat în legătură cu programarea orientată pe obiecte, baze de date orientate pe obiect, baze de date orientate pe obiect sau probleme solving orientat pe obiect.

Conceptul de frame sau cadru este întâlnit de obicei în reprezentarea cunoștințelor. El apare cu rezultate deosebit de interesante în teoria sistemelor Lindenmayer, în legătură cu obținerea de detalii ale imaginilor sau de sinteză a imaginilor prin moștenirea unor forme. Există numeroase sisteme de procesare a cunoștințelor bazate pe aceste concepte.

Un obiect poate fi des întâlnit ca o pereche (ob_id,ob_st) unde prima componentă reprezintă identificarea obiectului și a doua este starea obiectului. În comparație cu acest concept, un cadru sau frame este o colecție de proprietăți ale unui obiect. O proprietate a unui obiect se poate descrie cu ajutorul unei perechi de forma (atribut, valoare). Pentru a obține valoarea unui atribut se utilizează proprietatea de moștenire.

Vom considera în acest paragraf ca un frame F este caracterizat de următoarele elemente:

un nume simbolic N, care reprezintă numele cadrului;

fiecare cadru are un nume unic;

o mulțime finită de numere simbolice, fiecare din aceste nume reprezintă un părinte al cadrului; un cadru poate avea zero sau mai mulți părinți;

o mulțime finită de sloturi; un slot este o pereche ordonată de forma (atribut,valoare), unde atribut este numele unei proprietăți a cadrului, iar valoare este valoarea corespunzătoare a acestuia.

Vom reprezenta un cadru ca în figura următoare unde atributiatributj pentru ij.

Reprezentarea grafică a unui cadru

Presupunem că se dorește valoarea V a unui atribut A al cadrului F. Sunt posibile următoarele cazuri:

există un slot S de forma (A, V) sau (A,P) unde V este valoarea directă a atributului, iar P este numele unei proceduri; în primul caz V este valoarea atributului A; în al doilea caz , valoarea atributului este valoarea returnată de procedura P.

Nu există nici un slot al lui F astfel încât A să fie prima componentă a slotului; în acest caz valoarea atributului se obține cu ajutorul unui părinte al lui F, adică valoarea atributului A este moștenită; dacă nici unul din părinții lui F nu conține atributul respectiv, se utilizează părinții acestora ș. a. m. d.

Din punct de vedere sintactic vom considera că un cadru este un string de forma:

Frame(nume, listă_nume, listă_attribute), unde

nume este numele cadrului;

listă_nume este o listă de nume de cadre care reprezintă părinții;

listă_attribute este o listă de elemente având una din următoarele forme:

-attr(nume_atribut, valoare);

-attr(nume_atribut, proc(nume_proc));

-attr(nume_atribut,demon)

Entitatea valoare reprezintă valoarea directă a atributului.

Nume_proc reprezintă numele unei proceduri care calculează valoarea atributului; cuvântul demon precizează faptul că avem de a face cu un atribut abstract a cărui valoare sa calculează pe cazuri particulare cu ajutorul unei proceduri.

O mulțime de cadre reprezentate sintactic sub forma figurii de mai sus este o bază de cunoștințe cu cadre.

Unei baze de cunoștințe cu cadre B putem să-i atașăm un graf în care nodurile sunt cadrele lui B, iar de la nodul X la nodul Y există un arc dacă X este un părinte al lui Y. Distanța dintre două noduri X și Y o notăm cu dist(X,Y) și ea reprezintă lungimea celui mai scurt drum de la X la Y. În cazul în care nu există nici un drum de la X la Y, dist(X,Y) nu este definită.

În general asupra unei baze de cunoștințe se impun anumite restricții cu privire la elementele ei componente. În cazul bazelor de cunoștințe cu cadre impunem următoarele restricții, prezentate în următoarea definiție:

Definiție. Considerăm o bază de cunoștințe cu cadre B. Baza B se numește bază admisibilă dacă satisface următoarele condiții:

nu există două cadre în b cu același nume;

dacă X este un cadru al lui B și (atr, demon) este un slot al lui X atunci nici un părinte al lui X nu conține atributul atr;

fie X un cadru din B și atr numele unui atribut care nu apare în X; considerăm mulțimea ZX,atr a tuturor nodurilor Y care conțin atributul atr și există un drum de la Y la X; vom presupune că nu există două noduri distincte Y1,Y2 din astfel încât:

dist(Y1,X)=dist(Y2,X)=min{dist(Y,X)/YZX,atr}

Din punct de vedere intuitiv, necesitatea introducerii acestor restricții se poate justifica astfel:

prima condiție impune cerința că toate atributele unui cadru trebuie declarate și definite într-un string; cu alte cuvinte nu există într-o bază admisibilă două cadre de forma:

frame(scaun[obiect],[attr(culoare,galben)])

frame (scaun[obiect],[attr(picioare,40])

În acest caz baza va conține un singur cadru, de forma:

Frame(scaun,[obiect],[attr(culoare,galben),attr(picioare,4)])

– necesitatea introducerii celei de a doua condiții este evidentă dacă ținem seama de interpretarea valorii demon pentru un atribut.

– a treia condiție este impusă de necesitatea calculării valorii atributului atr pentru cadrul X prin moștenire de la părinți.

Asupra unei baze admisibile se pot executa următoarele operații :

ștergerea unui slot dintr-un cadru dat ;

ștergerea unui cadru ;

adăugarea unui slot la un cadru dat ;

adăugarea unui cadru ;

modificarea valorii unui atribut ;

calculul valorii unui atribut pentru un cadru dat.

Capitolul 4

Prezentarea limbajului Java

4.1 Introducere în limbajul Java

Limbajul Java împreună cu mediul său de dezvoltare și execuție au fost proiectate pentru a rezolva o parte dintre problemele actuale ale programării. Proiectul Java a pornit cu scopul de a dezvolta un software performant pentru aparatele electronice de larg consum.

Mai târziu Java a devenit un limbaj de programare adecvat pentru proiectarea de software dedicat lucrului în Internet. Java a intrat în cursa limbajelor de programare evoluate prin cumpărarea licenței de către firma Netscape și integrarea lui în browserele Netscape. Cele mai mari firme de software au cumpărat licența Java în vederea dezvoltării unor produse care consideră tehnologia Java.

Java încearcă să rămână un limbaj simplu de folosit, chiar și de programatorii neprofesioniști, programatorii care doresc să se concentreze asupra aplicațiilor în principal și abia apoi asupra tehnicilor de implementare a acestora.

Din Java au fost îndepărtate toate aspectele mai incoerente din C++ precum supraîncărcarea operatorilor și moștenirea multiplă. A fost introdus un collector automat de reziduuri-garbage collector – care să rezolve problema deblocării memoriei în mod uniform, fără intervenția programatorului. Colectorul este o trăsătură nouă, dar implementarea acestuia în Java este făcută inteligent și eficient folosind un fir separat de execuție, pentru că Java are încorporate facilități de execuție pe mai multe fire de execuție implicit.

Limbajul Java este pur obiectual. Cu el se pot crea clase de obiecte și instante ale acestora, se pot încapsula informațiile, se pot moșteni variabilele și metodele de la o clasă la alta. Singura trăsătură specifică limbajelor orientate pe obiecte care lipsește este moștenirea multiplă, dar, pentru a suplini această lipsă, Java oferă o facilitate mai simplă, numită interfață, care permite definirea unui anumit comportament pentru o clasă de obiecte, ce poate fi altul decât cel definit de clasa de bază printr-o implementare specifică unei interfețe. În Java orice element este un obiect, în afară de datele primare. Din Java lipsesc funcțiile și variantele globale. Rămân desigur metodele și variantele statice ale claselor.

Java este distribuit, având implementate biblioteci pentru lucrul în rețea care ne oferă TCP/IP, URL și încărcarea resurselor din rețea. Aplicațiile Java pot accesa foarte rapid rețeaua, folosindu-se de apelurile către un set standard de clase.

Java este robust. În Java legarea funcțiilor se face în timpul execuției și informațiile de compilare sunt disponibile până în momentul rulării aplicației. Acest mod de lucru face ca sistemul să poată determina în orice moment neconcordanța dintre tipul referit la compilare și cel referit în timpul execuției, evitându-se astfel posibile intruziuni răuvoitoare în sistem, prin intermediul unor referințe falsificate. În același timp Java detectează referințele nule, dacă acestea sunt folosite în operații de acces. Indicii în tablourile Java sunt verificați permanent în timpul execuției și tablourile nu se pot parcurge prin intermediul unor pointeri așa cum se întâmpla în C/C++. De altfel, pointerii lipsesc complet în limbajul Java, împreună cu întreaga lor aritmetică, eliminându-se astfel una din principalele surse de erori. În plus eliberarea memoriei ocupate de obiecte și tablouri se face automat, prin mecanismul de colectare de gunoaie evitându-se astfel încercările de eliberare multiplă a unei zone de memorie.

Java este un limbaj de securitate ridicată. El verifică la fiecare încărcare codul prin diferite mecanisme și prin verificarea operațiilor disponibile pentru fiecare set de obiecte. Robustețea este și ea o trăsătură de securitate. La un al doilea nivel, Java are încorporate facilități de protecție a obiectelor din sistem la scriere și/sau citire. Variabilele protejate într-un obiect Java nu pot fi accesate fără a avea drepturile necesare, verificarea fiind făcută în timpul execuției. În plus, mediul de execuție Java poate fi configurat pentru a proteja rețeaua, fișierele și celelalte resurse ale calculatorului pe care rulează o aplicație Java.

Limbajul Java are inclus suportul nativ pentru aplicații care lucrează cu mai multe fire de execuție, inclusiv primitive de sincronizare între fire de execuție, acest suport este independent de sistemul de operare, dar poate fi conectat, pentru o performanță mai bună la facilitățile sistemului, dacă acestea există.

Java este dinamic. Bibliotecile de clase în Java pot fi reutilizate cu foarte mare ușurință. Cunoscuta problemă a fragilității superclasei este rezolvată mai bine decât în C++. Acolo, dacă o superclasă este modificată trebuie modificate toate subclasele acesteia pentru că obiectele au o altă structură în memorie. În Java această problemă este rezolvată prin legarea târzie a variabilelor, doar la execuție–late binding-. Regăsirea variabilelor se face prin nume și nu prin deplasament fix. Dacă superclasa nu a șters o parte dintre vechile metode și variabile, ea va putea fi refolosită fară a fi necesară recompilarea subclaselor sale. Se elimină astfel necesitatea actualizării aplicațiilor.

Limbajul Java este independent de arhitectura calculatorului pe care lucreză, ceea ce îi conferă portabilitate. În loc să genereze cod nativ pentru o platformă sau alta, compilatorul Java generează o secvență de instrucțiuni ale unei mașini virtuale Java – Java-bytecode. Java-bytecode este un cod independent de platformă și care este interpretat apoi de interpretorul platformei Java.

Orice interpretor Java, chiar dacă este un mediu de dezvoltare sau un browser web capabil să ruleze appleturi, este o interpretare a mașinii virtuale Java. Acest interpretor analizează și rulează fiecare instrucțiune Java-bytecode pe calculator. Compilarea se face o singură dată, iar interpretarea intervine de câte ori este nevoie să se execute programul.

Singura parte din mediul de execuție Java care trebuie portată de pe o arhitectură pe alta este mediul de execuție cuprinzând interpretorul și o parte din bibliotecile standard care depind de sistem. În acest fel aplicațiile Java arhitectura de un anumit tip pot fi rulate fără recompilare pe un sistem cu un alt tip de arhitectură.

Una dintre principalele probleme ale limbajelor interpretate este viteza de execuție, considerabil mai scăzută față de cea a limbajelor compilate. Dacă nu este mulțumitoare viteza de execuție a unei astfel de aplicații, se poate cere mediului de execuție Java să genereze automat un executabil nativ care poate rula la viteză maximă. De obicei însă, în Java se compilează doar acele părți ale programului care sunt mari consumatoare de timp, restul rămânând interpretate, pentru a nu se pierde flexibilitatea. Mediul de execuție însuși este scris în C, ceea ce îl face extrem de portabil.

Editarea unui program în Java se face utilizând orice editor simplu de text care salvează datele în format text. Este important ca fișierul în care se salvează programul să aibă numele clasei respective ( doar în cazul în care clasa este declarată publică). Iar în cazul în care aplicațiile stand-alone este obligatoriu ca în clasă să existe metoda main(). Această metodă trebuie să existe în orice aplicație Java, fiind prima metodă apelată de interpretor când se lansează în execuție un program Java.

4.2 Platforma Java

O platformă este un mediu hardware sau software în care se execută un program. Cele mai importante platforme – Windows, Linux, Solaris- pot fi descrise ca fiind o combinație dintre un sistem de operare și un sistem hardware adecvat.

Platforma Java diferă de celelalte platforme prin faptul că este o platformă exclusiv software, care rulează deasupra altor platforme bazate pe hardware.

Platforma Java este compusă din două componente:

mașina virtuală Java –Java VM- care a fost descrisă mai sus;

Interfața de programare a aplicațiilor Java –Java API – care este o colecție componentă software ce furnizează multe posibilități utile, cum ar fi utilitarele pentru interfața grafică cu utilizatorul. Java API este grupată în biblioteci de clase și interfețe, aceste biblioteci purtând numele de pachete.

Platforma Java

După cum se vede, Java API și Java VM izolează programul care rulează pe platforma Java de partea hardware a sistemului.

Platforma Java împreună cu limbajul de programare alcătuiesc tehnologia Java.

Descrierea mediului JDK

La baza dezvoltării unui program Java stă mediul de dezvoltare pus la dispoziție de către firma Sun. Acesta este Java Developer Kit- JDK și trebuie considerat ca mediu de referință în programarea Java.

Se consideră important ca un programator să cunoască mai întâi uneltele standard și apoi să treacă la utilizarea uneltelor mai importante. Mediul JDK conține pe de o parte o serie de biblioteci Java de clase java necesare scrierii unui program și pe de altă parte un set de utilitare necesare compilării, testării, execuției și documentării unei aplicații Java.

Un fișier cu extensia *.class reprezintă unitatea fundamentală a unui program executabil Java. O bibliotecă de clase cuprinde o serie de clase ce au un numitor comun. O astfel de bibliotecă este cunoscută în Java sub numele de pachet (package).

Pachete fundamentale

JDK-ul include câteva pachete fundamentale , care conțin clase fără de care nu se pot dezvolta aplicații Java performante, și anume:

Package java.applet – conține clase necesare dezvoltării unui program java care se execută în cadrul unui browser www sau este rulat cu appletviewer-ul;

Package java.awt.* – utilizate pentru dezvoltarea de interfețe grafice standard;

Package java.beans – include clasele necesare dezvoltării de componente reutilizabile (beans-uri);

Package java.*lang – conține clasele fundamentale, fără de care nici o aplicație Java nu ar exista. Utilizarea unei clase din oricare alt pachet decât Java.lang într-un program java se specifică în clar prin directiva import nume_pachet. Acest pachet este inclus automat de către compilator, fără a fi nevoie de precizări suplimentare.

Package java.math – se folosește pentru utilizarea de funcții matematice standard implementate;

Package java.net – este utilizat pentru programarea în rețea și conține mai multe clase pentru aceasta;

Package java.rmi* – este utilizat pentru crearea de aplicații ce lucrează în sisteme distribuite. Facilitează apelul unor metode din obiecte disponibile pe fiecare dintre calculatoarele conectate în rețea;

Package java.security.* – asigură un mecanism de securitate al sistemului software dezvoltat;

Package java.sql – este utilizat pentru lucrul cu baze de date;

Package java.text – este utilizat pentru lucrul cu texte, date calendaristice și numere;

Package java.util – oferă suport pentru lucrul cu liste, vectori, dicționare, informații legate de dată și timp etc.;

Programatorul poate utiliza și alte pachete dezvoltate de către alți utilizatori. Trebuie însă să se asigure că aceste pachete adiționale sunt disponibile și pe platforma pe care aplicația se execută, nu numai unde aceasta a fost creată.

Unelte Java

Principalele unelte utilizate în Java sunt:

Javac – Java Language Compiler

Este compilatorul Java, care transformă sursele text având extensia *.java scrise într-un limbaj de programare Java, în cod executabil pe mașina virtuală Java, în Bytecode. Adică fișiere de tip *.class.

Java- Java interpretor

Este interpretorul Java care execută programele, realizând nivelul de Java VM deasupra platformei reale. Prin lansarea în execuție a acestui utilitar se pornește de fapt Java VM. Programul convertește instrucțiunile Java VM din bytecode în instrucțiuni ale mașinilor reale. Este utilizată pentru aplicații stand-alone.

Javadoc

Acest program generează documentația programelor Java în format HTML. Documentarea se face pe baza comentariilor specifice Java din program și acest program se aplică doar fișierelor sursa Java.

Orice mașină virtuală Java (fie interpretor, fie browser) se presupune că are acces la fișierele bytecode existente în mediul JDK. Aceasta în cazul în care se formează versiuni. Variabila de mediu CLASSPATH este cea care definește căile de acces la biblioteci.

Capitolul 5 – Prezentarea aplicației

Numele aplicației realizate pentru ilustrarea celor prezentate până în acest punct al lucrării este “Rețele de tranziție de bază. Implementare în Java”.

O rețea de tranziție de bază este o diagramă de tranziție în care arcele nu sunt etichetate cu cuvinte ci cu categorii sintactice ale limbajului. Astfel, dintr-o rețea de tranziție se pot obține mai multe diagrame de tranziție dacă înlocuim categoriile sintactice cu cuvinte care aparțin acestor categorii.

Structura prezentată în figura următoare se numește rețea de tranziție de bază. În literatura de specialitate pentru acest concept se utilizează prescurtarea BTN care provine de la Basic Transition Network.

<subst>

<verb>

<num> <num>

<subst> <prep>

<subst>

Rețeaua de tranziție de bază provine din digrama de tranziție care poate prelucra o frază în sensul următor :

Presupunem că fraza este descompusă în entități. În general aceste entități sunt cuvinte aparținând unor categorii sintactice ale limbajului .O succesiune (e1…….en) de entități se numește succesiune acceptată de diagramă dacă există o succesiune de stări (s0…….,sn) astfel încât :

s0 este stare inițială

sn este stare finală

pentru fiecare i{0,…..,n-1} există un arc de la starea si la starea si+1 pe care se gasește înscrisă entitatea ei+1.

Rețeaua de tranziție de bază prezentată are o mulțime de stări notate q0,……q7 reprezentate prin dreptunghiuri și între unele dintre aceste stări există legături reprezentate prin arce orientate. Aceste arce definesc trecerea dintr-o stare în alta.

Diagrama prezentată are o singură stare inițială q0 și două stări finale q6 și q7.

Există numai două drumuri de la q0 la q6 și de la q0 la q7, deci diagrama noastră va accepta numai două tipuri de fraze. Primul tip de frază va determina trecerea diagramei din starea q0 în q7, iar cel de-al doilea tip de frază va realiza trecerea din q0 în q6. Nu este greu de observat că rețeaua de tranziție de bază va accepta fraze de tipul următor:

Fotografiază prima scară din bloc

Vizitează primul muzeu din ultima zonă

Tratează primul subiect din muzeu

Fotografiază al doilea subiect din localitate

Vizitează prima localitate către ultimul pod

Rețelei de tranziție de bază studiate îi vom atașa un analizator care va comunica pe baza unei interfețe cu utilizatorul și va informa dacă tipul de frază introdus va fi acceptat sau nu. Analizatorul va avea sarcini precise și va comunica prin mesaje scrise cu utilizatorul. Analizatorul va funcționa pe baza unor reguli precise care sunt clar definite. Analizatorul are atașat și un set de instrucțiuni care sunt folosite pentru utilizarea rețelei de bază. Acestea sunt:

1. Nu se pot introduce mai mult de 10 componente.

2. Pentru construirea unei noi fraze se va apăsa butonul <Frază Nouă>.

3. Pentru a analiza fraza construită se va apăsa butonul <Analizează>.

4. Dacă sunt mai mult de 6 componente se semnalează eroare.

5. Dacă sunt mai puțin de 5 componente se semnalează eroare.

6. Dacă fraza este acceptată se semnalează prin mesaj.

7. Pe figură se va semnala care componentă nu este acceptată.

Analizatorul va funcționa pe baza regulilor descrise mai sus. El va analiza frazele introduse care vor fi formate din cuvinte ce aparțin următoarelor categorii gramaticale: verb, numeral, substantiv,prepoziție.

De asemenea vom avea:

verb{tratează, vizitează, fotografiază, conectează, utilizează}

numeral{primul, prima, ultimul, ultima, al doilea, a treia, al treilea}

substantiv{subiect, scară, muzeu, pod, localitate, calculator, laborator, depertament}

prepoziție{din, la, către, dinspre}

Analizatorul nu permite decât introducerea prin selectare a cuvintelor care fac parte din categoriile gramaticale enumerate mai sus. Cuvintele introduse vor forma frazele. El va semnala dacă fraza introdusă va fi acceptată sau nu. Analizatorul nu va permite de asemenea decât introducerea de cuvinte pentru a forma fraze decât în ordinea stabilită de diagramă. Altfel dacă vom avea o altă ordine, alta decât cea stabilită în diagramă cum ar fi:

“ Dinspre localitate fotografiază prima scară” sau “primul muzeu subiect din localitate fotografiază” vom primi un mesaj de eroare “Respinsă! Vezi figura!”

Astfel la fraza de tipul ”Fotografiază prima scară din localitate” sau “Tratează primul subiect din laborator “ vom obține mesajul “acceptată”.

În schimb, dacă de la tastatură vom introduce prea multe sau prea puține cuvinte vom primi mesajul “respinsă – prea multe componente” sau “respinsă – prea puține componente”, iar dacă vom avea fraze de tipul “Tratează primul subiect din muzeu” sau “Fotografiază al doilea subiect din localitate” vom observa că frazele vor primi un mesaj precum că sunt acceptate. De ce?- pentru că ele respectă diagrama introdusă și au numărul de cuvinte acceptat.

În următorul program este definită și explicată – Categoria sintactică – este inițializată clasa Categ_sint și sunt introduse elementele acestei clase, sunt introduse categoriile gramaticale care formează rețeaua de tranziție și astfel vom avea:

verbe[]={"tratează", "fotografiază","vizitează","conectează","utilizează"}

numerale[]={"primul","prima","ultimul","ultima","al doilea","a treia","al treilea"};

substantive[]={"subiect","scară","muzeu","pod","localitate","calculator", "laborator","rețea","departament"};

prepoziții[]={"din","la","către","dinspre"};

Categoria sintactică

import java.io.*;

import java.util.*;

public class Categ_sint {

String verbe[]={"tratează","fotografiază","vizitează","conectează","utilizează"};

String numerale[]={"primul","prima","ultimul","ultima","al doilea","a treia","al treilea"};

String substantive[]={"subiect","scară","muzeu","pod","localitate","calculator","laborator", "rețea","departament"};

String prepozitii[]={"din","la","catre","dinspre"};

String entitate;

String categ;

public Categ_sint(){

entitate=new String();

categ=new String();

}

public Categ_sint(String s){

SetEntitate(s);

SetCateg();

}

public void SetEntitate(String s){

entitate=s;

}

public void SetCateg(){

for (int i=0;i<verbe.length;i++)

if (entitate.equals(verbe[i]))

categ="verb";

for (int i=0;i<numerale.length;i++)

if (entitate.equals(numerale[i]))

categ="numeral";

for (int i=0;i<substantive.length;i++)

if (entitate.equals(substantive[i]))

categ="substantiv";

for (int i=0;i<prepoziții.length;i++)

if (entitate.equals(prepoziții[i]))

categ="prepoziție";

}

public String GetEntitate(){

return entitate;

}

public String GetCateg(){

return categ;

}

}

Mai jos este introdus Analizatorul. Acesta recepționează frazele create de către utilizator, pe baza programului “categoria sintactică“ prezentat anterior.

Analizator:

import java.io.*;

import java.util.*;

public class Analizor {

String fraza;

int nr_elem;

int eroare[];

Categ_sint[] categ;

public Analizor(){

categ=new Categ_sint[10];

fraza=null;

eroare=null;

}

public Analizor(String s){

fraza=s;

nr_elem=0;

categ=new Categ_sint[10];

eroare=new int[10];

Split();

Analizează();

}

public void Split(){

try {

StringTokenizer sir=new StringTokenizer(fraza,".");

nr_elem=sir.countTokens();

for (int i=1;i<=nr_elem;i++)

{

categ[i]=new Categ_sint(sir.nextToken());

}

}catch(Exception e){System.err.println(e);}

}

public void Analizează(){

eroare[0]=1;

if ((nr_elem<5) || (nr_elem>6))

eroare[0]=0;

else

{

if (categ[1].GetCateg().equals("verb"))

eroare[1]=1;

else

eroare[1]=0;

if (categ[2].GetCateg().equals("numeral"))

eroare[2]=1;

else

eroare[2]=0;

if (categ[3].GetCateg().equals("substantiv"))

eroare[3]=1;

else

eroare[3]=0;

if (categ[4].GetCateg().equals("prepoziție"))

eroare[4]=1;

else

eroare[4]=0;

if (nr_elem==5)

{

if (categ[5].GetCateg().equals("substantiv"))

eroare[5]=1;

else

eroare[5]=0;

}

else

{

if (categ[5].GetCateg().equals("numeral"))

eroare[5]=1;

else

eroare[5]=0;

if (categ[6].GetCateg().equals("substantiv"))

eroare[6]=1;

else

eroare[6]=0;

}

}

}

public int GetError(int i){

return eroare[i];

}

public String GetCateg(int i){

return categ[i].GetCateg();

}

public String GetEntit(int i){

return categ[i].GetEntitate();

}

public int GetElem(){

return nr_elem;

}

public String isAccepted(){

String rez=new String("accepted");

for (int i=0;i<=nr_elem;i++)

if (eroare[i]==0)

rez="denied";

return rez;

}

}

BIBLIOGRAFIE

Nicolae Țăndăreanu – Sisteme expert. Reprezentarea cunoștințelor și inferența, Editura Universitaria, 2001

Dorin Zaharie – Sisteme expert. Teorie și Aplicații, Editura Dual Tec, 1999

The Java Tutorial, http:// Java.sun.com

Java 2SDK, Standard Edition Documentation, http:// java.sun.com