TD 2 Termes

Etat-civil

1. Traduire par un fait Prolog une fiche d’etat-civil du type :
´etat–civil nom NGAOUNDERE
pr´enom Richard
date de naissance 15/02/1960
nationalit´e camerounaise
sexe masculin
adresse rue 4 rue Leclerc
ville Brest
On suppose que la base de faits contient un certain nombre de fiches d’etat-civil. Traduire par des buts Prolog les questions suivantes :
Quels sont les individus (nom,prenom) de nationalite francaise ?
Quels sont les individus (nom,pr´enom,nationalite) de nationalite etrangere ?
Quels sont les individus (nom,pr´enom,nationalite) de nationalite etrangere habitant Brest dans le Finist`ere ?
Y a-t-il des individus habitant la mˆeme adresse ?

Entiers naturels

Traduire en Prolog les axiomes1 d´efinissant les nombres entiers non n´egatifs (N) et les principales op´erations les concernant.
Le vocabulaire initial de la th´eorie des entiers non n´egatifs comprend :
– une constante z qui repr´esente l’entier 0 (z´ero) ;
– une fonction unaire s(X) qui traduit la notion de successeur d’un entier X ;
– un pr´edicat unaire entier(X) (X est un entier).
G´en´eration : z ∈ N et ∀x ∈ N, s(x) ∈ N
Addition : ∀x ∈ N, x + z = x et ∀x, y ∈ N, x + s(y) = s(x + y)
Multiplication : ∀x ∈ N, x • z = z et ∀x, y ∈ N, x • s(y) = x • y + x
Exponentiation : ∀x ∈ N, xz = s(z) et ∀x, y ∈ N, xs(y) = xy • x
1voir par exemple : Manna Z., Waldinger R., (1985) The logical basis for computer programming, Addison-Weslay.
Pr´ed´ecesseur : ∀x ∈ N, p(s(x)) = x
Soustraction : ∀x ∈ N, x − z = x et ∀x, y ∈ N, s(x) − s(y) = x − y
Inf´erieur ou ´egal : ∀x ∈ N, x ≤ z ⇔ x = z et ∀x, y ∈ N, x ≤ y ⇔ x = y ou x ≤ p(y)
Strictement inf´erieur : ∀x, y ∈ N, x < y ⇔ x ≤ y et x 6= y
Quotient et reste :
∀x ∈ N, ∀y ∈ N∗, x < y ⇒ quot(x, y) = 0 et quot(x + y, y) = s(quot(x, y))
∀x ∈ N, ∀y ∈ N∗, x < y ⇒ rest(x, y) = x et rest(x + y, y) = rest(x, y)
Division : ∀x ∈ N, ∀y ∈ N∗, x ÷ y ⇔ ∃q ∈ N∗ tel que x • q = y
Plus grand commun diviseur :
∀x ∈ N, pgcd(x, z) = x et ∀x ∈ N, ∀y ∈ N∗, pgcd(x, y) = pgcd(y, rest(x, y))
12. Factorielle : z! = s(z) et ∀x ∈ N, s(x)! = s(x) • x!

Polynomes

D´efinir le pr´edicat polynome(+Expression,+Variable) vrai si et seulement si l’Expression est un polynˆome par rapport a` la Variable (variable prise au sens math´ematique du terme). Exemples : ?- polynome(3*x^2 + 2*x,x).
true.
?- polynome(3*x^2 + 2*x,y).
false.
?- polynome(3*cos(x)^2 + 1,x).
false.
?- polynome(3*cos(x)^2 + 1,cos(x)).
true.

Arithmetique

1. D´efinir sous forme de pr´edicats Prolog les fonctions math´ematiques suivantes :
(a) abs(X,Y) %Y =|X|
(b) min(X,Y,Z) % Z = min(X, Y )
(c) pgcd(X,Y,Pgcd) % P gcd = pgcd(X, Y )
(d) ppcm(X,Y,Ppcm) % P pcm = ppcm(X, Y )
(e) ch(X,Y) % Y = ch(X)
D´efinir les pr´edicats Prolog correspondant aux suites r´ecurentes suivantes :
Suite factorielle : u0 = 1 et un = n • un−1 ∀n ∈ N∗
Suite de Fibonacci : u0 = 1 , u1 = 1 et un = un−1 + un−2 ∀n ∈ N, n > 1
Un nombre complexe sera repr´esent´ ici par un terme binaire c(Reel,Imaginaire). D´efinir les op´erations suivantes sur les nombres complexes :
(a) argC(Z,Arg) % Arg = arg(Z)
(b) modC(Z,Mod) % M od =| Z |
(c) addC(Z1,Z2,Z) %Z=Z1+Z2
(d) mulC(Z1,Z2,Z) %Z=Z1•Z2
(e) conj(Z,Z1) %Z1= Z
4. D´efinir le pr´edicat dans(I,Min,Max) vrai si et seulement si :
∀I, M in, M ax ∈ N, M in ≤ I ≤ M ax 5 64

