INFO DS BTS1B 10 AVRIL 09

 INFO  DS   BTS1 B   10 AVRIL 2009 

    EXERCICE  1

         1.  Résoudre dans IR3   le système  linéaire suivant.

   2     x +     y +     z  =  0          L1                         
                    5 y - 7 z =  8          L2  
                            3 z  = 3          L3   

     Le système est déjà triangulaire. 

         L3    donne    3 z = 3

                     c-à-d  z = 1

        Puis  L2   donne   5 y = 8 + 7 z =  15

                          c-à-d  y = 3

        Enfin  L1   donne 2 x = - y - z = - 3 - 1

                       c-à-d     x = 2

        Conclusion : S = { ( - 2 , 3, 1 ) }

        2.  Triangulariser le système puis le résoudre.

        x +   2  y +     z  =  0         L1                           
        x  +  y  +  4 z         =  4          L2 
         x-  y - z = 1           L3   

  Considérons         L3   ←   L2 -   L1           et           L3   ←  L3  -  L1             

 Le système s'écrit :       

        x +   2  y +     z  =  0         L1                           
                    - y  +  3 z         =  4          L2 
                   -  3 y - 2 z = 1           L3   

 Considérons :    L3   ←  L3  - 3 L2     

    Le système s'écrit :       

        x +   2  y +     z  =  0         L1                           
                    - y  +  3 z         =  4          L2 
                             - 11 z = -11       L3   

 L3      donne  z = 1

Puis    L2     donne   y = 3 z - 4 = 3 - 4 = - 1

                      c-à-d     y = - 1

 Enfin   L1     donne  x = - 2 y - z  = - 2 ( - 1 ) - 1 = 1

                    c-à-d    x = 1

      Conclusion : S = { ( 1 , - 1 , 1 ) }

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

      EXERCICE 2             

         Soit les matrices : 

   /  0     1  -1  \
M = |  -3     4  -3   |
   \ -1     1   0  /

 

  

   /  1     0   0  \
I = |   0     1   0   |
   \  0     0   1  /

   1. Calculer M2 et M3 .       

   /  - 2     3  - 3  \
M² = |    -9     10  - 9    |
   \  -3     3  - 2  /

 

   /  - 6     7    -7  \
M3 = |  -21     22  -21   |
   \   -7     7   - 6  /

                          

   2. Déterminer les réels a et b tels que  M2 = a M + b I .

 

 On a :

   /    b     a  - a   \
a M + b I = |    -3 a     4 a + b  - 3 a  |
   \  - a     a     b   /

et

   /  - 2     3  - 3  \
M² = |    -9     10  - 9    |
   \  -3     3  - 2  /

    Ainsi :    M2 = a M + b I . 

   entraîne   :  b = - 2     et    a = 3   en  considérant  les deux premiers termes

   de la première ligne.

   Conclusion :  a = 3       b = -  2     

 

    EXERCICE 3                 

 Le tableau ci-dessous est extrait d'une grille présentant les différents points d'une ville reliés par

 des lignes de transport en commun avec la durée des trajets en minutes .

 A ce tableau est associé un graphe dont les sommets sont A , B , C , D , F et G .

         →      A       B         C        D          E           F       G      
A         8                  3
B                     4                 
C                       6      4
D       10        9                        
E                            
F         3                      
G          7                           

 

  Par exemple, dans le tableau, la cellule contenant le nombre 9 correspond à la durée ( 9 minutes)  

 du trajet du bus reliant le point de départ D au point d'arrivée C.

 1.Réaliser le tableau des prédécesseurs de ce graphe, et déterminer le niveau de chacun des sommets.  

 Le tableau commence de la façon suivante:

    Première étape:   Comme D est de niveau 0 car sans prédécesseur on barre D dans la colonne

                                des prédécesseurs.

                                Puis comme A et C n'ont plus de sommets dans la colonne des prédécesseurs

                                ils sont déclarés du niveau suivant c-à-d  1.

PREDECESSEURS SOMMETS   NIVEAUX
 On barre D  .    La case est vierge.                        D              A                 1      
                                        A      F           G          B      
 On barre D .   La case est vierge.                        D              C                       1    
Pas de prédecesseur pour D donc niveau 0             D                    0    
                                                                    B             E     
                                                                     C              F     
                                                                A     C                G       

       Seconde étape:        On barre A et C dans la colonne des prédécesseurs.

                                        Alors  les sommets F et G  n'ont plus de sommet dans la colonne des prédécesseurs.

                                        Ils sont donc déclarés du niveau suivant c-à-d  2.

       Troisième étape :     On barre  F et G dans la colonne des prédécesseurs.

                                        Alors  le sommet B  n'a plus de sommet dans la colonne des prédécesseurs.

                                        Il est donc déclaré du niveau suivant c-à-d  3.

         Quatrième étape:    On barre  B  dans la colonne des prédécesseurs.

                                         Alors  le sommet E  n'a plus de sommet dans la colonne des prédécesseurs.

                                         Il est donc déclaré du niveau suivant c-à-d  4.

    On obtient finalement le tableau suivant:

PREDECESSEURS SOMMETS   NIVEAUX
                                                                        D              A                 1      
                                    A              F                  G                      B                   3       
                                                                D              C                       1    
                     D                    0    
                                                                B                                     E                      4     
                                                             C                                   F                        2   
                                                   A            C                                        G                  2  

 

 2. Dessiner le graphe en ordonnant les sommets par niveaux et en marquant la longueur de chaque arc.  

 

 3.  Déterminer le ou les trajets de durée minimale permettant d'aller de D à E.

( On détaillera la méthode utilisée.)

             •  Méthode par inventaire:

  DCFBE :  9 + 6 + 3 + 4 = 22  minutes

  DCGBE : 9 + 4 + 7 + 4 = 24 minutes

 DAGBE :  10 + 3 + 7 + 4 = 24 minutes

 DABE :    10 + 8 + 4 = 22 minutes

    Conclusion:   Il y a  deux trajets de D à E de durée minimale: 22 minutes

          DCFBE     et      DABE

       • METHODE avec le tableau de Moore-Djstra

 

  Tbmoore 3

                 Alors  à reculons:

                    E ← B( 22) ← F( 18 ) ← C( 15 ) ← D( 9) ←  D

         ou          "         "    ← A(18) ←D(10) ← D

                  c-à-d            D C F B E

                                    ou  

                                      DABE 

                    On retrouve le résultat.