Diviser pour régner
Dans quel cas ?
- On parvient à découper un problème en sous-problèmes indépendants les uns des autres. On poursuit cette démarche jusqu’à aboutir à une situation simple : cas de base.
- La solution du cas de base est généralement simple à obtenir et permet la construction de la solution du problème.
Remarque
C’est l’indépendance des sous-problèmes qui permet la construction de la solution globale directe par recombinaison des solutions intermédiaires.
Exemples
- Exponentiation rapide
- Recherche dichotomique dans un tableau trié, dans une liste triée
- Tri rapide d’un tableau
- Tri fusion récursif d’un tableau
- etc.
Schéma de résolution
À retenir
- Diviser
- On décompose le problème initial en un ou plusieurs sous-problèmes de plus petites tailles.
- Régner
- Chaque sous-problème est résolu
- Combiner
- Les solutions des sous-problèmes sont combinées pour construire la solution du problème initial.
Remarques
- Cette procédure se prête naturellement à un traitement récursif des problèmes mais une approche itérative reste possible.
- Cette procédure assure que l’algorithme est correct. Il reste à valider sa terminaison (que le cas de base est toujours atteint ).
Exercice : exponentiation rapide
L’algorithme suivant permet de calculer :
- Programmer la fonction
puissance1dont la spécification est :
Penser à écrire quelques tests.
- Quelle est la complexité de cet algorithme ?
L’algorithme suivant permet aussi de calculer :
- Programmer la fonction
puissance2dont la spécification est :
Penser à écrire quelques tests.
-
Justifier que le seconde algorithme met en œuvre le raisonnement « Diviser pour règner ».
-
Pourquoi appelle-t-on l’algorithme 2, l’exponentiation rapide ?
Conclusion
À retenir
- La méthode « Diviser pour régner » est le paradigme naturel de la récursivité.
- La complexité d’un algorithme qui s’appuit sur le paradigme « Diviser pour régner » est parfois optimale (exponentiation rapide, recherche dichotomique, tri fusion, etc.) mais pas toujours (recherche du minimum et du maximum dans une liste, somme des éléments d’une liste, recherche dans une liste non triée, etc.).
- L’efficacité d’un algorithme qui s’appuit sur le paradigme « Diviser pour régner » dépend de l’implémentation de la récursivité par le langage choisi.
Exercice : recherche dichotomique
- Écrire le code de la fonction
recherche1dont la spécification est la suivante :
-
Tester la fonction
recherche1. -
Écrire le code de la fonction
recherche2dont la spécification est la suivante :
- Tester la fonction
recherche2.