Diviser pour régner

Notification de cookies

Nous utilisons des cookies pour améliorer votre expérience. En poursuivant votre navigation sur ce site, vous acceptez l'utilisation de cookies. Plus d'informations

Introduction à l'approche diviser pour régner

Dans l'approche diviser pour régner, le problème en question est divisé en sous-problèmes plus petits, puis chaque problème est résolu indépendamment. Si nous continuons à diviser les sous-problèmes en sous-problèmes encore plus petits, nous pouvons éventuellement atteindre un stade où plus aucune division n'est possible. Les "sous-problèmes" les plus petits "atomiques" possibles sont résolus. La solution de tous les sous-problèmes est finalement fusionnée afin d'obtenir la solution d'un problème original.

Un algorithme typique de Divide and Conquer résout un problème en utilisant les trois étapes suivantes :

Diviser

Cette étape implique la décomposition du problème en sous-problèmes plus petits. Les sous-problèmes devraient représenter une partie du problème initial. Cette étape adopte généralement une approche récursive pour diviser le problème jusqu'à ce qu'aucun sous-problème ne soit divisible. À ce stade, les sous-problèmes deviennent de nature atomique mais représentent toujours une partie du problème actuel.

Régner/Résoudre

Cette étape reçoit beaucoup de problèmes secondaires plus petits à résoudre. Généralement, à ce niveau, les problèmes sont résoulées à l'aide de cas de base de l'algorithme récursive.

Combiner

Lorsque les plus petits problèmes sont résolus, cette étape les combine de manière récursive jusqu'à ce qu'ils formulent une solution au problème initial.
Cette approche algorithmique fonctionne de façon récursive et les étapes de conquête et de fusion fonctionnent si près qu'ils apparaissent comme un seul.

cette approche suit l'algorithme ci-dessous

    Fonction DiviserRegner(problème P)
        SI (problème plus petit) ALORS
            Résoudre(P)
        SINON
            Diviser P en P1,P2,P3,..., Pk
            Appliquer DiviserRegner(P1),DiviserRegner(P2),DiviserRegner(P3),...,DiviserRegner(Pk)
            Combiner(DiviserRegner(P1),DiviserRegner(P2),DiviserRegner(P3),...,DiviserRegner(Pk))
        FINSI
    FINFonction
Applications

Voici quelques algorithmes standard basés sur une approche de programmation diviser pour régner

  1. La recherche binaire. À chaque étape, l'algorithme compare l'élément d'entrée x à la valeur de l'élément intermédiaire du tableau. Si les valeurs correspondent, retourne l'index du milieu. Sinon, si x est inférieur à l'élément du milieu, l'algorithme est récurrent pour le côté gauche de l'élément du milieu, sinon, pour le côté droit de l'élément du milieu.
  2. Tri rapide. L'algorithme sélectionne un élément de pivot, réorganise les éléments du tableau de manière à ce que tous les éléments plus petits que l'élément de pivot se déplacent vers le côté gauche du pivot et que tous les éléments plus grands se déplacent vers le côté droit. Enfin, l'algorithme tri de manière récursive les sous-tableau gauche et droit.
  3. Le tri par fusion. L'algorithme divise le tableau en deux moitiés, les trie de façon récursive et fusionne finalement les deux moitiés triées
  4. Paire de points la plus proche Le problème est de trouver la paire de points la plus proche dans un ensemble de points dans le plan x-y. Le problème peut être résolu en un temps O(n2) en calculant les distances de chaque paire de points et en comparant les distances pour trouver le minimum. L'algorithme Diviser pour régner résout le problème en temps O(nLogn).
  5. L’algorithme de Strassen est un algorithme efficace pour multiplier deux matrices. Une méthode simple pour multiplier deux matrices nécessite 3 boucles imbriquées en temps O (n3). L’algorithme de Strassen multiplie deux matrices en temps O(n2,8974).
  6. L'algorithme Cooley–Tukey de transformation de Fourier rapide (FFT) est l'algorithme le plus courant pour la FFT. C'est un algorithme qui fonctionne en temps O(nlogn).
  7. Algorithme de Karatsuba pour une multiplication rapide

Partager ce cours avec tes amis :

Rédigé par M. ESSADDOUKI

Learning a new programming language is an easy thing, but the most difficult thing is how to design efficient algorithms for real-world problems, so don't be a programmer, be a problems solver.

Cours Similaires :