Algorithme, ou programme ?

Exercice · niveau 2 · informatique (MP2I/MPI), chapitre 3 — Algorithmes, programmes et complexité

É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 $⌊ lo g_{2} n ⌋ + 1$ tours. »
« Cette recherche s'exécute en $2, 3$  ms sur mon portable. »
« Ce tri est en place : il n'utilise qu'un espace supplémentaire constant. »
« Ce calcul déborde pour $n \geq 2^{31}$ . »
« 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 $2^{31}$ vient du type `int` choisi. En OCaml, la limite serait $2^{62}$ ; 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 $2^{31}$ . 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.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.