Algorithmique, programmation

Lionel GUEZ∗

École normale supérieure – L3 sciences de la planète Terre

23 octobre 2012

Table des matières

1 Introduction aux langages et méthodes de programmation 1

2 Langage de description d’algorithmes 3

2.1 Variables et types . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2 Les instructions simples . . . . . . . . . . . . . . . . . . . . . . . 5
2.3 Les instructions composées . . . . . . . . . . . . . . . . . . . . . 6
2.3.1 La séquence . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.3.2 L’alternative . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.3.3 L’itération . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.4 Complément : les tableaux . . . . . . . . . . . . . . . . . . . . . . 9

3 Présentation des algorithmes et programmes 10

4 Conception descendante 11

5 Sous-algorithmes 13
5.1 Cas particulier : les fonctions . . . . . . . . . . . . . . . . . . . . 15

6 Conception des algorithmes avec sous-algorithmes 17

1 Introduction aux langages et méthodes de pro-

grammation
Ce cours présente des concepts communs aux divers langages de programma-
tion utilisés en calcul scientifique, des méthodes utiles pour tous ces langages,
et des conseils généraux.
Les langages concernés sont dits “impératifs”. Un langage impératif est un
langage de programmation constitué de différentes catégories syntaxiques. Ce
sont principalement les déclarations (de variables, de types, de procédures), les
expressions, les instructions et les procédures. Lorsqu’un programme impératif
est exécuté, des opérations (c’est-à-dire des instructions et éventuellement des
∗ Emprunts nombreux au cours de Philippe FACON, Institut d’informatique d’entreprise,
1988, et au mémoire d’habilitation à diriger des recherches de Sandrine BLAZY, Université
d’Évry, 2008.

1
expressions, selon le langage considéré) modifient l’état du programme, c’est-à-
dire les valeurs de certaines variables du programme, stockées dans une mémoire.
Le caractère impératif du langage provient de l’exécution en séquence des ins-
tructions du programme.
On peut distinguer des langages interprétés et des langages compilés. La
compilation est une traduction du programme en un langage spécifique au pro-
cesseur utilisé. C’est une étape qui précède l’exécution du programme. Cf. figure
(1). La compilation crée un nouveau fichier (qui n’est pas un texte lisible), dit

programme
Python exécution
(texte lisible) interpréteur résultats
Python
données

compilation
programme
Fortran compilateur
Fortran programme exécution
(texte lisible)
machine, système résultats
fichier d'exploitation
exécutable
données

Figure 1 – Langage interprété et langage compilé. Pour un langage interprété,

l’exécution est confiée à l’interpréteur du langage. Pour un langage compilé,
l’exécution est prise en charge directement par le système d’exploitation.

fichier exécutable. C’est ce fichier exécutable dont on lance l’exécution. Avec un

langage interprété, le fichier contenant le texte du programme est directement
exécutable. Fortran, C et C++ sont des exemples de langages compilés. Python
et Bash sont des exemples de langages interprétés. Un programme en langage
compilé donne en principe un exécutable plus rapide qu’un programme analogue
en langage interprété.
Un programme manipule des objets : des noms, des entiers, des tableaux,
des ensembles, etc. auxquels sont associées des opérations. Une variable dans un
programme a un nom, un type (entier, logique . . .) et peut recevoir une valeur. Le
type détermine les opérations possibles pour la variable et les valeurs possibles.
Le programme enchaı̂ne des opérations dans des structures. On distingue
trois structures :
la séquence :
instruction 1
instruction 2
instruction 3
l’alternative :
si a > b alors
...
sinon

2
 ...
fin si
l’itération : répéter
Ces trois structures sont suffisantes. C’est-à-dire que, théoriquement, tout pro-
gramme peut être écrit avec seulement ces trois structures.
À partir de l’énoncé d’un problème de programmation, avant d’arriver au
programme, nous pouvons d’abord décrire dans un langage naturel la méthode
de résolution du problème. Cf. figure (2). Nous pouvons passer ensuite à la des-

méthode de algorithmes
résolution du de plus en
problème plus détaillés
(langage naturel)
problème
programme

(difficile) en langage de
description
d'algorithmes
informel

Figure 2 – Intérêt d’un langage de description d’algorithme. Le problème peut

être quelconque (paye, échecs, intégration numérique . . .).

cription dans un “langage de description d’algorithmes”. Le langage de descrip-

