Download - Inteligenta Artificial A Curs

Transcript

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 1/183

Programare Logică

Nicolae Constantinescu

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 2/183

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 3/183

Cuprins

Prefaţă . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

0.1 Introducere. Fapte. Reguli . . . . . . . . . . . . . . . . . . . . . 15

0.1.1 Fundamente teoretice . . . . . . . . . . . . . . . . . . . . 15

0.1.2 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

0.1.3 Exerciţii propuse . . . . . . . . . . . . . . . . . . . . . . 28

0.1.4 Teme de studiu . . . . . . . . . . . . . . . . . . . . . . . 28

0.2 Termeni. Variabile. Backtracking. Predicatele-sistem trace,

read, write . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

0.2.1 Fundamente teoretice . . . . . . . . . . . . . . . . . . . . 29

0.2.2 Exerciţii propuse . . . . . . . . . . . . . . . . . . . . . . 40

0.2.3 Teme de studiu . . . . . . . . . . . . . . . . . . . . . . . 40

0.3 Unificarea. Operaţiile aritmetice . . . . . . . . . . . . . . . . . . 41

0.3.1 Fundamente teoretice . . . . . . . . . . . . . . . . . . . . 41

0.3.2 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

0.3.3 Exerciţii propuse . . . . . . . . . . . . . . . . . . . . . . 48

0.3.4 Teme de studiu . . . . . . . . . . . . . . . . . . . . . . . 48

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 4/183

0.4 Recursivitate. Predicatele !(cut) şi fail . . . . . . . . . . . . . . 49

0.4.1 Fundamente teoretice . . . . . . . . . . . . . . . . . . . . 49

0.4.2 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . 560.4.3 Exerciţii propuse . . . . . . . . . . . . . . . . . . . . . . 64

0.4.4 Teme de studiu . . . . . . . . . . . . . . . . . . . . . . . 64

0.5 Turnurile din Hanoi. Funcţiile Fibonacci şi Ackermann . . . . . 65

0.5.1 Fundamente teoretice . . . . . . . . . . . . . . . . . . . . 65

0.5.2 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

0.5.3 Exerciţii propuse . . . . . . . . . . . . . . . . . . . . . . 71

0.5.4 Teme de studiu . . . . . . . . . . . . . . . . . . . . . . . 72

0.6 Liste . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

0.6.1 Fundamente teoretice . . . . . . . . . . . . . . . . . . . . 73

0.6.2 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

0.6.3 Exerciţii propuse . . . . . . . . . . . . . . . . . . . . . . 98

0.6.4 Teme de studiu . . . . . . . . . . . . . . . . . . . . . . . 99

0.7 Grafuri. Arbori . . . . . . . . . . . . . . . . . . . . . . . . . . . 100

0.7.1 Fundamente teoretice . . . . . . . . . . . . . . . . . . . . 100

0.7.2 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . 101

0.7.3 Exerciţii propuse . . . . . . . . . . . . . . . . . . . . . . 105

0.7.4 Teme de studiu . . . . . . . . . . . . . . . . . . . . . . . 105

0.8 Probleme speciale . . . . . . . . . . . . . . . . . . . . . . . . . . 106

0.8.1 Problema Damelor . . . . . . . . . . . . . . . . . . . . . 106

0.8.2 Problema mutării calului . . . . . . . . . . . . . . . . . . 108

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 5/183

0.8.3 Exerciţii propuse . . . . . . . . . . . . . . . . . . . . . . 110

0.8.4 Teme de studiu . . . . . . . . . . . . . . . . . . . . . . . 110

0.9 Fişiere. Baze de date dinamice . . . . . . . . . . . . . . . . . . . 1120.9.1 Fundamente teoretice . . . . . . . . . . . . . . . . . . . . 112

0.9.2 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . 115

0.9.3 Exerciţii propuse . . . . . . . . . . . . . . . . . . . . . . 120

0.9.4 Teme de studiu . . . . . . . . . . . . . . . . . . . . . . . 121

1 Probleme de la concursurile de programare 123

1.1 Probleme de la concursurile de programare . . . . . . . . . . . . 1241.1.1 Ascii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124

1.1.2 Staţii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125

1.1.3 Triplete . . . . . . . . . . . . . . . . . . . . . . . . . . . 126

1.1.4 Spirala . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127

1.1.5 Perioada . . . . . . . . . . . . . . . . . . . . . . . . . . . 127

1.1.6 Numere . . . . . . . . . . . . . . . . . . . . . . . . . . . 128

1.1.7 Triunghi . . . . . . . . . . . . . . . . . . . . . . . . . . . 130

1.1.8 Diamant . . . . . . . . . . . . . . . . . . . . . . . . . . . 130

1.1.9 Drum . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131

1.1.10 Tabla . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134

1.1.11 Şarpele belgian . . . . . . . . . . . . . . . . . . . . . . . 135

1.1.12 Hexagon . . . . . . . . . . . . . . . . . . . . . . . . . . . 136

2 Soluţiile problemelor propuse 139

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 6/183

2.1 Introducere. Fapte. Reguli . . . . . . . . . . . . . . . . . . . . . 139

2.1.1 Soluţie teoretică . . . . . . . . . . . . . . . . . . . . . . . 139

2.1.2 Apel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141

2.1.3 Cod sursă . . . . . . . . . . . . . . . . . . . . . . . . . . 142

2.2 Termeni. Variabile. Backtracking. Predicatele-sistem trace,

read, write . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144

2.2.1 Soluţie teoretică . . . . . . . . . . . . . . . . . . . . . . . 145

2.2.2 Apel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145

2.2.3 Cod sursă . . . . . . . . . . . . . . . . . . . . . . . . . . 146

2.3 Unificarea. Operaţiile aritmetice . . . . . . . . . . . . . . . . . . 149

2.3.1 Soluţie teoretică . . . . . . . . . . . . . . . . . . . . . . . 150

2.3.2 Apel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150

2.3.3 Cod sursă . . . . . . . . . . . . . . . . . . . . . . . . . . 150

2.4 Recursivitate. Predicatele !(cut) şi fail . . . . . . . . . . . . . . 151

2.4.1 Soluţie teoretică . . . . . . . . . . . . . . . . . . . . . . . 151

2.4.2 Apel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151

2.4.3 Cod sursă . . . . . . . . . . . . . . . . . . . . . . . . . . 152

2.5 Turnurile din Hanoi. Funcţiile Fibonacci şi Ackermann . . . . . 152

2.5.1 Soluţie teoretică . . . . . . . . . . . . . . . . . . . . . . . 152

2.5.2 Apel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152

2.5.3 Cod Sursă . . . . . . . . . . . . . . . . . . . . . . . . . . 153

2.6 Liste . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153

2.6.1 Soluţie teoretică . . . . . . . . . . . . . . . . . . . . . . . 153

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 7/183

2.6.2 Apel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154

2.6.3 Cod sursă . . . . . . . . . . . . . . . . . . . . . . . . . . 155

2.7 Probleme speciale . . . . . . . . . . . . . . . . . . . . . . . . . . 1562.7.1 Soluţie teoretică . . . . . . . . . . . . . . . . . . . . . . . 156

2.7.2 Apel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157

2.7.3 Cod sursă . . . . . . . . . . . . . . . . . . . . . . . . . . 157

2.8 Fişiere. Baze de date dinamice . . . . . . . . . . . . . . . . . . . 158

2.8.1 Soluţia problemei 0.9.1 . . . . . . . . . . . . . . . . . . . 159

2.8.2 Soluţia problemei 0.9.2 . . . . . . . . . . . . . . . . . . . 163

3 Anexa Predicate 167

3.1 Anexa predicate . . . . . . . . . . . . . . . . . . . . . . . . . . . 168

3.1.1 Notaţiile predicatelor . . . . . . . . . . . . . . . . . . . . 168

3.1.2 Încărcarea fişierelor sursă . . . . . . . . . . . . . . . . . . 168

3.1.3 Compararea şi unificarea termenilor . . . . . . . . . . . . 168

3.1.4 Predicate de control . . . . . . . . . . . . . . . . . . . . 169

3.1.5 Baze de date dinamice . . . . . . . . . . . . . . . . . . . 170

3.1.6 Intrări şi Ieşiri . . . . . . . . . . . . . . . . . . . . . . . . 170

3.1.7 Predicate primitive pentru I/O . . . . . . . . . . . . . . 173

3.1.8 Citirea şi scrierea termenilor . . . . . . . . . . . . . . . . 174

3.1.9 Predicate pentru operaţii cu liste . . . . . . . . . . . . . 175

3.1.10 Predicate aritmetice . . . . . . . . . . . . . . . . . . . . 176

3.1.11 Funcţii aritmetice . . . . . . . . . . . . . . . . . . . . . . 177

3.1.12 Urmărirea execuţiei programului . . . . . . . . . . . . . . 179

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 8/183

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 9/183

Listă de figuri

1 Fereastra pentru trace în mod grafic . . . . . . . . . . . . . . . . 35

1.1 Exemple de apel pentru N=5 şi respectiv N=3 . . . . . . . . . . 124

1.2 Exemplu de display digital . . . . . . . . . . . . . . . . . . . . . 129

1.3 Tabla nemodificată de spiritul rău . . . . . . . . . . . . . . . . . 132

1.4 Tabla alterată . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133

1.5 Exemplu de tablă şi reprezentarea corespunzătoare . . . . . . . 134

1.6 Hexagon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 10/183

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 11/183

Listă de tabele

1 Funcţii trigonometrice disponibile în SWI-Prolog . . . . . . . . . 43

2 Funcţii matematice disponibile în SWI-Prolog . . . . . . . . . . 44

3 Predicatele aritmetice in SWI-Prolog . . . . . . . . . . . . . . . 45

4 Câteva valori ale funcţiei Ackermann . . . . . . . . . . . . . . . 70

5 Valorile funcţiei Ackerman calculate în SWI-Prolog . . . . . . . 71

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 12/183

Prefaţă

Programarea logică este o paradigmă a programării declarative, bazată pe

logica de ordinul I. Teza potrivit căreia logica de ordinul I este un util şi practic

limbaj de programare non-deterministic de nivel înalt cu un solid fundament

teoretic aparţine lui R. Kowalsky, care dezvoltă un punct de vedere relaţional

al calculabilităţii ca deducţie, sintetizat prin următoarea formulă:

Calculabilitate = Logică + Control

Dacă punem în antiteză relaţia lui Kowalsky cu cea a lui N. Wirth potrivit

căreia:

Program = Structuri de date + Algoritm

observăm că, în domeniul programării

• procedurale - trebuie rezolvate la nivelul codului atât aspectele logice,

cât şi cele de control

• declarative - trebuie rezolvate numai cele de control.

Considerând că un program logic este constituit dintr-o familie de axiome şi

o ţintă, iar regulile de inferenţă determină faptul că axiomele sunt suficiente

pentru a proba veridicitatea ţintei, execuţia unui program logic corespunde

construcţiei unei demonstraţii a ţintei pe baza axiomelor ataşate programu-

lui. Practic, execuţia unei secvenţe de cod în programarea logică este realizată

prin intermediul unui demonstrator rezolutiv de teoreme. Plecând de la aceste

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 13/183

observaţii şi analizând relaţia dintre calculabilitate şi deducţie, aşa cum a fost

ea tratată de P. J. Hayes1, putem concluziona că un interpretor al unui limbaj

de programare şi un demonstrator automat de teoreme (motor de inferenţe)au structuri practic identice, iar avantajele de natură practică şi teoretică sunt

obţinute prin combinarea celor două metodologii. În fapt, Kowalsky şi Hayes

propun un comportament convergent pentru deducţie şi calculabilitate.

Teza este similară celei potrivit căreia sistemele de gestiune a bazelor de

date pot fi văzute drept colecţii de structuri relaţionale care definesc logica

datelor.

Colmerauer implementează ideea în construcţia limbajului de programarePROLOG (PROgramming in LOGic), bazându-se şi pe o importantă lucrare

a lui A. Robinson2 şi utilizând de la Kowalsky conceptul de "clauză Horn",

fundamentând astfel strategia bazată pe o demonstraţie lineară cu backtrac-

king şi unificarea capetelor de clauze. Limbajul PROLOG al acestui început

nu era la fel de matur ca limbajul LISP, dar implementarea realizată de H.D.

Warren a condus la îmbunătăţiri substanţiale ale limbajului.

Compilatorul a fost scris aproape integral în PROLOG, translatând clau-zele PROLOG în instrucţiuni ale unei maşini abstracte cunoscută sub numele

de Maşina Abstractă Warren (WAM).

1P. Hayes, Computation and deduction, Proc. 2nd Symp. on Mathematical Foundations

of Computer Science (MFCS), Czechoslovakian Academy of Sciences, Prague, 1973, pp.

105-118.2Robinson J.A., A machine-oriented logic based on the resoulution principle, J. ACM

12,1, pp. 23-41, January 1965.

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 14/183

Clocksin şi Mellish continuă efortul de perfecţionare a limbajului obţinând

o versine acceptată ca standard si numită "sintaxă C&M" sau "sintaxă Edin-

burgh". Dintre dialectele limbajului PROLOG amintim Quintus PROLOG,C-PROLOG, Turbo PROLOG, Visual PROLOG, SWI-PROLOG, λPROLOG,

B-PROLOG, BinProlog, GNU Prolog, jPROLOG, SICStus PROLOG , Amzi

PROLOG etc.

Cu toate aceste importante realizări, comunitatea specialiştilor în informa-

tică, în general şi cea a specialiştilor în inteligenţă artificială, în particular, nu

au acordat atenţia cuvenită programării logice.

O schimbare de atitudine s-a înregistrat odată cu lansarea "Japanese FifthGeneration Project", care a redefinit importanţa programării logice pentru ur-

mătoarele generaţii de calculatoare.

Din acel moment limbajul PROLOG a cunoscut o dezvoltare permanentă.

O paradigmă mai recentă este cea a Constraint Language Programming

(CLP), unde domeniul nu este restricţionat la universul Herbrand şi unde uni-

ficarea este înlocuită cu satisfacerea restricţiilor. O instanţă a acestei abordări

poate fi considerată CLP(R) (Constraint Logic Programming over the Realdomain), cu implementarea operatorilor aritmetici (+,-,*,/) şi a funcţiilor sin,

cos etc.

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 15/183

0.1 Introducere. Fapte. Reguli

0.1.1 Fundamente teoretice

PROLOGul a fost inventat la începutul anilor ’70 de către Alain Colmerauer

în Franţa (PROgramming in LOGic=PROLOG). Printre aplicaţiile la care

poate fi folosit PROLOG-ul se numără: sisteme expert, limbaje de specifi-

caţie, înţelegerea limbajelor naturale, baze de date, programarea roboţilor şi

automatizarea gândirii artificiale.

Un program este, în general, compus din două elemente din care unul estepredominant, ne referim la noţiunile de logică şi control. Acestea sunt ele-

mentele care descriu ce face un program şi respectiv cum procedează pentru a

ajunge la o soluţie (spre exemplu în programarea structurată prin intermediul

unui algoritm se ajunge la o soluţie, iar secvenţa de instrucţiuni ale algoritmu-

lui este ce se întâmplă pentru a se ajunge la soluţie ).

Limbajele care aparţin programării structurate descriu pas cu pas modul în

care programul trebuie să se comporte pentru ca după un număr finit de paşisă se obţină soluţia, de aceea spunem că programarea structurată urmează

paradigma imperativă. Aceste limbaje nu sunt însă lipsite de componenta

descriptivă, dincolo de modul imperativ. Să spunem că avem nevoie la un

moment dat să calculăm o valoare, printr-o instrucţiune vom descrie şi modul

în care valoarea va fi obţinută.

Prin contrast, programarea logică se bazează pe alegerea predicatelor care de-

scriu cel mai bine relaţiile care există între obiecte, fiindcă ele vor fi cele care vor

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 16/183

stabili legătura între datele de intrare şi cele de ieşire. Dacă această legătură

nu va fi corect definită este posibil să primim răspunsuri eronate. Compo-

nenta logică a limbajului PROLOG este deci alegerea predicatelor si stabilirearelaţiilor dintre datele descrise de aceste predicate. Controlul asupra modului

de execuţie al programului se află în felul în care sunt aranjate clauzele, dar

şi în câteva elemente de control structural cum este predicatul "cut" (notat

"!") sau predicatul fail . Din aceste motive programarea logică este o abordare

descriptivă, la care elementul structural imperativ este element de control.

PROLOG-ul şi versiunile sale (printre care şi SWI-Prolog) face parte din ca-

tegoria limbajelor de programare logice si este un limbaj declarativ ceea ceînseamnă că mai degrabă programatorul va scrie un program care conţine o

bază de date cu faptele şi relaţiile logice (regulile) dintre ele, astfel încât

atunci când sistemului i se va adresa o întrebare el va consulta baza de fapte şi

reguli pentru a găsi un răspuns (prin deducţie logică). Programarea în PRO-

LOG nu utilizează conceptele de procedură şi atribuire, concepte foarte

răspândite în alte limbaje de programare, în locul acestora întâlnim concepte

proprii programării logice. Faptul că nu există atribuire se explică prin exis-tenţa unei legături (conceptul de unificare) ce se stabileşte între valoare şi

variabilă. Odată produsă această legătură participă la un lanţ de deducţii ce

au loc pe parcursul programului, iar la terminarea lanţului deductiv variabilele

sunt dezlegate de aceste valori.

Printre calităţile PROLOG-ului se număra ’variabilele logice’ care se comportă

ca variabilele matematice, utilizarea backtrackingului pentru căutarea dovezi-

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 17/183

lor şi pentru a se ajunge la o concluzie, structuri de date uniforme. În multe

ocazii vor exista fie mai multe căi de a găsi o soluţie fie mai multe soluţii de

aceea capabilitatea sistemului de a face backtracking se dovedeşte o caracte-ristică importantă.

PROLOG-ul este un limbaj slab în ceea ce priveşte tipurile variabilelor, aceasta

înseamnă că o variabilă de un anumit tip poate conţine, la un moment dat,

date de alt tip.

Exemplele din acest material au fost concepute şi testate în SWI-Prolog ver-

siunea 5.4.3.

0.1.1.1 Structura programului

Aşa cum am spus mai sus un program PROLOG constă în fapte şi reguli , care

se pot grupa sub denumirea generală de date, şi întrebări venite din partea

utilizatorului, la care sistemul trebuie să răspundă.

Datele şi întrebarile sunt clauze Horn de forma:

A(t1, . . . , tn) ←

şi în PROLOG ele sunt notate simbolic prin

A(t1, . . . , tn).

unde A este un predicat iar t1, . . . , tn sunt constante ale limbajului predicatelor.

Simbolul "." marchează finalul unei formule.

O regulă în PROLOG are forma:

A(t1, . . . , tn) : −B1( p1, . . . , pi), . . . , Bn(q1, . . . , q j).

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 18/183

unde A, B1, . . . , Bn sunt predicate, iar t1, . . . , tn, p1, . . . , pi, q1, . . . , q j sunt ter-

meni. Se spune adesea că regulile şi faptele alcătuiesc baza de date a progra-

mului.Interogările sunt numite şi scopuri şi sunt clauze Horn de forma:

B1(s1, . . . , si), . . . , Bn(t1, . . . , t j)

în PROLOG aceste clauze au forma:

? − B1(s1, . . . , si), . . . , Bn(t1, . . . , t j).

unde B1, . . . , Bn sunt simboluri de predicate, iar s1, . . . , si, t1 . . . , t j sunt ter-

meni.

Aşadar un program PROLOG este o colecţie de fapte, reguli şi interogări fără

prea multe indicaţii despre fluxul şi controlul programului. Această structură

marchează fineţea cu care în acest limbaj pot fi obţinute extensii şi îmbunătă-

ţiri prin introducerea de fapte sau reguli fără a interveni asupra structurii si

datelor deja existente în program.

0.1.1.2 Faptele

Faptele sunt cea mai simplă formă de predicat în PROLOG. Ele sunt predica-

tele sau acţiunile care se întâmplă fară să depindă de alte acţiuni sau predicate.

Faptele mai pot fi văzute şi ca o bază de cunoştinţe sau ca date de intrare.

Sintaxa este următoarea:

nume_ predicat( param1, param2, ..., paramN ).

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 19/183

unde N este numărul de parametri fiind numit aritatea predicatului. Un pre-

dicat de aritate 0 se defineşte astfel: nume_ predicat.

Exemple de fapte:

ploua. - predicat de aritate 0

citeste(emil,literatura). - predicat de aritate 2

frati(emil,ion,george). - predicat de aritate 3

Alegerea numelor predicatelor precum şi a interpretării lor se face de către

programator, este deci foarte important să se aleagă nume care nu prezintăambiguităţi şi interpretarea unui predicat să se păstreze pe tot parcursul pro-

gramului. Spre exemplu considerăm predicatul bunic(dan, andrei). care are

interpretarea "Dan este bunicul lui Andrei" dacă vom mai avea un predicat

bunic(marcel, gabi). pe care îl interpretăm "Gabi este bunicul lui Marcel".

Programul scris de noi nu va întoarce rezultatele aşteptate deoarece interpre-

tările programatorului pentru acelaşi predicat sunt diferite, aceasta conducând

în mod indiscutabil la aşteptări eronate cu privire la rezultatul care va fi ob-ţinut.

0.1.1.3 Regulile

O regulă este o formă de predicat care depinde de alte predicate pentru a fi

îndeplinită. Sintaxa este următoarea :

nume_predicat(arg1,arg2,...,argN):-

predicat1(param1,..,paramN),

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 20/183

predicat2(param1,..paramN),

. . . ,

predicatN(param1,...,paramN).Virgula în SWI-Prolog are valoarea unui şi logic. Astfel în exemplul de mai sus

îndeplinirea predicatului de argumente arg1,...,argN depinde de îndeplinirea

tuturor celorlalte predicate, dacă unul din ele întoarce "No" nu se va mai trece

la următorul predicat şi nume_predicat va întoarce şi el "No".

Exemple de reguli:

frate(X,Y):-

parinte(Z,X),parinte(Z,Y).

Această regulă conţine 2 predicate care trebuiesc îndeplinite pentru ca ea să

se îndeplinească. O posibilă traducere a regulii în limbaj natural ar putea fi

următoarea: X este frate cu Y dacă există Z care este părintele lui X şi Z este

părinte şi pentru Y.

picteaza(X):-

pictor(X),tablou(X,Z),

critic_de_arta(Y),

place(Y,Z).

Regula de mai sus conţine 3 sub-scopuri ea poate fi tradusă după cum urmează:

X pictează dacă X este pictor şi el are un tablou Z, Y este un critic de artă şi

îi place tabloul Z.

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 21/183

0.1.1.4 Comenzi în SWI-Prolog

Comenzile SWI-Prolog sunt la rândul lor predicate pe care sistemul le pune la

dispoziţia programatorului. O comandă SWI-Prolog se termină întotdeauna

cu caracterul "." deoarece este considerată a fi un fapt. Iată câteva comenzi

uzuale:

?-pwd. - afişează directorul curent.

?-ls. - afişează fisierele din directorul curent. Directoarele vor avea caracterul

final "/" pentru a putea fi deosebite de fişiere.

?-cd(’cale’). - schimbă directorul.

?-halt. - încheie sesiunea de lucru.

?-help(nume_comandă) - afişează informaţii despre nume_comandă .

?- cd(’c:/PROLOG’).

Yes

?- pwd.c:/PROLOG

Yes

?- ls.

alte ex/ L2ex4.pl L5ex1.pl L7ex4.pl L9ex2.pl

grad.pl L2ex5.pl L5ex2.pl L7ex5.pl L9ex3.pl

Yes.

SWI-Prolog dispune de un browser de fişiere în mod grafic, pentru ca

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 22/183

utilizatorul să nu fie nevoit să vizualizeze structura de directorare şi fişiere

din linie de comandă. Acest browser este util în special pentru editarea

