INFO SUJET BTS SIO 2017

      SUJET BTS SIO   jeudi 11 mai 2017   Maths pour l'informatique  

              (  Brevet de technicien supérieur Métropole : épreuve obligatoire )

  EXERCICE 1      8 points   

      Cet exercice envisage deux problèmes relatifs à l’équipement d’une salle

       informatique d’une entreprise. Les deux parties sont indépendantes.

   PARTIE 1 : Choix d’un réseau
     Le réseau informatique qui équipera la salle doit satisfaire au moins

     l’une des conditions suivantes :
          • le réseau compte 5 postes ou plus et il existe un poste qui ne reçoit pas de
            données en entrée.
          • il existe un poste qui ne reçoit pas de données en entrée, et le réseau compte
            strictement moins de 5 postes, et il comporte strictement plus de 12 connexions.
          • le réseau comporte 12 connexions ou moins.
     On définit les variables booléennes suivantes :
          • a = 1 si le réseau compte 5 postes ou plus, a = 0 sinon .
          • b = 1 s’il existe un poste qui ne reçoit pas de données en entrée, b = 0 sinon .
          • c = 1 si le réseau comporte 12 connexions ou moins, c = 0 sinon.
  1. Cette question est une question à choix multiple.

    Une seule réponse est correcte.

    Recopier sur la copie seulement la réponse correcte.

   On ne demande pas de justification.
      Parmi les quatre phrases suivantes, donner celle qui traduit la variable   :
      — réponse A : « il existe un poste qui reçoit des données en entrée » ;
      — réponse B : « tout poste reçoit des données en entrée » ;
      — réponse C : « il existe un poste qui envoie des données en sortie » ;
      — réponse D : « aucun poste ne reçoit des données en entrée ».

       REPONSE: 

            Le contraire de il existe un poste (  sous entendu au moins ) qui ne reçoit pas

           de données en entrée est: tout poste reçoit des données en entrée

        Conclusion : Réponse B.
   2. Donner l’expression booléenne E traduisant les critères voulus pour un réseau
       informatique.

         REPONSE:

            Traduisons chaque condition suffisante:

           a.b • le réseau compte 5 postes ou plus et il existe un poste qui ne reçoit pas de
                   données en entrée.
     • il existe un poste qui ne reçoit pas de données en entrée, et le réseau compte
                   strictement moins de 5 postes, et il comporte strictement plus de 12 connexions.
            c    • le réseau comporte 12 connexions ou moins. 

          Conclusion : 

                       
   3. À l’aide d’un tableau de Karnaugh ou par des calculs, exprimer E comme somme
       de deux variables booléennes.

          REPONSE:

            Tableau de Karnaugh:

            Ainsi :    E = b + c 

                Conclusion:  E = b + c
   4. Traduire les critères de sélection simplifiés, à partir de l’expression obtenue à
       la question 3.

          REPONSE:

          Conclusion : Le réseau devra disposer d'un poste qui ne reçoit pas de données en entrée

                                ou " le réseau doit avoir 12 connexions ou "
   5. Un réseau dans lequel 2 postes ne reçoivent pas de données en entrée et qui
       comporte 15 connexions répond-il aux critères voulus ? Justifier la réponse.

          REPONSE:

             Un tel réseau respecte le critère b , même si le critère c n'est pas respecté.

           Cela suffit pour acceptation  car on a  E vrai. 

             Conclusion: Il correspond aux critères voulus.
 

   PARTIE 2 : Étude des connexions
       La salle informatique doit comprendre cinq postes numérotés de 1 à 5 
       et branchés en réseau selon le graphe orienté ci-contre.
       Dans ce graphe, une flèche d’un poste A vers un poste
       B traduit le fait que l’on peut envoyer des données de A vers B.
           

     Remarque: Il semble que la boucle en 1 ne figure pas dans le sujet officiel alors que dans 

      l'APMEP  il y a cette boucle. Auquel cas cela supprime un 1 à la premère ligne et première colonne.

      1. Donner la matrice d’adjacence M de ce graphe
          en prenant les numéros des postes dans l’ordre croissant.

          REPONSE:

          On a  11 arcs . Chacun correspond à  un arc.

           Ainsi la matrice d'adjacence M est:  

                                    
      2. Déterminer la matrice M̂ de la fermeture transitive de ce graphe.

          REPONSE:

             On a :

            La matrice de la fermeture transitive est obtenu en rajoutant  dans M

           les 1 qui correspondent à des arcs de raccourcis.

          On peut aussi l'obtenir avec une somme booléene .

        Ainsi :

        
      3. Pour permettre l’envoi de données entre les postes, même en cas de défaillance
          d’une connexion on utilise la fermeture transitive du graphe.
           Dessiner sur la copie le graphe correspondant à cette fermeture transitive.

          REPONSE:

      EXERCICE  2         7 points
      Le but de cet exercice est d’étudier, sur des exemples numériques simples,
      deux variantes d’une méthode de cryptage inventée par Gilbert Vernam en 1917, 
     et appelée« masque jetable ».
     Dans tout l’exercice, on note respectivement M le mot initial, K la clé de cryptage etY le mot crypté.
     Les trois nombres M, K, Y sont des entiers naturels.
     Les deux parties de cet exercice sont indépendantes
     PARTIE 1 : Masque jetable
     La méthode décrite dans cette partie utilise le connecteur logique « xor », appelé « ou
      exclusif », qui est défini par la table de vérité suivante :

    Par exemple les deux premières lignes signifient que 0 xor 0 = 0 et que 0 xor 1 = 1.
   1. Recopier intégralement la table de vérité ci-après et compléter la dernière colonne.

     2. Parmi les quatre propositions P, Q, (P xor Q) et ((P xor Q) xor Q), deux sont
         équivalentes.
        À l’aide de la table 2 complétée, déterminer lesquelles, en expliquant la ré-
        ponse.
        Dans la suite de l’exercice, on note a_b l’écriture du nombre entier a en base b.

       REPONSE:

         La première et la dernière colonnes sont identiques.

      Conclusion : P   équivaut à ( P xor Q) xor Q
    3. Donner la représentation binaire de l’entier qui s’écrit 26₁₀ en décimal.

         REPONSE:

           26 =16 + 8 + 2=  2⁴  + 2³ + 2   = 1× 2⁴  + 1 ×  2³ + 0 × 2² + 1 × 2¹ + 0 × 2⁰ 

            Conclusion  :  26₁₀ = 1110₂
    4. Soit M et K deux entiers naturels écrits en binaire, tels que la longueur de
        l’écriture de K est supérieure ou égale à celle de M.
        Pour crypter le mot M avec la clé K, on procède comme suit : pour chaque
        chiffre m du mot initial M, on considère le chiffre k de la clé K qui a la même
        position que m dans l’écriture.
        On obtient alors le chiffre y du mot crypté Y qui a la même position que m
        dans l’écriture du mot initial M, par la relation : y = m xor k.
        L’écriture binaire du mot crypté Y est la juxtaposition dans le même ordre des
        chiffres y calculés pour chaque chiffre m du mot M.      

         Question : avec le mot initial M = 011₂ et la clé K = 101₂, déterminer le mot crypté Y .
          REPONSE:

               M=  011₂        K=101₂

           De la droite  vers la gauche:

         •   On a:   m = 1   k = 1    donc    m xor k = 0

         •   On a:   m = 1    k = 0    donc    m xor k = 1

          •   On a:   m = 0    k = 1      donc    m xor k = 1

             Conclusion:  M est codé  Y =110₂

      Remarque : d’après la question 2, le décryptage s’effectue de la même manière que
        le cryptage.
          PARTIE 2 : Masque jetable hexadécimal
       Cette partie envisage le cryptage de nombres entiers écrits dans le système hexadé-
       hexadécimal.
        Les chiffres hexadécimaux sont notés 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F.
        1. Questions préliminaires
             a. Donner la représentation en hexadécimal de l’entier binaire 1011101₂ .
            REPONSE:

            On a  en complétant par un 0 à gauche:

                1011101₂ = 0101 1101₂

              Or   0101₂ = 2² + 2⁰  = 5₁₀ =5₁₆

             et     1101₂ = 2³+ 2² + 2⁰  =13₁₀ = D₁₆

              Conclusion :    1011101₂ = 5D₁₆

          b. Calculer en travaillant dans le système hexadécimal les sommes 7₁₆+4₁₆
                et A₁₆ +C₁₆.
             REPONSE:

              •  On a :   7₁₆  + 4₁₆ = B₁₆        car    7₁₆ + 4₁₆ = 11₁₆ = B₁₆

              •  On a :  A₁₆ +C₁₆  = 16₁₆         car   A₁₆ + C₁₆  = 10 + 12 = 22 = 16 + 6 = 1 × 16¹ + 6 × 16⁰

     2. Soit M et K deux entiers naturels écrits en hexadécimal, tels que la longueur
            de l’écriture de K est supérieure ou égale à celle de M, et tels que l’écriture de
            K ne comporte aucun chiffre 0.
            Pour crypter le mot M avec la clé K, on procède comme suit : pour chaque
            chiffre m du mot initial M, on considère le chiffre k de la clé K qui a la même
             position que m dans l’écriture.
             On obtient alors le chiffre y du mot crypté Y qui a la même position que m
            dans l’écriture du mot initial M, de la façon suivante : y est le chiffre hexadé-
            cimal des unités de la somme m +k.
            Le mot crypté Y est déterminé en hexadécimal par la juxtaposition dans le
            même ordre des chiffres y calculés pour chaque chiffre m du mot M.
 

         Donc le mot crypté est Y = 52₁₆ .
         Question : avec le mot initial M = 7A₁₆ et la clé K = 4C₁₆ , déterminer le mot
                               crypté Y .
          REPONSE:

             On a :           M = 7A₁₆          K = 4C₁₆  

           •   m = A        k = C       m + k = A₁₆ + C₁₆ = 16₁₆    Déjà vu  y = 16

           •   m = 7      k = 4       m + k =7₁₆ + 4₁₆  = B₁₆      Déjà vu    y = B

           Ainsi :

             Conclusion:    M est codé Y = B16₁₆

          3. Par cette méthode, on admet que le décryptage suit les mêmes étapes
               en remplaçant la clé K par une autre clé K′  . Lorsque l’écriture de K comporte au
              maximum deux chiffres hexadécimaux, la clé K′  est l’écriture en hexadécimal
              de la différence (écrite en décimal) 272₁₀ − K₁₀.
             Cette question est une question à choix multiple. Une seule réponse est exacte.
             Recopier sur la copie seulement la réponse exacte. On ne demande pas de justification.
             Avec la clé de cryptage K = 19₁₆, la clé de décryptage K′  est égale à :

             Réponse A :     253₁₆                     Réponse B :    247₁₆      
             Réponse C :     FD₁₆                       Réponse D :     F7₁₆    

        REPONSE:

         La bonne réponse est :

            Réponse D    La clé K ' est   F7₁₆   

          Explications non demandées:

           On a  K = 19₁₆

          K a donc au maximum deux chiffres en hexadécimal.

        On considère  K ' qui vaut  272₁₀ − K₁₀   en hexadécimal.( expression confuse )

        On a :   K = 19₁₆   = 1 ×  16 + 9 = 25₁₀  

        Ainsi :     272₁₀ − K₁₀   =   272₁₀ − 25₁₀  = 247₁₀  

        Mais :  247₁₀  = 15 × 16¹ + 7 × 16⁰ =  F7₁₆  

           Ainsi   K ' = F7₁₆  

      EXERCICE  3            5 points
 

         Pour effectuer des calculs, un ordinateur représente les nombres en binaire. Cet
         exercice étudie l’effet d’une perte de précision initiale sur une suite de calculs.
         Dans tout l’exercice, on note ab l’écriture du nombre a en base b.
      1. Représentation binaire de quelques nombres décimaux
            a. Cette question est une question à choix multiple. Une seule réponse la
               copie seulement la réponse exacte. On ne demande pas de justification.
               La représentation binaire du nombre qui s’écrit en décimal 15,5₁₀ est :

                Réponse A :         10101,101₂               Réponse B :      1111,1₂
                Réponse C :        1111,0101₂               Réponse D :       10101,1₂

             REPONSE: 

                      La bonne réponse est  B :    1111,1₂
             Explication non demandée.

            •  Déjà :    15₁₀ =  8 + 4 + 2 + 1 = 2³ + 2² + 2¹ + 2⁰

             Donc :    15₁₀ =  1111₂

            Cela permet d'éliminer les réponses A et D.

            •   De plus:   0,5₁₀ = 1 / 2  =  1 ×  2 ⁻¹

                                   0,5₁₀ = 0,1₂   

                  Le 5 à droite de la virgule en système décimal devient un 1 à droite de la virgule en binaire

                 15,5₁₀ = 2³ + 2² + 2¹ + 2⁰  +  2 ⁻¹  = 1111,1₂

                Donc après la virgule en binaire on doit avoir un 1.

                 Cela élimine la réponse C.

               Il ne reste plus que la réponse B.

      b. Justifier que le nombre décimal 15,625₁₀ a pour représentation binaire
               1111,101₂ .
           REPONSE:

          Déjà on a vu:          15₁₀ = 1111₂   

           De plus :    0,625₁₀  = 0,5 + 0,125 = 1 × 2 ⁻¹ + 0 × 2 ⁻² + 1 ×  2 ⁻³  

                Ainsi :       0,625₁₀  = 0,101₂

               Conclusion : On a bien  15,625₁₀ = 1111,,101₂

         2. On considère la suite géométrique (u_n) de terme initial u₀ = 32 et de raison
             15,625.
             a. Calculer la valeur exacte de u₁.
              REPONSE:

                On a :  u₁ = 32 × 15,625 = 500

                Conclusion:   u₁ = 500

           b. Donner l’expression de u_n en fonction de n.

              REPONSE:

              On a :

                        Conclusion: u_n = 32  15,625ⁿ     pour tout entier naturel n.
        3. Pour calculer les termes de la suite (u_n), on utilise un logiciel qui arrondit
             le nombre 15,62 et le transforme en 15,5. L’arrondi se répercute sur tous les
             termes calculés. qui sont alors ceux de la suite géométrique (v_n) qui a le même
              terme initial que la suite (u_n) c’est-à-dire v₀ = u₀ = 32, et dont la raison est
               égale à 15,5.
              Ainsi, par exemple, v₁ = 496.
               Pour tout entier naturel n, on définit la perte de précision relative en sur le
               n-ième terme par la relation :
                   e_n = v_n  / u_n   .
             a. Démontrer que la suite (e_n) est la suite géométrique de terme initial
                  e₀ = 1 et de raison 0,992.

                  REPONSE :

                 On a :  v_n = 32   × 15,5ⁿ    pour tout entier naturel n 

                             u₀ = v₀ = 32       

               Donc  :  e₀ = 32 / 32 = 1

               On a bien déjà :   e₀ = 1

               De plus :  

            Soit n un entier naturel quelconque .

            On a : e_n = v_n  / u_n    = (32   × 15,5ⁿ    ) / ( 32   × 15,625ⁿ   ) = 15,5ⁿ    / 15,625ⁿ  

                 Ainsi :       e_n = ( 15,5 / 15,625 )ⁿ    pour tout entier naturel n     

                15,5 / 15,625 ≈ 0,992    en arrondissant 

                   Conclusion:  la suite (e_n) est la suite géométrique de terme initial
                  e₀ = 1 et de raison 0,992.
             b. Déterminer le plus petit entier naturel n tel que e_n < 0,9.

                REPONSE:

                 C'est  n = 14 

                En effet :

                      Imposons : e_n < 0,9

                       c-à-d          0,992ⁿ < 0,9

                      cà)-d      ln (0,992ⁿ ) < ln(0,9)

                     c-à-d     n ×  ln( 0,992 ) < ln( 0,9 )

                      c-à-d    n >  (  ln( 0,9 )  ) /  ln( 0,992 )

                     Mais        (  ln( 0,9 )  ) /  ln( 0,992 ) ≈ 13,11

                    Donc le plus petit n est 14 

                      --------------------------------------------

                                               ------------------------