“doc” (Col. : Science Sup 17x24) — 2007/7/19 — 18:18 — page 11 — #21
i
i
i
i
i
i
i
i
1.7 La complexité calculatoire
11
– Pour les listes, le cas le plus simple est nil (la liste vide) et pour une liste donnée
T le cas suivant est H|T (sans aucune condition sur H).
Voyons comment l’induction fonctionne avec la fonction factorielle :
– {Fact 0} renvoie la bonne réponse, à savoir 1.
– Supposons que {Fact N-1} est correct. Alors considérons l’appel {Fact N}.
Nous observons que l’instruction if choisit la branche else (parce que N n’est
pas égale à zéro), et calcule N * {Fact N-1}. Selon notre hypothèse, {Fact
N-1} renvoie la bonne réponse. Donc, en supposant que la multiplication est
correcte, {Fact N} renvoie aussi la bonne réponse.
Ce raisonnement utilise la définition mathématique de la factorielle, n! = n × (n − 1)!
si n > 0, et 0! = 1. Plus loin dans le livre nous verrons d’autres techniques de raisonnement. Mais l’approche de base reste inchangée : commencer avec la sémantique du
langage et la spécification du problème, et utiliser le raisonnement mathématique pour
démontrer que le programme implémente correctement la spécification.
1.7 LA COMPLEXITÉ CALCULATOIRE
La fonction Pascal que nous avons définie ci-dessus devient très lente quand on
essaie de calculer des rangées de plus en plus grandes. La rangée 20 prend une fraction
de seconde. La rangée 30 prend plusieurs dizaines de secondes.
4 Si vous essayez des
rangées encore plus grandes, il faudra attendre patiemment le résultat. Pourquoi la
fonction prend-elle autant de temps ? Regardons encore une fois la définition de la
fonction Pascal :
fun {Pascal N}
if N==1 then [1] else
{AddList {ShiftLeft {Pascal N-1}}
{ShiftRight {Pascal N-1}}} end
end
Chaque appel de {Pascal N} appellera {Pascal N-1} deux fois. Donc, l’appel
{Pascal 30} appellera {Pascal 29} deux fois, ce qui fait quatre appels de
{Pascal 28}, huit de {Pascal 27}, et ainsi de suite, doublant avec chaque
rangée suivante. Cela donne 2
29 appels de {Pascal 1}, qui est environ un demimilliard. Il n’est pas étonnant que {Pascal 30} soit lent. Pouvons-nous l’accélérer ?
Oui, il y a une manière simple : il suffit d’appeler {Pascal N-1} une fois au lieu de
deux. Comme le deuxième appel donne le même résultat que le premier, si on pouvait
4. Ces chiffres dépendent de la vitesse de votre ordinateur, mais si votre ordinateur peut calculer la
rangée 50 dans un temps raisonnable avec cette définition contactez-nous !
© Dunod – La photocopie non autorisée est un délit
i
i
i
i
i
i
i
i
1.7 La complexité calculatoire
11
– Pour les listes, le cas le plus simple est nil (la liste vide) et pour une liste donnée
T le cas suivant est H|T (sans aucune condition sur H).
Voyons comment l’induction fonctionne avec la fonction factorielle :
– {Fact 0} renvoie la bonne réponse, à savoir 1.
– Supposons que {Fact N-1} est correct. Alors considérons l’appel {Fact N}.
Nous observons que l’instruction if choisit la branche else (parce que N n’est
pas égale à zéro), et calcule N * {Fact N-1}. Selon notre hypothèse, {Fact
N-1} renvoie la bonne réponse. Donc, en supposant que la multiplication est
correcte, {Fact N} renvoie aussi la bonne réponse.
Ce raisonnement utilise la définition mathématique de la factorielle, n! = n × (n − 1)!
si n > 0, et 0! = 1. Plus loin dans le livre nous verrons d’autres techniques de raisonnement. Mais l’approche de base reste inchangée : commencer avec la sémantique du
langage et la spécification du problème, et utiliser le raisonnement mathématique pour
démontrer que le programme implémente correctement la spécification.
1.7 LA COMPLEXITÉ CALCULATOIRE
La fonction Pascal que nous avons définie ci-dessus devient très lente quand on
essaie de calculer des rangées de plus en plus grandes. La rangée 20 prend une fraction
de seconde. La rangée 30 prend plusieurs dizaines de secondes.
4 Si vous essayez des
rangées encore plus grandes, il faudra attendre patiemment le résultat. Pourquoi la
fonction prend-elle autant de temps ? Regardons encore une fois la définition de la
fonction Pascal :
fun {Pascal N}
if N==1 then [1] else
{AddList {ShiftLeft {Pascal N-1}}
{ShiftRight {Pascal N-1}}} end
end
Chaque appel de {Pascal N} appellera {Pascal N-1} deux fois. Donc, l’appel
{Pascal 30} appellera {Pascal 29} deux fois, ce qui fait quatre appels de
{Pascal 28}, huit de {Pascal 27}, et ainsi de suite, doublant avec chaque
rangée suivante. Cela donne 2
29 appels de {Pascal 1}, qui est environ un demimilliard. Il n’est pas étonnant que {Pascal 30} soit lent. Pouvons-nous l’accélérer ?
Oui, il y a une manière simple : il suffit d’appeler {Pascal N-1} une fois au lieu de
deux. Comme le deuxième appel donne le même résultat que le premier, si on pouvait
4. Ces chiffres dépendent de la vitesse de votre ordinateur, mais si votre ordinateur peut calculer la
rangée 50 dans un temps raisonnable avec cette définition contactez-nous !
© Dunod – La photocopie non autorisée est un délit