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  
Non b :
      — 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.
   
Mcer4  • 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 : 

                       Mac2017
   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:

a \   b c   0 0  0 1   1 1  1 0 
  0     1  1     1  
  1     1   1     1  

            Ainsi :    E = b +

                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.
           Cal7

     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:  

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

          REPONSE:

             On a :

           Cal6

            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 :

        Cal9
      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:

      Cal8


      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 :

  P     Q    P xor Q   
0 0 0  
0 1 1  
1 0 1  
1 1 0  

    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.

   P       Q     Pxor Q   P xor Q ) xor Q   
0 0 0      0
0 1 1      0
1 0 1      1
1 1 0      1

     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 ab 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 2610 en décimal.

         REPONSE:

           26 =16 + 8 + 2=  24  + 2+ 2   = 1× 24  + 1 ×  2+ 0 × 22 + 1 × 21 +× 20 

            Conclusion  :  2610 = 11102
    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.      

    Exemple :      avec M = 012 et K = 102
             — Avec le chiffre de rang 1 en partant de la droite : m = 1 et k = 0 ; donc y = 1 xor 0 = 1. 
             — avec le chiffre de rang 2 : m = 0 et k = 1 ; donc y = 0 xor 1 = 1.
            Donc le mot crypté est Y = 112
          


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

               M=  0112        K=1012

           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 =1102

      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 10111012 .

            REPONSE:

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

                10111012 = 0101 11012

              Or   01012 = 2+ 2 = 510 =516

             et     11012 = 23+ 2+ 2 =1310 = D16

              Conclusion :    10111012 = 5D16

          b. Calculer en travaillant dans le système hexadécimal les sommes 716+416
                et A16 +C16.
             REPONSE:

              •  On a :   716  + 416 = B16        car    716 + 416 = 1116 = B16

              •  On a :  A16 +C16  = 1616         car   A16 + C16  = 10 + 12 = 22 = 16 + 6 = 1 × 161 + 6 × 160

     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.
 

       Exemple : avec M = 4916 et K = 1916
— Avec le chiffre de rang 1 en partant de la droite : m = 9 et k = 9 ; donc    
      m +k = 1216 et par suite y = 2 ;
— avec le chiffre de rang 2 : m = 4 et k = 1 ; donc m +k = 516 et par suite
       y = 5.
     

         Donc le mot crypté est Y = 5216 .
         Question : avec le mot initial M = 7A16 et la clé K = 4C1, déterminer le mot
                               crypté Y .

          REPONSE:

             On a :           M = 7A16          K = 4C16  

           •   m = A        k = C       m + k = A16 + C16 = 1616    Déjà vu  y = 16

           •   m = 7      k = 4       m + k =716 + 416  = B16      Déjà vu    y = B

           Ainsi :

             Conclusion:    M est codé Y = B1616

          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) 27210 − K10.
             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 = 1916, la clé de décryptage K′  est égale à :


             Réponse A :     25316                     Réponse B :    24716      
             Réponse C :     FD16                       Réponse D :     F716    

        REPONSE:

         La bonne réponse est :

            Réponse D    La clé K ' est   F716   

          Explications non demandées:

           On a  K = 1916

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

        On considère  K ' qui vaut  27210 − K10   en hexadécimal.( expression confuse )

        On a :   K = 1916   = 1 ×  16 + 9 = 2510  

        Ainsi :     27210 − K10   =   27210 − 2510  = 24710  

        Mais :  24710  = 15 × 161 + 7 × 160 =  F716  

           Ainsi   K ' = F716  

      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,510 est :


                Réponse A :         10101,1012               Réponse B :      1111,12
                Réponse C :        1111,01012               Réponse D :       10101,12

             REPONSE: 

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

            •  Déjà :    1510 =  8 + 4 + 2 + 1 = 23 + 22 + 21 + 20

             Donc :    1510 =  11112

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

            •   De plus:   0,510 = 1 / 2  =  1 ×  −1

                                   0,510 = 0,12   

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

                 15,510 = 23 + 22 + 21 + 20   −1  = 1111,12

                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,62510 a pour représentation binaire
               1111,1012 .

           REPONSE:

          Déjà on a vu:          1510 = 11112   

           De plus :    0,62510  = 0,5 + 0,125 = 1 × −1 + 0 × −2 + 1 ×  −3  

                Ainsi :       0,62510  = 0,1012

               Conclusion : On a bien  15,62510 = 1111,,1012

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

                On a :  u1 = 32 × 15,625 = 500

                Conclusion:   u1500

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

              REPONSE:

              On a :

                        Conclusion: un = 32  15,625n     pour tout entier naturel n.
        3. Pour calculer les termes de la suite (un), 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 (vn) qui a le même
              terme initial que la suite (un) c’est-à-dire v0 = u0 = 32, et dont la raison est
               égale à 15,5.
              Ainsi, par exemple, v1 = 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 :
                   en = vn  /
 un   .
             a. Démontrer que la suite (en) est la suite géométrique de terme initial
                  e0 = 1 et de raison 0,992.

                  REPONSE :

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

                             u= v0 = 32       

               Donc  :  e0 = 32 / 32 = 1

               On a bien déjà :   e0 = 1

               De plus :  

            Soit n un entier naturel quelconque .

            On a : en = vn  / un    = (32   × 15,5n    ) / ( 32   × 15,625n   ) = 15,5n    / 15,625n  

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

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

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

                REPONSE:

                 C'est  n = 14 

                En effet :

                      Imposons : en < 0,9

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

                      cà)-d      ln (0,992n ) < 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 

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

 

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