ALGORITHMES ET STRUCTURES DE
DONNÉES POUR L'INGÉNIERIE
GLO-2100
Chapitre 1 : Introduction à l’algorithmique
Thierry Eude, Ichrak Hamdi
0 Département d’informatique et de génie logiciel
Plan
• Algorithme
• Efficacité des algorithmes
• Analyse algorithmique
• Notations asymptotiques
• Opération baromètre
• Comparaison entre les classes de complexité
• Analyse en pire cas
• Récursivité
1 Département d’informatique et de génie logiciel
Algorithme
• Définition : “Enchaînement d’actions permettant l’accomplissement d’une tâche”
• Le nom vient du Mathématicien perse (8e siècle): al-Khwārizmī
• C’est l’auteur des premiers algorithmes (sous forme écrite)
• Description de procédures permettant de faire des opérations sur des nombres
(addition, soustraction, multiplication, division)
2 Département d’informatique et de génie logiciel
Algorithmique (étude des algorithmes)
• Concerne la Conception d’algorithmes pour la résolution de problèmes:
➢ Déterminer la séquence d’opérations pour accomplir la tâche désirée.
• Et l’analyse de la Complexité/Efficacité des algorithmes:
➢ Effectuer une preuve de bon fonctionnement (exactitude/validité): démontrer
que l’algorithme effectue toujours ce qu’il est censé faire.
➢ Déterminer les ressources utilisées pour exécuter l’algorithme.
3 Département d’informatique et de génie logiciel
Efficacité des algorithmes
• Se mesure par la quantité de ressources utilisées
• Ressources :
➢ Le temps d’exécution:
✓ temps que met l’algorithme pour accomplir sa tâche
➢ L’espace mémoire utilisé:
✓ nombre d’octets utilisés par l’algorithme pour accomplir sa tâche
➢ La bande passante utilisée:
✓ nombre d’octets que l’algorithme doit échanger avec une entité pour
accomplir sa tâche. (nous ne considèrerons pas cela dans ce cours)
4 Département d’informatique et de génie logiciel
L’approche empirique
• Consiste à essayer l’algorithme sur différents jeux de données bien choisis.
• Avantages:
➢ Ne nécessite aucune connaissance en algorithmique
➢ Résultats réalistes pour les instances testées dans l’environnement de test.
• Inconvénients:
➢ Pas toujours généralisable aux instances non testées.
➢ Couteux et long (nécessite beaucoup de tests)
➢ Dépend de l’environnement d’exécution (le processeur, l’OS, la charge,
l’implémentation…)
5 Département d’informatique et de génie logiciel
L’approche algorithmique
• Le cout d’exécution d’un algorithme est défini par le nombre d’opérations élémentaires
effectuées durant son exécution
➢ Une opération élémentaire est une opération non divisible.
✓ Exemples : comparaison, addition, multiplication … d’une donnée élémentaire
(comme un int, float, char, double…).
✓ Exemples d’opérations non élémentaires: tri d’un tableau, recherche d’un
élément, exécution d’un autre algorithme…
• Avantages:
➢ Résultats généraux: ne dépend pas de l’environnement d’exécution
➢ Estimation rapide et peu couteuse
• Inconvénients:
➢ Nécessite la compréhension de notions algorithmiques.
6 Département d’informatique et de génie logiciel
Approche algorithmique et analyse asymptotique
• Nous utilisons l’approche algorithmique
➢ Raison: L’approche empirique ne caractérise pas l’algorithme (caractérise plutôt
l’algorithme et son environnement d’exécution).
• Définition: le cout d'exécution d'un algorithme dépend du nombre d’opérations élémentaires
qu’il doit effectuer pour accomplir sa tâche.
• On s’intéresse uniquement à la croissance de ce nombre d’opérations en fonction des
paramètres pertinents de l’algorithme qui peuvent être :
➢ La taille de l’instance à traiter (le cas le plus fréquent).
✓ Ex: le nombre d’éléments (d’un tableau) à trier
➢ La précision du résultat demandé.
✓ Ex: lorsque l’on cherche la solution de f(x) = 0.
• On utilise la notation asymptotique pour exprimer l’ordre de croissance de ce nombre
d’opérations en fonction du paramètre pertinent (ex la taille n de l’instance à traiter).
7 Département d’informatique et de génie logiciel
Notation O (big-oh ou
grand-oh)
• Détermine une borne supérieure
éventuelle
• Définition formelle :
𝑓 𝑛 ∈ 𝑂(𝑔 𝑛 ) s’il existe deux
constantes positives 𝑛0 et 𝑐 tel que
𝑓 𝑛 ≤ 𝑐𝑔 𝑛
pour tout 𝑛 ≥ 𝑛0 .
8 Département d’informatique et de génie logiciel
Exemple
• Considérons 𝑓 𝑛 = 12𝑛2 + 5𝑛.
• On a que 12𝑛2 + 5𝑛 ≤ 17𝑛2 pour tout 𝑛 ≥ 1
• Donc 𝑓 𝑛 ∈ 𝑂(𝑛2 ).
• Par contre, il n’existe pas 𝑛0 et 𝑐 positifs tels que 12𝑛2 + 5𝑛 ≤ 𝑐𝑛 pour tout 𝑛 ≥
𝑛0
• Donc 𝑓 𝑛 ∉ 𝑂(𝑛).
9 Département d’informatique et de génie logiciel
Propriété de transitivité
Si
𝑓 𝑛 ∈ 𝑂(𝑔 𝑛 )
et
g 𝑛 ∈𝑂 ℎ 𝑛 ,
alors
𝑓 𝑛 ∈ 𝑂(ℎ 𝑛 ) .
10 Département d’informatique et de génie logiciel
Notation Ω (omega)
• Détermine une borne inférieure
éventuelle
• Définition formelle :
𝑓 𝑛 ∈ Ω(𝑔 𝑛 ) s’il existe deux
constantes positives 𝑛0 et 𝑐 tel que
𝑓 𝑛 ≥ 𝑐𝑔 𝑛
pour tout 𝑛 ≥ 𝑛0 .
• Donc 𝑓 𝑛 ∈ Ω 𝑔 𝑛 si et seulement
si g 𝑛 ∈ O 𝑓 𝑛 .
11 Département d’informatique et de génie logiciel
Exemple
• Considérons 𝑓 𝑛 = 12𝑛2 + 5𝑛.
• On a que 12𝑛2 + 5𝑛 ≥ 12𝑛2 pour tout 𝑛 ≥ 1
• Donc 𝑓 𝑛 ∈ Ω(𝑛2 ).
• Par contre, il n’existe pas 𝑛0 et 𝑐 positifs tels que 12𝑛2 + 5𝑛 ≥ 𝑐𝑛3 pour tout 𝑛 ≥ 𝑛0
• Donc 𝑓 𝑛 ∉ Ω(𝑛3 ).
12 Département d’informatique et de génie logiciel
Notation Θ (thêta)
• Définition formelle :
𝑓 𝑛 ∈ 𝛩(𝑔 𝑛 ) s’il existe trois
constantes positives 𝑛0 , 𝑐1 , 𝑐2 tel que
𝑐1 𝑔 𝑛 ≤ 𝑓 𝑛 ≤ 𝑐2 𝑔 𝑛
pour tout 𝑛 ≥ 𝑛0 .
• Donc 𝑓 𝑛 ∈ 𝛩 𝑔 𝑛 si et seulement
si f 𝑛 ∈ O 𝑔 𝑛 et f 𝑛 ∈ Ω 𝑔 𝑛 .
13 Département d’informatique et de génie logiciel
Exemple
• Considérons 𝑓 𝑛 = 12𝑛2 + 5𝑛.
• On a que 12𝑛2 ≤ 12𝑛2 + 5𝑛 ≤ 17𝑛2 pour tout 𝑛 ≥ 1
• Donc 𝑓 𝑛 ∈ Θ(𝑛2 ).
14 Département d’informatique et de génie logiciel
Remarques sur la notation asymptotique
• O 𝑔 𝑛 , Ω 𝑓 𝑛 et 𝛩 𝑔 𝑛 définissent des ensembles de fonctions.
➢ C’est pour cette raison que nous utilisons le symbole d’appartenance pour indiquer
qu’une fonction appartient à un ensemble.
✓ Ex: 𝑓 n ∈ O 𝑔 𝑛 .
• Certains auteurs utilisent le symbole d’égalité = à la place du symbole d’appartenance ∈
➢ nous décourageons cette pratique!
• Certains ensembles sont strictement plus grands que d’autres.
➢ Par exemple, si 𝑓 n ∈ O 𝑛 ⟹ 𝑓 n ∈ O 𝑛² mais il existe des fonctions dans
O 𝑛2 qui ne sont pas dans O 𝑛 .
✓ On a donc que O 𝑛 ⊂ O 𝑛2 .
15 Département d’informatique et de génie logiciel
Le truc de l’opération baromètre
• Le cout d’exécution d’un algorithme ⟺ nombre d’opérations élémentaires pour accomplir sa tâche.
• TRUC: Nous nous intéressons uniquement à son ordre de croissance, en fonction de son paramètre
pertinent n
➢ Il suffit d’identifier une opération baromètre et de compter le nombre de fois que cette
opération est effectuée en fonction de n.
Opération baromètre :
• opération élémentaire qui, à une constante près, est effectuée au moins aussi souvent que n’importe
quelle autre opération élémentaire de l’algorithme.
➢ Nous ne sommes pas obligés de choisir une opération qui est exécutée au moins aussi souvent
que n’importe quelle autre. Il suffit qu’elle le soit à une constante près.
• Identifier une opération baromètre : généralement assez simple
16 Département d’informatique et de génie logiciel
Exemple du tri sélection
• Baromètres possibles void triSelection(std::vector<int>& x)
{
• Baromètres invalides for (int i = [Link]() - 1; i > 0; i--)
{
int pMax = i;
for (int j = 0; j < i; j++)
{
if ([Link](j) > [Link](pMax))
{
pMax = j;
}
}
int temp = [Link](i);
[Link](i) = [Link](pMax);
[Link](pMax) = temp;
}
}
17 Département d’informatique et de génie logiciel
Exemple du tri sélection
• Baromètres possibles void triSelection(std::vector<int>& x)
{
• Baromètres invalides for (int i = [Link]() - 1; i > 0; i--)
{
int pMax = i;
for (int j = 0; j < i; j++)
{
if ([Link](j) > [Link](pMax))
{
pMax = j;
}
}
int temp = [Link](i);
[Link](i) = [Link](pMax);
[Link](pMax) = temp;
}
}
18 Département d’informatique et de génie logiciel
Exemple (suite) : calcul du coût d’exécution
• Soit 𝑛 = nombre d’éléments du tableau x (i.e., la taille de l’instance à traiter).
• Opération baromètre: la comparaison j < 𝑖
void triSelection(std::vector<int>& x)
{
1 𝑖−1 1 1 for (int i = [Link]() - 1; i > 0; i--)
{
𝑡 𝑛 = 1 = (𝑖 − 1 − 0 + 1) = 𝑖 int pMax = i;
for (int j = 0; j < i; j++)
{
𝑖=𝑛−1 𝑗=0 𝑖=𝑛−1 𝑖=𝑛−1 if ([Link](j) > [Link](pMax))
{
pMax = j;
}
𝑛−1 }
int temp = [Link](i);
𝑡 𝑛 = 𝑖 = 1+2+3+⋯+𝑛 −1 [Link](i) = [Link](pMax);
[Link](pMax) = temp;
𝑖=1 }
}
• 𝑡 𝑛 = 𝑛(𝑛 − 1)/2
• Alors t 𝑛 ∈ 𝑂(𝑛2 ). L’algorithme est en 𝑂(𝑛2 ).
19 Département d’informatique et de génie logiciel
Pourquoi avons-nous
𝑛−1
𝑖 = 1 + 2 + 3 + ⋯ + 𝑛 − 1 = 𝑛(𝑛 − 1)/2
𝑖=1
Preuve (de Carl Friedrich Gauss alors qu’il était âgé de 9 années):
S = 1 + 2 + 3 + … + n-1
S = n-1 + n-2 + n-3 + … + 1
Donc 2S = (n) + (n) + (n) + … + (n) (n-1 fois)
Donc 2S = (n) (n-1)
Donc S = (n) (n-1)/2 CQFD.
20 Département d’informatique et de génie logiciel
Classes de complexité pour temps d’exécution
• 𝑂 1 indique un temps d’exécution constant, indépendant de n
• 𝑂 𝑛 indique essentiellement que l’on doit effectuer un nombre constant d’opérations sur chaque
donnée d’entrée
• 𝑂 log(𝑛) implique que toutes les données n’ont pas à être traitées
• 𝑂 𝑛2 ) implique un nombre d’opérations proportionnel à n, pour chaque donnée
• 𝑂 𝑛 ∗ log(𝑛) est typique des algorithmes diviser-pour-régner (ex: tri fusion)
• 𝑂 𝑛𝑎 pour a ≥ 1: algorithme à temps polynomial
• 𝑂 𝑎𝑛 est un algorithme à temps exponentiel. Donc algorithme très lent!
➢ Certains problèmes, comme celui du voyageur de commerce, n’admettent toujours pas
d’algorithmes à temps polynomial..
• 𝑂 𝑛! : algorithme plus lent qu’exponentiel…
• 𝑂 1 ⊂ 𝑂 log(𝑛) ⊂ 𝑂 𝑛 ⊂ 𝑂 𝑛 ∗ log(𝑛) ⊂ 𝑂 𝑛2 ⊂ 𝑂 2𝑛 ⊂ 𝑂 10𝑛 ⊂ 𝑂 𝑛!
21 Département d’informatique et de génie logiciel
La règle du maximum
Si
𝑓1 𝑛 ∈ 𝑂 𝑔1 𝑛
et
𝑓2 𝑛 ∈ 𝑂 𝑔2 𝑛 ,
alors
𝑓1 𝑛 + 𝑓2 𝑛 ∈ 𝑂 max(𝑔1 𝑛 , 𝑔2 𝑛
• Exemple: 𝑛 + nlog 𝑛 ∈ 𝑂 𝑛𝑙𝑜𝑔 𝑛
➢ Lorsqu’un algorithme est constitué de deux parties, l’une s’exécutant après l’autre, le
cout d’exécution est déterminé uniquement par la partie la plus lente.
22 Département d’informatique et de génie logiciel
Exemples sur les boucles
• Baromètres possibles void f(int n)
{
for(int i = 0; i < n; i++)
{
cout << "Allo\n";
}
}
23 Département d’informatique et de génie logiciel
Exemples sur les boucles
• Baromètres possibles void f(int n)
{
• Cet algorithme est en for(int i = 0; i < n; i++)
𝑂 𝑛 . {
cout << "Allo\n";
}
}
24 Département d’informatique et de génie logiciel
Exemples sur les boucles
• Baromètres possibles void f(int n)
{
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
cout << i << j << endl;
}
}
}
25 Département d’informatique et de génie logiciel
Exemples sur les boucles
• Baromètres possibles void f(int n)
{
• Cet algorithme est en for(int i = 0; i < n; i++)
𝑂 𝑛2 . {
for(int j = 0; j < n; j++)
{
cout << i << j << endl;
}
}
}
26 Département d’informatique et de génie logiciel
Exemples sur les boucles
• Baromètres possibles void f(int n)
{
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n*n; j++)
{
cout << i << endl;
}
}
}
27 Département d’informatique et de génie logiciel
Exemples sur les boucles
• Baromètres possible void f(int n)
{
• Cet algorithme est en for(int i = 0; i < n; i++)
𝑂 𝑛3 . {
for(int j = 0; j < n*n; j++)
{
cout << i << endl;
}
}
}
28 Département d’informatique et de génie logiciel
Exemples sur les boucles
• Baromètres possibles void f(int n)
{
for(int i = 0; i < 10000000; i++)
{
cout << "Allo\n";
}
}
29 Département d’informatique et de génie logiciel
Exemples sur les boucles
• Baromètres possibles void f(int n)
{
• Cet algorithme est for(int i = 0; i < 10000000; i++)
en 𝑂 1 , même si la {
constante est très grande. cout << "Allo\n";
}
}
30 Département d’informatique et de génie logiciel
Exemples sur les boucles
• Baromètres possibles void f(int n)
{
for(int i = 0; i < 5340*n; i++)
{
cout << "Allo\n";
}
}
31 Département d’informatique et de génie logiciel
Exemples sur les boucles
• Baromètres possibles void f(int n)
{
• Cet algorithme est for(int i = 0; i < 5340*n; i++)
en 𝑂 𝑛 , puisque la {
grandeur d’une constante cout << "Allo\n";
}
multiplicative n’a pas }
d’importance.
32 Département d’informatique et de génie logiciel
Exemples sur les boucles
void f(int n)
• Baromètres possibles {
for(int i = 0; i < n; i++)
• On a deux parties {
indépendantes: for(int j = 0; j < n; j++)
{
• une boucle double cout << i << j << endl;
• une boucle simple }
}
➢ Utiliser une
opération baromètre for(int i = 0; i < n; i++)
pour chacune des {
cout << i << endl;
parties
}
}
33 Département d’informatique et de génie logiciel
Exemples sur les boucles
void f(int n)
• La double boucle s’exécute {
for(int i = 0; i < n; i++)
en 𝑂 𝑛2 .
{
• La boucle simple s’exécute for(int j = 0; j < n; j++)
{
en 𝑂 𝑛 . cout << i << j << endl;
➢ Selon la règle du }
}
maximum, cet algorithme
s’exécute donc en 𝑂 𝑛2 . for(int i = 0; i < n; i++)
{
cout << i << endl;
}
}
34 Département d’informatique et de génie logiciel
Exemples sur les boucles
• Baromètres possibles void f(int n)
{
• Le baromètre s’exécute 𝑖 for(int i = 0; i < n; i++)
fois pour chaque itération {
de la boucle externe. for(int j = 0; j < i; j++)
{
• C n =0+1+2+ cout << "Allo\n";
}
3 + ...+ 𝑛 − 1 }
➢ Méthode de Gauss }
• L’algorithme est donc en
𝑂 𝑛2
35 Département d’informatique et de génie logiciel
Exemples sur les boucles
• Baromètres possibles void f(int n)
{
• Le baromètre s’exécute une for(int i = 1; i <= n; i*=2)
fois à chaque itération de {
la boucle. cout << "Allo\n";
}
➢ On doit trouver combien }
d’itération la boucle fera
pour un 𝑛 donné en
entrée.
36 Département d’informatique et de génie logiciel
Exemples sur les boucles
• Au départ, 𝑖 = 1 = 20 . void f(int n)
{
• Après 1 itération, for(int i = 1; i <= n; i*=2)
𝑖 = 2 ∗ 1 = 21 . {
cout << "Allo\n";
• Après 2 itérations, }
𝑖 = 2 ∗ 2 = 22 . }
• Après 3 itérations,
𝑖 = 4 ∗ 2 = 23
• Après 4 itérations,
𝑖 = 8 ∗ 2 = 24
• Après k itérations,
𝑖 = 2𝑘
37 Département d’informatique et de génie logiciel
Exemples sur les boucles
• Le nombre k d’itérations est void f(int n)
donc donné par le plus petit k {
for(int i = 1; i <= n; i*=2)
tel que 2𝑘 > 𝑛. {
cout << "Allo\n";
• On cherche donc à isoler le
}
nombre k d’itérations. }
• On a donc 𝑙𝑜𝑔2 (2𝑘 ) > 𝑙𝑜𝑔2 (𝑛)
• On a donc k > 𝑙𝑜𝑔2 (𝑛).
38 Département d’informatique et de génie logiciel
Exemples sur les boucles
• On fera donc void f(int n)
𝑙𝑜𝑔2 𝑛 itérations. {
for(int i = 1; i <= n; i*=2)
• Nombre algorithme est {
cout << "Allo\n";
donc en 𝑂 log(𝑛) .
}
}
39 Département d’informatique et de génie logiciel
Pire cas
• Dans les exemples vus jusqu’à maintenant, le coût d’exécution était exactement le
même pour toutes les instances 𝑆 ayant la même taille 𝑛.
• Cas général : le coût d’exécution d’un algorithme dépend
➢ de la taille de l’instance,
➢ de sa nature
• Exemple:
➢ certains algorithmes de tri sont beaucoup plus rapides lorsque les données sont
quasiment triées (exemple: tri par insertion).
• Le coût d’exécution en pire cas 𝐶𝑤𝑜𝑟𝑠𝑡 (𝑛) est le coût d’exécution maximal parmi
toutes les instances 𝑆 de taille 𝑛.
40 Département d’informatique et de génie logiciel
Exemple 1 : Recherche séquentielle dans un tableau non
trié
• On recherche un élément 𝑋 dans un tableau 𝑆 de 𝑛 éléments non triés.
• Puisque le tableau n’est pas trié,
➢ examiner séquentiellement (du début à la fin) chaque élément du tableau.
✓ Si 𝑋 est égale à l’élément examiné, alors on retourne l’index (position) de
cet élément dans le tableau.
✓ Sinon, on passe à l’élément suivant.
✓ Si on n’a pas trouvé 𝑋 après avoir examiné tous les éléments du tableau,
alors on retourne -1 (index non valide).
• En pire cas, il faut examiner les 𝑛 éléments, donc 𝐶𝑤𝑜𝑟𝑠𝑡 𝑛 ∈ 𝑂 𝑛 .
41 Département d’informatique et de génie logiciel
données initialement triées
point milieu
Exemple 2
• On recherche un
élément 𝑋 dans un
tableau 𝑆 de 𝑛
éléments triés.
• On compare 𝑋 avec
l’élément 𝑀 du milieu
du tableau.
• On chercher à gauche
si 𝑋 < 𝑀, à droit si
𝑋 > 𝑀 et on retourne
la position de 𝑀 sinon.
42 Département d’informatique et de génie logiciel
Exemple 2 : Recherche binaire dans un tableau trié
• Opération Baromètre template <typename Comparable>
int binarySearch(const vector<Comparable>& tab, const Comparable& x)
{
int low = 0;
int high = [Link]() - 1;
int mid;
while (low <= high)
{
mid = (low + high) / 2;
if ([Link](mid) < x)
{
low = mid + 1;
}
else if (x < [Link](mid))
{
high = mid-1;
}
else
{
return mid;
}
}
return NOT_FOUND;
}
43 Département d’informatique et de génie logiciel
Exemple 2 : Recherche binaire dans un tableau trié
• En pire cas, nous devrons parcourir tout le tableau afin de déterminer que l’élément
n’est pas présent.
• À chaque itération, nous divisons donc notre tableau en deux parties.
• Combien de fois devons-nous diviser notre tableau en deux avant d’arriver à un
tableau vide?
• Regardons la définition du logarithme:
➢ Un logarithme est un exposant dont il faut affecter un autre nombre appelé
base du logarithme pour obtenir un nombre donné (argument)1.
44 Département d’informatique et de génie logiciel
Exemple 2 : Recherche binaire dans un tableau trié
• … Un logarithme est un exposant dont il faut affecter un autre nombre appelé base
du logarithme pour obtenir un nombre donné (argument).
• Exemple:
➢ 𝑙𝑜𝑔2 8 est la puissance à laquelle il faut élever 2 pour obtenir 8.
✓ Le log nous donne donc la réponse à la valeur 𝑥 dans l’équation suivante :
2𝑥 = 8.
➢ Ce nombre est donc également le nombre de fois qu’on peut diviser 8 par 2
avant d’obtenir 1.
• Si on cherche le nombre de fois qu’on peut diviser un nombre 𝑛 par deux, il suffit de
prendre le 𝑙𝑜𝑔2 𝑛 .
• L’algorithme de recherche binaire est donc en O(𝑙𝑜𝑔2 𝑛 ).
45 Département d’informatique et de génie logiciel
Espace mémoire
• La quantité d’espace mémoire utilisé est également déterminée à l’aide de l’analyse
asymptotique.
• On utilise donc les mêmes techniques que celles utilisées pour déterminer le temps
d’exécution
➢ Coût
46 Département d’informatique et de génie logiciel
Synthèse
• Algorithme : définition
• Efficacité des algorithmes : Complexité/Efficacité, ressources
• Analyse algorithmique : ordre de croissance du nombre d’opérations en fonction du paramètre
pertinent (ex taille n de l’instance à traiter).
• Notations asymptotiques : ensembles de fonctions O borne supérieure, Ω borne inférieure, Θ
bornes inférieure supérieure à deux constantes près
• Opération baromètre : opération élémentaire …
• Règle du maximum
• Comparaison entre les classes de complexité : 𝑂 1 ⊂ 𝑂 𝑙𝑜𝑔(𝑛) ⊂ 𝑂 𝑛 ⊂ 𝑂 𝑛 ∗ 𝑙𝑜𝑔(𝑛)
⊂ 𝑂 𝑛2 ⊂ 𝑂 2𝑛 ⊂ 𝑂 10𝑛 ⊂ 𝑂 𝑛!
• Analyse en pire cas : … non seulement de la taille de l’instance, mais également de sa nature
𝐶𝑤𝑜𝑟𝑠𝑡 (𝑛)
47 Département d’informatique et de génie logiciel
Récursivité
• Définition
➢ Un objet est récursif s'il est défini à partir de lui-même.
• Objets possibles:
➢ Algorithmes.
✓ Un algorithme qui est récursif est défini à partir de lui-même.
✓ Il s’exprime à partir de lui-même.
➢ Fonctions.
✓ Une fonction récursive, définie à partir d’elle-même, doit donc s’appeler elle-
même (directement ou indirectement)
✓ Ex: fonction factorielle: n! = n x (n-1)!
➢ Types.
✓ Liste non-vide = premier élément suivi d’une liste
✓ Arbre binaire = racine + sous-arbre droit + sous-arbre gauche
48 Département d’informatique et de génie logiciel
Algorithmes récursifs
• Idée générale :
➢ La réalisation d’une tâche par un algorithme récursif correct repose sur les deux
éléments suivants:
✓ L’algorithme résout un (ou des) cas particulier(s) du problème d’une façon
directe et non récursive.
✓ Le cas général est solutionné par des appels récursifs successifs qui doivent
converger au(x) cas particulier(s).
➢ Les cas particuliers fournissent donc une condition d’arrêt aux appels récursifs
successifs afin de résoudre un cas particulier de manière non récursive.
49 Département d’informatique et de génie logiciel
Règles qui régissent la récursivité
• Trouver la relation de récurrence permettant d’exprimer votre algorithme en termes
de lui-même.
• S’assurer d’avoir identifié les cas de base pouvant être résolus sans récursivité.
• S’assurer de toujours progresser vers les cas de base à chaque appel récursif.
➢ « Ayez la Foi », mais vérifiez que les appels récursifs progressent réellement
toujours vers les cas de base.
• Danger: Ne jamais refaire le même travail dans des appels récursifs différents (voir la
fonction récursive de Fibonacci).
➢ peut entrainer un temps d’exécution prohibitif.
50 Département d’informatique et de génie logiciel
Fonction récursive
• Structure générale d’une {
if (/*condition de convergence non
fonction récursive respectée*/)
{
//Lancer une exception;
}
if (/*condition d'arrêt*/)
{
return /*valeur*/;
}
else
{
//appel récursif
}
}
51 Département d’informatique et de génie logiciel
Exemple : fonction factorielle
int fact(int n)
• La fonction fact calcule {
l’opération 𝑛!. if (n < 0)
{
• La règle récursive est throw logic_error("l'argument est
𝑓𝑎𝑐𝑡 𝑛 = 𝑛 ∗ 𝑓𝑎𝑐𝑡(𝑛 − 1) négatif");
}
if (n == 0)
{
return 1;
}
else
{
return n * fact(n - 1);
}
}
52 Département d’informatique et de génie logiciel
Exemple : fonction factorielle
• La condition d’arrêt est int fact(int n)
𝑓𝑎𝑐𝑡(0) = 1. {
if (n < 0)
• La condition de convergence {
throw logic_error("l'argument est
est 𝑛 ≥ 0.
négatif");
}
if (n == 0)
{
return 1;
}
else
{
return n * fact(n - 1);
}
}
53 Département d’informatique et de génie logiciel
Avantages et inconvénients d’une solution récursive
• Avantages
➢ Formulation compacte, claire et élégante.
➢ Solution naturelle et facile à concevoir.
➢ Maîtrise des problèmes dont la nature même est récursive.
• Désavantages
➢ Possibilité de grande occupation de la mémoire.
➢ Temps d'exécution peut être plus long.
➢ Estimation parfois difficile de la profondeur maximale de la récursivité.
54 Département d’informatique et de génie logiciel
Dangers solutions récursives: exemple
• Considérez la suite de int fibo (int n)
{
Fibonacci: 0, 1, 1, 2, 3, 5, 8, 13 if (n < 0)
{
… throw logic_error("On doit avoir n >= 0");
}
• Le nième nombre de Fibonacci if (n <= 1)
𝐹(𝑛) est donné par la récurrence: {
return n;
• 𝐹 𝑛 = 𝐹 𝑛 − 1 + 𝐹(𝑛 − 2) et }
else
{
• 𝐹 0 = 0 et 𝐹(1) = 1 return(fibo(n - 1) + fibo(n - 2));
}
}
55 Département d’informatique et de génie logiciel
Exécution de Fibonnacci : algorithme récursif
• Les appels récursifs de 𝑓𝑖𝑏𝑜(𝑛).
• Règle: Ne jamais dupliquer le travail par des appels récursifs différents.
𝑓𝑖𝑏𝑜(𝑛)
𝑓𝑖𝑏𝑜(𝑛 − 2) 𝑓𝑖𝑏𝑜(𝑛 − 1)
𝑓𝑖𝑏𝑜(𝑛 − 3) 𝑓𝑖𝑏𝑜(𝑛 − 2)
𝑓𝑖𝑏𝑜(𝑛 − 4) 𝑓𝑖𝑏𝑜(𝑛 − 3)
𝑓𝑖𝑏𝑜(𝑛 − 4) 𝑓𝑖𝑏𝑜(𝑛 − 3)
𝑓𝑖𝑏𝑜(𝑛 − 6) 𝑓𝑖𝑏𝑜(𝑛 − 5)
56 Département d’informatique et de génie logiciel
Danger d’une solution récursive
• 𝑓𝑖𝑏𝑜(𝑛) effectue plusieurs appels au même calcul.
• Par exemple pour obtenir 𝑓𝑖𝑏𝑜 5 , on calculera 5 fois 𝑓𝑖𝑏𝑜(1) et 3 fois 𝑓𝑖𝑏𝑜 0 .
• Puisque 𝑓𝑖𝑏𝑜(𝑛) est exponentiel en 𝑛, le nombre de fois que 𝑓𝑖𝑏𝑜(1) et
𝑓𝑖𝑏𝑜 0 seront calculés pour un appel à 𝑓𝑖𝑏𝑜(𝑛) augmente exponentiellement avec 𝑛.
• Le temps d’exécution de cet algorithme est donc exponentiel en 𝑛.
57 Département d’informatique et de génie logiciel
Exécution de Fibonnacci : algorithme séquentiel
• Opération baromètre int fibonacci(int n)
{
if (n < 0)
• La solution séquentielle est {
obtenue en 𝑂(𝑛). throw logic_error("On doit avoir n
>= 0");
}
int fib[n + 1];
fib[0] = 0;
if(n > 0)
{
Fib[1] = 1;
}
for (int i = 2; i <= n; ++i)
{
fib[i] = fib[i - 1] + fib[i - 2];
}
return fib[n];
}
58 Département d’informatique et de génie logiciel
Utilisation des algorithmes récursifs
• Nous utiliserons fréquemment la récursivité dans ce cours.
• Particulièrement pour les arbres et les graphes
• Nous nous assurerons de ne pas dédoubler le travail dans les appels récursifs
successifs.
59 Département d’informatique et de génie logiciel
Références
1. Alloprof, [Link]
m1358, consulté le 5 mars 2024.
60 Département d’informatique et de génie logiciel