Briques de base

Le pseudo-code est constitué d'instructions dont le but est soit de manipuler des objets (création, affectation ou lecture) ou de contrôler le flux d'instructions (test et boucles).

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.

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.

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

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 cinq types suivant :

• le type booléen qui contient deux objets : vrai et faux
• le type bit qui contient les 2 objets : 0 et 1
• le type entier qui contient tous les entiers relatifs
• le type réel qui contient un ensemble dénombrable d'approximation de réels
• le type caractère qui contient l'ensemble des glyphes UNICODE : "a", "b", ...

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 peut être à la fois considéré comme un type ou un objet :

• le type vide ∅ ne contient aucun objet. On l'utilise pour des fonctions ne rendant aucun objet par exemple
• l'objet vide ∅ est de tous les types (le ∅ entier, bit, ...). Utilisé pour simuler un soucis ou un cas particulier : une fonction division pouvant rendre soit un réel soit le vide si on divise par 0 par exemple.

Autres types

Tous les autres types d'objets que l'on peut imaginer seront des compositions de ces 5 types d'objets (un point en 3D est constitué de 3 réels, une chaîne de caractères est un tableau de caractères, etc).

Taille et stockage des objets

Notez que tous les objets basiques à part les entiers sont de taille fixe :

• un booléen sur 1bit
• un caractère 32bits si on utilise les caractères Unicode
• un réel sur 64 bits si on utilise la norme IEEE 754 double précision