Arbres et dictionnaires binaires

Arbres binaires : structure soit vide, soit compos´ee de trois el´ements :
– une racine Val,
– un sous–arbre binaire Gauche,
– un sous–arbre binaire Droite.
Un arbre binaire vide sera repr´esent´ ici par le terme atomique [], un arbre non vide par le terme compos´e bt(Gauche,Val,Droite) (bt comme binary tree).
Exemple : bt(bt(bt([],3,[]),5,bt([],7,[])),9,bt([],12,[]))
D´efinir les pr´edicats suivants concernant les arbres binaires :
(a) arbreBinaire(T) % T est un arbre binaire
(b) dansArbre(X,A) % X est un el´ement de l’arbre binaire A
(c) profondeur(A,N) % N est la profondeur de l’arbre binaire A
Dictionnaires binaires : arbre binaire bt(Gauche,Val,Droite) ordonn´e tel que :
– tous les nœuds de Gauche ont une valeur strictement inf´erieure a` Val ;
– tous les nœuds de Droite ont une valeur strictement sup´erieure a` Val ;
– Gauche et Droite sont eux-mˆemes des dictionnaires binaires.
D´efinir les pr´edicats suivants concernant les dictionnaires binaires :
(a) dicoBinaire(T) % T est un dictionnaire binaire
(b) inserer(X,D1,D2) % X est ins´er´ dans le dictionnaire D1 pour donner D2
Exemple :
50 50
• •
Q Q
30•QQ60• 30•QQ60•
@ @ → insertion de 58 → @ @
10•@33• 52• @75• 10•@33• 52• @75•
A A A
A A A
•5 18• 64• •5 18• 58• 64•
(c) supprimer(X,D1,D2) % X est supprim´e du dictionnaire D1 pour donner D2
Exemple :
50 33
• •
Q Q
30•QQ60• 30•QQ60•
@ @ → suppression de 50 → @
10•@33• 52• @75• 10• 52• @75•
A A
A A
•5 18• 64• •5 18• 64•

Termes de base

D´efinir le pr´edicat base( ?Terme) vrai si et seulement si Terme est un terme de base ; c’est–a`–dire soit un terme atomique, soit un terme compos´e dont tous les arguments sont des termes de base.
D´efinir le pr´edicat sousTerme( ?SousTerme,+Terme) vrai si et seulement si SousTerme est un sous-terme de Terme.
D´efinir le pr´edicat substituer( ?Ancien, ?Nouveau,+Terme, ?NouveauTerme) vrai si et seulement si NouveauTerme correspond au Terme dans lequel toutes les occurences du sous–terme Ancien ont et´ remplac´ees par le sous-terme Nouveau.

Operateurs

Repr´esenter sous forme d’arbres les expressions suivantes :
2 * a + b * c
2 * (a + b) * c
2 * (a + b * c)
((2 * a) + b) * c
2 + a + b + c
D´efinir les op´erateurs Prolog n´ecessaires pour que les phrases suivantes soient des termes Prolog autoris´es :
diane est la secretaire de la mairie de brest. pierre est le maire de brest.
jean est le gardien de but des verts.
D´efinir les op´erateurs Prolog n´ecessaires pour que l’´ecriture de r`egles puissent se faire de la mani`ere suivante :
regle r1 avant regle r2 arriere
si a et b ou c si f ou g
alors d et e. alors h.

TD 3 Listes

Representations de listes

Repr´esenter par un arbre la liste Prolog [a,b,c].
Ecrire de toutes les mani`eres possibles la liste [a,b,c].

Informations sur les listes

