Défiez Baldr

Essayez de leurrer notre logiciel anti-fraude Baldr... Cela nous permettra de l'améliorer, en suivant l'adage "ce qui ne nous tue pas nous rend plus fort"...







Voici une proposition de « challenge » informatique, c'est un challenge ouvert, n'importe qui peut participer. Je pense que David reprendra ce sujet pour un projet du cours de compilation (en 3A). L'objectif est de faire un programme capable de tromper le logiciel anti-fraude « Baldr », ou au moins d'essayer. Ce programme devra copier un code source tout en le maquillant de sorte qu'il diffère de l'original. C'est le seul moyen de vraiment tester la validité de Baldr. Il s'agit bien d'un sujet de compilation car il faudra analyser un code, puis le re-écrire. C'est le même type de tâches que réalise un compilateur, il analyse du code source et produit un code exécutable. Ici, il faut analyser du code C et produire un autre code C, qui a le même comportement d'exécution. Ce code devra s'éloigner le plus possible du code original dans le sens , s'éloigner dans le sens où le mesure Baldr...

Il n'y a rien d'autre à gagner (à moins qu'un sponsor lise ces lignes...) que toute la considération de l'équipe des développeurs et utilisateurs de Baldr. Je publierai ici les résultats que vous aurez bien voulu m'envoyer. 

« Loki-challenge »

Introduction

Si vous lisez ce blog, vous connaissez certainement « Baldr » l'outil anti-fraude que nous avons développé. Cet outil utilise la notion de distance informationnelle pour détecter de la fraude par plagiat lors de TP informatique. Il est d'une puissance redoutable, mais pour mesurer son efficacité, il faudrait essayer de le mettre en défaut: c'est le sujet de ce challenge. Le nom de Loki vient de la mythologie nordique (il aurait provoqué la mort de Baldr). Notre objectif est d'améliorer Baldr, en analysant l' « attaque » et en imaginant les contre-mesures possible.

Schématiquement Baldr calcule une distance entre des fichiers (code source ou exécutable). Une simple analyse d'histogramme de ces distances entre tous les codes rendus pour un TP permet de détecter rapidement les codes qui sont « trop » proches (pour être honnête). Ainsi un programme capable de transformer du code source de manière à augmenter artificiellement cette distance par rapport au code source original pourrait constituer une contre mesure intéressante pour contrer Baldr. L'existence d'un tel programme rendrait l'utilisation de Baldr inutile. Il faudrait en plus, vu le contexte, que le programme soit simple à utiliser.

Voici un schéma global qui montre oû se « situe » le programme Loki lors d'un rendu de TP.

Les contraintes

Voici les contraintes que je propose pour considérer qu'un programme « Loki » est de bonne qualité :

• Il être capable de modifier du code source de manière automatique sans intervention extérieure. A priori la personne l'utilisant est dans une dynamique de fraude et on ne peut donc supposer aucune connaissance particulière en informatique, autre que démarrer un programme (le programme Loki en l'occurrence).
• Loki ne doit pas changer ce que fait le code source original. Le code transformé doit toujours être compilable avec les même options, et l'exécutable doit avoir l'exact même comportement. Dit autrement Loki ne doit pas introduire d'erreur dans le code transformé.
• Loki doit générer la plus grande distance possible entre le code source orignal et le code source transformé. Ce sera là un moyen simple de mesurer la qualité d'un programme de type Loki. Voir plus bas comment faire pour évaluer la qualité de la transformation.
• La taille, ainsi que l'aspect du code source doit rester « discret », typiquement il ne doit pas trop s'éloigner en terme de taille par rapport à la taille moyenne des codes sources rendus par l'ensemble des étudiants. Il doit aussi rester lisible, car les codes sont lus, même si en pratique un prof' pas les moyens de pouvoir tous les comparer deux à deux. Typiquement, je pense qu'utiliser un obfuscateur de code doit pouvoir générer un code satisfaisant le critère de distance. Mais l'objectif de ce genre d'outils est de produire du code illisible. C'est donc très visible.

Les données

Voici quelques données pour tester un programme Loki :

• Des codes source fait par des étudiants lors d'un TP (des originaux à transformer). Voir dans l'archive attaché à cet article (les fichier « code_*.c »).
• Des exemples d'entré/sortie : ce qui m'a servit pour noter les codes des étudiants. Ces données permettront de vérifier que le programme Loki ne modifie pas le comportement du programme original. Voir dans l'archive attaché à cet article : les fichiers « entre[1-4].txt », et « sortie[1-4].txt ».
• Baldr (téléchargeable gratuitement) pour mesurer la distance entre le code original et le code transformé/maquillé. L'objectif est essayer que cette distance soit la plus proche possible des distances « normales » de manière à ce qu'il n'y ai pas le « petit pic à gauche » caractéristique de fraude...
• Vous pouvez donc tester par vous même le résultat de votre Loki. Pour cela il suffit analyser les codes originaux ajouté de votre code fraudé par votre Loki. Une bosse devrai apparaître à gauche sur l'histogramme produit par Baldr. Plus cette bosse est proche de la courbe principale de l'histogramme et plus elle se fondra dans la masse meilleur sera votre Loki.

Postez ici vos questions et remarques, et n'hésitez pas à m'envoyer vos productions.

Annexe(s) :

lokiData.tar.gz :: 30.65 KB

Sujet de TP sur les arbres

