Devoirs Hebdomadaire N°12
CDL...DH12
M. Joseph DASSE BRIKA 

        

        
Rappels : Propriétés du pgdc (plus grand 
        diviseur commun) de deux nombres entiers naturels (>=0)
        

        
Soient a et b 2 entiers alors 
        :   

        
    
          
  • 
          
    pgdc(a,b) = a si a=b
          
    • 
          
  • 
          
    pgdc(a,b) = pgdc(b,a)
          
    • 
          
  • 
          
    pgdc(a,b) = pgdc(a-b , b) 
          si a>b 
    • 
          
  • 
          
    pgdc(a,b) = pgdc(a , b-a) 
          si b>a 
    • 
          
  • 
          
    pgdc(a,b) = b si a mod b=0 
           (a mod b est le reste de la division entière de a par b)
          
    • 
          
  • 
          
    pgdc(a,b) = pgdc(b , a mod 
          b) si a mod b>0  (a mod b est le reste de la division entière de a par 
          b) 
    • 
        

        
Ayant pris connaissance de 
        ces propriètés, montrez que la propriété 
        (pgdc(a,b)=Cste) 
        est invariante pour 
        la suite d'instructions :
        

        
if ~(a=b) 
        then if (a<b) then t := a ; a:=b ; b:=t end; t:=b ; b:=a mod b ; a:=t 
        end; 

        

        
Dijkstra : wp 

        

        

        QUESTION 1 : en montrant :
        (pgdc(a,b)=Cste) 
         ->   
         wp(if 
        ~(a=b) then if (a<b) then t := a ; a:=b ; b:=t end; t:=b ; b:=a mod b ; 
        a:=t end ,
        pgdc(a,b)=Cste)
        

        

        
Hoare : Assertions
        

        


QUESTION 2 : 
en validant :   


        {pgdc(a,b)=Cste}


              if 
~(a=b) then 


                       if 
(a<b) then 


                          
  t := a ; 


                          
  a:=b ; 


                          
  b:=t 


                       end 
; 


              t:=b ;



              b:=a mod b 
