2

2110 Unificare i backtracking

11 Laborator 4

UNIFICARE I BACKTRACKINGNoiuni teoreticeUnificare Procesul de cutare care ncearc s gseasc o potrivire a unui obiectiv cu o clauz din seciunea clauses poart denumirea de unificare, ceea ce presupune gsirea unei potriviri ntre structurile de date utilizate n apelul obiectivului i cele din clauzele date. n Prolog, unificarea implementeaz cteva dintre procedeele cunoscute din alte limbaje de programare cum ar fi: atribuirea, transmiterea parametrilor unei proceduri, selecie case, construcia unor structuri de date, etc.

Cnd Prolog ncearc s satisfac un obiectiv, trebuie testat fiecare clauz din program corespunztoare predicatelor ce compun obiectivul. Programul va cuta o potrivire de la nceputul programului i pn la sfrit. Cnd o clauz se potrivete cu un obiectiv, Prolog caut s atribuie valori pentru variabilele libere astfel nct clauza i obiectivul s fie identice. Se spune c obiectivul se unific cu clauza. Backtracking

n mai multe situaii cnd se dezvolt probleme reale trebuie urmat o cale pn la concluzia sa logic. Dac, pentru calea aleas nu se ajunge la rspunsul dorit, atunci trebuie aleas o alt cale. Prolog utilizeaz metoda numit revenire napoi i ncercare din nou (backing up and trying - again). ntr-un program Prolog este posibil s se obin o soluie prin alegerea unei alternative din dou posibile. Se pune un indicator la punctul de ramificare (cunoscut sub numele de backtracking point) i se selecteaz primul subobiectiv. Dac acesta euaz, Prolog va reveni napoi (backtrack) la punctul respectiv i va ncerca subobiectivul alternativ.Reguli specifice acestei metode: Cnd Prolog ncepe satisfacerea unui obiectiv, ncepe cutarea unei posibile unificri de la nceputul programului.

Cnd se face un apel, de asemenea Prolog va ncepe cutarea de la nceput spre sfrit.

Dac un apel a gsit o potrivire, el se va ncheia cu success, i se va ncerca n continuare satisfacerea urmtorului subobiectiv.

Odat ce o variabil a fost legat, ntr-un program Prolog, singura modalitate de a deveni liber este prin backtracking. Subobiectivele trebuie satisfcute n ordine, de la nceput spre sfrit.

Clauzele - predicat sunt testate n ordinea n care apar n program, de sus n jos.

Cnd un subobiectiv gsete o potrivire a antetului unei reguli, n continuare trebuie satisfcut corpul regulii respective. Corpul regulii va constitui un nou set de subobiective care trebuie satisfcute.

Un obiectiv este satisfcut cnd este gsit o potrivire pentru toate faptele de la extremitile arborelui corespunztor acestui obiectiv.

Cu ajutorul tehnicii backtracking Prolog poate gsi toate soluiile unui probleme, nu doar pe prima.

Controlul cutrii soluiilor

Mecanismul backtracking implementat de ctre Prolog poate conduce la cutri care nu sunt necesare; din acest motiv poate aprea o ineficien n cutarea soluiilor. De exemplu sunt situaii n care se dorete aflarea unei singure soluii, pentru o anumit problem particular; n alte situaii, dimpotriv, ar putea fi necesar ca mecanismul de cutare s fie forat s continue cutarea chiar dac un anumit obiectiv particular a fost ndeplinit.

Prolog furnizeaz dou predicate pentru controlul cutrii:

predicatul fail care se utilizeaz cnd se dorete forarea mecanismului backtracking;