D´efinir les pr´edicats suivants :
1. liste(?L) : L est une liste.
?- liste([a,b,c]). ?- liste(L).
true. L=[];
?- liste([a,b|c]). L = [_G504] ;
false. L = [_G504, _G507] ;
?- liste([a,b|[c]]). L = [_G504, _G507, _G510] ;
true. …
2. premier(?X,?L) : X est le premier el´ement de la liste L.
?- premier(a,[a,b,c]). ?- premier(X,[a,b,c]).
true. X = a.
?- premier(a,L). ?- premier(X,L).
L = [a|_G507]. L = [X|_G522].
3. dernier(?X,?L) : X est le dernier el´ement de la liste L.
?- dernier(c,[a,b,c]). ?- dernier(X,[a,b,c]).
true ; X = c ;
false. false.
?- dernier(c,L). ?- dernier(X,L).
L = [c] ; L = [X] ;
L = [_G506, c] ; L = [_G521, X] ;
L = [_G506, _G509, c] ; L = [_G521, _G524, X] ;
… …
4. nieme(?N,?X,+L) : X est le Neme` el´ement de la liste L.
?- nieme(2,b,[a,b,c]). ?- nieme(N,b,[a,b,c]).
true ; N = 2 ;
false. false.
?- nieme(2,X,[a,b,c]). ?- nieme(N,X,[a,b,c]).
X = b ; N = 1, X = a ;
false. N = 2, X = b ;
N = 3, X = c ;
false.
5. longueur(?N,+L) : N est le nombre d’´el´ements de la liste L.
?- longueur(3,[a,b,c]). ?- longueur(N,[a,b,c]).
true ; N=3;
false. false.
6. dans(?X,?L) : X appartient a` la liste L.
?- dans(b,[a,b,c]). ?- dans(X,[a,b,c]).
true ; X = a ;
false. X = b ;
?- dans(b,L). X = c ;
L = [b|_G275] ; false.
L = [_G274, b|_G278] ; ?- dans(X,L).
L = [_G274, _G277, b|_G281] ; L = [X|_G290] ;
… L = [_G289, X|_G293] ;
L = [_G289, _G292, X|_G296] ;
…
7. hors(+X,+L) : X n’appartient pas a` la liste L.
?- hors(b,[a,b,c]). ?- hors(d,[a,b,c]).
false. true ;
false.
8. suivants(?X,?Y,?L) : X et Y se suivent imm´ediatement dans la liste L.
?- suivants(a,b,[a,b,c]). ?- suivants(X,b,[a,b,c]).
true ; X = a ;
false. false.
?- suivants(a,b,L). ?- suivants(X,b,L).
L = [a, b|_G280] ; L = [X, b|_G295] ;
L = [_G276, a, b|_G283] ; L = [_G291, X, b|_G298] ;
… …
?- suivants(a,X,[a,b,c]). ?- suivants(X,Y,[a,b,c]).
X = b ; X = a, Y = b ;
false. X = b, Y = c ;
?- suivants(a,X,L). false.
L = [a, X|_G295] ; ?- suivants(X,Y,L).
L = [_G291, a, X|_G298] ; L = [X, Y|_G310] ;
L = [_G291, _G294, a, X|_G301] ; L = [_G306, X, Y|_G313] ;
… …
9. unique(?X,+L) : X n’apparaˆıt qu’une seule fois dans la liste L.
?- unique(b,[a,b,c,a]). ?- unique(X,[a,b,c,a]).
true ; X = b ;
false. X = c ;
false.
10. occurences(?X,?N,+L) : X apparaˆıt N fois dans la liste L.
?- occurences(a,3,[a,b,a,c,b,a]). ?- occurences(X,3,[a,b,a,c,b,a]).
true ; X = a ;
false. false.
?- occurences(a,X,[a,b,a,c,b,a]). ?- occurences(X,Y,[a,b,a,c,b,a]).
X = 3 ; X = a, Y = 3 ;
false. X = b, Y = 2 ;
X = c, Y = 1 ;
false.

I Enonces
1 De la logique `a Prolog
2 Termes
3 Listes
4 Controle de la resolution
5 Bases de donnees
6 Recherche dans les graphes
II Corriges
1 De la logique a Prolog
2 Termes
3 Listes
4 Contrˆole de la resolution
5 Bases de donnees
6 Recherche dans les graphes
III Annexes
Liste des exercices
Liste des listings
References