Chapitre 313 minDébutant
Produit cartésien et cardinal
Par Josselyn C., prof de BTS SIO. Mis à jour le .
À la fin de ce chapitre, tu sauras
- écrire tous les éléments du produit cartésien de deux ensembles finis ;
- calculer le cardinal de E × F et de Eⁿ ;
- dénombrer des mots de passe, des adresses ou des combinaisons ;
- relier le produit cartésien au CROSS JOIN de SQL.
5 exercices corrigés1 schéma
Le produit cartésien de deux ensembles E et F, noté E × F, est l'ensemble de tous les couples (x ; y) dont le premier terme x est dans E et le second y dans F. Si E a n éléments et F en a p, E × F en a n × p. C'est l'outil de base pour dénombrer des combinaisons (mots de passe, adresses, configurations), et c'est ce que calcule un CROSS JOIN en SQL.
Couple et ensemble : l'ordre change tout
Un couple (a ; b) est une liste de deux termes dans un ordre donné. Contrairement à un ensemble :
- l'ordre compte : (1 ; 2) ≠ (2 ; 1), alors que {1 ; 2} = {2 ; 1} ;
- un terme peut se répéter : (3 ; 3) est un couple tout à fait correct, alors que {3 ; 3} n'est que {3}.
Deux couples sont égaux quand leurs premiers termes sont égaux et leurs seconds termes aussi :
(a ; b) = (c ; d) si et seulement si a = c et b = d.
Une coordonnée sur un échiquier (e4), une position dans un tableau (ligne 3, colonne 2), une adresse et son port (192.168.1.10 ; 443) : ce sont des couples. Avec trois termes, on parle de triplet, et avec n termes de n-uplet : (192 ; 168 ; 1 ; 10) est un quadruplet.
Définition du produit cartésien
Exemple. Une boutique en ligne vend un t-shirt en trois tailles, T = {S ; M ; L}, et deux couleurs, C = {noir ; blanc}. Les déclinaisons possibles du produit forment T × C :
T × C = {(S ; noir) ; (S ; blanc) ; (M ; noir) ; (M ; blanc) ; (L ; noir) ; (L ; blanc)}
Il y a 3 × 2 = 6 déclinaisons, donc 6 références à créer dans le catalogue.
Et C × T ? Ses éléments sont (noir ; S), (noir ; M), etc. : les mêmes associations, mais écrites dans l'autre ordre. Ce sont donc d'autres couples, et C × T ≠ T × C. Le produit cartésien n'est pas commutatif (sauf si E = F ou si l'un des deux est vide).
Le carré cartésien. E × E se note E². Avec E = {0 ; 1} :
E² = {(0 ; 0) ; (0 ; 1) ; (1 ; 0) ; (1 ; 1)}
Ce sont les quatre lignes d'une table de vérité à deux variables. Les couples dont les deux termes sont égaux, ici (0 ; 0) et (1 ; 1), forment la diagonale de E².
Trois façons de représenter E × F
Pour lister tous les couples sans en oublier, trois représentations, à choisir selon l'énoncé.
Le tableau à double entrée. Les éléments de E en lignes, ceux de F en colonnes, un couple par case. Le nombre de cases, n lignes × p colonnes, donne le cardinal.
| T \ C | noir | blanc |
|---|---|---|
| S | (S ; noir) | (S ; blanc) |
| M | (M ; noir) | (M ; blanc) |
| L | (L ; noir) | (L ; blanc) |
L'arbre. Une branche par élément de E, puis, au bout de chacune, une branche par élément de F. Chaque chemin de la racine à une feuille est un couple. L'arbre se prolonge naturellement à trois ensembles ou plus.
Le graphique. Si E et F sont des ensembles de nombres, chaque couple est un point d'un repère : E × F est une grille de points. C'est d'ailleurs l'origine du nom : René Descartes, Cartesius en latin, a popularisé les coordonnées.
Le cardinal du produit cartésien
La justification tient en une phrase : pour chacun des n choix du premier terme, il y a p choix du second, soit n × p couples. C'est le principe multiplicatif que tu as déjà utilisé sans le nommer pour compter les parties d'un ensemble (2ⁿ parties).
Si l'un des deux ensembles est vide, il n'y a aucun couple : E × ∅ = ∅, et le cardinal vaut bien n × 0 = 0.
Dénombrer en informatique
Le produit cartésien est partout dès qu'on compte des valeurs possibles.
| Objet | Ensemble | Cardinal |
|---|---|---|
| Un octet | {0 ; 1}⁸ | 2⁸ = 256 |
| Une adresse IPv4 | {0 ; 1}³², ou {0 ; … ; 255}⁴ | 2³² = 256⁴ = 4 294 967 296 |
| Une adresse MAC | {0 ; 1}⁴⁸ | 2⁴⁸ ≈ 2,8 × 10¹⁴ |
| Une couleur RVB sur 24 bits | {0 ; … ; 255}³ | 256³ = 16 777 216 |
| Un code PIN à 4 chiffres | {0 ; … ; 9}⁴ | 10⁴ = 10 000 |
| Un identifiant de 2 lettres puis 4 chiffres | L² × {0 ; … ; 9}⁴, où L est l'ensemble des 26 lettres | 26² × 10⁴ = 6 760 000 |
Exemple corrigé : la force d'un mot de passe
Un mot de passe de longueur 8 est un élément de A⁸, où A est l'ensemble des caractères autorisés. Il y a card(A)⁸ mots de passe possibles. Prenons un attaquant qui teste 10 milliards (10¹⁰) de mots de passe par seconde.
| Caractères autorisés | card(A) | Nombre de mots de passe de 8 caractères | Temps pour tous les tester |
|---|---|---|---|
| Minuscules | 26 | 26⁸ ≈ 2,1 × 10¹¹ | environ 21 secondes |
| Minuscules, majuscules, chiffres | 62 | 62⁸ ≈ 2,2 × 10¹⁴ | environ 6 heures |
| Les 95 caractères imprimables ASCII | 95 | 95⁸ ≈ 6,6 × 10¹⁵ | environ 7,7 jours |
Allonger le mot de passe est bien plus efficace qu'élargir l'alphabet : 62¹² ≈ 3,2 × 10²¹ demande plus de 10 000 ans au même rythme. La longueur est l'exposant de la puissance. C'est pourquoi les recommandations de sécurité fixent d'abord une longueur minimale. Les cartes graphiques actuelles vont encore plus vite que 10¹⁰ essais par seconde contre une empreinte rapide comme MD5 : d'où l'usage de fonctions de hachage volontairement lentes (bcrypt, Argon2) pour stocker les mots de passe (cours Sécurité).
Une table SQL est une partie d'un produit cartésien
Chaque colonne d'une table a un domaine : l'ensemble des valeurs permises par son type et ses contraintes. Une ligne de la table service (id_service, code, libelle) est un triplet, élément de D₁ × D₂ × D₃, où D₁ est l'ensemble des entiers, D₂ et D₃ des ensembles de chaînes. La table entière est un ensemble de tels triplets : une partie de D₁ × D₂ × D₃.
C'est exactement la définition d'une relation au sens mathématique, et c'est pour cela qu'Edgar F. Codd a appelé son modèle, en 1970, le modèle relationnel (cours SQL, chapitre 1). Le nombre de colonnes est le degré, le nombre de lignes est le cardinal.
CROSS JOIN : le produit cartésien en SQL
CROSS JOIN renvoie toutes les combinaisons d'une ligne de la première table avec une ligne de la seconde : c'est le produit cartésien des deux tables.
-- taille(code) contient S, M, L ; couleur(nom) contient noir, blanc
SELECT t.code, c.nom
FROM taille t
CROSS JOIN couleur c
ORDER BY t.code, c.nom;
| code | nom |
|---|---|
| L | blanc |
| L | noir |
| M | blanc |
| M | noir |
| S | blanc |
| S | noir |
3 lignes × 2 lignes = 6 lignes. C'est l'usage volontaire du produit cartésien : générer toutes les combinaisons (toutes les déclinaisons d'un produit, tous les créneaux d'un planning), pour ensuite chercher celles qui manquent.
L'usage involontaire est bien plus fréquent : une jointure est un produit cartésien dont on ne garde que les couples de lignes qui se correspondent (ON e.id_service = s.id_service). Oublie la condition et tu obtiens tout le produit : avec 6 services et 14 employés, 84 lignes au lieu de 14 (le produit cartésien dans le cours SQL). Le chapitre 7 revient sur ce lien.
Exercices
Exercice 1 sur 5 Écrire des produits cartésiens Réussi À revoir
Soit E = {0 ; 1} et F = {a ; b ; c}.
- Écris E × F en extension et donne son cardinal.
- Écris F × E. Est-il égal à E × F ?
- Combien d'éléments a E³ ? Écris-les.
Voir la réponseMasquer la réponse de l'exercice 1
- E × F = {(0 ; a) ; (0 ; b) ; (0 ; c) ; (1 ; a) ; (1 ; b) ; (1 ; c)}, card(E × F) = 2 × 3 = 6.
- F × E = {(a ; 0) ; (a ; 1) ; (b ; 0) ; (b ; 1) ; (c ; 0) ; (c ; 1)}. Il a aussi 6 éléments, mais ce ne sont pas les mêmes couples : (0 ; a) ∈ E × F et (0 ; a) ∉ F × E. Donc F × E ≠ E × F.
- card(E³) = 2³ = 8 : (0 ; 0 ; 0), (0 ; 0 ; 1), (0 ; 1 ; 0), (0 ; 1 ; 1), (1 ; 0 ; 0), (1 ; 0 ; 1), (1 ; 1 ; 0), (1 ; 1 ; 1). Ce sont les 8 mots binaires de 3 bits.
Tu avais trouvé ?
Exercice 2 sur 5 Égalité de couples Réussi À revoir
Trouve les réels x et y tels que (2x − 1 ; y + 3) = (5 ; 1).
Voir la réponseMasquer la réponse de l'exercice 2
Deux couples sont égaux quand leurs termes sont égaux un à un : 2x − 1 = 5 et y + 3 = 1. Donc x = 3 et y = −2.
Tu avais trouvé ?
Exercice 3 sur 5 Identifiants et mots de passe Réussi À revoir
- Une école attribue à chaque étudiant un identifiant formé de 3 lettres minuscules suivies de 2 chiffres (par exemple
dup42). Combien d'identifiants différents peut-elle créer ? - Un code de déverrouillage est formé de 6 chiffres. Combien de codes existe-t-il ? Combien si le premier chiffre ne peut pas être 0 ?
- Un mot de passe de 10 caractères utilise les 26 minuscules et les 10 chiffres. Combien en existe-t-il ? Écris le résultat sous la forme d'une puissance.
Voir la réponseMasquer la réponse de l'exercice 3
- Un identifiant est un élément de L³ × C², avec card(L) = 26 et card(C) = 10 : 26³ × 10² = 17 576 × 100 = 1 757 600 identifiants.
- {0 ; … ; 9}⁶ : 10⁶ = 1 000 000 codes. Si le premier chiffre est pris dans {1 ; … ; 9} : 9 × 10⁵ = 900 000 codes.
- L'alphabet a 26 + 10 = 36 caractères (les deux ensembles sont disjoints, on additionne), et un mot de passe est un élément de A¹⁰ : 36¹⁰ mots de passe, environ 3,7 × 10¹⁵.
Tu avais trouvé ?
Exercice 4 sur 5 Un planning en SQL Réussi À revoir
Une table jour contient les 5 jours ouvrés (lundi à vendredi) et une table creneau les 4 créneaux d'une journée (8 h, 10 h, 13 h 30, 15 h 30).
- Combien de lignes renvoie
SELECT * FROM jour CROSS JOIN creneau? À quel ensemble mathématique ce résultat correspond-il ? - Une table
reservation(jour, creneau, salle)enregistre les réservations de la salle B12. Décris en une phrase, avec le vocabulaire des ensembles, l'ensemble des créneaux libres de la salle B12.
Voir la réponseMasquer la réponse de l'exercice 4
- 5 × 4 = 20 lignes : c'est le produit cartésien J × C de l'ensemble des jours par l'ensemble des créneaux.
- C'est la différence (J × C) \ R, où R est l'ensemble des couples (jour ; créneau) déjà réservés pour la salle B12. En SQL, on l'obtient avec un
CROSS JOINsuivi d'unEXCEPT, ou d'unNOT EXISTS.
Tu avais trouvé ?
Exercice 5 sur 5 Une partie de E² Réussi À revoir
Soit E = {1 ; 2 ; 3 ; 4}.
- Combien E² a-t-il d'éléments ? Combien de couples sont sur la diagonale ?
- Écris l'ensemble des couples (x ; y) de E² tels que x < y. Combien y en a-t-il ?
Voir la réponseMasquer la réponse de l'exercice 5
- card(E²) = 4² = 16. La diagonale compte 4 couples : (1 ; 1), (2 ; 2), (3 ; 3), (4 ; 4).
- {(1 ; 2) ; (1 ; 3) ; (1 ; 4) ; (2 ; 3) ; (2 ; 4) ; (3 ; 4)}, soit 6 couples. Contrôle : hors diagonale, il reste 16 − 4 = 12 couples, dont la moitié a x < y et l'autre x > y. Cet ensemble de couples est une relation binaire sur E, la relation « est strictement inférieur à » : c'est l'objet du chapitre suivant.
Tu avais trouvé ?