predicatul cut care se simbolizeaz prin ! i se utilizeaz cnd se dorete prevenirea mecanismului backtracking.Utilizarea predicatului failLa apelul acestui predicat Prolog ncepe cutarea prin backtracking (forat, de la nceput). Acest lucru poat fi necesar n anumite situaii pentru gsirea unor soluii alternative. Predicatul fail, foreaz apariia unui eec, i, n consecin, ncurajeaz mecanismul backtracking (revenire napoi i ncercare din nou backing up and trying again). Efectul predicatului fail corespunde efectului comparaiei 2 = 3 sau oricrui alt predicat imposibil.Predicatul fail nu poate fi niciodat satisfcut, astfel nct Prolog este obligat s revin napoi i va reveni n punctul n care se gsesc mai multe soluii. Cnd are loc revenirea napoi Prolog revine la ultimul apel care poate produce mai multe soluii. Un astfel de apel este numit nedeterminist. Un apel nedeterminist poate produce mai multe soluii, n timp ce un apel determinist produce o singur soluie.Predicatul fail nu poate oferi noi soluii, astfel nct Prolog trebuie s revin napoi, n acest caz la primul subobiectiv al regulei.

Dup un predicat fail n corpul unei reguli nu se mai pune alt subobiectiv deoarece dac oricum fail eueaz, nu se mai face nici un apel la vreun subobiectiv plasat dup fail.Utilizarea predicatului cutPredicatul cut este utilizat n Prolog pentru a preveni backtracking, el este scris ca un semn de exclamare (!). Efectul acestui predicat este urmtorul: este imposibil s se revin prin backtracking peste un cut.Predicatul cut se pune ntr-o clauz n acelai fel n care se pune un subobiectiv. Dup ce procesarea corpului unei reguli, apelul predicatului cut se va finaliza cu succes imediat, i se va apela urmtorul subobiectiv (dac acesta exist). Dup ce procesarea predicatului cut a fost ncheiat, este imposibil revenirea la subobiectivele care sunt plasate naintea predicatului cut.

Exist dou modaliti de utilizare a predicatului cut:

Atunci cnd se cunosc anticipat posibilitile care nu vor conduce niciodat la soluii care au sens i ar fi o pierdere inutil de timp i de spaiu de memorie s se caute soluii alternative. Programele rezultate vor rula mai repede i vor utiliza mai puin memorie. Acest tip de predicat se mai numete cut verde(green cut).

Cnd logica unui program cere utilizarea unui predicat cut pentru a preveni luarea n considerare a unor subobiective alternative, atunci predicatul se numete cut rou(red cut). Aplicaii rezolvateAplicaia 1

Se d urmtoarea baz de cunotine:

Slavici a scris Mara care are 280 de pagini.

Sadoveanu a scris Neamul oimretilorcare are 300 de pagini .

Creanga a scris Amintiri din copilrie care are 100 de pagini.

O carte este roman dac are cel puin 250 de pagini.

S se scrie un program Prolog care rspunde ntrebrii: Care cri sunt romane?

Programul corespunztor problemei este:

domains

titlu,autor = symbol

pagini = ushort

predicates

carte(titlu, pagini)

nondeterm scrisa_de(autor, titlu)

nondeterm roman(titlu)

clauses

scrisa_de(slavici,"Mara").

scrisa_de(creanga, "Amintiri din copilarie").

scrisa_de(sadoveanu, "Neamul Soimarestilor").

carte("Neamul Soimarestilor", 300).

carte("Amintiri din copilarie", 100).

carte("Mara",280).

roman(Titlu):-

scrisa_de(_, Titlu), carte(Titlu, Lungime), Lungime >=250.

goal

roman(X). Analiza programului:

Testul goal va furniza n fereastra de ieire urmtorul rezultat:X=Mara

X=Neamul Soimarestilor

2 SolutionsProgramul este structurat pe patru seciuni.

n prima seciune de definesc trei domenii standard cu nume personalizate pentru c se dorete clarificarea rolului fiecrui argument din predicatele declarate n seciunea urmtoare. n a doua seciune s-au declarat trei predicate: predicatul carte cu dou argumente de tip titlu, respectiv pagini, predicatul scrisa_de cu dou argumente de tip autor, respectiv titlu i predicatul roman cu un argument de tip titlu.

n seciunea legat de clauze sunt definite cele trei predicate, primele dou prin intermediul faptelor, iar ultimul prin intermediul unei reguli.

Ultima seciune corespunde cerinei din enunul problemei, ntrebare redat de interogarea roman(X). n interogarea roman(X) variabila X este o variabil liber, valoarea sa este necunoscut pn n momentul n care se gsete o soluie.

