Explosion combinatoire

Explosion combinatoire
Page d'aide sur l'homonymie 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 à 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

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”