Introduction à la conception des

algorithmes

A. DARGHAM
Faculté des Sciences
Oujda
Sommaire

 Notion d’algorithme
 Un langage pour décrire les algorithmes
 Itération
 Récursivité
 Preuve d’un algorithme
Notion d’algorithme
 Qu'est-ce qu'un algorithme ?
– Un algorithme est une procédure
effective qui sert à accomplir une tâche
spécifique.
– Un algorithme est l'idée derrière tout
programme informatique raisonnable.
– Pour qu’il mérite ce nom, un algorithme
doit résoudre d’une manière générale, un
problème bien spécifié.
Notion d’algorithme

 Qu'est-ce qu'un algorithme ?

– Un problème algorithmique est spécifié en
décrivant :
L'ensemble complet des ses instances
(Input) sur lesquelles il doit travailler;
Sa production (Output) après son
exécution sur une de ces instances.
– Cette distinction, entre un problème et une
instance d'un problème, est fondamental.
Notion d’algorithme
 Exemple d’un problème algorithmique :
Le problème algorithmique connu sous le
nom du problème de tri est défini comme
suit :
– Problème : le tri.
– Input : une liste de n clés <a , …, a >.
1 n
– Output : une permutation de la liste
d'entrée <a1', …, an'> qui soit ordonnée : a1'
 …  an'.
Notion d’algorithme

 Exemple d’un problème algorithmique :

– Une instance du problème de tri pourrait
être :
Une liste de noms, comme <Malika,
Bachir, Saleh, Jilali, Jamila};
Une liste de numéros comme <154, 245,
568, 324, 654, 324>;
…etc
Notion d’algorithme

 Spécification d’un problème algorithmique:

– La première étape dans la résolution d’un
problème algorithmique par un algorithme
est la spécification des données en entrée
(Input) et des données en sortie (Output).
– Par exemple, dans le problème de tri, on
peut indiquer que l’input est une liste de n
nombres (des entiers par exemple).
Notion d’algorithme

 Pluralité des solutions algorithmiques :

– Un algorithme est une procédure qui prend
l'une de ses instances en entrée possible et
la transforme en la sortie désirée.
– Il y a beaucoup d’algorithmes différents
pour résoudre le problème du tri : tri par
sélection, tri par insertion, tri à bulles, tri
par fusion, tri rapide, tri par tas, …etc.
Notion d’algorithme

 Les algorithmes sont-ils différents ?

– Pour un même problème algorithmique, il
peut exister plusieurs algorithmes
différents :
Certains itératifs, d’autres récursifs;
Certains sont plus rapides que les autres;
Certains utilisent moins d’espace mémoire
que d’autres;
…etc.
Notion d’algorithme

 Propriétés d’un bon algorithme :

– Il y a trois propriétés désirables pour un bon
algorithme :
Correction;
Efficacité;
Facilité à mettre en œuvre;

– Ces trois objectifs ne peuvent pas toujours

être tous atteints simultanément.
Un langage pour décrire les
algorithmes

 Type de données :
– Entier;
– Réel;
– Caractère;
– Chaîne (chaînes de caractères);
– Booléen (vrai / faux);
– Tableau;
Un langage pour décrire les
algorithmes

 Opérations de base :
– +-*/%
 , , , , = et 
– Non, Et, Ou
– := (affectation)
– Afficher
– Lire
Un langage pour décrire les
algorithmes

 Structures de contrôle :
– Si … Alors … Sinon … FinSi
– Pour … Faire … FinPour
– Tant Que … Faire … FinTQ
– Répéter … Jusqu’à … FinRép
– Retourner …
Un langage pour décrire les
algorithmes

 Structure générale d’un algorithme :

Fonction Nom_Algo(Input) : Output
Var … // variables
Début
… // actions
Fin
Itération
 Le concept d’itération :
– Un algorithme itératif résout un problème en
calculant son résultat par une méthode
d’approximation successive.
– Les composants d’un algorithme itératif :
Initialisation : préciser la valeur adéquate
de départ.
Approximation : décrire la manière de
s’approcher du résultat .
Progression : indiquer la façon d’aller
d’une étape à une autre.
Itération
 Les boucles :
– Les boucles sont un moyen pour décrire un
algorithme itératif.
– Il y a trois formes de boucles :
La boucle « Pour » : elle utilise un
compteur pour contrôler la progression.
Les boucles « Tant Que » et « Répéter
» : elles utilisent une condition pour
contrôler la progression.
Itération
 Un premier exemple :