Prolog va rezolva aceast interogare cutnd n lista de fapte i reguli de la nceput spre sfrit, utiliznd mecanismul de cutare cu revenire. Predicatul roman fiind definit prin intermediul unei reguli, se va ncerca satisfacerea tuturor subobiectivelor din corpul acestei reguli. Primul subobiectiv corespunde predicatului scrisa_de, iar variabila liber Titlu va deveni legat de atomul "Mara", primul argument al predicatului din subobiectiv fiind nlocuit cu variabila anonim, deoarece n determinarea acelor cri care sunt romane nu ne intereseaz numele autorului. Aceast unificare reprezint un prim punct de ramificare. Al doilea subobiectiv al regulii devine carte("Mara",Lungime). Se va cuta n seciunea unde este definit predicatul carte dac exist un fapt al crui prim argument s fie atomul "Mara". Se va gsi potrivire la cel de-al treilea fapt din definiia predicatului carte, variabila liber Lungime devenind legat de atomul 280. Aceast unificare reprezint al doilea punct de ramificare.Al treilea subobiectiv al regulii devine 280>=250, subobiectiv ncheiat cu succes. Astfel se obinut o prim soluie.

Cutarea nu se oprete aici, revenindu-se la al doilea punct de ramificare variabila Lungime redevine liber i se ncearc o nou potrivire la urmtorul fapt. Se observ c primul argument de la subobiectiv, atomul "Mara", nu mai poate fi unificat cu primul argument de la celelalte fapte din seciunea de clauze.

Revenindu-se la primul punct de ramificare, variabila Titlu redevine liber i se ncearc o nou potrivire la urmtorul fapt corespunztor predicatului scrisa_de. Variabila Titlu devine legat de atomul "Amintiri din copilarie", iar al doilea subobiectiv al regulii devine carte("Amintiri din copilarie",Lungime). Se va cuta n seciunea unde este definit predicatul carte dac exist un fapt al crui prim argument s fie atomul "Amintiri din copilarie". Se va gsi potrivire la cel de-al doilea fapt din definiia predicatului carte, variabila liber Lungime devenind legat de atomul 100. Al treilea subobiectiv al regulii devine 100>=250, subobiectiv ncheiat cu eec.Cutarea nu se oprete aici, revenindu-se la al doilea punct de ramificare variabila Lungime redevine liber i se ncearc o nou potrivire la urmtorul fapt. Se observ c primul argument de la subobiectiv, atomul "Amintiri din copilarie", nu mai poate fi unificat cu primul argument de la celelalte fapte din seciunea de clauze. Revenindu-se la primul punct de ramificare, variabila Titlu redevine liber i se ncearc o nou potrivire la urmtorul fapt corespunztor predicatului scrisa_de. Variabila Titlu devine legat de atomul "Neamul Soimarestilor", iar al doilea subobiectiv al regulii devine carte("Neamul Soimarestilor",Lungime). Se va cuta n seciunea unde este definit predicatul carte dac exist un fapt al crui prim argument s fie atomul "Neamul Soimarestilor". Se va gsi potrivire la primul fapt din definiia predicatului carte, variabila liber Lungime devenind legat de atomul 300. Al treilea subobiectiv al regulii devine 300>=250, subobiectiv ncheiat cu succes. Astfel se obine o nou soluie.Mecanismul de cutare cu revenire se ncheie odat cu revenirea la primul punct de ramificare, deoarece pentru variabila liber Titlu nu se mai poate realiza nicio potrivire. Aplicaia 2Se d urmtoarea baz de cunotine:

Mamiferele i petii sunt animale.

Zebra este mamifer.

Rechinul, pstravul i foca sunt peti.

Rechinul i foca triesc n ap.

Zebra i foca triesc pe pamnt.

S se scrie un program Prolog care rspunde ntrebrii: Cine noat?

Programul corespunztor problemei este:

predicates

nondeterm tip(symbol, symbol)

nondeterm este_un(symbol, symbol)

traieste(symbol, symbol)

nondeterm inoata(symbol)

clauses

tip(mamifer,animal).

tip(peste,animal).

este_un(zebra,mamifer).

este_un(rechin,peste).

este_un(pastrav,peste).

este_un(foca,peste).

traieste(zebra,pe_pamant).

