gilles.hunault@univ-angers.fr
G-ALG : Gestion d'ALGorithmes
Validation des algorithmes
Table des matières cliquable
1. Rappel de la validation dans l'interface Web
2. Validation en ligne de commandes
3. Présentation du format XML pour le modèle de validation
1. Rappel de la validation dans l'interface Web
Pour valider son algorithme selon un modèle, l'utilisateur doit écrire en haut de l'algorithme ## validation-via : XXXX ## où XXXX est le nom du modèle. Il faut bien sûr que l'analyse de l'algorithme ne renvoie pas d'erreur pour qu'on puisse le valider.
Il faut de plus mettre en commentaires (c'est mieux que de les supprimer) les lignes d'affectation des variables d'entrée et ajouter le code
appeler affecteVARSpourVALIDATION()afin que G-ALG initialise proprement les variables pour les tests de validation.
Voici un exemple de fichier avant validation où il y a des affectations et des affichages :
## Algorithme petitgrand.alg ; auteur : gH ############################################################################### # # # énoncé : # # # # à partir des valeurs valA et valB, on renvoie dans petit et grand # # respectivement la plus petite et la plus grande valeur # # # ############################################################################### AFFECTER valA <-- entierAuHasard(1,100) # génération automatique (1) AFFECTER valB <-- entierAuHasard(1,100) # génération automatique (2) si valA < valB alors affecter petit <-- valA affecter grand <-- valB fin_si # valA < valB si valA > valB alors affecter petit <-- valB affecter grand <-- valA fin_si # valA > valB ECRIRE " des deux nombres " , valA , " et " , valB ECRIRE_ " le plus petit est " , petit ECRIRE " et le plus grand " , grandVoici le même fichier aménagé pour la validation :
## Algorithme minmaxValidation.alg ; auteur : gH ############################################################################### # # # énoncé : # # # # à partir des valeurs valA et valB, on renvoie dans petit et grand # # respectivement la plus petite et la plus grande valeur # # # ############################################################################### ## affecter valA <-- entierAuHasard(1,100) # génération automatique (1) ## affecter valB <-- entierAuHasard(1,100) # génération automatique (2) APPELER affecteVARSpourVALIDATION() si valA < valB alors affecter petit <-- valA affecter grand <-- valB fin_si # valA < valB si valA > valB alors affecter petit <-- valB affecter grand <-- valA fin_si # valA > valB ## ecrire " des deux nombres " , valA , " et " , valB ## ecrire_ " le plus petit est " , petit ## ecrire " et le plus grand " , grand2. Validation en ligne de commandes
Si on ne passe pas par l'interface Web, l'interpréteur G-ALG en ligne de de commandes utilise une autre méthode pour la validation et on n'a pas besoin d'écrire le commentaire ## validation-via.. ; par contre il faut laisser affecteVARSpourVALIDATION().
La validation en ligne de commandes utilise le script galg-valide.pl et il faut fournir, dans cet ordre, le nom du fichier de validation puis le nom de l'algorithme. Là encore, il faut que l'analyse de l'algorithme ne renvoie pas d'erreur pour qu'on puisse le valider.
Appeler le script sans paramètre redonne cette syntaxe, comme rappelé ci-dessous :
$gh > galg-valide Il manque des paramètres. Syntaxe : perl galgvalide.pl XML ALGORITHME STOP. $gh > galg-valide minmax.xml minmaxIncomplet.alg Résultats de l'évaluation ========================= Exécution NbVar BonnesRéponses 1 / 3 2 2 2 / 3 2 2 3 / 3 2 0 Avec 2 exécutions réussies sur 3, le taux de réussite est de 66 %. $gh > galg-valide minmax.xml minmaxFaux2.alg Fichier ALGORITHME minmaxFaux2.alg incorrect, erreur(s) détectée(s) via minmaxFaux2.err. STOP à cause des erreurs.3. Présentation du format XML pour le modèle de validation
Les fichiers XML correspondant aux modèles ont pour racine l'élément exercice et contiennent, en plus d'un élément énoncé, des éléments execution -- sans accent sur le e. Voici le code correspondant XML au modèle minmax.xml :
<?xml version="1.0" encoding="ISO-8859-1" ?> <exercice nom="minmax" executions="3" > <énoncé> à partir des variables valA et valB supposées entières, on veut calculer les variables petit et grand contenant respectivement la plus petite et la plus grande des deux valeurs. </énoncé> <execution numero="1"> <entrees> <variable nom="valA" valeur="2" /> <variable nom="valB" valeur="6" /> </entrees> <sorties> <variable nom="petit" valeur="2" /> <variable nom="grand" valeur="6" /> </sorties> </execution> <execution numero="2"> <entrees> <variable nom="valA" valeur="8" /> <variable nom="valB" valeur="5" /> </entrees> <sorties> <variable nom="petit" valeur="5" /> <variable nom="grand" valeur="8" /> </sorties> </execution> <execution numero="3"> <entrees> <variable nom="valA" valeur="1" /> <variable nom="valB" valeur="1" /> </entrees> <sorties> <variable nom="petit" valeur="1" /> <variable nom="grand" valeur="1" /> </sorties> </execution> </exercice>Chaque élément execution contient un élément entrees et un élément sorties dont le contenu est uniquement composé d'éléments variable avec un nom et une valeur en attributs.
De façon plus formelle, une grammaire DTD minimale et raisonnable pour ces modèles est valideModele.dtd, soit le code ci-dessous :
<?xml version="1.0" ?> <!ELEMENT exercice (énoncé,execution+) > <!ELEMENT énoncé (#PCDATA) > <!ELEMENT execution (entrees,sorties) > <!ELEMENT entrees (variable)+ > <!ELEMENT sorties (variable)+ > <!ELEMENT variable EMPTY > <!ATTLIST exercice executions CDATA #REQUIRED > <!ATTLIST exercice nom NMTOKEN #REQUIRED > <!ATTLIST execution numero CDATA #REQUIRED > <!ATTLIST variable nom NMTOKEN #REQUIRED > <!ATTLIST variable valeur CDATA #REQUIRED >On peut aussi utiliser la grammaire schéma XSD définie dans le fichier valideModele.xsd, soit le code ci-dessous :
<?xml version="1.0" ?> <xs:schema xmlns:xs="http://www.w3.org/2001/XMLSchema" elementFormDefault="qualified"> <xs:element name="exercice"> <xs:complexType> <xs:sequence> <xs:element ref="énoncé"/> <xs:element maxOccurs="unbounded" ref="execution"/> </xs:sequence> <xs:attribute name="executions" use="required" type="xs:integer"/> <xs:attribute name="nom" use="required" type="xs:NCName"/> </xs:complexType> </xs:element> <xs:element name="énoncé" type="xs:string"/> <xs:element name="execution"> <xs:complexType> <xs:sequence> <xs:element ref="entrees"/> <xs:element ref="sorties"/> </xs:sequence> <xs:attribute name="numero" use="required" type="xs:integer"/> </xs:complexType> </xs:element> <xs:element name="entrees"> <xs:complexType> <xs:sequence> <xs:element maxOccurs="unbounded" ref="variable"/> </xs:sequence> </xs:complexType> </xs:element> <xs:element name="sorties"> <xs:complexType> <xs:sequence> <xs:element maxOccurs="unbounded" ref="variable"/> </xs:sequence> </xs:complexType> </xs:element> <xs:element name="variable"> <xs:complexType> <xs:attribute name="nom" use="required" type="xs:NCName"/> <xs:attribute name="valeur" use="required" type="xs:string"/> </xs:complexType> </xs:element> </xs:schema>On notera que le contenu d'une variable en entrée peut être une liste de valeurs, comme dans l'exercice premdernv :
<execution numero="4"> <entrees> <variable nom="tailleTab" valeur="5" /> <variable nom="tabVentes" valeur="[1,2,3,6,8]" /> </entrees> <sorties> <variable nom="som3prem" valeur="6" /> <variable nom="som2dern" valeur="14" /> </sorties> </execution>4. Vérification d'un modèle de validation
Nous conseillons d'utiliser xmlstarlet pour vérifier que les modèles sont bien formés et qu'ils respectent les grammaires comme suit :
xmlstarlet val -e -w minmax.xml xmlstarlet val -e -d valideModele.dtd minmax.xml xmlstarlet val -e -s valideModele.xsd minmax.xmlIl y a des vérifications que les grammaires présentées ne peuvent pas effectuer, comme par exemple vérifier que le nombre d'éléments execution est égal à la valeur de l'attribut executions. Il serait possible d'utiliser schematron pour cela, mais nous fournissons une solution plus simple via la transformation XSL nommée valideModele.xsl suivante :
<xsl:stylesheet xmlns:xsl='http://www.w3.org/1999/XSL/Transform' version="1.0"> <xsl:output method="text"/> <xsl:variable name="execs"> <xsl:value-of select="//exercice/@executions" /> </xsl:variable> <xsl:variable name="exec"> <xsl:value-of select="count(//execution)" /> </xsl:variable> <xsl:template match="/"> On a vu executions=<xsl:value-of select="$execs" /> et <xsl:value-of select="$exec" /> fois execution= dans le fichier XML. <xsl:if test="$execs=$exec">Donc tout est OK. </xsl:if> <xsl:if test="$execs!=$exec">Problème. </xsl:if> </xsl:template> </xsl:stylesheet>Là encore, on peut d'utiliser xmlstarlet pour effectuer cette vérification :
$gh > xmlstarlet tr valideModele.xsl minmax.xml On a vu executions=3 et 3 fois execution= dans le fichier XML. Donc tout est OK.Le script valideModele.pl effectue quelques autres vérifications et il est conseillé de l'utiliser :
$h > valideModele minmax.xml Validation de minmax.xml Document bien formé minmax.xml - valid Document conforme au schéma valideExo.xsd minmax.xml validates Comparaison executions= et execution= On a vu executions=3 et 3 fois execution= dans le fichier XML. Donc tout est OK. Affichage des numéros d'exécution <execution numero="1"> <execution numero="2"> <execution numero="3"> Affichage des noms de fichier et d'exerice fichier, nom = minmax exercice, nom = minmax OK, les deux correspondent.5. Caractéristiques non encore implémentées au 01/04/2018
Il n'y a actuellement () aucun moyen de vérifier l'affichage produit par un algorithme, il n'y aucun mécanisme de vérificaiton de contraintes sur les instructions (pas d'instruction POUR par exemple), pas de vérifications sur les tableaux en sortie...
Toute aide est donc la bienvenue...