Quelle est la différence entre un programme qui termine et un algorithme de décision ?

Réponse courte

Dire qu’un programme termine décrit son exécution sur une entrée donnée. Un algorithme de décision doit, lui, répondre correctement oui ou non et terminer pour chaque entrée autorisée de son problème.

Comprendre

Une exécution ou une promesse générale

Observer qu’un programme s’arrête après avoir reçu 7 établit seulement que cette exécution particulière termine. Cela ne dit pas ce qu’il fera sur les autres entrées. Un algorithme de décision a une exigence plus précise : pour toutes les entrées du domaine, il termine et renvoie la réponse correcte à une question binaire.

Deux situations à comparer

Un programme qui reçoit 7, affiche « calcul fini » puis s’arrête termine sur cette entrée, mais ne décide pas la parité s’il ne répond pas si 7 est pair ou impair. À l’inverse, la procédure qui calcule le reste de n par 2 et répond oui si le reste vaut 0 décide la parité sur tous les entiers naturels : elle termine et sa réponse répond à la question posée.

Pièges de raisonnement

Un seul essai terminé ne prouve pas une propriété universelle ; il faut préciser les entrées et justifier le comportement pour chacune. Et un programme qui donnerait toujours une réponse oui/non mais bouclerait sur certains cas n’est pas un décideur, même si ses réponses obtenues sont justes : la terminaison sur tout le domaine fait partie de la définition.

Exemples

  • L’exécution qui reçoit 7, affiche « calcul fini » et s’arrête termine, mais ne décide aucune question oui/non sans réponse correspondante.
  • Le calcul du reste de n par 2 répond correctement à la question « n est-il pair ? » et termine pour tout entier naturel n.

Pièges fréquents

  • Généraliser à toutes les entrées parce qu’un seul lancement s’est arrêté confond un cas observé avec une propriété de l’algorithme.
  • Oublier la correction de la réponse réduit la décision à une simple terminaison, alors qu’un décideur doit fournir le bon oui ou non.

Et maintenant ?

Questions proches

← Toutes les questions-réponses