Relation d'équivalence et relation d'ordre

Une relation d'équivalence est une relation réflexive, symétrique et transitive : elle regroupe les éléments qui « se valent » d'un certain point de vue, et découpe l'ensemble en classes. Une relation d'ordre est une relation réflexive, antisymétrique et transitive : elle permet de comparer et de ranger. Ces deux familles de relations sont au programme de l'E3, et elles sont derrière deux gestes quotidiens de l'informaticien : regrouper (GROUP BY, sous-réseaux, tables de hachage) et trier (ORDER BY, algorithmes de tri).

Relation d'équivalence : définition

L'égalité est la relation d'équivalence la plus stricte. Les autres sont des égalités « partielles » : deux éléments sont équivalents quand ils ont la même valeur pour un certain critère.

• « a le même reste dans la division par 4 que » sur ℤ ;
• « est dans le même réseau /24 que » sur l'ensemble des adresses IPv4 ;
• « a la même extension que » sur un ensemble de fichiers ;
• « travaille dans le même service que » sur les salariés.

Démontrer qu'une relation est une relation d'équivalence

Exemple corrigé. Sur ℤ, on définit x R y si et seulement si x − y est un multiple de 5. Montrer que R est une relation d'équivalence.

• Réflexive. Soit x ∈ ℤ. x − x = 0 = 5 × 0, multiple de 5. Donc x R x.
• Symétrique. Soient x, y ∈ ℤ tels que x R y : il existe k ∈ ℤ tel que x − y = 5k. Alors y − x = 5 × (−k), avec −k ∈ ℤ. Donc y R x.
• Transitive. Soient x, y, z ∈ ℤ tels que x R y et y R z : x − y = 5k et y − z = 5k′, avec k, k′ ∈ ℤ. En additionnant, x − z = 5(k + k′), avec k + k′ ∈ ℤ. Donc x R z.

R est réflexive, symétrique et transitive : c'est une relation d'équivalence. C'est la congruence modulo 5, notée x ≡ y [5], que tu retrouves en arithmétique dans les congruences modulo n et les clés de contrôle, et au chapitre 6 dans le chiffrement affine.

Classes d'équivalence et partition

La classe d'équivalence d'un élément x, notée cl(x) ou ẋ, est l'ensemble de tous les éléments équivalents à x :

cl(x) = {y ∈ E | y R x}

Exemple. Sur E = {0 ; 1 ; … ; 11}, avec x R y si x et y ont le même reste dans la division par 4 :

• cl(0) = {0 ; 4 ; 8}
• cl(1) = {1 ; 5 ; 9}
• cl(2) = {2 ; 6 ; 10}
• cl(3) = {3 ; 7 ; 11}

Et cl(4) = cl(8) = cl(0) : deux éléments équivalents ont la même classe. Chaque classe peut être désignée par n'importe lequel de ses éléments, qu'on appelle alors un représentant.

Ces quatre classes sont non vides, deux à deux disjointes, et leur réunion est E : elles forment une partition de E (chapitre 2). C'est toujours le cas.

Les relations d'équivalence en informatique

Les sous-réseaux. Deux adresses IPv4 sont dans le même réseau /24 si leurs 24 premiers bits sont égaux, c'est-à-dire si elles ont la même adresse réseau. C'est une relation de la forme « f(x) = f(y) » : une relation d'équivalence. Chaque classe est un réseau. 192.168.1.10 et 192.168.1.200 sont équivalentes (réseau 192.168.1.0/24) ; 192.168.2.10 est dans une autre classe. Un routeur fait ce calcul pour chaque paquet : il cherche le réseau, donc la classe, de l'adresse de destination pour choisir sa route.

Les tables de hachage. Une table de hachage range chaque clé dans une case numérotée h(k). Avec h(k) = k mod 8, les clés 3, 11 et 19 tombent dans la case 3, les clés 8 et 16 dans la case 0. « Tomber dans la même case » est une relation d'équivalence ; chaque case contient une classe. C'est ainsi que fonctionnent les dictionnaires de Python, les Map de JavaScript ou les index de hachage des SGBD.

Le regroupement en SQL. GROUP BY id_service regroupe les lignes qui ont la même valeur de id_service : il calcule les classes de la relation « a le même service que », puis applique COUNT, SUM ou AVG à chaque classe. Les groupes forment une partition des lignes : chacune est dans un groupe et un seul (GROUP BY dans le cours SQL).

Relation d'ordre : définition

La seule différence avec une relation d'équivalence est la deuxième propriété : antisymétrique au lieu de symétrique. Une équivalence met des éléments au même niveau ; un ordre les étage.

Exemples de relations d'ordre :

• ≤ sur ℕ, ℤ ou ℝ ;
• « divise » sur ℕ* ;
• l'inclusion ⊂ sur P(E) ;
• l'ordre alphabétique sur les mots ;
• « doit être terminée avant (ou est) » sur les tâches d'un projet.

