Laboratoire 11: Révisions

Sommaire

Résolution de programmes (Examen Été 2023)

Soit le programme suivant :

a(_).

b(X, Y) :- a(X), c(X, Y).
b(2, 5).

c(X, Y) :- d(X), e(Y).

d(1).
d(2).

e(3).
e(4).

Dans la suite de cette question, vous devrez dessiner des arbre de résolution. Pour cela, il est important :

  • d’indiquer les buts à résoudre dans les nœuds de l’arbre
  • d’indiquer les assignations aux variables logiques sur les arcs
  • d’indiquer true comme feuille pour les requêtes qui réussissent, et false. comme feuille pour les requêtes qui ratent.
  • de représenter l’arbre dans son entièreté.
  • de dessiner les nœuds de l’arbre dans le bon ordre.

1 . Quelles sont les solutions pour la requête suivante ? S’il n’y a pas de solution, indiquez false.

?- d(X).

Dessinez l’arbre de résolution complet pour cette même requête.

2 . Quelles sont les solutions pour la requête suivante ? S’il n’y a pas de solution, indiquez false.

?- c(U, V).

Dessinez l’arbre de résolution complet pour cette même requête.

3 . Quelles sont les solutions pour la requête suivante ? S’il n’y a pas de solution, indiquez false.

?- b(X, 5).

Dessinez l’arbre de résolution complet pour cette même requête.

Sélection (Examen Été 2023)

1 . Définissez une fonction select/3 de façon à avoir le résultat suivant (toutes les assignations possibles sont listées) :

?- select(10,[1,2,3], R).
false.

?- select(2, [1,2,3], R).
R = [1, 3] ;
false.

?- select(2, [1,2,3,2,4], R).
R = [1, 3, 2, 4] ;
R = [1, 2, 3, 4] ;
false.

?- select(2, [1,2,3,2,4,2], R).
R = [1, 3, 2, 4, 2] ;
R = [1, 2, 3, 4, 2] ;
R = [1, 2, 3, 2, 4] ;
false.

2 . Soit la définition suivante :

p([], []).
p(L, [X|Xs]) :-
    select(X, L, R),
    p(R, Xs).

Quels sont les résultats de la requête suivante ?

?- p([1,2], [A,B]).

3 . Donnez un nom plus approprié à la relation p/2.

Somme (Examen Automne 2023)

Écrire une relation sum_list/2 qui est telle que sum_list(L, R) met en relation la liste d’entiers L et l’entier R si la somme des éléments de L est R. Aucune autre relation que sum_list ne doit être utilisée. Par exemple :

  • ?- sum_list([], R). doit donner comme réponse R = 0.
  • ?- sum_list([1, 6, 4, 6], R). doit donner comme réponse R = 17.

Liste croissante (Examen Été 2024)

5 . Écrire une relation weakly_increasing/1 qui est telle que weakly_increasing(L) est vraie si la liste d’entiers L est triée dans l’ordre croissant. Aucune autre relation que weakly_increasing ne doit être utilisée. Par exemple :

  • ?- weakly_increasing([]). doit donner comme réponse true.
  • ?- weakly_increasing([1, 1, 3]). doit donner comme réponse true.
  • ?- weakly_increasing([1, 1, 3, 4, 2, 5]). doit donner comme réponse false.

Entrelacement (Examen Été 2024)

Définir une relation interleave/2 qui entrelace les éléments de deux listes. Par exemple :

?- interleave([a,b,c], [1,2,3], L).
L = [a,1,b,2,c,3]

Tri par insertion (Examen Été 2023)

Soit le code OCaml suivant :

let rec insert x = function
| [] -> [x]
| y :: ys ->
  if x < y then
    x :: y :: ys
  else
    y :: (insert x ys)

let rec isort = function
| [] -> []
| x :: xs -> insert x (isort xs)

Donnez une définition équivalente de ces deux fonctions en Prolog.

Concaténation (Examen Été 2024)

Soit la fonction OCaml suivante :

let rec concat lst1 lst2 =
  match lst1 with
  | [] -> lst2
  | x :: xs -> x :: concat xs lst2
  1. Traduire cette fonction en relation Prolog
  2. Donner un exemple d’utilisation de cette relation en Prolog.

Listes associatives (Examen Été 2023)

1 . Définissez une relation empty_assoc/1 qui est vraie pour la liste associative vide.

2 . Définissez une relation get_assoc/3 qui récupère la valeur correspondant à un élément dans une liste associative. Par exemple : get_assoc([(1, a), (2, b), (3, c)], 3, X) doit donner X = c.

3 . Définissez une relation put_assoc/4 qui ajoute un élément dans une liste associative. Si l’élément est déjà présent, il est remplacé. Par exemple : put_assoc([(1, a), (2, b), (3, c)], 3, d, L) donne L = [(1, a), (2, b), (3, d)].

Unification (Examen Automne 2023, Été 2024)

1 . Donner le résultat de l’unification des termes b(X, c) et b(c, Y). Le résultat doit être donné en spécifiant les valeurs que doivent prendre les variables X et Y pour que l’unification ait lieu. La réponse doit être justifiée.

2 . Donner le résultat de l’unification des termes a(X, b(Y, X), Y) et a(c(Y), Z, c(T)). Le résultat doit être donné en spécifiant les valeurs que doivent prendre les variables X, Y, Z, et T.

  1. Soit les requêtes d’unification suivantes. Si les deux termes unifient, donner la substitution qui permet de les unifier. Si ils n’unifient pas, expliquer pourquoi.
?- f(X, g(Y), h(a, Z)) = f(a, g(b), h(Z, a))

?- p(X, q(Y, Z), r(Z)) = p(a, q(b, c), r(d))

?- a(b(X, Y)) = a(b(c(d(Y)), b(1))).

Arbre de résolution (Examen Automne 2023)

Dessiner l’arbre de résolution complet de la requête ?- even(4). au sein des règles suivantes :

even(0).
even(N) :-
  N > 0,
  M is N - 2,
  even(M).

Interpréteur

Les exercices du labo 10 sont une bonne révision de l’interpréteur.