Langage de programmation - Mathématiques appliquées - Ensembles, relations et fonctions

Ensembles, relations et fonctions

Les ensembles, les relations et les fonctions constituent trois notions fondamentales des mathématiques discrètes et de la programmation. Elles permettent de décrire des collections d'objets, les liens existant entre ces objets et les transformations appliquées à leurs valeurs. Ces concepts apparaissent dans presque tous les domaines de l'informatique, notamment les structures de données, les bases de données, les graphes, les langages de programmation, la logique, les automates, les algorithmes et la théorie des types.

Un ensemble regroupe des éléments distincts. Une relation décrit une correspondance possible entre des éléments appartenant à un ou plusieurs ensembles. Une fonction représente une relation particulière dans laquelle chaque élément de départ possède exactement une image dans l'ensemble d'arrivée.

En programmation, ces notions prennent des formes concrètes. Un ensemble peut être représenté par une collection sans doublon, une relation par une table de correspondance ou un ensemble de couples, et une fonction par une routine recevant des paramètres et produisant une valeur. Leur compréhension est donc essentielle pour modéliser correctement les données et les traitements.

Ensemble

Un ensemble est une collection d'éléments distincts considérée comme une seule entité mathématique.

Un ensemble est généralement noté à l'aide d'une lettre majuscule :

A
B
C

Ses éléments sont placés entre accolades :

A = {1, 2, 3, 4}

Dans cet exemple, l'ensemble A contient les quatre entiers :

1
2
3
4

L'ordre dans lequel les éléments sont écrits n'a pas d'importance.

Ainsi :

{1, 2, 3}

et :

{3, 1, 2}

représentent le même ensemble.

Absence de doublons

Un ensemble ne contient pas plusieurs occurrences distinctes du même élément.

Par conséquent :

{1, 1, 2, 2, 3}

représente le même ensemble que :

{1, 2, 3}

Cette propriété distingue les ensembles de certaines structures informatiques comme les listes ou les tableaux, dans lesquels les doublons sont généralement autorisés.

Dans une structure de type ensemble, l'ajout d'un élément déjà présent ne modifie pas son contenu.

Appartenance

La notation :

x ∈ A

signifie que l'élément x appartient à l'ensemble A.

Par exemple, si :

A = {2, 4, 6, 8}

alors :

4 ∈ A

La notation :

x ∉ A

signifie que x n'appartient pas à A.

Ainsi :

5 ∉ A

Définition par énumération

Un ensemble peut être défini en énumérant explicitement ses éléments.

Par exemple :

JoursOuvrables =
{Lundi, Mardi, Mercredi, Jeudi, Vendredi}

Cette notation est adaptée aux ensembles contenant peu d'éléments.

Elle permet de voir immédiatement tous les éléments appartenant à l'ensemble.

Définition par compréhension

Un ensemble peut également être défini par une propriété caractérisant ses éléments.

Par exemple :

A = {x ∈ N | x est pair et x < 10}

Cette expression se lit :

A est l'ensemble des entiers naturels x tels que x est pair et inférieur à 10.

On obtient :

A = {0, 2, 4, 6, 8}

Le symbole :

se lit généralement :

tel que

Ensembles numériques courants

Plusieurs ensembles numériques sont utilisés fréquemment.

Symbole	Nom	Description
ℕ	Nombres naturels	Entiers positifs ou nuls selon la convention utilisée
ℤ	Entiers relatifs	Entiers négatifs, nuls et positifs
ℚ	Nombres rationnels	Nombres pouvant être écrits comme quotient de deux entiers
ℝ	Nombres réels	Ensemble comprenant notamment les rationnels et les irrationnels
ℂ	Nombres complexes	Nombres comprenant une partie réelle et une partie imaginaire

On rencontre généralement les inclusions suivantes :

ℕ ⊆ ℤ ⊆ ℚ ⊆ ℝ ⊆ ℂ

Ensemble vide

L'ensemble vide est l'ensemble qui ne contient aucun élément.

Il est noté :

∅

ou parfois :

{}

Sa cardinalité est :

|∅| = 0

L'ensemble vide est un sous-ensemble de tout ensemble.

Ainsi, pour tout ensemble A :

∅ ⊆ A

Ensemble universel

L'ensemble universel représente l'ensemble de tous les éléments considérés dans un contexte donné.

Il est souvent noté :

Par exemple, si l'on étudie les entiers compris entre 1 et 10 :

U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

Tous les ensembles utilisés dans le problème sont alors considérés comme des sous-ensembles de U.

La notion d'ensemble universel est particulièrement importante pour définir le complément d'un ensemble.

Cardinalité

