Reformuler l'énoncé d'un problème d'algorithmique

Mathias Hiron pour www.france-ioi.org

Introduction : pourquoi reformuler ?

Un problème bien posé est un problème à moitié résolu.

Si l'on prend au mot cet adage bien connu, on peut dire que ce document décrit comment effectuer la première moitié de la résolution d'un problème d'algorithmique.

La plupart des problèmes de ce site sont décrits au sein d'une petite histoire. On vous présente une situation impliquant des personnes ou animaux, dans un monde plus ou moins imaginaire avec des règles bien particulières, que vous devez mettre à profit pour vous tirer d'affaire.

L'histoire est en général présentée (parfois volontairement) d'une manière qui cache la vraie nature du problème. Une part significative de la difficulté est donc de comprendre précisément ce que l'on vous demande sans vous laisser embrouiller par tous les détails superflus liés à l'histoire.

Pour avoir une chance de trouver la solution à un problème, il faut s'assurer de l'avoir très clairement en tête. Ceci peut paraître évident, mais l'expérience montre que très souvent, on n'arrive pas à trouver la solution, tout simplement parce-que l'on a mal compris le problème. Pour s'assurer de l'avoir parfaitement compris, il faut bien sûr le relire plusieurs fois, mais le meilleur moyen est de le reformuler en quelques phrases. Le fait de les écrire vous aide à avoir une idée bien claire et synthétique de ce qu'est le problème, et vous fournit ensuite une base solide pour votre réflexion. Ce document décrit comment rédiger cette description succinte.

L'objectif est de décrire le sujet en ne conservant que ce qui est nécessaire pour pouvoir chercher une solution.

On ne conserve de l'histoire que ce qui aide à comprendre sans trop nuire à la concision. On pourra garder les noms des objets plutôt que de revenir sur des termes génériques comme « point », « case » etc., si cela ne nuit pas à la clarté.

Écrivez cette description comme si vous expliquiez le sujet à un ami qui n'a pas lu le sujet complet. Vérifiez bien que la description suffit pour réfléchir à une solution, éventuellement en demandant les valeurs des contraintes séparément.

Cet ensemble de conseils s'applique non seulement sur le problème initial que l'on vous fournit, mais également sur les sous-problèmes ou versions simplifiées que vous aurez également à résoudre : à chaque fois que vous avez un nouveau problème à résoudre, réexprimez le comme décrit dans ce document.

Structure de la description

La structure d'une reformulation doit généralement prendre la forme suivante :

• La description des objets du problème.

  Décrivez ce que représentent les données d'entrée, indépendamment du format dans lequel elles sont fournies. Dites par exemple « On vous donne une grille de nombres strictement positifs », ou « On vous donne les coordonnées de rectangles dans le plan, et les coordonnées d'un point de départ. », etc.

  Si vous avez repéré certaines caractéristiques de l'entrée qui permettent d'en avoir une vision simplifiée, n'hésitez pas à y faire appel. Par exemple, plutôt que de dire « On vous donne un ensemble de personnes et des relations entre ces personnes, telles qu'il existe toujours une suite de relations permettant de passer d'une personne à tout autre », dites simplement « On vous donne un graphe connexe, constitué de personnes et de relations entre ces personnes », voire même simplement « On vous donne un graphe connexe », si le fait qu'un nœud corresponde à une personne n'aide pas à la compréhension du sujet.

• La description des « règles » qui s'appliquent à ces objets (si nécessaire).

  Dans certains sujets, un certain nombre d'actions peuvent être effectuées sur ou relativement aux objets d'entrée. Il peut s'agir de règles de déplacement, d'ajouts ou de suppression d'objets, etc. Lorsque le sujet implique de telles règles, il est important d'en décrire l'essence. Par exemple : « À chaque étape, le jeton peut faire un déplacement en cavalier », ou « Vous pouvez placer un bloc uniquement au dessus d'un bloc plus grand. », etc. Cette section doit contenir autant de phrases qu'il y a de règles. On peut cependant omettre certaines choses comme la description précise de ce qu'est un mouvement en cavalier si on la connaît déjà sans hésiter, ou autres détails qui n'influent pas fondamentalement sur la solution.

• Ce que l'on vous demande.

  Ce point est le plus important, car il constitue le cœur du problème. Les points précédents n'étaient que les prérequis pour pouvoir exprimer celui-ci simplement.

  Pour décrire clairement ce que l'on vous demande, exprimez-le sous la forme d'une ou plusieurs questions. Ces questions commenceront généralement par « Quel est le … ». Par exemple : « Quelle est la longueur du plus court chemin entre l'entrée et la sortie », ou « Quelle est la longueur de la plus longue séquence de somme inférieure à S », etc. Si le sujet demande un ensemble de réponses correspondant à plusieurs éléments de l'entrée, on peut l'exprimer sous la forme : « Pour chaque …, quel est le … ? ». Par exemple : « Pour chaque intervalle fourni, quelle est la somme des nombres couverts par l'intervalle ? ».

• Les détails demandés sur la solution.

  Souvent, en plus de vous demander une meilleure valeur que l'on peut atteindre, on vous demandera les différentes étapes ou décisions à effectuer pour atteindre cette valeur. Le fait de le demander n'influence relativement que peu l'algorithme et ne doit pas être mentionné dans la question principale, mais il faut malgré tout le rappeler. On pourra ajouter sous la/les questions une simple phrase du style « Afficher la direction empruntée à chaque étape ».

Ce que l'on omet dans la description

• Les valeurs des contraintes.

  Celles-ci sont primordiales pour chercher une solution efficace, mais ne sont pas nécessaires à la compréhension du problème lui-même. On les mettra donc dans une autre section : la « liste des dimensions ».

• La description des formats d'entrée et de sortie, ou d'une éventuelle API.

• Les détails dont on est absolument certain qu'ils ne changent pas l'algorithme lui-même.

Conclusion

Une fois que vous avez terminé la rédaction de ces différentes parties, relisez-le en vérifiant que si l'on ne vous avait donné que cette description, vous auriez suffisamment d'éléments pour résoudre le problème. Si ce n'est pas le cas, c'est que la description est incomplète.

Relisez ensuite une dernière fois le sujet, pour bien vérifier que rien d'important ne manque à votre description.

Dans la suite de la réflexion, vous reviendrez régulièrement sur cette description. Assurez-vous donc qu'elle soit bien évidence et parfaitement lisible sur votre feuille, quitte à la réécrire entièrement si elle contient trop de ratures.