Programmation logique : TP2

Ajoutez les deux lignes suivantes en début de fichier :
:-prolog_flag(toplevel_print_options, _, [quoted(true), numbervars(true), portrayed(true), max_depth(30)]).
:-prolog_flag(debugger_print_options, _, [quoted(true), numbervars(true), portrayed(true), max_depth(30)]).

1 Programmation des entiers

L'entier 0 sera représenté par la constante zero. Les entiers strictement positifs seront de la forme s(X) où X est lui-même la représentation d'un entier positif ou nul. Définir les prédicats suivants :

1. inferieur(A,B) vrai si A est inférieur strictement à B. Test : affichez des couples d'entiers A et B tels que A est strictement inférieur à B. Est-ce que 3 (noté s(s(s(zero)))) est strictement inférieur à 1. Et l'inverse? Quels sont les entiers strictement inférieurs à 3?
2. max(A,B,M) vrai si M est le max de A et B. Quel est le maximum parmi les entiers 3 et 1? Quel est le maximum parmi les entiers 3 et 3?
3. somme(A,B,C) vrai si A+B=C. Quels entiers ont pour somme 3? Quelle est la somme de 1 et 2?
4. produit(A,B,C) vrai si A*B=C. Quels entiers ont pour produit 6? Quelle est la table de multiplication de 2?
5. div(A,B,Q,R) vrai si le quotient de la division entière de A par B est Q et son reste R. Quels sont les quotients et reste de la division de 5 par 2? de 0 par 3?

Pour les prédicats somme et produit vous les écrirez naturellement puis vous les modifierez en utilisant une borne afin d'empêcher Prolog de descendre trop en profondeur pour éviter les boucles infinies (ainsi, somme(A,B,C) sera défini à partir d'un prédicat somme1(A,B,C,Borne) où somme1(A,B,C,Borne) ne se relance que si la Borne est inférieure à un entier (par exemple 15)).

2 Programmation des liste

Définir les prédicats suivants :

1. conc(A,B,L) vrai si L est la liste obtenue par concaténation des listes A et B.
2. longueur(L,N) vrai si L est une liste de longueur N ou N est un entier comme défini dans la section 1.
3. extrait(L,N,X,AvantN,ApresN) vrai si X est l'élément de L de rang N, AvantN est la liste contenant les éléments de rang inférieur strict à N et AprèsN est la liste des éléments de rang supérieur strict à N. Exemple : extrait([a,b,c,d,e,f],s(s(s(s(zero)))),X,A,P). donne X=d,A=[a,b,c],P=[e,f]. Test : quelles sont toutes les façons de partager la liste [a,b,c,d,e,f] par le prédicat extrait?
4. dichotomie(L1,L2) vrai si L2 est la liste construite à partir de L1 contenant en premier l'élément milieu de L1 puis l'élément milieu de la partie avant le milieu de L1 etc. puis l'élément milieu de la partie après le milieu de L1, puis l'élement milieu de la partie après le milieu de L1 mais après le milieu de la partie après, etc. Par convention, une liste de longueur paire aura pour milieu l'élément situé juste après le milieu théorique. Exemple : dichotomie([a,b,c,d,e,f,g,h], L). donne L=[e,c,b,a,d,g,f,h].

3 Arbre binaire de recherche

On désire gérer des arbres binaires de recherche. Un arbre binaire est

• soit vide
• soit une liste de trois éléments : la racine, le fils droit et le fils gauche. Les fils droits et gauches étant eux-mêmes des arbres binaires.

Un arbre binaire est dit arbre binaire de recherche si pour chacun de ses sous-arbres, le fils gauche et tous ses descendants ont une valeur inférieure strictement à la racine, le fils droit et tous ses descendants ont une valeur supérieure strictement à la racine. L'arbre vide sera représenté par la constante vide. Un arbre non vide sera de la forme noeud(symbole, sous_arbreg, sous_arbred). Où symbole sera un entier représenté comme en partie 1 (nous ne manipulerons ici que des arbres binaires de recherche contenant des entiers), sous_arbreg et sous_arbred seront des arbres. Définir les prédicats suivants :