tion d’algorithmes a les caractéristiques principales d’un langage de program-
mation mais avec une syntaxe plus libre, et des parties informelles à détailler
plus tard. Nous décrirons dans la suite de ce cours le langage de description
d’algorithmes.
L’information nécessaire à l’exécution d’un programme inclut la liste des
instructions à exécuter et l’ensemble des objets manipulés par le programme,
variables, constantes, avec leurs valeurs. Lors de l’exécution d’un programme,
toute cette information est conservée dans une partie de l’ordinateur appelée
“mémoire vive”, ou encore “mémoire centrale”. Cette information n’existe que
le temps de l’exécution du programme. La mémoire vive, dédiée à l’exécution
des programmes, n’a donc en général rien à voir avec l’espace disque sur lequel
vous stockez vos fichiers. Au fur et à mesure de l’exécution d’un programme, la
mémoire vive consacrée à ce programme passe par une suite d’états. Cf. figure
(3). Chaque état est caractérisé par :
– le point du programme en cours ;
– l’environnement, c’est-à-dire l’état des variables.

2 Langage de description d’algorithmes

Cette partie décrit un langage possible pour la description d’algorithmes.
Les notations du langage choisies ici ne sont pas universelles. L’important est
le niveau de formalisation du langage, intermédiaire entre un langage naturel et
un langage de programmation.

3
 program exe1_1
implicit none

texte du
integer, parameter:: n = 3
logical mask(n,n)
integer id(n,n)
integer, dimension(n):: diagon = 1
integer i, j
character(len=12) fmt
mask = reshape((/ ((i == j, j = 1, n), i = 1, n) /), (/ n, n /))
programme
id = unpack(diagon, mask, 0)
write(unit=fmt,fmt='(a,i3,a)') '(', n, '(i1,1X))'
print *, 'id :'
do i = 1, n
write (unit=*,fmt) id(i,:)
end do
end program exe1_1

mémoire
variables du
programme
machine

Figure 3 – Suite d’états de la mémoire associée à un programme, pendant son

exécution.

2.1 Variables et types

On utilise des types de base, prédéfinis :
Type entier : Ensemble de valeurs : Z, ensemble des entiers relatifs. Opérations
arithmétiques usuelles.
Type réel : Ensemble de valeurs : R. Opérations arithmétiques usuelles.
Type texte : Ensemble des suites de caractères. Une suite de caractères est
notée entre guillemets :
"Il fait beau."
L’opération prédéfinie entre les suites de caractères est la concaténation,
notée “//” :
texte1 // texte2
Type logique : Seulement deux valeurs possibles : vrai, faux. Les opérations
sur ce type sont : et logique (notation ∧), ou logique (notation ∨), négation
(notation ¬), implication (⇒) . . .
On peut aussi utiliser, en plus des types de base, des types à définir. Entre
autres :
Type partie d’ensemble : Les valeurs sont les parties d’un type donné. Les
opérations sont : réunion ∪, intersection ∩, appartenance ∈ . . .
Type cartésien : Le type est défini par une succession particulière de champs,
chaque champ pouvant avoir un type quelconque. On notera par exemple,
pour un type appelé “personne” contenant un champ nom et un champ
nombre_enfants :

4
 type personne
nom: texte
nombre_enfants: entier
...
fin type
Attention : dans cet exemple, “personne” est le nom du type, pas un nom
de variable.
On peut associer un type à une variable par une déclaration. On notera la
déclaration sous la forme “type : variable”. Par exemple :
personne: X

Ce qui signifie que X est une variable de type personne. Le champ nom de X,
que l’on notera X%nom, peut recevoir une valeur, par exemple ”Dupond”.
Une“expression”est une combinaison de constantes ou variables. Les constantes
ou variables sont combinés avec des opérateurs. Les opérateurs utilisés doivent
être cohérents avec le type des objets combinés. Une expression peut être sim-
plement une valeur littérale, par exemple la valeur entière 3, ou la valeur chaı̂ne
de caractères “bonjour”. Une expression peut aussi être simplement une variable,
par exemple la variable réelle x. Une expression contenant une opération est par
exemple l’expression x + 3.

2.2 Les instructions simples

