Questions / réponses

Semaine 6 erreur moodle

Semaine 6 erreur moodle

Mendjeli Allan írta időpontban
Válaszok szám: 6

Bonjour,

Lorsque j'évalue mon fichier student.ml je rencontre le message d'erreur suivant durant la phase d'évaluation :


100 tests positifs + 100 tests négatifs
sur des arbres à 10000 noeuds
\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
Fonction is_bst

Échec sur les arguments suivants :

[Arbre trop grand pour affichage sous Moodle: relancez une évaluation]
///////////////////////////////////////////////////////////////////////////////

*** Test échoué, essayez à nouveau ***

J'ai beau relancer l'évaluation le même message s'affiche. Que dois-je faire pour remédier à ce problème ?

Cordialement,
Válasz erre: Mendjeli Allan

Re: Semaine 6 erreur moodle

Zeitoun Marc írta időpontban

Il faut relancer le test en espérant qu’un petit contre-exemple sera obtenu, ou tester soi-même.  Ça peut prendre plusieurs essais. 

J’ai dû désactiver l’affichage d’arbres trop gros (250 noeuds ou plus) car cela provoque un blocage sous Moodle et ca n’est de toute façon pas très informatif au delà d’une certaine taille. 

Válasz erre: Zeitoun Marc

Re: Semaine 6 erreur moodle

Zeitoun Marc írta időpontban

Une remarque concernant cette question (après visualisation du code) : plusieurs d'entre vous testent si un arbre est un arbre binaire de recherche en vérifiant que la liste obtenue par parcours infixe est croissante. La démarche est bonne mais il faut faire attention à 2 points :

- d'une part, comme dans ce cours on mémorise la multiplicité des clés dans les noeuds, il faut tester que la liste obtenue sans répéter les éléments selon leur multiplicité est strictement croissante. Par exemple, l'arbre Bin((10,1), Bin((10,1), Empty, Empty), Empty) ne doit pas être considéré comme un ABR.

- d'autre part, il faut faire attention à la complexité de la fonction construisant cette liste (l'utilisation de la concaténation de listes @ rend l'algorithme inefficace, et les tests sont faits sur des arbres assez gros).


Válasz erre: Zeitoun Marc

Re: Semaine 6 erreur moodle

Mendjeli Allan írta időpontban

Si je comprends bien, dans mon cas il va falloir que je trouve une alternative aux concaténations que j'utilise dans mon code afin de faire disparaître cette erreur ?

Válasz erre: Mendjeli Allan

Re: Semaine 6 erreur moodle

Zeitoun Marc írta időpontban

Normalement oui (mais il est possible que le test réussisse même si la fonction n'a pas une complexité linéaire par rapport au nombre de noeuds).

Une approche possible est d'écrire une fonction auxiliaire f qui prend en argument un arbre t et une liste l, et telle que f t l renvoie le parcours infixe de t concaténé à l. Le fait de rajouter l'argument  l permet d'écrire cette fonction sans l'opérateur @.

Par ailleurs, un point plus facile à corriger est que la fonction actuelle teste que la liste est croissante au sens large, ce qui conduit à détecter comme ABR l'arbre suivant: Bin((10,1), Bin((10,1), Empty, Empty), Empty). Il faut juste la modifier pour qu'elle teste que la liste est strictement croissante, si on oublie les multiplicités.

Válasz erre: Mendjeli Allan

Re: Semaine 6 erreur moodle

Lasvenes Remi írta időpontban

Sinon pour implémenter la fonction is_bst, tu peux faire une autre fonction, disons btree_every pred t

qui test si chaque étiquette de chaque noeud vérifie le prédicat, de cette manière ça deviens tout de suite beaucoup plus simple pour faire la fonction is_bst: quand tu es sur un noeud, tu doit vérifier que ....... pour le fils gauche, et que ....... pour le fils droit. Tu n'as plus qu'à remplacer les "......." par les bons prédicats.

Válasz erre: Lasvenes Remi

Re: Semaine 6 erreur moodle

Mendjeli Allan írta időpontban

Oui ma fonction marche car testé sous Emacs, et utilisant des arbres "basiques" en guise de paramètre, elle est bien fonctionnelle.

Merci de vos réponses elles me sont très utiles et me permettent de réfléchir à la meilleure façon d'optimiser mon code.