1. est_vide(A) vrai si A est vide
2. racine(A,R), gauche(A,G) et droit(A,G) qui permettent d'obtenir respectivement la racine, le sous-arbre gauche et le sous-arbre droit d'un arbre A.
3. ajout(X,A,Res) ajoute (si nécessaire) l'entier X au bon endroit dans l'arbre A pour donner l'arbre Res,
4. ajoutliste(L,A,Res) ajoute successivement les entiers de la liste L dans l'arbre A pour donner l'arbre Res. Testez en insérant successivement 6 (noté s(s(s(s(s(s(zero))))))), 2, 8, 1 et 7 dans un arbre initialement vide. Créez un prédicat arbre(A) vrai pour cet arbre.
5. appartient(X,A) vérifie si X appartient à l'arbre A. Testez si 3 appartient à l'arbre de la question précédente. Puis testez pour 2.
6. nbnoeud(A,N) : N est le nombre de noeud de A. Combien y a-t-il de noeuds dans l'arbre de la question 4.
7. hauteur(A,H) : H est la hauteur de A. Quelle est la hauteur de l'arbre de la question 4 ?
8. hauteur(A,X,H) : H est la hauteur de X dans A. Quelle est la hauteur de 1 dans l'arbre de la question 4 ?
9. parcours_RGD (A,L), L est la liste des entiers de l'arbre dans l'ordre Racine Gauche Droite. Quelle est la liste obtenue en parcourant l'arbre de la question 4 dans l'ordre Racine Droite Gauche?
10. parcours_croissant(A,L), L est la liste des entiers de l'arbre dans l'ordre croissant. Donnez la liste des entiers de l'arbre de la question 4 dans l'ordre croissant.
11. dernier(A,X) où X est le dernier (le plus grand) entier de l'arbre, c'est-à-dire l'entier le plus à droite. Quel est le dernier élément de l'arbre de la question 4?
12. supprimer(A,X,Res), Res est l'arbre de A dans lequel on a supprimé X. La suppression d'un élément X entraîne la remontée du sous-arbre gauche de X à la place de X et la réinsertion du sous-arbre droit de X à la bonne place dans cet arbre (tout ce sous-arbre sera positionné dans la première branche gauche vide du sous-arbre droit de cet arbre). Test : insérez 3 4 et 5 dans l'arbre de la question 4, puis supprimez 8. Toujours sur l'arbre de la question 4 auquel on a inséré 3, 4, et 5 supprimez 6.
13. equilibre(A) qui renvoie vrai si en tout noeud de A la différence, appelée déséquilibre, des hauteurs des sous-arbres gauche et droit est en valeur absolue inférieure ou égale à 1. Le calcul du déséquilibre se fera avec un prédicat de la forme desequilibre(A,D,S) où S est le signe (plus ou moins) et D la valeur absolue du déséquilibre. L'arbre de la question 4 est-il équilibré? En ajoutant 0 à l'arbre de la question 4, obtient-on un arbre équilibré?
14. inseretrie(L,A) où L est une liste de mots déjà triée, A est l'arbre obtenu en insérant cette liste de nombre de façon à obtenir un arbre binaire de recherche équilibré. ex : inseretrie([1,2,3,4,5,8],A).
    A = noeud(4,noeud(2,noeud(1,vide,vide),noeud(3,vide,vide)),noeud(8,noeud(5,vide,vide),vide)) (les entiers seront écrits sous la forme vue dans la partie 1).
15. Définir les prédicats permettant d'effectuer des rotations d'arbre simples et doubles (rd,rg,rdg,rgd) comme dessiné ci-dessous.
    
16. Définir un autre prédicat insereq qui ajoute un élément dans un arbre équilibré sans perturber l'équilibre. Pour cela, on insère l'élément aux feuilles comme précédemment, puis on rééquilibre l'arbre par une rotation simple ou double de la façon suivante :
    

    (déseq(A)=+2 et déseq(sag(A))=+1)	(déseq(A)=-2 et déseq(sad(A))=-1)
    rd(A)	rg(A)
    (déseq(A)=+2 et déseq(sag(A))=-1)	(déseq(A)=-2 et déseq(sad(A))=+1)
    rgd(A)	rdg(A)

    Test en insérant (avec insereq) 0 à l'arbre de la question 4.

À propos de ce document...

This document was generated using the LaTeX2HTML translator Version 2K.1beta (1.61)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -split 0 sujtp2.tex

The translation was initiated by Florence Bannay on 2003-01-17