samedi 26 septembre 2009

Challenge "Reverse Shredder"

Pour illustrer le cours sur les listes chaînées, je propose un challenge de reconstruction de documents détruits.
(Il y a ici un article plus récent sur ce sujet)
 
Pour commencer ce challenge je propose uniquement des données de "prise en main" du probleme :
  • 2 documents ("TP 1 &2 .pdf") explicant comment voir le probleme de reconstruction de document comme un probleme de liste (il s'agit des 2 premiers sujets de TP de l'an dernier, une bonne part de ces fonctions vous sont donnée ici .)
  • "reverseShredderBasics.c" : les fonctions C de base pour charger en mémoire les information correspondant aux bandelettes (ou "shreds")
  • "buildPicture.pl" un programme vous permettant de reconstituer une image en fonction d'une liste de nom de bandelette (pour visualiser votre proposition d'arrangement de bandelette). Il est expliqué dans les fichiers "TP.pdf" comment s'en servir (attention cependant les chemins des fichiers seront different que dans l'exemple presenté, mais le fonctionnement de base reste le même.)
  • les données du probleme les "shreds" dans le fichier "shreds.tar.gz".
Tous les fichiers donnees ici doivent etre dans le même répertoire pour que les différents programmes
fonctionnent correctement.

Ces fichiers sont dans la rubrique téléchargement dans la rubrique INF2031.
Ce sera a vous de trouver comment comparer efficacement 2 shreds (il s'agit la simplement d'un peu d'astuce, vos predecesseur en on trouvé plein) et trouver une stratégie generale de resolution du probleme : comment reconstituer le document (il s'agit la de construire une liste correspondant a l'etat initial du document).

Vous pouvez poster ici vos questions ou remarques pour que tout le monde puisse en profiter ainsi que de la réponse.

Un fois que cette prise en main sera faite je posterai des donnés correspondant au même probleme mais dans une situation plus réaliste (reconstruction de plusieurs pages, ce qui rend le probleme bien plus compliqué...) et on aura là un vrai "challenge".
Etonnez moi !

Annexe(s) :

TP1.pdf :: 0.680 B
TP2.pdf :: 0.527 B
buildPicture.pl :: 0.000 B
shreds.tar.gz :: 1.772 B