Cours d’Algorithmique

Cours d'algorithmique 10 / IntranetCours d'algorithmique 10 / Intranet 1119 décembre 200619 décembre 2006

Cours d’AlgorithmiqueCours d’Algorithmique

Logique de Hoare (fin) :Logique de Hoare (fin) :

Les boucles etLes boucles et

les invariants.les invariants.

19 décembre 200619 décembre 2006 Cours d'algorithmique 10 / IntranetCours d'algorithmique 10 / Intranet 22

• Trier et chercher, recherche textuelleTrier et chercher, recherche textuelle• Listes et arbresListes et arbres• Le back-trackLe back-track• Arbres équilibrésArbres équilibrés• Récursivité et induction sur la structureRécursivité et induction sur la structure• Divide and conquer, algorithmes gloutonsDivide and conquer, algorithmes gloutons• Minimax, alpha-betaMinimax, alpha-beta• DérécursionDérécursion• Divers problèmes particuliersDivers problèmes particuliers• Logique de HoareLogique de Hoare• Programmation dynamiqueProgrammation dynamique• Complexité et calculabilitéComplexité et calculabilité

Les grandes lignes du coursLes grandes lignes du cours


Logique de HoareLogique de Hoare----------------------------------------------------------------------------------------------------------------------------------

W H I L EW H I L E

e t l e se t l e s

I N V A R I A N T SI N V A R I A N T SD ED E

B O U C L EB O U C L E



• L’exemple qui nous sert à illustrer la notion L’exemple qui nous sert à illustrer la notion d’invariant :d’invariant :

– PRE : V , D PRE : V , D N N

– POST: POST: Q , R Q , R N N

telles V = Q * D + R telles V = Q * D + R et R < D .et R < D .

• C’est la spécification de la division euclidienne !C’est la spécification de la division euclidienne !

II

II



Exemple : V = 17 , D = 5Exemple : V = 17 , D = 5

V = 17 , D = 5 , Q = 0V = 17 , D = 5 , Q = 0

Q <- 0 ;Q <- 0 ;

R <- V ;R <- V ;

while R >= Dwhile R >= D

Q <- Q + 1 ;Q <- Q + 1 ;

R <- R - DR <- R - D

V = 17 , D = 5 , Q = 0 , R = 17V = 17 , D = 5 , Q = 0 , R = 17

V = 17 , D = 5 , Q = 0 , R = 17V = 17 , D = 5 , Q = 0 , R = 17

V = 17 , D = 5 , Q = 1 , R = 17V = 17 , D = 5 , Q = 1 , R = 17

V = 17 , D = 5 , Q = 1 , R = 12V = 17 , D = 5 , Q = 1 , R = 12

V = 17 , D = 5 , Q = 1 , R = 12V = 17 , D = 5 , Q = 1 , R = 12

Y a-t-il quelque-chose de communY a-t-il quelque-chose de communentre les différentes itérations ?entre les différentes itérations ?

OUI : V = Q * D + ROUI : V = Q * D + R

V = 17 , D = 5 , Q = 2 , R = 12V = 17 , D = 5 , Q = 2 , R = 12

V = 17 , D = 5 , Q = 2 , R = 7V = 17 , D = 5 , Q = 2 , R = 7



Exemple : V = 17 , D = 5Exemple : V = 17 , D = 5

V = 17 , D = 5 , Q = 0V = 17 , D = 5 , Q = 0

Q <- 0 ;Q <- 0 ;

R <- V ;R <- V ;

while R >= Dwhile R >= D

Q <- Q + 1 ;Q <- Q + 1 ;

R <- R - DR <- R - D

V = 17 , D = 5 , Q = 0 , R = 17V = 17 , D = 5 , Q = 0 , R = 17

Y a-t-il quelque-chose de communY a-t-il quelque-chose de communentre les différentes itérations ?entre les différentes itérations ?

OUI : V = Q * D + ROUI : V = Q * D + R

V = 17 , D = 5 , Q = 2 , R = 7V = 17 , D = 5 , Q = 2 , R = 7

V = 17 , D = 5 , Q = 3 , R = 7V = 17 , D = 5 , Q = 3 , R = 7

