Prolog TP 1 NFP120 - univ-tebessa.dz · Prolog TP 1 – NFP120 Pierre Courtieu Ecrire le programme...

Prolog TP 1 – NFP120

Pierre Courtieu

Ecrire le programme prolog dans un fichier (par exemple tpprolog.pl), puislancer prolog avec le commande : prolog -s tpprolog.pl.Testez ensuite vosprogramme en tapant des requetes (terminees par un “.” puis <entree>. Il est recom-mande de taper les requetes dans le meme fichier que le programme, en les mettant dansdes commentaires (%), puis de les copier dans prolog. Pour demander un autre solutiona la requete courante, tapez “;”. Pour sortir de la requete courante, tapez <entree>.

1 Rappels sur les listes– [a,b,c] represente la liste [a,b,c].– [a|[b,c]] represente la liste [a,b,c].– [a,b|[c]] represente la liste [a,b,c].– [a|X] represente une liste quelconque commencant par a et dont la queue est la

variable X (X est donc la liste des autres elements).– etc.

2 Predicats simplesEcrivez les predicats suivants :

Ex. 1 — prem(X, Y) : Y est la tete de la liste X.

Ex. 2 — rest(X, Y) : Y est la queue de la liste X.

Ex. 3 — der(X, Y) : Y est le dernier element de la liste X.

Ex. 4 — nieme(N, X, Y) : Y est le N-ieme element de la liste X.

Ex. 5 — elem(Y, X) : Y est un element de la liste X.

Ex. 6 — concat(X, Y, Z) : Z est la concatenation de X et Y.

Ex. 7 — long(X, N) : N est longueur de la liste X.

Ex. 8 — Ecrire paire et impaire qui permettent de tester la parite de la longueurd’une liste.

1

3 Reversibilite des predicatsEx. 9 —

1.Ecrire le predicat extraire(X, Y, E) : Y est la liste X dont on a extrait l’elementE.

2.Essayer les buts :

extraire([3], [], 3).extraire(L, [1,2,3,2,1], 2).extraire([1,2,3,4,5], [1,2,4,5], X).extraire([1,2,3,4,5], L, X).extraire([1,2,4,5], L, 3).

3.Commentez.

Ex. 10 — Utiliser concat pour ecrire sous_liste :sous_liste(ListeIncluse,ListeContenant):-...

Ex. 11 — Ecrire palindrome qui permet de tester si une liste est un palindrome. Onpourra penser a utiliser un accumulateur, c’est-a-dire une liste dans laquelle on stockeles elements lus au moment de l’appel recursif.

4 ArbresOn veut maintenant representer les arbres sous forme de listes contenant les valeurs

des nœuds et les sous-arbres (les listes n’etant pas typees en prolog, ceci est parfaite-ment possible).

Par exemple la liste ci-dessous :

[4,[2,[],[]],[4,[],[]],[7,[5,[],[]],

[9,[],[]]]]

correspond a l’arbre :

4

2 4 7

5 9

Ex. 12 — Ecrire un predicat qui verifie qu’une liste est un arbre binaire.

Ex. 13 — Ecrire un predicat qui verifie qu’un arbre binaire est un arbre de recherche.C’est-a-dire que pour tout nœud de valeur x, tous les nœuds du fils gauche contiennentdes valeurs inferieures (ou egales) a x, et tous les nœuds du file droit contiennent desvaleurs (strictement) superieurs a x. On utilisera les operateurs de comparaison sur lesentier : <, >, <=, >=. . .

2