fişierelor .pl (sursă SWI-Prolog ) care vor fi deschise cu utilitarul Note-pad, dacă un alt program de editare nu este configurat pentru a edita fişiere

cu această extesie. Acesta poate fi accesat din meniul File, opţiunea Navigator.

Pentru a încărca un fişier sursă SWI-Prolog tastăm comanda [numefi-

sier]., dacă sistemul va răspunde cu "Yes", fişierul a fost încărcat cu succes,

altfel vom primi un mesaj de genul "ERROR: source_sink ‘numefisier’does not exist" în cazul în care fişierul nu există. Numele fişierului trebuie

scris cu litere mici, mai precis prima literă din nume, altfel SWI-Prolog va

presupune că este vorba de o listă şi textul conţinut înte paranteze este o

variabilă căreia va încerca să-i dea o valoare. În cazul unei erori de sintaxă

în cadrul clauzelor scrise în fişier mesajul arată în felul următor: "ERROR:

c:/PROLOG/numefisier.pl:2:8: Syntax error: Operator expected", calea

către fişier poate fi alta în funcţie de directorul unde se află fişierul pe caredorim să-l compilăm. O altă metodă de a încărca şi compila un fişier este

folosirea predicatelor-sistem consult(numefisier) şi ensure_loaded(numefisier).

Exemple ale metodelor descrise sunt prezentate mai jos:

?- [l1ex1].

l1ex1 compiled 0.00 sec, 1,188 bytes

Yes

?- ensure_loaded(l3ex1). % l1ex1 compiled 0.00 sec, 1,188 bytes

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 23/183

Yes

?- consult(l3ex1).

% l3ex1 compiled 0.00 sec, 0 bytesYes

Pentru a verifica încărcarea corectă a clauzelor putem folosi comanda listing,

prezentată mai jos:

?-listing.

fruct(prune).

are(ion,mere).

...

0.1.2 Exemple

Exemplul 0.1.1.

Fişierul L1ex1.pl conţine clauzele:

are(ion,mere).are(ana,prune).

are(dan,bani).

fruct(mere).

fruct(prune).

Pentru a vedea ce fel de fructe deţine Ion vom apela predicatul are(), indicând

că vrem să aflăm ce fel de fructe deţine prin plasarea pe prima poziţie a ato-

mului "ion" şi pe poziţia secundă variabila X ( variabilele încep cu literă mare

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 24/183

în SWI-Prolog ).

?-are(ion,X).

X=mereDe data aceasta dorim să aflăm dacă Ion deţine un fruct însă nu vrem să ştim

ce fel de fruct este. Pentru aceasta folosim underline "_" ( variabila underline

în SWI-Prolog se numeşte variabilă anonimă, iar valorile conţinute de această

variabilă nu sunt relevante pentru scopul urmărit atunci când se execută pro-

gramul. Mai mult, dacă în cadrul aceluiaşi program exită mai multe variabile

"_" ele pot conţine valori diferite în acelaşi timp fără să se afecteze reciproc.

).?-are(ion,_).

Yes

În următorul exemplu dorim să aflăm cine are mere şi cine are prune.

?-are(X,mere),are(Y,prune).

X=ion Y=ana

Are cineva şi mere şi prune ? Observaţi faptul că faţă de exemplul precendent

primul parametru al predicatului are este aceeaşi variabilă X, asfel dorim sădesemnăm faptul că este vorba de aceeaşi persoană care deţine cele 2 tipuri de

fructe.

?-are(X,mere),are(X,prune).

Are Dan fructe? Pentru a afla răspunsul trebuie mai întâi să aflăm dacă Dan

deţine ceva. Folosim Predicatul are/2 , punând pe poziţia secundă variabila X,

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 25/183

care mai apoi ne întrebăm dacă este fruct . Dacă va fi definit un fapt de forma

fruct(valoareaLuiX). răspunsul va fi afirmativ.

?-are(dan,X),fruct(X).No

Are cineva ceva, dar nu fructe? De data aceasta negăm predicatul fructe prin

predicatul not care este un predicat predefinit în SWI-Prolog.

?-are(X,Y),not(fruct(Y)).

X=dan

Y=bani

Exemplul 0.1.2.

Prezentăm în continuare un exemplu de implementare a unui arbore genealo-

gic. Să observăm faptul că numele personajelor încep cu literă mică, aceasta

deoarece ele sunt atomi (constante sau valori fixate), dacă am fi avut aceste

nume cu literă mare compilatorul SWI-Prolog ar fi considerat că ele sunt va-

riabile. Exemplul este implementat în fişierul L1ex2.pl

parinte(andrei,ionut).parinte(andrei,ilie).

parinte(ilie,emil).

parinte(ilie,irinel).

Cine sunt copii lui andrei? În cazul acesta interogarea are două răspunsuri,

însă sistemul se va opri după găsirea primei soluţii şi va aştepta indicaţii din

partea noastă. Dacă dorim şi afişarea celuilalt răspuns trebuie să apăsam ";",

simbol care reprezintă un sau logic.

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 26/183

?-parinte(andrei,X).

X=ionut ;

X=ilie ;No

Are andrei vreun copil?

?-parinte(andrei,_).

Yes

Cine este tatăl lui emil?

?-parinte(Tata,emil).

Tata=ilieDorim o enumerare a tuturor numelor care se află într-o relaţie de tipul tată-

fiu. Pentru a obţine toate răspunsurile şi la această interogare apăsaţi ";" după

fiecare răspuns din partea sistemului.

?-parinte(X,Y).

X = andrei

Y = ionut ;

X = andreiY = ilie ;

X = ilie

Y = emil ;

X = ilie

Y = irinel ;

Este andrei bunic? Avem din nou o interogare compusă, observaţi din nou

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 27/183

poziţia variabilei X. Pentru ca andrei să fie bunic el trebuie să fie parintele

lui X ( parintele cuiva ) şi acel cineva să aibă un copil (nepotul lui andrei).

După afişarea tuturor soluţiilor vom obţine "No" deoarece sistemul încearcăsă determine alte soluţii pentru clauzele programului, considerând interogarea

adresată. Alte de soluţii neexistând vom primi răspunsul No.

?-parinte(andrei,X),parinte(X,Nepot).

X=ilie

Nepot=emil;

X=ilie

Nepot=irinel;No

Dacă dorim să nu folosim o interogare compusă putem edita fişierul sursă

pentru a defini predicatul bunic(B, N ), prezentat mai jos, care va putea fi apoi

apelat din linia de comandă SWI-Prolog.

bunic(B,N):-parinte(B,P),parinte(P,N).

?-bunic(andrei,irinel).

Yes?-bunic(andrei,Nepot).

Nepot=emil

Nepot=irinel

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 28/183

0.1.3 Exerciţii propuse

Exerciţiul 0.1.1.

Definiţi predicatele cumnat, matuşă, unchi, strabunic, soacră.

0.1.4 Teme de studiu

Tema 0.1.1.

Rulaţi în SWI-Prolog exemplele prezentate.

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 29/183

0.2 Termeni. Variabile. Backtracking.

Predicatele-sistem trace, read, write

0.2.1 Fundamente teoretice

0.2.1.1 Termenii de baza în PROLOG

Un program SWI-Prolog este alcătuit din predicate şi în general se urmăreşte

obţinerea unui răspuns pentru o interogare. Fiecare predicat poate avea una

sau mai multe clauze.

Exemplul 0.2.1.

masina(ferrari).

masina(dacia).

proprietar(george,ferrari).

În exemplul de mai sus predicatul masina are două clauze, iar predicatul pro-prietar are o singură clauză.

O altă caracteristică a predicatelor este aritatea ( numărul de parametri sau

termeni ). Termenii pot fi :

- Întregi - numere pozitive sau negative.

- Atomi - text care începe cu litera mică. Exemplu: ana, alt_atom, atom3,

douaCuvinte, etc.

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 30/183

- Variabile - încep cu litera mare sau "_". Exemplu: X, Y, _z, Variabila,

Masina, Dan, Maria, etc.

- Structuri compuse - ex. listele - [a,b,c,d] sau tuplurile

carte(autor(nume),titlu,data).

0.2.1.2 Variabilele

Variabilele în SWI-Prolog încep întotdeauna cu literă mare sau "_" şi sunt

fără tip, adică pot conţine orice fel de valoare. Totuşi iniţial o variabilă este

doar un loc unde se va stoca la un moment dat în timpul procesării unei clauze

o valoare, care la momentul actual nu este disponibilă. Spunem că variabila

iniţial nu este instanţiată. Această funcţie de loc de stocare a unei variabile

poate fi exemplificată printr-un exemplu simplu:

?- X is 1+1.

în cazul acesta rezultatul operaţiei de adunare nu este cunoscut înainte ca

expresia din dreapta lui "is" să fie evaluată. Variabila X este deci iniţial doar

un loc rezervat pentru o valoare care va deveni disponibilă după evaluarea

expresiei 1 + 1. Dacă considerăm un alt exemplu:

?- X = 1+1.

vom observa că într-o variabilă X, se pot păstra nu numai numere întregi dar

şi structuri de date. În acest caz particular semnul "=" este un atom special

care desemnează egalitatea termenilor, de data aceasta 1 + 1 nu va mai fi

considerată expresie şi nu va mai fi evaluată, X va fi unificat cu o structură de

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 31/183

tipul 1 + 1. Aşa cum am văzut în exemplele din secţiunea anterioară valorile

stocate în variabile pot fi recuperate în cadrul aceleiaşi interogări sau clauze,

în exteriorul lor valorile se pierd, chiar dacă numele variabilelor sunt aceleaşi.Aceasta ţine de mecanismul de unificare Prolog, care face ca variabilele din

cadrul altor clauze să fie legate de alte locaţii de memorie.

?- X = 1+2, Y is X.

În acest exemplu X este instanţiată cu termenul 1 + 2 si în interogarea care

urmează se recuperează din X expresia care va fi evaluată, în Y găsindu-se

valoarea rezultată în urma evaluării, şi anume 3.

Un alt tip de variabile sunt variabilele anonime, acestea sunt desemnate de

semnul "_" ( numai semnul acesta este o variabilă anonimă, _abc va fi con-

siderată o variabilă obişnuită ) şi valorile conţinute de ele nu sunt relevante.

Aceste variabile nu vor fi legate de valorile conţinute, şi o valoare a unei astfel

de variabile nu va putea fi accesată deoarece deşi reprezentarea este aceeaşi,

linuţa de subliniere, fiecare variabilă anonimă va desemna o altă zonă de me-

morie, astfel printr-un predicat de genul write(_). nu vom primi rezultatul

aşteptat.

Un concept important în PROLOG este acela de pattern sau model. De fie-

care dată când se întâlneşte o variabilă va căuta în baza de fapte şi reguli o

substituţie pentru care predicatul ce conţine variabila poate fi demonstrat prin

deducţie logică. Dacă acest lucru nu este posibil sistemul va întoarce "No." ca

răspuns. Să considerăm următorul exemplu:

Exemplul 0.2.2.

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 32/183

cuvant(buna).

cuvant(ziua).

fraza(A, B) :- cuvant(A), cuvant(B).

salut(A, B) :- fraza(A, B), A = buna.

Programul defineşte două fapte (cuvant(buna). şi cuvant(ziua).) şi două pat-

ternuri(fraza(. . . ) şi salut(. . . )). Întâlnind variabilele A şi B compilatorul

va încerca să găsească o substituţie care să satisfacă patternul sau modelul

din dreapta semnului ":-" ( poate fi interpretat ca fiind if-ul din programareastructurată ) , pentru acest caz particular avem substituţiile:

A=buna, B=buna

A=buna, B=ziua

A=ziua, B=ziua

A=ziua, B=buna

Pentru salut(A,B) însă vom avea o listă de substituţii mai scurtă deoarece

avem o condiţionare în plus (A=buna) care reduce lista substituţiilor care

îndeplinesc patternul ( modelul ) impus. Pentru a obţine totuşi o frază de

salut am putea adăuga încă o condiţionare şi anume B=ziua.

A=buna, B=buna

A=ziua, B=ziua

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 33/183

Pentru a ilustra modul de utilizare a variabilelor anonime considerăm progra-

mul precedent cu unele modificari. În cadrul predicatului fraza am adăugat

predicatul prieten(_). Acest predicat se va apela pentru toate predicatele dinbaza de fapte însă valorile din baza de fapte nu vor fi reţinute în variabila _.

Pentru a proba aceasta încercaţi să folosiţi write(_) şi urmăriţi răspunsul din

partea sistemului.

Exemplul 0.2.3.

Fişierul L2ex1.pl conţine programul de mai jos, tastaţi [l2ex1]. în linia de

comandă SWI-Prolog pentru a compila fişierul:cuvant(buna).

cuvant(ziua).

prieten(andrei).

prieten(alin).

prieten(alex).

fraza(A, B) :- cuvant(A), cuvant(B), prieten(_).

salut(A, B) :- fraza(A, B), A = buna , B=ziua.Substituţiile valide pentru exemplul de mai sus sunt în numar de 3 pentru A

şi B vom avea de fiecare dată A=buna, B=ziua iar _ va avea pe rând valorile

andrei, alin, alex.

0.2.1.3 Comanda trace

La fel ca oricare alt mediu de programare SWI-Prolog oferă posibilitatea de a

urmări execuţia programului. Pentru a urmări un program relativ simplu, tot

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 34/183

ce trebuie să faceţi este să tastaţi trace. Când veţi apela următorul predicat

pentru care doriţi un răspuns Prolog-ul va genera o listă de apeluri de forma:

Exit: (9) putere(ferrari, 500) ? creepCall: (9) put_min(gicu, _L204) ? creep

Exit: (9) put_min(gicu, 300) ? creep

Pentru a trece mai departe la apelul următor se apasă tasta Enter sau Spaţiu,

cuvântul "creep" apare automat pentru a marca trecerea la apelul curent.

Se poate urmări însă şi execuţia unui singur predicat prin apelul

trace(NumePredicat ). , de asemenea se poate urmări predicatul res-

pectiv numai pentru anumite acţiuni (call, redo, exit, fail). De exemplutrace(salut,+fail). va afişa numai Fail-urile pentru predicatul salut . O co-

mandă de genul trace(salut). este echivalentă cu trace(salut,+all). Putem opri

trace-ul prin comanda trace(salut,-all). Evident trace(salut,-call). sau oricare

altă opţiune va opri trace-ul pentru acea opţiune. Dacă la un moment dat

dorim să întrerupem trace-ul definitiv după ce am executat programul vom

folosi predicatul nodebug.

SWI-Prolog pune la dispoziţie şi un trace în mod grafic, acesta se activeazăprin predicatul guitracer., iar la următorul apel al lui trace pentru un predicat

se va deschide fereastra din figura 1. După cum se poate observa fereastra este

împărţită în 3 zone: în dreapta sus avem lista de apeluri, în stânga sus sunt

enumerate variabilele şi valorile de care sunt legate, iar jos se poate urmări

locaţia în sursă care generează apelul curent. Predicatul noguitracer. opreşte

trace-ul grafic.

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 35/183

Figura 1: Fereastra pentru trace în mod grafic

0.2.1.4 Predicatele read/write

O altă abordare eficientă pentru a afla ce se întamplă este aceea de a folosi

predicatele din SWI-Prolog write(<mesaj>). şi nl. Predicatul write va face

să apară în fereastra SWI-Prolog mesajul <mesaj>, iar nl. va trece pe linie

nouă.

Exemplul 0.2.4.

Considerăm programul de mai jos, implementat în fişierul L2ex2.pl

ingredient(zahar).

ingredient(faina).

cauta_ingredient(X):-

write(’Caut: ’),

write(X),

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 36/183

nl,

ingredient(X),

write(am_gasit(X)),nl.

Apel: ?- cauta_ingredient(zah).

Caut: zah

?- cauta_ingredient(zahar).

Caut: zahar

am_gasit(zahar)Yes

Desigur în timpul execuţiei unor programe dorim să citim variabile de la tas-

tatură. SWI-Prolog pune la dispoziţie predicatul-sistem read(<variabila>).

Exemplul 0.2.5.

Programul de mai jos exemplifică modul de funcţionare al predicatului read .

Implementarea se găseşte în fişierul L2ex3.pl .Program:

start:-

write(’Introduceti o valoare: ’),

read(X),nl,

write(’Ati introdus: ’),

write(X).

Apel: ?- start.

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 37/183

Introduceti o valoare: e345sd.

Ati introdus e345sd

YesComentariile în SWI- Prolog se fac în stilul C-ului /* comentariu */ sau co-

mentarii pe un singur rând, care încep cu %, iar tot ce urmează pe linia res-

pectivă va fi ignorat. Comentariile sunt utile întotdeauna într-un cod sursă,

o convenţie unanim acceptată este aceea de a pune comentarii înaintea unui

predicat SWI-Prolog pentru a-l explica.

0.2.1.5 Modul de funcţionare SWI-Prolog -Backtrackingul

În acest paragraf urmărim să arătăm modul de funcţionare al SWI-Prolog,

felul în care răspunde interogărilor utilizatorului , deci felul în care rulează un

program. Dându-i-se o interogare Prolog-ul caută în lista sa de fapte şi reguli

(de sus în jos) căutând în antetul faptelor şi regulilor pe acelea care se potrivesc

interogării (având date un set de variabile legate), atunci când găseşte un fapt

sau o regulă care se potriveşte reţine locul unde a ajuns în căutarea sa pentruca apoi să revină în cazul în care regula se dovedeşte a fi imposibil de rezolvat

prin deducţie. Să presupunem că avem următoarele fapte:

Exemplul 0.2.6.

Programul de mai jos se găseşte în fisierul L2ex4.pl .

pasare(tip(canar), nume(tweety)).

pasare(tip(pinguin), nume(tux)).

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 38/183

pasare(tip(pinguin), nume(bambi)).

Pentru o interogare de forma ?- pasare(tip(pinguin), nume(X)). Prolog-ul va

încerca primul fapt din lista de fapte însă va întoarce fail deoarece tipul păsăriieste canar şi nu pinguin. Va trece mai departe şi va încerca să potrivească cel

de-al doilea fapt şi atunci vom obţine X=tux. Totuşi va păstra un pointer

pentru locaţia în care a ajuns pentru ca mai apoi să poată reveni în cazul

în care o interogare sau un subscop va întoace fail sau utilizatorul va cere

un alt răspuns din partea sistemului apăsând ";". Atunci se va încerca să se

resatisfacă predicatul pasare pentru X=bambi.

Să considerăm acum un alt exemplu, avem baza de fapte/reguli de mai jos:

Exemplul 0.2.7.

Programul de mai jos se găseşte în fisierul L2ex5.pl .

animal(leo).

animal(spike).

animal(tweety).

animal(daffy).are_pene(tweety).

are_pene(daffy).

domestic(daffy).

pasare(X):- animal(X), are_pene(X).

pasare_domestica(X):- pasare(X), domestic(X).

Dacă vom adresa interogarea ?- pasare(P) se caută în baza de reguli şi fapte

până se găseşte predicatul pasare(X) şi variabila P va fi instanţiată ca variabila

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 39/183

X. Se trece apoi la corpul predicatului pasare(X) şi se încearcă rezolvarea

celor 2 predicate, pentru primul predicat animal(X) se va găsi valoarea X=leo.

însă pentru aceasta nu există un fapt are_pene(leo) sau un predicat, astfelse revine la ultimul predicat pentru care s-a încercat să găsească o potrivire (

şi anume animal(X) ). Acţiunile se repetă şi pentru X=spike. Când variabila

predicatului animal(X) va fi identificată cu "tweety" din faptul animal(tweety),

iar pentru predicatul are_pene(X), X va fi identificat cu "tweety" din faptul

are_pene(tweety)., predicatul parare/1 va întoarce "yes" pentru X=tweety.

Dacă tastăm ";" atunci se va căuta o nouă demonstraţie şi anume pentru

X=daffy.Pentru o nouă interogare , ?- pasare_domestica(X). compilatorul SWI-Prolog

va încerca mai întâi să satisfacă predicatul pasare(X), iar pentru X=tweety

va întoarce fail deoarece nu există faptul domestic(tweety)., pentru încă o

încercare X=daffy. domestic(daffy). există şi raspunsul va fi X=daffy.

În exemplul de mai sus am facut backtracking prin o bază de fapte însă de cele

mai multe ori este nevoie de backtracking prin baza de reguli. Să considerăm

exemplul următor:

Exemplul 0.2.8.

Programul de mai jos se găseşte în fisierul L2ex6.pl .

animal(tweety). /* faptul 1 */

are_pene(tweety). /* faptul 2 */

pinguin(edgar). /* faptul 3 */

pinguin(allan). /* faptul 4 */

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 40/183

domestic(allan). /* faptul 5 */

pasare(X):- pinguin(X). /* regula 1 */

pasare(X):- animal(X),are_pene(X). /* regula 2 */pasare_domestica(X):- pasare(X), domestic(X). /* regula 3 */

Fie interogarea pasare(P). , se va apela prima regulă care apelează pinguin(X).

răspunsul va fi X=edgar. apoi se pune în aplicare backtrackingul şi cel de-al

doilea raspuns va fi X=allan. Dacă se încearcă resatisfacera lui penguin(X). nu

mai există clauze pentru acest predicat asfel că se trece mai departe la regula

2 şi se apelează animal(X) şi are_pene(X) vom obţine X=tweety.

0.2.2 Exerciţii propuse

Exerciţiul 0.2.1.

Un om cumpară o maşină dacă îi place şi dacă poate să o ia. Unui om îi place

o maşină dacă are puterea pe care şi-o doreşte. Un om poate să ia o maşină

dacă are destui bani în cont să o cumpere sau dacă fiind căsătorit, soţiei îi

place şi ei maşina şi au împreună bani să o cumpere.

0.2.3 Teme de studiu

Tema 0.2.1.

Utilizaţi comanda trace pentru a urmări execuţia programului de la exerciţiul

propus 0.2.1 .

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 41/183

0.3 Unificarea. Operaţiile aritmetice

0.3.1 Fundamente teoretice0.3.1.1 Unificarea

PROLOG-ul este un limbaj de programare cu trăsături mai puţin obişnuite :

unificarea , backtrackingul şi recursivitatea. Unificarea este partea PROLOG-

ului care se ocupă cu potrivirea patternurilor sau modelelor. Ideea din spatele

acestui concept este simplă . Să presupunem că avem predicatul culoare(X,Y),

de asemenea avem o bază de fapte cu urmatoarea structură:

culoare(masina, gri).

culoare(semafor, verde).

Pentru o interogare de forma ?- culoare(X,Y) variabilele X, şi Y vor deveni

variabile legate, X=masina şi Y=gri, vom avea o potrivire a patternurilor.

Aceasta pentru primul fapt dacă apăsăm ";" atunci X şi Y vor fi legate de

valorile semafor şi verde . Dar dacă am fi avut un pattern de forma culoare(X,

X) atunci o potrivire pentru acest pattern nu ar fi fost posibilă. Potrivirea pat-

ternurilor se face între un scop şi antetul unui fapt sau al unei reguli . Variabi-

lele legate ale scopului sunt verificate cu cele din antetul regulii . Alte exemple:

Dacă avem predicatul carte(titlu(X),autor(nume(Nume), prenume(Pren))) la

apelul lui pentru clauza de mai jos:

carte(titlu(teoria_numerelor), autor(nume(georgescu), prenume(ionel))).

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 42/183

vom avea următoarele variabile legate:

X = teoria_numerelor

Nume = georgescuPren = ionel

PROLOG-ul examinează expresiile într-o manieră pur structurală, fără a face

o evaluare a lor. Următoarele expresii sunt tratate în mod similar, în aceste

cazuri semnul "=" înseamnă "au o structură identică".

?- 1 + 2 = 3

?- X + 2 = 3Y .

Totuşi următoarele afirmaţii sunt corecte deoarece au o structură asemănăn-

toare. În aceste cazuri se va produce unificarea variabilelor cu valorile respec-

tive.

