Terminale · Numérique et sciences informatiques

Découvrir diviser pour régner : découper, résoudre, recombiner

Reconnaître le schéma diviser pour régner sur la recherche dichotomique et le tri fusion, en identifier les trois temps (diviser, résoudre, combiner) et justifier la terminaison par la décroissance de la taille des sous-problèmes.

Aperçu gratuit
Illustration de la fiche « Découvrir diviser pour régner : découper, résoudre, recombiner »

Les points essentiels

  • Diviser pour régner résout un problème en le découpant en sous-problèmes du même type mais de taille strictement plus petite, résolus récursivement, puis en combinant leurs résultats.
  • Trois temps à identifier systématiquement : diviser (découper l'entrée), régner (appeler récursivement sur chaque morceau), combiner (assembler les résultats partiels en résultat global).

Les mots à connaître

Diviser pour régner
Paradigme algorithmique où l'on résout un problème de taille n en le décomposant en sous-problèmes de même nature et de taille plus petite, résolus récursivement, dont on combine les solutions.
Cas de base
Situation suffisamment simple pour être résolue directement, sans appel récursif (par exemple une liste de longueur 0 ou 1 pour un tri). Il arrête la récursion.

Un exemple pour comprendre

Recherche dichotomique : on cherche 23 dans la liste triée L = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] (indices 0 à 9). Détaille les étapes et dis quels temps de diviser pour régner on reconnaît.

On prend les bornes g = 0, d = 9. Étape 1 : m = (0+9)//2 = 4, L[4] = 16 < 23, donc on garde la moitié droite : g = 5. Étape 2 : m = (5+9)//2 = 7, L[7] = 56 > 23, donc on garde la moitié gauche : d = 6. Étape 3 : m = (5+6)//2 = 5, L[5] = 23 : trouvé à l'indice 5. Seulement 3 comparaisons pour 10 éléments. Diviser : on coupe l'intervalle au milieu. Régner : on poursuit sur une seule moitié. Combiner : rien à faire, on renvoie directement le résultat. Terminaison : la largeur d - g + 1 passe de 10 à 5 puis 2 puis 1 ; elle diminue strictement à chaque étape, donc la recherche s'arrête. Si l'élément était absent, on finirait avec un intervalle vide (g > d), cas de base qui renvoie « non trouvé ».

Première page de l’Essentiel : Découvrir diviser pour régner : découper, résoudre, recombiner
Ketty