Modèle et structures de données ensemble

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.

Un ensemble \(E\) est une collection d'objets distincts. Ces objects sont appelés les éléments de l'ensemble \(E\). Si \(x\) est un élément de \(E\), on écrit \(x\in E\) (parfois \(E\ni x\)) et dans le cas contraire \(x\not\in E\) plutôt que \(\neg (x\in E)\).

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 \(\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\not = F\), on écrit \(E\subset F\) et on dit que \(E\) est strictement inclus dans \(F\).

On décrit un ensemble à l'aide d'accolades ouvrante \(\{\) et fermante \(\}\), qui servent de délimiteurs. Il existe deux manières de décrire un ensemble :
  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)\}\).
Attention, un ensemble est caractérisé par les objets qu'il contient et qui doivent être distincts, l'ensemble \(\{2,2\}\) n'est constitué que du seul entier naturel \(2\), il s'agit donc d'un singleton et non d'une paire, l'écriture est simplement redondante et inutile.
Les abus de langage et de notations sont nombreux, par exemple \(\{1,2,\ldots,n\}\) est admis pour décrire l'ensemble des entiers naturels compris entre \(1\) et un entier naturel \(n\) que l'on devrait décrire en compréhension à l'aide de l'expression \(\{k\mid (k\in{\mathbf N})\wedge (1\leq k)\wedge (k\leq n)\}\). On note généralement de manière condensée \(\{x\in E\mid P(x)\}\) pour dé­cri­re la partie d'un ensemble \(E\) constituée par ses éléments qui satisfont le prédicat \(P(x)\) (l'existence d'un tel ensemble est un axiome de la théorie des ensembles appelé axiome de sélection).

