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)

TP2: Arbre des préfixes communs (ACP)

Avant propos

Pour beacoup d'entre-vous, c'est la première fois que vous allez être exposés à Scheme. Scheme est un langage dont la syntaxe est simple mais qui nécessite une bonne compréhension de deux concepts que vous avez déjà vus partiellement dans d'autres langages: les listes et la récursivité.

Lors de la prochaine démonstration, vous allez découvrir Scheme que nous verrons en cours après l'intra. Très rapidement, vous allez être en mesure de coder certaines méthodes demandées dans ce TP, aussi je vous conseille de ne pas attendre la dernière minute pour vous atteler à ce TP (vous n'y arriverez pas).

Les liens de la section liens utiles vous seront de précieux alliés pour la prise en main de Scheme.

J'ai coté les questions en fonction de leur difficulté:

  • Échauffement: indique une méthode dont la réalisation est simple et qui ne devrait pas vous poser de problème particulier (une fois bien évidemment l'effort initial pour apprivoiser Scheme).
  • Régime de croisière: indique une méthode un peu plus conséquente, tant au niveau de la conception, que du nombre de lignes à produire.
  • tough: indique une méthode qui mettra à plus rude épreuve votre compréhension de la récursivité.

Dans tous les cas, n'hésitez pas à utiliser des méthodes intermédiaires pour réaliser une méthode qui vous est demandée. Et pensez à utiliser au mieux les méthodes que vous avez déjà écrites.

Note: Certaines questions sont dépendantes. Par exemple les questions 4 et 5 dépendent du bon codage de la question 7.

Cadre général

Le but de ce travail est de vous faire programmer en langage Scheme (une variante de Lisp) la réalisation de fonctions capables de gérer un arbre codé en préfixe commun (ACP dans la suite).

Un ACP permet de stocker de grandes quantités de mots autrement qu'en les listant un à un. L'idée est de ne représenter qu'une seule fois les préfixes que les mots ont en commun.

Un schéma vaut mieux que de longues explications, aussi voici une représentation graphique d'un ACP qui contient les 10 mots suivants (la racine de l'arbre est le noeud le plus à gauche, les noeuds marqués d'un carré indiquent les fins de mots et les mots sont lus en partant de la racine et en suivant les arcs):

abricot, abricots, abricotier, abricotiers, abris, abribus, agricole, bricolage, bricole, bricoles

Dans ce travail, vous allez représenter un ACP par une liste.
Prenez note que le format de cette liste vous est imposé
(un projet qui utiliserait un autre codage des ACP ne serait pas corrigé).

Voici la liste qui correspond à l'ACP du schéma précédant:

( (a (b r i (b u s) (c o t ((i e r (s)) (s))) (s)) (g r i c o l e)) (b r i c o l (a g e) (e (s))) )

En voici l'explication:

  • un ACP ne contenant qu'un mot (ex: fruit) se réduit à la liste ordonnée de ses caractères (ex: '(f r u i t))
  • un élement d'un ACP est soit un symbole (le caractère d'un mot de l'ACP) soit une liste:
    • les différents choix de continuation d'un préfixe sont énumérés les uns à la suite des autres.
      Par exemple, dans l'ACP constitué des deux mots abris et abus il existe deux possibilités de continuer
      le préfixe commun ab qui sont ris et us. L'ACP résultant est donc représenté par la liste (a b (r i s) (u s))
    • lorsqu'un symbole d'une liste n'est suivi que d'une seule liste, cela indique que la liste est optionnelle
      (en d'autres mots, le préfixe déjà lu est un mot).
      Par exemple, l'ACP (a (b r is)) indique que a peut être suivi ou pas par b r i s (cet ACP contient donc les deux mots a et abris).
    • Il ne vous est pas demandé dans ce devoir (bien que vous pouvez décider de l'implémenter quand même) de maintenir un ACP trié.
      En clair, les deux ACP suivants sont équivalents (ils contiennent tous les deux les trois mots ananas, abricot et abricots):

      ACP1 = (a (n a n a s) (b r i c o t (s)))
      ACP2 = (a (b r i c o t (s)) (n a n a s))
      

    Voici quelques exemples d'ACP et la liste des mots qui leur correspondent.
    Les fichiers qui contiennent ces mots vous sont indiqués pour chaque exemple.
    Prenez note que ce sont des symboles (au sens de Lisp) et non des caractères qui sont utilisés pour le codage de l'ACP:

    • Fichier=file-5.lex
      Mots = {"abribus", "abricot", "abris", "abricotier", "are"}
      ACP = ((a (b r i (s) (c o t (i e r)) (b u s)) (r e)))

    • Fichier=file-8.lex
      Mots = {"biture", "bitume", "are", "abricotier", "abricot", "abris", "abricot", "abribus"}
      ACP = ((b i t u (m e) (r e)) (a (b r i (s) (c o t (i e r)) (b u s)) (r e)))

    • Fichier=file-10.lex
      Mots = {"brimer", "babillard", "babillages", "babillage", "babilan", "babil", "babies", "babeurre", "babas", "baba"}
      ACP = (b (a b (e u r r e) (i (e s) (l ((a n) (l a (g e (s)) (r d))))) (a (s))) (r i m e r))

    • Fichier=file-35.lex
      Mots = {"abaissés", "abaissèrent", "abaissons", "abaissions", "abaissiez", "abaissez", "abaisseur", "abaisses", "abaissées", "abaisseront",
      "abaisserons", "abaisserions", "abaisseriez", "abaisserez", "abaisseras", "abaisserait", "abaisserais", "abaisseraient", "abaisserai", "abaissera",
      "abaisser", "abaissent", "abaissements", "abaissement", "abaisse-langue", "abaisse", "abaissée", "abaissante", "abaissant", "abaissait",
      "abaissais", "abaissaient", "abaissable", "abaissa", "abaissé"}
      ACP = (a b a i s s (è r e n t) (é ((e (s)) (s))) (o n s) (i (e z) (o n s)) (e ((u r) (z) (s) (r ((i (e z) (o n s)) (o n (s) (t)) (e z) (a ((i ((s) (t) (e n t))) (s))))) (n t) (m e n t (s)) (- l a n g u e))) (a ((i (s) (t) (e n t)) (n t (e)) (b l e))))

    Quelques précisions:

    Dans la suite de cet énoncé, je parle parfois de peigne pour désigner la liste des symboles constitutifs d'un mot.
    Exemple: '(a b r i c o t) est le peigne du mot "abricot".
    Lorsque je parle d'ACP, je fais toujours référence à sa représentation sous forme de liste.


    Cahier des charges

    Nous allons tester votre code en appelant les méthodes que nous vous demandons de coder.
    Ceci implique que vous devez respecter à la lettre les contraintes qui vous sont données
    (même si je fais une erreur dans le nom d'une fonction, vous devez l'utiliser tel quel).
    Seules les méthodes que nous vous demandons de coder (et celles que vous développerez pour qu'elles marchent) sont à remettre. Toute intervention manuelle de la part des correcteurs dans votre source sera "sanctionnée".

    Note:
    Cette mise en garde peut sembler draconienne, mais ca n'est pas par vice. Voici les avantages que je vois à cette "rigueur":

    • moins de travail inintéressant de correction lié au non respect des contraintes (vous êtes nombreux dans ce cours !)
    • dans la vrai vie, vous allez devoir affronter des cahiers des charges plus contraignants encore,
    • vous êtes trop nombreux à poser des questions dont la réponse est dans l'énoncé, ceci vous forcera à le lire vraiment
    • vous saurez (après lecture) à quoi vous attendre.

    Question 1 (1 point) -- Échauffement

    Écrire une méthode purify qui prend en entrée une liste et qui retourne une liste épurée de tous les doublons.

    Ex:

    (purify '(1 2 3 4))         -> (1 2 3 4)
    (purify '(1 2 1 1 3 4))     -> (2 1 3 4)
    (purify '(1 2 2 3 3 4))     -> (1 2 3 4)
    (purify '(1 2 3 4 4))       -> (1 2 3 4)
    (purify '(1 2 3 4 4 3 2 1)) -> (4 3 2 1)
    (purify '(a b c b))         -> (a c b)
    (purify '(a (b a) c (b a))) -> (a c (b a))
    

    Question 2 (1 point) -- Échauffement

    Écrire une méthode mot->peigne qui prend en entrée une chaîne de caractère (au sens de Lisp) et qui retourne une liste des symboles (au sens de Lisp) correspondants:

    (mot->peigne "crême") -> (c r ê m e)
    (mot->peigne "glacée") -> (g l a c é e)
    

    Question 3 (1 point) -- Échauffement

    Écrire une méthode peigne->mot qui prend en entrée une liste de symbole et retourne la chaîne de caractères constituée de la concaténation des symboles de la liste:

    Ex:

    (mot->peigne '(c r ê m e))   -> "crême"
    (mot->peigne '(g l a c é e)) -> "glacée"
    
    Note:
    (peigne->mot (mot->peigne "abricot")) -> "abricot"
    

    Question 4 (2 points) -- Régime de croisière

    Écrire une méthode file->ACP qui prend en entrée le nom d'un fichier qui contient des mots (même format que les fichiers donnés en exemple plus haut) et qui produit en sortie un ACP.

    Ex:

    (writeln (file->ACP "file-10.lex")) ->
    (b (a b (e u r r e) (i (e s) (l ((a n) (l a (g e (s)) (r d))))) (a (s))) (r i m e r))
    

    Question 5 (2 points) -- Régime de croisière

    Écrire une méthode readDico qui prend en entrée le nom d'un fichier qui contient des mots (voir par exemple ceux donnés plus haut) et qui produit en sortie la liste des mots de ce fichier.

    (readDico "file-35.lex")
    
    ("abaissés" "abaissèrent" "abaissons" "abaissions" "abaissiez" "abaissez" "abaisseur" "abaisses" "abaissées" "abaisseront"
    
    "abaisserons" "abaisserions" "abaisseriez" "abaisserez" "abaisseras" "abaisserait" "abaisserais" "abaisseraient" "abaisserai" "abaissera"
    "abaisser" "abaissent" "abaissements" "abaissement" "abaisse-langue" "abaisse" "abaissée"
    "abaissante" "abaissant" "abaissait" "abaissais" "abaissaient" "abaissable" "abaissa" "abaissé")

    Question 6 (3 points) -- Tough

    Écrire le prédicat in? qui prend en entrée (dans l'ordre indiqué) un peigne et un ACP et qui retourne #t si le peigne est dans l'ACP et #f sinon.

    Soit les définitions suivantes:

    (define arbre1 '( (a (b r i ((b u s)(c o t (i e r))(s))) (r e)) (b i t u (m (e) (i e r)) (r e (s)))) )
    (define arbre2 '(a (b r i (b u s)(c o t (i e r))(s)) (r e)) )
    
    Alors:
    (in? '(a b r i s) arbre 1)          -> #t
    (in? '(a b r i s) arbre 2)          -> #t
    (in? '(a b r i) arbre1)             -> #t
    (in? '(a b r i) arbre2)             -> #f
    (in? '(a b r o) arbre1)             -> #f
    (in? '(a b r o) arbre2)             -> #f
    (in? '(a p) arbre1)                 -> #f
    (in? '(a p) arbre2)                 -> #f
    (in? '(b i t u) arbre1)             -> #f
    (in? '(b i t u) arbre2)             -> #f
    (in? '(b i t u m) arbre1)           -> #f
    (in? '(b i t u m) arbre2)           -> #f
    (in? '(b i t u m e) arbre1)         -> #t
    (in? '(b i t u m e) arbre2)         -> #f
    (in? '(b i t u m i e r) arbre1)     -> #t
    (in? '(b i t u m i e r) arbre2)     -> #f
    (in? '(b i t u r) arbre1)           -> #f
    (in? '(b i t u r) arbre2)           -> #f
    (in? '(b i t u r e) arbre1)         -> #t
    (in? '(b i t u r e) arbre2)         -> #f
    (in? '(c o t i e r) arbre1)         -> #f
    (in? '(c o t i e r) arbre2)         -> #f
    (in? '(a b r i c o t i e r) arbre1) -> #t
    (in? '(a b r i c o t i e r) arbre2) -> #t
    

    Question 7 (3 points) -- Tough

    Écrire une méthode ACP->liste qui prend en entrée un ACP et qui produit la liste des peignes contenues dans cet ACP.

    Ex:

    (ACP->liste '((a (b r i ((b u s) (c o t (i e r)) (s))) (r e)) (b i t u (m (e) (i e r)) (r e (s)))))
    
    ((a b r i) (a b r i b u s) (a b r i c o t) (a b r i c o t i e r) (a b r i s) (a r e) (b i t u m e) (b i t u m i e r) (b i t u r e) (b i t u r e s))
    

    Question 8 (3 points) -- Tough

    Écrire une méthode add qui prend en entrée (dans l'ordre indiqué) un peigne et un ACP et qui produit un nouvel ACP dans lequel le peigne a été ajouté (s'il n'existe pas déjà).

    Ex:

    (add '(a b r i b u s) '()) -> (a b r i b u s)
    (add '(a b r i c o t) '(a b r i b u s)) -> (a b r i (c o t) (b u s))
    (add '(a b r i c o t) '(a b r i (c o t) (b u s))) -> (a b r i (c o t) (b u s))
    (add '(a b r i) '(a b r i (c o t) (b u s))) -> (a b r i ((c o t) (b u s)))
    (add '(a b r i s) '(a b r i ((c o t) (b u s)))) -> (a b r i ((c o t) (b u s) (s)))
    (add '(a b r i c o t i e r) '(a b r i ((c o t) (b u s) (s)))) -> (a b r i ((c o t (i e r)) (b u s) (s)))
    (add '(a r e) '(a b r i ((c o t (i e r)) (b u s) (s)))) -> (a (r e) (b r i ((c o t (i e r)) (b u s) (s))))
    (add '(b i t u m e) '(a (r e) (b r i ((c o t (i e r)) (b u s) (s))))) -> ((a (r e) (b r i ((c o t (i e r)) (b u s) (s)))) (b i t u m e))
    (add '(b i t u r e) '((a (r e) (b r i ((c o t (i e r)) (b u s) (s)))) (b i t u m e))) -> ((a (r e) (b r i ((c o t (i e r)) (b u s) (s)))) (b i t u (r e) (m e)))
    


    Consignes

    Nous vous encourageons de remettre ce TP par groupe de deux (ce TP se prête bien au travail "séparé"). Cependant, si vous travaillez seul(e), il est préférable de remettre seul(e). Vous devez remettre un seul fichier qui doit nécessairement porter le nom tp2.scm. Une seule remise par binôme. Votre fichier doit indiquer en entête le nom des auteurs (vous et votre binôme si vous travaillez à deux).

    Voici un exemple de programme Scheme que nous pourrions utiliser pour vérifier l'exactitude de votre programme: test.scm
    Comme vous pourrez le constater, ceci vous impose de respecter le cahier des charges donné plus haut.

    
    


    Procédure de remise, date limite, barême

    La commande de remise est la suivante (prenez garde de remettre sous pift2030 et pas dift2030):
    remise pift2030 TP2 tp2.scm
    
    Pour ceux qui ne sont pas familiés avec la commande remise, tapez man remise dans un terminal.

    Vous avez jusqu'à lundi 25 novembre 2002 midi pour remettre votre travail. Le barême est en partie indiqué dans le sujet. Vous êtes notés sur 15 points (même si la somme des points à gagner est de 16). N'oubliez pas que la notation dépend toujours de critères comme: la qualité (pertinence) du code, son organisation (structuration), sa lisibilité (commentaires, indentation, etc.), sa justesse (le code est-il conforme aux consignes ?). De plus, des consignes vous sont spécifiées, le fait de ne pas les suivre est forcément pénalisant.

    Traduit en Scheme, ca ce dit:

    (set note 
      (min 
        (- 
           (+ question1 question2 question3 question4 question5 question6 question7 question8)
    	consignes_bafouées)
        15))
    

    Prenez le temps de lire ce sujet, et n'oubliez pas que vos démonstrateurs et moi-même sommes là pour toutes vos questions. Bon courage.

    [top]


Dernière mise à jour : Tue Nov 12 13:12:26 EST 2002
dift2030@iro.umontreal.ca