Algorithmique et pseudo-langage
Caroline Japhet
Version du 28 septembre 2023
Table des matières
1 Notations 1
2 Algorithmes : scripts et fonctions 3
2.1 Généralités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2 Boucle Pour . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.3 Boucle Tantque . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.4 Instruction Si . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.5 Intérêt des fonctions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.6 Fonctions prédéfinies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
Références :
r1s F. Cuvelier, Analyse numérique élémentaire, Notes de cours Ingénieurs MACS 1ère année, 2023
[Link]
Ce document est une introduction à l’algorithmique, dont une partie est extraite de la référence [1].
Pour tester les algorithmes, on utilisera le logiciel GNU Octave ([Link]
1 Notations
On utilisera le vocabulaire de base suivant :
— donnée : introduite par l’utilisateur
— résultat : ce que retourne l’algorithme (script ou fonction)
— constante : objet non modifiable
— variable : un objet dont la valeur est modifiable, qui possède un nom et un type (entier, caractère, réel,
complexe, tableau, matrice, vecteur...).
L’opérateur d’affectation d’une valeur “b “ (d’un type donné) à une variable “a” s’écrit :
Nom Symbole Exemple
affectation ÐÝ a ÐÝ b
Exemple : on veut affecter la valeur 3 à la variable a, on écrit : a ÐÝ 3.
Les opérateurs arithmétiques sont notés par :
Nom Symbole Exemple
addition ` a`b
soustraction ´ a´b
multiplication ˚ a˚b
division { a{b
puissance ˆ a ˆb
1
Les opérateurs relationnels sont notés par :
Nom Symbole Exemple Commentaire
identique ““ a ““ b vrai si a et b ont même valeur, faux sinon
différent „“ a „“ b faux si a et b ont même valeur, vrai sinon
inférieur ă aăb vrai si a est plus petit que b, faux sinon
supérieur ą aąb vrai si a est plus grand que b, faux sinon
inférieur ou égal ă“ a ă“ b vrai si a est plus petit ou égal à b, faux sinon
supérieur ou égal ą“ a ą“ b vrai si a est plus grand ou égal à b, faux sinon
Les opérateurs logiques sont notés par :
Nom Symbole Exemple Commentaire
négation „ „a vrai si a est faux (ou nul), faux sinon
ou | a |b vrai si a ou b est vrai (non nul), faux sinon
et & a &b vrai si a et b sont vrais (non nul), faux sinon
Vecteurs et tableaux 1D
Un vecteur v P Rn (ou tableau 1D) est un ensemble de n scalaires vi P R, i P t1, . . ., nu.
¨ ˛
v1
˚ v2 ‹
Il peut être représenté en ligne : v “ pv1 , v2 , . . . , vn q, ou en colonne : v “ ˚ . ‹ .
˚ ‹
˝ .. ‚
vn
La i-ème composante du vecteur v sera notée :
˛ vi pour la notation mathématique.
˛ vpiq pour la notation algorithmique.
Le premier indice est i “ 1.
Matrices ou tableaux 2D
Une matrice A P Mm,n pRq (ou tableau 2D), est un ensemble de m ˆ n scalaires Ai,j P R :
¨ ˛
A1,1 A1,2 ¨ ¨ ¨ A1,n
˚ A2,1 A2,2 ¨ ¨ ¨ A2,n ‹
.. ‹ .
˚ ‹
A“˚ . ..
˝ .. . . ‚
Am,1 Am,2 ¨ ¨ ¨ Am,n
On utilise l’abréviation A “ pAi,j q1ďiďm, 1ďjďn , i est l’indice de ligne, j est l’indice de colonne.
La matrice est carrée si m “ n (on note A P Mn pRq dans ce cas). ¨ ˛
A1,j
˚ A2,j ‹
La i-ième ligne de A est pAi,1 , Ai,2 , . . . , Ai,n q, et la j-ième colonne de A est ˚ . ‹
˚ ‹
˝ .. ‚
Am,j
L’élément situé sur la i-ième ligne et la j-ième colonne sera noté :
˛ Ai,j pour la notation mathématique.
˛ Api, jq pour la notation algorithmique.
Les indices commencent à i “ 1 et j “ 1.
Quelques rappels sur les vecteurs et les matrices
˛ Le produit scalaire euclidien de deux vecteurs u , v P Rn est défini par :
n
ÿ
u, v y “
xu ui vi .
i“1
2
˛ Le produit matrice-vecteur de A P Mn pRq par u P Rn est le vecteur v “ Au
u P Rn avec
n
ÿ
vi “ Ai,j uj , i P t1, . . ., nu.
j“1
˛ Le produit de deux matrices A, B P Mn pRq est la matrice C “ AB P Mn pRq avec
n
ÿ
Ci,j “ Ai,k Bk,j , i, j P t1, . . ., nu.
k“1
2 Algorithmes : scripts et fonctions
2.1 Généralités
Avant d’écrire un algorithme il est important de :
— clarifier l’énoncé du problème
— Rechercher une stratégie de construction de l’algorithme, en décomposant le problème en sous problèmes
partiels plus simples et que l’on peut tester séparément de l’algorithme global
Ensuite, l’algorithme doit être écrit de sorte que :
— le type des données et des résultats doivent être précisés
— l’algorithme doit fournir au moins un résultat
— l’algorithme doit être exécuté en un nombre fini d’opérations
— l’algorithme doit être écrit de façon claire et concise
Un algorithme peut-être écrit sous forme :
— d’un script : ensemble d’instructions qui joue le rôle de programme principal
— d’une fonction : ensemble d’instructions mis dans une fonction pour l’utilisateur,
qui sera (en général) ensuite appelée dans le script principal
Dans la suite nous allons voir des exemples de scripts et de fonctions avec les boucles “Pour”, “Tant que”, et
l’instruction “Si”.
2.2 Boucle Pour
Ce type de boucle est utilisé lorsque la valeur d’arrêt de la boucle est connue. On l’utilise par exemple pour le
calcul d’une somme ou d’un produit.
Remarque : on pourrait utiliser à la place une boucle Tantque, mais la boucle Pour est plus simple, plus facile
à débuguer, et plus rapide.
Exemple 1 : calcul d’une somme
Soit n P N˚ donné. On cherche à calculer
n
ÿ
s“ k 2 “ 1 ` 4 ` 9 ` . . . ` n2
k“1
1. Écrire une script permettant de calculer s pour n fixé (par exemple n “ 10).
řn
Algorithm 2.1 Script de calcul de k“1 k2
Donnée : n : entier pn ě 1q
s : réel, égal à n 2
ř
Résultat : k“1 k
1: n Ð 10 Ź valeur de la donnée n
2: sÐ0 Ź initialisation de s
3: Pour k Ð 1 à n faire
4: sÐs`k˚k
5: fin Pour
3
2. Écrire une fonction Somme, prenant en paramètre d’entrée n et retournant s.
řn
Algorithm 2.2 Fonction Somme : calcule k“1 k2
Donnée : n : entier pn ě 1q
s : réel, égal à n 2
ř
Résultat : k“1 k
1: Fonction s Ð Somme(n)
2: sÐ0 Ź initialisation de s
3: Pour k Ð 1 à n faire
4: sÐs`k˚k
5: fin Pour
6: fin Fonction
3. Réécrire le script du point 1) en utilisant la fonction Somme.
řn
Algorithm 2.3 Script de calcul de k“1 k2 , en utilisant la fonction Somme
Donnée : n : entier pn ě 1q
s : réel, égal à n 2
ř
Résultat : k“1 k
1: n Ð 10 Ź valeur de la donnée n
2: s Ð Somme(n)
4. Comment vérifier que le script est correct ?
˛ commencer par tester avec n “petit” pour lesquel on peut calculer s à la main.
npn`1qp2n`1q
˛ Puis tester pour n “quelconque” : comparer à la valeur de s si on la connait (ici : s “ 6 )
sinon, trouver d’autres tests.
Algorithm 2.4 Script de validation de la fonction Somme
1: nÐ4 Ź test n petit
2: se Ð 30 Ź valeur de s calculée à la main
3: s Ð Somme(n)
4: afficher ps ´ se q{se Ź erreur relative sur s
5:
6: n Ð 1000 Ź test n quelconque
7: se Ð n ˚ pn ` 1q ˚ p2 ˚ n ` 1q{6 Ź valeur exacte de s
8: s Ð Somme(n)
9: afficher ps ´ se q{se Ź erreur relative sur s
! les tests permettent de trouver d’éventuelles erreurs, ils ne montrent pas que l’algorithme est correct.
Exemple 2 : calcul d’un produit
Soit m P N˚ donné. On cherche à calculer
m
ź
p“ cosp3iq “ cosp3q ˆ cosp6q ˆ . . . ˆ cosp3mq
i“1
1. Écrire une script permettant de calculer p, pour m fixé (par ex. m “ 5)
śm
Algorithm 2.5 Script de calcul de i“1 cosp3iq
Données : m : entier pm ě 1q
śm
Résultat : p : réel, égal à i“1 cosp3iq
1: mÐ5 Ź valeur de la donnée m
2: pÐ1 Ź initialisation de p
3: Pour i Ð 1 à m faire
4: p Ð p ˚ cosp3 ˚ iq
5: fin Pour
4
2. Écrire une fonction Produit, prenant en paramètre d’entrée m et retournant p.
śm
Algorithm 2.6 Fonction Produit : calcule “ i“1 cosp3iq
Données : m : entier pm ě 1q
śm
Résultat : p : réel, égal à i“1 cosp3iq
1: Fonction p Ð Produit(m)
2: pÐ1 Ź initialisation de p
3: Pour i Ð 1 à m faire
4: p Ð p ˚ cosp3 ˚ iq
5: fin Pour
6: fin Fonction
3. Réécrire le script du point 1) en utilisant la fonction Produit.
śm
Algorithm 2.7 Script de calcul de i“1 cosp3iq, en utilisant la fonction Produit
Données : m : entier pm ě 1q
śm
Résultat : p : réel, égal à i“1 cosp3iq
1: m Ð 5 Ź valeur de la donnée m
2: p Ð Produit(m)
4. Comment vérifier que le script est correct ?
˛ commencer par tester avec m “petit” pour lesquel on peut calculer p à la main.
˛ Puis tester pour m “quelconque” : ici on ne connait pas la valeur de p, on pourrait la comparer à celle
que donne la fonction prod du logiciel Octave
Algorithm 2.8 Script de validation de la fonction Produit
1: mÐ3 Ź test m petit
2: pe Ð cosp3q ˚ cosp6q ˚ cosp9q Ź valeur de p calculée à la main
3: p Ð Produit(m)
4: afficher pp ´ pe q{pe Ź erreur relative sur p
5:
6: m Ð 300 Ź test m quelconque
7: pe Ð prodpmq Ź valeur de p avec Octave
8: p Ð Produit(m)
9: afficher pp ´ pe q{pe Ź erreur relative sur p
! les tests permettent de trouver d’éventuelles erreurs, ils ne montrent pas que l’algorithme est correct
2.3 Boucle Tantque
Elle est en général utilisée lorsque la valeur d’arrêt de la boucle n’est pas connue. C’est par exemple le cas
du calcul d’une suite numérique, avec un critère d’arrêt donné.
Calcul d’une suite numérique avec critère d’arrêt
Soit q Ps ´ 1, 1r donné. Considérons la suite géométrique :
"
u0 “ 1
un`1 “ qun , @n ě 0
Le problème que l’on se pose est le suivant : trouver le premier entier n tel que |un | ă tol, où tol ą 0 est un réel
donné (appelé “tolérance”). L’algorithme devra s’arrêter en au plus nmax itérations.
5
1. Écrire une script permettant de calculer n, pour q, tol et nmax fixés (par exemple q “ 32 , tol “ 10´4 ,
nmax “ 100).
Algorithm 2.9 Script de calcul de n tel que |un | ă tol
Données : q : réel pq Ps ´ 1, 1rq
tol : réel ptol ą 0q
nmax : entier pnmax ě 1q
Résultat : n : entier, n P t0, . . ., nmaxu, tel que |un | ă tol ou n “ nmax
1: q Ð 2{3 Ź valeur de la raison q
2: tol Ð 1e ´ 4 Ź valeur de la donnée tol
3: nmax Ð 100 Ź valeur de la donnée nmax
4: nÐ0 Ź initialisation de n
5: uÐ1 Ź initialisation u “ u0
6: Tantque abspuq ě tol & n ď nmax faire
7: uÐq˚u
8: nÐn`1
9: fin Tantque
2. Écrire une fonction SuiteG, prenant en paramètre d’entrée q, tol, nmax, et retournant n.
Algorithm 2.10 Fonction SuiteG : calcule n tel que |un | ă tol
Données : q : réel pq Ps ´ 1, 1rq
tol : réel ptol ą 0q
nmax : entier pnmax ě 1q
Résultat : n : entier, n P t0, . . ., nmaxu, tel que |un | ă tol ou n “ nmax
1: Fonction n Ð SuiteG(q, tol, nmax)
2: nÐ0 Ź initialisation de n
3: uÐ1 Ź initialisation u “ u0
4: Tantque abspuq ě tol & n ď nmax faire
5: uÐq˚u
6: nÐn`1
7: fin Tantque
8: fin Fonction
3. Réécrire le script du point 1) en utilisant la fonction SuiteG.
Algorithm 2.11 Script de calcul de n tel que |un | ă tol, en utilisant la fonction SuiteG
Données : q : réel pq Ps ´ 1, 1rq
tol : réel ptol ą 0q
nmax : entier pnmax ě 1q
Résultat : n : entier, n P t0, . . ., nmaxu, tel que |un | ă tol ou n “ nmax
1: q Ð 2{3 Ź valeur de la raison q
2: tol Ð 1e ´ 4 Ź valeur de la donnée tol
3: nmax Ð 100 Ź valeur de la donnée nmax
4: n Ð SuiteG(q, tol, nmax)
! Si l’algorithme s’arrête lorsque n “ nmax, alors il n’y a aucune garantie que |un | ă tol
2.4 Instruction Si
L’instruction conditionnelle Si est une instruction qui n’est exécutée que si une condition est validée. Il est
possible d’ajouter une instruction alternative avec Sinon.
Exemples : calcul de la valeur absolue d’un réel, tester si un réel est dans N, ...
6
Exemple 1 : calcul de la valeur absolue d’un réel
Soit x P R. On cherche à calculer "
x si x ě 0
|x| “
´x si x ď 0
1. Écrire une script permettant de calculer |x|, pour x fixé (par exemple x “ ´0.3).
Algorithm 2.12 Script de calcul de la valeur absolue d’un réel
Donnée : x : réel
Résultat : a : réel positif, tel que a “ |x|
1: x Ð ´0.3
2: Si x ě 0 alors
3: aÐx
4: Sinon
5: a Ð ´x
6: fin Si
2. Écrire une fonction Vabs, prenant en paramètre d’entrée x et retournant |x|.
Algorithm 2.13 Fonction Vabs : calcule la valeur absolue d’un réel
Donnée : x : réel
Résultat : a : réel positif, tel que a “ |x|
1: Fonction a Ð Vabs(x)
2: Si x ě 0 alors
3: aÐx
4: Sinon
5: a Ð ´x
6: fin Si
7: fin Fonction
3. Réécrire le script du point 1) en utilisant la fonction Vabs.
Algorithm 2.14 Script de calcul de la valeur absolue d’un réel, en utilisant la fonction Vabs
Donnée : x : réel
Résultat : a : réel positif, tel que a “ |x|
1: x Ð ´0.3
2: a Ð Vabspxq
Exemple 2 : tester si un réel est dans N
Soit x P R. Écrire un script retournant la valeur x, si x P N, et 0 sinon.
On pourra utiliser la fonction floor qui retourne la partie entière q d’un réel x (q Ð floorpxq).
Algorithm 2.15 Script pour tester si un réel est dans N
Donnée : x : réel
Résultat : n : entier naturel, tel que n “ x si x P N, et n “ 0 sinon
1: Si (x ą“ 0) & (floorpxq ““ xq alors
2: nÐx
3: Sinon
4: nÐ0
5: fin Si
7
2.5 Intérêt des fonctions
Les fonctions permettent
— d’automatiser certaines tâches répétitives au sein d’un même algorithme
— d’ajouter de la clarté à l’algorithme
— d’utiliser une portion de code dans un autre algorithme
— de valider plus efficacement un algorithme (en testant d’abord séparément chaque fonction, puis l’algo-
rithme complet).
Un exemple
On cherche à calculer ˇ ˇ
ˇźm ˇ
a “ ˇ cosp3iqˇ
ˇ ˇ
ˇi“1 ˇ
1. Écrire une script (sans utiliser de fonction) permettant de calculer a, pour m fixé
(par exemple m “ 5).
Algorithm 2.16 Script de calcul de ˇ m
ˇś ˇ
i“1 cosp3iq , sans utiliser de fonction
ˇ
Données : m : entier pm ě 1q
a : réel positif, égal à ˇ m
ˇś ˇ
Résultat : i“1 cosp3iq
ˇ
1: mÐ5 Ź valeur de la donnée m
2: pÐ1 Ź initialisation de p
3: Pour i Ð 1 à m faire
4: p Ð p ˚ cosp3 ˚ iq
5: fin Pour
6: Si p ě 0 alors
7: aÐp
8: Sinon
9: a Ð ´p
10: fin Si
! pour des problèmes plus complexes, l’algorithme deviendra très vite illisible et difficile à valider.
2. Réécrire le script du point 1) en utilisant les fonctions Produit et Vabs.
Algorithm 2.17 Script de calcul de ˇ m
ˇś ˇ
i“1 cosp3iq , en utilisant les fonctions Produit et Vabs
ˇ
Données : m : entier pm ě 1q
a : réel positif, égal à ˇ m
ˇś ˇ
Résultat : i“1 cosp3iq
ˇ
1: m Ð 5 Ź valeur de la donnée m
2: p Ð Produit(m)
3: a Ð Vabs(p)
Cet algorithme est clair, concis, avec des fonctions Produit et Vabs qui peuvent-être validées séparément.
2.6 Fonctions prédéfinies
Les fonctions prédéfinies sont :
— les fonctions mathématiques : sin, cos, exp, log, sqrt, . . .
— la fonction Length : retourne la longueur n d’un vecteur u P Rn
n Ð lengthpu uq
— la fonction Size : retourne la dimension pm, nq d’une matrice A P Mm,n pRq
rm, ns Ð sizepAq
— la fonction Rand : retourne un vecteur colonne v de Rn , ou une matrice A carrée de taille n, contenant
des valeurs aléatoires dans r0, 1s
v Ð randpn, 1q
A Ð randpnq
— la fonction floor : retourne la partie entière q d’un réel x
q Ð floorpxq