Lycée > Terminale > NSI > Utiliser la méthode « diviser pour régner »

Utiliser la méthode « diviser pour régner »

Fiche de cours
Quiz
Profs en ligne
Videos
Application mobile

Objectifs

Comprendre la méthode « diviser pour régner ».
Écrire un programme qui utilise la méthode « diviser pour régner ».

Points clés

La méthode « diviser pour régner » consiste à découper la donnée que l’on veut traiter en plusieurs parties, puis à appliquer l’algorithme étudié sur chacune de ces parties, pour enfin combiner les résultats obtenus afin d’obtenir un résultat sur la donnée initiale.
La récursivité est utilisée dans la méthode « diviser pour régner ».
Le tri fusion utilise la méthode « diviser pour régner ».
Le tri fusion consiste à diviser le tableau à trier en deux sous-tableaux, à trier récursivement chacun des deux sous-tableaux, puis à les fusionner.

Pour bien comprendre

Utiliser la récursivité en Python
Connaitre l’algorithme de recherche dichotomique dans un tableau trié

1. La méthode « diviser pour régner »

En informatique, la méthode (ou stratégie) « diviser pour régner » consiste à diviser le problème à résoudre en plusieurs sous-problèmes indépendants que l’on résout récursivement, puis dont on combine les solutions afin d’obtenir une solution globale au problème initial.

En pratique, il s’agit souvent de découper la donnée que l’on veut traiter en plusieurs parties, puis à appliquer l’algorithme étudié sur chacune de ces parties, pour enfin combiner les résultats obtenus afin d’obtenir un résultat sur la donnée initiale.

L’avantage de cette méthode est d’obtenir une résolution simple d’un problème complexe ou d’un problème dont la résolution itérative aurait été complexe.

Cette méthode est souvent décrite en trois phases.

Diviser : on divise le problème initial en plusieurs sous-problèmes indépendants (souvent en découpant la donnée initiale).
Régner : on résout chacun des sous-problèmes.
Combiner : on mutualise les réponses des sous-problèmes pour résoudre le problème initial.

Exemple
La recherche dichotomique d’un élément dans un tableau trié peut être programmée avec la méthode « diviser pour régner ».

Cet algorithme consiste à rechercher la position d’un élément en le comparant au milieu du tableau, il est donc en effet possible, si l’élément recherché n’est pas au milieu, d’appliquer la recherche dichotomique au sous-tableau dans lequel l’élément peut se trouver.

Par exemple, on applique la recherche dichotomique de 8 dans le tableau :

[1, 2, 3, 5, 8, 13, 21, 25, 30, 31, 32, 35, 38, 41, 42].

On obtient :

Étape 1 : le milieu du tableau est 25, la partie gauche est [1, 2, 3, 5, 8, 13, 21] et la partie droite est [30, 31, 32, 35, 38, 41, 42].
Comme 8 < 25, alors on applique la recherche dichotomique à la partie gauche [1, 2, 3, 5, 8, 13, 21].
Étape 2 : le milieu de [1, 2, 3, 5, 8, 13, 21] est 5, la partie gauche est [1, 2, 3] et la partie droite est [8, 13, 21].
Comme 8 > 5, alors on applique la recherche dichotomique à la partie droite [8, 13, 21].
Étape 3 : le milieu de [8, 13, 21] est 13, la partie gauche est [8] et la partie droite est [21].
Comme 8 < 13, alors on applique la recherche dichotomique à la partie gauche [8].
Étape 4 : [8] contient 8. On a trouvé l’élément.

Ainsi en divisant trois fois successivement le tableau initial et en appliquant la recherche dichotomique au sous-tableau choisi, on a trouvé 8. On a ainsi divisé le problème initial en sous-problèmes que l’on a résolu (régner) pour finalement obtenir le résultat final.

2. Utiliser la méthode « diviser pour régner » – Le tri fusion

Le tri fusion d’un tableau est un algorithme qui consiste à découper le tableau en deux sous-tableaux, à trier chaque sous-tableau, puis à les fusionner.
Ce tri utilise la méthode « diviser pour régner ».

