Pseudo-code

Cours/Algorithmie/Partie I : Écrire des algorithmes/Pseudo-code

La définition générale d'un programme ne spécifie rien sur les instructions à utiliser, juste qu'elles doivent être décrites en un nombre fini de mots. Un pseudo-code est une proposition d'instructions possibles pour décrire un programme, compréhensibles par un humain.

Ce n'est cependant pas une langue car il n'y a pas de place pour l'ambiguïté ni pour l'interprétation : tout doit y être rigoureusement défini et chaque étape élémentaire doit être réalisable en un temps fini par un humain.

On the foolishness of "natural language programming"

Ce n'est pas non plus un langage informatique dont le but est d'être exécuté par un ordinateur. Le but d'un pseudo-code est d'être compris par d'autres humains et doit être vu comme une démonstration mathématique : un algorithme prouve à d'autres humains qu'un problème est solvable par un ordinateur.

Définition

Un pseudo-code est une succession de lignes qui seront exécutées en séquence.

chaque ligne est composée d'une instruction qu'il faut réaliser avant de passer à la ligne suivante,
chaque instruction est clairement définie et est réalisable par un humain muni d'un papier et d'un crayon

Si le but premier d'un pseudo-code est d'être compris par un humain, les langages de programmation classiques comme python, go ou encore rust se transcrivent aisément en pseudo-code et réciproquement (ce sont deux notions équivalentes).

À retenir

on utilisera le pseudo-code pour l'étude théorique des algorithmes
on codera ces algorithmes dans un langage dédié à être exécuté lorsque l'on voudra les tester. Dans le cadre de ce cours on utilisera le python, puis le go et enfin le rust.

Écrire du pseudo-code

Commençons par décrire la grammaire de base du pseudo-code :

On peut maintenant utiliser les différentes instructions du pseudo-code pour écrire nos algorithmes :

Un bon pseudo-code doit être compréhensible en tant que tel, sans commentaires.

Pour cela il faut :

expliciter la signature de vos algorithmes,
utiliser des noms de variables ou de fonctions explicites et utiles à la compréhension,
séparer les différentes parties d'un algorithme en fonctions au nom explicite.

Leurs noms importent peu, seules leurs fonctions sont importantes. Vous pouvez donc utiliser les mots qui vous plaisent, du moment qu'ils sont compréhensibles pour vous et — surtout — pour votre lecteur. Le plus souvent, on utilisera un mix de python et de français, ou d'anglais.

Opérateurs utilisés en pseudo-code

Plusieurs opérateurs ressemblant à l'égalité sont utilisés en pseudo-code, attention à bien comprendre leurs différences.

ref x T : on définit la variable x pouvant référencer des objets de type T
x ← y : on affecte x à la valeur de y
x == y : on teste l'égalité entre les valeurs de x et de y. L'expression est vraie si la valeur de x vaut la valeur de y et fausse sinon. Par exemple 2 * x + 2 == 10

Les autres opérateurs possibles en algorithmie sont :

x := y : on définit x comme étant y. Par exemple $f(x) \coloneqq max(x, 10)$
x = y : avec les définitions et les propriétés de x et y les valeurs des deux variables sont toujours égales. C'est une conséquence comme $\cos(\pi) = -1$.