Diviser pour régner

Diviser pour régner

Lorsque vous avez appris à effectuer une addition posée, vous avez appliqué un algorithme découpant les nombres en chiffres sur lesquels l'opération d'addition devenait élémentaire, puisqu'elle consistait à additionner deux chiffres; la propagation de la retenue éventuelle combinant alors les additions des sous-instances pour obtenir le résultat. Cet algorithme entre dans la catégorie des algorithmes de type diviser pour régner.

Ce principe algorithmique dit diviser pour régner consiste à :

  • diviser l'instance d'un problème en sous-instances,
  • traiter indépendamment ces sous-instances,
  • combiner les différents résultats obtenus pour construire une solution au problème initial.

Un exemple classique de problème étudié dès le lycée et dont la résolution s'appuie sur ce principe algorithmique est la recherche dichotomique.

En effet, la partition divise la zone de recherche en deux parts de tailles égales et on se concentre uniquement sur la bonne moitié en reproduisant ce mécanisme sur une nouvelle moitié et ainsi de suite de manière à ramener la zone de recherche à une unité.
Notons que dans ce cas, la résolution d'un des deux sous-problèmes se résume à ne rien faire.

Les algorithmes qui s'appuient sur ce principe sont souvent récursifs et opèrent sur des instances de plus en plus petites jusqu'à ce que la taille de l'instance à traiter rende la résolution du problème simple voire triviale.

Bien que ce ne soit pas une obligation ,beaucoup d'algorithmes reposant sur ce principe sont récursifs, en effet si les sous-problèmes ne sont qu'une "réduction" du problème initial, il est tentant de leur appliquer à nouveau le principe et ainsi de suite.


Diviser et régner: cours, exercices et TP (pdf)


Programmation dynamique

Le paradigme diviser pour régner, et plus généralement la récursivité peuvent poser des problèmes de redondance dans l'appel des fonctions.

La programmation dynamique en sauvegardant dans une mémoire cache les résultats déjà obtenus évite de refaire ces calculs connus dans les instances des sous-problèmes.

On utilise -bien sûr par abus de langage- ce terme de mémoire cache car en informatique, un cache est une couche de stockage de données grande vitesse qui stocke des informations, de sorte que les utilisations futures soient plus rapides. C'est bien le but de la variable de type tableau ou liste qui sera utilisée pour stocker les résultats et éviter les appels récursifs redondants.


Le cours: Programmation dynamique.