Diviser pour régner
Période historique : XXe siècle (Algorithmique moderne, von Neumann)
Le paradigme algorithmique brisant un problème en sous-problèmes indépendants faciles à vaincre.
Contenu & Formulation mathématique
Genèse & Portée historique
Stratégie algorithmique majeure divisant récursivement un problème de taille n en plusieurs sous-problèmes indépendants de même nature mais de taille réduite, les résolvant récursivement jusqu'à un cas de base trivial, puis recombinant efficacement leurs solutions partielles (ex: tri fusion, transformée de Fourier rapide).
Si le principe informel remonte à l'Antiquité, John von Neumann formalisa son application aux ordinateurs électroniques en 1945 avec le tri fusion (Merge Sort) pour l'EDVAC, ramenant la complexité du tri à O(n log n).
Filiations & Relations conceptuelles (1)
Objet de collection MathTCG
Diviser pour régner
Principe : Décomposition récursive en sous-problèmes disjoints, résolution indépendante et combinaison finale (Divide, Conquer, Combine).
Dans l'édition physique et numérique de MathTCG, cette carte appartient à l'extension Foundations.