Physique-Chimie & NSI

Cours complets et originaux de Physique-Chimie & NSI

2-02. Diviser pour régner

La méthode « diviser pour régner » est une méthode algorithmique qui consiste à décomposer un problème en sous-problèmes plus faciles à résoudre, puis à combiner leurs solutions afin de construire une solution au problème de départ.

Principe de la méthode

La méthode algorithmique « diviser pour régner » (Divide and Conquer) est une approche fondamentale en informatique qui consiste à :

  1. Diviser : décomposer un problème complexe en sous-problèmes plus petits et plus simples
  2. Régner : résoudre ces sous-problèmes de façon récursive
  3. Combiner : assembler les solutions des sous-problèmes pour obtenir la solution du problème initial

Pour que cette méthode algorithmique soit applicable, il faut donc que le problème soit de nature à être divisé en sous-problèmes. Il s’agit donc d’identifier une propriété commune à tous les sous-problèmes, comme on l’a déjà fait avec la récursivité. Les algorithmes « diviser pour régner » se prêtent donc naturellement à une écriture récursive.

Efficacité

La méthode « diviser pour régner » est efficace quand :

  • les sous-problèmes sont sensiblement de même taille.
  • les sous-problèmes sont indépendants (contre-exemple : la suite de Fibonacci qui recalcule plusieurs fois la même chose).

Exemples d’applications
    Écrire un algorithme utilisant la méthode « diviser pour régner ».

Tri-fusion

Le tri fusion (merge sort) est un algorithme emblématique de l'approche « diviser pour régner » qui fonctionne en divisant récursivement le tableau à trier en deux moitiés, triant séparément chaque moitié, puis fusionnant ces sous-tableaux triés pour obtenir le résultat final. Sa force réside dans sa garantie d'une complexité O(n log n) dans tous les cas, le rendant particulièrement efficace pour trier de grandes quantités de données.

déroulement schématique du tri fusion
Étapes du tri-fusion d’un tableau

		Fonction TriFusion(tableau)
			// Cas de base : un tableau de taille 0 ou 1 est déjà trié
			Si longueur(tableau) <= 1 Alors
			|	Retourner tableau
			
			// Diviser
			gauche ← TriFusion(moitié gauche)
			droite ← TriFusion(moitié droite)
			
			// Combiner (fusionner)
			Retourner Fusion(gauche, droite)

		Fonction Fusion(tableauGauche, tableauDroite)
			résultat ← tableau vide
			i ← 0
			j ← 0
			
			// Tant qu'il reste des éléments dans les deux sous-tableaux
			Tant que i < longueur(tableauGauche) ET j < longueur(tableauDroite):
			|	Si tableauGauche[i] ≤ tableauDroite[j]:
			|	|	Ajouter tableauGauche[i] à résultat
			|	|	i ← i + 1
			|	Sinon
			|	|	Ajouter tableauDroite[j] à résultat
			|	|	j ← j + 1
			
			// Ajouter les éléments restants, s'il y en a
			Tant que i < longueur(tableauGauche):
			|	Ajouter tableauGauche[i] à résultat
			|	i ← i + 1
			
			Tant que j < longueur(tableauDroite) Faire
			|	Ajouter tableauDroite[j] à résultat
			|	j ← j + 1
			
			Retourner résultat

Tri fusion

1. Appliquez l’algorithme de tri-fusion au tableau [10, 9, 8, 7, 6, 5, 4, 3, 2, 1] en illustrant son déroulement grâce à un schéma identique à celui du cours.

2. Complétez l’implémentation ci-dessous du tri-fusion.


			def tri_fusion(tableau):
				# Cas de base
				if len(tableau) <= 1:
					return tableau
				
				# Division
				milieu = ...
				gauche = tri_fusion(tableau[...])
				droite = tri_fusion(tableau[...])
				
				# Combinaison (fusion)
				return fusion(gauche, droite)

			def fusion(gauche, droite):
				resultat = []
				i, j = 0, 0
				
				while i < len(gauche) and j < len(droite):
					if ... < ...:
						resultat.append(gauche[i])
						i += 1
					else:
						resultat.append(...)
						j += 1
				
				# Ajouter les éléments restants
				resultat.extend(gauche[i:])
				resultat.extend(...)
				return resultat

Recherche dichotomique

La recherche dichotomique est une méthode d'approche "diviser pour régner" qui permet de localiser rapidement un élément dans un ensemble ordonné en divisant systématiquement l'espace de recherche par deux à chaque étape. Ce procédé, qui garantit une complexité logarithmique en O(log n), exploite la structure ordonnée des données pour éliminer la moitié des éléments restants à chaque comparaison.

déroulement d’une recherche dichomotique
Étapes d’une recherche dichotomique dans un tableau

		Fonction RechercherDichotomie(tableau, valeur, debut, fin)
			// Cas de base : élément non trouvé
			Si debut > fin: 
			|	Retourner -1
			
			// Diviser : trouver l'élément au milieu
			milieu ← (debut + fin) / 2
			
			// Régner : décider quelle moitié explorer
			Si tableau[milieu] = valeur:
			|	Retourner milieu
			Sinon Si tableau[milieu] > valeur:
			|	// Chercher dans la moitié gauche
			|	Retourner RechercherDichotomie(tableau, valeur, debut, milieu - 1)
			Sinon
			|	// Chercher dans la moitié droite
			|	Retourner RechercherDichotomie(tableau, valeur, milieu + 1, fin)

		// Appel initial de la fonction
		RechercherDichotomie(tableau, valeur, 0, longueur(tableau) - 1)

Recherche dichotomique

1. Compléter la fonction ci-dessous de recherche dichotomique


			def recherche_dichotomique(tableau, element, debut=0, fin=None):
				if fin is None:
					fin = len(tableau) - 1
				
				# Cas de base : élément non trouvé
				if debut > fin:
					return -1
				
				# Division
				milieu = (debut + fin) // 2
				
				# Comparaison et récursion
				if tableau[milieu] == element:
					return milieu
				elif tableau[milieu] > element:
					return recherche_dichotomique(tableau, element, ..., ...)
				else:
					return recherche_dichotomique(tableau, element, ..., ...)

2. Tester votre code sur les tableaux suivants :


			tableau = [1, 2, 4, 4, 5, 7, 7, 7, 8, 9]
			recherche_dichotomique(tableau, 2)
			recherche_dichotomique(tableau, 7)
			recherche_dichotomique(tableau, 6)