Pseudo-code

La définition générale d'un algorithme 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 algorithme, 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 l'invention : tout doit y être rigoureusement défini, et chaque étape élémentaire doit être réalisable en un temps fini par un humain :

Ce n'est pas non plus un langage informatique dont le but est d'être compris par un ordinateur. Il est communément admis que tout algorithme peut être écrit en pseudo-code :

Avant de définir précisément le pseudo-code, notez la thèse (hypothèse) fondamentale de l'informatique :

La thèse de Church-Turing a été initialement formulée pour les Machines de Turing mais (nous le verrons bien plus tard) pseudo-code et machines de Turing sont deux notions équivalentes. Notez que cette affirmation n'est pas démontrée mais que toutes les tentatives (et il y en a eu) pour infirmer cette affirmation ont été des échecs.

Pseudo-code et langages de programmation

Les langages de programmation classiques comme python, java ou encore rust se transcrivent aisément en pseudo-code et réciproquement. Ce sont deux notions équivalentes :

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

Éléments de pseudo-code

Briques de base

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

Algorithmes en pseudo-code

On a vu qu'un programme et un algorithme doivent posséder des paramètres d'entrées En pseudo-code, un algorithme est une suite d'instructions qui, a partir de paramètres d'entrée, rend une sortie. Considérons par exemple la description de l'algorithme de recherche d'un élément dans une liste :

Nom : recherche
Entrées :
    t : un tableau d'entiers
    x : un entier
Programme :
 
    parcourir chaque élément de t jusqu'à trouver un élément dont la valeur est égale à la valeur de x.
    Si on trouve un tel élément, rendre "Vrai".
    Sinon rendre "Faux".

En pseudo-code, cela va donner ça :

algorithme recherche(t: [entier],
                     x: entier     # entier recherché dans t
                    ) → booléen:   # Vrai si x est dans t

    pour chaque e de t:
        si e == x:
            rendre Vrai
    rendre Faux

Le programme est un bloc. La definition du bloc (jusqu'aux :) est constitué :

1. du mot-clé algorithme qui détermine la nature du bloc
2. suit le du nom du programme
3. puis ses paramètres d'entrées entre parenthèses. Chaque paramètre est décrit par son nom suivit de son type
4. enfin, le type de sortie de l'algorithme qu'on fait précéder d'une flèche.

Si on a besoin d'information supplémentaire pour qu'un lecteur puisse mieux comprendre le pseudo-code on peut ajouter des commentaires en les faisant commencer par un #. Ne mettez pas trop de commentaires, normalement le pseudo-code et le nom des variables doit suffire. On a ici juste décrit ce que fait l'algorithme avec ses paramètres d'entrées.

Fonctions

Un algorithme est constitué uniquement d'instructions de base. Mais rien n'empêche de réutiliser des algorithmes déjà écrit en les appelant par leur nom. Ces algorithmes intermédiaires sont appelées fonctions.

Écrire du bon pseudo-code

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

Pour cela il faut :

• utiliser des noms de variables ou de fonctions explicites et utile à la compréhension
• séparer les différentes parties d'un algorithmes en fonctions au nom explicite.

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