Livre_silo 30 août 2013 16:32 Page 202
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
202
Informatique pour tous
Exercice 8.1 Pourquoi renvoyer
c + d
2
plutôt que m ?
EN PRATIQUE Passage d’une fonction en tant qu’argument
On aura noté que dans les arguments passés à la fonction de recherche dichotomique, il
y a la fonction f . Cela ne pose pas de problème à un langage tel que Python, pour lequel
une fonction est (presque) un objet comme un autre.
8.1.2 Terminaison, correction et complexité de l’algorithme
Il y a deux points à démontrer : la terminaison et la correction.
Pour la terminaison, on peut démontrer par récurrence immédiate qu’au début de la kième itération, on a : d − c =
b − a
2 k−1 · Sous les hypothèses 0 < ε et a < b, on aura
d − c < 2ε pour k suffisamment grand, ce qui fera sortir de la boucle et démontre la
terminaison.
Pour la correction, il faut montrer que le résultat renvoyé est un réel r tel que l’équation
f (x) = 0 possède une solution x 0 telle que |x 0 − r| ⩽ ε. La clé de la démonstration est
l’invariant suivant :
À chaque itération, on a f (c)f (d) ⩽ 0.
Pour démontrer cet invariant, on note qu’il est bien vérifié par hypothèse avant l’entrée dans
la boucle ¹. Ensuite (induction), on suppose la propriété vraie au début d’une itération. Si
f (c)f (m) ⩽ 0, alors on change la valeur de d en m sans toucher à c, donc on a bien
f (c)f (d) ⩽ 0 à la fin de l’itération (donc au début de la suivante). Si f (c)f (m) > 0, la
valeur de d est inchangée et on remplace c par m. Puisque f (m) a le même signe (strict)
que f (c), le signe de f (c)f (d) ne change pas dans l’affectation c ← m et, comme cette
quantité était négative au début de l’itération, elle l’est encore à la fin de celle-ci.
Ainsi, le réel r renvoyé est le milieu d’un intervalle de longueur majorée par 2ε (condition
de sortie de boucle) et qui contient un zéro x 0 de f (grâce à l’invariant de boucle et au
théorème des valeurs intermédiaires : la fonction en jeu était supposée continue). On a
alors bien |x 0 − r| ⩽ ε.
Enfin, on va s’intéresser à la complexité. Ici, il convient de préciser ce qu’on prend en
compte : comptabiliser les opérations arithmétiques usuelles de la même façon que les
appels de f serait imprudent (chaque appel de f peut être non élémentaire). Les opérations arithmétiques élémentaires comme les appels de la fonction sont contrôlés par le
nombre de passages dans la boucle.
1. Si cette hypothèse cruciale n’ est pas vérifiée, le comportement de l’algorithme n’ est pas spécifié. On peut
arranger un peu cela grâce à une vérification de propriété en début de programme (assert dans ce qui suit).
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
202
Informatique pour tous
Exercice 8.1 Pourquoi renvoyer
c + d
2
plutôt que m ?
EN PRATIQUE Passage d’une fonction en tant qu’argument
On aura noté que dans les arguments passés à la fonction de recherche dichotomique, il
y a la fonction f . Cela ne pose pas de problème à un langage tel que Python, pour lequel
une fonction est (presque) un objet comme un autre.
8.1.2 Terminaison, correction et complexité de l’algorithme
Il y a deux points à démontrer : la terminaison et la correction.
Pour la terminaison, on peut démontrer par récurrence immédiate qu’au début de la kième itération, on a : d − c =
b − a
2 k−1 · Sous les hypothèses 0 < ε et a < b, on aura
d − c < 2ε pour k suffisamment grand, ce qui fera sortir de la boucle et démontre la
terminaison.
Pour la correction, il faut montrer que le résultat renvoyé est un réel r tel que l’équation
f (x) = 0 possède une solution x 0 telle que |x 0 − r| ⩽ ε. La clé de la démonstration est
l’invariant suivant :
À chaque itération, on a f (c)f (d) ⩽ 0.
Pour démontrer cet invariant, on note qu’il est bien vérifié par hypothèse avant l’entrée dans
la boucle ¹. Ensuite (induction), on suppose la propriété vraie au début d’une itération. Si
f (c)f (m) ⩽ 0, alors on change la valeur de d en m sans toucher à c, donc on a bien
f (c)f (d) ⩽ 0 à la fin de l’itération (donc au début de la suivante). Si f (c)f (m) > 0, la
valeur de d est inchangée et on remplace c par m. Puisque f (m) a le même signe (strict)
que f (c), le signe de f (c)f (d) ne change pas dans l’affectation c ← m et, comme cette
quantité était négative au début de l’itération, elle l’est encore à la fin de celle-ci.
Ainsi, le réel r renvoyé est le milieu d’un intervalle de longueur majorée par 2ε (condition
de sortie de boucle) et qui contient un zéro x 0 de f (grâce à l’invariant de boucle et au
théorème des valeurs intermédiaires : la fonction en jeu était supposée continue). On a
alors bien |x 0 − r| ⩽ ε.
Enfin, on va s’intéresser à la complexité. Ici, il convient de préciser ce qu’on prend en
compte : comptabiliser les opérations arithmétiques usuelles de la même façon que les
appels de f serait imprudent (chaque appel de f peut être non élémentaire). Les opérations arithmétiques élémentaires comme les appels de la fonction sont contrôlés par le
nombre de passages dans la boucle.
1. Si cette hypothèse cruciale n’ est pas vérifiée, le comportement de l’algorithme n’ est pas spécifié. On peut
arranger un peu cela grâce à une vérification de propriété en début de programme (assert dans ce qui suit).