Voici le deuxième sujet de TP du module LAB2412.
Très important : changez de binôme (je n'accepterai pas les travaux si il s'agit d'un binôme déjà existant au TP précédent).
L'objectif est d'éviter que certains se reposent derrière un camarrade ayant un bon niveau d'info.
Je vous demande de lire le fichier "consignes de programmation" je pense que cela vous sera très utile. Vous trouverez aussi un petit fichier d'exemple pour débuter, il vous faudra absolument vous en éditer un plus complexe pour tester votre programme.

Annexe(s) :

TP2.pdf :: 0.107 B

consignes de programmation.pdf :: 299.72 KB

Le « dégrugeur », un programme de détection de fraude issu de la recherche en informatique théorique

J'ai implémenté un outils de détection de fraude. Je n'en suis qu'aux premiers résultats mais je pense qu'ils méritent votre attention que vous soyez fan d'algorithmique ou que vous en ayez horreur...
Actualité : Il y a maintenant un logiciel fonctionnel, voyez cet article pour plus d'information.

La distance informationnelle issue de la rechercher en bioinformatique et informatique théorique, permet de calculer une distance (dans le sens mathématique du terme) entre n'importe quel paire de fichiers. On peut donc s'en servir pour détecter une fraude typique de travaux pratique en informatique la « pompe ». C'est le fait de prendre le code d'un camarade et de le « maquiller » pour faire croire qu'il s'agit d'un travail original. Cette opération consiste à modifier le code de manière à le rendre visuellement différent de l'original mais sans rien changer de son fonctionnement. Il y a mille et une façon de faire cela mais en pratique ceux qui le font n'ont pas un bon niveau (sinon il ne frauderaient pas). Il est cependant difficile de détecter deux codes similaire quand on en regarde plusieurs dizaines, même si le « maquillage » est grossier. Ainsi en pratique la fraude est finalement difficile et pénible à détecter, même si une fois détectée elle s'avère souvent facile à prouver : en une ou deux question on voit très vite si une personne comprend ou non un code qu'elle est supposé avoir écrit
La mesure de la distance informationnelle peut nous aider à détecter cette fraude. Regardez dans la dernière version du support de cours du module d'algorithmique avancée (partie « compression de donnés » environ p.15) pour voir comment on peut facilement calculer cette distance.
On peut alors simplement regarder les distances entre les fichiers, sélectionner les fichiers les plus proches et les regarder en détail pour savoir si il y a réellement eu fraude ou non. Cette manière de faire, même si elle constitue déjà un progrès dans la lutte anti-fraude, peut-être insuffisante pour les raisons suivantes.

• Les programmes de TP visent tous le même but il est donc normal qu'ils puissent être plus ou moins proche les uns des autres.
• Un code commun donné de base (comme c'est parfois le cas de certain TP) « fausse » naturellement les calculs de distance.

Il est donc difficile de fixer un seuil de distance permettant de faire une détection fraude efficace dans tous les cas.
Une solution est d'essayer d'avoir une vue d'ensemble, pour trouver automatiquement un seuil de détection. Pour cela on fait implicitement la supposition suivante : la majorité des codes sont des « originaux » et le nombre de fraudes (si il y en a) est à priori faible. On peut imaginer que chaque fichier à analyser est un point dans un espace vectoriel ainsi l'ensemble des fichiers est assimilable à un nuage de point. La distance informationnelle représente la distance entre ces points. Il serait très intéressant de visualiser ce nuage de points. A priori, si il y a de la fraude on le repérera visuellement en constatant qu'un certain nombre de points sont beaucoup plus resserrés que la moyenne des autres points. Cette vision globale permettra d'un coup d'oeil d'estimer ce qu'est une distance « raisonnable » entre deux fichier, et donc de trouver naturellement un seuil de détection de fraude.
Cette idée est séduisante mais cela est problématique pour plusieurs raisons :

• On a les distances entre les points, pas les coordonnées.
• La dimension de l'espace considéré est élevée.

Il y a des moyens d'estimer les coordonnées à partir des distances, le premier problème est donc contournable Le deuxième est plus embarrassant On n'est assuré de pouvoir trouver les coordonnées exactes, ne contredisant pas l'information de distance qu'a partir de n-1 où n est le nombre de fichiers à analyser. En pratique cela fait plusieurs dizaines... Or on ne peut visualiser de manière claire et intuitive que des coordonnées en dimension inférieure ou égale à 3.
La première approche est de mesurer l'erreur commise en n'autorisant que 3 dimensions, avec de la chance si cette erreur est faible, cela veux dire qu'on à réussit à faire une représentation à peu près correcte en dimension 3. Cela fonctionne raisonnablement bien mais a ses limites... On ne peut analyser qu'un nombre limité de fichiers. Mais cela montre déjà avec quelle facilité on peut détecter de la fraude. J'ai pris les fichiers des TP du module LAB2412 que j'ai numérotés et auquel j'ai ajouté un code fraudé. Ce code est une copie du code numéro 4 que j'ai édité :

• Changement d'une bonne partie des noms de variables et fonctions
• Modification des commentaires
• Modifications de l'indentation

Dans l'image ci-dessous vous pouvez visualiser la « proximité » de ces programmes.

On constate qu'il y a deux points (donc deux programmes) qui sont notablement plus proche l'un de l'autre que toute autre paire de points/programmes. C'est bien évidement le code_4 et le code_Fraude qui sont le plus proches.
Cela marche donc bien quand il y a peu de documents à traiter mais on ne peut pas, comme cela, visualiser de « vrais » nuages de points c'est à dire analyser d'un coup un lot important de fichiers. Cela est du à la dimension est trop grande pour être correctement représenté en dimension 3. Un peu comme quand on représente une carte du monde à plat (3D->2D) on sait que la taille des pays proches des pôles n'est pas à l'échelle des tailles des pays des tropiques. On peut pourtant utiliser ces cartes pour un certain nombres de chose même si d'un certain point de vu elles sont fausses. Nous avons la un problème similaire. Ce type de représentation reste donc possible si on accepte un certain nombre de déformations contrôlées...
Typiquement ici ce qui nous intéresse c'est les distances faibles (correspondant aux fraudes suspectées) on peut donc modifier l'algorithme de calcul des coordonnées pour se focaliser sur ces points et tolérer une plus grande erreur sur les distances plus importantes. On peut regarder la distribution des distances entre les fichiers, et décider que les distances supérieures à un certain seuil n'ont pas besoin d'être respectées (tant qu'elle sont supérieures à la distance minimale exigée).
Voici la courbe de distribution des distances informationnelles sur l'exemple considéré :

• L'axe des x représente la distance informationnelle.
• L'axe des y représente le nombre de paires de points ayant cette distance.

On décide de « négliger » les distances supérieures à 0.23, ce qui semble raisonnable pour détecter une éventuelle fraude car cela représente les 45 plus petites distances entre points.
Voilà ce que ça donne :

A première vue cela fait un peu fouillis, car il y a beaucoup de données : 30 points.On voit ensuite qu'une paire de points vraiment plus proche que les autres, à tel point que les labels des points s'écrivent l'un sur l'autre (code4 et codeFraude). Les quelques autres paires de points qui ont l'air proches ne le sont en fait pas (par exemple code_26 et code_21). Il ne s'agit que d'un effet de projection de 3D vers 2D. Pour s'en apercevoir il suffit de rechercher ces points dans cette autre vue du même nuage de points pour s'apercevoir qu'il sont en fait passablement éloignés.

Notez que les points code4 et codeFraude sont toujours aussi près l'un de l'autre.
Si vous voulez avoir une meilleure vue de ce nuage de points utilisez le logiciel gnuplot pour visualiser vous même ces données. Si vous êtes sous Linux, ce logiciel est déjà probablement installé sur votre machine. Pour visualiser le nuage de point téléchargez ce fichier puis tapez gnuplot, après un bref affichage de texte, vous pourrez taper : load "nuagePoints.txt"
une fenêtre s'affiche alors. Cliquez (laissez le bouton gauche enfoncé) dans la fenêtre et bougez la souris , le nuage de points tournera sur lui même pour que vous le scrutiez sous tous les angles.
Pour conclure :

• C'est un outil très puissant pour détecter la fraude en TP ou toute autre activité pédagogique où le rendu est un fichier.
• Note : seul les codes « qui compilent » on été utilisés pour cet expérience car la mesure de comparaison à été faite sur les exécutables.
• Biensur j'utiliserai ce programme de détection à l'avenir...

Voici les prochaines étapes de ce projet :

• Je suis à la recherche de personnes pouvant m'aider à faire un « screencast » pour présenter le logiciel et ses capacités.
• Je suis à la recherche de compétences spécifiques en interface graphique en Java.
• Je suis aussi à la rechercher d'archive de fichiers de rendu de projets pour tester sur d'autres exemples.

• codes
• rapports
• etc...

C'est reparti pour un tour...

Fini les vacances, c'est la rentrée... Voici les nouveautés pour le cours d'info de 2A...

• Les cours en amphi seront fait en 1/2 promo' (et seront donc dispensé deux fois) pour permettre une meilleure interaction prof'/étudiants.
• Cela augmente donc mon nombre d'heures de cours, en compensation les TD du semestre 2 seront fait par un vacataire.
• Les TD seront mis en ligne sur ce blog à l'avance (donc plus d'excuse pour ne pas avoir préparé les TD à l'avance ! )

Nous espérons bien sûr que ces modifications amélioreront le taux de réussite.

mise à niveau TD2

Suite de la mise à niveau informatique. La séance précédente nous avons mis en oeuvre tous les concepts vu lors du séminaire de pré-rentrée en faisant un simple jeu de pendu... Maintenant nous allons apprendre de nouveaux concepts, comme celui de pointeur et d'allocation/désallocation mémoire (manuelle)...

• Nous allons voir ensemble le support de cours, pages 6 -> 10.
• Modifiez votre programme de jeu de pendu, de manière à faire les allocation "manuelles" (c'est à dire avec malloc et free)
• Laissez le code précédent de coté, et suivez  ce tutoriel de l'outils Valgrind qui permet de surveiller l'utilisation de la mémoire.
• Maintenant que vous avez compris comment fonctionne valgrind, utilisez le sur votre programme de jeu de pendu pour vérifier si ce que vous avez écrit précédemment est bel et bien correct.

TD 8

Encore des exercices sur les ABR...

La programmation récursive est encore difficile pour certains d'entre vous (et c'est normal car c'est pas très intuitif), nous allons donc encore réaliser un certain nombre d'exercices qui ne sont réalisable que récursivement. Pour implémenter et tester ce fonction vous prendrez votre code qui fait des ABR stockant des nombres entier.

• Faire une fonction qui affiche uniquement les feuilles (=les noeuds n'ayant pas de fils) d'un arbre.
• Faire une fonction qui compte, uniquement, les feuilles d'un arbre.
• Faire une fonction qui "inverse un arbre", les petites valeurs doivent alors se retrouver à droite et les grandes valeurs à gauche. Faites un affichage préfixe avant et après l'appel à la fonction d'inversion pour vérifier que cela fonctionne.
• Faire une fonction qui prend 2 arbres en paramètre (t1 et t2) et qui ajoute tous les élément de t2 dans t1 (t2 ne doit pas être modifié!).
• Faire une fonction qui teste l'égalité stricte entre deux arbres. C'est à dire qu'ils contiennent à la fois les même valeurs, mais aussi que ces valeurs sont placées aux même endroits. Cette fonction retourne 1 si les arbres sont identiques, 0 sinon. C'est typiquement la fonction que vous devriez utiliser pour tester vos fonctions de sauvegarde et de chargement d'arbre sur fichier faite au TD7.

Une fois que ces fonctions sont terminées (et bien testées) vous pouvez les re-implémenter sur votre code qui gère des ABR stockant des chaînes de caractères.

TP réseaux neuronaux

Voici le sujet de TP du cours "neural computing". Il s'agit d'identifier, grâce à un réseau de neurones, la langue utilisée dans des messages courts (des tweets)... Date limite de rendu 03/03/14 23h59. (Attention -1 point par jour de retard).

Ce TP peut etre réalisé seul ou en binôme (mais pas de trinôme!).

[update!] Vu que certains d'entre vous galèrent pour l'étape de paramétrisation (passer du texte à des valeurs numériques utilisable dans un réseau de neurones). Je vous donne une base de code supplémentaire ("freq.c") attaché à cet article. Notez que si vous utilisez l'apprentissage supervisé (avec FANN) il vous faudra encore "normaliser" les données (c'est à dire les "étaler" dans [-1;+1]).

Vous pouvez aussi faire de l'apprentissage "non-supervisé" comme vu dans le TD3, dans ce cas vous n'avez pas besoin de faire l'étape de normalisation, et le résultat de l'apprentissage étant plutôt visuel, cela peut être vu comme plus simple.

Annexe(s) :

test_2.c :: 910 B

tweets.tar.gz :: 2.58 MB

eval.txt.gz :: 633.33 KB 

sujet_TP.pdf :: 130.33 KB

freq.c :: 872 B

mise à niveau TD3

Nous avons vu comment gérer "manuellement" la mémoire, et aussi comment débugger les problèmes mémoire. Maintenant nous allons voir ensemble les limitations des structures de tableau, et comment aller au delà...

Préambule : vous utilisez valgrind (débugger mémoire) pour toute la suite de ce que vous programmerez!

• Nous allons voir ensemble Le support de cours, p. 16 -> 22 , qui décrit les structures de listes, permettant de s'affranchir de certaines limitations des tableaux.
• Pour mettre en pratique ce nouveau concept, nous allons implémenter une liste simplement chaînée contenant de simples nombres entiers.
• Écrivez le le nouveau type, nécessaire à la création d'une telle liste.
• Écrivez la fonction d'insertion en début de liste(et faites y appel dans votre main)
• Faites plusieurs appels (pour insérer plusieurs valeurs) et écrivez la fonction d'affichage. Utilisez la, que constatez vous ?
• Écrivez la fonction de désallocation (et utilisez la), vérifiez avec Valgrind que la désallocation fonctionne bien.
• Écrivez une nouvelle fonction d'insertion qui réalise l'insertion en fin de liste (et non en début comme précédemment). Testez cela en insérant plusieurs valeurs et en utilisant la fonction d'affichage.

En travail personnel vous pouvez appliquer la même méthodologie pour aborder les listes un peu plus complexes. Tout d'abord en modifiant le type de donnés stockées. Remplaces les entiers par des chaîne de caractères. Puis étudiez les listes chaînées un peu plus complexe, comme les listes circulaire, les listes doublement chaînées, etc...

Bilan du TP "neural computing"

Quelques informations au sujet du TP. Les meilleurs performances, les moins bonnes, là où vous m'avez épaté, et là où vous auriez pu faire un peu mieux. Je donne aussi quelques hypothèses pouvant expliquer la baisse de performance de prédiction que certains d'entre vous ont pu constater sur leur système. Je vous donne aussi le fichier de label (les réponses attendues) que beaucoup d'entre vous m'on demandé...

Le sujet était d'identifier,automatiquement, la langue d'un message. Il s'agit d'un problème classique en "machine learning" (apprentissage, en français.), et qui est souvent traité par des réseaux neuronaux.

En pratique la formulation du TP était notablement plus difficile que la version classique du problème, car les messages étudiés étaient des Tweets, donc des messages court, et forcément plus le message est court plus le problème est difficile. De plus ces messages pouvaient contenir des URL qui sont très souvent raccourcies et donc ne reflètent pas les statistiques du langage. Une autre difficulté est que l'information des langages est même parfois fausse, ce qui peut évidement gêner l'apprentissage (en particulier les allemands qui semblent tweeter très souvent anglais... Mais ces difficultés étaient les même pour tous.

Les résultats en chiffres :

Puisqu'il y avait 7 langues à prédire, une prédiction aléatoire donnerai environ (1/7*100= 14,29%). Seul 4 rendus était à ce niveau. Un rendu était à 90,67% !! , et 9 étaient > 80%, et les 35 autres se situent entre ~20% et 80%. C'est pas mal du tout vu la difficulté du problème, et le temps que vous aviez à consacrer à ce TP. Et surtout, c'était votre premier projet en "machine learning".

Je suis donc globalement satisfait du travail. Je note cependant un manque de rigueur. Presque 1/3 d'entre vous on perdu au moins 1 point pour non respect des modalités de rendu, ou l'oubli de donner une information demandée pour le rapport, ou on eu besoin de soumettre plusieurs fois leur prédiction par manque de vérification.

Pour beaucoup les performances annoncées dans le rapport était assez proche de celles que j'ai constaté sur les données d'évaluation. pour ceux qui ont perdu plus de 10% voici une liste d'hypothèses :

• Certain n'avaient pas bien compris le principe des test (quand la matrice de confusion du rapport était fausse) dans ce cas il s'agissait probablement de sur-apprentissage (de l'apprentissage "par coeur").
• Les retweets , si ils ne sont pas supprimés, peuvent fausser l'estimation des performance. En effet, si le tweet original se trouve dans la base d'apprentissage, et si les retweets se trouvent dans la base de test, ils seront naturellement (trop) bien identifiés. En gros ça revient à avoir une base d'apprentissage et une base de test non-disjointe. La base d'évaluation étant faite plusieurs jours après, à priori, elle ne contient pas de retweet provenant de la base que je vous avait fournit, d'où la baisse de performance. Pour être exact, il s'agirait plutôt d'une sur évaluation des performances sur les tests, que une baisse sur le fichier d'évaluation.
• Après discussion avec certains d'entre vous qui sont venu me voir, j'ai identifié que l'étape de normalisation était parfois mal comprise. Voici les deux mal-entendus que j'ai identifiés :
  • La normalisation doit de faire par colonne et non par ligne. C'est à dire qu'il faut rechercher, pour chaque neurone d'entrée, une valeur min et max. Certain l'avaient apparemment fait par ligne (et donc avoir un min et un max par tweet.)
  • La recherche des min et des max, doit être fait une seule fois, sur la base d'apprentissage. Il faut reprendre les même valeurs pour normaliser sur la base de test et d'évaluation. Pour vous en convaincre imaginez que vous n'avez qu'un seul tweet à évaluer, vous sentez bien que vous n'allez pas re-estimer les min et max sur un seul tweet. Gardez en mémoire que vous devez présenter des données qui ont eu le même traitement que la base d'apprentissage. Si vous re-estimez les min et max, vous ne présentez donc plus des données conformes à ce qu'on à présenté lors de l'apprentissage. Et donc les performances sont moins bonnes.

Certains étudiants on constaté qu'il y avait, quelque part dans le fichier d'évaluation, un caractère "retour à la ligne" non standard, et selon les manières de l'interpréter cela pouvait générer un décalage. Ce décalage pouvait évidement faire chuter les performances mesurées, et cela d'autant plus que ce décalage était vers le début du fichier. Rassurez vous, j'ai gérer le problème, j'ai tout simplement calculer les 2 cas (avec et sans le décalage) et j'ai pris la configuration qui donnait le meilleur résultat.

Pour finir, je suis content de voir que plusieurs personnes m'ont demandé le fichier de label, c'est à dire la réalité des prédictions que vous avez faites. C'est bien de s'intéresser au fond des choses, et pas seulement s'arrêter à la note. J'ai donc attaché à cet article la version compressée du fichier de labels.

Annexe(s) :

label.txt.gz :: 7.71 KB

TD 9

Nous avons 2 séances, nous allons faire des exercices sur les ABR, et ensuite nous allons utiliser la librairie Glib pour utiliser des AVL (arbres équilibrés).

Utilisez votre code de TD gérant des arbres binaire de recherche (ABR) stockant des entiers. Réalisez les fonctionnalités suivantes :

• Une fonction permettant de tester l'inclusion d'un arbre dans un autre. Typiquement est-ce que l'arbre T1 est inclu dans l'arbre T2? Cela revient à poser la question : est-ce que tous les éléments de T1 sont présents dans T2 ? (indépendamment de leur position dans l'arbre).
• Une fonction permettant de tester l'égalité « non-stricte » entre deux ABR : c'est à dire qu'ils contiennent les même éléments , mais pas forcément placés aux mêmes endroits. Soyez malin, cela peut s'écrire de manière très courte.
• Une fonction d'élagage c'est à dire enlever toutes les feuilles d'un arbre. Par exemple, si on créé un ABR où l'on insère ces données : 50, 25, 15, 75, 5, l'élagage doit supprimer (et désallouer) les éléments 5 et 75.

La programmation des AVL (ou arbres équilibrés) est trop longue à mettre en oeuvre en TD, nous allons donc utiliser une librairie qui propose ce genre de fonctionnalités. Cela sera l'occasion de voir comment on fait pour utiliser une librairie extérieure au C. En pratique, dans un contexte professionnel, vous ne reprogrammez pas les structures de données de base mais vous utilisez des structures déjà existantes, et si besoin vous les adapterez.

Tout d'abord, trouvez dans la documentation,

• comment compiler avec cette librairie. La librairie est déjà installée sur les ordinateurs des salles de TP, vous n'avez donc pas besoin ni de télécharger ni de compiler ou installer cette librairie. Pour tester la compilation commencez par un programme qui inclu les "header" de la libraire Glib (#include < glib.h >) et qui contient un "main" et c'est tout, ensuite essayer de le compiler. (Si vous voulez travailler avec votre ordinateur personnel vous trouverez aussi à cet endroit comment compiler et installer la librairie)
• Ensuite, identifiez la partie de la documentation qui parle des structures de données, plus précisément des arbres équilibrés.
• Dans le "main" déclarez une variable du type arbre équilibré. Testez la compilation.
• À l'étape précédente on a simplement déclaré une variable de type arbre, l'arbre n'est pas encore prêt a recevoir des données. Maintenant il faut trouver dans la doc' une fonction qui permet de créer un arbre équilibré. Vous créerez un arbre stockant des chaînes de caractères. Typiquement on va faire un dictionnaire, les clés (keys) et les valeurs (values) sont des chaînes de caractères. Une clé est un mot, sa valeur associé est une définition. Appelez cette fonction dans votre "main" pour disposer d'un arbre équilibré correctement construit. À quoi sert la fonction de comparaison exigée pour créer un arbre (souvenez vous du TD où on avait crée un dictionnaire avec un ABR) ? Créez cette fonction, de manière à pouvoir (enfin) créer votre arbre.
• Identifiez la fonction qui vous permettra d'insérer des chaines de caractères dans votre arbre. Vos verrez qu'il y a deux informations à donner lors de l'insertion : la clé et la valeur. La clé est l'élément sur lequel sera fait la comparaison pour le classement des données dans l'arbre. La valeur est une information qui y est associée mais sur laquelle aucun traitement n'est effectué (à part le stockage bien sûr). Typiquement si on réalise un dictionnaire, la clé est le mot, la valeur est la définition. Insérez quelques couples "mots/définitions" dans l'arbre.
• Trouvez la fonction de recherche d'un élément dans l'arbre et testez la.
• Trouvez et testez la fonction de désallocation de l'arbre.
• Cherchez à comprendre à quoi correspond cette fonction de création d'arbre.
• Maintenant que vous avez compris comment gérer la désallocation vous pouvez créer un dictionnaire donc les mots et définition proviennent d'un fichier et non plus simplement écrite "en dur" dans le code.  

Débriefing du projet C des 3A

Les étudiants de 3A avaient à programmer une simulation physique permettant de faire de l'agencement de graphes. Cliquez ici pour voir le sujet. Pour expliquer la notation ainsi que pour montrer un panel de ce qui a été fait, j'ai réalisé une vidéo ... Et j'ai attaché à cet article les 6 graphes d'exemples que j'ai utilisé pour la notation.

Si vous avez moins de 6/20, vous pouvez me re-soumettre votre code mais cette fois-ci via mail (wassner@esiea.fr). Je re-évaluerai votre travail, mais la note sera plafonnée à 6/20. Je n'accepterai de re-soumission de code que jusqu'au :mardi 21 janvier minuit.

Annexe(s) :

 exemples.zip

TD 10

Après s'être fait la main avec la librairie Glib avec les arbres équilibré, nous rapidement mettre en oeuvre la compilation séparée sur un exemple, puis allons utiliser les tables de hashage de la Glib pour analyser des tweets...

Appliquez ce qu'on a vu en cours sur la compilation séparée.

• Reprenez un code de TD sur les arbres ou les listes (comme vous voulez), séparez les en ".h" et ".c". De même séparer ces codes sources en un fichier de fonctions et un fichier de main.
• Lancez "à la main" les lignes de compilation nécessaire pour compiler le tout.
• Écrivez un fichier "Makefile" pour automatiser ces étapes de compilation. Testez son efficacité à ne recompiler que ce qui est nécessaire en cas de modification d'un seul fichier.

On va d'abord se familiariser avec fonction de base des table de hashage.

• Trouvez dans la doc de la Glib la structure de donnés permettant de gérer des table de hashage
• Créez une table de hashage.
• Insérez y des valeurs à l'intérieur (choississez le type de clé et de valeur que vous voulez)
• Récupérez une de ces valeurs grâce à sa clé.
• Désallouez la table.

Maintenant que nous maîtrisons les bases, nous allons utiliser cette structure de données pour analyser des tweets (message court sur le réseau Twitter). Notre objectif va être de trouver le "tweeter fou" , c'est à dire celui qui à posté le plus de tweet. Pour cela nous allons créer une table de hashage dont les clés sont les noms des utilisateurs, et les valeurs sont des entiers qui serviront de compteur.

Faites un programme de lecture des tweets (ligne par ligne, en utilisant la fonction fgets), vous utiliserez ce fichier de texte contenant 10.000 tweets.

• Dans chaque ligne récupérez uniquement le nom de l'auteur du tweet (c'est le premier mot de la ligne).
• Utiliser ce nom comme clé et comme valeur vous stockez un pointeur sur int qui servira de compteur. Pour chaque nom, commencez d'abord par le rechercher dans le hash, s'il n'est pas présent alors l'y insérer (en initialisant sont compteur à 1). Si il est déjà présent, tout simplement incrémentez sont compteur.
• Faites un test en recherchant "@boussdu87" dans la table de hashage,et vérifiez qu'il a posté 32 tweets.
• ... ce TD est un peu long pour 2 séances... la fin de ce TD est donc repoussé au TD suivant soir le TD11...

Annexe(s):

tweets.txt :: 1.75 MB

mise à niveau TD5

Nous allons maintenant passer au programme du semestre 2 (INF2032)... Comme pour le contenu du semestre 1 nous n'auront pas le temps de tout faire : c'est une mise à niveau, pas le cours complet. Je fais le choix de laisser de coté la partie compression de données, pour nous focaliser sur la notion de graphe...

Les graphes sont une suite naturelle des structures de données. Les listes gère les structures séquentielles : il n'y a pas d'embranchement dans les listes. Ces structures permettent une gestion plus souple de la mémoire (par rapport au tableau), mais on un inconvénient, un accès lent aux au données. Les arbres permettent eux d'avoir des embranchements. Cela permet de faire des recherches efficaces en temps, tout en étant aussi souple de des listes. Il est cependant interdit d'avoir des boucles dans une structure d'arbre (cela ferai "planter" les recherches).

Dans les graphes on peut relier n'importe quelle donnée à n'importe quelle autre. Donc d'un point de vue implémentation vous verrez que cela peut etre vu comme une extension naturelle des arbres, cependant en terme d'application c'est totalement différent. Là où les listes et les arbres servent au stockage, au tri, et la restitution de données, les graphes servent à modéliser, simuler, analyser des données complexes. Les graphes sont, par exemple, très utile pour modéliser/analyser/exploiter les informations provenant de réseaux sociaux, ou pour représenter des données de type géographiques (réseaux routier, etc...).

Nous allons voir les pages 20 à 22 du support de cours du module INF2032 pour le côté structure de données.

Nous verrons ensuite le parcours en profondeur (p. 22,23) qui permet d'étudier la connectivité d'un graphe.

Nous devrons faire détour sur l'allocation de matrice INF2031  p. 10 -> 12, car c'est un des moyens classique de représenter un graphe en mémoire.      

Voici les exercices préparatoire  que je vous propose:

• Charger un graphe en mémoire sous le format demandé par le projet.
• Écrire un parcours en profondeur (pour étudier la connectivité du graphe), partant , par défaut du noeud No 0.
• Avant de commencer le projet, je détaillant le contenu du code de base "fenetre.c".
• Vous pouvez commencer a réaliser les étapes proposées par le sujet. Je ne donnerai pas de corrigé mais des aides sous forme de bout de code que vous devrez adapter. On peut espérer avoir le temps que je vous présente des solution jusqu'au point 2.4 du sujet. Pour le reste ce sera à vous de trouver...
• 

Voilà c'était le dernier cours de ce module de mise à niveau. Vous avez vu une sélection des thèmes les plus importants présentés en 2A. Vous devez maintenant vous constituer une expérience par votre travail personnel. Le projet que vous avez à faire sur la disposition de graphes dans le plan, vise cet objectif. Je vous conseil de vous mettre en binôme avec un étudiant qui à passés ses 2 premières années à l'ESIEA qui aura plus d'expérience que vous en programmation, mais qui sera content de pouvoir exploiter vos connaissance plus approfondie sur les concepts de physique utilisé pour faire l'agencement de graphes.

En cas de difficulté que vous n'arrivez pas à surmonter, vous pouvez m'envoyer un mail en précisant au mieux votre question. Vous pouvez aussi passer me voir au labo ATIS (à coté du centre de documentation).

TD 8

L'édition de graphe, suite...

Partie 1

Partant de votre code d'éditeur de graphe, nous allons implémenter le parcours en largeur en lieu et place du parcours en profondeur. Si vous n'avez pas de code fonctionnel pour l'édition de graphe vous pouvez prendre le code "GrapheExplorer.java" attaché à cet article, comme code de base (Cette classe héritant d'autres classes, vous devrez disposez de tous les fichier attaché à cet article pour pouvoir compiler ce code.).

Pour le parcours en largeur, vous allez avoir besoin d'une liste

Voyez la classe ArrayList , qui vous permettra d'avoir une liste avec toutes les fonctionnalités dont vous aurez besoin.Dans une telle liste vous ne pourrez stocker que des éléments de type objet, or dans notre code noeuds sont des int, qui ne sont pas des objets... La solution est, dans ce cas, d'utiliser la classe Integer qui permet de manipuler des entiers représentés sous forme d'objets.

Vérifiez bien que votre fonction de parcours fonctionne, et que les noeuds sont bien affichés dans un ordre correspondant à un parcours en largeur.

Partant du noeud 0, l'ordre de visite d'un parcours en largeur doit être : 0, 1, 2, 3, 4, 5, 6. (là où un parcours en profondeur ferait : 0, 1, 3, 4, 2, 5 , 6.)

Partie 2

Remplacez les représentations en tableau et matrice par des représentations en listes. Conseil : gardez vos codes fonctionnels dans un répertoire archive, car vous allez probablement passer par des étapes transitoires où presque plus rien de fonctionnera...

• Créez une classe Node qui représentera les noeuds (les attributs seront les coordonnées x,y)
• Remplacez le tableau stockant les coordonnées des noeuds, par un ArrayList de Node.
• Modifiez toutes les méthodes utilisant le tableau pour qu'elles utilisent l'ArrayListde Node.
• Créez une classe Link qui représentera les arrêtes (les attributs seront simplement une paire de Noeuds).
• Remplacez la représentation en matrice, par une représentation en liste d'arrêtes.
• Modifiez toutes les méthodes utilisant la matrice pour qu'elles utilisent l'ArrayList de Link

Avec les ArrayList, vous disposez maintenant d'une structure plus souple que les tableau. Nous pouvons donc aborder l'autre partie d'un éditeur : la suppression.

• Utilisez le bouton du milieu de la souris pour faire la suppression d'un noeud lors d'un clic. Cherchez le noeud le plus proche de la position du clic, et supprimez le de la liste. Testez cela d'abord sur des Noeuds isolé. si ce noeud est aussi présent dans un lien, il faut aussi supprimer le lien correspondant.
• Utilisez le bouton du milieu de la souris lors d'un "glissé-déplacé" pour gérer la suppression d'un lien. Pour cela il suffit de gérer les deux événements MousePressed & MouseReleased, pour identifier les deux noeuds concerné. Ensuite chercher dans la liste des arrêtes s'il existe une arrête utilisant ces deux noeuds (dans n'importe quel ordre puisqu'il s'agit d'un graphe non-orienté).
• Pensez dans les deux cas à relancer l'affichage pour que les modifications soient visible dans l'interface.
• Vérifiez que ces modifications n'ont pas affecté vos parcours (profondeur et largeur).

Annexe(s) :

GraphExplorer.java :: 920 B

BasicGraphEditor.java :: 2.26 KB

NodesEditor.java :: 1.93 KB

révision pour l'éval'

Voici les points à réviser pour l'éval' :

• Tout ce qui a été vu pour la compression de données : les méthodes, les principes de composition de méthodes, etc... .
• Tout ce que vous avez vu sur les graphes, représentations, parcours, algorithmes de mesures et d'analyses.
• Il n'y a pas de question propre à Java ni à la programmation d'interface graphique. Mais les codes demandés seront à écrire en Java (comme dans la dernière interro)'. Si vous avez bien travaillé le TP java, vous n'avez pas de révision spécifique à Java a faire.

Je vous rappelle que vous avez une archive d'anciens sujets ici.

Bon courage, et bon travail...

UPDATE : voici le corrigé en attachement à ce billet (désolé pour le retard de publication, mais j'étais à Laval hier pour une réunion recherche).

Annexe(s) :

eval_S2_2014.corrige.pdf :: 249.1 KB

TD 1

Voici le premier TD du second semestre. Nous allons faire nos premiers pas en compression de données. Le but global de cette thématique va au delà de la simple compression de donnés. J'ambitionne de vous faire entrevoir des principes fondamentaux de l'information. Pour le moment nous allons déjà revoir certaines base de fonctionnement des fichiers, et implémenter une première méthode de compression simple que nous améliorerons par étapes...

Nous allons mettre en oeuvre la compression (et la décompression) de la méthode RLE (Run Length Encoding).

• Faites un programme qui lit le flux standard et lit caractère par caractère (avec la fonction fgets).
• Modifiez ce programme de manière à ce qu'il compte les plages de caractères identiques. Par exemple si on met "AAABBBBCC" en entré, le programme doit sortir "3A4B2C".
• Créez votre fichier compressé : pour cela, faites ouvrir un nouveau fichier par votre programme mais cette fois ci en écriture, et écrivez les données compressées, octet par octet. (grâce à la fonction fwrite, notez que cela peut aussi se faire avec la fonction printf). Utilisez la redirection (>) pour enregistrer les donnés compressées dans un fichier.
• Faites maintenant un (nouveau) programme qui lit les donnés compressés (avec la fonction fread, notez que cela peut aussi se faire avec les fonctions getc ou fgetc), et qui affiche les longueurs de plages et les caractère associées.
• Modifier le programme précédent pour reconstituer les données d'origine.
• Utilisez le fichier  "betty.txt" pour mesurer l'efficacité de votre compression.
• Grâce à la commande cmp, comparez le fichier d'origine ainsi que le fichier reconstitué, et vérifier qu'il sont parfaitement identique.
• Grâce à la commande ls -l, regardez les tailles des fichiers pour mesurer l'efficacité de cette méthode de compression.
• Compresser ce fichier d'image (il s'agit d'une image dans un format non compressé). Quel taux de compression obtenez vous ? Faites la même expérience avec cette autre image . Quel taux de compression obtenez vous ? ? Pourquoi ? 

Cette méthode peut être relativement inefficace s'il y a peu de plages longueus de caractères identiques. Typiquement "ABC" devient "1A1C1B" : ça ne compresse pas, pire les données sont alors plus volumineuses... On peut alors essayer d'imaginer une méthode RLE adaptative, qui ne compresse que les zones compressible. Il faut bien sûr alors inventer un format de fichier permettant d'identifier les zones compressées et les zone non compressées (sinon on ne saura pas décompresser). On peut utiliser l'octet de valeur 0 ('\0') qui ne peut pas être un caractère valide d'un fichier de texte, ainsi cet octet (caractère) peut être vu comme un signal qui indique une zone compressée, et son absence indique qu'il n'y a pas de compression. Ainsi à la décompression le programme saura comment interpréter les différentes zone du fichier compressé.

• Faites une copie de vos programmes de compression & décompression, et modifiez les de manière a disposer d'une méthode RLE adaptative. Testez les sur le fichier "betty.txt", et voyez si cela amène à une compression plus efficace. Cela sous-entend de compresser, décompresser, vérifier qu'on a perdu aucune information, et mesurer les taux de compression obtenus.
• Avec votre nouvelle méthode essayez de compresser les fichiers d'image utilisés précédemment. Pourquoi cela ne marche-t-il pas ?

TD 11

Dans ce TD nous allons finaliser l'analyse de Tweets commencée dans le TD10 en utilisant une table de hashage...

Relisez le dernier paragraphe du TD10 concernant l'analyse de tweets....

• Modifiez votre code de manière à ce qu'il prennent le nom du fichier de tweets à analyser en argument du programme comme on l'a vu en cours (et non plus sur le flux standard stdin). Vous devrez alors utiliser les fonctions fopen etfclose pour gérer le flux de données.
• Affichez toutes les paires clé-valeur du hash. Cherchez le mot clé foreachdans la documentation. Vous allez devoir utiliser un pointeur de fonction, mais ça fait maintenant au moins 3 fois qu'on utilise ce principe, vous devriez pouvoir vous débrouiller...
• Faites une fonction qui compte le nombre de personnes qui ont posté des tweets. Pour cela modifiez votre fonction d'affichage, en utilisant la "user_data" qu'on avait ignoré à la question précédente. Cette donnée est tout naturellement le compteur.
• Modifiez votre fonction d'affichage pour trouver la valeur de compteur la plus grande parmi toutes les paires clé-valeur du hash.
• Modifiez votre fonction de manière à identifier qui est la personne qui a posté le plus de tweets. Pour pouvoir stocker à la fois le compteur le plus élevé mais aussi le nom associé, il nous faudra créer une structure de données. Cette structure regroupera un int et un char* pour stocker à la fois le compteur et le nom qui est associé.
• Une données plus intéressante que le Twittos le plus actif, est la personne la plus mentionnée dans des tweets. Pour cela on va s'intéresser au contenu des message (et ignorer le premier mot qui est le nom de l'emmetteur). Modifiez simplement ce qui est inséré dans le hash : identifiez tout les nom de compte twitter (les mots qui commencent par @...), c'est ce qui sera la clé de notre hash, la valeur reste un compteur. On pourra comme cela facilement identifier qui est la personne la plus citée dans un paquet de tweets. Cette même logique peut être utilisée pour identifier les hashtag (=mots de la forme "#...") les plus utilisés.

Annexe(s) :
tweets.txt :: 1.75 MB

TD 3

Dans ces deux séances de TD vous allez programmer la méthode de compression (et décompression) LZW telle que vue en cours. Pour vous aider dans cette tâche vous avez une archive attaché à cet article. Cette archive contient un sujet qui découpe cet ambitieux objectif en sous parties plus simples. Vous y trouverez aussi des données pour mesurer l'efficacité de cette méthode.

Annexe(s) :

TD3_LZW.zip :: 657.34 KB

TD 4

Au programme, correction de l'interro, finalisation des codes sur la notion de compression, et vos premiers pas en langage Java... (Si besoin, vous avez quelques rappels de cours proposé par Mme Hamouda).

Annexe(s) :

ESIEA L2 AA TD 4.pdf :: 278.32 KB

Cours JavaFatma2014.pdf :: 104.67 KB

interro35.corrige.pdf :: 268.38 KB

TD 6

Pendant ces 2 séances vous allez aborder les prémisses de l'interface graphique, tout d'abord avec des exemple du genre "hello world" (c'est à dire sans réel but fonctionnel). Ensuite vous construirez une interface graphique minimale pour le jeu de pendu que vous avez développé pendant les séances précédentes...      

Annexe(s) :

TD6.pdf :: 27.65 KB

TD6_fin.pdf :: 67.61 KB

TD 7

Dans ce TD nous allons voir une introduction aux graphes. Pour cela nous allons programmer un éditeur de graphe. Nous allon réaliser cela progressivement, étape par étape. Nous partirons d'un code de base "SingleNodeEditor.java", qui sera détaillé en TD. Une fois les fonctions de base d'édition terminées (création de sommets, et d'arrêtes), vous pourrez coder le parcours en profondeur.

Annexe(s) :

TD7.pdf :: 409.48 KB

SingleNodeEditor.java :: 1.48 KB

TP graphes et java

Voici le sujet couvrant la thématique des graphes, il sera à faire en Java.

Ce sujet est comporte encore quelques petites erreurs qui seront corrigé prochainement, mais son contenu actuel est amplement suffisant pour démarrer l'activité qui est la suite naturelle de ce qui à été vu dans les TD7 et TD8...

UPDATE 14/05/14 : le sujet à été mis à jour.

Bon courage et bon travail.

Annexe(s) :
 ESIEA L2 AA TP 2.pdf :: 275.9 KB

TD 5

 Dans ce TD vous allez mettre en oeuvre les bases de la conception "Orienté Objet" (O.O), c'est à dire la notion de classe d'objet, d'attribut, de méthode et de constructeur...

Annexe(s) :

TD5.pdf :: 11.32 KB

 

Tp compression de données

    L'objectif : implémenter une algorithme de compression capable de compresser des donnée de séquences d'ADN. Évidement je ne vous demande pas de chercher à comprendre ce qu'il y a derrière ces séquences mais juste d'être capable de les compresser...

Nous utiliserons le format « Fasta », c'est le plus simple : composée d'une entête d'une seule ligne, précédé du caractère « > », puis ensuite des lignes de 60 caractères sans espace composée. Attention les séquences contiennent principalement les caractères « a,c,g,t », mais pas seulement!... On verra en TP pourquoi... Voyez le fichier d'exemple « seq.fas » attaché à ce billet. Je vous conseille la méthode LZW en langage C, telle qu'on l'a vue en cours ensemble. Vous pourrez adapter cette méthode selon votre intuition. L'objectif de ce TP (en plus d'implémenter un algorithme de compression) est de tester votre autonomie, je donnerai donc quelques indices sur la méthode LZW et son implémentation en C, mais bien moins et bien moins détaillé que ce j'ai pu faire jusqu'à présent. Je veux que vous arriviez par vous même à organiser votre code, et à mettre en place vos stratégies de débuggage/tests. D'ailleurs, à ce propos, je vous conseille fortement de commencer par des fichiers d'exemple extrêmement simple (comme par exemple les données utilisées pour l'exemple dans le support de cours), et seulement une fois que ça fonctionne,alors, utiliser les fichier d'ADN pour tester plus a fond la méthode et surtout pour essayer d'améliorer la compression sur ce type de données.

Note importante : vous pouvez vous inspirer de méthodes déjà existantes et vous pouvez échanger vos idées entre vous, par contre vous devez tout coder vous même. Tout « copié-collé » venant d'un camarade ou d'internet est strictement interdit!

Format exigé et modalités de rendu

Votre programme doit prendre 3 paramètres et dans cet ordre :

• « -c » ou « -d », respectivement pour signaler si vous voulez faire de la compression ou de la décompression
• le nom du fichier d'entrée
• le nom du fichier de sortie

exemple : pour compresser le fichier « seq.fas » dans un fichier appeler « seq.lzw », l'appel devra être comme ceci :

         ./monProgramme -c seq.fas seq.lzw

pour retrouver le fichier original dans « seq1.fas » :

         ./monProgramme -d seq.lzw seq1.fas

Votre programme sera évalué par un script, si vous ne suivez pas ces consignes votre note aura de grandes chance d'être 0 même si votre programme est correct....

Les modalités de rendu sont :

• Un seul et unique fichier C , dont le nom est la concaténation des noms du binôme
• Dans le mail d'envoi vous mettrez clairement les noms du binôme et quelques mots pour expliquer votre méthode (si vous avez fait quelque chose de différent de la méthode LZW, ou ce que vous aurez ajouté à cette méthode).
• Vous utilisez le système d'accusé réception, pour vous assurer la bonne réception du message (ne comptez pas sur moi pour le faire pour vous.)
• Date de rendu : lundi 18 mai, attention la dernière séance de TP sur le sujet sera la semaine précédente, je vous laisse le week-end pour finaliser votre travail. Le lundi 18 nous entamerons déjà le second TP du module, en Java.

Tout manquement à ces modalités pourra vous coûter des points, merci de les respecter, c'est ce qui va me permettre de pouvoir corriger rapidement...

Évaluation du travail

Il faut que la compression se fasse sans perte (j'utiliserai la commande unix « cmp » pour vérifier), et évidement vous devez arriver à compresser puis décompresser un fichier sans perdre un seul caractère (ni en ajouter). Ne donner qu'un programme de compression sans décompression amènera à la note 0 (et pas 10!). Le taux de compression que réalisera votre programme sera le point principal de la notation. Notez cependant que l'encombrement mémoire sera aussi évalué (taille que le programme occupe en mémoire), ainsi que la vitesse d'exécution. Comme à chaque fois, j'utiliserai valgrind pour détecter les erreurs et fuites mémoires (ce qui vous coûtera beaucoup de points si vous négligez cet aspect de la programmation).

Notez aussi que j'utiliserai d'autres fichiers d'ADN que celui d'exemple pour évaluer votre programme, ne vous « spécialisez » donc pas trop sur celui là...

Remarque : J'ai programmé une version sur 16 bit (en utilisant des « unsigned short int »), qui fait ~130 lignes et qui réduit la taille du fichier « seq.fas » d'environ 57% ,et en n'utilisant ~500 ko de mémoire (cette information est donné par Valgrind à la fin de son exécution). Ce programme s'exécute en moins de 5 secondes avec Valgrind (et moins de 2 secondes en exécution normale). Tout ça pour dire que ce n' est pas excessivement compliqué. Ces chiffres donnent une aussi une base de référence. Je pense que vous pouvez faire mieux.

Annexe(s):

seq.fas  :: 12.95 KB

 

Baldr l'outil anti-fraude anti-plagiat

Ce billet présente un logiciel détecteur de fraude. Ce programme à été réalisé avec des étudiants (voir ici le premier billet décrivant le projet). Le type de fraude dont on parle est une fraude typique des TP d'informatique ou de TDAO (Travaux Dirigé Assisté par Ordinateur, en math' par exemple), en un mot : toute activité dont le résultat est un fichier informatique utilisé par un programme. La fraude consiste à copier le travail d'un autre étudiant et de le "maquiller" (faire des éditions qui changent l'allure du programme mais pas son fonctionnement.)

News 1 : le "challenge Loki" vous propose d'essayer de défier Baldr...

News 2: Voyez ici la vidéo d'une présentation d'introduction à la problématique du plagiat de code et à Baldr en particulier.

En voici les étapes clés :

• le chargement des fichiers à analyser
• lancement de l'analyse
• affichage de l'histogramme des distances calculées entre les fichiers
• repérage d'un "pic" de distance faible sur l'histogramme
• recherche dans la matrice de distance du couple de fichiers donnant lieu au pic de faible distance (c'est à dire la case la plus rouge)
• ouverture de Kompare pour confirmer la fraude.

Pourquoi ce type d'activité pédagogique est-il sujet à fraude ?

• La fraude est alors une action « simple et apparemment anodine » : il suffit de reprendre le fichier d'un camarade, et éventuellement de le modifier un minimum pour que la ressemblance ne soit pas trop flagrante...
• L'évaluation du travail ne passe pas forcément par une lecture humaine du fichier. C'est souvent via un programme que le travail effectué est évalué. Les étudiants pensent alors avoir moins de chance de se faire attraper. Exemples :
• Les programmes via des langages classiques : C, java, etc...
• Les fichiers d'outils comme matlab, scilab, ou mathematica.
• Les tables de base de données.
• ...

Tous les travaux de ce type seront évalués en les utilisant mais sans forcément lire le contenu. Ainsi, si l'apparence (ce que l'on voit quand on utilise le fichier) est changée on peut ne pas détecter une fraude lors de la correction. D'ailleurs même si on lit les fichiers pour regarder en détail le travail effectué, il est très difficile de se souvenir du cinquième fichier traité et être capable de voir qu'il ressemble au 27 ième surtout si les fraudeur auront tout fait pour le rendre apparemment différent.

Pourquoi est-ce qu'on peut détecter ces fraudes ?

Tout d'abord par ce que ceux qui cherchent à frauder sont en général mauvais, sinon ils n'auraient que peu de raisons de le faire... Cela implique que les modifications que les fraudeurs vont apporter au fichier copié sont relativement simples, car sinon il y a le risque que le fichier ne « fonctionne » plus (typiquement le programme rendu ne compilera plus ou bien « plante » à l'exécution) . Même si ces modifications sont visuellement efficaces pour masquer la copie, le fond, le sens, lui reste le même, et par chance c'est typiquement ce que la distance informationnelle mesure.
Pour une description de la technique de mesure de distance informationnelle, je vous conseille de lire cet article. Il est très bien écrit et tout à fait abordable, c'est cet article qui m'a donné l'idée de ce projet. Mieux encore, lisez ce livre de Jean-Paul Delahaye sur la notion de complexité, il est tout simplement génial.
Pour affiner les système on peut même imaginer comparer les fichier exécutable (au lieu des sources) pour être encore plus indépendant des commentaires, noms de variables , et bel et bien comparer les algorithmes...

Ce que le logiciel fait, et ce qu'il ne fait pas

Ce que le logiciel fait

Il mesure la similarité entre les fichiers rendus. Pour cela il faut d'abord spécifier la liste des fichiers à analyser, cela se fait en cliquant sur le bouton « + » dans la partie gauche de l'interface.

Une fois les document sélectionnés, cliquez sur le symbole ∑ pour lancer l'analyse ...

La barre de progression s'anime alors, une fois l'analyse terminée un histogramme est affiché:

Cet histogramme est calculé pour donner une idée de la distribution des distances entre les fichiers. L'axe X représente toutes les distances possibles. L'axe Y représente le nombre de paires de fichiers ayant cette distance. Le « slider » en dessous permet de modifier le nombre de classes de l'histogramme (= la largeur des barres).
Note : la distance utilisée est comprise entre 0 et 1, 0 signifie que c'est les mêmes fichiers, 1 qu'il sont totalement différents.
L'histogramme permet de rapidement se faire une idée sur la distance moyenne entre les fichiers, ce qui est un paramètre important dans la mesure où un niveau de similarité « minimal » est inévitable dans la mesure où :

• Tous ces fichiers visent le même objectif (tous les étudiants avaient le même sujet)
• Ils ont appris avec le même professeur et se sont potentiellement entraidé
• Le sujet comporte peut-être un fichier de base servant comme point de départ (c'est le cas sur l'exemple utilisé ici). Ainsi

Sur cet exemple la distance la plus probable entre 2 fichiers est environ de 0.75, ce qui est différent de 1 donc les fichiers se ressemblent tous un petit peu, ce qui est normal au vu du contexte. Par contre on remarque un pic vers la distance 0.46 qui lui semble relativement éloigné du reste de la distribution (il est fort probable qu'il s'agisse d'une fraude)...
Lors de la création de l'histogramme une matrice de distance a aussi été affichée :

Les lignes et le colonnes représentent les fichiers, donc chaque case correspond à une comparaison de deux fichiers. Plus la case est verte plus les fichiers sont éloignés, plus la case est rouge plus les fichiers sont proches. La valeur à l'intérieur de chaque case est la distance multiplié par 10 (donc une valeur entre 0 et 10), il s'agit la simplement de rendre les valeur plus facile à lire.
Note la zone de texte au dessus de la matrice est une zone ou vous pouvez prendre des notes, notes qui seront bien sûr sauvegardées au moment ou vous sauvegarderez le résultat de votre analyse.
On va donc naturellement commencer notre recherche par les cases rouges (celle qui correspondent aux similarités les plus fortes.) Vous pouvez choisir l'applicatif de comparaison qui est automatiquement lancé lors d'un double clic sur une case de la matrice. Cela ce fait via le menu « options » -> « préférences ». Deux applicatifs sont demandés : celui à utiliser lors d'un double clic sur la liste de fichier et celui correspondant au double clic sur une case de la matrice. Dans la mesure ou il s'agit ici de fichiers de code j'ai donc configuré Baldr de manière à ce qu'il lance Kompare (un comparateur de code) lors d'un double clic sur la matrice.
Voilà le résultat de la comparaison de code (avec Kompare) correspondant à la case entourée sur l'image précédente.

Il ne faut pas bien longtemps pour constater que la similarité, ici , correspond bien à une fraude...
Vous avez probablement noté la présence d'un bouton, près de la matrice permettant de passer d'une vue « globale à « locale ». La vue « locale » est la plus adaptée pour détecter la fraude. La vue « globale » elle est plus adaptée pour analyser la globalité des fichiers. Elle permet, entre autre de faire ressortir les fichiers qui sont le plus éloignés des autres. Dans l'image ci-dessous il s'agit des quatre ou cinq dernière colonnes qui sont manifestement plus verte que les autres... Il se trouve que ce sont les 4 meilleurs notes du TP. C'est aussi ceux qui, en général, ont les meilleures notes sur le cours théorique correspondant à ce TP !

Cet outil peut donc permettre à la fois de découvrir de la fraude mais aussi de faire ressortir l' « exceptionnel ».
Note : la case rouge correspond à la fraude précédemment découverte, comme souvent les fraudeurs demandent leur code à de très bons étudiants, qui justement codent différemment des autres, ce qui rend la fraude encore plus facile à repérer...
Conclusion : en 5minutes on a identifié une fraude et cinq travaux exceptionnels sur une liste de 30 fichiers. Si on mettait une minute pour comparer « à la main » deux fichiers (il faut clairement bien plus) il faudrait alors environ 7 heure et demi pour faire l'analyse complète !

Ce que le logiciel ne fait pas

Évidement ce système n'a pas pour but d'être parfait, et il ne le sera certainement jamais. L'objectif est de rendre l'acte de fraude suffisement compliqué et dangereux pour qu'il ne vaille pas la peine d'être tenté. Grâce à ce système on détecte plus de fraude, cela devient donc naturellement plus dangereux de frauder. C'est plus compliqué aussi car les opérations de masquage de base sont très facilement identifiées. Pour espérer passer au travers du système il faut mettre en place des stratégies bien plus compliquées que la difficultés des TP demandés.
Il est à noter que ce système ne fait que donner des indications. La détection de fraude est au final faite par l'utilisateur. Le système ne fait que porter à l'utilisateur les couples de fichier ayant une ressemblance « étrange »... Cela veux dire que les résultats doivent être interprété dans leur contexte. C'est en particulier le cas, si un fichier de base ,commun à tous les rendu de projet, est donné pour le TP... Bien sûr le programme aidera à identifier les paires de fichiers « trop » similaires mais ne dira pas quel fichier est le fichier original...
En pratique, ces deux points que ne traite pas le logiciels :

• s'agit-il vraiment d'une fraude ?
• qui à fraudé sur qui ?

sont généralement les plus simples à élucider par l'expertise du professeur, à la fois sur la matière enseignée, et sur les étudiants encadrés...
Attention :

• Baldr ne recherche que les similarité à l'intérieur d'un groupe de fichier. Le plagiat via internet ne sera pas détecté (sauf si il sont plusieurs à prendre la même source).
• La méthode utilisant la notion de compression de donnés, elle ne marchera probablement pas sur tout type de fichier utilisant (directement ou non) des données (déjà) compressées.
• En cas de rendu composé de plusieurs fichiers, une simple concaténation des fichiers provenant d'un même projet étudiant, permet de faire l'analyse comme si il s'agissait d'un seul fichier.

Téléchargement

Le logiciel est disponible gratuitement en téléchargement sur sourceforge.