Modèle de données “ensemble”

Généralités

La formalisation du concept d'ensemble et l'édiction des règles qui permettent de les construire a été l'un des plus grand défis des mathématiques à la charnière entre le xix-ème siècle et le xx-ème siècle. Cette question a été centrale pour la résolution de la crise des fondements des mathématiques et a abouti à la construction axiomatique que l'on connaît aujourd'hui. Elle sera abordée dans le chapitre sur la calculabilité du cours de master Complexité algorithmique. Nous nous con­ten­te­rons ici d'en donner une définition informelle qui suffira pour les besoins de ce cours.

Il existe un unique ensemble qui ne contient aucun élément, c'est l'ensemble vide. On le note $\varnothing$ ou encore $\{\}$. On appelle singleton tout ensemble réduit à un unique élément et paire tout ensemble réduit à deux éléments. On appelle sous-ensemble ou partie d'un ensemble $F$ tout ensemble $E$ dont tous les éléments sont aussi des éléments de $F,$ soit $\mathrm{\forall }x,x\in E\Rightarrow x\in F$. On écrit alors $E\subseteq F$ où $\subseteq$ est le symbole dit d'inclusion et on dit que $E$ est inclus dans $F$. Deux ensembles $E$ et $F$ sont égaux si et seulement si $E\subseteq F$ et $F\subseteq E$. L'ensemble de toutes les parties d'un ensemble $E$ est appelé ensemble des parties de $E$ et on le note $\mathcal{P}(E)$. Il contient en particulier la partie vide $\varnothing$ et $E$. Pour tout ensemble $E,$ l'inclusion définit une relation d'ordre partiel sur $\mathcal{P}(E)$. Si $E\subseteq F$ et $E\ne F,$ on écrit $E\subset F$ et on dit que $E$ est strictement inclus dans $F$.

1. En extension. Dans ce cas on écrit explicitement la liste de tous les éléments qui constituent l'ensemble comme $\{1,2,5\}$ qui décrit l'ensemble constitué des trois entiers $1,2$ et $5$. ;
2. En compréhension. Cette fois les éléments de l'ensemble sont décrits à l'aide d'un prédicat $P(x)$ qui les caractérisent, autrement dit un prédicat que seuls ces objets satisfont. On écrit alors cet ensemble $\{x\mid P(x)\}$.

Opérations ensemblistes

Soient $E$ et $F$ deux ensembles. On définit la différence ensembliste $E\setminus F$ (on dit $E$ privé de $F$) des deux ensembles $E$ et $F$ par l'ensemble des éléments de $E$ qui n'appartiennent pas à $F$ : $$\begin{array}{}\text{(1)}& E\setminus F:=\{x\mid (x\in E)\wedge (x\notin F)\}.\end{array}$$ Dans le cas particulier où $F$ est une partie de $E,$ la différence symétrique $E\setminus F$ est appelée com­plé­men­tai­re de $F$ dans $E$ et notée ${\complement }_{E}F$. En général le contexte est non ambigü et l'ensemble contenant $E$ est omis dans l'écriture, on écrit donc plus simplement $\complement F$ ou $\bar{F}$. On définit la réunion $E\cup F$ des deux ensembles $E$ et $F$ par l'ensemble des éléments qui ap­par­tien­nent à $E$ ou à $F$ : $$\begin{array}{}\text{(2)}& E\cup F:=\{x\mid (x\in E)\vee (x\in F)\}.\end{array}$$ On définit l'intersection $E\cap F$ des deux ensembles $E$ et $F$ par l'ensemble des éléments qui ap­par­tien­nent à $E$ et à $F$ : $$\begin{array}{}\text{(3)}& E\cap F:=\{x\mid (x\in E)\wedge (x\in F)\}.\end{array}$$ Deux ensembles dont l'intersection est vide sont dits disjoints. On définit la différence symétrique des deux ensembles $E$ et $F$ par l'ensemble des éléments qui appartiennent à $E$ ou à $F$ mais pas aux deux, i.e. $$\begin{array}{}\text{(4)}& E\mathrm{\Delta }F:=(E\cup F)\setminus (E\cap F).\end{array}$$