Les instructions simples sont les entrées-sorties et l’affectation.
Les entrées-sorties sont des échanges entre la mémoire centrale et l’extérieur :
écran, clavier, mémoire de stockage. Pour les entrées, la syntaxe du langage de
description d’algorithmes est :
entrer (ma_variable)
qui signifie : attendre une valeur de l’extérieur, l’affecter à ma_variable. On
pourra aussi écrire l’instruction avec plusieurs variables, par exemple :
entrer (x, y, z)
Pour les sorties, la syntaxe est :
écrire (expression)

qui signifie : calculer la valeur de l’expression et l’écrire. On pourra aussi écrire

plusieurs expressions :
écrire (expression1, expression2, ...)
La syntaxe pour l’affectation est :

ma_variable := expression
qui signifie : calculer la valeur de l’expression et l’affecter à ma_variable.
Exemple :
x := y > z

5
où x est une variable de type logique. Dans cet exemple, y et z peuvent par
exemple être des variables de type entier, et y > z est une expression de type
logique.
Il est utile d’insérer dans un algorithme des assertions. Les assertions sont des
propositions (au sens de la logique mathématique) vraies qui caractérisent l’état
de la mémoire, ou une partie de l’état de la mémoire. Les assertions caractérisent
formellement l’effet des instructions. On notera les assertions entre accolades.
Par exemple :

{x + q * y = a et y > q}
x := x - y
Nous avons une assertion avant l’instruction d’affectation. Quelle assertion pouvons-
nous écrire après l’affectation ? La valeur de x a été modifiée par l’affectation.
Si nous notons x0 l’ancienne valeur, nous avons :

{x’ + q * y = a et y > q et x = x’ - y}
Éliminons l’ancienne valeur pour obtenir une assertion entre les variables qui
existent dans l’algorithme. Nous pouvons écrire après l’affectation :
{x + (q + 1) * y = a et y > q}

2.3 Les instructions composées

Les instructions composées sont la séquence, l’alternative et l’itération.

2.3.1 La séquence
Syntaxe de la séquence : on écrira simplement une instruction par ligne.

instruction1
instruction2
instruction3
qui signifie : exécuter instruction1 puis, de l’état obtenu, exécuter instruction2,
etc.
Exemple d’assertions avec une séquence :
{x = a et y = b}
x := x + y
{x = a + b et y = b}
y := x - y
{x = a + b et y = a}

2.3.2 L’alternative
Syntaxe de l’alternative :
si expression logique alors
instruction1
sinon
instruction2
fin si

6
qui signifie : évaluer l’expression logique ; si elle est vraie, exécuter instruction1,
sinon exécuter instruction2.
On peut caractériser formellement la sémantique d’une alternative en utili-
sant des assertions. En partant d’une assertion P avant l’alternative :
{P}
si C alors
{P et C} instruction1 {P1}
sinon
{P et non C} instruction2 {P2}
fin si
{P1 ou P2}
Ou en remontant l’alternative à partir d’une assertion Q :
{(Q1 et C) ou (Q2 et non C)}
si C alors
{Q1} instruction1 {Q}
sinon
{Q2} instruction2 {Q}
fin si
{Q}

2.3.3 L’itération
Syntaxe de l’itération :
tant que condition faire
instruction
fin tant que
où la condition est une expression logique. Ce qui signifie : évaluer la condition ;
si elle est vraie, exécuter l’instruction puis revenir à l’évaluation de la condition ;
si la condition est fausse, ne rien faire.
Deux modes de raisonnement correspondent à l’itération. Premier mode : ré-
pétition d’un même traitement sur des objets différents. Par exemple :
tant que lecture d’une ligne de mon fichier réussie faire
traitement à partir de la ligne lue
essai de lecture d’une nouvelle ligne de mon ficher
fin tant que
Deuxième mode de raisonnement : calcul du terme final d’une suite définie par
récurrence. Dans ce cas, on utilise à chaque passage le résultat du passage pré-
cédent. Exemple :
entrer (A, B)
I := 0
C := 0
tant que I < B faire
I := I + 1
C := C + A
fin tant que
écrire (C)
Comme pour l’alternative, caractérisons formellement la sémantique d’une
itération à l’aide des assertions. Notons C la condition de l’itération et P une

