Explosion combinatoire
- Explosion combinatoire
-
On nomme explosion combinatoire en recherche opérationnelle, et en particulier dans le domaine de la programmation dynamique, le fait qu'un petit changement du nombre de données à considérer dans un problème par ailleurs trivial peut suffire à rendre sa solution très difficile, voire impossible dans certains cas avec les ordinateurs actuels.
Un exemple parlant d'explosion combinatoire est celui de la fonction d'Ackermann.
L'explosion combinatoire peut être jugulée efficacement dans quelques cas par des limitations de bon sens dans les valeurs (relatives ou absolues) des variables à considérer, ou par des considérations plus générales sur les fonctions en question (la programmation dynamique met à profit par exemple le cas où les fonctions sont de type monotones croissantes).
Un procédé utilisé conjointement consiste, dans le cas où des calculs identiques et longs risquent d'être répétés souvent, de mettre en mémoire leurs résultats pour éviter ces recalculs.
Voir aussi
Wikimedia Foundation.
2010.
Contenu soumis à la licence CC-BY-SA. Source : Article Explosion combinatoire de Wikipédia en français (auteurs)
Regardez d'autres dictionnaires:
Explosion Combinatoire — Pour les articles homonymes, voir combinatoire (homonymie). On nomme explosion combinatoire en recherche opérationnelle, et en particulier dans le domaine de la programmation dynamique, le fait qu un petit changement du nombre de données à… … Wikipédia en Français
Explosion (Homonymie) — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Une Explosion est une transformation chimique ou physique rapide qui induit des mouvements de gaz. Mais aussi, par analogie : En biologie, les… … Wikipédia en Français
Combinatoire (homonymie) — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Sur les autres projets Wikimedia : « Combinatoire (homonymie) », sur le Wiktionnaire (dictionnaire universel) En mathématiques, la… … Wikipédia en Français
Explosion (homonymie) — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Une Explosion est une transformation chimique ou physique rapide qui induit des mouvements de gaz. Mais aussi, par analogie : En biologie, les… … Wikipédia en Français
Explosion exponentielle — Croissance exponentielle Article d une série sur la constante mathématique e … Wikipédia en Français
Calculateur quantique — La Sphère de Bloch est une représentation d’un qubit Un calculateur quantique ou ordinateur[1] quantique, repose sur des propriétés quantiques de la matière : superposition et intrication d éta … Wikipédia en Français
Calcul quantique — Calculateur quantique Cet article fait partie de la série Mécanique quantique Postulats de la mécanique quantique Histoire de … Wikipédia en Français
Ordinateur quantique — Calculateur quantique Cet article fait partie de la série Mécanique quantique Postulats de la mécanique quantique Histoire de … Wikipédia en Français
Recherche opérationnelle — La recherche opérationnelle (aussi appelée aide à la décision) peut être définie comme l ensemble des méthodes et techniques rationnelles orientées vers la recherche de la meilleure façon d opérer des choix en vue d aboutir au résultat visé ou au … Wikipédia en Français
Axiomes De Plans Projectifs/Suite Des Axiomes — Article principal : Axiomes de plans projectifs. La géométrie projective a permis de s abstraire des impressions intuitives de la géométrie plane euclidienne. La géométrie projective ne travaille que sur les alignements et les intersections … Wikipédia en Français
Pour les articles homonymes, voir combinatoire (homonymie).
