DIVISER POUR

REIGNER ET SES
VARIANTES

PLAN
 Diviser pour reigner

 Exemples

 Diminuer pour reigner

 Exemples

 Transformer pour reigner

 Exemples

1
 Diviser pour
régner
7 29 4  2 4 7 9

72  2 7 94  4 9

77 22 99 44

Diviser pour régner

• Principe
Nombres d’algorithmes ont une structure récursive: pour résoudre un
problème donné, ils s’appellent eux-mêmes récursivement une ou
plusieurs fois sur des problèmes très similaires, mais de taille
moindres, résolvent les sous-problèmes de manière récursive puis
combinent les résultats pour trouver une solution au problème initial.

Le paradigme ‘diviser pour régner’ donne lieu à trois étapes à chaque

niveau de récursivité:

Diviser : le problème en un certain nombre de sous-problèmes;

Régner : sur les sous-problèmes en les résolvant récursivement ou, si la
taille d’un sous-problème est assez réduite, le résoudre directement.
Combiner : les solutions des sous-problèmes en une solution complète du
problème initial.

2
 Tri fusion
• Principe
L’algorithme de tri par fusion est construit suivant le paradigme ‘diviser pour régner’:
Il divise la séquence de n nombres à trier en deux sous-séquences de taille n/ 2 .
Il trie récursivement les deux sous-séquences.
Il fusionne les deux sous-séquences triées pour produire la séquence complète
triée.

La récursion termine quand la sous-séquence à trier est de longueur 1 (car une telle
séquence est toujours triée).

• Algorithme
La principale action de l’algorithme de tri par fusion est justement la fusion des
deux listes triées.

•La fusion
Le principe de cette fusion est simple: à chaque étape, on compare les éléments
minimaux des deux sous-listes triées, le plus petit des deux étant l’élément minimal
de l’ensemble on le met de côté et on recommence. On conçoit ainsi un algorithme
5

Tri fusion
Fusionner qui prend en entrée un tableau A et trois entiers, p, q et r, tels que p ≤
q< r et tels que les tableaux A[p .. q] et A[q+1 .. r] soient triés. L’algorithme est
donné ci- dessous:
Fusionner ( A, p,q, r)
indice servant à parcourir le tableau A[ p ..q]
ip
indice servant à parcourir le tableau A[q  1 ..r ]
j  q 1
tableau temporaire dans lequel on construit le résultat
soit C un tableau de taille r  p 1
indice servant à parcourir le tableau temporaire
k1
boucle de fusion
tant que i  q et j  r faire
si A[i]  A[ j] alors C[k ]  A[i]
i  i 1 sinon C[k ]  A[ j]
j  j 1
k  k 1
tant que i  q faire C[k ]  A[i]
i  i 1
k  k 1
6

3
 Tri fusion
tant que j  r faire C[k ]  A[j]
j  j 1
k  k 1 pour k  1 à r  p 1 faire
A[ p  k 1]  C[k ]

•Complexité de la fusion
Etudions les différentes étapes de l’algorithme:
-Les initialisations ont un coût constant O(1).
-La boucle tant que de fusion s’exécute au plus r-p
fois, chacune de ses itérations
étant de coût constant, d’où un coût total en O(r  p).
-Les deux boucles tant que complétant C ont une complexité
respective au pire de
q-p+1 et de r-q, ces deux complexité étant O(r  p);
- La recopie finale coûte O(r  p 1).
Par conséquent, l’algorithme de fusion a une complexité en
O(r  p).
7

Tri fusion
• L'algorithme
Tri  Fusion( A, p, r)
si p  r alors q  ( pr ) /2 
Tri  Fusion( A, p, q) Tri  Fusion( A, q 1, r) Fusionner( A, p, q, r)

• Complexité
Pour déterminer la formule de récurrence qui nous donnera la complexité de
l’algorithme Tri-Fusion, nous étudions les trois phases de cet algorithme
‘diviser pour régner’:
Diviser: cette étape se réduit au calcul du milieu de l’intervalle [p; r], sa
complexité est donc en O(1).
Régner: l’algorithme résout récursivement deux sous-problèmes de tailles
respectives n/ 2 , d’où une complexité en 2  t(n/2).
Combiner: la complexité de cette étape est celle de l’algorithme de fusion qui est de O(n)
Pour la construction d’un tableau solution de taille n.
 le tri par fusion a pour complexité O(n log n)