7
proposition quelconque. Si l’instruction à l’intérieur de l’itération fait passer de
l’assertion P ∧C à l’assertion P :
{P et C } instruction1 {P}
alors P est appelé un invariant de la boucle. Si P est vrai avant la boucle, on a
les assertions :
{P}
tant que C faire
instruction1
fin tant que
{P et non C }
Exemple :
entrer (A, B)
I := 0
C := 0
{C = A * I}
tant que I 6= B faire
{C = A * I et I 6= B}
I := I + 1
C := C + A
{C = A * I}
fin tant que
{C = A * I et I = B}
écrire (C)
L’utilisation des assertions a ainsi permis de prouver l’effet de l’algorithme.
Lorsque l’algorithme itératif ne semble pas évident à écrire, l’utilisation des
invariants de boucle permet de bien poser le problème et d’arriver à une solution
sûre. La méthode conseillée pour écrire un algorithme itératif est donc :
1. Trouver une idée informelle de la boucle.
2. La traduire en invariant INV
3. Trouver une condition de sortie CS telle que : (invariant et condition de
sortie) ⇒ résultat final.
4. Initialiser avec une suite d’instructions INIT telle qu’on ait l’invariant après
cette initialisation :
INIT {invariant}
5. Trouver une instruction I qui permette de se rapprocher de CS en gardant
INV vrai.
6. Il ne reste qu’à assembler les éléments précédents. L’algorithme s’écrit :

INIT
tant que non CS faire
I
fin tant que
Nous avons vu l’itération avec la structure “tant que”. L’itération peut aussi
s’écrire sous quelques formes variantes. La variante“répéter”:
répéter
I

8
 jusqu’à C
qui signifie : exécuter l’instruction I ; évaluer la condition C ; si elle est fausse,
revenir à l’exécution de l’instruction. Une itération avec la structure “répé-
ter” peut toujours s’écrire de façon équivalente comme une itération avec “tant
que” :
I
tant que non C faire
I
fin tant que
L’écriture de l’itération avec “répéter” est plus concise ; on ne peut l’utiliser que
si l’instruction I doit être exécutée au moins une fois.
Une autre variante de l’itération est la variante“pour”:
pour X = V1 à V2 faire
I
fin pour
où X est un nom de variable d’un type discret, ordonné, et V1, V2 sont des
valeurs du type de X, avec V1 ≤ V2. Une itération avec la structure “pour”
peut toujours s’écrire de façon équivalente comme une itération avec “tant
que” :
X := V1
tant que X ≤ V2 faire
I
X := successeur(X)
fin tant que
Exemple :
pour I = 1 à 10 faire
Instructions
fin pour
est équivalent à :
I := 1
tant que I ≤ 10 faire
Instructions
I := I + 1
fin tant que
L’écriture avec “pour” est plus concise ; on ne peut l’utiliser que si on connaı̂t
avant le début de la boucle le nombre d’itérations à réaliser.

2.4 Complément : les tableaux

Le tableau est une structure de données. Les éléments d’un tableau contiennent
des valeurs d’un même type. Chaque élément du tableau a un indice, qui est
une valeur entière. Les indices prennent toutes les valeurs comprises entre une
borne inférieure et une borne supérieure. Les bornes sont des valeurs entières,
qui peuvent être négatives. Exemple de déclaration de tableau :
réel tab(1: 10)
qui signifie que tab est une variable tableau, qui contient des éléments de type
réel, avec des indices entre 1 et 10 (tab contient donc 10 éléments). On peut

9
généraliser à plusieurs indices :
réel tab2(1: 10, -2: 3)

qui signifie que tab2 est un tableau de réels, avec un premier indice variant de
1 à 10 et un second indice variant de -2 à 3 (tab2 contient donc 60 éléments).
On dira que tab2 a deux dimensions.
Notation pour l’accès à un élément du tableau :
nom_tableau(expression_entière)

L’expression entière donne une valeur d’indice et détermine donc l’élément de

tableau référencé. Exemples :
tab(i * j - 3)
tab(i) + tab(j)

où i et j sont des variables entières.

3 Présentation des algorithmes et programmes

