Ecole Supérieure d’Economie Numérique
Récursivité et Programmation Dynamique
Dr.Chiheb-Eddine Ben N’Cir
2016 − 2017
Outline
1 Récursivité
2 Programmation dynamique
Chiheb-Eddine Ben N’Cir (ESEN)
Algorithmique avancée
2016
2 / 23
Introduction: Récursivité et le fromage
Récursivité
Chiheb-Eddine Ben N’Cir (ESEN)
Algorithmique avancée
2016
3
3 / 23
Introduction: Récursivité et le fromage
Récursivité
Chiheb-Eddine Ben N’Cir (ESEN)
Algorithmique avancée
2016
3
3 / 23
Récursivité
Récursivité
(Définition récursive, algorithme récursif)
Un algorithme est dit récursif lorsqu’il est défini en fonction de lui-même.
Il résout un problème en calculant des solutions d’instances plus petites du même
problème.
Un algorithme récursif est obligatoirement une fonction
Quand peut-on implémenter un algorithme récursif ?
Est ce qu’un algorithme récursif est plus rapide qu’un algorithme itératif?
Chiheb-Eddine Ben N’Cir (ESEN)
Algorithmique avancée
2016
4
4 / 23
L’algorithme correspondant s’écrit : PUISSANCE (x, n)
if (n == 0) return 1 ;
else return x∗ PUISSANCE(x, n − 1) ;
Principe de récursivité simple
Récursivité
Prenons l’exemple de la fonction puissance x (cid:55)→ xn. Cette fonction peut être définie
récursivement :
xn =
(cid:26) 1si n = 0;
x.x(n−1)si n ≥ 1
Chiheb-Eddine Ben N’Cir (ESEN)
Algorithmique avancée
2016
5
5 / 23
Principe de récursivité simple
Récursivité
Prenons l’exemple de la fonction puissance x (cid:55)→ xn. Cette fonction peut être définie
récursivement :
xn =
(cid:26) 1si n = 0;
x.x(n−1)si n ≥ 1
L’algorithme correspondant s’écrit : PUISSANCE (x, n)
if (n == 0) return 1 ;
else return x∗ PUISSANCE(x, n − 1) ;
Chiheb-Eddine Ben N’Cir (ESEN)
Algorithmique avancée
2016
5
5 / 23
Algorithme pour calculer la combinaison:
COMBINAISON (n, p) if (p == 0 || p == n) return 1
else return COMBINAISON(n − 1, p) + COMBINAISON(n − 1, p − 1)
Récursivité Multiple
Récursivité
Une définition récursive peut contenir plus d’un appel récursif. Nous voulons calculer
ici les combinaisons C p
n en se servant de la relation de Pascal :
C p
n =
(cid:26) 1 si p = 0 ou p = n
n + C p−1
n−1 sinon
C p−1
Chiheb-Eddine Ben N’Cir (ESEN)
Algorithmique avancée
2016
6
6 / 23
Récursivité Multiple
Récursivité
Une définition récursive peut contenir plus d’un appel récursif. Nous voulons calculer
ici les combinaisons C p
n en se servant de la relation de Pascal :
C p
Publicité
n =
(cid:26) 1 si p = 0 ou p = n
n + C p−1
n−1 sinon
C p−1
Algorithme pour calculer la combinaison:
COMBINAISON (n, p) if (p == 0 || p == n) return 1
else return COMBINAISON(n − 1, p) + COMBINAISON(n − 1, p − 1)
Chiheb-Eddine Ben N’Cir (ESEN)
Algorithmique avancée
2016
6
6 / 23
Les algorithmes correspondants s’écrivent :
PAIR (n)
if (n == 0) alors return true
else return IMPAIR (n − 1)
IMPAIR (n)
if (n ==0) return false
else return PAIR (n − 1)
Récursivité mutuelle
Récursivité
Des définitions sont dites mutuellement récursives si elles dépendent les unes des
autres.
Ça peut être le cas pour la définition de la parité :
(cid:26) vrai si n = 0;
pair(n) =
et
impair(n) =
impair(n − 1) sinon;
(cid:26) f aux si n = 0;
pair(n − 1) sinon;
Chiheb-Eddine Ben N’Cir (ESEN)
Algorithmique avancée
2016
7
7 / 23
Récursivité mutuelle
Récursivité
Des définitions sont dites mutuellement récursives si elles dépendent les unes des
autres.
Ça peut être le cas pour la définition de la parité :
(cid:26) vrai si n = 0;
pair(n) =
et
impair(n) =
impair(n − 1) sinon;
(cid:26) f aux si n = 0;
pair(n − 1) sinon;
Les algorithmes correspondants s’écrivent :
PAIR (n)
if (n == 0) alors return true
else return IMPAIR (n − 1)
IMPAIR (n)
if (n ==0) return false
else return PAIR (n − 1)
Chiheb-Eddine Ben N’Cir (ESEN)
Algorithmique avancée
2016
7
7 / 23
l’algorithme de la fonction d’Akermann s’écrit alors:
ACKERMANN(m, n)
if (m == 0) return n + 1;
else if (n == 0&&m > 0) return ACKERM AN N (m − 1, 1)
else return ACKERMANN(m − 1, ACKERMANN(m, n − 1))
récursivité imbriquée
Récursivité
Exemple de récursivité imbriquée est la fonction d’Ackermann est définie comme suit :
A(m; n) =
n + 1 si m = 0
A(m − 1; 1) si m > 0 et n = 0
A(m − 1; A(m; n − 1)) sinon
Chiheb-Eddine Ben N’Cir (ESEN)
Algorithmique avancée
2016
8
8 / 23
récursivité imbriquée
Récursivité
Exemple de récursivité imbriquée est la fonction d’Ackermann est définie comme suit :
A(m; n) =
n + 1 si m = 0
A(m − 1; 1) si m > 0 et n = 0
A(m − 1; A(m; n − 1)) sinon
l’algorithme de la fonction d’Akermann s’écrit alors:
ACKERMANN(m, n)
if (m == 0) return n + 1;
else if (n == 0&&m > 0) return ACKERM AN N (m − 1, 1)
else return ACKERMANN(m − 1, ACKERMANN(m, n − 1))
Publicité
Chiheb-Eddine Ben N’Cir (ESEN)
Algorithmique avancée
2016
8
8 / 23
Non décidabilité de la terminaison
Récursivité
Question : peut-on écrire un programme qui vérifie automatiquement si un
programme donné P termine quand il est exécuté sur un jeu de données D ?
Entrée : Un programme P et un jeu de données D.
Sortie vrai si le programme P termine sur le jeu de données D, et faux sinon.
Chiheb-Eddine Ben N’Cir (ESEN)
Algorithmique avancée
2016
9
9 / 23
Démonstration de non-décidabilité
Récursivité
Supposons qu’il existe un tel programme, nommé termine, de vérification de la
terminaison. À partir de ce programme on conçoit le programme Q suivant :
programme Q
résultat = termine(Q, ∅)
tant que (résultat = vrai) faire
attendre une seconde
fin tant que
renvoyer résultat
Chiheb-Eddine Ben N’Cir (ESEN)
Algorithmique avancée
2016
10
10 / 23
Démonstration de la non-décidabilité
Récursivité
Supposons que le programme Q qui ne prend pas d’arguments- termine.
Donc termine(Q, ∅) renvoie vrai, la deuxième instruction de Q boucle indéfiniment et
Q ne termine pas. Il y a donc contradiction et le programme Q ne termine pas.
Donc, termine(Q, ∅) renvoie faux, la deuxième instruction de Q ne boucle pas, et le
programme Q termine normalement.
Il y a une nouvelle fois contradiction : par conséquent, il n’existe pas de programme tel
que termine, c’est-à-dire qui vérifie qu’un programme termine ou non sur un jeu de
données.
Le problème de la terminaison est indécidable !
Chiheb-Eddine Ben N’Cir (ESEN)
Algorithmique avancée
2016
11
11 / 23
Programmation dynamique
Programmation Dynamique: Principe
La programmation dynamique est une adaptation de la méthode diviser et
régner.
Introduit par Bellman, dans les années 50, pour résoudre des problèmes
d’optimisation.
Programmation veut dire planification et ordonnancement
Chiheb-Eddine Ben N’Cir (ESEN)
Algorithmique avancée
2016
12
12 / 23
Programmation dynamique
Programmation Dynamique vs divisier et régner
La résolution d’un sous problème peut dépondre de la résolution d’autres sous
problèmes
La méthode diviser et régner est récursive, les calculs se font de haut en bas.
La programmation dynamique est une méthode dont les calculs se font de bas
en haut
Chiheb-Eddine Ben N’Cir (ESEN)
Algorithmique avancée
2016
13
13 / 23
Quand utiliser le principe de programmation dynamique ?
il n’y pas de règle pour affirmer que la programmation dynamique peut ou ne peut être
utilisée pour résoudre tel ou tel problème.
Programmation dynamique
Etapes de la Prog. Dynamique
obtention de l’équation récursive liant la solution d’un problème à celle de
sousproblèmes.
initialisation de la table: cette étape est donnée par les conditions initiales de
l’équation obtenue à l’étape 1.
remplissage de la table cette étape consiste à résoudre les sous-problèmes de
taille de plus en plus grandes, en se servant bien entendu de l’équation obtenue
à l’étape 1.
Chiheb-Eddine Ben N’Cir (ESEN)
Algorithmique avancée
2016
14
14 / 23
Programmation dynamique
Etapes de la Prog. Dynamique
obtention de l’équation récursive liant la solution d’un problème à celle de
sousproblèmes.
initialisation de la table: cette étape est donnée par les conditions initiales de
l’équation obtenue à l’étape 1.
remplissage de la table cette étape consiste à résoudre les sous-problèmes de
taille de plus en plus grandes, en se servant bien entendu de l’équation obtenue
Publicité
à l’étape 1.
Quand utiliser le principe de programmation dynamique ?
il n’y pas de règle pour affirmer que la programmation dynamique peut ou ne peut être
utilisée pour résoudre tel ou tel problème.
Chiheb-Eddine Ben N’Cir (ESEN)
Algorithmique avancée
2016
14
14 / 23
Programmation dynamique
Programmation Dynamique: Suite de Fibonacci
Le problème de Fibonacci consiste à calculer les n premiers nombres de
Fibonacci donnés par la formule suivante :
F (0) = 1, F (1) = 1 et F (n) = F (n − 1) + F (n − 2)
Exempe pour n = 4
Chiheb-Eddine Ben N’Cir (ESEN)
Algorithmique avancée
2016
15
15 / 23
La solution proposée est récursive
Complexité: O(2n)
Programmation dynamique
Suite de Fibonacci: Solution récursive
public int Fibo(int n){
if (n <= 1)
return 1 ;
else return(Fibo(n-1)+Fibo(n-2))
}
Chiheb-Eddine Ben N’Cir (ESEN)
Algorithmique avancée
2016
16
16 / 23
Programmation dynamique
Suite de Fibonacci: Solution récursive
public int Fibo(int n){
if (n <= 1)
return 1 ;
else return(Fibo(n-1)+Fibo(n-2))
}
La solution proposée est récursive
Complexité: O(2n)
Chiheb-Eddine Ben N’Cir (ESEN)
Algorithmique avancée
2016
16
16 / 23
La solution proposée est itérative
Complexité: O(n)
Programmation dynamique
Suite de Fibonacci: Solution avec Prog. Dynamique
public int Fib(int n){
int [] F=new int[n]; F[1] =1 ; F[2] =1 ;
For (i=2 ; i<n ; i++)
F[i] = F[i-1] + F[i-2];
return (F[i]);
}
Chiheb-Eddine Ben N’Cir (ESEN)
Algorithmique avancée
2016
17
17 / 23
Programmation dynamique
Suite de Fibonacci: Solution avec Prog. Dynamique
public int Fib(int n){
int [] F=new int[n]; F[1] =1 ; F[2] =1 ;
For (i=2 ; i<n ; i++)
F[i] = F[i-1] + F[i-2];
return (F[i]);
}
La solution proposée est itérative
Complexité: O(n)
Chiheb-Eddine Ben N’Cir (ESEN)
Algorithmique avancée
2016
17
17 / 23
Programmation dynamique
Nombre de Combinaisons Possibles
Ecrire un algorithme qui permet de Déterminer le nombre de combinaisons possibles
de k éléments parmi n sachant que C n
k peut être calculé par:
k−1 + C n−1
k
C n
C n
C n
k = C n−1
0 = 1
n = 1
Chiheb-Eddine Ben N’Cir (ESEN)
Algorithmique avancée
2016
18
18 / 23
Publicité
Programmation dynamique
Solution recursive
int function Combinaison(int n,k) {
if (k = = 0) || (k = = n)
return 1;
else return(Combinaison(n-1,k-1) + Combinaison(n-1,k));
}
Complexité de la solution: exponontielle O(2n)
Chiheb-Eddine Ben N’Cir (ESEN)
Algorithmique avancée
2016
19
19 / 23
Programmation dynamique
Solution recursive: Plusieurs répétitions
Chiheb-Eddine Ben N’Cir (ESEN)
Algorithmique avancée
2016
20
20 / 23
Programmation dynamique
Solution avec Prog. Dynamique
Idée: Pour éviter de calculer plusieurs fois un nombre, on calcule tous les nombres de
petites tailles, ensuite, de tailles de plus en plus grandes avant d’arriver au nombre
désiré.
int function Combinaison(int n, int k) {
int B[][]= new int[n+1][k+1];
for(int i=0 ; i<=n ; i++)
for (int j=0; j<=min(i,k); j++)
if (i==0) ||(j==i)
B[i][j] = 1;
else B[i][j] = B[i-1][j-1] + B[i-1][j];
return (B[n][k]);
}
Complexité de la solution: O(nk)
Chiheb-Eddine Ben N’Cir (ESEN)
Algorithmique avancée
2016
21
21 / 23
Programmation dynamique
Solution 2
public int Combinaison(int n, int p) {
int[]t = new int[n+1];
t[0] = 1;
for (int i = 1; i <= n; i++) {
t[i] = 1;
for (int j = i - 1; j >= 1; j–)
t[j] = t[j] + t[j - 1];
} return t[p];
}
Chiheb-Eddine Ben N’Cir (ESEN)
Algorithmique avancée
2016
22
22 / 23
Programmation dynamique
Exercice
1 Ecrire une fonction itérative puissanceIterative(a, n) qui permet de calculer an.
(en utilisant seulement les opérateurs simples (+, −, ∗, /)
2 Ecrire une fonction récursive puissanceRecursive(a, n) qui permet de calculer
an.
3 Comparer la complexité asymptotique de chacune des fonctions proposées.
Quelle est la fonction la plus performante en terme de complexité de calcul.
4 Supposant qu’on peut écrire la fonction puissance de la manière suivante :
n
2 .a
n
2 .a
n
n
2 .a
n
4 .a
n
4
2 si n est pair sinon an = a
an = a
n
a
2 = a
...........
a1 = a
a0 = 1 Proposer une fonction puissanceDdynamique(a, n) en utilisant le principe
de la programmation dynamique.
5 Quelle est la complexité asymptotique de cette nouvelle fonction.
Chiheb-Eddine Ben N’Cir (ESEN)
Algorithmique avancée
2016
23
23 / 23