Le pseudo-code est une technique qui permet de gagner énormément d'efficacité dans l'implémentation d'algorithmes. Je ne connais pas de méthode plus performante pour arriver rapidement à une implémentation sans aucun bug, et qui de plus marche pour n'importe quel algorithme. L'idée de base est que le pseudo-code contient assez d'information pour que quelqu'un qui, l'ayant lu sans connaître l'algorithme, soit capable de l'implémenter.
Ce que l'on veut éviter
Les erreurs les plus fréquentes qui rendent les implémentations fausses :
Se tromper dans les noms de variables (en utiliser un à la place d'un autre) ;
Se tromper dans les indices de début et les conditions de fin des boucles ;
Oublier d'initialiser les valeurs contenues dans un tableau ;
Oublier de traiter des cas limites ;
Avoir des tableaux trop petits d'une case ;
Utiliser une valeur trop petite pour implémenter l'infini ;
Ce qui arrive lorsqu'on n'est pas organisé et qui fait perdre beaucoup de temps :
Changer a posteriori ses structures de données ;
Modifier du code déjà écrit pour gérer plus de variables ;
Modifier du code pour corriger un bug et en introduire d'autres au passage ;
S'apercevoir en codant qu'on a oublié une boucle et qu'on a donc sous-estimé la complexité ;
Ne pas avoir différents tests sous la main pour tester son algorithme.
Présentation générale
Une fois qu'on a une vague idée de l'algorithme, plutôt que de commencer à coder et préciser ses idées sur l'algorithme au fur et à mesure, on va découper le travail en trois.
Tout d'abord, on va préciser en français l'idée de l'algorithme, le but étant d'exprimer clairement la stratégie de l'algorithme. Pour cela on écrit les grandes lignes de l'algorithme, faisant apparaître les boucles et les fonctions que l'on utilisera. Cela prend en général entre 3 et 7 lignes seulement.
on n'utilise pas de nom de variables ni de symboles du langage de programmation, juste du français ;
si l'on utilise de la programmation dynamique, on formule précisément la question à laquelle la fonction répond.
Ensuite, on va chercher comment implémenter cet algorithme le plus simplement possible. On va donc réfléchir aux structures de données, aux noms de variables, à l'initialisation des valeurs, aux conditions de départ et d'arrêt des boucles et des fonctions récursives, ainsi qu'aux formules que l'on va utiliser. On appelle cette phase le pseudo-code de l'algorithme.
le pseudo-code doit être suffisamment précis pour que quelqu'un d'autre l'ayant lu sans connaître l'algorithme soit capable de le coder ;
l'objectif est d'avoir le pseudo-code le plus simple possible, afin de le coder facilement et sans bug ;
la simplification du pseudo-code se fait naturellement lorsqu'on a la flemme d'écrire beaucoup à la main.
On peut alors passer au code de l'algorithme. Normalement cette phase doit aller assez vite, puisque toutes les difficultés ont été résolues au niveau du pseudo-code. On peut ainsi se concentrer à fond sur les petits détails du code et éviter ainsi d'introduire des erreurs.
Comment présenter le pseudo-code
Aspect général :
Le pseudo-code d'un petit algorithme prend en général une douzaine de lignes. Pour un problème plus complexe, compter jusqu'à 20 ou 25 lignes. Prévoyez assez de place pour faire tenir tout le pseudo-code sur une même page, c'est plus pratique.
Lorsqu'on commence à écrire le pseudo-code, on ne sait pas encore précisément ce qui va venir ensuite. Il est judicieux de laisser des lignes blanches régulièrement pour pouvoir ajouter des choses ensuite tout en gardant quelque chose de propre.
Pour rendre compte visuellement des imbrications des boucles, indentez vers la droite le corps des boucles et des fonctions. Sur le papier, on peut ajouter de grandes barres verticales pour faire ressortir encore plus les différents blocs d'instructions.
Remarques locales :
Sur le papier, on évite de perdre du temps à écrire le mot-clé return, une petite flèche en coin convient tout-à-fait.
Pour l'affectation de valeur à des variables, on peut utiliser le symbole = ou alors une flèche vers la gauche, ou encore le symbole :=.
Pour la comparaison de valeurs, ceux qui codent en C++ ont intérêt à utiliser dans le pseudo-code le symbole ==.
Ce qu'on met dans le pseudo-code
Les constantes
les limites provenant du sujet (const int MAX_NB_SOMMETS, MAX_DISTANCE),
les limites calculées à partir de celles du sujet (mettre la formule du calcul et non le résultat),
les valeurs sentinelles (INFINI, MOINS_INFINI),
les valeurs indéfinies (INCONNU pour un dynamique, AUCUN_PARENT pour la racine d'un arbre).
Les structures globales
choisir un nom adapté (ceci sera détaillé plus bas),
préciser le type de la structure,
préciser la taille de la structure,
pour un tableau, indiquer les valeurs d'initialisation que l'on veut y mettre.
Les fonctions
choisir un nom décrivant précisément ce que la fonction retourne,
préciser le type de retour,
donner la liste de tous les paramètres,
expliciter le corps, y compris les conditions d'arrêt des fonctions récursives.
Les tests, et les boucles avec leurs indices
les tests Si avec leur condition et éventuellement Sinon, et Sinon Si,
les boucles Pour avec les valeurs de départ et de fin,
les boucles Tant que avec la condition d'arrête,
les boucles Pour tous les sur un ensemble,
les boucles Prendre le min (ou le max) sur un ensemble.
Les variables et les paramètres des fonctions
choisir un nom adapté (sera également détaillé plus bas),
toujours donner une valeur d'initialisation (ou sinon INDEFINI),
ne préciser le type que s'il n'est pas évident.
Les instructions
écrire complètement les lignes qui font quelque chose de non trivial,
expliciter les paramètres donnés lors des appels de fonction,
écrire toutes les formules mathématiques utilisées, y compris les calculs simples.
Quelques remarques :
Le pseudo-code, comme le code, doit toujours être factorisé au maximum. Si plusieurs lignes se ressemblent, elles doivent être factorisées à l'aide de boucles ou de fonctions. Même si l'on ne gagne pas grand chose en nombre de lignes, un code factorisé est toujours plus simple et contient donc moins de bugs.
Il doit être clairement défini, une fois pour toute, si les tableaux sont indexés de 0 à N-1 ou de 1 à N. En général, on préfèrera indexer de 0 à N-1.
Ce qu'on ne met pas dans le pseudo-code
On ne met surtout pas :
de zone trouble (toutes les parties de l'algorithme doivent être travaillées),
de commentaires (tout doit se comprendre à partir des noms des variables et des fonctions),
On n'écrit pas de trivialités (en Caml on n'en a d'ailleurs pas besoin dans le code) :
les déclarations des variables locales (mais on met les initialisations),
les types des variables, les types des paramètres des fonctions,
les indices de début et de fin des boucles triviales (ex : pour chaque direction, pour chaque sommet),
On ne détaille pas des morceaux de code usuels :
les entrées et sorties quand elles sont simples,
les structures courantes comme point{x;y} et les méthodes qui vont avec,
les instructions qui récupèrent le minimum d'un tableau, ou l'indice de ce minimum,
les fonctions de comparaison lorsqu'elles sont standards.
On ne l'écrit pas pour économiser du temps, mais on y pense sérieusement :
la quantité de mémoire consommée par chaque structure de donnée,
les endroits où il serait judicieux d'insérer du printf pour déboguer facilement.
Comment nommer les variables et les fonctions
Choisissez vos conventions :
Choisissez une langue : français ou anglais. Évitez de mélanger les deux dans le même source. En général, il est plus facile d'avoir des noms courts et précis en anglais, et on économise ainsi des caractères. De plus, certains mots français deviennent difficiles à lire une fois qu'on enlève leurs accents. Si vous êtes suffisamment à l'aise en anglais, utilisez cette langue de préférence.
Choisissez une convention d'écriture : soit des noms avec des majuscules à chaque début de mot sauf le premier, soit des noms tout en minuscules avec des underscore entre les mots. La première solution donne des mots plus compacts, et c'est cette convention qui est utilisée dans les corrections sur le site.
Les noms doivent satisfaire aux règles suivantes :
Un nom de variable doit impérativement refléter ce que représente la variable. Cependant des noms de plus de 12 caractères vont être assez pénibles à utiliser, rendant les lignes longues et peu lisibles. Il s'agit donc de trouver le juste milieu.
Un nom de fonction doit décrire précisément ce que fait et/ou calcule la fonction. On peut utiliser sans problèmes de longs noms pour les fonctions qui ne sont appelées qu'à deux ou trois endroits (par exemple selectionnerNoeudCritique ou calculerDistancesDepuisDepart).
Le nom d'une structure de donnée doit décrire les éléments qu'elle contient. Ainsi la file dans un parcours en largeur ne se nommera pas file et encore moins f, mais plutôt noeudsEnCours.
Petite précision relative aux noms des tableaux : faut-il mettre un singulier ou un pluriel ? Souvent on souhaite utiliser le même nom au singulier comme indice pour ce tableau, et donc on utilise le pluriel pour le nom du tableau :
sommets[sommet] pour le tableau décrivant les sommets d'un graphe,
distances[sommet1][sommet2] pour une matrice d'adjacence d'un graphe,
list voisins[sommet] pour un graphe sous forme de listes d'adjacences,
representant[sommet] pour le tableau utilisé dans de l'Union-Find.
Si le tableau contient des propriétés sur certains éléments, le pluriel n'a pas beaucoup de sens. Par exemple le tableau utilisé dans un crible d'Ératosthène : bool pasPremier[entier]. Le pluriel n'est donc pas une règle stricte.
Conclusion
En attendant de vous entendre dire comme le premier français médaillé d'or aux IOI : « maintenant, je n'arrive plus à coder sans pseudo-code » (Mehdi, 2005), je vous recommande de vous forcer à ne pas commencer à coder avant d'avoir un bon pseudo-code complet et simplifié au maximum. Vous verrez alors que lorsque ces conditions sont remplies, il devient possible d'obtenir du code qui compile du premier coup et qui obtienne 100 % des points sans avoir besoin de le déboguer, et ce même pour des algorithmes complexes. Tout ce qu'il faut, c'est de l'entraînement ET de la méthode.
