UFR IV : Sciences économiques, mathématiques et sociales Département Mathématiques et Informatique Appliqués Filière Mathématiques appliquées et sciences sociales (MASS: Cette filière est cohabilitée entre les universités de Montpellier 2 et 3). DEUG 2ème année

Option Intelligence Artificielle: partiel du 4 avril 2005.

Soient les clauses suivantes:
reste(X,[X|R],R).
reste(X,[Y|R],[Y|Z]) :- reste(X,R,Z).

Question 1: De quelle nature sont les arguments du prédicat reste (atomes ou listes ou quelconques)?

Attention face à une telle question: les arguments d'un prédicat ne sont pas les variables qui apparaissent dans les clauses, qui peuvent être en nombre variable, mais sont en nombre fixe égal à l'arité du prédicat: ici, le prédicat reste a 3 arguments (il est donc d'arité 3, ou ternaire), le prémier (le plus à gauche) est quelconque, et deux autres (à droite) sont obligatoirement des listes.

On peut le noter ainsi: reste(quelconque, liste, liste).

Question 2: Donnez l’ensemble des réponses à la requête suivante: reste(X,[1,0,1],Y).

Là, il suffit d'interroger gprolog, sans oublier de lui demander toutes les solutions. On obtient 3 solutions:
X = 1, Y = [0, 1]
X = 0, Y = [1, 1]
X = 1, Y = [1, 0]

Question 3: Que font ces deux clauses? Expliquez la propriété qui est toujours vérifiée entre les arguments du prédicat reste.

Si le premier argument (qui est quelconque) est un élément de la liste qui est le second argument, alors le dernier argument est unifié avec cette liste deont on a retiré le premier argument.

On en déduit que le second argument est toujours égal au premier argument ajouté à la liste qui est en dernier argument.

On ajoute les clauses suivantes:
affecter([],Vals).
affecter([X|Vars],Vals) :- reste(X,Vals,L), affecter(Vars,L).

Questions 4: Combien de variables sont présentes dans une solution à une requête telle que affecter([X,Y],[1,0,1]).

Il n'y avait pas de piège ici, la réponse est 2.

Question 5: Notre base contient maintenant 4 clauses. Exprimez le nombre de solutions à la requête affecter(X,Y) en fonction des longueurs des listes X et Y?

On peut bien sûr interroger gprolog pour avoir iune idée de la réponse, mais on peut aussi réfléchir directement: les deux arguments du prédicat affecter sont deux listes, une de variables et une de valeurs. Son rôle est d'affecter, de toutes les façons possibles, à chaque variable de la liste de variables une valeur de la liste de valeurs. Cette valeur ne peut ensuite être affectée à une autre variable. Il faut donc que la longueur de la liste de variables soit plus petite que celle de la liste de valeurs. Le nombre de solutions, avec p variables et n valeurs, est donc le nombre de combinaisons de p objets parmi n.

On ajoute la clause suivante:
somme(S,E,N,D,M,O,R,Y) :- N1 is 1000*S+100*E+10*N+D, N2 is 1000*M+100*O+10*R+E, N3 is 10000*M+1000*O+100*N+10*E+Y, N3 is N1+N2.

Question6: Combien de variables sont présentes dans une solution à une requête portant sur le prédicat somme(...) qui ne provoque pas d’erreur Prolog?

Là, il y avait un "piège": étant donnés les nombreux is et + dans les prémissses de la règle, toutes les variables doivent être instanciées pour qu'il n'y ait pas d'erreur Prolog. Tous les arguments du prédicat somme doivent dons être des valeurs entières. La réponse à la question est donc 0.

Question 7: Quelles sont donc les réponses possibles, et dans quels cas se produisent-elles, à une requête portant sur le prédicat somme(...)?

D'après la question précédente, tous les arguments doivent être des valeurs entières. Les deux réponses possibles sont succès ou échec, selon que les 8 valeurs vérifient ou non la règle.

On ajoute alors la clause suivante:
solution([S,E,N,D],[M,O,R,E],[M,O,N,E,Y]) :- affecter([S,E,N,D,M,O,R,Y],[0,1,2,3,4,5,6,7,8,9]), M > 0, S > 0, somme(S,E,N,D,M,O,R,Y).

Question 8: Combien de fois est appelé le prédicat: somme dans la requête: solution([S,E,N,D],[M,O,R,E],[M,O,N,E,Y])?

Le prédicat somme est appelé à chaque fois que tous ses arguments ont été instanciés, c'est à dire, compte tenu des contraintes sur M et S, 9*9*8*7*5*5*4*3*2 fois (voir question 5).

On cherche maintenant à réutiliser le programme précédent pour résoudre le casse tête: FORTY+TEN+TEN=SIXTY.

Question 9: Proposez une définition du prédicat somme pour le nouveau casse tête

On peut pour cela réutiliser le "modèle" précédent:
somme1(F,O,R,T,Y,E,N,S,I,X) :- N1 is 10000*F+1000*O+100*R+10*T+Y, N2 is 100*T+10+E+N, N3 is 10000*S+1000*I+100*X+10*T+Y, N3 is N1+N2+N2.

Question 10: Proposez une définition du prédicat solution .pour le nouveau casse tête

Selon le principe précédent:
solution1([F,O,R,T,Y],[T,E,N],[T,E,N],[S,I,X,T,Y]) :- affecter([F,O,R,T,Y,E,N,S,I,X],[0,1,2,3,4,5,6,7,8,9]), T>0, F>0, S>0, somme1(F,O,R,T,Y,E,N,S,I,X).