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:
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] |