?- X + Y = 1 + 2.

X = 1

Y = 2

?- 1 + Y = X + 3.

X = 1

Y = 3

Atomii diferiţi nu pot fi potriviţi astfel pentru o interogare de forma an-

drei=alin. raspunsul primit va fi în toate situaţiile No.

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 43/183

0.3.1.2 Operaţii aritmetice

Funcţiile matematice din SWI-Prolog nu întorc valori ci sunt evaluate cu o

valoare corespunzătoare. Predicatele din SWI-Prolog nu pot fi asemănate cu

funcţiile din programarea structurată sau OOP, ele nu întorc valori ! Dacă se

doreşte să se obţină anumite valori în urma apelului unui predicat atunci se

vor adăuga variabile în plus listei de parametri a acelui predicat, aceste varia-

bile vor fi unificate cu valorile care se doresc a fi obţinute înainte de ieşirea

din apelul predicatului. Aceasta se poate realiza prin scrierea unui pattern al

predicatului în care numele variabilelor care conţin valorile este scris pe poziţia

variabilelor libere adăugate, astfel variabilele libere vor fi unificate cu valorile.

Această adăugare trebuie însă facută cu grijă deoarece modificările trebuie fa-

cute la nivelul întregului program.

sin(X) sinus asin(X) arcsin

cos(X) cosinus acos(X) arccos

tan(X) tangenta atan(X) arctg

Tabela 1: Funcţii trigonometrice disponibile în SWI-Prolog

Evaluarea expresiilor matematice în SWI-Prolog se face prin intermediul ope-

ratorului is .

?- X is 5+4.

X=9

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 44/183

abs(X) modulul lui X

round(X) rotunjire

exp(X) evaluează e la puterea X

float(X) întoarce un float

sign(X) întoarce 1 pentru X pozitiv

real(X) întoarce un număr real

ceiling(X) primul întreg mai mare ca X

integer(X) întoarce un număr întreg

floor(X) primul întreg mai mic ca X

ln(X),log(X),log10(X) evaluează log din X

sqrt(X) radical din X

Tabela 2: Funcţii matematice disponibile în SWI-Prolog

?-X is 5 ∗ 4, Y is 2^3.

X=20

Y=8?-X is 234556^100.

Error 0:Arithmetic Overflow

0.3.2 Exemple

Exemplul 0.3.1.

Calculaţi aria şi lungimea unui cerc de raza R. Rezolvarea în fişierul L3ex1.pl

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 45/183

+ adunare /\ şi logic pe biţi

- scădere \/ sau logic pe biţi

* înmulţire « deplasare la stânga pe biţi

/ împărtire » deplasare la dreapta pe biţi

// împărtire întreagă \ complementul pe biţi

^ ridicare la putere xor sau exclusiv pe biţi

Tabela 3: Predicatele aritmetice in SWI-Prolog

Apel:

?-aria.

Dati raza unui cerc = 1.

Aria cercului este 3.14

Lungimea cercului este 6.28

Program:

aria:- write(’Dati raza unui cerc = ’),

read(R),nl,

write(’Aria cercului este ’),

A is 3.14*R*R,

write(A),nl,

write(’Lungimea cercului este ’),

L is 2*3.14*R,

write(L),nl.

Exemplul 0.3.2.

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 46/183

Verificaţi dacă 3 numere sunt laturile unui triunghi. Rezolvarea în fişierul

L3ex2.pl

Apel:

?- introdu.

introdu a= 3.

introdu b= 4.

introdu c= 5.

Aceste numere sunt laturile unui triunghi

Program:

introdu:-write(’introdu a= ’),read(A),

write(’introdu b= ’),read(B),

write(’introdu c= ’),read(C),

A>=0,B>=0,C>=0,A<(B+C),B<(C+A),C<(A+B),

write(’Aceste numere sunt laturile unui triunghi ’),nl.

Exemplul 0.3.3.

Calculaţi media aritmetică a 2 numere. Rezolvarea în fişierul L3ex3.pl

Apel:

?-start1.

HELLO

X=4.

Y=6.

R=5.

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 47/183

yes

Program:

scrie1:- write(’HELLO’),nl.medie:- write(’X=’),read(X),write(’Y=’),read(Y),

R is (X+Y)/2,write(’R=’),write(R).

start1:- scrie1,medie,nl.

Exemplul 0.3.4.

Scrieţi un program SWI-Prolog care rezolvă ecuaţia de gradul 2. Rezolvarea

în fişierul L3ex4.plApel:

?- rezolva(1,4,-3).

x1 = 0.645751

x2 = -4.64575

Program:

rezolva(A, B, C) :-

Delta is B*B-4*A*C, % calculez deltacaz(A, B, Delta), nl.

caz(_, _, Delta) :-

Delta < 0,

write("Nu are solutii reale"), !.

caz(A, B, Delta) :-

Delta is 0,

X is (-B)/(2*A),

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 48/183

write(’x1=x2= ’),write(X), !.

caz(A, B, Delta) :-

SqrtDelta=sqrt(Delta),X1 is ((-B) + SqrtDelta)/(2*A),

X2 is ((-B) - SqrtDelta)/(2*A),

write(’x1 = ’),write(X1),nl,

write(’x2 = ’),write(X2).

0.3.3 Exerciţii propuse

Exerciţiul 0.3.1.

Scrieţi un predicat care calculează media geometrică a două numere intro-

duse de la tastatură. Rezultatul va fi scris pe ecran.

0.3.4 Teme de studiu

Tema 0.3.1.

Urmăriţi cu trace programele prezentate pentru a înţelege modul în care

se evaluează expresiile aritmetice.

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 49/183

0.4 Recursivitate. Predicatele !(cut) şi fail

0.4.1 Fundamente teoretice0.4.1.1 Recursivitatea

Recursivitatea este o tehnică des întâlnită în mediile Prolog. Acest termen,

recursivitate , înseamnă că un predicat este definit de mai multe ori şi se

auto-apelează. Iată un exemplu simplu de recursivitate:

strabun(Bunic,Nepot) :-

parinte(Bunic,Nepot).

strabun(Bunic,Nepot) :-

parinte(Bunic,Tata),

strabun(Tata,Nepot).

Toate definiţiile recursive trebuie să conţină cel puţin 2 clauze clauza de

bază şi clauza recursivă. În clauza de bază trebuie să ne asigurăm că există

o condiţie de oprire şi că există cel puţin o soluţie în cadrul recursivităţii.

Clauza recursivă este cea care reapelează predicatul, observaţi faptul că

parinte/2 se apelează înainte ca predicatul strabun/2 să se auto-apeleze.

Dacă vom modifica programul de mai sus şi îl vom pune sub forma următoare

(implementarea în fişierul L4ex1.pl):

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 50/183

parinte(emilia,maria).

parinte(ion,maria).

parinte(maria,petre).strabun(Bunic,Nepot) :-

strabun(Tata,Nepot),

parinte(Bunic,Tata).

strabun(Bunic,Nepot) :-

parinte(Bunic,Nepot).

vom observa că ordinea în care se face apelul predicatelor este importantă

deoarece deşi definiţia programului este logic corectă acesta pentru interogarea?- strabun(X,petre). nu va ajunge la o soluţie.

0.4.1.2 Predicatele !(cut) şi fail

Cut

Cut este un predicat predefinit notat prin "!" în SWI-Prolog, totdeauna

adevărat şi care acţionează asupra motorului de inferenţe. Cu ajutorul luieste posibil să controlăm modul în care lucrează backtrackingul. Folosirea

acestui predicat într-o clauză are următoarele efecte:

1. Poate să forţeze eşecul unei clauze, deoarece după apelul lui clauzele care

îl succed nu se vor mai executa.

2. Poate limita numărul de soluţii prin reducerea arborelui de inferenţă, în

acelaşi timp fiind posibilă oprirea căutării de soluţii pe unele ramuri în cazul

în care programatorul ştie că pe ramurile respective nu sunt soluţii.

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 51/183

Exemplul de mai jos prezintă funcţionarea unui program fără predicatul cut.

De observat este faptul că în predicatul test , prima clauză apelează predicatul

conditie , el se va apela pentru fiecare din cele 3 clauze. Observaţi ce seîntâmplă în momentul în care adăugăm "!" în predicatul test după apelul

predicatului conditie . Implementarea acestor predicate se găseste în fişierul

L4ex2.pl

Apel:

?- start.

unu

doitrei

clauza doi predicatul test

Program:

conditie(unu).

conditie(doi).

conditie(trei).test(X) :-

conditie(X).

test(’clauza doi predicatul test’).

start:-

test(X), write(X), nl, fail.

Modificăm programul de mai sus astfel:

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 52/183

test_cut(X) :-

conditie(X),!. test_cut(’clauza doi test’).

start_cut:- test_cut(X), write(X), nl, fail.Rezultatul va fi următorul:

?- start_cut.

unu

Modificăm exemplul de mai sus astfel:

test_cut2(X,Y,Z,K) :-

conditie(X),conditie(Y),!,conditie(Z),conditie(K).test_cut2(’clauza doi test’).

start_cut2:- test_cut2(X,Y,Z,K), write(X - Y - Z - K), nl, fail.

În această ultimă modificare se observă cel mai bine rolul pe care îl are

cut. Deoarece este plasat după al doilea apel al predicatului conditie nu se

va mai încerca resatisfacerea primelor predicate conditie şi pentru celelalte

valori(respectiv "doi" şi "trei"). Altfel spus nu se va încerca resatisfacerea

predicatele conditie(X) si conditie(Y) pentru alte valori decât cele de "unu".Rezultatul este următorul:

?- start_cut2.

unu-unu-unu-unu

unu-unu-unu-doi

unu-unu-unu-trei

unu-unu-doi-unu

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 53/183

unu-unu-doi-doi

unu-unu-doi-trei

unu-unu-trei-unuunu-unu-trei-doi

unu-unu-trei-trei

Considerăm în continuare o altă implementare pentru a exemplifica predicatul

cut . Predicatele de mai jos se găsesc implementate în fişierul L4ex3.pl

Apel:

?- este_in_forma(X,Y).X = andrei

Y = nesatisfacatoare;

Program:

este_in_forma(Sportiv, nesatisfacatoare) :-

max_flotari(Sportiv,P),

P < 15,!.este_in_forma(Sportiv, satisfacatoare).

max_flotari(ionel,20).

max_flotari(andrei,12).

max_flotari(daniel,25).

max_flotari(alin,10).

Cut-ul din prima clauză inseamnă "dacă ai ajuns până aici atunci renunţă să

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 54/183

mai cauţi alte soluţii".

Cut-ul este o metodă des utilizată însă în acest caz distruge citirea logică a

clauzelor care îl conţin. Spre exemplu clauza de mai sus ar putea fi interpre-tată "Nu este în formă sportivul care nu poate face mai mult de 15 flotări"

însă cut-ul înlocuieşte negaţia şi foţează încheierea execuţiei programului.

Observaţi că deşi mai sunt soluţii în baza de fapte pentru interogare primim

răspunsul No.

Fail

Când un subscop al unui predicat întoarce "fail" PROLOG încearcă prinbacktracking să resatisfacă toate subscopurile acelui predicat. Este acelaşi

lucru cu a apăsa ";" atunci când dorim să obţinem un nou rezultat pentru o

problemă , dacă el există. Există un predicat (fail) predefinit, care întoarce

fail în orice ocazie, cauzând astfel backtrakingul. Iată un exemplu de utilizare

a predicatului fail/0 (nu are argumente).Exemplul este implementat în fişierul

L4ex4.pl

Apel:?- plante(_).

cartof

cires

garoafa

ficus

Yes

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 55/183

Program:

planta(cartof).

planta(cires).planta(garoafa).

planta(ficus).

plante(X):- planta(X),write(X),nl,fail.

plante(_).

Predicatul plante(X) din programul de mai sus, datorită subscopului fail, va

întoarce el însuşi fail, astfel se va încerca resatisfacerea sa pentru alte valori ale

variabilei X. Când nu mai există astfel de valori a doua clauză a predicatuluieste încercată, aceasta fiind un fapt ce are ca parametru o variabilă anonimă

va întoarce Yes .

Un exemplu interesant este următoarea bucată de cod, în care folosind o

combinaţie cut/fail putem înlocui cu succes negaţia.

nuestecopil(X, Y) :- copil(X, Y), !, fail.

nuestecopil(X, Y).

Este acelaşi lucru cu nuestecopil(X, Y) :- not(copil(X, Y)). deoarece în

cazul în care copil (X,Y) întoarce "Yes" cut opreşte backtrackingul, iar fail

întoarce "No", facând asfel ca nuestecopil(X, Y) să întoarcă imediat "No". În

cazul în care copil(X,Y) întoarce "No" atunci nuestecopil(X,Y) va întoarce

"Yes" pentru a 2-a clauză.

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 56/183

0.4.2 Exemple

Exemplul 0.4.1.

0.4.2.1 Funcţia factorial

Scrieţi un program Prolog care calculează funcţia factorial pentru un n dat.

Implementare în fişierul L4ex5.pl

Pentru a calcula factorialul unui număr ştim următoarele lucruri:

1 0! = 1 şi 1! = 1

2 n! = n(n − 1)!

Aşa cum am spus mai sus recursivitatea se realizează prin mai multe clauze

ale aceluiaşi predicat, astfel condiţiile de mai sus se pot traduce astfel:

1 condiţia de oprire şi în acelaşi timp o valoare cunoscută pentru funcţia fac-

torial

2 este condiţia de recursie

Apel:

?-fact(3,R).

R=6

Yes

Program:

fact(0,1).

fact(N,R):-fact(N1,R1),N is N1+1,R is R1N.

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 57/183

Rezolvarea prezentată se numeşte "calculul factorialului pe retur", deoarece

valoarea lui R (defapt valoarea lui N factorial)va fi calculată la revenirea din

apelurile succesive pentru resatisfacerea lui fact(N1,R1). Să urmărim execuţiaprogramului de mai sus cu trace pentru a observa mai bine modul de lucru al

SWI-Prolog.

?- trace,fact(3,R). <- apelul predicatului

Call: (9) fact(3, _G461) ? creep <- nu se intra pe prima ramură fact(0,1)

deoarece nu se potriveşte antetul predicatelor (avem apel pentru fact(3,R)),

acesta este apelul pentru fact(N,R)

Call: (10) fact(_L215, _L216) ? creep <- apel fact(N1,R1)Exit: (10) fact(0, 1) ? creep <- unificare cu fact(0,1)

^Call: (10) 3 is 0+1 ? creep <- verifică dacă N is 0+1, adică _L215+1

^Fail: (10) 3 is 0+1 ? creep <- fail

Redo: (10) fact(_L215, _L216) ? creep <- se încearcă resatisfacerea lui

fact(N1,R1) pentru alte valori

Call: (11) fact(_L234, _L235) ? creep <- se reapelează predicatul fact pentru

alte variabile care nu sunt legateExit: (11) fact(0, 1) ? creep <- unificare cu fact(0,1)

^Call: (11) _L215 is 0+1 ? creep <- variabilele din primul set vor lua alte

valori

^Exit: (11) 1 is 0+1 ? creep

^Call: (11) _L216 is 1*1 ? creep

^Exit: (11) 1 is 1*1 ? creep

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 58/183

Exit: (10) fact(1, 1) ? creep <- se iese din apelul de la (10) adăugându-se

fact(1,1) la baza de fapte şi se verifică din nou dacă N is N1+1

^Call: (10) 3 is 1+1 ? creep^Fail: (10) 3 is 1+1 ? creep

Redo: (11) fact(_L234, _L235) ? creep <- se încearcă din nou satisfacerea lui

fact(N1,R1) însă pentru un al treilea set de variabile

Call: (12) fact(_L246, _L247) ? creep <- din nou unificare cu fact(0,1)

Exit: (12) fact(0, 1) ? creep <- unificarea variabilelor din setul 3 cu valorile 0

şi respectiv 1

^Call: (12) _L234 is 0+1 ? creep <- variabilele din setul 2 vor lua alte valori1 şi respectiv 1

^Exit: (12) 1 is 0+1 ? creep

^Call: (12) _L235 is 1*1 ? creep

^Exit: (12) 1 is 1*1 ? creep

Exit: (11) fact(1, 1) ? creep <- se revine din Redo pentru pasul (11) şi varia-

bilele din setul 1 ia valorile 2 şi respectiv 2

^Call: (11) _L215 is 1+1 ? creep^Exit: (11) 2 is 1+1 ? creep

^Call: (11) _L216 is 1*2 ? creep

^Exit: (11) 2 is 1*2 ? creep

Exit: (10) fact(2, 2) ? creep <- la revenirea la pasul(10) N va fi N1+1 şi se

trece mai departe şi se calculează rezultatul final.

^Call: (10) 3 is 2+1 ? creep

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 59/183

^Exit: (10) 3 is 2+1 ? creep

^Call: (10) _G461 is 2*3 ? creep

^Exit: (10) 6 is 2*3 ? creepExit: (9) fact(3, 6) ? creep <- iesire din apel

R = 6

Yes

Exemplul 0.4.2.

Factorial calculat pe tur:

Apel: ?- fact2(4,R).R = 24

Yes

Program:

fact2(N,N,R,R).

fact2(N,N1,R1,R):- N2 is N1+1, R2 is R1*N2 , fact2(N,N2,R2,R).

fact2(N,R):- fact2(N,1,1,R).

Apelul se face asemănător primului program , din fact2(N,R) apelăm pefact2(N,N1,R1,R) , N1 fiind un N intermediar pentru a şti când să ne oprim,

iar R1 este un rezultat intermediar care atunci când se va ajunge la N1 = N

va fi unificat cu R prin faptul fact2(N,N,R,R). care este şi condiţia de oprire

pentru obţinerea rezultatului final. Să urmărim trace-ul pentru acest program:

?- trace,fact2(4,R). <- apel

Call: (8) fact2(4, _G283) ? creep <- predicatul care apelează pe

fact2(N,N1,R1,R)

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 60/183

Call: (9) fact2(4, 1, 1, _G283) ? creep <- apel fact2(N,N1,R1,R)

^Call: (10) _L196 is 1+1 ? creep <- calcul N1

^Exit: (10) 2 is 1+1 ? creep <- ieşire calcul N1^Call: (10) _L197 is 1*2 ? creep <- calcul R1

^Exit: (10) 2 is 1*2 ? creep <- ieşire calcul R1

Call: (10) fact2(4, 2, 2, _G283) ? creep <- se reapelează pentru noile valori

^Call: (11) _L217 is 2+1 ? creep <- calcul N1

^Exit: (11) 3 is 2+1 ? creep <- ieşire calcul N1

^Call: (11) _L218 is 2*3 ? creep <- calcul R1

^Exit: (11) 6 is 2*3 ? creep <- ieşire calcul R1Call: (11) fact2(4, 3, 6, _G283) ? creep <- se reapelează factorial

^Call: (12) _L238 is 3+1 ? creep <- calculul valorilor intermediare

^Exit: (12) 4 is 3+1 ? creep

^Call: (12) _L239 is 6*4 ? creep

^Exit: (12) 24 is 6*4 ? creep

Call: (12) fact2(4, 4, 24, _G283) ? creep

Exit: (12) fact2(4, 4, 24, 24) ? creep <- ieşire din factorialExit: (11) fact2(4, 3, 6, 24) ? creep

Exit: (10) fact2(4, 2, 2, 24) ? creep <- observaţi că valorile lui R intermediar

se pierd

Exit: (9) fact2(4, 1, 1, 24) ? creep

Exit: (8) fact2(4, 24) ? creep

R = 24

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 61/183

Yes

Exemplul 0.4.3.

0.4.2.2 Cmmdc şi Cmmmc

Scrieţi un program Prolog care calculează cmmdc şi cmmmc pentru două

numere X şi Y. Implementarea se găseşte în fişierul L4ex6.pl

Prezentăm algoritmul lui Euclid pentru cel mai mare divizor comun (cmmdc)

şi cel mai mic multiplu comun (cmmmc).

Apel:

?- cmmdc(6,15,X).

X=3

?-cmmmc(6,7,Y).

Y=42

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 62/183

Program:

cmmdc(X,0,X).

cmmdc(X,Y,D):- R is X mod Y, cmmdc(Y,R,D).cmmmc(X,Y,M):- cmmdc(X,Y,D),M is (XY)/D.

Programul defineşte cmmdc(X,Y,D) ca fiind clauza recursivă, în interiorul ei

vom calcula restul conform algoritmului lui Euclid şi vom reapela cmmdc

pentru Y,R şi o a 3-a variabilă D, iar cmmdc(X,0,X) este clauza de oprire

a recursivităţii, la final când această clauză este apelată, variabilele de pe

prima şi ultima poziţie vor fi unificate şi vom obţine cmmdc.

?- trace,cmmdc(14,8,R). <- apel cmdcCall: (9) cmmdc(14, 8, G492) ? creep <- intră pe clauza 2

^Call: (10) L218 is 14 mod 8 ? creep <- se calculează R

^Exit: (10) 6 is 14 mod 8 ? creep

Call: (10) cmmdc(8, 6, G492) ? creep <- se reapealează cmmdc pentru alte

valori

^Call: (11) L237 is 8 mod 6 ? creep <- calculează din nou R

^Exit: (11) 2 is 8 mod 6 ? creepCall: (11) cmmdc(6, 2, G492) ? creep <- se reapealează cmmdc pentru alte

valori

^Call: (12) L256 is 6 mod 2 ? creep <- calculează din nou R

^Exit: (12) 0 is 6 mod 2 ? creep

Call: (12) cmmdc(2, 0, G492) ? creep <- de data aceasta se intră pe clauza

cmmdc(X,0,X)

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 63/183

Exit: (12) cmmdc(2, 0, 2) ? creep <- pe poziţia secundă vom avea tot X şi se

revine din calcul

Exit: (11) cmmdc(6, 2, 2) ? creepExit: (10) cmmdc(8, 6, 2) ? creep

Exit: (9) cmmdc(14, 8, 2) ? creep

R = 2

Yes

Exemplul 0.4.4.

0.4.2.3 N la puterea K

Scrieţi un program prolog care calculează N la puterea K. Implementarea în

fişierul L4ex7.pl

Apel:

?-puterea(2,3,R).

R=8

Program:

puterea(N,K,R,K,R).

puterea(N,K,R,K1,Rez):- K2 is K1+1, R1 is N*R ,puterea(N,K,R1,K2,Rez).

puterea(N,K,R):-puterea(N,K,1,0,R).

Rezolvarea de mai sus este un exemplu "de calcul pe tur". Ideea din spatele

programului este de a calcula în două variabile K2 şi R1 puterea la care

s-a ajuns şi respectiv rezultatul intermediar.Astfel condiţia de oprire este

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 64/183

puterea(N,K,R,K,R). când se ajunge la puterea K (observaţi cele 2 perechi

de variabile identice , K şi R) acesta este un fapt şi valoarea din prima

variabilă R este unificată cu variabila a doua R. Urmăriţi cu trace modul delucru al acestui program.

0.4.3 Exerciţii propuse

Exerciţiul 0.4.1.

Scrieţi predicatul puterea(N,K,R) care returnează în variabila R pe N la

puterea K, cu calculul puterii pe retur.

0.4.4 Teme de studiu

Tema 0.4.1.

Rulaţi pas cu pas programele prezentate în exemplele de mai sus cât şi pe

cele propuse ca exerciţii.

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 65/183

0.5 Turnurile din Hanoi. Funcţiile Fibonacci şi

Ackermann

0.5.1 Fundamente teoretice

Prezentăm în continuare câteva probleme cunoscute ale programării structu-

rate şi modul în care sunt ele abordate în programarea logică şi mediul SWI-

Prolog.

0.5.2 ExempleExemplul 0.5.1.

0.5.2.1 Turnurile din Hanoi

Exista 3 turnuri , stânga, centru, dreapta, pe cel din stânga se gasesc N discuri

de mărimi diferite suprapuse descrescător de la bază spre vârf. Cum pot fi

