partitionnement

Partitionnement désigne, en mathématiques et en sciences de l’information, l’action de diviser un ensemble ou un espace en sous-ensembles non vides, appelés blocs ou parties, qui sont mutuellement disjoints et dont l’union recouvre l’ensemble initial. Une partition P d’un ensemble S est donc une famille de sous-ensembles non vides dont les blocs sont pairwise disjoints et dont la réunion est S. Deux éléments appartiennent au même bloc si et seulement si ils appartiennent à une même partie de P; cette relation d’appartenance rétablit une relation d’équivalence sur S. Réciproquement, toute relation d’équivalence sur S décompose S en classes d’équivalence, qui forment une partition.

Une partition peut être comparée à une autre selon le critère de refinement: P est plus fine que Q si chaque bloc de P est inclus dans un bloc de Q. L’ensemble des partitions d’un même ensemble S forme alors un treillis partiellement ordonné par refinement, et peut être utilisé pour modéliser des regroupements ou des regroupements possibles.

En combinatoire, on distingue les partitions d’un ensemble et les partitions d’un entier. Le nombre de partitions d’un entier n est noté p(n). Le nombre de partitions d’un ensemble de n éléments est donné par les nombres de Bell Bn. Les deux notions sont liées à des structures d’équivalence et à des tableaux ou à des récapitulations combinatoires.

Le partitionnement est également utilisé en informatique et en bases de données pour répartir les données (partitionnement horizontal ou vertical, sharding), améliorer les performances et la gestion des données. En géométrie et en apprentissage automatique, on parle de partitionnement spatial (diagrams de Voronoï, arbres k-d) et de division d’un jeu de données en ensembles d’entraînement et de test.