Ordre strict. La relation < (« strictement inférieur ») n'est pas réflexive, donc ce n'est pas une relation d'ordre au sens de la définition : c'est un ordre strict, irréflexif et transitif. On passe de l'un à l'autre en ajoutant ou en retirant la diagonale : x ≤ y si et seulement si x < y ou x = y.

Ordre total, ordre partiel

Deux éléments x et y sont comparables si x ≤ y ou y ≤ x.

• L'ordre est total si deux éléments quelconques sont toujours comparables. ≤ sur ℝ est total ; l'ordre alphabétique aussi.
• Sinon, il est partiel. Pour « divise », 2 et 3 ne sont pas comparables : 2 ne divise pas 3 et 3 ne divise pas 2. Pour l'inclusion, {a} et {b} ne sont pas comparables.

Un ordre partiel est tout aussi utile : l'ordre des tâches d'un projet est partiel (deux tâches indépendantes peuvent se faire dans n'importe quel ordre), et c'est précisément ce qui permet de les mener en parallèle. L'ordonnancement, au programme de l'E3, travaille sur ces ordres partiels.

Le diagramme de Hasse

Le graphe complet d'une relation d'ordre est illisible : une boucle sur chaque sommet, et tous les raccourcis dus à la transitivité. Le diagramme de Hasse n'en garde que l'essentiel.

1. On supprime les boucles (la réflexivité est sous-entendue).
2. On supprime les arcs qui se déduisent par transitivité : on ne relie x à y que si y « suit immédiatement » x, sans élément intermédiaire.
3. On place les plus petits éléments en bas et on supprime les flèches : un trait monte toujours de x vers y quand x ≤ y.

Exemple : les diviseurs de 12, ordonnés par « divise ». D = {1 ; 2 ; 3 ; 4 ; 6 ; 12}. On relie 1 à 2 et à 3, 2 à 4 et à 6, 3 à 6, 4 et 6 à 12. On ne relie pas 2 à 12 : on passe par 4 (ou par 6). On ne relie pas 3 à 12 : on passe par 6.

Pour savoir si x ≤ y, on cherche un chemin montant de x à y. 2 divise 12 (2 → 4 → 12) ; 4 ne divise pas 6 (aucun chemin montant de 4 à 6) : 4 et 6 ne sont pas comparables.

Le schéma des droits Unix du chapitre 1 est lui aussi un diagramme de Hasse, celui de l'inclusion sur les parties de {r ; w ; x} : un cube.

Plus petit élément, éléments minimaux

Ces mots ont un sens précis, et la nuance tombe souvent en QCM.

Dans {2 ; 3 ; 4 ; 6}, 2 et 3 sont minimaux (rien ne les divise dans cet ensemble, à part eux-mêmes), mais aucun des deux n'est le plus petit, car ils ne sont pas comparables entre eux. Un plus petit élément, quand il existe, est unique ; il peut y avoir plusieurs éléments minimaux. Sur un diagramme de Hasse, les minimaux sont les sommets d'où ne descend aucun trait.

L'ordre lexicographique : comment trier sur plusieurs critères

Pour comparer deux couples (a ; b) et (a′ ; b′) dont chaque terme est ordonné, l'ordre lexicographique compare d'abord les premiers termes, et seulement en cas d'égalité les seconds :

(a ; b) ≤ (a′ ; b′) si a < a′, ou si a = a′ et b ≤ b′.

C'est l'ordre du dictionnaire : on compare la première lettre, puis la deuxième en cas d'égalité, et ainsi de suite. Si chaque terme est totalement ordonné, l'ordre lexicographique est total.

Exemple. Les couples (2 ; 5), (1 ; 9), (2 ; 1), (1 ; 3), (3 ; 0) rangés dans l'ordre lexicographique : (1 ; 3), (1 ; 9), (2 ; 1), (2 ; 5), (3 ; 0). Le premier terme décide ; le second ne sert qu'à départager.

ORDER BY nom, prenom applique exactement cet ordre aux couples (nom ; prénom) :

Exercices

Exercice 1 sur 5 Classes d'équivalence Réussi À revoir

Sur E = {0 ; 1 ; 2 ; 3 ; 4 ; 5 ; 6 ; 7 ; 8}, on définit x R y si x et y ont le même reste dans la division par 3.

1. Justifie rapidement que R est une relation d'équivalence.
2. Détermine toutes les classes d'équivalence.
3. Combien y a-t-il de classes ? Vérifie qu'elles forment une partition de E.

Voir la réponseMasquer la réponse de l'exercice 1

1. R est de la forme « f(x) = f(y) », avec f(x) le reste de la division de x par 3. Elle hérite de la réflexivité, de la symétrie et de la transitivité de l'égalité.
2. cl(0) = {0 ; 3 ; 6}, cl(1) = {1 ; 4 ; 7}, cl(2) = {2 ; 5 ; 8}.
3. 3 classes, autant que de restes possibles (0, 1, 2). Elles sont non vides, deux à deux disjointes, et leur réunion contient les 9 éléments de E (3 + 3 + 3 = 9) : c'est une partition.

Tu avais trouvé ?

Oui, j'avais bonPas encore

Exercice 2 sur 5 Une relation sur ℤ Réussi À revoir

Sur ℤ, on définit x R y si et seulement si x² = y².

1. Démontre que R est une relation d'équivalence.
2. Détermine la classe de 0, la classe de 3 et la classe de −7.
3. R est-elle une relation d'ordre ?

Voir la réponseMasquer la réponse de l'exercice 2

1. R est de la forme f(x) = f(y) avec f(x) = x². En détail : x² = x², donc x R x (réflexive) ; si x² = y², alors y² = x² (symétrique) ; si x² = y² et y² = z², alors x² = z² (transitive).
2. cl(0) = {y ∈ ℤ | y² = 0} = {0}. cl(3) = {y ∈ ℤ | y² = 9} = {−3 ; 3}. cl(−7) = {−7 ; 7}.
3. Non : elle n'est pas antisymétrique, car 3 R (−3) et (−3) R 3 avec 3 ≠ −3.

Tu avais trouvé ?

Oui, j'avais bonPas encore

Exercice 3 sur 5 Fichiers et extensions Réussi À revoir

Un dossier contient les fichiers rapport.pdf, photo.jpg, cv.pdf, logo.png, plan.jpg et notes.txt. On les regroupe par la relation « a la même extension que ».

1. Écris les classes d'équivalence.
2. Quelle requête SQL produirait le nombre de fichiers par classe, si les fichiers étaient dans une table fichier(nom, extension) ?

Voir la réponseMasquer la réponse de l'exercice 3

1. {rapport.pdf ; cv.pdf}, {photo.jpg ; plan.jpg}, {logo.png}, {notes.txt} : 4 classes, dont deux singletons.
2. SELECT extension, COUNT(*) FROM fichier GROUP BY extension; : GROUP BY construit exactement ces classes.

Tu avais trouvé ?

Oui, j'avais bonPas encore

Exercice 4 sur 5 Diagramme de Hasse des diviseurs de 18 Réussi À revoir

On ordonne D = {1 ; 2 ; 3 ; 6 ; 9 ; 18}, l'ensemble des diviseurs de 18, par la relation « divise ».

1. Trace le diagramme de Hasse.
2. Cet ordre est-il total ? Justifie.
3. D a-t-il un plus petit élément ? un plus grand élément ?
4. Dans A = {2 ; 3 ; 6 ; 9}, quels sont les éléments minimaux et maximaux ? A a-t-il un plus grand élément ?

Voir la réponseMasquer la réponse de l'exercice 4

1. Traits : 1 – 2, 1 – 3, 2 – 6, 3 – 6, 3 – 9, 6 – 18, 9 – 18. On place 1 en bas, 2 et 3 au-dessus, puis 6 et 9, puis 18 en haut. Pas de trait 1 – 6 (on passe par 2 ou 3), ni 3 – 18 (on passe par 6 ou 9).
2. Non, l'ordre est partiel : 2 et 3 ne sont pas comparables (aucun des deux ne divise l'autre), de même que 2 et 9, ou 6 et 9.
3. Plus petit élément : 1, qui divise tous les éléments. Plus grand élément : 18, que tous divisent.
4. Minimaux : 2 et 3 (aucun autre élément de A ne les divise). Maximaux : 6 et 9 (ils ne divisent aucun autre élément de A). A n'a pas de plus grand élément, car 6 et 9 ne sont pas comparables.