4
 Tri rapide
• Principe

Tri rapide

14 88
98
31 30 23 ≤ 52 ≤ 62
25 79

Trier la première moitié. Trier la deuxième moitié.

14,23,25,30,31 62,79,98,88

10

5
 Tri rapide
• Algorithme

11

Tri rapide
Exemple

6 2 8 5 11 10 4 1 9 7 3

Utiliser 6 comme pivot

2 5 4 1 3 6 7 9 10 11 8

Trier les parties gauche et droite récursivement

12

6
 Tri rapide
Pivoter(A, p, r)
{
x = A[r] // x est pivot
i = p - 1
for j = p to r – 1
{
do if A[j] <= x
then
{
i = i + 1
permuter A[i]  A[j]
}
}
permuter A[i+1]  A[r]
return i+1 Le coût de pivoter() est
}
O(n)

13

Tri rapide
a) Pire cas

14

7
 Tri rapide

b) Meilleur cas

15

Diminuer pour
régner

8
 La technique diminuer pour régner
• Cette technique consiste à exploiter la relation qui existe entre la solution
d’une instance et celle d’une instance plus petite.
• Nous solutionnons alors l’instance en « diminuant sa taille ». Cela peut se
faire en:
• Diminuant la taille d’une constante (ex: taille réduite d’une unité)
• Diminuant la taille par un facteur (ex: taille réduite de moitié)
• Diminuant la taille d’une quantité variable (à chaque itération)
• Illustrons cette technique sur le problème d’exponentiation.
• L’objectif est de calculer f(n) = an pour une constante « a » donnée.
• Cette fonction se calcule du haut vers le bas à l’aide de la récurrence:

• Ce qui rend explicite le fait que la solution f(n) est obtenue à l’aide de la
solution f(n-1) d’une instance d’une unité plus petite.
17

Solutionner l’exponentiation en
diminuant pour régner
• Le nombre C(n) de multiplications effectuées pour calculer f(n) est
alors donné par:
• C(n) = C(n-1) + 1 avec C(1) = 0
• Ce qui donne C(n) = n-1 (en pires cas et meilleurs cas).
• Cette fonction f(n) se calcule également en diminuant la taille de
l’instance de moitié à chaque itération.
• En effet, lorsque n est pair, f(n) = (an/2)2. Dans ce cas f(n) = f2(n/2) et il suffit
alors de multiplier f(n/2) par lui-même.
• Si n est impair alors n-1 est pair. Alors f(n) = a¢(a(n-1)/2)2 . Dans ce cas, f(n) = a¢
f2((n-1)/2).
• Dans tous les cas, f(n) se calcule alors à l’aide le la récurrence:

18

9
 Un algorithme diminuer d’un facteur
2 pour régner
ALGORITHME Pow1(a, n)
//Entrée: deux entiers a et n ¸ 1
//Sortie: an
if n = 1 return a
temp à Pow1(a, bn/2c)
temp à temp £ temp
if n is even return temp
else return a £ temp

• Cette dernière récurrence diminuer pour régner est effectuée par l’algorithme
Pow1(a,n) ci-haut.
• Notez que chaque appel à Pow1 engendre un seul appel récursif.
• Utilisons temp  temp pour opération de base. Le nombre C(n) de fois que
cette opération est effectuée satisfait la récurrence:
• C(n) = 1 + C (bn/2c).
• Lorsque n = 2k, C(n) est alors donné (en pires cas et meilleurs cas) par:
• C(n) = C(n/2) + 1 avec C(1) = 0
19

Analyse de l’algorithme « diminuer

de moitié » pour régner
• La méthode des substitutions à rebours donne alors:
• C(2k) = C(2k-1) + 1
= C(2k-2) + 2
= C(2k-i) + i
= C(20) + k
=0+k
= lg(n) car 2k = n

• Alors C(n) = lg(n) pour n = 2k. Or lg(n) 2 O(log(n)) et log(n) est

harmonieuse. Alors C(n) 2 O(log(n)) pour tout n.

• L’approche « diminuer de moitié » est donc substantiellement plus

efficace que l’approche « diminuer d’une unité » car cette dernière
nécessitait O(n) multiplications
20