V = 17 , D = 5 , Q = 3 , R = 2V = 17 , D = 5 , Q = 3 , R = 2

A la fin :A la fin :

V = Q * D + RV = Q * D + Retet

R < DR < D



• Les valeurs de Les valeurs de V , D , Q , RV , D , Q , R peuvent changer. peuvent changer.

• Mais la relation Mais la relation V = Q * D + RV = Q * D + R reste toujours vérifiée. reste toujours vérifiée.

• C’est ce qu’on appelle un « invariant » !C’est ce qu’on appelle un « invariant » !

• Un invariant est un prédicat qui :Un invariant est un prédicat qui :

– est vrai à chaque début de boucle,est vrai à chaque début de boucle,

– et à chaque fin de boucle,et à chaque fin de boucle,

– c’est-à-dire début de la boucle suivante.c’est-à-dire début de la boucle suivante. (Les tests ne font pas d’affectation !)(Les tests ne font pas d’affectation !)



• Pour écrire un corps de boucle, il faut connaître Pour écrire un corps de boucle, il faut connaître l’invariant de la boucle !l’invariant de la boucle !

• Votre code sera exécuté par le « i » tour de Votre code sera exécuté par le « i » tour de boucle, quel que soit la valeur de « i ».boucle, quel que soit la valeur de « i ».

• Pour savoir ce que vous devez faire au « i » tour Pour savoir ce que vous devez faire au « i » tour de boucle, vous devez vous souvenir de ce que de boucle, vous devez vous souvenir de ce que vous avez fait pendant les « i – 1 » premiers tours. vous avez fait pendant les « i – 1 » premiers tours.

• Ceci revient à connaître « l’invariant » !Ceci revient à connaître « l’invariant » !

ee

ee



• Quel est l’invariant ?Quel est l’invariant ?

• Avant le « i » tour de boucle, nous avons fait les tours de boucle de « 1 » à « i – 1 ».Avant le « i » tour de boucle, nous avons fait les tours de boucle de « 1 » à « i – 1 ».

• Nous avons donc sommé dans « s » les valeurs de « 1 » à « i – 1 ».Nous avons donc sommé dans « s » les valeurs de « 1 » à « i – 1 ».

• Invariant :Invariant : s = s = j j

s <- 0 ;s <- 0 ;i <- 1 ;i <- 1 ;

while ( i <= n ) do while ( i <= n ) do

s <- s + i ;s <- s + i ; i <- i + 1 i <- i + 1

ee

j = 1j = 1

i – 1i – 1



• Règle pour le programme Règle pour le programme while C dowhile C do : :

• Nous dirons que « I » est l’invariant !Nous dirons que « I » est l’invariant !

• La condition La condition { I , C }{ I , C } { I } { I } vérifie que « I » est bien invariant ! ! !vérifie que « I » est bien invariant ! ! !

• La post-condition La post-condition { I{ I , , C } C } est évidente !est évidente !

• Il suffit alors que Il suffit alors que { I }{ I } soit vrai au début ! soit vrai au début !

{ I }{ I } while C dowhile C do { I{ I , , C } C }

{ I , C }{ I , C } { I }{ I }



• Dans la pratique, nous avons une post-condition Dans la pratique, nous avons une post-condition QQ et le code et le code while C dowhile C do : :

• Quel prédicat « I » faut-il choisir comme invariant ?Quel prédicat « I » faut-il choisir comme invariant ?

• C’est l’utilisateur qui doit faire une proposition !C’est l’utilisateur qui doit faire une proposition !

• Nouvelle syntaxe :Nouvelle syntaxe : while C do while C do inv Iinv I

{ ??? }{ ??? } while C dowhile C do { Q }{ Q }

{ ??? , C }{ ??? , C } { ??? }{ ??? }



• Règle pour le programme Règle pour le programme while C dowhile C do inv I inv I ::

• Nous devons prouver que I , Nous devons prouver que I , C => Q ! C => Q !

• Nous calculons la pré-condition « F » de { F } Nous calculons la pré-condition « F » de { F } { I } ! { I } !