mutate cele N discuri de pe turnul din stânga pe cel din dreapta, folosind

turnul din centru, astfel încât să fie îndeplinite următoarele condiţii:

- la fiecare operaţie de mutare se mută un singur disc.

- discurile fiind de dimensiuni diferite, un disc oarecare nu poate fi pus peste

altul mai mic.

La fel ca în cazul funcţiei factorial avem nevoie de un caz de bază şi un caz

general care poate fi exprimat prin operaţii de o complexitate redusă. Pentru

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 66/183

a sublinia faptul că mutăm un disc folosim predicatul muta(A,B) care în-

seamnă mută primul disc de sus de pe turnul A pe turnul B. De fiecare dată

când mutăm un disc acest predicat va afişa mesajul corespunzător prin inter-mediul predicatului write.

Cazul de bază.

Un caz de bază este mutarea unui singur disc de pe turnul A(stânga) pe trunul

B(dreapta) folosind turnul C(centru). Pentru aceasta am putea folosi predi-

catul hanoi(1, A, B, C):- muta(A,B), defapt pe lângă acest caz există un

caz mult mai simplu şi anume acela în care nu mutăm nici un disc , pentru

acesta vom folosi predicatul hanoi(0, _ , _ , _ ):- !.Cazul recursiv

Pentru cazul inductiv trebuie să transferăm N discuri de pe A pe B, presu-

punem că avem deja un program care transferă N-1 discuri . Paşii pe care îi

urmăm sunt următorii :

1. Transferăm primele N-1 discuri de pe A pe C

2. Transferăm ultimul disc de pe A pe B

3. Transferăm N-1 discuri de pe C pe B

În implementare predicatul corespunzător operaţiilor de mai sus este hanoi(N,

A, B, C) Programul este urmatorul: (implementarea în fişierul L4ex7.pl)

start(N) :- hanoi(N, stanga, centru, dreapta).

hanoi(0, _ , _ , _ ):- !.

hanoi(N, A, B, C):- /*mută de pe A pe B folosind C*/

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 67/183

N_1 is N-1,

hanoi(N_1, A, C, B), /*mută de pe A pe C folosind B - pasul 1*/

muta(A, B),/*mută de pe A pe B ultimul disc - pasul 2*/hanoi(N_1, C, B, A). /*mută de pe C pe B folosind A - pasul 3*/

muta(F, T) :- write(muta, F, –>, T), nl.

Apel:

start(3).

Rezultatul va fi următorul:

muta, stanga, (–>), centru

muta, stanga, (–>), dreaptamuta, centru, (–>), dreapta

muta, stanga, (–>), centru

muta, dreapta, (–>), stanga

muta, dreapta, (–>), centru

muta, stanga, (–>), centru

0.5.2.2 Modul de funcţionare al programului:

Se va apela cu start(N)., unde N este un număr natural. Pentru clauza start

se va apela predicatul hanoi(N, stanga, centru, dreapta). care apelează primul

predicat hanoi întâlnit, nu va intra pe ramura hanoi(0,_,_,_) deoarece pat-

ternurile nu sunt identice, şi anume N este diferit de 0 şi celelalte variabile nu

sunt libere, merge mai departe la următoarea clauză, aici va decrementa pe N

până la 0 , va intra pe clauza hanoi(0,_,_,_) unde va face cut, iar pe recursie

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 68/183

va afişa modul de aranjare a discurilor.

Exemplul 0.5.2.

0.5.2.3 Şirul lui Fibonacci

Să se definească un predicat care pentru un N dat să calculeze termenul de

rang n din şirul lui Fibonacci. Implementarea se găseşte în fişierul L5ex1.pl

Indicaţii:

Un termen din şirul lui Fibonacci se calculează conform relaţiei de recurenţă

în 2 paşi:

- f(1)= f(2)= 1

- f(n)= f(n-2) + f(n-1), daca n>=3

Şirul lui Fibonacci arată astfel:

- 1, 1, 2, 3, 5, 8, 13, 21, 34, 55...

Apel:?-fib(6,R).

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 69/183

Program:

fib(1,1).

fib(2,1).fib(N,R):- N>=3,N1 is N-1,N2 is N-2,

fib(N1,R1),fib(N2,R2),R is R1+R2.

Exemplul 0.5.3.

0.5.2.4 Funcţia Ackermann

Funcţia Ackermann este definită recursiv pentru numere întregi pozitive. Esteo funcţie ale cărei valori cresc foarte repede devenind atât de mari încât este

imposibil să fie calculate. De fapt, se spune că scrierea lor sub formă zecimală

nu poate fi stocată în tot universul fizic. Ca un exemplu A(4,2) este mai mare

decât numărul tutror particulelor din univers ridicate la puterea 200. Funcţia

a fost decoperită în 1928 de Wilhelm Ackermann (1896 - 1962) sub o altă formă

şi este un exemplu de funcţie recursivă care nu este însă o funcţie primitiv-

recursivă (exemple de funcţii primitiv-recursive: funcţia constantă egală cu 0,funcţia succesor). Este utilă în special la testarea compilatoarelor pentru a

verifica puterea de recursie a acestora. Spre exemplu dacă un compilator este

capabil să salveze valori ale lui A(2,n) şi A(3,n) pentru a calcula pe ... să

spunem A(3,30) atunci el va reduce numărul computaţiilor cu un factor de

ordinul sutelor de mii.

Există şi o inversă a funcţiei Ackermann care spre deosebire de aceasta

creşte foarte încet, defapt maximul ei este o valoare mai mică decât 5 pentru

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 70/183

m/n 0 1 2 3 4

0 1 2 3 4 5

1 2 3 4 5 6

2 3 5 7 9 11

3 5 13 29 61 125

4 13 65533 265536 − 3 A(3,A(4,2)) A(3,A(4,3))

5 65533 A(4,65533) A(4,A(5,1)) A(4,A(5,2)) A(4,A(5,3))

6 A(5,1) A(5,A(5,1)) A(5,A(6,1)) A(5,A(6,2)) A(5,A(6,3))

Tabela 4: Câteva valori ale funcţiei Ackermann

orice valori de intrare posibile. Trebuie reţinut faptul că aceasta nu este inversa

funcţiei Ackermann în sensul strict matematic.

Definiţie formală:

f (m, n) = min{i?1 : A(i,floor(m/n)) > log2n}

unde A(i,j) este funcţia Ackermann.Definiţia funţiei Ackermann:

Ack(0,n) = n+1

Ack(m,0) = Ack(m-1,1) pentru m >0

Ack(m,n) = Ack(m-1,Ack(m,n-1)) pentru m,n>0

Apel:

?- ack(3,5,R).

R = 253

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 71/183

m n ack(m,n) A(m,n) în general

0 1 2 n+1

1 1 3 n+2

1 2 4

2 1 5 2n+3

2 2 7

2 3 9

3 2 29 8 × 2n − 3

3 3 61

3 4 stack overflow

Tabela 5: Valorile funcţiei Ackerman calculate în SWI-Prolog

?- ack(3,6,R).

ERROR: Out of local stack

?- ack(4,5,R).

ERROR: Out of local stack

Programul:

ack(0,M,R):-R is M+1,!.

ack(N,0,R):-R1 is N-1,ack(R1,1,R).

ack(N,M,R):-N1 is N-1,M1 is M-1,ack(N,M1,R1),ack(N1,R1,R).

0.5.3 Exerciţii propuse

Exerciţiul 0.5.1.

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 72/183

Scrieţi predicatul PROLOG fib(N,R) care returnează în variabila R termenul

N din şirul lui Fibonacci şi care calculează acest termen pe tur.

Exerciţiul 0.5.2.

Scrieţi predicatul PROLOG ackermann(N,M,R) care returnează în varia-

bila R rezultatul funcţiei Ackermann, calculat pe tur.

0.5.4 Teme de studiu

Tema 0.5.1.

Studiaţi cu trace. evoluţia programelor prezentate cât şi a celor de la

"Exerciţii propuse".

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 73/183

0.6 Liste

0.6.1 Fundamente teoreticeListele în mediile Prolog sunt o secvenţă ordonată de termeni, conceptual nu

există prea multe asemănări între listele din PROLOG şi şirurile din C. Iată

câteva exemple de liste:

[] - lista vidă

[a,c,s,f,d,h,q,p] - listă cu 8 elemente

[carne, lapte, legume, fructe] - listă cu 4 elemente

[pornit(motor), arde(benzina), conduc(masina)] - lista cu 3 elemente (

cele 3 elemente termeni )

[1,a,[1,c,f,2],[nume(carte),1,a,floare]] - exemplu de listă în listă, cu ele-

mente diferite, care sunt însă atomi.

Deoarece listele sunt structuri ordonate de termeni lista [1,a,b] va fi diferită de[a,1,b].

0.6.1.1 Accesarea elementelor din listă

Accesul la elementele din listă se produce secvenţial, adică pentru a ajunge

la elementul N din listă trebuie să eliminăm din listă primele N-1 elemente.

Am spus "eliminăm" deoarece odată accesat un element din listă nu va mai

aparţine de lista respectivă. Scoatem un element din listă în felul urmator

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 74/183

[Element|Coada], elementul Element va fi unul din atomii listei , iar Coada va

fi restul listei care poate fi procesată în continuare.

Extragerea unui element

?- [Element|Coada]=[mere,prune,caise,cirese].

Element = mere

Coada = [prune, caise, cirese]

Introducerea unui element

?- L=[1,2],R=[a,b,c|L].L = [1, 2]

R = [a, b, c, 1, 2]

0.6.2 Exemple

Exemplul 0.6.1.

Scrieţi în ordine inversă elementele unei liste. Implementarea se găseşte înfişierul L6ex1.pl

Apel:

?-scrie([a,b,c]).

c b a

Yes

Program:

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 75/183

scrie([]).

scrie([X|R]):-scrie(R),write(X),write(’ ’).

Programul funcţionează pe baza recursiei. Predicatul scrie împarte lista în capşi coadă în antetul clauzei sale şi se reapelează pentru coada listei,R. Prima

clauză a acestui predicat este un fapt ce va întoarce Yes atunci când lista va

fi vidă. În acel moment se va reveni din apelurile succesive ale predicatului şi

pe întoarcere vor fi scrise elementele X extrase din listă.

Exemplul 0.6.2.

Verificaţi dacă o listă are un numar par de elemente. Implementarea se găseşte

în fişierul L6ex2.pl

Apel:

?-par([a,b,c,d]).

Yes

Program:

par([_,_]).

par([_,_|T]):-par(T).

Predicatul par/1 este un predicat recursiv, se scot câte 2 elemente din listă

în două variabile anonime, deoarece nu ne interesează elementele conţinute de

listă. La final, dacă vor rămâne 2 elemente care pot fi scoase din listă atunci

în lista există un număr par de elemente, altfel predicatul va returna Fail .

Exemplul 0.6.3.

Scrieţi un predicat care returnează numărul de elemente dintr-o listă. Imple-

mentarea se găseşte în fişierul L6ex3.pl

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 76/183

Exista şi predicatul sistem(built-in): length(Lista,Nr). care întoarce în Nr

numărul elementelor din listă.

Apel:

?-lungime([a,b,[c,d],e],R).

R=4

?-length([a,b,[c,d],e],R).

R=4

Program:

lungime([],0).

lungime([_|T],R):-lungime(T,R1),R is R1+1.Ştim ca în lista vidă sunt 0 elemente, extragem câte un element din listă şi

reapelăm predicatul pentru coada listei şi la revenirea din apelurile succesive

numărăm elementele.

Exemplul 0.6.4.

Verificaţi dacă un element aparţine unei liste. Implementarea se găseşte în

fişierul L6ex4.plApel:

?-member(b,[a,v,b,c]).

Yes

?-member(a,[b,c,g]).

Program:

member(X,[X|_]).

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 77/183

member(X,[_|T]):-member(X,T).

Predicatul member este tot un exemplu de predicat recursiv. Această definiţie

poate fi asemănată cu un if din programarea structurată. În antetul predi-catului se extrage din listă un element, dacă elementul extras este X, atunci

predicatul întoarce Yes. Altfel vor fi scoase elemente din listă până când în

cele din urmă lista va fi vidă si memeber/2 va întoarce Fail .

Exemplul 0.6.5.

Verificaţi dacă o listă este sau nu mulţime. O listă care este considerată mul-

ţime conţine elemente care nu se reptă. Implementarea se găseşte în fişierulL6ex5.pl

Apel:

?-set([a,b,c,c,d]).

set([a,b,c]).

Yes

Program:set([]).

set([X|T]):-not(member(X,T)),set(T).

Şi acest predicat este unul recursiv. Se extrag elemente din listă şi se verifică

dacă elementul extras este membru pentru coada listei. Ne oprim atunci când

lista este vidă, caz în care lista este o mulţime, deoarece toate elementele au

fost extrase şi niciunul nu a fost membru în coada listei. Dacă un element ar

fi fost membru în restul listei atunci predicatul member negat prin not ar fi

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 78/183

întors fail şi am fi primit răspunsul No.

Exemplul 0.6.6.

Scrieţi un predicat care face înmulţirea a 2 vectori. Implementarea se găseşte

în fişierul L6ex6.pl

Apel:

?-prodv([1,2,4],[3,2,3],R).

R=[3,4,12]

Yes

Program:prodv([X],[Y],[R]):-R is X*Y.

prodv([H|T],[H1|T1],[R|R1]):-

prodv(T,T1,R1),

R is H*H1.

Gestionăm 3 liste, 2 din ele reprezintă coordonatele vectorilor iar în ultima

avem rezultatul, scoatem elemente din primele 2 liste până cand vom rămâne

cu un singur element în fiecare , atunci ultima coordonată a vectorului rezultateste X*Y şi pe întoarcere calculăm celelalte componente.

Exemplul 0.6.7.

Scrieţi un predicat care găseşte ultimul element al unei liste. Implementarea

se găseşte în fişierul L6ex7.pl

Apel:

?- last([a],R)

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 79/183

R=a

?-last([a,b,1,c],X).

X=c?-last([a,b,[c,[d]]],X).

X=[c,[d]]

Program:

last([X],X).

last([H|T],R):-last(T,R).

Scoatem elemente din listă până cand în listă vom avea un singur element pe

care îl unificăm cu variabila liberă X.

Exemplul 0.6.8.

Să verificăm dacă o mulţime intră în toate mulţimile unei liste de mulţimi.

Implementarea se găseşte în fişierul L6ex8.pl

Apel:

?-inclus([a,b],[1,a,c,b]).

Yes?-inclus([],[a,b]).

Yes

?-inclus_multimi([a,b,c],[[a,b,c,d],[m,a,b,c]])

Yes

Program:

inclus([],L).

inclus([H|T],L):- member(H,L),inclus(T,L).

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 80/183

Orice mulţime include mulţimea vidă: dacă lista este vidă întoarce lista L.

Împart lista în cap şi coadă şi dacă primul element este în L merg mai departe

şi apelez recursiv predicatul pentru restul listei şi L .inclus_multimi(X,[Y]):- inclus(X,Y).

inclus_multimi(X,[H|T]):- inclus(X,H), inclus_multimi(X,T).

Împart lista de mulţimi în cap şi coadă, coada fiind restul de mulţimi din listă.

Apelez funcţia inclus pentru a vedea dacă X este inclusă în prima listă din

lista de mulţimi, apelez recursiv inclus_multimi pentru a vedea dacă X este

inclusă în restul de mulţimi din listă.

Exemplul 0.6.9.

Incrementaţi toate elementele unei liste. Programul se găseşte implementat în

fişierul L7ex1.pl

Apel:

?-increment (inc,[1,2,3],R).

R=[2,3,4]

Yes

Program:

inc(X,Y):-Y is X+1.

increment(F,[],[]).

increment(F,[H|T],[R|RT]):- L=..[F,H,R],call(L),increment(F,T,RT).

Programul foloseşte lista L pentru a aduna parametrii necesari pentru

predicatul built-in call() care formează un nou scop, în cazul de faţă apelează

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 81/183

incrementarea fiecărui element. Apelul are ca parametri predicatul inc , cel

care va incrementa elementele listei , lista şi variabila care va întoarce lista

rezultat.

Exemplul 0.6.10.

Scrieţi un program care înlocuieşte un element într-o listă. Implementarea se

găseşte în fişierul L7ex2.pl

Apel:

?- subst(a,b,[b,b,c,[d,b]],R).

R=[a,a,c,[d,b]]No

Program:

subst(N,V,[],[]):-!.

subst(N,V,[V|T],[N|R]):-subst(N,V,T,R),!.

subst(N,V,[X|T],[X|R]):-subst(N,V,T,R).

Programul substituie un element la nivelul superficial al listei, observaţi că

pentru lista [d,b] , b-ul din această listă nu este înlocuit. Programul estestructurat pe cazuri şi anume , cazul în care din listă poate fi extras elementul V

( cel ce va fi înlocuit ) şi cazul în care se extrage din listă un element oarecare.

În primul caz se face cut pentru a nu se încerca resatisfacerea predicatului

subst pentru alte clauze, dacă acest lucru s-ar întâmpla în lista R nu vom

avea elementele substituite. Pe întoarcere se reconstruieşte lista însă în lista

R ( rezultat ) vom avea lista modificată deoarece atunci când se poate extrage

elementul V în R introducem elementul N (elementul cu care înlocuim V-ul).

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 82/183

Exemplul 0.6.11.

Scrieţi un predicat care şterge toate apariţiile unui element într-o listă (nivel

superficial). Implementarea se găseşte în fişierul L7ex4.pl

Apel:

?-sterge(a,[a,c,[a,b],a,f],R).

R=[c,[a,b],f]

Program:

sterge(X,[],[]).

sterge(X,[X|T],R):-sterge(X,T,R),!.

sterge(X,[Y|T],[Y|R]):- sterge(X,T,R).

Programul funcţionează pe acelaşi principiu ca programul care înlocuieşte ele-

mente din listă, însă de data aceasta în locul elementelor extrase nu se va

adăuga un alt element.

Exemplul 0.6.12.

Scrieţi un predicat care şterge toate elementele dintr-o listă dată care apar în

altă listă. Implementarea se găseşte în fişierul L7ex5.plApel:

?-stergere([1,2,3],[1,4,2,5,3,7],R).

R=[4,5,7]

Program:

stergere([],L1,L1).

stergere([H|T],L1,L3):-sterge(H,L1,R2),stergere(T,R2,L3). Predicatul ster-

gere/3 are nevoie ca înainte de a fi apelat să se încarce fişierul de la exemplul

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 83/183

precedent (consult(l4ex4).). Principiul de funcţionare este foarte simplu, în

antetul predicatului extragem un element din prima listă pentru care apelăm

predicatul sterge/3 de mai sus. Elementul extras din prima listă va fi şters dina doua listă şi predicatul stergere/3 se reapelează pentru coada primei liste

lista R2 rezultată în urma ştergerii şi o listă L3 care va fi lista ce va conţine

rezultatul final.

Exemplul 0.6.13.

Scrieţi un predicat care inserează un element înaintea unui alt element al unei

liste. Mai jos sunt prezentate două variante de predicat ins/3 şi ins2/3, primulpredicat ins/3 inserează pe X înaintea lui A în lista L, numai la prima apariţie a

lui A, ins2/3 afişează toate posibilităţile de inserare, pentru o listă care conţine

mai multe apariţii ale lui A. Implementarea se găseşte în fişierul L7ex6.pl

Apel:

?- ins(x,b,[d,b,c,b],L).

L=[d,x,b,c,b]

Program:ins(X,A,[],[]).

ins(X,A,[A|T],[X,A|T]):- !.

ins(X,A,[H|T],[H|R]):- ins(X,A,T,R).

Apel:

?- ins2(x,c,[a,c,d],R).

R=[a,x,c,d]

?- ins2(x,c,[a,c,d,c],R).

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 84/183

R=[a,x,c,d,c];

R=[a,c,d,x,c]

YesProgram:

ins2(X,A,L,R):- append(L1,[A|L2],L),append(L1,[X,A|L2],R).

Exemplul 0.6.14.

Implementaţi o serie de predicate care primesc ca parametru o listă şi care

trebuie să simuleze o stivă FIFO, FILO, LIFO, LILO. Implementarea se găseşte

în fişierul L7ex3.plFIFO (First In First Out) - primul intrat , primul ieşit.

?-pop([a,b,c],R).

R=a

?-push(m,[a,b,c],R).

R=[m,a,b,c]

pop([H|T],H).

push(X,L,[X|L]).FILO (First In Last Out) - primul intrat, ultimul ieşit.

?-pop1([a,b,c],R).

R=c

?-push1(m,[a,b,c],R).

R=[m,a,b,c]

pop1([X],X).

pop1([H|T],R):-pop1(T,R).

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 85/183

push1(X,L,[X|L]).

LIFO (Last In First Out) - ultimul intrat , primul iesit.

?-pop2([a,b,c],R).R=a

?-push2(m,[a,b,c],E).

R=[a,b,c,m]

pop2([H|T],H).

push2(X,L,R):-append(L,[X],R).

LILO (Last In Last Out) - ultimul intrat, ultimul ieşit.

?-pop3([a,b,c],R).R=c

?-push3(m,[a,b,c],E).

R=[a,b,c,m]

pop3([X],X).

pop3([H|T],R):-pop1(T,R).

push3(X,L,R):-append(L,[X],R).

Exemplul 0.6.15.

Scrieţi un predicat care selectează dintr-o listă numerele întregi (numai de pe

nivelul superficial al listei). Implementarea în fişierul L8ex1.pl

Apel:

?-select([1,a,3],R).

R=[1,3]

?-select([1,[a,2],3],R).

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 86/183

R=[1,3]

Program:

select([],[]).select([H|T],[H|R]):-integer(H),select(T,R).

select([H|T],R):-select(T,R).

Programul funcţionează asemănător unui if din programarea structurată.

Scoate un element H din listă şi dacă este întreg îl adugă la lista rezultat

şi se reapeleză , altfel dacă interger(H) întoarce fail atunci se încearcă satis-

facerea celei de-a treia clauze, care scoate elementul din listă. Ne oprim când

lista va fi vidă.

Exemplul 0.6.16.

Scrieţi un program care numără câte vocale sunt într-o listă. Implementarea

în fişierul L8ex2.pl

Apel:

?- nr_vocale([a,s],X).

X=1?- nr_vocale([a,r,e,d,i],X).

X=3

?- nr_vocale([s,d],X).

X=0

Program:

member(X,[X|_]).

member(X[_|T]):-member(X,T).

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 87/183

vocala(X):-member(X,[a,e,i,o,u]).

nr_vocale([],0).

nr_vocale([X|T],N):-vocala(X),nr_vocale(T,N1),N is N1+1,!.nr_vocale([X|T],N):-nr_vocale(T,N).

Încă un exemplu de predicat recursiv. Predicatul este structurat pe 2 cazuri

simple, dacă litera este sau nu vocală. Dacă este, atunci se reapelează pentru

restul listei şi o variabilă liberă N1, care atunci când lista va fi vidă va fi

unificată cu 0, la revenirea din apeluri se vor număra vocalele. Dacă litera

nu este vocală predicatul se reaprelază pentru restul listei. Cazul de bază este

prima clauză a predicatului, care semnifică faptul că în lista vidă sunt 0 vocale.

Exemplul 0.6.17.

Selectaţi dintr-o listă primele şi ultimele N elemente. Implementarea se găseşte

în fişierul L8ex3.pl

Ultimul element dintr-o listă:

?- ultimul([1,2,3,4],R).

R=4last(L,R):- append(X,[R],L).

Primul element dintr-o listă:

?- primul([1,2,3,4],R).

R = 1

primul(L,R):- append([R],X,L).

Se observă modul în care predicatul-sistem append/3 răspunde interogărilor.

Se poate construi foarte uşor un predicat care să întoarcă primele şi ultimele

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 88/183

N elemente.

Apel:

?- prim([1,2,3,4,5,6],3,R).R = [1, 2, 3]

