Aller au contenu

Exercices – Relations et applications

BTS SIO SISR 1re année – Mathématiques pour l'informatique – S11

Note

Comment travailler. Cherche d'abord sur papier, avec la méthode du cours : écris les étapes, pas seulement le résultat. Ouvre ensuite « Voir la réponse » pour te corriger. À l'épreuve, aucune réponse sans justification n'est complète.

Exercice 1 – Produit cartésien

  1. Écrire \(A \times B\) pour \(A = \{1, 2, 3\}\) et \(B = \{x, y\}\), puis \(B \times A\). Sont-ils égaux ?
  2. Un pare-feu a 3 protocoles (TCP, UDP, ICMP) et 4 ports à considérer. Combien de couples (protocole, port) ?
  3. Combien d'éléments a \(A \times B \times C\) pour \(\lvert A \rvert = 3\), \(\lvert B \rvert = 2\), \(\lvert C \rvert = 5\) ?
Voir la réponse
  1. \(A \times B = \{(1, 'x'), (1, 'y'), (2, 'x'), (2, 'y'), (3, 'x'), (3, 'y')\}\) ; \(B \times A = \{('x', 1), ('x', 2), ('x', 3), ('y', 1), ('y', 2), ('y', 3)\}\). Ils ne sont pas égaux (le couple \((1, x)\) n'est pas le couple \((x, 1)\)), mais ils ont le même nombre d'éléments : 6.
  2. \(3 \times 4 = 12\).
  3. \(3 \times 2 \times 5 = 30\).

Exercice 2 – Propriétés de relations

Sur \(E = \{1, 2, 3, 4\}\), étudier les propriétés (réflexive, symétrique, antisymétrique, transitive) de : (a) \(x \le y\) ; (b) \(x\) divise \(y\) ; (c) \(x + y\) pair ; (d) \(x \neq y\) ; (e) \(\mathcal{R} = \{(1,1), (2,2), (3,3), (1,2), (2,1)\}\) sur \(\{1, 2, 3\}\).

Voir la réponse
Relation Réflexive Symétrique Antisymétrique Transitive Nature
(a) \(x \le y\) oui non oui oui ordre
(b) \(x\) divise \(y\) oui non oui oui ordre
(c) \(x+y\) pair oui oui non oui équivalence
(d) \(x \neq y\) non oui non non —
(e) \(\mathcal{R}\) oui oui non oui équivalence

Contre-exemples : (d) non transitive, car \(1 \neq 2\) et \(2 \neq 1\) mais \(1 = 1\) ; (e) non antisymétrique, car \((1,2)\) et \((2,1)\) sont dans \(\mathcal{R}\) avec \(1 \neq 2\).

Exercice 3 – Classes d'équivalence

Sur \(E = \{1, \dots, 10\}\), on pose \(x \sim y\) si \(x - y\) est un multiple de 3.

  1. Montrer que \(\sim\) est une relation d'équivalence.
  2. Donner ses classes.
Voir la réponse
  1. Réflexive : \(x - x = 0 = 3 \times 0\). Symétrique : si \(x - y = 3k\), alors \(y - x = 3(-k)\). Transitive : si \(x - y = 3k\) et \(y - z = 3l\), alors \(x - z = 3(k + l)\).
  2. \(\{1, 4, 7, 10\}\) ; \(\{2, 5, 8\}\) ; \(\{3, 6, 9\}\) — trois classes (restes 1, 2, 0 dans la division par 3), de tailles 4, 3, 3.

Exercice 4 – Ordre et diagramme de Hasse

On considère la divisibilité sur \(E = \{1, 2, 3, 4, 6, 8, 12, 24\}\).

  1. Montrer que c'est une relation d'ordre. Est-il total ?
  2. Dessiner le diagramme de Hasse.
  3. Quels sont le plus petit et le plus grand élément ? Trouver deux éléments non comparables.
Voir la réponse
  1. Réflexive (\(x\) divise \(x\)) ; antisymétrique (si \(x \mid y\) et \(y \mid x\) alors \(x = y\), entiers positifs) ; transitive (\(y = kx\) et \(z = ly\) donnent \(z = (kl)x\)). Pas total : 2 ne divise pas 3, et 3 ne divise pas 2.
  2. Arêtes de couverture : 1→2, 1→3, 2→4, 2→6, 3→6, 4→8, 4→12, 6→12, 8→24, 12→24.
1 2 3 4 6 8 12 24
  1. Plus petit : 1 ; plus grand : 24. Non comparables : 2 et 3, ou 8 et 12.

Exercice 5 – Application ou non ?

Les relations suivantes vont de \(A = \{1, 2, 3\}\) vers \(B = \{a, b, c\}\). Lesquelles sont des applications ?

  • \(\mathcal{R}_1 = \{(1,a), (2,b), (3,c)\}\)
  • \(\mathcal{R}_2 = \{(1,a), (1,b), (2,c), (3,c)\}\)
  • \(\mathcal{R}_3 = \{(1,a), (3,b)\}\)
Voir la réponse
  • \(\mathcal{R}_1\) : application (chaque élément de \(A\) a exactement une image).
  • \(\mathcal{R}_2\) : pas une application : 1 a deux images (\(a\) et \(b\)).
  • \(\mathcal{R}_3\) : pas une application : 2 n'a aucune image.

Exercice 6 – Injective, surjective, bijective

Pour chaque application donnée par sa table, dire si elle est injective, surjective, bijective.

(a) \(f : \{1,2,3,4\} \to \{a,b,c\}\) : | \(x\) | 1 | 2 | 3 | 4 | |---|---|---|---|---| | \(f(x)\) | a | b | a | c |

(b) \(g : \{1,2,3,4\} \to \{a,b,c,d\}\) : | \(x\) | 1 | 2 | 3 | 4 | |---|---|---|---|---| | \(f(x)\) | a | b | c | d |

(c) \(h : \{1,2,3\} \to \{a,b,c,d\}\) : | \(x\) | 1 | 2 | 3 | |---|---|---|---| | \(f(x)\) | a | b | c |

Voir la réponse

(a) surjective : \(a\) a deux antécédents (1 et 3), donc pas injective ; tous les éléments de \(B\) sont atteints. (b) bijective : les quatre images sont distinctes et couvrent \(B\). (c) injective : images distinctes, mais \(d\) n'est pas atteint.

Exercice 7 – Applications numériques

Dire si les applications sont injectives, surjectives, bijectives ; si oui, donner la réciproque.

(a) \(f : \mathbb{R} \to \mathbb{R},\ x \mapsto 3x - 2\) ; (b) \(g : \mathbb{Z} \to \mathbb{Z},\ n \mapsto n + 4\) ; (c) \(h : \mathbb{Z} \to \mathbb{Z},\ n \mapsto 2n\) ; (d) \(k : \mathbb{R} \to \mathbb{R},\ x \mapsto x^2\).

Voir la réponse

(a) Bijective : \(y = 3x - 2 \iff x = \dfrac{y + 2}{3}\), donc \(f^{-1}(y) = \dfrac{y + 2}{3}\) (tout réel \(y\) a un unique antécédent). (b) Bijective : \(g^{-1}(m) = m - 4\). (c) Injective (si \(2n = 2n'\), alors \(n = n'\)) mais pas surjective (3 n'a pas d'antécédent dans \(\mathbb{Z}\)). (d) Ni injective (\(k(2) = k(-2) = 4\)), ni surjective (\(-1\) n'a pas d'antécédent). Restreinte à \(\mathbb{R}_+ \to \mathbb{R}_+\), elle devient bijective, de réciproque \(\sqrt{\ }\).

Exercice 8 – Composition

Soient \(f(x) = 2x + 1\) et \(g(x) = x^2\) sur \(\mathbb{R}\). Calculer \(g \circ f\) et \(f \circ g\), puis leurs valeurs en \(x = 3\). Ces applications sont-elles égales ?

Voir la réponse

\((g \circ f)(x) = g(2x + 1) = (2x + 1)^2 = 4x^2 + 4x + 1\) ; \((f \circ g)(x) = f(x^2) = 2x^2 + 1\). En \(x = 3\) : 49 et 19. Elles ne sont pas égales : la composition n'est pas commutative.

Exercice 9 – Images directes et réciproques

Soit \(f : \{0, \dots, 9\} \to \{0, \dots, 4\}\), \(f(x) = x \bmod 5\). Calculer \(f(\{2, 7, 9\})\), \(f^{-1}(\{3\})\), \(f^{-1}(\{0, 4\})\), \(f^{-1}(\{5\})\).

Voir la réponse

\(f(\{2,7,9\}) = \{2, 4\}\) ; \(f^{-1}(\{3\}) = \{3, 8\}\) ; \(f^{-1}(\{0,4\}) = \{0, 4, 5, 9\}\) ; \(f^{-1}(\{5\}) = \varnothing\) (5 n'est pas dans l'ensemble d'arrivée).

Exercice 10 – Collisions

Une fonction de hachage associe à un identifiant (parmi 20) un numéro de case entre 0 et 7.

  1. Peut-elle être injective ? Pourquoi ?
  2. Montrer qu'une case au moins reçoit trois identifiants.
  3. Combien y a-t-il d'applications possibles de 3 éléments vers 4 éléments ? Parmi elles, combien d'injections ?
Voir la réponse
  1. Non : 20 identifiants pour 8 cases (principe des tiroirs).
  2. Si chaque case en recevait au plus 2, on aurait au plus \(8 \times 2 = 16 < 20\) identifiants : contradiction. Au moins \(\lceil 20 / 8 \rceil = 3\) identifiants sont dans la même case.
  3. \(4^3 = 64\) applications ; injections : \(4 \times 3 \times 2 = 24\) (le premier élément a 4 choix, le suivant 3, le dernier 2).

Je sais faire

Coche honnêtement ; ce que tu ne coches pas se reprend avant la séance suivante.

  • Calculer le cardinal d'un produit cartésien ;
  • Tester les propriétés d'une relation finie ;
  • Trouver les classes d'une relation d'équivalence ;
  • Décider si une application est injective, surjective, bijective ;
  • Composer deux applications.

Ce que je dois reprendre : ______________________

Ma question à poser à l'enseignant : ______________________