Vous pouvez visualiser le résultat de ces opérations ensemblistes en les survolant ci-dessous. La zone en surbrillance fournit le résultat. Ce type de représentation s'appelle un diagramme de Venn :

Structures de données

Le lecteur trouvera dans le chapitre Modèle et structures de données liste les définitions des tableaux et des listes chaînées qui vont être utilisés ici. Pour l'aspect statique des opérations, au sens ou les ensembles impliqués ne sont pas modifiés, nous devons bien sûr pouvoir accéder à chaque élément d'un ensemble et les opérations courantes sont :

1. Appartenance : déterminer si un objet appartient ou non à un ensemble ;
2. Cardinalité : calculer le cardinal d'un ensemble ;
3. Réunion : calculer la réunion de deux ensembles.
4. Intersection : calculer l'intersection de deux ensembles ;
5. Différence : calculer la différence de deux ensembles.
6. Différence sym. : calculer la différence symétrique de deux ensembles.

Pour l'aspect dynamique, nous devons pouvoir réaliser :

7. Ajout : ajouter un élément à un ensemble ;
8. Suppression : supprimer un élément d'un ensemble ;

Tableaux

Ce sont en général les structures de données associées au modèle de données liste qui sont utilisées pour coder les ensembles. Autrement dit, un ensemble est codé par une liste de ses éléments, il bénéficie donc des mécanismes d'indexation quand la structure associée le permet, comme un tableau par exemple. Dans ce cas les éléments de l'ensemble sont par conséquent ordonnés à travers leurs positions dans la structure (cf. exercice ci-dessous). Dans toute la suite, $E$ et $F$ désignent deux en­sembles de cardinal $n$ et $m$ respectivement.

Tableaux