Yes

4 ?- ultim([1,2,3,4,5,6],3,R).

R = [4, 5, 6]

Yes

Program:

ultim(L,N,R):- append(X,R,L),length(R,N).prim(L,N,R):- append(R,X,L),length(R,N).

Predicatul sistem append/3 fiind apelat cu primele variabile nelegate va încerca

toate posibilităţile pentru care din R şi X se obţine lista L, aceea care va avea

lungimea N va fi lista care ne interesează. Remarcaţi că lista rezultat R, se

află pe poziţii diferite în funcţie de fiecare apel append.

Exemplul 0.6.18.

Scrieţi un predicat care simulează o listă circulară. Implementarea se găseşte

în fişierul L8ex4.pl

Apel:

?- circular([a,b,c,d],R).

R=[a,b,c,d]

R=[b,c,d,a]

R=[c,d,a,b]

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 89/183

R=[d,a,b,c]

Program:

circ(_,[],_).

circ([H|T],[_|Rest],R):- concat(T,[H],R),write(R),nl,circ(R,Rest,R1).

circular(L,R):-circ(L,L,R).

Luăm lista [a,b,c,d] şi punem primul element a la coadă. Lista rezultat R

(R=[b,c,d,a]) va intra din nou în buclă şi din nou punem primul element la

coadă. Când ştim să ne oprim? Introducem încă o variabilă pe care o iniţia-

lizăm cu lista [a,b,c,d]. De fiecare dată când obţinem o lista circulară nouăscoatem din L=[_|Rest] un element şi continuăm cu Rest. În momentul în

care lista va fi vidă ne oprim.

Exemplul 0.6.19.

Scrieţi un predicat care sortează crescător o listă de numere întregi. Imple-

mentarea în fişierul L8ex5.pl

Apel:?- sort_ins([13,2,6,1,5,9,7],R).

R = [1, 2, 5, 6, 7, 9, 13]

Yes

Program:

sort_ins(List,Sort):-i_sort(List,[],Sort).

i_sort([],A,A).

i_sort([H|T],A,Sort):-insert(H,A,NA),i_sort(T,NA,Sort).

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 90/183

insert(X,[Y|T],[Y|NT]):-X>Y,insert(X,T,NT).

insert(X,[Y|T],[X,Y|T]):-X=<Y.

insert(X,[],[X]).

Exemplul 0.6.20.

Scrieţi un predicat care permută o listă folosind ştergerea din listă. Prezentăm

mai întâi predicatele de ştergere utilizate pentru a permuta lista. Implemen-

tarea în fişierul L8ex6.pl

Apel:

?-sterge(a,[a,c,[a,b],f],R).R=[c,[a,b],f]

?-sterge(X,[a,b,c],R).

X=a

R=[b,c]

X=b

R=[a,c]

X=cR=[a,b]

Predicat:

sterge(X,[X|T],T).

sterge(X,[Y|T],[Y|R]):-sterge(X,T,R).

Predicatul de mai sus şterge un element dintr-o listă.

Apel:

?-sterge_lista([1,2,3],[1,4,2,5,3,7],R).

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 91/183

R=[4,5,7].

Predicat

sterge_lista([],L1,L1).sterge_lista([H|T],L1,L3):-sterge(H,L1,L2),sterge_lista(T,L2,L3).

Predicatul de mai sus şterge elementele unei liste dintr-o listă, folosind şterge-

rea unui singur element dintr-o listă.

?-permutare([a,b,c],L).

L = [[a, b, c], [a, c, b], [b, a, c], [b, c, a], [c, a, b], [c, b, a]]

Predicat:

permutare(L,R):- findall(X,sterge_lista(X,L,[]),R).Predicatul sistem findall/3 găseşte toate soluţiile predicatului sterge_lista/3

pe care le va returna în variabila R. Rezultatele intermediare vor fi obţinute

în variabila X.

Exemplul 0.6.21.

Scrieţi un predicat care afişează toate permutările unei liste folosind adăugă-

rile în listă.(scoate pe rând fiecare element şi îl adaugă în dreptul fiecărui altelement). Implementarea în fişierul L8ex7.pl

Apel:

?- permutari([1,2],R).

R=[[1,2],[2,1]]

Predicate folosite:

?-adaug(a,[b,c,d],X).

X=[a,b,c,d]

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 92/183

X=[b,a,c,d]

X=[b,c,a,d]

X=[b,c,d,a]?-permut([a,b,c],X).

X=[a,b,c]

X=[b,a,c]

X=[b,c,a]

X=[a,c,b]

X=[c,a,b]

X=[c,b,a]Program:

adaug(X,L,[X|L]).

adaug(X,[L|H],[L|R]):-adaug(X,H,R).

permut([],[]).

permut([L|H],R):-permut(H,R1),adaug(L,R1,R).

permutari(L,R):- findall(P,permut(L,P),R).

Exemplul 0.6.22.

Scrieţi un predicat care găseşte toate combinările unei mulţimi luate câte K.

Implementarea în fişierul L8ex8.pl

Apel:

?- combinari([a,b,c],2,R).

R=[[a,b],[a,c],[b,c]]

?- adauga(a,[[b],[c]],I).

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 93/183

I=[[a,b],[a,c]]

Program:

combinari(L,N,[L]):-length(L,N),!.

combinari(L,1,R):- pune_paranteze(L,R).

combinari([H|T],K,R):-

K1 is K-1,

combinari(T,K1,R1),

adauga(H,R1,R2),

combinari(T,K,R3),concat(R2,R3,R).

adauga(X,[L],[[X|L]]).

adauga(X,[H|T],[[X|H]|R]):-adauga(X,T,R).

pune_paranteze([],[]).

pune_paranteze([H|T],[[H]|R]):-

pune_paranteze(T,R).

Exemplul 0.6.23.

Scrieţi un predicat SWI-Prolog care "împachetează" elemente consecutive iden-

tice dintr-o listă. Implementarea în fişierul L9ex1.pl

Apel:

?- impacheteaza([a,a,a,a,b,c,c,a,a,d,e,e,e,e],X).

X = [[a,a,a,a],[b],[c,c],[a,a],[d],[e,e,e,e]]

Program:

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 94/183

transfer(A, [], [], [A]).

transfer(A, [B|C], [B|C], [A]) :-

A\=B.transfer(A, [A|B], C, [A|D]) :-

transfer(A, B, C, D).

impacheteaza([], []).

impacheteaza([A|B], [C|D]) :-

transfer(A, B, E, C),

impacheteaza(E, D).

Predicatul împachetează elementele din lista B formând o listă, D, cu aceleaşielemente însă conţinute în subliste ale lui D. Predicatul transfer/4 este folosit

pentru a scoate elementele identice din lista B şi a depune rezultatul în lista

D care va fi lista rezultat. La încheierea acestei operaţii predicatul impache-

teaza/2 se reapelează pentru restul listei. Ne vom opri când ambele liste vor

fi goale, lista procesată şi lista rezultat, deoarece dacă prima listă a devenit

vidă şi lista rezultat va fi vidă, la revenirea din apeluri lista rezultat va con-

ţine sublistele cu elemente identice, care au fost introduse în antetul clauzeiimpacheteaza([A|B], [C|D]).

Exemplul 0.6.24.

Având programul de mai sus scrieţi un program care codifică o listă ast-

fel: pentru termeni consecutivi , identici vom avea o listă de liste de forma

[[N,X],[M,Y]] unde N şi M sunt numărul de apariţii ale lui X, respectiv Y.

Implementarea în fişierul L9ex2.pl

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 95/183

Predicatul ensure_loaded( fisier ) asigură faptul că fişierul fisier a fost încărcat.

El trebuie apelat înainte de a compila L9ex2.pl

?- ensure_loaded(L9ex1).Yes

Apel:

?- codifica[a,a,a,a,b,c,c,a,a,d,e,e,e,e],X).

X = [[4,a],[1,b],[2,c],[2,a],[1,d][4,e]]

Program:

codifica(L1,L2) :- impacheteaza(L1,L), transform(L,L2).

transform([],[]).transform([[X|Xs]|Ys],[[N,X]|Zs]) :-

length([X|Xs],N), transform(Ys,Zs).

Exemplul 0.6.25.

Având exemplul de mai sus , scrieţi un predicat SWI-Prolog care decodifică

listele obţinute cu programul din exemplul precedent. Implementarea în fişierul

L9ex3.plApel:

?- decodifica([[4,a],[1,b],[2,c],[2,e]],R).

R = [a, a, a, a, b, c, c, e, e]

Program:

decodifica([],[]).

decodifica([X|Ys],[X|Zs]) :-

is_list(X), decodifica(Ys,Zs).

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 96/183

decodifica([[1,X]|Ys],[X|Zs]) :- decodifica(Ys,Zs).

decodifica([[N,X]|Ys],[X|Zs]) :-

N > 1, N1 is N - 1,decodifica([[N1,X]|Ys],Zs).

Exemplul 0.6.26.

Scrieţi un predicat care întoarce o listă L2 obţinută din lista L1 prin adăugarea

la L2 a elementelor dintre indecşii I şi K. Implementarea în fişierul L9ex4.pl

Apel:

trunc([a,b,c,d,e,f,g,h,i,k],3,7,L).

L = [c,d,e,f,g]

Program:

trunc([X|_],1,1,[X]).

trunc([X|Xs],1,K,[X|Ys]) :-

K > 1,

K1 is K - 1,

trunc(Xs,1,K1,Ys).

trunc([_|Xs],I,K,Ys) :- I > 1,

I1 is I - 1,

K1 is K - 1,

trunc(Xs,I1,K1,Ys).

Exemplul 0.6.27.

Scrieţi un predicat SWI-Prolog care şterge toate elementele din N în N dintr-o

listă. Implementarea în fişierul L9ex5.pl

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 97/183

Apel:

?- sterge([a,b,c,d,e,f,g,h,i,k],3,R).

R = [a,b,d,e,g,h,k]Program:

sterge([],_,[],_).

sterge([_|Xs],N,Ys,1) :-

sterge(Xs,N,Ys,N).

sterge([X|Xs],N,[X|Ys],K) :-

K > 1, K1 is K - 1,

sterge(Xs,N,Ys,K1).

Exemplul 0.6.28.

Scrieţi un predicat SWI-Prolog care simulează o loterie. Şi anume se extrag N

numere în din intervalul 1..M care vor fi introduse într-o listă L. Implementarea

în fişierul L9ex5.pl

Apel:

?- extrage(5,20,L).L = [2, 15, 4, 7, 9]

În exemplul de mai sus N=5, M=20.

Program:

sterge(X,[X|Xs],1,Xs).

sterge(X,[Y|Xs],K,[Y|Ys]) :-

K > 1, K1 is K - 1,

sterge(X,Xs,K1,Ys).

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 98/183

select(_,0,[]).

select(Xs,N,[X|Zs]) :- N > 0,

length(Xs,L),I is random(L) + 1,

sterge(X,Xs,I,Ys),

N1 is N - 1,

select(Ys,N1,Zs).

interval(I,I,[I]).

interval(I,K,[I|L]) :-

I < K, I1 is I + 1,interval(I1,K,L).

extrage(N,M,L) :-

interval(1,M,R),

select(R,N,L).

0.6.3 Exerciţii propuse

Exerciţiul 0.6.1.

Scrieţi un predicat SWI-Prolog care simulează pe liste reuniunea, intersecţia

şi diferenţa pentru mulţimi.

Exerciţiul 0.6.2.

Scrieţi un predicat SWI-Prolog care caută o listă intr-o listă de liste.

Exerciţiul 0.6.3.

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 99/183

Scrieţi un predicat SWI-Prolog care afişează intersecţia a două liste care conţin

alte liste.

Exerciţiul 0.6.4.

Scrieţi un program care afişează reuniunea a două liste de liste.

0.6.4 Teme de studiu

Tema 0.6.1.

Rulaţi cu trace exemplele prezentate.

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 100/183

0.7 Grafuri. Arbori

0.7.1 Fundamente teoretice

0.7.1.1 Probleme de reprezentare

Reprezentarea datelor joacă un rol important în programare, în general o formă

de reprezentare sau alta poate uşura munca unui programator. De aceea ca

mod de reprezentare a muchiilor unui graf alegem forma de mai jos a clauzelor,

care credem că este cea mai potrivită pentru problemele prezentate în acest

material.- muchie(A,B). - prin aceasta simbolizăm faptul că există muchie de la A la B.

Reprezentarea de mai sus este suficientă pentru grafurile orientate. Dacă se

doreşte adăugarea de costuri pentru muchii aceasta se poate face prin adău-

garea la predicatul muchie a unei variabile care să reprezinte costul traversării

muchiei de la A la B.

Dorim în continuare pentru grafurile neorientate să avem un predicat care să

reprezinte faptul că muchiile sunt neorientate sau că se poate circula în ambelesensuri. Pentru aceasta am putea adopta o construcţie de forma:

- muchie(A,B):- muchie(B,A). în felul acesta programul va intra într-un ciclu

infinit.

O soluţie la problemă ar putea fi crearea de fapte de tipul muchie(a,b). şi

muchie(b,a). însă în felul acesta dublăm numărul predicatelor, iar pentru un

graf de dimensiuni considerabile efortul tastarii programului este prea mare

(această abordare poate fi o soluţie pentru reprezentarea grafurilor orientate).

100

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 101/183

Vom folosi predicatul următor pentru rezolvarea acestei probleme.

legatura(X,Y) :- muchie(X,Y) ; muchie(Y,X).

Semnul ";" reprezintă o disjuncţie ( sau logic ). Predicatul de mai sus ar fi

putut fi scris şi sub forma:

legatura(X,Y):- muchie(X,Y).

legatura(X,Y):- muchie(Y,X).

Pentru reprezentarea arborilor vom folosi acelaşi predicat muchie(a,b).

şi legatura(X,Y).

0.7.2 Exemple

Exemplul 0.7.1.

Considerăm graful de mai jos, scrieţi un program SWI-Prolog care găseşte

toate drumurile între oricare 2 vârfuri ale grafului. Implementarea în fişierul

L10ex1.pl.

101

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 102/183

Apel:

drum(1,5,R).

R = [1, 3, 5] ;R = [1, 3, 6, 5] ;

R = [1, 3, 2, 8, 4, 5] ;

R = [1, 7, 5] ;

R = [1, 6, 5] ;

R = [1, 6, 3, 5] ;

R = [1, 6, 3, 2, 8, 4, 5] ;

NoProgram:

muchie(1,3). muchie(1,7). muchie(1,6).

muchie(2,3). muchie(2,8).

muchie(3,5). muchie(3,6).

muchie(4,5). muchie(4,8).

muchie(5,6). muchie(5,7).

legatura(X,Y) :-muchie(X,Y) ; muchie(Y,X).

drum(A,B,Drum) :-

mergi(A,B,[A],L),

reverse(L,Drum).

mergi(A,B,P,[B|P]) :-

legatura(A,B).

102

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 103/183

mergi(A,B,V,Drum) :-

legatura(A,C),

C \== B,not(member(C,V)),

mergi(C,B,[C|V],Drum).

Exemplul 0.7.2.

Având programul de mai sus scrieţi un predicat SWI-Prolog care găseşte un

drum închis plecând dintr-un vârf dat. Programul trebuie să returneze toate

drumurile prin backtracking. Implementarea în fişierul L10ex2.pl

Apel:

?- ciclu(1,Drum).

Drum = [1, 7, 5, 3, 1] ;

Drum = [1, 7, 5, 6, 3, 1] ;

Drum = [1, 7, 5, 4, 8, 2, 3, 1] ;

. . .

Program:

ciclu(A,P) :-

legatura(B,A),

drum(A,B,P1),

length(P1,L),

L > 2,

append(P1,[A],P).

Exemplul 0.7.3.

103

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 104/183

Având graful de mai sus şi reprezentarea lui în SWI-Prolog scrieţi un pre-

dicat care calculează gradul unui nod. Implementarea în fişierul L10ex3.pl

Apel:

?- grad(1,R).

R = 3

Yes

Predicat:

grad(Nod,R):- findall(X,muchie(Nod,X),L),length(L,R).

Pentru acest predicat folosim reprezentarea grafului din figura de mai sus şi

predicatele built-in findall/3 şi length/2 . Predicatul findall/3 va găsi toatemuchiile care există de la Nod la X si va întoarce în lista L veciniii lui Nod .

Predicatul length/2 returnează lungimea unei liste în cel de-al doilea parame-

tru care trebuie să fie o variabilă liberă la apel, dacă este o variabilă legată şi

primul parametru este liber atunci va crea o listă aleatoare cu număr egal de

elemente cu valoarea celuilalt parametru.

Exemplul 0.7.4.

Scrieţi un predicat SWI-Prolog care întoarce într-o listă toate nodurile unui

graf şi lungimea listei. Implementarea în fişierul L10ex3.pl

Apel:

varfuri(R,N).

R = [1, 2, 3, 4, 5, 6, 7, 8]

N = 8

Yes

104

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 105/183

Predicat:

varfuri(R,N):-

findall(X,(muchie(X,_); muchie(_,X)),L),sort(L,R),length(R,N).

Predicatul built-in sort/2, după cum îi spune şi numele, sortează lista L şi

întoarce rezultatul în variabila R.

0.7.3 Exerciţii propuse

Exerciţiul 0.7.1.

Modificaţi primul program prezentat (drum în graf) pentru a afla fluxul

maxim dintre 2 noduri (A şi B) ale grafului. Fluxul maxim este valoarea

minimă a muchiilor grafului pe care le parcurgem pentru a ajunge din punctul

A în B.

0.7.4 Teme de studiu

Tema 0.7.1.

Scrieţi un program SWI-Prolog care parcurge un arbore.

105

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 106/183

0.8 Probleme speciale

0.8.1 Problema Damelor

Aceasta este o problemă clasică în programarea calculatoarelor, după cum se

ştie trebuie să plasăm pe o tablă de şah, de dimensiune N×N, N dame astfel

încât să nu se atace reciproc. Două dame se atacă atunci când se găsesc pe

aceeaşi linie, coloană sau diagonală.

Reprezentăm poziţia celor N dame printr-o listă de dimensiune N astfel :

dacă avem lista [4,2,7,3,6,8,5,1] aceasta înseamnă că dama de pe coloana 1se găseşte pe linia 4, dama de pe coloana 2 se găseşte pe linia 2 , ş.a.m.d. .

Folosind acest mod de reprezentare a informaţiilor şi folosind permutări ale

numerelor între 1 şi N ne asigurăm că oricare 2 dame nu se vor găsi pe aceeaşi

linie sau coloană. Singurul test care ne mai rămâne este testul diagonalelor,

astfel o damă plasată pe coloana X şi rândul Y ocupă două diagonale notate

prin C (diagonala secundară) şi D (diagonala principală) acestea vor fi un

număr C=X-Y şi D= X+Y , aceste valori , ale diagonalelor deja ocupate vorfi reţinute în două liste Cs şi Ds.

Apel:

?- dame_1(4,R).

R = [2, 4, 1, 3] ;

R = [3, 1, 4, 2] ;

?- dame_1(8,R).

R = [1, 5, 8, 6, 3, 7, 2, 4] ;

106

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 107/183

R = [1, 6, 8, 3, 7, 4, 2, 5] ;

R = [1, 7, 4, 6, 8, 2, 5, 3] ;

R = [1, 7, 5, 8, 2, 4, 6, 3] ;. . .

Program:

Predicatul dame_1(N,Qs) :- Qs este o soluţie de aşezare a celor N dame.

dame_1(N,Qs) :- intre(1,N,Rs), permuta(Rs,Qs), test(Qs).

Predicatul intre(A,B,L) :- L este o listă de numere între A şi B.

intre(A,A,[A]).

intre(A,B,[A|L]) :- A < B, A1 is A+1, intre(A1,B,L).

Predicatul permuta(Xs,Zs) :- lista Zs este o permutare a listei Xs.

permuta([],[]).

permuta(Qs,[Y|Ys]) :- del(Y,Qs,Rs), permuta(Rs,Ys).

del(X,[X|Xs],Xs).

del(X,[Y|Ys],[Y|Zs]) :- del(X,Ys,Zs).

Predicatul test(Qs) :- Lista Qs reprezintă o soluţie a damelor care nu

se atacă reciproc.

test(Qs) :- test(Qs,1,[],[]).

Predicatul test(Qs,X,Cs,Ds) :- Damele din Qs, reprezentând coloanele

de la X la N, nu sunt în conflict cu diagonalele Cs şi Ds.

107

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 108/183

test([],_,_,_).

test([Y|Ys],X,Cs,Ds) :-

C is X-Y, not(memberchk(C,Cs)),D is X+Y, not(memberchk(D,Ds)),

X1 is X + 1,

test(Ys,X1,[C|Cs],[D|Ds]).

Iată o a doua versine în care permutarea este verificată înainte de a trece mai

departe .

dame_2(N,Qs) :-

intre(1,N,Rs),permuta_test(Rs,Qs,1,[],[]).

permuta_test([],[],_,_,_).

permuta_test(Qs,[Y|Ys],X,Cs,Ds) :-

del(Y,Qs,Rs),

C is X-Y, not(member(C,Cs)),

D is X+Y, not(member(D,Ds)),

X1 is X+1,permuta_test(Rs,Ys,X1,[C|Cs],[D|Ds]).

Programul se găseşte implementat în fişierul L11ex1.pl

0.8.2 Problema mutării calului

Se dă o tablă de sah de dimensiuni N×N, se cere să se mute un cal pe tablă

în asa fel încât la final calul să fi trecut prin toate pătratele tablei.

108

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 109/183

Predicatul cal(N,Cal) :- Cal este o listă ce conţine rezultatul problemei sub

elemente de forma linie/coloană reprezentând poziţiile pe care se poate muta

calul.cal(N,Cal) :- M is N*N-1,cal(N,M,[1/1],Cal),write(Cal).

Predicatul drum_inchis/2 calculează dacă există un drum închis, şi anume

calul trebuie să se întoarcă în acelaşi pătrat din care a pornit.

drum_inchis(N,Cal) :-

cal(N,Cal),

Cal = [X/Y|_],

sare(N,X/Y,1/1).cal(_,0,Cal,Cal).

cal(N,M,Visited,Cal) :-

Visited = [X/Y|_],

sare(N,X/Y,U/V),

not(memberchk(U/V,Visited)),

M1 is M-1,

cal(N,M1,[U/V|Visited],Cal).Predicatul sare/3 specifică modul în care calul poate sări pe tablă de la pătratul

A/B la C/D.

sare(N,A/B,C/D) :-

sare_dist(X,Y),

C is A+X, C > 0, C =< N,

D is B+Y, D > 0, D =< N.

109

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 110/183

Baza de cunoştinţe cu distanţele pe care le poate sări calul.

sare_dist(1,2).

sare_dist(2,1).sare_dist(2,-1).

sare_dist(1,-2).

sare_dist(-1,-2).

sare_dist(-2,-1).

sare_dist(-2,1).

sare_dist(-1,2).

Apel:?- cal(5,R).

Cal=[1/5, 3/4, 5/5, 4/3, 5/1, 3/2, 1/3, 2/5, 4/4, 5/2, 3/1, 1/2, 2/4, 4/5, 5/3,

4/1, 2/2, 1/4, 3/3, 2/1, 4/2, 5/4, 3/5, 2/3, 1/1]

0.8.3 Exerciţii propuse

Exerciţiul 0.8.1.

O firmă de cartografie urmăreşte să coloreze o hartă a N tări cu M culori în

aşa fel încât două ţări vecine să nu fie colorate cu aceeaşi culoare. Scrieţi un

program Prolog care să afişeze toate soluţiile posibile pentru N şi M date.

0.8.4 Teme de studiu

Tema 0.8.1.

110

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 111/183

Rulaţi programele prezentate folosind comanda trace.

111

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 112/183

0.9 Fişiere. Baze de date dinamice

0.9.1 Fundamente teoretice

0.9.1.1 Fişiere