• Nous prouvons que I , C => F !Nous prouvons que I , C => F !

• A ce moment, nous connaissons la pré-condition « I » !A ce moment, nous connaissons la pré-condition « I » !

{ F } { F } { I } { I }I , C => FI , C => F I , I , C => Q C => Q

{ I }{ I } while C dowhile C do inv I inv I { Q }{ Q }



• Règle pour le programme Règle pour le programme while C dowhile C do inv I inv I ::

• Attention, il y a deux obligations de preuve !Attention, il y a deux obligations de preuve !

• Elles sont semi-automatisables.Elles sont semi-automatisables.

• Un prouveur peut ne pas trouver la preuve !Un prouveur peut ne pas trouver la preuve !

• Un prouveur ne saura jamais dire si elle n’existe pas ! ! !Un prouveur ne saura jamais dire si elle n’existe pas ! ! !

{ F } { F } { I } { I }I , C => FI , C => F I , I , C => Q C => Q




U NU N

P R E M I E RP R E M I E R

E X E M P L EE X E M P L E



• POST :POST :

R <- V ;R <- V ;Q <- 0 ;Q <- 0 ;

while ( R >= D ) dowhile ( R >= D ) do

Q <- Q + 1 ;Q <- Q + 1 ; R <- R – DR <- R – D

inv Iinv I

Q = { V = D * Q + R , 0 <= R < D }Q = { V = D * Q + R , 0 <= R < D }



• POST :POST :

R <- V ;R <- V ;Q <- 0 ;Q <- 0 ;


Q <- Q + 1 ;Q <- Q + 1 ; R <- R – DR <- R – D

inv Iinv I

Q = { V = D * Q + R , 0 <= R < D }Q = { V = D * Q + R , 0 <= R < D } = { V = D * Q + R , 0 <= R } et { R < D }= { V = D * Q + R , 0 <= R } et { R < D }

= { V = D * Q + R , 0 <= R }= { V = D * Q + R , 0 <= R }

Sans problème :Sans problème :

I , I , C => Q C => Q



• POST :POST :

R <- V ;R <- V ;Q <- 0 ;Q <- 0 ;


Q <- Q + 1 ;Q <- Q + 1 ; R <- R – DR <- R – D

inv Iinv I


= { V = D * Q + R , 0 <= R }= { V = D * Q + R , 0 <= R }


I , I , C => Q C => Q

F = { V = D * Q + R , D <= R }F = { V = D * Q + R , D <= R }

{ V = D * Q + R , 0 <= R }{ V = D * Q + R , 0 <= R }

{ V = D * Q + R – D , 0 <= R – D }{ V = D * Q + R – D , 0 <= R – D }

Après simplification !Après simplification !



{ F } { F } { I } { I } I , I , C => Q C => Q


I , C => FI , C => F

{ V = D * Q + R , 0 <= R } { V = D * Q + R , 0 <= R } et et { R >= D }{ R >= D }

!!!!!!!!!!!!=>=>

{ V = D * Q + R , D <= R }{ V = D * Q + R , D <= R }



• POST :POST :

R <- V ;R <- V ;Q <- 0 ;Q <- 0 ;


Q <- Q + 1 ;Q <- Q + 1 ; R <- R – DR <- R – D

inv Iinv I


= { V = D * Q + R , 0 <= R }= { V = D * Q + R , 0 <= R }


I , I , C => Q C => Q

F = { V = D * Q + R , D <= R }F = { V = D * Q + R , D <= R }

{ V = D * Q + R , 0 <= R }{ V = D * Q + R , 0 <= R }

{ V = D * Q + R – D , 0 <= R – D }{ V = D * Q + R – D , 0 <= R – D }

I = { V = D * Q + R , 0 <= R }I = { V = D * Q + R , 0 <= R }


I , C => FI , C => F

{ V = D * 0 + R , 0 <= R }{ V = D * 0 + R , 0 <= R }

{ V = D * 0 + V , 0 <= V } = { V >= 0 }{ V = D * 0 + V , 0 <= V } = { V >= 0 }• PRE :PRE :



U NU N

D E U X I E M ED E U X I E M E