Nous allons aborder succinctement les algorithmes réalisant les 8 opérations précédentes dans le cas où la structure pour coder un ensemble $E$ est un tableau. Sans autre hypothèse, tester l'appartenance d'un objet $x$ à $E$ nécessite de parcourir la structure associée et le coût est de $\mathrm{\Theta }(1)$ dans le meilleur des cas ($x$ est en première position) et $\mathrm{\Theta }(n)$ dans le pire des cas ($x$ n'appartient pas au tableau). En revanche, si l'ensemble $E$ peut-être muni d'une relation d'ordre total et que les éléments de $E$ sont triés dans le tableau, la recherche peut se faire en $\mathrm{\Theta }(\log n)$ par dichotomie si $n=\mathrm{\#}E.$

Calculer le cardinal de $E$ est une opération qui est généralement réalisée en $\mathrm{\Theta }(1),$ cette information étant souvent rangée dans la structure de donnée et mise à jour en cas d'ajout ou de suppression d'un élément. Dans le cas contraire, il faut évidemment $\mathrm{\Theta }(n)$ opérations.

La réunion de deux ensembles $E$ et $F$ consiste à créer un tableau résultat et à y ranger suc­ces­si­ve­ment les objets de $E$ puis ceux de $F,$ le coût est donc $\mathrm{\Theta }(n+m)$.

Si les objets ne sont pas triés, le calcul de l'intersection se fait en créant un tableau résultat et en y rangeant chaque élément de $E$ uniquement s'il appartient à $F$. Le coût est donc $\mathrm{\Theta }(nm)$. Si les tableaux sont triés, on teste alors l'appartenance d'un élément du plus petit des deux ensembles (disons $E$) dans $F$ par dichotomie, le coût est alors réduit en $\mathrm{\Theta }(n\log m)$.

La différence $E\setminus F$ s'obtient de manière similaire au calcul de l'intersection, en s'assurant cette fois que l'élément courant n'appartient pas à $F$. Les complexités sont donc identiques.

La différence symétrique est obtenue en appliquant successivement la réunion et l'intersection. (Peut-on faire un peu mieux ?)

Compte tenu de la structure statique de tableau, l'ajout d'un nouvel élément $x$ dans $E$ n'est pas réalisable directement. Cela nécessite de créer un nouveau tableau de taille $n+1$ et d'y recopier le tableau initial avant de rajouter $x$. Ceci suppose que $x$ n'appartenait pas à $E$ avant l'opération. Le coût est donc en $\mathrm{\Theta }(n$). La suppression d'un élément $x$ se passe de manière similaire en allouant un nouveau tableau de taille $n-1$ puis en testant lors de la copie si l'élément courant à ranger est différent de $x$. Le nouveau tableau peut bien sûr remplacer l'ancien si l'ajout ou la suppression d'un objet $x$ nécessite ou non de le conserver.

Listes chaînées

Nous reprenons la même démarche que pour les tableaux mais cette fois avec la structure dynamique de liste chaînée. Tester l'appartenance d'un objet $x$ nécessite de parcourir la liste, on retrouve donc la même complexité. En revanche l'absence d'accès direct ne permet pas de faire une recherche dichotomique pour baisser le coût.

La réunion est réalisée de la même manière que pour une structure statique, le coût est donc identique en $\mathrm{\Theta }(n+m)$. En revanche, si l'on n'a pas la nécessité de conserver les deux listes, il suffit de chaîner la dernière cellule de la liste chaînée codant $E$ vers la première cellule de la liste chaînée codant $F$ et dans ce cas le coût est $\mathrm{\Theta }(1)$.

L'intersection est réalisée de la même manière que pour les tableaux sans pouvoir bénéficier du tri des éléments, le coût reste donc en $\mathrm{\Theta }(nm)$.

Pour ajouter un élément qui n'est pas déjà dans la liste, il suffit de créer une nouvelle cellule en tête de liste ou en bout de liste, le coût est donc en $\mathrm{\Theta }(1)$. La suppression d'un objet présent dans le liste demande de le cherche en parcourant la liste, la suppression en elle même n'a qu'un coût de $\mathrm{\Theta }(1)$ puisqu'il suffit de décrocher la cellule et de la libérer de la mémoire, le coût est donc $\mathrm{\Theta }(n)$.

Nous verrons au chapitre Fonctions et tables de hachage une autre structure permettant, entre autres, de coder les ensembles et comment elle permet d'obtenir des opérations parfois moins coûteuses.

Codage par vecteur caractéristique

Algèbre de Boole

En logique, les trois opérateurs de négation, de disjonction et de conjonction sont notés res­pec­ti­ve­ment $\mathrm{\neg }a,$ $a\vee b$ et $a\wedge b,$ mais le mathématicien britannique George Boole a noté des similitudes entre le calcul algébrique sur les nombres et le calcul en logique propositionnelle, il a donc algébrisé la logique. En interprétant $0$ comme la valeur de vérité faux et 1 comme la valeur de vérité vrai, on peut munir l'ensemble $B:=\{0,1\}$ d'une structure algébrique particulière appelée algèbre de Boole à l'aide de ces trois opérateurs. Pour cela, on leur réserve une notation plus adaptée au calcul algébrique :

Ces trois opérateurs fonctionnent de manière analogue à ce que leur notation algébrique suggère en héritant essentiellement des mêmes propriétés que s'il s'agissait du calcul dans $\mathbb{Z}$. La loi mul­ti­pli­ca­ti­ve est ainsi souvent notée $\cdot$ et on omet parfois de l'écrire dans les ex­pres­sions al­gé­bri­ques quand il n'y aucune ambiguité, $x(y+z)$ au lieu de $x.(y+z)$ ou $x\times (y+z)$. La négation est donc involutive i.e. $\overline{\stackrel{―}{a}}=a,$ le tiers exclus s'exprime $a.\bar{a}=0$ et la non-contradiction $a+\bar{a}=1$. On dispose d'autre part des propriétés suivantes :

1. Associativité : $(a+b)+c=a+(b+c)=a+b+c$
2. Commutativité : $a+b=b+a$
3. Distributivité : $a\times (b+c)=a\times b+a\times c$
4. Idempotence : $a+a+\cdots +a=a$
5. Élément neutre : $a+0=0+a=a$
6. Absorption : $1+a=a+1=1$

Le principe de dualité permet de déduire les mêmes propriétés pour l'opérateur $\times$. Il suffit d'échan­ger le rôle des opérateurs $+$ et $\times$ et celui des valeurs $0$ et $1$. Par exemple $a\times 1=1\times a=a$ est la propriété duale de $a+0=0+a=a$. Notons que $1$ n'admet pas de symétrique pour l'addition mais qu'il est son propre symétrique pour la multiplication. On retrouve également les lois de De Morgan (du mathématicien britannique Augustus De Morgan) qui sont deux lois duales : $$\begin{array}{}\text{(5)}& \overline{a+b}& \equiv \bar{a}.\bar{b}\text{(6)}& \overline{a.b}& \equiv \bar{a}+\bar{b}\end{array}$$

On définit trois nouveaux opérateurs, la disjonction exclusive, l'implication et l'équi­va­len­ce à partir des trois premiers à l'aide des équivalences logiques suivantes : $$\begin{array}{}\text{(7)}& a\oplus b& \equiv (a+b)\cdot \overline{(a\cdot b)}\text{(8)}& a\Rightarrow b& \equiv \bar{a}+b\text{(9)}& a\iff b& \equiv (\bar{a}+b).(a+\bar{b})\end{array}$$ Leurs tables de vérité sont :

1. négation $\leftrightarrow$ complémentaire
2. ou $\leftrightarrow$ réunion
3. et $\leftrightarrow$ intersection
4. ou exclusif $\leftrightarrow$ différence symétrique

Vecteurs caractéristiques

Nous allons étudier à présent une autre structure de données très utilisée en pratique car ex­trê­me­ment performante en terme de temps et d'espace. Soit $X$ un ensemble. On rappelle que la fonction indicatrice d'une partie $A$ de $X$ est définie par $$\begin{array}{}\text{(12)}& {\mathbb{1}}_A(x)=\{\begin{array}{ll}1& \text{si}x\in A,\\ 0& \text{sinon}.\end{array}\end{array}$$ Supposons à présent que $X$ soit un ensemble fini est notons $n$ son cardinal. On peut donc numéroter ses élé­ments et écrire $E=\{x_0,x_1,\dots ,x_{n-1}\}$ (cf. exercice). On définit une application $\chi :\mathcal{P}(E)\to \{0,1{\}}^n$ par $$\begin{array}{}\text{(13)}& \chi (A):=({\mathbb{1}}_A(x_0),{\mathbb{1}}_A(x_1),\dots ,{\mathbb{1}}_A(x_{n-1}))\end{array}$$

Prenons l'exemple d'un jeu de $32$ cartes. Comment représenter une main, c'est-à-dire un sous-en­sem­ble de cartes ? Il faut tout d'abord se fixer une énumération de l'ensemble $X$ des $32$ cartes, par exemple dans l'ordre des couleurs et des valeurs suivantes :

Notons que pour tester l'appartenance $x\in A,$ l'opération $(1\ll x)\wedge A$ renvoie un entier non-nul si $x\in A$ et 0 sinon. Pour les langages de programmation, les opérateurs bit à bit agissant sur des registres vus comme des entiers, il est donc impossible de conserver les notations usuelles de l'algèbre de Boole puisque l'opérateur $+$ par exemple est généralement dédié à l'addition sur les entiers et non pas au ou logique. Le langage $C$ utilise les symboles ~A, A | B, A & B, A ^ B, A << s et A >> s respectivement à la table ci-dessus.

Le corps à deux éléments

En guise de complément, nous présentons une autre structure algébrique fondamentale sur l'en­sem­ble $\{0,1\}$ et qui intervient principalement dans le domaine de l'in­for­ma­tion et de la com­mu­ni­ca­tion.

On rappelle qu'une loi de composition interne*Une loi de composition externe est une application $\star :Y\times X\to X$ est une application de $X\times X\to X$. On utilise la notation infixe $x\diamond y$ plutôt que la notation préfixe $\diamond (x,y)$ généralement employée pour les fonctions. Une loi de composition interne peut disposer de propriétés remarquables :

1. Associativité : $\mathrm{\forall }a,b,c\in X,$ $(a\diamond b)\diamond c=a\diamond (b\diamond c)$.
2. Élément neutre : $\mathrm{\exists }e\in X\mid \mathrm{\forall }x\in X,x\diamond e=e\diamond x=x$ ($e$ est l'élément neutre).
3. Élément symétrique : $\mathrm{\forall }x\in X,\mathrm{\exists }{x}^{\prime }\in X\mid x\diamond x^{\prime }=x^{\prime }\diamond x=e$ ($x^{\prime }$ est le symétrique de $x$).
4. Commutativité : $\mathrm{\forall }a,b\in X,$ $a\diamond b=b\diamond a$.

Si $X$ est muni de deux lois de composition, $\diamond$ et $\bullet ,$ on peut disposer de la propriété de dis­tri­bu­ti­vi­té de $\diamond$ sur $\bullet$ :

1. Distributivité à gauche : $\mathrm{\forall }a,b,c\in X,$ $a\diamond (b\bullet c)=(a\diamond b)\bullet (a\diamond c)$.
2. Distributivité à droite : $\mathrm{\forall }a,b,c\in X,$ $(a\bullet b)\diamond c=(a\diamond c)\bullet (b\diamond c)$.

Si la loi est commutative, la distributivité à gauche entraîne la distributivité à droite et ré­ci­pro­que­ment. Dans ce cas, on ne précise plus à gauche ou à droite.

Un ensemble $X$ muni d'une loi $\diamond$ associative, disposant d'un élément neutre et d'un élément symé­tri­que pour tout élément de $X,$ constitue ce que l'on appelle un groupe. Ce groupe est un groupe com­mu­ta­tif si la loi $\diamond$ est commutative. Par exemple $(\mathbb{R},+)$ est un groupe commutatif, tout comme $({\mathbb{R}}^{\ast },\times )$. De plus la dis­tri­bu­ti­vi­té de $\times$ sur $+$ font du triplet $(\mathbb{R},+,\times )$ ce que l'on nomme un corps (commutatif ici car la loi multiplicative $\times$ est commutative).

Comme pour l'ensemble des nombres réels $\mathbb{R},$ on peut munir la paire $\{0,1\}$ d'une structure de corps commutatif avec deux lois de composition internes, l'addition notée $+$ et la multiplication notée $\times$ ou $\cdot ,$ dont les graphes sont fournis par les tables ci-dessous. On note ce corps ${\mathbb{F}}_2$.

Pour l'addition, les deux éléments $0$ et $1$ sont leurs propres symétriques (on dit aussi opposés pour une loi additive), i.e. $0+0=0$ et $1+1=0$ et pour la multiplication $1$ est son propre symétrique (on dit aussi inverse pour une loi multiplicative), i.e. $1\times 1=1$.

Soit $n$ un entier naturel. Le produit cartésien ${\mathbb{F}}_2^n$ de $n$ copies de l'ensemble $\{0,1\}$ est muni d'une struc­tu­re d'espace vectoriel à l'aide d'une loi de composition interne $+$ et une loi de loi de com­po­si­tion externe $\cdot$ définies par $$\begin{array}{}\text{(15)}& (x_1,x_2,\dots ,x_n)+(y_1,y_2,\dots ,y_n)& :=(x_1+y_1,x_2+y_2,\dots ,x_n+y_n)\text{(16)}& \lambda \cdot (x_1,x_2,\dots ,x_n)& :=(\lambda \cdot x_1,\lambda \cdot x_2,\dots ,\lambda \cdot x_n)\end{array}$$ Aucune ambiguïté n'étant possible et afin de ne pas allourdir les notations, on utilise gé­né­ra­le­ment les mêmes symboles $+$ et $\cdot$ pour désigner ces opérations sur les deux ensembles, ${\mathbb{F}}_2^n$ et ${\mathbb{F}}_2$. Un élément de $({\mathbb{F}}_2^n,+,\cdot )$ est appelé vecteur binaire. Le corps ${\mathbb{F}}_2$ et le ${\mathbb{F}}_2$-espace vectoriel ${\mathbb{F}}_2^n$ jouent un rôle ab­so­lu­ment fon­da­men­tal en informatique.

Travaux pratiques