SWI-Prolog dispune de 2 modalităţi de lucru cu fişiere: Stilul Edinburgh care

presupune gestionarea unui stream implicit, predicatele referă în mod implicit

stream-ul curent, şi stilul ISO Input and Output Streams, în care stream-urile

sunt explicite si sunt create cu predicatul open/3 sau open/4. Fiecare stream

astfel creat are un identificator unic folosit de alte predicate pentru a citi sauscrie pe streamul respectiv.

Prezentăm în continuare stilul Edinburgh.

În acest stil, stream-ul este conectat în mod implicit la terminal ( monitor +

tastatură pentru ieşiri respectiv intrări), el poate fi schimbat cu predicatele:

- see(+SrcDest) Deschide SrcDest pentru citire şi îl face stream-ul curent de

intrare.

- tell(+SrcDest) Deschide SrcDest pentru scriere şi îl face să fie stream-ul cu-rent de ieşire.

- append(+File) Similar cu tell/1, dar poziţionează pointerul de scriere la fi-

nalul fişierului.

- seeing(?SrcDest) şi telling(?SrcDest) nu returnează numele fişierului deschis

pentru citire/scriere ci returnează indentificatorul de stream.

- seen şi told închid stream-ul curent.

SrcDest poate fi un fişier, terminalul sau un termen desemnat prin

112

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 113/183

’pipe(Comanda)’. Iată câteva exemple pentru SrcDest:

?- see(f.txt). % citeşte din fişierul ’f.txt’

?- tell(user). % Scrie pe terminal.?- tell(pipe(lpr)). % Scrie la imprimantă

În exemplul de mai sus user şi lpr sunt cuvinte rezervate în SWI-Prolog.

Stilul ISO Input and Output Streams presupune crearea stream-urilor prin in-

termediul predicatului open/3 sau open/4. Identificatorul de stream rezultat

este apoi transmis predicatelor care fac citiri şi scrieri pentru a specifica sursa

sau destinaţia datelor. Predicatele built-in care respectă acest stil/standard

sunt:open(+SrcDest, +Mode, -Stream, +Options) SrcDest specifică una din

opţiunile de mai sus, Mode poate fi read, write, append sau update, Stream

poate fi fie o variabilă care la final va conţine identificatorul de stream fie un

atom şi în cazul acesta atomul va fi identificatorul de stream. Options pate fi

- type(Type) se foloseşte pentru a putea scrie în mod text în mod compatibil

cu sistemul de operare. Dacă se foloseşte tipul binar octeţii vor fi scrişi fără afi traduşi. De menţionat că pe sistemele Unix nu se face diferenţă între modul

text şi binar.

- alias(Atom) dă unui stream un nume. Atenţie la această opţiune deoarece

numele de stream-uri sunt globale. Exemplu:

?- open(data, read, Fd, [alias(input)]). , ...,read(input, Term),...

- eof_action(Action) defineşte ce se întamplă în momentul în care se ajunge

113

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 114/183

la final de fişier.

- buffer(Buffering) defineste posibilitatea de a avea un buffer.

- close_on_abort(Bool) închide stream-ul dacă în timpul execuţiei programu-lui se apelează predicatul abort/0.

- lock(LockingMode) încearcă să blocheze fişierul pentru ca alte procese să nu îl

modifice în timpul executiei programului. În mod implicit fişierul nu va fi blo-

cat , însă locking mode poate fi read sau shared , adică alte procese(programe)

pot accesa fişierul numai pentru citire.

open(+SrcDest, +Mode, ?Stream) este echivalent cu open/4 cu lista de

opţiuni vidă.open_null_stream(?Stream) deschide un stream vid. Toate funcţiile sunt

active pentru un asemenea stream, dar o încercare de a citi de pe un astfel de

stream returnează end_of_file.

close(+Stream) închide stream-ul specificat. Dacă acest stream este stream-

ul curent pentru intrare/ieşire atunci terminalul este făcut stream curent

pentru intrare/ieşire.

set_stream(+Stream, +Attribute) setează stream-ului atributele prezen-tate mai sus la predicatul open.

0.9.1.2 Baze de date dinamice.

Un program este o bază de date deoarece programul oferă posibilitatea intero-

gării "bazei de date" compusă din fapte şi reguli. O astfel de bază de date se

numeşte "statică" deoarece ea nu poate fi modificată în timpul execuţiei pro-

114

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 115/183

gramului. În SWI-Prolog există posibilitatea de a crea baze de date dinamice,

acestea se referă la faptul că la un moment dat putem avea o bază de fapte

creată în timpul execuţiei programului. Spre exemplu în timpul executiei pro-gramului dorim să mai adăugăm la baza de fapte încă o clauză. SWI-Prolog

pune la dispoziţie următoarele predicate-sistem pentru lucrul cu baze de date

dinamice:

- assert(+Term) adaugă un fapt la baza de date ca ultim fapt sau clauză a

predicatului corespunzător.

- asserta(+Term) echivalent cu predicatul de mai sus, dar Term este adăugat

ca primă clauză sau fapt al unui predicat.- assertz(+Clause) echivalent cu assert/1 .

- retract(+Term) atunci când Term este atom sau termen el este unificat cu

primul fapt sau prima clauză din baza de date , iar faptul sau clauza este şters

din baza de date.

- retractall(+Head) toate fapte sau clauzele cu care Head se poate unifica

sunt şterse din baza de date.

- abolish(+PredSpec) şterge toate predicatele specificate de PredSpec, undePredSpec este de forma Predicat/Aritate. Tot ce are legătura cu predicatul

specificat este şters din sistem.

0.9.2 Exemple

Exemplul 0.9.1.

Scrieţi un program care citeşte litere dintr-un fişier(litere.txt), le separă în

115

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 116/183

vocale şi consoane, apoi le scrie în fişiere diferite (vocale.txt şi consoane.txt).

Implementarea în fişierul L12ex1.pl(Atenţie la formatul fişierului! Literele sunt

scrise pe câte un rând urmate de "." doarece SWI-Prolog le consideră fapte.)Apel:

?- start.

Yes

Program:

vocala(’a’).

vocala(’e’).

vocala(’i’).vocala(’o’).

vocala(’u’).

citeste(L):-

read(X),

X \= end_of_file,

append(L,[X],Rez),

citeste(Rez).citeste(L):-

separ(L,Vocale,Consoane),

vocale(Vocale),

consoane(Consoane).

separ([],[],[]).

separ([Litera|R],[Litera|Cons],Voc):-

116

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 117/183

not(vocala(Litera)),

separ(R,Cons,Voc).

separ([Litera|R],Cons,[Litera|T]):-vocala(Litera),

separ(R,Cons,T).

vocale(V):-

tell(’vocale.txt’),scrie(V),told.

consoane(C):-

tell(’consoane.txt’),scrie(C),told.

scrie([]).scrie([C|Rest]):-

write(C),scrie(Rest).

start:-

see(’litere.txt’),citeste([]),seen.

Programul se rulează apelând start. şi nu va avea nici un output pe consolă

deoarece prelucrează fişierul litere.txt , iar rezultatul va fi scris sub formă de

fişiere în directorul curent în fişierele vocale.txt şi consoane.txt . Predicatulciteste/1 citeşte din fişierul litere.txt şi dacă nu s-a ajuns la finalul fişierului

adaugă la o listă, dacă se ajunge la final când se va face Redo din clauza

secundă a predicatului citeste/1 se va procesa lista şi vor fi scrise fişierele cu

vocale şi consoane.

Exemplul 0.9.2.

Scrieţi un program SWI-Prolog care introduce într-o bază de date dinamică

117

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 118/183

predicate de forma divizor(X,Y) şi par(X) , unde divizor este un predicat

care semnifică faptul că Y este divizorul lui X, iar par(X) semnifică faptul că

X este un număr par. Implementarea în fişierul L12ex2.plApel: ?- apel.

Continuati?(da/nu)d.

X=4.

Y=2.

Continuati?(da/nu)d.

X=8.

Y=4.Continuati?(da/nu)d.

X=10.

Y=5.

Continuati?(da/nu)n.

Yes

?- listing(are).

:- dynamic are/2.are(2, 1).

are(2, 1).

are(4, 2).

are(8, 4).

are(10, 5).

118

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 119/183

Yes

?- listing(par).

:- dynamic par/1.par(2).

par(2).

par(4).

par(8).

Yes

?-Program:

start:-

write(’X=’),read(X),

write(’Y=’),read(Y),

M is X mod Y,M=0,

adauga(X,Y),go.

adauga(X,Y):- assertz(are(X,Y)),fail.adauga(X,Y):- par(Y),assertz(par(X)).

adauga(_,_).

go:-

write(’Continuati?(da/nu)’),read(R),

R=’d’,start.

% go:- retract(are(_,_)),fail.

119

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 120/183

% go:- retract(par(_)),fail.

go.

apel:- asserta(par(2)),go.Programul funcţionează pe principiul: dacă Y divide pe X şi Y este număr

par atunci X este număr par. Liniile 6 şi 7 din program sunt comentate

deoarece nu vrem ca programul să şteargă predicatele adăugate în baza de

date dinamică, în cazul în care nu se continuă introducerea de numere. Pentru

a urmări însă modul în care funcţionează predicatul retract ele trebuiesc

decomentate.

0.9.3 Exerciţii propuse

Exerciţiul 0.9.1.

Scrieţi un program Prolog care citeşte de la tastatură informaţii de forma

persoana(nume(NumePrenume),telefon(NrTel)). le introduce în baza de date

dinamică şi le salvează într-un fişier specificat de utilizator, care mai apoi

poate fi citit şi încărcat în baza de date dinamică.

Exerciţiul 0.9.2.

Modificaţi programul de mai sus referitor la baze de date dinamice astfel

încât să nu se adauge de mai multe ori acelaşi fapt în baza de date.

120

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 121/183

0.9.4 Teme de studiu

Tema 0.9.1.

Rulaţi programele prezentate ca exemple, folosind comanda trace.

121

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 122/183

122

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 123/183

Capitolul 1

Probleme de la concursurile de

programare

123

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 124/183

1.1 Probleme de la concursurile de programare

1.1.1 Ascii

Pentru un N dat scrieţi un predicat cross/1 unde cross(N) desenează figura de

mai jos. În stânga este figura corespunzătoare penru N=5, săgeţile indicând

dimensiunile , iar în dreapta este figura corespunzătoare pentru N=3. Progra-

mul trebuie să funcţioneze pentru orice număr impar între 3 şi 23. Adăugarea

de spaţii în faţa celui mai din stânga asterix nu este permisă.

Figura 1.1: Exemple de apel pentru N=5 şi respectiv N=3

(The 10th Prolog Programming Contest - 20th International Conference on

Logic Programming, ICLP 2004, Saint-Malo, Franţa)

124

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 125/183

1.1.2 Staţii

Belgia este o ţară a căilor ferate. În 5 mai 1835 primul tren din Europaconecta capitala Bruxelles de oraşul Mechelen. În scurt timp au apărut mult

mai multe linii ferate , născându-se astfel o reţea feroviară densă. Totuşi

trenurile întârzie şi nu se poate face nimic pentru a preveni acest lucru.

Însă orice belgian poate locui în orice parte a ţării şi poate călători cu trenul

până la serviciu fără să piardă prea mult timp pe drum. Şi cum nu depărtarea

faţă de locul de muncă sau de staţiile mijloacelor de transport în comun nu

este o problemă , alte lucruri stau la baza alegerii unui loc pentru a locui .Scrieţi un predicat statie/1 care returnează staţia ( deci şi oraşul ) unde este

bine să locuiască un belgian. Predicatul trebuie să întoarcă un oraş sau fail în

cazul în care un astfel de oraş nu există.

Un oraş în care este bine să locuieşti este un oraş care nu este mare. Un

oraş mare este acela care are mai mult de 2 legături directe cu mai mult de 2

alte oraşe. În plus un oraş mic în care este bine să locuieşti se află la fel de

aproape de alte 2 oraşe mari.Informaţiile despre legăturile între oraşe sunt reprezentate ca fapte cale/2.

Toate căile ferate sunt bidirecţionale şi la fel de lungi. Răspunsul nu trebuie

să conţină fapte. Iată exemple de răspunsuri :

cale(bruxel,mechelen).

cale(bruxel, antwerpen).

cale(bruxel,gent).

cale(antwerp,mechelen).

125

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 126/183

cale(antwerp,gent).

cale(gent,brugge)

?- statie(X).X=mechelen

cale(bruxel,charleroi).

cale(bruxel,haacht).

cale(haacht,mechelen).

cale(mechelem,berchem).

cale(berchem,antwerp).cale(bruxel,boom).

cale(boom,antwerp).

cale(antwerp,eindhoven).

?-statie(X).

X=boom

(The 10th Prolog Programming Contest - 20th International Conference on

Logic Programming, ICLP 2004, Saint-Malo, Franţa)

1.1.3 Triplete

Să se genereze toate tripletele (X,Z,Y) care sunt numere întregi din intervalul

[0,9] şi (10*X+Y)/(10*Y+Z)=X/Z. Datele de ieşire trebuie să fie sub forma

următoare:

3 5 9

126

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 127/183

3 1 6

Dacă (3,5,9) şi (3,1,6) sunt soluţii.

(Prolog Programming Contest - 14 Noiembrie 1994 , Ithaca, ILPS’94)

1.1.4 Spirala

Se dau a şi b două numere întregi pozitive, se cere să se afişeze pe ecran un

dreptunghi cu lungimea b şi lăţimea a care conţine numerele de la 1 la a*b

aşezate în spirală. Pentru a=4 şi b=3 rezultatul este următorul:

1 2 3

10 11 4

9 12 5

8 7 6Coloanele trebuie aliniate la dreapta şi trebuie să ocupe N+1 poziţii, unde N

este numărul cifrelor reprezentării zecimale a lui a*b.

(Prolog Programming Contest - 14 Noiembrie 1994 , Ithaca, ILPS’94)

1.1.5 Perioada

Scrieţi un predicat perioada/3 care se apelează cu primii 2 parametri numere

întregi pozitive şi cel de-al treilea este o variabilă liberă. Un astfel de apel

trebuie să unifice cel de-al treilea parametru cu o listă de întregi (de la 0 la 9)

care reprezintă perioada obţinută atunci când primul argument este împărţit

la argumentul secund. Exemple:

?- perioada(3,4,P).

127

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 128/183

P=[0] % deoarece 3/4 = 0,250000. . .

?- perioada(4,3,P).

P=[3] % deoarece 4/3 = 1.33333. . .?- perioada(1,7,P).

P=[1,4,2,8,5,7] % deoarece 1/7 = 0.142857142857. . .

În ultimul exemplu P=[2,8,5,7,1,4] este de asemenea , un răspuns corect, orice

permutare a listei fiind un răspuns corect.

(Second Prolog Programming Contest - 4 Decembrie 1995 , Portland , Oregon

ILPS’95)

1.1.6 Numere

Se consideră o grilă infinită care are un număr finit de puncte luminoase (a se

vedea figura de mai jos). Aceste puncte luminoase sunt reprezentate de fapte

de forma iluminat/4 şi au un punct de start şi un punct de final ca argumente.

Asemănător unui unui ceas electronic aceste puncte pot forma numere de la

0 la 9. Se cere să se scrie predicatul numere/1 care returnează o listă (fărăduplicate, ordinea nefiind importantă) a tuturor numereleor care pot fi recu-

noscute dându-se setul de fapte pentu punctele luminoase. Pentru figura 1

avem numerele:

?- numere(L).

L=[0,1,2,3,4,5,6,7,8,9]

Figura 1 conţine într-adevăr toate numerele de la 0 la 9. Pentru a întelege cum

128

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 129/183

Figura 1.2: Exemplu de display digital

este format un număr punctul din centru este considerat ca având coordona-tele (0,0) , astfel numărul 3 poate fi reprezentat prin următorul set de fapte:

iluminat(1,2,2,2). iluminat(2,2,2,3). iluminat(2,4,2,3). iluminat(2,3,1,3). ilu-

minat(2,4,1,4).

Nu este permisă scalarea numerelor , de exemplu numărul 8 din figura 2 nu

trebuie recunoscut. Pe de altă parte însă numerele pot fi rotite si/sau părţi

care pot fi recunoscute din configuraţia unor puncte luminoase. Spre exemplu

se consideră figura 3 :?- numere(L).

L=[1,3,4,7]

Orientarea numerelor nu este aceeaşi în toate cazurile, iar un punct luminos

poate fi folosit ca parte componentă pentru mai multe numere (de exemplu

numărul 9 poate ascunde numărul 4 şi numărul 1, el însuşi poate fi conside-

rat un 6 rotit). (Second Prolog Programming Contest - 4 Decembrie 1995 ,

Portland , Oregon ILPS’95)

129

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 130/183

1.1.7 Triunghi

Un triunghi de mărimea 5 arată pe ecran în felul următor:

Remarcaţi faptul că există un spaţiu între fiecare steluţă de pe un rând orizon-

tal. Între vârful unui triunghi de dimensiune N şi partea stângă a ecranului nu

trebuie să fie mai mult de N+2 spaţii. Scrieţi predicatul triunghi/1 care este

apelat cu un întreg mai mare decât 0 şi care desenează triunghiul de dimen-

siunea respectivă pe ecran.

(Second Prolog Programming Contest - 4 Decembrie 1995 , Portland , Oregon

ILPS’95)

1.1.8 Diamant

Desenaţi pe ecran un diamant de forma prezentată mai jos. Generalizaţi din

exemple. Predicatul diamant/1 va trebui apelat cu un întreg mai mare decât

0, reprezentând dimensiunea diamantului. Iată exemple de apel ale acestui

predicat:

?- diamant(2).

130

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 131/183

3 2

4?-diamant(3).

4 2

7 5 3

8 6

9?-diamant(8).

(Second Prolog Programming Contest - 4 Decembrie 1995 , Portland , Oregon

ILPS’95)

1.1.9 Drum

Se consideră o tablă pătratică de dimensiune N (considerăm N=4 în acest

exemplu, acest lucru este dat în program de faptul dimensiune(4)), există un

punct de început (întotdeauna pătratul cu coordonatele 1,1) şi un punct de final

131

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 132/183

(dat în program de faptul mergi(1,4,f)). Există un drum corect între punctul de

început şi punctul de sfârşit, acest drum este marcat , fiecare pătrat conţinând

informaţii despre cum se ajunge la următorul pătrat , sub forma unui fapt:mergi(1,1,u). % de la 1,1 mergi în sus , adică spre 1,2

mergi(1,2,u).

mergi(1,3,r). % de la 1,3 mergi la dreapta , adica spre 2,3

mergi(2,3,r).

mergi(3,3,d). % de la 3,3 mergi în jos , adică spre 3,2

mergi(3,2,d)

mergi(3,1,r)Dacă am fi avut un l acesta ar fi însemnat la stânga , desigur f înseamnă

destinaţia finală. Informaţia de mai sus reprezintă tabla următoare:

Figura 1.3: Tabla nemodificată de spiritul rău

Pe o astfel de tablă nu este desigur dificil să se găsească drumul de la 1,1 la

1,4, însă un spirit rău a şters unele informaţii de pe tablă şi fapte de forma

mergi/3 astfel încât drumul nu mai are o reprezentare completă. Totuşi nu a

fost suficent de rău deoarece 2 pătrate vecine din drum nu au informaţie lipsă ,

132

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 133/183

punctul de final de asemenea nu lipseşte şi cel mult 2 vecini ai pătratelor lipsă

aparţin drumului corect (pătratele în diagonală nu sunt considerate vecine)

drumul şi în acest caz este uşor de găsit. Un al doilea spirit , mult mai răudecât primul a introdus informaţii pentru fiecare pătrat care NU se află pe

drumul spre pătratul final, informaţiile sunt de aşa natură încât dacă sunt

considerate corecte fie se iese de pe tablă fie formează un cerc . (în mod

particular nu vor fi întâlnite pătrate goale).

Figura 1.4: Tabla alterată

Se cere să se scrie un predicat drum/1 care returnează drumul corect sub forma

unei liste începând cu 1,1 şi terminând cu punctul final , lista fiind ordonată de-

a lungul drumului parcurs. Pentru exemplul de mai sus drum/1 dă următorul

rezultat:

X=[(1,1),(1,2),(1,3),(2,3),(3,3),(3,2),(3,1),(4,1)]

(Prolog Programming Contest - 14 Noiembrie 1994 , Ithaca ILPS’94)

133

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 134/183

1.1.10 Tabla

Se dă o tablă de dimensiune 4x4 şi în fiecare pătrat un operator binar şi unoperand număr întreg, Se porneşte cu 0 ca valoare curentă şi se alege un drum

pe tablă astfel încât să se viziteze fiecare pătrat o singură dată. De fiecare dată

se execută operaţia având ca operand stâng valoarea curentă şi continuând cu

rezultatul ca valoare curentă. La finalul drumului, valoarea curentă depinde

de drumul ales, această valoare se numeşte valoarea drumului. Trebuie găsită

valoarea maximă a tuturor drumurilor şi numărul drumurilor care au această

valoare. O astfel de tablă şi reprezentarea corespunzătoare ei se găseşte înfigura 1.5.

Predicatul tabla/3 are ca prim argument tabla (datele de intrare) şi produce

Figura 1.5: Exemplu de tablă şi reprezentarea corespunzătoare

ca argument secund valoarea maximală a drumurilor, argumentul numărul 3

fiind numărul drumurilor care au această valoare maximală.

134

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 135/183

1.1.11 Şarpele belgian

Şarpele belgian este un animal care are pe corp un tipar, dar acest tipar nu serepetă de un număr integral de ori. Un tipar este o secvenţă de inele, iar un

inel are un identificator care este un atom de lungime 1. De asemenea, şar-

pele belgian este un animal căruia îi place să stea încolăcit într-un fel anume:

întotdeauna se asează într-un dreptunghi cu capul în colţul din stânga-sus al

dreptunghiului şi corpul întinzându-se pe fiecare rând. Se cere să se scrie un

predicat sarpe/3 care să afişeze un astfel de şarpe belgian. Acel predicat va fi

apelat cu următoarele trei argumente:- o listă de atomi care reprezintă tiparul care se află pe corpul şarpelui.

- o listă a cărei lungime este numărul de inele care acoperă o linie din drep-

tunghiul în care stă şarpele (lista nu este vidă) .

- o listă a cărei lungime este numărul de inele care acoperă o coloană din

dreptunghiul în care stă şarpele (lista nu este vidă).

Predicatul trebuie să aibă următorul rezultat pe ecran:

?- sarpe([a,b,c,d],[_,_,_,_,_],[_,_,_]).(şarpele întins arată astfel a b c d a b c d a b c d a b c)

a b c d a

b a d c b

c d a b c

Înainte de a începe implementarea acestui predicat trebuie ştiut că şarpele bel-

gian dezaprobă operatorii aritmetici, astfel soluţia acestui predicat nu trebuie

să conţină nici un fel de operatori aritmetici. Folosirea următoarelor predicate

135

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 136/183

este interzisă:

is < > =< >= + - * name arg functor =..

(4th Annual Prolog Programming Contest 9 iulie 1997, Leuven)

1.1.12 Hexagon

Se consideră un hexagon compus din hexagoane mai mici numerotate (vezi

figura 1.6). Se cere să se genereze mulţimea hexagoanelor mici aflate la

distanţa N (cu N dat) faţă de un hexagon H dat. Predicatul hex/4 are ca

argumente dimensiunea S a hexagonului mare (adică numărul de hexagoanemici din prima coloană a hexagonului mare) , al doilea argument este H,

numărul hexagonului mic, iar al treilea argument este distanţa N. Predicatul

hex/4 trebuie să unifice ce de-al patrulea argument cu lista tuturor numerelor

hexagoanelor mici aflate la distanţa N de hexagonul H. Lista trebuie să fie

sortată.

Exemple de apel pentru predicatul hex/4:

?- hex(3,1,0,L).L=[3]

