Accueil
Professeur et Démonstrateurs
Horaires et locaux
Notes de cours
Démonstrations et devoirs
Examens
Liens utiles
Au sujet du livre de cours
Consultez vos notes
Foire aux questions (FAQ)
|
|
Démonstration 11: FPFPS (Foulées Préparatoires au Final pour Prolog Seulement)
dernière démo !!!
Note: Pas de "baratin" cette semaine, vous démonstrateurs
aborderons avec vous un exemple de code Prolog .
Travail pratique (pas noté mais fortement recommandé)
Listes
Écrivez les prédicats suivants:
Premier(L,X) qui est vrai si X est le premier élément de la liste L.
Dernier(L,X) qui est vrai si X est le dernier élément de la liste L.
PremierPair(L,X) qui est vrai si X est le premier élément pair de L, une liste d'entiers.
DernierPair(L,X) qui est vrai si X est le dernier élément pair de L, une liste d'entiers.
Somme(L,S) qui est vrai si S est la somme des éléments de L, une liste d'entiers
Length(L,S) qui est vrai si S est le nombre d'éléments de la liste L.
Palindrome(L) qui est vrai si L est une liste palindrome (sa lecture est la même de la gauche vers la droite et de la droite vers la gauche).
Profondeur(L,S) qui est vrai si S est la profondeur de la liste L (ex: [1,2,3,[5,6],4] est de profondeur 2).
|
Tris
- Implantez
insert(X,L1,L2) qui est vrai si L2 est la
liste triée L1 avec X inséré à la bonne place.
- Implantez
insertsort(X,Y) qui est vrai si Y est la
liste X avec ses éléments triés.
- Implantez un prédicat
partition(X,Y,P,G) qui est
vrai si P est la liste des éléments de X qui sont inférieurs ou égaux à
Y et G est la liste des éléments de X qui sont supérieurs à Y.
- Implantez un prédicat
quicksort(X,Y) qui est vrai si
Y est la liste X avec ses éléments triés en respectant l'algorithme de
tri rapide vu en cours (en Scheme ).
|
Arbres
Dans les questions qui suivent A et B sont des arbres binaires
d'entiers, X un entier.
- Écrivez un prédicat
inverse(X,A,B) qui est vrai si
B est l'arbre A où les fils gauches et les fils droits ont été
inversés à chaque noeuds (le fils gauche d'un noeud pointe maintenant
sur la partie de l'arbre qui contient des valeurs supérieure à la
valeur du noeud).
- Écrivez un prédicat
supprime(X,A,B) qui est vrai si
B est l'arbre A privé de l'élement X.
Dans la suite, A et B sont des arbres de calcul où les noeuds
contiennent des opérateurs (parmi + et *) où des entiers, le fils des
noeuds "opérateur" sont les opérandes de l'opérateur concerné. Par
exemple le calcul suivant: 1 + (0 + (3 * (4+2))) peut être
représenté par l'arbre:
- Écrivez un prédicat
calcul(A,C) qui est vrai si C
est le résultat du calcul de l'arbre A.
- Écrivez un prédicat
simplifie_somme(A,B) qui est vrai si B est l'arbre A simplifié de la manière suivante: toutes les branches dont le noeud est + et un des opérandes est 0 est remplacé par l'aure opérande (l'opérateur + ne sert à rien dans cet arbre et est supprimé).
- Écrivez un prédicat
simplifie_produit(A,B) qui est vrai si B est l'arbre A simplifié de la manière suivante: toutes les branches dont le noeud est * et un des opérandes est 1 est remplacé par l'aure opérande (l'opérateur * ne sert à rien dans cet arbre et est supprimé).
- Écrivez un prédicat
simplifie(A,B) qui est vrai si B est l'arbre A simplifié selon les deux précédantes transformations.
- Vérifiez que vos simplifications sont correctes en comparant le
résultat de l'arbre avant et après simplification.
- Écrire un prédicat
egal(A,B) qui est vrai si les
arbres A et B ont la même valeur une fois calculés.
- Écrire un prédicat
identite(A,B) qui est vrai si les
arbres A et B sont identiques (mêmes noeuds).
Les arbres de calcul peuvent maintenant contenir une variable et
dans ce cas, le nom de cette variable apparaît dans le noeud (sous
forme d'un atome). On appele de tels noeuds des noeuds atome.
- Écrivez le prédicat
listeVariables(A,L) qui est vrai
si L est la liste des variables (atomes) rencontrées dans l'arbre.
- Écrivez le prédicat
estInstancie(A) qui est vrai si
l'arbre ne contient pas de noeud atome.
- Écrivez le prédicat
instancie(A,L,B) qui est vrai si
B est le résultat de l'instanciation de A en appliquant les
substitutions des noeuds atomes spécifies dans la liste L. La liste L
est constituée de paires [atome,valeur]. Notez que si la liste est
sous-spécifiée (ne contient pas des associations pour tous les atomes
de A, alors B est à son tour un arbre non instancié.
|
Varias
Soit le programme:
ancetre(X,Y) :- ancetre(X,Z), parent(Z,Y).
ancetre(X,Y) :- parent(X,Y).
parent(a,b).
parent(b,c).
parent(b,d).
On considère la requête suivante:
| ?- ancetre(X,c).
Expliquez le problème et suggérez une solution.
Implantez un prédicat range(X,Y,L) qui est vrai si L
est une liste d'entiers de X à Y.
|
[top] |