10
Solutionner l’exponentiation en divisant
pour régner
• Il importe de réaliser que l’approche « diminuer de moitié » n’est pas une approche
diviser pour régner.
• En effet, l’approche diviser pour régner appliquée au problème de l’exponentiation
consiste à diviser l’instance n en deux instances distinctes bn/2c et dn/2e et solutionner
(régner sur) les deux instances!
• Alors, l’approche diviser pour régner calcule f(n) à l’aide le la récurrence:

• Cette récurrence est correcte car f(bn/2c) ¢ f(dn/2e) = abn/2c ¢ adn/2e = a(bn/2c + dn/2e) = an =
f(n). L’algorithme Pow2 effectue cette récurrence:
ALGORITHME Pow2(a, n)
//Entrée: deux entiers a et n ¸ 1
//Sortie: an
if n = 1 return a
return Pow2(a,bn/2c) £ Pow2(a,dn/2e)
21

Analyse de l’algorithme diviser pour

régner
• Le nombre C(n) de multiplications effectuées par Pow2 est donnée par la
récurrence:
• C(n) = C(bn/2c) + C(dn/2e) + 1 avec C(1) = 0
• C(n) = 2 C(n/2) + 1 avec C(1) = 0 lorsque n = 2k

• La méthode des substitutions à rebours donne:

• C(2k) = 2 C(2k-1) + 1
= 2 [ 2 C(2k-2) +1] + 1
= 22 C(2k-2) + 2 + 1
= 22 [ 2 C(2k-3) + 1 ] + 2 + 1
= 23 C(2k-3) + 22 + 2 + 1
= 2i C(2k-i) + 2i-1 + 2i-2 + … + 2 + 1
= 2k C(20) + 2k-1 + 2k-2 + … + 2 + 1
= 0 + 2k - 1 (série géométrique très connue: voir annexe A)
= n - 1 (car 2k = n)
• Alors C(n) = n -1 2 O(n) 22

11
Conclusions
• Donc, pour le problème de l’exponentiation:
• L’efficacité de l’algorithme diviser pour régner est nettement
inférieure à celle de diminuer pour régner car elle se trouve à calculer
récursivement deux fois la même quantité (au lieu d’une seule fois
comme c’est le cas pour diminuer pour régner)
• De manière générale, un algorithme « diminuer de moitié pour régner »
donne un temps d’exécution logarithmique (en la taille de l’instance)
lorsque, en diminuant de moitié, on génère uniquement un nombre
constant d’opérations
• En effet, la récurrence C(n) = C(n/2) + r avec C(1) = 0 a pour solution
C(n) = r lg(n).
• La recherche binaire dans un tableau trié est un autre exemple
d’algorithme « diminuer de moitié pour régner »
• Malheureusement, il est rare que l’on puisse introduire seulement un
nombre constant d’opérations en diminuant l’instance de moitié

23

Diminuer d’une quantité variable

pour régner
• L’algorithme d’Euclide nous fourni un exemple d’algorithme dont
la taille de l’instance diminue d’une quantité variable à chaque
itération
• Pour trouver le pgcd(m,n), l’algorithme d’Euclide solutionne
pgcd(n, m mod n).
• La taille de l’instance est donc diminuée d’une quantité qui
dépend des valeurs de m et n

24

12
 Le problème de sélection
• Le problème de sélection est celui de trouver le kième plus petit
élément dans un tableau de n nombres
• Lorsque k=1 (ou k=n), il suffit de balayer le tableau une seule fois
pour trouver le plus petit (ou le plus grand) élément.
• Ces cas triviaux prennent un temps 2 O(n).
• Un cas plus intéressant est celui de trouver l’élément médian. Cet
élément est le kième plus petit élément pour k = dn/2e.

• Pour résoudre ce problème nous pouvons d’abord trier le tableau

A[1..n] et, ensuite, aller directement à l’élément A[k].
• Selon la règle du maximum, l’ordre de croissance du temps requis est
déterminé par la partie la plus lente: trier le tableau.
• Dans ce cas, cet algorithme trier-d’abord-et-accéder, nécessite un temps 2
O(n log n) si on utilise le tri fusion.

25

Le problème de sélection
• Essayons de résoudre le problème de trouver le kième plus petit
élément sans trier d’abord le tableau

