Cours n°05
(suite du Diviser pour Régner)
Dr. Mahfoud Houari
[email protected]Université Abou-Bakr Belkaïd - Tlemcen
2023/2024
Diviser pour Régner
Exemple : Union des Intervalles
Étant donné un tableau T contenant des intervalles triés selon
leur début, l’objectif est de trouver l’union de tous ces intervalles
si elle existe. Par exemple :
Pour T={[1,5], [3,8], [7,13],[13,21]}, le résultat doit être [1, 21].
Pour T={[1,5], [3,8], [9,13],[13,21]}, le résultat doit être NULL.
À faire :
1. Proposez une méthode itérative pour ce problème et calculez sa
WCTC et sa WCSC.
2. Proposez une méthode Diviser-pour-Régner pour ce problème et
calculez sa WCTC et sa WCSC.
Diviser pour Régner
Exemple : Union des Intervalles
Méthode naïve :
class Intervalle {
int g, d;
public Intervalle(int g, int d) {
this.g = g; this.d = d;
}
public Intervalle unionWith(Intervalle I) {
if (this.d < I.g || I.d < this.g)
return null;
else
return new Intervalle(Math.min(this.g, I.g),
Math.max(this.d, I.d));
}
public String toString() {
return "["+this.g+","+this.d+"]";
}
}
Diviser pour Régner
Exemple : Union des Intervalles
Méthode naïve :
public static Intervalle UI_Naive(Intervalle[] T) {
if(T.length == 0)
return null;
if(T.length == 1)
return T[0];
Intervalle resultat = new Intervalle(T[0].g, T[0].d);
for(int i=1; i < T.length; i++) {
if(T[i].unionWith(resultat) == null)
return null;
else
resultat = T[i].unionWith(resultat);
}
return resultat;
WCTC : O(|T|)
}
WCSC : O( 1 )=
Diviser pour Régner
Exemple : Union des Intervalles
Méthode DpR :
public static Intervalle UI_DpR(Intervalle[] T, int D, int F) {
if(D > F)
return null;
if(D == F)
return T[D];
int M = (D + F)/2;
Intervalle resG = UI_DpR(T, D, M);
Intervalle resD = UI_DpR(T, M + 1, F);
if(resG == null || resD == null)
return null;
else
return resG.unionWith(resD); WCTC : O( ????? )
} WCSC : O( ????? )=
Diviser pour Régner
Exemple : Union des Intervalles
Méthode DpR – Mesure de la WCTC
public static Intervalle UI_DpR(Intervalle[] T, int D, int F) {
if(D > F) 1
return null; 1
if(D == F) 1
return T[D]; 2
int M = (D + F)/2; 4
Intervalle resG = UI_DpR(T, D, M); 2 + CG
Intervalle resD = UI_DpR(T, M + 1, F); 3 + CD
if(resG == null || resD == null) 3
return null; 1
else
return resG.unionWith(resD); 1 + CunionWith
}
Diviser pour Régner
Exemple : Union des Intervalles
Méthode DpR – Mesure de la WCTC
public static Intervalle UI_DpR(Intervalle[] T, int D, int F) {
if(D > F)
return null;
if(D == F)
return T[D];
int M = (D + F)/2;
Intervalle resG = UI_DpR(T, D, M); O(1)+CG+CD
Intervalle resD = UI_DpR(T, M + 1, F);
if(resG == null || resD == null)
return null;
else
return resG.unionWith(resD);
}
Diviser pour Régner
Exemple : Union des Intervalles
Méthode DpR – Mesure de la WCTC
public static Intervalle UI_DpR(Intervalle[] T, int D, int F) {
if(D > F)
return null;
if(D == F)
return T[D];
int M = (D + F)/2;
Intervalle resG = UI_DpR(T, D, M);
Intervalle resD = UI_DpR(T, M + 1, F);
if(resG == null || resD == null)
return null;
else
return resG.unionWith(resD); WCTC : O(|T|)
} WCSC : O( ????? )=
Diviser pour Régner
Exemple : Union des Intervalles
Méthode DpR – Mesure de la WCSC
public Intervalle UI_DpR(Intervalle[] T, int D, int F) { 3
if(D > F)
return null;
if(D == F)
return T[D];
int M = (D + F)/2; 1
Intervalle resG = UI_DpR(T, D, M); 1+CG
Intervalle resD = UI_DpR(T, M + 1, F); 1+CD
if(resG == null || resD == null)
return null;
else
return resG.unionWith(resD); CunionWith
}
Diviser pour Régner
Exemple : Union des Intervalles
Méthode DpR – Mesure de la WCSC
public Intervalle UI_DpR(Intervalle[] T, int D, int F) { 3
if(D > F)
return null;
if(D == F)
return T[D];
int M = (D + F)/2; 1
Intervalle resG = UI_DpR(T, D, M); 1+CG
Intervalle resD = UI_DpR(T, M + 1, F); 1+CD
if(resG == null || resD == null)
return null;
else
return resG.unionWith(resD); 6
}
Diviser pour Régner
Exemple : Union des Intervalles
Méthode DpR – Mesure de la WCSC
public Intervalle UI_DpR(Intervalle[] T, int D, int F) {
if(D > F)
return null;
if(D == F)
return T[D];
int M = (D + F)/2;
Intervalle resG = UI_DpR(T, D, M); O(1)+CD + CG
Intervalle resD = UI_DpR(T, M + 1, F);
if(resG == null || resD == null)
return null;
else
return resG.unionWith(resD);
}
Diviser pour Régner
Exemple : Union des Intervalles
Méthode DpR – Mesure de la WCSC
public static Intervalle UI_DpR(Intervalle[] T, int D, int F) {
if(D > F)
return null;
if(D == F)
return T[D];
int M = (D + F)/2;
Intervalle resG = UI_DpR(T, D, M);
Intervalle resD = UI_DpR(T, M + 1, F);
if(resG == null || resD == null)
return null;
else
return resG.unionWith(resD); WCTC : O(|T|)
} WCSC : O(log2(|T|))=
Diviser pour Régner
Quelques paradigmes de programmation
Calculer la Complexité d'un
Algorithme « Diviser pour Régner »
Diviser pour Régner
Calculer la Complexité d'un Algorithme DpR :
1. À travers l'Arbre des Appels Récursifs :
●
Calculer le coût d’un seul appel récursif en fonction des entrées.
●
Tracer un arbre montrant comment sont générés les appels récursifs.
●
À chaque niveau de l'arbre, calculer le coût de tous les appels récursifs
appartenant à ce niveau.
●
Compter le nombre des niveaux de l'arbre (un log en cas de division).
●
Le coût total de l'algorithme est la somme des coûts de tous les
niveaux (multiplication, suite géométrique,….).
Diviser pour Régner
Quelques paradigmes de programmation
Calculer la Complexité d'un Algorithme DpR :
1. À travers l'Arbre des Appels Récursifs :
Exemple de la recherche dichotomique :
public boolean Rech_Dichotomique(int[] T, int E, int D, int F) {
if (D > F) 1
return false ;
int M = D + (F – D)/2 ; 5
if(T[M] == E) 2
return true ;
else if (T[M] > E) 2
return Rech_Dichotomique(T, E, D, M -1); 2
else return Rech_Dichotomique(T, E, M+1, F); 2
} Chaque appel nécessite un coût borné par O(1).
Diviser pour Régner
Calculer la Complexité d'un Algorithme DpR :
1. À travers l'Arbre des Appels Récursifs :
Exemple de la recherche dichotomique :
●
À chaque niveau de l'arbre on effectue un nombre d'instructions qui
ne dépend pas de la taille N du tableau, donc c'est O(1).
● Le nombre des niveaux de l'arbre est égal à log2(N).
● Le coût total de l'algorithme : O(1) + . . . + O(1) = O(log2(N)).
log2(N) fois
Diviser pour Régner
Calculer la Complexité d'un Algorithme DpR :
2. À travers le théorème des récurrences : " Master Theorem "
Un algorithme DpR peut produire l'équation des récurrences suivante :
C(N) = a.C(N/b) + O(Nd) où a >= 1, b >= 2, d >= 0
●
N : La taille du problème initial.
●
a : Le nombre de sous-problèmes considérés à chaque récursion.
●
b : La taille du problème est divisée sur b à chaque récursion.
●
O(Nd) : Le coût de chaque récursion (division, combinaison,…) sans
compter le coût des appels récursifs.
Diviser pour Régner
Calculer la Complexité d'un Algorithme DpR :
2. À travers le théorème des récurrences : " Master Theorem "
Un algorithme DpR peut produire l'équation des récurrences suivante :
C(N) = a.C(N/b) + O(Nd) où a >= 1, b >= 2, d >= 0
Cette équation est résolue comme suit :
●
d > logb(a) ⇒ C(N) = O(Nd).
●
d = logb(a) ⇒ C(N) = O(Nd . logb(N)).
●
d < logb(a) ⇒ C(N) = O(N log b(a)).
Diviser pour Régner
Calculer la Complexité d'un Algorithme DpR :
2. À travers le théorème des récurrences : " Master Theorem "
Exemple 1 : La recherche dichotomique
C(N) = 1.C(N/2) + O(N0)
Donc on a :
d = 0 = log2(1) ⇒ C(N) = O(N0 . log2(N))
= O(log2(N))
Diviser pour Régner
Calculer la Complexité d'un Algorithme DpR :
2. À travers le théorème des récurrences : " Master Theorem "
Exemple 2 : Le Tri par Fusion
C(N) = ?.C(N/?) + O(N ?)
Diviser pour Régner
Calculer la Complexité d'un Algorithme DpR :
Tri par fusion:
public int[] triFusion(int[] T){
if( T.length <= 1 ) O(1)
return T; O(1)
else {
int [] TG = new int [T.length / 2]; O(|T|)
int [] TD = new int [T.length - T.length / 2]; O(|T|)
int i = 0 , j = 0 ; O(1)
while (i < T.length/2) { O(|T|)
TG[i] = T[i] ; i++ O(|T|)
}
while (i < T.length) { O(|T|)
TD[j] = T[i] ; i++ ; j++; O(|T|)
}
return fusionner(triFusion(TG), triFusion(TD)); O(|T|)
}
}
Diviser pour Régner
Calculer la Complexité d'un Algorithme DpR :
2. À travers le théorème des récurrences : " Master Theorem "
Exemple 2 : Le Tri par Fusion
C(N) = 2.C(N/2) + O(N1)
Donc on a :
d = 1 = log2(2) ⇒ C(N) = O(N1 . log2(N))
Diviser pour Régner
Calculer la Complexité d'un Algorithme DpR :
2. À travers le théorème des récurrences : " Master Theorem "
Exemple 3 : Recherche dans un arbre binaire A équilibré ayant
N nœuds
C(N) = ?.C(N/?) + O(N?)
public boolean existe(Arbre A, int E) {
if (A == null)
return false ;
else if (A.valeur == E)
return true ;
else
return existe(A.fg, E) || existe(A.fd, E) ;
}
Diviser pour Régner
Calculer la Complexité d'un Algorithme DpR :
2. À travers le théorème des récurrences : " Master Theorem "
Exemple 3 : Recherche dans un arbre binaire A équilibré ayant
N nœuds
C(N) = 2.C(N/2) + O(N0)
public boolean existe(Arbre A, int E) {
if (A == null)
return false ;
else if (A.valeur == E)
return true ;
else
return existe(A.fg, E) || existe(A.fd, E) ;
}
Diviser pour Régner
Calculer la Complexité d'un Algorithme DpR :
2. À travers le théorème des récurrences : " Master Theorem "
Exemple 3 : Recherche dans un arbre binaire A équilibré ayant
N nœuds
C(N) = 2.C(N/2) + O(N0)
Donc on a :
d = 0 < log2(2) = 1 ⇒ C(N) = O(N log2 (2))
= O(N)
Diviser pour Régner
Calculer la Complexité d'un Algorithme DpR :
2. À travers le théorème des récurrences : " Master Theorem "
Exemple 3 : Recherche dans un arbre binaire A équilibré ayant
N nœuds
C(N) = 2.C(N/2) + O(N0)
Donc on a :
d = 0 < log2(2) = 1 ⇒ C(N) = O(N log2 (2))
= O(N)
Que devient cette équation de récurrences
si l’arbre n’est pas équilibré ?
Diviser pour Régner
Calculer la Complexité d'un Algorithme DpR :
2. À travers le théorème des récurrences : " Master Theorem "
Exemple 4 : Recherche dans un ABR A équilibré de N nœuds
C(N) = ?.C(N/?) + O(N?)
public boolean existe(Arbre A, int E) {
if (A == null)
return false ;
else if (A.valeur == E)
return true ;
else if (A.valeur > E)
return existe(A.fg, E) ;
else
return existe(A.fd, E) ;
}
Diviser pour Régner
Calculer la Complexité d'un Algorithme DpR :
2. À travers le théorème des récurrences : " Master Theorem "
Exemple 4 : Recherche dans un ABR A équilibré de N nœuds
C(N) = 1.C(N/2) + O(N0)
public boolean existe(Arbre A, int E) {
if (A == null)
return false ;
else if (A.valeur == E)
return true ;
else if (A.valeur > E)
return existe(A.fg, E) ;
else
return existe(A.fd, E) ;
}
Diviser pour Régner
Calculer la Complexité d'un Algorithme DpR :
2. À travers le théorème des récurrences : " Master Theorem "
Exemple 4 : Recherche dans un ABR A équilibré de N nœuds
C(N) = 1.C(N/2) + O(N0)
Donc on a :
d = 0 = log2(1) ⇒ C(N) = O(N0 . log2(N))
= O(log2(N))
Diviser pour Régner
Calculer la Complexité d'un Algorithme DpR :
2. À travers le théorème des récurrences : " Master Theorem "
Exemple 5 : Afficher l'inverse d'un tableau T de N éléments
C(N) = ?.C(N/?) + O(N0)
Diviser pour Régner
Calculer la Complexité d'un Algorithme DpR :
Méthode DpR pour afficher l’inverse d’un tableau:
public void AlgoDpR(int[] T){
if( T.length == 1 )
System.out.print( T[0] + " ") ;
else {
int [] TG = new int [T.length / 2];
int [] TD = new int [T.length - T.length / 2];
int i = 0, j = 0 ;
while (i < T.length/2) { TG[i] = T[i] ; i++} ;
while (i < T.length) { TD[j] = T[i] ; i++; j++} ;
AlgoDpR(TD) ; AlgoDpR(TG) ;
}
}
a = 2, b = 2, et d = 1
Diviser pour Régner
Calculer la Complexité d'un Algorithme DpR :
2. À travers le théorème des récurrences : " Master Theorem "
Exemple 5 : Afficher l'inverse d'un tableau T de N éléments
C(N) = 2.C(N/2) + O(N1)
Donc on a :
d = 1 = log2(2) ⇒ C(N) = O(N1 . log2(N))
Diviser pour Régner
Calculer la Complexité d'un Algorithme DpR :
2. À travers le théorème des récurrences : " Master Theorem "
Exemple 6 : Recherche dans une matrice carrée
On veut tester si un élément E appartient à une matrice A[N][N].
Supposons que N est pair pour faciliter le discours.
⇒ Une recherche naïve coûtera O(N²) en temps et en espace.
⇒ Proposer une méthode DpR et calculer sa WCTC.
Diviser pour Régner
Calculer la Complexité d'un Algorithme DpR :
2. À travers le théorème des récurrences : " Master Theorem "
Exemple 6 : Recherche dans une matrice carrée
boolean Existe(int [][] A, int E, int DL, int FL, int DC, int FC){
if(DL > FL || DC > FC) return false;
if(DL == FL && DC == FC) return A[DL][DC] == E ;
int ML = (DL + FL)/2 ;
int MC = (DC + FC)/2 ;
return Existe(A, E, DL, ML, DC, MC)
|| Existe(A, E, DL, ML, MC + 1, FC)
|| Existe(A, E, ML + 1, FL, DC, MC)
|| Existe(A, E, ML + 1, FL, MC + 1, FC)
}
a = 4, b = 2, et d = 0
d < log2(4) ⇒ C(N) = O(N log2(4)) = O(N²).
Diviser pour Régner
Quelques paradigmes de programmation
Exercice:
Soient donnés un tableau T composé d'entiers triés en ordre
croissant, et un entier K. L’objectif est de tester s'il y a deux
éléments de T dont la somme est égale à K. La méthode doit
retourner soit une paire contenant les deux entiers ou NULL.
Diviser pour Régner
Quelques paradigmes de programmation
Solution naîve :
class Paire{
int e1, e2 ;
public Paire(int e1, int e2){
this.e1 = e1 ; this.e2 = e2 ;
}
}
Paire Sol_Naive(int[] T, int K){
for(int i=0 ; i < T.length - 1 ; i++){
for(int j= i + 1; j < T.length ; j++){
if(T[i] + T[j] == K)
return new Paire(T[i], T[j]) ;
}
}
return NULL ; WCTC : O( |T|² )
} WCSC : O( 1 )=
Diviser pour Régner
Quelques paradigmes de programmation
Solution DpR (version n°01) :
Paire Sol_DPR_v1(int[] T, int K){
for(int i=0 ; i < T.length ; i++){
int X = T[i] ;
int Y = K - T[i] ;
if((Y <= X && RechDicho(T, Y, 0, i-1)) ||
(Y > X && RechDicho(T, Y, i+1, T.lenght -1))
return new Paire(X, Y) ;
}
return NULL ;
} WCTC : O(|T|.log2(|T|))
WCSC : O(log2(|T|))=
Diviser pour Régner
Quelques paradigmes de programmation
Solution DpR (version n°02) :
Paire Sol_DPR_v2(int[] T, int K, int D, int F){
if(D > F)
return NULL ;
int M = (D + F)/2 ;
int X = T[M], Y = K - T[M] ;
if((Y <= X && RechDicho(T, Y, 0, i-1)) ||
(Y > X && RechDicho(T, Y, i+1, T.lenght -1))
return new Paire(X, Y) ;
else {
Paire g = Sol_DPR_v2(T, K, D, M - 1) ;
Paire d = Sol_DPR_v2(T, K, M + 1, F) ;
if(g != NULL)
return g ;
else if (d != NULL)
return d ;
else WCTC : O(|T|.log2(|T|))
return NULL ;
} WCSC : O(log2(|T|))=
}
