Algorithmes et fonctions

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

Algorithme

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

    e := entier
    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 := entier
    nb ← 0

    e := entier
    pour chaque e de T:
        si e == x:
            nb ← nb + 1
    rendre nb

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éfinis des sous-programmes réutilisables à volonté, appelés fonctions.

sortie ← nom_fonction(entrée_1, ..., entrée_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: [entier],
                     x: entier
                    ) → booléen:

    e := entier
    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-code comme une fonction. Par exemple :

t := [entier]{longueur: 3}
t ← [1, 2, 6]

trouve := booléen
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, la variable e définie dans la fonction recherche n'est pas visible depuis l'algorithme. En revanche, l'objet booléen de retour est lui transmis à l'algorithme via l'instruction rendre.

Pseudo-code avec fonctions

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

fonction recherche(t: [entier],
                   x: entier
                  ) → booléen:

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

algorithme exorcisme(t: [entier]
                    ) → chaîne:

    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: entier) → ∅:

    x := entier
    x ← 2 * e
    affiche x

algorithme calculatrice() → ∅:

    x := entier

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

Tableaux et fonctions

Par exemple :

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

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

algorithme tableau() → ∅:

    T := [entier]{longueur: 3}

    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é 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éfini en pseudo-code qui peuvent être modifiés, ce n'est pas le cas ni des 5 types basiques ni des chaînes.

Type d'un algorithme ou d'une fonction

Lorsque l'on défini un algorithme ou un pseudo-code on explicite le type des objets en entrées 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_premier_paramètre: type_dernier_paramètre) → type_de_sortie

Par exemple pour l'algorithme recherche :

• sa signature est recherche([entier], entier) → booléen
• son type est ([entier], entier) → booléen

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

f := ([entier], entier) → booléen

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

Récursivité

Le fait que les variables et les noms définies dans les fonctions restent dans le cadre de la fonction actuellement exécuté nous donnent 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: [entier],
                     x: entier     # entier recherché dans t
                    ) → booléen:   # 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)