La cardinalité d'un ensemble correspond au nombre d'éléments distincts qu'il contient.

Elle est notée :

|A|

Par exemple, si :

A = {2, 4, 6, 8}

alors :

|A| = 4

Pour les ensembles infinis, la cardinalité décrit leur taille au sens mathématique, même si le nombre d'éléments ne peut pas être exprimé par un entier fini.

Ensembles finis et infinis

Un ensemble est fini lorsqu'il contient un nombre limité d'éléments.

Par exemple :

A = {1, 2, 3}

est fini.

Un ensemble est infini lorsqu'il contient une quantité illimitée d'éléments.

Par exemple :

N = {0, 1, 2, 3, ...}

est infini.

En programmation, les collections manipulées sont généralement finies, même lorsqu'elles représentent conceptuellement un ensemble infini.

Sous-ensemble

Un ensemble A est un sous-ensemble de B lorsque tous les éléments de A appartiennent également à B.

On écrit :

A ⊆ B

Par exemple :

A = {1, 2}
B = {1, 2, 3, 4}

On a :

A ⊆ B

La relation de sous-ensemble autorise le cas où :

A = B

Sous-ensemble strict

Un ensemble A est un sous-ensemble strict de B lorsque :

tous les éléments de A appartiennent à B ;
A est différent de B.

On écrit généralement :

A ⊂ B

Par exemple :

{1, 2} ⊂ {1, 2, 3}

La notation exacte peut varier selon les ouvrages. Certains utilisent ? pour toute inclusion et ? pour l'inclusion stricte.

Égalité de deux ensembles

Deux ensembles sont égaux lorsqu'ils contiennent exactement les mêmes éléments.

On écrit :

A = B

si :

A ⊆ B

et :

B ⊆ A

L'ordre d'énumération n'a pas d'importance.

Ainsi :

{1, 2, 3} = {3, 2, 1}

Ensemble des parties

L'ensemble des parties d'un ensemble A est l'ensemble contenant tous les sous-ensembles possibles de A.

Il est noté :

P(A)

ou :

Si :

A = {a, b}

alors :

P(A) =
{
   ∅,
   {a},
   {b},
   {a,b}
}

Sa cardinalité est :

|P(A)| = 2^|A|

Un ensemble contenant n éléments possède donc exactement :

2ⁿ

sous-ensembles.

Union

L'union de deux ensembles A et B est l'ensemble des éléments appartenant à A, à B ou aux deux.

Elle est notée :

A ∪ B

Par exemple :

A = {1, 2, 3}
B = {3, 4, 5}

Alors :

A ∪ B = {1, 2, 3, 4, 5}

L'élément 3 n'apparaît qu'une seule fois dans le résultat.

Intersection

L'intersection de deux ensembles contient les éléments appartenant simultanément aux deux ensembles.

Elle est notée :

A ∩ B

Avec :

A = {1, 2, 3}
B = {3, 4, 5}

on obtient :

A ∩ B = {3}

Lorsque deux ensembles ne possèdent aucun élément commun, leur intersection est vide.

Ensembles disjoints

Deux ensembles sont disjoints lorsque leur intersection est vide.

On a alors :

A ∩ B = ∅

Par exemple :

A = {1, 2}
B = {3, 4}

sont disjoints.

Cette notion est importante dans les partitions, les classifications et les problèmes de dénombrement.

Différence

La différence entre A et B contient les éléments qui appartiennent à A, mais pas à B.

Elle est notée :

A \ B

ou parfois :

A - B

Par exemple :

A = {1, 2, 3, 4}
B = {3, 4, 5}

Alors :

A \ B = {1, 2}

et :

B \ A = {5}

La différence n'est donc pas commutative.

Différence symétrique

La différence symétrique contient les éléments appartenant à l'un des deux ensembles, mais pas aux deux simultanément.

Elle est notée :

A Δ B

ou :

A ⊕ B

Elle peut être définie par :

A Δ B =
(A \ B) ∪ (B \ A)

ou :

A Δ B =
(A ∪ B) \ (A ∩ B)

Par exemple :

{1, 2, 3} Δ {3, 4, 5}
=
{1, 2, 4, 5}

Complément

Le complément d'un ensemble A contient les éléments de l'ensemble universel U qui n'appartiennent pas à A.

Il est noté :

A^c

ou parfois :

Sa définition est :

A^c = U \ A

Par exemple, si :

U = {1, 2, 3, 4, 5}
A = {1, 3, 5}

alors :

A^c = {2, 4}

Propriétés des opérations ensemblistes

Les opérations sur les ensembles respectent plusieurs propriétés importantes.

Commutativité