En langage de description d’algorithme, on écrira toutes les déclarations
avant les instructions. On peut déclarer des variables (y compris des tableaux),
des types (autres que les types prédéfinis) et des constantes symboliques. Les
constantes symboliques sont des valeurs, non modifiables, auxquelles on donne
un nom. En langage de description d’algorithme, on les écrira avec le mot-clef
“constante”. Par exemple :
constante réelle pi = 3.141592654
De manière générale, en langage de description d’algorithme et dans n’importe
quel langage de programmation, faire l’effort de donner un nom significatif aux
variables. Il est conseillé aussi de regrouper les déclarations selon leur proximité
logique (plutôt que selon leur forme dans le langage).
De manière générale, en langage de description d’algorithme et dans n’im-
porte quel langage de programmation, la clarté de l’algorithme ou du programme
repose en partie sur l’indentation des instructions. Le principe de l’indentation
est de faire commencer les instructions d’une séquence à la même colonne, tan-
dis que, dans les alternatives et les itérations, les sous-instructions sont décalées.
Par exemple :
1: X := 3
2: si C alors
3: instruction1
4: instruction2
5: fin si
6: Y := 2
Les lignes numéros 1, 2, 5, 6 commencent à la même colonne. Les lignes 3 et 4
sont décalées.
Les commentaires sont en général nécessaires tout au long de l’algorithme ou
du programme. Ils peuvent être de plusieurs types et il est utile de choisir des
notations différentes en langage de description d’algorithme pour les distinguer :

10
Commentaire titre : titre d’une partie de l’algorithme. Notation possible :
entre étoiles. Par exemple :
* Tri du tableau *
Commentaire assertion Notation : entre accolades {...}.
Autre commentaire : expliquer le rôle d’une variable dans les déclarations ;
explications sur un passage délicat, etc. Notation possible : (*...*).
L’interface avec l’utilisateur peut être oubliée dans l’écriture de l’algorithme
mais requiert un minimum d’effort dans le programme finale. Chaque demande
de donnée et chaque sortie de résultat doit être précédée d’un message explicite.

4 Conception descendante
La conception descendante est une méthode de conception d’algorithme.
Principe : concevoir l’algorithme niveau par niveau, de plus en plus détaillé.
Chaque niveau s’écrit à l’aide des trois structures algorithmiques, plus des par-
ties simplement spécifiées, dont le contenu n’est pas donné.
Exemple : tri d’un tableau. Nous avons le tableau :
entier t(1:20)
Nous voulons trier les valeurs par ordre croissant. Suivons la méthode conseillée
dans le § 2.3.3 pour écrire un algorithme itératif. Première étape : idée informelle
de l’algorithme. Sur une séquence de quatre valeurs, nous progressons dans le
tri case par case, vers la droite. Si par exemple nous avons au départ la séquence
de valeurs :
3 7 5 2
Nous cherchons la plus petite valeur dans la séquence et nous la plaçons en
première position :
2 3 7 5
À l’itération suivante, nous obtenons :
2 3 5 7
(Nous ne prétendons pas ici donner l’algorithme de tri le plus rapide.) Seconde
étape : formaliser. Quel est l’invariant ? À un moment donné de la progression
du tri, les i plus petites valeurs sont à leur place finale dans le tableau :
i

La proposition :
{les i plus petites valeurs sont à leur place}
est l’invariant. La condition de sortie est :
i = n - 1

11
L’initialisation s’écrit simplement :
i := 0
Après cette initialisation, nous avons bien l’invariant. Nous trouvons ensuite
une instruction qui nous permet de nous rapprocher de la condition de sortie en
gardant l’invariant vrai :
i := i + 1
p := la place du plus petit élément entre i et n inclus
permuter t(i) et t(p)
Dans les lignes ci-dessus, nous n’avons pas précisé comment nous allions trouver
la place du plus petit élément entre i et n inclus. De même, nous n’avons pas
précisé les instructions qui permettent de permuter t(i) et t(p). C’est en écrivant
ainsi un premier algorithme de haut niveau avec des parties dont le contenu
n’est pas encore donné, que nous suivons une conception descendante. Nous
regroupons les éléments (initialisation, condition de sortie, instructions du corps
de la boucle) que nous avons obtenus ci-dessus et nous obtenons l’algorithme de
plus haut niveau : l’algorithme (1). Pour le second niveau de l’algorithme, nous

Algorithme 1 Algorithme de plus haut niveau pour le tri d’un tableau.

i := 0
tant que i 6= n - 1 faire
i := i + 1
p := la place du plus petit élément entre i et n inclus
permuter t(i) et t(p)
fin tant que

explicitons ce que nous avions simplement spécifié :

p := la place du plus petit élément entre i et n inclus
À nouveau, nous suivons la méthode du § 2.3.3. Idée informelle : nous progres-
sons vers la droite à partir de l’élément i.
i p j n

