Backtraking si Recursivitate

Idu Stefan AndreiGanea Daniel-ConstantinBacktraking si Recursivitate

Backtraking si RecursivitateUnificare;

Backtraking;

Algoritmi recursivi(factorial ,cmmdc ,putere, sir Fibonacci).

UnificareDefinitie :

Unificarea reprezinta modul in care Prologul realizeaza potrivirile intre termeni.

! Procesul de unificare se realizeaza in ambele sensuri.

UnificareExemple (fapte): Definitie: Descriu relatia dintre predicate. Sintaxa: nume_predicat(argument_1,argument_2);

Exemplu:Explicatie:X=marian.Intoarce rezultat pozitiv (Yes)marian=andrei.Intoarce No pentru ca nu pot fi doi atomi distinctix=marian,X=Y.X=marian ,Y=marian ; deci intoarce YesX=barbat(marian).Intoarce YesX=Y.Intoarce Yes , iar daca una din variabile ia o valoareSi cealalta o va avea

Exercitii: Introduceti urmatoarele interogari si observati de ce in unele cazuri reuseste si in unele nu:

1. 4+3=7. 2. g(Y,b)=g(b,Y). 3. daniel=daniel. 4. iubeste(alexandra,Y)=iubeste(Y,ioan). 5. g(X,Y)=g(Z,Z).

UnificareaExemplu(reguli):

Definitie reguli:

Reprezinta o concluzie care este adevarata daca una sau mai multe fapte sunt adevarate.

O regula are urmatoarea sintaxa:

Nume_relatie(arg1,,argn):-nume_relatie_1(),,nume_relatie_n())

Exemplu

Fisierul Swi Prologp(X):-a(X).?-p(X).p(X):-b(X),c(X),d(X),e(X).p(X):-f(X).a(1).b(1). b(2).c(1). c(2).d(2).e(2).f(3).

Exemplu Swi Prolog v-a rezolva aceasta unificare prin algoritmul de backtracking (vezi metoda de rezolvare pe tabla):

Rezultatul intors: X=1; X=2; X=3; no

Unificare/BacktrakingDefinitie:Backtrackingeste numele unuialgoritmgeneral de descoperire a tuturor soluiilor unei probleme de calcul, algoritm ce se bazeaz pe construirea incremental desoluii-candidat, abandonnd fiecare candidat parial imediat ce devine clar c acesta nu are anse s devin o soluie valid.

ExercitiiProgramatorul trebuie sa aiba absolvite scoala generala , liceul si facultatea (1=Absolvit).Trebuie sa aiba urmatoarele atuuri(ingenios , rapid).Le-am notat (1=bun ,2=foarte bun) si sa cunoasca foarte bine limbajul si sa ii faca placere sa lucreze (1=satisfacator ,2=bun, 3=excelent).

Deci avem: prog(Y):-scoala(Y),liceu(Y),fac(Y). prog(Y):-ingenios(Y),rapid(Y). prog(Y):-limbaj(Y),placere(Y). scoala(1). liceu(1). fac(1). ingenios(1). ingenios(2). rapid(1). rapid(2). limbaj(3). placere(3).

TemaUrmand exemplul din clasa , realizati o problema de backtraking .Care sa se refere la un angajat si sa contina 4 ramuri.Fiecare ramura la randul ei sa contina minim 2 ramuri.

RecursivitateDefinitie: Recursivitateasaurecursiaeste un mod de a defini unele funcii. Funcia este recursiv, dac definiia ei folosete o referire la ea nsi, crend la prima vedere uncerc vicios, care ns este numai aparent, nu i real.

O funcie recursiv care calculeaz N! se poate exprima astfel:factorial(0) = 1factorial(N) = N * factorial(N 1)

Recursivitate: factorial Formula matematica : 0!=1 ,N!=N*(N-1)!

In fisier: fact(0,1). fact(N,K):- N>0, N1 is N-1, fact(N1,K1), K is N*K1.In prolog: fact(3,F),write(F).Raspuns : 6

Recursivitate : cmmdcFormula matematica: cmmdc(a,b)=a daca a=b cmmdc(a,b)=cmmdc(a-b) daca a>b cmmdc(a,b)=cmmdc(b-a)Daca bB,A1 is A-B,cmmdc(A1,B,C). cmmdc(A,B,C):-A>B,B1 is B-A,cmmdc(A,B1,C).In prolog:cmmdc(3,2,C).Raspuns :1

Recursivitate:putereFormula matematica: X^n X^0=1X^2=x*x

In fisier: putere(X,0,1). putere(X,N,M):-N1 is N-1,putere(X,N1,M1),M1 is X*M1. go:-read(X),read(N),putere(X,N,P),write(M).

Recursivitate:sirul lui FibonacciNumerele lui Fibonacci: 1,1,2,3,5,8,13.Fiecare numar din secventa este suma a doua numere anterioare .

In fisier: fib(1,1). fib(2,1). fib(N,F):-N>2,N1 is N-1 ,fib(N1,F1),N2 is N-2,fib(N2,F2),F is F1+F2.In prolog: fib(6,F). Raspuns: F=8? ; (16 ms) no

Exercitii1.Folosind recursivitatea faceti un program care sa afiseze toti divizori unui numar

2.Folsind recursivitatea faceti un program care sa calculeze suma primelor N numere naturale.

TemaSa se decida daca un numar K este divizor al numarului N.Restul impartiri lui N la K este 0.

Bibliografiehttp://web.info.uvt.ro/~mmarin/lectures/LP/curs-03.pdf http://inf.ucv.ro/~rstoean/courses/logica/l13.pdf http://www.et.upt.ro/admin/tmpfile/fileY1363600058file5146e2ba3b9c9.pdf http://www.programare.biz/PROLOG/C3a_Recursivitate.pdf http://software.ucv.ro/~cstoica/TP/backtracking.pdf

Va multumim!