TermNSI/Recursivité/Diviser_pour_regner

Diviser pour régner

Le programme

La méthode diviser pour régner est une approche algorithmique puissante, souvent utilisée pour résoudre des problèmes complexes de manière récursive. Cette stratégie consiste à diviser un problème en sous-problèmes plus petits, à résoudre chaque sous-problème indépendamment, puis à combiner les solutions pour obtenir la solution finale du problème d'origine.

Principe général

Le principe de base de la méthode diviser pour régner repose sur trois étapes principales :

1. Diviser : Séparer le problème en plusieurs sous-problèmes de taille plus petite. Ces sous-problèmes doivent avoir la même nature que le problème initial.
2. Régner : Résoudre les sous-problèmes, généralement de manière récursive. Lorsqu'ils deviennent suffisamment simples, ils sont résolus directement.
3. Combiner : Réunir les solutions des sous-problèmes pour former la solution du problème original.

Cette approche est particulièrement adaptée aux problèmes qui peuvent être naturellement divisés, et elle est souvent utilisée pour concevoir des algorithmes efficaces.

---

Exemple : Le tri fusion (Merge Sort)

Le tri fusion est un exemple classique d'algorithme basé sur la méthode "diviser pour régner". Il permet de trier efficacement une liste d'éléments en les divisant successivement en sous-listes, puis en les fusionnant pour obtenir une liste triée.

Fonctionnement du tri fusion

Le tri fusion suit exactement le schéma "diviser pour régner" :

1. Diviser : Si la liste contient plus d'un élément, elle est divisée en deux sous-listes de taille à peu près égale.
2. Régner : Chaque sous-liste est triée récursivement en appliquant le même algorithme (tri fusion).
3. Combiner : Les deux sous-listes triées sont fusionnées pour former une liste finale triée.

Exemple illustré

Prenons une liste d'exemple : [38, 27, 43, 3, 9, 82, 10].

1. Diviser : On divise la liste en deux sous-listes :

   • Gauche : [38, 27, 43]
   • Droite : [3, 9, 82, 10]

2. Régner : On applique le tri fusion récursivement sur chaque sous-liste :

   • Gauche : [38, 27, 43] devient :
     • Division : [38] et [27, 43]
     • Régner : [27, 43] devient [27] et [43], puis est fusionné en [27, 43]
     • Combiner : [38] et [27, 43] deviennent [27, 38, 43]
   • Droite : [3, 9, 82, 10] devient :
     • Division : [3, 9] et [82, 10]
     • Régner : [3, 9] devient [3] et [9], puis est fusionné en [3, 9]
     • Régner : [82, 10] devient [82] et [10], puis est fusionné en [10, 82]
     • Combiner : [3, 9] et [10, 82] deviennent [3, 9, 10, 82]

3. Combiner : Enfin, on fusionne les deux sous-listes triées :

   • [27, 38, 43] et [3, 9, 10, 82] sont fusionnées pour donner la liste triée finale : [3, 9, 10, 27, 38, 43, 82].

   ---

Implémentation en python

def tri_fusion(gauche:list, droite:list):
  tab_fusion = []
  l1, l2 = len(gauche), len(droite)
  i1, i2 = 0,0
  while i1 < l1 and i2 < l2:
    if gauche[i1] < droite[i2]:
      tab_fusion.append(gauche[i1])
      i1 += 1
    else:
      tab_fusion.append(droite[i2])
      i2 += 1
  return tab_fusion + gauche[i1:] + droite[i2:]

def fusion(tab:list):
  if len (tab) <=1:
    return tab
  m = len(tab) // 2
  return tri_fusion(fusion(tab[:m]), fusion (tab[m:]))

	•	tab_fusion est une liste vide où seront ajoutés les éléments fusionnés.
	•	l1 et l2 stockent les tailles respectives de gauche et droite.
	•	i1 et i2 sont des indices qui parcourent gauche et droite.
	2.	Boucle principale :
	•	Tant que l’on n’a pas parcouru complètement l’une des deux listes (gauche ou droite), on compare les éléments actuels de chaque liste (c’est-à-dire gauche[i1] et droite[i2]).
	•	Si l’élément de gauche est plus petit, on l’ajoute à tab_fusion, et on incrémente i1.
	•	Sinon, on ajoute l’élément de droite et on incrémente i2.
	3.	Retour des éléments restants :
	•	Une fois que l’une des deux listes est entièrement parcourue, on ajoute les éléments restants de l’autre liste à tab_fusion. C’est ce que fait gauche[i1:] pour la première liste, et droite[i2:] pour la deuxième.

Condition de base :
	•	Si le tableau contient un seul élément (ou aucun), il est déjà trié, donc on le retourne tel quel.
	2.	Diviser :
	•	On divise le tableau en deux sous-tableaux de taille approximativement égale à l’aide de m = len(tab) // 2.
	•	tab[:m] correspond à la première moitié du tableau et tab[m:] à la deuxième.
	3.	Récursion et fusion :
	•	On applique récursivement fusion() aux deux moitiés du tableau.
	•	Une fois que les deux sous-tableaux sont triés, on les combine en utilisant la fonction tri_fusion.

Complexité

L'algorithme de tri fusion a une complexité en temps de O(n log n), où n est le nombre d'éléments de la liste. Cette complexité s'explique par le fait que chaque division divise la liste en deux parties, et que la fusion de deux listes triées se fait en temps linéaire.

Avantages et inconvénients

Avantages :

• Efficacité : Le tri fusion est très performant, même sur de grandes listes, et il garantit toujours une complexité de O(n log n).
• Stable : Il conserve l'ordre relatif des éléments égaux dans la liste, ce qui est un atout dans certains contextes.

Inconvénients :

• Utilisation de mémoire : Le tri fusion nécessite de l'espace mémoire supplémentaire pour stocker les sous-listes, ce qui peut être un inconvénient dans des contextes où la mémoire est limitée.

La méthode diviser pour régner est une approche puissante et efficace pour résoudre des problèmes complexes, et le tri fusion en est un exemple emblématique. Comprendre cette méthode permet de mieux appréhender la récursivité et la manière dont des problèmes peuvent être résolus en plusieurs étapes.

---

Auteur : Florian Mathieu

Licence CC BY NC

Ce cours est mis à disposition selon les termes de la Licence Creative Commons Attribution - Pas d’Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International.