traieste(foca,pe_pamant).

traieste(foca,in_apa).

traieste(rechin,in_apa).

inoata(Y):-

tip(X,animal),

este_un(Y,X),

traieste(Y,in_apa).

goal

inoata(Cine).

Analiza programului:Testul goal va furniza n fereastra de ieire urmtorul rezultat:Cine=rechinCine=foca2 Solutions

Programul este structurat pe trei seciuni.

n prima seciune s-au declarat patru predicate: predicatul tip cu dou argumente de tip symbol, predicatul este_un cu dou argumente de tip symbol, predicatul traieste cu dou argumente de tip symbol i predicatul inoata cu un argument de tip symbol.

n seciunea legat de clauze sunt definite cele patru predicate, primele trei prin intermediul faptelor, iar ultimul prin intermediul unei reguli.

Ultima seciune corespunde cerinei din enunul problemei, ntrebare redat de interogarea inoata(Cine). n interogarea inoata(Cine) variabila Cine este o variabil liber, valoarea sa este necunoscut pn n momentul n care se gsete o soluie.

Prolog va rezolva aceast interogare cutnd n lista de fapte i reguli de la nceput spre sfrit, utiliznd mecanismul de cutare cu revenire. Predicatul inoata fiind definit prin intermediul unei reguli, se va ncerca satisfacerea tuturor subobiectivelor din corpul acestei reguli. Primul subobiectiv corespunde predicatului tip, iar variabila liber X va deveni legat de atomul mamifer. Aceast unificare reprezint un prim punct de ramificare.

Al doilea subobiectiv al regulii devine este_un(Y,mamifer). Se va cuta n seciunea unde este definit predicatul este_un dac exist un fapt pentru care al doilea argument s fie atomul mamifer. Se va gsi potrivire la primul fapt din definiia predicatului este_un, variabila liber Y devenind legat de atomul zebra. Aceast unificare reprezint al doilea punct de ramificare.

Al treilea subobiectiv al regulii devine traieste(zebra,in_apa), iar n continuare se va cuta n seciunea unde este definit predicatul traieste dac exist un fapt care s coincid cu subobiectivul anterior precizat. Negsindu-se un astfel de fapt, cutarea se ncheie cu eec.

Cutarea nu se oprete aici, revenindu-se la al doilea punct de ramificare variabila Y redevine liber i se ncearc o nou potrivire la urmtorul fapt. Se observ c al doilea argument de la subobiectiv, atomul mamifer, nu mai poate fi unificat cu al doilea argument de la celelalte fapte corespunztoare predicatului este_un din seciunea de clauze. Revenindu-se la primul punct de ramificare, variabila X redevine liber i se ncearc o nou potrivire la urmtorul fapt corespunztor predicatului tip. Variabila X devine legat de atomul peste, iar al doilea subobiectiv al regulii devine este_un(Y,peste). Se va cuta n seciunea unde este definit predicatul este_un dac exist un fapt pentru care al doilea argument s fie atomul peste. Se va gsi potrivire la cel de-al doilea fapt din definiia predicatului este_un, variabila liber Y devenind legat de atomul rechin. Al treilea subobiectiv al regulii devine traieste(rechin,in_apa), iar n continuare se va cuta n seciunea unde este definit predicatul traieste dac exist un fapt care s coincid cu subobiectivul anterior precizat. Gsindu-se un astfel de fapt, cutarea se ncheie cu succes, obinndu-se o prim soluie.

Cutarea nu se oprete aici, revenindu-se la al doilea punct de ramificare variabila Y redevine liber i se ncearc o nou potrivire la urmtorul fapt. Se va gsi potrivire la cel de-al treilea fapt din definiia predicatului este_un, variabila liber Y devenind legat de atomul pastrav. Al treilea subobiectiv al regulii devine traieste(pastrav,in_apa), iar n continuare se va cuta n seciunea unde este definit predicatul traieste dac exist un fapt care s coincid cu subobiectivul anterior precizat. Negsindu-se un astfel de fapt, cutarea se ncheie cu eec.

