Briques de base

Le but d'un pseudo-code est d'être lu et compris par un humain. Il se doit d'être sans ambiguïté sans être lourd. Il est constitué d'instructions dont le but est soit :

• de manipuler des objets (création, affectation ou lecture)
• de contrôler le flux d'instructions (tests et boucles).

Nous allons montrer ici une version de pseudo-code sans accès direct à la mémoire (ie. sans pointeur). Ce modèle est tout à fait fonctionnel et est utilisé dans les langages de programmation comme python ou javascript par exemple. Nous ajouterons l'accès direct à la mémoire (bien) plus tard dans ce cours. Ce modèle est plus simple à comprendre et à implémenter que le modèle avec pointeur et ne change rien algorithmiquement. Il va cependant nécessiter des opérations élémentaires supplémentaires (on appelle ceci des overheads) pour trouver la valeur de la variable en mémoire par rapport à l'utilisation directe de pointeurs.

Commentaires

Comme en python, on considérera que tout ce qui suit le caractère # est considéré comme un commentaire dont le but est d'éclairer le lecteur.

# un commentaire

Objets et opérations

Commençons par décrire les objets que l'on peut manipuler en pseudo-code et les moyens d'y accéder.

Objets

Les objets sont ce que l'on manipule en algorithmie. On a vu qu'a priori on peut n'utiliser que des suites finies de 0 et de 1 (ou de façon équivalente des entiers), mais cela nuirait grandement à la lisibilité. En pseudo code on se permet d'utiliser d'autres formes d'objets appartenant à 6 types fondamentaux.

Objets basiques

Les objets que nous aurons directement à notre disposition sans avoir besoin de les définir sont appelés objets basiques et correspondent aux six types suivants :

Un type peut être vu comme un ensemble d'objets : le type entier contient tous les entiers possibles.

Chaîne de caractères

Le type str (chaîne de caractères) représente contient l'ensemble des mots dont l'alphabet est l'ensemble des caractères. Ce n'est pas un type basique en tant que tel mais est tellement utilisé qu'il fait parti des types toujours présent.

Le vide

En algorithmie on a également coutume de se doter d'un élément vide ∅ (nommé None en python, null en javascript ou encore void en C) qui sera à la fois considéré comme un type ou un objet :

Taille et stockage des objets

La plupart des objets basiques sont de taille fixe :

• un booléen a une taille de 1bit (0 pour faux, 1 pour vrai)
• un caractère a une taille de 32bit puisqu'on utilise les caractères Unicode
• un réel a une taille de 64bit si on utilise la norme IEEE 754 double précision

D'autres n'ont pas de limite fixée :

• les entiers
• les chaînes de caractères

Les objets que l'on manipule doivent pouvoir être conservés pour que l'on puisse les réutiliser tout au long du programme. Cet espace de stockage, que l'on nomme une mémoire, est identifié, d'un point de vue algorithmique, à une gigantesque suite de cases adjacentes à laquelle l'algorithme peut accéder en 1 instruction et pouvant contenir un objet basique. En algorithmie, on ne se préoccupe pas vraiment de ce qu'est la mémoire : cela peut être celle de l'informaticien lecteur ou sur un ordinateur : peu importe.

On verra d'autres modèles de pseudo-code plus tard qui gèrent la mémoire de façon plus réaliste mais pour celui que nous présentons maintenant on considérera que :

Opérations

Les opérations que peuvent effectuer les pseudo-codes sont liées aux objets. On doit pouvoir :

