Arthur Charguéraud et Mathias Hiron pour www.france-ioi.org
Ce document a pour but de vous aider à résoudre à un sujet d'algorithmique efficacement. Il décrit une méthode d'approche en plusieurs étapes qui permet de partir du sujet et d'arriver à un code juste implémentant la solution. Les conseils que vous trouverez dans ce document ne sont pas spécifiques aux concours : ils s'appliquent dès qu'il s'agit de trouver et/ou de programmer des algorithmes.
Annexe : Organisez-vous
La première chose à faire consiste à bien lire le sujet, et entièrement ! Cela peut paraître évident, mais l'expérience montre que certaines personnes impatientes de résoudre le sujet passent à côté de quelques détails importants. Pour éviter cela, il faut donc prendre son temps pour lire le sujet, et ne pas hésiter à le relire plusieurs fois pour bien tout comprendre et ne laisser aucun détail de côté.
Ce qui est important :
Reformuler un sujet, c'est ce que l'on fait naturellement lorsqu'on veut expliquer le sujet à quelqu'un qui ne l'a pas lu. En général, quelques courtes phrases suffisent lorsqu'on utilise des termes algorithmiques précis, comme « graphe », « plus court chemin », « dag » (graphe orienté sans cycle), « sous-ensemble », etc. Voici quelques exemples de reformulation de divers sujets :
Il est absolument crucial de vérifier que la version reformulée est bien équivalente au sujet. Il ne faut oublier aucun détail, et s'assurer que la version reformulée n'est pas une généralisation ni une simplification du sujet.
Il est très important de se concentrer jusqu'au bout sur la compréhension totale et sans contresens du sujet. Il faut s'interdire d'essayer de deviner la totalité du sujet alors qu'on en a lu que la moitié, car c'est la meilleure façon d'interpréter de travers ce qui est écrit dans la seconde moitié. Dès que vous avez fini de lire la description, lisez rapidement les contraintes, vérifiez votre compréhension du sujet sur l'exemple fourni en l'étudiant attentivement, puis revenez sur les contraintes pour les apprendre par cœur. Essayez autant que possible de ne pas laisser votre esprit dériver vers la recherche d'une solution alors que vous n'êtes pas encore certain de rechercher sur le bon sujet !
Vous avez lu et compris le sujet, puis vous l'avez reformulé le plus simplement possible, maintenant il faut le résoudre. Chercher comme ça dans votre tête jusqu'à obtenir une solution complète et efficace n'est pas le moyen le plus efficace de procéder sur des sujets d'algorithmique difficiles.
La première étape pour chercher un algorithme consiste à se demander comme on ferait soi-même, pour résoudre le problème posé à la main. Comment cela peut-il aider ? Le cerveau humain est très intelligent (en tout cas par rapport à une machine) donc il a de bonnes chances de trouver une manière juste de résoudre le problème, et puis aussi il est plutôt flemmard en général, et il trouvera donc naturellement une méthode efficace pour résoudre le problème. Une solution juste et efficace, c'est exactement ce que l'on cherche !
Résoudre des exemples à la main sert même à beaucoup plus que faire sortir des idées. Pour résoudre des exemples, il faut bien commencer par générer des exemples. Pendant cette phase, on commence souvent par générer de tout petits exemples qui seront les cas limites, et on repère aussi quels vont être les pires cas à résoudre. Ensuite, le fait d'avoir des exemples entièrement résolus à la main permettra de vérifier que l'algorithme que l'on propose est juste, et servira plus tard à tester son implémentation.
En résumé, résoudre des exemples sert à :
Ce qui est difficile dans cette étape, c'est de générer des exemples intéressants. Ces exemples doivent être :
On regroupera un jour dans un document des illustrations de résolution d'exemples à la main.
Sur des sujets compliqués, vous ne trouverez généralement pas la solution en ne faisant que résoudre quelques exemples. Attention, cela ne veut surtout pas dire qu'il faut sauter cette étape de résolution d'exemples à la main. L'objectif est de ne pas rester bloqué sur le problème. Pour aboutir à une solution qui marche, il n'y a pas de secret, il faut s'y prendre méthodiquement.
Tout cela est détaillé dans la méthode de recherche d'un algorithme, dont voici le résumé des points :
Rappel : appliquez cette méthode à tous les sous-problèmes rencontrés.
Une fois que vous avez décidé d'un algorithme à programmer pour un problème donné, ne vous jetez pas sur votre clavier pour le coder aussitôt. Entre avoir l'idée de l'algorithme en tête et savoir quel est le meilleur moyen de le programmer, il reste du travail. Si vous commencez directement à taper du code, vous risquez de vous perdre dans les détails et d'obtenir quelque-chose de trop compliqué, ou d'oublier certains points. Un même algorithme peut s'implémenter de nombreuses manières différentes, qui peuvent être plus ou moins difficiles à programmer, et surtout plus ou moins propices à l'apparition d'erreurs.
Pour avoir les idées claires au moment de l'implémentation et écrire votre programme d'une manière simple, en réduisant ainsi les risques de bugs, il est important de passer un certain temps à réfléchir sur papier à la manière dont vous allez organiser votre code. Pour ce faire, un moyen très efficace consiste à commencer par écrire le pseudo-code de votre algorithme. Le pseudo-code d'un algorithme est une version allégée de son implémentation. En se contentant des éléments essentiels du programme et en ignorant les détails spécifiques au langage, ou les parties évidentes, le pseudo-code permet de travailler efficacement sur la structure du programme et sur les points importants comme certaines limites ou les formules mathématiques utilisées.
Le pseudo-code étant beaucoup plus court que le programme complet, on peut en écrire plusieurs versions successives, de plus en plus simples, sans perdre de temps. Une fois que l'on a trouvé la manière la plus simple d'organiser son programme, on peut alors commencer à la programmer avec sérénité, en se focalisant sur les détails de l'écriture. Découvrez les secrets du pseudo-code, à quoi il ressemble, ce qu'on y met et ce qu'on n'y met pas.
Attendez d'avoir un algorithme dont vous êtes sûr, et que vous ayez testé à la main sur quelques exemples, et vérifié qu'il soit suffisamment efficace, avant d'envisager de programmer. Programmer prend du temps, et s'apercevoir que son algorithme est faux une fois qu'il est implémenté est une perte de temps considérable. Ne commencez pas avant d'être sûr à 100 %. Bien réfléchir avant de commencer à coder vous évitera de perdre beaucoup de temps par la suite. L'expérience montre que les candidats passent beaucoup plus de temps à corriger des erreurs, de tous types, qu'à résoudre le problème lui-même et écrire la partie principale du programme.
Ne commencez pas à coder avant d'avoir vérifié que votre algorithme :
Assurez-vous aussi qu'il restera du temps pour tester et déboguer une fois que vous aurez codé. S'il ne reste pas assez de temps, choisissez une version plus simple quitte à ne viser qu'un score partiel. Il vaut mieux avoir 9 chances sur 10 d'assurer 50 % des points, plutôt que de viser 100 % des points mais de n'avoir qu'une chance sur quatre d'obtenir ce score, en laissant ainsi 3 chances sur 4 d'avoir un bug et de n'obtenir au final que 10 % des points. Personne ne peut prétendre coder sans bugs. Il faut savoir en tenir compte et limiter son ambition d'obtenir 100 % des points pour assurer en moyenne un meilleur score et progresser plus.
Lorsque vous écrivez votre code, votre objectif doit être avant tout de réduire les risques de bugs :
Toutes ces techniques visant à simplifier le code au maximum et à réduire l'apparition de bugs sont détaillées pour ceux qui codent en C++ dans le document coder proprement en C/C++.
Lorsque vous avez fini d'écrire la dernière ligne de code, vous n'avez pas pour autant terminé cette phase de code. Et oui : lorsqu'on dit « coder », on sous-entend toujours « coder juste ». Pour coder juste, il faut être comme on l'a dit attentif durant toute la phase d'écriture du code, et il faut également se concentrer à fond ensuite pour relire le code. Relisez donc votre code, plusieurs fois et de différentes manières. Il y a des techniques pour ça, visant à vérifier que vous n'avez rien oublié et que chaque ligne est correcte. Par exemple, on peut relire le code ligne par ligne, mais aussi variable par variable. Il est également intéressant de relire le code en parallèle avec le pseudo-code.
Ces techniques de relecture seront bientôt détaillées dans un document spécifique.
Il y a deux choses à vérifier. D'abord, que votre algorithme est bien correct. Ensuite, s'il est correct, qu'il a bien la vitesse et la consommation mémoire attendue. Évidemment, dans l'idéal tout est bon. Mais en pratique, il est plutôt rare que les algorithmes soient justes du premier coup. Tester sa solution ne prend de toutes manières pas beaucoup de temps lorsque tout est correct.
Pour tester son implémentation, la première méthode qui vienne à l'esprit consiste à prendre un exemple, lancer le programme dessus, regarder la sortie, et la comparer au résultat obtenu en faisant les calculs à la main. Une seconde méthode bien plus puissante consiste à vérifier que la structure de données utilisée par l'algorithme se comporte correctement au cours de l'exécution de l'algorithme. Précisons cela en distinguant deux cas possibles :
Dans les deux cas, le travail supplémentaire est relativement minime : il faut rajouter quelques lignes de code. L'intérêt de la méthode est qu'elle facilite grandement la détection et la correction d'éventuels bugs.
Voici l'ordre recommandé des exemples à tester :
Souvent, pour générer un pire cas, il suffit de générer un fichier d'entrée à l'aide d'une boucle sur un printf
. Mais pour certains sujets, c'est bien plus délicat,
et on n'a pas toujours le temps d'écrire un générateur. Dans ces cas, il faut relire une fois de plus la complexité théorique de l'algorithme, et faire confiance à la théorie.
Il y aura prochainement un document pour détailler l'écriture les lignes d'affichage pour tester.
Très important : conservez vos fichiers de tests. Ne prenez pas la mauvaise habitude d'écrire un premier test, puis de le modifier plusieurs fois en retestant à chaque fois, sans conserver les différentes versions. Conservez tous vos fichiers de tests, pour pouvoir les réévaluer rapidement si vous faites une modification. En corrigeant un bug, on en ajoute souvent un autre… Il ne faut pas perdre de temps à recréer des tests que vous avez effacés.
Lorsqu'on trouve un exemple sur lequel l'algorithme se plante, il faut absolument commencer par simplifier l'exemple qui bugue. Passez une bonne minute s'il le faut pour obtenir l'exemple le plus petit possible que le programme ne résout pas correctement, cela vous fera gagner beaucoup de temps. En effet, plus l'exemple est simple, et moins il y a de choses à afficher pour suivre l'exécution de l'algorithme pas à pas sur cet exemple.
Une fois que vous avez votre test minimal qui plante, utilisez les instructions d'affichage des structures de données pour localiser le bug. Si cela ne suffit pas, rajoutez quelques lignes d'affichage pour visualiser quels sont les choix qu'effectue l'algorithme (par exemple, quels sont les paramètres des appels récursifs), et ce en plus des données contenues dans la structure. Ce qu'il ne faut pas faire, c'est afficher uniquement les paramètres des appels récursifs : vous verrez bien qu'au bout d'un moment il y a un problème, mais vous ne saurez pas pourquoi.
Remarque : certains adorent utiliser leur débogueur préféré (par exemple gdb). Ces outils sont très efficaces pour déboguer des gros projets de programmation, mais lorsqu'il s'agit d'algorithmique ils se révèlent assez inadaptés. Le principal cas où un débogueur sert, c'est pour localiser une erreur de segmentation (accès à une adresse mémoire invalide).
Déboguer prend énormément de temps par rapport au reste. Il faut impérativement être rigoureux, méthodique et savoir s'arrêter au bout d'un certain temps même si on n'a pas trouvé le problème. Il est dangereux de passer plus de 15 ou 20 minutes à déboguer. Dans 95 % des cas, si l'on ne trouve pas tous les bugs dans les 10 minutes, c'est que le code est trop compliqué ou alors (encore pire) que l'algorithme est faux. Conclusion : il faut vraiment tout faire pour que vous n'ayez pas besoin de déboguer, c'est-à-dire faire très sérieusement toutes ces phases :
Pour bien réfléchir, il faut être dans de bonnes conditions. En particulier, il faut éviter de perdre du temps à retrouver sur quelle page on a écrit le premier exemple, il vaut mieux gommer des lignes que les rayer dans tous les sens, et c'est pratique de laisser dans la marge des petites notes pour s'y retrouver entre les différentes phases de recherche de la solution. Pour être dans de bonnes conditions :
N'ayez pas la flemme de vous mettre dans de bonne conditions, vous verrez, c'est très rentable. Si vous doutez vraiment de ces conseils, essayez au moins une fois de les suivre à la lettre pendant toute une épreuve de 5 heures, et vous comprendrez peut-être.
Si certains points vous semblent obscurs et que vous ne voyez pas trop où l'on veut en venir, envoyez un mail à entraineur[at]france-ioi.org pour nous aider à améliorer la formulation des idées dans ce document.
Si vous pensez que nos conseils ne sont pas optimaux et que votre façon de faire est plus efficace, prenez le temps d'appliquer nos conseils à la lettre sur trois sujets d'algorithmique de suite. Une fois que vous les avez essayés vraiment, si vous n'avez pas changé d'avis, envoyez-nous un mail pour nous expliquer votre point de vue. Peut-être participerez-vous ainsi à l'amélioration de la méthode !
Bon courage, et bonne progression en algorithmique !