Skip to Main content Skip to Navigation
Journal articles

Modèles et calculs combinatoires

Résumé : De combien de façons peuvent être distribuées les 32 cartes d’un jeu de belote ? De combien de façons pouvons-nous obtenir 13 en sommant les résultats de 3 dés ? De combien de façons peut être mélangé un paquet de n cartes ? L’ambition de la combinatoire énumérative est de compter le nombre (fini) de combinaisons dans ce type de situation. La motivation pour envisager tous les cas possibles n’est pas toujours ludique. De combien de façons peut s’exécuter ce programme ? Combien de temps prend en moyenne cet algorithme de tri ? La probabilité d’un événement se définit souvent comme le ratio entre le nombre de cas où il se produit et le nombre de cas possibles. Compter nécessite aussi souvent d’avoir trouvé une structure sur toutes les combinaisons possibles. C’est souvent un premier pas vers la recherche (efficace) d’une combinaison optimale pour le critère que nous nous donnerons. Cette structure et ce comptage permettent aussi parfois de générer aléatoirement une, ou quelques, combinaison(s) typique(s) et ainsi de calibrer certaines choses. Un exemple de calibrage : observer une centaine d’individus pris au hasard dans une population humaine incite à fixer la hauteur des portes à environ 2,05 m, pour peu qu’on évite les rassemblements de basketteurs professionnels ou bien de gymnastes olympiques. En physique statistique, les combinaisons apparaissent fréquemment comme les états accessibles d’un système composé de nombreux éléments, par exemple le positionnement des particules d’un gaz. Ce nombre d’états est souvent lié à la notion d’entropie. Compter est donc souvent pertinent dans l’analyse d’un problème mais peut être extrêmement difficile. Si difficile par exemple que ce type de problème a été envisagé en 2010 par les chercheurs Scott Aaronson et Alex Arkhipov pour mettre en évidence la supériorité de l’éventuel ordinateur quantique sur l’ordinateur classique. Ce texte propose une promenade dans des exemples d’énumérations combinatoires. Ces exemples illustrent en quoi cette discipline réalise parfois un équilibre entre un modèle le plus pertinent possible et les possibilités d’y faire une analyse par un calcul faisable voire efficace. En effet, un modèle est une description approximative d’un objet d’étude, qui est à la fois fidèle à cet objet par certains aspects et mathématiquement confortable pour l’analyse, le calcul. Dans cette communauté, un résultat est donc souvent un modèle combinatoire, en général discret et non continu, permettant un calcul combinatoire, parfois qualifié de « beau » lorsque nous laissons s’épancher un excès de sentimentalisme.
Mots-clés : Enumerations Modelisation
Document type :
Journal articles
Complete list of metadata

https://hal.inria.fr/hal-02929164
Contributor : Inria Interstices <>
Submitted on : Monday, December 7, 2020 - 10:21:56 AM
Last modification on : Monday, December 7, 2020 - 10:39:19 AM
Long-term archiving on: : Monday, March 8, 2021 - 6:27:37 PM

File

le_borgne_modeles_et_calculs_c...
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02929164, version 1

Collections

Citation

Yvan Le Borgne. Modèles et calculs combinatoires. Interstices, INRIA, 2020. ⟨hal-02929164⟩

Share

Metrics

Record views

70

Files downloads

34