Informatique et recherche
opérationnelle
IFT2030

Concepts des langages de programmation

Automne 2002


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]


    Dernière mise à jour : Mon Dec 9 21:28:52 EST 2002
    dift2030@iro.umontreal.ca