x <- a ;x <- a ;y <- b ;y <- b ;

while ( y <> 0 ) dowhile ( y <> 0 ) do

m <- y ;m <- y ; y <- x % y ;y <- x % y ; x <- mx <- m

inv Iinv I

• POST :POST :

Q = { x = pgcd( a , b ) }Q = { x = pgcd( a , b ) }



x <- a ;x <- a ;y <- b ;y <- b ;


m <- y ;m <- y ; y <- x % y ;y <- x % y ; x <- mx <- m

inv Iinv I

• POST :POST :

Q = { x = pgcd( a , b ) } Q = { x = pgcd( a , b ) } = { pgcd( x , 0 ) = pgcd( a , b ) }= { pgcd( x , 0 ) = pgcd( a , b ) } = { pgcd( x , y ) = pgcd( a , b ) , y = 0 }= { pgcd( x , y ) = pgcd( a , b ) , y = 0 }

= { pgcd( x , y ) = pgcd( a , b ) }= { pgcd( x , y ) = pgcd( a , b ) }


I , I , C => Q C => Q



x <- a ;x <- a ;y <- b ;y <- b ;


m <- y ;m <- y ; y <- x % y ;y <- x % y ; x <- mx <- m

inv Iinv I

• POST :POST :


= { pgcd( x , y ) = pgcd( a , b ) }= { pgcd( x , y ) = pgcd( a , b ) }


I , I , C => Q C => Q

F = { pgcd( y , x % y ) = pgcd( a , b ) }F = { pgcd( y , x % y ) = pgcd( a , b ) }

{ pgcd( x , y ) = pgcd( a , b ) }{ pgcd( x , y ) = pgcd( a , b ) }

{ pgcd( m , y ) = pgcd( a , b ) }{ pgcd( m , y ) = pgcd( a , b ) }

{ pgcd( m , x%y ) = pgcd( a , b ) }{ pgcd( m , x%y ) = pgcd( a , b ) }



II , , C C => => FF

{ pgcd( x , y ) = pgcd( a , b ) }{ pgcd( x , y ) = pgcd( a , b ) } et et { y <> 0 }{ y <> 0 }

??????=>=>

{ pgcd( y , x % y ) = pgcd( a , b ) }{ pgcd( y , x % y ) = pgcd( a , b ) }

? ? ?? ? ?

Maths : x >= y et y <> 0 => pgcd( x , y ) = pgcd( y , x % y )Maths : x >= y et y <> 0 => pgcd( x , y ) = pgcd( y , x % y )

Nous devons renforcer l’invariant :Nous devons renforcer l’invariant :

{ pgcd( x , y ) = pgcd( a , b ) , x >= y }{ pgcd( x , y ) = pgcd( a , b ) , x >= y }



x <- a ;x <- a ;y <- b ;y <- b ;


m <- y ;m <- y ; y <- x % y ;y <- x % y ; x <- mx <- m

inv Iinv I

• POST :POST :


= { pgcd( x , y ) = pgcd( a , b ) , x >= y }= { pgcd( x , y ) = pgcd( a , b ) , x >= y }


I , I , C => Q C => Q



x <- a ;x <- a ;y <- b ;y <- b ;


m <- y ;m <- y ; y <- x % y ;y <- x % y ; x <- mx <- m

inv Iinv I

• POST :POST :



I , I , C => Q C => Q



{ . . . , m >= y }{ . . . , m >= y }

{ . . . , m >= x % y }{ . . . , m >= x % y }




II , , C C => => FF

{ pgcd( x , y ) = pgcd( a , b ) , x >= y }{ pgcd( x , y ) = pgcd( a , b ) , x >= y } et et { y <> 0 }{ y <> 0 }

!!!!!!!!!!!!=>=>

{ pgcd( y , x % y ) = pgcd( a , b ) }{ pgcd( y , x % y ) = pgcd( a , b ) }

Maths : x >= y et y <> 0 => pgcd( x , y ) = pgcd( y , x % y )Maths : x >= y et y <> 0 => pgcd( x , y ) = pgcd( y , x % y )



x <- a ;x <- a ;y <- b ;y <- b ;


