Algorithmique, programmation
Lionel GUEZ∗
guez@[Link]
Bureau E224
23 juillet 2018
École normale supérieure – L3 sciences de la planète
Table des matières
1 Introduction 1
2 Concepts 2
3 Langage d’algorithme 5
3.1 Variables et types . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3.2 Les tableaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3.3 Les instructions simples . . . . . . . . . . . . . . . . . . . . . . . 7
3.4 Assertions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.5 Les instructions composées . . . . . . . . . . . . . . . . . . . . . 8
3.5.1 La séquence . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.5.2 L’alternative . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.5.3 L’itération . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
4 Conseils de présentation 13
5 Conception descendante 14
6 Idéaux 16
7 Procédures 17
7.1 Choix entre sous-algorithme et fonction pure . . . . . . . . . . . 21
8 Conception avec procédures 23
1 Introduction
Ce cours présente des concepts communs aux divers langages de programma-
tion utilisés en calcul scientifique et des conseils généraux de programmation.
∗ Emprunts nombreux au cours de Philippe FACON, Institut d’informatique d’entreprise,
1988.
1
Nous nous plaçons donc à un niveau logique, que nous distinguons de l’écri-
ture du code des programmes. L’idée est de repousser à une étape ultérieure
les problèmes de programmation spécifiques à un langage de programmation
particulier et les problèmes de détail.
Le produit du travail au niveau logique est un “algorithme”. Un algorithme
est une suite finie, séquentielle, de règles que l’on applique à un nombre fini
de données, pour résoudre des classes de problèmes semblables. Par exemple :
l’algorithme d’Euclide permet de trouver le plus grand commun diviseur de deux
nombres entiers.
Exemple : algorithme d’Euclide
a et b 2 entiers naturels
non nuls et a > b
a prend la valeur de b calculer le reste r de la
b prend la valeur de r division de a par b
non
r=0?
oui
PGCD = b
Ce cours introduit un outil pour travailler au niveau logique : le langage de
description d’algorithme. Le langage proposé ici est textuel (il existe aussi des
descriptions graphiques d’algorithmes, comme illustré pour l’algorithme d’Eu-
clide). On trouve aussi l’appellation pseudo-code pour ce langage textuel de
description d’algorithme.
Ce cours : langage textuel de description d’algorithme (“pseudo-
code”)
entrer (a, b)
{a et b 2 entiers naturels non nuls et a > b}
r = reste de la division de a par b
tant que r 6= 0 faire
a=b
b=r
r = reste de la division de a par b
fin tant que
écrire (b)
2 Concepts de base des langages de program-
mation impératifs
Les langages de programmation classiquement utilisés en calcul scientifique
sont dits “impératifs”. Dans un tel langage, un programme est une suite d’ins-
2
tructions, dans un ordre bien défini, qui modifient “l’état de la mémoire”. La
mémoire est essentiellement un ensemble de “variables”, qui contiennent des va-
leurs, en général des nombres ou du texte. On peut imaginer les variables comme
des cases portant des noms. Le programme lit ou modifie les valeurs contenues
dans ces cases. Lorsqu’un programme impératif est exécuté, la mémoire passe
donc par une suite finie d’états. Cf. figure (1).
program exe1_1
implicit none
integer, parameter:: n = 3
logical mask(n,n)
integer id(n,n)
integer, dimension(n):: diagon = 1
texte du
integer i, j
character(len=12) fmt
mask = reshape((/ ((i == j, j = 1, n), i = 1, n) /), (/ n, n /))
id = unpack(diagon, mask, 0)
programme
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 1 – Exécution d’un programme. La mémoire de la machine passe par
une suite finie d’états. Le grand rectangle contenant le texte du programme avec
des variables représente un état de la mémoire. Le pointeur à gauche du texte
du programme représente la position courante dans ce texte.
Définitions
— Type d’une variable : type de la valeur qu’elle contient. Exemples : nombre
entier, ou texte. Le type détermine les opérations possibles sur la variable.
Exemple : + - × / pour les entiers.
— Constante littérale : une valeur, écrite littéralement. Exemple : 2,718 282.
— Constante symbolique : un nom donné à une valeur littérale. Exemple : e
pour la base des logarithmes népériens. Non modifiable par le programme.
— Expression : combinaison d’opérations appliquées à des variables ou des
constantes.
— Procédure : suite d’instructions à laquelle on donne un nom.
Typage statique, déclarations. Dans certains langages de programmation,
le type d’une variable donnée est fixé à l’écriture du programme. On dit que
le typage est statique dans ce langage de programmation. Par exemple, les lan-
gages Fortran, C et C++ sont à typage statique. Le type d’une variable est
alors fixé dans une ligne particulière du programme qu’on appelle une ligne de
“déclaration”. En plus des déclarations de types des variables, on peut aussi
trouver des déclarations qui définissent de nouveaux types (ne pas confondre la
définition d’un nouveau type et la déclaration d’une nouvelle variable avec un
3
type pré-existant), des déclarations de constantes symboliques, des procédures.
Les lignes de déclarations ne modifient pas l’état de la mémoire, elles définissent
ou caractérisent des objets que le programme manipule.
Typage dynamique Dans d’autres langages de programmation, une variable
de nom donné peut voir son type changer en cours d’exécution. Le type de la
variable est déterminé par la valeur affectée à cette variable. On dit que le
typage est dynamique dans ce langage de programmation. Le langage Python
par exemple est à typage dynamique.
Types entier et réel. Les langages de programmation scientifique permettent
d’utiliser des valeurs de type entier ou de type réel. La distinction entre entiers et
réels n’est pas la même en informatique qu’en mathématiques. Mathématique-
ment, si un nombre est entier, il est aussi réel, tandis que, informatiquement,
une valeur est ou bien entière ou bien réelle. Chaque langage offre donc une
possibilité de distinguer une valeur entière d’une valeur réelle. Par exemple,
dans les langages scientifiques classiques, les écritures 2 et 2. (avec un point)
distinguent la valeur 2 considérée comme entière ou réelle. En outre, pour les
langages à typage statique, la déclaration d’une variable distingue le type entier
et le type réel. Une valeur entière n’est pas traitée comme une valeur réelle. La
différence est dans le “codage” de la valeur. Le codage est la représentation d’un
nombre dans la mémoire de l’ordinateur. Les nombres sont représentés par leur
développement en base 2. Le développement est exact pour les nombres entiers.
Pour les nombres réels, le codage inclut une mantisse et un exposant, avec un
nombre de chiffres binaires (des “bits”) fixé, et le développement est approché.
Par exemple, le développement binaire du nombre 0,1 est infini donc son codage
informatique ne peut qu’en donner une approximation. De même, les opérations
sur les entiers donnent des résultats exacts tandis que les opérations sur les réels
donnent des résultats approchés. En conclusion, le choix entre l’utilisation d’une
valeur informatique entière ou réelle n’est pas anodin. Préférez les valeurs in-
formatiques entières si vous n’avez besoin mathématiquement que de valeurs
entières.
Structures algorithmiques. 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
...
fin si
l’itération : répéter
(La signification de ces structures sera détaillée plus bas.) Ces trois structures
sont suffisantes. C’est-à-dire que, théoriquement, tout algorithme peut être écrit
4
avec seulement ces trois structures.
Mémoire vive versus espace disque. L’information nécessaire à l’exécu-
tion 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.
Cf. figure (1). 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.
L’affichage à l’écran et la lecture sur le clavier sont analogues à l’écriture
et la lecture dans un fichier. On considère en général dans les langages de pro-
grammation l’écran et le clavier comme des fichiers particuliers. L’écran est un
fichier sur lequel on ne peut qu’écrire et le clavier est un fichier sur lequel on ne
peut que lire.
Les notions définies dans cette partie que vous devez avoir bien comprises :
variable, type d’une variable, constante littérale, constante symbolique, expres-
sion, typage statique ou dynamique, déclaration, mémoire vive.
3 Langage de description d’algorithme
À 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. Nous pouvons passer ensuite à la description dans
un “langage de description d’algorithme”.
Intérêt d’un langage de description d’algorithme
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
Langage de description d’algorithme
— Pour n’importe quel problème (intégration numérique, échecs, paye, . . .).
— Caractéristiques principales d’un langage de programmation mais avec
une syntaxe plus libre, et des parties informelles à détailler plus tard.
— Ce cours : un langage possible. Non universel (ici : notations proches
du Fortran). Ce qui importe : le niveau de formalisation du langage,
intermédiaire entre un langage naturel et un langage de programmation.
5
3.1 Variables et types
On utilise des types de base :
Type entier : Ensemble de valeurs : Z, ensemble des entiers relatifs. Opéra-
tions 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."
Une opération de base sur 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, ou logique, négation, implication . . .
On peut aussi utiliser, en plus des types de base, des types qui sont construits
à partir des types de base. 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 peut définir, par
exemple, un type appelé “personne” contenant un champ nom, de type
texte, et un champ nombre_enfants, de type entier.
En langage de description d’algorithme, on adopte un typage statique. On
déclare donc le type des variables. On notera la déclaration sous la forme “type
variable”. Par exemple :
entier i
Ce qui signifie que i est une variable de type entier. On peut déclarer des va-
riables, des types (autres que les types de base) et des constantes symboliques.
En langage de description d’algorithme, on écrira les constantes symboliques
avec le mot-clef “constante”. Par exemple :
constante réelle pi = 3.141592654
Dans une expression, les constantes ou variables sont combinées avec des
opérateurs. Les opérateurs utilisés doivent être cohérents avec le type des objets
combinés. Une expression peut être plus ou moins compliquée. Elle peut se
réduire simplement à 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 un cran plus
compliquée, contenant une opération, est par exemple l’expression x + 3.
3.2 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. La plage d’indices peut éventuellement avoir
une partie négative. Exemple de déclaration de tableau :