• créer des objets : le caractère "Ç", l'entier 42, etc...
• opérer sur des objets : rendre la somme de deux entiers, le résultat d'une formule logique, etc
• afficher un objet. On suppose que l'on possède une opération unaire spéciale nommée affiche qui affiche à l'écran (ou à n'importe quoi permettant à l'utilisateur d'avoir un retour) l'objet. Par exemple affiche 42 va afficher l'objet entier valant 42 à l'écran.

Créer des objets

La seule façon de créer un objet à partir de rien est d'écrire sa valeur. Par exemple :

42

Crée un objet entier de valeur 42.

On peut aussi demander à l'utilisateur de créer un objet d'un type donné (on suppose que l'utilisateur ne se trompe pas) :

donne int

Opérations

Les opérations correspondent au second moyen de créer des objets. Par exemple le booléen Vrai est créé comme résultat de l'opération 40 > 2. Les seules opérations définies par défaut dans tout pseudo-code sont peu nombreuses :

• pour les entiers et les réels :
  • arithmétique : addition (x + y), soustraction (x - y), multiplication (x * y), division (x / y)
  • opérations usuelles comme prendre la valeur entière, la valeur absolue, ...
  • la division entière de deux nombres (//) et le modulo (mod ou %) qui correspond au reste de la division entière
  • logique : égalité (avec le signe ==), plus petit que (<), plus grand que (>), plus petit ou égal (≤), plus grand ou égal (≥)
  • comparaisons : maximum (max(x, y)), minimum (min(x, y))
• pour les caractères :
  • logique : égalité (avec le signe ==)
• pour les chaînes de caractères :
  • logique : égalité (avec le signe ==), plus petit que (<), plus grand que (>), plus petit ou égal (≤), plus grand ou égal (≥) en utilisant l'ordre du dictionnaire
  • opération de concaténation (avec l'opérateur +) : "comment vas-tu" + " yau d’poêle ?" vaut la chaîne de caractères "comment vas-tu yau d’poêle ?"
• opérations sur les bits et les booléens :
  • "négation logique" (non, NON, NOT ou encore $\neg$),
  • "et logique" (et, ET, &&, AND ou encore $\land$), "ou logique" (ou, OU, ||, OR ou encore $\lor$)

40 + 2  # rendra l'objet entier 42

Toutes les autres opérations devront être définies soit dans le pseudo-code (avec des fonctions, comme on va le voir) soit dans un texte avant celui-ci.

Affichage

Enfin, la dernière opération autorisée pour les objets est l'affichage :

affiche 42

L'affichage est destiné, comme le commentaire, au lecteur du pseudo-code. Son but est de lui montrer des résultats intermédiaires intéressants lors de l'exécution du pseudo-code. Ce qui est affiché sort du contrôle du pseudo-code : dans l'exemple précédent l'entier 42 est affiché, le pseudo-code n'en a pas conscience.

On peut afficher plusieurs objets à la suite, par exemple :

affiche 40 " plus " 2 " égal " 42

Qui va afficher à la suite les cinq objets : 40, " plus ", 2, " égal " et 42

Variables

Une variable permet de retrouver un objet stocké en mémoire pour sa réutilisation :

Les variables nous permettent de manipuler les objets. Conceptuellement parlant, ce sont des liens vers les objets qu'elles référencent.

En algorithmie, tout comme pour les objets on ne se préoccupe pas vraiment de l'endroit où sont stockées les variables. On sait qu'elles existent : elles sont rangées dans une partie de la mémoire différente de celle des objets (les variables ne sont pas considérées comme des objets).

Concernant la taille en mémoire d'une variable, on considérera pour notre modèle de pseudo-code que :

Définition d'une variable

Avant de pouvoir être utilisée, une variable doit être définie. La ligne suivante définit une variable de nom $a$ pouvant référencer un objet de type entier :

ref a int

La ligne précédente crée une nouvelle variable nommée a pouvant référencer des objets de type entier. Dans tout le reste du pseudo-code, on sera sûr que a contient une valeur entière.

ref <nom de la variable> <type d'objet qu'elle peut référencer>

En pseudo-code, comme le principal souci est la non-ambiguïté, une variable ne peut référencer que des objets du type spécifié lors de sa définition.

Affectation

Une fois la variable créée, sa valeur est ∅ : elle est non affectée. Pour l'utiliser dans un programme il faut lui affecter un objet, par exemple pour notre variable a créée précédemment :

a ← 3

La ligne précédente associe à la variable a un objet entier valant 3.

<nom de la variable> ← <objet qu'elle va référencer>

L'affectation d'une variable est une opération répétable, on peut la réaffecter à un autre objet au cours du pseudo-code :

ref a int

# ... des instructions

a ← 4

# ... des instructions

a ← 2

Après la troisième ligne, le code précédent associe la variable a à un entier valant 4 et à un entier valant 2 après la cinquième ligne. Il est important de noter que :

Utilisation

Utiliser une variable consiste à la remplacer dans l'instruction par l'objet qu'elle référence. Par exemple :

ref a int
a ← 42
affiche a

Le code précédent affiche l'objet référencé par $a$. Il est équivalent à : affiche 42.

Regardons ceci avec quelques exemples :

ref a int
a ← 42
ref b int
b ← a

La ligne 4, une instruction d'affectation, s'exécute de la façon suivante :

1. on commence par retrouver l'objet à droite de l'opérateur ←. C'est une variable : on récupère son objet, un entier valant 42
2. on affecte cet objet à la variable à gauche de l'opérateur ←, la variable b

Autre exemple :

ref a int
a ← 41
ref b int
b ← a + 1

La ligne 4, une instruction composée d'une opération puis d'une affectation, s'exécute de la façon suivante :

1. on commence par retrouver l'objet à droite de l'opérateur ←. C'est le résultat d'une opération :
   1. pour effectuer l'opération, il faut commencer par retrouver l'objet associé à a : un entier valant 41
   2. on peut maintenant effectuer l'opération d'addition qui rend un objet de type entier valant 42
2. on affecte cet objet à la variable à gauche de l'opérateur ←, la variable b

Attention cependant :

Type d'un objet

On aura parfois besoin de connaître le type d'un objet pour définir une variable du même type. On suppose qu'il existera toujours une opération unaire spéciale nommée type qui rend le type de l'objet passé en paramètre, et que l'on pourra utiliser dans les déclarations de variables. Par exemple type 42 va rendre int. Ceci permet d'écrire :

ref a int
ref b (type a)

Tableaux

[]T

Créons un objet tableau pouvant contenir 13 variables de type entier :

ref T []int  # création de la variable pouvant accueillir un tableau d'entiers

T ← [13]int  # création d'un tableau pouvant contenir 13 variables entières

Un tableau est un mix entre variables et objets : c'est un objet contenant des variables de même type.

La remarque ci-dessus est cruciale à comprendre car cela peut entraîner tout un tas d'effets de bord incompréhensibles sinon. Pour comprendre ce qui se passe, voyez comment python gère les tableaux :

On utilise un tableau comme une collection de variables, par exemple :

ref T []int
T ← [3]int

T[0] ← 41
T[1] ← 1
T[2] ← T[0] + T[1]

La seule opération spécifique à un tableau est sa création qui est un mix entre création d'objet et création de variable, puis on affecte ses variables avant de pouvoir les utiliser. Toutes les autres opérations sur les tableaux sont faites grâce aux opérations des objets basiques qui les composent. Il n'y a pas d'opérations spécifiques à ceux-ci :

Ainsi, on ne peut pas affecter un tableau à un autre. Il faut créer un nouveau tableau puis y recopier tous les éléments de l'ancien.

On considère que :

Les tableaux peuvent être simples comme une suite finie d'entiers ou des types plus complexes comme une matrice à 2 dimensions où chaque élément du tableau est un autre tableau (on y reviendra).

Tranches

On utilisera parfois, comme en python par exemple, des sous-tableaux via des tranches (slices en anglais) :

• T[i:] représentera le tableau constitué des éléments de T à partir de l'indice i inclus jusqu'à la fin
• T[:j] représentera le tableau constitué des éléments de T à partir de l'indice 0 inclus jusqu'à j exclu
• T[i:j] représentera le tableau constitué des éléments de T à partir de l'indice i inclus jusqu'à j exclu

Chaînes de caractères et tableaux

Les chaînes de caractères, une fois créées, peuvent être utilisées comme un tableau composé de caractères. On peut :

• accéder à un caractère particulier en utilisant les crochets : s[2] vaut le caractère "l"
• connaître la longueur de la chaîne avec : s.longueur

On ne peut cependant pas : modifier un caractère de la chaîne. Elle est créée une fois pour toutes.

Instructions de contrôle

Si un des deux buts d'une instruction est de créer des objets à partir d'autres (ce que l'on vient de voir), le second but est de contrôler le flux d'instructions à exécuter. Ces instructions sont de deux types :

• l'exécution conditionnelle d'instructions,
• la répétition d'instructions

Ces formes d'instruction nécessitent de grouper les instructions en blocs.

Blocs

Lier les instructions en blocs. Ce formalisme a été popularisé par python et permet de voir du premier coup d'œil un bloc et ses instructions :

<type de bloc>:
    instruction 1
    instruction 2
    ...
    instruction n

Les blocs vont être utiles dans les très nombreuses situations où l'on veut, par exemple, répéter une suite d'instructions ou encore exécuter des instructions conditionnellement.

Exécution conditionnelle d’instructions

On veut pouvoir exécuter des instructions si une condition logique est VRAIE :

si <condition logique>:
    instruction 1

    ...
    instruction n

Par exemple :

si (age ≥ 18):
    affiche "Tu peux voter !"

Cette instruction basique suffit pour gérer toutes les exécutions de bloc conditionnelles, par exemple :

si (age ≥ 18):
    affiche "Tu peux voter !"
si (age < 18):
    affiche "Tu ne peux pas jouer au Loto."

Mais pour plus de lisibilité on admettra plein de variantes comme la variante "si-sinon" :

si <condition logique>:
    instruction 1
    ...
    instruction n
sinon:                      # <condition logique> est fausse
    instruction 1
    ...
    instruction n'

ou encore "si-sinon-si" :

si <condition logique>:
    instruction 1
    ...
    instruction n
sinon si <autre condition logique>:
    instruction 1
    ...
    instruction n'

Ou tout mix de tout ça (comme "si-sinon si-sinon"), du moment que c'est clair :

si <condition logique A>:
    # instructions A
sinon si <condition logique B>:
    # instructions B
sinon:                            # <condition logique A> et <condition logique B> sont fausses
    # instructions C

si <condition logique A>:
    # instructions A
si ((NON <condition logique A>) ET (<condition logique B>)):
    # instructions B
si ((NON <condition logique A>) ET (NON <condition logique B>)):
    # instructions C

Répétitions

On doit pouvoir répéter un bloc tant qu'une condition logique est vérifiée. Les répétitions en pseudo-code vont prendre deux formes dont l'une est un cas particulier de l'autre.

Boucles tant que

tant que <condition logique>:
    instruction 1
    ...
    instruction n

Boucles pour chaque

Tout comme l'exécution conditionnelle, la forme précédente suffit pour exprimer toutes les formes de répétition possibles, mais on admet la variation suivante, très utile :

pour chaque <variable> de <objet pouvant être énuméré>:
    instruction 1
    ...
    instruction n

On exécutera alors le bloc autant de fois qu'il y a d'éléments dans l'<objet pouvant être énuméré> et à chaque itération du bloc, la variable (de type de celui des objets stockés dans le tableau) vaudra un autre élément de l'objet.

Par exemple :

pour chaque x de [1 .. 10]:
    affiche x

Typiquement l'<objet pouvant être énuméré> est un tableau ou une chaîne de caractères que l'on parcourt par ordre d'indice croissant.

Les deux codes suivants sont équivalents. Le second, moins élégant, explicite le numéro de l'itération courante d'un tableau de chaînes.

Code pour chaque :

pour chaque x de T:
    affiche x

Code tant que :

ref x int

ref i int
i ← 0
tant que i < T.longueur:
    x ← T[i]
    affiche x
    i ← i + 1

Comme on va souvent faire des itérations sur des intervalles d'entiers, on utilise les notations suivantes :

• [a .. b] pour représenter l'intervalle formé des entiers allant de a à b (cet intervalle peut être vide) par incrément de +1,
• [a .. b[ pour représenter l'intervalle formé des entiers allant de a à b-1 (cet intervalle peut être vide),
• ]a .. b] pour représenter l'intervalle formé des entiers allant de a + 1 à b (cet intervalle peut être vide),
• ]a .. b[ pour représenter l'intervalle formé des entiers allant de a + 1 à b -1 (cet intervalle peut être vide),

On peut alors écrire, par exemple :

ref x int
x ← 0

pour chaque i de [0 .. 10000[:
    x ← i + x

Sortir d'une boucle avant la fin

On a parfois besoin de sortir d'un bloc de boucle avant la fin de sa condition. On utilise pour cela deux instructions spéciales de sortie de boucle :

• break : qui termine l'exécution du bloc
• continue : qui termine l'itération courante du bloc

Ces instructions sont utiles si elles permettent de rendre le pseudo-code plus lisible, en séparant le cas général (la condition de la boucle) des cas particuliers (traités avec un break ou un continue)

break

Par exemple le code suivant qui trouve le pgcd (plus grand commun diviseur dont on a déjà vu l'algorithme) entre deux nombres :

ref x int
ref y int

x ← donne int
y ← donne int

ref d int
d ← min(x, y)

tant que (d > 0):
    si (x mod d == 0) ET (y mod d == 0):
        break
    d ← d - 1

affiche "le pgcd entre " x " et " y " vaut " d

Qui est équivalent au code suivant, moins lisible :

ref x int
x ← donne int

ref y int
y ← donne int

ref d int
d ← min(x, y)

ref sortir bool
sortir ← Faux

tant que (sortir == Faux) ET (d > 0):
    si (x mod d == 0) ET (y mod d == 0):
        sortir ← Vrai
    sinon:
        d ← d - 1

affiche "le pgcd entre " x " et " y " vaut " d

Et qui donne en python :

x = int(input("Donne un entier : "))
y = int(input("Donne un entier : "))

d = min(x, y)

while (d > 0):
    if (x % d == 0) and (y % d == 0):
        break
    d -= 1

print("le pgcd entre", x, "et", y, "vaut", d)

continue

Par exemple le code suivant qui va afficher tous les diviseurs de x. Le continue permet d'expliciter les cas rejetés :

ref x int
x ← donne int

pour chaque d de [1 .. x]:
    si (x mod d != 0):
        continue

    affiche d " divise " x

Qui est équivalent au code suivant, un peu moins lisible :

ref x int
x ← donne int

pour chaque d de [1 .. x]:
    si (x mod d == 0):
        affiche d " divise " x

Et qui donne en python :

x = int(input("Donne un entier : "))

for d in range(1, x + 1):
    if (x % d != 0):
        continue
    
    print(d, "divise", x)

Boucles imbriquées

Par exemple :

pour chaque x de [1 .. 3]:
    pour chaque y de [0 .. 3]:
        si x * y > 2:
            break
        affiche "x = " x "; y = " y

for x in range(1, 4):
    for y in range(4):
        if x * y > 2:
            break

        print("x =", x, "; y =", y)

Va afficher :

• x = 1; y = 0
• x = 1; y = 1
• x = 1; y = 2
• x = 2; y = 0
• x = 2; y = 1
• x = 3; y = 0

L'instruction break ne sort que de la boucle la plus imbriquée.