S09 MÉTHODE DIVISER POUR RÉGNER

1) PRINCIPE DE LA MÉTHODE DIVISER POUR RÉGNER

 Diviser : partager le problème en sous-problèmes de même nature (souvent de taille n/2)
 Régner : résoudre ces différents sous-problèmes (généralement récursivement)
 Combiner : fusionner les solutions pour obtenir la solution du problème initial
Une illustration : [Link]

2) EXEMPLE INTRODUCTIF : LA DICHOTOMIE

Cette méthode, vous la connaissez tous! Soit une liste de n objets déjà triés. On recherche un objet en
Vous avez probablement joué au jeu :trouve un nombre particulier.
entre 1 et 100. Vous avez commencé par proposer 50. Si on  On choisit dans la liste l'objet médian (une moitié des objets
vous répond, c'est plus, vous proposez 75 puis si l'on vous est avant, l'autre moitié est après).
répond c'est moins vous proposez 62... Vous êtes alors en  On compare les deux objets. Trois cas sont possibles :
train d'effectuer une recherche dichotomique ! o Si on a trouvé l'objet cherché alors c'est fini.
Faire une recherche dichotomique, c'est chercher une o Si l'objet recherché est placé avant l'objet médian alors on
valeur dans un tableau trié. recommence avec cette première partie de la liste.
A chaque étape, on prend le milieu de l'ensemble des valeurs o Si l'objet recherché est placé après l'objet médian alors on
possibles pour éliminer la moitié des possibilités. On est recommence avec cette seconde partie de la liste
dans une méthode de diviser pour régner. On répète cette démarche jusqu'à ce qu'au bout d'un certain
La méthode générale est donc la suivante : nombre d'essais (cela se calcule) :
oSoit on a trouvé l'objet cherché,
oSoit il n'est pas dans la liste.
EXEMPLE À LA MAIN
Prenons par exemple la liste triée suivante : [1,3,4,6,7,8,10,13,14], où nous allons rechercher par dichotomie l'élément 4

On utilise deux pointeurs indice_gauche et indice_droit pour délimiter la sous-

liste sur laquelle porte la recherche courante. Au départ il s'agit de la liste entière donc
indice_gauche pointe vers l'élément d'indice 0 et indice_droite pointe vers le
dernier élément de notre liste qui ici a l'indice 8.
On cherche l'indice indice_centre de l'élément médian. C’est donc l'élément
0+8
d'indice = 4, c'est-à-dire l'élément 7.
2

Maintenant on compare l'élément central 7 à l'élément recherché 4 : ici 4 < 7, cela signifie
que 4 se trouve dans la première moitié de la liste (celle avant 7).
On modifie alors la valeur du pointeur indice_droit, qui prend la valeur de indice_centre-1=3.

On recommence avec cette nouvelle sous-liste :

indice_gauche = 0 indice_droit= 3
0+3
et indice_centre=1 (partie entière de )
2
Maintenant on compare l'élément central 3 à l'élément recherché 4 : ici 4 > 3, cela signifie que
4 se trouve dans la deuxième moitié de la sous-liste (celle après 3).

On modifie alors la valeur du pointeur indice_gauche, qui prend la valeur de

(indice_centre+1)

On recommence avec cette nouvelle sous-liste.

indice_gauche=2 indice_droit=3
2+3
et indice_centre=2 (partie entière de , c'est-à-dire de 2.5)
2

Maintenant on compare l'élément central 4 à l'élément recherché 4 : ici 4 = 4,

l'élément recherché est donc à l’indice 2.

1
EXERCICE 1
1) Compléter le pseudo code ci-contre. v ← élément cherché
2) Implémenter en python cette fonction itérative deb ← indice du premier élément de la liste
fin ← indice du dernier élément de la liste
dichotomie(t,v) qui m ← …..................................
o Renvoie l’indice d’une valeur v dans un Tant que deb <= fin faire
tableau trié t si v = ….............. alors
o Renvoie false, si v n’appartient pas à t renvoyer m
3) Implémenter en python une fonction récursive sinon si ….................... alors
fin ← m–1
dichotomieRecursive(t,v)qui sinon
o Renvoie l’indice d’une valeur v dans un deb ← m+1
tableau trié t fin si
o Renvoie false, si v n’appartient pas à t m ← …........................
Fin Tant que
Renvoyer Faux
COMPLEXITÉ D’UNE DICHOTOMIE:
Lors d’une recherche dichotomique d’un élément v dans une liste triée « list » de longueur n, le nombre 𝑓 de fois
dans le cas le plus défavorable ( v∉list ) où la liste sera coupée en deux vérifie
𝑛
𝑓
= 1 ⇔ 2 𝑓 = 𝑛 ⇔ log 2 2 𝑓 = log 2 𝑛 ⇔ 𝑓 = log 2 𝑛
2
La complexité en temps dans le pire des cas de l'algorithme de recherche dichotomique est 𝒪 log 2 𝑛
Une recherche séquentielle dans le pire des cas, en parcourant les éléments de gauche à droite dans le tableau est
en 𝒪 𝑛 ce qui est moins efficace. Néanmoins, il est à noter que la recherche dichotomique utilise un tableau TRIE,
ce qui peut aussi avoir un coût en temps...
REMARQUE :
La recherche dichotomique est bien une méthode où on divise le problème en un problème plus petit. En revanche,
on ne combine pas les solutions à la fin (pas de régner)

3) EXEMPLE D’UNE MÉTHODE DE DIVISER POUR RÉGNER : LE TRI FUSION