A ∪ B = B ∪ A
A ∩ B = B ∩ A

Associativité

(A ∪ B) ∪ C =
A ∪ (B ∪ C)
(A ∩ B) ∩ C =
A ∩ (B ∩ C)

Distributivité

A ∩ (B ∪ C) =
(A ∩ B) ∪ (A ∩ C)
A ∪ (B ∩ C) =
(A ∪ B) ∩ (A ∪ C)

Idempotence

A ∪ A = A
A ∩ A = A

Éléments neutres

A ∪ ∅ = A
A ∩ U = A

Lois de De Morgan

Les lois de De Morgan établissent des relations entre le complément, l'union et l'intersection.

(A ∪ B)^c =
A^c ∩ B^c

et :

(A ∩ B)^c =
A^c ∪ B^c

Ces lois jouent un rôle majeur en théorie des ensembles, en logique propositionnelle et en algèbre de Boole.

Elles permettent notamment de transformer des conditions complexes en expressions équivalentes.

Produit cartésien

Le produit cartésien de deux ensembles A et B est l'ensemble de tous les couples ordonnés dont le premier élément appartient à A et le second à B.

Il est noté :

A × B

Si :

A = {1, 2}
B = {a, b}

alors :

A × B =
{
   (1,a),
   (1,b),
   (2,a),
   (2,b)
}

Contrairement aux ensembles ordinaires, l'ordre dans un couple est important.

Ainsi :

(1,a)

est généralement différent de :

(a,1)

Cardinalité d'un produit cartésien

Si A et B sont des ensembles finis, alors :

|A × B| =
|A| × |B|

Par exemple, si :

|A| = 3

et :

|B| = 4

alors :

|A × B| = 12

Cette propriété correspond directement au principe multiplicatif du dénombrement.

Tuple

Un tuple est une généralisation du couple ordonné.

Un tuple de trois éléments est appelé un triplet :

(a,b,c)

Plus généralement, un tuple de n éléments est appelé un n-uplet :

(x₁,x₂,...,x_n)

En programmation, les tuples servent à regrouper plusieurs valeurs ordonnées, éventuellement de types différents.

Ils sont utilisés pour représenter des coordonnées, des enregistrements, des résultats multiples ou des clés composées.

Partition d'un ensemble

Une partition d'un ensemble A est une collection de sous-ensembles non vides vérifiant les conditions suivantes :

ils sont deux à deux disjoints ;
leur union est égale à A.

Par exemple, pour :

A = {1, 2, 3, 4}

la collection :

{{1,2}, {3}, {4}}

est une partition de A.

Chaque élément appartient exactement à une partie de la partition.

Les partitions apparaissent dans les classifications, les regroupements et les relations d'équivalence.

Relation binaire

Une relation binaire entre deux ensembles A et B est un sous-ensemble du produit cartésien :

A × B

Une relation R peut donc être définie par :

R ⊆ A × B

Si le couple :

(a,b)

appartient à R, on écrit :

a R b

ou :

(a,b) ∈ R

La relation indique que l'élément a est lié à l'élément b selon une propriété donnée.

Exemple de relation

Considérons :

A = {1, 2, 3}
B = {2, 4, 6}

Définissons la relation :

x R y

lorsque :

y = 2x

La relation est alors :

R =
{
   (1,2),
   (2,4),
   (3,6)
}

Cette relation associe chaque élément de A à son double dans B.

Relation sur un ensemble

Une relation sur un ensemble A est un sous-ensemble de :

A × A

Par exemple, la relation :

≤

sur les entiers est une relation sur :

car elle compare deux entiers.

Les relations sur un même ensemble peuvent posséder des propriétés particulières comme la réflexivité, la symétrie ou la transitivité.

Relation réflexive

Une relation R sur A est réflexive lorsque chaque élément est en relation avec lui-même.

On a :

∀x ∈ A, xRx

Par exemple, la relation :

≤

est réflexive, car :

x ≤ x

pour tout nombre x.

La relation :

n'est pas réflexive, car :

x < x

est toujours faux.

Relation irréflexive

Une relation est irréflexive lorsqu'aucun élément n'est en relation avec lui-même.

On a :

∀x ∈ A, non(xRx)

La relation :

est irréflexive.

Il ne faut pas confondre une relation irréflexive avec une relation qui n'est simplement pas réflexive. Une relation peut ne satisfaire aucune de ces deux propriétés.

Relation symétrique

Une relation R est symétrique lorsque :

xRy implique yRx

pour tous les éléments concernés.

Par exemple, la relation :

x est frère ou soeur de y

est généralement symétrique.

