View
760
Download
3
Category
Preview:
Citation preview
CHAPITRE III:
RÉCURSIVITÉ ET PARADIGME «
DIVISER POUR RÉGNER »
Université Saad Dahleb de Blida
Faculté des Sciences
Département d’Informatique
Licence Génie des Systèmes Informatique (GSI)
Semestre 5 (3ème année)
ALGORITHMIQUE 02
Cours n°3: 20 Octobre 2013
AROUSSI Sana
Disponible sur https://sites.google.com/a/esi.dz/s-aroussi/
PLAN DU CHAPITRE III
Partie 1: La récursivité
Partie 2: La dérécursivation
Partie 3: La paradigme « Diviser pour régner »
2
PARTIE1: LA RÉCURSIVITÉ
PLAN DE LA PARTIE I
Définitions
Évolution d’un appel récursif
Types de la récursivité
Récursivité terminale vs non terminale
Complexité des algorithmes récursifs
Écrire un algorithme récursif
Exemple: Tours de Hanoi
4
5
Un algorithme est dit récursif s'il est défini en fonction de
lui-même.
DÉFINITIONS
Exemple : la factorielle n!
Itératif
n! = 1 * 2 * ... * n
Récursif
n! = n * (n-1)!
Facto (n: entier): entier
Début
F1;
Pour i2 à n faire
FF*i;
retourne F;
Fin
Facto (n: entier): entier
Début
retourne n*Facto (n-1);
Fin
6
L'exécution d'un appel récursif passe par deux phases, la
phase de descente et la phase de la remontée :
Dans la phase de descente, chaque appel récursif fait à son tour
un appel récursif.
ÉVOLUTION D’UN APPEL RÉCURSIF
Exemple : 4! = Facto(4)
Facto(4) 4 * Facto(3)
Facto(3) 3 * Facto(2)
Facto(2) 2 * Facto(1)
Facto(1) 1 * Facto(0)
Facto(4) 0 * Facto(-1)
7
Puisqu'un algorithme récursif s'appelle lui-même, il est impératif
qu'on prévoit une condition d'arrêt à la récursion, sinon le
programme ne s'arrête jamais!
CONDITION D’ARRÊT
Exemple : la factorielle n!
Version précédente Version correcte
Facto (n: entier): entier
Début
retourne n*Facto (n-1);
Fin
Facto (n: entier): entier
Début
Si (n=1) alors retourne 1
Sinon retourne n*Facto (n-1);
Fin
8
En arrivant à la condition terminale, on commence la phase de la
remontée qui se poursuit jusqu'à ce que l'appel initial soit terminé,
ce qui termine le processus récursif.
ÉVOLUTION D’UN APPEL RÉCURSIF
Exemple :
Facto(4) 4 * Facto(3)
Facto(3) 3 * Facto(2)
Facto(2) 2 * Facto(1)
24 24
1 1 2 2
6 6
Ph
ase
de l
a r
em
on
tée
Ph
ase
de l
a r
em
on
tée
9
1. La récursivité simple où l’algorithme contient un seul appel
récursif dans son corps.
Exemple : la fonction factorielle
Facto (n: entier): entier
Début
Si (n=1) alors retourne 1
Sinon retourne n*Facto (n-1);
Fin
TYPES DE RÉCURSIVITÉ
10
2. La récursivité multiple où l’algorithme contient plus d'un appel
récursif dans son corps
Exemple : le calcul du nombre de combinaisons en se servant de la
relation de Pascal :
TYPES DE RÉCURSIVITÉ
11
3. La récursivité mutuelle: Des modules sont dits mutuellement
récursifs s’ils dépendent les unes des autres
Exemple : la définition de la parité d'un entier peut être écrite de la
manière suivante :
TYPES DE RÉCURSIVITÉ
12
4. La récursivité imbriquée consiste à faire un appel récursif à
l'intérieur d'un autre appel récursif.
Exemple : La fonction d'Ackermann
TYPES DE RÉCURSIVITÉ
13
Un module récursif est dit terminal si aucun traitement n'est effectué
à la remontée d'un appel récursif (sauf le retour du module).
Un module récursif est dit non terminal si le résultat de l'appel
récursif est utilisé pour réaliser un traitement (en plus du retour du
module).
RÉCURSIVITÉ TERMINALE VS NON TERMINALE
Récusivité non terminale Récursivité Terminal
Facto (n: entier): entier
Début
Si (n=1) alors
retourne 1
Sinon
retourne n*Facto (n-1);
Fin
Facto (n: entier, resultat: entier): entier
Début
si (n = 1) alors
retourne resultat;
sinon
retourne Facto (n-1, n * resultat);
Fin
// la fonction doit être appelée en mettant
resultat à 1
14
RÉCURSIVITÉ TERMINALE VS NON TERMINALE
Facto(4,1) Facto(3, 4*1)
Facto(3, 4) Facto(2, 3*4)
Facto(2, 12) Facto(1, 2*12)
Facto(1, 24)
15
La complexité d’un algorithme récursif se fait par la résolution
d’une équation de récurrence en éliminant la récurrence par
substitution de proche en proche.
Exemple : la fonction factorielle (T(n) le temps d’exécution nécessaire pour un
appel à Facto(n))
Facto (n: entier): entier
Début
Si (n=1) [O (1)] alors
retourne 1 [O (1)]
Sinon
retourne n*Facto (n-1); [T (n) dépend de T(n-1)]
Fin
COMPLEXITÉ DES ALGORITHMES RÉCURSIFS
n = 1
16
COMPLEXITÉ DES ALGORITHMES RÉCURSIFS
Pour calculer la solution générale de cette équation, on peut
procéder par substitution :
O (T) = O (n) O (T) = O (n)
17
Dans un module récursif (procédure ou fonction) les paramètres
doivent être clairement spécifiés
Dans le corps du module il doit y avoir:
un ou plusieurs cas particuliers: ce sont les cas simples qui ne
nécessitent pas d'appels récursifs
un ou plusieurs cas généraux: ce sont les cas complexes qui sont résolus
par des appels récursifs
L'appel récursif d'un cas général doit toujours mener vers un des cas
particuliers
ÉCRIRE UN ALGORITHME RÉCURSIF
18
EXEMPLE DES TOURS DE HANOI
Déplacer n disques (empilés les uns sur les autres) d'un piquet (A)
vers un autre piquet (B) en utilisant un troisième (C) comme
intermédiaire (ce sont des piles, on ne peut accéder qu'au
disque du sommet)
un disque ne peut jamais être placé au dessus d'un autre
plus petit
19
Il faut pouvoir exprimer :
« le déplacement de n disques » en fonction d'un ou de plusieurs «
déplacement de m disques » (avec m < n).
Par exemple (m=n-1) si on avait une solution pour déplacer n-1
disques, comment l'utiliser pour déplacer n disques ?
EXEMPLE DES TOURS DE HANOI
CONCEPTION DE LA SOLUTION RÉCURSIVE
20
EXEMPLE DES TOURS DE HANOI
CONCEPTION DE LA SOLUTION RÉCURSIVE
21
EXEMPLE DES TOURS DE HANOI
ALGORITHME INFORMEL
Pour Transférer n disques de A vers B avec C comme intermédiaire,
il faut :
Cas particulier (n = 1)
déplacer le disque de X vers Y.
Cas général (n > 1)
Transférer les n-1 premiers disques de A vers C, en utilisant B
comme intermédiaire
déplacer l'unique disque qui reste dans A vers B
Transférer les n-1 premiers disques de C vers B, en utilisant A
comme intermédiaire
22
EXEMPLE DES TOURS DE HANOI
ALGORITHME FINAL
Hanoi( n:entier; A,B,C : caractères )
SI ( n = 1 )
écrire(« déplacer un disque de », A, « vers », B );
SINON
Hanoi ( n-1, A, C, B );
écrire(« déplacer un disque de », A, « vers », B );
Hanoi( n-1, C, B, A );
FSI
23
EXEMPLE DES TOURS DE HANOI
AUTRE VERSION
Hanoi( n:entier; A,B,C : caractères )
SI ( n > 0 )
Hanoi ( n-1, A, C, B );
écrire(« déplacer un disque de », A, « vers », B );
Hanoi( n-1, C, B, A );
FSI
24
EXEMPLE DES TOURS DE HANOI
COMPLEXITÉ
Hanoi( n:entier; A,B,C : caractères ) [T(n)]
SI ( n > 0 )
Hanoi ( n-1, A, C, B ); [T(n-1)]
écrire(« déplacer un disque de », A, « vers », B ); [O(1)]
Hanoi( n-1, C, B, A ); [T(n-1)]
FSI
T(n) = 2*T(n-1) + a = 2 *(2*T(n-2) + a)+ a = 2*2T(n-2)+ 2a+ a
= ........
= 2n T(0) + (20+21+22+.......+ 2n-1) a
= 2n 0 + (2n -1) a
O (T) = 2 O (T) = 2n
PARTIE 2:
LA DÉRÉCURSIVATION
Cours n°4: 23 Octobre 2013
PLAN DE LA PARTIE II
Généralités
Élimination de la récursivité terminale simple
Élimination de la récursivité terminale multiple
Élimination de la récursivité non terminale simple
Élimination de la récursivité: Algorithme Général
26
27
Au niveau de l’utilisateur: la récursivité permet d’écrire
des algorithmes concis et élégants.
Au niveau de la machine: le compilateur élimine toujours
la récursivité (Dérécursiver) en construisant un
programme itératif (ensemble des instructions
séquentielles) afin d’économiser l'espace de la pile
d'exécution.
Dérécursiver, c’est transformer un algorithme récursif
en un algorithme itératif équivalent ne contenant pas des
appels récursifs.
GÉNÉRALITÉS
28
Rappel: Un algorithme est dit récursif terminal s’il ne
contient aucun traitement après un appel récursif.
ÉLIMINATION DE LA RÉCURSIVITÉ TERMINALE SIMPLE
Procédure ALGO (X) // Liste des paramètres
Si (COND) alors // Condition portant sur X
TRAIT1 // Traitement de base de l’algorithme (dépendant de X)
ALGO (B(X)) // B(X) représente la transformation des paramètres
Sinon
TRAIT2 // Traitement de terminaison (dépendant de X)
Fsi
29
Algorithme Récursif Algorithme Itératif
Procédure ALGO-R (X)
Début
Si (COND) alors
TRAIT1
ALGO-R (B(X))
Sinon
TRAIT2
Fsi
Fin
Procédure ALGO-I (X)
Début
Tant que (COND) faire
TRAIT1
X B(X)
FTQ
TRAIT2
Fin
ÉLIMINATION DE LA RÉCURSIVITÉ TERMINALE SIMPLE
ÉLIMINATION DE LA RÉCURSIVITÉ TERMINALE SIMPLE
EXEMPLE: FACTORIELLE
30
Algorithme Récursif Algorithme Itératif
Fonction Facto-R (n, resultat)
Début
Si (n>1) alors
Retourner (Facto-R (n-1, n * resultat))
Sinon
Retourner (resultat)
Fsi
Fin
Fonction Facto-I (n, resultat)
Début
Resultat1
Tant que (n>1) faire
résultat n * resultat
n n-1
FTQ
Retourner (resultat)
Fin
ÉLIMINATION DE LA RÉCURSIVITÉ TERMINALE MULTIPLE
EXEMPLE: PGCD
31
Écrire une fonction récursive permettant de calculer le PGCD (Plus
Grand Commun Diviseur) de deux nombres naturels non nul (a, b) en
utilisant l’algorithme d’Euclide:
32
Algorithme Récursif Algorithme Itératif
Fonction PGCD-R (a, b)
Début
Si (a = b) alors Retourner (a)
Sinon // ab
Si (a>b) alors
Retourner (PGCD-R (a-b, b))
Sinon
Retourner (PGCD-R (a, b-a))
Fsi
Fin
Fonction PGCD-R (a, b)
Début
Tant que (ab) faire
Si (a>b) alors aa-b
Sinon bb-a
FTQ
Retourner (a)
Fin
ÉLIMINATION DE LA RÉCURSIVITÉ TERMINALE MULTIPLE
EXEMPLE: PGCD
33
Dans un algorithme récursif non terminal, l’appel récursif est
suivi d’un traitement Il reste un traitement (TRAIT2) à
reprendre après l’appel récursif
ÉLIMINATION DE LA RÉCURSIVITÉ NON TERMINALE SIMPLE
Procédure ALGO (X) // Liste des paramètres
Si (COND) alors // Condition portant sur X
TRAIT1 // Traitement de base de l’algorithme (dépendant de X)
ALGO (B(X)) // B(X) représente la transformation des paramètres
TRAIT2 // Traitement à reprendre après le retour (dépendant de X)
Sinon
TRAIT3 // Traitement de terminaison (dépendant de X)
Fsi
34
Il faut donc sauvegarder le contexte de l’appel récursif
(typiquement les paramètres de l’appel engendrant l’appel
récursif) sur une pile
Les piles sont des structures de stockage qui fonctionnent
sur le principe LIFO « last In First Out: le dernier entré
est le premier sorti»
Le principe est de simuler la pile d’appels des processus
pour éliminer la récursivité non terminale.
ÉLIMINATION DE LA RÉCURSIVITÉ NON TERMINALE SIMPLE
35
Algorithme Récursif Algorithme Itératif
Procédure ALGO-R (X)
Début
Si (COND) alors
TRAIT1
ALGO-R (B(X))
TRAIT2
Sinon
TRAIT3
Fsi
Fin
Procédure ALGO-I (X)
Début
Init(P) //Initialiser la Pile P.
Tant que (COND) faire
TRAIT1
Empiler(P, X)
X B(X)
FTQ
TRAIT3
Tant que (Non Vide (P)) Faire
Dépiler(P, U)
TRAIT2
FTQ
Fin
36
ÉLIMINATION DE LA RÉCURSIVITÉ NON TERMINALE SIMPLE EXEMPLE: FACTORIELLE
Algorithme Récursif Algorithme Itératif
Fonction ALGO-I (N)
Début
Init(P) //P contient la valeur de N.
Tant que (n>1) faire
Empiler(P, N)
N N-1
FTQ
Y1
Tant que (Non Vide (P)) Faire
Dépiler(P, U)
Y Y * U
FTQ
Facto-RY;
Fin
Fonction Facto-R (N)
Début
Si (n>1) alors
Y N * Facto-R (N-1)
Sinon
Y1
Fsi
Facto-RY;
Fin
37
ÉLIMINATION DE LA RÉCURSIVITÉ
ALGORITHME GÉNÉRAL
1. Définir la zone de données
•Contient les paramètres, l’adresse du retour et les variables locales.
2. Définir les points d'appel et de retour.
•Il y a donc toujours un appel dans l'algorithme appelant. C'est le premier appel.
3. Appel de la procédure
•3.1. Empiler la zone de données courante.
•3.2. Préparer le nouvel appel en préparant la nouvelle zone de données avec les
paramètres (passage de paramètres) et avec l'adresse de retour (point d'appel).
•3.4. Se brancher vers le début de la fonction.
4. Retour de la procédure
•4.1. Récupérer l'adresse de retour qui se trouve dans la zone de données courante.
•4.2. Dépiler une zone de donnée (restaurer la dernière sauvegardée)
•4.3. Se brancher vers cette adresse.
38
ÉLIMINATION DE LA RÉCURSIVITÉ
EXEMPLE: LES TOURS DE HANOI
Programme appelant
.....
Et0:Hanoi(4,’A’,’B’,’C’);
.....
1. Soit Z la zone de données, Z = [n, S, D, I, @retour]
2. Soient Et0, Et2, Et3 les points d’appel et de retour et Et1
l’adresse de début de la fonction
Procédure appelée
Procédure Hanoi-R ( n, S, D, I)
Et1 SI ( n > 0 )
Et2 Hanoi-R ( n-1, S, I, D );
écrire(SD );
Et3 Hanoi-R ( n-1, I, D, S );
FSI
39
ÉLIMINATION DE LA RÉCURSIVITÉ
EXEMPLE: LES TOURS DE HANOI
Prog. appelant
Et0:Hanoi(4,’A’,’B’,’C’);
//suite du prog
CreerPile(P);
Empiler(P,Z);
Z.n4; Z.S ‘A’; Z.D ‘C’; Z.I ‘B’; Z.@Et0;
goto Et1;
Et0: suite du prog
Proc Hanoi-R ( n, S, D, I) /*Traduction de la procédure*/
Et1 SI ( n > 0 ) Et1: SI ( Z.n > 0 )
Et2 Hanoi-R ( n-1, S, I, D ); Empiler(P,Z)
Z.nZ.n-1; TZ.D; Z.DZ.I; Z.IT; Z.@Et2;
goto Et1;
écrire(SD ); Et2: écrire(Z.SZ.D );
Et3 Hanoi-R ( n-1, I, D, S ); Empiler(P,Z)
Z.nZ.n-1; TZ.S; Z.SZ.I; Z.IT; Z.@Et3;
goto Et1;
FSI Et3: FSI
Fin TmpZ.@;
Depiler(P,Z);
goto tmp
40
ÉLIMINATION DE LA RÉCURSIVITÉ
EXEMPLE: LES TOURS DE HANOI
CreerPile(P); Empiler(P,Z); Z.n4; Z.S ‘A’; Z.D ‘C’; Z.I ‘B’; Z.@Et0;
Allera Et1;
Et1: SI ( Z.n > 0 )
Empiler(P,Z); Z.n:=Z.n-1; T:=Z.D;Z.D:=Z.I;Z.I:=T;Z.@=Et2;
goto Et1;
Et2: écrire(Z.SZ.D );
Empiler(P,Z) Z.n:=Z.n-1; T=Z.S; Z.S:=Z.I; Z.I:=T; Z.@=Et3;
goto Et1;
Et3: FSI
Répéter
Tmp:=Z.@; Depiler(P,Z);
Jusqu’à tmp!=Et3;
Si tmp = Et2
alors goto Et2;
Sinon allera Et0;
Et0: suite du prog
Amélioration: Peut on éliminer les goto???
Équivalente à non pile vide
1
2
3 3
CONCLUSION
Les programmes itératifs sont souvent plus efficaces,
mais les programmes récursifs sont plus faciles à écrire.
Les compilateurs savent, la plupart du temps,
reconnaître les appels récursifs terminaux, et ceux-ci
n’engendrent pas de surcoût par rapport à la version
itérative du même programme.
Il est toujours possible de dérécursiver un algorithme
récursif.
41
PARTIE 3: DIVISER POUR
RÉGNER Cours n°5: 23 Octobre 2013
PLAN DE LA PARTIE III
Principe
Complexité des Algorithmes « Diviser pour
Régner »
43
44
La récursivité est un outils puissant permet de concevoir des
solutions (simples) sans se préoccuper des détails
algorithmiques internes
Paradigme Diviser pour Régner: spécifier la solution du
problème en fonction de la (ou des) solution(s) d'un (ou de
plusieurs) sous-problème plus simple(s).
Comment trouver la solution d'un sous-problème ?
Ce n'est pas important car on prendra comme hypothèse que
chaque appel récursif résoudra un sous-problème
Si on arrive à trouver une solution globale en utilisant ces
hypothèses, alors ces dernières (hypothèses) sont forcément
correctes, de même que la solution globale Cela ressemble à la
« démonstration par récurrence »
PRINCIPE
45
PRINCIPE D
ivis
er
Ré
gn
er
Co
mb
iner
Problème
Global
Sous
Problème
1
Sous
Problème
2
Sous
Problème
K
Décomposer le problème en k
sous problème de taille
moindre
Sous
Solution
1
Sous
Solution
2
Sous
Solution
K
Chaque sous problème sera résolu par la même décomposition récursive
....jusqu’à l’obtention de sous problèmes triviaux
Solution
Globale
Combinaison des solutions
obtenues
46
EXEMPLE 1 : RECHERCHE MAXIMUM
Soit Tab un tableau à n éléments, écrire une fonction
récursive permettant de rechercher de l’indice du
maximum dans Tab en utilisant le paradigme diviser
pour régner
5 8 1 10
5 8 1 10
5 8 1 10
8 10
10
Div
iser
Rég
ner
Combiner
47
EXEMPLE 1 : RECHERCHE MAXIMUM
Fonction maximum ( Tab , indDeb, indFin)
Si ( indDeb = indFin) alors retourner (indDeb)
Sinon
M(indDeb+indFin)/2 // division du problème en 2 sous-problèmes
k1 maximum (Tab, indDeb, m ) // régner sur le 1er sous-problème
k2 maximum (Tab, m+1, indFin) // régner sur le 2ème sous-problème
// Combiner les solutions
Si (Tab[k1] > Tab[k2]) alors retourner (k1)
Sinon retourner (k2)
Fsi
Fsi
Fin
T(n)
T(n) = 2 T(n/2) + c
T(n/2)
T(n/2)
48
EXEMPLE 2 : RECHERCHE DICHOTOMIQUE
Soit Tab un tableau trié (ordre croissant) à n éléments.
La recherche par dichotomie compare l‘élément cherché x avec
l‘élément en position m situé au milieu du sous-tableau :
si Tab[m] = x : on a trouvé l‘élément en position m
si Tab[m] > x : il est impossible que x se trouve après la position
m dans le tableau. Il reste à traiter uniquement la moitié
inférieure du tableau
De même si Tab[m] < x : il reste à traiter uniquement la moitié
supérieure du tableau
On continue ainsi la recherche jusqu’à trouver l’élément ou bien
aboutir sur un tableau de taille nulle, x n'est pas présent et la
recherche s'arrête.
49
EXEMPLE 2 : RECHERCHE DICHOTOMIQUE
Fonction RechDicho(Tab :Tableau, borneinf :entier, bornesup :entier, x :entier) : bool
Si (borneinf<=bornesup) alors
mil (borneinf+bornesup) DIV 2 ;
Si (Tab[mil]=elem) Alors retourner (vrai)
Sinon
Si (Tab[mil]>x) Alors Retourner (RechDicho(Tab, borneinf, mil-1, x))
Sinon
Retourner(RechDicho(Tab, mil+1, bornesup, elem))
Fsi
Sinon
Retourner (Faux)
Fsi
T(n)
T(n/2)
T(n) = T(n/2) + c
50
COMPLEXITÉ DES ALGORITHMES « DIVISER POUR RÉGNER »
Le temps d'exécution d’un algorithme « diviser pour régner » se décompose
suivant les trois étapes du paradigme de base :
Diviser: le problème en a sous-problèmes chacun de taille 1/b de la
taille du problème initial. Soit D(n) le temps nécessaire à la division du
problème en sous-problèmes.
Régner: Soit aT (n/b) le temps de résolution des a sous-problèmes.
Combiner: Soit C(n) le temps nécessaire pour construire la solution
finale à partir des solutions aux sous-problèmes.
T(n) = a T (n/b) + D(n) + C(n)
Soit la fonction f (n) la fonction qui regroupe D(n) et C(n). La fonction T(n) est
alors définie :
T(n) = a.T(n / b) + f(n)
51
COMPLEXITÉ DES ALGORITHMES « DIVISER POUR RÉGNER »
THÉORÈME DE RÉSOLUTION DE LA RÉCURRENCE :
Pour f (n) = c nk , on a : T(n) = a.T(n / b) + c nk
52
COMPLEXITÉ DES ALGORITHMES « DIVISER POUR RÉGNER »
EXEMPLES
Pour T(n) = a.T(n / b) + c nk, on a :
Complexité de l’algorithme de recherche du maximum:
T(n) = 2 T(n/2) + c
a = 2 , b = 2, k = 0 a > bk
T(n) = O(n)
53
COMPLEXITÉ DES ALGORITHMES « DIVISER POUR RÉGNER »
EXEMPLES
Pour T(n) = a.T(n / b) + c nk, on a :
Complexité de l’algorithme de recherche dichotomique:
T(n) = T(n/2) + c
a = 1 , b = 2, k = 0 a = bk
T(n) = O(log(n))
54
COMPLEXITÉ DES ALGORITHMES « DIVISER POUR RÉGNER »
EXEMPLES
Pour T(n) = a.T(n / b) + c nk, on a :
55
COMPLEXITÉ DES ALGORITHMES « DIVISER POUR RÉGNER »
EXEMPLES
Pour T(n) = a.T(n / b) + c nk, on a :
56
COMPLEXITÉ DES ALGORITHMES « DIVISER POUR RÉGNER »
AUTRES RÉSOLUTIONS DE RÉCURRENCE
Équations de récurrence linéaires:
Exemple : Les Tours de Hanoi
Hanoi( n:entier; A,B,C : caractères ) [T(n)]
SI ( n > 0 )
Hanoi ( n-1, A, C, B ); [T(n-1)]
écrire(« déplacer un disque de », A, « vers », B ); [cst]
Hanoi( n-1, C, B, A ); [T(n-1)]
FSI
T(n) = 2*T(n-1) + c avec T(0) = 0;
57
COMPLEXITÉ DES ALGORITHMES « DIVISER POUR RÉGNER »
AUTRES RÉSOLUTIONS DE RÉCURRENCE
Équations de récurrence linéaires:
Exemple : Les Tours de Hanoi
T(n) = 2*T(n-1) + c
O (T) = 2n O (T) = 2n
58
COMPLEXITÉ DES ALGORITHMES « DIVISER POUR RÉGNER »
AUTRES RÉSOLUTIONS DE RÉCURRENCE
Équations de récurrence linéaires sans second membre (f(n) = cte)
A une telle équation, on peut associer un polynôme:
La résolution de ce polynôme nous donne m racines ri ( avec
m<=k).
La solution de l’équation de récurrence est ainsi donnée par :
Cette solution est en général exponentielle
59
COMPLEXITÉ DES ALGORITHMES « DIVISER POUR RÉGNER »
AUTRES RÉSOLUTIONS DE RÉCURRENCE
Exemple : La suite de Fibonacci
SOURCES DE CE COURS
Frédéric Vivien, Algorithmique avancée, École Normale Supérieure de Lyon, 2002.,
pp. 93. Disponible sur http://perso.ens-lyon.fr/frederic.vivien/Enseignement/Algo-
2001-2002/Cours.pdf
Slim Msfar, Algorithmique et Complexité, 2012, pp 104. Disponible sur
http://p835.phpnet.org/testremorque/upload/catalogue/coursalgorithmi.pdf
Walid-Khaled Hidouci, La récursivité, École nationale Supérieure d’Informatique,
pp 107. Disponible sur hidouci.esi.dz/algo/cours_recursivite.pdf
La récursivité, Cours d’ Algorithmique et Structures de données dynamiques, École
nationale Supérieure d’Informatique, Année Universitaire 2009-2010.
60
Recommended