Chapitre 815 minIntermédiaire
Sujets type situation B (55 minutes) corrigés
Par Josselyn C., prof de BTS SIO. Mis à jour le .
À la fin de ce chapitre, tu sauras
- traiter un sujet de situation B en 55 minutes ;
- enchaîner des questions de difficulté progressive ;
- rédiger un ordonnancement MPM et une simplification booléenne ;
- évaluer ta copie avec le corrigé.
4 exercices corrigés1 schéma
La situation B du CCF de l'E3 est un écrit de 55 minutes, au second semestre de deuxième année, fait d'un ou deux exercices de difficulté progressive sur les modules autres que l'algorithmique. Ce chapitre propose deux sujets complets construits sur ce modèle, avec leurs corrigés rédigés comme sur une copie : le premier sur l'arithmétique et les ensembles, le second sur l'ordonnancement et la logique.
Comment utiliser ces sujets
Sujets d'entraînement construits sur le modèle décrit par le référentiel ; ce ne sont pas des sujets officiels. Ton professeur écrit ses propres sujets, qui peuvent porter sur d'autres modules : le référentiel demande seulement qu'ils couvrent une partie significative des modules autres que l'algorithmique.
Mets-toi en condition : 55 minutes chrono, calculatrice en mode examen, sans le cours. Garde 5 minutes de lecture au début et 5 minutes de relecture à la fin (chapitre 6). Ouvre les corrigés seulement après.
Sujet 1 : identifiants de colis et groupes de l'annuaire
Exercice 1 sur 4 Sujet 1, exercice 1 : les identifiants des colis (10 points) Réussi À revoir
Chaque colis de Sorbier Logistique reçoit un identifiant N, entier codé sur 16 bits et affiché en hexadécimal sur quatre chiffres. Une clé de contrôle k, égale au reste de la division euclidienne de N par 7, est imprimée à côté de l'identifiant.
- Combien d'identifiants différents peut-on coder sur 16 bits ? Quel est le plus grand, en hexadécimal et en base 10 ?
- Écrire l'identifiant (2F4A)₁₆ en base 2, puis en base 10.
- Calculer la clé de l'identifiant (2F4A)₁₆ en posant la division euclidienne.
- Vérifier que 16 ≡ 2 [7], que 256 ≡ 4 [7] et que 4 096 ≡ 1 [7].
- En déduire que, pour un identifiant N = (d₃d₂d₁d₀)₁₆, on a N ≡ d₃ + 4d₂ + 2d₁ + d₀ [7].
- Retrouver la clé de (2F4A)₁₆ avec cette formule.
- Un opérateur saisit (2F43)₁₆ au lieu de (2F4A)₁₆. La clé permet-elle de détecter l'erreur ? Plus généralement, quelles erreurs sur le dernier chiffre la clé ne détecte-t-elle pas ?
Voir la réponseMasquer la réponse de l'exercice 1
- Chaque bit a 2 valeurs : il y a 2¹⁶ = 65 536 identifiants, de 0 à 65 535. Le plus grand est (FFFF)₁₆ = 65 535 = 2¹⁶ − 1.
- Chaque chiffre hexadécimal donne 4 bits : 2 = 0010, F = 1111, 4 = 0100, A = 1010, donc (2F4A)₁₆ = (0010 1111 0100 1010)₂. En base 10 : 2 × 4 096 + 15 × 256 + 4 × 16 + 10 = 8 192 + 3 840 + 64 + 10 = 12 106.
- 12 106 = 7 × 1 729 + 3, avec 0 ≤ 3 < 7. La clé est k = 3.
- 16 = 2 × 7 + 2, donc 16 ≡ 2 [7]. Par compatibilité avec la multiplication, 256 = 16² ≡ 2² = 4 [7] et 4 096 = 16³ ≡ 2³ = 8 ≡ 1 [7].
- N = d₃ × 4 096 + d₂ × 256 + d₁ × 16 + d₀. Les congruences sont compatibles avec l'addition et la multiplication, donc N ≡ d₃ × 1 + d₂ × 4 + d₁ × 2 + d₀ [7].
- Pour (2F4A)₁₆ : 2 + 4 × 15 + 2 × 4 + 10 = 2 + 60 + 8 + 10 = 80, et 80 = 7 × 11 + 3. On retrouve k = 3, sans avoir converti le nombre en base 10.
- Pour (2F43)₁₆ : 2 + 60 + 8 + 3 = 73 = 7 × 10 + 3, la clé vaut aussi 3. L'erreur n'est pas détectée. En général, remplacer le dernier chiffre d₀ par d₀' change N de d₀' − d₀ ; la clé est la même si et seulement si d₀' − d₀ ≡ 0 [7], c'est-à-dire si les deux chiffres diffèrent de 7 ou de 14 (par exemple 3 et A, 0 et 7, 1 et F). Les autres erreurs sur le dernier chiffre sont détectées.
Tu avais trouvé ?
Exercice 2 sur 4 Sujet 1, exercice 2 : les groupes de l'annuaire (10 points) Réussi À revoir
Dans l'annuaire de Sorbier Logistique, chaque salarié a un groupe principal. On note E = {Amel ; Bruno ; Chloé ; David ; Emma ; Farid} un ensemble de salariés, G = {Compta ; Logistique ; Direction ; Informatique} l'ensemble des groupes, et f la fonction de E dans G qui associe à chaque salarié son groupe principal :
| Salarié | Amel | Bruno | Chloé | David | Emma | Farid |
|---|---|---|---|---|---|---|
| Groupe principal | Logistique | Compta | Logistique | Informatique | Logistique | Compta |
- Justifier que f est une application de E dans G. Est-elle injective ? Surjective ? Justifier.
- Déterminer f({Amel ; Bruno ; Chloé}), f⁻¹({Logistique}) et f⁻¹({Direction}).
- On définit sur E la relation R par : x R y si et seulement si f(x) = f(y). Montrer que R est une relation d'équivalence et donner ses classes d'équivalence.
- Chaque groupe a un dossier partagé sur le serveur de fichiers. On note g l'application de G dans l'ensemble D = {COMPTA ; LOGISTIQUE ; DIRECTION ; INFORMATIQUE} des dossiers, qui associe à chaque groupe son dossier. Justifier que g est une bijection. Déterminer g∘f(Emma). L'application g∘f est-elle injective ?
- Chaque salarié peut se connecter de trois façons : T = {poste fixe ; portable ; VPN}. Combien y a-t-il de couples (salarié, façon de se connecter) ? Écrire ceux qui concernent David.
Voir la réponseMasquer la réponse de l'exercice 2
- Chaque élément de E a une et une seule image dans G : f est une application. Elle n'est pas injective : Amel et Chloé, distinctes, ont la même image (Logistique). Elle n'est pas surjective : Direction n'a aucun antécédent.
- f({Amel ; Bruno ; Chloé}) = {Logistique ; Compta} (on ne répète pas Logistique). f⁻¹({Logistique}) = {Amel ; Chloé ; Emma}. f⁻¹({Direction}) = ∅ : aucun salarié de E n'a ce groupe.
- R est réflexive : f(x) = f(x), donc x R x. Elle est symétrique : si f(x) = f(y), alors f(y) = f(x). Elle est transitive : si f(x) = f(y) et f(y) = f(z), alors f(x) = f(z). C'est donc une relation d'équivalence. Ses classes sont les ensembles de salariés de même groupe : {Amel ; Chloé ; Emma}, {Bruno ; Farid} et {David}.
- Chaque dossier de D a exactement un antécédent par g (chaque groupe a son dossier, et chaque dossier appartient à un seul groupe) : g est une bijection. g∘f(Emma) = g(f(Emma)) = g(Logistique) = LOGISTIQUE. g∘f n'est pas injective : g∘f(Amel) = g∘f(Chloé) = LOGISTIQUE. La composée d'une application non injective par une bijection n'est pas injective.
- Le nombre de couples est le cardinal de E × T : 6 × 3 = 18. Pour David : (David ; poste fixe), (David ; portable), (David ; VPN).
Tu avais trouvé ?
Sujet 2 : la migration du stockage
Exercice 3 sur 4 Sujet 2, exercice 1 : ordonnancer la migration (12 points) Réussi À revoir
Sorbier Logistique migre ses partages de fichiers vers un nouveau serveur de stockage TrueNAS. Les tâches, leurs durées en jours et leurs tâches antérieures sont les suivantes.
| Tâche | Description | Durée (jours) | Tâches antérieures |
|---|---|---|---|
| A | Audit des partages existants | 2 | — |
| B | Commande et livraison des disques | 5 | A |
| C | Installation d'une machine de test dans le VLAN 21 APPLIS | 3 | A |
| D | Rédaction de la procédure de migration | 2 | A |
| E | Montage des disques et création des volumes | 2 | B, C |
| F | Migration d'essai sur un partage pilote | 3 | C, D |
| G | Migration de toutes les données | 4 | E, F |
| H | Information et formation des utilisateurs | 2 | F |
| I | Recette et bascule | 1 | G, H |
- Construire le graphe d'ordonnancement du projet selon la méthode MPM.
- Déterminer la date de début au plus tôt de chaque tâche et la durée minimale du projet.
- Déterminer la date de début au plus tard de chaque tâche. En déduire les tâches critiques et le chemin critique.
- Calculer la marge totale et la marge libre des tâches C, D, F et H. Calculer la marge certaine de H et l'interpréter.
- La même technicienne doit réaliser les tâches C et D : elle ne peut pas les mener en même temps. Quelle est alors la durée minimale du projet ? Justifier.
Voir la réponseMasquer la réponse de l'exercice 3
On note t la date de début au plus tôt, T la date de début au plus tard et d la durée, en jours, le projet commençant le jour 0.
Questions 1 et 2. Les dates au plus tôt se calculent dans l'ordre des antériorités : t est le maximum, sur les tâches antérieures p, de t(p) + d(p).
| Tâche | A | B | C | D | E | F | G | H | I |
|---|---|---|---|---|---|---|---|---|---|
| Calcul | 0 | 0 + 2 | 0 + 2 | 0 + 2 | max(2 + 5 ; 2 + 3) | max(2 + 3 ; 2 + 2) | max(7 + 2 ; 5 + 3) | 5 + 3 | max(9 + 4 ; 8 + 2) |
| t | 0 | 2 | 2 | 2 | 7 | 5 | 9 | 8 | 13 |
La fin au plus tôt est t(I) + d(I) = 13 + 1 = 14 : la durée minimale du projet est de 14 jours.
Question 3. Les dates au plus tard se calculent à rebours, à partir de la fin le jour 14 : T est le minimum, sur les tâches suivantes s, de T(s), moins la durée de la tâche.
| Tâche | I | H | G | F | E | D | C | B | A |
|---|---|---|---|---|---|---|---|---|---|
| Calcul | 14 − 1 | 13 − 2 | 13 − 4 | min(9 ; 11) − 3 | 9 − 2 | 6 − 2 | min(7 ; 6) − 3 | 7 − 5 | min(2 ; 3 ; 4) − 2 |
| T | 13 | 11 | 9 | 6 | 7 | 4 | 3 | 2 | 0 |
Les tâches critiques sont celles pour lesquelles t = T : A, B, E, G et I. Le chemin critique est A → B → E → G → I, de durée 2 + 5 + 2 + 4 + 1 = 14 jours.
Question 4. Marge totale MT = T − t ; marge libre ML = min t(s) − t − d, sur les tâches suivantes s.
| Tâche | MT | ML |
|---|---|---|
| C | 3 − 2 = 1 | min(t(E) ; t(F)) − 2 − 3 = 5 − 5 = 0 |
| D | 4 − 2 = 2 | t(F) − 2 − 2 = 5 − 4 = 1 |
| F | 6 − 5 = 1 | min(t(G) ; t(H)) − 5 − 3 = 8 − 8 = 0 |
| H | 11 − 8 = 3 | t(I) − 8 − 2 = 13 − 10 = 3 |
Marge certaine de H : sa seule tâche antérieure F finit au plus tard le jour T(F) + d(F) = 6 + 3 = 9, et sa suivante I commence au plus tôt le jour 13. MC(H) = 13 − 9 − 2 = 2 jours : même si la migration d'essai finit le plus tard possible, la formation des utilisateurs peut encore prendre 2 jours de retard sans décaler le début au plus tôt de la recette.
Question 5. Le graphe ne modélise pas cette contrainte de personnel : il faut placer C et D l'une après l'autre. Si C passe d'abord (jours 2 à 5), D occupe les jours 5 à 7 ; si D passe d'abord (jours 2 à 4), C occupe les jours 4 à 7. Dans les deux cas, F ne peut commencer que le jour 7 et finit le jour 10, G commence le jour max(9 ; 10) = 10 et finit le jour 14, et I finit le jour 15. La durée minimale devient 15 jours, un jour de plus. Le décalage dépasse la marge disponible : si C passe d'abord, D prend 3 jours de retard pour une marge totale de 2 ; si D passe d'abord, C prend 2 jours de retard pour une marge totale de 1.
Tu avais trouvé ?
Exercice 4 sur 4 Sujet 2, exercice 2 : les accès au partage (8 points) Réussi À revoir
On définit trois variables booléennes pour une connexion au partage LOGISTIQUE : a vaut 1 si l'utilisateur appartient au groupe Logistique, b vaut 1 s'il se connecte depuis le VLAN POSTES, c vaut 1 s'il a validé la double authentification. L'accès est autorisé dans trois cas, et seulement dans ceux-là :
-
un membre du groupe qui a validé la double authentification ;
-
un membre du groupe connecté depuis le VLAN POSTES sans double authentification ;
-
un non-membre connecté depuis le VLAN POSTES qui a validé la double authentification.
- Écrire l'expression booléenne E qui vaut 1 quand l'accès est autorisé.
- À l'aide d'un tableau de Karnaugh, écrire E sous la forme d'une somme de trois termes de deux variables.
- Traduire le résultat par une phrase courte.
- Exprimer Ē par une somme de trois termes et l'interpréter.
- Sur les 120 connexions d'une journée, 70 viennent de membres du groupe Logistique, 85 du VLAN POSTES, et 50 de membres du groupe connectés depuis le VLAN POSTES. Combien de connexions viennent d'un membre du groupe ou du VLAN POSTES ? Combien ne remplissent aucune de ces deux conditions ?
- On note p(x) : « la connexion x vient du VLAN VISITEURS » et q(x) : « la connexion x est refusée ». Écrire avec un quantificateur la règle « toute connexion venant du VLAN VISITEURS est refusée », puis sa négation, en langage courant.
Voir la réponseMasquer la réponse de l'exercice 4
- E = ac + abc̄ + ābc.
- Tableau de Karnaugh, a en lignes, bc en colonnes dans l'ordre 00, 01, 11, 10 :
| a \ bc | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 1 | 1 |
Trois regroupements de deux cases : colonnes 01 et 11 de la ligne a = 1, soit ac ; colonnes 11 et 10 de la ligne a = 1, soit ab ; colonne 11 des deux lignes, soit bc. Donc E = ab + ac + bc. 3. L'accès est autorisé quand au moins deux des trois conditions sont remplies. 4. Les 0 du tableau se regroupent en ā b̄ (colonnes 00 et 01 de la ligne a = 0), ā c̄ (colonnes 00 et 10 de la ligne a = 0, voisines par le bord) et b̄ c̄ (colonne 00 des deux lignes) : Ē = āb̄ + āc̄ + b̄c̄. L'accès est refusé quand au plus une des trois conditions est remplie. 5. On note L l'ensemble des connexions de membres du groupe et V celui des connexions depuis le VLAN POSTES : card(L ∪ V) = card(L) + card(V) − card(L ∩ V) = 70 + 85 − 50 = 105. Les connexions qui ne remplissent aucune des deux conditions forment le complémentaire de L ∪ V : 120 − 105 = 15. 6. La règle s'écrit ∀x, p(x) ⇒ q(x). Sa négation est ∃x, p(x) et non q(x) : « il existe une connexion venant du VLAN VISITEURS qui n'a pas été refusée ».
Tu avais trouvé ?