Algorithmes et fonctions

Le pseudo-code permet d'écrire des algorithmes de façon claire et sans ambiguïté.

Algorithme

algorithme <nom>(<nom paramètre>: <type paramètre>, ...) → <type de sortie>
    # ... instructions

    rendre <objet>

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
Sortie :
    un booléen
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: []int,
                     x: int      # entier recherché dans t
                    ) → bool:    # Vrai si x est dans t

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

La définition du bloc algorithme (jusqu'aux :) est constituée :

1. du mot-clé algorithme qui détermine la nature du bloc
2. du nom de l'algorithme : recherche
3. puis ses 2 paramètres d'entrée. Chaque paramètre est décrit par son nom suivi 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'informations supplémentaires 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 doivent suffire. On a ici juste décrit ce que fait l'algorithme avec ses paramètres d'entrée.

Tout algorithme se termine par un retour d'un objet (de même type que son type de sortie) avec l'instruction rendre. Cette instruction est la dernière qu'exécutera l'algorithme ainsi l'algorithme suivant rendra toujours 42 :

algorithme réponse() → int: 

    rendre 42
    rendre 0    # ne sera jamais exécuté

Ne confondez pas le retour d'un algorithme et un affichage à l'écran. L'algorithme suivant rendra l'entier 0 :

algorithme réponse() → int: 

    affiche 42
    rendre 0

L'affichage à l'écran est une information donnée à l'utilisateur, l'algorithme s'en fiche et fonctionne tout à fait sans.

Fonctions

Dans un programme, de nombreuses phases sont répétées à divers endroits du code (sommer ou multiplier des vecteurs 3D dans un moteur physique par exemple). Pour éviter de devoir replacer toutes ces instructions à chaque fois on définit des sous-programmes réutilisables à volonté, appelés fonctions.

sortie ← <nom fonction>(<paramètre 1>, ..., <paramètre n>)

Appels de fonctions

On peut définir des fonctions puis les utiliser ensuite comme dans tout langage de programmation. Considérons l'algorithme de recherche :

algorithme recherche(t: []int,
                     x: int
                    ) → bool:

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

On peut utiliser le pseudo code de nom recherche dans d'autres pseudo-codes comme une fonction. Par exemple :

ref T []int ← [1, 2, 6]
ref trouve ← recherche(t, 6)

affiche à l'écran trouve

Est un pseudo-code valide puisque recherche est bien défini et utilisé correctement (le type de ses paramètres est correct).

Dans l'exemple précédent, tout se passe comme si on disposait de deux ordinateurs, un qui exécute le pseudo-code, l'autre la fonction recherche :

1. le passage de l'ordinateur effectuant le pseudo-code à l'ordinateur exécutant l'algorithme recherche se fait en affectant les paramètres de la fonction recherche (ce sont des variables) à des objets manipulés par le pseudo-code : ici un tableau valant [1, 2, 3]
2. le passage de l'ordinateur effectuant l'algorithme recherche à l'ordinateur exécutant le pseudo-code se fait par le retour de la fonction

Dans l'exemple précédent, la variable e définie dans l'algorithme recherche n'est pas visible depuis le pseudo-code. En revanche, l'objet booléen de retour est lui transmis au pseudo-code via l'instruction rendre.

Pseudo-code avec fonctions

On peut aussi directement coder des fonctions dans un pseudo-code. Par exemple :

fonction recherche(T: []int, x: int) → bool:

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

algorithme exorcisme(T: []int) → str:
    si recherche(t, 666):
        rendre "Aspergez votre ordinateur d'eau bénite. Vite !"
    sinon:
        rendre "Tout va bien, le tableau n'est pas possédé. Ouf."

fonction affiche_double(e: int) → ∅:

    ref x ← 2 * e
    affiche x

algorithme calculatrice() → ∅:

    ref x int

    x ← demande un entier à l'utilisateur
    affiche_double(x)
    affiche x

Tableaux et fonctions

Par exemple :

fonction modif(U: []int) → ∅:

    U[2] ← U[0] + U[1]

algorithme tableau() → ∅:

    ref T ← [3]int

    T[0] ← 1
    T[1] ← 2
    T[2] ← 0
    affiche T[2]
    modif(T)
    affiche T[2]

Va afficher 0 puis 3. En effet :

• lors de l'exécution de la fonction modif la variable U va être associée à l'objet tableau de l'algorithme : la variable T de l'algorithme est différente de la variable U de la fonction mais est associée au même objet.
• on associe à la variable d'indice 2 de l'objet tableau un nouvel entier valant 3 : on a modifié le tableau défini dans l'algorithme.

Les tableaux sont les seuls objets définis en pseudo-code qui peuvent être modifiés, ce n'est pas le cas ni des 5 types basiques ni des chaînes.

Signature d'un algorithme ou d'une fonction

Lorsque l'on définit un algorithme ou un pseudo-code on explicite le type des objets en entrée et en sortie :

<nom de l'algorithme>(<type premier paramètre>, ..., <type dernier paramètre>) → <type de sortie>

<nom de l'algorithme>(<nom premier paramètre>: <type premier paramètre>, ..., <nom dernier paramètre>: <type dernier paramètre>) → <type de sortie>

Par exemple pour l'algorithme recherche :

• sa signature est recherche(T []int, x int) → bool ou recherche([]int, int) → bool
• son type est ([]int, int) → bool

Associer un type à une fonction lui permet d'être associée à un nom comme tout autre objet. Par exemple, en supposant que la fonction recherche soit définie :

ref f ([]int, int) → bool

f ← recherche
affiche f([1, 2, 6], 6)

Récursivité

Le fait que les variables et les noms définis dans les fonctions restent dans le cadre de la fonction actuellement exécutée nous donne accès à la récursivité : il suffit que notre pseudo-code s'appelle lui-même comme une fonction.

Par exemple l'algorithme suivant est une implémentation récursive de l'algorithme recherche :

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

    si T.longueur == 0:
        rendre Faux
    sinon si T[0] == x:
        rendre Vrai
    sinon:
        rendre recherche(T[1:], x)