Variabila Y redevine liber, iar n continuare se va gsi potrivire la ultimul fapt din definiia predicatului este_un, variabila liber Y devenind legat de atomul foca.Al treilea subobiectiv al regulii devine traieste(foca,in_apa), iar n continuare se va cuta n seciunea unde este definit predicatul traieste dac exist un fapt care s coincid cu subobiectivul anterior precizat. Gsindu-se un astfel de fapt, cutarea se ncheie cu succes, obinndu-se o nou soluie.

Variabila Y redevine liber, dar pentru c nu mai exist nicio o definiie a predicatului este_un, se revine la primul punct de ramificare. Mecanismul de cutare cu revenire se ncheie odat cu revenirea la primul punct de ramificare, deoarece pentru variabila liber X nu se mai poate realiza nicio potrivire.

Aplicaia 3

Se d urmtoarea baz de cunotine:

Preul mainii fiat de culoare verde este 24000.

Preul mainii audi de culoare alb este 28000.

Preul mainii renault de culoare gri este 15000.

Preul mainii mercedes de culoare negru este 24000.

Preul mainii mercedes de culoare roie este 26000.

Preul mainii porsche de culoare roie este 24000.

Preul mainii skoda de culoare alb este 19000.

Preul mainii citroen de culoare galben este 27000.

Preul mainii citroen de culoare verde este 22000. Culorile rou i galben sunt vesele.

Culorile negru i gri sunt sobre.

Culoarea alb este clasic.

Culoarea verde este iptoare.

O main va fi cumparat dac culoarea sa este vesel i preul este mai mare dect 25000. S se scrie un program Prolog care rspunde ntrebrii: Care main va fi cumprat prima?

Programul corespunztor problemei este:

predicates

nondeterm cumpara_masina(symbol,symbol)

nondeterm masina(symbol,symbol,integer)

culoare(symbol,symbol)

clauses

cumpara_masina(Model,Culoare):-

masina(Model,Culoare,Pret),

culoare(Culoare,vesela),!,

Pret > 25000.

masina(fiat,verde,25000). masina(audi,alb,28000).

masina(mercedes,rosu,26000). masina(mercedes,negru,24000).

masina(renault,galben,15000).

masina(porsche,rosu,24000).

masina(skoda,alb,19000).

masina(citroen,galben,27000).

masina(citroen,verde,22000).

culoare(rosu,vesela).

culoare(negru,sobra).

culoare(verde,tipatoare).

culoare(alb,clasic).

culoare(gri,sobra). culoare(galben,vesela).

goal cumpara_masina(Model,Culoare).Analiza programului:

Testul goal va furniza n fereastra de ieire urmtorul rezultat:Model=mercedes, Culoare=rosu1 SolutionProgramul este structurat pe trei seciuni.

n prima seciune s-au declarat trei predicate: predicatul cumpara_masina cu dou argumente de tip symbol, predicatul masina cu dou argumente de tip symbol i un argument de tip integer i predicatul culoare cu dou argumente de tip symbol. n seciunea legat de clauze sunt definite cele trei predicate, primul prin intermediul unei reguli, iar celelalte prin intermediul faptelor.

Ultima seciune corespunde cerinei din enunul problemei, ntrebare redat de interogarea cumpara_masina(Model,Culoare). n interogarea cumpara_masina (Model,Culoare) variabilele Model i Culoare sunt variabile libere, valorile lor fiind necunoscute pn n momentul n care se gsete o soluie.Prolog va rezolva aceast interogare cutnd n lista de fapte i reguli de la nceput spre sfrit, utiliznd mecanismul de cutare cu revenire. Predicatul cumpara_masina fiind definit prin intermediul unei reguli, se va ncerca satisfacerea tuturor subobiectivelor din corpul acestei reguli. Primul subobiectiv corespunde predicatului masina, iar variabilele libere Model, Culoare, Pret vor deveni legate de atomii fiat, verde i, respectiv, 25000. Aceast unificare reprezint un prim punct de ramificare.