Remarque
En informatique, « trier » consiste à ranger dans l’ordre croissant.

a. Algorithme

Voici un algorithme de la fonction récursive de tri fusion d’un tableau tab.

Algorithme	Explication
Fonction tri_fusion(tab):	On définit la fonction tri_fusion qui prend pour paramètre un tableau tab. Cette fonction permet de trier tab.
n ← taille(tab)	On affecte à n la taille de tab.
Si n < 2, alors retourner tab	Si tab contient au plus 1 élément, on retourne tab.
Sinon retourner fusion (tri_fusion(tab[0 : n/2]), tri_fusion(tab[n/2 : n]))	Sinon on retourne la fusion de la moitié gauche triée tab[0 : n/2] et de la moitié droite triée tab[n/2 : n].
FinSi	Fin de l’instruction conditionnelle.

La fonction fusion(tab1, tab2) prend en paramètres deux tableaux triés tab1 et tab2 et les fusionne pour obtenir un tableau trié.

Exemple
fusion([1, 5, 8, 9], [2, 3, 6]) renvoie [1, 2, 3, 5, 6, 8, 9].

Remarque
La fusion n'est pas une concaténation (mise bout à bout), mais un traitement qui renvoie un tableau trié à partir de deux tableaux triés.

b. Programme en Python

Diviser et régner

En Python, la fonction tri_fusion(tab) implémente le tri fusion de tab.

Python	Explication
def tri_fusion(tab):	On définit la fonction tri_fusion.
n = len(tab)	La longueur de la table len(tab) est affectée à la variable n.
if n < 2:	Si n est inférieure à 2,
return tab	on retourne tab.
else:	Sinon
return fusion (tri_fusion(tab[:n//2]), tri_fusion(tab[n//2:]))	on retourne la fusion de la partie gauche triée tri_fusion(tab[:n//2]) et de la partie droite triée tri_fusion(tab[n//2:])

Combiner

En Python, il reste à implémenter la partie « combiner » de la méthode « diviser pour régner » : il faut définir la fonction fusion(tab1, tab2) qui est utilisée dans la fonction tri_fusion(tab).

La fonction fusion prend pour paramètres des tableaux triés dans l’ordre croissant. Ces tableaux peuvent être de taille différente.

Dans cette fonction, on compare successivement les éléments de tab1 et de tab2 pour tous les ranger dans l’ordre croissant.

Python	Explication
def fusion(tab1, tab2):	On définit la fonction fusion.
n1 = len(tab1) n2 = len(tab2) i1 = 0 i2 = 0 tab_sortie = []	La variable n1 référence la taille de tab1. La variable n2 référence la taille de tab2. Les variables i1 et i2 sont initialisées à 0. La variable tab_sortie référence le tableau de sortie initialisé à [].
while i1 < n1 and i2 < n2:	Tant que i1 est inférieure à n1 et i2 est inférieure à n2
if tab1[i1] < tab2[i2]:	Si l’élément d’indice i1 du tableau tab1 est inférieur à l’élément d’indice i2 du tableau tab2,
tab_sortie.append(tab1[i1]) i1 = i1 + 1	on ajoute tab1[i1] au tableau de sortie et on incrémente i1 de 1.
else:	Sinon,
tab_sortie.append(tab2[i2]) i2 = i2 + 1	on ajoute tab1[i2] au tableau de sortie et on incrémente i2 de 1.
if i1 == n1: tab_sortie = tab_sortie + tab2[i2:]	Si i1 vaut n1, alors on a parcouru tout tab1, donc on ajoute la fin de tab2 au tableau de sortie.
else: tab_sortie = tab_sortie + tab1[i1:]	Sinon, on a parcouru tout tab2, donc on ajoute la fin de tab1 au tableau de sortie.
return tab_sortie	on retourne tab_sortie.

Exemple
On souhaite trier le tableau [1, 6, 5, 7, 8, 2, 4, 9, 3].

Voici l’exécution de l’algorithme tri fusion sur Pythontutor. On obtient le tableau trié [1, 2, 3, 4, 5, 6, 7, 8, 9].