Ecole Supérieure d’Economie Numérique
Complexité Algorithmique: Algorithme Glouton et
Programmation Dynamique
Dr.Chiheb-Eddine Ben N’Cir
2016 − 2017
Outline
Chiheb-Eddine Ben N’Cir (ESEN)
Complexité Algorithmique:
2016
2 / 1
Algorithme Glouton: Principe
Algorithme Glouton
Construire au fur et à mesure une solution en faisant les choix qui paraissent
optimaux localement
Dans certains cas, cela donnera finalement la meilleure solution: on parlera
d’algorithmes gloutons exacts.
Dans d’autres, non, on parlera d’heuristiques gloutonnes.
Chiheb-Eddine Ben N’Cir (ESEN)
Complexité Algorithmique:
2016
3
3 / 1
Problème
Algorithme Glouton
On dispose des pièces de monnaie correspondant aux valeurs {a0, a1, ..., an−1}
avec 1 = a0 < a2 < ... < an−1.
Pour chaque valeur le nombre de pièces est non borné. Etant donnée une
quantité c entière, on veut trouver une façon de "rendre" la somme c avec un
nombre de pièces minimum.
Chiheb-Eddine Ben N’Cir (ESEN)
Complexité Algorithmique:
2016
4
4 / 1
Solution 1
Algorithme Glouton
Chiheb-Eddine Ben N’Cir (ESEN)
Complexité Algorithmique:
2016
5
5 / 1
Solution 2
Algorithme Glouton
Chiheb-Eddine Ben N’Cir (ESEN)
Complexité Algorithmique:
2016
6
6 / 1
Gestion des films
Algorithme Glouton
Un cinéma possède s salles de cinéma. Chaque semaine, le cinéma propose une
liste de films à voir. Chaque film correspond à une date de début et une date de fin
(intervalle de temps précis) qui sera diffusé dans la salle si. Les films n’ont pas tous la
même durée.
Un amateur de film (libre toute la journée) veut voir le maximum de films pendant cette
journée (il peut voir un même film plusieurs fois). Ecrire un algorithme qui permet de
résoudre le problème en utilisant le principe Glouton.
Chiheb-Eddine Ben N’Cir (ESEN)
Complexité Algorithmique:
2016
7
7 / 1
Modélisation du Problème
Algorithme Glouton
A = {a1, a2, .., an} =⇒ Tableau de n Films qui seront diffusés pendant une journée
Publicité
chaque film ai est caractérisé par di, fi et numSi avec:
di date début du film ai,
fi date fin du film ai,
numSi numéro de la salle qui diffuse le film ai
Film ai et aj sont compatibles si dj >= fi ou di >= fj
Problème: le plus grand nombre de films
choisir le plus grand nombre de films compatibles à voir
Chiheb-Eddine Ben N’Cir (ESEN)
Complexité Algorithmique:
2016
8
8 / 1
Algorithme Glouton
public Film choixFilm(Film [] A)
{
Film [] M; // M contient les films à voir pour maximiser le nombre
de film à regarder
trier(A); // trier le tableau de film selon la date de fin fi
M[0]=A[0];
int nbfilm=1;
int i=1;
While(i<A.length) {
if A[i].d < M[nbfilm-1].f
{
M[nbfilm]=A[i];
nbfilm++;
}
i++
}
return M;
}
Chiheb-Eddine Ben N’Cir (ESEN)
Complexité Algorithmique:
2016
9
9 / 1
Cadre générale d’un algorithme glouton
Algorithme Glouton
Pour mettre au point un algorithme glouton, il faut donc:
Trouver un critère objectif
Trouver un critère de sélection qui parait optimal: souvent facile
L’implémenter: en général facile et efficace!
Chiheb-Eddine Ben N’Cir (ESEN)
Complexité Algorithmique:
2016
10
10 / 1
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)
Complexité Algorithmique:
2016
11
11 / 1
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)
Publicité
Complexité Algorithmique:
2016
12
12 / 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.
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)
Complexité Algorithmique:
2016
13
13 / 1
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.
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)
Complexité Algorithmique:
2016
13
13 / 1
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)
Complexité Algorithmique:
2016
14
14 / 1
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)
Complexité Algorithmique:
2016
15
15 / 1
Programmation dynamique
Suite de Fibonacci: Solution récursive
public int Fibo(int n){
if (n <= 1)
Publicité
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)
Complexité Algorithmique:
2016
15
15 / 1
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)
Complexité Algorithmique:
2016
16
16 / 1
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)
Complexité Algorithmique:
2016
16
16 / 1
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)
Complexité Algorithmique:
2016
17
17 / 1
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)
Publicité
Complexité Algorithmique:
2016
18
18 / 1
Programmation dynamique
Solution recursive: Plusieurs répétitions
Chiheb-Eddine Ben N’Cir (ESEN)
Complexité Algorithmique:
2016
19
19 / 1
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][k];
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)
Complexité Algorithmique:
2016
20
20 / 1
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)
Complexité Algorithmique:
2016
21
21 / 1