Voir les cours et résoudre les problèmes en :
Le C est un langage de programmation impératif conçu pour la programmation système. Inventé au début des années 1970 avec UNIX, C est devenu un des langages les plus utilisés. De nombreux langages plus modernes se sont inspirés de sa syntaxe. Il privilégie la performance sur la simplicité de la syntaxe. [En savoir plus]
Le C++ est un langage de programmation impératif. Inventé au début des années 1980, il apporte de nouveaux concepts au langage C (les objets, la généricité), le modernise et lui ajoute de nombreuses bibliothèques. C++ est devenu l'un des langages les plus utilisés. Sa performance et sa richesse en font le langage de prédilection pour les concours. [En savoir plus]
Pascal est un langage de programmation impératif inventé dans les années 1970 dans un but d'enseignement. Quoiqu'encore utilisé à cette fin, l'absence de bibliothèque standard en limite son utilisation malgré une grande efficacité. Sa syntaxe a été reprise par d'autres langages plus modernes avec plus ou moins de succès. [En savoir plus]


Remarque : Les cours pour ce langage ne sont disponibles que jusqu'au chapitre 4, « Lecture de l'entrée ». Les corrections sont toutefois toujours fournies.
OCaml est un langage de programmation fonctionnel inventé au milieu des années 1990. Il permet aussi une programmation impérative ou objet. Il permet d'écrire des programmes courts et faciles à vérifier et est ainsi utilisé pour certains systèmes embarqués très sensibles comme ceux des avions. Il est utilisé dans l'enseignement en classes préparatoires aux grandes écoles. [En savoir plus]


Remarque : Les cours pour ce langage ne sont disponibles que jusqu'au chapitre 4, « Lecture de l'entrée ». Les corrections sont toutefois toujours fournies.
Java est un langage de programmation impératif et orienté objet. Inventé au début des années 1990, il reprend en grande partie la syntaxe du langage C++ tout en la simplifiant, au prix d'une performance un peu moins bonne. S'exécutant dans une machine virtuelle, il assure une grande portabilité et ses très nombreuses bibliothèques en font un langage très utilisé. On lui reproche toutefois la « verbosité » de son code. [En savoir plus]


Remarque : Pour un débutant souhaitant apprendre Java, nous conseillons fortement de commencer par JavaScool, plus facile à apprendre, bien que fortement similaire.
Java's Cool (alias JavaScool) est conçu spécifiquement pour l'apprentissage des bases de la programmation. Il reprend en grande partie la syntaxe de Java sur laquelle il s'appuie, mais la simplifie pour un apprentissage plus aisé. La plateforme JavaScool est accompagnée d'un ensemble d'activités diverses de découverte de la programmation. [En savoir plus]
Python est un langage de programmation impératif inventé à la fin des années 1980. Il permet une programmation orientée objet et admet une syntaxe concise et claire qui en font un langage très bien adapté aux débutants. Étant un langage interprété, il n'est cependant pas aussi performant que d'autres langages. [En savoir plus]

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.

Pensez à vous inscrire pour valider les cours et résoudre les exercices.