Invariant :
{p est la place du petit élément entre i et j}
Condition de sortie :
j = n
Initialisation :
j := i
p := i
Les instructions à placer à l’intérieur de la boucle, qui nous rapprochent de la
condition de sortie, en gardant l’invariant vrai, sont :

12
 j := j + 1
si t(p) > t(j) alors
p := j
fin si
D’où l’algorithme (2), de second niveau (algorithme final dans cet exemple).

Algorithme 2 Algorithme de second niveau pour le tri d’un tableau.

i := 0
tant que i 6= n - 1 faire
i := i + 1

* recherche de la place p du plus petit élément entre i et n inclus *

j := i
p := i
tant que j 6= n faire
j := j + 1
si t(p) > t(j) alors
p := j
fin si
fin tant que

* permutation de t(i) et t(p) *

c := t(i)
t(i) := t(p)
t(p) := c
fin tant que

5 Sous-algorithmes
L’idée de sous-algorithmes est celle de décomposer un problème en sous-
problèmes. Par exemple, on peut avoir isolé le sous-problème du calcul du mi-
nimum de trois nombres. On écrit alors un sous-algorithme, auquel on donne
un nom, mettons min3, qui prend trois valeurs en entrée, mettons x, y, z et
qui a pour résultat une valeur, mettons p. x, y, z, p sont appelés les arguments
du sous-algorithme. En langage de description d’algorithme, pour noter l’appel
d’un sous-algorithme, on écrira simplement son nom, suivi des arguments entre
parenthèses. Par exemple :
min3(a, b, c, r)
min3(10, y + 4, a - 1, l)

On peut relever plusieurs intérêts à isoler des sous-algorithmes :

– la non duplication de lignes si on appelle plusieurs fois un sous-algorithme ;
– la possibilité de ré-utilisation dans un autre algorithme ;
– l’amélioration de la clarté de l’algorithme, en rendant apparente sa décom-
position ;
– la simplicité des sous-algorithmes isolés ;
– la facilité de mise au point de l’algorithme et des sous-algorithmes.

13
 Dans le sous-algorithme, on fait référence aux arguments, qui sont appelés
arguments formels, ou muets. Cf. figure (4). À l’appel du sous-algorithme, on

arguments effectifs

appelant foo (x, y, z, …)

appelé sous-algorithme foo (a, b, c, …)

arguments muets
(ou formels)

Figure 4 – Arguments effectifs et arguments muets.

choisit des arguments, qui sont appelés arguments effectifs. On dit qu’un argu-
ment muet est une donnée du sous-algorithme si la valeur provenant de l’ar-
gument effectif correspondant est seulement utilisée dans le sous-programme,
ou en d’autres termes si la valeur de l’argument muet n’est pas modifiée dans
le sous-programme. Dans le cas contraire, on dit que l’argument muet est un
argument résultat du sous-programme. Si un argument muet est une donnée,
l’argument effectif correspondant ne doit pas nécessairement être une variable,
ce peut être une expression quelconque. Cf. le deuxième exemple d’appel de
min3, ci-dessus : 10, y + 4 et a - 1 sont des expressions qui ne sont pas ré-
duites à une variable. Si un argument muet est un résultat du sous-algorithme,
l’argument effectif correspondant doit être un nom de variable.
Les variables utilisées dans un sous-algorithme autres que les arguments
muets sont appelées variables locales. Les variables locales à un sous-algorithme
ne sont pas connues de l’algorithme principal et ne peuvent pas être modifiées
dans l’algorithme principal. Exemple :
1: sous-algorithme min3(a, b, c, x)
2: données entier a, b, c
3: résultat entier x
4: entier m
5: si a ≤ b alors
6: m := a
7: sinon
8: m := b
9: fin si
10: si m ≤ c alors
11: x := m
12: sinon
13: x := c
14: fin si
À la ligne 2, on déclare a, b et c, comme des arguments de type entier, et comme
des données du sous-programme. À la ligne 3, on déclare x comme un argument
résultat de type entier. À la ligne 4, on déclare une variable entière m qui n’est