m <- y ;m <- y ; y <- x % y ;y <- x % y ; x <- mx <- m

inv Iinv I

• POST :POST :



I , I , C => Q C => Q



{ . . . , m >= y }{ . . . , m >= y }

{ . . . , m >= x % y }{ . . . , m >= x % y }


I , C => FI , C => F

I = { pgcd( x , y ) = pgcd( a , b ) , x >= y }I = { pgcd( x , y ) = pgcd( a , b ) , x >= y }

{ pgcd( a , b ) = pgcd( a , b ) , a >= b } = { a >= b }{ pgcd( a , b ) = pgcd( a , b ) , a >= b } = { a >= b }• PRE :PRE :




U NU N

T R O I S I E M ET R O I S I E M E




s <- 0 ;s <- 0 ;c <- 1 ;c <- 1 ;

while ( c <= n ) dowhile ( c <= n ) do

s <- s + c ;s <- s + c ; c <- c + 1c <- c + 1

inv Iinv I

• POST :POST :

i = 1i = 1

c – 1c – 1= { c <= n + 1 , s = = { c <= n + 1 , s = i } i }


I , I , C => Q C => Q

Q = { s = Q = { s = i } i } = { s = = { s = i , c <= n + 1 , c > n } i , c <= n + 1 , c > n }i = 1i = 1

nn

i = 1i = 1

c – 1c – 1



s <- 0 ;s <- 0 ;c <- 1 ;c <- 1 ;


s <- s + c ;s <- s + c ; c <- c + 1c <- c + 1

inv Iinv I

• POST :POST :

i = 1i = 1

c – 1c – 1= { c <= n + 1 , s = = { c <= n + 1 , s = i } i }


I , I , C => Q C => Q


nn

i = 1i = 1

c – 1c – 1

F = { c <= n , s = F = { c <= n , s = i } i }

I = . . .I = . . .

i = 1i = 1

c – 1c – 1




s <- 0 ;s <- 0 ;c <- 1 ;c <- 1 ;


s <- s + c ;s <- s + c ; c <- c + 1c <- c + 1

inv Iinv I

• POST :POST :

i = 1i = 1

c – 1c – 1= { c <= n + 1 , s = = { c <= n + 1 , s = i } i }


I , I , C => Q C => Q


nn

i = 1i = 1

c – 1c – 1

F = { c <= n , s = F = { c <= n , s = i } i }

I = . . .I = . . .

i = 1i = 1

c – 1c – 1Sans problème :Sans problème :

I , C => FI , C => F



s <- 0 ;s <- 0 ;c <- 1 ;c <- 1 ;


s <- s + c ;s <- s + c ; c <- c + 1c <- c + 1

inv Iinv I

• POST :POST :

i = 1i = 1

c – 1c – 1= { c <= n + 1 , s = = { c <= n + 1 , s = i } i }


I , I , C => Q C => Q


nn

i = 1i = 1

c – 1c – 1

F = { c <= n , s = F = { c <= n , s = i } i }

I = . . .I = . . .

i = 1i = 1

c – 1c – 1Sans problème :Sans problème :

I , C => FI , C => F

i = 1i = 1

c – 1c – 1I = { c <= n + 1 , s = I = { c <= n + 1 , s = i } i }

i = 1i = 1

1 – 11 – 1{ 1 <= n + 1 , 0 = { 1 <= n + 1 , 0 = i } i } = { n >= 0 } = { n >= 0 }• PRE :PRE :



s <- s <- 11 ; ;c <- c <- 2 2 ;;


. . .. . .

i = 1i = 1

c – 1c – 1I = { c <= n + 1 , s = I = { c <= n + 1 , s = i } i }

i = 1i = 1

22 – 1 – 1{ { 22 <= n + 1 , <= n + 1 , 1 1 = = i } i } = { n >= 1 } = { n >= 1 }• PRE :PRE :

• Une autre initialisation :Une autre initialisation :

• POST :POST :

Q = { s = Q = { s = i } i }i = 1i = 1

nn



s <- s <- 66 ; ;c <- c <- 2 2 ;;


. . .. . .

i = 1i = 1

