Problème algorithmique
On a vu que toute question n'admet pas forcément un algorithme pour le résoudre et que si on possède un algorithme il n'est pas évident de savoir ce qu'il fait. Cependant, on utilise quotidiennement des algorithmes et on se repose sur eux pour résoudre des problèmes concret.
Comment faire c eci alors que l'on a vu qu'il n'existe pas de procédure automatique pour le faire (on l'a vue, c'est le théorème de Rice) ? C'est ce qu'on va aborder ici, en deux temps :
- on va commencer par formaliser ce qu'est un problème
- se donner des outils pour prouver qu'un algorithme donné résout bien le problème posé.
Définition
Un problème est un texte composé de 3 parties :
- nom : le nom du problème
- données : les paramètres dont on a besoin
- question : ce que l'on cherche à résoudre
Par exemple :
Problème
- nom : maximum
- données : un tableau d'entiers
- question : quel est l'entier maximum du tableau ?
On se placera dans ce cours dans un cadre algorithmique : c'est à dire des problèmes qui admettent des algorithmes qui en trouve la solution (on se posera donc uniquement des questions sérieuses comme la recherche d'un éléments dans un tableau et on laissera de côté les problèmes futiles comme "quand est-ce qu'on mange ?" ou encore "quel est le sens de la vie ?"). Définissons formellement ce type de problème :
Définition
Un problème est algorithmique s'il existe un algorithme pour le résoudre, c'est à dire que cet algorithme :
- prend en paramètres les entrées du problème
- donne la réponse à la question.
Cette définition a un sens puisqu'il existe des problèmes non résoluble par un algorithme.