Vidéo : La méthode « diviser pour régner »

vidéo suivante

Contenu proposé par

France Télévisions
Emissions Lumni29:11

La méthode « diviser pour régner »

Les cours Lumni - Lycée

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 ?

Image contenu

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 n1 et n2 est en n1 + n2.

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

Image contenu

Réalisateur : Didier Fraisse

Producteur : France tv studio

Année de copyright : 2020

Année de production : 2020

Année de diffusion : 2020

Publié le 19/11/20

Modifié le 20/11/20

arrow
voir plus

Ce contenu est proposé par