c – 1c – 1I = { c <= n + 1 , s = I = { c <= n + 1 , s = i } i }

i = 1i = 1

22 – 1 – 1{ { 22 <= n + 1 , <= n + 1 , 6 6 = = i } i } = { n >= 1 , = { n >= 1 , 6 = 1 6 = 1 } } = { FAUX } = { FAUX }• PRE :PRE :

• Une mauvaise initialisation :Une mauvaise initialisation :

• POST :POST :

Q = { s = Q = { s = i } i }i = 1i = 1

nn



s <- s <- 66 ; ;c <- c <- 2 2 ;;


. . .. . .

i = 1i = 1

c – 1c – 1I = { c <= n + 1 , s = I = { c <= n + 1 , s = i } i }

i = 1i = 1

22 – 1 – 1{ { 22 <= n + 1 , <= n + 1 , 6 6 = = i } i } = { n >= 1 , = { n >= 1 , 6 = 1 6 = 1 } } = { n >= 1 }= { n >= 1 }• PRE :PRE :


• POST :POST :

Q = { s = Q = { s = i } i }i = 1i = 1

nn



s <- s <- 66 ; ;c <- c <- 2 2 ;;


. . .. . .

i = 1i = 1

c – 1c – 1I = { c <= n + 1 , s = I = { c <= n + 1 , s = i } i }

i = 1i = 1

22 – 1 – 1{ { 22 <= n + 1 , <= n + 1 , 6 6 = = i } i } = { n >= 1 , = { n >= 1 , 6 = 1 6 = 1 } } = { n >= 3 }= { n >= 3 }• PRE :PRE :


• POST :POST :

Q = { s = Q = { s = i } i }i = 1i = 1

nn


• POST :POST :


• Un mauvais invariant :Un mauvais invariant :


nn

. . .. . .


s <- s + c + 3 ;s <- s + c + 3 ; c <- c + 1c <- c + 1

inv Iinv Ii = 1i = 1

c – 1c – 1= { c <= n + 1 , s = = { c <= n + 1 , s = i } i }

i = 1i = 1

c – 1c – 1


I , I , C => Q C => Q


• POST :POST :




nn

. . .. . .


s <- s + c + 3 ;s <- s + c + 3 ; c <- c + 1c <- c + 1


c – 1c – 1= { c <= n + 1 , s = = { c <= n + 1 , s = i } i }

i = 1i = 1

c – 1c – 1

I = . . .I = . . .

F = { c <= n , s + 3 = F = { c <= n , s + 3 = i } i }i = 1i = 1

c – 1c – 1



I , I , C => Q C => Q



II , , C C => => FF

{ c <= n + 1 , s = { c <= n + 1 , s = i } i } et et { c <= n }{ c <= n }

NONNON=>=>

{ c <= n + 1 , s + 3 = { c <= n + 1 , s + 3 = i } i }i = 1i = 1

c – 1c – 1

i = 1i = 1

c – 1c – 1

////

Sinon, nous aurions 3 = 0 !Sinon, nous aurions 3 = 0 !


• POST :POST :



Q = { s = Q = { s = (i + 3) } (i + 3) } = { s = = { s = (i + 3) , c <= n + 1 , (i + 3) , c <= n + 1 , c > n }c > n }i = 1i = 1

nn

. . .. . .


s <- s + c + 3 ;s <- s + c + 3 ; c <- c + 1c <- c + 1


c – 1c – 1= { c <= n + 1 , s = = { c <= n + 1 , s = (i + 3) } (i + 3) }

i = 1i = 1

c – 1c – 1


I , I , C => Q C => Q

I = . . .I = . . .

F = { c <= n , s = F = { c <= n , s = (i + 3) } (i + 3) }i = 1i = 1

c – 1c – 1



I , C => FI , C => F



• Attention :Attention :

• Tout ceci n’empêche pas un programme de boucler !Tout ceci n’empêche pas un programme de boucler !

• Nous affirmons seulement queNous affirmons seulement que

– si le programme s’arrête,si le programme s’arrête,

– alors il rend le résultat indiqué !alors il rend le résultat indiqué !

Documents

Cours d’Algorithmique