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

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.

Terminons par un petit exercice :

nombre(T: [entier], x: entier) → entier

algorithme nombre(T: [entier], x: entier) → entier:
    nb ← 0
    pour chaque e de T:
        si e == x:
            nb ← nb + 1
    rendre nb

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 :

• expliciter la signature de vos algorithme
• 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.

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.

• x := y : on remplace x par y à chaque fois qu'on le voit
• x <- y : on affecte x à la valeur de y
• x = y : avec les définitions de x et y les 2 variables sont toujours égales (c'est une conséquence)
• x == y : vrai si la valeur de x vaut la valeur de y et faux sinon

"Abus" de notation

On se permettra, lorsque l'instruction est assez claire de procéder à des raccourci pour rendre le pseudocode plus digeste. Attention, la plupart de ces opérations ne seront pas des opérations élémentaires !

Définitions de variables

Le but d'un pseudo-code est d'être explicite, c'est pourquoi :

• les variables doivent être définies avant d'être utilisée
• une variable ne peut contenir que des objets d'un type donné

Mais cela ne doit pas rendre le code lourd. On se permettra donc, lorsqu'il n'y a pas d’ambiguïté possible, l'abus de notations qui crée et affecte une variable en une seule fois :

• comme : a := entier valant 3
• voir : a ← 3 lorsque le type de la variable est clair (ici un entier)

Vous verrez aussi parfois cet opérateur remplacé par le mot "soit", en particulier lorsqu'il y a plusieurs variables à créer :

Répétitions

répéter k fois:
    ...

Pour :

pour chaque i de [1 .. k]:
    ...

Répétitions par borne

Tout un tas de variations sont possibles, du moment que ce soit compréhensible. Par exemple :

pour i de a à b:
    ...

Ou encore :

pour i=a à i=b:
    ...

Pour :

pour chaque i de [a .. b]:
    ...

Répétitions à pas fixé

pour i de a à b par par pas de k:
    ...

ou encore :

pour chaque i de [a .. b] par pas de k:
    ...

pour :

i ← a
tant que i ≤ b:
  ...

  i ← i + k

Affectation d'une tranche de tableau

T[a:b] ← k

pour :

pour chaque i de [a .. b[:
    T[i] ← k

Fonctionne aussi pour :

T[:] ← k

Qui correspond à :

pour chaque i de [0 .. T.longueur[:
    T[i] ← k

Ou encore à :

T[a:b] ← T'[a':]

Qui correspond à :

pour chaque i de [0 .. b-a[:
    T[a + i] ← T'[a' + i]

T' ← un nouveau tableau contenant T[i:j]  # j - i + 1 instructions en 1 ligne

Concaténation

Avec deux tableaux :

T ← T1 + T2

pour :

T ← un nouveau tableau de taille T1.longueur + T2.longueur

pour chaque i de [0 .. T1.longueur[:
    T[i] ← T1[i]
pour chaque i de [0 .. T2.longueur[:
    T[T1.longueur + i] ← T2[i]