Al doilea subobiectiv al regulii devine culoare(verde,vesela). Se va cuta n seciunea unde este definit predicatul culoare dac exist un fapt care s coincid cu subobiectivul anterior precizat. Negsindu-se un astfel de fapt, cutarea se ncheie cu eec. Cutarea nu se oprete aici, revenindu-se la punctul de ramificare. Variabilele Model, Culoare, Pret redevin libere i se ncearc o nou potrivire la urmtorul fapt. Variabilele libere Model, Culoare, Pret vor deveni legate de atomii audi, alb i, repsectiv, 28000. Al doilea subobiectiv al regulii devine culoare(alb,vesela). Se va cuta n seciunea unde este definit predicatul culoare dac exist un fapt care s coincid cu subobiectivul anterior precizat. Negsindu-se un astfel de fapt, cutarea se ncheie cu eec.

Cutarea nu se oprete i se revene la punctul de ramificare. Variabilele Model, Culoare, Pret redevin libere i se ncearc o nou potrivire la urmtorul fapt. Variabilele libere Model, Culoare, Pret vor deveni legate de atomii mercedes, rosu i, repsectiv, 26000.

Al doilea subobiectiv al regulii devine culoare(rosu,vesela). Se va cuta n seciunea unde este definit predicatul culoare dac exist un fapt care s coincid cu subobiectivul anterior precizat. Gsindu-se un astfel de fapt, se ajunge la predicatul cut i se trece peste acesta de la stnga la dreapta. n continuare se verific dac ultimul subobiectiv este ndeplinit. Aceast verificare se ncheie cu succes, obinndu-se o soluie. Pentru c s-a utilizat predicatul cut, mecanismul de cutare cu revenire este stopat.

Aplicaia 4S se implementeze un program Prolog pentru a aranja un turneu ntre juctorii n vrsta de nou ani ai clubului respectiv. Se vor organiza dou jocuri pentru fiecare pereche de juctori. Scopul va fi s se gseasc toate perechile posibile pe care le putem face cu juctorii n vrsta de 9 ani.

Programul corespunztor problemei este:

domains

copil=symbol

varsta=byte

predicates

nondeterm jucator(copil, varsta)

perechi

clauses

jucator(marius,9).

jucator(paul,10).

jucator(cristian,9).

jucator(sorin,9).

perechi:-

jucator(Copil1, 9),

jucator(Copil2, 9),

Copil1Copil2,

write("Pereche: (",Copil1,",",Copil2,")"),

nl, fail.

perechi.

goal

perechi.

Analiza programului:

Testul goal va furniza n fereastra de ieire urmtorul rezultat: Pereche: (marius,cristian)

Pereche: (marius,sorin)

Pereche: (cristian,marius)

Pereche: (cristian,sorin)

Pereche: (sorin,marius)

Pereche: (sorin,cristian)

yes

Programul este structurat pe patru seciuni.

n prima seciune de definesc dou domenii standard cu nume personalizate pentru c se dorete clarificarea rolului fiecrui argument din predicatele declarate n seciunea urmtoare. n a doua seciune s-au declarat dou predicate: predicatul jucator cu dou argumente de tip copil, respectiv varsta i predicatul perechi fr argumente. n seciunea legat de clauze sunt definite cele dou predicate, primul prin intermediul faptelor, iar al doilea prin intermediul unei reguli i a unui fapt.

Ultima seciune corespunde cerinei din enunul problemei, ntrebare redat de interogarea perechi.

Prolog va rezolva aceast interogare cutnd n lista de fapte i reguli de la nceput spre sfrit, utiliznd mecanismul de cutare cu revenire. Predicatul perechi fiind definit prin intermediul unei reguli, se va ncerca satisfacerea tuturor subobiectivelor din corpul acestei reguli. Primele dou subobiective corespund predicatului jucator. Dup ce variabilele libere Copil1 i Copil2 devin legate, iar al treilea obiectiv al regulii este ndeplinit, predicatul predefinit write va afia numele celor 2 copii ce vor forma o pereche, obinndu-se o soluie. Regula se ncheie cu predicatul fail, prin intermediul cruia se presupune c a euat cutarea i se foreaz mecanismul de bactracking. Datorit prezenei ultimului fapt din seciunea de clauze, afiarea perechilor ce se pot forma se ncheie cu succes. Aplicaia 5Se d urmtoarea baz de cunotine:

Un student este bursier dac are media mai mare sau egal cu 8.50 i nu este restanier..