L'ensemble des entiers naturels inférieurs à 4 s'écrit en extension \(\{0,1,2,3,4\}\) et \(\{n\in{\mathbf N}\mid n\leq 4\}\) en compréhension. L'ensemble des entiers naturels pairs s'écrit en com­pré­hen­sion : \[\{n\in{\mathbf N}\mid \exists k\in{\mathbf N},\ n=2k\}.\] L'intervalle semi-ouvert à droite \([a,b[\) de \({\mathbf R}\) est défini par une écriture en compréhension : \[[a,b[\;:=\{x\in{\mathbf R}\mid a\leq x < b\}.\]
Décrivez l'ensemble des entiers premiers en compréhension. Décrivez l'ensemble des fonctions réelles paires, impaires en compréhension.
Soit \(E\) un ensemble quelconque. Discutez de la valeur de vérité de chacune des assertions suivantes : \begin{align*} \{1,2\}&=\{1,1,1,2\} & 1&\in\{\{1\}\} & 1&\in\{1,\{1\}\} & \{1\}&\in\{1,\{1\}\} \\ x&\in\varnothing & \varnothing&\in\{\varnothing\} & E&\in\{E\} & \{\varnothing\}&\in{\mathcal P}(\varnothing)\\ \varnothing&\subseteq\{\varnothing\} & \varnothing&\subseteq E & E&\subseteq\{E\}& \varnothing&\subseteq{\mathcal P}(\varnothing)\\ E&\subseteq E & E&\subseteq {\mathcal P}(E) & E&\in {\mathcal P}(E) & \varnothing&\in {\mathcal P}(E)\\ \{1,2,3\} &= \{1,3,2\} & \varnothing&\subseteq\varnothing & \varnothing&\in\varnothing & \{1,2\}&\in {\mathcal P}(\{1,2,3\}) \end{align*}
Soit \(E\) un ensemble. Montrez que \(\varnothing\) et \(E\) sont respectivement le plus petit et le plus grand élément de \({\mathcal P}(E)\) pour la relation d'inclusion \(\subseteq\).
Soit \(E=\{a,b,c\}\). Écrivez l'ensemble des parties de \(E\) en extension. Montrez que si \(E\) est un en­sem­ble fini de cardinal \(n\) alors \(\#{\mathcal P}(E)=2^n\).
Soit \(E=\{a,b,c,d\}\). Quels sont les éléments minimaux et quels sont les éléments maximaux de l'ensemble \(\#{\mathcal P}(E)\setminus\{\varnothing,E\}\) pour l'inclusion ? (voir paragraphe ci-dessous pour la définition de la différence ensembliste \(E\setminus F\)).

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{equation} E\setminus F:=\{x\mid (x\in E)\wedge (x\not\in F)\}. \end{equation} 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 \(\overline{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{equation} E\cup F:=\{x\mid (x\in E)\vee (x\in F)\}. \end{equation} 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{equation} E\cap F:=\{x\mid (x\in E)\wedge (x\in F)\}. \end{equation} 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{equation} E\,\Delta\, F:=(E\cup F)\setminus(E\cap F). \end{equation}

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 :

E 
 F
 
Diagramme de Venn des opérations ensemblistes sur les ensembles \(E\) et \(F\). Ensemble ou opération : aucune.

Soient \(E\), \(F\) et \(G\) trois ensembles. Montrez que la réunion et l'intersection sont des lois associatives et commutatives : \begin{align*} E\cup(F\cup G)&=(E\cup F)\cup G\\ E\cap(F\cap G)&=(E\cap F)\cap G\\ E\cup F&=F\cup E\\ E\cap F&=F\cap E\ \end{align*} Montrez que l'intersection est distributive sur la réunion et réciproquement : \begin{align*} E\cap(F\cup G)&=(E\cap F)\cup(E\cap G)\\ E\cup(F\cap G)&=(E\cup F)\cap(E\cup G) \end{align*}
Soient \(E\), \(F\) deux ensembles. Montrer que \(E\,\Delta\, F=\varnothing\) si et seulement si \(E=F\).

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 :

  1. Ajout : ajouter un élément à un ensemble ;
  2. Suppression : supprimer un élément d'un ensemble ;

Tableaux et listes

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.

Soit \(E\) un ensemble fini. Par définition il existe un entier \(n\) et une bijection \(\varphi:E\rightarrow[1,n]\). Démontrez que la relation \(\preceq\) définie sur \(E\) par \(x\preceq y\Leftrightarrow \varphi(x)\leq\varphi(y)\) est une relation d'ordre total.

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 \(\Theta(1)\) dans le meilleur des cas (\(x\) est en première position) et \(\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 \(\Theta(\log n)\) par dichotomie si \(n=\#E\).

Calculer le cardinal de \(E\) est une opération qui est généralement réalisée en \(\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 \(\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 \(\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 \(\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 \(\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 \(\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.

Écrivez les fonctions Python qui réalisent ces 8 opérations sur des ensembles représentés à l'aide de tableaux.

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 \(\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 \(\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 \(\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 \(\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 \(\Theta(1)\) puisqu'il suffit de décrocher la cellule et de la libérer de la mémoire, le coût est donc \(\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.

Écrivez les fonctions Python qui réalisent ces 8 opérations sur des ensembles représentés à l'aide de listes chaînées.

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 \(\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ébraisé 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 :

\(a\)\(\overline{a}\)
01
10
non \(\neg\)
\(a\)\(b\)\(a+b\)
000
011
101
111
ou \(\vee\)
\(a\)\(b\)\(a\times b\)
000
010
100
111
et \(\wedge\)
Tables de vérité des opérateurs logiques non, ou, et.

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 \({\mathbf 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{\overline{a}}=a\), le tiers exclus s'exprime \(a.\overline{a}=0\) et la non-contradiction \(a+\overline{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{align} \overline{a+b} &\equiv \overline{a}.\overline{b}\\ \overline{a.b} &\equiv \overline{a}+\overline{b} \end{align}

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{align} a\oplus b&\equiv (a+b)\cdot \overline{(a\cdot b)}\\ a\Rightarrow b&\equiv \overline{a}+b\\ a\Leftrightarrow b&\equiv (\overline{a}+b).(a+\overline{b}) \end{align} Leurs tables de vérité sont :

\(a\)\(b\)\(a\oplus b\)
000
011
101
110
ou exclusif
\(a\)\(b\)\(a\Rightarrow b\)
001
011
100
111
implication
\(a\)\(b\)\(a\Leftrightarrow b\)
001
010
100
111
équivalence
Tables de vérité des opérateurs logiques ou exclusif, implication et équivalence.
Démontrez la propriété de redondance (et sa duale) i.e. \(\forall a,b,x\in B\), \[ax + \overline{a}y = ax + \overline{a}y + xy.\] Montrez la propriété de simplification, i.e. \(\forall a,b\in B\), \[a+\overline{a}\times b = a+b.\]
Dressez les tables de vérité des deux opérateurs logiques \(\overline{+}\) (non ou) et \(\overline{\times}\) (non et) définis res­pec­ti­ve­ment par \begin{align} a\overline{+} b &:= \overline{a+b}\\ a\overline{\times} b &:= \overline{a\times b}\\ \end{align} Démontrez que l'opérateur non ou est un opérateur universel, c'est-à-dire que l'on peut définir les trois opérateurs non, ou et et par combinaison de cet opérateur. Indication : on a \(\overline{a}=a\overline{+} a\). Montrez que l'opérateur non et est lui aussi universel.
Il faut remarquer les similitudes entre les lois de l'algèbre de Boole et les opérations ensemblistes :
  1. négation \(\leftrightarrow\) complémentaire
  2. ou \(\leftrightarrow\) réunion
  3. et \(\leftrightarrow\) intersection
  4. ou exclusif \(\leftrightarrow\) différence symétrique
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.
Une loi de composition interne dans un ensemble \(E\) est une application \(\star:E\times E\rightarrow E\) (une loi de composition externe sur un ensemble \(F\) dans un ensemble \(E\) est une application de \(F\times E\rightarrow E\)). On utilise la notation infixe \(x\star y\) plutôt que la notation préfixe \(\star(x,y)\) généralement employée pour les fonctions. Une loi de composition interne peut disposer de propriétés remarquables :
  1. Associativité : \(\forall a,b,c\in E\), \((a\star b)\star c=a\star (b\star c)\).
  2. Élément neutre : \(\exists e\in E\ \mid\ \forall x\in E,\ x\star e=e\star x=x\) (\(e\) est l'élément neutre).
  3. Élément symétrique : \(\forall x\in E,\ \exists x'\in E\ \mid\ x\star x'=x'\star x=e\) (\(x'\) est le symétrique de \(x\)).
  4. Commutativité : \(\forall a,b\in E\), \(a\star b=b\star a\).

Si \(E\) est muni de deux lois de composition, \(\star\) et \(\bullet\), on peut disposer de la propriété de dis­tri­bu­ti­vi­té de \(\star\) sur \(\bullet\) :

  1. Distributivité à gauche : \(\forall a,b,c\in E\), \(a\star(b\bullet c)=(a\star b)\bullet(a\star c)\).
  2. Distributivité à droite : \(\forall a,b,c\in E\), \((a\bullet b)\star c=(a\star c)\bullet(b\star 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 \(E\) muni d'une loi \(\star\) associative, disposant d'un élément neutre et d'un élément symé­tri­que pour tout élément de \(E\), constitue ce que l'on appelle un groupe. Ce groupe est un groupe com­mu­ta­tif si la loi \(\star\) est commutative. Par exemple \(({\mathbf R},+)\) est un groupe commutatif, tout comme \(({\mathbf R}^*,\times)\). De plus la dis­tri­bu­ti­vi­té de \(\times\) sur \(+\) font du triplet \(({\mathbf 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 \({\mathbf 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 \({\mathbf F}_2\).

\(+\)01
001
110
\(\times\)01
000
101
Tables d'addition et de multiplication de \({\mathbf 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 \({\mathbf 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{align} (x_1,x_2,\ldots,x_n)+(y_1,y_2,\ldots,y_n)&:=(x_1+y_1,x_2+y_2,\ldots,x_n+y_n)\\ \lambda\cdot(x_1,x_2,\ldots,x_n)&:=(\lambda\cdot x_1,\lambda\cdot x_2,\ldots,\lambda\cdot x_n)\\ \end{align} 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, \({\mathbf F}_2^n\) et \({\mathbf F}_2\). Un élément de \(({\mathbf F}_2^n,+,\cdot)\) est appelé vecteur binaire. Le corps \({\mathbf F}_2\) et le \({\mathbf F}_2\)-espace vectoriel \({\mathbf F}_2^n\) jouent un rôle ab­so­lu­ment fon­da­men­tal en informatique.

La table de multiplication sur \({\mathbf F}_2\) coïncide bien avec la table de vérité du et logique, et les notations sont identiques, la table d'addition correspond en revanche à la table de vérité du ou exclusif. Il faut donc prendre garde au contexte pour les notations.

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 \(E\) un ensemble. On définit la fonction ca­rac­té­ris­ti­que \({\boldsymbol 1}_A:E\rightarrow\{0,1\}\) d'une partie \(A\) de \(E\) par \begin{equation} {\boldsymbol 1}_A(x)= \begin{cases} 1,&\text{si}\ x\in A.\\ 0,&\text{sinon}. \end{cases} \end{equation} Supposons à présent que \(E\) soit un fini est notons \(n\) son cardinal. On peut donc numéroter ses élé­ments et écrire \(E=\{x_0,x_1,\ldots,x_{n-1}\}\) (cf. exercice). On définit une application \(\chi:{\mathcal P}(E)\rightarrow\{0,1\}^n\) par \begin{equation} \chi(A):=({\boldsymbol 1}_A(x_0),{\boldsymbol 1}_A(x_1),\ldots, {\boldsymbol 1}_A(x_{n-1})) \end{equation}

Soit \(E\) un ensemble et \(A\) une partie de \(E\). Le vecteur \(\chi(A)\) est appelé vecteur caractéristique de la partie \(A\) de \(E\).

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 \(E\) des \(32\) cartes, par exemple dans l'ordre des couleurs et des valeurs suivantes :

7♣ 8♣ 9♣ 10♣ V♣ D♣ R♣ 1♣
\(x_{0}\) \(x_{1}\) \(x_{2}\) \(x_{3}\) \(x_{4}\) \(x_{5}\) \(x_{6}\) \(x_{7}\)
7♥ 8♥ 9♥ 10♥ V♥ D♥ R♥ 1♥
\(x_{8}\) \(x_{9}\) \(x_{10}\) \(x_{11}\) \(x_{12}\) \(x_{13}\) \(x_{14}\) \(x_{15}\)
7♠ 8♠ 9♠ 10♠ V♠ D♠ R♠ 1♠
\(x_{16}\) \(x_{17}\) \(x_{18}\) \(x_{19}\) \(x_{20}\) \(x_{21}\) \(x_{22}\) \(x_{23}\)
7♦ 8♦ 9♦ 10♦ V♦ D♦ R♦ 1♦
\(x_{24}\) \(x_{25}\) \(x_{26}\) \(x_{27}\) \(x_{28}\) \(x_{29}\) \(x_{30}\) \(x_{31}\)
Indexation de l'ensemble des 32 cartes. Cliquez sur une carte pour l'inclure ou l'exclure de la main.

Avec cette indexation, la main de la figure ci-dessus est codée par le vecteur caractéristique

\(\chi(A)=\) ()
de la partie \(\color{#FF0}A=\{\)\(\color{#FF0}\}\) de l'ensemble des cartes \(E\). L'analogie avec l'écriture binaire d'un nombre est patente, les registres machine sont donc par­ti­cu­liè­re­ment adaptés pour stocker les vecteurs ca­rac­té­ris­ti­ques. L'entier non-signé \(a=\) code en machine le vecteur ca­rac­té­ri­sti­que \(\chi(A)\) avec la relation \begin{equation} a=\sum_{k=0}^{n-1}1_A(x_k)2^k \end{equation} qui ne dit rien d'autre que le \(k\)-ème chiffre de l'écriture binaire de \(a\) (celui en coefficient de \(2^k\)) est la \(k\)-ème composante de \(\chi(A)\). La taille des ensembles est alors limitée par la taille des registres machines, soit 64 bits pour une machine moderne, mais on dépasse aisément cette limitation avec une structure contenant plusieurs registres (listes, tableaux, etc.)

Cette représentation est très utilisée en pratique pour les petits ensembles. Les vecteurs ca­rac­té­ris­ti­ques occupent peu d'espace mémoire et on dispose de l'arsenal des opérateurs bit à bit des processeurs pour manipuler le contenu des registres. Comme leur nom l'indique, les opérateurs bit à bit agissent comme leurs homologues logiques mais opèrent en parallèle sur chacun des bits qui constituent le registre. Ces opérations se font généralement en un seul cycle machine. Ils vont donc permettre de réaliser très simplement et très efficacement toutes les opérations classiques sur les ensembles comme nous allons le voir.

La table ci-dessous permet de voir l'action des opérateurs bit à bit et fournit leurs correspondances entre les opérations ensemblistes et celles de l'algèbre de Boole. Les nombres sont représentés en machine avec le bit significatif à gauche donc dans le sens invers de l'écriture des vecteurs ca­rac­té­ris­ti­ques. Le fonctionnement des 4 premiers opérateurs se passent d'explications, les deux derniers sont des opérateurs de décalage à gauche \(R\ll s\) et à droite \(R \gg s\), et décalent res­pec­ti­ve­ment tous les bits du registre de \(s\) positions sur la gauche ou sur la droite en insérant \(s\) valeurs 0 à droite et à gauche respectivement.

Vous pouvez saisir les valeurs entières codant les parties \(A\) et \(B\), ainsi que le nombre \(s\) de bits pour observer l'effet d'un décalage à gauche ou à droite :

Partie Codage déc. Codage binaire
\(A\)
\(B\)
Op. Ens. Boole Expression Codage déc. Codage binaire
non \(\complement A\) \(\overline{A}\) \(\neg A\)
ou \(A\cup B\) \(A+B\) \(A\vee B\)
et \(A\cap B\) \(A\times B\) \(A\wedge B\)
xou \(A\,\Delta\, B\) \(A\oplus B\) \(A\oplus B\)
Décalage Codage déc.
\(s\)
Op. Expression Codage déc. Codage binaire
décalage à gauche \(A \ll s\)
décalage à droite \(A \gg s\)
Élément Index dans \(E\)
\(x\)
Signification Expression Codage déc. Codage binaire
Singleton \(\{x\}\) \(1\ll x\)
Test \(x\in A?\) (\(1 \ll x)\wedge A\)
Opérations logiques sur vecteurs ca­rac­té­ris­ti­ques et correspondances ensemblistes.

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.

Écrivez un algorithme Poids qui calcule le poids binaire d'un entier naturel \(N\) en supposant que le nombre de ses chiffres est plus petit que la taille d'un registre machine et en utilisant les opérateurs bit à bit. En supposant que les registres puissent avoir une taille arbitrairement grande, calculez la complexité de votre algorithme en fonction du nombre de chiffres de \(N\).

Soit \(N\) un entier naturel. Calculez l'entier \(N\wedge (N-1)\) et comparez son écriture binaire avec celle de \(N\). Que remarquez vous ? En déduire un nouvel algorithme de calcul du poids binaire. Calculez sa complexité.

Écrivez les fonctions Python qui réalisent les opérations fondamentales sur les ensembles représentés à l'aide de vecteurs ca­rac­té­ris­ti­ques et des opérateurs bit à bit (décalage, opérations logiques et masques) et calculez la complexité de vos fonctions.
En exploitant la structure de vecteur caractéristique, écrivez un programme en Python qui simule le jeu de la pêche avec un jeu de 32 cartes.

On supposera qu'il y a 4 joueurs. Le gagnant est celui qui se sera débarrassé avant les autres des cartes de sa main. Initialement on distribue au hasard 5 cartes à chacun et les 12 cartes restantes sont placées en pile face cachée au milieu de la table. Celle pile constitue le lac.

À tour de rôle chaque joueur se débarrasse de toutes les paires qu'il peut constituer avec les cartes dans sa main en les déposant en pile dans son seau. S'il n'a pas ou plus de paire, il demande à un joueur de son choix (choisi au hasard par le programme) une carte qui lui permettrait de constituer une paire (choisie au hasard parmi les cartes qui restent dans sa main). Deux situations se présentent :

  1. L'autre joueur peut lui fournir la carte, la paire est alors placée dans le seau. S'il n'a plus de carte, la partie est gagnée, sinon il recommence.
  2. L'autre joueur ne peut pas lui fournir la carte, le joueur en pêche une dans le lac et la rajoute dans sa main. C'est au prochain joueur de jouer.

Estimez de manière expérimentale la durée moyenne d'une partie, l'unité de mesure étant le nombre d'actions réalisées, soit une paire déposée dans un seau ou une carte pêchée dans le lac. En numérotant les joueurs de 1 à 4 dans l'ordre de jeu, le joueur numéro 1 étant celui qui commence, calculez ex­pé­ri­men­ta­le­ment la probabilité \(p_i\) que le joueur numéro \(i\) gagne la partie.