"Abus" de notation

Cours/Algorithmie/Partie I : Écrire des algorithmes/Pseudo-code/"Abus" de notation

Il sera parfois plus simple d'écrire des raccourcis dans un pseudo-code pour le rendre plus lisible. Nous allons montrer dans cette partie plusieurs raccourcis courants et utilisés dans ce cours ainsi que leurs traductions en instructions é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ées
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 plusieurs abus de notation :

Déclarer plusieurs variables

Abus de notation

On déclare plusieurs variables du même type :

ref a, b, c <type>

Par exemple

ref i, j, k int

Déclarer puis affecter une variable

Abus de notation

On déclare et on affecte directement :

ref a <type> ← <objet>

Par exemple

ref réponse int ← 42

Pour ce type de déclaration/affectation il n'y a pas d’ambiguïté sur le type de la variable, on peut ainsi se permettre d'écrire directement :

Abus de notation

Type implicite si déclaration et affectation d'un objet de type connu :

ref a ← <objet de type connu>

Par exemple :

ref a ← 3
ref T ← [3]int

En pseudo-code on ne se permettra cependant jamais d'affecter une variable avant de l'avoir définie (comme on le ferait en python).

Affectations multiples

Abus de notation

Plusieurs affectations en même temps :

a, b ← c, d

pour :

ref a' ← c
ref b' ← d
a ← a'
b ← b'

On utilise des variables intermédiaires pour garantir que a, b ← b, a échange bien les valeurs des deux variables.

Tableaux

On va souvent manipuler (affecter, copier, créer) des parties de tableaux. Plutôt que d'expliciter les différentes boucles nécessaires à ces opérations qui alourdissent le pseudo code on aime à les remplacer par des notations plus compactes.

Ces différentes affectations ne sont pas des instructions simples, mais nécessitent des boucles.

Affectation d'une tranche de tableau

Abus de notation

Plusieurs affectations en même temps :

T[a:b] ← k

Pour remplacer :

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]

Les affectations de tranches ne sont pas des instructions simples, mais nécessitent plusieurs instructions : celles de la boucle sous-jacente.

Ainsi, le code suivant nécessite $1 + j - i$ instructions (1 instruction de création du nouveau tableau puis j-i affectations) :

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

Création de tableaux

Abus de notation

Création directe d'objets tableaux :

[1, 2, 3]

Pour remplacer :

T ← [3]int
T[0] ← 1
T[1] ← 2
T[2] ← 3

On pourra alors aussi directement créer un nouveau tableau et l'affecter :

Abus de notation

Création directe d'objets tableaux :

ref T []int ← [1, 2, 3]
ref T' []int ← [1 .. 10[

voire encore plus directement :

ref T ← [1, 2, 3]
ref T' ← [1 .. 10[

Pour remplacer :

ref T []int
T ← [3]int

T[0] ← 1
T[1] ← 2
T[2] ← 3

ref T' []int
T' ← [9]int

pour chaque i de [0 .. 9[:
    T[i] ← i + 1

Concaténation

Abus de notation

Création de tableau par concaténation de deux tableaux de même type :

ref T ← T1 + T2

Pour remplacer :

ref T ← [T1.longueur + T2.longueur](type T1)

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

Liste en compréhension

On pourra aussi utiliser les listes en compréhension (list comprehension) popularisées par python. De nombreux formats existent, du moment que c'est compréhensible :

Abus de notation

Écriture à la python :

[<expression> pour chaque <variable> de <énumérable> si <condition logique>]

Ou plus ensembliste :

[<expression> | <variable> ∈ <énumérable>, <condition logique>]

Par exemple :

[2 * x pour chaque x de [1 .. 5]]   # [2, 4, 6, 8, 10]
[2 * x | x ∈ [1 .. 5]]

Ou, avec la notation mathématique :

[1 + 4 * k pour chaque k de [1 .. ] si 1 + 4 * k < 20]   # [5, 9, 13, 17]
[1 + 4 * k | k ∈ [1 .. ], 1 + 4 * k < 20]  
[1 + 4 * k |  1 ≤ k ≤ 4]

Pour que la notation mathématique soit déterministe, on suppose que la variable sera énumérée selon l'ordre sous-jacent de l'ensemble.

Variable muette

Si on n'utilise pas la variable de boucle on utilise une variable muette _ :

pour chaque _ de [1 .. k]:
    # ...