Si x est frère ou soeur de y, alors y est frère ou soeur de x.

Relation antisymétrique

Une relation R est antisymétrique lorsque :

xRy et yRx impliquent x = y

La relation :

≤

est antisymétrique.

En effet, si :

x ≤ y

et :

y ≤ x

alors :

x = y

Une relation antisymétrique n'est pas nécessairement le contraire d'une relation symétrique. Une relation peut être à la fois symétrique et antisymétrique dans certains cas.

Relation transitive

Une relation R est transitive lorsque :

xRy et yRz impliquent xRz

Par exemple, la relation :

≤

est transitive.

Si :

x ≤ y

et :

y ≤ z

alors :

x ≤ z

La transitivité est importante dans les relations d'ordre, les dépendances et les graphes orientés.

Relation d'équivalence

Une relation d'équivalence est une relation qui est :

réflexive ;
symétrique ;
transitive.

Elle permet de considérer certains éléments comme équivalents selon un critère donné.

Par exemple, sur les entiers, la congruence modulo m est une relation d'équivalence :

a ≡ b MOD m

lorsque :

m divise a-b

Classe d'équivalence

La classe d'équivalence d'un élément a est l'ensemble de tous les éléments équivalents à a.

Elle est notée :

[a]

Par exemple, modulo 3, la classe de 1 contient :

[..., -5, -2, 1, 4, 7, 10, ...]

Tous ces entiers ont le même reste lorsqu'ils sont divisés par 3.

Les classes d'équivalence forment une partition de l'ensemble de départ.

Relation d'ordre

Une relation d'ordre est généralement une relation :

réflexive ;
antisymétrique ;
transitive.

Elle permet de comparer les éléments d'un ensemble.

La relation :

≤

est un ordre sur les nombres.

La relation d'inclusion :

⊆

est un ordre sur l'ensemble des parties d'un ensemble.

Ordre total

Un ordre est total lorsque tous les couples d'éléments sont comparables.

Pour tous x et y, on a :

xRy

ou :

yRx

La relation :

≤

sur les nombres réels est un ordre total.

Tous les nombres réels peuvent être comparés entre eux.

Ordre partiel

Un ordre est partiel lorsque certains éléments peuvent ne pas être comparables.

Par exemple, la relation :

⊆

sur les ensembles est un ordre partiel.

Les ensembles :

{1}

et :

{2}

ne sont pas comparables par inclusion, car aucun des deux n'est un sous-ensemble de l'autre.

Les ordres partiels apparaissent dans les dépendances, les hiérarchies et l'ordonnancement de tâches.

Représentation d'une relation par une matrice

Une relation finie peut être représentée par une matrice booléenne.

Supposons :

A = {a₁,a₂,...,a_n}

La matrice M de la relation est définie par :

M[i,j] = 1

si :

a_i R a_i

et :

M[i,j] = 0

sinon.

Cette représentation facilite l'utilisation d'algorithmes matriciels pour calculer la fermeture transitive ou analyser les propriétés d'une relation.

Représentation d'une relation par un graphe

Une relation sur un ensemble peut également être représentée par un graphe orienté.

Chaque élément devient un sommet.

Un arc est ajouté de x vers y lorsque :

xRy

Cette représentation permet d'interpréter :

la réflexivité par la présence de boucles ;
la symétrie par des arcs dans les deux directions ;
la transitivité par l'existence d'arcs correspondant aux chemins composés.

Les relations et les graphes orientés sont donc étroitement liés.

Fermeture réflexive

La fermeture réflexive d'une relation consiste à ajouter tous les couples nécessaires pour la rendre réflexive.

Pour un ensemble A, il faut ajouter :

(x,x)

pour chaque élément x qui ne possède pas déjà cette relation avec lui-même.

La fermeture réflexive de R peut être écrite :

R ∪ {(x,x) | x ∈ A}

Fermeture symétrique

La fermeture symétrique consiste à ajouter le couple inverse de chaque couple présent.

Si :

(x,y) ∈ R

alors on ajoute :

(y,x)

La fermeture symétrique est :

R ∪ R^-1

où R^-1 représente la relation inverse.

Fermeture transitive

La fermeture transitive d'une relation ajoute les couples nécessaires pour rendre la relation transitive.

Si :

xRy

et :

yRz

alors la fermeture doit contenir :

xRz

Dans un graphe orienté, la fermeture transitive relie directement deux sommets lorsqu'un chemin existe entre eux.

L'algorithme de Warshall permet de calculer cette fermeture pour une relation finie représentée par une matrice.

Fonction

Une fonction est une relation particulière associant à chaque élément d'un ensemble de départ exactement un élément d'un ensemble d'arrivée.