14
pas dans la liste des arguments figurant entre parenthèses ligne 1. m est donc
une variable locale du sous-algorithme. m n’est pas connue à l’extérieur de min3.
Il peut y avoir une variable m dans l’algorithme principal, qui n’interfère pas
avec la variable m de min3.
Un sous-algorithme peut lui-même contenir un sous-algorithme. En d’autres
termes, des sous-algorithmes peuvents être emboı̂tés les uns dans les autres.
Dans l’exemple du minimum de trois nombres, on pourrait imaginer un sous-
algorithme de min3 calculant le minimum de deux nombres :
1: sous-algorithme min3(a, b, c, x)
2: données entier a, b, c
3: résultat entier x
4: entier m
5:
6: sous-algorithme min2(x, y, r)
7: données entier x, y
8: résultat entier r
9: si x ≤ y alors
10: r := x
11: sinon
12: r := y
13: fin si
14: fin min2
15:
16: min2(a, b, m)
17: min2(m, c, x)
Les lignes 6 à 14 sont une déclaration dans min3 du sous-algorithme emboı̂té
min2. Les instructions de min3 sont seulement aux lignes 16 et 17. Si on choisit de
définir un sous-algorithme comme emboı̂té, il ne doit pas être appelé à l’extérieur
de l’algorithme qui le contient. Dans l’exemple ci-dessus, min2 ne peut pas être
appelé à l’extérieur de min3. On aurait pu choisir de définir min2 comme sous-
algorithme extérieur à min3. Le choix d’emboı̂ter ou non un sous-algorithme est
une question de clarté. Il faut se demander où le sous-algorithme en question a
vocation à être appelé.
Remarque : un argument d’un sous-algorithme peut être lui-même un sous-
algorithme. Par exemple, nous pouvons écrire un sous-algorithme cherchant le
zéro d’une fonction quelconque, et donc avoir la fonction en argument.

5.1 Cas particulier : les fonctions

Une fonction est une structure équivalente à un sous-algorithme dans le cas
particulier où un seul argument muet du sous-algorithme est un résultat, tous
les autres arguments muets du sous-algorithme étant des données. Cf. figure (5).
Notation pour l’appel à une fonction : nom de la fonction avec entre parenthèses
les arguments effectifs qui sont des données. Par exemple :
r := min3(a, b, c)

La notation min3(a, b, c) représente maintenant une expression, incluse dans

une instruction, et non plus une instruction à elle toute seule. En langage de
description d’algorithme, on utilise le mot clef “fonction” dans la déclaration

15
 données résultat
sous-algorithme bar(x, y, z, f )

forme préférable fonction f (x, y, z)

données

Figure 5 – Cas d’équivalence entre un sous-algorithme et une fonction.

d’une fonction. Dans le corps de la fonction seulement, le nom de la fonction est

considéré comme une variable, dans laquelle on doit placer le résultat de l’appel
de la fonction. Cf. par exemple algorithmes (3) et (4). min3 ne contient qu’une

Algorithme 3 fonction min2(x, y)

entier min2
données entier x, y
si x ≤ y alors
min2 := x
sinon
min2 := y
fin si

Algorithme 4 fonction min3(a, b, c)

1: entier min3
2: données entier a, b, c
3: min3 = min2(min2(a, b), c)

instruction : à la ligne 3. À l’intérieur de la fonction min3, aux lignes 1 et 3,

min3 est une variable comme une autre.
Lorsqu’un sous-algorithme n’a qu’un argument muet résultat, les autres ar-
guments muets éventuels étant des données, il est préférable de l’écrire sous
forme de fonction. Données et résultat sont plus clairement séparés. En outre,
puisque le résultat de la fonction est utilisé comme une expression, l’utilisation
de variables intermédiaires dans l’algorithme appelant peut parfois être évitée.
Autre exemple : nous souhaitons lire des suites de trois caractères et écrire,
pour chaque suite, si elle est dans l’ordre croissant, décroissant ou ni l’un ni
l’autre. L’utilisateur indiquera la dernière suite par ***. Pour effectuer ce trai-
tement, nous écrivons deux fonctions et un algorithme principal. Cf. algorithmes
(5), (6) et (7). Noter dans cet exemple l’économie en variables intermédiaires
grâce à l’utilisation de fonctions.

16
Algorithme 5 fonction ordc(x, y, z)
logique ordc
données caractère x, y, z
ordc := x ≤ y et y ≤ z

Algorithme 6 fonction fin(x, y, z)

logique fin
données caractère x, y, z
fin := x == ”*” et y == ”*” et z == ”*”

6 Conception des algorithmes avec sous-algorithmes