?- hex(3,1,1,L).

L=[2,4,5]

?- hex(3,1,2,L).

L= [3,6,8,9,10]

?- hex(3,1,3,L).

L = [7,11,13,14,15]

136

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 137/183

?- hex(3,1,4,L).

L = [12,16,17,18,19]

?- hex(3,1,5,L).L = []

(4th Annual Prolog Programming Contest 9 iulie 1997, Leuven)

Figura 1.6: Hexagon

137

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 138/183

138

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 139/183

Capitolul 2

Soluţiile problemelor propuse

2.1 Introducere. Fapte. Reguli

Rezolvarea 2.1.1.

Definiţi predicatele cumnat, matuşă, unchi, strabunic, soacră.

2.1.1 Soluţie teoretică

Pentru a putea defini predicatele cerute de exerciţiu avem nevoie de un ar-

bore genealogic care se va traduce în PROLOG prin mai multe predicate de

tipul fapt.Predicatul barbat(X) simbolizează faptul ca X este bărbat , acest

fapt ne va fi util în definirea celorlalte predicate. Predicate de forma casato-

rit(gicu,elena). se traduc în limbaj natural în faptul "gicu este căsătorit cu

elena", lucru valabil şi în cazul predicatelor parinte/2 şi frate/2. După ce am

stabilit un arbore genealogic trecem la scrierea predicatelor de tip fapte, pentru

139

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 140/183

toate relaţiile cerute avem nevoie de predicatele casatorit(A,B), parinte(A,B),

frate(A,B), vom înlocui variabilele A şi B cu numele persoanelor din arborele

nostru genealogic. Pentru a arăta că dacă A este casatorit cu B şi reciproca esteadevărată folosim predicatul casatoriti(A,B):- casatorit(A,B);casatorit(B,A).

unde semnul ";" are valoarea unui sau logic, folosim aceeaşi construcţie pentru

predicatele frati şi parinti. Predicatul cumnat(X,Y) va găsi soluţii dacă se rea-

lizează frati(Y,Z) şi casatoriti(X,Z) prin aceasta vrem să simbolizăm faptul că

X este cumnatul lui Y dacă Y are o soră (adică Y cu Z sunt fraţi, iar Z nu este

bărbăt) şi sora lui Y este căsătorită cu X. Predicatul unchi(A,B) se realizează

dacă A este barbat, C este părintele lui B şi C cu A sunt fraţi. Acest predicatmai are o posibilitate de a se realiza, aceasta dacă D este părintele lui B, D este

frate cu C, C este căsatorită cu A şi A este bărbat. Predicatul matusa are si el

2 posibilităţi de a se realiza deoarece pentru matusa(A,B) avem posibilitatea

ca A să fie mătuşa lui B dacă parinti(C,B) adică unul parintii lui B sunt C

care poate fi frate cu A şi bineînteles A nu este bărbat. Posibilitatea a doua A

este căsătorită cu C şi B are părinte D , C şi D sunt fraţi şi în plus A nu este

bărbat. Predicatul strabunic(A,B) folosim predicatul bunic(B,C) prezentat şiadăugăm condiţia C să fie părinte pentru B. Predicatul soacră are 3 conditii

care trebuie îndeplinite soacra(M,N) dacă N şi Z sunt căsătoriţi, M este părinte

pentru Z şi bineînteles Y nu este bărbat. Codul sursă al programului se găseşte

în fişierul L1r1.pl .

140

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 141/183

2.1.2 Apel

Pentru cine este gicu cumnat??- cumnat(gicu,X).

X = gigel

Are gigel cumnat?

?- cumnat(X,gigel).

X = gicu

Cine este mătusa alinei?

?- matusa(X,alina).X = ioana ;

X = anca ;

Pentru cine este mătuşă elena?

?- matusa(elena,X).

X = costi ;

X = gabi ;

X = catalin ;No

Cine este unchiul lui costi?

?- unchi(X,costi).

X = gicu ;

X = gigel ;

Nepoţii lui gicu sunt:

141

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 142/183

?- unchi(gicu,X).

X = costi ;

X = gabi ;X = catalin ;

Cine este soacra mariei?

?- soacra(X,maria).

X = monica ;

maria este soacră pentru:?- soacra(maria,X).

X = gigel ;

X = elena ;

X = anca ;

Străbunicul alinei este X:

strabunic(X,alina).X = marin ;

2.1.3 Cod sursă

barbat(marin).

barbat(ion). barbat(gicu).

142

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 143/183

barbat(george). barbat(gigel).

barbat(andrei). barbat(costi).

barbat(gabi). barbat(catalin).casatorit(marin,monica).

casatorit(ion,maria).

casatorit(gicu,elena).

casatorit(george,anca).

casatorit(gigel,ioana).

casatoriti(A,B):- casatorit(A,B);casatorit(B,A).

parinte(marin,ion). parinte(monica,ion).parinte(ion,gicu). parinte(maria,gicu).

parinte(ion,george). parinte(maria,george).

parinte(ion,ioana). parinte(maria,ioana).

parinte(gicu,andrei). parinte(elena,andrei).

parinte(gicu,alina). parinte(elena,alina).

parinte(george,costi). parinte(anca,costi).

parinte(gigel,gabi). parinte(gigel,catalin).parinte(ioana,gabi). parinte(ioana,catalin).

parinti(A,B):-parinte(A,B);parinte(B,A).

frate(gicu,george). frate(gicu,ioana). frate(george,ioana).

frate(andrei,alina). frate(gabi,catalin).

frati(A,B):- frate(A,B);frate(B,A).

soacra(M,N):-

143

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 144/183

casatoriti(N,Z),parinte(M,Z),not(barbat(M)).

cumnat(X,Y):-

frati(X,Z),not(barbat(Z)),casatoriti(Z,Y).matusa(A,B):-

parinte(C,B),frati(C,A),not(barbat(A)).

matusa(A,B):-

casatoriti(A,C),parinte(D,B),frati(C,D),not(barbat(A)).

unchi(A,B):-

parinte(C,B),frati(C,A),barbat(A).

unchi(A,B):-parinte(D,B),frati(C,D),casatoriti(C,A),barbat(A).

bunic(A,B):-

parinte(C,B),parinte(A,C).

strabunic(A,B):-

bunic(A,C),parinte(C,B),barbat(A).

2.2 Termeni. Variabile. Backtracking.

Predicatele-sistem trace, read, write

Rezolvarea 2.2.1.

Un om cumpară o maşină dacă îi place şi dacă poate să o ia. Unui om

îi place o maşină dacă are puterea pe care şi-o doreşte. Un om poate să ia

o maşină dacă are destui bani în cont să o cumpere sau dacă fiind casatorit,

144

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 145/183

soţiei îi place şi ei maşina şi au împreună bani să o cumpere.

2.2.1 Soluţie teoretică

Pentru a rezolva această problemă definim predicate pentru diferite tipuri de

maşini: pret_masina(masina,pret) este predicatul care defineşte pretul unei

maşini, putere reprezintă puterea unei maşini, putere_minima(masina,putere)

este puterea minimă pe care şi-o doreşte un om de la o maşină. Definim de

asemenea şi fapte pentru suma pe care o are un om în cont şi pentru faptul de

a fi căsătorit sau nu. Avem apoi predicatul place(X,Y) şi vrem să simbolizăm

faptul că lui X îi place maşina Y dacă are puterea T şi puterea_minimă nu

este mai mică decât T. X va putea cumpăra maşina Y dacă are în cont T

şi T este mai mare decât T1, preţul maşinii. Există şi o a doua posibilitate

de a cumpăra maşina şi pentru aceasta redefinim (adăugăm încă o clauză)

predicatul poate astfel dacă sotul lui X este R şi R place maşina Y şi sumele

adunate din conturile lor sunt mai mari decât T, pretul maşinii, atunci vor

cumpăra maşina. Ne mai rămâne să apelăm predicatele de mai sus într-un

predicat general cumpara(X,Y) dacă îi place şi dacă poate .

2.2.2 Apel

?- cumpara(ion,ferrari).

23 ?- cumpara(gicu,ferrari).

Yes

145

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 146/183

2.2.3 Cod sursă

Codul sursă al programului de mai jos se găseşte în fişierul L2r1.plpret_masina(ferrari,15000).

pret_masina(mazda,12000).

pret_masina(skoda,1100).

pret_masina(dacia,350).

putere(ferrari,500).

putere(dacia,65).

putere(mazda,350).putere(skoda,75).

cont(ion,11000).

cont(gicu,13000).

cont(nicu,7000).

cont(ana,5000).

cont(anda,10000).

putere_minima(ion,150).putere_minima(gicu,300).

putere_minima(nicu,500).

putere_minima(ana,300).

putere_minima(anda,350).

sot(gicu,ana).

sot(nicu,anda).

place(X,Y):-putere(Y,T),putere_minima(X,T1),T>=T1.

146

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 147/183

poate(X,Y):-cont(X,T),pret_masina(Y,T1),T>=T1.

poate(X,Y):-sot(X,R),place(R,Y),cont(X,T1),cont(R,T2),

pret_masina(Y,T),TT=T1+T2,TT>=T.cumpara(X,Y):-place(X,Y),poate(X,Y).

Prezentăm în continuare modul în care functionează trace pentru un apel

particular al predicatului cumpara/2:

?- trace,cumpara(gicu,ferrari). <- linia de comanda

Call: (9) cumpara(gicu, ferrari) ? creep <- apelul predicatului cumparaCall: (10) place(gicu, ferrari) ? creep <- predicatul cumpara se satisface dacă

lui gicu îi place maşina ( are puterea dorită ) şi poate să o cumpere

Call: (11) putere(ferrari, _L194) ? creep <- se apelează predicatul putere

Exit: (11) putere(ferrari, 500) ? creep <- puterea maşinii este 500

Call: (11) put_min(gicu, _L195) ? creep <- se apelează put_min

Exit: (11) put_min(gicu, 300) ? creep <- puterea minimă dorită de gicu este

300^Call: (11) 500>=300 ? creep <- se compară puterea maşinii cu puterea mi-

nimă dorită

^Exit: (11) 500>=300 ? creep <- relaţia putere maşină >= putere dorită este

adevărată

Exit: (10) place(gicu, ferrari) ? creep <- se iese cu succes din apelul

place(gicu,ferrari)

Call: (10) poate(gicu, ferrari) ? creep <- mai trebuie îndeplinită condiţia po-

147

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 148/183

sibilităţii financiare, se apelează poate(gicu,ferrari).

Call: (11) cont(gicu, _L194) ? creep

Exit: (11) cont(gicu, 13000) ? creep <- în contul lui gicu se găsesc 13000unităţi

Call: (11) car_cost(ferrari, _L195) ? creep

Exit: (11) car_cost(ferrari, 15000) ? creep <- maşina costă 15000 unităţi

^Call: (11) 13000>=15000 ? creep

^Fail: (11) 13000>=15000 ? creep <- predicatul aritmetic >= nu se îndepli-

neşte deoarece gicu nu are suficiente unităţi pentru a cumpăra maşina singur

Redo: (10) poate(gicu, ferrari) ? creep <- se încearcă resatisfacerea predica-tului poate(gicu,ferrari) pentru cea de-a doua clauză

Call: (11) sot(gicu, _L194) ? creep <- pentru a se îndeplini poate pentru a

doua clauză trebuie îndeplinite sot, place, putere, putere_min

Exit: (11) sot(gicu, ana) ? creep <- gicu are soţie pe ana

Call: (11) place(ana, ferrari) ? creep <- anei îi place ferrari ?

Call: (12) putere(ferrari, _L209) ? creep

Exit: (12) putere(ferrari, 500) ? creepCall: (12) put_min(ana, _L210) ? creep

Exit: (12) put_min(ana, 300) ? creep <- puterea minimă pe care şi-o doreşte

ana de la maşină este 300

^Call: (12) 500>=300 ? creep

^Exit: (12) 500>=300 ? creep

Exit: (11) place(ana, ferrari) ? creep <- anei îi place ferrari

148

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 149/183

Call: (11) cont(gicu, _L195) ? creep

Exit: (11) cont(gicu, 13000) ? creep <- gicu are în cont 13000 unităţi

Call: (11) cont(ana, _L196) ? creepExit: (11) cont(ana, 5000) ? creep <- ana are în cont 5000 unităţi

Call: (11) car_cost(ferrari, _L197) ? creep

Exit: (11) car_cost(ferrari, 15000) ? creep <- maşina costă 15000 unităţi

^Call: (11) _L198 is 13000+5000 ? creep

^Exit: (11) 18000 is 13000+5000 ? creep <- gicu şi ana au împreună 18000

unităţi

^Call: (11) 18000>=15000 ? creep^Exit: (11) 18000>=15000 ? creep <- preţul maşinii este mai mic decât suma

pe care o deţin cei doi

Exit: (10) poate(gicu, ferrari) ? creep <- se iese din clauza 2 a predicatului

poate , de data aceasta cu succes

Exit: (9) cumpara(gicu, ferrari) ? creep <- se iese din cumpara(gicu, ferrari).

Yes <- gicu poate cumpăra ferrari.

2.3 Unificarea. Operaţiile aritmetice

Rezolvarea 2.3.1.

Scrieţi un predicat care calculează media geometrică a două numere intro-

duse de la tastatură. Rezultatul va fi scris pe ecran.

149

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 150/183

2.3.1 Soluţie teoretică

Pentru a calcula media geometrică avem nevoie să calculăm radical din cele

două numere X şi Y. Folosim predicatul predefinit sqrt/1 care va fi evaluat

cu valoarea radicalului. Pentru a scrie pe ecran folosim predicatul write/1, iar

pentru citirile de la tastatură folosim read/1. Valoarea finală va fi obţinută prin

intermediul operatorului is în urma evaluării expresiei sqrt(X*Y). Clauzele vor

fi grupate în acelaşi predicat în ordinea în care ar fi şi în cadrul unui program

structurat.

2.3.2 Apel

?- start.

X=4.

Y=5.

media geometrica este: 4.47214

2.3.3 Cod sursă

start:-

write(’X=’),read(X),

write(’Y=’),read(Y),

M is sqrt(X*Y),

write(’media geometrica este: ’),

write(M).

150

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 151/183

2.4 Recursivitate. Predicatele !(cut) şi fail

Rezolvarea 2.4.1.

Scrieţi predicatul prolog puterea(N,K,R) care returnează în variabila R pe

N la puterea K, cu calculul puterii pe retur.

2.4.1 Soluţie teoretică

Programul trebuie să definească un fapt pentru N la puterea 0 rezultatul este

1, în continuare scădem din K până când K va fi 0 , facem cut în clauza în

care ştim cât este N la puterea 0 şi pe retur înmulţim rezultatul intermediar

cu N.

2.4.2 Apel

?- puterea(4,5,R).

R = 1024 Yes

?- puterea(3,3,R).

R = 27

Yes

151

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 152/183

2.4.3 Cod sursă

Codul sursă al programului de mai jos se găseşte în fişierul L4r1.pl

puterea(N,0,1):-!.

puterea(N,K,R):-

K1 is K-1,

puterea(N,K1,R1),

R is R1*N.

2.5 Turnurile din Hanoi. Funcţiile Fibonacci şi

Ackermann

2.5.1 Soluţie teoretică

N reprezintă termenul de rang N din şirul lui Fibonacci, vom scădea din N

câte o unitate atât timp cât N > 0. Pentru a ajunge la termenul de rang n,

calculăm X n = X n−1 + X n−2 şi reapelăm predicatul pentru termenii X n−1 şiX n şi N-1. Condiţia de oprire este dată de N=0, moment în care se va unifica

variabila liberă F cu valoarea calculată în N1.

2.5.2 Apel

?- fibo_tur(4,R).

R = 2

152

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 153/183

2.5.3 Cod Sursă

fibo_tur(N, F) :-

N1 is N - 2,

fibo_tur(0, 1, N1, F).

fibo_tur(_N0, N1, 0, N1).

fibo_tur(N0, N1, N, F) :-

N > 0,

N2 is N0 + N1,

M is N - 1,

fibo_tur(N1, N2, M, F).

2.6 Liste

Rezolvarea 2.6.1.

Scrieţi un program prolog care simulează pe liste reuniunea, intersecţia, dife-

renţa şi diferenţa simetrică pentru mulţimi.

2.6.1 Soluţie teoretică

Reuniune va fi un predicat recursiv structurat pe cazuri. Cazul în care un

element din prima listă este membru în a doua listă predicatul va face cut şi

se va reapela pentru coada primei liste şi lista a doua. Dacă elementul nu

153

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 154/183

este membru în a doua listă atunci el va fi introdus (la revenirea din apelurile

succesive) în lista rezultat. Oprirea apelurilor se va face atunci când în prima

listă nu mai sunt elemente, tot atunci se va unifica lista secundă cu lista rezul-tat, pe retur vor fi adăugate la lista rezultat elementele pentru care predicatul

member/2 a întors fail .

Intersecţia va funcţiona aproximativ pe acelaşi principiu cu diferenţa că ele-

mentele care sunt comune vor fi adăugate la lista rezultat, pe retur, în cadrul

primei clauze.

În cazul diferenţei la lista rezultat elementele se adaugă pe retur în cadrul

primei clauze dacă elementele din prima listă nu se găsesc şi în a doua listă.Diferenţa simetrică face uz de predicatele deja definite şi se bazează pe definiţia

matematică a acestei relaţii.

2.6.2 Apel

?- diferenta([1,5,3,8,6],[4,5,10,7,6],Rezultat).

Rezultat = [1, 3, 8]Yes

?- diferenta_simetrica([1,5,3,8,6],[4,5,10,7,6],Rezultat).

Rezultat = [1, 3, 8, 4, 10, 7]

Yes

?- reuniune([1,5,3,8,6],[4,5,10,7,6],Rezultat).

Rezultat = [1, 3, 8, 4, 5, 10, 7, 6]

Yes

154

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 155/183

?- intersectie([1,5,3,8,6],[4,5,10,7,6],Rezultat).

Rezultat = [5, 6]

Yes

2.6.3 Cod sursă

Codul sursă al programului de mai jos se găseşte în fişierul L6r1.pl

reuniune([],B,B).

reuniune([X|A],B,C):-

member(X,B),!,reuniune(A,B,C).

reuniune([X|A],B,[X|C]):- reuniune(A,B,C).

intersectie([X|Y],B,Z):-

member(X,B),!,

intersectie(Y,B,Z).

intersectie([_|A],B,C):- intersectie(A,B,C).

intersectie([],_,[]).diferenta(A,[],A):-!.

diferenta([X|A],B,[X|C]):-

not(member(X,B)),!,

dif(A,B,C).

diferenta([_|A],B,C):- diferenta(A,B,C).

diferenta([],_,[]).

diferenta_simetrica(A,B,C):-

155

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 156/183

diferenta(A,B,X),

diferenta(B,A,Y),

reuniune(X,Y,C).

2.7 Probleme speciale

Rezolvarea 2.7.1.

O firmă de cartografie urmăreşte să coloreze o hartă a N tări cu M culori

în aşa fel încât două ţări vecine să nu fie colorate cu aceeaşi culoare. Scrieţi

un program Prolog care să afişeze toate soluţiile posibile pentru N şi M date.

2.7.1 Soluţie teoretică

Predicatul coloreaza(-Lista) returnează o listă de termeni de forma

Tara/Culoare unde Tara este numele unei ţări şi Culoare este culoarea co-

respunzătoare pe hartă a acelei ţări. El apelează setof/3 pentru a construi o

listă de termeni de forma Tara/Var unde - Tara este numele ţării şi Var esteo variabilă, foloseşte apoi culori/2 pentru a lega fiecare variabilă Var de o cu-

loare.

Predicatul culori întoarce "Yes" atunci când , dându-i-se o listă de elemente

de forma Tara/Culoare, se poate găsi o valoare pentru Culoare în aşa fel încât

Tara careia îi este ataşată Culoare nu are ţări vecine de aceeaşi culoare. Pentru

o listă cu Tara/Culoare fiind capul listei şi coada Rest, colorează Rest şi apoi

selectează o valoare pentru Culoare din lista de culori apoi verifică daca există

156

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 157/183

o altă ţară în Rest care să fie colorată cu aceeaşi culoare cu cea selectată. Daca

nu mai sunt elemente în listă atunci întoarce "Yes".

Predicatul tari_vecine(Tara, Tara1) verifică dacă Tara1 este vecină cu Tara,iar lista_vecini/2 este un predicat folosit pentru a reţine în baza de fapte ceva

asemănător unei matrici de adiacenţă.

2.7.2 Apel

?- coloreaza(X).

X=[austria/rosu,belgia/verde,danemarca/albastru,franta/rosu,

italia/galben,olanda/albastru,portugalia/albastru,

spania/galben,elvetia/albastru,germania/galben]

2.7.3 Cod sursă

Codul sursă prezentat se găseşte în fişierul L11r1.pl

coloreaza(Culoare):-

setof(Tara_, X ^lista_vecini(Tara,X), Culoare),culori(Culoare).

culori([]).

culori([Tara/Culoare|Rest]):-

culori(Rest),

member(Culoare, [galben,albastru,rosu,verde]),

\+ (member(Tara1/Culoare, Rest), tari_vecine(Tara, Tara1)).

tari_vecine(Tara, Tara1):-

157

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 158/183

lista_vecini(Tara, Vecini),

member(Tara1, Vecini).

% Reprezentarea vecinilor fiecărei ţărilista_vecini(portugalia, [spania]).

lista_vecini(spania, [portugalia,franta]).

lista_vecini(franta, [spania,belgia,elvetia,germania,italia]).

lista_vecini(belgia, [franta,germania,olanda]).

lista_vecini(olanda, [belgia,germania]).

lista_vecini(germania, [olanda,belgia,franta,elvetia,austria,danemarca]).

lista_vecini(elvetia, [franta,germania,austria,italia]).lista_vecini(austria, [germania,elvetia,italia]).

lista_vecini(italia, [franta,elvetia,austria]).

lista_vecini(danemarca, [germania]).

2.8 Fişiere. Baze de date dinamice

Rezolvarea 2.8.1.

Scrieţi un program Prolog care citeşte de la tastatură informaţii de forma

persoana(nume(NumePrenume),telefon(NrTel)). le introduce în baza de date

dinamică şi le salvează într-un fişier specificat de utilizator, care mai apoi poate

fi citit şi încărcăt în baza de date dinamică.

158

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 159/183

2.8.1 Soluţia problemei 0.9.1

2.8.1.1 Soluţie teoretică

Citirea de la tastatură se face prin intermediul predicatului sistem read/1.

Citim informaţiile necesare şi folosim predicatul sistem assert/1 pentru a in-

troduce tuplul de forma dorită în baza de date dinamică. Pentru a salva datele

trebuie mai întâi să le recuperăm din baza de date dinamică, apelam predicatul

persoana(nume(NumePrenume),telefon(NrTel)). care se va apela pentru toate

persoanele introduse în baza de date dinamică, ne asigurăm de acest lucru

folosind predicatul sistem fail/0 pentru a cauza backtrackingul. Încărcareafişierului presupune citirea de la tastatură a numelui şi utilizarea predicatului

sistem consult/1 care va încărca toate clauzele predicatului persoana/2 salvate

în fişier. Afişarea foloseşte predicatul sistem listing/1 deoarece în urma unui

apel de forma listing. vom primi ca răspuns din partea sistemului o listă cu

toate predicatele compilate de sistem, listing(persoana). va lista numai predi-

catele persoana .

2.8.1.2 Apel

1 ?- adaug.

Nume: ionescu.

Telefon:123456.

mai adaugati?(y/n)y.

Nume: popescu.

Telefon:654321.

159

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 160/183

mai adaugati?(y/n)n.

Yes

2 ?- afisare.

:- dynamic persoana/2.

persoana(nume(ionescu), telefon(123456)).

persoana(nume(popescu), telefon(654321)).

Yes

3 ?- salvez_fisier.Fisier:agenda.

Yes

