Laboratoire 8

Sommaire

Les problèmes de ce labo sont inspirés de la suite de problème P-99

Arbres de résolutions

Note: pour vérifier vos dessins d’arbre de résolutions, vous pouvez vous baser sur la bibliothèque sldnfdraw, dont vous pouvez consulter la documentation, ou bien utiliser interactivement en ligne sur cette page. Attention, cela ne marchera que pour les arbres finis. Nous avons également mis en place un fork qui dessine les arbres au format DOT, voir ici.

  1. Soit le programme suivant :
member(X, [X|_]).
member(X, [_|R]) :- member(X, R).

Dessiner l’arbre de résolution de la requête :

?- member(X, L).
  1. Soit le programme suivant :
myappend([], L, L).
myappend([First | Rest], L1, [First | L2]) :- 
    myappend(Rest, L1, L2).

Dessiner l’arbre de résolution de la requête :

?- myappend([], [3], L3)
  1. Soit le programme suivant :
myappend([], L, L).
myappend([First | Rest], L1, [First | L2]) :- 
    myappend(Rest, L1, L2).

prefix(P, L) :- myappend(P, _, L).
suffix(S, L) :- myappend(_, S, L).

factor(F, L) :- 
    suffix(S, L),
    prefix(F, S).

Dessiner l’arbre de résolution de la requête :

?- factor(X, [1, 2]).
  1. Dessiner les arbres de résolutions des requuêtes effectuées avec les relations suivantes définies durant le labo 7 : same_length/2, reverse/2, flatten/2, max_member/2

Listes

  1. Écrire une relation palindrome/1 qui est vraie pour les listes étant un palindromes.
?- palindrome([a,b,c,b,a]).
true.

?- palindrome([a,b,c]).
false.
  1. Écrire une relation compress/2 entre une liste et la liste contenant les mêmes éléments, mais avec les éléments identiques consécutifs éliminés.
?- compress([a,a,a,a,b,c,c,a,a,d,e,e,e,e],X).
X = [a,b,c,a,d,e]
  1. Écrire une relation pack/2 entre une liste et la liste contenant les éléments identiques consécutifs groupés en sous-listes.
pack([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]]
  1. Écrire une relation encode/2 entre une liste et son encodage RLE.
?- encode([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]]
  1. Écrire la relation inverse à encode/2.
?- decode([[4,a],[1,b],[2,c],[2,a],[1,d],[4,e]], X).
X = [a,a,a,a,b,c,c,a,a,d,e,e,e,e].

Arbres

  1. Écrire un prédicat istree/1 qui est vrai pour les arbres binaires écrit sous la forme t(X, Left, Right) pour un nœud annoté avec X et composé de deux branches Left et Right, et nil pour les feuilles.
?- istree(t(a,t(b,nil,nil),nil)).
true.
?- istree(t(a,t(b,nil,nil))).
false.
  1. Écrire une relation count_leaves/2 entre un arbre et son nombre de feuilles.
?- count_leaves(t(a,t(b,nil,nil),nil),N).
N = 3.
  1. ÉCrire une relation leaves/2 entre un arbre et la liste des éléments contenus dans ses nœuds.
?- leaves(t(a,t(b,nil,nil),nil),L).
L = [a, b].