On écrit :

f : A → B

Cela signifie que la fonction f transforme les éléments de A en éléments de B.

Pour un élément :

x ∈ A

son image est notée :

f(x)

et appartient à B.

Domaine et codomaine

Dans :

f : A → B

l'ensemble A est appelé :

domaine

ou :

ensemble de départ

L'ensemble B est appelé :

codomaine

ou :

ensemble d'arrivée

Chaque élément du domaine doit posséder exactement une image dans le codomaine.

Image d'un élément

L'image d'un élément x par la fonction f est la valeur :

f(x)

Par exemple, si :

f(x) = x²

alors :

f(3) = 9

La fonction associe ici l'entier 3 à l'entier 9.

Image d'un ensemble

L'image d'un sous-ensemble S du domaine est l'ensemble des images de ses éléments.

Elle est notée :

f(S)

et définie par :

f(S) =
{f(x) | x ∈ S}

Par exemple, si :

f(x) = x²

et :

S = {-2,-1,0,1,2}

alors :

f(S) = {0,1,4}

Les doublons disparaissent puisque le résultat est un ensemble.

Image réciproque

L'image réciproque d'un ensemble T du codomaine est l'ensemble des éléments du domaine dont l'image appartient à T.

Elle est notée :

f^-1(T)

et définie par :

f^-1(T) =
{x ∈ A | f(x) ∈ T}

Cette notation ne signifie pas nécessairement que la fonction possède une fonction inverse.

Fonction totale

Une fonction est totale lorsque chaque élément de son domaine possède une image.

Dans la définition mathématique habituelle, une fonction est totale par défaut.

En informatique, certaines opérations peuvent toutefois être partielles.

Par exemple, la division :

f(x,y) = x/y

n'est pas définie lorsque :

y = 0

Si le domaine inclut les couples dont la seconde valeur est nulle, cette opération n'est pas une fonction totale.

Fonction partielle

Une fonction partielle n'est définie que pour une partie de son domaine potentiel.

Par exemple :

f(x) = √x

considérée comme une fonction réelle n'est pas définie pour les nombres négatifs.

Elle peut être décrite comme :

f : ℝ → ℝ

ou comme une fonction totale dont le domaine réel est limité à :

