Résumé
La consommation de ressources, telles que l'électricité ou les matériaux de fabrication des ordinateurs, s'accroît fortement avec le développement de l'économie et des activités humaines numériques. La question se pose de limiter cette consommation sans pour autant réduire des activités qui peuvent s'avérer socialement utiles ou nécessaires.En bioinformatique, nous développons beaucoup de logiciels, et parfois de nombreux logiciels pour la même tâche, la même question computationnelle. Prenez par exemple le cas de l'assemblage de génome ou celui de la localisation des lectures de séquençage (ou "read mapping" en anglais; plusieurs dizaines d'outils de mapping ont été développés et maintenus).En matière de développement logiciel, il est recommandé de développer des tests les plus complets possibles afin de s'assurer de la validité d'un logiciel. Dans le cycle de développement, nous itérons, fréquemment ou automatiquement, l'exécution des tests afin de vérifier la correction du logiciel ou d'en évaluer la rapidité. Dès lors, on peut se questionner scientifiquement sur l'utilité ou la redondance de certaines instances de tests.Considérons le cas d'un programme de recherche d'un mot dans un texte, par exemple votre génome préféré (ou bien dans la séquence de De Bruijn d'ordre /k/). Pour tester le logiciel dans toutes les situations, on peut lancer des tests sur tous les mots de longueur k, pour k égale 2, puis 3, puis 4, ..., jusqu'à par ex. disons 31 (La valeur k=31 est commune pour certaines analyses de séquences). Mais clairement le nombre d'instances augmente exponentiellement avec la longueur k, et devient vite rédhibitoire. Du point de vue de la science informatique, nous pouvons reformuler notre question initiale ainsi: Peut-on identifier des instances de test redondantes ? Peut-on générer seulement des instances de test utiles ?J'aborderai ces questions durant cet exposé en les illustrant avec deux algorithmes complexes de traitement des séquences et en montrant l'impact du choix des instances. Ce principe d'organisation des tests se nomme Partitionnement par Classes d'Équivalence. L'étude de ces classes d'équivalence pour un algorithme donné peut s'avérer complexe.Étant donnée la fréquence d'exécution des tests durant le développement logiciel, ce type d'approche peut aider à diminuer l'impact écologique de nos développements. Outre l'avantage en termes d'utilisation de ressources, l'approche par Partitionnement peut aussi nous informer sur le temps moyen d'exécution du programme sur une classe d'instances d'une taille donnée. Cette réflexion générique ouvre des pistes de recherches pour de nombreux algorithmes, pistes à même de favoriser des interactions avec d'autres domaines de la recherche en informatique.