Lucia are media 8.50.

Sebastian are media 7.00.

Ioana are media 8.70.

Lucia i Sebastian sunt restanieri.

S se scrie un program Prolog care rspunde ntrebrii: Cine este bursier?

Programul corespunztor problemei este:

domains

nume = symbol

media = real

predicates

nondeterm bursier(nume)

nondeterm student(nume, media)

restantier(nume)

clauses

bursier(Nume):-

student(Nume, Media),

Media>=8.5,

not(restantier(Nume)).

student("Lucia", 8.5).

student("Petre", 7.0).

student("Ioana", 8.7).

restantier("Lucia").

restantier("Sebastian").

goal

bursier(Cine). Analiza programului:

Testul goal va furniza n fereastra de ieire urmtorul rezultat: Cine=Ioana

1 Solution Programul este structurat pe patru seciuni. n prima seciune de definesc dou domenii standard cu nume personalizate pentru c se dorete clarificarea rolului fiecrui argument din predicatele declarate n seciunea urmtoare. n a doua seciune s-au declarat trei predicate: predicatul bursier cu un argument de tip nume, predicatul student cu dou argumente de tip nume, respectiv media i predicatul restantier cu un argument de tip nume.

n seciunea legat de clauze sunt definite cele trei predicate, primul prin intermediul unei reguli, iar celelalte prin intermediul faptelor.

Ultima seciune corespunde cerinei din enunul problemei, ntrebare redat de interogarea bursier(Cine). n interogarea bursier(Cine) variabila Cine este o variabil liber, valoarea sa este necunoscut pn n momentul n care se gsete o soluie.

Prolog va rezolva aceast interogare cutnd n lista de fapte i reguli de la nceput spre sfrit, utiliznd mecanismul de cutare cu revenire. Predicatul bursier fiind definit prin intermediul unei reguli, se va ncerca satisfacerea tuturor subobiectivelor din corpul acestei reguli. Primul subobiectiv corespunde predicatului student, iar variabilele libere Nume i Media vor deveni legate de atomii "Lucia", respectiv 8.5. Aceast unificare reprezint un prim punct de ramificare.

Al doilea subobiectiv al regulii devine 8.5>=8.5, subobiectiv ncheiat cu succes. Al treilea subobiectiv este definit prin intermediul predicatelor not i restantier. Acesta se va ncheia cu eec pentru c n seciunea de clauze exist faptul restantier(Lucia). Cutarea nu se oprete aici, revenindu-se la punctul de ramificare. Variabilele Nume i Media redevin libere i se ncearc o nou potrivire la urmtorul fapt. Variabila Nume devine legat de atomul "Petre" i variabila Media de atomul 7.0, iar al doilea subobiectiv al regulii devine 7.0>=8.5. Acesta se ncheie cu eec i se revine la punctul de ramificare. Variabilele Nume i Media redevin libere i se ncearc o nou potrivire la urmtorul fapt. Variabila Nume devine legat de atomul "Ioana" i variabila Media de atomul 8.7, iar al doilea subobiectiv al regulii devine 8.7>=8.5 i se ncheie cu succes. Al treilea subobiectiv se va ncheia cu succes pentru c n seciunea de clauze nu exist faptul restantier(Ioana). Astfel se obine o prim soluie, apoi se revine la punctul de ramaficare. Mecanismul de cutare cu revenire se ncheie odat cu revenirea la primul punct de ramificare, deoarece pentru variabilele libere Nume i Media nu se mai poate realiza nicio potrivire. Aplicaia 6S se implementeze un program Prolog pentru rezolvarea ecuaiei de gradul al doilea.

Programul corespunztor problemei este:

predicates

nondeterm ecuatia(real,real,real)

nondeterm solutie (real,real,real)

nondeterm rezolva

clauses

ecuatia(0,0,0):- !,write("Exista o infinitate de solutii"),nl.

ecuatia(0,0,_):-

!,write("Ecuatie imposibila"),nl.

ecuatia(0,B,C):-

!,X=-C/B,write("Solutia este ",X),nl.

ecuatia(A,B,C):-

D=B*B-4*A*C,solutie(A,B,D).

solutie(_,_,D):-

D