Tu avais trouvé ?

Oui, j'avais bonPas encore

Exercice 5 sur 5 Trier comme un SGBD Réussi À revoir

1. Range dans l'ordre lexicographique les couples (service ; ancienneté) suivants : (COMPTA ; 12), (INFO ; 3), (COMPTA ; 4), (DIR ; 20), (INFO ; 11).
2. Range les versions 2.0.0, 1.10.0, 10.0.0 et 1.9.2 dans l'ordre croissant des versions, puis dans l'ordre où les range un tri de chaînes de caractères.

Voir la réponseMasquer la réponse de l'exercice 5

1. (COMPTA ; 4), (COMPTA ; 12), (DIR ; 20), (INFO ; 3), (INFO ; 11). Les services sont rangés par ordre alphabétique, puis l'ancienneté départage à l'intérieur d'un même service, comme ORDER BY service, anciennete.
2. Ordre des versions, en comparant les triplets d'entiers : 1.9.2, 1.10.0, 2.0.0, 10.0.0. Tri de chaînes, caractère par caractère : "1.10.0", "1.9.2", "10.0.0", "2.0.0". Le tri de chaînes place 1.10.0 avant 1.9.2 et 10.0.0 avant 2.0.0, ce qui est faux pour des versions.

Tu avais trouvé ?

Oui, j'avais bonPas encore