; 


              a:=t 



              end ;



        {pgdc(a,b)=Cste}






  

  

    

      

      Montrons que la propriété (pgdc(a,b)=Cste) est invariante pour la suite 
      d'instructions : 

      if ~(a=b) then if (a<b) then t := a ; a:=b ; b:=t end; t:=b ; b:=a mod b ; 
      a:=t end; 

 		
    

    

      

    

    

      
      Question 1:
    

    

      Dijkstra: 

      Calculons wp(if ~(a=b) then if (a<b) then t := a ; a:=b ; b:=t end; t:=b ; 
      b:=a mod b ; a:=t end , pgdc(a,b)=Cste) 

      

      Premiere condition ~(a=b):

      

      ~(a=b) => wp( if (a<b) then t := a ; a:=b ; b:=t end; t:=b ; b:=a mod b 
      ;a:=t , pgdc(a,b)=Cste )  (1)

      v a=b => pgdc(a,b)=Cste.  (2)

      

      2eme condition dans (1), (a<b):

      

      wp( if (a<b) then t := a ; a:=b ; b:=t end; t:=b ; b:=a mod b ;a:=t , pgdc(a,b)=Cste 
      );

      =

      a<b => wp( t := a ; a:=b ; b:=t ; t:=b ; b:=a mod b ;a:=t , pgdc(a,b)=Cste 
      );  (3)

      v a>=b => wp ( t:=b ; b:=a mod b ;a:=t , pgdc(a,b)=Cste );  (4)

      

      Calcul du wp dans (4) (contenu aussi dans (3))

      wp ( t:=b ; b:=a mod b ;a:=t , pgdc(a,b)=Cste );

      = wp ( t:=b ; b:=a mod b , wp ( a:=t , pgdc(a,b)=Cste ));

      = wp ( t:=b ; wp( b:=a mod b , pgdc(t,b)=Cste ));

      = wp ( t:=b , pgdc(t,a mod b)=Cste );

      = pgdc(b,a mod b)=Cste;

      

      (3) et (4) deviennent:

      a<b => wp( t := a ; a:=b ; b:=t ; pgdc(b,a mod b)=Cste )  (3)

      v a>=b => pgdc(b,a mod b)=Cste  (4)

      

      Calcul du wp dans (3)

      wp( t := a ; a:=b ; b:=t ; pgdc(b,a mod b)=Cste )

      =wp( t := a ; a:=b , wp( b:=t ; pgdc(b,a mod b)=Cste))

      =wp( t := a , wp(a:=b , pgdc(t,a mod t)=Cste))

      =wp( t := a , pgdc(t,b mod t)=Cste)

      = pgdc(a,b mod a)=Cste

      

      Au final on obtient :

      

      ~(a=b) & a<b & pgdc(a,b mod a)=Cste

      v ~(a=b) & a>=b & pgdc(b,a mod b)=Cste 

      v a=b & pgdc(a,b)=Cste. 

      

      Simplification:

      ~(a=b) & a<b = a<b

      et

      ~(a=b) & a>=b = a>b

      

      Soit :

      

      a<b & pgdc(a,b mod a)=Cste

      v a>b & pgdc(b,a mod b)=Cste 

      v a=b & pgdc(a,b)=Cste. 

      

      On ramène le tout à la démonstration:

      (pgdc(a,b)=Cste) -> a<b & pgdc(a,b mod a)=Cste

      v a>b & pgdc(b,a mod b)=Cste 

      v a=b & pgdc(a,b)=Cste. 

      

      Pour le cas a=b la démonstration est faite: car pgdc(a,b)=Cste de 
      chaque coté de l'implique.

      

      Pour les cas a<b et a>b, on a (b mod a) >0 et (a mod b)>0 , car 
      ~(a=b).

      Et d'apres les propriétés du pdgc on sait que

      

      pgdc(a,b) = pgdc(b , a mod b) si a mod b>0

      

      donc pour a>b:

      

      pgdc(b,a mod b) = pgdc(a,b) = Cste

      

      et pour a<b

      

      pgdc(b,a mod b) = pgdc(b,a) = pgdc(a,b) = Cste

      

      Dans tous les cas, la relation de la démonstration est valide.

      On a donc bien:

      (pgdc(a,b)=Cste)-> wp(if ~(a=b) then if (a<b) then t := a; a:=b; b:=t end; 
      t:=b; b:=a mod b; a:=t end, pgdc(a,b)=Cste) 		
    

    

      

    

    

      
      Question 2:
    

    

      Hoare : Assertions 

      Afin de simplifier l'affichage je considère:

      P = pgdc(a,b)=Cste 

      Q = pgdc(a,b)=Cste 

      

      S1 = t := a ; a:=b ; b:=t ;

      S2 = t:=b ; b:=a mod b ; a:=t ;

      
      

        

          
          
  Conjecture  1
________________________________________________________
{pgdc(a,b)=Cste& ~(a=b)&(a<b)}=>{pgdc(a,b mod a)=Cste}*1
	
		|					 Conjecture 2
		| 		  ___________________________________________________
		|
		|	      {pgdc(a,b)=Cste&~(a=b)&~(a<b)}=>{pgdc(b,a mod b)=Cste}*2
______________________________	  _____________________________
 
{P & ~(a=b) & (a<b)} S1;S2 {Q}      {P & ~(a=b) & ~(a<b)} S2 {Q}
________________________________________________________________    _______________
								
{P & ~(a=b)} if (a<b) then S1 end ;S2; {Q} 			    {P & (a=b)}=>{Q}
________________________________________________________________________________
	{P} if  ~(a=b) then if (a<b) then S1 end ;S2; end ; {Q}

          		
        

      

      


      

    

    

      *1 : {pgdc(a,b)} t := a ; a:=b ; b:=t ; t:=b 
      ; b:=a mod b ; a:=t ;{pgdc(a,b mod a)}

      *2 : {pgdc(a,b)} t:=b ; b:=a mod b ; a:=t ; {pgdc(b,a mod b)}

      

      Conjecture 1:

         On sait que pgdc(a,b) = pgdc(a,b mod a) si (b mod a) >0

         on sait aussi (b mod a)>0 si a different de b.

         or ici on a ~(a=b) donc {pgdc(a,b)=Cste & ~(a=b) & (a<b)}=>{pgdc(a,b 
      mod a)=Cste}

      

      Conjecture 2: idem avec pgdc(a,b mod a) = pgdc(b,a) = pgdc(a,b)
      		
    

  

  



  
    		
  

  

    

    
  

  

    

            
FIN_dh12

  

  

    

    
  

  

    

            
ACCUEIL
            CONTACT
            
            FAVORIS ANNALES
            DH1
            DH2
            DH3 DH4 DH5 DH6
            DH7
            DH8
            DH9
            DH10 
            DH11 DH12 DH13 DH14 
            DH15 DH16