– Soit le problème suivant :
Problème : somme des N premiers
entiers.
Input : un entier N.
Output : L’entier S = 1 + 2 + … + N.
Itération
 Algorithme itératif (1) :
Fonction somme(N : Entier) : Entier;
Var i, S : Entier;
Début
S := 0; // Initialisation
i := 1; // Initialisation
Tant Que(i  N) Faire
S := S + i; // Approximation
i := i + 1; // Progression
FinTQ
Retourner S;
Fin
Itération
 Un second exemple :
– Soit le problème suivant :
Problème : plus grand élément d’un
tableau.
Input : un entier « n » et un tableau « a »
de « n » nombres entiers.
Output : un entier « g » qui est le plus
grand élément de « a ».
Formellement, g = Max { a[1], …, a[n] }.
Itération
 Algorithme itératif (2) :
Fonction plusGrand(a : Tableau, n : Entier) : Entier;
Var i, g : Entier;
Début
g := a[1]; // Initialisation
Pour i := 2 à n Faire // Progression
Si(a[i] > g) Alors
g := a[i]; // Approximation
FinSi
FinPour
Retourner g;
Fin
Itération
 Un troisième exemple :
– Soit le problème suivant :
Problème : produit de deux entiers en
utilisant uniquement des additions.
Input : deux entiers « a » et « b ».
Output : un entier « c » tel que c = a  b,
mais en utilisant uniquement des
additions.
Idée : a  b = a + a + … + a (b fois)
Itération
 Algorithme itératif (3) :
Fonction produit(a, b : Entier) : Entier;
Var i, c : Entier;
Début
c := 0; // Initialisation
Pour i := 1 à b Faire // Progression
c := c + a; // Approximation
FinPour
Retourner c;
Fin
Itération
 Un quatrième exemple :
– Soit le problème suivant :
Problème : factorielle.
Input : un entier « n ».
Output : un entier « f » tel que f = n! = 1
 2  …  n.
Itération
 Algorithme itératif (4) :
Fonction factorielle(n : Entier) : Entier;
Var i, f : Entier;
Début
f := 1; // Initialisation
Pour i := 1 à n Faire // Progression
f := f * i; // Approximation
FinPour
Retourner f;
Fin
Itération
 Exercices TD :
– Pour chacun des problèmes suivants,
élaborer un algorithme itératif qui le résout :
Le quotient et le reste d’un entier a par
un entier b.
La puissance nème d’un entier a.
La somme des chiffres d’un entier a.
Récursivité

 Objet récursif :
– Un objet récursif est formé de plusieurs petits
objets de même forme que l’objet le plus
grand.
– Exemples :
Chaînes : supprimer la première lettre d’une
chaîne, le résultat est une chaîne plus petite
Graphes : supprimer un sommet (ou un arc) d’un
graphe, le résultat est un graphe plus petit.
 chaînes, graphes sont des objets récursifs.
Récursivité

 Algorithme récursif :
– Un algorithme récursif résout un problème
en utilisant un algorithme plus petit, mais
qui lui ressemble à 100%.
– Un algorithme récursif est exactement un
objet récursif.
Récursivité

 Composants d’un algorithme récursif :

– Cas de base (condition d’arrêt) : le
problème peut se résoudre d’une manière
directe. La donnée est suffisamment petite
pour qu’elle puisse traitée de façon simple.
– Appel récursif (récurrence) : le problème
se résout en utilisant un algorithme
identique mais sur une donnée plus petite.
Récursivité

 Un premier exemple :
– Soit le problème suivant :
Problème : somme des N premiers
entiers.
Input : un entier N.
Output : L’entier S = 1 + 2 + … + N.
Récursivité

 Idée de la récursivité :
– S = 1 + 2 + … + N = SN
– SN = (1 + 2 + … + N - 1) + N
– SN = SN-1 + N // appel récursif
– S0 = 0 // cas de base
Récursivité
 Algorithme récursif (1) :
Fonction somme(N : Entier) : Entier;
Début
Si(N = 0) Alors
Retourner 0; // Cas de base
Sinon
Retourner somme(N - 1) + N; // Appel récursif
FinSi
Fin
Récursivité
 Un second exemple :
– Soit le problème suivant :
Problème : plus grand élément d’un
tableau.
Input : un entier « n » et un tableau « a »
de « n » nombres entiers.
Output : un entier « g » qui est le plus
grand élément de « a ».
Formellement, g = Max { a[1], …, a[n] }.
Récursivité
 Idée de la récursivité :
