2017

Utilizarea SRR al clauzelor precise

Capitolul 4

2017

Etape in utilizarea SRR

1. Se stabileste domeniul problema.

2. Se identifica obiectele/conceptele/relatiile din domeniul problemei –

conceptualizarea domeniului.

3. Se asociaza simboluri pentru reprezentarea obiectelor/

conceptelor/relatiilor din domeniul problemei.

4. Se construieste baza de cunostinte din domeniul problema. Clauzele

sunt adevarate in interpretarea intentionata.

5. Se interogheaza SRR. Rezultatele se interpreteaza conform interpretarii

intentionate.

• Probleme:

– Identificarea obiectelor/conceptelor/relatiilor si a nivelului de detaliere la care se

face conceptualizarea.

– Clauzele trebuie sa fie adevarate in interpretarea intentionata.

– Clauzele acopera toate situatiile posibile ?

2017

Sistemul electric al unei case de locuit

2017

Obiective. Conceptualizarea domeniului

• Se urmareste simularea sistemului, adica determinarea care dintre sursele de lumina sunt active in functie de starile dispozitivelor din sistem.

• Obiectele din domeniul problemei sunt: conexiuni (engl.wire), comutatoare (engl.switch), surse de lumina (engl.light), prize (engl.power outlet) si intrerupatoare (engl.circuit breaker).

• Se asociaza simboluri obiectelor din domeniul problemei.

– Conexiuni: w0, …, w6

– Comutatoare: s1, s2 si s3

– Intrerupatoare: cb1 si cb2

– Surse de lumina: l1 si l2

– Prize: p1 si p2

– Alimentare exterioara: exterior

2017

Identificarea relatiilor

% lumina(L) L este o sursa de lumina

% aprinsa(L) sursa L de lumina este aprinsa

% activa(W) componenta W este alimentata

% sus(S) comutatorul S este in pozitia “sus”

% jos(S) comutatorul S este in pozitia “jos”

% ok(E) componenta E (intrerupator sau sursa de lumina) nu este

% defecta

% conectata_la(X,Y) componenta X este conectata la

% componenta Y, ceea ce inseamna ca exista un flux de

% curent de la Y inspre X.

• Observatie: modelarea domeniului se face la nivelul cunoasterii de bun simt (engl.common-sense). La acest nivel de abstractizare se ignora legile lui Kirchhoff si valorile curentilor si tensiunilor. In schimb se modeleaza existenta sau absenta fluxului de curent dinspre exterior prin conexiuni spre componentele sistemului.

2017

Axiomatizarea domeniului (I)

• Se scriu axiomele domeniului. Acestea trebuie sa fie adevarate in

interpretarea intentionata.

• Situatia curenta se descrie printr-o multime de fapte:

conectata_la(l1,w0)

conectata_la(w0,w1) sus(s2)

conectata_la(w0,w2) jos(s2)

conectata_la(w1,w3) sus(s1)

conectata_la(w2,w3) jos(s1)

conectata_la(l2,w4)

conectata_la(w4,w3) sus(s3)

conectata_la(p1,w3)

conectata_la(w3,w5) ok(cb1)

conectata_la(p2,w6)

conectata_la(w6,w5) ok(cb2)

conectata_la(w3,exterior)

lumina(l1)

lumina(l2)

jos(s1)

sus(s2)

sus(s3)

ok(l1)

ok(l2)

ok(cb1)

ok(cb2)

2017

Axiomatizarea domeniului (II)

• Se adauga axiome care descriu ceea ce este adevarat in orice situatie.

% aprinsa(L) exista un flux de curent inspre

% sursa de lumina L si L nu este defecta

aprinsa(L)

lumina(L)

ok(L)

activa(L)

% activa(Y) Y este conectata la o componenta

% activa sau Y este alimentarea exterioara

activa(Y)

conectata_la(Y,Z)

activa(Z)

activa(exterior)

• Interogari: ? conectata_la(l1,W) W = w0

? aprinsa(L) L = l2

? activa(W) W = w2, W = l2, W = w4, ...

2017

Reprezentarea bazelor de date relationale

• SRR al clauzelor precise se poate folosi pentru definirea operatiilor clasice cu baze de date relationale: selectie, reuniune, proiectie, etc.

• O baza de date relationala se reprezinta in SRR al clauzelor precise printr-o multime de fapte de baza.

% curs(C) C este un curs

curs(312)

curs(322)

curs(315)

curs(371)

% departament(C,D) cursul C

% este oferit in

% departamentul D

departament(312,stiinta_calc)

departament(322,stiinta_calc)

departament(315,matematica)

departament(371,fizica)

% student(S) S este un student

student(maria)

student(ioana)

student(ion)

student(horatiu)

% inscris(S,C) studentul S este inscris in

% la cursul C

inscris(maria,322)

inscris(ioana,312)

inscris(ion,322)

inscris(ion,315)

inscris(horatiu,322)

inscris(maria,315)

inscris(ioana,312)

inscris(ioana,322)

2017

Operatii in baze de date relationale

• Operatiile din algebra relationala se definesc cu reguli.

• Selectie:

curs_mate(C) departament(C,matematica)

curs_sc(C) departament(C,stiinta_calc)

• Reuniune:

