Qu’est-ce qu’un problème décidable en informatique ?

Réponse courte

Un problème de décision est décidable s’il existe un algorithme qui répond correctement oui ou non et termine pour chaque entrée autorisée du problème.

Comprendre

Une réponse totale et correcte

Un problème de décision demande une réponse oui ou non pour chaque entrée de son domaine. Il est décidable s’il existe un algorithme, appelé décideur, qui fournit toujours la bonne réponse et termine sur toutes ces entrées. La terminaison seule ne suffit pas : un programme qui s’arrête en donnant une réponse erronée n’est pas un décideur.

Exemples concrets

La parité d’un entier naturel est décidable : calcule son reste dans la division par 2 et réponds oui si ce reste vaut 0, sinon non. La procédure termine pour chaque entier naturel. Pour un programme particulier qui décrémente un compteur naturel jusqu’à zéro, la terminaison se prouve aussi par la mesure qui diminue ; cela ne règle toutefois que cette famille définie de programmes.

Pièges à éviter

Un test réussi sur plusieurs entrées ne démontre pas que l’algorithme répond pour toutes les entrées du domaine. De même, un programme qui répond exactement lorsqu’il termine, mais boucle sur certains cas, ne décide pas le problème : il ne fournit pas de réponse totale. Précise donc toujours les entrées autorisées avant de conclure.

Exemples

  • Pour n = 8, le reste de la division par 2 est 0 : l’algorithme répond que 8 est pair.
  • Pour n = 11, ce reste vaut 1 : la même procédure répond que 11 n’est pas pair et termine.

Pièges fréquents

  • Dire qu’un programme est un décideur parce qu’il répond correctement aux essais observés ignore les autres entrées autorisées.
  • Accepter un algorithme qui boucle sur certaines entrées oublie que le décideur doit terminer partout dans son domaine.

Et maintenant ?

Questions proches

← Toutes les questions-réponses