– Cas de base : si le tableau a un seul
élément (n = 1), son plus grand élément est
a[1].
– Appel récursif : si n > 1, le plus grand
élément de a[1…n] est le plus grand entre
a[n] et le plus grand élément de a[1…n-1].
Récursivité
 Algorithme récursif (2) :
Fonction plusGrand(a : Tableau, n : Entier) : Entier;
Début
Si(n = 1) Alors
Retourner a[1]; // Cas de base
Sinon
Retourner Max(plusGrand(a, n-1), a[n]);
// A.r
FinSi
Fin
Récursivité
 Un troisième exemple :
– Soit le problème suivant :
Problème : produit de deux entiers en
utilisant uniquement des additions.
Input : deux entiers « a » et « b ».
Output : un entier « c » tel que c = a  b,
mais en utilisant uniquement des
additions.
Récursivité
 Idée de la récursivité :
– Cas de base : si b = 0, alors : a  b = 0.
– Appel récursif : si b > 0, alors :
a  b = a  (b - 1) + a
Récursivité
 Algorithme récursif (3) :
Fonction produit(a, b : Entier) : Entier;
Début
Si(b = 0) Alors
Retourner 0; // Cas de base
Sinon
Retourner produit(a, b-1) + a; // Appel
récursif
FinSi
Fin
Récursivité
 Un quatrième exemple :
– Soit le problème suivant :
Problème : factorielle.
Input : un entier « n ».
Output : un entier « f » tel que f = n! = 1
 2  …  n.
Récursivité
 Idée de la récursivité :
– Cas de base : si n = 0, alors : n! = 1.
– Appel récursif : si n > 0, alors :
n! = (n - 1)!  n
Récursivité
 Algorithme récursif (4) :
Fonction factorielle(n : Entier) : Entier;
Début
Si(n = 0) Alors
Retourner 1; // Cas de base
Sinon
Retourner factorielle(n - 1) * n; // Appel
récursif
FinSi
Fin
Récursivité
 Exercices TD :
– Pour chacun des problèmes suivants,
élaborer un algorithme récursif qui le
résout :
Le quotient et le reste d’un entier a par
un entier b.
La puissance nème d’un entier a.
La somme des chiffres d’un entier a.
Preuve d’un algorithme

 Terminaison & correction :

– Preuve de correction d’un algorithme :
prouver (mathématiquement) qu’il produit
toujours le bon résultat pour toutes les
instances du problème.
– Preuve de terminaison d’un algorithme :
prouver qu’il aboutit au résultat au bout d’un
nombre fini d’étapes.
Preuve d’un algorithme

 Preuve d’un algorithme récursif :

– Correction : se démontre par récurrence.
– Terminaison : se démontre également par
récurrence.
 Types de récurrence :
– Récurrence simple : la propriété s’hérite du
père direct au fils.
– Récurrence forte : la propriété s’hérite des
parents (directs ou indirects) au fils.
Preuve d’un algorithme

 Schéma de la récurrence simple :

– Cas de base : on vérifie que la propriété est
vraie pour n0.
– Hypothèse de récurrence : soit n  n0. On
suppose que la propriété est vraie pour n.
– Cas inductif (récurrence) : on montre que la
propriété est vraie pour n+1.
Preuve d’un algorithme

 Schéma de la récurrence forte :

– Cas de base : on vérifie que la propriété est
vraie pour n0.
– Hypothèse de récurrence : soit n > n0. On
suppose que la propriété est vraie pour tout
entier k tel que n0  k  n.
– Cas inductif : on montre que la propriété est
vraie pour n.
Preuve d’un algorithme

 Exemples :
– La propriété « 1 + 2 + … + N = N(N + 1)/2 »,
pour tout entier N  1, se démontre par
récurrence simple.
– La propriété « N se décompose en produit
de facteurs tous premiers », pour N  2, se
démontre par récurrence forte.
Preuve d’un algorithme

 Exemple de la récurrence simple :

– 1 + 2 + … + N = N(N + 1) / 2
– Cas de base : Pour N = 1. Vraie, car 12/2 = 1.
– Hypothèse de récurrence : soit N  1. On suppose
que : 1 + 2 + … + N = N(N + 1) / 2.
– Cas inductif : on montre que 1 + 2 + … + N + (N+1)
= (N+1)((N+1)+1) / 2.
– On a : 1 + 2 + … + N + (N+1) = (1 + 2 + … + N) +
(N+1) = N(N+1)/2 + (N+1) = (N+1)(N/2 + 1) = (N+1)
(N+2)/2 = (N+1)((N+1)+1) / 2
Preuve d’un algorithme

 Exemple de la récurrence forte :