• Considérons la procédure Partition(A[1..n]) utilisée pour le tri rapide.

• Cette procédure utilise l’élément A[1]=p pour pivot, partitionne le
tableau A[1..n] autour du pivot p et retourne l’index s du pivot.
• Partition(A[1..n]) doit permuter certains éléments de A pour
accomplir cette tâche

• Cela signifie que lorsque Partition(A[1..n]) retourne, le tableau A est

partitionné comme suit:
• A[i] · A[s] pour i 2 {1..s-1}
• A[s] = p
• A[i] ¸ A[s] pour i 2 {s+1..n}

• Donc A[s] est le s-ième plus petit élément de A[1..n] 26

13
 Le problème de sélection
• Donc, lorsque Partition(A[1..n]) retourne:
• si s = k, A[s] est le kième plus petit élément de A[1..n] (et le problème est résolu).
• si s > k, le kième plus petit élément de A[1..n] se trouve dans A[1..s-1]. Ce sera le kième
plus petit élément de A[1..s-1].
• si s < k, le kième plus petit élément de A[1..n] se trouve dans A[s+1..n]. Ce sera (k-s)ième
plus petit élément de A[s+1..n].
• L’algorithme suivant trouve donc le kième plus petit élément de A[1..n].
• C’est un algorithme « diminuer d’une quantité variable pour régner ».
• Contrairement au tri rapide, un seul des sous tableaux est traité à chaque appel

ALGORITHME SelectionRec(A[l..r], k)
//Entrée: un sous tableau A[l..r] et un entier k : 1 · k · r – l + 1
//Sortie: le kième plus petit élément dans A[l..r]
s à Partition(A[l..r])
if s-l+1 = k return A[s]
if s-l+1 > k return SelectionRec(A[l..s-1], k)
if s-l+1 < k return SelectionRec(A[s+1..r], k-s+l-1)
27

Le problème de sélection

• Exemple: trouvez l’élément médian de 4, 1, 10, 9, 7, 12, 8, 2, 15

• Puisque nous avons n = 9 éléments, l’élément médian est le dn/2eième =
5ième plus petit élément. Donc k = 5.
• Le premier appel à Partition(A[1..9]), choisira A[1]=4 pour le pivot et
partitionnera A de la manière suivante:
2, 1, 4, 9, 7, 12, 8, 10, 15
• Nous avons alors s = 3 · k = 5. L’algorithme cherchera alors le (5-3)ième
= 2ième plus petit élément dans 9, 7, 12, 8, 10, 15
• (posons maintenant k = 2)
• L’appel à Partition pour ce sous tableau donnera la partition suivante:
8, 7, 9, 12, 10, 15
• Nous avons maintenant s = 3 ¸ 2 = k. L’algorithme cherchera alors le 2ième
plus petit élément dans 8, 7
• L’appel à Partition donnera alors 7, 8 et s = 2 = k. L’élément médian
recherché est donc 8.

28

14
Analyse de l’algorithme
SelectionRec(A[1..n])
• En pire cas et meilleur cas nous avons Cpartition(n) 2 O(n) (voir le tri
rapide, Diviser pour reigner)
• En meilleur cas, un seul appel à Partition est effectué lorsque le pivot
coïncide avec le kième plus petit élément.
• Alors Cbest(n) = Cpartition(n) 2 O(n)

• En pire cas, chaque appel récursif de SelectionRec(A[l..r],k) s’effectue

sur un tableau dont la taille a diminuée d’un seul élément.
• Cela se produit par exemple lorsque k=n et que le tableau initial A[1..n] est
déjà trié et que tous ses éléments sont distincts.
• Dans ces pire cas, nous obtenons la même récurrence que celle obtenue lors
de l’analyse du tri rapide en pire cas:
• Cworst(n) = Cworst(n-1) + Cpartition(n)
• Donc Cworst(n) 2 O(n2) d’après notre analyse du tri rapide

29

Transformer pour
régner

15
 L’approche « transformer pour
