Ensemble (informatique)

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En informatique, un ensemble ou set est une structure de données de type abstrait qui peut stocker certaines valeurs, sans ordre particulier, et ne présentant aucun doublon (la tentative d'insertion de doublons est sans effet)[1]. Il s'agit d'une mise en œuvre informatique de la notion mathématique d'ensemble fini. Contrairement à la plupart des autres types de collections[2] les ensembles sont plus utilisés pour tester l'appartenance d'une valeur à cet ensemble que pour en extraire des données.

Certaines structures de données de type ensemble sont conçues pour être statiques (ou « gelées ») : elles ne peuvent pas être modifiées après leur conception. Ces ensembles statiques ne permettent que des opérations de requête sur leurs éléments — telles que vérifier si une valeur donnée est présente dans l'ensemble, ou énumérer les valeurs dans un ordre arbitraire. Il existe généralement sur les serveurs les supportant des opérateurs tels qu'union, intersection et différence permettant des opérations de requête rapides[1]. D'autres variantes, appelés ensembles dynamiques ou modifiables, permettent également l'insertion et la suppression d'éléments de l'ensemble.

Une structure de données de type abstrait est une collection, ou agrégat, de données. Les données peuvent être des opérateurs booléens, des nombres, des caractères ou autres structures de données. Si l'on prend en compte les fonctionnalités d'empaquetage[3] ou d'indexation[4], il existe quatre grandes structures de données :

  • non empaquetée, non indexée: collection d'objets (bunch)
  • empaquetée, non indexée : ensemble
  • non empaquetée, indexée : chaîne (séquence)
  • empaquetée, indexée : liste (array).

Dans cette structuration, les ensembles contiennent des éléments, alors que la collection d'objets consiste en ces éléments[5].

Une structure de données probabiliste implémentant ce type est le filtre de Bloom.

Notes et références[modifier | modifier le code]

  1. a et b Rudi Bruchez, Les bases de données NoSQL : Comprendre et mettre en œuvre, Éditions Eyrolles, , 279 p. (ISBN 9782212135602, lire en ligne), p. 172
  2. Constituent d'autres types de collections (de type conteners) les listes, les multiensembles, les arborescences et les graphes
  3. "Empaqueter", faire des paquets, consiste à fournir un conteneur pour une agrégation d'objets afin de les transformer en un objet unique. Dans le cas d'un appel de fonction: sans paquet, une fonction ne peut être appelée à agir sur une chaîne qu'en passant en revue chaque élément du groupe comme argument séparé, ce qui complique considérablement l'exécution de la fonction (et est tout simplement pas possible dans certains langages de programmation). En regroupant les éléments en un ensemble, la fonction peut maintenant être appelée sur un argument unique, élémentaire : l'ensemble d'objets (bunch's package en anglais).
  4. L'indexation est possible lorsque les éléments envisagés sont totalement ordonnés. En l'absence d'ordre, les éléments d'un multi-ensemble (par exemple) ne présentent pas de relations telles qu'inférieures/supérieures, ou précédents/ suivants un autre élément : ils ne peuvent être comparés qu'en termes absolus (identiques/différents)
  5. Eric C.R. Hehner [a Practical Theory of Programming http://www.cs.utoronto.ca/~hehner/aPToP/aPToP.pdf] p. 14

Articles connexes[modifier | modifier le code]