informatique (MP2I/MPI) · Chapitre 3 · Application directe du cours
Algorithme, ou programme ?
Algorithmes, programmes et complexité · niveau 2
Énoncé
Chacune de ces six affirmations porte sur un algorithme ou sur un programme. Laquelle, et comment le sait-on ?
- « La dichotomie fait au plus tours. »
- « Cette recherche s'exécute en ms sur mon portable. »
- « Ce tri est en place : il n'utilise qu'un espace supplémentaire constant. »
- « Ce calcul déborde pour . »
- « Cette boucle ne s'arrête jamais parce que la condition teste l'égalité de deux flottants. »
- « Ce tri est quadratique dans le pire cas. »
Corrigé
Le critère est simple : une affirmation porte sur l'algorithme si elle reste vraie quand on change de langage et de machine. Sinon elle porte sur le programme, ou sur son exécution.
| Porte sur | Pourquoi | |
|---|---|---|
| 1 | l'algorithme | Un comptage d'opérations, indépendant de toute réalisation. |
| 2 | l'exécution | Dépend de la machine, du compilateur, de la charge. Le même programme donnera un autre chiffre demain. |
| 3 | l'algorithme | La complexité en espace est une propriété de la méthode. |
| 4 | le programme | Le seuil vient du type int choisi. En OCaml, la limite serait ; avec des entiers de taille arbitraire, il n'y en aurait pas. |
| 5 | le programme | L'algorithme mathématique s'arrête ; c'est sa mise en {œ}uvre en flottants qui ne s'arrête pas. Le chapitre l'énonce ainsi : « la boucle théorique termine ; le programme, non ». |
| 6 | l'algorithme | Le pire cas est un maximum sur les entrées, pas une mesure. |
Le cas 4 mérite un mot, parce qu'on le range volontiers du mauvais côté. Le débordement n'appartient pas à l'algorithme : l'algorithme d'Euclide, de la somme ou du tri ne connaît pas de . Il appartient au type choisi lors de la mise en {œ}uvre, et il disparaît si l'on en change. C'est précisément pourquoi il faut le documenter en tête de fonction : rien dans la méthode ne le laisse deviner.
Le cas 5 est le plus instructif. Il montre qu'un programme peut échouer alors que l'algorithme est correct — c'est exactement la « divergence entre le calcul théorique d'un algorithme et les valeurs calculées par un programme » que le programme officiel demande d'illustrer. Prouver un algorithme ne dispense donc jamais de tester son programme, et le chapitre chap:discipline en fait une règle.
Exercices semblables
- Une boucle sans variant connu corrigé
- Le milieu qui déborde corrigé
- Trois divergences flottantes corrigé
- Pire cas, cas moyen, coût amorti corrigé
- Un qui bat un corrigé