La méthode « diviser pour régner »

Présentation de la méthode algorithmique « diviser pour régner », une méthode générale de résolution de problèmes particulièrement adaptée aux programmes informatiques. Explications avec Olivier, professeur de numérique et sciences informatiques.

Téléchargez le support de cours en PDF.

Objectifs du cours

Présentation d'une méthode générale de résolution de problèmes particulièrement adaptée à une utilisation informatique par le biais de fonctions récursives. Elle consiste à diviser un problème en problèmes du même type mais de plus petite taille. Comment décomposer le problème en problèmes plus petits ? Comment obtenir une solution du problème initial à partir des solutions des petits problèmes ? Illustration de cette méthode avec deux exemples : les tours de Hanoï, un casse-tête adapté à une résolution récursive, et le tri-fusion qui est un exemple d’algorithme de tri efficace.

Le plan du cours

I. Présentation de la méthode

► Situation

• On veut résoudre un type de problème pour une taille n ;
• On peut le faire en se basant sur la résolution du même problème pour de plus petits tailles.

► Résolution en 3 étapes

1. Diviser pour faire apparaître les sous-problèmes à résoudre ;
2. Régner pour résoudre effectivement les sous-problèmes ;
3. Combiner pour obtenir une solution du problème initial.

II. Les tours de Hanoï

C'est un plateau en bois constituté de 3 tiges. Sur la première tige, on retrouve un ensemble de disques de plus en plus grand. Le but est de transférer les disques sur la dernière tige.

► Règles :

• On ne peut déplacer qu’un disque à la fois ;
• On ne peut poser un disque que sur un disque plus grand ou une tige vide.

► Questions

1. Diviser : Quels problèmes « plus petits » considérer ?
2. Cas de base : Comment résoudre les problèmes les plus petits ?
3. Combiner : À partir d’une solution du problème plus petit, comment obtenir une solution du problème plus grand ?

III. Le tri-fusion

Nous allons appliquer la méthode « diviser pour régner » à l’élaboration d’un algorithme de tri.

La fusion de deux tableaux de longueurs n₁ et n₂ est en n₁ + n₂.

Il y a de l’ordre de log₂ n étapes de division/combinaison.
Chaque étape a un coût de l’ordre de n.
Le tri-fusion est en n log₂ n.