régner »
• Cette méthode de conception regroupe plusieurs techniques qui
s’appuient toutes sur l’idée générale de transformer les instances pour
qu’elles soient plus faciles à solutionner.
• Il existe trois grandes classes de transformations:
• Simplification de l’instance: l’instance est transformée en une instance du même
problème mais qui est plus simple (et moins coûteuse) à traiter.
• Ex: « pré triage »: on trie le tableau avant de le traiter
• Changement de représentation: l’instance est représentée sous une autre forme
plus adaptée au problème initial
• Ex: on transforme un tableau en un arbre binaire, arbre AVL, tas, etc.
• Réduction (d’un problème à un autre): le problème initial est transformé en un
autre problème pour lequel on possède un algorithme efficace
• Il faut alors toujours pouvoir reconstruire la solution du problème initial à partir de la solution
du nouveau problème

31

Simplification d’instance :Le « pré

triage »
• Plusieurs opérations sur un tableau s’effectuent plus rapidement
lorsqu’il est trié
• Considérons le problème de déterminer si tous les n éléments d’un
tableau sont distincts
• Si l’on tente de résoudre ce problème sur un tableau non trié, il faut
alors comparer, en pire cas, toutes les n(n-1)/2 paires d’éléments
• Cela nécessite O(n2) comparaisons en pire cas
• Si l’on trie d’abord le tableau, il suffit simplement d’examiner chaque
paire A[i], A[i+1] d’éléments consécutifs
• Cela nécessite alors O(n) comparaisons en pire cas
• Mais le tri fusion nécessite O(n log n) opérations
• Le temps d’exécution total (trier + balayer) est donc O(n log n) en
pire cas.
• Ce problème se résout donc plus rapidement si l’on tri d’abord le
tableau.
32

16
 Simplification d’instance :Le « pré
triage »
• Considérons le problème de recherche d’un élément K dans un tableau de n
éléments
• Nous pouvons effectuer une recherche séquentielle sur un tableau non
trié. Cela nécessite O(n) comparaisons en pire cas
• Nous pouvons trier d’abord le tableau et ensuite faire une recherche
binaire sur le tableau trié
• Le tri-fusion nécessite O(n log n) opérations en pire cas
• Le recherche binaire nécessite O(log n) comparaisons en pire cas
• Le temps total d’exécution (tri + recherche) en pire cas sera donc de O(n
log n).

• Ce problème se résout donc moins rapidement en triant d’abord

33

Changement de représentation
• Considérons le problème de recherche d’un élément K dans un ensemble
de n éléments

• La recherche doit être considérée dans le contexte de la dynamique des

données (statique ou dynamique).

• Les opérations (données dynamiques):

trouver (rechercher)
Insérer
effacer

34

17
 Changement de représentation

• Recherche dans les listes (pour les données statiques)

Recherche séquentielle
Recherche dichotomique
Recherche par interpolation

• Recherche dans les arbres (pour données dynamiques):

Arbre binaire
Arbre AVL
Etc.

35

Changement de représentation
CALCUL DE LA VALEUR D’UN POLYNÔME

Schéma de Horner

Schéma de Horner
Début
P  T[n]
Pour i  n-1 à 0 faire P  P*X + T[i]

FP
Fin
36

18
 Changement de représentation
CALCUL DE LA VALEUR D’UN POLYNÔME

Schéma de Horner

Example: p(x) = 2x4 - x3 + 3x2 + x - 5

= x(2x3 - x2 + 3x + 1) - 5
= x(x(2x2 - x + 3) + 1) - 5
= x(x(x(2x - 1) + 3) + 1) - 5

coefficients 2 -1 3 1 -5
x=3 2 3*2+(-1)=5 3*5+3=18 3*18+1=55 3*55+(-5)=160

Trouver un autre algorithme pour calculer an en se basant sur l’algorithme

de Horner?

37

Réduction de problème
• Cette variante résout un problème en le transformant en un problème
différent pour lequel un algorithme est déjà disponible.

• La réduction est justifiée lorsque la complexité combinée de la

transformation et de la résolution de l’autre problème devrait être
inférieure à la résolution du problème donné par une autre méthode.

38

19
 Réduction de problème
• Calcul du plus petit commun multiple via le calcul du plus grand commun
diviseur.
ppcm(m,n)*pgcd(m,n) = m*n

• compter le nombre de chemins de longueur n dans un graphe donné en

calculant An avec A la matrice d’adjacence du graphe.

• Transformer un problème de minimisation en un problème de

maximisation et vice versa.
Min(Z) = Max(-Z).

• Résoudre des problèmes en utilisant la représentation par des graphes

d’états.
39

20