4 ?- deschid_fisier.

Fisier:agenda.

% agenda.dat compiled 0.00 sec, 676 bytes

Yes

5 ?- afisare.

persoana(nume(ionescu), telefon(123456)).

persoana(nume(popescu), telefon(654321)).

Yes

160

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 161/183

2.8.1.3 Cod sursă

sterg :-deschide_fisier,

prel,

st,

salvez_in_fisier.

deschid_fisier :-

write(’Fisier:’),

read(A),concat_atom([A, ’.dat’], B),

incarc(B).

prel :-

persoana(nume(A), telefon(B)),

fail.

prel.

incarc(A) :-exists_file(B),

consult(A).

incarc(A).

adaug :-

write(’Nume: ’),

read(A),

write(’Telefon:’),

161

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 162/183

read(B),

assert(persoana(nume(A), telefon(B))),

write(’mai adaugati?(y/n)’),read(C),

C=y,

adaug.

salvez :-

persoana(nume(A), telefon(B)),

write(persoana(nume(A), telefon(B))),write_ln(’.’),

fail.

salvez.

salvez_fisier :-

write(’Fisier:’),

read(A),

concat_atom([A, ’.dat’], B),tell(B),

salvez,

told.

st :-

write(’Nume: ’),

read(A),

162

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 163/183

retract(persoana(nume(A), telefon(B))).

afisare :-

listing(persoana).

Rezolvarea 2.8.2.

Modificaţi programul de mai sus referitor la baze de date dinamice astfel

încât să nu se adauge de mai multe ori acelaşi fapt în baza de date.

2.8.2 Soluţia problemei 0.9.2

2.8.2.1 Soluţie teoretică

Ideea de rezolvare este simplă: înainte de a insera în baza de date verifi-

căm dacă există deja faptul respectiv , astfel adăugăm clauza adauga(X,Y):-

are(X,Y). care va întoarce yes dacă există deja un fapt în baza de date şi nu se

va mai încerca resatisfacerea celorlalte clauze. Pentru predicatul par/1 adop-

tăm aceeaşi metodă adauga(X,Y):- par(Y),par(X)., dacă există deja clauze în

baza de date nu se vor mai introduce altele pentru aceleaşi valori.

2.8.2.2 Apel

?- apel.

Continuati?(da/nu)d.

X=6.

Y=3.

Continuati?(da/nu)d.

163

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 164/183

X=6.

Y=2.

Continuati?(da/nu)d.X=6.

Y=2.

Continuati?(da/nu)n.

În urma unei comenzi listing. putem să observăm predicatele introduse în

baza de date dinamică:

:- dynamic par/1.par(2).

par(6).

:- dynamic are/2.

are(4, 2).

are(6, 3).

are(6, 2).

2.8.2.3 Cod sursă

start:-

write(’X=’),read(X),write(’Y=’),read(Y),

M is X mod Y,M=0,

adauga(X,Y),go.

164

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 165/183

adauga(X,Y):- are(X,Y).

adauga(X,Y):- par(Y),par(X).

adauga(X,Y):- assertz(are(X,Y)),fail.adauga(X,Y):- par(Y),assertz(par(X)).

adauga(_,_).

go:- write(’Continuati?(da/nu)’),read(R),R=’d’,start.

% go:- retract(are(_,_)),fail.

% go:- retract(par(_)),fail.

go.

apel:- asserta(par(2)),asserta(are(4,2)),go.% introducem faptele par(2) şi are(4,2) pentru a avea o definiţie pentru aceste

predicate în baza de date.

165

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 166/183

166

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 167/183

Capitolul 3

Anexa Predicate

167

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 168/183

3.1 Anexa predicate

3.1.1 Notaţiile predicatelorNumele predicatului este scris cu text îngroşat şi este urmat de paranteze, iar

între paranteze lista de argumente. Argumentele al căror nume este precedat

de "+" , "-" sau "?" denotă faptul că argumentul care începe cu "+" este

parametru de intrare , cel cu "-" este parametru de ieşire, cele cu "?" sunt

parametri care pot fi fie de intrare , fie de ieşire.

3.1.2 Încărcarea fişierelor sursă

Un fişier PROLOG conţine clauze şi directive, el este încărcat de obicei folosind

predicatele:

consult(+Fisier) Citeşte Fisier ca sursă PROLOG. Fisier poate fi o listă de

fişiere caz în care , fiecare va fi consultat pe rând.

?- consult(fisier). % încarcă fişier sau fisier.pl dacă se găseşte în directorul

curent.

ensure_loaded(+Fisier) Dacă fişierul nu este deja încărcat, acest predicat

este echivalent cu consult/1.

3.1.3 Compararea şi unificarea termenilor

Termenii sunt ordonaţi în ceea ce se cheama ordine standard , această ordine

este definită după cum urmează:

1. Variabile <Atomi <Şiruri de caractere <Numere <Termeni

168

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 169/183

2. Variabilă veche < Variabilă nouă

3. Atomii sunt comparaţi alfabetic.

4. Şirurile de caractere sunt comparate alfabetic.5. Numerele sunt comparate după valoare, numerele întregi şi cele în virgulă

mobilă sunt tratate identic.

6. Termenii compuşi sunt verificaţi mai întâi după aritatea lor, apoi după nu-

mele functorului şi la final după argumente, începând de la cel mai din stânga.

+Term1 == +Term2 Întoarce Yes dacă Term1 şi Term2 sunt echivalenţi.

+Term1 \ == +Term2 Echivalent cu \ +Term1 == Term2.

+Term1 = +Term2 Unifică pe Term1 cu Term2 şi întoarce Yes dacă unifi-carea reuşeşte.

3.1.4 Predicate de control

fail Întoarce fail în toate ocaziile.

true Întoarce Yes în toate ocaziile.

repeat Întoarce Yes pentru a oferi un număr infinit de puncte de alegere.! Cut. Renunţă la a mai căuta soluţii pentru alte valori are unor variabile.

+Scop1 , +Scop2 Conjuncţie. Întoarce Yes dacă Scop1 şi Scop2 pot fi

demonstrate.

+Scop1 ; +Scop2 Disjuncţie. Întoarce Yes dacă Scop1 sau Scop2 poate fi

demonstrat.

\+ +Scop Întoarce Yes dacă Scop nu poate fi demonstrat. + referă ceva

demonstrabil, iar \ este folosit pentru a indica negaţia în PROLOG.

169

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 170/183

3.1.5 Baze de date dinamice

assert(+Term) Adaugă un fapt la baza de date ca ultim fapt sau clauză a

predicatului corespunzător.

asserta(+Term) Echivalent cu predicatul de mai sus, dar Term este adăugat

ca primă clauză sau fapt al unui predicat.

assertz(+Clause) Echivalent cu assert/1 .

retract(+Term) Atunci când Term este atom sau termen el este unificat cu

primul fapt sau prima clauză din baza de date , iar faptul sau clauza este şters

din baza de date.

retractall(+Head) Toate faptele sau clauzele cu care Head se poate unifica

sunt şterse din baza de date.

abolish(+PredSpec) Şterge toate predicatele specificate de PredSpec, unde

PredSpec este de forma Predicat/Aritate. Tot ce are legătură cu predicatul

specificat este şters din sistem.

3.1.6 Intrări şi Ieşiri

3.1.6.1 Stilul ISO

open(+SrcDest, +Mode, -Stream, +Optiuni) SrcDest poate fi un fişier, ter-

minalul sau un termen, Mode poate fi read, write, append sau update, Stream

poate fi, fie o variabilă care la final va conţine identificatorul de stream, fie un

atom şi în cazul acesta atomul va fi identificatorul de stream. Optiuni pate fi :

- type(Type) se foloseşte pentru a putea scrie în mod text, compatibil cu sis-

170

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 171/183

temul de operare. Dacă se foloseşte tipul binar octeţii vor fi scrişi fără a fi

traduşi. De menţionat că pe sistemele Unix nu se face diferenţă între modul

text şi binar.- alias(Atom) dă unui stream un nume. Atenţie la această opţiune deoarece

numele de stream-uri sunt globale. Exemplu:

?- open(data, read, Fd, [alias(input)]). , ...,read(input, Term),...

- eof_action(Action) defineşte ce se întamplă în momentul în care se ajunge

la final de fişier

- buffer(Buffering) defineşte posibilitatea de a avea un buffer.

- close_on_abort(Bool) închide stream-ul dacă în timpul execuţiei programu-lui se apelează predicatul abort/0.

- lock(LockingMode) încearcă să blocheze fişierul pentru ca alte procese să nu

îl modifice în timpul execuţiei programului PROLOG. În mod implicit fişierul

nu va fi blocat , însă locking mode poate fi read sau shared, adica alte pro-

cese(programe) pot accesa fişierul numai pentru citire.

open(+SrcDest, +Mode, ?Stream) Este echivalent cu open/4 cu lista de op-

ţiuni vidă.open_null_stream(?Stream) Deschide un stream vid. Toate funcţiile sunt

active pentru un asemenea stream, dar o încercare de a citi de pe un astfel de

stream returnează end_of_file.

close(+Stream) Închide stream-ul specificat. Dacă acest stream este stream-

ul curent pentru intrare/ieşire atunci terminalul devine stream curent pentru

intrare/ieşire.

171

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 172/183

set_stream(+Stream, +Attribute) Setează stream-ului atributele prezentate

mai sus la predicatul open.

Alte predicate utile

character_count(+Stream, -Numar) Unifică Număr cu indexul curent al ca-

racterului. Pentru stream-urile de intrare acest index este numărul caracterelor

citite de când a fost deschis stream-ul, iar pentru cele de ieşire numărul carac-

terelor scrise. Primul caracter va avea indexul 0.

line_count(+Stream, -Numar) Unifică Numar cu numărul liniilor citite sau

scrise pe Stream.

line_position(+Stream, -Numar) Unifică Numar cu poziţia de pe linia cu-rentă. Se presupune că poziţia este 0 după deschiderea stream-ului , tab-urile

se presupun a exista după fiecare al 8-lea caracter, iar backspace reduce din

Numar o unitate, Numar fiind presupus a fi pozitiv.

3.1.6.2 Stilul Edinburgh

see(+SrcDest) Deschide SrcDest pentru citire şi îl face stream-ul curent deintrare.

tell(+SrcDest) Deschide SrcDest pentru scriere şi îl face să fie stream-ul curent

de ieşire.

append(+File) Similar cu tell/1, dar poziţionează pointerul de scriere la fina-

lul fişierului.

seeing(?SrcDest) şi telling(?SrcDest) Nu returnează numele fişierului deschis

pentru citire/scriere ci returnează indentificatorul de stream.

172

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 173/183

seen. Închide stream-ul curent de intrare.

told. Închide stream-ul curent de ieşire.

3.1.7 Predicate primitive pentru I/O

nl Trece pe linia următoare a stream-ului implicit.

nl(+Stream) Trece pe linia următoare a lui Stream.

put(+Char) Scrie un Char pe stream-ul curent. Char este un cod astfel încât

0=<Char=< 255

put(+Stream, +Char) Scrie Char pe Stream.put_byte(+Byte) Echivalent cu put/1.

put_byte(+Stream, +Byte) Echivalent cu put/2.

put_char(+Char) Echivalent cu put/1.

put_char(+Stream, +Char) Echivalent cu put/2.

put_code(+Code) Echivalent cu put/1.

put_code(+Stream, +Code) Echivalent cu put/2.

tab(+Numar) Scrie un Numar de tab-uri pe stream-ul implicit. Numar trebuiesă fie o expresie care se evaluează ca un întreg pozitiv.

tab(+Stream, +Numar) Scrie Numar de tab-uri pe Stream

flush_output Scrie output-ul pe stream-ul curent.

flush_output(+Stream) Scrie output-ul pe Stream.

get_byte(-Byte) Citeşte de pe stream-ul curent de intrare şi unifică următorul

octet cu Byte. Byte este un întreg între 1 şi 255 şi va fi unificat cu -1 când se

ajunge la final de fişier.

173

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 174/183

get_byte(+Stream, -Byte) Citeşte un octet de pe Stream

get_code(-Code) Asemănător cu get_byte/1.

get_code(+Stream, -Code) Asemănător cu get_byte/2.get_char(-Char) Asemănător cu get_byte/1.

get_char(+Stream, -Char) Asemănător cu get_byte/1.

get(-Char) Citeşte un caracter de pe stream-ul curent de intrare. Char va fi

diferit de caracterul vid şi va fi unificat cu -1 dacă se ajunge la final de fişier.

get(+Stream, -Char) Citeşte un Char de pe Stream.

3.1.8 Citirea şi scrierea termenilor

write(+Term) Scrie Term pe output-ul curent, se pot folosi paranteze şi ghi-

limele.

write(+Stream, +Term) Scrie Term pe Stream.

writeq(+Term) Scrie Term pe output-ul curent , atomii care au nevoie să fie

scrişi cu ghilimele vor fi scrişi în acest fel. Termenii scrişi cu acest predicat pot

fi citiţi cu read/1.writeq(+Stream, +Term) Scrie Term pe Stream şi inserează ghilimele.

print(+Term) Similar cu write/1 , însă acest predicat apelează portray/1

pentru fiecare sub-termen, iar dacă portray/1 întoarce Yes se presupune că

sub-termenul a fost scris. Este folosit pentru a scrie termeni definiţi de utili-

zator.

print(+Stream, +Term) Scrie Term pe Stream.

portray(+Term) Predicat dinamic care poate fi definit de utilizator pentru a

174

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 175/183

schimba felul în care se comportă print/1 .

read(-Term) Citeşte următorul termen PROLOG de pe stream-ul curent şi îl

unifică cu Term.read(+Stream, -Term) Citeşte Term de pe Stream.

3.1.9 Predicate pentru operaţii cu liste

is_list(+Term) Întoarce Yes dacă Term este lista vidă sau este legat de olistă.

memberchk(?Elem, +List) Echivalent cu member/2.

length(?Lista, ?Int) Întoarce în Int numărul elementelor din Lista. Poate fi

folosit pentru crearea unei liste ce conţine variabile neinstanţiate dacă variabila

Int este legată de o valoare întreagă mai mare sau egală cu 0. Dacă este 0 Lista

va fi o listă vidă.

sort(+Lista, -S) Întoarce Yes dacă S poate fi unificată cu o listă ce conţineelementele din Lista, sortate în mod standard. Dublurile vor fi eliminate.

msort(+List, -Sorted) Echivalent cu sort/2, dar nu elimină dublurile.

merge(+Lista1, +Lista2, -Lista3) Lista1 şi Lista2 sunt liste sortate în ordine

standard a termenilor. Lista3 va fi unificată cu o listă ordonată ce conţine

elementele din Lista1 şi Lista2.

merge_set(+Set1, +Set2, -Set3) Set3 va conţine elementele din Set1 şi Set2

cu dublurile eliminate.

175

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 176/183

3.1.10 Predicate aritmetice

between(+Min, +Max, ?Valoare) Min si Max si Valoare sunt numereîntregi. Dacă valoare este instanţiată predicatul întoarce Yes dacă

Min=<Valoare=<Max. Dacă Valoare este o variabiă liberă este legată succe-

siv de toate valorile întregi dinte Min şi Max.

succ(?Int1, ?Int2) Întoarce Yes dacă Int2 poate fi legat de o valoare egală cu

Int1+1 sau Int2 se evaluează ca fiind echivalent cu Int1+1.

plus(?Int1, ?Int2, ?Int3) Întoarce Yes dacă Int3= Int1+Int2 , cel puţin 2 ar-

gumente trebuie intstanţiate.+Expr1 > +Expr2 Întoarce Yes atunci când Expr1 se evaluează cu un nu-

măr mai mare decât Expr2.

+Expr1 < +Expr2 Întoarce Yes atunci când Expr1 se evaluează cu un nu-

măr mai mic decât Expr2.

+Expr1 =< +Expr2 Întoarce Yes atunci când Expr1 se evaluează cu un

număr mai mic sau egal cu Expr2.

+Expr1 >= +Expr2 Întoarce Yes atunci când Expr1 se evaluează cu unnumăr mai mare sau egal cu Expr2.

+Expr1 =\= +Expr2 Întoarce Yes atunci când Expr1 se evaluează cu un

număr care nu este egal cu Expr2.

+Expr1 =:= +Expr2 Întoarce Yes atunci când Expr1 se evaluează cu un

număr care este egal cu Expr2.

-Numar is +Expr Întoarce Yes când Numar a fost unificat cu numărul cu

care se evaluează Expr.

176

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 177/183

?- 1.0 is sin(pi/2). Întoarce No, deoarece sin(pi/2) întoarce 1.0 dat is va

reprezenta ca 1 valoare întreagă, iar după unificare va întoarce fail.

?- 1.0 is float(sin(pi/2)). Întoarce Yes deoarece predicatul float forţeazărezultatul să fie float.

?- 1.0 =:= sin(pi/2). Întoarce Yes deoarece predicatul =:= consideră ambii

termeni ca fiind expresii.

3.1.11 Funcţii aritmetice

+IntExpr1 mod +IntExpr2 Împărtire modulo.+IntExpr1 rem +IntExpr2 Restul împărţirii ca număr real.

abs(+Expr) Modulul expresiei Expr.

sign(+Expr) Semnul lui Expr, se evaluează ca fiind -1 dacă Expr<0 , 1 dacă

Expr>0 şi 0 daca Expr=0.

max(+Expr1, +Expr2) Evaluează cel mai mare număr din cele două.

min(+Expr1, +Expr2) Evaluează cel mai mic număr din cele două.

random(+Int) Se evaluează ca fiind un număr întreg i pentru care 0=<i<Int.round(+Expr) Evaluează Expr si rotunjeşte rezultatul.

integer(+Expr) Asemănător cu round/1.

float(+Expr) Se evaluează ca un număr în virgulă mobilă, în mod normal

PROLOG-ul utilizează pe cât posibil valori întregi. Dacă este folosită în

combinaţie cu predicatul is/2 ca al doilea argument returnează un număr în

virgulă mobilă. În alte contexte operaţia nu are efect.

float_fractional_part(+Expr) Se evaluează ca fiind partea fracţională

177

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 178/183

a unui număr în virgulă mobilă. Întoarce 0 dacă Expr este număr întreg,

negativ dacă Expr este negativ.

float_integer_part(+Expr) Se evaluează ca fiind partea întreagă a unuinumăr în virgulă mobilă. Întoarce Expr dacă Expr este număr întreg, negativ

dacă Expr este negativ.

truncate(+Expr) Trunchiază expresia Expr , asemănător cu

float_integer_part/1.

floor(+Expr) Evaluează Expr şi returnează cel mai mare întreg mai mic sau

egal cu rezultatul evaluării expresiei Expr.

ceiling(+Expr) Evaluează Expr şi returnează cel mai mic întreg mai maresau egal cu rezultatul evaluării expresiei Expr.

ceil(+Expr) Asemănător cu ceiling/1.

+IntExpr » +IntExpr Deplasare la dreapta pe biţi.

+IntExpr « +IntExpr Deplasare la stânga pe biţi.

+IntExpr \/ +IntExpr Operaţia "sau" pe biti.

+IntExpr /\ +IntExpr Operaţia "şi" pe biti.

+IntExpr xor +IntExpr Operaţia "sau exclusiv" pe biti.\ +IntExpr Negaţie pe biţi.

sqrt(+Expr) Radicalul expresiei Expr.

sin(+Expr) Sinusul expresiei Expr.

cos(+Expr) Cosinusul expresiei Expr.

tan(+Expr) Tangenta expresiei Expr.

asin(+Expr) Arcsinusul expresiei Expr.

178

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 179/183

acos(+Expr) Arccosinusul expresiei Expr.

atan(+Expr) Arctangenta expresiei Expr.

log(+Expr) Întoarce logaritmul natural al expresiei Expr.log10(+Expr) Întoarce logaritmul în baza 10 al expresiei Expr.

exp(+Expr) Întoarce e la puterea Expr.

+Expr1 ** +Expr2 Întoarce Expr1 la puterea Expr2.

+Expr1 ^+Expr2 Identic cu **/2.

pi Constanta matematică pi (3.141593).

e Constanta matematică e (2.718282).

3.1.12 Urmărirea execuţiei programului

trace Porneşte urmărirea programului.

tracing Întoarce Yes atunci când trace este activ.

notrace Opreşte trace-ul.

guitracer Instalează puncte cheie în program pentru a putea fi urmărit

trace-ul pe o interfaţă grafică.noguitracer Contrarul lui guitracer.

trace(+Pred) Echivalent cu trace(Pred, +all).

trace(+Pred, +Ports) Urmăreşte predicatul Pred pentru porturile specificate,

porturile valide sunt: call, redo, exit, fail.

notrace(+Scop) Apelează Scop dar suspendă debugger-ul cât timp se execută

Scop.

debug Porneşte debugger-ul.

179

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 180/183

nodebug Opreşte debugger-ul.

debugging Afişează informaţii despre starea debugger-ului.

180

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 181/183

Glosar

ţintă, 36

ţintă vidă, 36

abordare

descriptivă, 93

imperativă, 93

Ackermann, 147

algoritmi de unificare, 58

aritate, 24

backtracking, 115

baza Herbrand, 48

capul clauzei, 35cel mai general unificator, 59

clauză, 34

clauză definită, 36

clauză Horn, 36

clauză unitară, 36

clauză vidă, 34

clauza de bază, 127

clauza recursivă, 127

comentariu PROLOG, 114

comenzi SWI-Prolog, 98

conectori logici, 22

consecinţă logică, 39control, 92

corpul clauzei, 35

cuantificator existenţial, 23

cuantificator universal, 23

cut, 128

rectificată, 69

domeniu nevid, 31

echivalenţă logică, 40

fail, 128

familia formulelor, 26

fapt, 36

fapte PROLOG, 96

Fibonacci, 146

181

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 182/183

Forma Normală Prenex, 42

Forma Normală Skolem, 45

format relaţional, 71formulă, 25

formulă închisă, 26

formulă atomică, 25

formulă derivabilă, 41

formulă prenex, 42

graf de dependenţă, 71

guitracer, 112

inferenţă, 41

interogări PROLOG, 95

interpretare, 31

interpretare Herbrand, 48

Legea lui DeMorgan, 40

liste PROLOG, 151

literal, 34

Loewenheim-Skolem, 45

logică, 92

model, 76

model Herbrand, 49

model minimal, 76

predicat extensional, 72

predicat intensional, 72

predicatul cut, 128predicatul fail, 128

predicatul read, 113

predicatul write, 113

program DATALOG, 66

program definit, 37

program logic, 37

program rectificat, 69program recursiv, 72

rangul unei formule, 27

recursivitate, 127

regulă consistentă, 41

regulă PROLOG, 97

regulile de inferenţă, 41

rezolvent, 54

scop, 36

scopuri PROLOG, 95

simboluri, 22

simboluri funcţionale, 24

simboluri predicative, 22

SLD-arbore, 54

182

5/10/2018 Inteligenta Artificial A Curs - slidepdf.com

http://slidepdf.com/reader/full/inteligenta-artificial-a-curs 183/183

subformulă, 25

substituţie, 27

subtermen, 25

termen, 24

termen de bază, 26

termen ground, 26

termeni PROLOG, 106

trace, 111

transformare în forma prenex, 43

turnurile din Hanoi, 143

unificarea variabilelor, 119

unificatori, 58

univers Herbrand, 47

variabilă, 21

variabilă legată, 26

variabile anonime, 108

variabile limitate, 65

183

Top Related

INTELIGEN ¸T˘A ARTIFICIAL˘A

Suport de Curs - Inteligenta Emotional A

15085833 Intrebari Cu Raspunsuri La Inteligenta Artificial A I

44090454 Inteligenta Artificial A Inferenta in Logica Propozitionala Si Predicativa

Curs Inteligenta Artificiala-master

82130657 Suport de Curs Inteligenta Emotional A

44090502 Inteligenta Artificial A Logica Vaga Fuzzy

Inteligenta Superioara