curs_mate_sau_sc(C) curs_mate(C)

curs_mate_sau_sc(C) curs_sc(C)

• Legatura (engl.join):

? inscris(S,C) departament(C,D)

• Proiectie:

in_departament(S,D) inscris(S,C) departament(C,D)

2017

Recursivitate si inductie

• Recursivitate = o modalitate de a defini concepte prin definitii cu autoreferire.

• Inductie matematica = demonstrarea unor proprietati ale conceptelor definite recursiv.

• In recursivitate exista o relatie de ordine partiala pe multimea instantelor conceptelor definite. Un concept este fie primitiv (cel mai simplu cu putinta) sau este definit in termenii unor elemente “mai mici” decat el in raport cu relatia de ordine partiala.

• In programare intalnim recursivitatea algoritmilor si recursivitatea datelor.

• In Datalog intalnim recursivitatea regulilor si recursivitatea termenilor. Daca se considera ca Datalog este un limbaj de programare de nivel inalt atunci algoritmii se pot identifica cu regulile si datele cu termenii.

2017

Axiomatizarea domeniului numerelor naturale

• Multimea IN a numerelor naturale poate fi definita recursiv astfel:

– 0 IN

– Daca x IN atunci succ(x) IN

• In Datalog avem:

numar_natural(0)

numar_natural(s(X)) numar_natural(X)

• Relatia definita pe IN IN se defineste recursiv astfel:

– Daca x IN atunci 0 x

– Daca x,y IN si x y atunci succ(x) succ(y)

• In Datalog avem:

0 X numar_natural(X)

s(X) s(Y) X Y

• Tema pentru acasa: axiomatizati adunarea numerelor naturale.

2017

Reprezentarea conceptelor abstracte – liste

• Lista = o secventa ordonata liniar (secvential) de elemente.

• O abordare a reprezentarii listelor este de a le da un nume si de a utiliza o relatie pentru a defini apartenenta elementelor la lista.

% element(L,I,E) E este al I-lea element al listei L

% dimensiune(L,N) lista L are N elemente

element(anul_2_calc,1,ionel)

element(anul_2_calc,2,georgica)

element(anul_2_calc,3,mariuca)

...

dimensiune(anul_3_calc,50)

• O alta metoda este utilizarea atomului vid pentru a reprezenta o lista vida si o functie cons care construieste o noua lista dintr-un prim element si o alta lista. Daca E este multimea elementelor si L este multimea listelor atunci cons : E L L. Multimea listelor se defineste recursiv:

– vid L

– Daca e E si l L atunci cons(e,l) L

2017

Operatii cu liste

• Definitia de tip a listelor:

lista(vid)

lista(cons(H,T)) lista(T)

• Apartenenta unui element la o lista:

membru(X,cons(X,L))

membru(X,cons(Y,L)) membru(X,L)

• Concatenarea a doua liste:

concat(vid,L,L)

concat(cons(X,T),U, cons(X,V)) concat(T,U,V)

• Notatia Prolog a listelor: [ | ] = cons( ,)

[ | []] = [, ]

[ | vid] = []

• Rasturnarea unei liste – versiunea naiva:

rasturnat([],[])

rasturnat([H | T],R) rasturnat(T,T1) concat(T1,[H],R)

• Interogarea ? rasturnat(L,R) necesita un timp O(|L|2). (de ce ?)

x cons(x,l)

Daca x l atunci x cons(y,l)

vid + l = l

cons(x,l) + m = cons(x,l+m)

Exemplu:

[a | [b | vid]] = [a,b | vid] =

[a,b]

2017

Rasturnarea unei liste – varianta eficienta

• Se extrag elementele unul cate unul incepand cu primul si se depun intr-o lista temporara, prin adaugare la inceput. La terminare rezultatul se obtine in lista temporara.

([a,b,c],[]) ([b,c],[a]) ([c],[b,a]) ([],([c,b,a])

rasturnat(L,R) rasturnat(L,[],R) % 1

rasturnat([],R,R) % 2

rasturnat([X | Y],T,R) rasturnat(Y,[X | T],R) % 3

• Argumentul care desemneaza lista temporara se numeste acumulator. Folosirea acumulatorilor este o tehnica de implmentare eficienta a predicatelor recursive. Pornind de la o descriere iterativa.

• Interogarea ? rasturnat(L,R) necesita un timp O(|L|).

2017

Reprezentarea conceptelor abstracte – arbori

• Arborii binari se definesc recursiv:

Un nod frunza este un arbore binar.

Un subarbore stang si un subarbore

drept atasati la un nod radacina

formeaza un arbore binar.

• Fie N multimea nodurilor si B multimea arborilor binari.

• Reprezentarea unui arbore binar foloseste functiile:

fr : N B

arb : N B B B

a

b c

d e

arb

a arb fr(b)

c fr(e)

fr(d)

2017

Definitia de tip a arborilor binari

• Definitia de tip a unui arbore binar este urmatoarea:

arb_bin(fr(X))

arb_bin(arb(N,S,D)) arb_bin(S) arb_bin(D)

• Determinarea frunzelor unui arbore binar:

este_frunza(fr(X),X)

este_frunza(arb(N,S,D),X) este_frunza(S,X)

este_frunza(arb(N,S,D),X) este_frunza(D,X)