C’est une forme de conception descendante. On décompose un problème
en sous-problèmes et on associe un sous-algorithme à chaque sous-problème.
Chaque sous-algorithme doit être paramétré, c’est-à-dire que ses arguments
doivent être décrits. Les arguments peuvent être des données, des résultats ou
des données-résultats. La spécification du sous-algorithme précise l’effet du sous-
algorithme : les résultats, les écritures par le sous-algorithme, et les valeurs fi-
nales des arguments données-résutats en fonction des données, des entrées dans
le sous-algorithme, et des valeurs initiales des arguments données-résutats. Cf.
figure (6). Par exemple, un sous-algorithme de tri peut avoir pour arguments :
tableau entier donnée-résultat t
et comme spécification :
t final = t initial trié dans l’ordre croissant
Ce sous-algorithme peut lui-même utiliser une fonction dont l’interface serait :
fonction pmin(t, i)
tableau entier donnée t
entier donnée i
et la spécification :

Algorithme 7 Algorithme principal pour l’ordre d’une suite de trois caractères.

entrer(a,b, c)
tant que non fin(a, b, c) faire
si ordc(a, b, c) alors
écrire(”ordre croissant”)
sinon
si ordc(c, b, a) alors
écrire(”ordre décroissant”)
sinon
écrire(”ni croissant ni décroissant”)
fin si
fin si
entrer(a,b, c)
fin tant que

17
 D R
E S
Minitial Mfinal

Figure 6 – Spécification d’un sous-algorithme. D : arguments données, E :

entrées directes (dans le corps du sous-algorithme), R : arguments résul-
tats, S : écritures directes (dans le corps du sous-algorithme), M : arguments
données-résultats. La spécification indique comment (R, S, Mfinal ) dépend de
(D, E, Minitial ).

pmin(t, i) = l’indice du plus petit élément entre t(i) et le dernier

élément de t
Les étapes à suivre, dans l’ordre, dans l’esprit de la conception descendante,
sont :
1. préciser les arguments ;
2. écrire la spécification ;
3. utiliser le sous-algorithme dans l’algorithme appelant ;
4. écrire le sous-algorithme.
Prenons un exemple de conception descendante avec sous-algorithme. Nous
voulons dessiner la forme représentée sur la figure (7), à l’aide de simple carac-
tères, par exemple des étoiles : *.

10

10 x

70
y

Figure 7 – Exemple de conception descendante : forme à dessiner.

18
Idée. Une solution rigide et laborieuse consisterait à réaliser le dessin ligne par
ligne. Une meilleure solution consiste à superposer des rectangles. Nous
pouvons d’abord réaliser le dessin dans un tableau puis afficher le tableau
ligne à ligne. Tableau utilisé :
caractère d(60, 60)
Algorithme principal. Après l’initialisation du tableau d, l’algorithme prin-
cipale décompose juste le problème en deux sous-problèmes décrits en
langage naturel :
d = ’ ’ (* mise à blanc du tableau *)
dessin des rectangles dans le tableau
écriture du tableau
Il faut maintenant formaliser les sous-problèmes, c’est-à-dire faire appa-
raı̂tre des sous-algorithmes, avec des spécifications.
Sous-algorithme d’écriture du tableau. Il peut s’écrire :
* écriture du tableau *
pour i = 1 à n faire
écrire(d(i, :))
fin pour
Interface du sous-algorithme rectangle. Elle s’écrit :
sous-algorithme rectangle(x, y, l, h, t)
entier données x, y, l, h
caractère donnée-résultat t(60, 60)
Spécification du sous-algorithme rectangle. Le sous-algorithme met dans
le tableau t un rectangle dont le coin inférieur gauche est au couple d’in-
dices (x, y), la largeur est l et la hauteur est h. Parler de coin “inférieur”
suppose une représentation géométrique de t. Nous considérerons que le
“haut” du tableau correspond à l’indice de ligne 1.
Utilisation du sous-algorithme rectangle. Dans l’algorithme principal :
* dessin des rectangles *
x := 10
y := 45
l := 50
h := 20
pour i = 0 à 4 faire
rectangle(x + 5i, y + 5i, l - 10i, h + 10i, d)
fin pour
Il ne reste qu’à écrire le contenu, ou encore la réalisation, du sous-algorithme
rectangle.
Réalisation de rectangle. Le sous-algorithme peut s’écrire :
* lignes horizontales *
t(x: x + l, y) = "*"
t(x: x + l, y - h) = "*"
* lignes verticales *
t(x, y - h: y) = "*"
t(x + l, y - h: y) = "*"

19