Conclusion du chapitre 10

  Exercice commenté


C'était le but premier de l'exercice : il est évident maintenant que pour tester si une liste est vide il faut utiliser le prédicat null? (qui est d'ailleurs fait pour cela !) et non pas mesurer la longueur de la liste. C'est d'ailleurs ce que chacun ferait : si pour savoir si une liste n'a qu'un seul élément, nous vous énumérons les éléments d'une liste, vous nous arrêterez dès que nous aurons donné le second élément pour nous répondre ``Non'', vous n'attendrez pas que nous vous ayons annoncé les 83940 autres !

D'un point de vue plus général, nous venons de montrer que si pour un même algorithme, il est possible de produire plusieurs codages, ce que nous savions, le choix du codage n'est pas toujours sans conséquence. La mesure la complexité (selon un critère) d'un programme permet alors de comparer les différentes solutions. Nous avons mesuré ici une complexité en nombre d'appels (ce qui revient à une complexité en temps de calcul) mais il aurait été possible de le faire en mesurant l'espace de travail utilisé (on pourrait par exemple calculer cette mesure pour les fonctions plus-grand1 et plus-grand3 du paragraphe ??, cela est laissé en exercice).

De plus ce travail nous montre qu'un programme peut lui aussi être un sujet d'étude. Un programme est donc non seulement la réponse à un problème mais peu lui même être une source d'étude.


next up previous
Next: Résumé du chapitre 11 Up: No Title Previous: Résumé du chapitre 9

Eric.Wegrzynowski
Thu Mar 20 13:58:10 MET 1997