On peut sans perte de généralité se restreindre aux entiers entre 0 et $2^{64}$, et c'est d'ailleurs ce que beaucoup de langages de programmation font, puisque qu'un entier quelconque peut être représenté en base $2$ et découpé en paquets de 64 bits. C'est ce que font les languages d programmation comme python où un entier, qui n'est pas borné par nature, est composé d'un tableau d'entiers codés sur 64bits. Ceci est cependant transparent pour l'utilisateur (et c'est tant mieux).

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 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. An algorithmie, on ne 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. Pour un ordinateur réel, les objets sont stockés dans une partie de la mémoire nommée tas (le tas est un tableau où chaque case contient 1 byte = 8 bit).

Les objets sont stockées dans le tas. Notez que le tas peut contenir des "trous", c'est à dire des endroits sans objets.

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 de définir une constante.

Opérations

De façon formelle, une opération est une fonction dont l'espace de départ est un produit cartésien de types et l'espace d'arrivée un type donné. Les opérations sont le second moyen de créer des objets via leur résultat. Par exemple le booléen Vrai est crée 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 (+), soustraction (-), multiplication (*), division (/)
  • opérations usuelles comme prendre la valeur entière, la valeur absolue, ...
  • la division entière de deux nombre (//) et le modulo (%)
  • logique : égalité (avec le signe ==), plus petit que (<), plus grand que (>), plus petit ou égal (≤), plus grand ou égal (≥)
• pour les caractères :
  • logique : égalité (avec le signe ==)
• opérations sur les bits et les booléens :
  • "négation logique" (non, NOT, $\neg$),
  • "et logique" (et, &&, AND ou $\land$), "ou logique" (ou, ||, OR ou $\lor$)

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 objet est l'affichage :

L'affichage est destiné, comme le commentaire, au lecteur du pseudo-code. Son but est de lui montrer des résultats intermédiaires intéressant lors de l'exécution du pseudo-code. Ne confondez pas un commentaire avec un retour de fonction : 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.

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 juste des liens vers les objets qu'elles référencent.

En algorithmie, tout comme pour les objets on ne se préoccupe pas vraiment où sont stockés les variables. Pour un ordinateur réel, elles sont stockées dans une partie de la mémoire nommée pile et contiennent l'indice de la mémoire du tas où commence l'objet qu'elle référence. Chaque variable est donc juste assez grande pour stocker un indice (64bit sur les ordinateur actuel ce qui permet d'avoir théoriquement un tas de taille $2^{64}$byte = 18446744073709551616B = 16777216 terabyte).

Chaque variable a la même taille et sont stockés de façon consécutives dans la pile. En effet, les variables sont crées au début de l'algorithme et sont toues supprimées en même temps à la fin de l'algorithme.

Définition

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

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 sur que a contient une valeur entière.

En pseudo-code, comme le principal soucis est la non ambiguïté, une variable ne peut contenir que des objets d'un type spécifié lors de sa définition.

Affectation

Une fois la variable crée, on peut lui affecter des objets, par exemple pour notre variable a crée précédemment :

a ← 3

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

On n'utilisera pas le signe = en pseudo-code pour l'affectation car cette opération n'est pas symétrique : à gauche une variable à droite un objet.

Une variable est une opération temporaire. On peut réaffecter une variable à un autre objet au cours du pseudo-code :

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 :

D'un point de vue matériel, rappelez vous qu'une variable est un entier qui correspond à un indice dans le tableau de la mémoire.

Utilisation

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

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

Regardons ceci avec quelques exemples :

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

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

Autre exemple :

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

1. on commence par retrouver 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 3
   2. on peut maintenant effectuer l'opération d'addition qui rend un objet valant 4
2. on affecte cet objet à la variable à gauche de l'opérateur ←, la variable b

Attention cependant :

Tableaux

Créons un tableau :

La ligne précédente crée un tableau de 13 entiers.

Un tableau est un mix entre variables et objet : c'est un objet contenant des variables. Les différentes références des variables du tableau sont stockées de façon contiguë en mémoire pour pouvoir y accéder rapidement pour y être lu ou modifiée :

On considère que :

• la taille en mémoire d'un tableau est proportionnelle à la taille d'un objet fois la taille.
• il faut 1 instruction pour créer un tableau
• il faut 1 instruction pour accéder à une variable d'indice donné.

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. La seule opération spécifique à un tableau est sa création qui prendra toujours 1 instruction, puis on affecte les variables.

Toutes les autres opérations sur les tableaux sont faites graces 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. Il faut créer un nouveau tableau puis y recopier tous les éléments de l'ancien.

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

Les chaines de caractères sont un tableau uniquement composés de caractères. Cette structure est utilisée lorsque l'on veut écrire ou représenter plus qu'un caractère, c'est à dire quasi tout le temps.

Une chaîne de caractères est un tableau constitué uniquement de caractères.

Comme ce sont des tableaux, on peut :

• créer une chaîne de caractères : "salut" crée la chaîne contenant les caractères "s", "a", "l", "u" et "t" de façon contiguë en mémoire.
• affecter une chaîne de caractères à une variable prend 1 instruction : s ← "salut" prend 2 instructions, une pour la création et une pour l'affectation.
• 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

Les chaines étant très utilisées, des langages comme python les considèrent comme un type de base et considèrent les caractères comme étant des chaîne de langueur 1.

La chaîne de caractère étant très utilisée, on se permettra les abus suivant :

• de définir une chaîne directement : s := chaine" en utilisant le type chaîne
• puis de l'affecter : s ← "Salut"
• on définit l'opération de concaténation avec l'opérateur + : "salut" + " toi !" vaut la chaîne de caractères "salut toi !"

Le type chaîne peut être vu comme un synonyme [caractère] sauf que l'on ne peut pas modifier un de ses indices (s[2] ← "p" ne sera pas une instruction valide), bien que l'on puisse y accéder (affiche s[2] sera une instruction valide). Un tableau de chaînes sera de type [chaîne].

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. On va utiliser ici le formalisme de python pour définir un bloc :

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

On décale les instructions du bloc de sa définition. C'est un truc clair qui permet de voir du premier coup d'œil les instructions d'un bloc.

Exécution conditionnelle d’instructions

On veut pouvoir exécuter un bloc de code si une condition logique est VRAIE :

si (condition logique):
    instruction 1

    ...
    instruction n

Cette instruction basique peut avoir plein de variantes comme :

si (condition logique):
    instruction 1
    ...
    instruction n
sinon:
    instruction 1
    ...
    instruction n'

ou encore :

si (condition logique):
    instruction 1
    ...
    instruction n
sinon si (autre condition logique):
    instruction 1
    ...
    instruction n'

Ou tout mix de tout ça, du moment que c'est clair !

Répétition

On doit pouvoir répéter un bloc tant qu'une condition logique est vérifiée :

tant que (condition logique):
    instruction 1
    ...
    instruction n

Le ploc précédent est exécuté tant que la condition logique est vraie. Il existe une variation de ce bloc très utile :

pour chaque élément x d'un tableau:
    instruction 1
    ...
    instruction n

On exécutera alors le bloc autant de fois qu'il y a d'éléments dans le tableau et à chaque itération du bloc, la variable x (de type de celui des objets stockés dans le tableau) vaudra un autre élément du tableau. On prendra les éléments du tableau par indice croissant.

Le code précédent est équivalent au code suivant, moins élégant, mais qui explicite le numéro de l'itération courante : à l'itération $i$ on examine le $i+1$ ème élément du tableau et on a déjà examiné les $i$ premiers. :

x := entier
pour chaque i de [0 .. tableau.longueur[:
    x ← tableau[i]

    instruction 1
    ...
    instruction n

Enfin, on peut tout à fait écrire la variante pour chaque de la forme initiale tant que :

x := entier

i := entier
i ← 0
tant que i < tableau.longueur:
    x ← tableau[i]

    instruction 1
    ...
    instruction n

    i ← i + 1