[0,+∞[

En programmation, les fonctions partielles peuvent provoquer des exceptions, retourner une valeur spéciale ou utiliser un type optionnel.

Fonction constante

Une fonction est constante lorsque tous les éléments du domaine possèdent la même image.

Par exemple :

f(x) = 5

Pour tout x :

f(x) = 5

La fonction génératrice constante et les conditions constantes en programmation reposent sur cette idée simple.

Fonction identité

La fonction identité associe chaque élément à lui-même.

Elle est définie par :

id_A(x) = x

pour tout :

x ∈ A

Elle est souvent notée :

id_A

La fonction identité joue le rôle d'élément neutre pour la composition des fonctions.

Fonction injective

Une fonction est injective lorsque deux éléments différents du domaine possèdent toujours des images différentes.

On peut écrire :

f(x₁) = f(x₂)

implique :

x₁ = x₂

ou de manière équivalente :

x₁ ≠ x₂

implique :

f(x₁) ≠ f(x₂)

Une fonction injective ne produit donc aucune collision entre des éléments distincts du domaine.

Exemple de fonction injective

La fonction :

f : Z → Z

définie par :

f(x) = 2x

est injective.

En effet, si :

2x₁ = 2x₂

alors :

x₁ = x₂

En revanche, la fonction :

f(x) = x²

sur les entiers n'est pas injective, car :

f(2) = f(-2) = 4

Fonction surjective

Une fonction est surjective lorsque chaque élément du codomaine possède au moins un antécédent dans le domaine.

On écrit :

∀y ∈ B,
∃x ∈ A tel que f(x) = y

Autrement dit, l'image de la fonction est égale à tout le codomaine.

Une fonction peut être surjective sans être injective lorsque plusieurs éléments du domaine possèdent la même image.

Exemple de fonction surjective

Considérons :

f : ℝ → [0,+∞[

définie par :

f(x) = x²

Cette fonction est surjective.

Pour chaque valeur positive ou nulle y, il existe au moins un nombre réel x tel que :

x² = y

Par exemple :

x = √y

En revanche, la même formule considérée comme :

f : R → R

n'est pas surjective, car aucun nombre réel n'a pour carré un nombre négatif.

Fonction bijective

Une fonction est bijective lorsqu'elle est à la fois :

injective ;
surjective.

Chaque élément du codomaine possède alors exactement un antécédent.

Une bijection établit une correspondance un à un entre deux ensembles.

Deux ensembles finis possèdent une bijection entre eux lorsqu'ils ont la même cardinalité.

Fonction inverse

Une fonction bijective possède une fonction inverse.

Si :

f : A → B

est bijective, alors :

f^-1 : B → A

est définie par :

f^-1(y) = x

lorsque :

f(x) = y

Les identités suivantes sont vérifiées :

f^-1(f(x)) = x

et :

f(f^-1(y)) = y

Exemple de fonction inverse

Considérons :

f : R → R

définie par :

f(x) = 2x + 3

Pour déterminer la fonction inverse, on pose :

y = 2x + 3

Puis on isole x :

x = (y-3)/2

On obtient donc :

f^-1(x) = (x-3)/2

Composition de fonctions

La composition de deux fonctions consiste à appliquer une fonction au résultat d'une autre.

Si :

f : A → B

et :

g : B → C

alors la composition :

g ∘ f

est une fonction :

g ∘ f : A → C

définie par :

(g ∘ f)(x) =
g(f(x))

L'ordre d'application est important.

Exemple de composition

Considérons :

f(x) = x + 1

et :

g(x) = x²

Alors :

(g ∘ f)(x)
=
g(x+1)
=
(x+1)²

Tandis que :

(f ∘ g)(x)
=

f(x²)
=
x²+1

En général :

g ∘ f ≠ f ∘ g

La composition n'est donc pas commutative.

Associativité de la composition

La composition des fonctions est associative.

Si les domaines et codomaines sont compatibles, alors :

h ∘ (g ∘ f)
=
(h ∘ g) ∘ f

Cette propriété permet de composer plusieurs transformations sans ambiguïté sur le regroupement.

Elle est largement utilisée dans les pipelines de traitement et la programmation fonctionnelle.

Fonction indicatrice

La fonction indicatrice d'un ensemble A indique si un élément appartient ou non à cet ensemble.

Elle est définie par :

1_A(x) =
1 si x ∈ A
0 sinon

Cette fonction transforme un test d'appartenance en une valeur numérique.

Elle est utile en probabilités, en combinatoire, en optimisation et dans les filtres logiques.

Fonction caractéristique en programmation

En programmation, une fonction indicatrice peut être représentée par une fonction booléenne :

MODULE AppartientA(x)

   SI x appartient à A ALORS
      RETOURNER VRAI
   SINON
      RETOURNER FAUX
   FIN SI

Elle peut aussi retourner :

ou :

selon le contexte.

Les prédicats utilisés dans les filtres sont des fonctions de ce type.

Fonction comme relation particulière

Toute fonction peut être représentée par un ensemble de couples.

Par exemple, la fonction :

f : {1,2,3} → {2,4,6}

définie par :

f(x) = 2x

peut être représentée par :

{
   (1,2),
   (2,4),
   (3,6)
}

La différence avec une relation générale est que chaque élément du domaine apparaît exactement une fois comme première composante.

Relation qui n'est pas une fonction

Considérons la relation :

R =
{
   (1,a),
   (1,b),
   (2,c)
}

Cette relation n'est pas une fonction de :

{1,2}

vers :

{a,b,c}

car l'élément 1 possède deux images différentes :

et :

Une fonction exige une seule image par élément du domaine.

Algorithme d'union de deux ensembles

Si les ensembles sont représentés par des structures empêchant les doublons, l'union peut être calculée simplement.

MODULE Union(A,B)

   résultat ← copie de A

   POUR CHAQUE élément DANS B
      Ajouter élément à résultat
   FIN POUR

   RETOURNER résultat

La structure utilisée doit ignorer ou empêcher l'ajout d'un doublon.

Algorithme d'intersection

MODULE Intersection(A,B)

   résultat ← ensemble vide

   POUR CHAQUE élément DANS A

      SI élément appartient à B ALORS
         Ajouter élément à résultat
      FIN SI

   FIN POUR

   RETOURNER résultat

L'efficacité dépend fortement de la structure utilisée pour tester l'appartenance.

Algorithme de différence

MODULE Différence(A,B)

   résultat &lar; ensemble vide

   POUR CHAQUE élément DANS A

      SI élément n'appartient pas à B ALORS
         Ajouter élément à résultat
      FIN SI

   FIN POUR

   RETOURNER résultat

Cette opération conserve uniquement les éléments propres à A.

Exemple en Java avec Set


import java.util.HashSet;
import java.util.Set;
 
public class EnsemblesSample {
 
    public static <T> Set<T> union(
        Set<T> a,
        Set<T> b
    ) {
        Set<T> resultat = new HashSet<>(a);
        resultat.addAll(b);
        return resultat;
    }
 
    public static <T> Set<T> intersection(
        Set<T> a,
        Set<T> b
    ) {
        Set<T> resultat = new HashSet<>(a);
        resultat.retainAll(b);
        return resultat;
    }
 
    public static <T> Set<T> difference(
        Set<T> a,
        Set<T> b
    ) {
        Set<T> resultat = new HashSet<>(a);
        resultat.removeAll(b);
        return resultat;
    }
 
    public static void main(String[] args) {
        Set<Integer> a =
            new HashSet<>(Set.of(1, 2, 3, 4));
 
        Set<Integer> b =
            new HashSet<>(Set.of(3, 4, 5));
 
        System.out.println(
            "Union : " + union(a, b)
        );
 
        System.out.println(
            "Intersection : "
            + intersection(a, b)
        );
 
        System.out.println(
            "Différence : "
            + difference(a, b)
        );
    }
}

Le résultat contient les éléments correspondant aux opérations ensemblistes demandées. L'ordre d'affichage peut varier avec une structure de type HashSet.

Représentation d'un ensemble par table de hachage

Une table de hachage permet généralement :

l'ajout d'un élément ;
la suppression d'un élément ;
le test d'appartenance ;

en temps moyen proche de :

O(1)

Cette représentation est adaptée lorsque l'ordre des éléments n'a pas d'importance.

Les performances dépendent toutefois de la qualité de la fonction de hachage et de la gestion des collisions.

Représentation par arbre équilibré

Un ensemble peut être représenté par un arbre de recherche équilibré.

Les opérations principales ont généralement une complexité :

O(log n)

Cette représentation présente l'avantage de conserver les éléments dans un ordre défini.

Elle est utile pour :

parcourir les éléments en ordre croissant ;
rechercher un minimum ou un maximum ;
effectuer des recherches par intervalle.
Représentation par vecteur de bits

Lorsqu'un ensemble contient des entiers appartenant à un domaine limité, il peut être représenté par un vecteur de bits.

Chaque position correspond à une valeur possible.

Un bit égal à 1 indique que l'élément appartient à l'ensemble.

Par exemple, pour représenter :

{0,2,5}

on peut utiliser :

101001

selon la convention d'orientation choisie.

Les unions et intersections peuvent alors être calculées par des opérations binaires.

Opérations binaires sur les ensembles

Avec une représentation par vecteur de bits :

Union =
A OR B
Intersection =
A AND B
Différence =
A AND NOT B
Différence symétrique =
A XOR B

Ces opérations sont très rapides et permettent de traiter plusieurs éléments simultanément à l'échelle des mots machine.

Complexité des opérations ensemblistes

La complexité dépend de la représentation.

Structure	Appartenance	Ajout	Suppression
Liste non triée	O(n)	O(1) ou O(n)	O(n)
Tableau trié	O(log n)	O(n)	O(n)
Table de hachage	O(1) en moyenne	O(1) en moyenne	O(1) en moyenne
Arbre équilibré	O(log n)	O(log n)	O(log n)
Vecteur de bits	O(1)	O(1)	O(1)

La taille du domaine, l'ordre attendu et la fréquence des opérations déterminent la structure la plus appropriée.

Relations dans les bases de données

Dans une base de données relationnelle, les données sont organisées sous forme de relations tabulaires.

Une ligne peut être vue comme un tuple.

Une table représente un ensemble de tuples partageant la même structure.

Les opérations de l'algèbre relationnelle, comme la sélection, la projection et la jointure, reposent directement sur les notions d'ensemble, de relation et de produit cartésien.

Jointure

Une jointure combine des tuples provenant de deux relations selon une condition.

Elle peut être interprétée comme :

un produit cartésien ;
suivi d'un filtrage selon une relation donnée.

Par exemple, une jointure entre une table Employés et une table Départements peut associer chaque employé au département dont l'identifiant correspond à sa clé étrangère.

Cette opération est une application directe des relations mathématiques.

Fonctions dans les langages de programmation

Dans un langage de programmation, une fonction est généralement un bloc de code :

possédant un nom ;
recevant zéro ou plusieurs paramètres ;
exécutant un traitement ;
retournant éventuellement une valeur.

Cependant, une fonction informatique peut avoir des effets secondaires, alors qu'une fonction mathématique associe uniquement une entrée à une sortie.

Une fonction pure se rapproche davantage de la définition mathématique.

Fonction pure

Une fonction est dite pure lorsqu'elle respecte généralement les propriétés suivantes :

le même ensemble d'arguments produit toujours le même résultat ;
elle ne modifie pas d'état externe ;
elle ne dépend pas d'une valeur externe variable ;
elle ne produit pas d'effet secondaire observable.

Par exemple :

Carré(x) = x × x

est une fonction pure.

Une fonction lisant l'heure courante ou modifiant un fichier ne l'est généralement pas.

Fonction d'ordre supérieur

Une fonction d'ordre supérieur est une fonction qui :

reçoit une fonction en paramètre ;
retourne une fonction ;
ou effectue les deux.

Les opérations comme :

Map
Filter
Reduce

utilisent fréquemment des fonctions passées comme arguments.

Cette approche repose sur l'idée qu'une fonction peut être manipulée comme une valeur.

Correspondance avec les types

Une déclaration de fonction comme :

f : A → B

ressemble à une signature de type en programmation.

Elle indique que la fonction :

reçoit une valeur de type A ;
produit une valeur de type B.

Cette correspondance permet d'utiliser la théorie des ensembles et des fonctions pour raisonner sur les systèmes de types.

Application de fonctions à une collection

L'opération Map applique une fonction à chaque élément d'une collection.

MODULE Map(f,A)

   résultat ← collection vide

   POUR CHAQUE x DANS A
      Ajouter f(x) à résultat
   FIN POUR

   RETOURNER résultat

Mathématiquement, cette opération construit l'image de l'ensemble ou de la collection par la fonction f.

Filtrage par prédicat

L'opération Filter conserve les éléments satisfaisant un prédicat.

MODULE Filter(prédicat,A)

   résultat ← collection vide

   POUR CHAQUE x DANS A

      SI prédicat(x) ALORS
         Ajouter x à résultat
      FIN SI

   FIN POUR

   RETOURNER résultat

Le résultat correspond au sous-ensemble :

{x ∈ A | prédicat(x)}

Le filtrage est donc une application directe de la définition d'un ensemble par compréhension.

Réduction

L'opération Reduce combine successivement les éléments d'une collection à l'aide d'une fonction binaire.

MODULE Reduce(f,A,initial)

   accumulateur ← initial

   POUR CHAQUE × DANS A
      accumulateur ←
         f(accumulateur,x)
   FIN POUR

   RETOURNER accumulateur

Lorsque l'opération est associative, elle peut parfois être parallélisée ou regroupée de différentes façons.

Applications

Les ensembles, les relations et les fonctions sont utilisés dans de nombreux domaines :

structures de données ;
bases de données relationnelles ;
théorie des graphes ;
algèbre de Boole ;
logique ;
automates ;
théorie des langages ;
programmation fonctionnelle ;
systèmes de types ;
intelligence artificielle ;
combinatoire ;
probabilités ;
optimisation ;
vérification de programmes ;
modélisation de domaines.

Ils constituent le langage de base permettant de formaliser les objets et leurs interactions.

Avantages

Ces notions présentent plusieurs avantages :

elles fournissent une représentation abstraite des collections ;
elles permettent de distinguer clairement les objets et leurs relations ;
elles facilitent les raisonnements formels ;
elles se traduisent directement en structures informatiques ;
elles permettent de modéliser des transformations déterministes ;
elles servent de fondement aux bases de données et aux graphes ;
elles facilitent l'analyse des types et des interfaces ;
elles rendent possibles de nombreuses démonstrations mathématiques.

Limites et précautions

Plusieurs précautions doivent être prises :

un ensemble ne conserve ni l'ordre ni les doublons ;
une collection informatique n'est pas toujours un ensemble mathématique ;
le codomaine doit être distingué de l'image réelle d'une fonction ;
une relation n'est pas nécessairement une fonction ;
une fonction inverse exige une bijection ;
la notation f^-1 peut désigner une image réciproque sans désigner une fonction inverse ;
une fonction informatique peut avoir des effets secondaires ;
les ensembles infinis ne peuvent pas toujours être matérialisés ;
la complexité des opérations dépend de la représentation choisie ;
certaines notations d'inclusion varient selon les ouvrages.

Remarque

Les ensembles, les relations et les fonctions constituent une base commune à une grande partie des mathématiques et de l'informatique. Les ensembles permettent de décrire les objets disponibles, les relations permettent de formaliser les liens entre eux et les fonctions permettent de représenter des transformations déterministes.

Ces notions se retrouvent directement dans les collections sans doublon, les tables relationnelles, les graphes, les prédicats, les signatures de fonctions et les systèmes de types. Leur étude prépare naturellement à l'algèbre de Boole, aux relations de récurrence, aux graphes, aux probabilités, aux bases de données et à la logique mathématique.

Dernière mise à jour : Jeudi, le 16 juillet 2026