Diviser pour régner

Sommaire du document

Du latin divide ut imperes (ou ses variantes divide et impera, divide ut reges), le principe divise pour commander (ou divise pour régner) est attribué au Sénat romain, et relève de la stratégie militaire suivante : semer la discorde parmi ses opposants permet de les contrôler, les manipuler et les soumettre plus aisément. Cette machiavélique[1] expression était inculquée aux enfants destinnés à prendre les rênes du pouvoir.

La division de l'opposant réduit ses forces, diminue sa confiance en l'opposition du fait du manque d'unité, et le déstabilise par des conflits internes.

Si en politique l'utilisation récurente de cette tactique peut avoir pour conséquence la révélation de la stratégie répétitive auprès des opposants, il n'en est pas de même en informatique, et nous pouvons continuer à affaiblir la difficulté d'une opération en la divisant.

Cette stratégie est fortement employée dans les alorithmes récursifs et sera généralement de type dichotomique (division en deux éléments, mais dont la taille n'est pas forcément égale).

 

Exemple de diviser pour régner

Si nous devons chercher une définition dans un dictionnaire, nous pouvons parcourir les pages depuis la première jusqu'au moment où nous trouvons la définition. Espérons que l'on ne doive pas trop souvent chercher la définition des zygomatiques.

Intuitivement, lorsque nous cherchons une définition, nous ouvrons le dictionnaire à un endroit où il y a une forte probabilité que les mots définis ne soient pas trop éloignés du mot que nous cherchons, nous comparons les mots de la page ouverte avec celui cheché, et puis nous sautons encore quelques pages en avant ou en arrière jusqu'à trouver la bonne page.

 

Principe de diviser pour régner

Nous allons à chaque fois diviser la quantité de données à traiter, jusqu'au moment où nous atteindrons le cas de base. A chaque fois nous devons respecter le fait que la division mène à un cas plus simple : nous dirons qu'il s'agit d'une relation bien fondée.

Nous atteignons le cas de base (minimal) de cette relation bien fondée "<" quand il n'est plus possible de diviser, ce qui peut s'écrire a minimal ⇔ Il n'existe pas deb : b < a

Ensuite, nous devrons combiner tous les éléments.

Nous pouvons employer des boucles pour implémenter ce genre de concept, mais la récursion est vraiment indiquée car nous effectuons la division lors de "la descente" dans la pile des appels récursifs, et nous effectuons la combinaison lors de" la remontée" de la pile.

L'algorithme résoudre(v) de type diviser pour régner peut donc se résumer de la manière suivante :

  • v est un cas de base ?
    • si oui : résoudre_directement(v)
    • si non :
      • Phase de décomposition : (v1, v2, ..., vn) := diviser(v) pour lequel v1, v2, etc. sont des sous ensembles de v obtenus après division.
      • Phase de récurtion : pour chaque i : ri = résoudre(vi) appel à la récursion pour encore diviser notre sous ensemble
      • Phase de recomposition : r = combiner(r1, r2, ..., rn)

 

Trier en appliquant diviser pour régner

Nous pouvons appliquer le principe "diviser pour régner" aux différents algorithmes de tri, en remplaçant résoudre(v) par trier(liste_in). Pour nos exemples, nous allons définir certaines conditions:

liste_in : Liste<T>
liste_out : Liste<T>
Post-condition : liste_out est triée[2], liste_in est une permutation[3] de liste_out, et l'ordre de tri est réflexif.

  • Le tri par sélection :
    • Info : comme l'algorithme est récursif et retourne à chaque fois une nouvelle liste, listei correspond à la liste utilisée au moment i.
    • combiner = cons(v, listei) {v est l'élément à mettre en tête si il possède la plus petite valeur des éléments de la liste triée}
    • Cas de base : listei = null
    • "diviser" correspond ici à la recherche de la plus petite valeur, en Ordre de grandeur(n)
    • Nous pouvons en déduire que le temps total (diviser + résoudre + combiner) sera de l'ordre de Ordre de grandeur(n2), car il est fait n fois appel à "diviser".
  • Le tri par insertion :
    • diviser(listei) = {head(listei), tail(listei)}
    • Cas de base : listei = null
    • "combiner" correspond ici à l'insertion d'un élément dans une liste triée, et le temps est proportionnel à la taille de la liste Ordre de grandeur(n)[4]
    • Le temps total sera de l'ordre de Ordre de grandeur(n2)
    • Nous ne constatons donc aucune différence en ordre de grandeur avec le tri par sélection
  • Le tri par fusion :
    • Le tri par fusion est par définition un cas typique de diviser pour régner.
    • diviser(listei) = listei1, listei2 tel que listei1 + listei2 = listei et |listei1| = |listei1| ± 1 en Ordre de grandeur(log n)
    • Cas de base : |listei| = 1
    • "combiner" correspond ici à la fusion de deux listes triées en Ordre de grandeur(n)
    • Le temps total sera de l'ordre de Ordre de grandeur(n log n)
    • Le tri par fusion est donc nettement plus efficace en ordre de grandeur que le tri par sélection ou le tri par insertion.

 

Réseaux sociaux

Vous pouvez modifier vos préférences dans votre profil pour ne plus afficher les interactions avec les réseaux sociaux sur ces pages.

 

Nuage de mots clés

19 mots clés dont 0 définis manuellement (plus d'information...).

Avertissement

Cette page ne possède pas encore de mots clés manuels, ceci est donc un exemple automatique (les niveaux de pertinence sont fictifs, mais les liens sont valables). Pour tester le nuage avec une page qui contient des mots définis manuellement, vous pouvez cliquer ici.

Vous pouvez modifier vos préférences dans votre profil pour ne plus afficher le nuage de mots clés.

 

Notes

  1.  Machiavel : Machiavel use de cette stratégie dans son ouvrage "Le Prince" (ISBN : 2-7427-3241-1)

  2.  Trié vs strictement trié : Une liste(simplement) triée peut contenir des doublons alors qu'une liste strictement triée ne peut en contenir (car une valeur ne peut être plus petite ou plus grande qu'elle-même

  3.  Permutation vs contient : Si liste_out une permutation de liste_in, tous les éléments de liste_in seront présents dans liste_out
    alors que si nous déclarons que liste_out contient toutes les valeurs de liste_in, les doublons contenus dans liste_in ne seront présents qu'une seule fois dans liste_out

  4.  Combiner : L'ordre de grandeur du temps de combiner dépend de l'implémentation utilisée pour notre liste. Dans le cas par exemple d'un arbre Rouge/Noir "combiner" sera de Ordre de grandeurlogn)

 

Références

  1. livre Langue du document: fr IHDCB331 - Méthodes de Programmation : PY Schobbens, Cours de Méthodes de Programmation (Septembre 2009)
  2. Consulter le document html Langue du document: fr Diviser pour régner : Wikipedia (version 15/10/09)
  3. livre Langue du document: uk Introduction to Algorithms : Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest (1999)

Ces références et liens indiquent des documents consultés lors de la rédaction de cette page, ou qui peuvent apporter un complément d'information, mais les auteurs de ces sources ne peuvent être tenus responsables du contenu de cette page.
L'auteur de ce site est seul responsable de la manière dont sont présentés ici les différents concepts, et des libertés qui sont prises avec les ouvrages de référence. N'oubliez pas que vous devez croiser les informations de sources multiples afin de diminuer les risques d'erreurs.

 

Astuce pour imprimer les couleurs des cellules de tableaux : http://www.gaudry.be/ast-rf-450.html
Aucun commentaire pour cette page

© Ce document issu de l′infobrol est enregistré sous le certificat Cyber PrInterDeposit Digital Numbertection. Enregistrement IDDN n° 5329-11347
Document créé le 16/10/09 04:42, dernière modification le Mercredi 28 Juin 2017, 15:26
Source du document imprimé : http:///www.gaudry.be/programmer-divide-ut-imperes.html
St.Gaudry©07.01.02
Outils (masquer)
||
Recherche (afficher)
Recherche :

Utilisateur (masquer)
Apparence (afficher)
Stats (afficher)
15838 documents
455 astuces.
550 niouzes.
3107 definitions.
447 membres.
8121 messages.

Document genere en :
0,09 seconde

Mises à jour :
Mises à jour du site
Citation (masquer)
Realizing ones own weaknesses is the greatest strength one could have.

Venkat Subramaniam
 
l'infobrol
Nous sommes le Mardi 26 Septembre 2017, 22:04, toutes les heures sont au format GMT+1.00 Heure, heure d'été (+1)