Méthode de résolution d'un sujet

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.

Étapes de la méthode

1. Lisez le sujet
2. Résolvez des exemples
3. Cherchez un algorithme
4. Pseudo-codez l'algorithme
5. Vérifiez votre solution
6. Codez votre solution
7. Testez votre solution
8. Déboguez votre code

Annexe : Organisez-vous

1) Lisez le sujet

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 :

• Ne faites surtout pas de contresens. Si vous comprenez un autre sujet que celui qui est décrit, c'est foutu. Ne commencez pas à chercher avant d'être sûr d'avoir bien compris le sujet.
• À la fin, vous devez avoir le sujet entièrement en tête. Il faut vraiment éviter d'y revenir toutes les 30 secondes pendant que vous cherchez une solution.
• Reformulez le sujet le plus simplement possible, de manière à faire le tri entre les idées clés et le texte d'enrobage.

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 :

• On a N entiers entre -1000 et +1000, et on veut en piocher un certain nombre de manière à obtenir une somme donnée.
• On a un arbre avec des poids positifs ou négatifs sur chaque nœud, et on cherche le sous-arbre dont le poids total est maximal.
• On a un graphe quelconque, et on cherche un circuit passant une et une seule fois par chaque sommet.
• On a un rectangle quadrillé, chacune des cases a une certaine altitude, le but est de calculer la plus grande zone rectangulaire tel que la hauteur de la plus basse case de cette zone et de celle de la plus haute ne diffère pas de plus de 10.

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 !

2) Résolvez des exemples

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 à :

• faire sortir des idées ;
• déterminer les cas limites (les cas triviaux et les cas pathologiques) ;
• préparer un support pour tester et déboguer efficacement.

Ce qui est difficile dans cette étape, c'est de générer des exemples intéressants. Ces exemples doivent être :

• différents, de manière à faire apparaître tous les cas possibles ;
• corrects, sinon cela peut faire perdre énormément de temps ;
• proprement résolus, pour pouvoir les utiliser facilement dans la phase de test ;
• suffisamment gros pour être intéressants, mais pas trop pour ne pas perdre de temps.

On regroupera un jour dans un document des illustrations de résolution d'exemples à la main.

3) Cherchez un algorithme

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 :

1. Lisez bien le sujet, et reformulez-le.
2. Faites la liste des dimensions du sujet.
3. Cherchez une bonne représentation visuelle du problème.
4. Générez des exemples, et résolvez+les entièrement à la main.
5. Décrivez la solution naïve, puis essayez de l'améliorer.
6. Simplifiez le problème, puis généralisez-les solutions obtenues.
7. Changez de point de vue, en envisageant les algorithmes classiques.

Rappel : appliquez cette méthode à tous les sous-problèmes rencontrés.

4) Pseudo-codez l'algorithme

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.

5) Vérifiez votre solution

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 :

• répond bien au sujet (relire le sujet !),
• est correct (en particulier qu'il résout bien les exemples que vous avez générés au début, y compris les cas limites),
• a bien la complexité que vous pensez (recalculez-la soigneusement),
• a le pseudo-code le plus simple possible.

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.

6) Codez votre solution

Lorsque vous écrivez votre code, votre objectif doit être avant tout de réduire les risques de bugs :

• Faites du code le plus simple possible, non pas en minimisant le nombre de caractères du source, mais en minimisant la probabilité d'apparition d'un bug dans le code.
• N'essayez pas d'optimiser le code, vous ne gagnerez pas plus de 10 ou 15 % des points, et vous augmenterez sérieusement le risque d'introduire un bug et du coup de vous retrouver avec 0 point. S'il vous reste du temps et que votre algorithme n'est pas dans une complexité suffisante pour prétendre avoir 100 % des points, optimiser la principale boucle de l'algorithme sera beaucoup plus rentable que de parsemer l'ensemble du code d'optimisations diverses.
• Prenez votre temps. Avec du bon pseudo-code, le code peut s'écrire en peu de temps. En prenant bien votre temps, vous mettrez peut être 5 minutes de plus, mais vous diviserez par deux le nombre de bugs dans le code, et ce sera autant de temps qui ne sera pas perdu à déboguer.

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.

7) Testez votre solution

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 :

• Premièrement, si les structures de données utilisées dans l'algorithme sont simples (tableaux), on peut les afficher en entier au fur et à mesure des itérations de l'algorithme. On vérifie ainsi qu'à chaque étape l'état de l'algorithme est entièrement cohérent.
• Second cas, les structures utilisées sont complexes, et à ce moment-là, on va les tester séparément avant de commencer à tester l'ensemble de l'algorithme. On va donc écrire du code en plus effectuant quelques requêtes sur ces structures complexes afin de vérifier que leur comportement est cohérent.

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 :

1. l'exemple du sujet,
2. les exemples résolus entièrement à la main,
3. d'autres exemples générés sur le tas,
4. des exemples de pire cas, dans la mesure du possible.

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.

8) Déboguez votre code

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 :

• simplifier l'algorithme,
• vérifier l'algorithme,
• simplifier le pseudo-code,
• vérifier le pseudo-code,
• relire le code des différentes manières possibles,
• tester indépendamment les morceaux difficiles du code.

Annexe : Organisez-vous

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 :

1. Prenez un porte-mine et une gomme. C'est très pratique de gommer, ça permet d'améliorer une partie de ce qu'on a écrit sans tout recopier.
2. Prenez une grande feuille toute blanche. Trouvez du papier qui ne se froisse pas quand on le gomme plusieurs fois.
3. Notez le nom de l'exercice et le numéro de la page en haut de chacune des feuilles utilisées pour l'exercice, afin de vous y retrouver plus tard. L'idéal est d'avoir une grande feuille double.
4. Marquez l'heure de début et de fin de chaque phase de recherche dans la marge, pour pouvoir bien gérer votre temps.

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.

Conclusion

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 !