Fiche de révision : Diviser pour régner

Principes généraux

• La méthode « diviser pour régner » est une approche de résolution de problèmes qui consiste à décomposer un problème en sous-problèmes plus faciles à traiter.
• La méthode du tri-fusion, la méthode algoritmique et l’algoritme d’Euclide sont des exemples d’approche « diviser pour régner ».
• Dans le paradigme « diviser pour régner » les problèmes sont différents les uns des autres, ils ne se répètent pas (contrairement à ceux du paradigme de programmation dynamique).
• L’approche « diviser pour régner » comporte trois étapes :

• Les sous-problèmes peuvent eux-mêmes être décomposés en sous-problèmes selon une logique récursive.
• L’implémentation récursive est généralement privilégiée dans ce contexte (même s’il est également possible de réaliser des implémentations itératives).
• Étudions à présent deux applications :
• la recherche dichotomique ;
• puis le tri-fusion.

Recherche dichotomique

• La recherche dichotomique consiste à vérifier si un élément est présent dans un ensemble ordonné.
• On utilise cette méthode à chaque fois qu’on effectue une recherche dans un dictionnaire papier ou qu’on tente de deviner un nombre.
• Dans ce second exemple, on tend vers l’élément médian de l’ensemble considéré : si ce n’est pas l’élément recherché, on poursuit la recherche dans la première ou dans la seconde partie de l’ensemble.
• Cette méthode très simple est très efficace puisqu’on élimine à chaque fois la moitié de l’ensemble des possibles.
• La complexité de l’algorithme de recherche dichotomique est $O(log(n))$.
• L’ensemble des données doit être préalablement trié (conventionnellement par ordre croissant).
• La recherche dichotomique est généralement rattachée au paradigme « diviser pour régner », mais avec la particularité de ne pas résoudre tous les sous-problèmes.
• L’implémentation récursive présente deux cas de base possibles :
• la découverte du nombre cherché, qui peut survenir à tout moment ;
• une sous-liste devenue vide au terme des divisions successives.
• Nous créons la fonction correspondante : l’insertion de valeurs par défaut évitera d’avoir à spécifier manuellement les valeurs initiales de début et de fin de liste.
• Avec cette modification, l’appel de fonction s’effectue en spécifiant uniquement le nombre à trouver et la liste dans laquelle le chercher.
• On peut également implémenter une version itérative de la recherche dichotomique, avec une boucle while en remplacement des appels récursifs.
• On notera que l’élimination des sous-listes non pertinentes à chaque étape de la recherche dichotomique, nous a dispensé d’un traitement de recombinaison puisque nous aboutissons à un résultat unique.

Tri-fusion

• Le principe du tri-fusion consiste à trier une liste en la divisant récursivement en deux sous-listes qui sont ensuite triées puis fusionnées entre elles.
• Le tri-fusion :
• présente une complexité de $O(n log (n))$ ;
• fait partie des algorithmes de tri dont la complexité est constante dans tous les cas de figure.
• Nous souhaitons trier la liste [4, 2, 1, 3] de façon croissante en appliquant le tri-fusion appuyé sur la méthode « diviser pour régner ».
• Nous effectuons dans un premier temps des divisions successives :
• la liste [4, 2, 1, 3] est divisée en deux listes distinctes : [4, 2] et [1, 3] ;
• chacune des listes obtenues précédemment est encore divisée ;
• pour obtenir quatre listes distinctes : [4], [2], [1] et [3].
• Les sous-problèmes sont ensuite facilement résolus : en effet une liste comprenant un seul élément est nécessairement triée.
• Les listes individuelles sont fusionnées deux par deux, en ordonnant leurs contenus : [1, 2, 3, 4].
• La division en sous-listes s’effectue sur la même base que pour la recherche dichotomique, à ceci près que tous les sous-problèmes seront traités à l’issue des divisions.
• La partie « régner » (étape 2) correspond au cas de base des appels récursifs.
• Elle repose sur le fait qu’une liste composée d’un seul élément est nécessairement triée (valable aussi pour une liste vide).
• La recombinaison des solutions individuelles (fusion) rassemble les listes deux à deux pour chaque niveau de division.
• La fusion s’applique à deux listes triées, qui doivent être fusionnées de manière à former une liste unique triée.
• La fonction implémentée réalisant cette fusion utilisera des index pour repérer la progression dans le parcours séquentiel des listes. Commençons par implémenter une fonction réalisant cette fusion entre deux listes individuellement triées par ordre croissant :
• Les éléments courants de chaque liste sont comparés et seul le plus petit des deux est ajouté à la liste fusionnée.
• La première boucle while est exécutée tant qu’aucune liste n’a été parcourue en totalité.
• Les deux boucles suivantes ont pour objet l’ajout à la liste fusionnée des valeurs non encore utilisées de la seule des deux listes qui n’a pas été parcourue en totalité à ce stade.
• La fonction principale de tri-fusion effectuera des appels récursifs jusqu’à atteindre des listes contenant au plus un seul élément.
• Elle combinera ensuite les résultats issus des divisions récursives à l’aide de la fonction de fusion créée précédemment.