Rappel : les tris connus, par sélection ou par insertion, sont de complexité quadratique en .
Si vous ne connaissez pas ces tris, voici 2 vidéos de présentations :
Le tri par sélection : [Link]
Le tri par insertion : [Link]
PRINCIPE DU TRI FUSION :
 On se donne une liste de longueur n, d’objets de même type, comparables.
 On scinde la liste en deux sous-listes de même longueur (à 1 près), de manière récursive jusqu’à obtenir des
listes de longueur 1.
 Ces listes sont triées : avec un seul élément, ce n’est pas trop dur…
 On remonte la récursivité en fusionnant deux listes « voisines » de manière à conserver l’ordre sur le résultat.
EXEMPLE À LA MAIN :
 Fonctionnement général de l’algorithme

8 7
-3 0 4 12 2
↙︎ ↘
Division 1 8 7 -3 0 4 12 2
↙︎ ↘ ↓ ↘
Division 2 8 7 -3 0 4 12 2
↙︎ ↓ ↙︎ ↓ ↓ ↘ ↘
Division 3 8 7 -3 0 4 12 2
↘ ↓ ↘ ↓ ↓ ↙︎ ↙︎
Fusion 1 7 8 -3 0 4 12 2
↘ ↓ ↘ ↙︎
Fusion 2 -3 0 7 8 2 4 12
↘ ↙︎
Fusion 3 -3 0 2 4 7 8 12

2
  Détails de la phase de fusion.
On parcourt les deux sous-listes de gauche et de droite en même temps, en triant les éléments au fur et à
mesure.
Supposons que le programme en soit au moment où il doit combiner les tableaux [7, 8] et [-3, 0].

Résultat
Début 7 8 -3 0

Comparaison 1 : -3 < 7 7 8 -3 0 -3

Comparaison 2 : 0 < 7 7 8 -3 0 -3 0

La liste de droite a été entièrement explorée, 7 8 -3 0 -3 0 7 8

on recopie les éléments restants à gauche

COMPLEXITÉ :
Comme on divise la taille du tableau par 2 à chaque appel récursif, on fait appels.
Lors de la phase de combinaison, on parcourt les listes de gauche et de droite, donc en temps n à chaque appel
récursif. D’où une complexité quasi linéaire .
PROGRAMME EN PSEUDO CODE
Fonction triFusion(liste) : Fonction fusion(liste1, liste2) :
""" """
Sépare la liste en deux Fusionne deux listes triées en seule liste triée
Et appelle récursivement sur les sous-listes """
""" On définit une liste vide résultat
Si la liste a une longueur inférieur ou égale 1 : On va parcourir les 2 listes triées en partant du plus petit élément
On renvoie la liste de chaque liste.
Sinon On va ajouter à la liste résultat le plus petit des éléments entre la
On sépare la liste en 2 liste1 et la liste2 tant que les 2 listes ne seront pas vides.
La liste gauche sera la liste du début au milieu Si une des listes devient vide, on ajoute à résultat alors tous les
La liste droite sera la liste du milieu à la fin éléments de la liste encore pleine.
On renvoie la fusion du triFusion de la liste gauche
et du triFusion de la liste droite On retourne la liste résultat
EXERCICE 2 :
Implémenter en Python le tri fusion d’une liste de nombres

4) EXEMPLE VISUEL : RECHERCHE DES DEUX POINTS LES PLUS PROCHES DANS UN NUAGE PLANAIRE
On dispose de plusieurs points dans un plan.
On cherche quels sont les deux points les plus proches.
Méthode par force brute :
On ordonne les points par coordonnée x croissante (tri fusion ou tri
rapide de complexité ).
Puis, pour chaque point d’abscisse , on calcule toutes les
distances avec j ≥ i.
On retrouve un « classique » du calcul de complexité, à savoir que le nombre d’itérations est

, soit une complexité quadratique

(on rappelle que dans ce cas le coût du tri en est négligeable en comparaison).

3
Méthode avec diviser pour régner :
On commence par créer deux tableaux ordonnés avec les points. L’un, , est ordonné suivant les abscisses x
croissantes, l’autre est ordonné suivant les ordonnées y croissantes. On a donc une complexité

1. Descente récursive 1 (et suivantes): 2. Descente récursive 2 et suivantes :

Avec , on scinde l’ensemble de points en deux parties de On scinde chaque sous-ensemble en deux parties de taille
taille égale à 1 près. égale à 1 près (toujours avec )

3. Fin de la descente récursive : 4. Phase de combinaison :

Dans chaque ensemble de 2 ou 3 points, on résout le On crée une bande de largeur , où
problème directement. Avec 2 points il n’y a qu’une seule avec de chaque côté de la
possibilité, avec 3 points on fait 2 comparaisons. On obtient
bande médiane
dans chaque partie.

Dans cette bande, pour chaque point à gauche, on calcule La phase de combinaison se termine en prenant le minimum
les distances avec points de droites qui sont « autour » de ce des trois distances , ,
point dans le tableau
(cf. ① ci-dessous).
On appelle le minimum de ces distances

On itère le processus en remontant la récursivité. Ici on a Fin.

représenté le calcul de certaines distances à cheval sur
droite et gauche
①Lors de ce calcul, pour un point P donné à gauche et d’ordonnée , on se contente de calculer les
distances avec les points de droite situés dans le rectangle centré en ordonnée , de hauteur (ordonnées)
2 , et de largeur . En effet, hors de ce rectangle, les points seront trop loin. On trouve ces points par une
recherche dichotomique dans le tableau trié (complexité )
Complexité : On admet que la complexité de cet algorithme est (y compris les tris initiaux) ce
qui est bien plus performant que la force brute en .