– N se décompose en produit de facteurs
tous premiers.
– Cas de base : Pour N = 2. Vraie, car 2 = 2
premier.
– Hypothèse de récurrence : soit N > 2. On
suppose que K se décompose en produit de
facteurs tous premiers, pour 2  K < N.
Preuve d’un algorithme

 Exemple de la récurrence forte :

– Cas inductif : il y a deux cas :
Si N est premier : la propriété est
évidente.
Si N n’est pas premier, alors N = A  B
avec 2  A < N et 2  B < N. Par H.R, A
et B se décomposent en produit de
facteurs tous premiers. Il en est de même
pour N.
Preuve d’un algorithme

 Preuve de l’algorithme récursif (1) :

– Cas de base : pour n = 0; l’algorithme « somme »
retourne 0 (donc correcte) et se termine.
– H.R : soit n  0; on suppose que l’algorithme «
somme » se termine et qu’il est correct.
– Cas inductif : pour n+1. Comme n+1 > 0, l’algorithme
« somme » va effectuer un appel récursif avec le
paramètre n. Or l’algorithme « somme » avec
l’argument « n » se termine et il est correct (retourne
1 + … + n). Donc, l’algorithme « somme » avec
l’argument « n+1 » se termine aussi et renvoie : 1 +
… + n + n+1, donc correcte.
Preuve d’un algorithme

 Exercices TD :
– Donner les preuves des algorithmes
récursifs vus dans ce cours :
plusGrand
produit
factorielle
Preuve d’un algorithme

 Preuve d’un algorithme itératif :

– Preuve de terminaison : on montre que le
nombre d’itérations (répétitions de la boucle)
est fini et que chaque itération elle-même se
termine.
– Preuve de correction : on utilise un invariant
de boucle.
– un invariant de boucle est une propriété qui
lie les variables d’une boucle et qui est
toujours vraie à la fin de chaque itération.
Preuve d’un algorithme

 Méthode de prouver un algorithme itératif :

– Prouver sa terminaison.
– Trouver un invariant de boucle.
– Le montrer par récurrence.
– L’exploiter pour prouver la correction.
Preuve d’un algorithme

 Preuve de l’algorithme itératif (1) :

– Preuve de terminaison :
Chaque itération se termine : 2 affectations.
La variable i est initialisée à 1 et
s’incrémente à chaque itération, il arrivera
donc à être égale à n+1 au bout de n
itérations.
La boucle « Tant Que » se termine alors.
– Conclusion : l’algorithme se termine.
Preuve d’un algorithme

 Preuve de l’algorithme itératif (1) :

– Trouver un invariant de boucle :
On notera par « x » la valeur de la variable «
i
x » à la fin de l’itération « i ».
– Les faits :
S = 0;
0
i = 1;
0
S = S + i ; pour j > 0
j j-1 j-1
i = i + 1; pour j > 0
j j-1
Preuve d’un algorithme

 Preuve de l’algorithme itératif (1) :

– Trouver un invariant de boucle :
Les faits :
– i = j + 1; pour j >= 0.
j
Invariant de boucle :
– S = 1 + 2 + … + j; pour j > 0.
j
Preuve d’un algorithme

 Preuve de l’algorithme itératif (1) :

– Montrer l’invariant de boucle :
Preuve par récurrence :
– Cas de base : pour j = 1, S = S + i =
1 0 0
1. (vraie)
– H.R : soit j >= 1 et supposons que S =
j
1 + … + j.
– Induction : S = S + i = (1 + … + j) +
j+1 j j
(j + 1). (vraie)
Preuve d’un algorithme

 Preuve de l’algorithme itératif (1) :

– Exploiter l’invariant pour prouver la correction.
La boucle s’effectue « n » fois et la valeur
de « i » après la nème itération est « n+1».
La valeur retournée est bien S .
n
D’après l’invariant, S = 1 + … + n.
n
Ce qui prouve que l’algorithme est correcte.
Preuve d’un algorithme

 Exercices TD :
– Donner les preuves des algorithmes itératifs
vus dans ce cours :
plusGrand
Produit
factorielle
Preuve d’un algorithme

 Exercices de TP :
– Programmer en C++ tous les algorithmes
vus dans ce cours et ceux faits en TD.